Residue matrices and their orbits

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

The sampled columns of the construction are lifts of residue columns modulo \(h=B^k\). Before lifting, the three digit columns of the previous lesson, A determinant obstruction from field norms, are multiplied by one common random matrix \(G\) of determinant one modulo \(h\). This lesson describes what that does. A residue matrix \(C\) with a unit entry has a diagonal form \(\operatorname{diag}(1,D,E)\) with \(D=B^b\) dividing \(E=B^e\); the integer vectors whose residues lie in the row span of \(C\) form a lattice of index \(I=DE\); and \(GC\) is uniform on an orbit of at least about \(h^8/(D^3E^2)\) matrices. Finally, for digit columns the smaller divisor \(D\) has bounded expectation, even when the labels are fixed and repeated.

We use the orbit–stabilizer theorem from the core course Abstract Algebra I (Judson, Theorem 14.1.11: for a finite group acting on a finite set, an orbit has as many elements as the index of a stabilizer).

Throughout, \(B\) is a prime, \(k\geq1\), \(h=B^k\) and \(R_h=\mathbb Z/h\mathbb Z\). Every nonzero element of \(R_h\) is \(uB^v\) with \(u\) a unit and \(0\leq v<k\) uniquely determined (the valuation \(v\)); we give \(0\) the valuation \(k\). An element is a unit exactly when it is not divisible by \(B\). In counting formulas \(B^k\) means the integer \(h\), while as an entry of a matrix over \(R_h\) it is \(0\).

1. Diagonal form and the row lattice

The elementary operations on a matrix over \(R_h\) are: exchanging two rows (or columns), multiplying a row (or column) by a unit, and adding a multiple of one row (or column) to another. They are left (or right) multiplications by invertible matrices.

Lemma 1.1 (diagonal form). Let \(C\in M_3(R_h)\) have a unit entry. There are \(P,Q\in\mathrm{GL}_3(R_h)\) and integers \(0\leq b\leq e\leq k\) with \[ C=P\operatorname{diag}(1,B^b,B^e)\,Q . \] Put \(D=B^b\), \(E=B^e\) and \(I=DE\) (as positive integers). Then:

(a) for \(1\leq j\leq k\), \(b\geq j\) holds if and only if every \(2\times2\) minor of \(C\) vanishes modulo \(B^j\); in particular \(b\) does not depend on the choice of \(P,Q\);

(b) the set \(\Lambda_C\) of all \(v\in\mathbb Z^3\) such that \(v\bmod h\) lies in the row span of \(C\) is a lattice of rank three with \[ \begin{gathered} [\mathbb Z^3:\Lambda_C]=I,\\ E\mathbb Z^3\subseteq\Lambda_C . \end{gathered}\tag{1.1} \]

Proof. Reduction. Move a unit entry to the corner by exchanges, scale it to \(1\), and clear the rest of the first row and column. In the remaining \(2\times2\) block choose an entry of least valuation \(b\) (if the block is zero, put \(b=e=k\) and stop), move it to the corner of the block and scale it to \(B^b\). All entries of the block are multiples of \(B^b\), so the rest of its row and column can be cleared. The last entry is still a multiple of \(B^b\), equal to a unit times \(B^e\) with \(b\leq e\leq k\); scale it to \(B^e\).

(a) An elementary operation changes every \(2\times2\) minor into a combination, with coefficients in \(R_h\), of \(2\times2\) minors (by multilinearity of determinants: adding \(s\) times row \(i\) to row \(l\) changes a minor using row \(l\) by \(s\) times the minor with row \(l\) replaced by row \(i\)); the inverse operation gives the reverse. So the ideal generated by the \(2\times2\) minors is the same for \(C\) and for \(\operatorname{diag}(1,B^b,B^e)\), whose minors generate \(B^bR_h\). This ideal vanishes modulo \(B^j\) exactly when \(b\geq j\).

