Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
Integrality of matrices, finiteness of matrix semigroups, and dynamics of linear and additive cellular automata
arXiv (Cornell University)
19 Jul 2019
Abstract
Let $\mathbb{K}$ be a finite commutative ring, and let $\mathbb{L}$ be a
commutative $\mathbb{K}$-algebra. Let $A$ and $B$ be two $n \times n$-matrices
over $\mathbb{L}$ that have the same characteristic polynomial. The main result
of this paper states that the set $\left\{ A^0,A^1,A^2,\ldots\right\}$ is
finite if and only if the set $\left\{ B^0,B^1,B^2,\ldots\right\}$ is finite.
We apply this result to Cellular Automata (CA). Indeed, it gives a complete and
easy-to-check characterization of sensitivity to initial conditions and
equicontinuity for linear CA over the alphabet $\mathbb{K}^n$ for $\mathbb{K} =
\mathbb{Z}/m\mathbb{Z}$ i.e., CA in which the local rule is defined by $n\times
n$-matrices with elements in $\mathbb{Z}/m\mathbb{Z}$. To prove our main
result, we derive an integrality criterion for matrices that is likely of
independent interest. Namely, let $\mathbb{K}$ be any commutative ring (not
necessarily finite), and let $\mathbb{L}$ be a commutative
$\mathbb{K}$-algebra. Consider any $n \times n$-matrix $A$ over $\mathbb{L}$.
Then, $A \in \mathbb{L}^{n \times n}$ is integral over $\mathbb{K}$ (that is,
there exists a monic polynomial $f \in \mathbb{K}\left[t\right]$ satisfying
$f\left(A\right) = 0$) if and only if all coefficients of the characteristic
polynomial of $A$ are integral over $\mathbb{K}$. The proof of this fact relies
on a strategic use of exterior powers (a trick pioneered by Gert Almkvist).
Furthermore, we extend the decidability result concerning sensitivity and
equicontinuity to the wider class of additive CA over a finite abelian group.
For such CA, we also prove the decidability of injectivity, surjectivity,
topological transitivity and all the properties (as, for instance, ergodicity)
that are equivalent to the latter.
Metrics
3 Record Views
Details
- Title
- Integrality of matrices, finiteness of matrix semigroups, and dynamics of linear and additive cellular automata
- Creators
- Alberto DennunzioEnrico FormentiDarij GrinbergLuciano Margara
- Publication Details
- arXiv (Cornell University)
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Mathematics
- Other Identifier
- 991021862233904721