# Switching Checkerboards

David Ellison  RMIT University, School of Science, Melbourne, Australia
Bertrand Jouve  LISST UMR5193, Toulouse University, CNRS, France  Lewi Stone
RMIT University, School of Science, Melbourne, Australia

###### Abstract

In order to study $\mathbf{M}(R,C)$, the set of binary matrices with fixed row
and column sums $R$ and $C$, we consider sub-matrices of the form
$\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}$ and $\begin{pmatrix}0&1\\\
1&0\end{pmatrix}$, called positive and negative checkerboard respectively. We
define an oriented graph of matrices $G(R,C)$ with vertex set
$\mathbf{M}(R,C)$ and an arc from $\mathbf{A}$ to $\mathbf{A}^{\prime}$
indicates you can reach $\mathbf{A}^{\prime}$ by switching a negative
checkerboard in $\mathbf{A}$ to positive. We show that $G(R,C)$ is a directed
acyclic graph and identify classes of matrices which constitute unique sinks
and sources of $G(R,C)$. Given
$\mathbf{A},\mathbf{A}^{\prime}\in\mathbf{M}(R,C)$, we give necessary
conditions and sufficient conditions on
$\mathbf{M}=\mathbf{A}^{\prime}-\mathbf{A}$ for the existence of a directed
path from $\mathbf{A}$ to $\mathbf{A}^{\prime}$.

We then consider the special case of $\mathbf{M}(\mathcal{D})$, the set of
adjacency matrices of graphs with fixed degree distribution $\mathcal{D}$. We
define $G(\mathcal{D})$ accordingly by switching negative checkerboards in
symmetric pairs. We show that $Z_{2}$, an approximation of the spectral radius
$\lambda_{1}$ based on the second Zagreb index, is non-decreasing along arcs
of $G(\mathcal{D})$. Also, $\lambda_{1}$ reaches its maximum in
$\mathbf{M}(\mathcal{D})$ at a sink of $G(\mathcal{D})$. We provide simulation
results showing that applying successive positive switches to an Erdős-Rényi
graph can significantly increase $\lambda_{1}$.

######  Keywords.

Graph theory, binary matrices, spectral radius, graph modifications

## Introduction

In the study of diffusion processes along a network, the largest eigenvalue of
the adjacency matrix, called the spectral radius of the network and denoted by
$\lambda_{1}$, plays a critical role. For instance, in epidemic models, having
a reproduction number $R_{0}$ greater or smaller than $1/\lambda_{1}$
determines whether the epidemic will die out or keep spreading. Also, in the
problem of synchronisation of coupled oscillators on a network, a key
threshold criterion for the stability of the synchronised solution is based on
$\lambda_{1}$. The largest eigenvalue similarly affects other percolation
processes such as wildfires or rumors spreading in social networks and is also
of interest in the study of random matrices.

The parameter which has the greatest impact on the value of $\lambda_{1}$ is
the degree distribution of the network. Indeed, some lower bounds and
approximations of $\lambda_{1}$ are entirely determined by the degree
distribution [14]. Such approximations can be very precise for the vast
majority of cases, but tend to become wildly inaccurate in extreme cases of
networks with very particular topological properties. In this article, we
consider the degree distribution fixed in order to analyse how the topology of
the network affects $\lambda_{1}$. The study of matrices with fixed degree
distribution has applications to epidemic models [6], synchronisation problems
[11], ecology [5], LT codes [8] and many other areas. Once the degree
distribution is fixed, the degree assortativity is the most important
parameter of real networks [16, 12].

When working with a fixed degree distribution, we rely on a basic operation
which consists in switching the $1$s and $0$s in a $2\times 2$ sub-matrix of
the adjacency matrix of the form $\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}$ or
$\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}$, called a checkerboard. Any such
switching amounts to rewiring two edges in a way that leaves the degree
distribution invariant. This allows us to visualise the set of binary matrices
with a given degree distribution as the vertex set of a graph where two
matrices are adjacent if they differ by one switch. It was shown in [15] that
this graph of matrices is connected.

In this paper, we call the two above sub-matrices positive and negative
checkerboards. This polarisation of checkerboards defines an orientation of
the edges of the graph of matrices. In Section 1, we introduce the basic
definitions surrounding checkerboards. Then, in Section 2, we show that the
oriented graph of matrices is a directed acyclic graph and discuss its sources
and sinks as well as when $\mathbf{A}^{\prime}$ can be reached from
$\mathbf{A}$ by following an oriented path. Finally, in Section 3, we describe
how the second Zagreb index, an approximation of $\lambda_{1}$, evolves
throughout the graph of matrices. We then show that $\lambda_{1}$ reaches its
global maximum at a sink of the graph of matrices and describe the evolution
of $\lambda_{1}$ through simulations. The proofs of two theorems from Section
2 have been placed in the appendix for the sake of improving readability. In
order to maximise the generality of our results, we have considered non-
symmetric binary matrices with fixed row and column sums in all sections
except Section 3, where we consider only adjacency matrices. Note that a non-
symmetric matrix $\mathbf{A}$ can be interpreted as a characteristic sub-
matrix of $\mathbf{M}=\begin{pmatrix}0&\mathbf{A}\\\
{}^{t}\mathbf{A}&0\end{pmatrix}$, where $\mathbf{M}$ is the adjacency matrix
of a bipartite graph.

##  1 Positive and Negative Switches

Given a $(0,1)$-matrix $\mathbf{A}$, a _checkerboard_ of $\mathbf{A}$ is a
$2\times 2$ sub-matrix of $\mathbf{A}$ of the form either
$\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}$ or $\begin{pmatrix}0&1\\\
1&0\end{pmatrix}$. A checkerboard found on rows $i$ and $j$ and columns $k$
and $l$, with $i<j$ and $k<l$, is said to have _coordinates_ $(i,j,k,l)$. A
_unitary checkerboard_ is a checkerboard of area $1$ and has coordinates
$(i,i+1,k,k+1)$. _Switching_ a checkerboard refers to replacing one form with
the other. Note that row and column sums are invariant under this operation.
The following result was shown by Ryser in 1957:

######  Theorem 1 ([15]).

Given two matrices $\mathbf{A}$ and $\mathbf{A}^{\prime}$ in the class of
$(0,1)$-matrices having specified row and column sums, one can pass from
$\mathbf{A}$ to $\mathbf{A}^{\prime}$ by a finite sequence of switches.

This property makes switching checkerboards an essential tool for studying
classes of matrices with fixed row and column sums as well as classes of
graphs with fixed degree distributions. Applying successive random switches to
a binary matrix creates a Markov chain which visits all possible matrices with
the same row and column sums. This Markov chain can then be used to sample
randomly matrices with a fixed degree distribution [2].

In this paper, we attribute a sign to checkerboards and switches: a
checkerboard of the form $\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}$ is said to
be _positive_ while a checkerboard of the form $\begin{pmatrix}0&1\\\
1&0\end{pmatrix}$ is said to be _negative_. A _positive switch_ corresponds to
replacing a negative checkerboard with a positive one while a _negative
switch_ is the reverse. We define a _switching matrix_ $\mathbf{C}_{i,j,k,l}$,
with $i<j$ and $k<l$, as having coefficients $c_{ik}=c_{jl}=1$,
$c_{il}=c_{kj}=-1$ and 0 elsewhere. Thus, a positive (resp. negative) switch
of coordinates $(i,j,k,l)$ corresponds to adding (resp. subtracting)
$\mathbf{C}_{i,j,k,l}$. Note that $\mathbf{C}_{i,j,k,l}=\sum_{i\leq p<j,k\leq
q<l}\mathbf{C}_{p,p+1,q,q+1}$; i.e. any switching matrix is a sum of _unitary
switching matrices_. Note also that the unitary switching matrices are
linearly independent and form a basis of the space of zero-sum (for rows and
columns) matrices.

##  2 Oriented Graph of Matrices

###  2.1 Sources and Sinks

