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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Gesucht ist die Anzahl ganzzahliger \(3\times3\)-Matrizen \(M\) mit Einträgen in \([-n,n]\), die
$$M^2=M$$
erfüllen. Solche Matrizen sind idempotent. Eine direkte Durchmusterung aller \( (2n+1)^9 \) Matrizen ist völlig unpraktisch, daher nutzt die Lösung die Struktur idempotenter Abbildungen: Jede solche Matrix ist eine Projektion, und in Dimension \(3\) führt das auf ein Gitterpunktproblem auf einer Ebene.
Die Implementierungen prüfen Matrizen nicht Eintrag für Eintrag, sondern zerlegen alle idempotenten Matrizen nach ihrem Rang. Die nichttrivialen Fälle lassen sich durch einen primitiven ganzzahligen Richtungsvektor und ein lineares Funktional beschreiben.
Aus \(M^2=M\) folgt für jeden Eigenwert \(\lambda\) die Gleichung \(\lambda^2=\lambda\), also \(\lambda\in\{0,1\}\). Deshalb kann eine idempotente \(3\times3\)-Matrix nur Rang \(0,1,2\) oder \(3\) haben.
Die Extremfälle sind sofort klar:
$$\operatorname{rank}(M)=0 \Rightarrow M=0,\qquad \operatorname{rank}(M)=3 \Rightarrow M=I.$$
Für positives \(n\) sind damit zwei Matrizen bereits bekannt; gezählt werden müssen nur noch die Fälle Rang \(1\) und Rang \(2\).
Sei \(M\) von Rang \(1\). Dann ist das Bild von \(M\) ein eindimensionales Untergitter von \(\mathbb{Z}^3\) und wird von einem primitiven Vektor \(\mathbf{p}\in\mathbb{Z}^3\) erzeugt. Weil \(M\) auf seinem Bild als Identität wirkt, existiert ein ganzzahliger Zeilenvektor \(\mathbf{w}^{T}\) mit
$$M=\mathbf{p}\mathbf{w}^{T},\qquad \mathbf{w}\cdot\mathbf{p}=1.$$
Die Primitivität von \(\mathbf{p}\) ist zwingend: Wären alle Komponenten durch \(d>1\) teilbar, dann wäre auch \(\mathbf{w}\cdot\mathbf{p}\) durch \(d\) teilbar, im Widerspruch zu \(\mathbf{w}\cdot\mathbf{p}=1\).
Umgekehrt liefert jedes ganzzahlige Paar \((\mathbf{p},\mathbf{w})\) mit \(\mathbf{w}\cdot\mathbf{p}=1\) tatsächlich ein Idempotent, denn
$$\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}.$$
Die Paare \((\mathbf{p},\mathbf{w})\) und \((-\mathbf{p},-\mathbf{w})\) erzeugen dieselbe Matrix. Deshalb wird die Vorzeichenfreiheit beseitigt, indem die erste von null verschiedene Komponente von \(\mathbf{p}\) positiv verlangt wird.
Hat \(M\) Rang \(2\), dann ist \(I-M\) ein idempotentes Element vom Rang \(1\). Mit der vorherigen Beschreibung erhält man daher
$$M=I-\mathbf{p}\mathbf{w}^{T},\qquad \mathbf{w}\cdot\mathbf{p}=1.$$
Auch das ist genau die richtige Form, denn
$$\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}.$$
Damit werden beide nichttrivialen Ränge durch dieselben arithmetischen Daten beschrieben; nur die Schranken für die Matrixeinträge unterscheiden sich.
Schreibe \(\mathbf{p}=(p_1,p_2,p_3)^{T}\) und \(\mathbf{w}=(w_1,w_2,w_3)^{T}\).
Für Rang \(1\) gilt \(M_{ij}=p_iw_j\), also
$$|p_iw_j|\le n \qquad (1\le i,j\le 3).$$
Mit \(P=\max(|p_1|,|p_2|,|p_3|)\) folgt für jede Koordinate
$$|w_j|\le \left\lfloor\frac{n}{P}\right\rfloor.$$
Rang \(1\) reduziert sich damit auf das Zählen ganzzahliger Lösungen von
$$p_1w_1+p_2w_2+p_3w_3=1$$
in einem symmetrischen Würfel.
Für Rang \(2\) sind die Nebendiagonaleinträge \(-p_iw_j\) mit \(i\ne j\). Daher gilt für jede Spalte \(j\)
$$|w_j|\le \left\lfloor\frac{n}{\max_{i\ne j}|p_i|}\right\rfloor$$
sofern mindestens einer der beiden anderen Koeffizienten ungleich null ist. Die Diagonaleinträge sind \(1-p_jw_j\), also
$$|1-p_jw_j|\le n \iff 1-n\le p_jw_j\le 1+n.$$
Für \(p_j\ne 0\) ergibt das mit Abrundungs- und Aufrundungsdivision ein explizites ganzzahliges Intervall. Zulässig sind genau die Werte von \(w_j\), die sowohl die Diagonal- als auch die Nebendiagonalbedingungen erfüllen.
Sobald die drei Koordinatenintervalle feststehen, bleibt nur noch die Aufgabe, ganzzahlige Punkte in einem Quader zu zählen, die auf
$$p_1w_1+p_2w_2+p_3w_3=1$$
liegen. Falls ein oder zwei Koeffizienten verschwinden, vereinfacht sich das zu einer eindimensionalen oder zweidimensionalen Zählung. Im allgemeinen Fall wird eine Koordinate aus der Gleichung bestimmt, die beiden anderen werden innerhalb ihrer Intervalle durchlaufen, und die dritte Koordinate wird auf Ganzzahligkeit und Schranken geprüft.
So wird eine Suche über neun Matrixeinträge auf ein deutlich kleineres Gitterpunktproblem auf einer affinen Ebene reduziert.
Für Rang \(1\) wird aus \(\mathbf{w}\cdot\mathbf{p}=1\) einfach \(w_1=1\). Die Boxbedingungen liefern \(|w_2|\le 1\) und \(|w_3|\le 1\). Dieser eine primitive Richtungsvektor trägt also
$$3\cdot 3=9$$
Matrizen vom Rang \(1\) bei.
Für Rang \(2\) gilt \(M=I-\mathbf{p}\mathbf{w}^{T}\). Wieder erzwingt die Gleichung \(w_1=1\), die Nebendiagonale liefert erneut \(|w_2|,|w_3|\le 1\), und der Diagonaleintrag \(1-w_1=0\) ist zulässig. Daher entstehen aus demselben Richtungsvektor noch einmal \(9\) Matrizen vom Rang \(2\).
Wenn man über alle kanonischen primitiven Richtungen summiert und anschließend \(0\) und \(I\) addiert, erhält man \(C(1)=164\). Dieser Wert stimmt mit dem kleinen Test der Implementierung überein.
Die C++-, Python- und Java-Implementierungen verwenden alle dieselbe Rangzerlegung. Zunächst werden die trivialen Idempotenten gezählt. Danach werden alle von null verschiedenen primitiven Richtungsvektoren in \([-n,n]^3\) mit kanonischem Vorzeichen durchlaufen. Für jeden solchen Vektor werden zwei Familien gezählt: Rang-\(1\)-Matrizen in einem symmetrischen Würfel und Rang-\(2\)-Matrizen im Schnitt dreier Koordinatenintervalle.
Der gemeinsame Kern ist ein beschränkter Löser für die lineare diophantische Gleichung
$$p_1w_1+p_2w_2+p_3w_3=1.$$
Sonderfälle mit verschwindenden Koeffizienten werden direkt behandelt. Im allgemeinen Fall wird eine Koordinate aus der Gleichung bestimmt und über die beiden anderen iteriert. Die äußere Enumeration wird auf mehrere Arbeitsbereiche verteilt, sodass unabhängige Teilmengen der primitiven Richtungen parallel gezählt und am Ende aufsummiert werden können.
Die äußere Suchbox enthält \(O(n^3)\) Kandidaten für Richtungsvektoren. Für jeden überlebenden primitiven kanonischen Vektor ist der innere Schritt eine beschränkte zweidimensionale Durchmusterung von ganzzahligen Paaren. Eine konservative obere Schranke ist daher \(O(n^5)\) Zeit. Diese Schranke ist grob, denn große Koeffizienten verkleinern die zulässigen Intervalle stark, und viele Rang-\(2\)-Boxen sind leer oder sehr schmal. Der Zusatzspeicher beträgt \(O(1)\) pro Arbeitsbereich, zuzüglich weniger Teilsummen für die Parallelakkumulation.
Aranan şey, tüm elemanları \([-n,n]\) aralığında olan ve
$$M^2=M$$
koşulunu sağlayan tamsayı \(3\times3\) matrislerin sayısıdır. Böyle matrisler idempotenttir. Tüm \( (2n+1)^9 \) matrisi tek tek denemek mümkün olmadığı için çözüm, idempotent matrislerin birer projeksiyon olması gerçeğini kullanır ve sayımı bir düzlem üzerindeki kafes noktalarına indirger.
Uygulamalar, matrisi doğrudan dokuz giriş üzerinden taramak yerine idempotent matrisleri ranklarına göre ayırır. Rank \(1\) ve rank \(2\) durumları, bir primitif tamsayı yön vektörü ile bir tamsayı lineer fonksiyonel üzerinden tam olarak ifade edilir.
\(M^2=M\) olduğunda her özdeğer \(\lambda\), \(\lambda^2=\lambda\) denklemini sağlar; dolayısıyla \(\lambda\in\{0,1\}\) olur. Bu yüzden idempotent bir \(3\times3\) matrisin rankı yalnızca \(0,1,2\) veya \(3\) olabilir.
Uç durumlar hemen bulunur:
$$\operatorname{rank}(M)=0 \Rightarrow M=0,\qquad \operatorname{rank}(M)=3 \Rightarrow M=I.$$
Böylece pozitif \(n\) için iki matris en baştan bellidir; asıl sayılması gerekenler rank \(1\) ve rank \(2\) durumlarıdır.
\(M\) rank \(1\) olsun. O zaman \(M\)'nin görüntüsü \(\mathbb{Z}^3\) içinde bir boyutlu bir altörgüdür ve bunu \(\mathbf{p}\in\mathbb{Z}^3\) biçiminde primitif bir vektör üretir. \(M\) idempotent olduğu için kendi görüntüsü üzerinde özdeşlik gibi davranır; bu nedenle bir tamsayı satır vektörü \(\mathbf{w}^{T}\) vardır ve
$$M=\mathbf{p}\mathbf{w}^{T},\qquad \mathbf{w}\cdot\mathbf{p}=1.$$
\(\mathbf{p}\)'nin primitif olması zorunludur. Eğer \(\gcd(p_1,p_2,p_3)=d>1\) olsaydı, \(\mathbf{w}\cdot\mathbf{p}\) de \(d\)'ye bölünürdü; bu ise \(\mathbf{w}\cdot\mathbf{p}=1\) ile çelişir.
Tersi yönde, \(\mathbf{w}\cdot\mathbf{p}=1\) sağlayan her tamsayı çifti gerçekten idempotent üretir, çünkü
$$\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}.$$
\((\mathbf{p},\mathbf{w})\) ile \((-\mathbf{p},-\mathbf{w})\) aynı matrisi verdiği için işaret tekrarını önlemek amacıyla \(\mathbf{p}\)'nin ilk sıfır olmayan bileşeninin pozitif olması şartı konur.
\(M\) rank \(2\) ise \(I-M\) rank \(1\) ve yine idempotenttir. Bu nedenle önceki biçim doğrudan
$$M=I-\mathbf{p}\mathbf{w}^{T},\qquad \mathbf{w}\cdot\mathbf{p}=1$$
şeklini verir. Bunun gerçekten yeterli olduğunu görmek için
$$\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}$$
hesabı yeterlidir. Yani rank \(1\) ve rank \(2\) aynı aritmetik veriyle tanımlanır; fark yalnızca eleman sınırlarındadır.
\(\mathbf{p}=(p_1,p_2,p_3)^{T}\) ve \(\mathbf{w}=(w_1,w_2,w_3)^{T}\) yazalım.
Rank \(1\) için her giriş \(M_{ij}=p_iw_j\) olduğundan
$$|p_iw_j|\le n \qquad (1\le i,j\le 3).$$
\(P=\max(|p_1|,|p_2|,|p_3|)\) dersek her koordinat için
$$|w_j|\le \left\lfloor\frac{n}{P}\right\rfloor$$
elde edilir. Böylece rank \(1\), simetrik bir küp içindeki
$$p_1w_1+p_2w_2+p_3w_3=1$$
denklemine ait tamsayı çözümleri sayma problemine dönüşür.
Rank \(2\)'de köşegen dışı girişler \(i\ne j\) için \(-p_iw_j\) olur. Bu yüzden her sütun \(j\) için, diğer iki katsayıdan en az biri sıfır değilse,
$$|w_j|\le \left\lfloor\frac{n}{\max_{i\ne j}|p_i|}\right\rfloor$$
sınırı gelir. Köşegen girişler \(1-p_jw_j\) olduğundan
$$|1-p_jw_j|\le n \iff 1-n\le p_jw_j\le 1+n.$$
\(p_j\ne 0\) ise bu ifade taban ve tavan bölmeleriyle açık bir tamsayı aralığına çevrilir. Son geçerli değerler, her koordinatta köşegen ve köşegen dışı kısıtların kesişimidir.
Üç koordinat aralığı belirlendikten sonra geriye yalnızca şu düzlem üzerindeki kutu içi tamsayı noktaları saymak kalır:
$$p_1w_1+p_2w_2+p_3w_3=1.$$
Bir ya da iki katsayı sıfır olduğunda denklem tek değişkenli veya iki değişkenli basit sayımlara iner. Genel durumda ise bir koordinat denklemden çözülür, diğer ikisi aralıklarında gezilir ve kalan koordinatın hem tamsayı olup olmadığına hem de sınırlar içinde kalıp kalmadığına bakılır.
Böylece dokuz girişli kaba matris taraması, tek bir afin düzlem üzerindeki çok daha küçük bir geometrik sayım problemine dönüşür.
Rank \(1\) için \(\mathbf{w}\cdot\mathbf{p}=1\) denklemi doğrudan \(w_1=1\) verir. Kutu sınırları \(|w_2|\le 1\) ve \(|w_3|\le 1\) olduğundan bu tek yön vektörü
$$3\cdot 3=9$$
adet rank-\(1\) matris üretir.
Rank \(2\) için \(M=I-\mathbf{p}\mathbf{w}^{T}\) yazılır. Aynı denklem yine \(w_1=1\) zorlar, köşegen dışı kısıtlar \(|w_2|,|w_3|\le 1\) verir ve köşegen giriş \(1-w_1=0\) uygun kalır. Dolayısıyla aynı yön vektörü bir \(9\) adet daha rank-\(2\) matris üretir.
Tüm kanonik primitif yönler üzerinden toplayıp sonra \(0\) ve \(I\)'yi eklediğimizde \(C(1)=164\) elde edilir; bu, uygulamadaki küçük test değeriyle tam uyumludur.
C++, Python ve Java implementasyonları aynı rank ayrışımını kullanır. Önce trivial idempotentler eklenir. Sonra \([-n,n]^3\) içindeki sıfırdan farklı, primitif ve işareti kanonik seçilmiş tüm yön vektörleri dolaşılır. Her yön için iki aile sayılır: simetrik küp içindeki rank-\(1\) matrisler ve üç koordinat aralığının kesişiminde kalan rank-\(2\) matrisler.
Ortak çekirdek,
$$p_1w_1+p_2w_2+p_3w_3=1$$
şeklindeki sınırlı lineer Diofant denklemi çözücüsüdür. Sıfır katsayılı özel durumlar doğrudan ele alınır; genel durumda bir koordinat denklemden belirlenir ve diğer iki koordinat üzerinde dolaşılır. Dış döngü farklı iş parçalarına bölündüğü için primitif yönlerin bağımsız dilimleri paralel sayılıp sonunda güvenle toplanabilir.
Dış arama kutusunda \(O(n^3)\) aday yön vektörü vardır. Ayakta kalan her primitif kanonik vektör için iç sayım, sınırlı bir iki boyutlu tamsayı çift taramasıdır; bu yüzden ihtiyatlı bir üst sınır \(O(n^5)\) zamandır. Bu sınır kaba kalır, çünkü büyük katsayılar izin verilen aralıkları hızla küçültür ve birçok rank-\(2\) kutusu boş ya da çok dardır. Yardımcı bellek, her iş parçası için \(O(1)\) ve buna ek olarak birkaç kısmi toplam kadardır.
Debemos contar las matrices enteras \(3\times3\) cuyas entradas están en \([-n,n]\) y que cumplen
$$M^2=M.$$
Estas matrices son idempotentes. Probar una por una las \( (2n+1)^9 \) matrices posibles es inviable, así que la solución explota la estructura de las matrices idempotentes: toda idempotente es una proyección y, en dimensión \(3\), eso reduce el problema a contar puntos de una red sobre un plano.
Las implementaciones no recorren directamente las nueve entradas de la matriz. En cambio, separan por rango y describen los casos no triviales mediante un vector entero primitivo y un funcional lineal entero.
Si \(M^2=M\), entonces todo autovalor \(\lambda\) satisface \(\lambda^2=\lambda\), de modo que \(\lambda\in\{0,1\}\). Por tanto, una matriz idempotente \(3\times3\) solo puede tener rango \(0,1,2\) o \(3\).
Los casos extremos son inmediatos:
$$\operatorname{rank}(M)=0 \Rightarrow M=0,\qquad \operatorname{rank}(M)=3 \Rightarrow M=I.$$
Así, para \(n\) positivo ya conocemos dos matrices; el trabajo real consiste en contar las de rango \(1\) y rango \(2\).
Sea \(M\) de rango \(1\). Su imagen es un subretículo unidimensional de \(\mathbb{Z}^3\), generado por un vector primitivo \(\mathbf{p}\in\mathbb{Z}^3\). Como \(M\) actúa como la identidad sobre su imagen, existe un vector fila entero \(\mathbf{w}^{T}\) tal que
$$M=\mathbf{p}\mathbf{w}^{T},\qquad \mathbf{w}\cdot\mathbf{p}=1.$$
La primitividad de \(\mathbf{p}\) es forzosa: si \(\gcd(p_1,p_2,p_3)=d>1\), entonces \(\mathbf{w}\cdot\mathbf{p}\) también sería múltiplo de \(d\), contradiciendo \(\mathbf{w}\cdot\mathbf{p}=1\).
En sentido inverso, cualquier par entero \((\mathbf{p},\mathbf{w})\) con \(\mathbf{w}\cdot\mathbf{p}=1\) produce una idempotente, porque
$$\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}.$$
Los pares \((\mathbf{p},\mathbf{w})\) y \((-\mathbf{p},-\mathbf{w})\) generan la misma matriz, así que se fija una orientación canónica: la primera componente no nula de \(\mathbf{p}\) debe ser positiva.
Si \(M\) tiene rango \(2\), entonces \(I-M\) es idempotente de rango \(1\). Aplicando la descripción anterior a \(I-M\) obtenemos
$$M=I-\mathbf{p}\mathbf{w}^{T},\qquad \mathbf{w}\cdot\mathbf{p}=1.$$
Y de nuevo es exactamente la forma correcta, ya que
$$\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}.$$
Por tanto, los rangos \(1\) y \(2\) comparten la misma parametrización aritmética; lo único que cambia es cómo se traducen las cotas sobre las entradas.
Escribamos \(\mathbf{p}=(p_1,p_2,p_3)^{T}\) y \(\mathbf{w}=(w_1,w_2,w_3)^{T}\).
Para rango \(1\), las entradas son \(M_{ij}=p_iw_j\), así que
$$|p_iw_j|\le n \qquad (1\le i,j\le 3).$$
Si \(P=\max(|p_1|,|p_2|,|p_3|)\), entonces cada coordenada satisface
$$|w_j|\le \left\lfloor\frac{n}{P}\right\rfloor.$$
Así, el caso de rango \(1\) se reduce a contar las soluciones enteras de
$$p_1w_1+p_2w_2+p_3w_3=1$$
dentro de un cubo simétrico.
Para rango \(2\), las entradas fuera de la diagonal son \(-p_iw_j\) con \(i\ne j\). Por ello, para cada columna \(j\),
$$|w_j|\le \left\lfloor\frac{n}{\max_{i\ne j}|p_i|}\right\rfloor$$
si al menos uno de los otros dos coeficientes es no nulo. Las entradas diagonales son \(1-p_jw_j\), luego
$$|1-p_jw_j|\le n \iff 1-n\le p_jw_j\le 1+n.$$
Cuando \(p_j\ne 0\), esto se convierte en un intervalo entero explícito mediante divisiones con piso y techo. Los valores admisibles de \(w_j\) son las intersecciones de las restricciones diagonales y fuera de la diagonal.
Una vez fijados los tres intervalos coordenados, la tarea restante es contar los puntos enteros de un paralelepípedo rectangular que satisfacen
$$p_1w_1+p_2w_2+p_3w_3=1.$$
Si uno o dos coeficientes son cero, la ecuación se reduce a un conteo sencillo en una o dos variables. En el caso general, se despeja una coordenada a partir de la ecuación, se recorren las otras dos dentro de sus intervalos y se comprueba que la tercera sea entera y además permanezca dentro de su rango.
De este modo, la búsqueda sobre nueve entradas se reemplaza por un problema geométrico mucho más pequeño sobre un único plano afín.
Para rango \(1\), la ecuación \(\mathbf{w}\cdot\mathbf{p}=1\) se convierte en \(w_1=1\). Las cotas de caja dan \(|w_2|\le 1\) y \(|w_3|\le 1\), así que esta única dirección primitiva aporta
$$3\cdot 3=9$$
matrices de rango \(1\).
Para rango \(2\), escribimos \(M=I-\mathbf{p}\mathbf{w}^{T}\). La misma ecuación fuerza otra vez \(w_1=1\), las cotas fuera de la diagonal vuelven a dar \(|w_2|,|w_3|\le 1\), y la entrada diagonal \(1-w_1=0\) es válida. Por tanto, la misma dirección aporta otras \(9\) matrices de rango \(2\).
Al sumar todas las direcciones primitivas canónicas y añadir luego \(0\) e \(I\), se obtiene \(C(1)=164\), exactamente el valor pequeño que usa la implementación como comprobación.
Las implementaciones en C++, Python y Java siguen esta misma descomposición por rango. Empiezan con las idempotentes triviales, enumeran todos los vectores de dirección no nulos, primitivos y con signo canónico dentro de \([-n,n]^3\), y para cada uno cuentan dos familias: matrices de rango \(1\) dentro de un cubo simétrico y matrices de rango \(2\) dentro de la intersección de tres intervalos coordenados.
El núcleo compartido es un resolvedor acotado para la ecuación diofántica lineal
$$p_1w_1+p_2w_2+p_3w_3=1.$$
Los casos especiales con coeficientes nulos se tratan aparte. En el caso genérico, una coordenada se fija mediante la ecuación y se itera sobre las otras dos. La enumeración exterior se reparte entre varios trabajadores, de modo que distintos fragmentos del conjunto de direcciones primitivas se cuentan en paralelo y después se suman.
La caja exterior contiene \(O(n^3)\) vectores de dirección candidatos. Para cada vector primitivo canónico que sobrevive, la fase interna es un barrido bidimensional acotado de pares enteros, por lo que una cota conservadora es \(O(n^5)\) en tiempo. Esa cota es amplia: cuando los coeficientes crecen, los intervalos admisibles se contraen con rapidez, y muchas cajas del caso de rango \(2\) quedan vacías o muy estrechas. La memoria auxiliar es \(O(1)\) por trabajador, además de unas pocas sumas parciales.
我们要求所有元素都落在 \([-n,n]\) 内的整数 \(3\times3\) 矩阵 \(M\) 的个数，并且这些矩阵满足
$$M^2=M.$$
这类矩阵称为幂等矩阵。若直接枚举全部 \( (2n+1)^9 \) 个候选矩阵，规模完全不可接受，所以解法必须利用幂等矩阵的结构性质。关键事实是：幂等矩阵本质上就是投影算子，而在三维情形下，这会把问题压缩成一个关于整数平面截盒子的计数问题。
实现并不是逐个测试九个矩阵元素，而是先按秩分类，再把非平凡情形写成“一个原始整向量 + 一个整线性泛函”的形式，最后只需求一个线性丢番图方程在有限盒子中的整数解个数。
由 \(M^2=M\) 可知，若 \(\lambda\) 是 \(M\) 的特征值，那么一定满足 \(\lambda^2=\lambda\)，因此
$$\lambda\in\{0,1\}.$$
所以一个 \(3\times3\) 幂等矩阵的秩只能是 \(0,1,2,3\) 之一。极端情形立刻就能写出：
$$\operatorname{rank}(M)=0 \Rightarrow M=0,\qquad \operatorname{rank}(M)=3 \Rightarrow M=I.$$
也就是说，当 \(n\ge 1\) 时，零矩阵和单位矩阵已经贡献了两项，真正需要计数的是秩 \(1\) 与秩 \(2\) 的幂等矩阵。
设 \(M\) 的秩为 \(1\)。那么它的像空间在 \(\mathbb{Z}^3\) 中对应一个一维子格，可以由某个原始整向量 \(\mathbf{p}\in\mathbb{Z}^3\) 生成。由于 \(M\) 是幂等的，它在自己的像空间上必须充当恒等映射，因此存在一个整数行向量 \(\mathbf{w}^{T}\)，使得
$$M=\mathbf{p}\mathbf{w}^{T},\qquad \mathbf{w}\cdot\mathbf{p}=1.$$
\(\mathbf{p}\) 必须是原始的，这不是额外假设，而是由方程本身强制出来的。若 \(\gcd(p_1,p_2,p_3)=d>1\)，那么 \(\mathbf{w}\cdot\mathbf{p}\) 也会被 \(d\) 整除，不可能等于 \(1\)。
反过来，只要 \(\mathbf{p},\mathbf{w}\) 是整数向量并且满足 \(\mathbf{w}\cdot\mathbf{p}=1\)，就一定得到一个幂等矩阵，因为
$$\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}.$$
这里还有一个符号重复：\((\mathbf{p},\mathbf{w})\) 与 \((-\mathbf{p},-\mathbf{w})\) 产生同一个矩阵。为避免重复计数，只保留一个规范方向，例如要求 \(\mathbf{p}\) 的第一个非零分量为正。
若 \(M\) 的秩为 \(2\)，则 \(I-M\) 仍然是幂等矩阵，而且秩为 \(1\)。因此可直接套用上一步对 \(I-M\) 的描述，得到
$$M=I-\mathbf{p}\mathbf{w}^{T},\qquad \mathbf{w}\cdot\mathbf{p}=1.$$
这同样是充要形式，因为
$$\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}.$$
因此，秩 \(1\) 和秩 \(2\) 的计数都归结到同一类整数对 \((\mathbf{p},\mathbf{w})\) 上，只是矩阵元素的范围条件在这两个情形下会翻译成不同的坐标区间。
记 \(\mathbf{p}=(p_1,p_2,p_3)^{T}\)、\(\mathbf{w}=(w_1,w_2,w_3)^{T}\)。
在秩 \(1\) 的情形里，矩阵元素就是
$$M_{ij}=p_iw_j.$$
于是约束 \(|M_{ij}|\le n\) 等价于
$$|p_iw_j|\le n \qquad (1\le i,j\le 3).$$
若设
$$P=\max(|p_1|,|p_2|,|p_3|),$$
那么每个坐标都必须满足
$$|w_j|\le \left\lfloor\frac{n}{P}\right\rfloor.$$
所以秩 \(1\) 的计数问题就变成：在一个对称立方体中，统计平面
$$p_1w_1+p_2w_2+p_3w_3=1$$
上的整数点。
秩 \(2\) 的情形稍微复杂一些。此时 \(M=I-\mathbf{p}\mathbf{w}^{T}\)。对角线外元素为 \(-p_iw_j\)（其中 \(i\ne j\)），因此对每个列指标 \(j\)，只要另外两个系数里至少有一个非零，就有
$$|w_j|\le \left\lfloor\frac{n}{\max_{i\ne j}|p_i|}\right\rfloor.$$
对角线元素则为 \(1-p_jw_j\)，所以必须满足
$$|1-p_jw_j|\le n \iff 1-n\le p_jw_j\le 1+n.$$
当 \(p_j\ne 0\) 时，这条不等式可以直接转成一个用上取整和下取整表示的整数区间。最终每个 \(w_j\) 的可行范围，就是“对角线约束区间”和“非对角线约束区间”的交集。
当三个坐标区间都确定后，剩下的任务就是：统计一个长方体盒子中满足
$$p_1w_1+p_2w_2+p_3w_3=1$$
的整数点个数。
如果三个系数里有一个或两个为零，那么方程会退化成一维或二维的简单计数问题。一般情形下，做法是先选定一个坐标作为“由方程决定的坐标”，然后在另外两个坐标的允许区间内枚举，检查由方程解出来的第三个坐标是否为整数，以及它是否仍在自己的区间内。
这样一来，原本对九个矩阵元素的暴力搜索，就被压缩成了对一个仿射平面截盒子的整数点计数。
先看秩 \(1\)。方程 \(\mathbf{w}\cdot\mathbf{p}=1\) 直接化为 \(w_1=1\)。盒子约束给出 \(|w_2|\le 1\)、\(|w_3|\le 1\)，因此这个单独的原始方向就贡献了
$$3\cdot 3=9$$
个秩 \(1\) 矩阵。
再看秩 \(2\)。此时 \(M=I-\mathbf{p}\mathbf{w}^{T}\)。同样由 \(\mathbf{w}\cdot\mathbf{p}=1\) 得到 \(w_1=1\)，非对角线约束仍给出 \(|w_2|,|w_3|\le 1\)，而对角线元素 \(1-w_1=0\) 也是允许的，所以这一方向还会额外贡献 \(9\) 个秩 \(2\) 矩阵。
把所有规范化后的原始方向都加起来，再补上 \(0\) 与 \(I\)，最终得到 \(C(1)=164\)。这与实现里使用的小规模校验值完全一致。
C++、Python 和 Java 版本都遵循同一条思路。它们先计入平凡的幂等矩阵，然后枚举 \([-n,n]^3\) 中所有非零、原始且方向规范化后的整向量。对每个方向，分别统计两个部分：一个是对称立方体中的秩 \(1\) 情形，另一个是三个坐标区间交集中的秩 \(2\) 情形。
核心子程序是求解有界线性丢番图方程
$$p_1w_1+p_2w_2+p_3w_3=1.$$
若某些系数为零，就走专门的简化分支；否则就固定一个由方程确定的坐标，只遍历另外两个坐标。最外层的方向枚举还会被切分到多个工作线程上，因此不同的方向块可以并行统计，最后再把计数安全相加。
最外层搜索盒子里有 \(O(n^3)\) 个候选方向向量。对每个通过筛选的原始规范方向，内部计数本质上都是一次有界的二维整数对扫描，所以保守的最坏时间上界可以写成 \(O(n^5)\)。这个上界偏松，因为当系数变大时，可行区间会迅速缩小，而且很多秩 \(2\) 的盒子要么为空，要么非常窄。辅助空间方面，除少量并行累加用的部分和之外，每个工作线程只需要 \(O(1)\) 级别的额外内存。
Нужно посчитать количество целочисленных матриц \(3\times3\), все элементы которых лежат в \([-n,n]\), и при этом выполняется условие
$$M^2=M.$$
Такие матрицы называются идемпотентными. Полный перебор всех \( (2n+1)^9 \) вариантов нереален, поэтому решение использует структурное свойство идемпотентов: любая такая матрица является проектором, а в размерности \(3\) это сводит задачу к подсчёту целых точек на плоскости.
Реальные реализации не проверяют девять элементов матрицы по отдельности. Вместо этого они разбивают задачу по рангу, а нетривиальные случаи описывают через один примитивный целочисленный вектор направления и один целочисленный линейный функционал.
Если \(M^2=M\), то любой собственный корень \(\lambda\) обязан удовлетворять \(\lambda^2=\lambda\), а значит
$$\lambda\in\{0,1\}.$$
Следовательно, идемпотентная матрица \(3\times3\) может иметь только ранг \(0,1,2\) или \(3\). Крайние случаи очевидны:
$$\operatorname{rank}(M)=0 \Rightarrow M=0,\qquad \operatorname{rank}(M)=3 \Rightarrow M=I.$$
Итак, при положительном \(n\) две матрицы уже известны заранее, а считать нужно только случаи ранга \(1\) и \(2\).
Пусть \(\operatorname{rank}(M)=1\). Тогда образ \(M\) является одномерной подрешёткой в \(\mathbb{Z}^3\), порождённой некоторым примитивным вектором \(\mathbf{p}\in\mathbb{Z}^3\). Поскольку \(M\) действует как тождество на своём образе, существует целочисленный строковый вектор \(\mathbf{w}^{T}\), для которого
$$M=\mathbf{p}\mathbf{w}^{T},\qquad \mathbf{w}\cdot\mathbf{p}=1.$$
Примитивность \(\mathbf{p}\) неизбежна. Если бы \(\gcd(p_1,p_2,p_3)=d>1\), то и \(\mathbf{w}\cdot\mathbf{p}\) делилось бы на \(d\), что противоречит равенству \(\mathbf{w}\cdot\mathbf{p}=1\).
Обратное тоже верно: любое целочисленное решение \((\mathbf{p},\mathbf{w})\) с \(\mathbf{w}\cdot\mathbf{p}=1\) даёт идемпотент, потому что
$$\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}.$$
Пары \((\mathbf{p},\mathbf{w})\) и \((-\mathbf{p},-\mathbf{w})\) задают одну и ту же матрицу, поэтому для устранения удвоения фиксируется каноническое направление: первая ненулевая компонента \(\mathbf{p}\) должна быть положительной.
Если у \(M\) ранг \(2\), то матрица \(I-M\) тоже идемпотентна и имеет ранг \(1\). Поэтому сразу получаем представление
$$M=I-\mathbf{p}\mathbf{w}^{T},\qquad \mathbf{w}\cdot\mathbf{p}=1.$$
Это снова точная характеристика, так как
$$\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}.$$
Значит, ранги \(1\) и \(2\) описываются одной и той же целочисленной парой \((\mathbf{p},\mathbf{w})\); различаются только ограничения на элементы матрицы.
Пусть \(\mathbf{p}=(p_1,p_2,p_3)^{T}\), \(\mathbf{w}=(w_1,w_2,w_3)^{T}\).
Для ранга \(1\) все элементы имеют вид \(M_{ij}=p_iw_j\), поэтому
$$|p_iw_j|\le n \qquad (1\le i,j\le 3).$$
Если обозначить
$$P=\max(|p_1|,|p_2|,|p_3|),$$
то каждая координата обязана удовлетворять
$$|w_j|\le \left\lfloor\frac{n}{P}\right\rfloor.$$
Итак, случай ранга \(1\) сводится к подсчёту целых решений уравнения
$$p_1w_1+p_2w_2+p_3w_3=1$$
внутри симметричного куба.
Для ранга \(2\) внедиагональные элементы равны \(-p_iw_j\) при \(i\ne j\). Поэтому для каждого столбца \(j\), если среди двух остальных коэффициентов есть хотя бы один ненулевой, получаем
$$|w_j|\le \left\lfloor\frac{n}{\max_{i\ne j}|p_i|}\right\rfloor.$$
Диагональные элементы равны \(1-p_jw_j\), то есть должно выполняться
$$|1-p_jw_j|\le n \iff 1-n\le p_jw_j\le 1+n.$$
Если \(p_j\ne 0\), это даёт явный целочисленный интервал через операции потолка и пола. Допустимые значения \(w_j\) находятся пересечением диагональных и внедиагональных ограничений.
После того как заданы три координатных интервала, остаётся подсчитать целые точки в прямоугольном параллелепипеде, лежащие на плоскости
$$p_1w_1+p_2w_2+p_3w_3=1.$$
Если один или два коэффициента равны нулю, задача вырождается в простой одномерный или двумерный подсчёт. В общем случае одна координата выражается из уравнения, две другие перебираются в своих диапазонах, а затем проверяется, что третья координата целая и попадает в допустимый интервал.
Так перебор по девяти элементам матрицы заменяется гораздо меньшей геометрической задачей о целых точках на одной аффинной плоскости.
Для ранга \(1\) уравнение \(\mathbf{w}\cdot\mathbf{p}=1\) сразу даёт \(w_1=1\). Ограничения куба дают \(|w_2|\le 1\) и \(|w_3|\le 1\), поэтому одно это примитивное направление даёт
$$3\cdot 3=9$$
матриц ранга \(1\).
Для ранга \(2\) пишем \(M=I-\mathbf{p}\mathbf{w}^{T}\). То же уравнение снова навязывает \(w_1=1\), внедиагональные ограничения снова дают \(|w_2|,|w_3|\le 1\), а диагональный элемент \(1-w_1=0\) допустим. Значит, это же направление порождает ещё \(9\) матриц ранга \(2\).
Если просуммировать вклад всех канонических примитивных направлений и затем добавить \(0\) и \(I\), получится \(C(1)=164\), что совпадает с малой проверкой, используемой в реализации.
Реализации на C++, Python и Java используют одну и ту же схему. Сначала учитываются тривиальные идемпотенты, затем перебираются все ненулевые примитивные векторы направления в \([-n,n]^3\) с каноническим выбором знака. Для каждого такого вектора отдельно считаются матрицы ранга \(1\) в симметричном кубе и матрицы ранга \(2\) в пересечении трёх координатных интервалов.
Общий вычислительный центр — это ограниченный решатель линейного диофантова уравнения
$$p_1w_1+p_2w_2+p_3w_3=1.$$
Вырожденные случаи с нулевыми коэффициентами обрабатываются отдельно. В общем случае одна координата определяется уравнением, а две другие перебираются. Внешнее перечисление делится между несколькими рабочими потоками, поэтому независимые части множества примитивных направлений можно считать параллельно и затем суммировать.
Во внешнем поисковом кубе находится \(O(n^3)\) кандидатов на векторы направления. Для каждого выжившего примитивного канонического вектора внутренний этап представляет собой ограниченный двумерный перебор целочисленных пар, поэтому консервативная верхняя оценка по времени равна \(O(n^5)\). Это грубая граница: при больших коэффициентах допустимые интервалы быстро сужаются, а многие коробки в случае ранга \(2\) оказываются пустыми или очень тонкими. Дополнительная память составляет \(O(1)\) на один рабочий поток плюс небольшой набор частичных сумм.
نريد عدّ جميع المصفوفات الصحيحة \(3\times3\) التي تقع عناصرها داخل \([-n,n]\) وتحقق
$$M^2=M.$$
هذه هي المصفوفات idempotent. الفحص المباشر لكل المصفوفات الممكنة وعددها \( (2n+1)^9 \) غير عملي تمامًا، لذلك تعتمد الفكرة على البنية الجبرية لهذه المصفوفات: كل مصفوفة من هذا النوع هي إسقاط، وفي البعد \(3\) يمكن تحويل المسألة إلى عدّ نقاط شبكية على مستوى أفيني.
التنفيذ لا يتعامل مع العناصر التسعة مباشرة، بل يقسم المصفوفات idempotent بحسب الرتبة، ثم يصف الحالات غير التافهة بواسطة متجه صحيح بدائي واحد ودالة خطية صحيحة واحدة، وبعد ذلك يحسب عدد الحلول الصحيحة لمعادلة خطية داخل صندوق محدود.
إذا كانت \(M^2=M\)، فإن كل قيمة ذاتية \(\lambda\) تحقق \(\lambda^2=\lambda\)، ومن ثم
$$\lambda\in\{0,1\}.$$
إذن رتبة مصفوفة idempotent من الحجم \(3\times3\) لا يمكن إلا أن تكون \(0\) أو \(1\) أو \(2\) أو \(3\). والحالتان الطرفيتان مباشرتان:
$$\operatorname{rank}(M)=0 \Rightarrow M=0,\qquad \operatorname{rank}(M)=3 \Rightarrow M=I.$$
لذلك عندما يكون \(n\) موجبًا نعرف مسبقًا مصفوفتين، وتبقى مهمة العد الفعلية في حالتي الرتبة \(1\) والرتبة \(2\).
لتكن \(M\) ذات رتبة \(1\). عندئذ تكون صورة \(M\) تحتشبكة أحادية البعد داخل \(\mathbb{Z}^3\)، ويمكن توليدها بمتجه بدائي \(\mathbf{p}\in\mathbb{Z}^3\). وبما أن \(M\) idempotent فهي تعمل كهُوية على صورتها، ولذلك يوجد متجه صفّي صحيح \(\mathbf{w}^{T}\) بحيث
$$M=\mathbf{p}\mathbf{w}^{T},\qquad \mathbf{w}\cdot\mathbf{p}=1.$$
كون \(\mathbf{p}\) بدائيًا ليس اختيارًا إضافيًا، بل نتيجة ضرورية. فلو كان \(\gcd(p_1,p_2,p_3)=d>1\)، لكان \(\mathbf{w}\cdot\mathbf{p}\) أيضًا من مضاعفات \(d\)، وهذا يناقض الشرط \(\mathbf{w}\cdot\mathbf{p}=1\).
وبالعكس، أي زوج صحيح \((\mathbf{p},\mathbf{w})\) يحقق \(\mathbf{w}\cdot\mathbf{p}=1\) يعطي مصفوفة idempotent فعلًا، لأن
$$\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}.$$
كما أن الزوجين \((\mathbf{p},\mathbf{w})\) و\((-\mathbf{p},-\mathbf{w})\) ينتجان المصفوفة نفسها، لذلك نفرض اختيارًا معياريًا للاتجاه: أول مركبة غير صفرية في \(\mathbf{p}\) يجب أن تكون موجبة.
إذا كانت رتبة \(M\) تساوي \(2\)، فإن \(I-M\) يكون أيضًا idempotent ورتبته \(1\). ومن ثم نحصل مباشرة على الصيغة
$$M=I-\mathbf{p}\mathbf{w}^{T},\qquad \mathbf{w}\cdot\mathbf{p}=1.$$
وهذه صيغة مكافئة تمامًا، لأن
$$\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}.$$
إذن حالتا الرتبة \(1\) والرتبة \(2\) توصفان بالبيانات العددية نفسها، لكن الاختلاف يظهر في القيود المفروضة على عناصر المصفوفة.
لنكتب \(\mathbf{p}=(p_1,p_2,p_3)^{T}\) و\(\mathbf{w}=(w_1,w_2,w_3)^{T}\).
في حالة الرتبة \(1\) تكون العناصر
$$M_{ij}=p_iw_j,$$
ومن ثم فإن الشرط \(|M_{ij}|\le n\) يكافئ
$$|p_iw_j|\le n \qquad (1\le i,j\le 3).$$
إذا وضعنا
$$P=\max(|p_1|,|p_2|,|p_3|),$$
فإن كل إحداثي من إحداثيات \(\mathbf{w}\) يجب أن يحقق
$$|w_j|\le \left\lfloor\frac{n}{P}\right\rfloor.$$
وبذلك تتحول حالة الرتبة \(1\) إلى عدّ الحلول الصحيحة للمعادلة
$$p_1w_1+p_2w_2+p_3w_3=1$$
داخل مكعب متناظر.
أما في حالة الرتبة \(2\)، فالعناصر خارج القطر هي \(-p_iw_j\) عندما \(i\ne j\). لذلك نحصل لكل عمود \(j\)، ما دام أحد المعاملين الآخرين غير صفري، على القيد
$$|w_j|\le \left\lfloor\frac{n}{\max_{i\ne j}|p_i|}\right\rfloor.$$
والعناصر القطرية هي \(1-p_jw_j\)، ولذلك يجب أن يتحقق
$$|1-p_jw_j|\le n \iff 1-n\le p_jw_j\le 1+n.$$
وعندما يكون \(p_j\ne 0\)، يمكن تحويل هذا مباشرة إلى فترة صحيحة باستعمال القسمة مع التقريب للأعلى وللأسفل. والقيم المسموح بها لكل \(w_j\) هي تقاطع القيود القطرية وغير القطرية.
بعد تحديد الفترات الثلاث، تبقى مسألة واحدة فقط: عدّ النقاط الصحيحة داخل صندوق مستطيلي والتي تقع على المستوى
$$p_1w_1+p_2w_2+p_3w_3=1.$$
إذا اختفى معامل واحد أو معاملان، فإن المسألة تختزل إلى عدّ أحادي أو ثنائي البعد. وفي الحالة العامة يتم حل أحد الإحداثيات من المعادلة، ثم تُستعرض القيم الممكنة للإحداثيين الآخرين، وبعد ذلك يُفحص ما إذا كان الإحداثي الثالث عددًا صحيحًا وما إذا كان يقع ضمن فترته.
بهذا تتحول عملية بحث ضخمة على تسعة عناصر إلى مسألة هندسية أصغر بكثير: عدّ نقاط صحيحة على مستوى أفيني واحد.
في حالة الرتبة \(1\)، تصبح المعادلة \(\mathbf{w}\cdot\mathbf{p}=1\) ببساطة \(w_1=1\). كما تعطي قيود الصندوق \(|w_2|\le 1\) و\(|w_3|\le 1\)، ولذلك يساهم هذا الاتجاه البدائي الواحد بعدد
$$3\cdot 3=9$$
من مصفوفات الرتبة \(1\).
وفي حالة الرتبة \(2\)، نكتب \(M=I-\mathbf{p}\mathbf{w}^{T}\). وتفرض المعادلة نفسها مرة أخرى \(w_1=1\)، وتبقى القيود \(|w_2|,|w_3|\le 1\)، كما أن العنصر القطري \(1-w_1=0\) مسموح. إذن يضيف هذا الاتجاه نفسه \(9\) مصفوفات أخرى من الرتبة \(2\).
وعند جمع مساهمات جميع الاتجاهات البدائية المعيارية ثم إضافة \(0\) و\(I\)، نحصل على \(C(1)=164\)، وهو نفس الاختبار الصغير الذي تتوافق معه عملية التنفيذ.
تتبع تطبيقات C++ وPython وJava الخطة نفسها. فهي تبدأ بالمصفوفتين التافهتين، ثم تعدّد جميع متجهات الاتجاه غير الصفرية والبدائية وذات الإشارة المعيارية داخل \([-n,n]^3\). ولكل اتجاه تحسب عائلتين مستقلتين: مصفوفات الرتبة \(1\) داخل مكعب متناظر، ومصفوفات الرتبة \(2\) داخل تقاطع ثلاث فترات إحداثية.
النواة المشتركة هي محلّل محدود للمعادلة الديوفانتية الخطية
$$p_1w_1+p_2w_2+p_3w_3=1.$$
تُعالج الحالات الخاصة ذات المعاملات الصفرية مباشرة، أما في الحالة العامة فيُثبَّت أحد الإحداثيات بواسطة المعادلة ويُجرى المسح على الإحداثيين الآخرين فقط. كما تُقسَّم الحلقة الخارجية على عدة عمال، بحيث يمكن عدّ أجزاء مستقلة من مجموعة الاتجاهات البدائية بالتوازي ثم جمع النتائج في النهاية.
يحتوي صندوق البحث الخارجي على \(O(n^3)\) من متجهات الاتجاه المرشحة. ولكل متجه بدائي معياري ينجو من التصفية، تكون مرحلة العد الداخلية عبارة عن مسح ثنائي البعد محدود على أزواج صحيحة، ولذلك فإن حدًا علويًا محافظًا للزمن هو \(O(n^5)\). هذه قيمة تقريبية خشنة، لأن المعاملات الكبيرة تجعل الفترات المسموح بها أصغر بكثير، كما أن كثيرًا من صناديق حالة الرتبة \(2\) يكون فارغًا أو شديد الضيق. أما الذاكرة الإضافية فهي \(O(1)\) لكل عامل، مع مقدار صغير فقط من المجاميع الجزئية.