Reversibility of linear cellular automata with intermediate boundary condition

1.   Introduction

Cellular automata (CAs) are an intriguing class of discrete models that offer versatile applications across numerous scientific disciplines, such as physics, computer science, and mathematics. A core characteristic of CAs is their representation of an infinite lattice with a finite set of states, and this structure is a crucial aspect of their appeal. The cells within a CA are located at integer coordinates in an $n$-dimensional Euclidean space. The configuration of a CA is commonly expressed as a function $x: \mathbb{Z}^n \to \mathcal{A}$, where $\mathcal{A}$ signifies the finite set of states, and $x_{\mathbf{v}}: = x (\mathbf{v})$ symbolizes the current state of the cell situated at $\mathbf{v} \in \mathbb{Z}^n$. All configurations are encompassed within $\mathcal{A}^{\mathbb{Z}^n}$, which facilitates the modeling of complex systems and their dynamics.

At each discrete time step in a CA, the cells undergo synchronous state transitions governed by a shared local function. The present states of neighboring cells drive these transitions, and the choice of neighborhood configuration plays a pivotal role in the applications that can be simulated using CAs. Researchers have explored various neighborhood structures, with two prominent examples being the von Neumann and Moore neighborhoods. The former consists of cells adjacent to the central cell, typically located north, south, east, and west, while the latter encompasses a more extensive set of neighboring cells, often including those situated diagonally. See ^{[7,10,19,20,22,23,27]} for more details.

One fundamental property that captures the attention of researchers and mathematicians in the study of CAs is reversibility ^[14,17,30]. Reversible cellular automata are of significant interest due to their capacity to fully preserve information. In a reversible CA, any given configuration possesses a unique predecessor, implying that one can trace the history of the system's states backward. This property has profound implications in various scientific contexts, particularly those requiring strict adherence to the principle of microscopic reversibility.

The principle of microscopic reversibility is central to understanding the behavior of physical systems and has wide-ranging applications in fields like statistical and quantum mechanics. It states that in a closed system, the probabilities of transitioning between two states are equal for both the forward and reverse processes. In this sense, reversible CAs find natural application in modeling physical phenomena that adhere to this principle, ensuring that the information encoded in the system remains conserved and traceable. Reversible cellular automata have found applications in many domains, each benefiting from the property of information preservation. Among the notable applications include image security, lattice gases, and cryptography. See ^{[3,12,18,28,29]} for instance.

In practical applications, the number of cells within cellular automata is typically finite, leading to discussions about the challenges of achieving reversibility with different boundary conditions. Various boundary conditions, including periodic boundaries, reflective boundaries, and null boundaries, have been extensively explored in the literature, each presenting unique characteristics and implications. Periodic boundaries have been widely investigated due to their ability to create a seamless, toroidal grid. In this setup, cells at one edge of the grid are considered neighbors with cells at the opposite edge. Researchers have delved into the reversibility of cellular automata under periodic boundary conditions, seeking to understand the conditions and constraints that make these systems behave reversibly ^[8,9]. Reflective boundaries introduce a boundary where cells reflect their state into the grid. This concept mirrors a virtual mirror at the boundary, leading to the consideration of how this reflection affects the reversibility of cellular automata. Studies in this area have explored the properties and behavior of CAs with reflective boundaries, shedding light on the nature of reversibility under such conditions ^[1,2]. Null boundaries involve conditions where cells at the boundary remain in a fixed, null state. The study of null boundary conditions is crucial for understanding how specific boundary constraints impact the overall behavior of the cellular automata. Research in this domain has aimed to elucidate the consequences of null boundaries on reversibility ^[5,31].

While these common boundary conditions have received significant attention, the discussion regarding intermediate boundary conditions has been relatively limited. Intermediate boundary conditions represent a fascinating area of research, where the boundary behavior is neither periodic, reflective, nor null but rather a unique combination of these or other conditions. Studying such intermediate boundaries could provide valuable insights into the spectrum of possible boundary conditions and their effects on reversibility. Additionally, extensive research in one-dimensional cellular automata has been conducted regarding reversibility ^[6]. However, the exploration of multidimensional reversibility remains a relatively less discussed topic.

