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.

  • $\begingroup$ 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}.$) $\endgroup$ – awllower Jul 6 '16 at 2:11
  • $\begingroup$ @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? $\endgroup$ – user330984 Jul 6 '16 at 9:04
  • $\begingroup$ 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}.$ $\endgroup$ – awllower Jul 6 '16 at 9:07
  • $\begingroup$ 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? $\endgroup$ – user330984 Jul 6 '16 at 9:10
  • $\begingroup$ 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.$ $\endgroup$ – 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.

  • $\begingroup$ ehh, how did you derive the second formula from the first one? $\endgroup$ – user330984 Jul 6 '16 at 9:59
  • $\begingroup$ @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. $\endgroup$ – stewbasic Jul 6 '16 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.