1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Can you clarify what you mean by "arbitrary products"? Does this include products of any finite length, like $AB^2AC$? $\endgroup$ – Omnomnomnom Mar 4 at 17:17
  • $\begingroup$ I suspect that it would be useful to represent each matrix as a sum of rank-1 matrices. For instance, $$ A = \pmatrix{1\\1\\0\\0}\pmatrix{1&0&0&0} + \pmatrix{0\\0\\1\\1}\pmatrix{0&1&1&1} $$ $\endgroup$ – Omnomnomnom Mar 4 at 17:22
  • $\begingroup$ @saulspatz Not true, e.g. $(0,-1,0,1)^T$ is an eigenvector of the first but not of the second. $\endgroup$ – Robert Israel Mar 4 at 18:06
  • $\begingroup$ @RobertIsrael Yes. I just noticed this, and I don't know what's wrong. numpy gave all the same eigenvectors, but when I switched to a CAS, I get different eigenvectors. I'm trying to track it down. $\endgroup$ – saulspatz Mar 4 at 18:08
  • $\begingroup$ @RobertIsrael I was misinterpreting the output from numpy. I thought I was looking at the transpose of the matrix of eigenvectors. All the matrices have two null eigenvectors, and one each of eigenvalues $1$ and $2$. I don't see how that helps, though. $\endgroup$ – saulspatz Mar 4 at 18:31
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ok, I re-read your proof and understood it :) How did you compute the cardinalities of $T_2,𝑇_3,𝑇_4,𝑇_5$? And do you think there is an algebraic way to do it? $\endgroup$ – nbayo Mar 5 at 10:20
  • $\begingroup$ Explicit enumeration using Maple. $\endgroup$ – Robert Israel Mar 7 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.