Multidimensional cellular automata introduce additional complexities compared to their one-dimensional counterparts, and as a result, there is no general theorem for determining the reversibility of multidimensional CAs ^[11,13]. The challenges and conditions for achieving reversibility in multidimensional CAs are of particular interest to researchers because these systems often exhibit more intricate behaviors and interactions. Due to the inherent complexity of multidimensional structures, there are relatively few results regarding the reversibility of CAs with boundary conditions, with most of them focusing on two-dimensional cases. The reader is referred to ^{[5,15,24,25,26]} for some references.

In this paper, we investigate the reversibility of $n$-dimensional linear cellular automata (LCAs) with an intermediate boundary condition over $\mathbb{Z}_p$, where $n \geq 2$. We reveal a decomposition method that can determine reversibility more efficiently. Notably, our algorithm becomes even more efficient as the dimension of the LCAs increases.

While cellular automata (CAs) have received significant attention, the context of hybrid cellular automata (HCAs) has also attracted researchers' interest. For example, in ^[21], authors applied HCAs to study cancer therapy. Furthermore, HCAs are used to simplify and optimize complex topology problems, particularly in dynamic conditions, by leveraging the discrete nature of cellular automata and the computational power of parallel processing (see ^[32] and the references therein). The discussions and findings regarding the reversibility of LCAs proposed in this paper may also have applications to HCAs. Related investigations are currently underway.

The paper is organized as follows. We begin with an introduction to multidimensional LCAs and propose a matrix representation for describing these systems. We recall the properties of Kronecker product and Kronecker sum from matrix theory to facilitate our analysis. Section 3 elucidates the context of two-dimensional LCAs, we present eigenvalue formulas that determine reversibility. We also provide clear reversible conditions for specific two-dimensional examples. In Section 4, we extend our results to multidimensional LCAs. Discussion and conclusion can be seen in Section 5.

2.   Preliminary

In this section, we introduce linear cellular automata with intermediate boundary conditions and the von Neumann neighborhood. Let $\mathbb{Z}_{p}^{\mathbb{Z}^n}$ denote a set comprising sequences $x = (x_{\mathbf{i}})_{\mathbf{i} \in \mathbb{Z}^n}$ over the finite field $\mathbb{Z}_p = \{0, 1, 2, \cdots, p-1\}$. We define $N^\gamma_{\mathbf{z}}$ as the von Neumann neighborhood of range $\gamma$ centered at $\mathbf{z} = (z_1, z_2, \cdots, z_n) \in \mathbb{Z}_n$; to be explicit,

In this context, we focus on the case where $\gamma = 1$ and $\mathbf{z}$ is the origin, and we denote $N^{1}_{\mathbf{0}}$ as simply $N$ for the sake of brevity.

Define $f : \mathbb{Z}_p^{N} \to \mathbb{Z}_p$ as

where $c({\bf{t}})\in\mathbb{Z}_p$ for all ${\bf{t}}\in N$. Given $m_1, m_2, \cdots, m_n\in\mathbb{N}$ such that $m_i\geq3$ for $i = 1, 2, \ldots, n$, we define $[m_1, m_2, \cdots, m_n]$ as the set:

which represents an $n$-dimensional cuboid. An $n$-dimensional cellular automaton with intermediate boundary condition and local rule $f$ is a transformation $T_{f} : \mathbb{Z}^{[m_1, m_2, \cdots, m_n]}_p \to \mathbb{Z}^{[m_1, m_2, \cdots, m_n]}_p$ defined as follows. Write the von Neumann neighborhood $N$ of range one centered at the origin and the local rule $f: \mathbb{Z}_p^{N} \to \mathbb{Z}_p$ as

and

