# Conjugacy of Subshifts of Finite Type

The goal of this page is to compile for me a list of references on the main open problem of symbolic dynamics: decide if two subshifts of finite type are conjugate.

Formally, this can be defined on matrices as follows: Say two nonnegative square matrices $$A$$ and $$B$$ are elementary SSE if there exists nonnegative matrices R,S s.t. $$A=RS$$ and $$B=SR$$. Then Strong Shift Equivalence (SEE, aka conjugacy) is the transitive closure of elementary SSE.

As an example, the two matrices $$M = \begin{pmatrix} 1 & 2 & 4 \\ 0 & 3 & 3 \\ 1 & 1 & 3 \end{pmatrix}$$ and $$N = \begin{pmatrix} 3 & 4 \\ 1 & 4 \end{pmatrix}$$ are conjugate, as

$$M = \begin{pmatrix} 1 & 2 \\ 0 & 3 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 2 \\ 0 & 1 & 1\end{pmatrix}$$ and $$N = \begin{pmatrix} 1 & 0 & 2 \\ 0 & 1 & 1 \end{pmatrix} \begin{pmatrix}1 & 2 \\0 & 3 \\1 & 1\end{pmatrix}$$.

It is crucial in the definition that the matrices $$R,S$$ are also nonnegative.

# Invariants

One way to study conjugacy is via invariant. An invariant is a quantity $$\phi(M)$$ s.t. $$\phi(M) = \phi(N)$$ whenever $$M$$ and $$N$$ are conjugate.

Here are examples of invariants:

• The spectral radius of the matrix (linked to its entropy)
• The Zeta function of the matrix $$f(t) = 1/det(I-tM)$$

# (Counter)-examples

Conjugacy is not known to be decidable. The examples below are either not known to be conjugate, or I do not know of an easy invariant that proves they are not conjugate.

• $$\begin{pmatrix} 1 & k \\ k-1 & 1\\ \end{pmatrix}$$ and $$\begin{pmatrix} 1 & k(k-1) \\ 1 & 1\\ \end{pmatrix}$$.

They are known to be conjugate for $$k=2,3$$, nothing is known for $$k \geq 4$$ .

• $$\begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}$$ and the matrix $$\begin{pmatrix}2 \end{pmatrix}$$.

This example is due to Ashley

• $$\begin{pmatrix} 0 & 0 & 1 & 1 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0 & 3 & 0 & 0 \\0 &1&0&0&3 & 0 & 0 \\0&0&1&0&3&0&0\\0&0&0&0&0&0&1\\1&1&1&1&10&0&0\\1&1&1&1&0&1&0\\ \end{pmatrix}$$ and $$\begin{pmatrix} 0&0 & 1 & 1 & 3 & 0 & 0 \\ 1 &0 & 0 & 0 & 0 & 0 &0 \\0&1&0&0&0&0&0\\ 0 &0 &1 & 0&0&0&0 \\ 0&0&0&0&0&0&1\\4&5&6&3&10&0&0\\4&5&6&3&0&1&0\end{pmatrix}$$.

These matrices are known not to be conjugate but I don’t know of a proof involving an invariant.

• $$\begin{pmatrix} 0&0&1&1&2&0&0\\1&0&0&0&0&0&0\\0&1&0&0&0&0&0\\0&0&1&0&0&0&0\\0&0&0&0&0&0&1\\1&1&2&1&3&0&0\\1&1&2&1&0&1&0 \end{pmatrix}$$ and $$\begin{pmatrix} 0&0&1&1&2&0&0 \\1&0&0&0&2&0&0\\0&1&0&0&2&0&0\\0&0&1&0&2&0&0\\0&0&0&0&0&0&1\\0&1&0&0&3&0&0 \\0&1&0&0&0&1&0 \end{pmatrix}$$

These matrices are known not to be conjugate but I don’t know of a proof involving an invariant.

If you want to play with the matrices, here they are ready to be put in sage:

AshleyM1 = matrix([[1,1,0,0,0,0,0,0],[0,0,1,0,0,1,0,0],[0,0,0,1,0,0,1,0],[0,1,0,0,1,0,0,0],[0,0,0,1,0,1,0,0],[0,0,1,0,0,0,1,0],[0,0,0,0,1,0,0,1],[1,0,0,0,0,0,0,1]])
AshleyM2 = matrix([[2]])
KRM1=matrix([[0,0,1,1,3,0,0],[1,0,0,0,3,0,0],[0,1,0,0,3,0,0],[0,0,1,0,3,0,0],[0,0,0,0,0,0,1],[1,1,1,1,10,0,0],[1,1,1,1,0,1,0]])
KRM2=matrix([[0,0,1,1,3,0,0],[1,0,0,0,0,0,0],[0,1,0,0,0,0,0],[0,0,1,0,0,0,0],[0,0,0,0,0,0,1],[4,5,6,3,10,0,0],[4,5,6,3,0,1,0]])
WM1=matrix([[0,0,1,1,2,0,0],[1,0,0,0,0,0,0],[0,1,0,0,0,0,0],[0,0,1,0,0,0,0],[0,0,0,0,0,0,1],[1,1,2,1,3,0,0],[1,1,2,1,0,1,0]])
WM2=matrix([[0,0,1,1,2,0,0],[1,0,0,0,2,0,0],[0,1,0,0,2,0,0],[0,0,1,0,2,0,0],[0,0,0,0,0,0,1],[0,1,0,0,3,0,0],[0,1,0,0,0,1,0]])

## References

Kim, K. H., and F. W. Roush. 1999. “The Williams Conjecture Is False for Irreducible Subshifts.” Annals of Mathematics 149 (2): 545–58. https://doi.org/10.2307/120975.
Kitchens, Bruce P. 1998. Symbolic Dynamics. Springer. https://doi.org/10.1007/978-3-642-58822-8.
Lind, Douglas A., and Brian Marcus. 1995. An Introduction to Symbolic Dynamics and Coding. New York, NY, USA: Cambridge University Press.
Wagoner, J. B. 1999. “Strong Shift Equivalence Theory and the Shift Equivalence Problem.” Bulletin of the American Mathematical Society 36 (3): 271–96. https://doi.org/10.1090/S0273-0979-99-00798-3.