(b) Let \(\mathcal M\) be the row span of \(C\). Left multiplication by \(P\) does not change the row span, and right multiplication by \(Q\) is a bijection of \(R_h^3\) onto itself; so \(|\mathcal M|\) is the size of the row span \(R_h\times DR_h\times ER_h\) of the diagonal matrix, which is \(h\cdot\frac hD\cdot\frac hE=h^3/I\). The reduction \(\mathbb Z^3\to R_h^3\) is onto, and \(\Lambda_C\) is the preimage of \(\mathcal M\); it contains \(h\mathbb Z^3\), so it is a lattice of rank three, and \(\mathbb Z^3/\Lambda_C\cong R_h^3/\mathcal M\) has \(I\) elements. Since \(D\mid E\), the row span of the diagonal matrix contains \(ER_h^3\), which right multiplication by \(Q\) maps onto itself; so \(\mathcal M\supseteq ER_h^3\) and \(\Lambda_C\supseteq E\mathbb Z^3\). \(\square\)

The diagonal entries may be zero (\(b\) or \(e\) equal to \(k\)): singular residue matrices are included, as they must be, since determinant zero is the hardest case of the triangle problem.

2. Orbits of the special linear group

Lemma 2.1 (orbit bound). Under the hypotheses of Lemma 1.1, let \(\mathcal O_C=\{GC:G\in\mathrm{SL}_3(R_h)\}\). Then \[ |\mathcal O_C|\geq\frac{21}{64}\,\frac{h^8}{D^3E^2}.\tag{2.1} \] For \(G\) uniform in \(\mathrm{SL}_3(R_h)\), the matrix \(GC\) is uniform on \(\mathcal O_C\). All matrices of \(\mathcal O_C\) have the row span and the determinant of \(C\).

Proof. Let \(\mathcal G=\mathrm{GL}_3(R_h)\) act on \(M_3(R_h)\) by left multiplication, and let \(\mathcal H\) be the stabilizer of \(C\). Since \(Q\) is invertible, \(GC=C\) exactly when \(P^{-1}GP\) fixes \(\Delta=\operatorname{diag}(1,D,E)\); so \(\mathcal H=P\mathcal H_\Delta P^{-1}\), where \(\mathcal H_\Delta\) is the stabilizer of \(\Delta\), and conjugation preserves sizes and determinants.

Size of \(\mathcal H\). \(S\Delta=\Delta\) means \(Se_1=e_1\), \(D(Se_2-e_2)=0\) and \(E(Se_3-e_3)=0\). An element \(x\) of \(R_h\) with \(Dx=0\) is a multiple of \(h/D\): there are \(D\) of them, and likewise \(E\) for \(Ex=0\). Ignoring invertibility, \(|\mathcal H|\leq D^3E^3\).

Determinants in \(\mathcal H\). For a unit \(u\equiv1\pmod{h/E}\), \(\operatorname{diag}(1,1,u)\Delta=\operatorname{diag}(1,D,uE)=\Delta\), since \((u-1)E\equiv0\pmod h\). If \(e<k\) there are exactly \(E\) residues \(u\equiv1\pmod{h/E}\), all units; if \(e=k\), every unit qualifies, and there are \(\varphi(h)=(1-B^{-1})h=(1-B^{-1})E\) units. So the image \(\det\mathcal H\) of the determinant on \(\mathcal H\) has at least \((1-B^{-1})E\) elements, and since \(|R_h^\times|=(1-B^{-1})h\), \[ \frac{|\det\mathcal H|}{|R_h^\times|}\geq\frac Eh . \] Counting. The determinant is a homomorphism of \(\mathcal G\) onto \(R_h^\times\) (\(\det\operatorname{diag}(1,1,u)=u\)) with kernel \(\mathcal S=\mathrm{SL}_3(R_h)\); on \(\mathcal H\) it has image \(\det\mathcal H\) and kernel \(\mathcal H\cap\mathcal S\). By the orbit–stabilizer theorem for \(\mathcal G\) and for \(\mathcal S\), \[ \begin{aligned} |\mathcal O_C|&=\frac{|\mathcal S|}{|\mathcal H\cap\mathcal S|}=\frac{|\mathcal G|/|R_h^\times|}{|\mathcal H|/|\det\mathcal H|}\\ &=\frac{|\mathcal G|}{|\mathcal H|}\cdot\frac{|\det\mathcal H|}{|R_h^\times|}\geq\frac{|\mathcal G|}{D^3E^3}\cdot\frac Eh . \end{aligned} \] A matrix over \(R_h\) is invertible exactly when its reduction modulo \(B\) is (its determinant is a unit exactly when it is not divisible by \(B\)), and each matrix over \(\mathbb F_B\) has \(B^{9(k-1)}\) preimages. Since \(|\mathrm{GL}_3(\mathbb F_B)|\) is \((B^3-1)(B^3-B)(B^3-B^2)\) and \(B\geq2\), \[ \begin{aligned} |\mathcal G|&=B^{9(k-1)}|\mathrm{GL}_3(\mathbb F_B)|\\ &=h^9(1-B^{-1})(1-B^{-2})(1-B^{-3})\\ &\geq\tfrac{21}{64}h^9 . \end{aligned} \] This proves (2.1).

