# How many ways can I factor a matrix (over $\mathbb{Z}$)?

Let $A$ be a fixed matrix in $M_2\mathbb{Z}$ with determinant $n \neq 0$.

Question 1 How many ways can I write $A = XY$ for $X, Y \in M_2\mathbb{Z}$?

The answer to this question is pretty clearly infinite, since for any $\gamma \in GL_2\mathbb{Z}$ and any such pair $(X, Y)$, then $(X \gamma^{-1}, \gamma Y)$ is another such factorization. So let's get rid of that.

Question 2 Consider the set $S_A = \{(X, Y) \in (M_2\mathbb{Z})^2 \mid A = XY\}$. The group $G = GL_2\mathbb{Z}$ acts naturally on this set via $$\gamma \cdot (X, Y) = (X \gamma^{-1}, \gamma Y)$$ What is the cardinality of $S_A/G$?

Unfortunately, this depends on our choice of $A$ (fixing $n$). If we compare $$A_1 = \begin{pmatrix}4 & 0 \\ 0 & 1 \end{pmatrix} \qquad \qquad A_2 = \begin{pmatrix}2 & 0 \\ 0 & 2 \end{pmatrix}$$ then in the first case, we find $|S_{A_1}/G| = 3$ while in the second, $|S_{A_2}/G| = 4$. This is due to the fact that the second matrix is not primitive. We could exclude such matrices, or we could define an equivalence relation on factorizations via $$(X, kY) \sim (kX, Y)$$ which is compatible with the action of $G$. For a fixed $A$, define $T_A = S_A/_\sim$.

The Real Question Does the cardinality of $T_A/G$ depend on $A$? If not, what is it?

By computation, it seems that this does not depend on $A$ and moreover, $$|T_A/G| = \sum_{d \mid n} 1 = \sigma_0(n)$$

This seems like it should be a pretty obvious question about arithmetic/algebraic groups, but it's not really my area of expertise.

• Notice that your second equivalence relation is just $(X,Y) \sim (k^{-1}X, kY)$, which is just the same as the action of scalar matrices, so you don't gain anything by quotienting by it. – Kevin Casto Mar 29 '16 at 22:34
• Well... I think that depends on the definition of $GL_2Z$ being used. I've been thinking of this as $GL_2Z = \{A \in M_2Z \mid \det A = \pm 1\}$, in which case that is a different relation. But as David points out below, it's still the wrong relation, so the point is kind of moot. – Simon Rose Mar 30 '16 at 6:06

$\def\ZZ{\mathbb{Z}}$Your conjecture is right when you require $A$ to be primitive. The version where you set $(X,kY) \sim (kX,Y)$ doesn't work even in your chosen example.
$A$ gives a map $\ZZ^2 \to \ZZ^2$. Set $K = \ZZ^2/A \ZZ^2$; this is an abelian group of order $n$ generated by $2$ elements and the condition that $A$ is primitive implies that $G \cong \ZZ/n \ZZ$.
You want to know how many ways you can factor this as $\ZZ^2 \to L \to \ZZ^2$, where $L \cong \ZZ^2$ and we work up to isomorphisms on the middle factor. Such a factorization is uniquely determined by the subgroup $L/ZZ^2$ of $K$. So we are counting subgroups of $\ZZ/n \ZZ$, which there are $\sigma_0(n)$ of.
If we take $A = \left( \begin{smallmatrix} 2 & 0 \\ 0 & 2 \end{smallmatrix} \right)$, then $G \cong (\ZZ/2 \ZZ)^2$, with five subgroups. Representative factorizations are $$\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}, \quad \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix},$$ $$\begin{pmatrix} 2 & 0 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix}, \quad \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix}\begin{pmatrix} 2 & 0 \\ 0 & 1 \end{pmatrix}, \quad \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\begin{pmatrix} 1& 1 \\ 1 & -1 \end{pmatrix}.$$ Your equivalence relation collapses these $5$ cases to $4$, not $3$.
It is clear that $\#(T_A/G)$ will only depend on the isomorphism type of the abelian group $\ZZ^2/A \ZZ^2$ (in other words, on the Smith normal form of $A$). If you really need it, I could work it out; I suspect you could too.