Trace of product of matrices with nonzero trace

Question

I have the four matrices $$\begin{pmatrix}1&0&0&0\\1&0&0&0\\0&1&1&1\\0&1&1&1\end{pmatrix},\quad \begin{pmatrix}0&1&0&0\\0&1&0&0\\1&0&1&1\\1&0&1&1\end{pmatrix},\quad \begin{pmatrix}1&1&0&1\\1&1&0&1\\0&0&1&0\\0&0&1&0\end{pmatrix},\quad \begin{pmatrix}1&1&1&0\\1&1&1&0\\0&0&0&1\\0&0&0&1\end{pmatrix}.$$

They have nonvanishing trace. I want to show that any arbitrary product of these four matrices and their transposes also has nonvanishing trace (or, since all entries are nonnegative, it suffices to show that the diagonal entries of said product are non all equal to zero).

I thought about doing it by induction on the number of factors, and using $\textrm{tr}(AB)=\textrm{tr}(BA)$, but I don't get anything useful. Is induction the correct way to do it?

Answer 1

Well, there's an algorithmic way to do it. Consider the directed graph whose vertices are all $2^{16}$ $4 \times 4$ matrices with entries in $\{0,1\}$, with an arc from $A$ to $B$ if $MA$ and $B$ have the same set of nonzero entries where $M$ is one of your four matrices or its transpose. You want to show there is no path from $I$ to a matrix with trace $0$. It will be a finite search, which turns out to be not so bad with the help of a computer. So:

Let $s$ be the function that operates elementwise on a matrix, taking each nonzero element to $1$ and $0$ to $0$.

Let $T_1$ be the set consisting of your matrices and their transposes. There are $8$ of them, all with nonzero trace.

Let $T_2$ consist of all matrices $s(AB)$ where $A \in T_1$ and $B \in T_1$, which are not already in $T_1$. There are $37$ of them, and all have nonzero trace.

Let $T_3$ consist of all matrices $s(AB)$ where $A \in T_1$ and $B \in T_2$, which are not already in $T_1$ or $T_2$. There are $49$ of them, and all have nonzero trace.

Let $T_4$ consist of all matrices $s(AB)$ where $A \in T_1$ and $B \in T_3$, which are not already in $T_1$ or $T_2$ or $T_3$. There are $32$ of them, and all have nonzero trace.

Let $T_5$ consist of all matrices $s(AB)$ where $A \in T_1$ and $B \in T_4$, which are not already in $T_1$ or $T_2$ or $T_3$ or $T_4$. There are none, so our proof is complete.