Global Reversibility of Radius-2 1D Finite Linear Cellular Automata with Periodic Boundary Conditions: An Explicit 17th-Order Recurrence Approach
Haolin Zhang, Chao Wang, Ziyu Li, Siyu Liu and Mengyan Zhou
The determinant computation of Toeplitz matrices is a fundamental problem in numerical linear algebra, yet unified explicit recursive formulas for matrices with periodic boundary conditions are currently lacking in the literature. In this paper, we bridge this gap by deriving explicit homogeneous linear recurrence formulas for the determinants of periodic Toeplitz matrices with quaddiagonal and pentadiagonal structures. By establishing an algebraic framework based on characteristic polynomial factorization and auxiliary matrix decomposition, we prove that the determinant sequence of a general periodic pentadiagonal matrix satisfies a homogeneous linear recurrence of order 17. Furthermore, we apply these results to the study of radius-2 1D Linear Cellular Automata. By mapping the reversibility problem to the singularity of transition matrices over finite fields, we provide a rigorous algebraic criterion for determining the global invertibility of such LCAs with periodic boundary conditions. Numerical experiments validate the correctness and computational efficiency of the proposed method.
Keywords: Toeplitz matrix, Periodic boundary condition, Recurrence relation, Linear cellular automata, Reversibility, Characteristic polynomial