# How many singular $3\times3$ matrices exist using only the numbers $1$ and $0$?

I've been pondering this question for a couple of days now, and I was wondering if anyone could help me.

I've started by considering the determinant to be:

Det(A) = aei - afh - bdi + bfg + cdh - ceg

I've then partitioned it into the cases for having 9 0s, 8 0s, 7 0s ETC and using 9C0, 9C1 ETC, but obviously some cases are less straight forward. Does anyone have any idea how to work this out?

Thank you!

• See this post and this sequence. There isn't a particularly effective "shortcut" for computing the answer, but it is known that the answer is $338$. Commented Sep 14, 2020 at 8:28
• As the linked post states, we can get an upper bound for the number of such matrices (in this case, $2^9 - (8-1)(8-2)(8-4) = 344$) by counting the number of such matrices with even determinant. With that in mind, it would suffice to count the number of matrices with even non-zero determinant, which seems like a much more manageable task since there are only $6$ such matrices. Commented Sep 14, 2020 at 8:34

An alternative to the given answer: is established here for instance, the number of $$3 \times 3$$ matrices with $$(0,1)$$ entries that have even determinant is given by $$2^9 - (2^3 - 2^0)(2^3 - 2^1)(2^3 - 2^2) = 344.$$ Thus, it suffices to determine how many of these matrices have a non-zero determinant and then note that the rest will have determinant zero.

As you note, the determinant can be expanded via the Leibniz formula or the rule of Sarrus to give a sum of six terms. $$3$$ can be equal to either $$0$$ or $$1$$, and $$3$$ can be equal to either $$0$$ or $$-1$$. Thus, the possible non-zero even determinants are $$2$$ and $$-2$$.

We note that given an matrix with determinant $$2$$, we can switch the first two rows to produce a matrix with determinant $$-2$$. Thus, it suffices to count the matrices with determinant $$2$$.

From there, one needs to show that the only such matrices are $$\pmatrix{1&0&1\\1&1&0\\0&1&1}, \quad \pmatrix{1&1&0\\0&1&1\\1&0&1}, \quad \pmatrix{0&1&1\\1&0&1\\1&1&0}.$$ Thus, there are $$3$$ matrices $$(0,1)$$ matrices with determinant $$2$$, which means that there are $$344 - 2 \times 3 = 338$$ $$(0,1)$$ matrices with determinant zero

First case: Every row is identical. We can choose any of the $$2^3 = 8$$ possible row vectors (including the zero row), and obtain uniquely a singular such matrix.

Second case: Two rows are identical, but a third row is not. In this case, we have a choice of $$^3C_2 = 3$$ choices for the two rows that will be the same. There will be $$2^3 = 8$$ choices for this row, and then $$2^3 - 1 = 7$$ choices for the other row, totalling $$3 \times 8 \times 7 = 168$$ possibilities.

Third case: Each row is unique, but one of the rows is the zero row. In this case, we have $$^3C_1$$ possible rows to make zero, $$2^3 - 1 = 7$$ possibilities for the topmost non-zero row, and then $$2^3 - 2 = 6$$ possibilities for the bottommost non-zero row, for a total of $$3 \times 7 \times 6 = 126$$ possibilities.

Fourth case: Each row is unique, and none of the rows are zero. In order to get a zero determinant, we still need the rows to be linearly dependent. So, one of the rows needs to be a linear combination of the others. I claim that one row must be the sum of two other rows. For the sake of not interrupting the flow, I shall prove this claim at the end.

So we have $$^3C_1 = 3$$ choices of row that can be the sum of the other two, and this row will be completely determined by the other two rows. The other two rows obviously cannot have a one in the same column, because this will result in a two in the matrix. With this in mind, we split into three subcases:

Subcase 4a: Each of the two rows to be summed only contain a single one, and two zeros. In this case, we have $$^3C_1 = 3$$ possibilities for the topmost summand row, and $$^3C_1 - 1 = 2$$ possibilities for the bottommost summand row, for a total of $$3 \times 2 = 6$$ possibilities.

