# A Complete Invariant for Shift Equivalence for Boolean Matrices and Finite
Relations

Ethan Akin  Mathematics Department
The City College
137 Street and Convent Avenue
New York City, NY 10031, USA<EMAIL_ADDRESS>,  Marian Mrozek
Division of Computational Mathematics, Faculty of Mathematics and Computer
Science, Jagiellonian University, ul. St. Łojasiewicza 6, 30-348 Kraków,
Poland<EMAIL_ADDRESS>,  Mateusz Przybylski  Division of
Computational Mathematics, Faculty of Mathematics and Computer Science,
Jagiellonian University, ul. St. Łojasiewicza 6, 30-348 Kraków, Poland
<EMAIL_ADDRESS>and  Jim Wiseman  Department of Mathematics
Agnes Scott College
141 East College Avenue
Decatur, GA 30030, USA<EMAIL_ADDRESS>
###### Abstract.

We give a complete invariant for shift equivalence for Boolean matrices
(equivalently finite relations), in terms of the period, the induced partial
order on recurrent components, and the cohomology class of the relation on
those components.

##  1\. Introduction

Let $X$ be a finite set. A relation $R$ on $X$ is a subset of $X\times X$ and
associated to it is a subshift of finite type, an important and well-studied
dynamical system. The relation can equivalently be described by a Boolean
matrix (a $(0,1)$-matrix for which matrix addition and multiplication are
induced by Boolean algebra, where $1+1=0+1=1$). For such a relation (or
matrix) _shift equivalence_ is a natural equivalence relation with important
dynamical significance. It is strictly weaker than conjugacy, and corresponds
roughly to “eventual conjugacy” ([9]). It is useful in the classification of
such subshifts and it arises in defining a Conley index for computational
approximations of dynamical systems. Classifications of shift equivalence are
given in [3, 4, 10]. Here, we give a complete invariant in terms of the
period, the induced partial order on recurrent components, and the cohomology
class of the relation on those components.

Our main theorem is as follows. (We define the relevant terms more precisely
in sections 2 and 3.) There exists a least integer $p\geq 1$ such that there
exists an integer $N>0$ such that $R^{n+p}=R^{n}$ for all $n\geq N$; we call
$p$ the _period_ of $R$. Additionally, $R$ induces a partial order $R_{\geq}$
on the strongly connected components, determined by which components map to
which. Finally, a choice of representatives of the strongly connected
components induces a cocycle $\xi:R_{\geq}\to\mathcal{L}_{p}$, where
$\mathcal{L}_{p}$ is the additive monoid of non-empty subsets of
$\mathbb{Z}/p\mathbb{Z}$; we denote the cohomology class of $\xi$ by $[\xi]$.

######  Theorem.

For a finite relation $R$, the triple $(R_{\geq}$, $p$, $[\xi])$ is a complete
invariant of shift equivalence.

##  2\. Background and definitions

Let $X$ and $Y$ be sets. A _relation_ from $X$ to $Y$ is a subset $R\subseteq
X\times Y$. If $X=Y$ we call $R$ a _relation on_ $X$, and denote the pair by
$(X,R)$. For $x\in X$ and $A\subseteq X$ we define

$R(x):=\\{y\in Y:(x,y)\in R\\},$ $R(A):=\bigcup\\{R(x):x\in A\\}.$

Given a relation $R\subseteq X\times Y$, the _reverse relation_
$R^{-1}\subseteq Y\times X$ is defined by $R^{-1}:=\\{(y,x):(x,y)\in R\\}$.

Given another relation $S\subseteq Y\times Z$ we define the _composition_ of
$S$ with $R$ as the relation

$S\circ R:=\\{(x,z)\in X\times Z:\text{ $(x,y)\in R$ and $(y,z)\in S$ for some
$y\in Y$}\\}.$

As with functions, composition of relations is associative.

The identity relation on $X$ is $\operatorname{id}_{X}=\\{(x,x):x\in X\\}$.
For $n\in\mathbb{Z}_{+}$ the _$n$ th power_ of a relation $R$ in $X$ is given
recursively by

$R^{n}:=\begin{cases}\operatorname{id}_{X}&\text{ for $n=0$,}\\\ R\circ
R^{n-1}&\text{ for $n>0$.}\\\ \end{cases}$

From associativity it follows that $R^{i}\circ R^{j}=R^{i+j}$ for all
$i,j\in\mathbb{Z}_{+}$, the set of nonnegative integers.

Now let $X$ be a finite set. We can think of a relation on $X$ in various
ways: as a Boolean matrix, a directed graph, a multi-valued map, or a morphism
in an appropriately defined category. We discuss each briefly.

### Boolean matrix

If $X=\\{x_{1},\dots,x_{n}\\}$, then we can identify a relation $R$ on $X$
with the $n\times n$ Boolean matrix $A$ with $i,j$ entry given by 1 if
$x_{i}\in R(x_{j})$ and 0 otherwise. It is easy to check that $A^{n}$ (where
matrix multiplication is Boolean) is the matrix for the relation $R^{n}$. Thus
any statement about finite relations has a corresponding linear algebraic
statement about Boolean matrices. Furthermore, Boolean matrices describe the
structure of nonnegative matrices, since the map sending positive numbers to 1
and 0 to 0 is a homomorphism. See [8] for details, and [1] for applications.

### Directed graph

We can identify a finite relation $(X,R)$ with the directed graph whose
vertices are the elements of $X$ and with an edge from $x$ to $y$ if and only
if $y\in R(x)$. Thus, there is a path in the graph of length $n$ from $x$ to
$y$ if and only if $y\in R^{n}(x)$. It is often convenient to think of $(X,R)$
in this way and to use graph-theoretic terminology. The Boolean matrix
corresponds to the adjacency matrix for the directed graph.

### Multi-valued map

We can think of a relation as a multi-valued map, where the image of a point
$x$ is the set $R(x)$. (In general, the image could be empty, but when
considering shift equivalence, we can assume that it contains at least one
point ([10]Proposition 13). This is equivalent to the condition that every
vertex in the directed graph have at least one outgoing edge, or the condition
that every column of the Boolean matrix have at least one 1.) From a dynamical
systems point of view, the powers $R^{n}$ tell us about the long-term behavior
of the map under iteration. In this context, finite relations can arise from
ordinary (single-valued) maps in the form of numerical approximations or
reconstructions from sampled data.

### The category $\text{\sc Rel}_{\mathrm{f}}$.

The objects in the category $\text{\sc Rel}_{\mathrm{f}}$ are finite sets, and
the morphisms from set $X$ to set $Y$ are the relations from $X$ to $Y$.
Composition of morphisms is composition of relations, and the identity
morphism is the identity relation. This is the viewpoint we will adopt when we
consider the Szymczak functor and shift equivalence below.

### The category $\operatorname{End}(\text{\sc Rel}_{\mathrm{f}})$.

This is the category of endomorphisms of $\text{\sc Rel}_{\mathrm{f}}$. The
objects of $\operatorname{End}(\text{\sc Rel}_{\mathrm{f}})$ are pairs
$(X,R)$, where $X$ is a finite set (an object in $\text{\sc
Rel}_{\mathrm{f}}$) and $R$ is a relation on $X$ (a morphism from $X$ to $X$).
A morphism $A$ from $(X,R)$ to $(X^{\prime},R^{\prime})$ (written
$A:(X,R)\to(X^{\prime},R^{\prime})$ ) is a relation $A$ from $X$ to
$X^{\prime}$ such that $R^{\prime}\circ A=A\circ R$.

######  Definition 2.1.

Two finite relations $(X,R)$ and $(X^{\prime},R^{\prime})$ are _shift
equivalent_ if there exist morphisms $A:(X,R)\to(X^{\prime},R^{\prime})$ and
$B:(X^{\prime},R^{\prime})\to(X,R)$ such that for some
$\ell\in\mathbb{Z}_{+}$, $B\circ A=R^{\ell}$ and $A\circ
B=(R^{\prime})^{\ell}$.

