Detailed mathematical approach

Problem Summary

We must count integer \(3\times3\) matrices \(M\) whose entries lie in \([-n,n]\) and satisfy

$M^2=M.$

Such matrices are idempotent. A direct search over all \( (2n+1)^9 \) matrices is hopeless, so the solution instead uses the structure theorem for idempotents: every such matrix is a projection, and in dimension \(3\) that reduces the problem to counting lattice points on a plane.

Mathematical Approach

The implementations classify idempotent matrices by rank, express the nontrivial cases through one primitive integer direction vector and one integer linear functional, and then count the admissible integer solutions of a single equation.

Step 1: Split the problem by rank

If \(M^2=M\), then every eigenvalue \(\lambda\) satisfies \(\lambda^2=\lambda\), so \(\lambda\in\{0,1\}\). Therefore an idempotent \(3\times3\) matrix can only have rank \(0,1,2,\) or \(3\).

The extreme cases are immediate:

$\operatorname{rank}(M)=0 \Rightarrow M=0,\qquad \operatorname{rank}(M)=3 \Rightarrow M=I.$

So for positive \(n\), two matrices are already known, and the real work is to count the rank-\(1\) and rank-\(2\) cases.

Step 2: Parametrize every rank-\(1\) idempotent

Let \(M\) have rank \(1\). Its image is a one-dimensional sublattice of \(\mathbb{Z}^3\), so it is generated by a primitive integer vector \(\mathbf{p}\in\mathbb{Z}^3\). Because \(M\) is idempotent, it acts as the identity on its image, hence there exists an integer row vector \(\mathbf{w}^{T}\) such that

$M=\mathbf{p}\mathbf{w}^{T},\qquad \mathbf{w}\cdot\mathbf{p}=1.$

The primitive condition on \(\mathbf{p}\) is forced: if \(\gcd(p_1,p_2,p_3)=d>1\), then \(\mathbf{w}\cdot\mathbf{p}\) would also be divisible by \(d\), contradicting \(\mathbf{w}\cdot\mathbf{p}=1\).

Conversely, any integer pair \((\mathbf{p},\mathbf{w})\) with \(\mathbf{w}\cdot\mathbf{p}=1\) gives an idempotent, because

$\left(\mathbf{p}\mathbf{w}^{T}\right)^2=\mathbf{p}\left(\mathbf{w}\cdot\mathbf{p}\right)\mathbf{w}^{T}=\mathbf{p}\mathbf{w}^{T}.$

The pair \((\mathbf{p},\mathbf{w})\) and \((-\mathbf{p},-\mathbf{w})\) produces the same matrix, so we fix a canonical orientation by requiring the first nonzero component of \(\mathbf{p}\) to be positive.

Step 3: Parametrize every rank-\(2\) idempotent

If \(M\) has rank \(2\), then \(I-M\) is idempotent of rank \(1\). Applying the previous description to \(I-M\) yields

$M=I-\mathbf{p}\mathbf{w}^{T},\qquad \mathbf{w}\cdot\mathbf{p}=1.$

This is again a complete characterization, since

$\left(I-\mathbf{p}\mathbf{w}^{T}\right)^2=I-2\mathbf{p}\mathbf{w}^{T}+\mathbf{p}\left(\mathbf{w}\cdot\mathbf{p}\right)\mathbf{w}^{T}=I-\mathbf{p}\mathbf{w}^{T}.$

Thus both nontrivial ranks are described by the same arithmetic data; only the entry bounds are different.

Step 4: Turn the entry bounds into intervals for \(\mathbf{w}\)

Write \(\mathbf{p}=(p_1,p_2,p_3)^{T}\) and \(\mathbf{w}=(w_1,w_2,w_3)^{T}\).

For rank \(1\), every entry is \(M_{ij}=p_iw_j\), so

$|p_iw_j|\le n \qquad (1\le i,j\le 3).$

