8

Find a $3 \times 3 $ matrix $M$ with entries 0 and 1 only such that $M^7=I$ and $M\neq I$.

This was a short question in a recent exam. I tried with permutation matrices but couldn't find $M^{odd}=I$ except for 3.

Hu Zhengtang
  • 3,757
  • 4
    A permutation matrix has $M^6=1$ as $S_3$ has order $6$. So the only permutation matrix with $M^7=I$ is $I$. – Julien May 16 '13 at 01:55
  • Does the question or context specify the nature of the entries of the matrix - are they real numbers, or could we choose to work over a finite field? – Mark Bennet May 16 '13 at 02:08
  • 3
    This seems impossible (at least over $\mathbb{R}$). The matrix satisfies $x^7-1$ which implies that the eigenvalues lie amongst the $7$th roots of unity and the matrix is diagonalizable. This implies that the characteristic polynomial, being a real cubic, has either $3$ real roots, or one real root and a conjugate root pair. If all roots are real then we must have $1$ repeated three times as the eigenvalues, forcing $M=I$. If we have one conjugate root pair $(\omega,\ \overline{\omega})$ and a real root (again $1$) then from the trace we have $2\Re(\omega)=\text{integer}$ which is impossible. – EuYu May 16 '13 at 02:16
  • 2
    As pointed out by Mark Bennett, the trick is to work on a different coefficient ring. For instance, $M=\pmatrix{1&0&1\0&1&0\0&0&1}$ will do over $\mathbb{Z}_7$. – Julien May 16 '13 at 02:19
  • @julien I would put that as an answer. – EuYu May 16 '13 at 02:23
  • @EuYu I would put your comment as an answer, actually. Feel free to add this example. I suspect this was a tricky exam question with no solution. – Julien May 16 '13 at 02:24
  • @julien Alright then, thanks. – EuYu May 16 '13 at 02:32
  • 2
    Also, $M=\pmatrix{1&0&1\1&0&0\0&1&0}$ over $\mathbb{Z}_2$ – Josh B. May 16 '13 at 02:37

1 Answers1

6

There is no such matrix over $\mathbb{R}$. The matrix satisfies the polynomial $x^7−1$ which implies that the eigenvalues lie amongst the $7^{\text{th}}$ roots of unity and that the matrix is diagonalizable. This implies that the characteristic polynomial, being a real cubic, has either three real roots, or one real root and a conjugate root pair.

If all roots are real then we must have $1$ repeated three times as the eigenvalues. Diagonalizability then forces $M=I$.

If we have a conjugate root pair, say $\left(\omega, \overline{\omega}\right)$ and a real root (which is again $1$) then we know that $$1 + \omega + \overline{\omega} = 1 + 2\Re(\omega) = \mathrm{tr}(M)$$ But since $M$ has only $0$s and $1$s as entries this implies that the trace is integral and hence $2\Re(\omega)$ is integral. It is easy to check that this is impossible.

If you allow other fields then this is possible. As julien points out, if we work over $\mathbb{Z}/7\mathbb{Z}$ then $$M=\begin{pmatrix}1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$ is a working example.

EuYu
  • 41,421