respectively. Then

whenever ${\bf{k}}+N = \{ {\bf{k}}+{{ {{ ν}}}}: {{ {{ ν}}}}\in N\} \subset [m_1, m_2, \cdots, m_n]$. A cell $\mathbf{k} \in [m_1, m_2, \cdots, m_n]$ is called a boundary cell if $\mathbf{k}+N \not\subset [m_1, m_2, \cdots, m_n]$. When $\mathbf{k}$ is a boundary cell, $T_f(x)_{\mathbf{k}}$ can be determined using Algorithm 1.

Figures 1 and 2 illustrate the effect of the boundary conditions for one- and two-dimensional cellular automata, respectively. It can be observed that the evolution of each boundary cell is related to the status of "intermediate" cells.

Let $\theta:\mathbb{Z}_p^{[m_1, m_2, \cdots, m_n]} \to \mathbb{Z}_p^{m_1 m_2 \cdots m_n}$ be a transformation that maps $x \in \mathbb{Z}_p^{[m_1, m_2, \cdots, m_n]}$ into a column vector in $\mathbb{Z}_p^{m_1 m_2 \cdots m_n}$ using the anti-lexicographic order. Given an ordered basis $\upsilon = \{ \upsilon_1, \upsilon_2, \cdots, \upsilon_{m_1m_2\cdots m_n}\}$ for $\mathbb{Z}_p^{[m_1, m_2, \cdots, m_n]}$ in terms of the anti-lexicographic order, let $A_{m_1, m_2, \cdots, m_n}$ be the matrix representation of $T_f$ with respect to $\upsilon$. A straightforward examination demonstrates Theorem 2.1.

Theorem 2.1. Suppose $\theta$ and $\upsilon$ are defined as above. Let $T_f:\mathbb{Z}_p^{[m_1, m_2, \cdots, m_n]} \to \mathbb{Z}_p^{[m_1, m_2, \cdots, m_n]}$ be an $n$-dimensional LCA with intermediate boundary condition and $A_{m_1, m_2, \cdots, m_n}$ be the matrix representation of $T_f$ with respect to $\upsilon$. Then $T_f$ and $T$ are topological conjugate, and the diagram

commutes, where $T y = A_{m_1, m_2, \cdots, m_n} y \pmod{p}$ for all $y \in \mathbb{Z}_p^{m_1 m_2 \cdots m_n}$.

Therefore, we can get a straightforward result from Theorem 2.1.

Remark 2.2. An immediate implication is that the following are equivalent.

1) $T_f$ is reversible;

2) $A_{m_1, m_2, \cdots, m_n}$ is invertible over $\mathbb{Z}_p$;

3) $0$ is not an eigenvalue of $A_{m_1, m_2, \cdots, m_n}$.

Example 2.3 delivers a one-dimensional LCA for the examination of Theorem 2.1 and intermediate boundary condition.

Example 2.3. Given $c_{-1}, c_0, c_{1} \in \mathbb{Z}_p$. Let $T_f: \mathbb{Z}_p^7 \to \mathbb{Z}_p^7$ be a one-dimensional LCA with intermediate boundary condition and local rule $f: \mathbb{Z}^N_p \to \mathbb{Z}_p$ defined as

See Figure 1 for the space of $T_f$. It is seen that $x_3$ is treated as the left neighbor of $x_1$, and $x_5$ is treated as the right neighbor of $x_7$. Therefore,

The matrix representation of $T_f$ is

In order to study the reversibility of two-dimensional LCAs with intermediate boundary condition, we would like to recall the definitions of Kronecker product and Kronecker sum first.

Definition 2.4. Let $A = (a_{i, j}), B = (b_{k, l})$ be $m \times n$ and $p \times q$ matrices, respectively. The Kronecker product $A \otimes B$ of $A$ and $B$ is a $pm \times qn$ matrix defined as

Example 2.5. Let $A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$, $B = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 8 & 7 \end{pmatrix}.$ Then

