# Mutually orthogonal Sudoku Latin squares and their graphs

Sho Kubota Department of Applied Mathematics, Faculty of Engineering, Yokohama
National University, Yokohama, Kanagawa 240-8501, Japan. kubota-sho-
<EMAIL_ADDRESS>Sho Suda Department of Mathematics, National Defense Academy of
Japan, Yokosuka, Kanagawa 239-8686, Japan<EMAIL_ADDRESS>Akane Urano Konan
Highschool, Konan, Aichi 483-8177, Japan.

###### Abstract

We introduce a graph attached to mutually orthogonal Sudoku Latin squares. The
spectra of the graphs obtained from finite fields are explicitly determined.
As a corollary, we then use the eigenvalues to distinguish non-isomorphic
Sudoku Latin squares.

##  1 Introduction

A Latin square is an array of order $n$ with $n$ symbols such that each symbol
occurs exactly once in each row and column. Orthogonal Latin squares are a
pair of Latin squares of same order such that the superimposition of the same
entries of the Latin squares contains each ordered pair. Mutually orthogonal
Latin squares (MOLS) are a family of Latin squares such that any two of them
are orthogonal. One of the most important problem on the area of Latin squares
is to determine the maximum number $N(n)$ of Latin squares of order $n$ for
which they consist of mutually orthogonal Latin squares. It is easy to see
that the upper bound on $N(n)$ is at most $n-1$, and the upper bound is
achieved when $n$ is a prime power (see [4] for example). The converse is
conjectured, that is, if $N(n)=n-1$, then is $n$ a prime power?

In the last decades, Sudoku Latin squares have been investigated in the
literature. A Sudoku Latin square is a Latin square of order $n^{2}$ such that
the array is divided into $n^{2}$ $n\times n$ subarrays such that each symbol
occurs exactly once in each subarray. Mutually orthogonal Sudoku Latin squares
(MOSLS) have been investigated in the topics such as the upper bounds and
maximal examples obtained from finite fields [1, 6], non-extendible examples
[3].

In this paper, we consider a slightly generalized case, which we call Sudoku
Latin square of order $qr$ of type $(q,r)$: Latin squares of order $qr$
partitioned into $qr$ $q\times r$ subarrays such that each symbol occurs
exactly once in a subarray.

It is well-known that MOLS $L_{1},\ldots,L_{f}$ of order $n$ yield a strongly
regular graph, denoted $G_{[f],\text{MOLS}}$, with parameters
$(n^{2},(f+2)(n-1),n-2+f(f+1),(f+1)(f+2))$, see Section 2.2. In particular,
the spectra of the graph $G_{[f],\text{MOLS}}$ is uniquely determined by the
order and the number of Latin squares consisting of MOLS.

In this paper, we define a graph, denoted $G_{[f],\text{MOSLS}}$, attached to
MOSLS by adding edges corresponding to subarrays in Sudoku Latin squares to
the graph attached to MOLS. We are interested in the spectrum of the graph
$G_{[f],\text{MOSLS}}$. In contrary to the case of MOLS, the spectra are not
uniquely determined by the order and the number of Sudoku Latin squares
consisting of MOSLS in general. We explicitly determine the spectrum of the
graph of MOSLS with certain property which MOSLS obtained from finite fields
satisfy. Also we apply a cycle switching to a Sudoku Latin square obtained
from finite fields to obtain a new Sudoku Latin square with different spectra.
Thus we conclude that the new Sudoku Latin square is not equivalent to the old
one, and the spectra of the graphs obtained from a Sudoku Latin square can be
used to distinguish non-equivalent Sudoku Latin squares.

##  2 Preliminaries

###  2.1 Graphs

A graph $X$ consists of a vertex set $V(X)$ and an edge set $E(X)$, where
$E(X)\subset\binom{V(X)}{2}=\\{\\{x,y\\}\mid x,y\in V(X),x\neq y\\}$. The
adjacency matrix $A=A(X)$ of a graph $X$ is the integer matrix with rows and
columns indexed by $V(X)$ such that

$A_{x,y}=\begin{cases}1\quad&\text{if $\\{x,y\\}\in E(X)$,}\\\
0\quad&\text{otherwise.}\end{cases}$

The spectrum of a graph $X$, denoted by $\operatorname{Spec}(X)$ or
$\operatorname{Spec}(A(X))$, is the list of its eigenvalues of $A(X)$ together
with their multiplicities. Define $N_{X}(x)=\\{y\in V(X)\mid\\{x,y\\}\in
E(X)\\}$ for a vertex $x$ of a graph $X$. If there is no fear of confusion, we
simply write $N(x)$ instead of $N_{X}(x)$. A graph $X$ is said to be
$k$-regular if $|N(x)|=k$ for any $x\in V(X)$.

For example, we consider the graph $X$ defined by $V(X)=\\{1,2,3\\}$ and
$E(X)=\\{\\{1,2\\},\\{2,3\\}\\}$. The adjacency matrix is

$\begin{bmatrix}0&1&0\\\ 1&0&1\\\ 0&1&0\end{bmatrix},$

so the spectrum is
$\operatorname{Spec}(X)=\\{[\sqrt{2}]^{1},[0]^{1},[-\sqrt{2}]^{1}\\}$, where
the superscripts indicate the multiplicities of eigenvalues.

Let $X$ be a graph, and let $\pi=\\{C_{1},C_{2},\dots,C_{t}\\}$ be a partition
of $V(X)$. The partition $\pi$ is equitable if $|N(x)\cap C_{j}|$ is a
constant number, say $q_{i,j}$, for a vertex $x\in C_{i}$. Then, the matrix
$Q\in\mathbb{C}^{\pi\times\pi}$ defined by $Q_{i,j}=q_{i,j}$ is called the
quotient matrix with respect to $\pi$.

######  Lemma 2.1.

([2, Lemma 2.3.1]) Let $X$ be a graph with an equitable partition $\pi$, and
let $Q$ be the quotient matrix with respect to $\pi$. Then we have
$\operatorname{Spec}(Q)\subset\operatorname{Spec}(X)$.

Let $X$ be a regular graph such that $E(X)\neq\emptyset,\binom{V(X)}{2}$. Then
$X$ is said to be strongly regular with parameters $(n,k,\lambda,\mu)$ if
$|V(X)|=n$ and for any $x,y\in V(X)$,

$|N(x)\cap N(y)|=\begin{cases}k\quad&\text{if $x=y$,}\\\ \lambda\quad&\text{if
$\\{x,y\\}\in E(X)$,}\\\ \mu\quad&\text{if $\\{x,y\\}\not\in E(X)$ and $x\neq
y$.}\end{cases}$

######  Lemma 2.2.

([5, Chapter 10]) Let $X$ be a strongly regular graph with parameters
$(n,k,\lambda,\mu)$. Let $\Delta=(\lambda-\mu)^{2}+4(k-\mu)$. Then

$\operatorname{Spec}(X)=\left\\{[k]^{1},\left[\frac{\lambda-\mu+\sqrt{\Delta}}{2}\right]^{s},\left[\frac{\lambda-\mu-\sqrt{\Delta}}{2}\right]^{t}\right\\},$

where

$\displaystyle s$
$\displaystyle=\frac{1}{2}\left((n-1)-\frac{2k+(n-1)(\lambda-\mu)}{\sqrt{\Delta}}\right),$
$\displaystyle t$
$\displaystyle=\frac{1}{2}\left((n-1)+\frac{2k+(n-1)(\lambda-\mu)}{\sqrt{\Delta}}\right).$

###  2.2 Mutually orthogonal Latin squares and their graphs

For a positive integer $n$, set $[n]=\\{1,2,\ldots,n\\}$. A Latin square of
order $n$ on $[n]$ is an $n\times n$ array with entries in the set $[n]$ of
symbols $1,2,\ldots,n$ such that each row and each column contain every symbol
exactly once. Two Latin squares $L_{1},L_{2}$ of order $n$ on $[n]$ are said
to be orthogonal if the ordered pairs $(L_{1}(i,j),L_{2}(i,j))$ ($i,j\in[n]$)
are distinct where $L(i,j)$ denotes the $(i,j)$-entry of an array $L$. Latin
squares $\\{L_{1},L_{2},\ldots,L_{f}\\}$ are said to be mutually orthogonal if
any two distinct Latin squares of them are orthogonal.

######  Example 2.3.

The following are an example of orthogonal Latin squares of order $4$:

$L_{1}=\begin{array}[]{|c|c|c|c|}\hline\cr 1&2&4&3\\\ \hline\cr 3&4&2&1\\\
\hline\cr 4&3&1&2\\\ \hline\cr 2&1&3&4\\\ \hline\cr\end{array},\quad
L_{2}=\begin{array}[]{|c|c|c|c|}\hline\cr 1&4&3&2\\\ \hline\cr 3&2&1&4\\\
\hline\cr 4&1&2&3\\\ \hline\cr 2&3&4&1\\\ \hline\cr\end{array}.$

Let $L_{k}$ ($k\in[f]$) be mutually orthogonal Latin squares of order $n$ on
the set $[n]$ of symbols $1,2,\ldots,n$. For a subset $F$ of $[f]$, consider
the set

$C_{F}=\\{(i,j,L_{k}(i,j))_{k\in F}\mid 1\leq i,j\leq n\\},$

where $L_{k}(i,j)$ denotes the $(i,j)$-entry of $L_{k}$. Regard the set
$C_{F}$ as a subset of $[n]^{|F|+2}$ and consider the graph
$G_{F,\text{MOLS}}=(C_{F},E)$ where

$E_{F,\text{MOLS}}=\\{\\{x,y\\}\mid x,y\in C_{F},d(x,y)=|F|+1\\}$

where $d(x,y)$ is the Hamming distance between $x$ and $y$. Write its
adjacency matrix as $A_{F,\text{MOLS}}$. When $F=\\{m\\}$, we denote by
$A_{m,\text{MOLS}}$ in stead of $A_{\\{m\\},\text{MOLS}}$.

######  Lemma 2.4.

([5, Theorem 10.4.2]) Let $L_{k}$ ($k\in[f]$) be mutually orthogonal Latin
squares of order $n$ on the set $[n]$ of symbols $1,2,\ldots,n$. Then the
graph $G_{[f],\text{MOLS}}$ is a strongly regular graph with parameters
$(n^{2},(f+2)(n-1),n-2+f(f+1),(f+1)(f+2))$.

##  3 Mutually orthogonal Sudoku Latin squares

###  3.1 Mutually orthogonal Sudoku Latin squares and some properties

For positive integers $m$ and $n$ with $m<n$, define
$[m,n]=\\{x\in\mathbb{Z}\mid m\leq x\leq n\\}$. A Latin square of order $qr$
is said to be a Sudoku Latin square of type $(q,r)$ if each submatrix of $L$
restricted the rows to $[(i-1)q+1,iq]$ and the columns to $[(j-1)r+1,jr]$,
called the $(i,j)$-block, for $i\in[q],j\in[r]$ contains every symbol exactly
once. When the order of a Sudoku Latin square is a square $q^{2}$ and we omit
its type, then it means that the type is $(q,q)$. Though Sudoku Latin squares
of types $(q,1)$ or $(1,r)$ are exactly the same as just Latin squares, the
cases of $q=1$ or $r=1$ are allowed. Define a row-block as the rows with
indices in $[(i-1)q+1,iq]$ for some $i$, and define a column-block similarly.

######  Example 3.1.

The following is an example of Sudoku Latin square of order $9$ of type
$(3,3)$:

$L=\begin{array}[]{Ic|c|cIc|c|cIc|c|cI}\hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 5&6&4\hfil\lx@intercol\vrule
width=2.0&8&9&7\hfil\lx@intercol\vrule width=2.0&2&3&1\hfil\lx@intercol\vrule
width=2.0\\\ \hline\cr width=2.0pt\lx@intercol\hfil
9&7&8\hfil\lx@intercol\vrule width=2.0&3&1&2\hfil\lx@intercol\vrule
width=2.0&6&4&5\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 1&2&3\hfil\lx@intercol\vrule
width=2.0&4&5&6\hfil\lx@intercol\vrule width=2.0&7&8&9\hfil\lx@intercol\vrule
width=2.0\\\ \hrule height=2.0pt\cr width=2.0pt\lx@intercol\hfil
3&1&2\hfil\lx@intercol\vrule width=2.0&6&4&5\hfil\lx@intercol\vrule
width=2.0&9&7&8\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 4&5&6\hfil\lx@intercol\vrule
width=2.0&7&8&9\hfil\lx@intercol\vrule width=2.0&1&2&3\hfil\lx@intercol\vrule
width=2.0\\\ \hline\cr width=2.0pt\lx@intercol\hfil
8&9&7\hfil\lx@intercol\vrule width=2.0&2&3&1\hfil\lx@intercol\vrule
width=2.0&5&6&4\hfil\lx@intercol\vrule width=2.0\\\ \hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 7&8&9\hfil\lx@intercol\vrule
width=2.0&1&2&3\hfil\lx@intercol\vrule width=2.0&4&5&6\hfil\lx@intercol\vrule
width=2.0\\\ \hline\cr width=2.0pt\lx@intercol\hfil
2&3&1\hfil\lx@intercol\vrule width=2.0&5&6&4\hfil\lx@intercol\vrule
width=2.0&8&9&7\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 6&4&5\hfil\lx@intercol\vrule
width=2.0&9&7&8\hfil\lx@intercol\vrule width=2.0&3&1&2\hfil\lx@intercol\vrule
width=2.0\\\ \hrule height=2.0pt\cr\end{array}.$