Subcase 4b: The topmost summand row has two ones, and a single zero, whereas the bottom summand row has a single one and two zeros. In this case, we have $$^3C_2 = 3$$ choices of where to put the ones in the topmost summand row. The bottommost summand row is completely determined by this choice (the one has to be placed where the zero was placed in the top summand row). So, we have a total of $$3$$ possibilities.

Subcase 4c: The bottommost summand row has two ones, and the bottommost summand row has a single one. This is just a symmetry of the above subcase, and still has $$3$$ possibilities.

In total for case four, we have: $$3 \times (6 + 3 + 3) = 36$$ possibilities.

Therefore in total over all the cases, we get: $$8 + 168 + 126 + 36 = 338,$$ as expected.

We have, under assumption, some linear dependence of the form $$a_1 r_1 + a_2 r_2 + a_3 r_3 = 0$$ where $$r_1, r_2, r_3$$ are the row vectors. If $$a_i = 0$$ for some $$i$$, then this would imply two rows are parallel, but the facts that they consist of zeros and ones and are not all zeros imply that they would be equal. Therefore $$a_1, a_2, a_3$$ are non-zero.

Without loss of generality, let's suppose that $$r_1$$ has the most ones out of all three rows (I'm OK if it has as many ones as another row, but I don't want $$r_2$$ or $$r_3$$ to have more ones than $$r_1$$). We have, $$(-a_1)r_1 = a_2r_2 + a_3r_3.$$ There must be a column in which $$r_1$$ has a one. Note that at least one of $$r_2$$ and $$r_3$$ needs to have a one in the same column, otherwise the left side cannot equal the right side. If only $$r_2$$ has a one in this column, then $$-a_1 = a_2$$. If only $$r_3$$ has a one in this column, then $$-a_1 = a_3$$. If both have a one in this column, then $$-a_1 = a_2 + a_3$$, but if this is the case for every column, then both $$r_2$$ and $$r_3$$ have at least as many ones as $$r_1$$! Since we assumed $$r_1$$ has the (possibly tied) most number of ones, this implies $$r_1 = r_2 = r_3$$, against assumption (this would put the matrix in the first case!).

So, we must have $$-a_1 = a_2$$ or $$-a_1 = a_3$$. If the former is true, then, $$\frac{a_3}{-a_1}r_3 = r_1 - r_2.$$ The only possible entries in $$r_1 - r_2$$ are $$-1, 0, 1$$. The only possible entries of the right hand side are $$0$$ or $$\frac{a_3}{-a_1}$$ (which, recall, is non-zero). Thus, $$\frac{a_3}{-a_1} = \pm 1 \implies |a_3| = |a_1| = |a_2|$$. Similarly, assuming $$-a_1 = a_3$$ implies that $$|a_1| = |a_2| = |a_3|$$ as well.

Simple division yields: $$r_1 = \frac{a_2}{-a_1} r_2 + \frac{a_3}{-a_1} r_3 = \pm r_2 \pm r_3.$$ If $$r_1 = -r_2 - r_3$$, then $$r_1 + r_2 + r_3$$ contains only non-negative entries, with at least one non-zero entry, and hence cannot equal $$0$$, which is a contradiction. So, one way or another, we have one row is the sum of two others.

The number of $$0-1$$ matrices of that size with three distinct non-zero rows is

$$7\cdot 6 \cdot 5=210$$

So the other $$512-210=\mathbf{302}$$ are definitely singular.

But the matrix $$\begin{pmatrix} 1 & 0& 0\\ 0 & 1& 0\\ 1 & 1 &0 \end{pmatrix}$$

Has three distinct nonzero rows but determinant $$0.$$

Choice of the zero column and then permutations of the rows gives $$\mathbf{18}$$ such.

Another case is $$\begin{pmatrix} 1 & 0& 0\\ 0 & 1& 1\\ 1 & 1 &1 \end{pmatrix}$$

Here choice of the all ones row and then permutations of the columns gives $$\mathbf{18}$$ such.

Convince yourself that nothing was missed, it isn’t hard, to arrive at a total of $$\mathbf{338}.$$

A similar attack on $$4\times 4$$ would be much more involved.