If we think of $R$ and $R^{\prime}$ as Boolean matrices, then this is just the
usual notion of shift equivalence for Boolean matrices ([3]). Working from
$\operatorname{End}(\text{\sc Rel}_{\mathrm{f}})$ we define a category for
which shift equivalence is the isomorphism concept.

### The category $\text{\sc Szym}(\text{\sc Rel}_{\mathrm{f}})$.

We can now define the Szymczak category $\text{\sc Szym}(\text{\sc
Rel}_{\mathrm{f}})$ (cf. [11]). The objects of $\text{\sc Szym}(\text{\sc
Rel}_{\mathrm{f}})$ are the objects of $\operatorname{End}(\text{\sc
Rel}_{\mathrm{f}})$. Given objects $(X,R)$ and $(X^{\prime},R^{\prime})$ in
$\text{\sc Szym}(\text{\sc Rel}_{\mathrm{f}})$, we consider the equivalence
relation given by $(A_{1},m_{1})\equiv(A_{2},m_{2})$, for
$A_{1},A_{2}:(X,R)\to(X^{\prime},R^{\prime})$ and
$m_{1},m_{2}\in\mathbb{Z}_{+}$, if and only if there exists a
$k\in\mathbb{Z}_{+}$ such that $A_{1}\circ R^{m_{2}+k}=A_{2}\circ
R^{m_{1}+k}$, or equivalently $(R^{\prime})^{m_{2}+k}\circ
A_{1}=(R^{\prime})^{m_{1}+k}\circ A_{2}$. The morphisms in $\text{\sc
Szym}(\text{\sc Rel}_{\mathrm{f}})$ from $(X,R)$ to $(X^{\prime},R^{\prime})$
are the equivalence classes of $\equiv$. Composition is given by
$[A^{\prime},m^{\prime}]\circ[A,m]=[A^{\prime}\circ A,m+m^{\prime}]$ and
$[\operatorname{id}_{X},0]$ is the identity morphism on $(X,R)$.

For example, for any $(X,R)\in\operatorname{End}(\text{\sc Rel}_{\mathrm{f}})$
and $m\in\mathbb{N}$, $R^{m}:(X,R)\to(X,R)$ is a morphism with
$[R^{m},m]=[id_{X},0]$.

The functor $\text{\sc Szym}:\operatorname{End}(\text{\sc
Rel}_{\mathrm{f}})\to\text{\sc Szym}(\text{\sc Rel}_{\mathrm{f}})$ fixes
objects and sends a morphism $A$ to $[A,0]$.

As shown in [2]Proposition 8.1, $(X,R)$ and $(X^{\prime},R^{\prime})$ are
shift equivalent if and only if they are isomorphic in the Szymczak category.
Notice that if $[A,m]:(X,R)\to(X^{\prime},R^{\prime})$ and
$[B,n]:(X^{\prime},R^{\prime})\to(X,R)$ are inverse isomorphisms in $\text{\sc
Szym}(\text{\sc Rel}_{\mathrm{f}})$, then for some $k,\ BAR^{k}=R^{m+n+k}$ and
$AR^{k}B=AB(R^{\prime})^{k}=(R^{\prime})^{m+n+k}$. So $A\circ
R^{k}:(X,R)\to(X^{\prime},R^{\prime})$ and $B:(X^{\prime},R^{\prime})\to(X,R)$
yield the shift equivalence with $\ell=m+n+k$.

Shift equivalence (Szymczak isomorphism) is an important notion dynamically,
when we consider the long-term behavior of a relation. Very roughly speaking,
it ignores transient behavior and focuses on the dynamics within and between
recurrent components. The same is true when we consider powers of graphs. In
[3, 4], Kim and Roush consider shift equivalence of Boolean matrices in part
as a step toward disproving the Williams Conjecture from symbolic dynamics
([5, 6, 7]). They provide the following algebraic classification of Boolean
matrices up to shift equivalence.

######  Theorem 2.2 ([4]Proposition 3.5).

Every matrix is shift equivalent to a periodic power of itself. Two periodic
matrices are shift equivalent if and only if after deletion of dependent rows
and columns, they are conjugate by a permutation matrix.

Another important application is in defining the discrete Conley index for
continuous self-maps [11], which provides information about invariant sets.
The form of the index relies on choices made in its construction, and it is
defined exactly up to shift equivalence. In this context it is useful to have
a dynamical, rather than algebraic, classification of finite relations up to
shift equivalence. Such a classification was given in [10] as a step toward
defining a Conley index for such relations, particularly those approximating
physical systems.

To state the result from [10] on shift equivalence, and to describe the
complete invariant in the next section, we need a few more definitions.

For a relation $R$ on $X$, we write $x\to_{R}y$ if there is a path from $x$ to
$y$ in the graph corresponding to $R$, or, equivalently, if $y\in R^{n}(x)$
for some $n\in\mathbb{N}$, the set of positive integers. We say that $x$ is
_recurrent_ if $x\to_{R}x$, and denote by $X_{R}$ the set of recurrent points.
We write $x\leftrightarrow_{R}y$ if $y\to_{R}x$ and $x\to_{R}y$. For the
purposes of shift equivalence, we can assume that every point is recurrent
([10]Theorem 11), so the relation $\leftrightarrow_{R}$ is an equivalence
relation; in accordance with graph theory usage, we call the equivalence
classes the _strongly connected components_. For a recurrent point $x$, we
denote the strongly connected component to which it belongs by $[x]_{R}$, and
the quotient $X/\leftrightarrow_{R}$ (the set of strongly connected
components) by $\overline{X}$.

Observe that $\to_{R}$ induces a partial order on $\overline{X}$ as follows:
$[x]_{R}\geq[y]_{R}$ if $x\to_{R}y$, which is clearly independent of the
choice of representatives of $[x]_{R}$ and $[y]_{R}$. For notational clarity,
we will somewhat redundantly denote the relationship $\geq$ by $R_{\geq}$,
that is, $([x]_{R},[y]_{R})\in R_{\geq}$ if and only if $[x]_{R}\geq[y]_{R}$.

######  Definition 2.3.

Let $X$ be a finite set. A relation $R$ on $X$ is in _canonical form_ if

  1. (1)

every point of $X$ is recurrent,

  2. (2)

$R$ is a bijection (and hence cyclic) on each strongly connected component,
and

  3. (3)

$R$ is periodic, that is, there exists a least integer $p\geq 1$, called the
period of $R$, such that $R^{p+1}=R$.

Shift equivalence can be characterized as follows.

######  Theorem 2.4 ([10]Theorems 12, 13).

Let $(X,R)$ be a finite relation. Then $(X,R)$ is shift equivalent to a finite
relation in canonical form. Furthermore, two relations $(X,R)$ and
$(X^{\prime},R^{\prime})$ in canonical form are shift equivalent if and only
if they are isomorphic, that is, there is a bijection $h:X\to X^{\prime}$ such
that $h\circ R=R^{\prime}\circ h$.

The reduction to canonical form is constructive. We sketch the steps.

### Periodicity

Since the infinite sequence $\\{R^{n}\\}$ consists of subsets of a finite set,
it follows that the set

(1) $\operatorname{Per}(R)=\\{q\in\mathbb{N}:R^{q+N(q)}=R^{N(q)}\ \text{for
some}\ N(q)\in\mathbb{N}\\}$

is nonempty. Clearly, if $n\geq N(q)$, then $R^{q+n}=R^{n}$.

######  Definition 2.5.

An _eventual period_ for $R$ is $q\in\mathbb{N}$ such that $R^{q}\circ
R^{q}=R^{q}$ and so $R^{q+n}=R^{n}$ for all $n\geq q$. In particular,
$R^{nq}=R^{q}$ for all $n\in\mathbb{N}$.