In the present paper, we focus on the following certain property of Sudoku
Latin squares. Let $B_{i,j}=\\{(a,b)\in\mathbb{N}^{2}\mid(i-1)q+1\leq a\leq
iq,(j-1)r+1\leq b\leq jr\\}$ for $i\in[r],j\in[q]$. For a Sudoku Latin square
$L$ order $qr$ of type $(q,r)$, we denote by $L[i,j]$ the subarray of $L$ with
rows and columns restricted to $B_{i,j}$. A Sudoku Latin square $L$ of order
$qr$ of type $(q,r)$ is said to be of block-permutational if for any $i,j$,
there exist permutation matrices $P,Q$ of order $q,r$ respectively such that
$L[i,j]=P^{-1}L[1,1]Q$ holds.

######  Lemma 3.2.

Let $M,M^{\prime}$ be $q\times r$ matrices with distinct entries in $[qr]$,
and $P,Q$ be permutation matrices of orders $q,r$, respectively. Let $A$ be a
$qr\times qr$ $(0,1)$-matrix with rows and columns indexed by $[q]\times[r]$
defined by $A_{(i,j),(i^{\prime},j^{\prime})}=1$ if and only if
$M_{i,j}=(M^{\prime})_{i^{\prime},j^{\prime}}$ Then
$M_{i,j}=(P^{-1}MQ)_{i^{\prime},j^{\prime}}$ holds if and only if $A=P\otimes
Q$ holds.

###### Proof.

Write $P=(\delta_{i,\sigma(j)})_{i,j=1}^{q}$ and
$Q=(\delta_{i,\tau(j)})_{i,j=1}^{r}$ for some permutations $\sigma$ on $[q]$
and $\tau$ on $[r]$.

$\displaystyle(P\otimes Q)_{(i,j),(i^{\prime},j^{\prime})}=1\Leftrightarrow
P_{i,i^{\prime}}=Q_{j,j^{\prime}}=1\Leftrightarrow
i=\sigma(i^{\prime}),j=\tau(j^{\prime}).$

Since the entries of $M$ are mutually distinct, this condition is equivalent
to the fact that $M_{i,j}=M_{\sigma(i^{\prime}),\tau(j^{\prime})}$, which is
equivalent to the fact that $M_{i,j}=(P^{-1}MQ)_{i^{\prime},j^{\prime}}$. ∎

###  3.2 Associated graphs and their adjacency matrices

In this subsection we define a graph from mutually orthogonal Sudoku Latin
squares.

Let $L_{k}$ ($k\in[f]$) be mutually orthogonal Sudoku Latin squares of order
$qr$ on the set $[q^{2}r^{2}]$ of the symbols $1,2,\ldots,q^{2}r^{2}$. For
$F\subset[f]$, consider the graph
$G_{F,\text{MOSLS}}=(C_{F},E_{F,\text{MOSLS}})$ with $E_{F,\text{MOSLS}}$
defined as

$\displaystyle E_{F,\text{MOSLS}}=$ $\displaystyle E_{F,\text{MOLS}}$
$\displaystyle\cup\\{(x_{1},x_{2}),(y_{1},y_{2})\\}\in\tbinom{C_{F}}{2}|(x_{1},x_{2}),(y_{1}y_{2})\in
B_{i,j}\text{ for some }i,j.\\}$

Write its adjacency matrix as $A_{F,\text{MOSLS}}$. When $F=\\{m\\}$, we
denote by $A_{m,\text{MOSLS}}$ in stead of $A_{\\{m\\},\text{MOSLS}}$.

######  Remark 3.3.

A Sudoku graph was defined in [7] as the vertex set equal to a set of cells of
the $n\times n$ grid and the edge set consisting of pairs $(x,y)$ where $x,y$
are in a same row, in a same column, or in a same block. The spectrum of the
Sudoku graph is explicitly determined.

It is easy to see that the spectra of graphs obtained from MOSLS of order $qr$
is invariant under the following symmetries:

  * •

relabeling the symbols $[qr]$,

  * •

permuting the row-blocks and the column-blocks, and the rows in a row-block
and the columns in a column-block,

  * •

any reflection or rotation type keeping the type.

Here we label the rows and columns of the matrix as follows. Define a map We
consider the bijection $[r]\times[q]\times[q]\times[r]$ to $[q^{2}r^{2}]$ by
$(i,j,k,\ell)\rightarrow qr((i-1)r+k-1)+(j-1)q+\ell$.

In this ordering of the rows and columns, set

$B=I_{rq}\otimes(J_{q}-I_{q})\otimes(J_{r}-I_{r}).$

Then the matrix $A_{F,\text{MOLS}}+B$ coincides with the adjacency matrix
$A_{F,\text{MOSLS}}$ of the graph of mutually orthogonal Sudoku Latin squares.
Set $I_{1}=\\{(i,j,k,\ell)\in[r]\times[q]\times[r]\times[q]\mid i\neq
k,j\neq\ell\\}$, $I_{2}=\\{(i,j,k,\ell)\in[r]\times[q]\times[r]\times[q]\mid
i=j\text{ and }k\neq\ell,\text{ or }i\neq j\text{ and }k=\ell\\}$. For each
$m\in F$, the following holds:

$\displaystyle A_{m,\text{MOLS}}$ $\displaystyle=\sum_{(i,j,k,\ell)\in
I_{1}}e_{\varphi(i,j),\varphi(k,\ell)}\otimes P_{m,(i,j),(k,\ell)}$
$\displaystyle\quad+\sum_{(i,j,k,\ell)\in
I_{2}}e_{\varphi(i,j),\varphi(k,\ell)}\otimes(I_{q}\otimes
J_{{r}}+P^{\prime}_{m,(i,j),(k,\ell)})$
$\displaystyle\quad+\sum_{i\in[r],j\in[q]}e_{\varphi(i,j),\varphi(i,j)}\otimes(I_{q}\otimes(J_{{r}}-I_{{r}})+(J_{q}-I_{q})\otimes
I_{{r}}),$

where $\varphi(a,b)=(a-1)q+b$ and $e_{i,j}$ is a square matrix of order $qr$
whose $(i,j)$-entry is $1$ and all other entries are $0$,
$P_{m,(i,j),(k,\ell)}$ is a permutation matrix of order $qr$, and
$P^{\prime}_{m,(i,j),(k,\ell)}$ is a permutation matrix of order $qr$ such
that $I_{q}\otimes J_{r}+P^{\prime}_{m,(i,j),(k,\ell)}$ is a $(0,1)$-matrix.

######  Lemma 3.4.

Let $L_{k}$ ($k\in[f]$) be mutually orthogonal Sudoku Latin squares of order
$qr$ of type $(q,r)$. The following is a subset of the spectrum of
$G_{[f],\text{MOSLS}}$:

$\displaystyle\\{[3qr-q-r-1+f(qr-1)]^{1},[2qr-q-r-1-f]^{q+r-2},[qr-
q-r-1-f]^{(q-1)(r-1)}\\}.$

###### Proof.

Recall that $B_{i,j}=\\{(a,b)\in\mathbb{N}^{2}\mid(i-1)q+1\leq a\leq
iq,(j-1)r+1\leq b\leq jr\\}$ for $i\in[r],j\in[q]$. The partition
$\\{B_{i,j}\mid i\in[r],j\in[q]\\}$ of $[qr]^{2}$ is an equitable partition.
The quotient matrix $Q$ of $A_{[f],\text{MOSLS}}$ with the ordering
$B_{1,1},B_{1,2},\ldots,B_{1,q},\ldots,B_{r,q}$ is

$\displaystyle Q$
$\displaystyle=(qr-1)I_{rq}+(r+f)I_{r}\otimes(J_{q}-I_{q})+(q+f)(J_{r}-I_{r})\otimes
I_{q}+f(J_{r}-I_{r})\otimes(J_{q}-I_{q})$ $\displaystyle=(qr-
q-r-1-f)I_{rq}+rI_{r}\otimes J_{q}+qJ_{r}\otimes I_{q}+fJ_{rq}.$

It is easy to see that the spectrum of $Q$ is

$\displaystyle\\{[3qr-q-r-1+f(qr-1)]^{1},[2qr-q-r-1-f]^{q+r-2},[qr-
q-r-1-f]^{(q-1)(r-1)}\\}.$

Therefore, $A_{[f],\text{MOSLS}}$ has the desired eigenvalues. ∎

The following lemma provides a sufficient condition for $A_{[f],\text{MOLS}}$
and $B$ to commute.

######  Lemma 3.5.

Assume that each matrix $A_{m,\text{MOSLS}}$ satisfies that
$P_{m,(i,j),(k,\ell)}=P_{m,1,i,j}\otimes P_{m,2,k,\ell}$ where $P_{m,1,i,j}$
and $P_{m,2,k,\ell}$ are permutation matrices, and
$P^{\prime}_{m,(i,j),(k,\ell)}=P^{\prime}_{m,1,i,j}\otimes
P^{\prime}_{m,2,k,\ell}$ where $P^{\prime}_{m,1,i,j}$ and
$P^{\prime}_{m,2,k,\ell}$ are permutation matrices and $P^{\prime}_{m,1,i,j}$
has $0$ on the diagonal entries. Then the matrices $A_{[f],\text{MOLS}}$ and
$B$ commute.

###### Proof.

Since

$\displaystyle A_{[f],\text{MOLS}}$
$\displaystyle=\sum_{m\in[f]}A_{m,\text{MOLS}}-(f-1)I_{rq}\otimes(I_{q}\otimes(J_{r}-I_{r})+(J_{q}-I_{q})\otimes
I_{r})$ $\displaystyle-(f-1)(J_{q}-I_{q})\otimes I_{r}\otimes I_{q}\otimes
J_{r},$

it is enough to verify that $A_{m,\text{MOLS}}$ and $B$ commute for each $m$.
To do this, by

$\displaystyle B=I_{qr}\otimes(I_{q}\otimes I_{r}-I_{q}\otimes
J_{r}-J_{q}\otimes I_{r}+J_{q}\otimes J_{r}),$

we show that $K\in\\{I_{q}\otimes J_{r},J_{q}\otimes I_{r}\\}$ and
$P_{m,(i,j),(k,\ell)}$ or $P^{\prime}_{m,(i,j),(k,\ell)}$ commute. Indeed,

$\displaystyle(I_{q}\otimes J_{r})P_{m,(i,j),(k,\ell)}$
$\displaystyle=(I_{q}\otimes J_{r})P_{m,(i,j),(k,\ell)}=(I_{q}\otimes
J_{r})(P_{m,1,i,j}\otimes P_{m,2,k,\ell})$ $\displaystyle=P_{m,1,i,j}\otimes
J_{r}P_{m,2,k,\ell}$ $\displaystyle=P_{m,1,i,j}\otimes J_{r}.$

In the same manner, we have $P_{m,(i,j),(k,\ell)}(I_{q}\otimes
J_{r})=P_{m,1,i,j}\otimes J_{r}$, and thus $(I_{q}\otimes
J_{r})P_{m,(i,j),(k,\ell)}=P_{m,(i,j),(k,\ell)}(I_{q}\otimes J_{r})$. Also,
the case $K=J_{q}\otimes I_{r}$ and $P_{m,(i,j),(k,\ell)}$ or
$P^{\prime}_{m,(i,j),(k,\ell)}$ are similarly proven. ∎

We then determine the spectrum of $A_{[f],\text{MOSLS}}$ under the assumption
that $A_{[f],\text{MOLS}}$ and $B$ commute.

######  Theorem 3.6.

Let $L_{k}$ ($k\in[f]$) be mutually orthogonal Sudoku Latin squares of order
$qr$ of type $(q,r)$ on the set $[qr]$ of symbols $1,2,\ldots,qr$. If
$A_{[f],\text{MOLS}}$ and $B$ commute, then the spectrum of
$A_{[f],\text{MOSLS}}$ is

$\displaystyle\\{$
$\displaystyle[(q-1)(r-1)+(qr-1)(f+2)]^{1},[(q-1)(r-1)+qr-2-f]^{q+r-2},$
$\displaystyle[(q-1)(r-1)-2-f]^{(q-1)(r-1)},$
$\displaystyle[qr-1-f]^{f(q-1)(r-1)},[qr-q-1-f]^{(r-1)(q+f)},[qr-r-1-f]^{(q-1)(r+f)},$
$\displaystyle[-1-f]^{(q-1)(r-1)(qr-f)},[-q-1-f]^{(r-1)(qr-
q-f)},[-r-1-f]^{(q-1)(qr-r-f)}\\}.$

###### Proof.

By Lemmas 2.2, 2.4, the spectrum of $A_{[f],\text{MOLS}}$ is

$\text{Spec}(A_{[f],\text{MOLS}})=\\{[(f+2)(qr-1)]^{1},[qr-f-2]^{(f+2)(qr-1)},[-f-2]^{(qr-f-1)(qr-1)}\\}.$

The spectrum of $B$ is easy to see that

$\text{Spec}(B)=\\{[(q-1)(r-1)]^{qr},[1]^{q(q-1)r(r-1)},[-q+1]^{qr(r-1)},[-r+1]^{q(q-1)r}\\}.$

Write $\text{Spec}(A_{[f],\text{MOLS}})=\\{[\theta_{i}]^{m_{i}}\mid
i=1,2,3\\}$ and $\text{Spec}(B)=\\{[b_{i}]^{n_{i}}\mid i=1,2,3,4\\}$ where
$\theta_{1}>\theta_{2}>\theta_{3}$ and $b_{1}>b_{2}>0,b_{3}=-q+1,b_{4}=-r+1$.
Note that $m_{1}=1$. Since $A_{[f],\text{MOLS}}$ and $B$ commute, we obtain

$\text{Spec}(A_{[f],\text{MOSLS}})=\\{[\theta_{i}+b_{j}]^{m_{i,j}}\mid
i\in\\{1,2,3\\},j\in\\{1,2,3,4\\}\\},$

for some non-negative integer $m_{i,j}$. We determine $m_{i,j}$ in the
following. Note that since $A_{[f],\text{MOLS}}$ and $B$ have the all ones
vector as an eigenvector, $m_{1,1}=1,m_{1,2}=m_{1,3}=m_{1,4}=0$.