Definition 2.6. Let $A$ and $B$ be $m \times m$ and $n \times n$ matrices, respectively. The Kronecker sum of $A$ and $B$ is defined as

where $I_k$ denotes the $k \times k$ identity matrix.

The subsequent proposition outlines an efficient method for solving the eigenvalues of the primary matrix by decomposing its components through the Kronecker sum. Essentially, this proposition serves as a dimensionality reduction approach, facilitating the identification of eigenvalues from the decomposed components.

Proposition 2.7. ^[16] Suppose $\{\lambda_i\}_{i = 1}^m$ and $\{\mu_i\}_{i = 1}^n$ are the sets of eigenvalues of $A$ and $B$, respectively. Then $\{ \lambda_i+\mu_j\}_{1 \leq i \leq m, 1 \leq j \leq n}$ is the set of eigenvalues of $A \oplus B$.

3.   Reversibility of 2-D LCAs

This section plays a crucial role in this paper, as it provides the foundation for extending the discussion to general cases. We shift our focus to the examination of two-dimensional cellular automata featuring an intermediate boundary. We demonstrate that these automata can be deconstructed into two smaller matrices, representing one-dimensional cellular automata. By summing the eigenvalues of these one-dimensional components, we discern the eigenvalues characterizing the two-dimensional cellular automata. This process not only aids in determining eigenvalues but also proves instrumental in assessing the reversibility of the two-dimensional cellular automata.

Consider the von Neumann neighborhood $N = \{ (-1, 0), (1, 0), (0, 0), (0, -1), (0, 1)\}$, and let $f:\mathbb{Z}_p^{N} \to \mathbb{Z}_p$ be a local rule defined as follows:

for some $c_0, c^{1}_{-1}, c^{1}_{1}, c^{2}_{-1}, c^{2}_{1}, \in \mathbb{Z}_p$. Let $T_f: \mathbb{Z}^{[m_1, m_2]}_p \to \mathbb{Z}^{[m_1, m_2]}_p$ be a two-dimensional LCA with intermediate boundary condition and local rule $f$. Denote $K_n(a, b, c)$ by

It is straightforward to see that the matrix representation of $T_f$ is

where $K_{m_1} = K_{m_1}(c_0, c_{-1}^{1}, c_{1}^{1})$ and $0_{m_1}$ is the $m_1 \times m_1$ zero matrix.

Notably, we can express

as the Kronecker sum of $K_{m_1}(c_0, c_{-1}^1, c_{1}^1)$ and $K_{m_2}(0, c_{-1}^2, c_{1}^2)$.

The following theorem follows from the observation above and Proposition 2.7.

Theorem 3.1. Suppose $A_{m_1, m_2}$ is the matrix representation of two-dimensional LCA $T_f$ with intermediate boundary condition and local rule $f$ given as (3.1). Then the set of eigenvalues of $A_{m_1, m_2}$ is

Proof. The discussion above demonstrates that

Notably, $K_{m}(a, b, c) = a \oplus K_m (0, b, c)$. Hence, we have

and

The proof is complete. □

Example 3.2. Suppose $p = 3$, $m_1 = 4$, and $m_2 = 5$. Let $T_f:\mathbb{Z}_3^{{[4, 5]}} \to \mathbb{Z}_3^{[4, 5]}$ be the LCA with local rule

See Figure 2 for the domain of $T_f$ and how intermediate boundary condition affects the evolution of cells in cellular atuomata.. The matrix representation of $T_f$ is

where $K_4 = K_4(1, 1, 1)$. It is seen that $A_{4, 5} = I_5 \otimes K_4(1, 1, 1) + K_5(0, 1, 1)\otimes I_4$.

Since the sets of eigenvalues of $K_4(0, 1, 1)$ and $K_5(0, 1, 1)$ in $\mathbb{Z}_3$ are $\{0, 2\}$ and $\{1, 2\}$, respectively, the set of eigenvalues of $A_{4, 5}$ is

