\section{Introduction}
Cellular automata (CA) are one of the simplest mathematical
models for nonlinear dynamics to produce complex patterns of
behavior.  They had been originally introduced by von
Neumann\cite{Neumann} to investigate some artificial life.
Wolfram had reintroduced CA as a model to
investigate complexity and randomness\cite{Wolfram:1}. He
investigated many fundamental features of
them\cite{Wolfram:2,Wolfram:3,Martin}.
Since then many authors have made efforts to clarify the
properties of CA and applied to natural
systems including biological systems, complex fluids, chemical
reactions, astronomical systems and so on\cite{CA}.

Computational simplicity is the advantages of using CA to
simulate complex behaviors. Discrete states are defined on
each lattice point and evolve with discrete time steps in
CA.  Moreover nonlinear properties are expected to be
emphasized by discretization.  A simple modeling, however,
does not mean simple properties.  Even though the great
efforts, the fundamental properties of CA are still unclear.
Studies on these simple systems seems to be a key for
understanding discretized simulated systems.

One-dimensional CA are described by the discrete time
evolution of site \(a_i\):
\begin{equation}
a_i(t+1) = F[a_{i-r}(t),
a_{i-r+1}(t),\ldots,a_i(t),\ldots,a_{i+r}(t)],
\end{equation}
where $a_i$ takes $k$ discrete values over $Z_k$.  The
simplest models, {\em elementary cellular automata}, consist
of sites with two internal states over $Z_2$ ($k=2$)
interacting with the nearest neighbor sites ($r=1$).
Wolfram introduced a naming scheme for these models and
classified the behavior of CA into four
classes\cite{Wolfram:1,Wolfram:2}.

Most authors have worked on CA within the scope of the
infinite number of sites.  A few works have concerned the
effects of finiteness.  The orbits of {\it cylindrical}
linear CA, which are CA with periodic boundaries, are
analyzed on the basis of {\it characteristic polynomials},
which directly describe the states of linear
CA\cite{Martin,Wolfram:4,Jen,Voorhees,Guan}.  Stevens,
Rosensweig and Cerkanowicz had investigated rule 90 CA,
which will be described in \ref{Model}, with Dirichlet
boundary conditions.  They analyzed the eigenvalue
polynomials of the matrices which give the time evolution of
the system\cite{Stevens}.  In our previous
papers\cite{Tadaki:1,Tadaki:2} (referred as papers I and
II), we had also investigated the periodic orbits of finite
linear CA (rule 90 and 150) with Dirichlet boundary
conditions by analyzing the eigenvalue equations. In the
present paper the method is applied to cylindrical linear
CA. The proof of the classification of the orbits for
Dirichlet boundary cases is given in Appendix
\ref{Appendix-Classify}.

\section{The models and orbits of states}\label{Model}
There are two examples of linear cellular automata in the
elementary ones (\(k=2, r=1\)).  They are called as rule 90
and rule 150 following the Wolfram's naming scheme.  For
rule 90 CA, the time evolution of the $i$-th site
$a_i\in\{0,1\}$($i=1,\ldots,N$) is described as a sum modulo
2 of the nearest-neighbor sites:
\begin{equation}
a_i(t+1)=a_{i-1}(t)+a_{i+1}(t)\bmod2.
\end{equation}
The time evolution of rule 150 CA is given as a sum modulo 2
of the nearest-neighbor sites and itself:
\begin{equation}
a_i(t+1)=a_{i-1}(t)+a_i(t)+a_{i+1}(t)\bmod2.
\end{equation}
We use the periodic boundary conditions: $a_0=a_N,
a_{N+1}=a_1$.  These models belong to the third class which
show the chaotic behavior in the Wolfram's classification

These models are linear because the rules are additive and
the time evolutions are also expressed by the matrices
\begin{equation}
A(t+1)=U A(t),
\end{equation}
where $A(t) =\ ^t(a_1(t),a_2(t),\ldots,a_N(t))$ describes the
state, $N$ bits binary number, at $t$.
The components of the transfer matrices $U$ are given by
\begin{eqnarray}
U_{ij} &=&\cases{1&$j=i\pm1$\cr
                 1&$i=1,\ j=N$\cr
                 1&$i=N,\ j=1$\cr
                 0&otherwise\cr}\quad\hbox{(rule-90)},\\
       &=&\cases{1&$j=i\pm1$\cr
                 1&$j=i$\cr
                 1&$i=1,\ j=N$\cr
                 1&$i=N,\ j=1$\cr
                 0&otherwise\cr}\quad\hbox{(rule-150)}.
\end{eqnarray}