Letting $\mathcal{E}(M,\theta)$ be the eigenspace of a real symmetric matrix
$M$ corresponding to the eigenvalue $\theta$, we have
$\sum_{i=1}^{3}\mathcal{E}(A_{[f],\text{MOLS}}+B,\theta_{i}+b_{j})=\mathcal{E}(B,b_{j})$
and
$\sum_{j=1}^{4}\mathcal{E}(A_{[f],\text{MOLS}}+B,\theta_{i}+b_{j})=\mathcal{E}(A_{[f],\text{MOLS}},\theta_{i})$.
Comparing the dimension, we have

$\displaystyle\sum_{i=1}^{3}m_{i,j}$ $\displaystyle=n_{j}\text{ for
}j\in\\{1,2,3,4\\},$ (1) $\displaystyle\sum_{j=1}^{4}m_{i,j}$
$\displaystyle=m_{i}\text{ for }i\in\\{1,2,3\\}.$ (2)

For $j=1$, Equation (1) with $m_{1,1}=1$ reads as $m_{2,1}+m_{3,1}=qr-1$.
Lemma 3.4 shows that $m_{2,1}\geq q+r-2$ and $m_{3,1}\geq(q-1)(r-1)$.
Therefore $m_{2,1}=q+r-2$ and $m_{3,1}=(q-1)(r-1)$. Since the graph with
adjacency matrix $A_{[f],\text{MOLS}}$ is $((f+2)(qr-1)+(q-1)(r-1))$-regular,

${\rm
tr}(A_{[f],\text{MOLS}}+B)^{2}=\sum_{i=1}^{3}\sum_{j=1}^{4}(\theta_{i}+b_{j})^{2}m_{i,j}=q^{2}r^{2}((f+2)(qr-1)+(q-1)(r-1)).$

Furthermore, it follows from counting the triangles that

  * •

the number of triangles with three edges corresponding to
$A_{[f],\text{MOLS}}$ is $q^{2}r^{2}(f+2)(qr-1)(qr-2+f(f+1))$,

  * •

the number of triangles with two edges corresponding to $A_{[f],\text{MOLS}}$
and one edge $B$ is $3(f+1)(f+2)(q-1)(r-1)q^{2}r^{2}$,

  * •

the number of triangles with one edge corresponding to $A_{[f],\text{MOLS}}$
and two edges $B$ is $3q^{2}r^{2}(q-1)(r-1)(q+r-4)$,

  * •

the number of triangles with three edges corresponding to $B$ is
$q^{2}(q-1)(q-2)r^{2}(r-1)(r-2)$.

Thus we have

$\displaystyle{\rm tr}(A_{[f],\text{MOLS}}+B)^{3}$
$\displaystyle=\sum_{i=1}^{3}\sum_{j=1}^{4}(\theta_{i}+b_{j})^{3}m_{i,j}$
$\displaystyle=q^{2}r^{2}(f+2)(qr-1)(qr-2+f(f+1))+3(f+1)(f+2)q^{2}r^{2}(q-1)(r-1)$
$\displaystyle+3q^{2}r^{2}(q-1)(r-1)(q+r-4)+q^{2}(q-1)(q-2)r^{2}(r-1)(r-2).$

Solving Equations (1) and (2) with the above yields that

$\displaystyle m_{2,1}=q+r-2,m_{2,2}=f(q-1)(r-1),$ $\displaystyle
m_{2,3}=(r-1)(q+f),m_{2,4}=(q-1)(r+f),$ $\displaystyle
m_{3,1}=(q-1)(r-1),m_{3,2}=(q-1)(r-1)(qr-f),$ $\displaystyle m_{3,3}=(r-1)(qr-
q-f),m_{3,4}=(q-1)(qr-r-f).\qed$

######  Example 3.7.

The following are orthogonal Sudoku Latin squares of order $4$:

$L_{1}=\begin{array}[]{Ic|cIc|cI}\hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 1&2\hfil\lx@intercol\vrule
width=2.0&4&3\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 3&4\hfil\lx@intercol\vrule
width=2.0&2&1\hfil\lx@intercol\vrule width=2.0\\\ \hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 4&3\hfil\lx@intercol\vrule
width=2.0&1&2\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 2&1\hfil\lx@intercol\vrule
width=2.0&3&4\hfil\lx@intercol\vrule width=2.0\\\ \hrule
height=2.0pt\cr\end{array},\quad L_{2}=\begin{array}[]{Ic|cIc|cI}\hrule
height=2.0pt\cr width=2.0pt\lx@intercol\hfil 1&4\hfil\lx@intercol\vrule
width=2.0&3&2\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 3&2\hfil\lx@intercol\vrule
width=2.0&1&4\hfil\lx@intercol\vrule width=2.0\\\ \hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 4&1\hfil\lx@intercol\vrule
width=2.0&2&3\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 2&3\hfil\lx@intercol\vrule
width=2.0&4&1\hfil\lx@intercol\vrule width=2.0\\\ \hrule
height=2.0pt\cr\end{array}.$

The adjacency matrix $A_{[2],\text{MOSLS}}$ of the graph of orthogonal Sudoku
Latin squares $L_{1},L_{2}$ is

$\left(\begin{array}[]{cccccccccccccccc}0&1&1&1&1&1&1&1&1&1&1&1&1&0&0&1\\\
1&0&1&1&1&1&1&1&1&1&1&1&0&1&1&0\\\ 1&1&0&1&1&1&1&1&1&1&1&1&0&1&1&0\\\
1&1&1&0&1&1&1&1&1&1&1&1&1&0&0&1\\\ 1&1&1&1&0&1&1&1&1&0&0&1&1&1&1&1\\\
1&1&1&1&1&0&1&1&0&1&1&0&1&1&1&1\\\ 1&1&1&1&1&1&0&1&0&1&1&0&1&1&1&1\\\
1&1&1&1&1&1&1&0&1&0&0&1&1&1&1&1\\\ 1&1&1&1&1&0&0&1&0&1&1&1&1&1&1&1\\\
1&1&1&1&0&1&1&0&1&0&1&1&1&1&1&1\\\ 1&1&1&1&0&1&1&0&1&1&0&1&1&1&1&1\\\
1&1&1&1&1&0&0&1&1&1&1&0&1&1&1&1\\\ 1&0&0&1&1&1&1&1&1&1&1&1&0&1&1&1\\\
0&1&1&0&1&1&1&1&1&1&1&1&1&0&1&1\\\ 0&1&1&0&1&1&1&1&1&1&1&1&1&1&0&1\\\
1&0&0&1&1&1&1&1&1&1&1&1&1&1&1&0\\\ \end{array}\right).$

Then the spectrum of $A_{[2],\text{MOSLS}}$ is

$\displaystyle\text{Spec}(A_{[2],\text{MOSLS}})$
$\displaystyle=\\{[13]^{1},[1]^{4},[-1]^{8},[-3]^{3}\\}.$

######  Example 3.8.

The following is a Sudoku Latin squares of order $6$ of type $(2,3)$:

$L=\begin{array}[]{Ic|c|cIc|c|cI}\hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 1&2&3\hfil\lx@intercol\vrule
width=2.0&4&5&6\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 4&5&6\hfil\lx@intercol\vrule
width=2.0&1&2&3\hfil\lx@intercol\vrule width=2.0\\\ \hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 2&3&1\hfil\lx@intercol\vrule
width=2.0&5&6&4\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 5&6&4\hfil\lx@intercol\vrule
width=2.0&2&3&1\hfil\lx@intercol\vrule width=2.0\\\ \hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 3&1&2\hfil\lx@intercol\vrule
width=2.0&6&4&5\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 6&4&5\hfil\lx@intercol\vrule
width=2.0&3&1&2\hfil\lx@intercol\vrule width=2.0\\\ \hrule
height=2.0pt\cr\end{array}.$

Let $A$ be the adjacency matrix of the graph of the Sudoku Latin square $L$ of
order $6$. Then the spectrum of $A$ is

$\displaystyle\text{Spec}(A)$
$\displaystyle=\\{[17]^{1},[-5]^{2},[-4]^{6},[-2]^{10},[-1]^{2},[1]^{4},[2]^{6},[4]^{2},[5]^{3}\\}.$

##  4 Construction of mutually orthogonal Sudoku Latin squares

###  4.1 Using finite fields

Let $p$ be a prime number, $m,n$ positive integers and set $q=p^{m},r=p^{n}$.
Let $f(t)$ be a irreducible polynomial of degree $m+n$ over $\mathbb{Z}_{p}$
and $\mathbb{F}_{qr}=\mathbb{Z}_{p}[t]/(f(t))$ be the finite field of $qr$
elements.

For $a\in\mathbb{F}_{qr}$, define $L_{a}=(x-ay)_{x,y\in\mathbb{F}_{qr}}$. It
is well-known that $L_{a}$ ($a\in\mathbb{F}_{qr}\setminus\\{0\\}$) form
mutually orthogonal Latin squares of order $qr$.

Write

$\displaystyle\left\\{\sum_{i=n}^{m+n-1}a_{i}t^{i}\mid
a_{i}\in\mathbb{Z}_{p}\right\\}=\\{f_{1}(t)=0,f_{2}(t),\ldots,f_{r}(t)\\},$
$\displaystyle\left\\{\sum_{i=m}^{m+n-1}a_{i}t^{i}\mid
a_{i}\in\mathbb{Z}_{p}\right\\}=\\{g_{1}(t)=0,g_{2}(t),\ldots,g_{q}(t)\\}.$

Set

$\displaystyle X_{k}$
$\displaystyle=\left\\{f_{k}(t)+\sum_{i=0}^{n-1}a_{i}t^{i}\mid
a_{i}\in\mathbb{Z}_{p}\right\\},$ $\displaystyle Y_{\ell}$
$\displaystyle=\left\\{g_{\ell}(t)+\sum_{i=0}^{m-1}a_{i}t^{i}\mid
a_{i}\in\mathbb{Z}_{p}\right\\},$

for $k\in\\{1,2,\ldots,r\\}$ and for $\ell\in\\{1,2,\ldots,q\\}$. We regard
$L_{a}$ as a block matrix with rows according to the partition
$\mathbb{F}_{qr}=X_{1}\cup\cdots\cup X_{r}$ and the columns according to the
partition $\mathbb{F}_{qr}=Y_{1}\cup\cdots\cup Y_{q}$.

######  Lemma 4.1.

If $a$ is a polynomial of degree $n$, then $L_{a}$ is a Sudoku Latin square.

###### Proof.

Consider a block corresponding to $X_{k}\times Y_{\ell}$ for
$k,\ell\in\\{1,\ldots,r\\},\ell\in\\{1,\ldots,q\\}$. Let $x,x^{\prime}\in
X_{k},y,y^{\prime}\in Y_{\ell}$. Assume that the $(x,y)$-entry equals to the
$(x^{\prime},y^{\prime})$-entry. By definition, $x-ay=x^{\prime}-ay^{\prime}$,
and thus $x-x^{\prime}=a(y-y^{\prime})$ holds. On the one hand $x-x^{\prime}$
is a polynomial of degree at most $n-1$ in $t$, and on the other hand
$a(y-y^{\prime})$ is a polynomial of degree at least $n$ in $t$ provided that
$y\neq y^{\prime}$. Therefore $y=y^{\prime}$ holds, and thus $x=x^{\prime}$
follows. Therefore, all the entries of the block are different. ∎

Thus we have the following result: For any prime powers $q=p^{m},r=p^{n}$,
there exist $\max(p^{m}(p-1),p^{n}(p-1))$ mutually orthogonal Sudoku Latin
squares of order $qr$ of type $(q,r)$. We then claim the resulting mutually
orthogonal Sudoku Latin squares are block permutational, that is, satisfy the
assumption of Lemma 3.5. For this, we need the following lemmas.

######  Lemma 4.2.

Let $a$ be a polynomial of degree $n$. For
$(i,j),(i^{\prime},j^{\prime})\in[r]\times[q]$, the $(i,j)$-block $L[i,j]$ and
$(i^{\prime},j^{\prime})$-block $L[i^{\prime},j^{\prime}]$ of $L_{a}$ satisfy
that $L[i,j]=P^{-1}L[i^{\prime},j^{\prime}]Q$ for some permutation matrices
$P,Q$.

###### Proof.

There uniquely exist $A,B\in\\{\sum_{i=0}^{n-1}a_{i}t^{i}\mid
a_{i}\in\mathbb{Z}_{p}\\}$ such that

$A-aB=(f_{i}-f_{i^{\prime}})-a(g_{j}-g_{j^{\prime}}).$

Define bijections $\sigma,\tau$ on $[q]$ as

$f_{\sigma(\alpha)}=f_{\alpha}+A,g_{\tau(\beta)}=g_{\beta}+B.$

for $\alpha\in\\{1,2,\ldots,r\\},\beta\in\\{1,2,\ldots,q\\}$. Define
$P=(\delta_{i,\sigma(j)})_{i,j=1}^{{r}},Q=(\delta_{i,\tau(j)})_{i,j=1}^{q}$
Then it is readily shown that

$(f_{i}+g_{\alpha})-a(f_{j}+g_{\beta})=(f_{i^{\prime}}+g_{\sigma(\alpha)})-a(f_{j^{\prime}}+g_{\tau(\beta)}),$

which implies that
$(L[i,j])_{\alpha,\beta}=(L[i^{\prime},j^{\prime}])_{\sigma(\alpha),\tau(\beta)}=(P^{-1}L[i^{\prime},j^{\prime}]Q)_{\alpha,\beta}$.
∎

Then by considering the transpose of Latin squares, the following theorem is
obtained from Lemmas 4.2, 3.2.

######  Theorem 4.3.

Let $p$ be a prime and $m,n$ positive integers, and set $q=p^{m},r=p^{n}$, and
$\ell=\max\\{p^{m}(p-1),p^{n}(p-1)\\}$. Then there exist mutually orthogonal
Sudoku Latin squares $L_{1},\ldots,L_{\ell}$ of order $qr$ of type $(q,r)$
which are of block permutational.

