# If $A$ is an $n$ by $n$ integer matrix such that $A^3 = I$, then $\operatorname{tr}(A) = n\mod3$

Attempt:

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.

• 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. – Joel Pereira Dec 17 '18 at 21:25
• 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. – Saad Dec 17 '18 at 21:27
• @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$ – Saad Dec 17 '18 at 21:45
• @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$. – levap Dec 18 '18 at 0:48

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.
• 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. – Saad Dec 17 '18 at 22:27