# The sum of same powers of all matrices modulo p

The following is a problem from our department algebra competition for students:

Non-question. An experimental-math geek was trying to raise all matrices $17\times17$ over the field with 17 elements to the power of 100, sum the returns, and observe the result, when his computer broke. Help him.

Probably, the most of us can calculate the sum without use of computer (alternatively, Russian readers can find a solution here). The problem seems to become much harder when we replace 100 by, say, 80. More generally, my question is the following:

Question. What is the sum $$> \sum_{A\in M_p(\mathbb F_p)}A^k, >$$ where $p$ is prime and $k$ is a multiple of $p-1$?

It is easy to show that the sum is a scalar matrix, but which one? Note that the coincidence of the matrix size and the characteristic makes trace useless.

• Why $p \times p$ matrices and not another size? Apr 7, 2013 at 20:51
• The top left element of $\left( \begin{array}{cc} a & b \\ c & d \end{array}\right)^k$ has the form $\sum_{i=0}^k \sum_{j=0}^{\frac{i-k}{2}} \left(\begin{array}{c} i+j \\ j \end{array} \right) \left(\begin{array}{c} k-i-j-1 \\ j-1 \end{array} \right) a^i b^j c^j d^{k-i-2j}$ If we sum over all matrices, the monomial terms become $0$ unless $i,k,k-i-2j$ are all positive multiples of $p-1$ and $1$ if they are. So we just get a combinatoric sum mod $p$. But the combinatorics seem really hard in general already for the $2 \times 2$ case. Apr 7, 2013 at 22:15
• Will, if the size is not a multiple of the characteristic, it suffice to evaluate the sum of traces. because the sum in question is, clearly, a scalar matrix. But I argee that the problem seems non-trivial for any sizes. The case where size $=p$ is just an additional difficulty. Apr 8, 2013 at 9:52
• One may ask the following question as well. Let $\Omega$ be an adjoint orbit of ${\rm GL(p,{\mathbb F}_p)$ in ${\rm M}(p,{\mathbb F}_p)$ and $k$ be a positive integer. Then $$\sum_{A\in \Omega} A^k$$ is a scalar matrix $\lambda (\Omega )I_p$. Can one find the scalar $\lambda (\Omega )$ ? Apr 10, 2013 at 5:59

[corrections applied, per Ilya and Anton]

Consider the formal series $$f(x) = \sum_{k=0}^\infty (\sum_A A^k) x^k$$ where $A$ runs through $p \times p$ matrices. It is equal to $\sum_A (I - Ax)^{-1}$, a rational function with values in scalar matrices. Thus, for some $d$, if the first $d$ coefficients vanish all coefficients must vanish.

To determine $d$, we need to bound the degree of the numerator and denominator of $f(x)$. Note by Cramer's rule, each $(I - Ax)^{-1}$ is a matrix of degree $(p-1)$ polynomials divided by the degree $p$ determinant of $(I - Ax)$.

There are $p^p$ different denominators, i.e. polynomials of the form $$\det(I - Ax) = c_p x^p + c_{p-1} x^{p-1} + \cdots + c_1 x + 1$$ The $c_i$ are unconstrained, they appear at least once in case $A$ is the companion matrix with $-c_p,-c_{p-1},\ldots$ along the last column. So we can write the sum as $$\sum_{c_p,\ldots,c_1} \frac{\text{something of degree p-1}}{c_p x^p + \cdots + c_1 x + 1}$$ There are $(p-1)$ linear denominators, $p (p-1)$ quadratic denominators, $p^2 (p-1)$ cubic denominators and so on, so the product of all the $c_p x^p + \cdots + 1$ has degree $$d = (p-1) + 2p(p-1) + 3p^2(p-1) + \cdots + p p^{p-1}(p-1)$$ i.e. $d = p^{p+1} - \frac{p^p - 1}{p - 1}$. So $f(x)$ is a polynomial of degree less than $d$ divided by a polynomial of degree $d$.

Ilya's answer shows that the first $p^{p+1} - p$ Taylor coefficients of $f(x)$ vanish, and when $p \geq 3$ this is larger than $d$ so all the remaining Taylor coefficients are vanish as well. When $p = 2$ Will points out the sums are not always zero, in fact for $p=2$ $$f(x) = \frac{x^5}{(x+1)^2 (x^2 + x + 1)} I$$

• The approach is interesting. But it seems that you think there are $p^3$ matrices; in fact, there are $p^{p^2}$ of them. But you do not need so much, since there are less than $p^p$ distinct denominators (all costant terms are ones). This gives the estimate of about $2p^{p+1}$ coefficients to check. Unfortunately, now we have a half of this amount. Apr 9, 2013 at 4:50
• Oh! - Apr 9, 2013 at 5:42
• ya-tayr, Ilya, I am not sure I understand. Should "determinant of $A$" read "determinant of $I-Ax$"? If so, there are exactly $p^{p-1}$ different denominators: they are just polynonomials reciprocal to characteristic polynomials of all matrices (= all unitary polynomials of degree $p$). Apr 9, 2013 at 6:45
• ... and it is easy to find the LCM of all unitary polynomials of degree $p$. Apr 9, 2013 at 7:01
• Matthieu, the solution goes as follows: Ilya showed that the sum in question vanishes for sufficiently small $k$; then ya-tayr showed that if the sum vanishes for all sufficiently large $k$, than it vanishes always; when these bounds have met, "we're done!". This is all right, but honestly I hoped for a simpler solution. ---- Thanks, ya-tayr, Ilya, Will, and everybody involved! Apr 11, 2013 at 8:19

The sum is zero for all $k<p^2-1$.

Assume that $k$ is a multiple of $p-1$ and $k<p^2-1$. Divide all matrices into classes of the form $\{A,A+1,A+2,\dots,A+(p-1)\}$ . Summimg the $k$th powers over such a class yields $$\sum_{s=0}^k A^{k-s}\binom ks \sum_{j=0}^{p-1} j^s$$ where $0^0=1$. If $s=0$ or $s$ is not a multiple of $p-1$, the inner sum is 0 mod $p$. If $s$ is a multiple of $p-1$ and $s<k$, then the binomial coefficient is 0 mod $p$. (This is what breaks for $k=p^2-1$.) The only remaining term is the one $s=k$ and it does not depend on $A$. So the sum over a class is the same for all classes. The number of classes is a multiple of $p$, hence the result.

• Wonderfully clear! Apr 7, 2013 at 22:14
• Since the formal series $f(x) = \sum_k \sum_A A^k x^k = \sum_A (I - Ax)^{-1}$ doesn't change if you replace the summand by $(I - (A+I)x)^{-1}$, the series satisfies $f(x) = (1-x) f(x/(1-x))$, which is a little bit like being a modular form of weight 1. Apr 8, 2013 at 0:16

These are just several thoughts. but it seems that they show in particular that the answr is $0$ for $k< p^p-1$.

$\def\FF{{\mathbb F}}$ 1. Firstly, denoting $d=\mathop{\rm lcm}(p-1,p^2-1,\dots,p^p-1)$ we see that $A^{pd+p}=A^p$ for every matrix $A$ (the order of a semisimple component divides $d$, and we need $p$ in order for a nilpotent component to vanish). Thus we may assume that $k < pd+p$.

2. Your sum is equal to $$S=\sum_{a_{11}\in\FF_p} \dots\sum_{a_{pp}\in\FF_p} \left(\sum_{i=1}^p\sum_{j=1}^p a_{ij}E_{ij}\right)^k,$$ Now expand the inner brackets; we obtain $$S=\sum_J \left(\sum_{a_{11}\in\FF_p} \dots\sum_{a_{pp}\in\FF_p} a^J\right)M_J,$$ where the outer summation is taken over some multiindices $J$ with $|J|=k$, and $M_J$ are some matrices. The summation in brackets over $a_{ij}$ gives zero unless the exponent of $a_{ij}$ is nonzero and divisible by $p-1$. Thus the sum in the brackets vanishes unless all the coordinates of $J$ are nonzero and divisible by $p-1$. So, if $k < p^2(p-1)$ then $S=0$, as is in the case $k=80$ and $p=17$.

3. For the remaining case, we need to calculate $M_J$. Assume that $J=(j_{11},\dots,j_{pp})$ (all $j$'s are multiples of $p-1$). Consider a digraph $G_J$ with $\FF_p$ as the set of vertices and $j_{k\ell}$ edges from $k$ to $\ell$. Now, if $M_J=[m_{k\ell}]$ then $m_{kk}$ is the number of Eulerian paths starting at $k$ (multiplies by the sum in brackets which is $-1$), and all other entries are zeroes.

Now let us show that the number of such cycles is divisible by $p$. We will assume that $k=1$, so that the cycles start and end at $1$. Split each cycle into subcycles starting at $1$, ending at $1$ and not passing through $1$ any more. Correspond to each cycle all the cycles obtained by permutatons of subcycles; thus the set of all cycles is partitioned into such equivalence classes, and the number of elements in each class is a corresponding multinomial coefficient $\binom{s}{s_1,\dots,s_t}$ where $s_1,\dots,s_t$ are the numbers of occurences of different subcycles. This coefficient is divisible by $p$ unless in the $p$-adic notation there are no transitions in the addition $s_1+\dots+s_t=k$.

Notice that there are at least $p$ distinct subcycles --- at least one starting from each of the edges $1\to 1$, $1\to 2$, \dots, $1\to p$. Moreover, we may partition all the subcycles into such classes --- the number in each will be divisible by $p-1$. THus, we have $p$ nonzero numbers divisble by $p-1$, and there shpuld be no transitions in addition of these $p$ numbers; this may happen only if $k\geq (p-1)+p(p-1)+\dots+p^{p-1}(p-1)=p^p-1$. So, for $k< p^p-1$ we definitely have $S=0$.

EDIT. Below in the comments, several improvements of this bound are shown.

• For p = 3, k = 26, the sage command sum([m^26 for m in MatrixSpace(GF(3),3,3)]) also returns the 0 matrix. Apr 7, 2013 at 20:56
• Does it remain for larger $k$? Apr 7, 2013 at 21:05
• You can go further. You've shown that the number of subcycles is at least $p^p-1$. But $k$ is certainly larger than the number of subcycles. In fact, I think the same logic shows that the number coming out of $2$, the number coming out of $3$, and so on, are all at least $p^p-1$. So you get $p^{p+1} -p$. Or for $d\times d$ matrices, $p^{d+1}-p$. Apr 7, 2013 at 21:15
• Replace 26 by 78,80,82,84, or 340 and sage still returns 0. Apr 7, 2013 at 21:24
• The command sum([m^6 for m in MatrixSpace(GF(2),2,2)]) returns the identity matrix. As does m^7. This completely solves $p=2$. Apr 7, 2013 at 21:37