###  4.2 A recursive construction

A recursive construction for mutually orthogonal Sudoku Latins squares is
established. The type $(q,r)$ for seed Sudoku Latin squares are allowed the
cases $(q,1)$ or $(1,r)$.

######  Theorem 4.4.

Assume that for $i=1,2$, there exist orthogonal Sudoku Latin squares of order
$q_{i}r_{i}$ of type $(q_{i},r_{i})$ such that each satisfies the assumption
of Theorem 3.6. Then there exists orthogonal Sudoku Latin squares of order
$q_{1}q_{2}r_{1}r_{2}$ of type $(q_{1}q_{2},r_{1}r_{2})$ which are of block
permutational.

###### Proof.

Let $L_{1}^{(i)},L_{2}^{(i)}$ be such Sudoku Latin squares of order
$q_{i}r_{i}$ of type $(q_{i},r_{i})$ for $i=1,2$. Assume that the rows and the
columns of $L_{1}^{(i)},L_{2}^{(i)}$ are decomposed into
$X_{1}^{(i)},\ldots,X_{r_{i}}^{(i)}$ and $Y_{1}^{(i)},\ldots,Y_{q_{i}}^{(i)}$,
respectively. It is easy to see that

$M_{i}:=(((L_{i}^{(1)})_{x_{1},y_{1}},(L_{i}^{(2)})_{x_{2},y_{2}}))_{(x_{1},x_{2}),(y_{1},y_{2})\in[q_{1}r_{1}]\times[q_{2}r_{2}]}\quad(i=1,2)$

are orthogonal Latin squares of order $q_{1}q_{2}r_{1}r_{2}$. We then show
that each $M_{i}$ is a Sudoku of type $(q_{1}q_{2},r_{1}r_{2})$ satisfying the
assumption of Theorem 3.6. Note that the indices of blocks are
$(i_{1},i_{2})$, $i_{1}\in[r_{1}],i_{2}\in[r_{2}]$, for the rows and
$(j_{1},j_{2})$, $j_{1}\in[q_{1}],j_{2}\in[q_{2}]$, for the columns.

First, the entries of $M_{i}$ on the rows in $X_{i_{1}}^{(1)}\times
X_{i_{2}}^{(2)}$ where $i_{1},i_{2}\in[r_{1}]$ and on the columns in
$Y_{j_{1}}^{(1)}\times Y_{j_{2}}^{(2)}$ where $j_{1},j_{2}\in[q_{1}]$ are

$((L_{i}^{(1)})_{x_{1},y_{1}},(L_{i}^{(2)})_{x_{2},y_{2}})$

where $(x_{1},x_{2})\in X_{i_{1}}^{(1)}\times X_{i_{2}}^{(2)},(y_{1},y_{2})\in
Y_{j_{1}}^{(1)}\times Y_{j_{2}}^{(2)}$. Then $(x_{1},y_{1})$ runs over the set
$X_{i_{1}}^{(1)}\times Y_{j_{1}}^{(1)}$, and thus
$(L_{i}^{(1)})_{x_{1},y_{1}}$ takes all the elements in $[q_{1}r_{1}]$ exactly
once because of the Sudoku property for $L_{1}$. Similarly, the same is true
for $(L_{i}^{(2)})_{x_{2},y_{2}}$. Therefore, $M_{i}$ is a Sudoku of type
$(q_{1}q_{2},r_{1}r_{2})$.

Next, let $N^{(1)}_{i_{1},j_{1}},N^{(2)}_{i_{2},j_{2}}$ be the
$(i_{1},j_{1})$-block of $L_{1}^{(i)}$ and $(i_{2},j_{2})$-block of
$L_{2}^{(i)}$ respectively and $P^{(i)},Q^{(i)}$ be the permutation matrices
of order $q_{i},r_{i}$ respectively such that
$N^{(1)}_{k,\ell}=(P^{(1)})^{-1}N^{(1)}_{1,1}Q^{(1)},N^{(2)}_{k,\ell}=(P^{(2)})^{-1}N^{(2)}_{1,1}Q^{(2)}$.
Then, letting $\tilde{N}_{(i_{1},i_{2}),(j_{1},j_{2})}^{(i)}$ be the
$((i_{1},i_{2}),(j_{1},j_{2}))$-block of $M_{i}$, we have

$\tilde{N}_{(i_{1},i_{2}),(j_{1},j_{2})}^{(i)}=(P^{(1)}\otimes
P^{(2)})^{-1}\tilde{N}_{(1,1),(1,1)}^{(i)}(Q^{(1)}\otimes Q^{(2)}).$

Therefore, $M_{i}$ is of block permutational.∎

Combining Theorems 4.3 and 4.4, we obtain:

######  Theorem 4.5.

Let $p_{1},\ldots,p_{k}$ be distinct primes, $m_{1},n_{1},\ldots,m_{k},n_{k}$
be non-negative integers such that either $m_{i}$ or $n_{i}$ is positive. Then
there exist mutually orthogonal Sudoku Latin squares $L_{1},\ldots,L_{f}$ of
order $\prod_{i=1}^{k}p_{i}^{m_{i}+n_{i}}$ of type
$(\prod_{i=1}^{k}p_{i}^{m_{i}},\prod_{i=1}^{k}p_{i}^{n_{i}})$ which are of
block permutational, where
$f=\min\\{\ell(p_{1},m_{1},n_{1}),\ldots,\ell(p_{k},m_{k},n_{k})\\}$ where

$\ell(p,m,n)=\begin{cases}\max\\{p^{m}(p-1),p^{n}(p-1)\\}&\text{ if }m>0\text{
and }n>0,\\\ \max\\{p^{m}(p-1),p^{n}-1\\}&\text{ if }m>0\text{ and }n=0,\\\
\max\\{p^{m}-1,p^{n}(p-1)\\}&\text{ if }m=0\text{ and }n>0.\end{cases}$

Table 1: Lower bounds on the maximum number of $f$ order | type | $f$
---|---|---
2 | (1,2) | 1
3 | (1,3) | 2
4 | (1,4) | 3
| (2,2) | 2
5 | (1,5) | 4
6 | (1,6) | 1
| (2,3) | 1
7 | (1,7) | 6
8 | (1,8) | 7
| (2,4) | 4
9 | (1,9) | 8
| (3,3) | 6
10 | (1,10) | $\geq 2$
| (2,5) | $\geq 1$
11 | (1,11) | 10
12 | (1,12) | $\geq 5$
| (2,6) | $\geq 2$
| (3,4) | $\geq 2$

##  5 Cycle switching for a Sudoku Latin square

In Sections 3 and 4, we constructed Sudoku Latin squares whose graph spectrum
is explicitly determined. In this section, we apply the method of cycle
switching [8] to Sudoku Latin squares and determine the graph spectra.

Let $L$ be a Latin square of order $n$ on the symbol $[n]=\\{1,2,\ldots,n\\}$.
Regard a $\\{r,s\\}\times[n]$ subarray of $L$ as a permutation
$\sigma:L_{r,i}\mapsto L_{s,i}$ for $i\in[n]$. Consider the cycle
decomposition of $\sigma=\sigma_{1}\cdots\sigma_{t}$. Assume $\sigma_{1}$
involves the set $C$ of columns. A cycle switching of $L$ with respect to
$\sigma_{1}$ is a new Latin square $L^{\prime}$ obtained in the following way:

$\displaystyle L^{\prime}_{ij}$ $\displaystyle=\begin{cases}L_{sj}&\text{ if
}i=r\text{ and }j\in C,\\\ L_{rj}&\text{ if }i=s\text{ and }j\in C,\\\
L_{ij}&\text{ otherwise}.\end{cases}$

A cycle switching for a Sudoku Latin square does not necessarily provide a
Sudoku Latin square, as described below.

######  Remark 5.1.

The following square $L_{1}$ is a Sudoku Latin square of order $4$ and $L_{2}$
is obtained from $L_{1}$ by switching the entries $1,4$ in the second and
third rows:

$L_{1}=\begin{array}[]{|c|c|c|c|}\hline\cr 1&2&3&4\\\ \hline\cr 3&4&1&2\\\
\hline\cr 2&1&4&3\\\ \hline\cr 4&3&2&1\\\ \hline\cr\end{array},\quad
L_{2}=\begin{array}[]{|c|c|c|c|}\hline\cr 1&2&3&4\\\ \hline\cr 3&1&4&2\\\
\hline\cr 2&4&1&3\\\ \hline\cr 4&3&2&1\\\ \hline\cr\end{array}.$

Then $L_{2}$ is a Latin square, but not a Sudoku Latin square. Therefore the
cycle switching does not necessarily preserve the property of Sudoku.

Let $L$ be a Sudoku Latin square of order $qr$ of type $(q,r)$ with $q,r\geq
2$ which are of block permutational. Let $k_{1},k_{2}$ be distinct entries in
a column of $B_{1,1}$ in $L$, and set $\sigma=(k_{1},k_{2})$ to be a
transposition. We then apply $\sigma$ on the first row blocks
$B_{1,1},B_{1,2},\ldots,B_{1,q}$, and set the resulting Sudoku Latin square to
be $L^{\prime}$111This is certainly cycle switching if we regard a Latin
square as the set of triples $(i,j,L_{ij})$ and then . In this section, we
determine the spectrum of the graph $G_{L^{\prime}}$ and claim the spectrum of
$G_{L^{\prime}}$ differs from that of $G_{L}$. Thus we conclude that they are
not isomorphic.

Write $A_{L}$ and $A_{L^{\prime}}$ as the adjacency matrices of the Latin
square graphs. We prove the following theorem.

######  Theorem 5.2.

The spectrum of $A_{L^{\prime}}+B$ is

$\displaystyle(\mathrm{Spec}(A_{L}+B)\setminus X)\cup Y$

as a multiset, where

$\displaystyle\mathrm{Spec}(A_{L}+B)=$
$\displaystyle\\{[(q-1)(r-1)+3qr-3]^{1},[(q-1)(r-1)+qr-3]^{q+r-2},$
$\displaystyle[(q-1)(r-1)-3]^{(q-1)(r-1)},[qr-2]^{f(q-1)(r-1)},$
$\displaystyle[qr-q-2]^{(q+1)(r-1)},[qr-r-2]^{(q-1)(r+1)},$
$\displaystyle[-2]^{(q-1)(r-1)(qr-1)},[-q-2]^{(r-1)(qr-q-1)},[-r-2]^{(q-1)(qr-r-1)}\\},$
$\displaystyle X=$ $\displaystyle\\{-2,-r-2,qr-2,qr-r-2\\},$ $\displaystyle
Y=$
$\displaystyle\left\\{\frac{1}{2}\left((q-1)r-4\pm\sqrt{\left(q^{2}+1\right)r^{2}\pm
2q(r-2)\sqrt{r^{2}+4r-4}}\right)\right\\}.$

###### Proof.

If $x,y\in B_{1,1}$ or $x,y\in\bigcup_{\begin{subarray}{c}2\leq k\leq r\\\
2\leq\ell\leq q\end{subarray}}B_{k,\ell}$, then

$\displaystyle(A_{L^{\prime}}-A_{L})_{x,y}$ $\displaystyle=0.$

Since $B_{1,\ell}$ is permutaionally equivalent to $B_{1,1}$, the submatrix of
$A_{L^{\prime}}-A_{L}$ with rows restricted to $B_{1,1}$ and columns
restricted to $B_{1,\ell}$ has two non-zero column vectors such that one is
negative to the other for $\ell\in\\{2,\ldots,q\\}$. Moreover, the set of non-
zero column vectors with respect to $B_{1,\ell}$ coincides with those with
respect to $B_{1,\ell^{\prime}}$ for $\ell,\ell^{\prime}\in\\{2,\ldots,q\\}$.

Thus the matrix $Y=A_{L^{\prime}}-A_{L}$ is of the following form:

$Y=\begin{pmatrix}0&Z\\\ Z^{\top}&0\end{pmatrix},$

where $Z$ is a $q^{2}r\times(q^{2}r^{2}-q^{2}r)$ $(0,\pm 1)$-matrix of rank
$1$. Then there exist column vectors $u,v$ of $Y$ with
$u^{\top}u=2q(r-1),v^{\top}v=2q,v^{\top}v=0$ such that $Y=UV^{\top}$ holds,
where

$U=\begin{pmatrix}u&v\end{pmatrix},\quad V=\begin{pmatrix}v&u\end{pmatrix}.$

Note that $u,v$ can be written as

$\displaystyle u$
$\displaystyle=\sum_{i=2}^{r}\sum_{j=1}^{q}e_{i}^{(q)}\otimes
e_{j}^{(r)}\otimes(e_{\psi_{1}(i,j)}^{(q)}-e_{\psi_{2}(i,j)}^{(q)})\otimes
e_{\psi_{3}(i,j)}^{(r)},$ (3) $\displaystyle v$
$\displaystyle=\sum_{j=1}^{q}e_{1}^{(q)}\otimes
e_{j}^{(r)}\otimes(e_{\psi_{1}(1,j)}^{(q)}-e_{\psi_{2}(1,j)}^{(q)})\otimes
e_{\psi_{3}(1,j)}^{(r)},$ (4)

where $\psi_{1},\psi_{2}$ are functions from $[q]\times[r]$ to $[q]$ such that
$\psi_{1}(i,j)\neq\psi_{2}(i,j)$ for any $i,j$ and $\psi_{3}$ is a functions
from $[q]\times[r]$ to $[r]$.

Since $A_{L^{\prime}}=A_{L}+UV^{\top}$ and by matrix determinant lemma, we
obtain

$\displaystyle\det(A_{L^{\prime}}-tI_{q^{2}r^{2}})$
$\displaystyle=\det(A_{L}-tI_{q^{2}r^{2}}+UV^{\top})$
$\displaystyle=\det(A_{L}-tI_{q^{2}r^{2}})\det(I_{2}+V^{\top}(A_{L}-tI_{q^{2}r^{2}})^{-1}U).$
(5)

