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\) (Lind and Marcus 1995).
- \(\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 (Kitchens 1998)
- \(\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 (Kim and Roush 1999) 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 (Wagoner 1999) 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]])