An eventual period $q$ is an element of $\operatorname{Per}(R)$. On the other
hand, if $q\in\operatorname{Per}(R)$ and $Nq\geq N(q)$, then $Nq$ is an
eventual period.

######  Proposition 2.6.

  * (a)

There exists $p\in\mathbb{N}$ such that $\operatorname{Per}(R)=p\mathbb{N}$.
In particular, if $q$ is an eventual period, then $p|q$. We call $p$ the
_period_ of $R$ (despite the fact that it need not be an eventual period).

  * (b)

If $q_{1},q_{2}$ are eventual periods, then $R^{q_{1}}=R^{q_{2}}$.

  * (c)

If $q$ is an eventual period and $p$ is the period, then $R^{q+p}=R^{q}$.

  * (d)

Define $\bar{R}=R^{q+1}$ where $q$ is an eventual period. For all
$n\in\mathbb{N}$,

(2) $\bar{R}^{n}=R^{q+n}=\bar{R}^{p+n}$

In particular, $\bar{R}^{np}=R^{q}$ for all $n\in\mathbb{N}$.

  * (e)

The period $p$ is the minimum element of the set
$\\{p^{\prime}\in\mathbb{N}:R^{q+p^{\prime}}=R^{q}\\}$.

###### Proof.

(a) For $q_{1},q_{2}\in\operatorname{Per}(R),$ if $M\geq N(q_{1}),N(q_{2})$,
then $R^{q_{1}+q_{2}+M}=R^{q_{2}+M}=R^{M}.$ Thus, $\operatorname{Per}(R)$ is
an additive sub-semigroup of $\mathbb{N}$. Let $p$ be the gcd of
$\operatorname{Per}(R)$. It follows that for sufficiently large $N$,
$Np\in\operatorname{Per}(R)$. For a proof of this classical result see, e.g.
[10] Lemma 1. It follows that $p|q$ for all $q\in\operatorname{Per}(R)$. Let
$N$ be large enough that $Np$ and $(N+1)p$ are in $\operatorname{Per}(R)$. If
$M\geq N(Np),N((N+1)p)$, then $R^{p+M}=R^{Np+p+M}=R^{(N+1)p+M}=R^{M}.$ Thus,
$p\in\operatorname{Per}(R)$ and so is every multiple of $p$.

(b) Assume $q_{1}\leq q_{2}$. Since $q_{1}$ is an eventual period,
$R^{q_{1}+q_{2}}=R^{q_{2}}$. Choose $N$ so that $Nq_{1}\geq q_{2}$. Since
$q_{1}$ is an eventual period $R^{Nq_{1}}=R^{q_{1}}$. Hence, because $q_{2}$
is an eventual period,
$R^{q_{1}}=R^{Nq_{1}}=R^{Nq_{1}+q_{2}}=R^{q_{1}+q_{2}}$.

(c) Since $p\in\operatorname{Per}(R)$, for large enough $N$,
$R^{p+q}=R^{p+Nq}=R^{Nq}=R^{q}$, where again we use $R^{Nq}=R^{q}$.

(d) $\bar{R}^{n}=R^{(q+1)n}=R^{nq+n}=R^{q+n}$ since $R^{nq}=R^{q}$. In
particular, $\bar{R}^{p+n}=R^{q+p+n}=R^{q+n}$. Furthermore,
$\bar{R}^{np}=R^{q+np}=R^{q}$ by induction on $n$.

(e) If $R^{q+p^{\prime}}=R^{q}$, then $p^{\prime}\in\operatorname{Per}(R)$ and
so $p|p^{\prime}$. ∎

We now fix an eventual period $q$.

It easily follows that $[R^{q},q]:(X,R)\to(X,\bar{R})$ and
$[R^{q},q]:(X,\bar{R})\to(X,R)$ are inverse isomorphisms in $\text{\sc
Szym}(\text{\sc Rel}_{\mathrm{f}})$. For details see [10] Theorem 9.

### Recurrence

Recall that $x$ is recurrent for $R$ if $x\rightarrow_{R}x$ or, equivalently,
$x\in R^{n}(x)$ for some $n\in\mathbb{N}$. It then follows that for any
$k\in\mathbb{N}$, $x\in R^{kn}(x)$ and so $x$ is recurrent for $R^{k}$. Thus,
$x$ is recurrent for $R$ if and only if it is recurrent for $R^{k}$. In
particular, $x$ is recurrent for $R$ if and only if for $R^{q}$ and so if and
only if for some $n$, $x\in R^{nq}(x)=R^{q}(x)$. Thus $X_{R}$, the set of
recurrent points, equals $\\{x:x\in R^{q}(x)=\bar{R}^{p}(x)\\}$.

In general, $x\rightarrow_{R}y$ if $y\in R^{n}(x)$ for some $n\in\mathbb{N}$.
Hence, $x\rightarrow_{\bar{R}}y$ if $y\in\bar{R}^{n}(x)=R^{q+n}(x)$ for some
$n\in\mathbb{N}$. If $y\in R^{n}(x)$ and $x\in X_{R}$, then $x\in R^{q}(x)$
and so $y\in R^{q+n}(x)$. Similarly, if $y\in X_{R}$, then $y\in R^{q+n}(x)$.
Thus, if $x$ or $y$ is recurrent, then $x\rightarrow_{R}y$ if and only if
$x\rightarrow_{\bar{R}}y$. In particular, if $x\leftrightarrow_{R}y$ then both
$x$ and $y$ are recurrent and so $x\leftrightarrow_{\bar{R}}y$.

######  Lemma 2.7.

If $x\in X_{R}$, then
$\operatorname{Per}(x)=\\{n\in\mathbb{N}:x\in\bar{R}^{n}(x)=R^{q+n}(x)\\}$ is
nonempty and there exists $p^{\prime}(x)\in\mathbb{N}$ such that
$\operatorname{Per}(x)=p^{\prime}(x)\mathbb{N}$. In particular,
$p^{\prime}(x)|p$. Furthermore, $p$ is the least common multiple of the set
$\\{p^{\prime}(x):x\in X_{R}\\}$.

In addition, if $x\leftrightarrow_{R}y$ then $p^{\prime}(x)=p^{\prime}(y)$.

###### Proof.

If $x\in\bar{R}^{n}(x)$, then $\bar{R}^{m}(x)\subset\bar{R}^{n+m}(x)$. So if
$x\in\bar{R}^{m}(x)$ as well, then $x\in\bar{R}^{n+m}(x)$. That is,
$\operatorname{Per}(x)$ is a sub-semigroup of $\mathbb{N}$. Let
$p^{\prime}(x)$ be the gcd. Since $x\in\bar{R}^{p}(x)$, it follows that
$p^{\prime}(x)|p$. As before, large enough multiples of
$p^{\prime}=p^{\prime}(x)$ are contained in $\operatorname{Per}(x)$. Hence,
for large enough $N$, $Np+p^{\prime}\in\operatorname{Per}(x)$. Hence,
$x\in\bar{R}^{Np+p^{\prime}}(x)=\bar{R}^{p^{\prime}}(x)$. Thus,
$p^{\prime}\in\operatorname{Per}(x)$ and so
$\operatorname{Per}(x)=p^{\prime}\mathbb{N}$. If $\ell$ is the lcm of the
$p^{\prime}(x)$’s, then $\ell$ divides $p$ since each $p^{\prime}(x)$ does. On
the other hand, if $y\in R^{q}(x)$, then $y\in R^{q+np^{\prime}(x)}(x)$ for
all $n\in\mathbb{Z}_{+}$ and so $y\in R^{q+\ell}(x)$. Conversely, if $y\in
R^{q+\ell}(x)$, then $y\in R^{q+\ell+np^{\prime}(x)}(x)$ for all
$n\in\mathbb{Z}_{+}$. We can choose $n$ so that $\ell+np^{\prime}(x)=q$. Thus,
$y\in R^{2q}(x)=R^{q}(x)$. We have shown that $R^{q+\ell}=R^{q}$. From
Proposition 2.6 (e) it follows that $p\leq\ell$.