Let $A_{L}$ have the spectral decomposition as
$A_{L}=\sum_{i=1}^{3}\theta_{i}E_{i}$, where $\theta_{i}$ are the same as in
the proof of Theorem 3.6 with $f=1$. Since $E_{1}u=E_{1}v={\bf 0}$ which
follow from (3) and (4),

$\displaystyle V^{\top}(A_{L}-tI_{{q^{2}r^{2}}})^{-1}U$
$\displaystyle=V^{\top}\left(\sum_{i=1}^{3}\frac{1}{\theta_{i}-t}E_{i}\right)U$
$\displaystyle=\sum_{i=1}^{3}\frac{1}{\theta_{i}-t}V^{\top}E_{i}U$
$\displaystyle=\sum_{i=1}^{3}\frac{1}{\theta_{i}-t}\begin{pmatrix}v^{\top}E_{i}u&v^{\top}E_{i}v\\\
u^{\top}E_{i}u&u^{\top}E_{i}v\end{pmatrix}$
$\displaystyle=\sum_{i=2}^{3}\frac{1}{\theta_{i}-t}\begin{pmatrix}v^{\top}E_{i}u&v^{\top}E_{i}v\\\
u^{\top}E_{i}u&u^{\top}E_{i}v\end{pmatrix}.$

Therefore Equation (5) is

$\displaystyle\eqref{eq:cs01}=\det(A_{L}-tI_{q^{2}r^{2}})\det\left(I_{2}+\sum_{i=2}^{3}\frac{1}{\theta_{i}-t}\begin{pmatrix}v^{\top}E_{i}u&v^{\top}E_{i}v\\\
u^{\top}E_{i}u&u^{\top}E_{i}v\end{pmatrix}\right).$ (6)

Since $A_{L^{\prime}}$ and $A_{L}$ are the adjacency matrices of strongly
regular graphs with the same parameters, we have
$\det(A_{L}-tI_{q^{2}r^{2}})=\det(A_{L^{\prime}}-tI_{q^{2}r^{2}})$. Combining
this with Equation (6) yields that

$\det\left(I_{2}+\sum_{i=2}^{3}\frac{1}{\theta_{i}-t}\begin{pmatrix}v^{\top}E_{i}u&v^{\top}E_{i}v\\\
u^{\top}E_{i}u&u^{\top}E_{i}v\end{pmatrix}\right)=1,$

which gives rise to. Therefore, by using the formula that
$u^{\top}E_{2}u+u^{\top}E_{3}u=2q(r-1),v^{\top}E_{2}v+v^{\top}E_{3}v=2q$,
which follow from (3) and (4) and $u^{\top}E_{i}v=v^{\top}E_{i}u$ for $i=2,3$,
we obtain the following identity in a variable $t$:

$\displaystyle-36q+36qr+24q^{2}r-24q^{2}r^{2}-4q^{3}r^{2}+4q^{3}r^{3}+(18r-6qr^{2})a_{1,1}-qr^{2}a_{1,1}^{2}-6qra_{1,2}$
$\displaystyle+(6qr^{2}+2q^{2}r^{2}-2q^{2}r^{3})a_{1,2}+(6qr-2q^{2}r^{2})a_{2,1}+qr^{2}a_{1,2}a_{2,1}$
$\displaystyle+t(-24q+24qr+8q^{2}r-8q^{2}r^{2}+(12r-2qr^{2})a_{1,1}+(-2qr+2qr^{2})a_{1,2}+2qra_{2,1})$
$\displaystyle+t^{2}(-4q+4qr+2ra_{2,1})=0,$

where $a_{1,1}=v^{\top}E_{2}u,a_{1,2}=v^{\top}E_{2}v,a_{2,1}=u^{\top}E_{2}u$.
Then, either of the following holds:

  1. (i)

$\begin{pmatrix}v^{\top}E_{2}u&v^{\top}E_{2}v\\\
u^{\top}E_{2}u&u^{\top}E_{2}v\end{pmatrix}=\begin{pmatrix}-\frac{2q(r-1)}{r}&\frac{2q}{r}\\\
\frac{2q(r-1)^{2}}{r}&-\frac{2q(r-1)}{r}\end{pmatrix},\quad\begin{pmatrix}v^{\top}E_{3}u&v^{\top}E_{3}v\\\
u^{\top}E_{3}u&u^{\top}E_{3}v\end{pmatrix}=\begin{pmatrix}\frac{2q(r-1)}{r}&\frac{2q(r-1)}{r}\\\
\frac{2q(r-1)}{r}&\frac{2q(r-1)}{r}\end{pmatrix}$.

  2. (ii)

$\begin{pmatrix}v^{\top}E_{2}u&v^{\top}E_{2}v\\\
u^{\top}E_{2}u&u^{\top}E_{2}v\end{pmatrix}=\begin{pmatrix}-\frac{2q(r-1)}{r}&\frac{2q(r-1)}{r}\\\
\frac{2q(r-1)}{r}&-\frac{2q(r-1)}{r}\end{pmatrix},\quad\begin{pmatrix}v^{\top}E_{3}u&v^{\top}E_{3}v\\\
u^{\top}E_{3}u&u^{\top}E_{3}v\end{pmatrix}=\begin{pmatrix}\frac{2q(r-1)}{r}&\frac{2q}{r}\\\
\frac{2q(r-1)^{2}}{r}&\frac{2q(r-1)}{r}\end{pmatrix}$.

Then, corresponding to the above, we have the following:

  1. (i)

$E_{2}(u-v)=u-v,E_{2}(u+(r-1)v)={\bf 0},E_{3}(u-v)={\bf
0},E_{3}(u+(r-1)v)=u+(r-1)v$, that is
$E_{2}u=\frac{r-1}{r}(u-v),E_{2}v=-\frac{1}{r}(u-v),E_{3}u=E_{3}v=\frac{1}{r}(u+(r-1)v)$.

  2. (ii)

$E_{2}(u+v)={\bf
0},E_{2}(u-(r-1)v)=u-(r-1)v,E_{3}(u+v)=u+v,E_{3}(u-(r-1)v)={\bf 0}$, that is
$E_{2}u=-\frac{1}{r}(u-(r-1)v),E_{2}v=\frac{1}{r}(u-(r-1)v),E_{3}u=\frac{r-1}{r}(u+v),E_{3}v=\frac{1}{r}(u+v)$.

Indeed, for (i),
$(u^{\top}-v^{\top})E_{3}(u-v)=u^{\top}E_{3}u-u^{\top}E_{3}v-v^{\top}E_{3}u+v^{\top}E_{3}v=0$,
and thus $E_{3}(u-v)={\bf 0}$ by $E_{3}$ being positive semidefnite. Since
$I=\sum_{i=1}^{3}E_{i}$ and $E_{1}u=E_{1}v={\bf 0}$, we have $E_{2}(u-v)=u-v$.
The others are similarly shown.

Next we calculate $\det(A_{L^{\prime}}+B-tI_{q^{4}})$. By matrix determinant
lemma again, we obtain:

$\displaystyle\det(A_{L^{\prime}}+B-tI_{q^{4}})$
$\displaystyle=\det(A_{L}+B-tI_{q^{4}}+UV^{\top})$
$\displaystyle=\det(A_{L}+B-tI_{q^{4}})\det(I_{2}+V^{\top}(A_{L}+B-tI_{q^{4}})^{-1}U).$
(7)

Let $B$ have the spectral decomposition as $B=\sum_{i=1}^{4}b_{i}F_{i}$. Note
that

$\displaystyle F_{1}$ $\displaystyle=\frac{1}{qr}I_{qr}\otimes J_{qr},$
$\displaystyle F_{2}$
$\displaystyle=I_{qr}\otimes(I_{q}-\frac{1}{q}J_{q})\otimes(I_{r}-\frac{1}{r}J_{r}),$
$\displaystyle F_{3}$ $\displaystyle=\frac{1}{q}I_{qr}\otimes
J_{q}\otimes(I_{r}-\frac{1}{r}J_{r}),$ $\displaystyle F_{4}$
$\displaystyle=\frac{1}{r}I_{qr}\otimes(I_{q}-\frac{1}{q}J_{q})\otimes J_{r}.$

Since

$\displaystyle A_{L}+B=A_{l}\cdot I+I\cdot
B=\sum_{i=1}^{3}\theta_{i}E_{i}\sum_{j=1}^{4}F_{j}+\sum_{i=1}^{3}E_{i}\sum_{j=1}^{4}b_{j}F_{j}=\sum_{i=1}^{3}\sum_{j=1}^{4}(\theta_{i}+b_{j})E_{i}F_{j}$

and $E_{1}u=F_{1}u=E_{1}v=F_{1}v=F_{3}u=F_{3}v={\bf 0}$ which follow from (3)
and (4),

$\displaystyle V^{\top}(A_{L}+B-tI_{q^{4}})^{-1}U$
$\displaystyle=V^{\top}(\sum_{i=1}^{3}\sum_{j=1}^{4}\frac{1}{\theta_{i}+b_{j}-t}E_{i}F_{j})U$
$\displaystyle=\sum_{i=1}^{3}\sum_{j=1}^{4}\frac{1}{\theta_{i}+b_{j}-t}V^{\top}E_{i}F_{j}U$
$\displaystyle=\sum_{i=1}^{3}\sum_{j=1}^{4}\frac{1}{\theta_{i}+b_{j}-t}\begin{pmatrix}v^{\top}E_{i}F_{j}u&v^{\top}E_{i}F_{j}v\\\
u^{\top}E_{i}F_{j}u&u^{\top}E_{i}F_{j}v\end{pmatrix}$
$\displaystyle=\sum_{i=2}^{3}\sum_{j=2,4}\frac{1}{\theta_{i}+b_{j}-t}\begin{pmatrix}v^{\top}E_{i}F_{j}u&v^{\top}E_{i}F_{j}v\\\
u^{\top}E_{i}F_{j}u&u^{\top}E_{i}F_{j}v\end{pmatrix}$ (8)

Using the following fact:

$\displaystyle
u^{\top}F_{2}u=\frac{2q(r-1)^{2}}{r},v^{\top}F_{2}v=\frac{2q(r-1)}{r},u^{\top}F_{2}v=v^{\top}F_{2}u=0,$
$\displaystyle
u^{\top}F_{4}u=\frac{2q(r-1)}{r},v^{\top}F_{4}v=\frac{2q}{r},u^{\top}F_{4}v=v^{\top}F_{4}u=0,$

we have in the case (i)

$\displaystyle\begin{pmatrix}v^{\top}E_{2}F_{2}u&v^{\top}E_{2}F_{2}v\\\
u^{\top}E_{2}F_{2}u&u^{\top}E_{2}F_{2}v\end{pmatrix}=\begin{pmatrix}-\frac{2q(r-1)^{2}}{r^{2}}&\frac{2q(r-1)}{r^{2}}\\\
\frac{2q(r-1)^{3}}{r^{2}}&-\frac{2q(r-1)^{2}}{r^{2}}\end{pmatrix},\begin{pmatrix}v^{\top}E_{2}F_{4}u&v^{\top}E_{2}F_{4}v\\\
u^{\top}E_{2}F_{4}u&u^{\top}E_{2}F_{4}v\end{pmatrix}=\begin{pmatrix}-\frac{2q(r-1)}{r^{2}}&\frac{2q}{r^{2}}\\\
\frac{2q(r-1)^{2}}{r^{2}}&-\frac{2q(r-1)}{r^{2}}\end{pmatrix},$
$\displaystyle\begin{pmatrix}v^{\top}E_{3}F_{2}u&v^{\top}E_{3}F_{2}v\\\
u^{\top}E_{3}F_{2}u&u^{\top}E_{3}F_{2}v\end{pmatrix}=\begin{pmatrix}{\frac{2q(r-1)^{2}}{r^{2}}}&{\frac{2q(r-1)^{2}}{r^{2}}}\\\
{\frac{2q(r-1)^{2}}{r^{2}}}&{\frac{2q(r-1)^{2}}{r^{2}}}\end{pmatrix},\begin{pmatrix}v^{\top}E_{3}F_{{4}}u&v^{\top}E_{3}F_{{4}}v\\\
u^{\top}E_{3}F_{{4}}u&u^{\top}E_{3}F_{{4}}v\end{pmatrix}=\begin{pmatrix}{\frac{2q(r-1)}{r^{2}}}&{\frac{2q(r-1)}{r^{2}}}\\\
{\frac{2q(r-1)}{r^{2}}}&{\frac{2q(r-1)}{r^{2}}}\end{pmatrix}.$

while we have in the case (ii)

$\displaystyle\begin{pmatrix}v^{\top}E_{2}F_{2}u&v^{\top}E_{2}F_{2}v\\\
u^{\top}E_{2}F_{{2}}u&u^{\top}E_{2}F_{{2}}v\end{pmatrix}=\begin{pmatrix}{-\frac{2q(r-1)^{2}}{r^{2}}}&{\frac{2q(r-1)^{2}}{r^{2}}}\\\
{\frac{2q(r-1)^{2}}{r^{2}}}&{-\frac{2q(r-1)^{2}}{r^{2}}}\end{pmatrix},\begin{pmatrix}v^{\top}E_{2}F_{{4}}u&v^{\top}E_{2}F_{{4}}v\\\
u^{\top}E_{2}F_{{4}}u&u^{\top}E_{2}F_{{4}}v\end{pmatrix}=\begin{pmatrix}{-\frac{2q(r-1)}{r^{2}}}&{\frac{2q(r-1)}{r^{2}}}\\\
{\frac{2q(r-1)}{r^{2}}}&{-\frac{2q(r-1)}{r^{2}}}\end{pmatrix},$
$\displaystyle\begin{pmatrix}v^{\top}E_{3}F_{2}u&v^{\top}E_{3}F_{2}v\\\
u^{\top}E_{3}F_{2}u&u^{\top}E_{3}F_{2}v\end{pmatrix}=\begin{pmatrix}{\frac{2q(r-1)^{2}}{r^{2}}}&{\frac{2q(r-1)}{r^{2}}}\\\
{\frac{2q(r-1)^{3}}{r^{2}}}&{\frac{2q(r-1)^{2}}{r^{2}}}\end{pmatrix},\begin{pmatrix}v^{\top}E_{3}F_{{4}}u&v^{\top}E_{3}F_{{4}}v\\\
u^{\top}E_{3}F_{{4}}u&u^{\top}E_{3}F_{{4}}v\end{pmatrix}=\begin{pmatrix}{\frac{2q(r-1)}{r^{2}}}&{\frac{2q}{r^{2}}}\\\
{\frac{2q(r-1)^{2}}{r^{2}}}&{\frac{2q(r-1)}{r^{2}}}\end{pmatrix}.$