Given vectors $R\in\mathbb{N}^{p}$ and $C\in\mathbb{N}^{q}$, let
$\mathcal{M}(R,C)$ denote the set of binary matrices with row and column sums
$R$ and $C$. We assume $\mathcal{M}(R,C)\neq\emptyset$. Let $G(R,C)$ denote
the oriented graph with vertex set $\mathcal{M}(R,C)$ and there is an arc from
$\mathbf{A}$ to $\mathbf{A}^{\prime}$ if $\mathbf{A}^{\prime}$ can be obtained
from $\mathbf{A}$ with a positive switch.

As mentioned in the introduction, the undirected graph underlying $G(R,C)$,
called _interchange graph_ in [4], is well-studied in the literature. In [2],
multiple algorithms which generate random networks with a fixed degree
distribution are based on this graph. Our purpose here, however, is to focus
on properties which derive from the orientation.

######  Proposition 1.

The graph $G(R,C)$ is connected and acyclic.

###### Proof.

For $\mathbf{A}\in\mathcal{M}(R,C)$, let $I(\mathbf{A})=\sum_{i,j}ija_{ij}$.
Let $\mathbf{A}^{\prime}$ be obtained from $\mathbf{A}$ with a positive switch
of coordinates $(i,j,k,l)$ where $i<j$ and $k<l$; i.e there is an arc from
$\mathbf{A}$ to $\mathbf{A}^{\prime}$ in $G(R,C)$. Then,

$I(\mathbf{A}^{\prime})-I(\mathbf{A})=I(\mathbf{C}_{i,j,k,l})=(i-j)(k-l)>0.$

Since $I$ increases along arcs, and therefore along directed paths, $G(R,C)$
is acyclic.

The connectedness property is Ryser’s theorem: a sequence of (positive or
negative) switches leading from $\mathbf{A}$ to $\mathbf{A}^{\prime}$
corresponds to an undirected path in $G(R,C)$. ∎

Recall that directed acyclic graphs have _sources_ and _sinks_ which are
vertices with zero in-degree and out-degree, respectively. In $G(R,C)$,
sources and sinks are, respectively, matrices with no positive checkerboards
and no negative checkerboards.

A matrix $\mathbf{A}\in\mathcal{M}(R,C)$ is said to be _nested_ (resp. anti-
nested) if the sequence $01$ (resp. $10$) does not appear in any row or
column; i.e if the 1s occur before the $0$s (resp. $0$s before $1$s) in every
row and column. Nested graphs have important applications, in particular in
ecology [5]. For our purpose, the nested case is both trivial and
theoretically important, as indicated by the following proposition and its
corollary.

######  Proposition 2.

If $R$ and $C$ are non-increasing, then $\mathbf{A}\in\mathcal{M}(R,C)$ is
nested if and only if it has no checkerboards.

###### Proof.

If $\mathbf{A}$ is nested, the sequence $01$ does not appear in any row or
column of $\mathbf{A}$. Hence, there is no checkerboard in $\mathbf{A}$.

Conversely, if $\mathbf{A}$ is not nested, there is a row or column containing
the sequence $01$. Say it is a row; since the column with the $0$ has degree
at least equal to that with the $1$, there is another row containing $10$ in
the same two columns. Hence, there is a checkerboard. ∎

######  Corollary 1.

The set $\mathcal{M}(R,C)$ is a singleton if and only if it includes a matrix
which becomes nested after reordering its rows and columns by non-increasing
degree.

###### Proof.

This result derives from 2 by using Theorem 1 and the fact that the number of
checkerboards in a matrix is invariant under row and column permutation. ∎

We define a _zebra_ as a matrix in $\mathcal{M}(R,C)$ which is the sum of two
matrices, one nested and one anti-nested. The name zebra refers to the three
stripes formed by the $1$s and $0$s in the matrix, as shown in Example 1. We
say that a zebra is _split vertically_ (resp. _horizontally_) if no column
(resp. row) has $1$s from both the nested and anti-nested parts (see Example
1). In other words, a split zebra can be split along a vertical (or
horizontal) axis so that the left (resp. top) half is nested while the right
(resp. bottom) half is anti-nested. Note that the two "halves" need not be of
equal size. Also, we define an _anti-zebra_ as the complement of the vertical
reflection of a zebra; i.e. $b_{ij}=1-a_{n-i,j}$ (see Example 1).

######  Example 1 (Zebras and Anti-zebras).

The matrices $\mathbf{A}$ and $\mathbf{A}^{\prime}$ are zebras. In
$\mathbf{A}$, the nested and anti-nested parts overlap horizontally and
vertically, so $\mathbf{A}$ is not split. Meanwhile, $\mathbf{A}^{\prime}$ is
a horizontally split zebra, where the top three rows are nested and the bottom
three anti-nested. Matrices $\mathbf{B}$ and $\mathbf{B}^{\prime}$ are anti-
zebras which are the complement of the vertical reflection of $\mathbf{A}$ and
$\mathbf{A}^{\prime}$, so $\mathbf{B}^{\prime}$ is horizontally split and
$\mathbf{B}$ is not split.

$\mathbf{A}=\begin{pmatrix}1&1&1&1&1&0\\\ 1&1&1&1&0&0\\\ 1&1&0&0&0&1\\\
1&0&0&0&0&1\\\ 1&0&0&0&1&1\\\ 0&0&1&1&1&1\end{pmatrix}\hskip
28.45274pt\text{and}\hskip 28.45274pt\mathbf{B}=\begin{pmatrix}1&1&0&0&0&0\\\
0&1&1&1&0&0\\\ 0&1&1&1&1&0\\\ 0&0&1&1&1&0\\\ 0&0&0&0&1&1\\\
0&0&0&0&0&1\end{pmatrix}$ $\mathbf{A}^{\prime}=\begin{pmatrix}1&1&1&1&1&0\\\
1&1&1&1&0&0\\\ 1&1&0&0&0&0\\\ 0&0&0&0&0&1\\\ 0&0&0&0&1&1\\\
0&0&1&1&1&1\end{pmatrix}\hskip 28.45274pt\text{and}\hskip
28.45274pt\mathbf{B}^{\prime}=\begin{pmatrix}1&1&0&0&0&0\\\ 1&1&1&1&0&0\\\
1&1&1&1&1&0\\\ 0&0&1&1&1&1\\\ 0&0&0&0&1&1\\\ 0&0&0&0&0&1\end{pmatrix}$

Like nested graphs, zebras and anti-zebras can be characterised by the absence
of certain sub-matrices:

######  Claim 1.

If we exclude full (resp. empty) rows and columns, zebras (resp. anti-zebras)
are exactly the matrices without $\begin{pmatrix}0&1\\\ *&0\end{pmatrix}$ or
$\begin{pmatrix}0&*\\\ 1&0\end{pmatrix}$ (resp. $\begin{pmatrix}*&1\\\
1&0\end{pmatrix}$ or $\begin{pmatrix}0&1\\\ 1&*\end{pmatrix}$) sub-matrices,
where $*$ denotes either $0$ or $1$.

###### Proof.

The absence of those sub-matrices derives from the geometry of the zebra. The
converse, which is not needed to prove the theorem, we leave as an exercise. ∎

Note that the forbidden sub-matrices include negative checkerboards; thus
zebras and anti-zebras form sinks of $G(R,C)$.

######  Claim 2.

Split zebras, split anti-zebras and their complements include at most one of
the following vectors as sub-matrix: $\begin{pmatrix}1&0&1\end{pmatrix}$,
$\begin{pmatrix}0&1&0\end{pmatrix}$, $\begin{pmatrix}1\\\ 0\\\ 1\end{pmatrix}$
and $\begin{pmatrix}0\\\ 1\\\ 0\end{pmatrix}$. In particular, horizontally
split zebras have no $\begin{pmatrix}1&0&1\end{pmatrix}$,
$\begin{pmatrix}0&1&0\end{pmatrix}$ and $\begin{pmatrix}0\\\ 1\\\
0\end{pmatrix}$ sub-matrix.

