# Find the number of square matrices A of size n over the field $\mathbb F_p$ of $p$ elements such that $A^p = A$.

A question from entrance test of PRIMES 2016, namely M3.

The solution says:

The matrix has eigenvalues $0, 1, ...., p-1$ with eigenspaces of dimension $n_0, n_1, ...n_{p-1}$. The group $GL_n(\mathbb F_p)$ acts on such arrangements transitively, with the stabilizer $GL_{n_0}(\mathbb F_p) \times GL_{n_1}(\mathbb F_p) \times ..... \times Gl_{n_{p-1}}(\mathbb F_p)$. So the number of matrices is : $$\sum_{{n_0},...,{n_{p-1}}:\sum n_i =n} \frac{\prod_{j=0}^{n-1} (p^n - p^j)}{\prod_{i=0}^{p-1} \prod_{j=0}^{n_i -1} (p^{n_i -1} -p^j)}$$

So, could anybody help me understand why is the product of bunch of general linear group $GL_{n_0}(\mathbb F_p) \times GL_{n_1}(\mathbb F_p) \times ..... \times Gl_{n_{p-1}}(\mathbb F_p)$ the stabilizer? And I can't really see the importance of eigenspace here in this proof..

Besides, what is it summing there... it's $\sum n_i =n$ in the right corner under that bigger sigma in case that equal sign is not clear.

• What it is summing is clear: the dimensions $n_i$ of eigenspaces might not be fixed, so we sum over all possible dimensions $\sum n_i=n.$ Also I think that stabilizer just means that it maps every eigen-space to itself, so that it becomes a product of endomorphisms of eigen-spaces (actually they are automorphisms, so we get a lot of $\operatorname{GL}.$) – awllower Jul 6 '16 at 2:11
• @awllower , but how do you guarantee $\sum n_i =n$? Isn't the sum of eigenvalues the sum of elements on the diagonal? And you mean each general linear group maps every eigenspace with corresponding dimension to itself? How so? – user330984 Jul 6 '16 at 9:04
• These $n_i$ are not eigenvalues, but dimensions of the eigen-spaces. As to the latter question, I mean that an automorphism of a space of dimension $n_i$ is in $\operatorname{GL}_{n_i}.$ – awllower Jul 6 '16 at 9:07
• Besides, if we need to sum over all possible $n_i$, shouldn't there be a $n_i$ not mentioned in by any sigma or pi? I mean, wasn't all possible dimension already covered in the prodution in denominator? Why do we need to sum that again? – user330984 Jul 6 '16 at 9:10
• The product in the denominator just counts the cardinality of $GL_{n_0}(\mathbb F_p) \times GL_{n_1}(\mathbb F_p) \times ..... \times Gl_{n_{p-1}}(\mathbb F_p)$ for a fixed set of dimensions $n_i.$ – awllower Jul 6 '16 at 9:13

Part of the argument is that $A$ is diagonalizable (with eigenvalues in $\mathbb F_p$). One way to see this is using the following identity in the ring of polynomials $\mathbb F_p[x]$: $$\prod_{a\in\mathbb F_p}(x-a)=x^p-x.$$ It follows that $$\prod_{a\in\mathbb F_p}(A-aI_n)=0.$$ This implies that $$\mathbb F_p^n=\bigoplus_{a\in\mathbb F_p}V_a$$ where $V_a=\ker(A-aI_n)$ is the $a$-eigenspace of $A$. Since $A$ acts as $a$ on $V_a$, $A$ is determined by the spaces $V_0,\ldots,V_{p-1}$. So the formula is counting the number of such sequences of subspaces. The sum is over the possible dimensions of the subspaces.
• @user330984 By substituting $A$ for $x$. Formally for any element $r$ in an $\mathbb F_p$-algebra $R$, there is an $\mathbb F_p$-algebra homomorphism $\mathrm{eval}_r:\mathbb F_p[x]\rightarrow R$ sending $x$ to $r$. I applied $\mathrm{eval}_A$ to the first equation. – stewbasic Jul 6 '16 at 22:01