# Control of strongly interacting quantum many-body states with an effective
mean-field approach

Muhammad S. Hasan1 T. Fogarty1 J. Li2 A. Ruschhaupt2 Th. Busch1 1Quantum
Systems Unit, Okinawa Institute of Science and Technology Graduate University,
Okinawa, Japan  2School of Physics, University College Cork, Cork, Ireland

###### Abstract

Shortcuts to adiabaticity (STA) are powerful tools that can be used to control
quantum systems with high fidelity. They work particularly well for single
particle and non-interacting systems which can be described exactly and which
possess invariant or self-similar dynamics. However, finding an exact STA for
strongly correlated many-body systems is difficult, as their complex dynamics
cannot be easily described, especially for larger systems. Here, we outline a
method to design STAs for these systems using a mean-field approach that
succinctly captures the strong interaction effects through a quartic nonlinear
term. We show that for the case of the harmonic oscillator with a time-
dependent trap frequency the mean-field approach works exactly and recovers
the well-known STA from literature. To highlight the robustness of our
approach we also show that it works effectively for anharmonic potentials,
achieving higher fidelities than other typical control techniques.

##  I Introduction

The experimental control available to prepare, manipulate and measure ultra-
cold atomic systems has pushed these systems to the forefront of being
simulators for quantum many-body physics [1, 2]. Since their first realisation
in 1995, atomic Bose-Einstein condensates (BECs) have become one of the best
testbeds available to explore and scrutinise many aspects of quantum physics.
The precise control over larger numbers of degrees of freedom have allowed the
investigation of quantum phase transitions, the simulation of condensed matter
systems, the study of many-body quantum interference and the control over
atom-photon interactions, among many others [3, 4].

The main difficulty in developing full control over the dynamics of
interacting quantum many-body systems is that their high spectral density
makes it hard to experimentally isolate specific states. To do this with high
fidelity, one usually needs to resort to techniques that rely on adiabatic
evolution and which therefore do not provide the system enough energy to make
unwanted transitions. However, this leads to additional challenges in real-
time applications since the time consuming nature of adiabatic evolution can
lead to additional noise and decoherence in the system. This intersection
between the need for practicality and the desire for high fidelity gave rise
to the area of shortcuts to adiabaticity [5, 6]. STA techniques manipulate the
evolution of a physical system by driving the dynamics in the direction of the
target state in a rapid non-adiabatic manner, while still achieving high
fidelities. They therefore provide an alternative to the time-consuming
adiabatic methods. Since their inception in 2009, STAs have found countless
applications in areas where fast and robust quantum control is required [7],
including quantum thermodynamics, atom transport and state preparation [8, 9,
10]. The field is constantly evolving and recently enhanced STA have been
introduced and applied [11, 12, 13].

STAs have mostly been developed for single particle and mean-field systems
where scale invariance can be exploited, and experiments involving BECs and
ultracold Fermi gases in harmonic traps have shown that STAs are technically
feasible using modern techniques [14, 15, 16, 17]. However, outside of these
regimes practical STA protocols are rare, as controlling the increased number
of degrees of freedom in interacting many-body systems can be a complex and
difficult endeavour. To design experimentally realisable control ramps for
such systems one therefore has to resort to approximate STA techniques, which
can give high fidelity control via local potentials over a wide range of
interactions [18, 19, 20, 21, 22]. Developing suitable STA techniques for
many-body systems is therefore of significant interest, particularly in the
strongly interacting regimes where large classical and quantum correlations
are present.

In this work we focus on the efficient control of a specific quantum many-body
system consisting of strongly interacting bosons in the Tonks–Girardeau (TG)
limit [23, 24]. The gas is assumed to be trapped in an arbitrary time-
dependent potential and the whole system is confined to a one-dimensional
geometry. While such a system requires a full quantum mechanical many-body
treatment, we use a mean-field model to describe some aspects of its dynamics
effectively [25]. We show that this approach allows us to efficiently
calculate STA pulses for systems with large particle numbers and strong
interactions, and characterise its effectiveness compared to other commonly
used control ramps through the many-body fidelity. Moreover, in the case of a
harmonic trapping potential we retrieve the well known (and exact) STA pulse
for non-interacting particles [6], while for anharmonic traps our method
exhibits high fidelity control and robustness. The manuscript is organised as
follows: in Section II we outline the model of the TG gas and its mean-field
description. In Section III we derive STAs using the mean-field solution for
harmonic and anharmonic traps, and discuss their results for different control
parameters. Finally, in Section IV we discuss potential applications for our
approach and conclude.

##  II System

The quantum many-body system we consider is an ultracold gas of neutral
bosonic atoms of mass $m$, which is strongly confined in two spatial
directions such that it can be effectively described as a one-dimensional
system. In the remaining direction the atoms are trapped in a potential
$V(x,t)$, which can be modulated in time. Since the scattering processes at
low temperatures can be described by point-like interactions of strength $g$
[26], the many-body Schrödinger equation can be written as

$\displaystyle i\hbar\frac{\partial}{\partial
t}\Phi(\mathbf{x},t)=\left[-\sum_{j=1}^{N}\frac{\hbar^{2}}{2m}\right.$
$\displaystyle\frac{\partial^{2}}{\partial x_{j}^{2}}+V(x_{j},t)$
$\displaystyle\left.+g\sum_{k>j}\delta(x_{k}-x_{j})\right]\Phi(\mathbf{x},t)\;.$
(1)

Here $\mathbf{x}=\\{x_{1},x_{2},\dots,x_{N}\\}$ are the coordinates of the $N$
bosons. In the TG limit of infinite repulsive interactions,
$g\rightarrow\infty$, the system can be famously mapped onto a system of non-
interacting fermions, for which the many-body wavefunction can be written in
terms of single-particle states as
$\Phi_{F}(\mathbf{x},t)=\det[\varphi_{n}(x_{j},t)]$ [23]. From this the
bosonic many-body wavefunction can be obtained via
$\Phi(\mathbf{x},t)=A(\mathbf{x})\Phi_{F}(\mathbf{x},t)$, where
$A(\mathbf{x})=\prod_{k>j}\text{sgn}(x_{k}-x_{j})$ is the unit anti-symmetric
function. The description of the dynamics of the system can therefore be
reduced to $N$ single particle Schrödinger equations of the form

$i\hbar\frac{\partial\varphi_{j}}{\partial
t}=\left[-\frac{\hbar^{2}}{2m}\frac{\partial^{2}}{\partial
x_{j}^{2}}+V(x_{j},t)\right]\varphi_{j}\,.$ (2)

Since this mapping from a strongly interacting gas to a collection of non-
interacting single particles often makes the simulation of the dynamical
processes easier, it also seems an enticing approach to construct shortcuts to
adiabaticity for this many-body system, since many methods for constructing
STAs for single particle states exist [27]. However, for a many-body Fermi gas
in an anharmonic potential each particle sees a different local spectral
density and therefore they need to be optimised separately [18, 28]. If one
requires that the STA needs to be driven by a change in a global potential,
one has to either average over all single particle STAs [29] or pick an
optimal individual STA [28]. While both can be effective, neither of these is
perfect for the whole system.

In this work we propose a different approach by approximating the exact many-
body TG system using a non-linear mean-field (MF) description for the gas
wave-function. It has been shown that the density distribution of the TG gas
can be well approximated using a quartic mean-field equation of the form [25]

$i\hbar\frac{\partial\psi}{\partial
t}=\bigg{[}-\frac{\hbar^{2}}{2m}\frac{\partial^{2}}{\partial
x^{2}}+V(x,t)+\frac{\hbar^{2}\pi^{2}}{2m}|\psi|^{4}\bigg{]}\psi\,,$ (3)

with $N=\int|\psi|^{2}dx$. Here the strong interactions between the bosonic
atoms are described by the quartic non-linear term, and the resulting density
distribution $\rho_{MF}=|\psi|^{2}$ closely matches the one of a corresponding
TG gas, $\rho_{TG}=\sum_{j=1}^{N}|\varphi_{j}|^{2}$ (see Fig. 1$(a)$). In the
following, we will derive a shortcut for the non-linear system given by Eq.
(3) and demonstrate its applicability to the many-body TG gas described by Eq.
(1). Except for a class of scale invariant systems [5, 30, 31, 32, 33], it is
difficult to find exact STAs for nonlinear systems. However, effective
approximate methods have been devised [6, 34, 35] and successfully
experimentally implemented [36, 37, 38]. Our STA will in general also be
approximate, as the MF equation does not fully capture the intricacies of the
full many-body state, exemplified by the lack of Friedel oscillations in Fig.
1$(a)$. However, we will show that our approach is amenable to arbitrary
trapping potentials, and can become exact in certain limits.

Figure 1: $(a)$ Densities from the exact solution of the non-linear Eq. (3)
(dotted yellow, MF), for the corresponding TG gas from Eq. (2) (grey, TG) and
from the Thomas–Fermi approximation to Eq. (3) (black, TF). All are for $N=10$
atoms trapped in a harmonic potential (see Sec. III for scaling). The density
of the TG gas displays Friedel oscillations, but otherwise aligns well with
the density obtained from the MF Eq. (3). $(b)$ The shape of the ramp in Eq.
(6) as a function of the scaled time for two overall times (purple, solid and
dotted) and the reference case ($\ddot{b}=0$ in Eq.(6), green, REF).

##  III Design and implementation of shortcuts

###  III.1 Harmonic oscillator

In the following we will focus on power-law potentials of the form
$V(x,t)=\lambda(t)(x^{2}+\gamma x^{4})$, where $\gamma$ is the anharmonicity
factor and $\lambda(t)$ corresponds to a time-dependent trapping strength.
Here we scale all the energies in terms of the harmonic oscillator energy
$\hbar\sqrt{\lambda_{0}}$ and all lengths in terms of
$a_{0}=\sqrt{\frac{\hbar}{m\sqrt{\lambda_{0}}}}$, where $\lambda_{0}$ is the
trapping strength at $t=0$. This leads to the anharmonicity factor $\gamma$
being scaled in units of $a_{0}^{2}$ and the trapping strength in terms of
$\lambda_{0}$. First we investigate the harmonic oscillator ($\gamma=0$) which
is oft-studied in the STA literature due to its analytical tractability and
experimental relevance [39, 34, 40, 35, 41, 42, 22]. To derive the STA for Eq.
(3) we adopt a scaling ansatz for the wavefunction of the form [5]

$\psi(x,t)=\frac{1}{\sqrt{b(t)}}e^{-i\beta(t)}e^{-i\alpha(t)x^{2}}\phi\left(\frac{x}{b(t)}\right),$
(4)

where $\alpha(t)$ is a chirp, $\beta(t)$ is a global phase and $b(t)$ is the
dynamical scaling parameter describing the width of the state [43, 44, 45].
Inserting this ansatz into the mean-field Eq. (3) and making the scaling
transformation $y=\frac{x}{b(t)}$, with $b(t)\in\mathbb{R}$ being a time-
dependent scaling parameter, we get

$i\dot{\phi}=-\frac{1}{2b^{2}}\frac{\partial^{2}\phi}{\partial
y^{2}}+\left[\lambda(t)-\dot{\alpha}+2\alpha^{2}\right]y^{2}b^{2}\phi+\frac{\pi^{2}}{2b^{2}}|\phi|^{4}\phi\\\
+\left[\frac{i\dot{b}}{2b}-\dot{\beta}+i\alpha\right]\phi+y\frac{\partial\phi}{\partial
y}\left[2i\alpha+\frac{i\dot{b}}{b}\right],$ (5)

where the dots represent the time derivative. We set the chirp
$\alpha=-\frac{1}{2}\frac{\dot{b}}{b}$ so that the last term in Eq. (5)
vanishes. We then demand that
$\left[\lambda(t)-\dot{\alpha}+2\alpha^{2}\right]=\frac{\lambda_{0}}{b^{4}}$
so that the equation resembles a harmonic oscillator with stationary trapping
strength $\lambda_{0}$. Substituting the expression for $\alpha$ gives the
equation that establishes the relation between $b$ and the trapping strength
$\lambda(t)$ as

$\lambda(t)=\frac{\lambda_{0}}{b^{4}}-\frac{\ddot{b}}{2b}\;,$ (6)

with $\lambda_{0}=\lambda(0)$. If we substitute $\lambda(t)$ into Eq. (5) we
get

$i\dot{\phi}=-\frac{1}{2b^{2}}\frac{\partial^{2}\phi}{\partial
y^{2}}+\frac{\lambda_{0}}{b^{4}}y^{2}b^{2}\phi+\frac{\pi^{2}}{2b^{2}}|\phi|^{4}\phi\;.$
(7)

Performing a transformation in $t$ such that
$\tau=\int_{0}^{t}\frac{dt}{b^{2}}$ results now in the rescaled Schrödinger
equation for a harmonic oscillator with stationary trapping strength

$i\frac{\partial\Psi}{\partial\tau}=\left[-\frac{1}{2}\frac{\partial^{2}}{\partial
y^{2}}+\lambda_{0}y^{2}+\frac{\pi^{2}}{2}|\Psi|^{4}\right]\Psi$ (8)

where $\Psi(y,\tau)=\phi(y,t)$.