###### Proof.

This derives from the geometry of the split zebra and anti-zebra. ∎

######  Theorem 2.

If $\mathcal{M}(R,C)$ contains a split zebra or a split anti-zebra, then that
split zebra or anti-zebra is the only element of $\mathcal{M}(R,C)$ without
negative checkerboards; i.e it is the unique sink in $G(R,C)$.

(Proof in the appendix)

######  Corollary 2.

Let $\mathbf{B}\in\mathcal{M}(R,C)$ be a split zebra or a split anti-zebra.
For all $\mathbf{A}\in\mathcal{M}(R,C)$, $\mathbf{B}$ can be reached from
$\mathbf{A}$ via a sequence of positive switches.

######  Corollary 3.

If $\mathcal{M}(R,C)$ contains the complement of a split zebra or a split
anti-zebra, then it is the unique source in $G(R,C)$.

###### Proof.

The complement of a unique sink is a unique source. ∎

###  2.2 Adapting Ryser’s Theorem to the Oriented Graph of Matrices

It follows from Theorem 1 that the undirected version of $G(R,C)$ is
connected. Having introduced an orientation naturally raises the question of
when can a matrix $\mathbf{A}^{\prime}$ be reached from matrix $\mathbf{A}$
via a sequence of positive switches. The remainder of this section is devoted
to answering this question. We will denote by
$\mathbf{A}\rightarrow\mathbf{A}^{\prime}$ that there is a directed path
connecting $\mathbf{A}$ to $\mathbf{A}^{\prime}$ in $G(R,C)$.

######  Proposition 3.

Let $R\in\mathbb{N}^{p}$, $C\in\mathbb{N}^{q}$, let
$\mathbf{A},\mathbf{A}^{\prime}\in\mathcal{M}(R,C)$ and let
$\mathbf{M}=\mathbf{A}^{\prime}-\mathbf{A}$. If
$\mathbf{A}\rightarrow\mathbf{A}^{\prime}$, then $\mathbf{M}$ is a sum of
unitary switching matrices; i.e.

  1. (i)

$\exists!\mathbf{T}\in\mathcal{M}_{p-1,q-1}(\mathbb{N})$:
$\mathbf{M}=\sum_{i,k}t_{ik}\mathbf{C}_{i,i+1,k,k+1}$.

###### Proof.

Each positive switch corresponds to adding a switching matrix and each
switching matrix is a sum of unitary switching matrices. The unicity of
$\mathbf{T}$ follows from the linear independence of the unitary switching
matrices. ∎

######  Remark 1.

  * •

Note that $\mathbf{T}$ is uniquely determined by $\mathbf{M}$, even when
multiple switching sequences lead from $\mathbf{A}$ to $\mathbf{A}^{\prime}$
(see Example 2).

  * •

Given $\mathbf{M}=\mathbf{A}^{\prime}-\mathbf{A}$ which satisfies condition
$(i)$, if we switch a negative checkerboard in $\mathbf{A}$ to positive, then
the coefficients of $\mathbf{T}$ inside a rectangle corresponding to the
checkerboard are all decreased by $1$. The new matrix $\mathbf{M}$ still
satisfies condition $(i)$ if and only if the coefficients of $\mathbf{T}$ all
remain non-negative. Reaching $\mathbf{A}^{\prime}$ via successive switches
corresponds to reducing $\mathbf{T}$ to $0$ in this fashion. (See examples
below for more details.)

We denote by $(i)$ the necessary condition given in 3. Unfortunately,
condition $(i)$ is not sufficient to ensure
$\mathbf{A}\rightarrow\mathbf{A}^{\prime}$, as shown in Example 3.

######  Example 2.

Let $\mathbf{A}=\begin{pmatrix}0&0&1\\\ 1&0&0\\\ 1&1&0\end{pmatrix}$ and
$\mathbf{A}^{\prime}=\begin{pmatrix}1&0&0\\\ 0&1&0\\\ 1&0&1\end{pmatrix}$.
There are two directed paths from $\mathbf{A}$ to $\mathbf{A}^{\prime}$:
$\mathbf{A}\rightarrow\begin{pmatrix}1&0&0\\\ 0&0&1\\\
1&1&0\end{pmatrix}\rightarrow\mathbf{A}^{\prime}$ and
$\mathbf{A}\rightarrow\begin{pmatrix}0&1&0\\\ 1&0&0\\\
1&0&1\end{pmatrix}\rightarrow\mathbf{A}^{\prime}$. In the first case, we add
the switching matrices $\mathbf{C}_{1,2,1,3}=\begin{pmatrix}1&0&-1\\\
-1&0&1\\\ 0&0&0\end{pmatrix}$ followed by
$\mathbf{C}_{2,3,2,3}=\begin{pmatrix}0&0&0\\\ 0&1&-1\\\ 0&-1&1\end{pmatrix}$.
In the second case, we add $\mathbf{C}_{1,3,2,3}=\begin{pmatrix}0&1&-1\\\
0&0&0\\\ 0&-1&1\end{pmatrix}$ and
$\mathbf{C}_{1,2,1,2}=\begin{pmatrix}1&-1&0\\\ -1&1&0\\\ 0&0&0\end{pmatrix}$.
We have $\mathbf{M}=\mathbf{A}^{\prime}-\mathbf{A}=\begin{pmatrix}1&0&-1\\\
-1&1&0\\\
0&-1&1\end{pmatrix}=\mathbf{C}_{1,2,1,3}+\mathbf{C}_{2,3,2,3}=\mathbf{C}_{1,3,2,3}+\mathbf{C}_{1,2,1,2}$.
In both of these sums, the first switching matrix can be split into two
unitary switching matrices. So $\mathbf{M}$ is the sum of three unitary
switching matrices:
$\mathbf{M}=\mathbf{C}_{1,2,1,2}+\mathbf{C}_{1,2,2,3}+\mathbf{C}_{2,3,2,3}$.
Thus $\mathbf{M}$ satisfies condition $(i)$ with
$\mathbf{T}=\begin{pmatrix}1&1\\\ 0&1\end{pmatrix}$.

######  Example 3.

Let $\mathbf{A}=\begin{pmatrix}0&0&0&1\\\ 1&1&0&1\\\ 1&0&1&1\\\
1&0&0&0\end{pmatrix}$ and $\mathbf{A}^{\prime}=\begin{pmatrix}1&0&0&0\\\
1&0&1&1\\\ 1&1&0&1\\\ 0&0&0&1\end{pmatrix}$. We have
$\mathbf{M}=\mathbf{A}^{\prime}-\mathbf{A}=\begin{pmatrix}1&0&0&-1\\\
0&-1&1&0\\\ 0&1&-1&0\\\ -1&0&0&1\end{pmatrix}$, which satisfies condition
$(i)$ with
$\mathbf{T}=\begin{pmatrix}1&1&1\\\ 1&0&1\\\ 1&1&1\end{pmatrix}$. Matrix
$\mathbf{A}$ has only one negative checkerboard, with coordinates $(1,4,1,4)$.
After switching it to positive, reaching $\mathbf{A}^{\prime}$ now requires a
negative switch of coordinates $(2,3,2,3)$. Indeed, switching that
checkerboard decrements all coefficients of $T$, leaving a -1 in the centre.
Hence $\mathbf{A}\not\rightarrow\mathbf{A}^{\prime}$. While the matrix
$\mathbf{M}$ is the sum of eight unitary switching matrices, and can be
written as a sum of (not all unitary) switching matrices in many ways, none of
these sums includes $\mathbf{C}_{1,4,1,4}$. So none of the switches appearing
in these sums is feasible in $\mathbf{A}$.

######  Lemma 1.

