MathDB

Strong shift equivalence problem for the Baker matrices and Ashley’s eight-by-eight matrix

Given two square nonnegative integer matrices A∈Nm×mA\in\mathbb{N}^{m\times m} and B∈Nn×nB\in\mathbb{N}^{n\times n}, determine whether they are strong shift equivalent: that is, whether there exist an integer ℓ≥0\ell\ge 0, square matrices A=A0,A1,…,Aℓ=BA=A_0,A_1,\ldots,A_\ell=B, and, for each ii, rectangular nonnegative integer matrices RiR_i and SiS_i such that Ai=RiSiA_i=R_iS_i and Ai+1=SiRiA_{i+1}=S_iR_i. Equivalently, determine whether there is an algorithm deciding strong shift equivalence for every pair of nonnegative integer matrices.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. Conjugacy problem for shifts of finite type

    Given two shifts of finite type, determine whether they are topologically conjugate. This is equivalent to deciding whether their associated nonnegative integer adjacency matrices are strong shift equivalent.

    source: Combinatorial Search for Strong Shift Equivalence

References

Primary source

arXiv

Additional references

computational-algebraoperator-theorysymbolic-dynamics
Posted

Progress summary

Refreshed
Claimed progress

A new paper reports computer evidence for several concrete cases, but the general question remains open.

The problem asks whether specific pairs of nonnegative matrices are strongly shift equivalent, including the Baker family and Ashley’s eight-by-eight example. Strong shift equivalence remains undecidable in general, and no complete resolution of these families is reported.

Known results

  • Baker’s matrices are shift equivalent for every k≥1k \ge 1.
  • Baker proved strong shift equivalence for k=3k=3.
  • Whether the Baker matrices are strongly shift equivalent for all k≥4k \ge 4 was open in the 2024 literature.

September 2026 computational evidence

The paper Combinatorial Search for Strong Shift Equivalence reports explicit computer experiments finding strong shift equivalences for small values of kk in the Baker family and between Ashley’s eight-by-eight matrix and the one-by-one matrix 22. This is claimed computational progress, not a general proof, and is not independently confirmed here.

Current status (as of September 2026): Small Baker cases and Ashley’s matrix are claimed computationally settled, but the claim is unverified and the general Baker question for k≥4k \ge 4, as well as general decidability, remains open.

Sources

Solutions 0

No solutions have been posted yet.