If $y\leftrightarrow_{\bar{R}}x$, then for some $i$, $y\in\bar{R}^{i}(x)$.
Since $x\in\bar{R}^{np^{\prime}(x)}(x)$, $y\in R^{i+np^{\prime}(x)}(x)$ for
all $n\in\mathbb{N}$. On the other hand, for some $j$, $x\in\bar{R}^{j}(y)$
and so $y\in R^{i+j+np^{\prime}(x)}(y)$ for all $n$. Therefore,
$p^{\prime}(y)|(i+j+np^{\prime}(x))$ for all $n$ and so
$p^{\prime}(y)|p^{\prime}(x)$. Similarly, $p^{\prime}(x)|p^{\prime}(y)$. ∎

######  Lemma 2.8.

If $y\in R^{q+i+j}(x)=\bar{R}^{i+j}(x)$ for some $i,j\in\mathbb{N}$, then
there exists $z\in X_{R}$ such that $z\in R^{q+i}(x)=\bar{R}^{i}(x)$ and $y\in
R^{q+j}(z)=\bar{R}^{j}(z)$.

###### Proof.

By reducing mod $q$ we may assume $i,j\leq q$. Since $R^{Nq+i+j}=R^{q+i+j}$,
we can choose $N$ so that $(N-2)q$ is greater than the cardinality of $X$ and
obtain a path $x=x_{0},x_{1},\dots,x_{Nq+i+j}=y$. It follows that the portion
of the path from $x_{q}$ to $x_{(N-1)q+i+j}$ contains a loop and so contains a
recurrent point. Insert a cycle of length $q$ beginning and ending at this
point. Of course all of the points of this cycle are recurrent. Renumbering,
we have a path $x=x_{0},\dots,x_{(N+1)q+i+j}=y$. We can choose a point
$z=x_{t}$ on the cycle so that $t=M_{1}q+i$ for some $M_{1}\geq 1$ and so that
$((N+1)q+i+j)-t=M_{2}q+j$ for some $M_{2}\geq 1$. Thus, $z\in
R^{M_{1}q+i}(x)=R^{q+i}(x)$ and $y\in R^{M_{2}q+j}(z)=R^{q+j}(z)$. ∎

Let $\bar{R}^{n}|X_{R}=(\bar{R}^{n})\cap(X_{R}\times X_{R})$. Using the Lemma
and induction on $n$ we obtain

(3) $\bar{R}^{n}|X_{R}=(\bar{R}|X_{R})^{n}$

for all $n\in\mathbb{N}$.

Furthermore, if we define $T=R^{q}\cap(X\times X_{R})$ and
$S=R^{q}\cap(X_{R}\times X)$, it follows that
$[T,q]:(X,\bar{R})\to(X_{R},\bar{R}|X_{R})$ and
$[S,q]:(X_{R},\bar{R}|X_{R})\to(X,\bar{R})$ are inverse isomorphisms in
$\text{\sc Szym}(\text{\sc Rel}_{\mathrm{f}})$.

### Quotient

On the set $X_{R}$ of recurrent points, we define the equivalence relation

(4)
$\begin{split}\equiv_{R}:=R^{q}\cap(R^{q})^{-1}=\bar{R}^{p}\cap(\bar{R}^{p})^{-1}=\\\
\\{(x,y):y\in\bar{R}^{p}(x)\ \text{and}\ x\in\bar{R}^{p}(y)\\}.\end{split}$

Let $\pi:X_{R}\to X_{R}/\equiv_{R}$ be the quotient map to the set of
$\equiv_{R}$ equivalence classes and let $\hat{R}:=(\pi\times\pi)(\bar{R})$.

######  Proposition 2.9.

  1. (a)

If $x_{1}\equiv_{R}x_{2}$ and $y_{1}\equiv_{R}y_{2}$, then
$y_{1}\in\bar{R}^{n}(x_{1})$ if and only if $y_{2}\in\bar{R}^{n}(x_{2})$. That
is, for all $n\in\mathbb{N}$

$(\pi\times\pi)^{-1}(\hat{R}^{n})=\equiv_{R}\circ\bar{R}^{n}\circ\equiv_{R}=\bar{R}^{n}.$

  2. (b)

If $x,y,z$ lie in the same strongly connected component of $X_{R}$, i.e. each
pair is connected by $\leftrightarrow_{R}$, then for any $i\in\mathbb{N}$, if
$y,z\in\bar{R}^{i}(x)$, then $y\equiv_{R}z$.

###### Proof.

(a) This is obvious from
$\bar{R}^{p}\circ\bar{R}^{n}\circ\bar{R}^{p}=\bar{R}^{n}$.

(b) Let $p^{\prime}=p^{\prime}(x)$. There exists $j\in\mathbb{N}$ such that
$x\in\bar{R}^{j}(y)$ and so $x\in\bar{R}^{i+j}(x)$. From the definition of
$p^{\prime}(x)$ we have $p^{\prime}|(i+j)$. Write $i+j=ap^{\prime}$.

For any $n\in\mathbb{N}$, $x\in\bar{R}^{np^{\prime}}(x)$ and so
$z\in\bar{R}^{i+np^{\prime}}(x)$. It follows that
$z\in\bar{R}^{i+j+np^{\prime}}(y)$. Since $p^{\prime}|p$ we can write
$p=bp^{\prime}$. If we choose $n=a(b-1)+b$, then $p|i+j+np^{\prime}$ and so
$z\in\bar{R}^{p}(y)$. Similarly, $y\in\bar{R}^{p}(z)$ and so $y\equiv_{R}z$. ∎

It follows from part (a) that
$[\pi,0]:(X_{R},\bar{R}|X_{R})\to(X_{R}/\equiv_{R},\hat{R})$ and
$[\pi^{-1},0]:(X_{R}/\equiv_{R},\hat{R})\to(X_{R},\bar{R}|X_{R})$ are inverse
isomorphisms in $\text{\sc Szym}(\text{\sc Rel}_{\mathrm{f}})$. Note that
distinct $\leftrightarrow_{R}$ classes are mapped to distinct
$\leftrightarrow_{\hat{R}}$ classes.

From part (b) it follows that $(X_{R}/\equiv_{R},\hat{R})$ is canonical.

##  3\. The main result

Intuitively, if a relation $R$ on $X$ is in canonical form, with $p$ as its
period and $R_{\geq}$ as the partial order on the strongly connected
components, we might like to think of $R$ as a product
$R_{\geq}\times\tau_{p}$ on $\overline{X}\times\mathbb{Z}/p\mathbb{Z}$, where
$\tau_{p}$ is the shift on $\mathbb{Z}/p\mathbb{Z}$, that is,
$\tau_{p}(t)=t+1\mod p$. However, it is more complicated than that, for two
reasons. First, for a given strongly connected component, the period of the
cycle may be a proper divisor of $p$, and different components may have
different periods. Second, several points of one component may be related to a
single point of another component, or vice versa. We can address both of these
issues as follows.

In the simplest case, when these issues do not arise, $(X,R)$ is isomorphic to
$R_{\geq}\times\tau_{p}$ on $\overline{X}\times\mathbb{Z}/p\mathbb{Z}$: we can
identify a point $x\in X$ with a point
$(a,t)\in\overline{X}\times\mathbb{Z}/p\mathbb{Z}$, and the image $R(x)$ with
the set $\\{(b,t+1):(a,b)\in R_{\geq}\\}$. Otherwise, for each point
$(a,t)\in\overline{X}\times\mathbb{Z}/p\mathbb{Z}$, we need to keep track of
which other points are in the image, that is, for each $b\in R_{\geq}(a)$, the
set of integers $k\mod p$ such that $(b,t+1+k)$ is in the image of $(a,t)$.