Let $\mathbf{A},\mathbf{A}^{\prime}\in\mathcal{M}(R,C)$ and
$\mathbf{M}=\mathbf{A}^{\prime}-\mathbf{A}$ such that there exists
$\mathbf{T}\in\mathcal{M}_{p-1,q-1}(\mathbb{N})$ such that
$\mathbf{M}=\sum_{i,k}t_{ik}\mathbf{C}_{i,i+1,k,k+1}$ $(i)$. Let us extend $T$
so that $t_{ij}=0$ if $i=0$ or $p$, or if $j=0$ or $q$. Then, for all $i,j$,
we have:

$m_{ij}=t_{ij}+t_{i-1,j-1}-t_{i,j-1}-t_{i-1,j}.$

###### Proof.

Each switching matrix has four non-zero coefficients. So in condition $(i)$,
exactly four terms in the sum contribute to $m_{ij}$. ∎

$m_{i,j-1}$$m_{i,j}$$m_{i,j+1}$$m_{i-1,j-1}$$m_{i-1,j}$$m_{i-1,j+1}$$m_{i+1,j-1}$$m_{i+1,j}$$m_{i+1,j+1}$$t_{i,j-1}$$t_{i-1,j-1}$$t_{i,j}$$t_{i-1,j}$

$m_{ij}=t_{ij}+t_{i-1,j-1}-t_{i,j-1}-t_{i-1,j}$

Figure 1: Relation between coefficients of $\mathbf{M}$ and $\mathbf{T}$

If $\mathbf{M}$ satisfies $(i)$, we create a $(p-1)\times(q-1)$ grid, with the
coefficients of $\mathbf{T}$ inside the cells and the coefficients of
$\mathbf{M}$ at the corners (see Figure 1). Each cell corresponds to a unitary
switching matrix and each coefficient of $\mathbf{T}$ indicates how many times
its cell needs to be switched in order to go from $\mathbf{A}$ to
$\mathbf{A}^{\prime}$. Let $m=\max t_{ik}$. For $1\leq i\leq m$, we define
$\mathcal{P}_{i}(\mathbf{M})$ as the reunion of the cells of the grid with
coefficients at least $i$ (see Example 4). Note that
$\mathcal{P}_{i}(\mathbf{M})$ is formed by one or several polyominoes. We
recall that a _polyomino_ is a shape formed by a finite number of orthogonally
connected cells in a square grid.

######  Example 4.

Let $\mathbf{A}=\begin{pmatrix}0&0&1&1\\\ 0&0&1&1\\\ 1&1&0&0\\\
1&1&0&0\end{pmatrix}$ and $\mathbf{A}^{\prime}=\begin{pmatrix}1&1&0&0\\\
1&1&0&0\\\ 0&0&1&1\\\ 0&0&1&1\end{pmatrix}$. We have
$\mathbf{M}=\mathbf{A}^{\prime}-\mathbf{A}=\begin{pmatrix}1&1&-1&-1\\\
1&1&-1&-1\\\ -1&-1&1&1\\\ -1&-1&1&1\end{pmatrix}$, which satisfies condition
$(i)$ with
$\mathbf{T}=\begin{pmatrix}1&2&1\\\ 2&4&2\\\ 1&2&1\end{pmatrix}$. Thus,
$\mathcal{P}_{1}(\mathbf{M})$ is a $3\times 3$ square,
$\mathcal{P}_{2}(\mathbf{M})$ is an X-shaped pentomino (see Figure 2) and
$\mathcal{P}_{3}(\mathbf{M})$ and $\mathcal{P}_{4}(\mathbf{M})$ are monominoes
surrounding only the central cell. Note that we have
$\mathbf{A}\rightarrow\mathbf{A}^{\prime}$ and going from $\mathbf{A}$ to
$\mathbf{A}^{\prime}$ requires at minimum four switches.

$-1$$-1$$1$$1$$1$$1$$-1$$-1$$-1$$-1$$1$$1$$1$$1$$-1$$-1$$1$$2$$2$$4$$1$$2$$1$$2$$1$
Figure 2: Polyomino $\mathcal{P}_{2}(\mathbf{M})$ of Example 4. Coefficients
of $\mathbf{M}$ are placed at the intersections of the grid and coefficients
of $\mathbf{T}$ are inside the cells.

######  Lemma 2.

If $\mathcal{P}_{i}(\mathbf{M})$ contains two diagonally adjacent cells, then
at least one of the two common neighbouring cells is also in
$\mathcal{P}_{i}(\mathbf{M})$.

###### Proof.

Say the cells of coordinates $(i,j)$ and $(i-1,j-1)$ are in
$\mathcal{P}_{i}(\mathbf{M})$ and the cells of coordinates $(i-1,j)$ and
$(i,j-1)$ are not in $\mathcal{P}_{i}(\mathbf{M})$ (or vice versa). Then,
$t_{ij},t_{i-1,j-1}\geq i$ (resp. $\leq i-1$) and $t_{i-1,j},t_{i,j-1}\leq
i-1$ (resp. $\geq i$). It follows from Lemma 1 that $m_{ij}\geq 2$ (resp.
$\leq-2$). Since $\mathbf{M}=\mathbf{A}^{\prime}-\mathbf{A}$ and $\mathbf{A}$
and $\mathbf{A}^{\prime}$ have binary coefficients, the coefficients of
$\mathbf{M}$ are in $\\{-1,0,1\\}$. This is impossible. ∎

######  Remark 2.

This means that $\mathcal{P}_{i}(\mathbf{M})$ cannot contain two polyominoes
connected by a corner.

######  Theorem 3.

Let $R\in\mathbb{N}^{p}$, $C\in\mathbb{N}^{q}$, let
$\mathbf{A},\mathbf{A}^{\prime}\in\mathcal{M}(R,C)$ and let
$\mathbf{M}=\mathbf{A}^{\prime}-\mathbf{A}$. If $\mathbf{M}$ satisfies the
following conditions:

  1. (i)

$\exists\mathbf{T}\in\mathcal{M}_{p-1,q-1}(\mathbb{N})$:
$\mathbf{M}=\sum_{i,k}t_{ik}\mathbf{C}_{i,i+1,k,k+1}$,

  2. (ii)

For all $i$, each connected component of $\mathcal{P}_{i}(\mathbf{M})$ is
simply connected,

  3. (iii)

$|i^{\prime}-i|\leq 1$ and $|k^{\prime}-k|\leq
1\Rightarrow|t_{i^{\prime}k^{\prime}}-t_{ik}|\leq 1$,

then $\mathbf{A}\rightarrow\mathbf{A}^{\prime}$.

(Proof in the appendix)

Note that the third condition says that the coefficients inside orthogonally
or diagonally adjacent cells must be equal or successive integers. Condition
$(iii)$ in Theorem 3 is probably unnecessary and it seems that if for some
$i$, $\mathcal{P}_{i}(\mathbf{M})$ is not simply connected, it should be
possible to create an instance where
$\mathbf{A}\not\rightarrow\mathbf{A}^{\prime}$, like in Example 3. Combining
these two observations yields the following conjecture:

######  Conjecture 1.

Let $R\in\mathbb{N}^{p}$, $C\in\mathbb{N}^{q}$ and let
$\mathbf{M}\in\mathcal{M}_{p,q}(\\{-1,0,1\\})$. We have
$\mathbf{A}\rightarrow\mathbf{A}^{\prime}$ for all
$\mathbf{A},\mathbf{A}^{\prime}\in\mathcal{M}(R,C)$ such that
$\mathbf{A}^{\prime}-\mathbf{A}=\mathbf{M}$ if and only if $\mathbf{M}$
satisfies:

  1. (i)

$\exists\mathbf{T}\in\mathcal{M}_{p-1,q-1}(\mathbb{N})$:
$\mathbf{M}=\sum_{i,k}t_{ik}\mathbf{C}_{i,i+1,k,k+1}$,

  2. (ii)

For all $i$, each connected component of $\mathcal{P}_{i}(\mathbf{M})$ is
simply connected.

##  3 Spectral Radius and Second Zagreb index

###  3.1 Extrema