The trajectories of the states can be classified into three
cases with the properties of the transfer matrices as
mentioned in papers I and II (See Fig.~\ref{bigschematic}).
\begin{eqnarray}
U^{\Pi_N}&=&I,\label{periodic}\\
U^{\Pi_N+\pi_N}&=&U^{\pi_N},\label{relaxation}\\
U^{f_N}&=&0,\label{null}
\end{eqnarray}
where $I$ denotes a unit matrix.  The first case,
Eq.~(\ref{periodic}), corresponds to perfectly periodic
motions with the maximum period $\Pi_N$.  Namely all states
belong to perfectly periodic orbits whose period does not
exceed $\Pi_N$.  The second case, Eq.~(\ref{relaxation}),
shows periodic motions with relaxation.  A relaxation path
whose time step is not greater than $\pi_N$ leads to a
periodic orbit with the maximum period $\Pi_N$.  The third,
Eq.~(\ref{null}), is a special case of the second one. All
states are drawn to a null state on the contrary to that the
current CA belong to the third class of Wolfram's
classification of motions (chaotic motions).

\section{Eigenvalue analysis}
The eigenvalue polynomials for $N$-site linear cellular
automata are defined by
\begin{equation}
D^{\rm(R)}_N(\lambda) = \vert U+\lambda I\vert,
\end{equation}
where the index R specifies the rule number and the boundary
condition, for example, 90D for rule 90 CA with Dirichlet
boundaries and 150P for rule 150 with periodic boundaries.
Since each site $a_i$ takes binary values, the eigenvalue
polynomials are over $Z_2$, namely each coefficient is 0 or
1. The eigenvalues $\lambda$ are not usual numbers but over
the Galois field GF($2^N$), a finite field with $2^N$
elements.

The eigenvalue polynomials enable us to find the maximum
period $\Pi_N$ and the maximum relaxation $\pi_N$ as
discussed in Ref. \cite{Stevens}, papers I and II.  For
nilpotent cases, $D^{\rm(R)}_N(\lambda)=\lambda^N$, all
states are drawn into a null state within $N$ steps or less.
If the eigenvalue polynomial has a constant term,
$D^{\rm(R)}_N(0)=1$, the eigenvalue equation
$D^{\rm(R)}_N(\lambda)=0$ can be reduced to a simple form as
$\lambda^{P_N}+1=0$ by multiplying some powers of $\lambda$
and repeatedly substituting the eigenvalue
equation\cite{num}.  Then the minimum value of $P_N$
corresponds to the maximum period $\Pi_N$.  In other words
the maximum period $\Pi_N$ is the minimum integer $m$
satisfying $D^{\rm(R)}_N(\lambda)\vert(\lambda^m-1)$, where
the notation $f\vert g$ denotes $f$ divides $g$.  The
remaining cases are mixture of above two cases as
$D^{\rm(R)}_N(\lambda)=\lambda^{p_N}\times d(\lambda)$,
where the polynomial $d(\lambda)$ has a constant term ($
D^{\rm(R)}_N(0)=0$ and $d(0)=1$). One can evaluate the
maximum period with the above procedure from $d(\lambda)$.
The maximum period is the minimum integer $m$ satisfying
$d(\lambda)\vert(\lambda^m-1)$.  The relaxation length to
periodic orbits is $p_N$.  Actual periods and relaxation
paths are given by divisors of the maximum values
respectively.  They depend on the symmetry of the initial
states as shown in papers I and II.

The eigenvalue polynomials for rule 90 cylindrical CA obey
the relation
\begin{equation}
D_N^{\rm(90P)}(\lambda)=\lambda D_{N-1}^{\rm(90D)}(\lambda).
\label{REL90}
\end{equation}
Orbits of rule 90 cylindrical CA can be
classified as
\begin{eqnarray}
&U^{\Pi_N+1}=U&(N\hbox{ is odd}),\\
&U^{\Pi_N+\pi_N}=U^{\pi_N}\quad&(N\hbox{ is even except }N=2^n),\\
&U^{N}=0&(N=2^n),
\end{eqnarray}
by Eq. (\ref{REL90}) and the classification of orbits for
rule 90 finite CA with Dirichlet boundaries (see Appendix
\ref{Appendix-Classify}).  There are no perfect periodic
orbits by comparing with the Dirichlet boundary cases.

The maximum values of the period and relaxation are derived
from the polynomials
\begin{equation}
D_N^{\rm(90P)}(\lambda) =
\sum_{j=0}^{\lfloor (N-1)/2\rfloor}
\left(C^{N-1}_j\bmod 2\right) \lambda^{N-2j},
\end{equation}
which are the solutions of Eq. (\ref{REL90}), where $\lfloor
x\rfloor$ denotes the largest integer not exceeding $x$ and
\begin{equation}
C^N_j = (-1)^j{N-j\choose j}.
\end{equation}
Some examples of the eigenvalue polynomials are shown in
Table~\ref{poly90}.  Equation (\ref{REL90}) leads that the
maximum period for rule 90 cylindrical CA with $N$ sites are
equal to that for $N-1$-site case with Dirichlet boundaries,
$\Pi_N ({\rm rule\ 90P}) = \Pi_{N-1} ({\rm rule\ 90D})$.

