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$ – Joel Pereira Dec 17 '18 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$ – Saad Dec 17 '18 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$ – Saad Dec 17 '18 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 '18 at 0:48

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$ – Saad Dec 17 '18 at 22:27
  • 1
    $\begingroup$ If that's the case, you should probably ask another question for the trace property. $\endgroup$ – EuYu Dec 17 '18 at 23:32
  • $\begingroup$ Ill do just that. Hopefully it doesn't get marked a duplicate. $\endgroup$ – Saad Dec 18 '18 at 2:02

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.