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
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$.
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}}|$.
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}|$.