# How many $3\times 3$ binary matrices $X$ are there with determinant $0$ and $X^2=X^T$?

How many $3 \times 3$ binary matrices $X$ are there with determinant as $0$ that also satisfy $X^2 = X^T$?

-
There are only $2^9=512$ to check. Not hard for a program. –  Ross Millikan Jul 9 '12 at 3:17
What is the source of the problem? –  Jonas Meyer Jul 9 '12 at 3:17
And only $344$ that are not invertible. –  Arturo Magidin Jul 9 '12 at 3:19
@Hyperbola: Count the nonsingular ones: $7$ possibilities for the first row (any nonzero); anything other than $0$ and the first row for the second row ($6$ possibilities); and anything not in the span of the first two rows for the third row ($4$ possibilities). –  Arturo Magidin Jul 9 '12 at 3:24
Does "binary" here mean $\{0,1\}$ or $\mathbb F_2$? –  Erick Wong Jul 9 '12 at 5:13

There are $2^9=512$ binary $3\times 3$ matrices. Of these, $7\times 6\times 4 = 168$ are invertible, so there are $344$ singular ones.

Here's a somewhat naive way of going about it; I suspect there must be a clever/elegant way of doing it, but I couldn't think of one and then started going down this path. All computations are over $\mathbb{F}_2$.

If the first row of $X$ is all zeros, then so is the first row of $X^2$, so the first column of $X$ must be all zeros. The matrix is of the form $$\left(\begin{array}{ccc} 0 & 0 & 0\\ 0 & a & b\\ 0 & c & d \end{array}\right).$$ Then $$X^2 = \left(\begin{array}{ccc} 0 & 0 & 0\\ 0 & a^2+bc & b(a+d)\\ 0 & c(a+d) & bc+d^2 \end{array}\right).$$ Hence $a^2+bc = a+bc = a$, so $bc=0$. Since $b(a+d)=c$ and $c(a+d)=b$, they are both equal to $0$.

Similar computations hold if the second or third row are equal to $0$. So the matrices that have at least one row equal to $0$ and satisfy the property are diagonal, with arbitrary values in the diagonal, at least one equal to $0$ (we cannot have the identity, because it is nonsingular). That shows that there are exactly $7$ matrices in which a row is equal to $0$.

If no row is equal to $0$, but the matrix is singular, then either the matrix has a repeated row, or the third row is the sum (modulo $2$) of the first two rows. Suppose first that the matrix has the first and second row repeated; then the first two rows of $X^2$ are the same. Since the $(1,1)$ and $(2,1)$ entries of $X^2=X^T$ are equal, that means that the $(1,1)$ and $(1,2)$ entries of $X$ are equal. Since the $(1,2)$ and $(2,2)$ entries of $X^2$ are equal, that means that the $(2,1)$ and $(2,2)$ entries of $X$ are equal. And since the $(1,3)$ and $(2,3)$ entries of $X^2$ are equal, then the $(3,1)$ and $(3,2)$ entries of $X$ are equal. So we have: $$X = \left(\begin{array}{ccc} a & a & b\\ a & a & b\\ c & c & d \end{array}\right).$$ Then $$X^2 = \left(\begin{array}{ccc} a+a+bc & a+a+bc & ab+ab+bd\\ a+a+bc & a+a+bc & ab+ab+bd\\ ac+ac+dc & ac+ac+dc & bc+bc+d \end{array}\right).$$ Therefore, $bc=a$, $bd=c$, $dc=b$. So $c = bd = dcd = cd$. Therefore, either $c=0$ or $d=1$.

If $c=0$, then $a=b=0$, and we have a row of zeros, which we are assuming we do not have. So $c=d=1$. Then $a=b=1$, so we just have the matrix of all $1$s.

Likewise, if the first and third rows are equal, then the first and third rows of $X^2$ are equal, so the $(1,1)$ and $(3,1)$ entries of $X^2$ are equal, hence the $(1,1)$ and $(1,3)$ entries of $X$ are equal; the $(2,1)$ and $(2,3)$ entries are equal; and the $(3,1)$ and $(3,3)$ entries are equal, so $X$ would be $$X = \left(\begin{array}{ccc} a & b & a\\ c & d & c\\ a & b & a \end{array}\right).$$ Similar computations follow, and likewise if the second and third row are equal. So there is only one such singular matrix.

Finally, if no row is zero and there are no repeated rows, then the third row must be the sum of the first two; hence, the same is true in $X^2$. That means that the third column of $X$ must be the sum of the first two, we we have: $$X = \left(\begin{array}{ccc} a & b & a+b\\ r& s & r+s\\ a+r & b+s & a+b+r+s \end{array}\right).$$ Then the $(1,1)$ entry of $X^2$ is $a+rb+(a+r)(a+b) = a+rb+a+ab+ar+rb = a(b+r)$, so $b+r=1$.

The $(1,2)$ entry of $X^2$ is $ab+bs+(a+b)(b+s) = ab+bs + ab+as + b + bs = as+b$, and it must be equal to $r$. So $as+b=r$, hence $as=r+b$, so $as=1$. Therefore, $a=s=1$. Plugging in we have $$X = \left(\begin{array}{ccc} 1 & b & r\\ r & 1 & b\\ b & r & 1 \end{array}\right)$$ with $b+r=1$. A quick check shows both choices work (namely, $b=0$, $r=1$; or $b=1$, $r=0$). This gives two possibilities.

So in total, if I didn't mess up, we have: seven possibilities with at least one row equal to $0$; one possibility with repeated rows; and two more possibilities with two linearly independent rows and the third row a linear combination of the other two, for a total of $10$ such matrices.

-
I wonder if there's a slicker way based on seeing that $X$ is diagonalizable (over, at worst, a quadratic extension) and $X^4=X$. –  Gerry Myerson Jul 9 '12 at 5:01
@Gerry: I'm sure there has to be a slicker way, I just couldn't think of one. –  Arturo Magidin Jul 9 '12 at 5:03
Do you guys think the solution to this problem could help? math.stackexchange.com/questions/148453/… The conclusion of this problem is that any real matrix satisfying the identity $A^2 = A^T$ can only have $0,1,e^{\frac{2\pi i}{3}}, e^{\frac{4\pi i}{3}}$ as eigenvalues. –  Jernej Jul 9 '12 at 18:48
@Azoo: Here, the matrix has eigenvalue $0$; the minimal polynomial divides $t(t-1)(t^2+t+1)$, so the matrix is diagonalizable over $\mathbb{F}_4$. I suspect this could be finessed into a solution that isn't as ugly and pedestrian as the one I give above. –  Arturo Magidin Jul 9 '12 at 19:09