AIMS Mathematics (Feb 2024)

Reversibility of linear cellular automata with intermediate boundary condition

  • Chih-Hung Chang,
  • Ya-Chu Yang ,
  • Ferhat Şah

DOI
https://doi.org/10.3934/math.2024371
Journal volume & issue
Vol. 9, no. 3
pp. 7645 – 7661

Abstract

Read online

This paper focuses on the reversibility of multidimensional linear cellular automata with an intermediate boundary condition. We begin by addressing the matrix representation of these automata, and the question of reversibility boils down to the invertibility of this matrix representation. We introduce a decomposition method that factorizes the matrix representation into a Kronecker sum of significantly smaller matrices. The invertibility of the matrix hinges on determining whether zero can be expressed as the sum of eigenvalues of these smaller matrices, which happen to be tridiagonal Toeplitz matrices. Notably, each of these smaller matrices represents a one-dimensional cellular automaton. Leveraging the rich body of research on the eigenvalue problem of Toeplitz matrices, our result provides an efficient algorithm for addressing the reversibility problem. As an application, we show that there is no reversible nontrivial linear cellular automaton over $ \mathbb{Z}_2 $.

Keywords