2
$\begingroup$

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

  • 1
    Does "binary" here mean $\{0,1\}$ or $\mathbb F_2$?2012-07-09

1 Answers 1

4

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.

  • 0
    @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.2012-07-09