Number of matrices with zero determinant

Question

I want to count matrices over finite field with zero determinant. For example, the numbet of $2\times2$ matrices over $\Bbb{Z}_4$ with zero determinant is 88 by hand computations. On the other hand the size of the group $GL(2,4)$ is $180$ and the total number of such $2\times2$ matrices is $256$. So something is wrong. What is my mistake?

Revised question: I am looking for the number of $2×2$ matrices over $\Bbb{Z}_4$ (the ring of integers modulo 4), with zero determinant. By a quick computations, there are $88$ ones. So what is the formula in general?

Answer 1

Over a finite field of order $q$, it is easy to count matrices with nonzero determinant (and from there, get matrices with zero determinant by complementary counting).

There are $q^n-1$ choices for the first column: we just have to choose a nonzero vector in $\mathbb F_q^n$. Then there are $q^n-q$ choices for the second column: we must avoid choosing any multiple of the first column. There are $q^n-q^2$ choices for the third column (since there are $q^2$ distinct linear combinations of the first two columns, which we must avoid, and so on). So the number of $n\times n$ matrices over $\mathbb F_q$ with nonzero determinant is $$ \prod_{k=0}^{n-1} (q^n - q^k) $$ and then $q^{n^2}$ minus this product gives the number of matrices with zero determinant.

But $\mathbb Z_4$ (if by this you mean the integers modulo $4$) is not a field, and so this calculation doesn't quite work. For example, $$\det \begin{bmatrix}2 & 0 \\ 0 & 2\end{bmatrix} \equiv 0 \pmod 4$$ even though the second column is not a multiple of the first.

---

Here is a general formula for $n\times n$ matrices over $\mathbb Z_4$.

Write the matrix as $A + 2B$, where $A,B$ have entries from $\{0,1\}$.

Suppose that mod $2$, $A$ has corank $r$ (rank $n-r$). Then we can choose $r$ independent (mod $2$) vectors $\mathbf x_1, \dots, \mathbf x_r$ such that $A\mathbf x_i \equiv \mathbf 0 \pmod 2$. Extend these to a set of $n$ vectors that are independent mod $2$, and let $X$ be the matrix whose columns are these $n$ vectors.

Because $X$ is invertible mod $2$, $X$ is invertible mod $4$, so $\det(A + 2B) = \det(X(A+2B)X^{-1}) = \det(XAX^{-1} + 2 XBX^{-1})$. If we find a decomposition of $XAX^{-1} + 2 XBX^{-1}$ into $A' + 2B'$, where $A', B'$ have entries from $\{0,1\}$, then the first $r$ rows of $A'$ are $0$ and the last $n-r$ rows are linearly independent.

It follows that if $r \ge 2$, then $\det(A + 2B)$ is definitely $0$: a row expansion by the first row of $A' + 2B'$ picks up a factor of $2$, and a row expansion by the second row of $A' + 2B'$ picks up another factor of $2$. What about when $r=1$?

When $r=1$, we can factor out a $2$ from the first row of $A' + 2B'$. This lets us rewrite $\det(A' + 2B')$ as $2 \cdot \det(A'' + 2B'')$ where:

• the first row of $A''$ is the first row of $B'$, and other rows are taken from $A'$.
• the first row of $B''$ is $0$, and other rows are taken from $B'$.

If $\det(A' + 2B') = 2$, then $\det(A'' + 2B'')$ is odd, which means $A''$ is invertible mod $2$. Given the last $n-1$ rows of $A''$ (which were fixed by $A'$), $2^{n-1}$ out of $2^n$ choices for the first row of $A''$ (which comes from $B'$) will make $A''$ invertible mod $2$. Therefore half of the possible choices for $B'$ (which come from half of the possible choices for $B$) give determinant $2$ here. So exactly half of the matrices with $r=1$ will have determinant $0$, and the other half will have determinant $2$.

Thus, if we want to count the matrices mod $4$ with determinant $0$, let $N_0, N_1, N_{\ge 2}$ (with $N_0 + N_1 + N_{\ge 2} = 2^{n^2}$) be the number of matrices over $\mathbb F_2$ with corank $0$, corank $1$, and corank $\ge 2$. Then the number we're interested in is $$ N_1 \cdot 2^{n^2-1} + N_{\ge 2} \cdot 2^{n^2}. $$ (When $A$ is counted by $N_{\ge 2}$, any matrix $B$ will make $\det(A+2B)=0$; when $A$ is counted by $N_1$, half of all possible matrices will do.) For example, when $n=2$, $N_1 = 9$ and $N_{\ge 2} = 1$, so there are $9 \cdot 2^3 + 1 \cdot 2^4 = 72 + 16 = 88$ matrices.