It is worth noting that Eq. (6) is the well-known Ermakov equation of motion
which is synonymous with describing the integrable dynamics of the harmonic
oscillator [5]. The Ermakov equation also appears in single particle and many-
body scale invariant systems, of which the non-interacting Fermi gas and TG
gas are examples [46, 47, 33]. It is also interesting to note that in the case
of changing the trapping strength of a harmonic oscillator in one dimension
within the non-linear framework of the Gross-Pitaevskii equation, where the
nonlinearity is quadratic, $g|\psi|^{2}$, the ansatz (4) works only
approximately, unless the interaction strength is rescaled in time by $b(t)$
[5]. However, we have just shown that in the case of a quartic non-linearity,
the ansatz (4) works exactly, which should translate into the ability of Eq.
(3) to exactly describe the non-equilibrium dynamics of many-body quantum
states in the strongly interacting limit.

To find the exact form of $\lambda(t)$ requires one to choose a suitable
ansatz for the scaling factor $b(t)$. A common and convenient choice is a
polynomial of the form $b(t)=\Sigma_{i=0}^{5}a_{i}t^{i}$, with the boundary
conditions at the beginning ($t=0$) and at the end of the STA ($t=t_{f}$)
given by $b(0)=1$, $b(t_{f})=(\frac{\lambda_{0}}{\lambda_{f}})^{\frac{1}{4}}$
and $\dot{b}(0)=\dot{b}(t_{f})=\ddot{b}(0)=\ddot{b}(t_{f})=0$. The shape of
the resulting STA is strongly dependent on the ramp duration $t_{f}$ (see Fig.
1$(b)$), with larger modulations of the trap strength required to drive the
system to the target state for $t_{f}$ smaller than the characteristic
timescale of the trap $1/\sqrt{\lambda_{f}}$. Meanwhile, when the system is
driven slowly, such that $t_{f}\ggg 1/\sqrt{\lambda_{f}}$, the STA ramp
approaches the adiabatic limit defined by $\ddot{b}=0$, in which it is simply
described by $\lambda(t)=\lambda_{0}/b^{4}$. In what follows we will use this
as a convenient reference ramp (REF) to compare to the STAs derived for
arbitrary $t_{f}$.

To confirm the effectiveness of the STA to drive quantum many-body dynamics we
apply it to the many-body TG state described by Eq. (1) and its effective
mean-field description in Eq. (3). To quantify the success of the driving
protocol we calculate the overlap between the density of the state at the end
of the shortcut, $\rho(x,t_{f})$, and that of the target state, $\rho^{T}(x)$,
as

$\mathcal{O}(t_{f})=\bigg{|}\int_{-\infty}^{\infty}\sqrt{\rho(x,t_{f})\rho^{T}(x)}dx\bigg{|}^{2}\,,$
(9)

which takes the value of $\mathcal{O}(t_{f})=1$ when the target state is
reached exactly.

The density overlap is shown in Fig. 2$(a)$, where one can see that values of
exactly $\mathcal{O}(t_{f})=1$ can be obtained for both the TG gas and its
mean-field description, confirming that the STA derived above works perfectly
for both the nonlinear and many-body systems. In comparison, using the
reference ramp gives density overlaps smaller than unity, which shows that the
target state is not reached (except at the so-called magic times, where the
final state is dynamically unstable). We also note that the density overlap of
the mean-field description closely matches that of the TG gas even when using
the reference ramp, and only shows slight deviations when both systems are
driven far from equilibrium, i.e. when $\mathcal{O}(t_{f})\ll 1$. This
highlights the ability of the mean-field model to accurately describe the
many-body density dynamics.

While the density overlap is a useful metric to compare the mean-field and TG
dynamics, deeper insights can be obtained by considering the many-body
fidelity which describes the overlap of the full many-body states

$\mathcal{F}(t_{f})=\bigg{|}\int_{-\infty}^{\infty}\Phi(\textbf{x},t_{f})\Phi^{T}(\textbf{x})dx\bigg{|}^{2}\,.$
(10)

This will, in particular, give information about the appearance of the
orthogonality catastrophe, which can be detrimental to quantum control of
large systems [29]. However, as the mean-field approach is an effective single
particle representation of the full interacting system, it possesses no
information about many-body effects, and therefore the quantity in Eq. (10)
can only be calculated for the TG model. In general, the many-body fidelity is
difficult to compute for large quantum states, however in the TG limit we can
take advantage of the Fermi-Bose mapping theorem and the decomposition of the
many-body dynamics in terms of single particle states. This allows one to
write the many-body fidelity as

$\mathcal{F}(t_{f})=\left|\mathbf{det}[\mathcal{A}(t_{f})]\right|^{2}\;,$ (11)

where the matrix elements $\mathcal{A}_{l,m}(t_{f})$ are given by

$\mathcal{A}_{l,m}(t_{f})=\int_{-\infty}^{\infty}\varphi_{l}^{*}(x,t_{f})\varphi^{T}_{m}(x)\;dx,$
(12)

with $\varphi_{l}(x,t_{f})$ being the single particle states at the end of the
STA and $\varphi^{T}_{m}(x)$ the target single particle states.

The many-body fidelity for the STA and the reference ramp is shown in Fig.
2$(b)$ as a function of $t_{f}$. Echoing the density overlap we find that
$\mathcal{F}(t_{f})=1$ for all ramp times when using the STA, as it perfectly
drives each of the $N$ single particle states to their respective target
states without any loss in fidelity. Again, this is to be expected as the STA
ramp for the harmonic oscillator is exact and independent of the number of
particles [48, 28, 32].

Figure 2: $(a)$ Density overlap $\mathcal{O}$ of the TG gas (solid) and
obtained from the mean-field approach (dotted) as a function of final time
$t_{f}$ for compressing a harmonic trap ($\gamma=0$) from $\lambda_{0}=1$ to
$\lambda_{f}=10$ using the STA (Eq. (6), purple) and reference ramps
($\ddot{b}(t)=0$ in Eq. (6), green), for $N=10$ particles. $(b)$ Many-body
fidelity $\mathcal{F}$ as a function of $t_{f}$ for the same parameters.

In comparison, the many-body fidelity of the reference ramp shows that the
final state is orthogonal to the target state for ramp times $t_{f}<1$ which
is in stark contrast to the density overlap in Fig. 2$(a)$. This highlights
that care must be taken when quantifying the adiabaticity of driven quantum
systems by considering the density alone, especially for many-body states. In
what follows we will therefore only focus on the many-body fidelity to
quantify the effectiveness of the STA protocols.

###  III.2 Anharmonic traps

Next we explore the effects of an anharmonicity, $\gamma>0$, in the trapping
potential. In general to derive an STA for anharmonic traps the scaling
approach used previously can not be employed. This is due to the breaking of
many-body scale invariance in the system which as a consequence requires
individual equations of motion for each single particle state
$\varphi_{n}(x,t)$ [28]. This makes it exceedingly difficult to find an exact
STA using local potentials only. We are therefore restricted to using
approximate STA techniques to control the system with high fidelity, such as
variational approaches [49, 44, 50]. These STAs rely on minimising the action
on the quantum state by solving the Euler-Lagrange equations. Like in the
scaling approach we will design the STA based on the mean-field approximation
for the TG gas in Eq. (3), which has the following Lagrangian density

$\displaystyle\mathcal{L}=\int_{-\infty}^{\infty}dx\Bigg{[}$
$\displaystyle\frac{i}{2}(\psi\dot{\psi}^{*}-\psi^{*}\dot{\psi})+\frac{1}{2}\left|\frac{d}{dx}\psi\right|^{2}$
$\displaystyle+\lambda(t)(x^{2}+\gamma
x^{4})|\psi|^{2}+\frac{\pi^{2}}{6}|\psi|^{6}\Bigg{]}\;,$ (13)

with the last term describing the interaction. The variational approach is
strongly dependent on the ansatz for the time evolved state $\psi(x,t)$, and
inspired by its success, we choose the same form as for the scaling approach
given in Eq. (4) and which again depends on the scaling parameter $b(t)$.
Applying a change of variables $x=yb(t)$ and dropping the explicit notation of
the time-dependence of the Lagrangian parameters, the Lagrangian itself then
becomes

$\displaystyle\mathcal{L}=-\dot{\beta}N-b^{2}\dot{\alpha}W+$
$\displaystyle\frac{1}{2}\left[\frac{F}{b^{2}}+4\alpha^{2}b^{2}W\right]+b^{2}\lambda(t)W$
$\displaystyle+\lambda(t)\gamma b^{4}J+\frac{\pi^{2}}{6b^{2}}K\;,$ (14)

where $N=\int_{-\infty}^{\infty}dy~{}|\phi(y)|^{2}$,
$W=\int_{-\infty}^{\infty}dy~{}y^{2}|\phi(y)|^{2}$,
$F=\int_{-\infty}^{\infty}dy~{}\big{(}\frac{d\phi(y)}{dy}\big{)}^{2}$,
$J=\int_{-\infty}^{\infty}dy~{}y^{4}|\phi(y)|^{2}$ and
$K=\int_{-\infty}^{\infty}dy~{}|\phi(y)|^{6}$. The Euler-Lagrange equations

$\frac{\partial\mathcal{L}}{\partial
s}-\frac{d}{dt}\bigg{(}\frac{\partial\mathcal{L}}{\partial\dot{s}}\bigg{)}=0\;,$
(15)

for $s=\alpha,b$ and $\beta$ can then be straightforwardly calculated and for
the variational parameter describing the phase, $\beta$, we simply obtain
particle number conservation. The other two give

$\displaystyle 4\alpha^{2}b-2\dot{\alpha}b-\ddot{b}$ $\displaystyle=0,$ (16)
$\displaystyle
4bW\left(\alpha^{2}-\frac{\dot{\alpha}}{2}\right)-\frac{1}{b^{3}}\left(F+\frac{\pi^{2}K}{3}\right)$
$\displaystyle+2b\lambda(t)(W+2\gamma b^{2}J)$ $\displaystyle=0.$ (17)

Solving these for $\lambda(t)$ gives the expression for the ramp as

$\lambda(t)=\frac{1}{2b^{4}[W+2b^{2}\gamma
J]}\left[\left(F+\frac{\pi^{2}}{3}K\right)-\ddot{b}b^{3}W\right]\;,$ (18)

where $W$, $F$, $J$, and $K$ are obtained by integrating the ansatz
wavefunction $\phi(y)$. The boundary conditions on the scaling factor $b$ is
chosen to be same as before except for $b(0)\equiv b_{0}$ and $b(t_{f})\equiv
b_{f}$ which are found by solving the polynomial equations

$\displaystyle 4\gamma
Jb_{0}^{6}+2Wb_{0}^{4}-\frac{F}{\lambda_{0}}-\frac{\pi^{2}K}{3\lambda_{0}}$
$\displaystyle=0,$ (19) $\displaystyle 4\gamma
Jb_{f}^{6}+2Wb_{f}^{4}-\frac{F}{\lambda_{f}}-\frac{\pi^{2}K}{3\lambda_{f}}$
$\displaystyle=0.$ (20)

The choice of the functional form of $\phi(y)$ is crucial for constructing an
accurate STA and a common choice in harmonic and anharmonic traps is a
Gaussian (G) ansatz
$\phi_{\text{G}}(y)=\sqrt{N}\left(\frac{2}{\pi}\right)^{\frac{1}{4}}e^{-y^{2}}$.
This is known to well approximate the density for weakly interacting Bose
gases [51] and also to significantly simplify the calculations. However, it
does not capture the broadening of the wavefunction due to the hardcore
interactions in TG limit. To more accurately describe this a better choice is
to use the Thomas–Fermi (TF) approximation of Eq. (3),
$\phi_{\text{TF}}(y)=\left(\frac{2\mu-2(y^{2}+\gamma
y^{4})}{\pi^{2}}\right)^{\frac{1}{4}}$, where $\mu$ is the chemical potential.
This choice is further motivated by the fact that Eq. (18) reduces to the
harmonic oscillator STA Eq. (6) when $\gamma=0$. The integral constants in
that case are then given by $W=\frac{N^{2}}{2\sqrt{2}}$,
$K=\frac{3N^{2}}{\pi^{2}\sqrt{2}}$ and $F=-\frac{1}{2\sqrt{2}}$. In the limit
$N\rightarrow\infty$ the $\frac{F}{W}$ term vanishes and the STA in Eq. (6) is
recovered, showing that the variational approach becomes exact in the harmonic
trap.

Figure 3: Integrals $W,K,F~{}\text{and}~{}J$ for anharmonicity factor
$\gamma=0.5$ as a function of $N$ for $(a)$ the Gaussian ansatz and $(b)$ the
Thomas–Fermi ansatz. $(c)$ The integrals as a function of $\gamma$ for $N=30$
particles using the Thomas-Fermi ansatz. Note that the units for each curve
are different and given in the text.

In Fig. 3 we show the behaviour of the integral values appearing in the ramp
expression (18) as a function of $N$ for the Gaussian (panel $(a)$) and
Thomas–Fermi ansatz (panel $(b)$), with a fixed anharmonicity strength
$\gamma=0.5$. The presence of the anharmonic term does not affect the Gaussian
ansatz and therefore the terms $W$, $F$ and $J$ are linear in $N$, while the
contribution from the interaction term scales as $K\propto N^{3}$. On the
contrary, the Thomas–Fermi ansatz is by construction strongly dependent on the
anharmonicity of the trap, which in turn affects the scaling of these terms
(see panels $(b)$ and $(c)$). It is immediately apparent that they differ from
the harmonic oscillator case ($\gamma=0$) presented above, as $W\propto
N^{1.745}$, $K\propto N^{2.285}$, $F\propto N^{0.49}$ and $J\propto N^{2.458}$
for an anharmonicity of $\gamma=0.5$. The resultant STA derived from the
Thomas–Fermi ansatz is therefore more amenable to changes in the trap shape,
which should allow for enhanced control of many-body dynamics in different
trapping potentials.