If \(P=\max(|p_1|,|p_2|,|p_3|)\), then each coordinate of \(\mathbf{w}\) must satisfy

$|w_j|\le \left\lfloor\frac{n}{P}\right\rfloor.$

So rank \(1\) is reduced to counting integer solutions of

$p_1w_1+p_2w_2+p_3w_3=1$

inside a symmetric cube.

For rank \(2\), the off-diagonal entries are \(-p_iw_j\) for \(i\ne j\). Therefore, for each column \(j\),

$|w_j|\le \left\lfloor\frac{n}{\max_{i\ne j}|p_i|}\right\rfloor$

whenever at least one of the other two coefficients is nonzero. The diagonal entries are \(1-p_jw_j\), so

$|1-p_jw_j|\le n \iff 1-n\le p_jw_j\le 1+n.$

When \(p_j\ne 0\), this becomes an explicit integer interval via floor and ceiling division. The admissible values of \(w_j\) are obtained by intersecting the diagonal and off-diagonal restrictions for each coordinate.

Step 5: Count lattice points on the plane \(\mathbf{w}\cdot\mathbf{p}=1\)

Once the three coordinate ranges are known, the problem becomes: count integer points in a rectangular box that lie on

$p_1w_1+p_2w_2+p_3w_3=1.$

When one or two coefficients vanish, the equation collapses to an easy one-variable or two-variable count. In the generic case, one coordinate is solved from the equation, the other two are enumerated inside their intervals, and the remaining coordinate is checked for integrality and for being within range.

This turns a nine-variable matrix search into a much smaller geometric counting problem on one affine plane.

Worked Example: \(n=1\) and \(\mathbf{p}=(1,0,0)^{T}\)

For rank \(1\), the equation \(\mathbf{w}\cdot\mathbf{p}=1\) becomes \(w_1=1\). The box constraints give \(|w_2|\le 1\) and \(|w_3|\le 1\), so this one primitive direction contributes

$3\cdot 3=9$

rank-\(1\) matrices.

For rank \(2\), we have \(M=I-\mathbf{p}\mathbf{w}^{T}\). The same equation still forces \(w_1=1\), the off-diagonal bounds again give \(|w_2|,|w_3|\le 1\), and the diagonal entry becomes \(1-w_1=0\), which is allowed. So the same direction contributes another \(9\) rank-\(2\) matrices.

Summing over all canonical primitive directions and then adding \(0\) and \(I\) gives \(C(1)=164\), which matches the small test value used by the implementation.

How the Code Works

The C++, Python, and Java implementations all use this rank decomposition. They begin with the trivial idempotents, enumerate all nonzero primitive direction vectors in \([-n,n]^3\) with a canonical sign choice, and for each direction count two families: rank \(1\) matrices in a symmetric cube and rank \(2\) matrices in the intersection of three coordinate intervals.

The shared core is a bounded linear Diophantine solver for

$p_1w_1+p_2w_2+p_3w_3=1.$

Special cases with zero coefficients are treated separately, while the generic case fixes one coordinate from the equation and loops over the other two. The outer enumeration is split across multiple workers, so independent slices of the primitive direction set can be counted in parallel and added safely at the end.

Complexity Analysis

The outer search box contains \(O(n^3)\) candidate direction vectors. For each surviving primitive canonical vector, the counting stage is a bounded two-dimensional scan of integer pairs, so a conservative worst-case bound is \(O(n^5)\) time. That upper bound is crude, because large coefficients make the admissible intervals much smaller and many rank-\(2\) boxes are empty or very thin. The auxiliary memory is \(O(1)\) per worker, plus a small amount of storage for partial sums.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=572
2. Idempotent matrix: Wikipedia — Idempotent matrix
3. Projection (linear algebra): Wikipedia — Projection (linear algebra)
4. Linear Diophantine equation: Wikipedia — Linear Diophantine equation
5. Rank-nullity theorem: Wikipedia — Rank-nullity theorem