Then Equation (8) in either case (i), (ii) is

$\displaystyle\eqref{eq:cs0211}$
$\displaystyle=\det\left(I_{2}+\sum_{i=2}^{3}{\sum_{j=2,4}}\frac{1}{\theta_{i}+{b_{j}}-t}\begin{pmatrix}v^{\top}E_{i}F_{j}u&v^{\top}E_{i}F_{j}v\\\
u^{\top}E_{i}F_{j}u&u^{\top}E_{i}F_{j}v\end{pmatrix}\right)$
$\displaystyle=\frac{f(t)}{(t+2)(t+{r}+2)\left(t-{qr}+2\right)\left(t-{qr}+{r}+2\right)}$
(9)

where

$\displaystyle f(t)$
$\displaystyle={t^{4}+\left(-2qr+2r+8\right)t^{3}+\left(q^{2}r^{2}-3qr^{2}-12qr+r^{2}+12r+24\right)t^{2}}$
$\displaystyle{+\left(q^{2}r^{3}+4q^{2}r^{2}-qr^{3}-12qr^{2}-24qr+4r^{2}+24r+32\right)t}$
$\displaystyle{+2q^{2}r^{3}+8q^{2}r^{2}-8q^{2}r+4q^{2}-2qr^{3}-12qr^{2}-16qr+4r^{2}+16r+16}.$

Substituting (9) into (7) yields that

$\displaystyle\det(A_{L^{\prime}}+B-tI_{{q^{2}r^{2}}})$
$\displaystyle=\frac{\det(A_{L}+B-tI_{{q^{2}r^{2}}})f(t)}{(t+2)(t+{r}+2)\left(t-{qr}+2\right)\left(t-{qr}+{r}+2\right)}.$
(10)

Note that the polynomial $f(t)$ has the roots

$t={\frac{1}{2}\left((q-1)r-4\pm\sqrt{\left(q^{2}+1\right)r^{2}\pm
2q(r-2)\sqrt{r^{2}+4r-4}}\right)}.$

This completes the proof. ∎

######  Example 5.3.

The following are examples of Sudoku Latin squares of order $4$:

$L_{1}=\begin{array}[]{Ic|cIc|cI}\hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 1&2\hfil\lx@intercol\vrule
width=2.0&3&4\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 3&4\hfil\lx@intercol\vrule
width=2.0&1&2\hfil\lx@intercol\vrule width=2.0\\\ \hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 2&1\hfil\lx@intercol\vrule
width=2.0&4&3\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 4&3\hfil\lx@intercol\vrule
width=2.0&2&1\hfil\lx@intercol\vrule width=2.0\\\ \hrule
height=2.0pt\cr\end{array},\quad L_{2}=\begin{array}[]{Ic|cIc|cI}\hrule
height=2.0pt\cr width=2.0pt\lx@intercol\hfil 1&2\hfil\lx@intercol\vrule
width=2.0&3&4\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 3&4\hfil\lx@intercol\vrule
width=2.0&2&1\hfil\lx@intercol\vrule width=2.0\\\ \hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 2&1\hfil\lx@intercol\vrule
width=2.0&4&3\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 4&3\hfil\lx@intercol\vrule
width=2.0&1&2\hfil\lx@intercol\vrule width=2.0\\\ \hrule
height=2.0pt\cr\end{array}$

Write the adjacency matrix of graphs of Sudoku Latin squares $L_{i}$ as
$A_{L_{i}}$ ($i\in\\{1,2\\}$). Then the spectra of $A_{L_{1}}$ and $A_{L_{2}}$
are

$\displaystyle\text{Spec}(A_{L_{1}})$
$\displaystyle=\\{[10]^{1},[-4]^{2},[-2]^{4},[2]^{3},[0]^{6}\\},$
$\displaystyle\text{Spec}(A_{L_{2}})$
$\displaystyle=\\{[10]^{1},[-4]^{1},[-1-\sqrt{5}]^{2},[-2]^{3},[2]^{2},[-1+\sqrt{5}]^{2},[0]^{5}\\}.$

######  Example 5.4.

The following are examples of Sudoku Latin squares of order $6$ of type
$(2,3)$:

$L_{1}=\begin{array}[]{Ic|c|cIc|c|cI}\hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 1&2&3\hfil\lx@intercol\vrule
width=2.0&4&5&6\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 4&5&6\hfil\lx@intercol\vrule
width=2.0&1&2&3\hfil\lx@intercol\vrule width=2.0\\\ \hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 2&3&1\hfil\lx@intercol\vrule
width=2.0&5&6&4\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 5&6&4\hfil\lx@intercol\vrule
width=2.0&2&3&1\hfil\lx@intercol\vrule width=2.0\\\ \hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 3&1&2\hfil\lx@intercol\vrule
width=2.0&6&4&5\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 6&4&5\hfil\lx@intercol\vrule
width=2.0&3&1&2\hfil\lx@intercol\vrule width=2.0\\\ \hrule
height=2.0pt\cr\end{array},\quad L_{2}=\begin{array}[]{Ic|c|cIc|c|cI}\hrule
height=2.0pt\cr width=2.0pt\lx@intercol\hfil 4&2&3\hfil\lx@intercol\vrule
width=2.0&1&5&6\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 1&5&6\hfil\lx@intercol\vrule
width=2.0&4&2&3\hfil\lx@intercol\vrule width=2.0\\\ \hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 2&3&1\hfil\lx@intercol\vrule
width=2.0&5&6&4\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 5&6&4\hfil\lx@intercol\vrule
width=2.0&2&3&1\hfil\lx@intercol\vrule width=2.0\\\ \hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 3&1&2\hfil\lx@intercol\vrule
width=2.0&6&4&5\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 6&4&5\hfil\lx@intercol\vrule
width=2.0&3&1&2\hfil\lx@intercol\vrule width=2.0\\\ \hrule
height=2.0pt\cr\end{array}$

Write the adjacency matrix of graphs of Sudoku Latin squares $L_{i}$ as
$A_{L_{i}}$ ($i\in\\{1,2\\}$). Then the spectra of $A_{L_{1}}$ and $A_{L_{2}}$
are

$\displaystyle\text{Spec}(A_{L_{1}})$
$\displaystyle=\\{[17]^{1},[-5]^{2},[-4]^{6},[-2]^{10},[-1]^{2},[1]^{4},[2]^{6},[4]^{2},[5]^{3}\\},$
$\displaystyle\text{Spec}(A_{L_{2}})$
$\displaystyle=\left\\{[17]^{1},[-5]^{2},[-4]^{5},[-2]^{9},[-1]^{2},[1]^{4},[2]^{5},[4]^{1},[5]^{3},\left[\frac{1}{2}\left(-1\pm\sqrt{45\pm
4\sqrt{17}}\right)\right]^{1}\right\\}.$

######  Example 5.5.

The following are examples of Sudoku Latin squares of order $9$:

$L_{1}=\begin{array}[]{Ic|c|cIc|c|cIc|c|cI}\hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 5&6&4\hfil\lx@intercol\vrule
width=2.0&8&9&7\hfil\lx@intercol\vrule width=2.0&2&3&1\hfil\lx@intercol\vrule
width=2.0\\\ \hline\cr width=2.0pt\lx@intercol\hfil
9&7&8\hfil\lx@intercol\vrule width=2.0&3&1&2\hfil\lx@intercol\vrule
width=2.0&6&4&5\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 1&2&3\hfil\lx@intercol\vrule
width=2.0&4&5&6\hfil\lx@intercol\vrule width=2.0&7&8&9\hfil\lx@intercol\vrule
width=2.0\\\ \hrule height=2.0pt\cr width=2.0pt\lx@intercol\hfil
3&1&2\hfil\lx@intercol\vrule width=2.0&6&4&5\hfil\lx@intercol\vrule
width=2.0&9&7&8\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 4&5&6\hfil\lx@intercol\vrule
width=2.0&7&8&9\hfil\lx@intercol\vrule width=2.0&1&2&3\hfil\lx@intercol\vrule
width=2.0\\\ \hline\cr width=2.0pt\lx@intercol\hfil
8&9&7\hfil\lx@intercol\vrule width=2.0&2&3&1\hfil\lx@intercol\vrule
width=2.0&5&6&4\hfil\lx@intercol\vrule width=2.0\\\ \hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 7&8&9\hfil\lx@intercol\vrule
width=2.0&1&2&3\hfil\lx@intercol\vrule width=2.0&4&5&6\hfil\lx@intercol\vrule
width=2.0\\\ \hline\cr width=2.0pt\lx@intercol\hfil
2&3&1\hfil\lx@intercol\vrule width=2.0&5&6&4\hfil\lx@intercol\vrule
width=2.0&8&9&7\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 6&4&5\hfil\lx@intercol\vrule
width=2.0&9&7&8\hfil\lx@intercol\vrule width=2.0&3&1&2\hfil\lx@intercol\vrule
width=2.0\\\ \hrule height=2.0pt\cr\end{array},\quad
L_{2}=\begin{array}[]{Ic|c|cIc|c|cIc|c|cI}\hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 5&6&4\hfil\lx@intercol\vrule
width=2.0&8&9&7\hfil\lx@intercol\vrule width=2.0&1&3&2\hfil\lx@intercol\vrule
width=2.0\\\ \hline\cr width=2.0pt\lx@intercol\hfil
9&7&8\hfil\lx@intercol\vrule width=2.0&3&1&2\hfil\lx@intercol\vrule
width=2.0&6&4&5\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 1&2&3\hfil\lx@intercol\vrule
width=2.0&4&5&6\hfil\lx@intercol\vrule width=2.0&7&8&9\hfil\lx@intercol\vrule
width=2.0\\\ \hrule height=2.0pt\cr width=2.0pt\lx@intercol\hfil
3&1&2\hfil\lx@intercol\vrule width=2.0&6&4&5\hfil\lx@intercol\vrule
width=2.0&9&7&8\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 4&5&6\hfil\lx@intercol\vrule
width=2.0&7&8&9\hfil\lx@intercol\vrule width=2.0&2&1&3\hfil\lx@intercol\vrule
width=2.0\\\ \hline\cr width=2.0pt\lx@intercol\hfil
8&9&7\hfil\lx@intercol\vrule width=2.0&2&3&1\hfil\lx@intercol\vrule
width=2.0&5&6&4\hfil\lx@intercol\vrule width=2.0\\\ \hrule height=2.0pt\cr
width=2.0pt\lx@intercol\hfil 7&8&9\hfil\lx@intercol\vrule
width=2.0&1&2&3\hfil\lx@intercol\vrule width=2.0&4&5&6\hfil\lx@intercol\vrule
width=2.0\\\ \hline\cr width=2.0pt\lx@intercol\hfil
2&3&1\hfil\lx@intercol\vrule width=2.0&5&6&4\hfil\lx@intercol\vrule
width=2.0&8&9&7\hfil\lx@intercol\vrule width=2.0\\\ \hline\cr
width=2.0pt\lx@intercol\hfil 6&4&5\hfil\lx@intercol\vrule
width=2.0&9&7&8\hfil\lx@intercol\vrule width=2.0&3&2&1\hfil\lx@intercol\vrule
width=2.0\\\ \hrule height=2.0pt\cr\end{array}$

Write the adjacency matrix of graphs of Sudoku Latin squares $L_{i}$ as
$A_{L_{i}}$ ($i\in\\{1,2\\}$). Then the spectra of $A_{L_{1}}$ and $A_{L_{2}}$
are

$\displaystyle\text{Spec}(A_{L_{1}})$
$\displaystyle=\\{[28]^{1},[10]^{4},[7]^{4},[-5]^{20},[4]^{16},[-2]^{32},[1]^{4}\\},$
$\displaystyle\text{Spec}(A_{L_{2}})$
$\displaystyle=\left\\{[28]^{1},[10]^{4},[7]^{3},[-5]^{19},[4]^{15},[-2]^{31},[1]^{4},\left[\frac{1}{2}\left(2\pm\sqrt{6\left(15\pm\sqrt{17}\right)}\right)\right]^{1}\right\\}.$

## Acknowledgments.

Sho Kubota is supported by JSPS KAKENHI Grant Nnumber 20J01175, and Sho Suda
is supported by JSPS KAKENHI Grant Number 18K03395.

## References

  * [1] R. A. Bailey, P. J. Cameron, R. Connelly, Sudoku, gerechte designs, resolutions, affine space, spreads, reguli, and Hamming codes, Amer. Math. Monthly 115 (2008), 383–404.
  * [2] A. E. Brouwer, W. H. Haemers, Spectra of graphs, Universitext. Springer, New York, 2012. xiv+250 pp.
  * [3] J. D’haeseleer, K. Metsch, L. Storme, Leo, G. Van de Voorde, On the maximality of a set of mutually orthogonal Sudoku Latin squares, Des. Codes Cryptogr. 84 (2017), 143–152.
  * [4] J. Dénes, J, A. D. Keedwell, Latin squares and their applications, New York-London: Academic Press, 1974. 547 pp.
  * [5] C. Godsil, G. Royle, Algebraic graph theory, Graduate Texts in Mathematics, 207. Springer-Verlag, New York, 2001. xx+439 pp.
  * [6] R. M. Pedersen, T. L. Vis, Sets of mutually orthogonal Sudoku Latin squares. College Math. J. 40 (2009), 174–180.
  * [7] T. Sander, Sudoku graphs are integral, Electron. J. Combin. 16 (2009), Note 25, 7 pp.
  * [8] I. M. Wanless, Cycle switches in Latin squares, Graphs Combin. 20 (2004), 545–570.