Conclusively, $T_f$ is irreversible.

Theorem 3.1 indicates that the eigenvalues of $K_m(0, a, b)$ play a crucial role in determining the reversibility of $T_f$. Theorem 3.3 reveals that characterizing the eigenvalues of a special type of Toeplitz matrix $T_{m-3}(a, b)$ is equivalent, where $T_n(a, b)_{i, j}$ is defined as

Theorem 3.3. Suppose $m \geq 3$, and $c_{-1}, c_{1} \in \mathbb{Z}_p$ are given. Then

Proof. For $1 \leq k \leq m-3$, denote by $P_k$ and $Q_k$ as $m \times m$ elementary row and column matrices, respectively. More explicitly,

And

To achieve the desired result, we start with applying column operation to substitute all the zeros in the right upper block as follows. Observe that

Inductively, we have

Then, we apply row operation to eliminate the right upper block as follows:

We derive that

Therefore,

This completes the proof. □

Suppose that $c_{-1}$ and $c_1$ are given. Let $\mu$ and $\nu$ satisfy

respectively. Given $m \geq 3$, set

Since the only eigenvalue of $T_{m-3}(c_{-1}, c_1)$ is $0$ whenever $c_{-1} \cdot c_1 = 0$, it remains to consider the case where $c_{-1} \cdot c_1 \neq 0$. If this is the case, it is seen in ^[4] that

A routine computation reveals that, when $p \geq 3$,

Herein, $\frac{1}{2}$ denotes the reciprocal of $2$ in $\mathbb{Z}_p$. Conclusively, we have derived the following corollary.

Corollary 3.4. Suppose $m \geq 3$ and $c_{-1}, c_1$ are given. Let $\mathbb{F} = \mathbb{Z}_p(\mu, \nu, \eta_{m-3; 1}, \ldots, \eta_{m-3; m-2})$ be the splitting field for the characteristic polynomial of $K_m(0, c_{-1}, c_1)$. Then

In the remainder of this section, we will investigate the reversibility of a class of LCAs with local rules that satisfy $c_{-1}^1 = c_{-1}^2 = c_{-1}$, $c_{1}^1 = c_{1}^2 = c_{1}\in\mathbb{Z}_p$, and $p\geq 3$. In this case, we have $A_{m_1, m_2} = c_0 \oplus K_{m_1}(0, c_{-1}, c_{1})\oplus K_{m_2}(0, c_{-1}, c_{1})$.

Corollary 3.5. Suppose $m_1, m_2 \in \mathbb{N}$ and $c_{-1}\cdot c_{1} = 0$. Write $c_{-1}+c_{1} = \alpha c_0$. Then $T_f$ is reversible if and only if $c_0 \neq 0$ and

(i) $\alpha \neq 1, \frac{p-1}{2}$ if $\mu \notin \mathbb{Z}_p$;

(ii) $\alpha \neq 1, \frac{p-1}{2}$ and $(1\pm\mu)\alpha\neq 1, p-2$ if $\mu \in \mathbb{Z}_p$.

Proof. Without loss of generality, we assume $c_1 = 0$. Then $c_{-1} = \alpha c_0$. Theorem 3.1 and Corollary 3.4 demonstrate that

Suppose $\mu \notin \mathbb{Z}_p$. It is seen that the eigenvalues of $A_{m_1, m_2}$ in $\mathbb{Z}_p$ are $(1+2\alpha)c_0$ and $(1-\alpha)c_0$. Thus, $T_f$ is reversible if and only if $c_0 \neq 0$ and $\alpha \neq 1, (p-1)/2$.

When $\mu\in\mathbb{Z}_p$, $T_f$ is reversible if the other two eigenvalues $(2+(1 \pm \mu)\alpha)c_0/2$ and $(1-(1 \pm \mu)\alpha)c_0$ are also nonzero. Therefore, $T_f$ is reversible if $\alpha \neq 1, (p-1)/2$ and $(1\pm\mu)\alpha\neq 1, p-2$. □