More formally, let $\mathcal{L}_{p}$ be the collection of nonempty subsets of
$\mathbb{Z}/p\mathbb{Z}$. For $F_{1}$, $F_{2}\in\mathcal{L}_{p}$, define
$F_{1}+F_{2}:=\\{t_{1}+t_{2}:t_{1}\in F_{1},t_{2}\in F_{2}\\}$. Then
$\mathcal{L}_{p}$ is a commutative monoid with identity $\\{0\\}$.

######  Definition 3.1.

A map $\xi:R_{\geq}\to\mathcal{L}_{p}$ is a _cocycle_ for the partial order
$R_{\geq}$ if it satisfies the condition:

(5) $(a,b),(b,c)\in R_{\geq}\Rightarrow\xi(a,b)+\xi(b,c)\subseteq\xi(a,c).$

(Note that $(a,b),(b,c)\in R_{\geq}$ implies that $(a,c)\in R_{\geq}$.) If
$\xi$, $\xi^{\prime}$ are cocycles, then $\xi+\xi^{\prime}$ is a cocycle, and
so the cocycles form a monoid with identity $\xi_{0}$ defined by
$\xi_{0}(a,b)=\\{0\\}$ for all $(a,b)\in R_{\geq}$.

######  Lemma 3.2.

Let $\xi$ be a cocycle for $R_{\geq}$. If $(a,b)\in R_{\geq}$, then $\xi(a,a)$
and $\xi(b,b)$ are subgroups of $\mathbb{Z}/p\mathbb{Z}$ and

(6) $\xi(a,a)+\xi(a,b)=\xi(a,b)=\xi(a,b)+\xi(b,b).$

###### Proof.

For $F\in\mathcal{L}_{p}$, we claim that $F+F\subseteq F$ if and only if $F$
is a subgroup of $\mathbb{Z}/p\mathbb{Z}$. Clearly, if $F$ is a subgroup, then
$0\in F$ and $F+F=F$. Conversely, if $F+F\subseteq F$, then $F$ is closed
under addition, and so if $a$ is in $F$, then so are $2a,3a,\ldots$. In
particular, $0=pa\in F$ and $-a=(p-1)a\in F$. So $F$ is a subgroup.

By the definition of cocycle, we have $\xi(a,a)+\xi(a,b)\subset\xi(a,b)$.
Since $0\in\xi(a,a)$, equality holds. The proof that
$\xi(a,b)=\xi(a,b)+\xi(b,b)$ is similar. ∎

For a cocycle $\xi:R_{\geq}\to\mathcal{L}_{p}$ and $a\in\overline{X}$, let
$q_{a}$ and $p_{a}$ be the order and index, respectively, of the subgroup
$\xi(a,a)\subseteq\mathbb{Z}/p\mathbb{Z}$. Let
$\zeta=\bigcap\\{\xi(a,a):a\in\overline{X}\\}$. Let $q_{*}$ and $p_{*}$ be the
order and index, respectively, of the subgroup
$\zeta\subseteq\mathbb{Z}/p\mathbb{Z}$.

######  Definition 3.3.

A cocycle $\xi:R_{\geq}\to\mathcal{L}_{p}$ is called _irreducible_ when it
satisfies the following equivalent conditions:

  * •

The subgroup $\zeta$ is trivial, i.e.
$\bigcap\\{\xi(a,a):a\in\overline{X}\\}=\\{0\\}$.

  * •

The least common multiple of the set $\\{p_{a}:a\in\overline{X}\\}$ equals
$p$.

  * •

The greatest common divisor of the set $\\{q_{a}:a\in\overline{X}\\}$ equals
$1$.

Otherwise, $\xi$ is called _reducible_.

In general we have:

$\displaystyle p_{*}:=\text{the index of}$ $\displaystyle\ \
\zeta=lcm\\{p_{a}:a\in\overline{X}\\}.$ $\displaystyle q_{*}:=\text{the order
of}$ $\displaystyle\ \ \zeta=gcd\\{q_{a}:a\in\overline{X}\\}.$

###### Proof.

Using the quotient map $\mu_{p}:\mathbb{Z}\to\mathbb{Z}/p\mathbb{Z}$,
$\mu_{p}^{-1}(\xi(a,a))=p_{a}\mathbb{Z}$ for some $p_{a}\in\mathbb{N}$. The
quotient map $\mu_{p_{a}}$ factors to define a surjection from
$\mathbb{Z}/p\mathbb{Z}\to\mathbb{Z}/p_{a}\mathbb{Z}$ with kernel $\xi(a,a)$.
Hence, $p_{a}$ is the index of $\xi(a,a)$ in $\mathbb{Z}/p\mathbb{Z}$.
Furthermore, $\mu_{p}^{-1}(\zeta)=p_{*}\mathbb{Z}$ where $p_{*}$ is the lcm of
the $p_{a}$’s. Hence, $p_{*}$ is the index of $\zeta$.

Now we use the number theory fact that if $p_{1},\dots,p_{n}$ all divide $p$
and $p_{*}$ is the lcm, then

$p/p_{*}\ =\ gcd(p/p_{1},\dots,p/p_{n}).$

This is trivial for $n=1$ and is an easy exercise for $n=2$. The general
result then follows by induction.

It then follows that the order of $\zeta$, which equals $\ p/p_{*}$, is the
gcd of the orders $p/p_{a}$.

The equivalences in the above definition are now clear. ∎

Observe that if $\xi$ is reducible, then we have a surjection
$\rho_{p^{*}}:\mathbb{Z}/p\mathbb{Z}\to\mathbb{Z}/p_{*}\mathbb{Z}$ with kernel
$\zeta$. From Lemma 3.2 it follows that $\zeta+\xi(a,b)+\zeta=\xi(a,b)$ for
all $(a,b)\in R_{\geq}$. If we define $\xi^{*}(a,b)$ to be the image of
$\xi(a,b)$ under the map $\rho_{p^{*}}$, then we obtain a cocycle
$\xi^{*}:R_{\geq}\to\mathcal{L}_{p^{*}}$ with
$\xi(a,b)=\rho_{p^{*}}^{-1}(\xi^{*}(a,b))$ for all $(a,b)\in R_{\geq}$. We
call $\xi^{*}$ the _irreducible quotient_ of $\xi$.

Intuitively, we think of $\xi(a,b)$ as specifying the points
$(b,s)\in\overline{X}\times\mathbb{Z}/p\mathbb{Z}$ that are in the image of
$(a,t)$. Given a cocycle $\xi$, we define the relation $\overline{R}_{\xi}$ on
$\overline{X}\times\mathbb{Z}/p\mathbb{Z}$ by

(7) $\overline{R}_{\xi}(a,t)=\\{(b,s):b\in R_{\geq}(a),s-t-1\in\xi(a,b)\\},$

and more generally $\overline{R}_{\xi}^{i}(a,t)=\\{(b,s):b\in
R_{\geq}(a),s-t-i\in\xi(a,b)\\}$. In particular,
$\overline{R}_{\xi}(a,0)=\\{(b,s^{\prime}+1):b\in
R_{\geq}(a),s^{\prime}\in\xi(a,b)\\}$.

######  Proposition 3.4.

$\overline{R}_{\xi}^{i}\circ\overline{R}_{\xi}^{j}=\overline{R}_{\xi}^{i+j}$
and $\overline{R}_{\xi}^{p+i}=\overline{R}_{\xi}^{i}$ for $i,j\geq 1$. Every
point of $\overline{X}\times\mathbb{Z}/p\mathbb{Z}$ is recurrent for
$\overline{R}_{\xi}$.

###### Proof.

If $(b,s)\in\overline{R}_{\xi}^{j}(a,t)$ and
$(c,r)\in\overline{R}_{\xi}^{i}(b,s)$, then $c\in R_{\geq}(a)$ and
$r-t-(i+j)=(s-t-j)+(r-s-i)\in\xi(a,b)+\xi(b,c)\subseteq\xi(a,c)$. Thus
$(c,r)\in\overline{R}_{\xi}^{i+j}(a,t)$, and thus
$\overline{R}_{\xi}^{i}\circ\overline{R}_{\xi}^{j}\subseteq\overline{R}_{\xi}^{i+j}$.
To prove the opposite inclusion, suppose that
$(c,r)\in\overline{R}_{\xi}^{i+j}(a,t)$, so that $u=r-t-(i+j)\in\xi(a,c)$. It
is clear that $(c,t+u+j)\in\overline{R}_{\xi}^{j}(a,t)$, since
$t+u+j-t-j=u\in\xi(a,c)$, and $(c,r)\in\overline{R}_{\xi}^{i}(c,t+u+j)$, since
$r-(t+u+j)-i=0\in\xi(c,c)$, by Lemma 3.2. Thus
$\overline{R}_{\xi}^{i+j}\subseteq\overline{R}_{\xi}^{i}\circ\overline{R}_{\xi}^{j}$.

Because addition is mod $p$ it follows from the definition that
$\overline{R}_{\xi}^{p+i}=\overline{R}_{\xi}^{i}$. Finally, since
$t-t-p=0\in\xi(a,a)$, we have $(a,t)\in\overline{R}_{\xi}^{p}(a,t)$, and thus
every point is recurrent.

∎

We will recover the period of a strongly connected component, which may be a
proper divisor of $p$, as follows. Let $p_{a}$ be the index of the subgroup
$\xi(a,a)$ in $\mathbb{Z}/p\mathbb{Z}$. Then the projection from $\mathbb{Z}$
to $\mathbb{Z}/p_{a}\mathbb{Z}$ factors to define the surjective homomorphism
$\rho_{a}:\mathbb{Z}/p\mathbb{Z}\to\mathbb{Z}/p_{a}\mathbb{Z}$ with kernel
$\xi(a,a)$. Thus the period of the component is the index $p_{a}$.

We can now construct a relation $\tilde{R}_{\xi}$ in canonical form. Define

(8)
$\begin{split}\tilde{X}_{\xi}=\bigcup_{a\in\overline{X}}&\\{a\\}\times\mathbb{Z}/p_{a}\mathbb{Z}.\hskip
56.9055pt\\\
\rho:\overline{X}\times\mathbb{Z}/p\mathbb{Z}\to\tilde{X}_{\xi}&\text{ with
$\rho(a,t)=(a,\rho_{a}(t))$.}\\\
\tilde{R}_{\xi}=&\rho\circ\overline{R}_{\xi}\circ\rho^{-1}.\hskip
71.13188pt\end{split}$

######  Theorem 3.5.

If $\xi$ is an irreducible cocycle, then $\tilde{R}_{\xi}$ is a canonical
relation on $\tilde{X}_{\xi}$ with $\tilde{R}_{\xi}^{p+i}=\tilde{R}_{\xi}^{i}$
for $i\geq 1$ and with period $p$.

###### Proof.

The strongly connected components are of the form
$\\{a\\}\times\mathbb{Z}/p_{a}\mathbb{Z}$ for ${a\in\overline{X}}$. By
Proposition 3.4 and Lemma 3.2, the restriction of $\tilde{R}_{\xi}$ to
$\\{a\\}\times\mathbb{Z}/p_{a}\mathbb{Z}$ is cyclic of period $p_{a}$.
$\tilde{R}_{\xi}^{i}=(\rho\circ\overline{R}_{\xi}\circ\rho^{-1})^{i}=\rho\overline{R}_{\xi}^{i}\rho^{-1}$,
again by Lemma 3.2, and so $\tilde{R}_{\xi}^{p+i}=\tilde{R}_{\xi}^{i}$ by
Proposition 3.4.

Because the period is $p_{a}$ on the strongly connected component
$\\{a\\}\times\mathbb{Z}/p_{a}\mathbb{Z}$, it follows from Lemma 2.7 that the
period equals the lcm of the $p_{a}$’s. This equals $p$ because $\xi$ is
irreducible. ∎

Observe that if $\xi$ is reducible, $\tilde{R}_{\xi}$ is still a canonical
relation on $\tilde{X}_{\xi}$ but with period $p_{*}$ the index of the
subgroup $\zeta\subseteq\mathbb{Z}/p\mathbb{Z}$. Furthermore, if
$\xi^{*}:R_{\geq}\to\mathcal{L}_{p^{*}}$ is the irreducible quotient
constructed above, it is easy to check that the two cocycles yield same
canonical relation on $\tilde{X}_{\xi}$.

######  Example 3.6.

Let $\overline{X}=\\{a,b\\}$, with $a\geq b$, and let $p=6$. If
$\xi(a,a)=\xi(a,b)=\xi(b,b)=\\{0\\}$, then
$\tilde{X}_{\xi}=\overline{X}\times\mathbb{Z}/6\mathbb{Z}$ and
$\tilde{R}_{\xi}=\overline{R}_{\xi}=R_{\geq}\times\tau_{6}$. This is the
simplest case.

######  Example 3.7.

Again, let $\overline{X}=\\{a,b\\}$, with $a\geq b$, and let $p=6$. If
$\xi^{\prime}(a,a)=\\{0,2,4\\}$ and $\xi^{\prime}(b,b)=\\{0\\}$, then
$q_{a}=2$, and
$\tilde{X}_{\xi^{\prime}}=(\\{a\\}\times\mathbb{Z}/2\mathbb{Z})\cup(\\{b\\}\times\mathbb{Z}/6\mathbb{Z})$.
If $\xi^{\prime}(a,b)=\\{1,3,5\\}$, then
$\tilde{R}_{\xi^{\prime}}(a,0)=\\{(a,1)\\}\cup\\{b\\}\times\\{0,2,4\\}$ and
$\tilde{R}_{\xi^{\prime}}(a,1)=\\{(a,0)\\}\cup\\{b\\}\times\\{1,3,5\\}$.

######  Example 3.8.

Now let $\overline{X}=\\{a,b\\}$, with $a\geq b$, and let $p=2$. If
$\xi(a,a)=\xi(a,b)=\xi(b,b)=\\{0\\}$, then again we get the simplest case,
$\tilde{X}_{\xi}=\overline{X}\times\mathbb{Z}/2\mathbb{Z}$ and
$\tilde{R}_{\xi}=\overline{R}_{\xi}=R_{\geq}\times\tau_{2}$. If instead we
have $\xi^{\prime}(a,b)=\\{1\\}$ and
$\xi^{\prime}(a,a)=\xi^{\prime}(b,b)=\\{0\\}$, then
$\tilde{R}_{\xi^{\prime}}(a,0)=\\{(a,1)\\}\cup\\{(b,0)\\}$ and
$\tilde{R}_{\xi^{\prime}}(a,1)=\\{(a,0)\\}\cup\\{(b,1)\\}$. Note that
$(\tilde{X}_{\xi},\tilde{R}_{\xi})$ and
$(\tilde{X}_{\xi^{\prime}},\tilde{R}_{\xi^{\prime}})$ are isomorphic via the
bijection that interchanges $(b,0)$ and $(b,1)$.

So, given a partial order, a period, and a cocycle, we can construct a
relation in canonical form. Next, given a relation in canonical form, from
which we obtain a partial order, period, and cocycle, we show that the
relation constructed as above is isomorphic to the original.

Let $(X,R)$ be a relation in canonical form so that $R$ has a period $p$. Let
$\pi:X\to\overline{X}$ be the projection to the set of strongly connected
components; then $R_{\geq}=\pi\circ R\circ\pi^{-1}$ is the induced partial
order on $\overline{X}$.