Figure 4: Many-body fidelity as a function of $t_{f}$ for ramps based on
Thomas-Fermi (blue, solid, $TF$) and Gaussian (orange, dashed, $G$) ansätze,
and the reference ramp (green, dotted, $REF$) for $(a)~{}\gamma=0.5$ and
$(b)~{}\gamma=2.0$ for fixed $N=30$ TG particles.

The many-body fidelity as a function of $t_{f}$ for a trap compression from
$\lambda_{0}=1$ to $\lambda_{f}=100$ is shown in Fig. 4. The results are shown
for a system size of $N=30$, for $\gamma=0.5$ in panel $(a)$ and $\gamma=2.0$
in panel $(b)$. Here we compare fidelities from STAs designed with both the
Thomas–Fermi and Gaussian ansätze, and also the reference ramp. Both STAs
perform well compared to the reference, which is not optimised for the chosen
$t_{f}$. However, the STAs are not perfect as they rely on approximations to
the full many-body state and their fidelities rapidly decrease for quick ramps
$t_{f}<1$. Regardless, the Thomas–Fermi STA clearly outperforms the other
ramps for all driving times $t_{f}$, suggesting it is an effective ansatz for
the TG gas.

Figure 5: The many-body fidelity of the TG gas as a function of $N$ for ramps
based on the Thomas–Fermi (blue, solid, $TF$), Gaussian (orange, dashed, $G$)
ansätze, and for the reference ramp (green, dotted, $REF$) at final time
$(a)~{}t_{f}=0.7$ and $(b)~{}t_{f}=1.0$ for fixed anharmonicity $\gamma=0.5$.

As mentioned previously, the many-body fidelity allows to explore the presence
of orthogonality catastrophe (OC), whereby the overlap between two states
decreases with increasing particle number $\langle\Psi|\Phi\rangle\sim
N^{-\delta}$, with $\delta$ the strength of the perturbation [52]. This has
consequences for the ability to control large systems [18] as the quantum
speed limit can vanish in the thermodynamic limit [53, 29]. While exact STAs
allow to circumvent this, approximate STAs will nevertheless be affected by
the OC as the variational ansatz is not exact and the effectiveness of the
STAs will strongly depend on $N$. In Fig. 5 we show the many-body fidelity as
a function of $N$ for two ramps times, $(a)$ $t_{f}=0.7$ and $(b)$ $t_{f}=1$.
The OC is clearly visible in the decay of $\mathcal{F}$ when considering the
dynamics of the reference ramp which vanishes for $N=30$ and $t_{f}=0.7$. The
approximate STAs perform better, arresting the decay of the fidelity and
reducing the effects of the OC, especially when using the Thomas–Fermi ansatz.
Indeed, while simplistic in description, the dependence of the Thomas–Fermi
ansatz on both the trap shape and particle number, coupled with the mean-field
approach presented in this work, suggest that it can be a powerful tool for
controlling strongly interacting many-body states.

##  IV Conclusion

We have shown that the quartic mean-field description of the TG gas can be
used to design effective STAs for strongly interacting many-body states.
Applying this mean-field approach to the harmonic oscillator potential shows
that our chosen ansatz works exactly, resulting in the well-known STA ramp
from literature. To test the robustness of our approach we have considered
anharmonic potentials which require using a variational ansatz for the STA and
which are therefore no longer exact. While perfect fidelity cannot be
preserved for fast driving of the system, the use of the Thomas–Fermi
approximation for the TG density in the variational ansatz allows to construct
an efficient STA when compared to other trial wavefunctions.

Computation of the STA using the mean-field description offers practical
advantages over using the full many-body state, requiring less numerical
resources and being applicable to any trapping potential where the
Thomas–Fermi profile closely matches the systems density. This method could
also be extended to consider weakly interacting many-body states, which can be
approximated by the Gross–Pitaevskii equation, while intermediate interaction
regimes could be described by a superposition ansatz combining both weakly and
strongly interacting regimes [20].

## Acknowledgements

This work was supported by the Okinawa Institute of Science and Technology
Graduate University. The authors are grateful for the the Scientific Computing
and Data Analysis (SCDA) section of the Research Support Division at OIST.
M.S.H. thanks Prof. Nathan Harshman and Mr. David Rea for discussions. T.F.
acknowledges support from JSPS KAKENHI Grant No. JP23K03290. T.F. and T.B. are
also supported by JST Grant No. JPMJPF2221 and JSPS Bilateral Program No.
JPJSBP120227414. J.L. and A.R. acknowledge that this publication has emanated
from research supported in part by a research grant from Science Foundation
Ireland (SFI) under Grant Number 19/FFP/6951.

## References

  * Bloch  _et al._ [2008] I. Bloch, J. Dalibard, and W. Zwerger, Rev. Mod. Phys. 80, 885 (2008).
  * Gross and Bloch [2017] C. Gross and I. Bloch, Science 357, 995 (2017).
  * Schäfer  _et al._ [2020] F. Schäfer, T. Fukuhara, S. Sugawa, Y. Takasu, and Y. Takahashi, Nature Reviews Physics 2, 411 (2020).
  * Takahashi [2022] Y. Takahashi, Proceedings of the Japan Academy, Series B 98, 141 (2022).
  * Muga  _et al._ [2009] J. G. Muga, X. Chen, A. Ruschhaupt, and D. Guéry-Odelin, Journal of Physics B: Atomic, Molecular and Optical Physics 42, 241001 (2009).
  * Chen  _et al._ [2010] X. Chen, A. Ruschhaupt, S. Schmidt, A. del Campo, D. Guéry-Odelin, and J. G. Muga, Phys. Rev. Lett. 104, 063002 (2010).
  * Ruschhaupt  _et al._ [2012] A. Ruschhaupt, X. Chen, D. Alonso, and J. G. Muga, New Journal of Physics 14, 093040 (2012).
  * Torrontegui  _et al._ [2013] E. Torrontegui, S. Ibáñez, S. Martínez-Garaot, M. Modugno, A. del Campo, D. Guéry-Odelin, A. Ruschhaupt, X. Chen, and J. G. Muga, in  _Advances in Atomic, Molecular, and Optical Physics_, Vol. 62 (Academic Press, 2013).
  * Guéry-Odelin  _et al._ [2019] D. Guéry-Odelin, A. Ruschhaupt, A. Kiely, E. Torrontegui, S. Martínez-Garaot, and J. G. Muga, Rev. Mod. Phys. 91, 045001 (2019).
  * Cárdenas-López  _et al._ [2023] F. A. Cárdenas-López, J. C. Retamal, and X. Chen, Communications Physics 6, 167 (2023).
  * Whitty  _et al._ [2020] C. Whitty, A. Kiely, and A. Ruschhaupt, Phys. Rev. Research 2, 023360 (2020).
  * Hauck and Stojanović [2022] S. H. Hauck and V. M. Stojanović, Phys. Rev. Appl. 18, 014016 (2022).
  * Odelli  _et al._ [2023] M. Odelli, V. M. Stojanović, and A. Ruschhaupt, Phys. Rev. Appl. 20, 054038 (2023).
  * Schaff  _et al._ [2011a] J.-F. Schaff, X.-L. Song, P. Capuzzi, P. Vignolo, and G. Labeyrie, Europhysics Letters 93, 23001 (2011a).
  * Rohringer  _et al._ [2015] W. Rohringer, D. Fischer, F. Steiner, I. E. Mazets, J. Schmiedmayer, and M. Trupke, Scientific Reports 5, 9820 (2015).
  * Deng  _et al._ [2018] S. Deng, P. Diao, Q. Yu, A. del Campo, and H. Wu, Phys. Rev. A 97, 013628 (2018).
  * Diao  _et al._ [2018] P. Diao, S. Deng, F. Li, S. Yu, A. Chenu, A. del Campo, and H. Wu, New Journal of Physics 20, 105004 (2018).
  * Sels and Polkovnikov [2017] D. Sels and A. Polkovnikov, Proceedings of the National Academy of Sciences 114, E3909 (2017).
  * Li  _et al._ [2018] J. Li, T. Fogarty, S. Campbell, X. Chen, and T. Busch, New Journal of Physics 20, 015005 (2018).
  * Fogarty  _et al._ [2019] T. Fogarty, L. Ruks, J. Li, and T. Busch, SciPost Phys. 6, 021 (2019).
  * Kahan  _et al._ [2019] A. Kahan, T. Fogarty, J. Li, and T. Busch, Universe 5 (2019).
  * Huang  _et al._ [2021] T.-Y. Huang, M. Modugno, and X. Chen, Phys. Rev. A 104, 063313 (2021).
  * Girardeau [1960] M. Girardeau, Journal of Mathematical Physics 1, 516 (1960).
  * Kinoshita  _et al._ [2006] T. Kinoshita, T. Wenger, and D. S. Weiss, Nature 440, 900 (2006).
  * Kolomeisky  _et al._ [2000] E. B. Kolomeisky, T. J. Newman, J. P. Straley, and X. Qi, Phys. Rev. Lett. 85, 1146 (2000).
  * Pethick and Smith [2008] C. Pethick and H. Smith,  _Bose–Einstein Condensation in Dilute Gases_ (Cambridge University Press, 2008).
  * Hatomura [2023] T. Hatomura, (2023), arXiv:2311.09720 [quant-ph] .
  * Xu  _et al._ [2020] T.-N. Xu, J. Li, T. Busch, X. Chen, and T. Fogarty, Phys. Rev. Res. 2, 023125 (2020).
  * Fogarty  _et al._ [2020] T. Fogarty, S. Deffner, T. Busch, and S. Campbell, Phys. Rev. Lett. 124, 110601 (2020).
  * Keller  _et al._ [2020] T. Keller, T. Fogarty, J. Li, and T. Busch, Phys. Rev. Res. 2, 033335 (2020).
  * del Campo [2020] A. del Campo, Phys. Rev. Res. 2, 043114 (2020).
  * del Campo [2021] A. del Campo, Phys. Rev. Lett. 126, 180603 (2021).
  * Yang and del Campo [2022] J. Yang and A. del Campo, Phys. Rev. Lett. 129, 150601 (2022).
  * Chen  _et al._ [2011] X. Chen, E. Torrontegui, D. Stefanatos, J.-S. Li, and J. G. Muga, Phys. Rev. A 84, 043415 (2011).
  * Torrontegui  _et al._ [2012] E. Torrontegui, X. Chen, M. Modugno, S. Schmidt, A. Ruschhaupt, and J. G. Muga, New Journal of Physics 14, 013031 (2012).
  * Masuda  _et al._ [2014] S. Masuda, K. Nakamura, and A. del Campo, Phys. Rev. Lett. 113, 063003 (2014).
  * Dupont-Nivet  _et al._ [2018] M. Dupont-Nivet, R. Demur, C. I. Westbrook, and S. Schwartz, New Journal of Physics 20, 043051 (2018).
  * Corgier  _et al._ [2018] R. Corgier, S. Amri, W. Herr, H. Ahlers, J. Rudolph, D. Guéry-Odelin, E. M. Rasel, E. Charron, and N. Gaaloul, New Journal of Physics 20, 055002 (2018).
  * Torrontegui  _et al._ [2011] E. Torrontegui, S. Ibáñez, X. Chen, A. Ruschhaupt, D. Guéry-Odelin, and J. G. Muga, Phys. Rev. A 83, 013415 (2011).
  * Ibáñez  _et al._ [2011] S. Ibáñez, A. Peralta Conde, D. Guéry-Odelin, and J. G. Muga, Phys. Rev. A 84, 013428 (2011).
  * Abah and Lutz [2018] O. Abah and E. Lutz, Phys. Rev. E 98, 032121 (2018).
  * Viedma and Modugno [2020] D. Viedma and M. Modugno, Phys. Rev. Res. 2, 033478 (2020).
  * Castin and Dum [1996] Y. Castin and R. Dum, Phys. Rev. Lett. 77, 5315 (1996).
  * Pérez-García  _et al._ [1997] V. M. Pérez-García, H. Michinel, J. I. Cirac, M. Lewenstein, and P. Zoller, Phys. Rev. A 56, 1424 (1997).
  * Abdullaev  _et al._ [2001] F. K. Abdullaev, A. Gammal, L. Tomio, and T. Frederico, Phys. Rev. A 63, 043604 (2001).
  * Kagan  _et al._ [1996] Y. Kagan, E. L. Surkov, and G. V. Shlyapnikov, Phys. Rev. A 54, R1753 (1996).
  * Deffner  _et al._ [2014] S. Deffner, C. Jarzynski, and A. del Campo, Phys. Rev. X 4, 021013 (2014).
  * del Campo [2011] A. del Campo, Phys. Rev. A 84, 031606 (2011).
  * Pérez-García  _et al._ [1996] V. M. Pérez-García, H. Michinel, J. I. Cirac, M. Lewenstein, and P. Zoller, Phys. Rev. Lett. 77, 5320 (1996).
  * Li  _et al._ [2016] J. Li, K. Sun, and X. Chen, Scientific Reports 6, 38258 (2016).
  * Schaff  _et al._ [2011b] J.-F. Schaff, P. Capuzzi, G. Labeyrie, and P. Vignolo, New Journal of Physics 13, 113017 (2011b).
  * Anderson [1967] P. W. Anderson, Phys. Rev. Lett. 18, 1049 (1967).
  * Bukov  _et al._ [2019] M. Bukov, D. Sels, and A. Polkovnikov, Phys. Rev. X 9, 011034 (2019).


TRANSITIVITY AND RELATED NOTIONS FOR GRAPH INDUCED SYMBOLIC SYSTEMS]TRANSITIVITY AND RELATED NOTIONS FOR GRAPH INDUCED SYMBOLIC SYSTEMS
Prashant Kumar and Puneet Sharma
Department of Mathematics, I.I.T. Jodhpur, NH 65, Nagaur Road, Karwar, Jodhpur-342030, INDIA
<EMAIL_ADDRESS><EMAIL_ADDRESS>
37B10, 37B20, 37B51

In this paper, we investigate the dynamical behavior of a two dimensional shift $X_G$ (generated by a two dimensional graph $G=(\mathcal{H},\mathcal{V})$) using the adjacency matrices of the generating graph $G$. In particular, we investigate properties such as transitivity, directional transitivity, weak mixing, directional weak mixing and mixing for the shift space $X_G$. We prove that if $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ (for all $i,j$), while doubly transitivity (weak mixing) of $X_H$ (or $X_V$) ensures the same for two dimensional shift generated by the graph $G$, directional transitivity (in the direction $(r,s)$) can be characterized through the block representation of $H^rV^s$. We provide necessary and sufficient criteria to establish horizontal (vertical) transitivity for the shift space $X_G$. We also provide examples to establish the necessity of the conditions imposed. Finally, we investigate the decomposability of a given graph into product of graphs with reduced complexity.

§ INTRODUCTION

Symbolic dynamics has widely been used to investigate the dynamics of a various physical and natural processes around us. As any general dynamical system can be embedded in a symbolic system with appropriate number of symbols [27], it is sufficient to study the shift spaces and its subsystems to investigate the dynamics of a general discrete dynamical system. As the study of a general symbolic system can be used to model the dynamics of various systems arising in different fields of sciences and engineering, the area has found applications in various areas of science and engineering such as automata theory, data transmission, data storage and communication systems [2, 3, 5].

In recent years, multidimensional symbolic dynamics has emerged as a topic of interest and has captivated the attention of several researchers across the globe. The convenience of symbol-based representation allows a system with higher complexity to be studied through multidimensional symbolic systems. The easier computability and wide applicability of such systems has enabled the topic to find applications in different fields of sciences and engineering including mathematics, computer science, physics and many more. In particular, area has found applications areas such as computational biology, tiling spaces and study of quasicrystals [7, 22, 24, 26]. In recent times, several researchers have extensively investigated various dynamical and structural aspects of multidimensional shifts and interesting results have been obtained. In [21], the author established the undecidability of the non-emptiness problem for multidimensional shift spaces. In [19], the authors characterized any multidimensional shift of finite type using an infinite matrix. In [20], the authors provide an algorithm for generating the elements of the shift space using a sequence of ﬁnite matrices (of increasing order). The authors establish that the sequence generated yields precisely the elements of the shift space under consideration and hence characterizes the elements of the shift space. In [23], the authors established that any strongly irreducible two dimensional shift space has a dense set of periodic points. In [1], the authors proved that any multidimensional shifts of finite type exhibiting positive topological entropy cannot be minimal. In particular, they established that any shift of finite type with positive topological entropy contains a shift which is not of finite type and hence contains infinitely many shifts of finite type. In [14], the authors investigate mixing $Z^d$ shifts of finite type and sofic shifts with large entropy. They give examples to prove that there exists $Z^d$-mixing systems such that no non-trivial full shift is a factor for such systems. They also establish existence of sofic systems such that the only minimal subsystem is a singleton. In [13], authors prove that the set of entropies for $Z^d$ shifts of finite type ($d\geq 2$) coincides with the set of the infimum of all possible recursive sequences of rational numbers. In [12], the author established that any $h\geq 0$ is the entropy of a $Z^d$ effective dynamical system if and only if it is the lim inf of a recursive sequence of rational numbers. In [18], authors discuss the non-emptiness problem and the existence of periodic points for a multidimensional shift space. They derive conditions under which the shift space is non-empty and posseses periodic points. The authors investigate the structure of the shift space using the generating matrices. They prove that any $d$-dimensional shift of finite type is finite if and only if it is conjugate to a shift generated through permutation matrices. In [10], authors investigated the structure and mixing properties of two-dimensional shift spaces generated by consistent matrices. In [11], the authors discuss the entropy and ergodicity of a two-dimensional shift space using consistent matrices. In [16], authors gave generalized definitions of transitivity for two-dimensional shift spaces and studied various mixing notions for Dot Systems. Before we move further, we provide some of the basic definitions and concepts required.

Let $A = \{a_i : i \in I\}$ be a finite set, $d$ be a positive integer and let $A$ be equipped with the discrete metric. Let $A^{\mathbb{Z}^d}$ be equipped with the product topology. Then, the metric $\mathcal{D} : A^{\mathbb{Z}^d} \times A^{\mathbb{Z}^d} \rightarrow \mathbb{R}^+$  defined as $\mathcal{D} (x,y) = \frac{1}{n+1}$  (where $n$ is the least non-negative integer such that $x \neq y$ in $R_n = [-n,n]^d$) generates the product topology. For any $a\in \mathbb{Z}^d$, the map $\sigma^a : A^{\mathbb{Z}^d} \rightarrow A^{\mathbb{Z}^d}$ defined as $(\sigma^a (x))(k)= x(k+a)$ is a $d$-dimensional shift and is a homeomorphism. Any $X \subset A^{\mathbb{Z}^d}$ is called shift invariant if $\sigma^a(X)\subset X$ for all $a\in\mathbb{Z}^d$. Any non-empty, closed, shift invariant subset of $A^{\mathbb{Z}^d}$ is called a subshift. Let $\mathcal{F}$ be a given set of finite patterns and let $X=\overline{\{x\in A^{\mathbb{Z}^d}: \text{any pattern from~~} \mathcal{F} \text{~~does not appear in~~} x \}}$. Then $X$ defines a subshift of $A^{\mathbb{Z}^d}$ generated by set of forbidden patterns $\mathcal{F}$. We say that the shift space $X$ is a shift of finite type if it can be generated by a finite forbidden set of finite patterns. We say that a pattern is allowed if it is not an extension of any forbidden pattern.  See [2, 4, 5, 8, 9, 15, 19] for details.

A subshift $X$ is called transitive if for any pair of non-empty open sets $U,V$ in $X$, there exists  $n\in\mathbb{Z}^d$ such that $\sigma^n (U)\cap V\neq \emptyset$. A one-dimensional subshift $X$ is called doubly transitive if both the  left and right shifts are transitive for positive time. For any $r\in\mathbb{Z}^d$, a subshift $X$ is called r-transitive if for any non-empty open sets $U,V$ in $X$, there exists  $k\in\mathbb{Z}$ such that $\sigma^{kr} (U)\cap V\neq \emptyset $. It may be noted that a subshift  $X$ is $r$-transitive if the system $(X,\sigma^r)$ is transitive (as a one dimensional system). A shift space $X$ is called totally transitive if $(X,\sigma^r)$ is transitive for all $r\in\mathbb{Z}^d \setminus \{\textbf{0}\}$. A subshift $X$ is called weakly mixing if for any pairs of non-empty open sets $U_1, U_2$ and $V_1,V_2$ in $X$, there exists  $n\in\mathbb{Z}^d$ such that $\sigma^n (U_i)\cap V_i\neq \emptyset~~$ for $i=1,2$. For any $r\in\mathbb{Z}^d$, a subshift $X$ is called  r-weakly mixing if for any pairs of non-empty open sets $U_1, U_2$ and $V_1,V_2$ in $X$, there exists  $k\in\mathbb{Z}$ such that $\sigma^{kr} (U_i)\cap V_i\neq \emptyset~~$ for $i=1,2$. Once again, it may be noted that a subshift  $X$ is $r$-weakly mixing if the system $(X,\sigma^r)$ is weakly mixing (as a one dimensional system). A subshift $X$ is called mixing if for any non-empty open sets $U$ and $V$ in $X$, the set $\{n\in\mathbb{Z}^d: \sigma^n (U)\cap V\neq \emptyset \}$ is cofinite. Refer [2, 9, 16, 25] for details.

Let $G=(V,E)$ be a graph (where $V$ and $E$ are the set of vertices and edges respectively). It may be noted that the set of bi-infinite walks over the graph $G$ is a one dimensional (one step) shift of finite type. Also, as any given shift of finite type $X$ can be coded as a higher block shift (conjugate to $X$ and can be generated by a finite graph $G$), every one dimensional shift of finite type can be visualized as a shift generated from some graph. Also, if $\{G_1,G_2,\ldots,G_d\}$ is a set of graphs with a common set of vertices $V$, the collection naturally induces a $d$-dimensional shift of finite type (where $i$-th graph determines the compatibility of the vertices in the $i$-th direction). In such a case, we refer $(G_1,G_2,\ldots,G_d)$ as a $d$-dimensional graph. We say that a two dimensional graph $G=(H, V)$ is connected if for every pair of vertices $i , j \in \mathcal{V}(G)$, $\exists \ (r, s) \in (\mathbb{Z}^{+} \times \mathbb{Z}^{+}) \setminus\{0,0\}$ such that $(H^r V^s)_{ij} >0$. It may be noted that if $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ for all $i,j$, then any $1\times r$ strip can extended to a $2\times r$ (and hence to $n\times m$ block for any $n,m\in\mathbb{N}$) block allowed for the shift space. Consequently, the condition ensures extension of a given $r\times s$ block to a valid configuration for the shift space under discussion. See [2, 5, 10, 11, 18] for details.

An $n\times n$ real, non-negative, square matrix $A$ is called irreducible if for any pair of indices $i,j\in \{1,2,\ldots,n\}$, there exists $k\in\mathbb{N}$ such that $A^k_{ij}\neq 0$. Such a matrix $A$ is called primitive if there exists $k\in\mathbb{N}$ such that $A^k_{ij}\neq 0~~ \forall i,j\in\{1,2,\ldots,n\}$. It can be seen that a one dimensional shift generated by the matrix $A$ is doubly transitive (strongly mixing) if and only if $A$ is irreducible (primitive). Further, it is known that any one dimensional shift of finite type $X$ is totally transitive $\Leftrightarrow X$ is weakly mixing  $\Leftrightarrow X$ is strongly mixing. Refer [2, 25] for details.

Let $G_1$ and $G_2$ be two directed graphs. Then, the Cartesian (Tensor) product of $G_1$ and $G_2$ is defined as the graph with  $\mathcal{V}(G_1) \times \mathcal{V}(G_2)$ as the set of vertices. The vertices $(a,b)$ and $(c,d)$ are connected in Cartesian Graph Product (denoted by $G_1  \scalebox{0.7}{$\square$} G_2$), if $ a= c \ (ac \in \mathcal{E}(G_1))$ and $ bd \in \mathcal{E}(G_2) \ (b=d)$. In other words, two tuples are connected in Cartesian graph product if one of the indices (of the tuple) coincide and the other is connected (in their respective graphs). The vertices $(a,b)$ and $(c,d)$ are connected in Tensor Graph Product (denoted by $G_1 \times G_2$) if $ ac \in \mathcal{E}(G_1)$ and $bd \in \mathcal{E}(G_2)$. We define the graph product (Cartesian and Tensor) of two-dimensional graphs $G_1$ and $G_2$ to be component-wise graph product. See [6, 17] for details.

In this paper, we investigate the dynamical behavior of a two dimensional shift generated by the graph $G=(\mathcal{H},\mathcal{V})$). For the sake of simplicity, we use $H$ and $V$ for the adjacency matrices of $\mathcal{H}$ and $\mathcal{V}$ respectively. In particular, we investigate transitivity, $r$-transitivity, total transitivity, weakly mixing, $r$-weakly mixing and mixing for shift space under consideration. We prove that if $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0, ~~\forall i,j$, while doubly transitivity (weak mixing) of $X_H$ (or $X_V$) ensures the same for two dimensional shift generated by the graph $G$, irreducibility of $H^rV^s$ provides a necessary and sufficient criteria to establish directional doubly transitivity (in $(r,s)$ direction ($rs>0$)) for the multidimensional shift space under discussion. We provide examples to show that the results derived do not hold if any of the conditions imposed fails to hold. We also provide necessary and sufficient criteria to establish horizontal (vertical) transitivity for the shift space $X_G$. We also investigate the decomposability of a given graph into product of graphs with reduced complexity.

§ MAIN RESULTS

Let $X_{G}$ be a shift space generated by the two dimensional graph  $G=(\mathcal{H},\mathcal{V})$. If $H$ and $V$ are irreducible permutation matrices such that $HV=VH$, then $X_{G}$ comprises of a single periodic point (with finite orbit).