#  Covy – An AI-powered Robot for Detection of Breaches in Social Distancing

Serge Saaybi
Delft University of Technology  Amjad Yousef Majid
Delft University of Technology
R Venkatesha Prasad
Delft University of Technology  Anis Koubaa
Prince Sultan University  Chris Verhoeven
Delft University of Technology

###### Abstract

We present Covy – a robotic platform that promotes social distancing during
pandemics like COVID-19. Covy features a novel compound vision system that
enables it to detect social distancing breaches up to $16\text{\,}\mathrm{m}$
away. Covy navigates its surroundings autonomously using a hybrid navigation
stack that combines Deep Reinforcement Learning (DRL)and a probabilistic
localization method. We built the complete system and evaluated Covy’s
performance through extensive sets of experiments both in simulated and
realistic environments. Amongst others, our results show that the hybrid
navigation stack is more robust compared to a pure DRL-based solution.

##  1 Introduction

The successful fight against a pandemic is partly determined by the degree to
which the imposed public health measures are adhered to by the population.
Enforcing these measures manually is a difficult and tiresome task if not
impossible. Manual intervention in itself may lead to further spread.
Technology can promote the desired social behaviors, such as social distancing
and face masking without the risk of additional infections. To this end, many
technological solutions have been proposed to monitor, analyze, and encourage
people to follow the recommended guidelines. Examples of proposed solutions
include monitoring through closed-circuit television (CCTV) [27] or tracking
via cellular networks, wearables and smartphones [24]. While the former has no
straightforward way of providing feedback to people, the latter compromise
their privacy.

We look towards autonomous Robots that can support humans in this situation.
They are mobile and can relatively easily be equipped with means to interact
with humans and encourage desired social behaviors (e.g. alerting littering
individuals). Nonetheless, a single robot, no matter how advanced, (e.g., Spot
from Boston Dynamics [12]) would not provide adequate coverage as it can only
cover limited areas. A better alternative is to employ a swarm of
collaborating robots. However, to make the swarm solution viable, the cost of
manufacturing the robots should be kept to a minimum while meeting the
application requirements. Towards this end, we developed Covy – a low-cost
robot that has a unique vision system and a hybrid navigation stack.

Figure 1: Hardware and software overview of Covy: a prototype swarm robot for
promoting social distancing practice.

Challenges. While there are many aspects to building a robot for such a
purpose, we provide herewith only relevant challenges. Covy was developed with
two main challenges in mind:  ➊ Designing a long-range, low-cost vision system
that can estimate the 3D coordinates of people in the scene; and  ➋ Developing
a navigation stack that is generalizable and easily deployable on different
robot models.

Contributions. Our contributions are manifold.  ➊ We built a platform with
complete stack called Covy and used it for evaluation.  ➋ We developed a
compound algorithm that increases the effective range of the Intel RealSense
depth camera by two times for detecting social distancing breaches.  ➌ We
developed a hybrid navigation stack that combines the power of Deep
Reinforcement Learning and a probabilistic localization system.  ➍ We
evaluated Covy by conducting extensive experiments in simulated and realistic
environments.

##  2 Related work

The use of robots for surveillance has been suggested before. Dr. spot is a
teleoperated quadruped robot that monitors social distancing and face masking
in public space and alerts offenders [30]. Chen et al. [6] introduced a fully
autonomous yet expensive surveillance quadruped, meaning large-scale
production for encouraging desired social behavior will be costly. Therefore,
Sathyamoorthy et al. [28] proposed a low-cost robotic system – similar to Covy
– able to detect and navigate towards the breaches using an RGB-D camera and
2D lidar. Their system also leverages static CCTV to increase the detection
range. However, a major drawback is the limited detection range of only up to
4 m for the mounted depth camera and 3 m for the fixed CCTV. We, in this work,
propose a compound low-cost vision system with a breach detection range of up
to 16$+$ m.

There is a growing interest in robotic navigation based on different DRL
algorithms [32, 31, 14, 22]. This is driven mainly by the portability of a DRL
navigation stack onto different robotic platforms and the capability for
online learning. Tai et al. [32] used Deep Deterministic Policy Gradient
(DDPG) to develop a mapless motion planner able to navigate a robot in real
unseen environments with obstacles. Costa de Jesus et al. [7] replaced the
DDPG with the Soft Actor-Critic [9] (SAC) DRL model and showed its efficacy
through simulation. Long et al. [20] utilized Proximal Policy Optimization
(PPO) [29] for a multi-robot collision avoidance policy directly mapping raw
sensor measurements to an agent’s steering commands. They also validated the
policy in various simulated environments. Kulhánek et al. [17] developed a
purely camera-based navigation system by extending a version of the batched
A2C algorithm [22] and validated the performance on a real robot [18]. For
Covy, we experimented with DDPG and SAC, a deterministic and probabilistic DRL
model, and developed a hybrid navigation stack to overcome some of the
observed limitations in a pure DRL approach.

##  3 Systems Overview

###  3.1 Hardware

Figure 1 shows Covy’s hardware and software stack. We explain briefly the Covy
system below.

Main CPU. Covy is based on the Jetson single-board computer family that is
capable of running multiple neural networks on low power. Jetson processor
family includes Jetson Nano, Jetson Xavier NX, and Jetson Xavier AGX.

Vision Sensor. An RGB-D camera captures RGB images and their depth information
on a per-pixel basis [21]. As such it is the natural choice for estimating 3D
coordinates of objects in images. The two most suitable depth cameras for our
applications are the ZED2 [3] and the Intel RealSense D435i [23]. The ZED2 has
twice the depth range of the D435i but also costs twice as much. We chose to
work with the lower-cost D435i which has a nominal depth range of
$10\text{\,}\mathrm{m}$.

Robot body. As we target indoor environment we equipped Jetbot [1] with a 2D
lidar [2] to enable the robot to navigate autonomously within a building.

###  3.2 Software

Figure 2: Schematic of the compound vision system of Covy.

Covy has a ROS-based [25] software that is divided into two main modules:
breach detection and navigation.

####  3.2.1 Breach Detection

Covy vision system scans the scene for people twice: (i) Using RGB-D images,
Covy localizes nearby people, and (ii) using pure RGB images, it estimates the
localization of people that cannot be detected in the first stage (Figure 2).
In stage one, YOLOv3 ROS [26] takes in an RGB image and identifies the people
in it. Then, it publishes three ROS topics: bounding boxes around identified
objects, their categories, and confidence scores. To determine the 3D
coordinates of identified people, Covy obtains the depth information from the
RealSense depth camera and lays over the images published by YOLOv3. The
obtained 3D coordinates are then sent to the SORT [5] algorithm to track
people across multiple images.