In this section, we consider the class of adjacency matrices of simple graphs
with fixed degree distribution $\mathcal{D}$. We investigate how the topology
of simple graphs affects their spectral radius. To this purpose, we analyse
the effect of successive positive checkerboard switches on the spectral radius
$\lambda_{1}$ as well as on the second Zagreb index $M_{2}$, which was used in
[1] to create an approximation of $\lambda_{1}$:
$Z_{2}=\sqrt{\frac{M_{2}}{m}}$. Amongst all the existing approximations for
$\lambda_{1}$, we chose to focus on $Z_{2}$ because we are able to map very
precisely how it varies throughout the set of adjacency matrices of fixed
degree distribution. In contrast, most other commonly used approximations are
determined by the degree distribution, meaning that they are invariant under
checkerboard switching. [13, 14].

Let $G=(V,E)$ be a simple graph with $|V|=n$ and $|E|=m$ and adjacency matrix
$\mathbf{A}$. Let $d_{i}$ denote the degree of vertex $i\in V$. The _spectral
radius_ of $G$, denoted by $\lambda_{1}(G)$ or $\lambda_{1}(\mathbf{A})$, is
the largest eigenvalue of $\mathbf{A}$. The _first_ and _second Zagreb
indices_ are defined as $M_{1}=\sum_{i\in V}d_{i}^{2}$ and $M_{2}=\sum_{ij\in
E}d_{i}d_{j}$ and we have $Z_{1}=\sqrt{\frac{M_{1}}{n}}$ and
$Z_{2}=\sqrt{\frac{M_{2}}{m}}$. Note that $Z_{1}$ is the quadratic average
over $V$ of the degrees, while $Z_{2}$ is the quadratic average over $E$ of
$\sqrt{d_{i}d_{j}}$. It is well-known that $\lambda_{1}\geq Z_{1}$, with
equality if $G$ is a regular graph [7]. Thus, it is the heterogeneity of
$\mathcal{D}$ that allows $\lambda_{1}$ and $Z_{2}$ to vary among the class of
graphs with degree distribution $\mathcal{D}$. Also, for a fixed degree
distribution, $M_{2}$ is proportional to the _degree assortativity
coefficient_ $r$, which is the standard Pearson coefficient for correlation
between the degrees [10]:

$r=\frac{M_{2}-(\sum_{i=1}^{n}\frac{1}{2}d_{i}^{2})^{2}/m}{\sum_{i=1}^{n}\frac{1}{2}d_{i}^{3}-(\sum_{i=1}^{n}\frac{1}{2}d_{i}^{2})^{2}/m}.$

Let $\mathcal{D}\in\mathbb{N}^{n}$ be the degree distribution of a simple
graph. We now consider the class $\mathcal{M}(\mathcal{D})$ of adjacency
matrices of simple graphs of order $n$ with fixed degree distribution
$\mathcal{D}$; i.e. symmetric binary matrices with zeroes on the diagonal and
row and column sums $\mathcal{D}$. Due to the absence of loops, we only
consider, in this section, checkerboards with no coefficient on the diagonal.
Also, given the symmetry of the matrices, checkerboards always come in
symmetric pairs which are always switched together. In terms of graphs, a
checkerboard corresponds to a 4-cycle of alternating edges and non-edges.
Switching a checkerboard means switching the edges and non-edges. We define
the _symmetric switching matrix_
$\mathcal{C}_{ijkl}=\mathbf{C}_{ijkl}\;+\;^{t}\mathbf{C}_{ijkl}$. Note that we
now require the coordinates $(i,j,k,l)$ to be all different. The distinction
between positive and negative checkerboards for graphs is dependent on an
ordering of the vertices. We will always sort the vertices by non-increasing
degree; i.e $\mathcal{D}$ is non-increasing. A positive (resp. negative)
switch of coordinates $(i,j,k,l)$ now corresponds to adding (resp.
subtracting) $\mathcal{C}_{ijkl}$ to the adjacency matrix. We define
$G(\mathcal{D})$ as the directed graph with vertex set
$\mathcal{M}(\mathcal{D})$ and an arc joins $\mathbf{A}$ to
$\mathbf{A}^{\prime}$ when $\mathbf{A}^{\prime}$ can be obtained from
$\mathbf{A}$ by a positive switch.

######  Proposition 4.

The graph $G(\mathcal{D})$ is connected and acyclic.

###### Proof.

The connectedness is shown in [3]. The acyclicity follows from the acyclicity
in the asymmetric case. ∎

######  Lemma 3.

Let $\mathbf{A},\mathbf{A}^{\prime}\in\mathcal{M}(\mathcal{D})$ be such that
$\mathbf{A}^{\prime}$ can be obtained from $\mathbf{A}$ by a positive switch
of coordinates $(i,j,k,l)$. We have
$M_{2}(\mathbf{A}^{\prime})-M_{2}(\mathbf{A})=(d_{i}-d_{j})(d_{k}-d_{l})$.

###### Proof.

$\mathbf{A}^{\prime}$ is obtained from $\mathbf{A}$ by adding the edges $ik$
and $jl$ and removing $il$ and $kj$. So
$M_{2}(\mathbf{A}^{\prime})=M_{2}(\mathbf{A})+d_{i}d_{k}+d_{j}d_{l}-d_{i}d_{l}-d_{j}d_{k}$.
∎

######  Proposition 5.

$M_{2}$ and $Z_{2}$ are non-decreasing along arcs of $G(\mathcal{D})$.

###### Proof.

This follows from Lemma 3 and $\mathcal{D}$ being non-decreasing. ∎

Note that $M_{2}$ and $Z_{2}$ are constant only along arcs of $G(\mathcal{D})$
which correspond to a checkerboard of coordinates $(i,j,k,l)$ where
$d_{i}=d_{j}$ or $d_{k}=d_{l}$.

######  Corollary 4.

The sources and sinks of $G(\mathcal{D})$ are, respectively, the local minima
and maxima of $M_{2}$ and $Z_{2}$.

The above results give a clear picture of the variations of $M_{2}$ and
$Z_{2}$ along $G(\mathcal{D})$. Unfortunately, the variations of $\lambda_{1}$
are not quite so neatly organised. The following lemma gives a lower bound to
the effect of a single positive switch on the spectral radius:

######  Lemma 4.

Let $\mathbf{A},\mathbf{A}^{\prime}\in\mathcal{M}(\mathcal{D})$ such that
$\mathbf{A}^{\prime}$ can be obtained from $\mathbf{A}$ by a sequence of
positive switches of coordinates $(i_{p},j_{p},k_{p},l_{p})$. Let $X$ denote
the normalised principal eigenvector of $\mathbf{A}$. We have

$\lambda_{1}(\mathbf{A}^{\prime})-\lambda_{1}(\mathbf{A})\geq
2\sum_{p}(x_{i_{p}}-x_{j_{p}})(x_{k_{p}}-x_{l_{p}}).$

###### Proof.

Let $X^{\prime}$ denote the normalised principal eigenvector of
$\mathbf{A}^{\prime}$. Recall that

$\lambda_{1}(\mathbf{A})=\leavevmode\nobreak\
^{t}X\mathbf{A}X=\max_{x\in\mathbb{R}^{n},||x||=1}\leavevmode\nobreak\
^{t}x\mathbf{A}x,$

where $||\leavevmode\nobreak\ ||$ is the $L^{2}$-norm. We have:

$\lambda_{1}(\mathbf{A}^{\prime})-\lambda_{1}(\mathbf{A})=\leavevmode\nobreak\
^{t}X^{\prime}\mathbf{A}^{\prime}X^{\prime}-\leavevmode\nobreak\
^{t}X\mathbf{A}X\geq\leavevmode\nobreak\
^{t}X\mathbf{A}^{\prime}X-\leavevmode\nobreak\ ^{t}X\mathbf{A}X$
$=\leavevmode\nobreak\
^{t}X\sum_{p}\mathcal{C}_{i_{p},j_{p},k_{p},l_{p}}X=2\sum_{p}(x_{i_{p}}-x_{j_{p}})(x_{k_{p}}-x_{l_{p}}).$

