# Arithmetic properties of positively reduced $2\times 2$-matrices

Call a $$2\times 2$$ matrix with coefficients in $$\{0,1,2,3,\ldots\}$$ positively reduced if any row or column reduction (given by replacing a row/column by itself minus the other row/column) produces at least one strictly negative entry.

A matrix $$\left(\begin{array}{cc}a&b\\c&d\end{array}\right)$$ (with coefficients $$a,b,c,d\in\{0,1,2\ldots\}$$) of strictly positive determinant $$n=ad-bc>0$$ is positively reduced if and only if $$0\leq \max(b,c)<\min(a,d)$$. One shows easily that $$\max(a,d)\leq n$$. The number of positively reduced matrices of given strictly positive determinant is thus finite.

(Observation: Positive reduction can be seen as a generalization of Euclids algorithm which is positive reduction on (columns of) a $$1\times 2$$ matrix.)

We denote by $$\mathcal R(n)$$ the finite set of all positively reduced matrices of determinant $$n>0$$ and by $$r(n)=\sharp(\mathcal R(n))$$ the number of elements in $$\mathcal R(n)$$. (The set $$\mathcal R(0)$$ of positively reduced matrices with determinant $$0$$ consists of all matrices with at most one strictly positive entry and is infinite. The set $$\mathcal R(-n)$$ is isomorphic to $$\mathcal R(n)$$ by row-exchange.)

The first $$25$$ values of the sequence $$r(1),r(2),\ldots$$ are given by $$1,2,3,5,5,8,7,11,10,14,11,19,13,20,18,24,17,30,19,31,26,26,32,23,44,26$$ and are not recognized by https://oeis.org/.

The numbers $$r(n)$$ and the set $$\mathcal R(n)$$ seem to have interesting arithmetical properties:

We have seemingly $$r(n)\geq n$$ with equality if and only if $$n=1$$ or $$n$$ is prime.

More precisely, for a prime $$p$$, (reductions modulo $$p$$ of) elements in $$\mathcal R(p)$$ have all rank $$1$$ over the finite field $$\mathbb F_p$$. The two row-vectors of a matrix in $$\mathcal R(p)$$ are thus collinear over $$\mathbb F_p$$ and represent a unique element $$[a:b]$$ of the projective line $$\mathbb P^1(\mathbb F_p)$$ over $$\mathbb F_p$$. This induces a bijection between $$\mathcal R(p)$$ and $$\mathbb P^1(\mathbb F_p)\setminus\{[1:1]\}$$. (See update below for a proof.)

The two points $$[1:0]$$ and $$[0:1]$$ for example correspond to the two diagonal matrices $$\left(\begin{array}{cc}1&0\\0&p\end{array}\right)$$ and $$\left(\begin{array}{cc}p&0\\0&1\end{array}\right)$$.

Update: The definition of positive reducedness can be reformulated as follows. The two rows $$v,w$$ of a positively reduced matrix $$M$$ of determinant $$n$$ generate a sublattice $$\Lambda(M)=\mathbb Zv+\mathbb Zw$$ of index $$n$$ in $$\mathbb Z^2$$. The map $$\mathcal R(n)\ni M\longmapsto \Lambda(M)$$ is injective but never surjective for $$n>1$$. More precisely, a sublattice $$\Lambda$$ of index $$n$$ in $$\mathbb Z^2$$ has an associated (unbounded) "Newton polygon" $$P(\Lambda)$$ by considering the convex hull of $$\Lambda\cap(\mathbb N^2\setminus\{(0,0)\})$$.

A sublattice $$\Lambda$$ of index $$n$$ in $$\mathbb Z^2$$ is the of the form $$\Lambda(M)$$ for $$M$$ in $$\mathcal R(n)$$ if and only if the boundary $$\partial P(\Lambda)$$ of the polygone $$P(\Lambda)$$ intersects the diagonal $$\mathbb R(1,1)$$ in a point $$Q$$ which is not integral. The two rows of $$M$$ are then given by the two consecutive integral points on $$\partial P(\Lambda)$$ separated by $$Q$$.

This implies the result easily for $$n=p$$ prime: The only sublattice of prime index $$p$$ in $$\mathbb Z^2$$ with $$\partial P(\Lambda)$$ intersecting $$\mathbb N(1,1)$$ is the lattice $$\mathbb Z(p,0)+\mathbb Z(1,1)$$.

This should give a fast algorithm by removing the number of "bad" lattices (with $$\partial P(\Lambda)$$ intersecting $$\mathbb Z(1,1)$$) from the total number of sublattices of index $$n$$ in $$\mathbb Z^2$$. (The number of sublattices of given index $$n$$ in $$\mathbb Z^d$$ is given by $$\prod_{p\vert n}{e_p+d-1\choose d-1}_p$$ where $$n$$ has prime-decomposition $$n=\prod_{p\vert N}p^{e_p}$$ and where $${a\choose b}_q$$ is the $$q$$-binomial, see Y. M. Zou, “Gaussian binomials and the number of sublattices”, Acta Crystallogr. 62 (2006), no. 5, p. 409--410). (End of update)

More generally, the function $$n\longmapsto r(n)$$ behaves almost multiplicatively:

We have experimentally for small prime-powers: \begin{align*} r(p^2)&=p^2+1,\\ r(p^3)&=p^3+p^2-p+1,\\ r(p^4)&=p^4+p^3-p+2,\\ r(p^5)&=p^5+p^4+p^3-p^2-p+2,\\ r(p^6)&=p^6+p^5+p^4-p^2-p+3. \end{align*}

$$r(pq)=(p+1)(q-1)+2$$ for primes $$p,

