Introduction

Welcome to John Wilmes' website for his DIMACS REU on shift equivalence.

Shift equivalence is an equivalence relation on matrices that arises naturally out of the study of dynamical systems. Two integral matrices $A$ and $B$ (not necessarily of the same dimension) are shift equivalent if there exist matrices $R$ and $S$ and a positive integer $l$ such that the following four equations are satisfied:


Although shift equivalence is easy to characterize, the shift equivalence class of an arbitrary integral matrix is not. Given two arbitrary matrices $A$ and $B$, it is not known in general how to determine whether or not they are shift equivalent, short of finding the required $R$ and $S$ through brute force computation. However, some easily computed necessary conditions are known.

The Jordan canonical form of a matrix is invariant under shift equivalence, as is the generalized Bowen-Franks group of a matrix. The Jordan form of a matrix is familiar from linear algebra. For any $n\times n$ matrix $A$ and any polynomial $p(t) \in \mathbb{Z}[t]$ such that $p(0) = \pm 1$, the generalized Bowen-Franks group $BF_p(A)$ of a matrix $A$ induced by $p$ is the quotient $\mathbb{Z}^n/\mathbb{Z}^np(A)$. If ${d_1, d_2, \ldots, d_r}$ is the set of elementary divisors of $p(A)$, then we can write the generalized Bowen-Franks group as


where $\mathbb{Z}_0 = \mathbb{Z}$.

Under the direction of Dr. Debbie Yuster, I am currently studying the shift equivalence classes of sparse matrices with nonzero entries $\pm1$. I hope to determine (a) how many shift equivalence classes exist for a given dimension of matrix, (b) how well the known necessary conditions divide matrices into equivalence classes, and (c) how to select polynomials for Bowen-Franks groups that will split a family of matrices into as many equivalence classes as possible.