∎

Unfortunately, the coefficients of the principal eigenvector are not always in
the same order as the degrees. They are, however, strongly correlated [9]; so
$\lambda_{1}$ increases along most arcs of $G(\mathcal{D})$. In fact, they are
perfectly correlated in the case where $\lambda_{1}$ is maximum:

######  Proposition 6.

If $\mathbf{A}$ realises the maximum of $\lambda_{1}$ over
$\mathcal{M}(\mathcal{D})$, then the coefficients of the principal eigenvector
$X$ of $\mathbf{A}$ are in the same order as the degrees; i.e.
$d_{i}>d_{j}\Rightarrow x_{i}\geq x_{j}$.

###### Proof.

Assume we have $d_{i}>d_{j}$ and $x_{i}<x_{j}$. Let $E$ be a set of
$d_{i}-d_{j}$ vertices adjacent to $i$ and not $j$, with $j\notin E$. Let
$\mathbf{A}^{\prime}$ be obtained from $\mathbf{A}$ by replacing the edges
between $i$ and $E$ with edges between $j$ and $E$. Note that all the non-zero
coefficients of $\mathbf{A}^{\prime}-\mathbf{A}$ are in rows and columns $i$
and $j$. Let $X^{\prime}$ be the normalised principal eigenvector of
$\mathbf{A}^{\prime}$. We have:

$\lambda_{1}(\mathbf{A}^{\prime})-\lambda_{1}(\mathbf{A})\geq\leavevmode\nobreak\
^{t}X\mathbf{A}^{\prime}X-\leavevmode\nobreak\
^{t}X\mathbf{A}X=2(x_{j}-x_{i})\sum_{k\in E}x_{k}\geq 0.$

Consider the case where $2(x_{j}-x_{i})\sum_{k\in E}x_{k}=0$. According to the
Perron-Froebenius theorem for non-negative matrices, $X$ has non-negative
coefficients. Thus, since $x_{j}>x_{i}$, $\forall k\in E,x_{k}=0$. Let $k\in
E$, then $\sum_{l}a_{kl}x_{l}=\lambda_{1}(\mathbf{A})x_{k}=0$. Since all terms
in $\sum_{l}a_{kl}x_{l}$ are non-negative and $k$ is adjacent to $i$, we
deduce that $x_{i}=0$. Similarly, any vertex $l$ in the connected component of
$i$ has $x_{l}=0$. Since $x_{j}>0$, $\lambda_{1}(\mathbf{A})$ is the spectral
radius of the connected component of $j$, to which $i$ does not belong. Thus,
the connected component of $j$ in $\mathbf{A}$ is a proper sub-graph of that
in $\mathbf{A}^{\prime}$. So
$\lambda_{1}(\mathbf{A}^{\prime})>\lambda_{1}(\mathbf{A})$ in this case and in
all cases.

Let $\mathbf{A}^{\prime\prime}$ be obtained from $\mathbf{A}^{\prime}$ by
switching the $i$-th and $j$-th rows and the $i$-th and $j$-th columns.
$\mathbf{A}^{\prime\prime}$ has the same row and column sums as $\mathbf{A}$
and we have
$\lambda_{1}(\mathbf{A}^{\prime\prime})=\lambda_{1}(\mathbf{A}^{\prime})>\lambda_{1}(\mathbf{A})$.
Thus, $\mathbf{A}$ does not maximise $\lambda_{1}$. ∎

From this, we deduce the following:

######  Theorem 4.

The maximum of $\lambda_{1}$ is reached at a sink of $G(\mathcal{D})$.

###### Proof.

Let $\mathbf{A}$ maximise $\lambda_{1}$ over $\mathcal{M}(\mathcal{D})$. For
each set of same-degree vertices, we can reorder the rows and columns of
$\mathbf{A}$ so that within these sets, the coefficients of the principal
eigenvector are non-increasing. This operation does not affect $\lambda_{1}$.
It follows from 6 that all the coefficients of $X$ are now non-increasing. Let
$\mathbf{A}^{\prime}$ be obtained from $\mathbf{A}$ by a sequence of positive
switches of coordinates $(i_{p},j_{p},k_{p},l_{p})$. It follows from Lemma 4
that

$\lambda_{1}(\mathbf{A}^{\prime})-\lambda_{1}(\mathbf{A})\geq
2\sum_{p}(x_{i_{p}}-x_{j_{p}})(x_{k_{p}}-x_{l_{p}})\geq 0.$

Since $\lambda_{1}(\mathbf{A})$ is maximum, any matrix
$\mathbf{A}^{\prime}\in\mathcal{M}(\mathcal{D})$ such that
$\mathbf{A}\rightarrow\mathbf{A}^{\prime}$ also maximises $\lambda_{1}$,
including the sinks that can be reached from $\mathbf{A}$. ∎

###  3.2 Switching Algorithm Simulations

While Theorem 4 tells us that at least one sink of $G(\mathcal{D})$ realises
the global maximum of $\lambda_{1}$, it gives no indications for identifying
which sink to aim for when $G(\mathcal{D})$ contains several, as is usually
the case. In this section, we showcase how applying successive random switches
to Erdős-Rényi and Small-World graphs, after ordering its vertices by degree,
leads to an increase in $\lambda_{1}$, which is significant when the edge
density is low.

Figure 3: Spectral radius (plain) and $Z_{2}$ (dotted) as functions of the
number of positive switches, starting from Erdős-Rényi graphs with $N=100$
vertices. From left to right, the edge density $p$ ranges from $0.2$ to $0.7$.
Both the initial (Erdős-Rényi with vertices ordered by degree) and the final
matrices are shown in each case.

Instead of using a Monte-Carlo method as in the Xulvi-Brunet Sokolov algorithm
[16], we only apply positive switches selected randomly in the adjacency
matrix. Simulations that begin with an Erdős-Rényi graph $E(N,p)$ with
vertices ordered by degree are shown in Figure 3 and Small World graphs appear
in Figure 4. In both cases, the end result of the switching process is a zebra
with some noise when $p>0.5$ and an anti-zebra with some noise when $p<0.5$.
When $p=0.5$, the end point is simultaneously almost a zebra and almost an
anti-zebra. In the Erdős-Rényi case with $p=0.2$, the spectral radius
increases by more than $15\%$, which is very impressive for a fixed degree
distribution. Conversely, when $p=0.7$, the spectral radius increases only by
a few decimal points.

Figure 4: Same as Figure 3 with Small-World graphs obtained from a $10\times
10$ regular grid after a random rewiring of 10% of the edges.

##  4 Conclusion

Our analysis of the oriented graph of matrices has given us the tools needed
to study how the topology of graphs impacts their spectral radius
$\lambda_{1}$. We have shown that the global maximum of $\lambda_{1}$ is
reached for a matrix without negative checkerboards. Our simulations show that
successively switching negative checkerboards to positive can yield a high
increase in $\lambda_{1}$, especially for sparse graphs.

## Acknowledgements

We would like to thank Cristophe Crespelle for a fruitful research session in
Bergen, where Example 3 was discovered and Theorem 3 was intuited, and the
LabEx SMS ANR-11-LABEX-0066 for providing mobility funding.

## Appendix: Proofs of Theorems 2 and 3

###  4.1 Proof of Theorem 2

######  Theorem.

If $\mathcal{M}(R,C)$ contains a split zebra or a split anti-zebra, then that
split zebra or anti-zebra is the only element of $\mathcal{M}(R,C)$ without
negative checkerboards; i.e it is the unique sink in $G(R,C)$.

###### Proof of theorem 2.

