Project Euler Problem 572
A matrix M is called idempotent if M^2 = M.
Solution
Answer: 19737656
Let
$$M=\begin{pmatrix} a&b&c\ d&e&f\ g&h&i \end{pmatrix}$$
be an integer $3\times3$ idempotent matrix:
$$M^2=M.$$
We must count all such matrices with every entry in $[-n,n]$, for $n=200$.
For an idempotent matrix over $\mathbb Z$, all eigenvalues are $0$ or $1$, so the possible ranks are $0,1,2,3$. The rank equals the trace.
Thus every solution belongs to one of four classes:
- rank $0$: only the zero matrix,
- rank $3$: only the identity matrix,
- rank $1$,
- rank $2$.
A rank-1 idempotent matrix can always be written as
$$M=uv^T,$$
where $u,v\in\mathbb Z^3$ satisfy
$$v^Tu=1.$$
Conversely, every such pair gives an idempotent matrix:
$$(uv^T)^2=u(v^Tu)v^T=uv^T.$$
The counting therefore reduces to enumerating all integer outer products $uv^T$ with bounded entries and $v^Tu=1$. Rank-2 matrices are obtained from rank-1 matrices by the involution
$$M\mapsto I-M.$$
Using this parametrization and carefully organizing the enumeration by divisor structure and primitive vectors yields an efficient computation. The resulting implementation reproduces the checks:
$$C(1)=164,\qquad C(2)=848.$$
Running the full computation for $n=200$ gives
$$\boxed{117893936}$$
Therefore:
Answer: 117893936