Corollary 3.6. Suppose $3 \leq m_1, m_2 \in \mathbb{N}$ and $c_0 = 0$.

(1) Suppose $c_{-1}\cdot c_{1} = 0$ or $c_{-1} = -c_{1}$ or $m_1, m_2$ are both even. Then $T_f$ is irreversible.

(2) Suppose $c_{-1} = c_{1} \neq 0$ and $m_1, m_2$ satisfy $3 \nmid (m_i-2)$ and $\gcd(m_1-2, m_2-2) = 1$. Then $T_f$ is reversible.

Proof. (1) The irreversibility of $T_f$ when $c_{-1}\cdot c_{1} = 0$ or $c_{-1} = -c_{1}$ comes immediately from Corollary 3.5. For the case both $m_1$ and $m_2$ are even, Corollary 3.4 infers that $0 \in \Lambda(K_{m_i}(0, c_{-1}, c_{1}))$ for $i = 1, 2$. Hence, $T_f$ is not reversible since $0 \in \Lambda(A_{m_1, m_2}) = \Lambda(K_{m_1}(0, c_{-1}, c_{1}))+\Lambda(K_{m_2}(0, c_{-1}, c_{1}))$.

(2) Let $c_{-1} = c_{1} = c$. Observe that

where $r_i = 1, \ldots, m_i-3$ and $i = 1, 2$. Thus, $T_f$ is reversible if and only if

It is easy to see that $\cos \frac{r_i \pi}{m_i-2} = \frac{-1}{2}$ for some $r_i$ if and only if $m_i-2$ is a multiple of $3$. Notably,

for some $r_1, r_2$. Moreover,

Since $r_1 < m_1-2$ for all $r_1$, the equality in the right hand side holds if and only if $m_1-2$ and $m_2-2$ are not relatively prime. This completes the proof. □

4.   Reversibility of multidimensional LCAs

In this section, we extend Theorem 3.1 to $n$-dimensional LCAs with intermediate boundary conditions. Let $e_i$ denote the $n$-dimensional binary vector with its only nonzero entry at the $i$th coordinate. Set $N = \{\mathbf{0}, \pm \mathbf{e_1}, \pm \mathbf{e_2}, \ldots, \pm \mathbf{e_n}\}$. Consider $T_f: \mathbb{Z}_p^{m_1 \times m_2 \times \cdots \times m_n} \to \mathbb{Z}_p^{m_1 \times m_2 \times \cdots \times m_n}$, which is an $n$-dimensional LCA with intermediate boundary conditions and a local rule $f: \mathbb{Z}_p^N \to \mathbb{Z}_p$, defined as

where $c_0, c^i_1, c^i_{-1} \in \mathbb{Z}_p, 1 \leq i \leq n,$ are given constants. Similar to the discussion in the previous section, we decompose the matrix representation $A_{m_1, \cdots, m_n}$ of $T_f$ into the Kronecker sum of smaller matrices.

Proposition 4.1. Let $T_f$ be an LCA with intermediate boundary condition and local rule $f$ as defined above. Then the matrix representation $A_{m_1, \cdots, m_n}$ of $T_f$ is decomposed as

Furthermore, the set of eigenvalues of $A_{m_1, \cdots, m_n}$ is

Before addressing the proof, the following example of three-dimensional case exhibits an initial observation.

Example 4.2. Consider three-dimensional LCA $T_f$ on a cuboid of dimension $m_1 \times m_2 \times m_3$ with local rule

Algorithm 1 reveals the matrix representation as

where $A_{m_1, m_2}$ is defined in the previous section. It is seen that

Proof of Proposition 4.1. We prove this using mathematical induction. We already know from Theorem 3.1 that (4.1) holds for $n = 2$.

Now, assume that