We have $N_0 = \prod_{k=0}^{n-1} (2^n - 2^k)$ by the formula for the first section. Counting $N_1$ is a bit harder, but we can do it: if we first choose a linearly dependent row on the $i^{\text{th}}$ step ($i=0, 1,\dots, n-1$), the number of ways is $2^i \prod_{k=0}^{n-2} (2^n - 2^k)$, so altogether $N_1 = (2^n - 1)\prod_{k=0}^{n-2} (2^n - 2^k)$. So the general formula for $n \times n$ matrices of $\mathbb Z_4$ is $$ 2^{n^2-1}(2^n - 1)\prod_{k=0}^{n-2} (2^n - 2^k) + 2^{n^2}\left(2^{n^2} - \prod_{k=0}^{n-1} (2^n - 2^k) - (2^n - 1)\prod_{k=0}^{n-2} (2^n - 2^k)\right). $$ Some algebra simplifies this to $$ 4^{n^2} - 2^{n^2-1} (2^{n+1}-1) \prod_{k=0}^{n-2} (2^n - 2^k). $$ The sequence begins $1, 88, 100864, 1735131136, \dots$.

For $\mathbb Z_{p^2}$ in general, similar reasoning should work.

Answer 2

If you are counting matrices over $\Bbb{F}_4$, here's a useful fact:

An $n\times n$-matrix over a field $k$ is invertible if and only if its columns form a basis for $k^n$.

I'll leave the proof to the reader. For $2\times2$-matrices over $\Bbb{F}_4$ this means the columns are two non-collinear vectors. So any choice of non-zero vector for the first column, and any choice of non-collinear vector for the second column yields an invertible matrix.

If you are counting matrices over $\Bbb{Z}/4\Bbb{Z}$, then here's a useful fact:

An $n\times n$-matrix over $\Bbb{Z}/p^k\Bbb{Z}$ is invertible if and only if it is invertible over $\Bbb{Z}/p\Bbb{Z}$.

Again I'll leave the proof to the reader. This reduces the problem to counting invertible matrices over $\Bbb{F}_2$, which you can do using the first fact.

Answer 3

Here's a different approach to counting $2\times2$-matrices over $\Bbb{Z}/p^2\Bbb{Z}$ with determinant $0$. I'll start with $p=2$ as an example, and then generalize the result to arbitrary $p$.

The number of $2\times2$-matrices with coefficients in $\Bbb{Z}/4\Bbb{Z}$ with determinant $0$ is precisely the number of pairs of pairs $$((a,d),(b,c))\in((\Bbb{Z}/4\Bbb{Z})^2)^2 \qquad\text{ with }\qquad ad=bc.$$ A simple multiplication table for $\Bbb{Z}/4\Bbb{Z}$ $$\begin{array}{r|cccc} &0&1&2&3\\ \hline 0&0&0&0&0\\ 1&0&1&2&3\\ 2&0&2&0&2\\ 3&0&3&2&1 \end{array},$$ shows that there are $8$ pairs with product $0$, $2$ pairs with product $1$, $4$ pairs with product $2$, and $2$ pairs with product $3$. Hence the number of pairs of pairs with the same product is $$8^2+2^2+4^2+2^2=88,$$ and so this is the number of $2\times2$-matrices with coefficients in $\Bbb{Z}/4\Bbb{Z}$ with determinant $0$.

In the same way, making a multiplication table for $\Bbb{Z}/p^2\Bbb{Z}$ we count the number of pairs...

1. ... with product $0$. There are $3p^2-2p$ such pairs, yielding $$(3p^2-2p)=p^2(3p-2)^2,$$ matrices with determinant $0$.

2. ... with non-zero product a multiple of $p$. There are $2p(p-1)^2$ such pairs, evenly distributed over the $p-1$ non-zero elements of $\Bbb{Z}/p^2\Bbb{Z}$ that are a multiple of $p$. So there are $2p(p-1)$ pairs for each value, yielding $$(p-1)\times(2p(p-1))^2=4p^2(p-1)^3,$$ matrices with determinant $0$.

3. ... with product coprime to $p$. There are $p^2(p-1)^2$ such pairs, evenly distributed over the $p(p-1)$ elements of $\Bbb{Z}/p^2\Bbb{Z}$ coprime to $p$. So there are $p(p-1)$ pairs for each value, yielding $$p(p-1)\times (p(p-1))^2=p^3(p-1)^3,$$ matrices with determinant $0$.

Hence the total number of matrices with coefficients in $\Bbb{Z}/p^2\Bbb{Z}$ and determinant $0$ equals $$p^3(p-1)^3+4p^2(p-1)^3+p^2(3p-2)^2=p^3(p^3+p^2-1).$$ For $p=2,3,5,7,11,\ldots$ we find the numbers $$88,\ 945,\ 18\,625,\ 134\,113,\ 1\,931\,281,\ \ldots$$