The eigenvalue polynomials for rule 150 cylindrical CA can
be also written with those with Dirichlet boundaries
\begin{equation}
D_N^{\rm(150P)}(\lambda)=(1+\lambda)D_{N-1}^{\rm(150D)}(\lambda).
\label{REL150}
\end{equation}
Orbits can be classified as
\begin{eqnarray}
&U^{\Pi_N}=I&(N\not=3n),\\
&U^{N}=I&(N=2^n),\\
&U^{\Pi_N+\pi_N}=U^{\pi_N}\quad&(N=3n).
\end{eqnarray}
by virtue of the classification of orbits for rule 150 CA
with Dirichlet boundaries.  There are no characteristic
difference from the Dirichlet boundary cases.  No simple
relations on the maximum periods between the periodic and
Dirichlet boundary cases are found.

The maximum periods and relaxations are derived from the
polynomials
\begin{equation}
D_N^{\rm(150P)}(\lambda) =
\left(\sum_{j=0}^{\lfloor (N-1)/2 \rfloor}C^{N-1}_j\bmod2\right)
+\sum_{k=1}^N
\left(\sum_{j=0}^{\lfloor (N-k)/2\rfloor}
C^{N-1}_j {N-2j\choose k}\bmod2\right)
\lambda^k.
\end{equation}
Some examples of the eigenvalue polynomials are shown in
Table~\ref{poly150}.

The actual period and relaxation of the system may be
suppressed by the translational symmetry which the periodic
boundary conditions ensure.  Direct matrix multiplications
are also the tool to find the maximum period and relaxation.
The results are summarized in Table \ref{actual-period} with
those obtained from the eigenvalue analysis.  The suppressed
maximum period, which means the maximum period obtained by
the direct matrix multiplications, are just a half of those
by the eigenvalue analysis.  On the relaxation, the same
situations happen except for the $\pi_N=1$ cases.  The
suppressed maximum periods are plotted in
Figs.~\ref{period90} and \ref{period150}.

As the results from the suppression of the maximum values of
the period and relaxation, we can find a simple relation of
the period of rule 90 CA with periodic and Dirichlet
boundaries.  The period of $N$-site rule 90 cylindrical CA
is half of $N-1$-site rule 90 CA with Dirichlet boundaries.
No such simple relations are found for rule 150 cases.

\section{Summary and Discussion}
The method of the eigenvalue analysis was applied to linear
cellular automata with periodic boundaries.  The
trajectories of the states of CA were classified.  The
maximum values of the period and relaxation were evaluated
by the eigenvalue equations.  For rule 90 cases a simple
relation was found between the eigenvalue polynomials with
periodic boundaries and those with Dirichlet boundaries.

The cylindrical CA enjoy the translational
invariance with periodic boundaries.  This translational
symmetry suppresses the maximum values of the period and
relaxation.

In the previous papers\cite{Tadaki:1,Tadaki:2} I had found
the symmetry of the initial states suppress the period.  So
it is natural that the translational symmetry suppresses the
period and relaxation.  The translational symmetry changes
the form of the transfer matrices $U$ and consequently the
form of the eigenvalue polynomials.  The eigenvalue
polynomials, however, do not tell us the suppression of the
period and relaxation.

The eigenvalue analysis may not be able to handle the
translational invariance well.  The matrix $U$ for rule 90
CA can be decomposed as $U=L+R$, where $L$ and $R$ denote
the translation operation to the left and right direction
respectively.  For rule 150 CA it can be describe as
$U=L+R+I$. Namely the dynamics is described only with the
composition of the translation operation.  This may be the
reason of the different results from the eigenvalue analysis
and the direct matrix multiplications.

Let me investigate the cas of $N=4$ rule 90 CA with periodic
boundary conditions for instance.
The eigenvalue equation is $\lambda^4=0$. This can be expressed with the
transfer matrix $U$ as
\begin{equation}
U^4=(L+R)^4=L^4+R^4=I+I=0,
\end{equation}
where all operations are carried over GF(2).
On the other hand, another identity
\begin{equation}
U^2=(L+R)^2=L^2+R^2=0
\end{equation}
holds by virtue of the identity
\begin{equation}
L^m=R^{N-m}.
\end{equation}
This identity may not be taken account into the eigenvalue
analysis.

\acknowledgements
The author would like to thank S. Matsufuji, K. Niizeki and
S. Takagi for valuable discussions and comments.

