We work with $A'$, the matrix with entries $a_{ij}\mod 3$. Note that cubing $A'$ still gives $I$ as $I$ is unchanged by considering remainders $\mod 3$. For the rest of the proof, we will not differentiate between $A$ and $A'$. The minimal polynomial of $A$ divides $x^{3} - 1$ so each eigenvalue $\lambda$ of $A$ satisfies $\lambda^{3} = 1$. The trace of $A^3$ is clearly just $n$ as $A^3 = I$.

Next, note that for integers $a_1, ...., a_n$ we have that $(a_1 +... + a_n)^k = a_1^{k} + a_2^{k} ... + a_n^{k}\mod k$.

Now this is where I am stuck. I would like to say that this implies $\operatorname{tr}(A)^3 =\operatorname{tr}(A^3)$, but why is it that $\operatorname{tr}(A^3)$ is the sum of the cubed diagonal entries of $A$? I can only say that $\operatorname{tr}(A^3)$ is the sum of the cubed eigenvalues of $A$, but these eigenvalues need not be integers so the argument fails.

If I am able to prove this, then the result follows since I have $a^3 = a\mod 3$ for all $a$ in $\{0,1,2\}$.

Edit: I can confirm that my proof does work since $\operatorname{tr}(A)^p = \operatorname{tr}(A^p)\mod p$ for prime $p$ as said here https://rjlipton.wordpress.com/2009/08/07/fermats-little-theorem-for-matrices/

But I can't find the proof for this statement itself.

  • $\begingroup$ It might be easier to use the fact that A$^3$ - I = 0 and get the Jordan canonical form of A to see the types of ways the trace of A can be computed. $\endgroup$ Dec 17, 2018 at 21:25
  • $\begingroup$ I'd like a solution where I do not have to mess around with the roots of unity; my instructor said all I need to know about the eigenvalues is that they give $1$ when cubed & nothing else. If I do compute the roots of unity & analyze what the trace can be, things become much easier since $A$ is in fact diagonalizable. $\endgroup$
    – John
    Dec 17, 2018 at 21:27
  • $\begingroup$ @qbert I don't think it matters if we consider the original matrix as a matrix with complex coefficients & then diagonalize. The trace is the same as for the diagonal matrix, so we essentially have a diagonal matrix $D$ such that $D^3 = I$ and each entry of $D$ is a 3rd root of unity. We get a total trace of $n-3k$ where $k$ is the number of entries which are equal to $w$, where $w$ is one of the non-trivial roots of unity, so the trace is $n$ $mod$ $3$ $\endgroup$
    – John
    Dec 17, 2018 at 21:45
  • 1
    $\begingroup$ @Saad: You can use a Newton identity (see en.wikipedia.org/wiki/Newton%27s_identities, Expressing power sums in terms of elementary symmetric polynomials) to write $\operatorname{tr}(A^3) = \operatorname{tr}(A)^3 - 3e_2 e_1 + 3e_3$ where the $e_i$ are (up to sign) the coefficients in the characteristic polynomial of $A$ so they are integer. This presumably generalizes to arbitrary $p$ if you can show the coefficients are divisible by $p$. $\endgroup$
    – levap
    Dec 18, 2018 at 0:48

1 Answer 1


Here's one solution, although I'm not sure if it's the one your instructor had in mind.

We know the minimal polynomial of $A$ must divide $x^3 - 1$. That means the irreducible factors of the characteristic polynomial are $x-1$ and $x^2+x+1$. Therefore we know that the characteristic polynomial $p$ of $A$ must be of the form $$p(x) = (x-1)^a(x^2+x+1)^b,$$ where $a$ and $b$ are integers such that $a+2b = n$. The trace of $A$ is the negative coefficient of $x^{n-1}$. But we have $$(x-1)^a = x^a - ax^{a-1} + O(x^{a-2}),$$ and $$(x^2+x+1)^b = x^{2b} + bx^{2b-1} + O(x^{2b-2}),$$ and therefore we have $$p(x) = x^n + (b-a)x^{n-1} + O(x^{n-2}).$$ It follows that the trace of $A$ is given by $$\mathrm{tr}(A) = a-b.$$ This is equivalent modulo $3$ to $a+2b = n$, as required.

  • $\begingroup$ That's a cool way to do it which avoids messing around with the complex roots themselves, but one still has to factor $x^3 - 1$. I'm looking for (essentially) a proof that the trace of a matrix to a prime power is the trace to that prime power working mod p. $\endgroup$
    – John
    Dec 17, 2018 at 22:27
  • 1
    $\begingroup$ If that's the case, you should probably ask another question for the trace property. $\endgroup$
    – EuYu
    Dec 17, 2018 at 23:32
  • $\begingroup$ Ill do just that. Hopefully it doesn't get marked a duplicate. $\endgroup$
    – John
    Dec 18, 2018 at 2:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .