Matrix problems arising fromsymbolic dynamicsMike BoyleUniversity of Maryland(Kansas State UniversityMay 5, 2009)Outline of the talkI.1 Shifts of finite typeI.2 Strong shift equivalenceI.3 SSE and SFTsI.4 Shift equivalenceI.5 More on SSE as a matrix relationI.6 The Spectral ConjecturesI.7 G-SFTsII.1 Polynomial matricesII.2 Positive equivalenceII.3 Positive K-theory1III.1 Flow equivalenceIII.2 Flow equivalence of mixing SFTsIII.3 Equivariant flow equivalence of G-SFTsIV. Flow equivalence of sofic shiftsV. References2I.1. Shifts of finite type• Given: A an n × n matrix over Z+,• view A as adjacency matrix of directed graphGAon vertices 1, 2, . . . , nA(i, j) = number of edges from i to j• Let XAbe t he space of doubly infinite se-quences x = . . . , x(−1), x(0), x(1), . . . suchthat for all n, x(n) is an edge of GA, andx(n + 1) follows x(n) in GA.• XAis naturally a compact metrizable space• σA: XA→ XAis the shift homeomorphism,(σA(x))(n) = x(n + 1).3The topological dynamical system σAis a shiftof finite type (SFT). It is a mixing SFT if thematrix A is primitive (nonnegative, with someAnstrictly positive). The mixing SFTs (anal-ogous to primitive among nonnegative squarematrices) are the basic building blocks and themost important case of SFT.Two top. dyn. systems S and T are topologi-cally conjugate, or isomorphic,S∼=Tif there is some homeomorphism h such thathS = T h. Every SFT is isomorphic to someσA. SFTs play a significant role in dynamicalsystems.To study topological conjugacy of SFTs σAin terms of the defining matrices A, we mustdefine some matrix relations.4I.2. Strong shift equivalenceS := a subset of a ring, containing 0 and 1.Matrices A, B are elementary strong shift equiv-alent over S (ESSE-S) if there exist matricesU, V over S such that A = UV and B = V U.The relation strong shift equivalence over S(SSE-S) is the transitive closure of (ESSE-S).Example.A =2= 11!1 1= U1V1B = 1 11 1!=1 1 11!= V1U1B = 1 11 1!= 1 1 00 0 1!1 00 11 1= U2V2C =1 1 00 1 11 1 1=1 00 11 1 1 1 00 0 1!= V2U25So, A and C are SSE-Z+.A and C are not ESSE-Z+(or even ESSE-R+): it is easy to see that aone-by-one real matrix can only be ESSE to arank one matrix.As another example, if A is a real matrix suchthat Ak6= 0 and Ak+1= 0, then A is SSE-Rto (0) in k elementary steps but not fewer.SSE is clearly a natural relation to consider formatrices. But what does it have to do withsymbolic dynamics?6I.3. SSE and SFTsTHEOREM (Williams, 1973)σA∼=σB⇐⇒ A, B are SSE-Z+BUT it is still unknown if SSE-Z+is decidable,i.e., whether there exists an algorithm whichwill take two matrices and decide whether theyare SSE-Z+.We have no bounds on the sizes of matriceswhich might be involved in a chain of ESSE.So, Williams introduced a more tractable rela-tion, shift equivalence.7I.4. Shift equivalenceDEFN Square matrices A, B are shift equiva-lent over S (SE-S) if ∃ matrices U, V over Sand ` ∈ N such thatA`= UV B`= V UAU = UB BV = V A• SE-Z+is decidable (Kim-Roush)• SE-Z+is conceptual – equivalent to iso-morphism of certain associated ordered mod-ules (Krieger).• A, B are SE-Z+iff(σA)n∼=(σB)nfor all large n8SHIFT EQUIVALENCE CONJECTURE (Williams1974): SE-Z+implies SSE-Z+.Counterexamples (Kim Roush 1992,1999) arefew and so far require quite special conditionson the matrices. Explaining these is beyondthe scope of the talk. Now we want to know,with what extra assumptions does SE-Z+im-ply SSE-Z+?LITTLE SHIFT EQUIVALENCE CONJECTUREIf A over Z+has a single nonzero eigenvaluen, then A and (n) are SSE-Z+.THEOREM (Kim-Roush, 1990) The last con-jecture is true with R or Q in place of Z.POSITIVE RATIONAL SHIFT EQUIVALENCECONJECTURE If A, B are shift equivalent overQ and have all entries positive, then A and Bare SSE-Q+.9I.5. More on SSE as a matrix relationFACT (Williams) For a unital subring S of R,primitive mat rices are SE-S+iff they are SE-S.FACT (Williams,Effros,B-Handelman) For S aPID or Dedekind domain, SE-S implies SSE-S.PROBLEM For which other unital subrings Sof R does S E-S implies SSE-S?At any rate:for primitive matrices over S = Z or Q,SE-S+is equivalent to SSE-S and to SE-S.10For any nonnilpotent matrix A over a PID S(e.g. Z or Q), there is an invertible U overS such that UAU−1has block form A0X0 N!where A0is nonsingular and N is nilpotent tri-angular (or empty). Given likewise B, B0:A, B SSE − Q ⇐⇒ A0, B0SIM − QA, B SSE − Z ⇐= A0, B0SIM − ZFor any unital ring S, we think of SSE-S asa stabilized version of similarity over S. Here,the equivalence relation SSE-S is generated bythe following relations on square matrices overS: similarity over S (A ∼ UAU−1), and A X0 0!∼ A ∼ A 0X 0!(i.e., if in a ma trix row n or column n is allzero, then we can delete row n and colum n).11More facts around SSE as a stabilized similar-ity.The SIM-Z classes of matrices with a givenirreducible characteristic polynomial with rootλ are in bijective correspondence with the idealclasses of Z[λ] (Taussky-Todd). Their SSE-Zclasses are in bijective correspondence with theideal classes of Z[1/λ] (B-Marcus-Trow).Suppose A is a square matrix over Z whosecharacteristic polynomial has no nonzero re-peated root. Then the class of mat rices SE-Zto A is a union of finitely many SI M-Z classes.12I.6. The Spectral ConjecturesLet Λ denote a list of complex numbers andΛnthe list of their nth powers. Let tr(Λ)be the sum of t he entries of Λ. So, if Λ isthe nonzero spectrum ΛAof a matrix A, thentr(Λn) = trace(An).[Remark: det(I − tA) encodes ΛA.]For A over Z+, the trace of Anis the number offixed points of σnA. So, ΛAencodes the periodicpoint counts of σA. What can these counts be?SPECTRAL CONJECTURE (B-Handelman 1991)Suppose S is a subring of R containing 1, and(λ1, ..., λk) is a list of nonzero complex num-bers. Then Λ is the nonzero spectrum of aprimitive matrix over S if the follow ing neces-sary conditions hold.131. (Perron condition) λ1> |λi|, ∀i > 1.2. (Coefficients condition) The polynomial(t − λ1) · · · (t − λk) has all coefficients in S.3. (Trace condition)• If S 6= Z, then for all k, n ∈ N– tr(Λn) ≥ 0,– tr(Λn) > 0 =⇒ tr(Λnk) > 0.• If S = Z, then for all n ∈ N,Xk|nµ(n/k)tr(Λk) ≥ 0where µ is the Mobius function.14The Spectral Conjecture is true for S = R(B-Handelman 1991) and S = Z (Kim-Ormes-Roush, 2000).What is a grand analogue realization conjec-ture for