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]])A smaller SSE for the example by Baker
The following two matrices were shown to be SSE by Kirby Baker (Lind and Marcus 1995) by computer search. It is part of the family of examples shown above.
\[A = \begin{pmatrix} 1 & 3 \\ 2 & 1 \end{pmatrix}\] \[B = \begin{pmatrix} 1 & 6 \\ 1 & 1 \end{pmatrix}\]
The equivalence in (Lind and Marcus 1995) is in 7 steps. I managed to simplify some of the matrices in the equivalence. The equivalence is still in 7 steps, but the last two are simpler (the matrices are smaller). Matrices \(A_2, A_3, A_4\) are the same as in the book up to permutations of rows and columns. Matrix \(A_1\) is different from the book, but this is mostly cosmetic.
\[ A = A_0 = \begin{pmatrix} 1 & 3 \\ 2 & 1 \end{pmatrix} = \left(\begin{array}{rrr} 1 & 2 & 0 \\ 0 & 0 & 1 \end{array}\right) \left(\begin{array}{rr} 1 & 1 \\ 0 & 1 \\ 2 & 1 \end{array}\right) \]
\[ \left(\begin{array}{rr} 1 & 1 \\ 0 & 1 \\ 2 & 1 \end{array}\right) \left(\begin{array}{rrr} 1 & 2 & 0 \\ 0 & 0 & 1 \end{array}\right) = \left(\begin{array}{rrr} 1 & 2 & 1 \\ 0 & 0 & 1 \\ 2 & 4 & 1 \end{array}\right) = A_1\]
\[ A_1 = \left(\begin{array}{rrr} 1 & 2 & 1 \\ 0 & 0 & 1 \\ 2 & 4 & 1 \end{array}\right) = \left(\begin{array}{rrrr} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 2 \end{array}\right) \left(\begin{array}{rrr} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 2 & 1 \\ 1 & 1 & 0 \end{array}\right) \]
\[ \left(\begin{array}{rrr} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 2 & 1 \\ 1 & 1 & 0 \end{array}\right) \left(\begin{array}{rrrr} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 2 \end{array}\right) = \left(\begin{array}{rrrr} 0 & 1 & 1 & 2 \\ 0 & 0 & 1 & 2 \\ 0 & 2 & 1 & 2 \\ 1 & 1 & 0 & 1 \end{array}\right) = A_2 \]
\[ A_2 = \left(\begin{array}{rrrr} 0 & 1 & 1 & 2 \\ 0 & 0 & 1 & 2 \\ 0 & 2 & 1 & 2 \\ 1 & 1 & 0 & 1 \end{array}\right) = \left(\begin{array}{rrrr} 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 2 \\ 0 & 2 & 1 & 0 \\ 1 & 1 & 0 & 0 \end{array}\right) \left(\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right) \]
\[ \left(\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right) \left(\begin{array}{rrrr} 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 2 \\ 0 & 2 & 1 & 0 \\ 1 & 1 & 0 & 0 \end{array}\right) = \left(\begin{array}{rrrr} 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 2 \\ 0 & 2 & 1 & 0 \\ 1 & 1 & 0 & 0 \end{array}\right) = A_3 \]
\[ A_3 = \left(\begin{array}{rrrr} 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 2 \\ 0 & 2 & 1 & 0 \\ 1 & 1 & 0 & 0 \end{array}\right) = \left(\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right) \left(\begin{array}{rrrr} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 2 & 1 & 0 \\ 1 & 1 & 0 & 0 \end{array}\right) \]
\[ \left(\begin{array}{rrrr} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 2 & 1 & 0 \\ 1 & 1 & 0 & 0 \end{array}\right) \left(\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right) = \left(\begin{array}{rrrr} 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 2 & 2 & 1 & 0 \\ 2 & 1 & 0 & 0 \end{array}\right) = A_4\]
\[A_4 = \left(\begin{array}{rrrr} 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 2 & 2 & 1 & 0 \\ 2 & 1 & 0 & 0 \end{array}\right) = \left(\begin{array}{rrr} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{array}\right) \left(\begin{array}{rrrr} 2 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{array}\right)\]
\[\left(\begin{array}{rrrr} 2 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{array}\right) \left(\begin{array}{rrr} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{array}\right) = \left(\begin{array}{rrr} 0 & 2 & 3 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array}\right) = A_5 \]
\[A_5 = \left(\begin{array}{rrr} 0 & 2 & 3 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array}\right) = \left(\begin{array}{rr} 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array}\right) \left(\begin{array}{rrr} 0 & 2 & 3 \\ 1 & 1 & 1 \end{array}\right)\]
\[\left(\begin{array}{rrr} 0 & 2 & 3 \\ 1 & 1 & 1 \end{array}\right) \left(\begin{array}{rr} 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array}\right) = \left(\begin{array}{rr} 0 & 5 \\ 1 & 2 \end{array}\right) = A_6\]
\[ A_6 = \left(\begin{array}{rr} 0 & 5 \\ 1 & 1 \end{array}\right) \left(\begin{array}{rr} 1 & 1 \\ 0 & 1 \end{array}\right)\]
\[\left(\begin{array}{rr} 1 & 1 \\ 0 & 1 \end{array}\right) \left(\begin{array}{rr} 0 & 5 \\ 1 & 1 \end{array}\right) = \left(\begin{array}{rr} 1 & 6 \\ 1 & 1 \end{array}\right) = A_7\]
If you want to play with the matrices, here they are ready to be put in sage:
C0 = matrix([[1,3],[2,1]])
R1 = matrix([[1,2,0],[0,0,1]])
S1 = matrix([[1,1],[0,1],[2,1]])
assert R1*S1 == C0
C1 = S1*R1
R2 = matrix([[1,0,0,1], [0,1,0,0], [0,0,1,2]])
S2 = matrix([[0,1,1],[0,0,1],[0,2,1], [1,1,0]])
assert R2*S2 == C1
C2 = S2*R2
R3 = matrix([[0,1,1,1],[0,0,1,2],[0,2,1,0],[1,1,0,0]])
S3 = matrix([[1,0,0,0], [0,1,0,1], [0,0,1,0], [0,0,0,1]])
assert R3*S3 == C2
C3 = S3*R3
R4 = matrix([[1,0,0,0], [1,1,0,0], [0,0,1,0], [0,0,0,1]])
S4 = matrix([[0,1,1,1], [1,0,0,1], [0,2,1,0], [1,1,0,0]])
assert R4*S4 == C3
C4 = S4*R4
S5 = matrix([[2,1,0,0],[0,1,1,0],[1,0,0,1]])
R5 = matrix([[0,1,1],[0,0,1],[1,1,0],[1,0,0]])
assert R5*S5 == C4
C5 = S5*R5
R6 = matrix([[1,0],[0,1],[0,1]])
S6 = matrix([[0,2,3],[1,1,1]])
assert R6*S6 == C5
C6 = S6*R6
R7 = matrix([[0,5],[1,1]])
S7 = matrix([[1,1],[0,1]])
assert R7*S7 == C6
C7 = S7*R7