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?