Since $R$ is in canonical form, the restriction of $R$ to the strongly
connected components is a bijection; denote this bijection by $f:X\to X$.

######  Lemma 3.9.

The bijection $f$ is an isomorphism from $(X,R)$ to itself, i.e. $(x,y)\in R$
if and only if $(f(x),f(y))\in R$. So for all $i\in\mathbb{N}$

(9) $f\circ R^{i}=R^{i}\circ f=R^{i+1}.$

###### Proof.

Observe that $x=f^{p}(x)\in R^{p-1}(f(x))$ and so if $y\in R(x)$, then $y\in
R^{p}(f(x))$ and $f(y)\in R^{p+1}(f(x))=R(f(x))$. Conversely, if $f(y)\in
R(f(x))$, then $y\in R^{p-1}(f(y))\subset R^{p}(f(x))\subset R^{p+1}(x)=R(x)$.

It immediately follows that $f\circ R^{i}=R^{i}\circ f\subseteq R^{i+1}$. If
$y\in R^{i+1}(x)$, then $f^{p-1}(y)\in R^{p+i}(x)=R^{i}(x)$ and so
$y=f^{p}(y)\in f\circ R^{i}(x)$.

∎

Let $s:\overline{X}\to X$ be a section, that is, a map such that $\pi\circ
s=id_{\overline{X}}$. For $a\in\overline{X}$, $s(a)$ is a point in $X$ such
that $[s(a)]_{R}=a$, that is, $a$ is the strongly connected component
containing $s(a)$, so a section is a choice function for the set
$\overline{X}$ of equivalence classes. For $(a,b)\in R_{\geq}$, define

(10) $\xi(a,b)=\\{i:f^{i}(s(b))\in R^{p}(s(a))\\}.$

######  Theorem 3.10.

Let $(X,R)$ be a relation in canonical form. If $p$, $R_{\geq}$, and $\xi$ are
as above, then $\xi$ is an irreducible cocylcle and $(X,R)$ is isomorphic to
$(\tilde{X}_{\xi},\tilde{R}_{\xi})$.

###### Proof.

It follows from Lemma 3.9 that $\xi$ is a cocycle.

Define the map $\bar{m}:\overline{X}\times\mathbb{Z}/p\mathbb{Z}\to X$ by
$\bar{m}(a,t)=f^{t}(s(a))$, where $s\colon\overline{X}\to X$ is a section
given by $\xi$. Since $f$ has period $p$, $f^{t}(s(a))$ depends only on $t\mod
p$ and so $f^{t}$, and hence $\bar{m}$, are well defined. We show that
$\bar{m}\circ\overline{R}_{\xi}=R\circ\bar{m}$, that is, $\bar{m}$ is a
morphism from $(\overline{X}\times\mathbb{Z}/p\mathbb{Z},\overline{R}_{\xi})$
to $(X,R)$:

(11) $\begin{split}(\bar{m}\circ\overline{R}_{\xi})(a,t)=\bar{m}(\\{(b,r):b\in
R_{\geq}(a),r-t-1\in\xi(a,b)\\})\\\ =\\{f^{r}(s(b)):b\in
R_{\geq}(a),r-t-1\in\xi(a,b)\\}\hskip 56.9055pt\\\
=R(f^{t}(s(a)))=(R\circ\bar{m})(a,t),\hskip 85.35826pt\end{split}$