Uniformity. The fibres of \(G\mapsto GC\) on \(\mathcal S\) are the cosets \(G(\mathcal H\cap\mathcal S)\), all of the same size. Finally \(G\) is invertible with \(\det G=1\). \(\square\)

3. The smaller divisor of digit matrices

Lemma 3.1 (conditional digit estimate). Let \(r\geq2\) and \(L\) be integers with \(r\mid L\) and \(L<B\). Let \(\mathscr L\) be a set of labels, and for every \(\lambda\in\mathscr L\), \(1\leq i\leq3\) and \(0\leq u<k\) prescribe a residue \(a_{iu}(\lambda)\in\mathbb Z/r\mathbb Z\). Fix labels \(\lambda_1,\lambda_2,\lambda_3\), repetitions allowed. Choose, independently for all \(i,j,u\), digits \(d_{iju}\) uniformly from \(\{a\in\{1,\ldots,L\}:a\equiv a_{iu}(\lambda_j)\pmod r\}\), and let \(C\in M_3(R_h)\) have entries \(C_{ij}=\sum_{u<k}d_{iju}B^u\bmod h\). Let \(b\) and \(D=B^b\) be as in Lemma 1.1, and \(\theta=B(r/L)^4\). Then for \(1\leq j\leq k\) \[ \Pr(b\geq j)\leq(r/L)^{4j},\tag{3.1} \] and if \(\theta<1\), then \(\mathbb E[D]\leq1+\sum_{j=1}^k\theta^j\leq1/(1-\theta)\).

Proof. Every entry of \(C\) is a unit, since its lowest digit lies in \([1,L]\subseteq[1,B-1]\); so Lemma 1.1 applies. Condition, in addition, on the first column of \(C\) and on \(C_{12},C_{13}\). If \(b\geq j\), the minors \(C_{11}C_{iv}-C_{i1}C_{1v}\) vanish modulo \(B^j\) (Lemma 1.1(a)), that is, for \(i,v\in\{2,3\}\), \[ C_{iv}\equiv C_{i1}C_{11}^{-1}C_{1v}\pmod{B^j}. \] The right sides are fixed by the conditioning. Since every digit lies in \([0,B-1]\), the residue of \(C_{iv}\) modulo \(B^j\) determines its digits \(d_{ivu}\), \(u<j\); each of these \(j\) independent digits takes a prescribed value with probability at most \(r/L\). The four entries \(C_{22},C_{23},C_{32},C_{33}\) use disjoint independent digits, so the probability of all four congruences is at most \((r/L)^{4j}\); averaging over the conditioning gives (3.1). Finally \[ \begin{aligned} B^b&=1+\sum_{j=1}^k(B^j-B^{j-1})\mathbf 1\{b\geq j\}\\ &\leq1+\sum_{j=1}^kB^j\mathbf 1\{b\geq j\}, \end{aligned} \] and (3.1) gives the moment bound. \(\square\)