$$r(p^kq)=\frac{p^{k+1}-1}{p-1}(q-1)+k+1$$ for primes $$q>p^k$$ (checked for small cases),

for three distinct primes $$p_1,p_2,p_3>p_1p_2$$ we have $$r(p_1p_2p_3)=(p_1+1)(p_2+1)(p_3-1)+4$$,

Question: Does someone have any ideas for proofs? The function $$n\longmapsto r(n)$$ seems to have interesting arithmetic properties: Is there something similar to a modular form lurking somewhere? Ideas for fast algorithms (for computing $$r(n)$$ or $$\mathcal R(n)$$) would also be wellcome. (I think my algorithm below is worse than $$n^2$$.)

(Update on questions: The above update transforms the questions into the determination of the set (and its number of elements) of "bad" index $$n$$-sublattices of $$\mathbb Z^2$$.)

Computations: We set $$r(N)=r_1(N)+r_2(N)+2r_3(N)+2r_4(N)+4r_5(N)$$ where $$r_1(N)=\sum_{d\vert N}\left(2\min(d,N/d)-1\right)$$ counts all triangular matrices in $$\mathcal R(N)$$, $$r_2(N)=\sum_{d\vert N,d^2>N,d\equiv N/d\pmod 2}1$$ counts all matrices of the form $$\left(\begin{array}{cc}a&b\\b&a\end{array}\right)$$ with $$0 in $$\mathcal R(N)$$, $$r_3=\sum_{1\leq \delta< \alpha,\alpha\delta counts all matrices of the form $$\left(\begin{array}{cc}a&b\\b&d\end{array} \right)$$ with $$0 in $$\mathcal R(N)$$ (the factor $$2$$ before $$r_3$$ accounts for the symmetry exchanging the role of $$a$$ and $$d$$),
$$r_4(N)=\sum_{1\leq \beta<\alpha,\alpha^2
counts all matrices of the form $$\left(\begin{array}{cc}a&b\\c&a\end{array}\right)$$ with $$0 in $$\mathcal R(N)$$ (the factor $$2$$ before $$r_4$$ accounts for the symmetry exchanging the role of $$b$$ and $$c$$) and
$$r_5(N)=\sum_{2\leq \delta<\alpha,\alpha\delta
counts the generic type $$\left(\begin{array}{cc}a&b\\c&d\end{array}\right)$$ with $$0 in $$\mathcal R(N)$$ (the factor $$4$$ accounts
for the symmetric roles of elements in the pairs $$(a,d)$$ and $$(b,c)$$).

Formulae for $$r_3,r_4,r_5$$ are based on the identity
$$\det\left(\begin{array}{cc} a&b\\c&d\end{array}\right)=ad-bc =(a-c)(d-c)+c(a+d-b-c)=\alpha\delta+c(\alpha+\delta-\beta)$$ with $$\alpha=a-c,\beta=b-c,\delta=d-c$$ entries of the positively reduced upper triangular matrix
$$\left(\begin{array}{cc}\alpha&\beta\\0&\gamma\end{array}\right)$$ obtained by subtracting the minimal entry $$c$$ from
all entries of a positively reduced matrix $$\left(\begin{array}{cc} a&b\\c&d\end{array}\right)$$
with $$0\leq c\leq b.

Final Remark: There are two possible generalizations to higher dimensions of positive reducedness. Both are problematic.

The matrix generalization: Positive reducedness can of course be defined for matrices of any size. Counting positively reduced matrices accordingly to non-zero determinants is however no longer interesting in dimension larger than $$2$$: For any $$x$$ in $$\{0,1,2,\ldots\}$$ the matrix $$\left(\begin{array}{ccc}4+x&2+x&1+x\\x&1+x&3+x\\1+x&1+x&2+x\end{array}\right)$$ has determinant $$1$$ and is positively reduced. (Counting positively reduced matrices accordingly to entry-sums is of course always possible and not very difficult in principle.) See comments by Dima Pasechnik for possibles remedies using total positivity.

The point of view of subgroups of finite index in $$\mathbb Z^d$$. One can of course define a "Newton polytope" and look at the intersection of its boundary with $$\mathbb N(1,1,\ldots,1)$$. This intersection can be integral (bad, I guess) or lie on a face of codimension larger than $$1$$ (acceptable or not?). Even in the case of a codimension $$1$$ face, there is a problem: It can happen that integral points of this face generate a sublattice of index $$kd$$ in $$\mathbb Z^d$$ for some integer $$k>1$$.

In any case, there is no longer an obvious way to associate a matrix to such a sublattice (there is of course an obvious sublattice associated to an integral matrix by considering $$\mathbb Z$$-linear combinations of rows.)

• The numbers inside a matrix are usually called entries, not coefficients. Sep 29, 2021 at 11:18
• @Gerry Myerson Thanks for this information. I think I have replaced all occuring 'coefficients' by the correct term. Sep 29, 2021 at 19:43
• I see bold update announcement but I was not able to fish the question. Could you make it bold or somehow more visible? Sep 30, 2021 at 8:50
• Perhaps a generalisation to bigger sizes should involve total positivity: en.wikipedia.org/wiki/Totally_positive_matrix That is, start with a totally positive matrix and demand that every reduction leads to total positvity breakage. Sep 30, 2021 at 8:54
• such a generalisation (more precisely, one should talk about total nonnegativity rather than total positivity) gives finiteness, by induction on dimension: 2x2 minors should remain nonnegative, thus you have only finitely many of these in any size. Sep 30, 2021 at 9:00

The number $$r(n)$$ of positively reduced matrices of determinant $$n\geq 1$$ is given by $$r(n)=\sum_{d\vert n,\ d^2\geq n}\left(d+1-\frac{n}{d}\right)\ .$$