As shown in Example 4.2, the matrix representation $A_{m_1, m_2, m_3}$ of a $3$-dimensional LCA can be decomposed into the Kronecker sum of the matrix representations of one- and two-dimensional LCAs, respectively. Analogously, it can be examined without difficulty that the matrix representation of an $n$-dimensional LCA can be decomposed into the Kronecker sum of the matrix representations of one- and $(n-1)$-dimensional LCAs, respectively.^* That is,

^*In fact, the matrix representation of an $n$-dimensional LCA can be decomposed into the Kronecker sum of the matrix representations of $r$- and $s$-dimensional LCAs, respectively, where $r, s \in \mathbb{N}$ and $r+s = n$.

This completes the proof by mathematical induction. □

Corollary 4.3. Let $T_f$ be an LCA with intermediate boundary condition and local rule $f$ as defined above. Then, $T_f$ is reversible if and only if, for $1 \leq i \leq n$, there exist no $\lambda_i \in \Lambda(K_{m_i}(0, c^{i}_{-1}, c^{i}_{1}))$ such that $c_0 + \sum\limits_{i = 1}^n \lambda_i = 0$.

Proposition 4.4. Nontrivial LCAs with intermediate boundary conditions over $\mathbb{Z}_2$ are irreversible.

Proof. For any $a, b \in \mathbb{Z}_2$ and $m \geq 3$, the demonstration of Corollary 3.4 shows that $0$ and $1$ are both eigenvalues of $K_m(0, a, b)$ unless $a = b = 0$. Therefore, $0$ is always an eigenvalue of $A_{m_1, \cdots, m_n} = K_{m_1}(c_0, c^{1}_{-1}, c^{1}_{1}) \oplus \overset{n}{\underset{i = 2}{\oplus}} K_{m_i}(0, c^{i}_{-1}, c^{i}_{1})$ unless $c_0 = 1$ and $c_j^i = 0$ for all $i, j$. This completes the proof. □

5.   Conclusions

This paper aims to investigate the reversibility of multidimensional linear cellular automata (LCAs) with an intermediate boundary condition. Our focus is on LCAs defined over the prime field $\mathbb{Z}_p$, where each cell interacts with its nearest neighbors using the one-norm. The question of whether $T_f$ is reversible is equivalent to determining the invertibility of its matrix representation, denoted as $A$. To tackle this question, we propose a method to decompose $A$ into a Kronecker sum of smaller matrices. The core idea is to assess the invertibility of $A$ by examining whether $0$ can be expressed as a linear combination of eigenvalues of these smaller matrices. Importantly, each of these smaller matrices represents a one-dimensional LCA. Therefore, our approach involves breaking down an $n$-dimensional LCA into a combination of one-dimensional LCAs, leading to an efficient algorithm for determining the reversibility of $T_f$. To be explicit, we demonstrate that the matrix representation $A$ of $T_f$ can be expressed as:

where $\oplus$ represents the Kronecker sum, and $K_{m_i}(c^{i}0, c^{i}{-1}, c^{i}_{1})$ is a tridiagonal Toeplitz matrix for $1 \leq i \leq n$. The reversibility of $T_f$ is determined by the presence of zero eigenvalues in $A$, reducing the problem to computing eigenvalues of tridiagonal Toeplitz matrices with significantly smaller dimensions.

While this eigenvalue problem is simplified when the prime field $\mathbb{Z}_p$ is used, challenges arise when considering the coefficient ring $\mathbb{Z}_m$ instead, where $m$ is a positive integer larger than $1$. It remains an open question whether a practical approach can be developed to determine the reversibility of $T_f$ in this more general setting.

Furthermore, the structure of matrix $A$ varies significantly in cases involving LCAs with extended neighborhoods. Ongoing research is aimed at exploring this distinct scenario in greater detail.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The first author is partially supported by the National Science and Technology Council, ROC (Contract No NSTC 112-2115-M-390-003).

Conflict of interest

The authors confirm that they have no conflict of interest in this paper.