Let $\mathbf{A}\in\mathcal{M}(R,C)$ be a zebra with a horizontal split (i.e.
the top half is nested and the bottom anti-nested) and let
$\mathbf{A}^{\prime}\in\mathcal{M}(R,C)$, $\mathbf{A}^{\prime}\neq\mathbf{A}$.
We will show that $\mathbf{A}^{\prime}$ has a negative checkerboard. Let
$\mathbf{M}=\mathbf{A}^{\prime}-\mathbf{A}$. Since $\mathbf{A}$ and
$\mathbf{A}^{\prime}$ have the same row and column sums, $\mathbf{M}$ has as
many 1s and -1s in each row and column. We can thus choose in each row and
column of $\mathbf{M}$ a matching associating each 1 to a -1. Let us now
choose a -1 in $\mathbf{M}$ as a starting point for the sequence defined by
the following rules: a -1 is followed by its paired 1 in the same row; a 1 is
followed by its paired -1 in the same column. Since the matrix $\mathbf{M}$ is
finite, the sequence must form a cycle. A 1-11 sub-sequence in $\mathbf{M}$
corresponds to a 010 sequence in $\mathbf{A}$, with the first 0 in the same
column as the 1 and the second 0 in the same row. Thus, it follows from 1 that
at a -1, the cycle must form a right turn. Also, after turning right (resp.
left) at a 1 in $\mathbf{M}$ (0 in $\mathbf{A}$), the following -1 is located
in the same column on the other side (resp. the same side) of the split in
$\mathbf{A}$.

-1-1-111$A$ Figure 5: Section of a cycle with a left turn. The dotted line indicates the horizontal split of the zebra.

If the cycle turns left at every 1 (and right at every -1), it forms an
infinite staircase pattern, which is impossible. Assume that there is at least
one left turn at a 1. There must be a left turn at a 1 followed by a right
turn at the next 1 somewhere in the cycle. This yields a -11-11-1 sequence
with a left turn at the first 1 and a right turn at the second, as shown in
Figure 5. Note that the first four digits are located on the same side of the
split while the final -1 is on the other side. We now consider the coefficient
located at the intersection point $A$ of the row containing the first two
digits and the column with the last two. Note that $A$ must be positioned
between those last two digits due to the final -1 being on the other side of
the split. If that coefficient is a 0 in $\mathbf{A}^{\prime}$, then it forms
a negative checkerboard in $\mathbf{A}^{\prime}$ together with the middle
three coefficients of our sequence; and thus $\mathbf{A}^{\prime}$ is not a
sink. Assume now that it is a 1 in $\mathbf{A}^{\prime}$. The first two terms
of our sequence are respectively 1 and 0 in $\mathbf{A}$. According to 2,
there is no $\begin{pmatrix}1&0&1\end{pmatrix}$ sub-matrix in $\mathbf{A}$. So
the coefficient at $A$ is 0 in $\mathbf{A}$ and 1 in $\mathbf{M}$. Thus, we
can shorten our cycle by replacing the middle three coefficients of our
sequence with this 1. The resulting cycle has one fewer left turns. By
repeating this operation, we obtain a cycle with no left turn.

Let us now consider the corresponding cycle in $\mathbf{A}^{\prime}$. It
satisfies the following properties:

  * •

It alternates between 0s and 1s, going from 0 to 1 horizontally and 1 to 0
vertically.

  * •

It always turns to the right.

  * •

All vertical segments cross the split.

If this cycle self-intersects, it forms one of the patterns shown in Figure 6
(possibly rotated by $180^{\circ}$). In case a) (resp. b)), if the coefficient
located at intersection point $A$ is a $0$ (resp $1$), it forms a negative
checkerboard with the second, third and fourth (resp. fourth, fifth and sixth)
terms of the sequence. Else, if the coefficient located at $B$ is a $0$ (resp.
$1$), $A$, $B$ and the fifth and sixth terms (resp. second and third terms)
form a negative checkerboard. Else, if $B$ is a $1$ (resp. $0$), the sequence
can be shortened by replacing the five middle terms with $B$. This removes the
intersection at $A$ while maintaining the three properties of the cycle. By
repeating this operation, we obtain a cycle with no left turn and no
intersection; i.e. a negative checkerboard. Thus $\mathbf{A}^{\prime}$ must
have a negative checkerboard.

a)0000111$A$$B$b)1111000$A$$B$ Figure 6: Section of a self-intersecting cycle
with no left turn. The dotted line indicates the horizontal split of the
zebra.

The case of vertically split zebras follows by symmetry along the main
diagonal. The vertical reflection of a unique sink is a unique source; and the
complement of a unique source is a unique sink. Thus, the same property holds
if $\mathbf{A}$ is a split anti-zebra.

∎

###  4.2 Proof of Theorem 3

######  Theorem.

Let $R\in\mathbb{N}^{p}$, $C\in\mathbb{N}^{q}$, let
$\mathbf{A},\mathbf{A}^{\prime}\in\mathcal{M}(R,C)$ and let
$\mathbf{M}=\mathbf{A}^{\prime}-\mathbf{A}$. If $\mathbf{M}$ satisfies the
following conditions:

  1. (i)

$\exists\mathbf{T}\in\mathcal{M}_{p-1,q-1}(\mathbb{N})$:
$\mathbf{M}=\sum_{i,k}t_{ik}\mathbf{C}_{i,i+1,k,k+1}$,

  2. (ii)

For all $i$, each connected component of $\mathcal{P}_{i}(\mathbf{M})$ is
simply connected,

  3. (iii)

$|i^{\prime}-i|\leq 1$ and $|k^{\prime}-k|\leq
1\Rightarrow|t_{i^{\prime}k^{\prime}}-t_{ik}|\leq 1$,

then $\mathbf{A}\rightarrow\mathbf{A}^{\prime}$.

In order to prove Theorem 3, we will first prove that one of the shapes
described in Figure 7 must appear on the contour of any simply connected
polyomino. We will then show that where this shape appears on
$\mathcal{P}_{m}(\mathbf{M})$, we can locate a checkerboard to switch.
Repeating the operation will create a directed path from $\mathbf{A}$ to
$\mathbf{A}^{\prime}$.

1)$A$$B$$C$$D$2)$A$$B$$C$$D$3)$A$$B$$C$$D$

1) Motif 1 occurs when the entire polyomino is a rectangle.

2) In motif 2, the two vertical sides must have equal length; i.e. $AB=CD$.
Also, the inside of rectangle $ABCD$ must be entirely included in the
polyomino. The lengths are variable and the motif may be rotated.

3) In motif 3, the rightmost side is longer than $AB$. The inside of rectangle
$ABCD$ must be entirely included in the polyomino. The lengths are variable
and the motif may be rotated or reflected.

Figure 7: Motifs from the contour of a polyomino

######  Lemma 5.

On the contour of any simply connected polyomino, there appears at least one
of the three motifs described in Figure 7.

###### Proof.

Let $\mathcal{P}$ be a simply connected polyomino. If $\mathcal{P}$ is a
rectangle, we have motif 1. We will now assume that $\mathcal{P}$ is not a
rectangle.

We define _left_ (resp. _right_) corners of $\mathcal{P}$ as corners where the
contour of $\mathcal{P}$, when followed clockwise, turns left (resp. right).
Note that $\mathcal{P}$ is locally non-convex (resp. convex) around left
(resp. right) corners.

For $x,y\in\mathcal{P}$, we define an _orthogonal path from $x$ to $y$_ as a
line joining $x$ and $y$ consisting of only horizontal and vertical segments
included inside $\mathcal{P}$. We denote by $OP(x,y)$ the set of orthogonal
paths joining $x$ and $y$. We then define the _length_ of an orthogonal path
$\mathcal{L}$ as the pair $(N_{\mathcal{L}},l_{\mathcal{L}})$, where
$N_{\mathcal{L}}$ is the number of segments of $\mathcal{L}$ and
$l_{\mathcal{L}}$ is the length of the last segment. We define $d(x,y)$, the
_distance_ between $x$ and $y$, as the length of the minimal orthogonal path,
going by lexicographic order (ie. $d(x,y)=(N_{0},l_{0})$ with
$N_{0}=\min_{\mathcal{L}\in OP(x,y)}N_{\mathcal{L}}$ and
$l_{0}=\min_{\mathcal{L}\in OP(x,y);N_{\mathcal{L}}=N_{0}}l_{\mathcal{L}}$).
111Note that $d$ is not a distance in the usual sense, as its co-domain is not
$\mathbb{R}^{+}$. Yet, while $d^{\prime}:(x,y)\mapsto
N_{0}+\frac{2}{\pi}\arctan l_{0}$ defines an actual distance, $d$ is more
practical for our purposes.

