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](http://halgebra.math.msu.su/Olympiad/2007/)).
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.



The sum of same powers of all matrices modulo p
[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
$$