SORT utilizes both the position and size of the bounding box for motion
estimation and data association using the Kalman filter and Hungarian method
respectively and outputs unique IDs for each identified pedestrian. After
tracking the identified pedestrians for 20 frames, their 3D coordinates are
averaged and the inter-person distance is calculated using the Euclidean
distance measure. If the distance between two individuals is less than the
specified threshold (e.g., $1.5\text{\,}\mathrm{m}$ Covy reports a breach.
This process is repeated pairwise for all the detected individuals. The result
is a list of breaches containing the different groups of non-compliant
pedestrians. Covy determines the largest group, computes its middle
coordinates and sends these to the navigation module (Figure 2). Since depth
information is only available at a short-range (our experiments show an
effective range of $6\text{\,}\mathrm{m}$), when no individuals are detected
Covy switches to MonoLoco [4] for long-range scanning (i.e., up to
$20\text{\,}\mathrm{m}$). MonoLoco processes RGB images as a set of 2D joints
using two pose detectors: Mask R-CNN [11], which works top-down, and
OpenPifPaf [16], which works bottom-up. Then, the MonoLoco [4] algorithm takes
these 2D joints as input and outputs the 3D locations, orientations, and
dimensions of the detected people together with localization uncertainty.
Finally, the system publishes an approximation of each pedestrian’s x, y, z
coordinates identified in the image along with their status and any
corresponding breaches. The navigation module then guides Covy towards the
largest breach density. Using this compound procedure Covy triple the
effective range of Intel RealSense at no additional costs.

####  3.2.2 Navigation

We have experimented with two different DRL algorithms to navigate Covy in
different environments. Deep Deterministic Policy Gradient (DDPG, Figure 3(a))
and Soft Actor-Critic (SAC, Figure 3(b)). These agents have actor-critic
network architectures that act in continuous action space [19] (Figure 3). The
environment is observed through 10 laser range findings emitted in a range
from -90°to 90°, 0°being the middle front of the robot. These laser scans are
concatenated with the angular and linear velocity and with the position and
heading angle of the robot relative to the target to form the input state of
the DRL agents (Figure 3, input($s_{t}$)|14). The position and heading of the
robot are determined using the rf2o [13] Lidar odometry approach which relies
purely on Lidar scan measurements to determine the robots change in position.
In DDPG, a tanh activation function is applied to the angular velocity output
layer to limit the range to [-2, 2], and a sigmoid activation function is
applied to the linear velocity output layer to limit the range to [0,0.2]. As
for SAC, it uses the tanh activation function and the clip operation to
similarly limit its linear and angular velocities. Since the laser readings
only record data in front of the robot only positive linear velocity is
considered (i.e., no backward motion is allowed or considered). Our DDPG
network configuration is based on [32, 7] with minor modifications to the
critic. As for SAC, we used the network from [33],and omitted the value
network, as mentioned in [10]. To train the DRL agents the following reward
function is:

$\vspace{-5pt}r(s_{t},a_{t})=\begin{cases}&r_{a}\text{ if }D_{t}<T\\\
&r_{c}\text{ if }min_{c}<L_{t}\\\ &r_{d1}(D_{t-1}-D_{t})\text{ if
}(D_{t-1}-D_{t})>0\\\ &r_{d2}\text{ if }(D_{t-1}-D_{t})\leq 0\end{cases}$

(a) DDPG architecture [32]

(b) SAC architecture [33, 10]

Figure 3: DRL models used for navigation

There are four different conditions for the reward system. If the robot
reaches the goal within a predefined time threshold $T$, it receives a big
positive reward. If the lidar reading $L_{t}$ is smaller than the minimum
allowed $min_{c}$ then a negative reward is given as the robot is about to
collide or has collided. Compared to the previous position, if the current
robot position is closer to the target, the robot gets a positive reward
proportional to its advancements. Otherwise, it is penalized.

Hybrid Autonomous Navigation. When testing the DRL navigation agents, we
noticed that the error in the Lidar odometry can become suddenly too large
causing the robot to lose track. Whenever this happens the navigation fails
and the robot is unable to reach its target.

To counter this unwanted behavior, we developed a hybrid navigation stack that
combines the DRL mapless navigation with a map-based localization algorithm,
namely, the Adaptive Monte Carlo Localization (AMCL) [8] method. First, the
SAC DRL agent navigates the robot towards a target using Lidar odometry. Then,
for every $X$ step (in our case, $X=20$) Covy compares the Lidar odometry
output to the pose estimation obtained from AMCL. If the difference between
the two positions is higher than a preset threshold, Covy reinitializes its
position and orientation based on the output of the AMCL algorithm.

##  4 Experimental Evaluation

###  4.1 Vision System

Two sets of experiments were conducted to evaluate Covy’s vision system –
person’s location estimation accuracy and classification accuracy of breaches
in social distancing. For the former, a person moves away from the camera by
$1\text{\,}\mathrm{m}$, and for the latter, two pedestrians stood at various
coordinates in the scene. We ensured that the people were in the field of view
of the camera and took 50 pictures at each location. For the classification
experiments, balanced data was ensured. These experiments were conducted in a
simulated and real environment and repeated until the camera could not detect
any pedestrian. Finally, we profiled the execution of these algorithms on
Jetson Nano and Jetson Xavier NX.

####  4.1.1  Localization

Figure 4 shows the average localization error (ALE) of Covy’s vision RGB-D and
RGB localization methods. We can observe that the RGB-based method has a range
2.4 x and 4.3 x longer than RGB-D in the real and simulated environment,
respectively. However, for proximity scanning, the RGB-D method has a higher
localization accuracy. Therefore, by combining these two coacting methods Covy
can localize people at a long-range and with increased accuracy.

(a) RGBD simulation

(b) RGB simulation

(c) RGBD Real

(d) RGB Real

Figure 4: Average localization error (ALE) with confidence interval as a
function of distance – RGBD and RGB based system.

####  4.1.2 Accuracy of Classification of Breaches

This experiment compares the performance of the RGB-D and RGB-based vision
systems in detecting social distancing violations. We treat the problem as a
binary classification task and evaluate the detection accuracy, recall, and
precision. Figure 6 shows the confusion matrices for the RGB-D and RGB breach
detection, and Table 1 compares the accuracy, precision, and recall between
them. First, we notice a drop in the performance of both methods when moving
from simulated to the real world. This is mainly due to the increase in the
ALE (as shown in Figure 4). However, while the RGB-D method performs better in
simulation, the margin in performance between the two methods shrinks in
reality. This is due to the ratio at which the ALE changes in the simulated
and real environment of both methods. Overall, both algorithms maintained an
accuracy equal to 82%. Qualitative results of both methods are shown in Figure
5. Combined, these results show the promising ability of these approaches in
recognizing breaches in social distancing.

(a) RGBD qualitative results

(b) RGB qualitative results

Figure 5: Example of Covy’s vision modules (i.e., RGB and RGB-D) and detection accuracy of breaches. Method |  Accuracy (%) |  Precision (%) |  Recall (%) | Env.
---|---|---|---|---
RGB-D | 96 | 98 | 95 | Sim.
RGB | 92 | 96 | 88 | Sim.
RGB-D | 82 | 90 | 72 | Real
RGB | 82 | 93 | 70 | Real
Table 1: Accuracy of classifying social distancing breaches

(a) RGB-D simulation

(b) RGB simulation

(c) RGB-D real env.

(d) RGB real env.

Figure 6: Accuracy in Detection of Breaches Using Covy’s Vision Modules (RGB
and RGB-D) in simulated and real environment.

####  4.1.3 Hardware Requirements

Table 2: Performance comparison of breach detection algorithms on different hardware. Processor | Algorithm |  CPU (%) |  GPU (%) |  Memory (GB)
---|---|---|---|---
Nano | Idle | 15 | 3 | 1.6/4.1
| RGB-D | 99 | 83 | 2.7/4.1
| RGB | NA | NA | NA
Xavier NX | Idle | 14 | 1 | 2.5/8
| RGB-D | 58 | 15 | 3.3/8
| RGB | 39 | 59 | 7.2/8
| Covy’s vision | 70 | 63 | 7.4/8

After testing the accuracy of the two breach detection systems, we deployed
them on the intended edge devices to profile their execution. We tested the
performance in terms of CPU, GPU, and memory usage. Firstly, we measured the
resources utilization levels at an idle condition. Then, we let the model
reach its steady-state behavior by running it for a few minutes. Finally, 100
performance measurements were taken and averaged out (Table 2).

Jetson Nano was able to run the RGB-D detection system based on Yolov3 [26],
but reached maximum CPU utilization ($\approx 99\%$) and very high GPU
utilization (83 %). Moreover, Jetson Nano was unable to run the resource-
intensive RGB-based detection algorithm which runs multiple DL models to
estimate the 3D coordinates of people in the scene.

Jetson Xavier NX was able to run both systems adequately keeping peak GPU
utilization (59%) and peak CPU utilization (58%) at acceptable levels.
However, the RBG system consumed most of the available memory averaging 7.2 GB
RAM usage out of the total 8.

Considering that the individual performances were favorable, we tested Covy’s
vision algorithm as a whole on Jetson Xavier NX. The overall performance
seemed promising, with the highest average utilization reaching 70% for CPU,
63% for GPU utilization, and 7.4 GB for RAM usage.

###  4.2 Navigation

Figure 7:  Training in environment with static and dynamic obstacles. Table 3: DDPG vs SAC. Results averaged over 100 episodes.  DRL |  Failure (%) (collision/lost) |  Average Speed (m/s) | Env.
---|---|---|---
DDPG | 13 (8 / 5) | 0.125 | Sim.
DDPG | 26 (15 / 11) | 0.099 | Real
SAC | 8 (6 / 2) | 0.17 | Sim.
SAC | 20 (8 / 12) | 0.13 | Real
Hybrid | 7 (7 / 0) | 0.046 | Sim.
Hybrid | 10 (10 / 0) | 0.057 | Real

Covy’s navigation is evaluated using three metrics: the time to goal, the
distance to the goal and the failure rate which includes collisions and
deadlocks.

####  4.2.1 DRL Agents Training

We trained the DDPG and SAC models on a computer equipped with an NVIDIA
GeForce GTX 1060, 16 GB of RAM, and an Intel Core i7-8750H processor. The
models were trained for 4000 episodes on a Jetbot robot model in a
$4\times$4\text{\,}\mathrm{m}$^{2}$ room-like simulated environment with
either: no obstacles, static obstacles, or dynamic obstacles [15]. After
training completion, we tested the models’ capabilities in a simulated and
real environment by sampling 35 random configurations from the aforementioned
environments.

Figure 7 shows the cumulative rewards obtained by DDPG and SAC during training
in an environment with static and dynamic obstacles where each data point
represents the average reward over 25 episodes. After $\approx 350$ episodes,
SAC surpasses DDPG in performance constantly. SAC reached a maximum average
reward of approximately 3000, double that of DDPG. We hypothesize that as SAC
is a stochastic policy, it is able to explore better the environment and
therefore collect higher rewards.

####  4.2.2 Navigation Accuracy

From Table 3 we see that the SAC model performs better than the DDPG model in
terms of the failure rate. Additionally, SAC is faster than DDPG in reaching
the target: we suspect that the stochastic nature of SAC provides better
exploration and allows the model to find an optimal path, whereas DDPG is
deterministic. An interesting observation is that both DDPG and SAC can get
lost (or end up in a deadlock) in simulated and real environments. We
conjecture that this is due to the use of Lidar odometry which can produce
inconsistent measurement when the robot moves fast. However, our hybrid
approach is designed to overcome this limitation and performs best with
respect to the failure rate at the cost of slower navigation.

##  5 Conclusion and Future Work

Covy is a prototype designed to test a compound vision system and different
navigation stacks. The target application is to promote social distancing
practice during a pandemic (e.g., COVID-19). The compound algorithm that Covy
uses extends the range of depth of the Intel RealSense D435i camera from an
effective range of $6\text{\,}\mathrm{m}$ to 16$+$ m. Covy navigates its
surroundings autonomously using a hybrid navigation stack that combines a SAC
(DRL) agent with the probabilistic localization method AMCL. compared to a
pure DRL-based navigation stack, Covy’s stack performas better in navigating
in realistic and simulated environments with static and dynamic obstacles.
Next step is to develop a complete swarm of Covy robots and target other
applications such as alerting littering individuals, finding objects of
interest, e.g., security of airports.

## References

  * [1] Jetbot: An AI driven robot.  URL https://www.waveshare.com/jetbot-ai-kit.htm.
  * [2] Rplidar A2: a laser range scanner.  URL https://www.slamtec.com/en/Lidar/A2.
  * [3] Zed 2: An AI stereo camera.  URL https://www.stereolabs.com/zed-2i/.
  * Bertoni et al. [2019] Lorenzo Bertoni, Sven Kreiss, and Alexandre Alahi.  Monoloco: Monocular 3d pedestrian localization and uncertainty estimation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 6861–6871, 2019.
  * Bewley et al. [2016] Alex Bewley, Zongyuan Ge, Lionel Ott, Fabio Ramos, and Ben Upcroft.  Simple online and realtime tracking.  _2016 IEEE International Conference on Image Processing (ICIP)_ , Sep 2016.  doi: 10.1109/icip.2016.7533003.  URL http://dx.doi.org/10.1109/ICIP.2016.7533003.
  * Chen et al. [2021] Zhiming Chen, Tingxiang Fan, Xuan Zhao, Jing Liang, Cong Shen, Hua Chen, Dinesh Manocha, Jia Pan, and Wei Zhang.  Autonomous social distancing in urban environments using a quadruped robot.  _IEEE Access_ , 9:8392–8403, 2021.
  * Costa de Jesus et al. [2021] Junior Costa de Jesus, Victor Kich, Alisson Kolling, Ricardo Grando, Marco Cuadros, and Daniel Fernando Gamarra.  Soft actor-critic for navigation of mobile robots.  _Journal of Intelligent & Robotic Systems_, 102, 06 2021.  doi: 10.1007/s10846-021-01367-5.
  * Fox et al. [1999] Dieter Fox, Wolfram Burgard, Frank Dellaert, and Sebastian Thrun.  Monte carlo localization: Efficient position estimation for mobile robots.  _AAAI/IAAI_ , 1999(343-349):2–2, 1999.
  * Haarnoja et al. [2018a] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In _International conference on machine learning_ , pages 1861–1870. PMLR, 2018a.
  * Haarnoja et al. [2018b] Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al.  Soft actor-critic algorithms and applications.  _arXiv preprint arXiv:1812.05905_ , 2018b.
  * He et al. [2017] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2961–2969, 2017.
  * Huang et al. [2020] Hen-Wei Huang, peter chai, Claas Ehmke, Gene Merewether, Fara Dadabhoy, Annie Feng, Akhil John Thomas, Canchen Li, Marco da Silva, Marc H Raibert, et al.  Agile mobile robotic platform for contactless vital signs monitoring.  2020\.
  * Jaimez et al. [2016] Mariano Jaimez, Javier G. Monroy, and Javier Gonzalez-Jimenez.  Planar odometry from a radial laser scanner. a range flow-based approach.  In _2016 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 4479–4485, 2016.  doi: 10.1109/ICRA.2016.7487647.
  * Kahn et al. [2018] Gregory Kahn, Adam Villaflor, Bosen Ding, Pieter Abbeel, and Sergey Levine.  Self-supervised deep reinforcement learning with generalized computation graphs for robot navigation.  In _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 5129–5136. IEEE, 2018.
  * Koenig and Howard [2004] Nathan Koenig and Andrew Howard.  Design and use paradigms for gazebo, an open-source multi-robot simulator.  In _2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)(IEEE Cat. No. 04CH37566)_ , volume 3, pages 2149–2154. IEEE, 2004.
  * Kreiss et al. [2019] Sven Kreiss, Lorenzo Bertoni, and Alexandre Alahi.  Pifpaf: Composite fields for human pose estimation.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 11977–11986, 2019.
  * Kulhánek et al. [2019] Jonáš Kulhánek, Erik Derner, Tim De Bruin, and Robert Babuška.  Vision-based navigation using deep reinforcement learning.  In _2019 European Conference on Mobile Robots (ECMR)_ , pages 1–8. IEEE, 2019.
  * Kulhánek et al. [2021] Jonáš Kulhánek, Erik Derner, and Robert Babuška.  Visual navigation in real-world indoor environments using end-to-end deep reinforcement learning.  _IEEE Robotics and Automation Letters_ , 6(3):4345–4352, 2021.
  * Lillicrap et al. [2015] Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra.  Continuous control with deep reinforcement learning.  _arXiv preprint arXiv:1509.02971_ , 2015.
  * Long et al. [2018] Pinxin Long, Tingxiang Fan, Xinyi Liao, Wenxi Liu, Hao Zhang, and Jia Pan.  Towards optimally decentralized multi-robot collision avoidance via deep reinforcement learning.  In _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 6252–6259. IEEE, 2018.
  * Lv et al. [2020] Zhihan Lv, Jaime Lloret Mauri, and Houbing Song.  Editorial rgb-d sensors and 3d reconstruction.  _IEEE Sensors Journal_ , 20(20):11751–11752, 2020\.
  * Majid et al. [2021] Amjad Yousef Majid, Serge Saaybi, Tomas van Rietbergen, Vincent Francois-Lavet, R Venkatesha Prasad, and Chris Verhoeven.  Deep reinforcement learning versus evolution strategies: A comparative survey.  _arXiv preprint arXiv:2110.01411_ , 2021.
  * Neupane et al. [2021] Chiranjivi Neupane, Anand Koirala, Zhenglin Wang, and Kerry Brian Walsh.  Evaluation of depth cameras for use in fruit localization and sizing: Finding a successor to kinect v2.  _Agronomy_ , 11(9):1780, 2021.
  * Nguyen et al. [2020] Cong T. Nguyen, Yuris Mulya Saputra, Nguyen Van Huynh, Ngoc-Tan Nguyen, Tran Viet Khoa, Bui Minh Tuan, Diep N. Nguyen, Dinh Thai Hoang, Thang X. Vu, Eryk Dutkiewicz, and et al.  A comprehensive survey of enabling and emerging technologies for social distancing—part i: Fundamentals and enabling technologies.  _IEEE Access_ , 8:153479–153507, 2020.  ISSN 2169-3536.  doi: 10.1109/access.2020.3018140.  URL http://dx.doi.org/10.1109/ACCESS.2020.3018140.
  * Quigley et al. [2009] Morgan Quigley, Ken Conley, Brian Gerkey, Josh Faust, Tully Foote, Jeremy Leibs, Rob Wheeler, and Andrew Ng.  Ros: an open-source robot operating system.  volume 3, 01 2009.
  * Redmon and Farhadi [2018] Joseph Redmon and Ali Farhadi.  Yolov3: An incremental improvement.  _arXiv preprint arXiv:1804.02767_ , 2018.
  * Rezaei and Azarmi [2020] Mahdi Rezaei and Mohsen Azarmi.  Deepsocial: Social distancing monitoring and infection risk assessment in covid-19 pandemic.  _Applied Sciences_ , 10(21):7514, Oct 2020.  ISSN 2076-3417.  doi: 10.3390/app10217514.  URL http://dx.doi.org/10.3390/app10217514.
  * Sathyamoorthy et al. [2020] Adarsh Jagan Sathyamoorthy, Utsav Patel, Yash Ajay Savle, Moumita Paul, and Dinesh Manocha.  Covid-robot: Monitoring social distancing constraints in crowded scenarios.  _CoRR_ , 2020.
  * Schulman et al. [2017] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Shen et al. [2020] Yang Shen, Dejun Guo, Fei Long, Luis A Mateos, Houzhu Ding, Zhen Xiu, Randall B Hellman, Adam King, Shixun Chen, Chengkun Zhang, et al.  Robots under covid-19 pandemic: A comprehensive survey.  _Ieee Access_ , 2020.
  * Surmann et al. [2020] Hartmut Surmann, Christian Jestel, Robin Marchel, Franziska Musberg, Houssem Elhadj, and Mahbube Ardani.  Deep reinforcement learning for real autonomous mobile robot navigation in indoor environments.  _arXiv preprint arXiv:2005.13857_ , 2020.
  * Tai et al. [2017] Lei Tai, Giuseppe Paolo, and Ming Liu.  Virtual-to-real deep reinforcement learning: Continuous control of mobile robots for mapless navigation.  In _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 31–36. IEEE, 2017.
  * Xiang et al. [2019] Jiaqi Xiang, Qingdong Li, Xiwang Dong, and Zhang Ren.  Continuous control with deep reinforcement learning for mobile robot navigation.  In _2019 Chinese Automation Congress (CAC)_ , pages 1501–1506. IEEE, 2019.