Corollary 3.2. For the digit construction of the previous lesson (\(L=r^{10}\), \(B\leq200k^2L^3\)) one has \(\theta\leq200k^2r^{-6}\), so for all sufficiently large \(r\) and every triple of labels \[ \mathbb E[D\mid\lambda_1,\lambda_2,\lambda_3]\leq2.\tag{3.2} \] If the three labels are independent and uniform in a set of \(r^d\) elements and \(\mathcal E\) is the event that two of them coincide, then \(\mathbb E[D\mathbf 1_{\mathcal E}]\leq2\Pr(\mathcal E)\leq6r^{-d}\).

Proof. \(\theta=B\,r^4/L^4\leq200k^2r^{30}\cdot r^{-36}\). Conditioning on the labels, \(\mathbb E[D\mathbf 1_{\mathcal E}]=\mathbb E[\mathbf 1_{\mathcal E}\,\mathbb E(D\mid\text{labels})]\leq2\Pr(\mathcal E)\), and \(\Pr(\mathcal E)\leq3r^{-d}\). \(\square\)

The point of (3.2) is that it holds for every triple of labels, including repeated ones: fresh digits for every column keep the residue matrix far from rank one even when two columns carry the same label.

4. Exercises

4.1. Find the diagonal form over \(\mathbb Z/8\mathbb Z\) (\(B=2\), \(k=3\)) of \(\begin{pmatrix}1&2&4\\3&6&4\\1&2&0\end{pmatrix}\), and the index of \(\Lambda_C\).

4.2. Show that for \(C=\operatorname{diag}(1,D,E)\) the lattice \(\Lambda_C\) is \(\mathbb Z\times D\mathbb Z\times E\mathbb Z\) (if \(e<k\); what if \(e=k\)?).

4.3. Check the formula \(|\mathrm{GL}_3(\mathbb Z/4\mathbb Z)|=4^9\cdot\frac12\cdot\frac34\cdot\frac78\).

4.4. In Lemma 3.1, why is it necessary to condition on the first column and on \(C_{12},C_{13}\), rather than on the first row and column of a different shape?

4.5. Show that the bound (2.1) is attained up to a constant when \(b=e=0\), and compare it with \(|\mathrm{SL}_3(R_h)|\).

5. Solutions

4.1. The first column has the unit \(1\). Clearing: subtract \(3\) times row 1 from row 2 and row 1 from row 3, then clear the first row with column operations: the block becomes \(\begin{pmatrix}0&-8\\0&-4\end{pmatrix}\equiv\begin{pmatrix}0&0\\0&4\end{pmatrix}\) modulo \(8\). The least valuation in the block is that of \(4\), \(b=2\); clearing gives the last entry \(0\), so \(e=3\). The diagonal form is \(\operatorname{diag}(1,4,0)\), with \(D=4\), \(E=8\), index \(32\).

4.2. The row span of \(\operatorname{diag}(1,D,E)\) is \(R_h\times DR_h\times ER_h\); its preimage is \(\mathbb Z\times D\mathbb Z\times E\mathbb Z\) when \(E<h\), and \(\mathbb Z\times D\mathbb Z\times h\mathbb Z\) when \(e=k\), which is the same formula with \(E=h\).

4.3. \(|\mathrm{GL}_3(\mathbb F_2)|=7\cdot6\cdot4=168\), and each matrix over \(\mathbb F_2\) has \(2^9\) preimages modulo \(4\): \(168\cdot512=86016=4^9\cdot\frac{168}{512}\), and \(\frac12\cdot\frac34\cdot\frac78=\frac{21}{64}=\frac{168}{512}\).

4.4. The congruences express \(C_{22},C_{23},C_{32},C_{33}\) through \(C_{11},C_{21},C_{31},C_{12},C_{13}\). Conditioning on exactly these five entries fixes the right sides while leaving the four left sides independent and still uniform in their digit sets.

4.5. For \(D=E=1\) the stabilizer is trivial and \(|\mathcal O_C|=|\mathrm{SL}_3(R_h)|=|\mathcal G|/|R_h^\times|\), which lies between \(\frac{21}{64}h^8\) and \(h^8\cdot\frac{h}{\varphi(h)}\leq2h^8\).

References