Number of matrices with determinant value $0$

combinationscombinatoricsdeterminantmatricespermutations

A $3 \times 3$ matrix is formed using the elements from the set $\{-1,0,1\}$. How many matrices will have determinant value $0$.

Let matrix is \begin{bmatrix}
p & q & r\\
x & y & z \\
a & b &c
\end{bmatrix}

So total matrices formed will be $3^9$ and determinant is given by $\Delta=pyc+rxb+qza-rya-qxc-pzb$

Making some combinations I deduced that determinant value will go from $-4$ to $4$ but what approach should I follow to get number of determinants having value $0$?

Best Answer

Fun question! We'll start by reducing the determinant $\bmod 3$. The matrices of determinant $\pm 1 \bmod 3$ are exactly the matrices which, interpreted as having entries in the finite field $\mathbb{F}_3 = \{ 0, \pm 1 \}$, are invertible, so there are

$$|GL_3(\mathbb{F}_3)| = (3^3 - 1)(3^3 - 3)(3^3 - 3^2) = 11232$$

of them, and hence there are

$$|M_3(\mathbb{F}_3)| - |GL_3(\mathbb{F}_3)| = 3^9 - |GL_3(\mathbb{F}_3)| = 8451$$

matrices with determinant $0 \bmod 3$ (which agrees with J.G.'s count in the comments: $7875 + 2 \cdot 288$). So (assuming you're right that the determinant is in $[-4, 4]$, I haven't checked this) we've reduced the problem to counting the set $S$ of matrices with determinant $\pm 3$.

Let $H$ be the hyperoctahedral group $C_2 \wr S_3$ of $3 \times 3$ signed permutation matrices. $|H| = 48$ and $H$ acts freely from either the left or the right on $S$ (because $S$ consists of invertible matrices over $\mathbb{Q}$), so we can already show that $48$ divides $|S|$. Explicitly, allowing $H$ to act on the left amounts to giving ourselves the freedom to permute the rows and multiply any of them by $-1$, and similarly allowing $H$ to act on the right amounts to giving ourselves the freedom to permute the columns and multiply any of them by $-1$. The rest of the argument will proceed as follows:

  1. Identify the equivalence classes under the action of $G = H \times H$, with $H$ acting on both the right and the left, by finding a canonical form for the matrices in each equivalence class.

  2. Compute the size of the orbit of each canonical form by computing the size of its stabilizer.

Lemma 1: A matrix $X \in S$ can have at most one $0$ in any row or column.

Proof. If any row or column contains two $0$s then Laplace expansion along that row or column gives that the determinant is at most $2$ in absolute value. $\Box$

Lemma 2: A matrix $X \in S$ can have at most one row with no $0$s, and similarly for columns. Hence $X$ has at least two $0$s.

Proof. $\det(X) \equiv 1 \bmod 2$, so the rows and columns of $X$ must be linearly independent $\bmod 2$, and in particular distinct. $\Box$

Lemma 3: A matrix $X \in S$ must have exactly two $0$s.

Proof. If it has $3$ or more then they must be in distinct rows or columns by Lemma 1, and then the Laplace expansion shows that the determinant is at most $2$ in absolute value. $\Box$

Now it follows that one column must have the form $(\pm 1, \pm 1, \pm 1)$ and the other two must be permutations of $(\pm 1, \pm 1, 0)$ where the $0$s are in distinct places, and similarly for the rows (the signs are not necessarily the same here and below). By permuting rows and columns and changing their signs we can reduce to a matrix of the form

$$X = \left[ \begin{array}{cc} 1 & 1 & 0 \\ 1 & \pm 1 & 1 \\ 0 & 1 & \pm 1 \end{array} \right]$$

and now there are only $4$ cases to check determinants. Exactly one of them works, and we get that there is a single orbit, generated by

$$X = \left[ \begin{array}{cc} 1 & 1 & 0 \\ 1 & -1 & 1 \\ 0 & 1 & 1 \end{array} \right].$$

At this point, we know not only that $48$ divides $|S|$ but that $|S|$ divides $|G| = |H \times H| = 48^2$. It remains to compute the size of the stabilizer $G_X$ of this matrix under the action of $H \times H$, and then we'll have that $|S| = \frac{|G|}{|G_X|} = \frac{48^2}{|G_X|}$ (by the orbit-stabilizer theorem).

We can compute this stabilizer as follows. First let's ignore signs and only consider the effect of permuting columns and rows. The second row and column are unique because they're the only ones that contain three nonzero entries, so we can only swap the first and third row, and the first and third column, and then it's not hard to see that the only permutation that works is to simultaneously swap the first and third row and the first and third column; in other words, to conjugate by the permutation $(13)$.

Next, let's consider the effect of signs. By conjugating by $(13)$ if necessary we can suppose that we're considering only the effect of a bunch of sign changes. To preserve $X$ each entry must be flipped in sign an even number of times, and working through what that implies about which rows and columns can have their signs flipped we get that every row and every column must have their sign flipped the same number of times. The unique non-identity element which does this flips the sign of every row and every column simultaneously; this is the central element $(-1, -1) \in H \times H$.

It follows that the stabilizer is $C_2 \times C_2$ and hence that

$$|S| = \frac{|H \times H|}{|C_2 \times C_2|} = \frac{48^2}{2^2} = 24^2 = 576$$

which agrees with the Python-generated answers in the comments. Or rather, strictly speaking we were supposed to calculate the number of matrices with determinant $0$, which is

$$8451 - 576 = \boxed{ 7875 }.$$

Probably a somewhat more geometric approach is possible; note that the problem can be interpreted as being about volumes of certain tetrahedra made of lattice points in $\mathbb{Z}^3$ with entries in $\{ 0, \pm 1 \}$, which form a $3 \times 3 \times 3$ cube.

enter image description here

The problem asks us to count the number of degenerate tetrahedra with the center as a vertex (and an ordering of the other $3$ vertices) and we reduced the problem in the first step to counting tetrahedra with volume $\frac{3}{6} = \frac{1}{2}$ (or something like that). The hyperoctahedral group $H$ then appears naturally as the symmetry group of this cube, although it's a bit less clear how to see the action of the second copy of $H$.