because $f^{r-t-1}(s(b))\in R^{p}(s(a))$ if and only if $f^{r}(s(b))\in
R^{p}(f^{t+1}(s(a))=R^{p+1}((f^{t}(s(a)))=R(f^{t}(s(a)))$ by Lemma 3.9 again.

By Lemma 3.2, $\bar{m}$ factors to define a morphism $m:\tilde{X}_{\xi}\to X$.
The morphism $m$ is clearly surjective, and it is injective: if
$\bar{m}(a,t)=\bar{m}(a^{\prime},t^{\prime})$, then $a=a^{\prime}$ and
$f^{t}(s(a))=f^{t^{\prime}}(s(a))$, so that $t-t^{\prime}\in\xi(a,a)$. Thus
$m$ is an isomorphism $(\tilde{X}_{\xi},\tilde{R}_{\xi})\to(X,R)$.

Because $p$ is the period of $R$, Lemma 2.7 implies that $p$ the lcm of the
orders $p_{a}$ of the strongly connected components. It follows that the
cocycle is irreducible. ∎

However, the cocycle $\xi$ in Theorem 3.10 depends on the choice of section.

######  Example 3.11.

We refer back to Example 3.8. If we choose the section $s$ such that
$m^{-1}(s(a))=(a,0)$ and $m^{-1}(s(b))=(b,0)$, then we get the cocycle $\xi$.
However, if we choose the section $s^{\prime}$ such that
$m^{-1}(s^{\prime}(a))=(a,0)$ and $m^{-1}(s^{\prime}(b))=(b,1)$, then we get
the cocycle $\xi^{\prime}$.

Note that although the two sections give two different cocycles, the resulting
relations are isomorphic. Thus we need to find an invariant that does not
depend on the choice of section.

Let $\pi_{1}:(\tilde{X}_{\xi},\tilde{R}_{\xi})\to(\overline{X},R_{\geq})$ be
the projection.

######  Definition 3.12.

If $\theta:\overline{X}\to\mathbb{Z}/p\mathbb{Z}$ is an arbitrary map, then
$\eta(a,b)=\\{\theta(b)-\theta(a)\\}$ is a cocycle which we call a
_coboundary_. We say that two cocycles are _cohomologous_ if they differ by a
coboundary.

Observe that if $\xi$ and $\xi^{\prime}$ are cohomologous, then the subgroups
$\xi(a,a)=\xi^{\prime}(a,a)$ for all $a\in\overline{X}$. Hence, $\xi$ is
irreducible if and only if $\xi^{\prime}$ is. That is, irreducibility is a
property of the cohomology class.

######  Theorem 3.13.

For cocycles $\xi$ and $\xi^{\prime}$, there exists an isomorphism
$g:(\tilde{X}_{\xi},\tilde{R}_{\xi})\to(\tilde{X}_{\xi^{\prime}},\tilde{R}_{\xi^{\prime}})$
with $\pi_{1}\circ g=\pi_{1}$ if and only if $\xi$ and $\xi^{\prime}$ are
cohomologous.

###### Proof.

First, assume that they are cohomologous:
$\xi^{\prime}(a,b)=\xi(a,b)+\\{\theta(b)-\theta(a)\\}$ for some $\theta$. Then
the map $m_{\theta}(a,t):=(a,t+\rho_{a}(\theta(a))$ is an isomorphism
$(\tilde{X}_{\xi},\tilde{R}_{\xi})\to(\tilde{X}_{\xi^{\prime}},\tilde{R}_{\xi^{\prime}})$,
since $\tilde{X}_{\xi}$ and $\tilde{X}_{\xi^{\prime}}$ are identical,
$m_{\theta}\circ\tilde{R}_{\xi}=\tilde{R}_{\xi^{\prime}}\circ m_{\theta}$, and
$m_{\theta}$ has inverse $m_{-\theta}$.

Next, assume that the isomorphism $g$ exists, and choose $\theta(a)$ so that
$g(a,0)=(a,\rho_{a}(\theta(a)))$. Then
$g(a,\rho_{a}(t))=(a,\rho_{a}(t+\theta(a)))$ and
$g(b,\rho_{b}(t+i))=(b,\rho_{b}(t+\theta(b)+i))$. For $(a,b)\in R_{\geq}$,

$\displaystyle((a,\rho_{a}(t)),(b,\rho_{b}(t+i+1)))\in\tilde{R}_{\xi}\ $
$\displaystyle\Longleftrightarrow\ i\in\ \xi(a,b)$
$\displaystyle((a,\rho_{a}(s)),(b,\rho_{b}(t+j+1)))\in\tilde{R}_{\xi^{\prime}}\
$ $\displaystyle\Longleftrightarrow\ j+t-s\in\ \xi^{\prime}(a,b).$

Since $(g(a,\rho_{a}(t)),g(b,\rho_{b}(t+i+1)))$ is in
$\tilde{R}_{\xi^{\prime}}$ if and only if
$((a,\rho_{a}(t)),(b,\rho_{b}(t+i+1)))$ is in $\tilde{R}_{\xi}$, it follows
that $i+\theta(b)-\theta(a)\in\xi^{\prime}$. if and only if $i\in\xi(a,b)$.
Thus, $\xi$ and $\xi^{\prime}$ are cohomologous. ∎

######  Example 3.14.

We refer again to Examples 3.8 and 3.11. Observe that if we set $\theta(a)=0$
and $\theta(b)=1$, then
$\xi^{\prime}(a,b)=\xi(a,b)+\\{\theta(b)-\theta(a)\\}$, that is, $\xi$ and
$\xi^{\prime}$ are cohomologous.

We denote the cohomology class of $\xi$ by $[\xi]$.

######  Theorem 3.15.

For a finite relation in canonical form $(X,R)$, the triple
$(R_{\geq},p,[\xi])$ provides a complete invariant of shift equivalence (and
thus of Szymczak isomorphism class), consisting of the quotient partial order
$(\overline{X},R_{\geq})$, the period $p>0$ and $[\xi]$, the irreducible
cohomology class associated with any section $s:\overline{X}\to X$.

###### Proof.

By Theorem 2.4, two finite relations in canonical form are shift equivalent if
and only if they are isomorphic, and the triple determines the isomorphism
class by Theorem 3.10. To see that the triple is an invariant, let
$h:(X,R)\to(X^{\prime},R^{\prime})$ be an isomorphism of finite relations in
canonical form. Since $y\in R(x)$ if and only if $h(y)\in R^{\prime}(h(x))$,
$h$ preserves the partial order $(\overline{X},R_{\geq})$ and the period $p$.
Choose sections $s:\overline{X}\to X$ and $s^{\prime}:\overline{X}\to
X^{\prime}$, which induce cocycles $\xi$ and $\xi^{\prime}$ respectively. By
Theorem 3.10, $(X,R)$ is isomorphic to $(\tilde{X}_{\xi},\tilde{R}_{\xi})$ and
$(X^{\prime},R^{\prime})$ is isomorphic to
$(\tilde{X}_{\xi^{\prime}},\tilde{R}_{\xi^{\prime}})$, so
$(\tilde{X}_{\xi},\tilde{R}_{\xi})$ is isomorphic to
$(\tilde{X}_{\xi^{\prime}},\tilde{R}_{\xi^{\prime}})$ and
$[\xi]=[\xi^{\prime}]$ by Theorem 3.13. ∎

######  Corollary 3.16.

For any finite relation, the triple $(R_{\geq},p,[\xi])$ provides a complete
invariant of shift equivalence, where the triple is associated to any relation
in canonical form shift equivalent to the original.

###### Proof.

This follows from Theorems 2.4 and 3.15. ∎

For a general relation $R$ on $X$ we obtain the invariant via the following
steps:

  1. (1)

Let $i,j\in\mathbb{N}$ such that $R^{i}=R^{i+j}$ is the first repeat in the
sequence $\\{R^{n}\\}$. Let $q=nj$, the smallest multiple of $j$ so that
$nj\geq i$. So $q$ is an eventual period. In particular, $R^{q+q}=R^{q}$.

  2. (2)

Let $p$ be the smallest element of $\mathbb{N}$ such that $R^{q+p}=R^{q}$. So
$p$ is the period and $p$ divides $q$.

  3. (3)

Let $X_{R}=\\{x\in X:x\in R^{q}(x)\\}=\\{x\in X:x\to_{R}x\\}$. So $X_{R}$ is
the set of recurrent points.

  4. (4)

Let $\overline{X}$ be the set of $\leftrightarrow_{R}$ equivalence classes of
elements of $X_{R}$ and $\pi:X_{R}\to\overline{X}$ be the projection. So for
$x\in X_{R}$, $\pi(x)=[x]_{R}$ is the equivalence class containing $x$. On
$\overline{X}$ the relation $\to_{R}$ induces the partial order $R_{\geq}$ on
$\overline{X}$.

  5. (5)

Choose a section $\sigma:\overline{X}\to X_{R}$ for the map $\pi$ so that for
$a\in\overline{X}$, $\sigma(a)\in X_{R}$ with $[\sigma(a)]_{R}=a$.

  6. (6)

Define the irreducible cocycle $\xi:R_{\geq}\to\mathcal{L}_{p}$ by

(12) $\xi(a,b)=\\{i:[\sigma(b)]_{R}\cap R^{q+i}(\sigma(b))\cap
R^{q}(\sigma(a))\not=\emptyset\\}.$

That is, $i\in\xi(a,b)$ when there exists $w\leftrightarrow_{R}\sigma(b)$ with
$w\in R^{q+i}(\sigma(b))\cap R^{q}(\sigma(a))$.

Observe that if $s(a)$ is the $\equiv_{R}$ equivalence class of $\sigma(a)$
and $\hat{R}$ is the relation induced by $R^{q+1}$ on the set of $\equiv_{R}$
classes, then the above condition on $i$ says that
$f^{i}(s(b))\in\hat{R}^{p}(s(a))$. Compare equation (10).

  7. (7)

Thus, we have the triple consisting of the period $p$, the partial order
$R_{\geq}$ on $\overline{X}$, and the irreducible cocycle
$\xi:R_{\geq}\to\mathcal{L}_{p}$. This triple is the invariant for $(X,R)$.

### Acknowledgement

The research of MM was partially supported by Polish National Science Center
under Opus Grant 2019/35/B/ST1/00874 and the research cooperation was funded
in part by the program Excellence Initiative – Research University at the
Jagiellonian University in Kraków.

The research of MP was partially supported by Polish National Science Center
under Opus Grant 2019/35/B/ST1/00874.

## References

  * [1] Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the math- ematical sciences, Classics in Applied Mathematics, vol. 9, Society for In- dustrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. Revised reprint of the 1979 original. MR1298430
  * [2] John Franks and David Richeson, Shift equivalence and the Conley index, Trans. Amer. Math. Soc. 352 (2000), no. 7, 33053322. MR1665329
  * [3] K. H. Kim and F. W. Roush, Some results on decidability of shift equivalence, J. Combin. Inform. System Sci. 4 (1979), no. 2, 123146. MR564188
  * [4] by same author, On strong shift equivalence over a Boolean semiring, Ergodic Theory Dynam. Systems 6 (1986), no. 1, 8197. MR837977
  * [5] by same author, Williams’s conjecture is false for reducible subshifts, J. Amer. Math. Soc. 5 (1992), no. 1, 213215. MR1130528
  * [6] by same author, The Williams conjecture is false for irreducible subshifts, Electron. Res. Announc. Amer. Math. Soc. 3 (1997), 105109. MR1472090
  * [7] by same author,The Williams conjecture is false for irreducible subshifts, Ann. of Math. (2) 149 (1999), no. 2, 545558. MR1689340
  * [8] K. H. Kim, Boolean matrix theory and applications, Vol. 70., Marcel Dekker, Inc., New York, 1982. MR655414
  * [9] Douglas Lind and Brian Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. MR1369092
  * [10] M. Przybylski, M. Mrozek, and J. Wiseman, The Szymczak functor and shift equivalence on the category of finite sets and finite relations, J. Dyn. Diff. Equat. (2023).
  * [11] A. Szymczak, The Conley index for discrete dynamical systems, Topology and its Applications 66 (1995), 215240.