Talk abstract:

Applications of Symbolic Dynamics to the Structure Theory of Nonnegative Matrices

M. Michael Boyle
Department of Mathematics
University of Maryland
mmb@emmy.umd.edu

I'll discuss the two most dramatic results of the last several years in which symbolic dynamics is contributing to a deeper understanding of the "asymptotic algebra" of nonnegative matrices. Below S represents a unital subring S of the reals R (e.g. Q, R, Z) and S+ denotes the nonnegative elements of S.

Definition 1

The nonzero spectrum of a square matrix A is the unordered k-tuple (d₁, ... , d_k) of nonzero complex numbers such that the characteristic polynomial of A has the form p(t) = t ⁱ(t-d₁)...(t-d_k).

Definition 2

Let E be a subset of R containing 0 and 1. Say A ~ B over E if there exist matrices U,V with entries in E such that A=UV, B=VU. Then strong shift equivalence over E is the equivalence relation on square matrices over E which is generated by the relation ~ . (We are interested in the case E = S+.)

Question 1

What can be the nonzero spectrum of a square matrix over S+?

Question 2

When are two matrices over S₊ strong shift equivalence over S₊?

The motivation for Question 1 is clear. Q1 was solved using symbolic dynamics for the case S=R (and many other cases) in [BH1]. The recent work [KOR] works in a polynomial matrix setting to prove the result for the case S=Z. This setting comes from symbolic dynamics also. This work [KOR] is one of the two dramatic interventions of symbolic dynamics. It is a radical advance for attacking the inverse spectral problem.

It takes more background to appreciate the motivation for the second question, although presumably the relation of strong shift equivalence looks natural enough. The key fact is that shifts of finite type determined by matrices A and B over Z+ are isomorphic as dynamical systems iff A and B are strong shift equivalent over Z+. This isomorphism can be interpreted as saying that the coding constraints corresponding to A and B are essentially the same.

The second key advance is a deeper understanding of when matrices are strong shift equivalent over Z+. Especially: Kim and Roush (advancing on previous work with Wagoner, in a setting created by Wagoner) have given a counterexample to the irreducible Williams conjecture.

Reading

I will give the talk without prerequisites, but of course a listener could get more out of the talk with some preparation (or followup reading). Perhaps the most useful point would be to get a clear idea about what a shift of finite type is; this is elementary but a simple and thorough development takes a bit of time. Then it would be helpful to have seen the relations between properties of the shift of finite type and algebraic properties of its defining matrix, and have some feeling for the meaning of strong shift equivalence.

For the above, the best quick source may be [B1]. (Overlapping [B1] is [B2], which has the advantage of being on my home page.) A thorough introduction, very clear and accessible to nonmathematicians, is [LM].

For background and the main results on the inverse nonzero spectral problem, see [BH1] and [KOR]. There is a similar (fundamental) inverse strong shift equivalence problem, as discussed in [B1]. See [BH2] for more on this.

For the progress on strong shift equivalence and Williams' Conjecture, see [KR1,2] and their references.

References

[B1] M. Boyle,

Symbolic dynamics and matrices, Combinatorial and graph-theoretical problems in linear algebra (Minneapolis, MN, 1991), 1-38, IMA Vol. Math. Appl., 50, Springer, New York, 1993.

[B2] M. Boyle,

Algebraic aspects of symbolic dynamics, 1997 Temuco Lectures,http://www.math.umd.edu/~mmb/

[BH1] M. Boyle and D. Handelman,

The spectra of nonnegative matrices via symbolic dynamics. Annals of Math. (2) 133 (1991), 249-316.

[BH2] M. Boyle and D. Handelman,

Algebraic shift equivalence and primitive matrices. Trans. Amer. Math. Soc. 336 (1993), 121-149.

[KOR] K. H. Kim, N. Ormes and F. W. Roush.

The spectra of nonnegative integer matrices via formal power series, preprint, http://rene.ma.utexas.edu/users/ormes/

[KR1] K. H. Kim and F. W. Roush,

The Williams conjecture is false for irreducible subshifts ERA Amer. Math. Soc. 3 (1997), pp. 105-109. http://www.ams.org/era/home-1997.html

[KR2] K. H. Kim and F. W. Roush,

The Williams conjecture is false for irreducible subshifts Annals of Math. 149, (1999),545-558.

H. Kim and F. Roush,

"The Williams conjecture is false for irreducible subshifts," paper math. DS/9907095 at http://xyz.lanl.gov/list/math.DS

Material used during the talk

Back to Workshop Schedule

Back to Codes, Systems and Graphical Models