Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Integrality of matrices, finiteness of matrix semigroups, and dynamics of linear cellular automata

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 the theory of discrete time dynamical systems. Indeed, it gives a complete and easy-to-check characterization of sensitivity to initial conditions and equicontinuity for linear cellular automata over the alphabet $\mathbb{K}^n$ for $\mathbb{K} = \mathbb{Z}/m\mathbb{Z}$, i.e. cellular automata 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).
Complete list of metadata

https://hal.inria.fr/hal-02190317
Contributor : Enrico Formenti <>
Submitted on : Monday, July 22, 2019 - 12:31:32 PM
Last modification on : Friday, June 11, 2021 - 9:26:03 AM

Links full text

Identifiers

  • HAL Id : hal-02190317, version 1
  • ARXIV : 1907.08565

Collections

Citation

Alberto Dennunzio, Enrico Formenti, Darij Grinberg, Luciano Margara. Integrality of matrices, finiteness of matrix semigroups, and dynamics of linear cellular automata. 2019. ⟨hal-02190317⟩

Share

Metrics

Record views

39