Let $X_{G}$ be shift space generated by the two dimensional graph $G=(\mathcal{H},\mathcal{V})$. Firstly, note that if $H$ and $V$ are permutation matrices, then the horizontal (vertical) neighbor of any symbol is uniquely determined. Further, if $HV=VH$, fixing a symbol at $(0,0)$ determines the symbols at all other positions in the plane and hence yields a unique configuration in the shift space $X_G$. Finally, as $H$ and $V$ are irreducible, any two symbols are connected by a horizontal (vertical) path. Consequently, the shift space comprises of a single periodic orbit (with finite orbit) and the proof is complete.

The above proof provides a sufficient condition for the shift space to be finite (in fact a single periodic orbit) when the generating matrices commute with each other.  It may be noted that as the above arguments hold even when only one of the generating matrix is irreducible, the above result holds under a weaker condition (irreducibility of one of the generating matrices). In [10], the authors establish transitivity of the shift space under irreducibility of one of the generating matrices when the generating matrices are “consistent". However, as irreducibility of $H$ (or $V$) ensures connectivity of any two vertices through a horizontal (vertical) path, $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ for all $i,j$ ensures that any two allowed rectangular blocks can be connected (horizontally or vertically) and hence can be extended to a configuration in the shift space $X_G$. Consequently, the shift space $X_G$ is transitive for a bigger class of subshifts (of the full shift) and we get the following result.

Let $X_{G}$ be a shift space generated by the two dimensional graph $G=(\mathcal{H},\mathcal{V})$ such that $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds for all $i,j$. If $H$ (or $V$) is irreducible then $X_G$ is transitive.

Let $H$ be an irreducible matrix and let $x,y\in X_G$. For any central blocks $x_n= {\begin{array}{cccccccc}

x_{-n,n}  & \hdots &  x_{n,n}  \\
\vdots  & \vdots & \vdots     \\
x_{-n,-n}  & \hdots & x_{n,-n}      \\

\end{array} } $ and $y_n= {\begin{array}{cccccccc}

y_{-n,n}  & \hdots &  y_{n,n}  \\
\vdots & \vdots & \vdots     \\
y_{-n,-n}  & \hdots & y_{n,-n}      \\

\end{array} } $ of $x$ and $y$ respectively, irreducibility of $H$ ensures that $x_{n,n}$ and $y_{-n,-n}$ can be connected through a horizontal path. Consequently, there exists symbols $a_1,a_2,\ldots, a_k$ such that
&&&&  y_{-n,n} & \hdots  &  y_{n,n}  \\
&&&&  \vdots & \vdots  & \vdots     \\
x_{-n,n} & \hdots  &  x_{n,n} & a_{1}\hdots \ a_{k} & y_{-n,-n}  & \hdots & y_{n,-n} \\
\vdots & \vdots  & \vdots  &&&& \\
x_{-n,-n} & \hdots  & x_{n,-n}  &&&&   \\

\end{array} }$$

is an allowed pattern for the shift space $X_G$. Further, as $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds for all $i,j$, such an allowed pattern can be extended to a $(4n+k+2)\times (4n+k+2)$ square and hence to a configuration in $X_G$. As the argument holds for any central blocks of any size $n$,  for any neighborhoods $U$ and $V$ of $x$ and $y$ respectively, there exists $r,s\in \mathbb{N}$ such that $\sigma^{(r,s)}(U)\cap V\neq \emptyset$. As the arguments hold for any $x,y\in X_G$, $X_G$ is transitive and the proof is complete.

The above results establish non-emptiness and transitivity under suitable conditions for a two dimensional shift space. While Proposition $1$ establishes the shift space to comprise of a single periodic orbit when generating matrices are irreducible permutation matrices commuting with each other, Proposition $2$ provides sufficient conditions to establish transitivity for the two dimensional shift space respectively. However, the conditions derived are sufficient in nature and the conclusions derived may hold even in the absence of the conditions imposed. We now provide examples in support of our arguments.

Let $X_{G}$ be a shift space generated by the adjacency matrices given below:

$$\textit{H}= \bordermatrix{ & 1 & 2 & 3 & 4  \cr
1 & 1 & 1 & 0 & 0   \cr
2 & 1 & 0 & 0 & 0   \cr
3 & 0 & 0 & 0 & 1   \cr
4 & 0 & 0 & 1 & 0   \cr
\ \ \ \ \ \ \ \ \
\textit{V}= \bordermatrix{ & 1 & 2 & 3 & 4  \cr
1 & 0 & 0 & 1 & 0   \cr
2 & 0 & 0 & 0 & 1   \cr
3 & 1 & 1 & 0 & 1   \cr
4 & 0 & 1 & 0 & 0   \cr

It may be noted that $H$ and $V$ are neither irreducible nor permutation matrices. Further, as $HV\neq VH$, none of the conditions (imposed in Proposition $1$) holds. However, as the shift space comprises of a single periodic orbit of the point

$$ {\begin{array}{ccccccccccccccccccccccc}

\ldots & \vdots & \vdots & \vdots & \vdots & \vdots  & \vdots & \vdots & \vdots   & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots  & \vdots & \vdots & \vdots   & \ldots   \\

\ldots & 1 & 2 & 1 & 2 & 1  & 2 & 1 & 2  & 1 & 2 & 1 & 2 & 1  & 2 & 1 & 2  & \ldots   \\

\ldots & 3 & 4 & 3 & 4 & 3 & 4 & 3 & 	4 & 3 & 4 & 3 & 4 & 3 &	4 & 3 & 4 & \ldots    \\

\ldots & 1 & 2 & 1 & 2 & 1  & 2 & 1 & 2  & 1 & 2 & 1 & 2 & 1  & 2 & 1 & 2  & \ldots   \\

\ldots & 3 & 4 & 3 & 4 & 3 & 4 & 3 & 	4 & 3 & 4 & 3 & 4 & 3 &	4 & 3 & 4 & \ldots    \\
\ldots & 1 & 2 & 1 & 2 & 1  & 2 & 1 & 2  & 1 & 2 & 1 & 2 & 1  & 2 & 1 & 2  & \ldots   \\
\ldots & \vdots & \vdots & \vdots & \vdots & \vdots  & \vdots & \vdots & \vdots   &\vdots & \vdots & \vdots & \vdots & \vdots & \vdots  & \vdots & \vdots & \vdots   &  \ldots   \\

\end{array} } $$

$X_G$ comprises of a single periodic point (even when none of the conditions imposed in Proposition $1$ hold).

Let $X_{G}$ be the shift space corresponding to graph $G=(\mathcal{H},\mathcal{V})$, where the adjacency matrices for the generating graph are given by

$$\textit{H}= \bordermatrix{ & 0 & 1 & 2 & e & f & g \cr
0 & 0 & 1 & 0 & 0 & 0 & 0  \cr
1 & 0 & 0 & 1 & 0 & 0 & 0  \cr
2 & 1 & 0 & 0 & 1 & 0 & 0  \cr
e & 0 & 0 & 1 & 0 & 1 & 0  \cr
f & 0 & 0 & 0 & 0 & 0 & 1  \cr
g & 0 & 0 & 0 & 1 & 0 & 0  \cr
\ \ \ \ \ \ \ \ \
\textit{V}= \bordermatrix{ & 0 & 1 & 2 & e & f & g \cr
0 & 0 & 1 & 0 & 0 & 0 & 0  \cr
1 & 0 & 0 & 1 & 0 & 0 & 0  \cr
2 & 1 & 0 & 0 & 0 & 1 & 0  \cr
e & 0 & 0 & 0 & 0 & 1 & 0  \cr
f & 0 & 0 & 1 & 0 & 0 & 1  \cr
g & 0 & 0 & 0 & 1 & 0 & 0  \cr

It may be noted that $H$ and $V$ are irreducible but $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ for all $i,j$ does not hold. Further, as the pattern $2e$ cannot be extended vertically to form a valid pattern for the shift space, any valid configuration for $X_G$ comprises either of $0,1,2$ or $e,f,g$ and hence the two dimensional shift space $X_G$ is not transitive.  Thus, the shift space may fail to be transitive even when each of the generating matrices are irreducible (It is worth mentioning that if $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds for all $i,j$, irreducibility of any of the generating matrices is sufficient to ensure transitivity of the two dimensional shift $X_G$).

Let $X_{G}$ be a shift space generated by the two dimensional graph $G=(\mathcal{H},\mathcal{V})$ such that $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds for all $i,j$. If $X_H$ (or $X_V$) is weak mixing then $X_G$ exhibits weak mixing.

As proof of Proposition <ref> establishes that if $H$ (or $V$) is irreducible then $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ for all $i,j$ ensures transitivity of the shift space $X_G$. As a similar set of arguments can be repeated for any pair of open sets in the shift space, if $X_H$ is weakly mixing then $X_G$ is weak mixing (under the imposed condition).

The above result proves that if the imposed conditions hold, then the two dimensional shift is weak mixing when the one dimensional shift generated by any of the generating matrices is weak mixing. However, the result holds strictly under the imposed conditions and may not be true otherwise even when the one dimensional shifts generated by each of the generating matrices are weak mixing. We now give an example in support of our claim.

Let $X_G$ be the two dimensional shift space generated by graph $G=(\mathcal{H},\mathcal{V})$, where corresponding adjacency matrices are

$$\textit{H}= \bordermatrix{ & 0 & 1 & 2 \cr
0 & 1 & 1 & 0 \cr
1 & 0 & 0 & 1 \cr
2 & 1 & 0 & 0 \cr
\ \ \ \ \ \ \ \ \
\textit{V}= \bordermatrix{ & 0 & 1 & 2 \cr
0 & 0 & 1 & 1 \cr
1 & 1 & 0 & 0 \cr
2 & 1 & 0 & 1 \cr

Firstly, it may be noted that $H$ and $V$ are primitive matrices (hence generate one dimensional weak mixing shifts) and the condition $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ for all $i,j$ fails to hold. However, the two dimensional shift generated by $G$ comprises of a single periodic orbit generated by the point

$$ {\begin{array}{ccccccccccccccccccccccc}

\ldots & \vdots & \vdots & \vdots & \vdots & \vdots  & \vdots & \vdots & \vdots   & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots  & \vdots & \vdots & \vdots   & \ldots   \\

\ldots & 1 & 2 & 0 & 0 & 1  & 2 & 0 & 0  & 1 & 2 & 0 & 0 & 1  & 2 & 0 & 0  & \ldots   \\

\ldots &	0 & 0 & 1 & 2 & 0 & 0 &	1 & 2 &	0 & 0 & 1 & 2 & 0 & 0 &	1 & 2 & \ldots    \\

%\ldots & 1 & 2 & 0 & 0 & 1  & 2 & 0 & 0  & 1 & 2 & 0 & 0 & 1  & 2 & 0 & 0  & \ldots   \\
%			\ldots &	0 & 0 & 1 & 2 & 0 & 0 &	1 & 2 & 	0 & 0 & 1 & 2 & 0 & 0 &	1 & 2 & \ldots    \\

\ldots & 1 & 2 & 0 & 0 & 1  & 2 & 0 & 0  & 1 & 2 & 0 & 0 & 1  & 2 & 0 & 0  & \ldots   \\
\ldots & \vdots & \vdots & \vdots & \vdots & \vdots  & \vdots & \vdots & \vdots   &\vdots & \vdots & \vdots & \vdots & \vdots & \vdots  & \vdots & \vdots & \vdots   &  \ldots   \\
\end{array} } $$

Consequently, the shift space $X_G$ does not exhibit weak mixing. Thus, the shift space $X_G$ generated by a graph $G$ need not exhibit weak mixing even when the shift spaces generated by each of the generating matrices are weak mixing.

Let $G=(H,V)$ be a two dimensional connected graph satisfying $(HV)_{ij} \neq 0 \Leftrightarrow (VH)_{ij} \neq 0$ for all $i, j$, then $X_G$ is transitive.

Let $U, V$ be $\frac{1}{n}$-neighborhoods of configurations $x, y \in X_G$. If $x_n$ and $y_n$ are central blocks of length $(2n+1)$ of the elements $x$ and $y$ respectively, as $G$ is connected, there exists a path from $x_{n,n}$ (top right corner of $x_n$) to $y_{-n,-n}$ (bottom left corner of $y_n$). As $(HV)_{ij} \neq 0 \Leftrightarrow (VH)_{ij} \neq 0$ (for all $i, j$), the extended pattern can further be extended to an allowed rectangular pattern in $\mathcal{B}(X_G)$ (and finally to a valid configuration $z \in X_G$). Thus, there exists $(r,s)\in (\mathbb{Z}^{+} \times \mathbb{Z}^{+})\setminus\{0,0\}$ such that $\sigma^{(r,s)}(U) \cap V \neq \emptyset$. Hence $X_G$ is transitive and the proof is complete.

Let $X_{G}$ be a shift space and let $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds for all $i,j$. Then, $X_{G}$ is doubly $(r,s)$-transitive ($rs>0)$ if and only if $H^{r}V^{s}$ is irreducible.

Without loss of generality, assume that $r,s>0$ (as $rs>0)$. Let  $X_{G}$ be doubly $(r,s)$-transitive ($rs>0)$, $x,y\in X_G$ and $U, V$ be $\frac{1}{n}$-neighborhoods of $x$ and $y$ respectively. Let $x_n, y_n$ be central blocks (of size $2n+1$) of the elements $x$ and $y$ respectively. As $X_G$ is transitive in the direction $(r,s)$, there exists $u\in U$, $v\in V$ and $k\in\mathbb{N}$ such that $\sigma^{(kr,ks)}(u)=v$. As $U, V$ are $\frac{1}{n}$-neighborhoods of $x, y$ respectively, $x_n, y_n$ are central blocks of $u, v$ respectively and hence $(H^{r}V^{s})^{k}_{x_{n,n}y_{-n,-n}}\neq 0$. As the proof holds with central blocks of arbitrary sizes (and hence with arbitrary corner points), $H^{r}V^{s}$ is irreducible and the proof of forward part is complete.

Conversely, let $H^{r}V^{s}$ be irreducible ($r, s>0$), $x,y\in X_G$, $U$ and $V$ be $\frac{1}{n}$-neighborhoods of $x$ and $y$ respectively and $x_n, y_n$ be central blocks (of size $2n+1$) of the elements $x, y$ respectively. For any central blocks $x_n$ and $y_n$ (of size $2n+1$) of $x$ and $y$ respectively, irreducibility of $H^{r}V^{s}$ ensures existence of $k\in\mathbb{N}$ such that $(H^{r}V^{s})^{k}_{x_{n,n}y_{-n,-n}}\neq 0$. Consequently, there exists a pattern of the form
&& &&&&& y_{-n,n} & \hdots  &  y_{n,n}  \\
&& &&&&& \vdots & \vdots  & \vdots     \\
&& &&&&& y_{-n,-n}  & \hdots & y_{n,-n} \\

&&&&&&& \vdots & \\
&&&&&& \hdots  \\
&&&&& \reflectbox{$\ddots$}  \\
&&&& \vdots &&& \\
x_{-n,n} & \hdots  &  x_{n,n} &  \hdots  &&&& \\
\vdots & \vdots  & \vdots  &&&&& \\
x_{-n,n} & \hdots  & x_{n,-n}  &&&&&   \\
\end{array} }$$

(where each $(\hdots)$ is a horizontal path of length $r$ and each $(\vdots)$ is a vertical path of length $s$) which is an allowed pattern for the shift space $X_G$. Further, as $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds for all $i,j$, such an allowed pattern can be extended to a configuration (say $z$) in $X_G$. Finally, note that $z\in U$ (as central block of $z$ is $x_n$) and $\sigma^{(kr,ks)}(z)\in V$ (as central block of $\sigma^{(kr,ks)}(z)$ is $y_n$), $X_G$ is doubly $(r,s)$-transitive and the converse also holds.

Finally, if $r,s<0$ (as $rs>0$) then arguments similar to above prove that $X_G$ is $(r,s)$-transitive  if and only if $(H^T)^{r}(V^T)^{s}$ is irreducible. Since $A$ is irreducible if and only if $A^T$ is irreducible,  $X_{G}$ is doubly $(r,s)$-transitive ($rs>0)$ if and only if $H^{r}V^{s}$ is irreducible and the proof is complete.

The above result establishes the $(r,s)$-doubly transitivity of the two dimensional shift space under the irreducibility of the matrix $H^rV^s$. However, as the interactions among symbols may happen in negative time, irreducibility of $H^rV^s$ cannot be guaranteed under $(r,s)$-transitivity of the shift space under discussion. It may be noted that a similar set of arguments establish weak mixing in the $(r,s)$-direction when $H^rV^s$ is primitive (under the condition $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ for all $i,j$). We now establish our claims below.

Let $X_G$ be a shift space arising from the following adjacency matrices:

$$\textit{H}= \bordermatrix{ & 1 & 2 & 3 & 4  \cr
1 & 0 & 1 & 0 & 0 \cr
2 & 1 & 0 & 1  & 0 \cr
3 & 0 & 0 & 0  & 1 \cr
4 & 0 & 0 & 1  & 0 \cr
\ \ \ \ \ \
\textit{V}= \bordermatrix{ & 1 & 2 & 3  & 4 \cr
1 & 1 & 0 & 0 & 0   \cr
2 & 0 & 1 & 0 & 0   \cr
3 & 0 & 0 & 1 & 0   \cr
4 & 0 & 0 & 0 & 1   \cr

Then, it can be seen that $X_{G}$ is (1,1)-transitive (is transitive along the line $y=x$). However, as

$$\textit{HV=VH}=  \bordermatrix{ & 1 & 2 & 3 & 4  \cr
1 & 0 & 1 & 0 & 0 \cr
2 & 1 & 0 & 1  & 0 \cr
3 & 0 & 0 & 0  & 1 \cr
4 & 0 & 0 & 1  & 0 \cr

The matrix $HV$ fails to be irreducible and hence $(r,s)$-transitivity of the shift space $X_G$ need not imply irreducibility of the matrix $H^{r}V^{s}$.

Let $X_{G}$ be a shift space where condition $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds for all $i,j$. Then, $H^{r}{V}^{s}$ is primitive $\Leftrightarrow$ $X_{G}$ is weak mixing in direction $(r,s)$ ($ rs >0)$.

The proof follows from the discussions in the Remark <ref>.

Let $X_G$ be a one dimensional shift space generated by a one dimensional graph $G$ (with adjacency matrix $A$). Then $X_G$ is transitive $\Leftrightarrow$ $A$ is irreducible or $A$ has exactly two irreducible, permutation sub-matrices $A_{1}, A_{2}$ such that for any $i \in A_{1}$, $j \in A_{2}$, there exists a unique path connecting the two vertices (which traverses through all the vertices of $A \setminus (A_1 \cup A_2)$).

Let $X_G$ be a one dimensional transitive shift space generated by a one dimensional graph $G$ (with adjacency matrix $A$). Note that if $A$ is not irreducible then there exists $i,j\in\{1,2,\ldots,n\}$ such that $A^k_{ij}=0~~ \forall k\in\mathbb{N}$. However,  as $X_G$ is transitive, there exists a block of the form $ja_1a_2\ldots a_r i$ allowed for the shift space. Further, as existence of two blocks of the form $ja_1a_2\ldots a_r i$ ensures $A^k_{ij}\neq 0$ for some $k\in\mathbb{N}$ (as $X_G$ is transitive), there exists a unique block of the form $ja_1a_2\ldots a_r i$. Thus, fixing position of $j$ fixes every position before $j$ in a unique manner. Also, as existence of two blocks of the form $ja_1a_2\ldots a_r i b_1b_2\ldots b_m$ ensures $A^k_{ij}\neq 0$ for some $k\in\mathbb{N}$ (again by transitivity of $X_G$), fixing position of $j$ fixes the entire sequence and the proof of forward part is complete.

Conversely, if hypothesis for the converse holds then any non-periodic point in the shift space is of the form $\overline{x_1x_2\ldots x_k} j c_1 c_2\ldots c_l i \overline{y_1y_2\ldots y_m}$  Also, as $\overline{x_1x_2\ldots x_k}$ and $\overline{y_1y_2\ldots y_m}$ are the only other elements in the shift space, any two blocks allowed for the shift space interact over time and the shift space is transitive.

The above result characterizes the transitivity for a one dimensional shift space generated by a graph $G$. However, as directional shifts for a multidimensional shift spaces can be visualized as a one dimensional shift, a similar result can be derived to characterize the transitivity (in a particular direction) for a multidimensional shift space. In particular, for a two dimensional shift space generated by $G=(\mathcal{H},\mathcal{V})$, if $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds (for all $i,j$) then a similar argument establishes $(r,s)$-transitivity for the shift space if $H^rV^s$ can be represented using the similar block form (as derived in Proposition <ref>). Thus we get the following corollary.

Let $X_{G}$ be a two dimensional shift space generated by the graph $G=(\mathcal{H},\mathcal{V})$ such that $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds for all $i,j$. Then $X_{G}$ is $(r,s)$-transitive $\Leftrightarrow$ $H^rV^s$ is irreducible or $H^rV^s$ has exactly two irreducible, permutation sub-matrices $A_{1}, A_{2}$ such that for any $i \in A_{1}$, $j \in A_{2}$, there exists a unique path connecting the two vertices (which traverses through all the vertices of $H^rV^s \setminus (A_1 \cup A_2)$).

The proof follows from discussions in Remark <ref>.

Let $X_{G}$ be a two dimensional shift space and let $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds for all $i,j$. If $H$ or $V$ are irreducible matrices, then $X_{G}$ is doubly $(r,s)$-transitive (for some direction  $(r,s)\in\mathbb{N}\times\mathbb{N} $).

Let $X_G$ be the shift generated by the two dimensional graph $G$ such that $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds for all $i,j$ and let $H$ be an irreducible matrix. As $V$ generates a non-empty one dimensional shift, there exists a vertex $i\in\{1,2,\ldots,n\}$ and $m\in\mathbb{N}$ such that $V^m_{ii}\neq 0$. Also, as $H$ is irreducible, there exists a finite path $W=a_0a_1\ldots a_r$ such that $a_0=a_r=i$ and each symbol $j$ appears atleast once in the path $W$. Consequently, for the pattern $P$ of the form

&&&&& i & a_{1} & a_{2} & \ldots & a_{r-1} &  i\\
&  &  &      & & \vdots &&&&& \\

i & a_{1} & a_{2} & \ldots & a_{r-1} &  i &&
\end{array} } $$

is allowed for the shift space $X_G$. Further, note that diagonal repetition ($R$ times, where $R$ is more than the number of symbols) is allowed for the shift space and can be extended to a configuration in $X_G$. Also, as $\sigma^{(s(r+1),sm)}(i)=a_s$, $H^{r+1}V^m$ is irreducible. Consequently, $X_G$ is doubly $(r+1,m)$-transitive and the proof is complete.

The above proof establishes that if $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds for all $i,j$, then irreducibility of any of the generating matrices ensures directional transitivity (in some direction $(r,s)$) and thus transitivity cannot happen in the shift space independently (without directional transitivity). However, in general, the transitivity of the shift space $X_G$ need not imply directional transitivity and the notions are indeed distinct. Also, as weakly mixing ensures interaction between any two pairs of symbols, if any of the shift spaces generated by $H$ or $V$ is weakly mixing, $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ for all $i,j$ ensures weak mixing in some direction $(r,s)$ for the two dimensional shift space. It may be noted that as a shift is $(r,s)$-weak mixing if and only if $H^rV^s$ is primitive (for $rs>0$), $(r,s)$-weak mixing of a system is equivalent to $(1,1)$-weak mixing.  It is worth mentioning that directional mixing of a system indeed depends on the direction and existence of mixing notions in one direction for a shift space $X_G$ need not guarantee existence of mixing notion in the other. Consequently, total transitivity and weak mixing are indeed distinct notions for higher dimensional shifts of finite type (recall that the two notions coincide for shifts of finite type in one dimensional case).  We now establish our claims below.

Let $X_{G}$ be a shift space such that $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ for all $i,j$. If $H$ or $V$ is primitive, then $X_{G}$ is $(r,s)$-weak mixing (for some direction  $(r,s)\in\mathbb{N}\times\mathbb{N}$). Further, $X_{G_{}} $ is $(r,s)$-weak mixing (for $rs > 0$) if and only if $X_{G} $ is $(1,1)$-weak mixing.

The proof follows from the discussions in Remark <ref>.

Let $X_G$ be a shift space arising from following adjacency matrices.

$$\textit{H = V}= \bordermatrix{ & 0 & 1 & 2 & 3  \cr
0 & 0 & 1 & 0 & 0   \cr
1 & 0 & 1 & 1 & 0   \cr
2 & 1 & 0 & 0 & 1   \cr
3 & 1 & 0 & 0 & 1   \cr

It may be noted that as $H$ is primitive ($H^4_{ij}>0 \  \forall \  i,j$), $X_G$ is $(1,1)$-weak mixing. However, $HV^T=V^TH$ fails to hold. Further, as

$$\textit{$HV^{T}$}= \bordermatrix{ & 0 & 1 & 2 & 3  \cr
0 & 1 & 1 & 0 & 0   \cr
1 & 1 & 2 & 0 & 0   \cr
2 & 0 & 0 & 2 & 2   \cr
3 & 0 & 0 & 2 & 2   \cr
\ \ \ \ \ \
\textit{$V^{T}H$}= \bordermatrix{ & 0 & 1 & 2 & 3  \cr
0 & 2 & 0 & 0 & 2   \cr
1 & 0 & 2 & 1 & 0   \cr
2 & 0 & 1 & 1 & 0   \cr
3 & 2 & 0 & 0 & 2   \cr

fixing any symbol at $(0,0)$ enforces the same symbol along the line $y=-x$ and hence $X_G$ does not exhibit (1,-1)-weak mixing. Consequently, any of the mixing notions in one direction need not ensure the mixing notions in the other. Also, as the example exhibits weak mixing in $(1,1)$-direction, the case provides an example of weak mixing shift which fails to be totally transitive. Consequently, the two notions are distinct for higher dimensional shifts of finite type and an analogous extension of the result valid for one dimensional case does not hold.

Let $P_k$ and $Q_k$ denote the collection of valid $1\times k$ and $k\times 1$ patterns respectively and let $V_k (H_k)$ denote the matrix characterizing vertical (horizontal) compatibility of elements of $P_k$ ($Q_k$). It may be noted that $H_1=H$ and $V_1=V$. In general, $H_k$ and $V_k$ generate valid patterns of size $k\times r$ and $r\times k$ respectively (for any $r\in \mathbb{N}$). Such matrices have been defined in [11] and have been used to investigate the dynamical properties of “shifts of finite type"(as defined in [10, 11]). We now investigate notions of horizontal (vertical) mixing for the shift space $X_G$ in terms of the matrices $H_k$ and $V_k$.

Let $X_G$ be a two dimensional shift space generated by a graph $G$ and let $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds for all $i,j$. Then, $X_G$ is horizontally doubly transitive $\Leftrightarrow~~$ $H_k$ is irreducible $\forall k\in \mathbb{N}$.

Let $X_G$ be a two dimensional horizontally doubly transitive shift space. Let $x,y\in X_G$, $x_k= {\begin{array}{cccccccc}

x_{-k,k}  & \hdots &  x_{k,k}  \\
\vdots  & \vdots & \vdots     \\
x_{-k,-k}  & \hdots & x_{k,-k}      \\

\end{array} } $ and $y_k= {\begin{array}{cccccccc}

y_{-k,k}  & \hdots &  y_{k,k}  \\
\vdots & \vdots & \vdots     \\
y_{-k,-k}  & \hdots & y_{k,-k}      \\

\end{array}}~$, be central blocks and let $U, V$ be $\frac{1}{k}$-neighborhoods of $x, y$ respectively. As $X_G$ is horizontally doubly transitive, there exists $z\in U$, $w\in V$ and $r\in \mathbb{N}$ such that $\sigma^{(r,0)}(z)=w$. It may be noted that as $z\in U$ and $w\in V$, the central blocks of $z$ and $w$ are $x_k$ and $y_k$ respectively. Further, as $\sigma^{(r,0)}(z)=w$,  $a={\begin{array}{cccccccc} x_{k,k}\\ \vdots \\ x_{k,-k}\\ \end{array}}$ and $b={\begin{array}{cccccccc} y_{-k,k}\\ \vdots \\ y_{-k,-k}\\ \end{array}}$ can be connected horizontally (through a finite path). As the arguments hold for any $a,b\in H_k$, $H_k$ is irreducible. Further, as the argument holds for any $k\in \mathbb{N}$, $H_k$ is irreducible for all $k\in\mathbb{N}$ and the proof of forward part is complete.

Conversely, let $H_k$ be irreducible for all $k\in\mathbb{N}$. Let $x,y\in X_{G}$ and let $U$ and $V$ be $\frac{1}{k}$-neighborhoods of $x$ and $y$ respectively. For any central blocks $x_k= {\begin{array}{cccccccc}

x_{-k,k}  & \hdots &  x_{k,k}  \\
\vdots  & \vdots & \vdots     \\
x_{-k,-k}  & \hdots & x_{k,-k}      \\

\end{array} } $ and $y_k= {\begin{array}{cccccccc}

y_{-k,k}  & \hdots &  y_{k,k}  \\
\vdots & \vdots & \vdots     \\
y_{-k,-k}  & \hdots & y_{k,-k}      \\
\end{array}}~$ of $x$ and $y$ respectively, irreducibility of $H_k$ ensures that $a={\begin{array}{cccccccc} x_{k,k}\\ \vdots \\ x_{k,-k}\\ \end{array}}$ and $b={\begin{array}{cccccccc} y_{-k,k}\\ \vdots \\ y_{-k,-k}\\ \end{array}}$ can be connected horizontally through a finite path (say of length $l$) and hence there exists a valid pattern of the form

x_{-k,k}  & \hdots &  x_{k,k} & \hdots & y_{-k,k}  & \hdots &  y_{k,k} \\
\vdots  & \vdots & \vdots  & \vdots & \vdots & \vdots & \vdots    \\
x_{-k,-k}  & \hdots & x_{k,-k}  & \hdots &  y_{-k,-k}  & \hdots & y_{k,-k}   \\
\end{array} } $$

As $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds for all $i,j$, the above pattern can be extended to a valid configuration in $X_G$ (say $z$). Then, $z\in U$, $\sigma^{(2k+1+l,0)}(z)\in V$. As the proof holds for any $x,y\in X_G$, the shift space is horizontally doubly transitive and the proof is complete.

The above result establishes that for any shift space $X_G$, $X_G$ is horizontally doubly transitive if and only if each $H_k$ is irreducible. However, transitivity of $X_G$ need not ensure irreducibility for all $H_k$. Once again, as horizontal transitivity can be visualized as a one dimensional shift, horizontal transitivity of the shift space can be characterized via the block representations of the matrices $H_k$. Finally, as similar arguments establish the equivalence of vertical transitivity with irreducibility of $V_k$ (for all $k$), we get the following corollary.

Let $X_{G}$ be two dimensional shift space generated by the graph $G=(\mathcal{H},\mathcal{V})$ such that $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ for all $i,j$. Then, $X_G$ is horizontally transitive $\Leftrightarrow$ either all $H_k$ are irreducible or all $H_{k}$ have exactly two irreducible, permutation sub-matrices $A_{1k}, A_{2k}$ such that for any $i \in A_{1k}$, $j \in A_{2k}$, there exists a unique path connecting the two vertices (which traverses through all the vertices of $H_k \setminus (A_{1k} \cup A_{2k})$).

The proof follows from discussions in Remark <ref>.

Let $X_G$ be a two dimensional shift generated by the graph $G$ and let $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds for all $i,j$. If $X_H$ is weakly mixing then $X_G$ is vertically doubly transitive $\Leftrightarrow$ $X_G$ is vertically weakly mixing.

Let $X_G$ be vertically doubly transitive shift space and let $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ holds for all $i,j$. Let $x,y,z,w\in X_G$ and
$x_k= {\begin{array}{cccccccc}

x_{-k,k}  & \hdots &  x_{k,k}  \\
\vdots  & \vdots & \vdots     \\
x_{-k,-k}  & \hdots & x_{k,-k}      \\

\end{array} } $, $y_k= {\begin{array}{cccccccc}

y_{-k,k}  & \hdots &  y_{k,k}  \\
\vdots & \vdots & \vdots     \\
y_{-k,-k}  & \hdots & y_{k,-k}      \\
\end{array}}~$, $z_k= {\begin{array}{cccccccc}

z_{-k,k}  & \hdots &  z_{k,k}  \\
\vdots  & \vdots & \vdots     \\
z_{-k,-k}  & \hdots & z_{k,-k}      \\

\end{array} } $ and $w_k= {\begin{array}{cccccccc}

w_{-k,k}  & \hdots &  w_{k,k}  \\
\vdots & \vdots & \vdots     \\
w_{-k,-k}  & \hdots & w_{k,-k}      \\

\end{array} } $ be central blocks of size $k$ (squares of size $2k+1$) of $x,y,z$ and $w$ respectively. Let $U,V,Z,W$ be $\frac{1}{k}$-neighborhoods of $x,y,z$ and $w$ respectively. As $X_H$ is weakly mixing, the symbols $x_{k,k}$ and $z_{k,-k}$ can be connected to $y_{-k,k}$ and $w_{-k,-k}$ respectively through  horizontal paths of same length (say $l$). Also, as $V_k$'s are irreducible for all $k$, the strips $x_{-k,k}\ldots x_{k,k}\ldots y_{-k,k}\ldots y_{k,k}$ and $z_{-k,-k}\ldots z_{k,-k}\ldots w_{-k,-k}\ldots w_{k,-k}$ can be connected vertically (say through a path of length $p$).  Consequently, there exists patterns of the form

z_{-k,k} & \hdots  &  z_{k,k} &\hskip 1.5cm&  w_{-k,k} & \hdots  & w_{k,k} \\
\vdots & \vdots  & \vdots   && \vdots & \vdots  & \vdots  \\
z_{-k,-k}  & \hdots & z_{k,-k}  && w_{-k,-k}  & \hdots & w_{k,-k}\\
&&&&&&&&&& \\
\vdots&\vdots& \vdots&&\vdots&\vdots&\vdots&&&& \\
\vdots&\vdots& \vdots&&\vdots&\vdots&\vdots&&&& \\
&&&&&&&&&& \\
x_{-k,k} & \hdots  &  x_{k,k} &&  y_{-k,k} & \hdots  & y_{k,k} \\
\vdots & \vdots  & \vdots   &&  \vdots & \vdots  & \vdots  \\
x_{-k,-k}  & \hdots & x_{k,-k}  &&   y_{-k,-k}  & \hdots & y_{k,-k}\\
\end{array} } $$

which are valid for the shift space $X_G$ and hence can be extended to  configurations in $X_G$ (say $r$ and $s$ respectively). Finally, note that while $r\in U, s\in V$ (as central blocks of $r$ and $s$ are $x_k$ and $y_k$ respectively), we also have $\sigma^{(0,2k+1+p)}(r)\in Z$ and  $\sigma^{(0,2k+1+p)}(s)\in W$ (as their central blocks are $z_k$ and $w_k$ respectively). Consequently, $X_G$ exhibits weak mixing and the proof of forward part is complete.

Conversely, if $X_G$ exhibits vertical weak mixing then it exhibits vertical doubly transitivity and the proof is complete.

The above results establish the equivalence of vertical doubly transitivity and vertical weak mixing under the condition $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ for all $i,j$ when $H$ exhibits weak mixing. For stronger notions of mixing in any direction $(r,s)$, it may be noted that as shift in a particular direction is a one dimensional map and stronger notions of mixing (such as total transitivity, weak mixing and strong mixing) are equivalent for one dimensional shifts, similar arguments establish analogous results for various notions of directional mixing.  It may be noted that while any of the mixing notions for one of the generating matrices ensures the same for $X_G$ under $(HV)_{ij}\neq 0 \Leftrightarrow (VH)_{ij}\neq 0$ for all $i,j$, any of the mixing notions for $X_G$ need not ensure the same for any of the generating matrices under the conditions imposed. We now give an example in support of our claim.

Let $X_G$ be a shift space arising from following adjacency matrices:

$$\textit{H}= \bordermatrix{ & 0 & 1 & 2 & 3  \cr
0 & 1 & 1 & 1 & 1   \cr
1 & 1 & 1 & 1 & 1   \cr
2 & 0 & 0 & 1 & 1  \cr
3 & 0 & 0 & 1 & 1   \cr
\ \ \ \ \ \
\textit{V}= \bordermatrix{ & 0 & 1 & 2 & 3  \cr
0 & 1 & 1 & 0 & 0   \cr
1 & 1 & 1 & 0 & 0   \cr
2 & 1 & 1 & 1 & 1   \cr
3 & 1 & 1 & 1 & 1   \cr

It may be noted that $H$ and $V$ are not irreducible. However, as $(HV)_{ij} \neq 0 \Leftrightarrow (VH)_{ij} \neq 0 \ \forall \ i,j$ holds and $HV$ is primitive, the shift space $X_G$ exhibits $(1,1)$-weak mixing. Consequently, weak mixing (directional weak mixing) for $X_G$ need not ensure weak mixing (any form of mixing) for any of the generating matrices.

We now turn our attention to the graph shifts arising from graph products between two-dimensional graphs $G_i= (H_i, V_i)$. It may be noted that if a two-dimensional graph $G$ can be expressed as a graph product of some two-dimensional graphs, then dynamics of shift space $X_G$ can be investigated through graphs of reduced complexity and hence provides a more efficient way of investigating the dynamics of the shift space under discussion. Before we move further, we first provide an example in support of our claim.

Let $G$ be a two-dimensional graph generated by matrices

$$\textit{H}= \bordermatrix{ & a & b & c & d & e & f  \cr
a & 1 & 1 & 1 & 1 & 0 & 0 \cr
b & 1 & 0 & 1  & 0 & 0 & 0 \cr
c & 0 & 0 & 0  & 0 & 1 & 1 \cr
d & 0 & 0 & 0  & 0  & 1 & 0\cr
e & 1 & 1 & 0  & 0  & 0 & 0\cr
f & 1 & 0 & 0  & 0  & 0 & 0\cr
\ \ \ \ \ \
\textit{V}= \bordermatrix{ & a & b & c & d & e & f  \cr
a & 0 & 0 & 1 & 1 & 1 & 1 \cr
b & 0& 0 & 1  & 0 & 1 & 0 \cr
c & 1 & 1 & 0  & 0 & 0 & 0 \cr
d & 1 & 0 & 0  & 0  & 0 & 0\cr
e & 1 & 1 & 0  & 0  & 0 & 0\cr
f & 1 & 0 & 0  & 0  & 0 & 0\cr

Next, consider matrices

$$\textit{$H_1$}= \bordermatrix{ & 0 & 1 & 2  \cr
0 & 1 & 1 & 0   \cr
1 & 0 & 0 &  1  \cr
2 & 1 & 0 &  0  \cr
\ \ \ \
\textit{$ V_1 $}= \bordermatrix{ & 0 & 1 & 2  \cr
0 & 0 & 1 & 1   \cr
1 & 1 & 0 & 0   \cr
2 & 1 & 0 & 0   \cr

$$\textit{$H_2$}= \bordermatrix{ & 3 & 4  \cr
3 & 1 & 1   \cr
4 & 1 & 0  \cr
\ \ \ \
\textit{$ V_2 $}= \bordermatrix{ & 3 & 4  \cr
3 & 1 & 1   \cr
4 & 1 & 0  \cr

It can be observed that $ \exists$ indices $i,j$ such that $(HV)_{ij}=0$ but $(VH)_{ij}\neq 0$ and $ \exists$ indices $k,l$ such that $(VH)_{kl}=0$ but $(HV)_{kl}\neq 0$. However, as $H=H_1 \times H_2$ and $V=V_1 \times V_2$, the two-dimensional graph $G=(H,V)$ can be expressed as the Tensor product $G_1 \times G_2$, where $G_i= (H_i, V_i)$ for $i \in \{1,2\}$. Consequently, $X_G$ is conjugate to $X_{G_1 \times G_2}$ and thus the qualitative nature of the shift space can be investigated through dynamics of “much simpler spaces" $X_{G_1}$ and $X_{G_2}$. In particular, it can be seen that $X_{G_1}$ and $X_{G_2}$ are non-empty, have horizontal (vertical) periodic points and are $(1,1)$-transitive. Consequently, the shift space $X_G$ is indeed non-empty, has horizontal (vertical) periodic points and is also $(1,1)$-transitive. Consequently, the dynamics of the shift space $X_G$ can be investigated through dynamics of “much simpler spaces" $X_{G_1}$ and $X_{G_2}$.

For any given graph $G=(V,E)$ with $n$ vertices, $G$ can be expressed as a Tensor product of two graphs if and only if there exists $r_1,r_2\in\mathbb{N}$ such that $n=r_1r_2$, a $r_2\times r_2$ matrix $B$ and a permutation $\{v_{\sigma(1)},v_{\sigma(2)}, \ldots, v_{\sigma(n)} \}$ of the vertex set $V$ such that adjacency matrix $A_G$ (with respect to $\{v_{\sigma(1)},v_{\sigma(2)},\ldots,v_{\sigma(n)} \}$) is of the form

$\bordermatrix{ & &  &  & \cr
&	S_{11} & S_{12} & \ldots & S_{1 r_2} \cr
&   S_{21} & S_{22} & \ldots & S_{2 r_2} \cr
&   \vdots & \vdots & \vdots & \vdots \cr
&   S_{r_11} & S_{r_12} & \ldots & S_{r_1 r_2} \cr
\ \ \ \ \ \ $  where $S_{ij}$ are either $B$ or $0$ (the zero matrix)

First, consider that graph $G$ can be expressed as a Tensor product of two graphs $G_1, G_2$, where $\mathcal{V}(G_1)=\{a_1, a_2 \ldots a_{r_1}\}$ and $\mathcal{V}(G_2)=\{b_1, b_2 \ldots b_{r_2}\}$. Then, if the vertex set for Tensor product is ordered as $(a_1, b_1), (a_1, b_2)  \ldots (a_1, b_{r_2}), (a_2, b_1), (a_2, b_2)\ldots (a_2,$ $   b_{r_2}) \ldots (a_{r_1}, b_1), (a_{r_1}, b_2)\ldots $ $(a_{r_1}, b_{r_2})$, as $(a_i, b_j) (a_k, b_l) \in \mathcal{E}(G_1 \times G_2)$  if and only if  $a_i a_k \in \mathcal{E}(G_1)$ and  $b_j b_l \in \mathcal{E}(G_2)$, the adjacency matrix for the Tensor product is given by

$\bordermatrix{ & &  &  & \cr
&	S_{11} & S_{12} & \ldots & S_{1r_2} \cr
&   S_{21} & S_{22} & \ldots & S_{2r_2} \cr
&   \vdots & \vdots & \vdots & \vdots \cr
&   S_{r_11} & S_{r_12} & \ldots & S_{r_1 r_2} \cr
\ \ \ \ \ \ $ where $S_{ij}=A_{G_2}$ if $a_i$ and $a_j$ are adjacent in $G_1$ (and $0$ otherwise). As $G$ is the Tensor product of $G_1$ and $G_2$,  $A_G= A_{G_1 \times G_2}$ and hence the proof of forward part is complete.

Conversely, let the adjacency matrix of $G$ be of the form

$\bordermatrix{ & &  &  & \cr
&	S_{11} & S_{12} & \ldots & S_{1r_2} \cr
&   S_{21} & S_{22} & \ldots & S_{2r_2} \cr
&   \vdots & \vdots & \vdots & \vdots \cr
&   S_{r_11} & S_{r_12} & \ldots & S_{r_1 r_2} \cr
\ \ \ \ \ \ $  where $S_{ij}$ are either $B$ or $0$ (the zero matrix). Define $G_1=(V_1,E_1)$, where $V_1=\{a_1,a_2,\ldots a_{r_1}\}$ and $(a_i a_j) \in E_1$ if $B_{ij}=B$ and $G_2=(V_2,E_2)$ where $V_2=\{b_1,b_2,\ldots,b_{r_2}\}$ and $E_2$ be defined such that $A_{G_2}=B$. Then, as $n=r_1r_2$ and $A_G= A_{G_1 \times G_2}$, the converse holds and the proof is complete.

It may be noted that for any graph $G$, $G=G_1\times G_2$ where $G_1=G$ and $G_2=(V_2,E_2)$ with $V_2=\{v_2\}$ is a singleton and $E_2$ consists of a self loop at $v_2$. Consequently, any graph $G$ can be written as a Tensor product of two graphs. However, such a factorization does not reduce the computational complexity of the shift space induced by $G$ and the reduction of the computational complexity indeed depends on the structure of the adjacency matrix of the underlying graph. Further, for given graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$, note that $(a_i, b_j) (a_k, b_l) \in \mathcal{E}(G_1  \scalebox{0.7}{$\square$} G_2)$  if and only if  $a_i a_k \in \mathcal{E}(G_1)$ ($a_i =a_k$) and $b_j =b_l$  ($b_j b_l \in \mathcal{E}(G_2)$). Further, if $\mathcal{V}(G_1) = \{a_1, a_2 \ldots a_n\}$, $\mathcal{V}(G_2) = \{b_1, b_2 \ldots b_m\}$ and the adjacency matrix of ($G_1  \scalebox{0.7}{$\square$} G_2)$ is indexed using natural order then for $a_i \neq a_j$, while $a_i a_j \notin \mathcal{E}(G_1)$  forces the corresponding $m\times m$ block to be zero matrix, $a_i a_j \in \mathcal{E}(G_1)$ forces the corresponding  $m\times m$ block to be an $m\times m$ identity matrix (for $a_i \neq a_j$). Finally, while $a_i=a_j$ then, $a_i a_i \notin \mathcal{E}(G_1)$ forces the corresponding $m\times m$ block to be $B$, and $a_i a_i \in \mathcal{E}(G_1)$ forces the corresponding block to be $B_{ii}= B*I$ (where $B$ is a binary matrix and $*$ is a matrix operation such that $(P*Q)_{ij}=max(P_{ij}, Q_{ij})$). Consequently, the adjacency matrix of the Cartesian product of graphs can be characterized using the corresponding block representation and we get the following corollary.

For any given graph $G=(V,E)$ with $n$ vertices, $G$ can be expressed as a Cartesian product of two graphs if and only if there exists $r_1,r_2\in\mathbb{N}$ such that $n=r_1r_2$, a $r_2\times r_2$ matrix $B$ and a permutation $\{v_{\sigma(1)},v_{\sigma(2)}, \ldots, v_{\sigma(n)} \}$ of the vertex set $V$ such that adjacency matrix $A_G$ (with respect to $\{v_{\sigma(1)},v_{\sigma(2)},\ldots,v_{\sigma(n)} \}$) is of the form

$\bordermatrix{ & &  &  & \cr
&	B_{11} & B_{12} & \ldots & B_{1r_2} \cr
&   B_{21} & B_{22} & \ldots & B_{2r_2} \cr
&   \vdots & \vdots & \vdots & \vdots \cr
&   B_{r_11} & B_{r_12} & \ldots & B_{r_1 r_2} \cr
\ \ \ \ \ \ $  where 			$B_{ij} = \left\{%
\begin{array}{ll}
0 \text{~~or~~} I, & \hbox{$i\neq j$;} \\
B \text{~~or~~} (B*I)  & \hbox{$ i=j $;} \\
\end{array}%
\right.$

The proof follows from the discussion in Remark <ref>.

[1]
A. Quas, P. Trow,
Subshifts of Multidimensional shifts of finite type,
Ergodic Theory and Dynamical Systems, 20 (03), 2000, 859 - 874.

[2]
Bruce P. Kitchens,
Symbolic Dynamics: One-Sided, Two-Sided and Countable State Markov Shifts,
Universitext. Springer-Verlag, Berlin Heidelberg, 1998.

[3]
C.E. Shannon,
A mathematical theory of communication,
The Bell System Technical Journal, vol. 27, no. 3, 1948, pp. 379-423.

[4]
Coven, E., Johnson, A., Jonoska, N., and Madden, K.,
The Symbolic Dynamics Of Multidimensional Tiling Systems,
Ergodic Theory And Dynamical Systems, 23(2), 2003,  pp. 447-460.

[5]
D. Lind, B. Marcus,
An Introduction to Symbolic Dynamics and Coding,
Cambridge University Press, Cambridge, 1995.

[6]
Gert Sabidussi,
Graph Multiplication,
Mathematische Zeitschrift, vol. 72, 1959/60, pp. 446-457.

[7]
Izhikevich Eugene M.,
Dynamical Systems in Neuroscience : The Geometry of Excitability and Bursting,
Cambridge Mass: MIT Press., 2007.

[8]
Jan De Vries,
Topological Dynamical system: An Introduction to the Dynamics of Continuous Mappings.
De Gruyter, Berlin, Boston, 2014.

[9]
M. Hochman,
On the automorphism groups of multidimensional shifts of finite type,
Ergodic Theory and Dynamical Systems, 30(3), 2010, pp. 809-840, doi:10.1017/S0143385709000248.

[10]
Markley, Nelson G. and Paul, Michael E.,
Matrix Subshifts for $\mathbb{Z}^v$ Symbolic Dynamics,
Proceedings of the London Mathematical Society, Volume s3-43, Issue 2, September 1981, pp. 251–272.

[11]
Markley, Nelson G. and Paul, Michael E.,
Maximal Measures and Entropy for  $\mathbb{Z}^v$ Subshifts of Finite Type,
Classical Mechanics and Dynamical Systems, 1981, pp. 135–157.

[12]
Michael Hochman,
On Dynamics and Recursive Properties of Multidimensional Symbolic Dynamics,
Inventiones Mathematica, Volume 176, Number 1, April, 2009.

[13]
Michael Hochman, Tom Meyerovitch,
A Characterization of the Entropies of Multidimensional Shifts of Finite type,
Annals of Mathematics, Vol. 171 (2010), No. 3, 2011-2038.

[14]
Mike Boyle, Ronnie Pavlov, and Michael Schraudner,
Multidimensional Sofic Shifts without Separation and their Factors,
Transactions of the American Mathematical Society, Volume 362, Number 9, September 2010, Pages 4617-4653.

[15]
Morse, Marston, and Gustav A. Hedlund,
Symbolic Dynamics II. Sturmian Trajectories,
American Journal of Mathematics,  vol. 62, no. 1, 1940, pp. 1–42.

[16]
Natasa Jonoska, Joni Burnette Pirnot,
Transitivity in two-dimensional Local Languages Defined by Dot Systems,
International Journal of Foundations of Computer Science, vol. 17, no. 2, 2006, pp. 435-463, https://doi.org/10.1142/S0129054106003917.

[17]
Paul M. Weichsel,
The Kronecker product of graphs,
Proceedings of the American Mathematical Society,  vol 13 (1962), pp. 47-52.

[18]
Prashant Kumar and Puneet Sharma,
On Graph Induced Symbolic Systems,
Appl. Gen. Topol.,  vol. 24, no. 2, pp. 359–378, Oct. 2023.

[19]
Puneet Sharma and Dileep Kumar
Matrix characterization of multidimensional subshifts of finite type,
Appl. Gen. Topol., vol. 20, no. 2, pp. 407–418, Oct. 2019.

[20]
Puneet Sharma and Dileep Kumar
Multidimensional Shifts and Finite Matrices,
Topology Proceedings, vol. 57, pp. 241–257, 2021.

[21]
R. Berger
The undecidability of the Domino Problem,
Mem. Amer. Math. Soc., 66, 1966.

[22]
Robinson, R.M,
Undecidability and nonperiodicity for tilings of the plane,
Inventiones mathematicae, 12, 1971, pp. 177-209.

[23]
Morphisms from non-periodic $Z^2$-subshifts I: Constructing embeddings from homomorphisms,
Ergodic Theory Dynamical Systems, 23 (2), 2003, pp. 587-609.

[24]
Song M, Ouyang Z, Liu ZL,
Discrete dynamical system modelling for gene regulatory networks of 5-hydroxymethylfurfural tolerance for ethanologenic yeast,
IET Syst Biol., 2009 May;3(3):203-18. doi: 10.1049/iet-syb.2008.0089.

[25]
T. K. Subrahmonian Moothathu,
Stronger forms of sensitivity for dynamical systems,
Nonlinearity,  vol. 20, no. 9, 2007, pp. 2115 -2126.

[26]
Ted Janssen and Marc de Boissieu,
Dynamics of quasicrystals,
Comptes Rendus Physique, vol. 15, no. 1, 2014, pp. 58-69.

[27]
Xin-Chu Fu, WeiPing Lu, Peter Ashwin, Jinqiao Duan,
Symbolic Representations of Iterated Maps,
Topological Methods in Nonlinear Analysis, volume 18, no. 1, 2001, pp.  119-147.