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.

Answer 2

Here's a proof that doesn't require any computer search. By the way, the question stems from a proof in Chapter 7 of Combinatorial Set Theory.

Let's intend your matrices as relations $R_1,\dots,R_4$, so that we want to show that any arbitrary product $P$ of these relations or of their inverses has a fixed point, i.e. some label $i\in\{1,2,3,4\}$ with $P(i,i)$. In terms of visualization it can be useful to draw each relation as a bipartite graph, and product of relations as juxtaposition of the corrisponding graphs. For instance, $R_1$ will can be represented with the following picture:

Now, let's divide the four labels into two classes: the first class contains lables $1$ and $2$, whereas the second class contains the labels $3$ and $4$.

First remark: a quick hand-search should confirm the following: assume that you are in some label $i$. Then there is exactly one relation among $R=\{R_1,\dots,R_4,R_1^{-1},\dots, R_4^{-1}\}$ which forces you to end up in a different class. For instance, if $i=1$ then the relation is $R_2$, if $i=2$ then it would be $R_1$, etc. Notice that it's never the inverse of some basic relation.

Second remark: For any relation in $R$, we always have more than a choice of where to go, unless it's an inverse and we're in a specific class. Again, for instance, if we're in class $1$ and we need to "traverse" $R_1^{-1}$.

Considering at the same time these two remarks allows us to conclude that we can always choose to stay in the same class, unless we're for instance in class $1$ and we encounter $R_1^{-1}$ followed by $R_2$, as we would surely end up in class $2$ (but, notice, we have a choice of where to end up within the class). Notice that there are exactly $4$ such combinations of relations, explicitely $R_2\circ R_1^{-1}, R_1\circ R_2^{-1}, R_3\circ R_4^{-1}, R_4\circ R_3^{-1}$, and that they are pairwise disjoint. We can then consider the last such combination that appears in our product of relations. We look for our fixed point in the target class of the last appearing such combination, as we know that we can end up in the same class if we start from there.

To make sure that we end up in the same label as well as in the same class, we consider again the second remark from above and look at the last relation we have to traverse. Indeed, from the remark it follows that we have to worry only if WLOG we want to start (and finish) in class $1$ and the last relation is $R_1^{-1}$ (or $R_2^{-1}$). Then we clearly have to start from label $1$ (or from label $2$), and since we know that before the last relation we'll be in class $1$, we know we will finish in label $1$ (or in label $2$).

The proof isn't particularly elegant or insightful, but at least it can be fully carried on by hand.