Since $\mathcal{P}$ is not a rectangle, it is not convex; so we may choose a
point $x_{0}\in\mathcal{P}$ such that $\mathcal{P}$ is not starred in $x_{0}$.
The set of points in $\mathcal{P}$ which maximise the distance to $x_{0}$
comprises one or several segments from the contour of $\mathcal{P}$. Let $B$
and $C$ be the ends of one such segment. Both $B$ and $C$ must be corners of
$\mathcal{P}$, else points on $(B,C)$ outside of $[B,C]$ would be at an equal
or greater distance from $x_{0}$. Let $A$ and $D$ be the other two corners
adjacent to $B$ and $C$, respectively. $B$ and $C$ must be right corners,
otherwise points inside of $[AB]$ or $[CD]$ would be at a greater distance
from $x_{0}$. The rectangle $ABCD$ must be included inside of $\mathcal{P}$:
if a part of $ABCD$ was outside $\mathcal{P}$, since $\mathcal{P}$ is simply
connected, the minimal orthogonal path from $x_{0}$ to $B$ would need to go
around one side of the missing part, and reaching the other side from $x_{0}$
would require a path with more turns.

We may assume w.l.o.g that $AB\leq CD$. Then, $A$ must be a left corner, else
reaching $[AB]$ from $x_{0}$ would require one more turn than $[BC]$. If
$AB=CD$, $D$ must similarly be a left turn, and we have the second motif. If
$AB<CD$, we have the third motif. ∎

We may now prove Theorem 3.

###### Proof of Theorem 3.

Let $\mathbf{A}$, $\mathbf{A}^{\prime}$ and $\mathbf{M}$ satisfy the
conditions of Theorem 3; let $\mathbf{T}$ satisfy $(i)$ and let $m=\max
t_{ik}$. It follows from applying Lemma 5 to a connected component of
$\mathcal{P}_{m}(\mathbf{M})$ that there is a rectangle $ABCD$ corresponding
to one of the three motifs described in Figure 7 included inside
$\mathcal{P}_{m}(\mathbf{M})$. Since $m$ is the maximum coefficient, all cells
in $\mathcal{P}_{m}(\mathbf{M})$ have coefficient $m$. It follows from $(iii)$
and Remark 2 that all cells orthogonally or diagonally adjacent to
$\mathcal{P}_{m}(\mathbf{M})$ have coefficient $m-1$. From Lemma 1, we have
$m_{ij}=t_{ij}+t_{i-1,j-1}-t_{i,j-1}-t_{i-1,j}$, where $t_{ij}=0$ if $i=0$ or
$p$ or $j=0$ or $q$. For a right (resp. left) corner of
$\mathcal{P}_{m}(\mathbf{M})$, three (resp. one) of the incident cells have
coefficient $m-1$ and one (resp. three) has coefficient $m$. Thus coefficients
of $\mathbf{M}$ located at corners of $\mathcal{P}_{m}(\mathbf{M})$ must be
$1$ or $-1$. More precisely, regardless of the orientation of $ABCD$, the
coefficients of $\mathbf{M}$ located at the corners are $1$ for the top left
and bottom right corners and $-1$ for the top right and bottom left, except
for $D$ in motif 3 which has a $0$.

A $1$ in $\mathbf{M}$ means a $0$ in $\mathbf{A}$ and $1$ in
$\mathbf{A}^{\prime}$; a $-1$ in $\mathbf{M}$ is the reverse; and a $0$ in
$\mathbf{M}$ means either two $0$s or two $1$s in $\mathbf{A}$ and
$\mathbf{A}^{\prime}$. So, a $\begin{pmatrix}1&-1\\\ -1&1\end{pmatrix}$ sub-
matrix in $\mathbf{M}$ means there is a negative checkerboard in $\mathbf{A}$
and a positive checkerboard in $\mathbf{A}^{\prime}$. If any one of the four
coefficients is replaced by $0$, then there is either a negative checkerboard
in $\mathbf{A}$ or a positive checkerboard in $\mathbf{A}^{\prime}$. Switching
that checkerboard, either in $\mathbf{A}$ or in $\mathbf{A}^{\prime}$, results
in a new instance where $ABCD$ has been cropped from
$\mathcal{P}_{m}(\mathbf{M})$. Thus, the new instance still satisfies the
three conditions of Theorem 3. Repeating the process terminates with
$\mathbf{M}=0$, as $\sum t_{ik}$ is reduced at each step. This constructs a
directed path from $\mathbf{A}$ to $\mathbf{A}^{\prime}$ in $G(R,C)$. ∎

## References

  * [1] Hosam Abdo, Darko Dimitrov, Tamás Réti, and Dragan Stevanovic.  Estimating the spectral radius of a graph by the second zagreb index.  MATCH Commun. Math. Comput. Chem, 72:741–751, 2014.
  * [2] Yael Artzy-Randrup and Lewi Stone.  Generating uniformly distributed random networks.  Physical Review E, 72(5):056708, 2005.
  * [3] Claude Berge.  Graphes et hypergraphes, volume 37 of monographie universitaire de mathématique.  Dunod, Paris, 1970.
  * [4] Richard A Brualdi.  Matrices of zeros and ones with fixed row and column sum vectors.  Linear algebra and its applications, 33:159–231, 1980.
  * [5] Richard A Brualdi and James G Sanderson.  Nested species subsets, gaps, and discrepancy.  Oecologia, 119(2):256–264, 1999.
  * [6] Emilie Coupechoux and Marc Lelarge.  How clustering affects epidemics in random networks.  Advances in Applied Probability, 46(4):985–1008, 2014.
  * [7] Clive Elphick and Tamás Réti.  On the relations between the zagreb indices, clique numbers and walks in graphs.  MATCH Commun. Math. Comput. Chem, 74:19–34, 2015.
  * [8] Wei Jiang and Junjie Yang.  A degree distribution optimization algorithm for image transmission.  Journal of Optical Communications, 37(3):301–310, 2016.
  * [9] Cong Li, Qian Li, Piet Van Mieghem, H Eugene Stanley, and Huijuan Wang.  Correlation between centrality metrics and their application to the opinion model.  The European Physical Journal B, 88(3):1–13, 2015.
  * [10] Lun Li, David Alderson, John C Doyle, and Walter Willinger.  Supplemental material: The $s(g)$-metric and assortativity [a supplement to" towards a theory of scale-free graphs: Definition, properties, and implications"].  Internet Mathematics, 2(4), 2005.
  * [11] Patrick N McGraw and Michael Menzinger.  Clustering and the synchronization of oscillator networks.  Physical Review E, 72(1):015101, 2005.
  * [12] M.E.J. Newman.  Mixing patterns in networks.  Physical review. E, Statistical, nonlinear, and soft matter physics, 67:026126, 03 2003.
  * [13] Romualdo Pastor-Satorras and Claudio Castellano.  Eigenvector localization in real networks and its implications for epidemic spreading.  Journal of Statistical Physics, 173(3):1110–1123, 2018.
  * [14] Juan G Restrepo, Edward Ott, and Brian R Hunt.  Approximating the largest eigenvalue of network adjacency matrices.  Physical Review E, 76(5):056119, 2007.
  * [15] Herbert J Ryser.  Combinatorial properties of matrices of zeros and ones.  Canadian Journal of Mathematics, 9:371–377, 1957.
  * [16] Ramon Xulvi-Brunet and Igor M Sokolov.  Reshuffling scale-free networks: From random to assortative.  Physical Review E, 70(6):066102, 2004.