Let $p$ be a prime number. For any $\sigma \in S_p$ (the permutation group of $\{1,2,...,p \}),$ define the matrix $A_{\sigma}=(a_{ij}) \in \mathcal{M}_p(\mathbb{Z})$ as $a_{ij} = \sigma^{i-1}(j),$ where $\sigma^0$ is the identity permutation and $\sigma^k = \underbrace{\sigma \circ \sigma \circ ... \circ \sigma}_k.$ Prove that $D = \{ |\det A_{\sigma}| : \sigma \in S_p \}$ has at most $1+ (p-2)!$ elements.
Problem
Source: Romanian National Olympiad 2019 - Grade 11 - Problem 4
Tags: prime numbers, group theory, linear algebra, matrix, permutations
SAUDITYA
26.04.2019 09:12
Cute! First we see that if the cyclic decomposition $\sigma$ has more than one cycle then $\det A_{\sigma}=0$.
Consider $a,b \in \{1,2,\cdots,p\}$ belonging to different cycles. Now add the rows beginning with orbits of $a$ and $b$ to the row beginning with $a$ and $b$ respectively. See that row $a$ and $b$ are linear multiples of each other.
So we will work with cyclic permutations in $S_p$. Lemma: if $ \sigma$ is a cyclic permutation then so is $\sigma^k$ , $\forall k =\{1,2,\cdots,p-1\}$.Moreover ${\sigma^k}$ are all distinct. Proof: See that $\sigma^k(1)$ are all distinct for $k = \{1,2,\cdots,p-1\}$.Now fix a $k \in \{1,2,\cdots,p-1\}$.see that if $\sigma^{kj}(1) =1 => \sigma^{kj \mod p}(1) =1 => kj \equiv 0 \mod p => p|j$. See that $|A_{\sigma}| = |A_{\sigma^{k}}|$.
Let $\omega$ be a primitive $p$ -root of unity.See that by using circulant matrix formula $|\det {A_{\sigma}}| = |\prod_{i=0}^{p-1}(\sum_{j=0}^{p-1} \sigma^{j}(1)\omega^{ij})$.Now, $\sum_{j=0}^{p-1} \sigma^{jk}(1)\omega^{ijk} = \sum_{j=0}^{p-1} \sigma^{j}(1)\omega^{ij}$.So , $|A_{\sigma}| = |A_{\sigma^{k}}|$.
So we have partitioned the set of cyclic permutation into sets of size $p-1$ having same value of $|A_{\sigma}|$ so we have atmost $1+ \frac{(p-1)!}{(p-1)} = 1+ (p-2)!$ values of $|A_{\sigma}|$.