Two square matrices $A$ and $B$ are called elementary strong shift equivalent (denote $A\sim B$) iff there exist non-negative integer matrices $U$ and $V$ (not necessarily square), such that $A=UV$ and $B=VU$. Two square matrices $A$ and $B$ are called strong shift equivalent iff there are square matrices $A=M_{1},M_{2},\ldots,M_{n}=B$ such that $M_i\sim M_{i+1}$ for all $i$. Given are the two following matrices: $$A:=\begin{pmatrix}1&1&0\\1&1&1\\2&2&1\end{pmatrix},\qquad B:=\begin{pmatrix}3\end{pmatrix}.$$ It is not hard to prove that $A$ and $B$ are not elementary strong shift equivalent. However, I have no idea how to prove that they are strong shift equivalent. Any suggestions are greatly appreciated!
This is part of an exercise from the book Introduction to Dynamical Systems by Michael Brin and Garrett Stuck.
Best Answer
By simple inspection, \begin{aligned} \pmatrix{1&1&0\\ 1&1&1\\ 2&2&1} &=\pmatrix{1&0\\ 1&1\\ 2&1}\pmatrix{1&1&0\\ 0&0&1}\\ &\sim\pmatrix{1&1&0\\ 0&0&1}\pmatrix{1&0\\ 1&1\\ 2&1}\\ &=\pmatrix{2&1\\ 2&1}\\ &=\pmatrix{1\\ 1}\pmatrix{2&1}\\ &\sim\pmatrix{2&1}\pmatrix{1\\ 1}\\ &=3. \end{aligned}