# Laplace and Dirac Operators on Graphs

Beata Casiday  Department of Mathematics
Yale University
Yale University
442 Dunham Lab
10 Hillhouse Ave
New Haven, CT 06511<EMAIL_ADDRESS>,  Ivan Contreras  ,  Thomas Meyer
Department of Mathematics and Statistics
Amherst College
31 Quadrangle Drive
Amherst, MA 01002<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>,  Sabrina Mi  Department of Mathematics
University of Chicago
Eckhart Hall
5734 S University Ave
Chicago IL, 60637<EMAIL_ADDRESS>and  Ethan Spingarn

###### Abstract.

Discrete versions of the Laplace and Dirac operators haven been studied in the
context of combinatorial models of statistical mechanics and quantum field
theory. In this paper we introduce several variations of the Laplace and Dirac
operators on graphs, and we investigate graph-theoretic versions of the
Schrödinger and Dirac equation. We provide a combinatorial interpretation for
solutions of the equations and we prove gluing identities for the Dirac
operator on lattice graphs, as well as for graph Clifford algebras.

###### Contents

  1. 1 Introduction
    1. 1.1 Acknowledgments
  2. 2 The graph Laplacian and the Schrödinger equation
    1. 2.1 Steady states
    2. 2.2 Average of quantum states
  3. 3 The graph Dirac operator and the Dirac equation
    1. 3.1 Matrix representations of graph Dirac operators
    2. 3.2 Visualization
    3. 3.3 Quadratic forms
    4. 3.4 Powers of $\not{D}_{I}$
  4. 4 Dimer models and a gluing formula for Dirac operators
    1. 4.1 Graph gluing
    2. 4.2 The $2\times n$ case
    3. 4.3 The $3\times n$ case
    4. 4.4 The $4\times n$ case
  5. 5 Spinors, Clifford algebras on graphs and gluing
    1. 5.1 Examples
    2. 5.2 Graph gluing and Clifford algebras
  6. 6 Future directions

##  1\. Introduction

The Laplace operator, or Laplacian, is a fundamental object of study in
mathematics and physics. In particular, the evolution of quantum-mechanical
systems is controlled by the Schrödinger equation, which relies on the
properties of the Laplace operator. Discretized versions of the Laplacian have
been implemented in order to study combinatorial models in quantum field
theory [Mnev16, Reshetikhin:2014jaa, Cimasoni07]. Similarly, the Dirac
operator (that can be understood as a square root of the Laplacian) is part of
the mathematical formulation of spinors. One of the purposes of this paper is
to study different versions of the Laplace and Dirac operators on finite
graphs, and to analyze the (time dependent) Dirac equation on graphs, which
gives a graph-theoretic interpretation of spinors. The notion of spinor has
its origins in particle physics: it first appeared around 1922 when Stern and
Gerlach realized that electrons can be catalogued into two groups or streams
(“up” or “down”), depending on a separation by a non-uniform magnetic field.
It was later interpreted as a version of angular momentum, so the spin of a
particle is naturally associated to the notion of rotation. Mathematically
speaking, we can think of spinors as vectors in $\mathbb{C}^{2}$. For
instance, $\begin{bmatrix}1\\\ 0\end{bmatrix}$ can be seen as a spinor.
Spinors have natural linear transformations, which can be seen as rotations in
$\mathbb{R}^{3}$. More generally, it turns out that quaternions are useful to
describe higher dimensional rotations, and therefore, spinors.

From the point of view of quantum mechanics, the dynamics of a quantum
particle can be described in terms of the Schrödinger equation:

$\partial_{t}(\psi)=\frac{i}{\hbar}\Delta(\psi),$ (1)

where $\psi$ is a state (a special type of function) and $\Delta$ is the
Laplace operator:

$\Delta=\nabla\cdot\nabla,$

where $\nabla$ denotes the gradient. Dirac provided a way to include particles
with spin in the equation:

$\not{\partial}(\psi)=\frac{mc}{i\hbar}\psi$ (2)

where $\not{\partial}$ is called the Dirac operator, satisfying
$\not{\partial}^{2}=\Delta$.

A toy model of these equations is given in terms of the discrete Laplace and
Dirac operators. The key advantage is that the evolution of states in this toy
model depends only on the spectral properties of the graph. In particular,
spectral graph theory analyzes the features of a graph in relationship with
the behavior of the (eigenvalues/eigenvectors of) matrices associated with
that graph.

Given the adjacency matrix $A$, and the degree matrix $D$, for a given graph
$\Gamma$, the Laplacian $\Delta(\Gamma)$ of the graph is defined as the
following matrix:

$\Delta(\Gamma)=D(\Gamma)-A(\Gamma).$

In Section 2 we introduce the even and odd graph Laplacian matrix, and the
main results (Theorems 2.19 and 2.21) describe the steady states for the even
and odd versions of the graph Schrödinger equations, in terms of the connected
components and inependent cycles of the graph.

In Section 3 we introduce various versions of the Dirac operator on graphs,
including the incidence Dirac operator (Definition 3.3), inspired by the work
of Knill [Knill]. The main result of this section (Theorem 3.14) is a graph-
theoretic interpretation of the powers of the incidence Dirac operator, in
terms of the number of certain walks on the graph.

A particular type of Dirac operators on graphs appears in the context of dimer
models, following the work of Kenyon [Kenyon2002], Cimasoni and Reshetikhin
[Cimasoni07]. It turns out that the Kasteleyn matrix, which produces the
number of perfect matchings of lattice graphs, can be interpreted as a
discrete Dirac operator. We prove (see Theorems 4.6, 4.7, 4.9, A.1) gluing
formulae for different cases of graph gluing of lattice graphs. On the other
hand, spinors have an algebraic representation via Clifford algebras. In
Section 5 we follow the construction of Clifford algebras for graphs
introduced by Khovanova in [Khovanova]. There it is described how to assign
Clifford algebras to graphs. The main results (Theorems 5.5 and 5.6) provide
an algebraic interpretation for the gluing of graphs in terms of their
corresponding Clifford algebras.

###  1.1. Acknowledgments

This research project started during the 2021 SUMRY Program at Yale
University, which was supported by NSF (DMS-2050398). I.C. thanks Pavel Mnev
for useful discussions during the early stages of this project.

##  2\. The graph Laplacian and the Schrödinger equation

The Laplacian describes the evolution of a quantum state over time for
particles without spin, as governed by the Schrödinger equation. We study
graph theoretic analogues of the Laplacian [nica_SpectralGraph] and its
interpretation in quantum mechanics [Mnev16]. We provide characterizations of
the steady states of the graph Schrödinger equation and give a result on the
average of quantum states.

We begin by defining quantum states on a graph. In the continuum, a quantum
state is an assignment of a complex number to each point in space. We consider
a graph theoretical model in which a graph quantum state is an assignment of a
complex number to each vertex and each edge of a finite simple graph. This
model can be considered as taking a ”sampling” of points from the continuum
and restricting our study to the evolution of this sample over time.

We next define several operators that are integral to our study of graph
quantum mechanics.

######  Definition 2.1.

Let $\Gamma=(V,E)$ be a finite simple graph. The incidence matrix of $\Gamma$,
denoted $I$, is the $|V|\times|E|$ matrix whose $(i,j)$ entry is defined by

$[I]_{i,j}=\begin{cases}1&\text{edge $j$ ends at vertex $i$}\\\ -1&\text{edge
$j$ starts at vertex $i$}\\\ 0&\text{otherwise.}\end{cases}$

We use the incidence matrix to define the even and odd graph Laplacians. These
operators act as discretized forms of the Laplace operator, and act on the
vertices and edges of our graph respectively.

######  Definition 2.2.

Let $\Gamma=(V,E)$ be a finite simple graph. A vertex state assigns a complex
number to each vertex $v\in V$. An edge state assigns a complex number to each
edge $e\in E$. A vertex-edge state assigns a complex number to each $v\in V$
and each $e\in E$.

######  Remark 1.

When clear from context, we refer to these states as quantum states. In
general, the even and odd Laplacian and Dirac operators act on vertex states
and edge states respectively, and the incidence Dirac operator acts on vertex-
edge states. We use the notation $\psi$ to refer to a general quantum state,
and use $v$ and $e$ to denote vertex and edge states respectively.

######  Definition 2.3.

Let $I$ be the incidence matrix of a finite simple graph $\Gamma$. The Even
Graph Laplacian is defined as

$\Delta_{+}=II^{t}.$

Equivalently, $\Delta_{+}$ can be defined as

$\Delta_{+}=D-A,$

where $D$ and $A$ are the degree and adjacency matrices of $\Gamma$
respectively.

######  Definition 2.4.

The Odd Graph Laplacian is defined as

$\Delta_{-}=I^{t}I.$

We now give a concrete example of the even and odd Laplacians on a small
graph.

######  Example 2.5.

Let $\Gamma$ be the path graph with 3 vertices, and orientation given below.

Figure 1. Oriented path graph $P_{3}$.

Then the previously defined operators are given by:

$I=\begin{bmatrix}-1&0\\\ 1&1\\\ 0&-1\end{bmatrix}$
$\Delta_{+}=II^{t}=\begin{bmatrix}-1&0\\\ 1&1\\\
0&-1\end{bmatrix}\begin{bmatrix}-1&1&0\\\
0&1&-1\end{bmatrix}=\begin{bmatrix}1&-1&0\\\ -1&2&-1\\\ 0&-1&1\end{bmatrix}$
$\Delta_{-}=I^{t}I=\begin{bmatrix}-1&1&0\\\
0&1&-1\end{bmatrix}\begin{bmatrix}-1&0\\\ 1&1\\\
0&-1\end{bmatrix}=\begin{bmatrix}2&1\\\ 1&2\end{bmatrix}.$

######  Remark 2.

By definition, we have $\Delta_{+}=D-A$, so that the even Laplacian is
independent of the orientation of $\Gamma$. In contrast, $\Delta_{-}$ does
depend on orientation of the underlying graph, as shown in the following
example.

######  Example 2.6.

Let $\Gamma_{1}$ and $\Gamma_{2}$ be $C_{3}$ with the orientations given
below:

Figure 2. Two orientations of $C_{3}$.

A routine calculation yields
$\Delta_{-}(\Gamma_{1})=\begin{bmatrix}2&-1&-1\\\ -1&2&-1\\\ -1&-1&2\\\
\end{bmatrix}$

$\Delta_{-}(\Gamma_{2})=\begin{bmatrix}2&-1&1\\\ -1&2&1\\\ 1&1&2\\\
\end{bmatrix}$.

######  Remark 3.

Eigenvalues of the odd Laplacian are independent of orientation. Indeed, for
two graphs $\Gamma_{1}$ and $\Gamma_{2}$ of differing orientations, the odd
Laplacians $\Delta_{-}(\Gamma_{1})$ and $\Delta_{-}(\Gamma_{2})$ are related
by conjugation, hence have the same eigenvalues.

With these operators in hand, we introduce the discrete Schrödinger equation.

######  Definition 2.7.

Let $\Gamma$ be a finite simple graph with m vertices and n edges, and let
$\psi:\mathbb{R}\to\mathbb{C}^{m}$ ($\mathbb{C}^{n}$) be a function assigning
a complex number to each vertex (edge) of $\Gamma$. The discrete Schrödinger
equation is defined as

$\partial_{t}\psi=\frac{i}{\hbar}\Delta_{\pm}\psi.$

######  Remark 4.

The following theorem [Mnev16] characterizes the solutions.

######  Theorem 2.8.

Solutions to the discrete Schrödinger equation are given by

$\psi(t)=e^{\frac{i}{\hbar}\Delta_{\pm}t}\psi(0).$

From now on, we will write $\psi(0)$ as $\psi_{0}$ or simply $\psi$.

###  2.1. Steady states

We now proceed to characterize steady states of the even and odd graph
Laplacians. These states are constant under the time evolution of the graph
Schrödinger equation. From these steady states, we can extract graph-theoretic
information on the connected components and independent cycles of our graph.

We show that steady states are in bijection with the kernels of the even and
odd graph Laplacians, and identify these kernels accordingly.

######  Definition 2.9.

A quantum state $\psi_{0}$ is a steady state if
$e^{\frac{i}{\hbar}\Delta_{\pm}t}\psi_{0}=\psi_{0}$ for all $t\geq 0$.

######  Theorem 2.10.

Let $A$ be an $n\times n$ matrix, $\psi_{0}\in\mathbb{C}^{n}$ be a quantum
state, $k\in\mathbb{C}$ be a nonzero complex constant, and $t$ a complex
variable. Then $e^{kAt}\psi_{0}=\psi_{0}$ for all values of $t$ if and only if
$\psi_{0}\in\ker(A)$.

###### Proof.

$(\Leftarrow)$ Suppose $\psi_{0}\in\ker(A)$, so $A\psi_{0}=0$. Then

$\displaystyle e^{kAt}\psi_{0}$
$\displaystyle=(\sum_{n=0}^{\infty}\frac{(kAt)^{n}}{n!})\psi_{0}$
$\displaystyle=(I+kAt+\frac{k^{2}A^{2}t^{2}}{2}+\frac{k^{3}A^{3}t^{3}}{3!}+...)\psi_{0}$
$\displaystyle=I\psi_{0}+kAt\psi_{0}+\frac{k^{2}A^{2}t^{2}}{2}\psi_{0}+\frac{k^{3}A^{3}t^{3}}{3!}\psi_{0}+\cdots$
$\displaystyle=I\psi_{0}+kA\psi_{0}t+\frac{k^{2}A^{2}\psi_{0}t^{2}}{2}+\frac{k^{3}A^{3}\psi_{0}t^{3}}{3!}+\cdots$
$\displaystyle=I\psi_{0}+k(0)t+\frac{k^{2}A(0)t^{2}}{2}+\frac{k^{3}A^{2}(0)t^{3}}{3!}+\cdots$
$\displaystyle=I\psi_{0}+0+0+0\cdots=I\psi_{0}=\psi_{0}.$

$(\Rightarrow)$ Suppose $e^{kAt}\psi_{0}=\psi_{0}$ for all values of $t$. Then
$\frac{\partial}{\partial t}e^{kAt}\psi_{0}=\frac{\partial}{\partial
t}\psi_{0}$. The right-hand side of this equation equals $0$ as $\psi_{0}$ is
constant for all $t$. Now, considering the left hand side of this equation, we
obtain:

$\displaystyle\frac{\partial}{\partial t}e^{kAt}\psi_{0}$
$\displaystyle=\frac{\partial}{\partial
t}(\sum_{n=0}^{\infty}\frac{(kAt)^{n}}{n!})\psi_{0}$
$\displaystyle=\frac{\partial}{\partial
t}(I+kAt+\frac{k^{2}A^{2}t^{2}}{2}+\frac{k^{3}A^{3}t^{3}}{3!}+\cdots)\psi_{0}$
$\displaystyle=(\frac{\partial}{\partial t}I+\frac{\partial}{\partial
t}kAt+\frac{\partial}{\partial
t}\frac{k^{2}A^{2}}{2}t^{2}+\frac{\partial}{\partial
t}\frac{k^{3}A^{3}}{3!}t^{3}+\cdots)\psi_{0}$
$\displaystyle=(0+kA+k^{2}A^{2}t+\frac{k^{3}A^{3}}{2}t^{2}+\cdots)\psi_{0}$
$\displaystyle=kA(I+kAt+\frac{k^{2}A^{2}t^{2}}{2}+\frac{k^{3}A^{3}t^{3}}{3!}+\cdots)\psi_{0}$
$\displaystyle=kAe^{kAt}\psi_{0}.$

By assumption, $kAe^{kAt}\psi_{0}=kA\psi_{0}$. This means $kA\psi_{0}=0$, so
$\psi_{0}\in\ker(A)$. ∎

Since we have proven that steady states are in bijection with elements in the
kernel of the graph Laplacians, it suffices to find the kernels of the even
and odd graph Laplacians in order to characterize our steady states.

We now characterize the kernel of the even Laplacian. We begin with an
intermediate lemma.

######  Lemma 2.11.

Let $\Gamma$ be a graph with connected components $\\{1,2,\dots,b_{0}\\}$. A
quantum state $\psi$ is in $\ker\Delta_{+}$ if $\psi=1$ on the vertices of the
$i$th connected component, and $0$ on all other vertices, for some
$i\in\\{1,\dots,b_{0}\\}$.

We digress to provide a brief example, from which the general method of proof
is clear.

######  Example 2.12.

Let $\Gamma$ be the oriented graph below, with two cycles and two connected
components.

Figure 3. Oriented graph with two cycles and two connected components.

The even Laplacian of $\Gamma$ is

$\Delta_{+}=\begin{bmatrix}2&-1&-1&0&0&0\\\ -1&2&-1&0&0&0\\\ -1&-1&2&0&0&0\\\
0&0&0&2&-1&-1\\\ 0&0&0&-1&2&-1\\\ 0&0&0&-1&-1&2\end{bmatrix}.$

Let $\psi=\begin{bmatrix}1\\\ 1\\\ 1\\\ 0\\\ 0\\\ 0\end{bmatrix}$ be the
quantum state with entries $1$ on the elements of the leftmost connected
component of the graph, and $0$ on all other vertices. We immediately see that

$\Delta_{+}\psi=\begin{bmatrix}2&-1&-1&0&0&0\\\ -1&2&-1&0&0&0\\\
-1&-1&2&0&0&0\\\ 0&0&0&2&-1&-1\\\ 0&0&0&-1&2&-1\\\
0&0&0&-1&-1&2\end{bmatrix}\begin{bmatrix}1\\\ 1\\\ 1\\\ 0\\\ 0\\\
0\end{bmatrix}=0,$

so that $\psi$ is in the kernel of $\Delta_{+}$ as was claimed in our lemma.

We now proceed to a formal proof of this lemma.

###### Proof.

Let $\Gamma$ be a graph with $n$ vertices. Let $v_{1},v_{2},\dots,v_{k}$ be
the vertices of a connected component of $\Gamma$.

Let

$\Delta_{+}=\begin{bmatrix}\Delta_{1,1}&\dots&\Delta_{1,n}\\\
\vdots&\ddots&\vdots\\\ \Delta_{n,1}&\dots&\Delta_{n,n}\end{bmatrix}$

and let

$\psi=\begin{bmatrix}1\\\ \vdots\\\ 1\\\ 0\\\ \vdots\\\ 0\end{bmatrix}$

be the column vector with values $[\psi]_{i,1}=\begin{cases}1&1\leq i\leq k\\\
0&k<i\leq n\end{cases}.$

Multiplying by the even Laplacian, we observe that

$\Delta_{+}\psi=\begin{bmatrix}\Delta_{1,1}\cdot 1+\dots+\Delta_{1,k}\cdot
1+\Delta_{1,k+1}\cdot 0+\dots+\Delta_{1,n}\cdot 0\\\ \vdots\\\
\Delta_{k,1}\cdot 1+\dots+\Delta_{k,k}\cdot 1+\Delta_{k,k+1}\cdot
0+\dots+\Delta_{k,n}\cdot 0\\\ \Delta_{k+1,1}\cdot 1+\dots+\Delta_{k+1,k}\cdot
1+\Delta_{k+1,k+1}\cdot 0+\dots+\Delta_{k+1,n}\cdot 0\\\ \vdots\\\
\Delta_{n,1}\cdot 1+\dots+\Delta_{n,k}\cdot 1+\Delta_{n,k+1}\cdot
0+\dots+\Delta_{n,n}\cdot 0\\\
\end{bmatrix}=\begin{bmatrix}\Delta_{1,1}+\dots+\Delta_{1,k}\\\ \vdots\\\
\Delta_{k,1}+\dots+\Delta_{k,k}\\\ \Delta_{k+1,1}\dots+\Delta_{k+1,k}\\\
\vdots\\\ \Delta_{n,1}+\dots+\Delta_{n,k}\\\ \end{bmatrix}.$

Recall that $\Delta_{+}=D-A$, where $D$ and $A$ denote the degree and
adjacency matrices of $\Gamma$ respectively. Thus, for all $\Delta_{i,j}$ with
$i>j$ and $j\in\\{1,2,\dots,k\\}$, we have $\Delta_{i,j}=0$, as vertices $i$
and $j$ are in different connected components of $\Gamma$. Thus, we have

$\Delta_{+}\psi=\begin{bmatrix}\Delta_{1,1}+\dots+\Delta_{1,k}\\\ \vdots\\\
\Delta_{k,1}+\dots+\Delta_{k,k}\\\ \Delta_{k+1,1}\dots+\Delta_{k+1,k}\\\
\vdots\\\ \Delta_{n,1}+\dots+\Delta_{n,k}\\\
\end{bmatrix}=\begin{bmatrix}\Delta_{1,1}+\dots+\Delta_{1,k}\\\ \vdots\\\
\Delta_{k,1}+\dots+\Delta_{k,k}\\\ 0\\\ \vdots\\\ 0\\\ \end{bmatrix}.$

Note that both $D(v_{i})$ and $\sum_{j=1}^{k}A_{i,j}$ count the number of
edges incident to the vertex $v_{i}$, hence are equal. Thus, we obtain our
desired result, as by definition we have
$\Delta_{i,1}+\dots+\Delta_{i,k}=D(v_{i})-\sum_{j=1}^{k}A_{i,j}=0$, so that
$\Delta_{+}\psi=0$ as desired. ∎

######  Lemma 2.13.

A quantum state is in the kernel of the even Laplacian if and only if it is
constant on each of the connected components of the graph.

###### Proof.

From [Contreras19], we know that $\dim(\ker\Delta_{+})=b_{0}$. Label our
connected components $\\{1,2,\dots,b_{0}\\}$. Let $\psi_{i}$ be the vertex
state with the value $1$ on the vertices of the $i$th connected component, and
$0$ on all other vertices. By the above lemma, each of these $\psi_{i}$ is in
the kernel of $\Delta_{+}$. Furthermore, each $\psi_{i}$ is linearly
independent, and we have one $\psi_{i}$ for each connected component, so these
$\psi_{i}$ must span $\ker\Delta_{+}$ as desired. ∎

######  Corollary 2.14.

A vertex state $\psi$ is steady if and only if $\psi$ is constant on each of
the graph’s connected components.

###### Proof.

Combining results 2.10 and 2.13, we see that a vertex state is steady if and
only if it is in the kernel of the even Laplacian if and only if it is
constant on a graph’s connected components. ∎

######  Corollary 2.15.

The vector space of steady vertex states is isomorphic to
$\mathbb{C}^{b_{0}}$.

###  2.2. Average of quantum states

We now proceed to characterize quantum states (both vertex and edge states)
which have a constant average under the Schrödinger equation.

######  Definition 2.16.

Let $\psi=\begin{bmatrix}z_{1}\\\ z_{2}\\\ \vdots\\\ z_{n}\end{bmatrix}$ be a
vertex state of a graph. We define the average of $\psi$ to be

$\mu(\psi)=\frac{z_{1}+z_{2}+\dots+z_{n}}{n}.$

######  Definition 2.17.

Let $\Delta_{\pm}$ denote the even and odd graph Laplacians. The partition
function of $\Delta_{\pm}$ is defined to be

$Z(t)=e^{\frac{i}{\hbar}\Delta_{\pm}t}.$

######  Remark 5.

The even Laplacian is a real symmetric matrix so it is Hermitian.

######  Lemma 2.18.

The partition function of a Hermitian matrix is unitary. In particular, the
partition function of the even Laplacian is unitary.

###### Proof.

Let $A$ be a Hermitian matrix; that is, $A=\overline{A}^{T}$. We want to show
$e^{iA}=I+iA+\frac{(iA)^{2}}{2}+\frac{(iA)^{3}}{3!}+...$ is unitary; that is,
$\overline{e^{iA}}^{T}=e^{-iA}$. There are a few linear algebra facts that
will be useful in this proof:

  1. (1)

$\overline{A+B}^{T}=\overline{A}^{T}+\overline{B}^{T}$

  2. (2)

$\overline{(A^{n})}^{T}=(\overline{A}^{T})^{n}$

  3. (3)

$\overline{iA}=\overline{i}\text{ }\overline{A}=-i\overline{A}$.

The proof consists of a string of equalities:

$\displaystyle\overline{e^{iA}}^{T}$ $\displaystyle=$
$\displaystyle\overline{I+iA+\frac{(iA)^{2}}{2}+\frac{(iA)^{3}}{3!}+\cdots}^{T}$
$\displaystyle=$ $\displaystyle
I+\overline{iA}^{T}+\frac{\overline{(iA)^{2}}^{T}}{2}+\frac{\overline{(iA)^{3}}^{T}}{3!}+\cdots$
$\displaystyle=$ $\displaystyle
I+\overline{iA}^{T}+\frac{(\overline{iA}^{T})^{2}}{2}+\frac{(\overline{iA}^{T})^{3}}{3!}+\cdots$
$\displaystyle=$ $\displaystyle
I+-i\overline{A}^{T}+\frac{(-i\overline{A}^{T})^{2}}{2}+\frac{(-i\overline{A}^{T})^{3}}{3!}+\cdots$
$\displaystyle=$ $\displaystyle
I+-iA+\frac{(-iA)^{2}}{2}+\frac{(-iA)^{3}}{3!}+...$ $\displaystyle=$
$\displaystyle e^{-iA}.$

∎

######  Theorem 2.19.

For a vertex state $\psi_{0}$, the average $\mu(\psi_{0})=\mu(\psi_{t})$ for
all $t\geq 0$.

###### Proof.

Let $\psi_{0}=\begin{bmatrix}z_{1}\\\ z_{2}\\\ \vdots\\\ z_{n}\end{bmatrix}$
be a vertex state on a graph. The average of $\psi_{0}$ can be given by the
inner product $\langle v,\psi_{0}\rangle$, where
$v=\begin{bmatrix}\frac{1}{n}\\\ \frac{1}{n}\\\ \vdots\\\
\frac{1}{n}\end{bmatrix}$. The partition function
$Z(t)=e^{\frac{i}{\hbar}\Delta_{+}t}$ of the even Laplacian is unitary, hence
preserves inner product. From this, we have

$\mu(\psi_{0})=\langle v,\psi_{0}\rangle=\langle
Z(t)v,Z(t)\psi_{0}\rangle=\langle v,\psi_{t}\rangle=\mu(\psi_{t}),$

where the equality $Z(t)v=v$ follows as $v$ is a steady state (constant on all
vertices), and $Z(t)\psi_{0}=\psi_{t}$ simply denotes a solution to the
Schrödinger equation over time. Thus the average is constant as desired. ∎

Having characterized the steady states of the even graph Schrödinger equation,
we now turn our attention to the odd graph Schrödinger equation.

######  Definition 2.20.

Recall that the first Betti number $b_{1}$ is equivalent to the dimension of
the cycle space of a graph. Let $c_{1},c_{2},\dots,c_{b_{1}}$ be the
independent cycles of a graph $\Gamma$. To each independent cycle $c_{i}$, we
define the independent cycle edge state $\alpha_{i}$ to be the edge state with
value $1$ on all edges with clockwise orientation on $c_{i}$, $-1$ on all
edges with counterclockwise orientation on $c_{i}$, and $0$ on all edges not
in $c_{i}$.

######  Theorem 2.21.

An edge state $\psi$ is steady for the odd Schrödinger if and only if $\psi$
represents a linear combination of independent cycle edge states.

Note that this theorem is not independent of orientation; that is, two
orientations of the same graph may admit two different spaces of steady states
of the odd Laplacian.

Let us consider $C_{3}$ with the same orientations as in Example 2.6. The
theorem above tells us that the leftmost graph has steady states
$\ker(\Delta_{-})=\displaystyle{span\left\\{\begin{bmatrix}1\\\ 1\\\
1\end{bmatrix}\right\\}}$, while the rightmost graph has steady states
$\ker(\Delta_{-})=\displaystyle{span\left\\{\begin{bmatrix}1\\\ 1\\\
-1\end{bmatrix}\right\\}}$. With this example in hand, we now prove the
theorem in general.

###### Proof.

By 2.10, it suffices to show that the kernel of $\Delta_{-}$ is spanned by
linear combinations of independent cycles. To this end, we show that every
vector representing an independent cycle is in the kernel of the incidence
matrix.

We first consider the action of the incidence matrix on a single edge $e_{k}$;
that is, on the edge state with value $1$ on the edge $e_{k}$, and value $0$
on all remaining edges. By definition, we have

$[I]_{i,j}=\begin{cases}-1&\text{edge $e_{j}$ begins at vertex $v_{i}$}\\\
1&\text{edge $e_{j}$ ends at vertex $v_{i}$}\\\ 0&\text{otherwise.}\\\
\end{cases}$

Let $v_{e_{k},i}$ and $v_{e_{k},f}$ denote the initial and final vertices of
$e_{k}$ respectively. By the above definition, using a slight abuse of
notation, we see that $Ie_{k}=v_{e_{k},f}-v_{e_{k},i}$ (where here, $e_{k}$,
$v_{e_{k},i}$, and $v_{e_{k},i}$ represent the edge and vertex states with
value $1$ on $e_{k}$, $v_{e_{k},i}$, and $v_{e_{k},i}$ respectively and $0$ on
all other edges and vertices).

We now consider the action of $I$ on an independent cycle edge state. Let
$\alpha_{i}$ be an independent cycle edge state. We many decompose
$\alpha_{i}$ into a sum of its individual edges
$\alpha_{i}=e_{i,1}+e_{i,1}+\cdots+e_{i,k_{i}}$. Without loss of generality,
we may assume the final vertex of each edge $e_{i,j}$ is the initial vertex of
the edge $e_{i,j+1}$ and the final vertex of $e_{i,k_{i}}$ is the initial
vertex of $e_{i,1}$). By linearity, we obtain
$I\alpha_{i}=Ie_{i,1}+Ie_{i,2}+\cdots+Ie_{i,k_{i}}$. Combining this with our
previous consideration of the action of $I$ on individual edges, we know

$Ie_{i,1}+Ie_{i,2}+\cdots+Ie_{i,k_{i}}=(v_{e_{1},f}-v_{e_{1},i})+(v_{e_{2},f}-v_{e_{2},i})+\cdots+(v_{e_{k_{i}},f}-v_{e_{k_{i}},i}).$

Since we have chosen our independent cycle edge states to have value $1$ on
clockwise oriented edges and $-1$ on counterclockwise oriented edges, and our
edges are assumed to be consecutive, we see that

$(v_{e_{1},f}-v_{e_{1},i})+(v_{e_{2},f}-v_{e_{2},i})+\cdots+(v_{e_{k_{i}},f}-v_{e_{k_{i}},i})=(v_{e_{1},f}-v_{e_{k_{i}},f})+(v_{e_{2},f}-v_{e_{1},f})+\cdots+(v_{e_{k_{i}},f}-v_{e_{k_{i}-1},f}).$

This sum telescopes to the zero vector as desired.

From this, we see that all independent cycle edge states are in
$\ker(\Delta_{-})$; indeed, for an independent cycle edge state $\alpha$, by
the above we have

$\Delta_{-}\alpha=I^{t}I\alpha=0,$

so that $\alpha\in\ker(\Delta_{-})$ as desired.

Lastly, recall that $\dim\ker(\Delta_{-})=b_{1}$. Each independent cycle edge
state is linearly independent, and moreover, we have precisely $b_{1}$ of
these states, so that the kernel of $\Delta_{-}$ is equal to the span of
independent cycle edge states. Thus by Theorem 2.10, we see that a state is
steady if and only if it is a linear combination of independent cycle edge
states as desired. ∎

##  3\. The graph Dirac operator and the Dirac equation

###  3.1. Matrix representations of graph Dirac operators

We now proceed to consider the graph Dirac operators. These operators can be
viewed as formal square roots of the graph Laplacians. Note that both the even
and odd Laplacian are real symmetric matrices, hence are diagonalizable.

Let $Q_{+}D_{+}Q_{+}^{-1}$ and $Q_{-},D_{-},Q_{-}^{-1}$ be the
diagonalizations of the even and odd Laplacians respectively. Let
$\sqrt{D_{\pm}}$ be the matrix given by taking the square root of each
diagonal entry. The graph Dirac operators are defined as follows.

######  Definition 3.1.

The Even Dirac operator is defined as
$\not{D}_{+}=Q_{+}\sqrt{D_{+}}Q_{+}^{-1}.$

######  Definition 3.2.

The Odd Dirac operator is defined as
$\not{D}_{-}=Q_{-}\sqrt{D_{-}}Q_{-}^{-1}.$

To see that the above operators serve as formal square roots of the even and
odd Laplacians, note that we have

$(\not{D}_{\pm})^{2}=Q_{\pm}\sqrt{D_{\pm}}Q_{\pm}^{-1}Q_{\pm}\sqrt{D_{\pm}}Q_{\pm}^{-1}=\Delta_{\pm},$

as desired.

######  Definition 3.3.

The Incidence Dirac operator is defined as $\not{D}_{I}=\begin{pmatrix}0&I\\\
I^{t}&0\end{pmatrix}$.

The incidence Dirac operator also serves as a formal square root of the
Laplace operators, as we have

$(\not{D}_{I})^{2}=\begin{pmatrix}\Delta_{+}&0\\\ 0&\Delta_{-}\end{pmatrix}.$

In this section, we study the linear algebraic properties of the graph Dirac
operators. In particular, we prove $\ker\not{D}_{\pm}=\ker\Delta_{\pm}$ and
$\ker\not{D}_{I}=\ker\not{D}_{+}\bigoplus\not{D}_{-}$. Additionally, we prove
a relationship between the nonzero eigenvalues of $\not{D}_{I}$ and the
nonzero eigenvalues of $\Delta_{\pm}.$

######  Proposition 3.4.

$\ker{I^{t}}=\ker{\Delta^{+}}$ and $\ker{I}=\ker{\Delta^{-}}$.

###### Proof.

We prove the first equality; the second follows analogously. We first show
$\ker I^{t}\subseteq\ker\Delta_{+}$. Indeed, suppose $v\in\ker I^{t}$. Then
$\Delta_{+}v=I(I^{t}v)=0$, so $v\in\ker\Delta_{+}$. Conversely, suppose
$v\in\ker\Delta_{+}$. Then $\Delta_{+}v=II^{t}v=0$, so that
$v^{t}(II^{t}v)=(I^{t}v)^{t}(I^{t}v)=\|I^{t}v\|=0$, so that $I^{t}v=0$ as
desired. ∎

######  Proposition 3.5.

$\not{D}_{+}$ and $\not{D}_{-}$ are non-negative definite matrices,
$\ker{\not{D}_{+}}=\ker{\Delta_{+}}$, and
$\ker{\not{D}_{-}}=\ker{\Delta_{-}}$.

###### Proof.

We first claim that $\not{D}_{+}$ is non-negative definite. Let $QDQ^{-1}$ be
the diagonalization of $\Delta_{+}$. Since $\Delta_{+}$ is non-negative
definite, all entries in the matrix $D$ will be non-negative, so that all
entries in the diagonal matrix $\sqrt{D}$ of $\not{D}_{+}=Q\sqrt{D}Q^{-1}$
will be non-negative. Thus, the eigenvalues of $\not{D}_{+}$ are non-negative,
so $\not{D}_{+}$ is non-negative definite as desired.

We next claim that $\ker{\not{D}_{+}}=\ker{\Delta_{+}}$. To this end, we show
that $\ker\not{D}_{+}\subseteq\ker\Delta_{+}$, and
$\dim\ker\not{D}_{+}=\dim\ker\Delta_{+}$.

To see the first of these claims, let $v\in\ker\not{D}_{+}$. By definition
$\not{D}_{+}v=0$, so that $\Delta_{+}v=\not{D}_{+}(\not{D}_{+}v)=0$. Thus we
have $v\in\ker\Delta_{+}$ as desired.

We now demonstrate the second claim. Let
$\lambda_{1},\lambda_{2},\dots,\lambda_{n}$ be the eigenvalues of
$\Delta_{+}$. By definition, we see the eigenvalues of $\not{D}_{+}$ are
$\sqrt{\lambda_{1}},\sqrt{\lambda_{2}},\dots,\sqrt{\lambda_{n}}$.

Recall that $\dim\ker\Delta_{+}$ is precisely the geometric multiplicity of
the eigenvalue $0$. From the above, we see that the algebraic multiplicities
of $0$ for $\Delta_{+}$ and $\not{D}_{+}$ are equal. Each of these matrices
are diagonalizable, hence the geometric multiplicities of $0$ for $\Delta_{+}$
and $\not{D}_{+}$ are equal, so that $\dim\ker\Delta_{+}=\dim\ker\not{D}_{+}$
as desired.

Similarly, $\not{D}_{-}$ is a non-negative definite matrix and
$\ker{\not{D}_{-}}=\ker{\Delta_{-}}$.

∎

######  Remark 6.

We know that $\ker\Delta_{+}\cong\mathbb{C}^{b_{0}}$ and
$\ker\Delta_{-}\cong\mathbb{C}^{b_{1}}$, so by the above we have
$\ker\not{D}_{+}\cong\mathbb{C}^{b_{0}}$ and
$\ker\not{D}_{-}\cong\mathbb{C}^{b_{1}}$.

######  Proposition 3.6.

$\ker{\not{D}_{I}}=\ker{\Delta^{+}}\bigoplus\ker{\Delta^{-}}$.

###### Proof.

We first prove that $\ker\not{D}_{I}=\ker I^{t}\bigoplus\ker I$. Let
$v=\begin{bmatrix}x\\\ y\end{bmatrix}$ where $x\in\mathbb{C}^{|V|}$ and
$y\in\mathbb{C}^{|E|}$. By definition, we see

$v\in\ker\not{D}_{I}\iff\begin{bmatrix}0&I\\\
I^{t}&0\end{bmatrix}\begin{bmatrix}x\\\
y\end{bmatrix}=0\iff\begin{bmatrix}Iy\\\
I^{t}x\end{bmatrix}=\begin{bmatrix}0\\\ 0\end{bmatrix}.$

Thus we see $v=\begin{bmatrix}x\\\ y\end{bmatrix}\in\ker\not{D}_{I}\iff
x\in\ker I^{t}\text{ and }y\in\ker I$ so that by proposition 3.4 we have

$\ker{\not{D}_{I}}=\ker{I^{t}}\bigoplus\ker{I}=\ker{\Delta^{+}}\bigoplus\ker{\Delta^{-}}.$

∎

######  Proposition 3.7.

The eigenvalues of $\not{D}_{I}$ are independent of orientation.

###### Proof.

Let $\Gamma$ and $\Gamma^{\prime}$ be two orientations of the same graph. Let
$v$ be a vertex state on this graph, and let $e=\begin{pmatrix}e_{1}\\\
e_{2}\\\ \vdots\\\ e_{n}\end{pmatrix}$ be an edge state on this graph. Without
loss of generality, assume $\Gamma$ and $\Gamma^{\prime}$ differ on edges
$e_{1},\cdots,e_{k}$. Suppose $\not{D}_{I}(\Gamma)\begin{pmatrix}v\\\
e\end{pmatrix}=\lambda\begin{pmatrix}v\\\ e\end{pmatrix}$, so that $\lambda$
is an eigenvalue of $\Gamma$. Then $I(\Gamma)e=\lambda v$ and
$I^{t}(\Gamma)v=\lambda e$. By definition of the incidence matrix, for each
$i\leq k$, we have col${}_{i}(I(\Gamma^{\prime}))=-\text{col}_{i}(I(\Gamma))$,
so that $I(\Gamma^{\prime})\begin{pmatrix}-e_{1}\\\ \vdots\\\ -e_{k}\\\
e_{k+1}\\\ \vdots\\\ e_{n}\end{pmatrix}=I(\Gamma)e=\lambda v$.

Because $I^{t}(\Gamma)v=\lambda e$, we know from the relationship between
their columns that
$I^{t}(\Gamma^{{}^{\prime}})v=\lambda\begin{pmatrix}-e_{1}\\\ \vdots\\\
-e_{k}\\\ e_{k+1}\\\ \vdots\\\ e_{n}\end{pmatrix}$. Thus,
$\not{D}_{I}(\Gamma^{\prime})\begin{pmatrix}v\\\ -e_{1}\\\ \vdots\\\ -e_{k}\\\
e_{k+1}\\\ \vdots\\\ e_{n}\end{pmatrix}=\lambda\begin{pmatrix}v\\\ -e_{1}\\\
\vdots\\\ -e_{k}\\\ e_{k+1}\\\ \vdots\\\ e_{n}\end{pmatrix}$, so $\lambda$ is
an eigenvalue for $\not{D}_{I}(\Gamma^{\prime})$. ∎

######  Corollary 3.8.

The non-zero eigenvalues of $\not{D}_{I}$ are
$-\sqrt{\lambda_{1}},\sqrt{\lambda_{1}},-\sqrt{\lambda_{2}},\sqrt{\lambda_{2}},\cdots,-\sqrt{\lambda_{n}},\sqrt{\lambda_{n}}$,
where $\lambda_{1},\cdots,\lambda_{n}$ are the non-zero eigenvalues of
$\Delta_{\pm}$.

###### Proof.

Let $\lambda_{1},\dots,\lambda_{n}$ be the nonzero eigenvalues of
$\Delta_{\pm}$. Because $\not{D}_{I}^{2}=\begin{bmatrix}\Delta_{+}&O\\\
O&\Delta_{-}\end{bmatrix}$, we have
$P_{\not{D}_{I}^{2}}(t)=P_{\Delta_{+}}(t)\cdot P_{\Delta_{-}}(t)$, where
$P_{A}(t)$ denotes the characteristic polynomial of a matrix $A$.

Because $\not{D}_{I}^{2}=\begin{bmatrix}\Delta_{+}&O\\\
O&\Delta_{-}\end{bmatrix}$, we have
$P_{\not{D}_{I}^{2}}(t)=P_{\Delta_{+}}(t)\cdot P_{\Delta_{-}}(t)$, where
$P_{A}(t)$ denotes the characteristic polynomial of a matrix $A$. We know that
$\Delta_{+}$ and $\Delta_{-}$ have the same eigenvalues with the same
multiplicity, so the non-zero eigenvalues of $\not{D}_{I}^{2}$ are
$\lambda_{1},\lambda_{1},\lambda_{2},\lambda_{2},\cdots,\lambda_{n},\lambda_{n}$.
Then the non-zero eigenvalues of $\not{D}_{I}$ are
$\pm\sqrt{\lambda_{1}},\pm\sqrt{\lambda_{1}},\cdots,\pm\sqrt{\lambda_{n}},\pm\sqrt{\lambda_{n}}$.
If $a$ is an eigenvalue of $\not{D}_{I}$, then $-a$ is an eigenvalue of
$-\not{D}_{I}$. Because this is equivalent to the Incidence Dirac for the same
graph with the opposite orientations, Proposition 3.7 tells us that $-a$ must
also be an eigenvalue for $\not{D}_{I}$. This means that for each pair of
$\pm\sqrt{\lambda_{i}}$ eigenvalues, if one is positive the other must be
negative, and vice-versa. ∎

###  3.2. Visualization

We implemented a program in Python which computes solutions to the different
versions of the Dirac equation over time, given a random graph and initial
random quantum state (vertex state for even Dirac operator, edge state for odd
Dirac operator, vertex and edge state for incidence Dirac operator).

We plotted average position and average angle of these solutions over time,
where average position is given as the average of real components and the
average of imaginary components, and average angle is given as the angle
formed by the coordinates of the average position in the complex plane.

Figure 4 is a typical plot of average position over time for solutions to the
Dirac equation for the even, odd, and incidence Dirac operators, for a random
graph with 10 vertices.

(a) Even Dirac operator.

(b) Odd Dirac operator.

(c) Incidence Dirac operator.

Figure 4. Plots of average position over time for a random quantum state.

The geometric features of these plots can yield information to the behavior of
the quantum system over time. As a brief example, consider a quantum state
which is constant on each connected component of a graph. By corollary 2.14,
we know that such a quantum state is steady over time. Figure 5 plots the
average angle and position over time of a quantum state in the kernel of a
graph. The nonconstant behavior of the graph is due to rounding error in
Python.

(a) average angle over time.

(b) average position in complex plane.

Figure 5. Plots of a vertex state in the kernel of the even Dirac operator.

###  3.3. Quadratic forms

We can encode information on the eigenvalues of the graph operators via their
quadratic forms, as their signatures provide invariants of the graph, which
determine the behavior of the solutions of the graph Schrödinger and Dirac
equations.

######  Definition 3.9.

For a symmetric matrix $M$, its associated quadratic form is defined as
$q_{M}(v)=v^{t}Mv$

Using this definition we find graph theoretical expressions for the quadratic
forms of our graph operators. For instance, it is well known
[nica_SpectralGraph] that the quadratic form of $\Delta_{+}$ is

$q_{\Delta_{+}}(v)=\sum_{e_{i,j}\in E(\Gamma)}(v_{j}-v_{i})^{2}.$ (3)

We find similar expressions for the quadratic forms of other operators. Where
the even Laplacian sums a function on the vertices over the edges, the odd
Laplacian sums a similar function on the edges over the vertices.

######  Proposition 3.10.

The quadratic form of the odd Laplacian is

$q_{\Delta_{-}}(e)=\sum_{v_{i}\in V(\Gamma)}\big{(}\sum_{e_{i,j}\in
E(\Gamma)}k_{i,j}\cdot e_{i,j}\big{)}^{2},$

where $k_{i,j}=\begin{cases}-1&e_{i,j}\text{ leaves }v_{i}\\\ 1&e_{i,j}\text{
enters }v_{i}\end{cases}.$

###### Proof.

From the definition of the odd Laplacian, we have that

$\Delta_{-}(i,j)=\begin{cases}2&i=j\\\ 0&i\neq j,e_{i}\text{ not incident to
}e_{j}\\\ 1&i\neq j,e_{i}\text{ incident to }e_{j},\text{ both start or end at
}v_{s}\\\ -1&i\neq j,e_{i}\text{ incident to }e_{j},\text{ one starts and the
other ends at }v_{s}.\\\ \end{cases}$

For each $v_{s}\in V(\Gamma)$, there are $\frac{D(v_{s})(D(v_{s})-1)}{2}$
terms of the form $(-1)^{k}2e_{i,s}\cdot e_{j,s}$, where $k=0$ when $e_{i}$
and $e_{j}$ both start or end at $v_{s}$ and $k=1$ when one starts and the
other ends at $v_{s}$. The diagonal adds the term $2e_{i,j}^{2}$ to the
quadratic form. Each edge is incident to exactly two vertices, thus we assign
a squared term to each of these vertices. Thus for each $v_{s}$, we have

$\sum_{e_{i,s}\in E(\Gamma)}\left(e_{i,s}^{2}+\sum_{e_{j,s}\neq e_{i,s}\in
E(\Gamma)}(-1)^{k}2e_{i,s}\cdot e_{j,s}\right)$

in this quadratic form. Because each $e_{i,s}$ which appears in the second sum
will appear in our first, this sum is equal to

$\left(\sum_{e_{i,s}\in E(\Gamma)}k_{i,s}e_{i,s}\right)^{2},$

where $k=-1$ if an edge starts at $v_{s}$ and $k=1$ if it ends at $v_{s}$.
Adding these terms for each vertex finishes the proof. ∎

######  Proposition 3.11.

The quadratic form of the incidence Dirac operator $\not{D}_{I}$ is

$q_{\not{D}_{I}}\begin{pmatrix}v\\\ e\end{pmatrix}=2\sum_{e_{i,j}\in
E(\Gamma)}e_{i,j}\cdot(v_{j}-v_{i}).$

###### Proof.

Because $(v^{t}\ e^{t})\not{D}_{I}\begin{pmatrix}v\\\
e\end{pmatrix}=v^{t}Ie+e^{t}I^{t}v$, and these $1\times 1$ matrices are
transposes of one another, they are equal, giving $(v^{t}\
e^{t})\not{D}_{I}\begin{pmatrix}v\\\ e\end{pmatrix}=2e^{t}I^{t}v$. Each row of
$I^{t}$ represents some $e_{i,j}$, and returns $v_{j}-v_{i}$ (where $e_{i,j}$
goes from $v_{j}$ to $v_{i}$), so when we multiply this out, we get
$\sum_{e_{i,j}\in E(\Gamma)}e_{i,j}\cdot(v_{j}-v_{i})$. ∎

Because the roots of the quadratic form of a non-negative definite matrix are
exactly the vectors in the kernel of the matrix, the set of roots of
$q_{\Delta_{\pm}}$ (denoted by root$(q_{\Delta_{\pm}})$) provides important
graph-theoretical information. Specifically, $q_{\Delta_{+}}(v)=0$ if and only
if $v$ is constant on connected components, and $q_{\Delta_{-}}(e)=0$ if and
only if $e$ represents a cycle on the graph. Interestingly, there is not a
similar equality for $\not{D}_{I}$, as stated in the following proposition.

######  Proposition 3.12.

$\text{root
}(q_{\not{D}_{I}})\supseteq\ker(\Delta_{+})\bigoplus\mathbb{C}^{|E|}\cup\mathbb{C}^{|V|}\bigoplus\ker(\Delta_{-}).$

###### Proof.

If $v\in\ker(\Delta_{+})$, then we know $v$ is constant on connected
components, so $v_{j}-v_{i}=0$ for each $e_{i,j}\in E(\Gamma)$. Then for any
$e$, we will have that $q_{\not{D}_{I}}(v\bigoplus e)=0$.
For $e\in\ker(\Delta_{-})$, any non-zero terms of $e$ must be a part of a
cycle, so by definition of $q_{\not{D}_{I}}$, each $v_{i}$ will be added and
subtracted exactly once on the cycle (if an edge goes in the opposite
direction to an incident edge, the edge term must have the opposite sign to be
in the kernel). From the properties of $\ker(\Delta_{-})$, the terms by which
these vertex terms are multiplied will be equal, so $v\bigoplus e$ is a root
of our quadratic for any $v$.

∎

Because the eigenvalues of the Incidence Dirac operator come in pairs of
positive and negative values, it is not non-negative definite, so the root of
the quadratic form doesn’t match with the kernel of the matrix as it did for
the Laplace operators. For this reason, it is not clear what the entire root
of $q_{\not{D}_{I}}$ would look like for most graphs.
An example of a graph where we can see the entire root of $q_{\not{D}_{I}}$ is
$P_{2}$, for which we have

$\not{D}_{I}=\begin{pmatrix}0&0&-1\\\ 0&0&1\\\ -1&1&0\end{pmatrix}.$

Here, if $v\bigoplus e\in{\rm root}(q_{\not{D}_{I}})$, we must have that
either $e=0$ or $v_{1}=v_{2}$, so in this case $\text{root
}(q_{\not{D}_{I}})=\ker(\Delta_{+})\bigoplus\mathbb{C}^{|E|}\cup\mathbb{C}^{|V|}\bigoplus\ker(\Delta_{-})$
By contrast, cycle graphs will have many roots which are not a part of this
union. For example, the vector $\begin{pmatrix}1\\\ 2\\\ 2\\\ 2\\\ 1\\\
2\end{pmatrix}$ is a root for $q_{\not{D}_{I}}$ for the oriented graph in
Figure 6.

Figure 6. Oriented cycle graph $C_{3}$.

###  3.4. Powers of $\not{D}_{I}$

An interesting property of the Laplace operators is the fact that the entries
of the powers of these matrices encode combinatorial information about
superwalks on the graph, as explained by [Yu17].
A vertex superwalk of length 1 starting at $v_{i}$ can

  1. (1)

go through an incident edge to one of it’s neighbors, in which case
sgn$(\gamma)=-1$, or

  2. (2)

go through an incident edge and return to $v_{i}$, in which case
sgn$(\gamma)=1$.

Similarly, an edge superwalk of length 1 starting at $e_{i}$ can

  1. (1)

go through an incident vertex $v$ to an adjacent edge $e_{j}$, in which case
sgn$(\gamma)=1$ if $e_{j}$ and $e_{i}$ both go into or both leave $v$ and
sgn$(\gamma)=-1$ if one of $e_{j}$ and $e_{i}$ enters $v$ and the other exits
it, or

  2. (2)

go to an incident vertex and back to $e_{i}$ in which case sgn$(\gamma)=1$.

Similarly, we can define a new type of walk on the graph which is encoded by
the Incidence Dirac operator.

######  Definition 3.13.

A vertex-edge walk of length 1 moves from a vertex to an incident edge, or an
edge to an incident vertex. We can define the sign of the walk as follows: If
the edge involved in the walk originates from the vertex involved then
sgn$(\gamma)=-1$ and if the edge enters the vertex involved then
sgn$(\gamma)=1$. Note for this definition we do not care whether we’re
starting at a vertex or an edge. For a graphical way of thinking about the
signs of these walks see figure 7.
A vertex-edge walk of length $k$ is a combination of $k$ walks of length 1,
and has a sign equal to the product of the signs of each step.

Figure 7. Signs of vertex-edge walks on a $P_{2}$ graph.

By this definition, we note that vertex superwalks are vertex-edge walks with
an even length, while edge superwalks are vertex-edge walks of an odd length.

######  Theorem 3.14.

$\not{D}_{I}^{k}(i,j)=\sum_{\gamma,i\to j,k}\text{sgn}(\gamma).$

###### Proof.

We will prove this theorem by induction on $k$.
Letting $k=1$, we know $\not{D}_{I}=\begin{pmatrix}O&I\\\
I^{t}&O\end{pmatrix}$, and checking these entries we see that the theorem is
true.
Let it be true for some arbitrary $k-1$. There are two cases.
Case 1: Let $k-1$ be odd. Then
$\not{D}_{I}^{k}=\begin{pmatrix}\Delta_{+}^{k/2}&O\\\
O&\Delta_{-}^{k/2}\end{pmatrix}$, so we know that the entries count vertex
superwalks and edge superwalks of length $k/2$, which means that they count
vertex-edge walks of length $k$.
Case 2: Let $k-1$ be even. Then
$\not{D}_{I}^{k}=\begin{pmatrix}O&\Delta_{+}^{(k-1)/2}I\\\
\Delta_{-}^{(k-1)/2}I^{t}&O\end{pmatrix}$. We know there cannot be vertex or
edge superwalks, so the $0$ block matrices are expected. Because the other
block matrices are transposes of one another, we will analyze
$A=\Delta_{+}^{(k-1)/2}I$. Looking at each entry, we have

$a_{i,j}=row_{i}(\Delta_{+}^{(k-1)/2})\cdot col_{j}(I)=1\cdot\sum_{\gamma,i\to
n,k-1}\text{sgn}(\gamma)-1\cdot\sum_{\gamma,i\to m,k-1}\text{sgn}(\gamma),$

where $e_{j}$ goes from $v_{m}$ to $v_{n}$. Then because the last step of a
vertex-edge walk starting at $v_{i}$ and ending at $e_{j}$ must include one of
the vertices adjacent to $e_{j}$, our sum must include a term for each such
walk, and we have that $a_{i,j}=\sum_{\gamma,i\to j,k}\text{sgn}(\gamma)$. ∎

As an example of this result we look to the third power of the incidence
matrix for $K_{3}$ with clockwise orientation.

$\not{D}_{I}^{3}=\begin{pmatrix}0&0&0&0&3&-3\\\ 0&0&0&-3&0&3\\\
0&0&0&3&-3&0\\\ 0&-3&3&0&0&0\\\ 3&0&-3&0&0&0\\\ -3&3&0&0&0&0\end{pmatrix}.$

Here we see that there are 3 vertex-edge walks between a vertex and and an
incident edge, and that the powers follow as expected. Looking at the entries
between $v_{1}$ and $e_{1}$, we see a value of 0, because there are two such
walks of length 3 connecting these elements, but these walks have opposite
signs, cancelling one another out as seen in Figure 8.

Figure 8. Length 3 walks from $v_{1}$ to $e_{1}$.

The full list of vertex edge walks and their signs for $K_{3}$ originating at
$v_{1}$, each of which is equivalent to performing the same moves at one of
the other vertices.

$\displaystyle\gamma_{1}$ $\displaystyle=v_{1}\to e_{2}\to v_{3}\to e_{1}\ \ \
\ \ \ $ $\displaystyle sgn(\gamma_{1})=-1$ $\displaystyle\gamma_{2}$
$\displaystyle=v_{1}\to e_{3}\to v_{2}\to e_{1}\ \ \ \ \ \ $ $\displaystyle
sgn(\gamma_{2})=1$ $\displaystyle\gamma_{3}$ $\displaystyle=v_{1}\to e_{2}\to
v_{3}\to e_{2}\ \ \ \ \ $ $\displaystyle sgn(\gamma_{3})=1$
$\displaystyle\gamma_{4}$ $\displaystyle=v_{1}\to e_{2}\to v_{1}\to e_{2}\ \ \
\ \ $ $\displaystyle sgn(\gamma_{4})=1$ $\displaystyle\gamma_{5}$
$\displaystyle=v_{1}\to e_{3}\to v_{1}\to e_{2}\ \ \ \ \ $ $\displaystyle
sgn(\gamma_{5})=1$ $\displaystyle\gamma_{6}$ $\displaystyle=v_{1}\to e_{3}\to
v_{2}\to e_{3}\ \ \ \ \ $ $\displaystyle sgn(\gamma_{6})=-1$
$\displaystyle\gamma_{7}$ $\displaystyle=v_{1}\to e_{3}\to v_{1}\to e_{3}\ \ \
\ \ $ $\displaystyle sgn(\gamma_{7})=-1$ $\displaystyle\gamma_{8}$
$\displaystyle=v_{1}\to e_{2}\to v_{1}\to e_{3}\ \ \ \ \ $ $\displaystyle
sgn(\gamma_{8})=-1.$

##  4\. Dimer models and a gluing formula for Dirac operators

Gluing formulae for discrete operators have been studied in mathematical
physics [Reshetikhin:2014jaa], and in the case of the discrete Laplace
operator, it has some interesting connections with graph theory [Contreras20].
On the other hand, dimer models have been studied extensively in the context
of statistical physics, dimer models, quantum mechanics and combinatorics
[Cimasoni07, KenyonNotes, Kenyon2002].

In this section we describe a combinatorial interpretation of a gluing formula
for the Kastelyn matrix, which can be regarded as a discrete Dirac operator
for lattice graphs.

###  4.1. Graph gluing

First, we define two different types of gluing of graphs, which are relevant
while discussing gluing identities for graph Dirac operators.

######  Definition 4.1.

Let $\Gamma_{1}$ and $\Gamma_{2}$ be two graphs. Let $\Gamma^{\partial}_{1}$
and $\Gamma^{\partial}_{2}$ be isomorphic subgraphs of $\Gamma_{1}$ and
$\Gamma_{2}$ respectively. Then
$I=\Gamma^{\partial}_{1}=\Gamma^{\partial}_{2}$ is an interface of
$\Gamma_{1}$ and $\Gamma_{2}$.

######  Definition 4.2.

Let $\Gamma_{1}$ and $\Gamma_{2}$ be two graphs and $I$ an interface. The
interface gluing of the two graphs $\Gamma_{1}\sqcup_{I}\Gamma_{2}$ is defined
by: $V(\Gamma_{1}\sqcup_{I}\Gamma_{2})=(V(\Gamma_{1})\setminus
V(I))\cup(V(\Gamma_{2})\setminus V(I))\cup V(I)$ and
$E(\Gamma_{1}\sqcup_{I}\Gamma_{2})=(E(\Gamma_{1})\setminus
V(I))\cup(E(\Gamma_{2})\setminus E(I))\cup E(I)$.

######  Definition 4.3.

Let $\Gamma_{1}$ and $\Gamma_{2}$ be two graphs. Let
$\\{v_{1,1},...,v_{1,k}\\}\subseteq\Gamma_{1}$ and
$\\{v_{2,1},...,v_{2,k}\\}\subseteq\Gamma_{2}$. Let $\\{e_{1},...,e_{k}\\}$ be
the set of edges that connect the pairs of vertices
$(v_{1,1},v_{2,1}),...,(v_{1,k},v_{2,k})$. Then a bridge graph $B$ between
$\Gamma_{1}$ and $\Gamma_{2}$ is the graph with
$V(B)=\\{v_{1,1},...,v_{1,k},v_{2,1},...,v_{2,k}\\}$ and
$E(B)=\\{e_{1},...,e_{k}\\}$.

######  Definition 4.4.

Let $\Gamma_{1}$ and $\Gamma_{2}$ be two graphs and $B$ a bridge graph. The
bridge gluing of the two graphs $\Gamma_{1}\sqcup_{B}\Gamma_{2}$ is defined
by: $V(\Gamma_{1}\cup_{B}\Gamma_{2})=V(\Gamma_{1})\cup V(\Gamma_{2})$ and
$E(\Gamma_{1}\sqcup_{B}\Gamma_{2})=E(\Gamma_{1})\cup E(B)\cup E(\Gamma_{2})$.

A perfect matching of a graph is a set of edges such that each vertex is
connected to exactly one edge. Kasteleyn’s Theorem [Kasteleyn] allows us to
connect the number of perfect matchings to the Kasteleyn matrix, $K$, defined
as the weighted adjacency matrix of a graph $G$, with horizontal edges
weighted 1 and vertical edges weighted $i=\sqrt{-1}$. We are interested in
this matrix because of its connection to graph quantum mechanics: following
[KenyonNotes], the matrix $K$ acts like a Dirac operator when restricted to
sublattices of a lattice graph. That is, when a lattice graph’s Kastelyn
matrix is restricted to the four sublattices comprised of vertices spaced two
apart in each cardinal direction, $K^{*}K=\Delta_{+}$.

Figure 9. Visual representation of Kasteleyn operating on graph as a
Laplacian.

We reinterpret Kasteleyn’s theorem by introducing explicit recurrence
relations for perfect matchings of integer lattices. We prove gluing
identities for the determinants of Kasteleyn matrices by introducing explicit
formulae for perfect matchings of integer lattices when one of the sides is 2,
3, or 4. We denote an $k$ by $n$ lattice graph as $L_{k,n}$ and the number of
ways to tile $L_{k,n}$ as $T_{k}(n)$.

###  4.2. The $2\times n$ case

######  Theorem 4.5.

The number of unique ways that dominos can tile $L_{2,n}$ is given by the
recursive formula $T_{2}(n)=T_{2}(n-1)+T_{2}(n-2)$, where $T_{2}(1)=1$ and
$T_{2}(2)=2$.

###### Proof.

For clarity of notation, note that $L_{2,n}$ has 2 rows of vertices and $n$
columns of vertices (so here a vertical domino fills one column of the graph).
We can see that when $n=1$, $T_{2}(n)=1$, as it can only be filled by placing
the domino vertically, and when $n=2$, $T_{2}(n)=2$, as it can be filled by
placing both tiles vertically or both tiles horizontally
We will now prove that for all $n>2$, $T_{2}(n)=T_{2}(n-1)+T_{2}(n-2)$.
Let $n>2$ be arbitrary. We can split the possible ways of filling our graph
into 2 cases, depending on the orientation of the tile(s) in the first column
Case 1: Let the first column be filled by a vertically placed domino. Then we
have a $L_{2,n-1}$ graph left to fill, so from the definition of our function
we have that there are $T_{2}(n-1)$ unique ways to tile the graph.
Case 2: Let the first 2 columns be filled by 2 horizontally placed dominos.
Then we have a $L_{2,n-2}$ graph left to fill, so there will be $T_{2}(n-2)$
unique ways to tile the graph.
Now because each possible way to fill the graph is given by one of these two
cases, $T_{2}(n)$ will be the sum of the number of ways to fill the graph in
each of these cases, so we have that $T_{2}(n)=T_{2}(n-1)+T_{2}(n-2)$. ∎

Figure 10. Cases for end of a $2\times n$ graph.

We can also find the formula for the number of perfect matchings for two such
graphs glued together. In order to talk about this in more general terms, we
will introduce notation for such a formula, given by $T_{k}(m\sqcup_{s,B}n)$,
where we are gluing $L_{k,m}$ and $L_{k,n}$ graphs such that their sides of
length $k$ are aligned, with $s$ indicating by how many vertices the right
graph has been shifted down relative to the left, as seen in 12, and $B$ being
the set of bridges from the gluing included in the perfect matching. $s$ and
$B$ aren’t extremely impactful in the $2\times n$ case, but make a big
difference with bigger graphs.

######  Theorem 4.6.

The number of perfect matchings of $L_{2,m}$ and $L_{2,n}$ glued together with
a shift is given by

$T_{2}(m\sqcup_{s,B}n)=\begin{cases}T_{2}(m)T_{2}(n)&s=1\text{ or
}2,B=\emptyset\\\ 0&s=0\text{ or }1,B=\\{e_{1}\\}\\\
T_{2}(m)T_{2}(n)+T_{2}(m-1)T_{2}(n-1)&s=0,B=\emptyset\text{ or
}\\{e_{1},e_{2}\\}.\end{cases}\\\ $

###### Proof.

We begin by noting that in the case of a shift 1 or 2 gluing, it is only
possible to tile the graph if we treat them separately, giving rise to the
first equation. In general, for $T_{k}(m\sqcup_{s,B}n)$ where $k$ is even and
$|B|$ is odd, we find that there are 0 ways to tile because that would leave
an odd number of spaces to tile on either side of the gluing.
For the third case, letting $m$ and $n$ be arbitrary, we want to find how many
ways we can tile the $2\times(m+n)$ graph formed by gluing $2\times m$ and
$2\times n$ graphs together. We can split this into two sub-cases: that where
we include both bridges in the matching and that where neither are included.
Case 1: Let there be no bridges between the graphs. Then for each possible
tiling of the $2\times m$ graph, there are $T_{2}(n)$ ways to finish the
tiling. Thus, in this case there are $T_{2}(m)T_{2}(n)$ solutions.
Case 2: Let there be bridges between the graphs. Then we have a $2\times(m-1)$
and a $2\times(n-1)$ graph left to fill, so there will be
$T_{2}(m-1)T_{2}(n-1)$ solutions. This completes the proof. ∎

###  4.3. The $3\times n$ case

######  Theorem 4.7.

The number of unique ways that dominos can tile $L_{3,n}$ is given by the
recursive formula $T_{3}(n)=4T_{3}(n-2)-T_{3}(n-4)$, where $T_{3}(0)=1$,
$T_{3}(1)=0$, $T_{3}(2)=3$, and $T_{3}(3)=0$.

###### Proof.

If n is odd, then the total number of spaces is odd, so it is impossible to
cover the graph using domino tiles, each of which covers an even number of
spaces. In order to have a nonzero number of ways to tile the graph, n must be
even, so $n=2k$ for some $k\in\mathbb{Z}$. Looking at one end of the graph,
and considering a vertical line that separates the first two columns from the
rest, any tiling will either have no dominoes that cross the line or it will
have some dominoes that cross the line. In the first case, there are
$T_{3}(2)T_{3}(n-2)=3T_{3}(n-2)$ ways. In the other case, there are some
domino tiles that cross the vertical line separating the second and third
columns. Now consider a vertical line between the fourth and fifth columns.
There are only two ways to tile $L_{3,4}$ with at least one horizontal domino
on the second and third columns, adding $2T_{3}(n-4)$ ways to tile the whole
graph. Similarly, pushing the vertical line further down the graph $2m$ spaces
to account for all the possible tilings only adds $2T_{3}(n-2m)$ to the total,
so the number of ways to tile $L_{3,n}$ is equal to
$3T_{3}(n-2)+2(T_{3}(n-4)+T_{3}(n-6)+...+T_{3}(0))$. Since
$2(T_{3}(n-4)+T_{3}(n-6)+...+T_{3}(0))=T_{3}(n-2)-T_{3}(n-4)$, we can simplify
$T_{3}(n)$ to the recurrence relation $T_{3}(n)=4T_{3}(n-2)-T_{3}(n-4)$.
∎

Figure 11. First 2 cases for tiling from the end of the graph.

######  Proposition 4.8.

$\sum_{i=0}^{\frac{n-2}{2}}T_{3}(2i)=\frac{T_{3}(n)-T_{3}(n-2)}{2}.$

###### Proof.

Recall from the proof of 4.7 that
$T_{3}(n)=3T_{3}(n-2)+2\sum_{i=0}^{\frac{n-4}{2}}T_{3}(2i)$. The result
follows from subtracting $T_{3}(n-2)$ from both sides and dividing by 2. ∎

We can also find information about gluing these graphs together, first
considering the case where the lattice graphs are shifted such that there is
only one bridge between the two, such as in Figure 12.

Figure 12. A perfect matching of $L_{3,5}\sqcup_{2,\\{e_{1}\\}}L_{3,3}$.

######  Theorem 4.9.

The number of perfect matchings of $L_{3,m}$ and $L_{3,n}$ glued together with
a shift is given by

$T_{3}(m\sqcup_{s,B}n)=\begin{cases}T_{3}(m)T_{3}(n)&B=\emptyset\\\
\frac{(T_{3}(m+1)-T_{3}(m-1))(T_{3}(n+1)-T_{3}(n-1))}{4}&s=2,B=\\{e_{1}\\}\\\
0&s=1,B=\\{e_{1}\\}\text{ or }\\{e_{2}\\}\\\
\frac{(T_{3}(m)-T_{3}(m-2))(T_{3}(n)-T_{3}(n-2))}{4}&s=1,B=\\{e_{1},e_{2}\\}\\\
\frac{(T_{3}(m+1)-T_{3}(m-1))(T_{3}(n+1)-T_{3}(n-1))}{4}&s=0,B=\\{e_{1}\\}\text{
or }\\{e_{3}\\}\\\ 0&s=0,B=\\{e_{2}\\}\text{ or }\\{e_{1},e_{3}\\}\\\
\frac{(T_{3}(m)-T_{3}(m-2))(T_{3}(n)-T_{3}(n-2))}{4}&s=0,B=\\{e_{1},e_{2}\\}\text{
or }\\{e_{2},e_{3}\\}\\\
T_{3}(m-1)T_{3}(n-1)&s=0,B=\\{e_{1},e_{2},e_{3}\\}.\\\ \end{cases}\\\ $

###### Proof.

When $B=\emptyset$, there are no bridges between the two lattice graphs, so
the number of ways to tile them is the number of ways to tile one of them
multiplied by the number of ways to tile the other. That is,
$T_{3}(m)T_{3}(n)$.

When $s=2$ and $B=\\{e_{1}\\}$ or when $s=0$ and $B=\\{e_{1}\\}$ or
$\\{e_{3}\\}$, then the graphs are positioned like in Figure 12. If $m$ or $n$
is even, then there will be an odd number of vertices left on either the
$3\times m$ or $3\times n$ graph which is impossible to tile, so suppose both
$m$ and $n$ are odd. The method of solving will be the same for each graph in
the gluing, so we will look at the $3\times n$ graph. On the first row, there
are 2 available vertices adjacent to one another, so we can split this into
two cases, as seen in Figure 13: either include the vertical edge between the
two, in which case there are $T_{3}(n-1)$ ways to finish the perfect matching,
or we include the horizontal edges connecting them to the adjacent row. In
this case we’re forced to include the edge next to the bridge going into the
top or bottom of the third edge. This means we have a $3\times(n-2)$ lattice
graph missing one vertex, so we will finish tiling it in the same way as we
tiled the $3\times n$ graph missing a vertex. Then we will add a $T_{3}(n-3)$
term and continue until we have a $2\times 1$ graph left, adding $1=T_{3}(0)$
to the sum. Thus we get that the number of ways to tile $L_{3,n}$ missing one
corner vertex is equal to $T_{3}(n-1)+T_{3}(n-3)+...+T_{3}(0)$. By proposition
4.8, this sum equals $\frac{T_{3}(n+1)-T_{3}(n-1)}{2}$. Similarly, the number
of ways to tile the left graph is $\frac{T_{3}(m+1)-T_{3}(m-1)}{2}$.
Multiplying these two values together gives us the total number of tilings for
these shift and bridge gluing combinations:
$\frac{(T_{3}(m+1)-T_{3}(m-1))(T_{3}(n+1)-T_{3}(n-1))}{4}$.

Figure 13. Possible ways to finish a perfect matching including $B_{1}$.

When $s=1$ and $B=\\{e_{1}\\}$ or $\\{e_{2}\\}$ or when $s=0$ and
$B=\\{e_{2}\\}$ or $\\{e_{1},e_{3}\\}$, then at least one of the $3\times m$
or the $3\times n$ graph will have either only the middle tile or only the top
and bottom tiles of an end column covered, as in Figure 14, which is
impossible to tile. This is because the only way to fill the top and bottom
spaces of an end column missing its middle tile is with horizontal tiles,
which then leaves the middle tile of the second column uncovered in a way that
can only be covered by a horizontal tile. However, once that space has been
covered, the graph is in the same state as it was at the beginning, though now
two of its columns have been covered. This process repeats itself, forcing the
placement of horizontal tiles until there is not enough space for another
domino and either the middle vertex or the top and bottom vertices of the end
column will always be uncovered, meaning there is no way to tile the whole
graph. Therefore, these combinations of shifting and gluing contribute 0 to
the total.

Figure 14. Impossible tiling configurations.

When $s=1$ and $B=\\{e_{1},e_{2}\\}$ or when $s=0$ and $B=\\{e_{1},e_{2}\\}$
or $\\{e_{2},e_{3}\\}$, then the graphs are positioned like in Figure 15. If
$m$ or $n$ is odd, then there will be an odd number of spaces left on either
the $3\times m$ or $3\times n$ graph which is impossible to tile, so suppose
both $m$ and $n$ are even. Then for each graph we have an odd number of rows
with one extra tile, forcing us to place a domino horizontally next to the
bridges. This leaves a $3\times(m-1)$ graph missing a vertex to fill. In the
proof of the $s=2$ and $B=\\{e_{1}\\}$ or when $s=0$ and $B=\\{e_{1}\\}$ or
$\\{e_{3}\\}$ gluing cases we showed that the number of ways to finish tiling
such a graph is given by $\frac{T_{3}(m)-T_{3}(m-2)}{2}$, so in this case the
total number of ways to tile the graph is given by multiplying this result for
$m$ with the same result for $n$. Adding these formulas together gives us the
final result: $\frac{(T_{3}(m)-T_{3}(m-2))(T_{3}(n)-T_{3}(n-2))}{4}$.

Figure 15. Initial tiling configurations of
$L_{3,5}\sqcup_{1,\\{e_{1},e_{2}\\}}L_{3,3}$ and
$L_{3,5}\sqcup_{0,\\{e_{1},e_{2}\\}}L_{3,3}$.

When $s=0$ and $B=\\{e_{1},e_{2},e_{3}\\}$, then the graphs are positioned
like in Figure 16. This configuration leaves a $3\times(m-1)$ and a
$3\times(n-1)$ graph to be tiled, so the number of ways to tile them is the
number of ways to tile one of them multiplied by the number of ways to tile
the other. That is, $T_{3}(m-1)T_{3}(n-1)$.

Figure 16. Initial tiling configuration of
$L_{3,5}\sqcup_{0,\\{e_{1},e_{2},e_{3}\\}}L_{3,3}$.

∎

In the proof for Theorem 4.9, the cases for the number of perfect matchings
were split based on the shift and bridges that defined the gluing. We can
combine a number of these cases to express $T_{3}(m+n)$ in terms of tilings
relating to $m$ and $n$ (See Corollary A.1).

###  4.4. The $4\times n$ case

######  Theorem 4.10.

The number of unique ways to tile $L_{4,n}$ with dominoes is given by the
recursive formula $T_{4}(n)=T_{4}(n-1)+5T_{4}(n-2)+T_{4}(n-3)-T_{4}(n-4)$,
where $T_{4}(1)=1$, $T_{4}(2)=5$, $T_{4}(3)=11$, and $T_{4}(4)=36$.

###### Proof.

The initial values of the recursion can be checked by hand. As for the
recursive formula, let $n$ be an arbitrary positive integer greater than 4.
All possible tilings of $L_{4,n}$ must begin on the left-hand side with one of
these initial configurations:

In the first case, where the first column is filled with vertical dominoes,
there is a $4\times(n-1)$ graph left to tile, contributing $T_{4}(n-1)$ ways
to fill the graph.
In the second case, where the first two columns are filled with horizontal
dominoes, there is a $4\times(n-2)$ graph left to tile, contributing
$T_{4}(n-2)$ ways to fill the graph.
In the third case, the two empty spaces in the second column can either be
filled with a vertical tile or two horizontal tiles. Adding a vertical tile
leaves a $4\times(n-2)$ graph to tile and adding two horizontal tiles gives
you the same choice of filling the two empty spaces in the third column either
by adding a vertical tile or two horizontal tiles. You can continue choosing
to add horizontal tiles until you run out of space on the graph, in total
adding
$T_{4}(n-2)+T_{4}(n-3)+T_{4}(n-4)+...+T_{4}(0)=\sum_{i=0}^{n-2}T_{4}(i)$ ways
to tile the graph. The same goes for the fourth case.
In the fifth case, the two empty spaces in the second column can either be
filled with a vertical tile or two horizontal tiles. Adding a vertical tile
leaves a $4\times(n-2)$ graph to tile and adding two horizontal tiles forces
you to place horizontal tiles in the top and bottom rows and then gives you
the same choice of filling the two empty spaces in the fourth column either by
adding a vertical tile or two horizontal tiles. You can continue choosing to
add horizontal tiles until you run out of space on the graph, in total adding

$T_{4}(n-2)+T_{4}(n-4)+T_{4}(n-6)+...+((T_{4}(1)\text{ if $n$ is odd) or
}(T_{4}(0)\text{ if $n$ is
even}))=\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}T_{4}(n-2i)$

ways to tile the graph.
So far, we have

$T_{4}(n)=T_{4}(n-1)+T_{4}(n-2)+2\sum_{i=0}^{n-2}T_{4}(i)+\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}T_{4}(n-2i).$

However, we can simplify this formula further:

$T_{4}(n-2)=T_{4}(n-3)+T_{4}(n-4)+2\sum_{i=0}^{n-4}T_{4}(i)+\sum_{i=1}^{\lfloor\frac{n-2}{2}\rfloor}T_{4}(n-2-2i),$

so

$\displaystyle T_{4}(n)-T_{4}(n-2)$
$\displaystyle=(T_{4}(n-1)+T_{4}(n-2)+2\sum_{i=0}^{n-2}T_{4}(i)+\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}T_{4}(n-2i))$
$\displaystyle-(T_{4}(n-3)+T_{4}(n-4)+2\sum_{i=0}^{n-4}T_{4}(i)+\sum_{i=1}^{\lfloor\frac{n-2}{2}\rfloor}T_{4}(n-2-2i))$
$\displaystyle=T_{4}(n-1)+4T_{4}(n-2)+T_{4}(n-3)-T_{4}(n-4)$

So $T_{4}(n)=T_{4}(n-1)+5T_{4}(n-2)+T_{4}(n-3)-T_{4}(n-4)$. ∎

In order to prove a gluing formula for the $4\times n$ case, it will be
helpful to derive formulae for the sums in the proof of the recursion formula,
see Propositions A.3 and A.4 in the Appendix.

We can also find information about gluing graphs together, considering
different shifts and bridge sets. If the number of bridges is odd, then what
it left is impossible to tile because an odd number of vertices will be left
on each graph.

######  Theorem 4.11.

The number of perfect matchings of $L_{4,m}$ and $L_{4,n}$ glued together with
a shift $T_{4}(m\sqcup_{s,B}n)$ is given by

$\begin{cases}T_{4}(m)T_{4}(n)&B=\emptyset\\\
\frac{(T_{4}(m+1)-T_{4}(m-2))(T_{4}(n+1)-T_{4}(n-2))}{25}&s=2,B=\\{e_{1},e_{2}\\}\\\
f(m)\frac{(T_{4}(n+1)-T_{4}(n-2))}{5}&s=1,B=\\{e_{1},e_{2}\\}\\\
\frac{(T_{4}(m+1)-T_{4}(m-2))}{5}f(n)&s=1,B=\\{e_{2},e_{3}\\}\\\
\frac{(T_{4}(m+1)-T_{4}(m-2))(T_{4}(n+1)-T_{4}(n-2))}{25}&s=0,B=\\{e_{1},e_{2}\\}\text{
or }\\{e_{3},e_{4}\\}\\\ 0&s=0\text{ or }1,B=\\{e_{1},e_{3}\\}\text{ or
}\\{e_{2},e_{4}\\}\\\ f(m+1)f(n+1)&s=0,B=\\{e_{1},e_{4}\\}\\\
f(m)f(n)&s=0,B=\\{e_{2},e_{3}\\}\\\
T_{4}(m-1)T_{4}(n-1)&s=0,B=\\{e_{1},e_{2},e_{3},e_{4}\\}\\\ \end{cases}\\\ $

Where
$f(n)=-\frac{2}{5}T_{4}(n)+4T_{4}(n-2)+\frac{7}{5}T_{4}(n-3)-T_{4}(n-4)$.

###### Proof.

When $B=\emptyset$, there are no bridges between the two lattice graphs, so
the number of ways to tile them is the number of ways to tile one of them
multiplied by the number of ways to tile the other. That is,
$T_{4}(m)T_{4}(n)$.

When $s=2$ and $B=\\{e_{1},e_{2}\\}$ or when $s=0$ and $B=\\{e_{1},e_{2}\\}$
or $\\{e_{3},e_{4}\\}$, then the graphs are positioned like in Figure 17. The
method of solving will be the same for each graph in the gluing, so we will
look at the $4\times n$ graph. On the first row, there are 2 available
vertices adjacent to one another, so we can split this into two cases as shown
in 18: either include the vertical edge between the two, in which case there
are $T_{4}(n-1)$ ways to finish the perfect matching, or we include the
horizontal edges connecting them to the adjacent row. In this case we again
have the choice between including a vertical edge, leaving us with a
$4\times(n-2)$ graph to tile, adding $T_{4}(n-2)$ ways to finish the perfect
matching, or including two horizontal edges, again allowing for either a
vertical tile or two horizontal tiles. This will continue until we have a
$2\times 1$ graph left, adding $1=T_{4}(0)$ to the sum. Thus we get that the
number of ways to tile $L_{4,n}$ missing one corner vertex and one vertex
above or beneath it is equal to $T_{4}(n-1)+T_{4}(n-2)+...+T_{4}(0)$. By
proposition A.3, this sum equals $\frac{T_{4}(n+1)-T_{4}(n-2)}{5}$. Similarly,
the number of ways to tile the left graph is
$\frac{T_{4}(m+1)-T_{4}(m-2)}{5}$. Multiplying these two values together gives
us the total number of tilings for these shift and bridge gluing combinations:
$\frac{(T_{4}(m+1)-T_{4}(m-2))(T_{4}(n+1)-T_{4}(n-2))}{25}$.

Figure 17. Initial tiling configurations of
$L_{4,5}\sqcup_{2,\\{e_{1},e_{2}\\}}L_{4,3}$ and
$L_{4,5}\sqcup_{0,\\{e_{1},e_{2}\\}}L_{4,3}$. Figure 18. Intermediate tiling
configurations of $L_{4,5}$ glued with 2 bridges.

When $s=1$ and $B=\\{e_{1},e_{2}\\}$ or $\\{e_{2},e_{3}\\}$, then the graphs
are positioned like in Figure 19. This means that one of the graphs will be
missing one corner vertex and another vertex above or beneath the corner and
the other graph will be missing the middle two vertices from one of the end
columns. We already have a formula from the previous paragraph for the number
of perfect matchings of the first graph, so let us focus on the second. Since
the middle two vertices of the end column are covered, we are forced to place
two horizontal tiles on the corner spaces. To fill the second-to-last column,
we can either use a vertical tile or two horizontal tiles, as shown in Figure
19. In the case of a vertical tile, we are left with a $4\times(m-2)$ graph,
contributing $T_{4}(m-2)$ perfect matchings to the total. In the case of two
horizontal tiles, we are again forced to place horizontal tiles in the top and
bottom rows, now leaving the middle two vertices of the fourth column
uncovered, and thus the pattern repeats, adding $T_{4}(m-2k)$ (where $1\leq
k\leq\lfloor\frac{m}{2}\rfloor$) tilings in each iteration until there is
either the middle two vertices of the last column or the entire last column
and the middle two vertices of the second-to-last column left uncovered,
depending on if $m$ is even or odd. Therefore, in total there are

$\displaystyle T_{4}(m-2)+T_{4}(m-4)+T_{4}(m-6)+...+(T_{4}(1)\text{ if m is
odd) or }(T_{4}(0)\text{ if m is even})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{\lfloor\frac{m}{2}\rfloor}T_{4}(m-2i)=-\frac{2}{5}T_{4}(m)+4T_{4}(m-2)+\frac{7}{5}T_{4}(m-3)-T_{4}(m-4)$

ways to tile $L_{4,m}$ with the middle two vertices missing from the last
column. From now on, we will abbreviate this quantity as $f(m)$. By
multiplying this value by the number of ways to tile $L_{4,n}$ missing a
corner vertex and a vertex directly below it, we see that there are

$f(m)\frac{(T_{4}(n+1)-T_{4}(n-2))}{5}$

ways to tile two lattice graphs shifted by 1 with a bridge set equal to
$\\{e_{1},e_{2}\\}$ and

$\frac{(T_{4}(m+1)-T_{4}(m-2))}{5}f(n)$

ways to tile two lattice graphs shifted by 1 with a bridge set equal to
$\\{e_{2},e_{3}\\}$.

Figure 19. Initial and intermediate tiling configurations of
$L_{4,5}\sqcup_{1,\\{e_{1},e_{2}\\}}L_{4,3}$.

When $s=0$ or $1$ and $B=\\{e_{1},e_{3}\\}$ or $\\{e_{2},e_{4}\\}$, then at
least one of the graphs has its corner vertex missing along with a non corner,
nonadjacent vertex from the same column, which is impossible to tile. This is
because the only way to cover the vertices of an end column missing a corner
and a non corner, nonadjacent tile is with horizontal tiles, which then leaves
two nonadjacent vertices of the second column uncovered in a way that can only
be covered by two more horizontal tiles. However, once those vertices have
been covered, the graph is in the same state as it was at the beginning,
though now two of its columns have been covered. This process repeats itself,
forcing the placement of horizontal tiles until there is no more space on the
graph and either the middle vertex or the top and bottom vertices of the end
column will always be uncovered, meaning there is no way to tile the whole
graph. Therefore, these combinations of shifting and gluing contribute 0 to
the total.

When $s=0$ and $B=\\{e_{1},e_{4}\\}$, then we have two graphs next to each
other, each missing two corner vertices from an end column, as shown in Figure
20. We will look at just the right graph, since the possible ways to tile each
graph are the same. We can either use one vertical tile or two horizontal
tiles to cover the vertices in the column missing its corners. If we use a
vertical tile, there are $T_{4}(n-1)$ ways to tile the $4\times(n-1)$ graph
that remains. If we use two horizontal tiles, we are forced to place two more
horizontal tiles in the top and bottom rows, so what’s left is a
$4\times(n-2)$ graph with two of the corners missing from the left-most
column. As we have seen before, we can keep reducing the length of the graph
like this, adding $T_{4}(n-2k+1)$ (where $1\leq
k\leq\lfloor\frac{n}{2}\rfloor$) perfect matchings to the total with each
iteration until there is either the middle two vertices of the last column or
the entire last column and the middle two vertices of the second-to-last
column left uncovered, depending on if $n$ is even or odd. Therefore, in total
there are $T_{4}(n-1)+T_{4}(n-3)+T_{4}(n-5)+...+(T_{4}(1)\text{ if n is even)
or }(T_{4}(0)\text{ if n is
odd})=\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}T_{4}(n-2i+1)$, which, by
Proposition A.4 equals $f(n+1)$ ways to tile $L_{4,n}$ with the two corner
vertices missing from the last column. The number of ways to tile the left
graph is the same except for replacing every instance of $n$ with $m$. By
multiplying these values together, we see that there are $f(n+1)f(m+1)$ ways
to tile two lattice graphs shifted by 0 with a bridge set equal to
$\\{e_{1},e_{4}\\}$.

Figure 20. Initial tiling configuration of
$L_{4,5}\sqcup_{0,\\{e_{1},e_{4}\\}}L_{4,3}$.

When $s=0$ and $B=\\{e_{2},e_{3}\\}$, then we have two graphs next to each
other, each missing the two middle vertices from their end columns. From a
previous paragraph, we know there are

$-\frac{2}{5}T_{4}(m)+4T_{4}(m-2)+\frac{7}{5}T_{4}(m-3)-T_{4}(m-4)$

ways to tile such graphs. By multiplying these values together, we see that
there are

$f(m)f(n)$

ways to tile two lattice graphs shifted by 0 with a bridge set equal to
$\\{e_{2},e_{3}\\}$.

When $s=0$ and $B=\\{e_{1},e_{2},e_{3},e_{4}\\}$, then the graphs are
positioned like in Figure 21. This configuration leaves a $4\times(m-1)$ and a
$4\times(n-1)$ graph to be tiled, so the number of ways to tile them is the
number of ways to tile one of them multiplied by the number of ways to tile
the other. That is, $T_{4}(m-1)T_{4}(n-1)$.

Figure 21. Initial tiling configuration of
$L_{4,5}\sqcup_{1,\\{e_{1},e_{2},e_{3},e_{4}\\}}L_{4,3}$.

∎

##  5\. Spinors, Clifford algebras on graphs and gluing

Spinors can be examined as elements of linear representation of Clifford
Algebras. For example, the space of Pauli spinors can be approached as the
space $Cl^{-}(0,3)$ and the space of Dirac spinors as $Cl^{+}(1,3)$
[renaud:hal-03015551]. The relations between the generators of the algebra
parallel the rules governing interactions between spinors in a quantum system.
While there are a number of candidate Clifford algebras that have been
explored as representations of the space of spinors [renaud:hal-03015551], we
focus on a special type of Clifford algebra associated to a graph, introduced
by Khovanova [Khovanova].

######  Definition 5.1.

Let $\Gamma$ be a graph with $n$ vertices. Its associated Clifford algebra
$A_{\Gamma}$ has $n$ generators $e_{1},\ldots,e_{n}$ corresponding to each
vertex. For each $i$, $e_{i}^{2}=-1$ and

$\begin{cases}e_{i}e_{j}=-e_{j}e_{i}&i\text{ and }j\text{ are adjacent in
}\Gamma\\\ e_{i}e_{j}=e_{i}e_{j}&i\text{ and }j\text{ not adjacent in
}\Gamma\end{cases}$.

The center of a Clifford graph algebra characterizes the structure of the
whole algebra. Each central monomial of a Clifford graph algebra gives a
decomposition as a direct sum of two algebras. As a result, the structure of a
Clifford graph algebra can be identified solely by the number of vertices and
the dimension of its center [Khovanova].

The center of a Clifford graph algebra is spanned by its monomials. They are
determined by the structure of the graph [Khovanova], as stated in the
following

######  Lemma 5.2.

A monomial $e_{\alpha}$ is central if and only if for each vertex
$i\in\Gamma$, there are an even number of edges connecting $i$ to $\alpha$.

###  5.1. Examples

We give some examples of Clifford graph algebras and their centers.

######  Proposition 5.3.

Let $P_{n}$ be a path graph. Then

$Z(A_{P_{n}})=\begin{cases}\mathbb{C}&\text{ if }n\text{ is even}\\\
\mathbb{C}^{2}&\text{ if }n\text{ is odd}\end{cases}.$

To be precise, for odd $n$, $Z(A_{P_{n}})$ is spanned by the central monomial
$e_{1}e_{3}\cdots e_{n}$ and $1$.

Consider the path graph $P_{5}$, labeled as follows:

The center of $P_{7}$ is
$Z(A_{P_{5}})=\\{\alpha\,e_{1}e_{3}e_{5}+\beta\;|\;\alpha,\beta\in\mathbb{C}\\}$.

$e_{1}e_{3}e_{5}$ is a central monomial in $A_{P_{7}}$ because we can check
that each vertex is connected to $\alpha=\\{1,3,5\\}$ by an even number of
edges.

All edges in $P_{5}$ connect an even vertex to an odd vertex. This means for
odd $i$, there are no edges connecting it to $\alpha$. For even $i$, the only
incident edges are $(i,i-1)$ and $(i,i+1)$. Both $i-1$ and $i+1$ are in
$\alpha$, so there are two edges connecting it to $\alpha$.

###  5.2. Graph gluing and Clifford algebras

######  Definition 5.4.

Let $V$, $W$ be two $\mathbb{C}$-algebras with bases $\\{v_{i}\\}_{i=1}^{n}$
and $\\{w_{j}\\}_{j=1}^{n}$. The tensor product $V\otimes W$ has basis
$\\{v_{i}\otimes w_{j}\\}$ such that

  1. (1)

$(v_{1}+v_{2})\otimes w=v_{1}\otimes w+v_{2}\otimes w$

  2. (2)

$v\otimes(w_{1}+w_{2})=v\otimes w_{1}+v\otimes w_{2}$

  3. (3)

$\lambda(v\otimes w)=(\lambda v)\otimes=v\otimes(\lambda
w),\lambda\in\mathbb{C}$.

In the case of Clifford graph algebras: $V$ and $W$ are $\mathbb{C}$-algebras
spanned by monomials. Assume the generators $\\{e_{k}\\}$ for $V$ are distinct
from the generators $\\{e_{l}\\}$ for $W$. Each element $v\in V$ and $w\in W$
is a polynomial:

  1. (1)

$v=\sum\limits_{i=1}^{n}\alpha_{i}v_{i}$

  2. (2)

$w=\sum\limits_{j=1}^{m}\lambda_{j}w_{j},$

where $\alpha_{i},\lambda_{j}\in\mathbb{C}$. Following the normal rules of
multiplying two monomials, we define the tensor product $v_{i}\otimes
w_{j}=v_{i}w_{j}$. Because the monomial $v_{i}$ is defined in different
generators from $w_{j}$, $v_{i}w_{j}$ is a monomial of degree 1.

Under the normal polynomial multiplication, we have:

$v\otimes w=vw=\sum_{i=1}^{n}\sum_{j=1}^{m}\alpha_{i}\lambda_{j}v_{i}w_{j}.$

Every element $v\otimes w\in V\otimes W$ is a linear combination of the
monomials $v_{i}\otimes w_{j}=v_{i}w_{j}$.

In addition, polynomial multiplication satisfies the following properties:

  1. (1)

$(v_{1}+v_{2})w=v_{1}w+v_{2}w\iff(v_{1}+v_{2})\otimes w=v_{1}\otimes
w+v_{2}\otimes w$

  2. (2)

$v(w_{1}+w_{2})=vw_{1}+vw_{2}\iff v\otimes(w_{1}+w_{2})=v\otimes
w_{1}+v\otimes w_{2}$

  3. (3)

$\lambda vw=(\lambda v)w=v(\lambda w)\iff\lambda(v\otimes w)=(\lambda
v)\otimes=v\otimes(\lambda w)$.

######  Theorem 5.5.

Let $\Gamma_{1}$ and $\Gamma_{2}$ be graphs and $A_{\Gamma_{1}}$ and
$A_{\Gamma_{2}}$ be their associated Clifford algebras. Then
$Z(A_{\Gamma_{1}})\otimes
Z(A_{\Gamma_{2}})=Z(A_{\Gamma_{1}\sqcup\Gamma_{2}}).$

###### Proof.

($\Rightarrow$) First, we need to show $Z(A_{\Gamma_{1}})\otimes
Z(A_{\Gamma_{2}})\subseteq Z(A_{\Gamma_{1}\sqcup\Gamma_{2}})$.

Let $\\{e_{\alpha}\\}$ be the basis of central monomials for
$Z(A_{\Gamma_{1}})$ and $\\{e_{\beta}\\}$ be the basis of central monomials
for $Z(A_{\Gamma_{2}})$.

Then $\\{e_{\alpha}e_{\beta}\\}$ is a basis for
$Z(A_{\Gamma_{1}\sqcup\Gamma_{2}})$. We want to show it is contained in
$Z(A_{\Gamma_{1}}\sqcup A_{\Gamma_{2}})$.

Let $e_{\alpha}e_{\beta}$ be fixed. Observe $e_{\alpha}e_{\beta}$ is a
monomial associated with the vertex set $\alpha\sqcup\beta$, so we can denote
$e_{\alpha\beta}=e_{\alpha}e_{\beta}$.

Recall a monomial $e_{\alpha}$ is central in $A_{\Gamma}$ if and only if for
all $v\in V(\Gamma)$, the number of edges connecting it to $\alpha$ is even.

In order to show $e_{\alpha\beta}\in Z(A_{\Gamma_{1}\sqcup\Gamma_{2}})$, we
need to show for every $v\in V(\Gamma_{1}\sqcup\Gamma_{2})$, there are an even
number of edges connecting it to $\alpha\sqcup\beta$.

Case 1: $v\in V(\Gamma_{1})$. Because $e_{\alpha}$ is a central monomial of
$A_{\Gamma_{1}}$, there are an even number of edges connected $v$ to $\alpha$.
$\Gamma_{1}$ and $\Gamma_{2}$ are disconnected in
$\Gamma_{1}\sqcup\Gamma_{2}$, so there are no edges between $v$ and $\beta$.

Together, there are an even number of edges connecting $v$ to
$\alpha\sqcup\beta$.

Case 2: $v\in V(\Gamma_{2})$. Because $e_{\beta}$ is a central monomial of
$A_{\Gamma_{2}}$, there are an even number of edges connected $v$ to $\beta$.

$\Gamma_{1}$ and $\Gamma_{2}$ are disconnected in
$\Gamma_{1}\sqcup\Gamma_{2}$, so there are no edges between $v$ and $\alpha$.

Together, there are an even number of edges connecting $v$ to
$\alpha\sqcup\beta$.

We thus conclude that $e_{\alpha}e_{\beta}=e_{\alpha\beta}$ is a central
monomial of $A_{\Gamma_{1}\sqcup\Gamma_{2}}$. It follows that
$Z(A_{\Gamma_{1}})\otimes Z(A_{\Gamma_{2}})\subseteq
Z(A_{\Gamma_{1}\sqcup\Gamma_{2}})$.

($\Leftarrow$) Next, we need to show
$Z(A_{\Gamma_{1}\sqcup\Gamma_{2}})\subseteq Z(A_{\Gamma_{1}})\otimes
Z(A_{\Gamma_{2}})$.

Let $\\{e_{\alpha}\\}$ be the basis of monomials for
$Z(A_{\Gamma_{1}\sqcup\Gamma_{2}})$. We want to show it is contained in
$Z(A_{\Gamma_{1}})\otimes Z(A_{\Gamma_{2}})$.

Let $e_{\alpha}$ be a central monomial of $A_{\Gamma_{1}\sqcup\Gamma_{2}}$.
Because $\Gamma_{1}$ and $\Gamma_{2}$ are disconnected components of
$\Gamma_{1}\sqcup\Gamma_{2}$, we can separate the vertex set
$\alpha=\alpha_{1}\sqcup\alpha_{2}$, where $\alpha_{1}$ and $\alpha_{2}$ are
the subsets of vertices from $\Gamma_{1}$ and $\Gamma_{2}$, respectively.

We want to show $e_{\alpha}=e_{\alpha_{1}}e_{\alpha_{2}}\in
Z(A_{\Gamma_{1}})\otimes Z(A_{\Gamma_{2}})$, or $e_{\alpha_{1}}\in
Z(A_{\Gamma_{1}})$ and $e_{\alpha_{2}}\in Z(A_{\Gamma_{2}})$.

Start with $e_{\alpha_{1}}$. Let $v\in V(\Gamma_{1})$.

Because $e_{\alpha}$ is a central monomial of $\Gamma_{1}\sqcup\Gamma_{2}$, we
know there are an even number of edges between $v$ and
$\alpha_{2}\sqcup\alpha_{2}$. In particular, there are no edges between $v$
and $\alpha_{2}$ because $\Gamma_{1}$ and $\Gamma_{2}$ are disconnected. Then
the number of edges connecting $v$ to $\alpha_{1}$ is the same for
$\alpha_{1}\sqcup\alpha_{2}$, which is even. We have shown for any $v\in
V(G_{1})$, there are an even number of edges connecting it to $\alpha_{1}$, so
$e_{\alpha_{1}}$ is a central monomial of $A_{\Gamma_{1}}$. Similarly, we can
find that $e_{\alpha_{2}}$ is a central monomial of $A_{\Gamma_{2}}$. Then
$e_{\alpha}=e_{\alpha_{1}}e_{\alpha_{2}}\in Z(A_{\Gamma_{1}})\otimes
Z(A_{\Gamma_{2}})$. We conclude $Z(A_{\Gamma_{1}\sqcup\Gamma_{2}})\subseteq
Z(A_{\Gamma_{1}})\otimes Z(A_{\Gamma_{2}})$, as desired. ∎

The centers of Clifford graph algebras from bridge gluings are more
challenging to identify, but we can start with some simple examples.

There are two ways to glue the path graphs $P_{2}$ and $P_{3}$ with one
bridge:

Figure 22. Two different bridge gluings between $P_{3}$ and $P_{2}$.

By Proposition 5.3, the bases for $Z(A_{P_{2}}$ and $Z(A_{P_{3}})$ are
$\\{1\\}$ and $\\{1,e_{1}e_{3}\\}$, respectively. In the left gluing,
$P_{2}\sqcup_{B_{1}}P_{3}=P_{5}$, which has a center spanned by
$e_{1}e_{3}e_{5}$ and $1$. The right gluing also has basis
$\\{e_{1}e_{3}e_{5},1\\}$. With the same number of vertices and dimension of
their centers, the Clifford algebras associated to the two bridge gluings are
isomorphic.

This is not always the case though. Take the following gluing of two copies of
$P_{3}$:

Figure 23. Two different bridge gluings between two copies of $P_{3}$.

The Clifford algebra of the left gluing has a center of dimension one, while
the center for the right gluing has dimension four with central monomials
$e_{1}e_{3}$, $e_{1}e_{4}e_{6}$, and $e_{3}e_{4}e_{6}$.

We can characterize the dimension of the Clifford algebras of glued path
graph. The case of bridge gluing the endpoints of two path graphs is simple:
by Proposition 5.3, $P_{n}\sqcup_{B_{1}}P_{m}$ has a center of dimension $1$
if $n$ and $m$ have the same parity and $0$ if they have opposite parity.

######  Theorem 5.6.

Let $\Gamma=P_{n}\sqcup_{B_{1}}P_{m}$ be two path graphs glued by a bridge
between an interior vertex and endpoint.

  1. (1)

If $n$ and $m$ are both even, then $Z(A_{\Gamma})$ has dimension 1.

  2. (2)

If $n$ is even and $m$ is odd, then $Z(A_{\Gamma})$ has dimension 2.

  3. (3)

If $n$ and $m$ are both odd, then $Z(A_{\Gamma})$ has dimension 4.

We prove the following lemma to identify central monomials of the glued graph
Clifford algebra:

######  Lemma 5.7.

Let $\Gamma$ be a tree. Suppose $e_{\alpha}$ is a central monomial of
$A_{\Gamma}$. Then

  1. (1)

there are at least one vertex of degree one in $\alpha$,

  2. (2)

for every vertex $v\in\alpha$, there exists $u\in\alpha$ such that $d(u,v)=2$,
and

  3. (3)

no pair of vertices $u,v\in\alpha$ are adjacent.

This will help us to prove Theorem 5.6, because we only need to check the
vertex sets that start at a leaf and skip every other vertex.

###### Proof.

Let $e_{\alpha}$ be a central monomial of $A_{\Gamma}$.

  1. (1)

Suppose for the sake of contradiction, there is no vertex of degree one in
$\alpha$.

Pick any interior vertex of $\Gamma$ as the root $r$. This gives $\Gamma$ a
partial ordering relation $<_{r}$, where $x<_{r}y$ if $x$ lies in the $r-y$
path. Pick any maximal element $x\in\alpha$, that is, there is no $y\in\alpha$
such that $x<_{r}y$. By assumption, $x$ is not a leaf, so there is some vertex
$v$ that is adjacent to $x$ away from the root $r$. Then $v$ is connected to
$\alpha$ by a single edge $(v,x)$. There are no other edges between $v$ and
$\alpha$ because for any other neighbor $u$, $x<_{r}u$, so $u\notin\alpha$ by
the maximality of $x$. We conclude $e_{\alpha}$ is not a central monomial, in
contradiction.

  2. (2)

Let $v\in\alpha$. Suppose for the sake of contraction, there is no vertex
$u\in\alpha$ such that $d(u,v)=2$. Pick any vertex $x$ adjacent to $v$. Then
$x$ is connected to $\alpha$ by a single edge $(v,x)$. There are no other
edges between $x$ and $\alpha$ because for any other neighbor $y$, $d(y,v)=2$.
We conclude $e_{\alpha}$ is not a central monomial, in contradiction.

  3. (3)

Let $v\in\alpha$. Suppose for sake of contradiction, $u,v\in\alpha$ that are
adjacent.

Case 1: $u$ or $v$ is a leaf. Assume WLOG $v$ is a leaf. Then $v$ is connected
to $\alpha$ by a single edge $(u,v)$, since $v$ has no other neighbors.

Case 2: $u$ and $v$ are both interior vertices. At least one neighbor of $v$,
say $x$, is in $\alpha$, otherwise $v$ only has one edge connecting it to
$\alpha$. We can show the same for $x$, at least one of its neighbors is in
$\alpha$. We repeat until we have found some leaf $z$ in $\alpha$, which is
connected to $\alpha$ by a single edge. In contradiction, $e_{\alpha}$ is not
a central monomial.

∎

One corollary of this proof is that if a central vertex set starts at one
leaf, then branches out, skipping every other vertex, then it must contain a
leaf at the end of the branch. Otherwise, like in part 1, the “next” vertex in
the branch connects to the vertex set by one edge. As a result, the vertex set
corresponding to a central monomial must contain at least two leaves that are
an even distance apart.

Now we are able to prove Theorem 5.6.

###### Proof.

Let $P_{n}$ and $P_{m}$ be two path graphs. Label the vertices of $P_{n}$,
$v_{1},\ldots,v_{n}$, and similarly for $P_{m}$. Let $\Gamma$ be $P_{n}$ and
$P_{m}$ glued by bridge $(v_{k},u_{1})$, where $v_{k}$ is an internal vertex
of $P_{n}$ and $u_{1}$ is an endpoint of $P_{m}$.

Case 1: $n$ and $m$ are both even.

Because $n$ is even, we know $v_{k}$ is an even distance from some endpoint of
$P_{n}$ and an odd distance from the other. Assume WLOG $v_{k}$ is an even
distance from $v_{1}$. The only pair of leaves that are an even apart is
$v_{1}$ and $u_{1}$, so any central vertex set must contain
$v_{1},\ldots,v_{k},u_{2},\ldots,u_{m}$. We note $v_{k-1}$ connects to the set
by a single edge $(v_{k-1},v_{k})$, so its associated monomial is not central.
However, if it branches towards $v_{k-2}$ from $v_{k}$, it will not contain
leaf $v_{1}$ because they are odd distances apart.

Figure 24. A candidate vertex set

Case 2: $n$ is even and $m$ is odd.

Let’s assume without loss of generality that $v_{k}$ is at an even distance
from $v_{1}$. We observe $v_{1},\ldots,v_{k},u_{2},\ldots,v_{m}$ corresponds
to a central monomial. Moreover, this is the only central monomial because the
other pairs of leaves are an odd distance apart.

Figure 25. The vertex set associated to the unique central monomial of
$A_{\Gamma}$

Case 3: $n$ is odd and $m$ is even.

Because $n$ is odd, $v_{nk}$ is either an odd distance from both endpoints or
an even distance from both endpoints of $P_{n}$.

Suppose $v_{nk}$ is an even distance from both $v_{n1}$ and $v_{nn}$. Then
$v_{n1},\ldots,v_{nk},\ldots,v_{nn},v_{m2},\ldots,v_{mm}$.

If $v_{nk}$ is an odd distance from both $v_{n1}$ and $v_{nn}$, then it is
equivalent to Case 2. $\Gamma$ is also two paths,
$v_{1},\ldots,v_{k},u_{1},\ldots,u_{m}$ and $v_{k+1},\ldots,v_{n}$, glued by
bridge $(v_{k},v_{k+1})$. The former has an even number of vertices while the
latter has an odd number, like in Case 2.

Case 4: $n$ and $m$ both odd.

Assume $k$ is even. Otherwise, if $k$ is odd, $\Gamma$ can also be seen as two
paths, $v_{n1},\ldots,v_{nk},v_{m1},\ldots,v_{mm}$ and
$v_{n(k+1)},\ldots,v_{nn}$ glued by bridge $(v_{nk},v_{n(k+1)})$. Both path
graphs have even length, as in Case 1.

The vertex sets associated to central monomials are:

  * •

$v_{1},\ldots,v_{k-1},v_{k+1},\ldots,v_{n}$

  * •

$v_{1},\ldots,v_{k-1},u_{1},\ldots,u_{m}$

  * •

$v_{n},\ldots,v_{k+1},u_{1},\ldots,u_{m}$.

∎

##  6\. Future directions

Currently, our program to compute and create visualizations of solutions to
the Dirac equation over time has been used to numerically verify our results.
Future directions include investigating whether this process can be carried
out in reverse, i.e. can information about the underlying graph or initial
quantum state be extracted given these graphs and data of solutions to the
Dirac equation over time.

Our gluing formulae help us to understand the behavior of spinors and Dirac
operators on graphs as they become more complex. A formula that generalizes
the results in Section 4 is still open, and its complexity is expected to
increase with the size of the lattice graphs. We also hope to generate gluing
formulae for other types of graphs, e.g. honeycomb graphs, and planar graphs
in general.

We have discovered explicit formulae for the quadratic forms of the odd
Laplacian and the incidence Dirac operator. Future work could be carried out
to determine explicit formulae for the quadratic forms of the even and odd
Dirac operators.

The case of Clifford graph algebras for disjoint gluings and bridge gluings of
path graphs help to understand the space of spinors in higher dimensions.
Further research in generalizing bridge gluings will be foundational in
understanding the Clifford algebras of more complex graphs.

While our results on gluing formalae focus on the Clifford graph algebras
defined by Khovanova [Khovanova], the Clifford algebras that represent spaces
of spinors extend beyond those introduced. For example, $Cl(1,3)^{+}$, the
even part of the Clifford algebra $Cl(1,3)$ is suitable for describing Dirac
spinors.[renaud:hal-03015551] $Cl(1,3)$ has four generators: one of which
squares to $+1$, while the remaining three square to $-1$. In order to allow
for such a distinction under Khovanov’s framework of Clifford graph algebras,
we propose an additional graph coloring. We propose a form of Clifford graph
algebra where vertices $i$ are given a color based on their associated
generator $e_{i}$, for example, red, if $e_{i}^{2}=+1$, or blue, if
$e_{i}^{2}=-1$. Because the generators of Clifford algebras anticommute, their
colored graphs are complete.

## Appendix: Algebraic computations for the gluing of lattice graphs

######  Corollary A.1.

The number of perfect matchings of $L_{3,n+m}$ is given by

$T_{3}(m+n)=T_{3}(m)T_{3}(n)+T_{3}(m-1)T_{3}(n-1)\\\
+\frac{(T_{3}(m+1)-T_{3}(m-1))(T_{3}(n+1)-T_{3}(m-1))}{2}\\\
+\frac{(T_{3}(m)-T_{3}(m-2))(T_{3}(n)-T_{3}(n-2))}{2}.$

###### Proof.

$\displaystyle T_{3}(m+n)$ $\displaystyle=\sum_{B}T_{3}(m\sqcup_{0,B}n)$
$\displaystyle=T_{3}(m)T_{3}(n)+2\frac{(T_{3}(m+1)-T_{3}(m-1))(T_{3}(n+1)-T_{3}(m-1))}{4}$
$\displaystyle+2(0)+2\frac{(T_{3}(m)-T_{3}(m-2))(T_{3}(n)-T_{3}(n-2))}{4}$
$\displaystyle+T_{3}(m-1)T_{3}(n-1).$

∎

######  Proposition A.2.

The number of ways to tile $L_{3,n}$ with dominoes is given by the explicit
formula

$\frac{(1-(-1)^{n+1})(\alpha^{n+1}+(\frac{1}{\alpha})^{n+1})}{2\sqrt{6}},$

where $\alpha=\frac{\sqrt{2}+\sqrt{6}}{2}$.

###### Proof.

We can represent the recursion equation using matrices:

$\displaystyle\begin{bmatrix}T_{3}(n+3)\\\ T_{3}(n+2)\\\ T_{3}(n+1)\\\
T_{3}(n)\end{bmatrix}$ $\displaystyle=\begin{bmatrix}0&4&0&-1\\\ 1&0&0&0\\\
0&1&0&0\\\ 0&0&1&0\end{bmatrix}^{n}\begin{bmatrix}T_{3}(3)\\\ T_{3}(2)\\\
T_{3}(1)\\\ T_{3}(0)\end{bmatrix}.$

By diagonalizing the recursion matrix and performing matrix multiplication, we
find that

$T_{3}(n)=\frac{3-\sqrt{3}}{12}(\frac{-\sqrt{2}+\sqrt{6}}{2})^{n}+\frac{3-\sqrt{3}}{12}(\frac{\sqrt{2}-\sqrt{6}}{2})^{n}+\frac{3+\sqrt{3}}{12}(\frac{\sqrt{2}+\sqrt{6}}{2})^{n}+\frac{3+\sqrt{3}}{12}(\frac{-\sqrt{2}-\sqrt{6}}{2})^{n}.$

By rearranging, the formula becomes:

$T_{3}(n)=\frac{\alpha^{n+1}-(\frac{-1}{\alpha})^{n+1}}{2\sqrt{6}}+\frac{(\frac{1}{\alpha})^{n+1}-(-\alpha)^{n+1}}{2\sqrt{6}}=(1-(-1)^{n+1})\frac{\alpha^{n+1}+(\frac{1}{\alpha})^{n+1}}{2\sqrt{6}}$

where $\alpha=\frac{\sqrt{2}+\sqrt{6}}{2}$. ∎

######  Proposition A.3.

The following identity holds:

$\sum_{i=0}^{n-2}T_{4}(i)=\frac{T_{4}(n)-T_{4}(n-3)}{5}.$

###### Proof.

$T_{4}(n)=T_{4}(n-1)+T_{4}(n-2)+2\sum_{i=0}^{n-2}T_{4}(i)+T_{4}(n-2)+T_{4}(n-4)+T_{4}(n-6)+...+(T_{4}(1)\text{
if n is odd) or }(T_{4}(0)\text{ if n is even})$. By substituting $n-1$ for
$n$, we see that
$T_{4}(n-1)=T_{4}(n-2)+T_{4}(n-3)+2\sum_{i=0}^{n-3}T_{4}(i)+T_{4}(n-3)+T_{4}(n-5)+T_{4}(n-7)+...+(T_{4}(0)\text{
if n is odd) or }(T_{4}(1)+T_{4}(-1)\text{ if n is even})$. Since
$T_{4}(-1)=0$, we can ignore that term. By adding these two equations
together, we find that

$\displaystyle T_{4}(n)+T_{4}(n-1)$
$\displaystyle=(T_{4}(n-1)+T_{4}(n-2)+2\sum_{i=0}^{n-2}T_{4}(i)$
$\displaystyle+T_{4}(n-2)+T_{4}(n-4)+T_{4}(n-6)+...$
$\displaystyle+(T_{4}(1)\text{ if n is odd) or }(T_{4}(0)\text{ if n is
even}))$ $\displaystyle+(T_{4}(n-2)+T_{4}(n-3)+2\sum_{i=0}^{n-3}T_{4}(i)$
$\displaystyle+T_{4}(n-3)+T_{4}(n-5)+T_{4}(n-7)+...$
$\displaystyle+(T_{4}(0)\text{ if n is odd) or }(T_{4}(1)+T_{4}(-1)\text{ if n
is even}))$ $\displaystyle=T_{4}(n-1)+T_{4}(n-3)+5\sum_{i=0}^{n-2}T_{4}(i).$

From this equality, we can deduce that

$\sum_{i=0}^{n-2}T_{4}(i)=\frac{T_{4}(n)-T_{4}(n-3)}{5}.$

∎

######  Proposition A.4.

The following identity holds:

$\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}T_{4}(n-2i)=-\frac{2}{5}T_{4}(n)+4T_{4}(n-2)+\frac{7}{5}T_{4}(n-3)-T_{4}(n-4).$

###### Proof.

Again, we start with
$T_{4}(n)=T_{4}(n-1)+T_{4}(n-2)+2\sum_{i=0}^{n-2}T_{4}(i)+\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}T_{4}(n-2i)$.
From the previous proposition, we can rewrite this formula as
$T_{4}(n)=T_{4}(n-1)+T_{4}(n-2)+2\frac{T_{4}(n)-T_{4}(n-3)}{5}+\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}T_{4}(n-2i)$
We also know that $T_{4}(n)=T_{4}(n-1)+5T_{4}(n-2)+T_{4}(n-3)-T_{4}(n-4)$. The
result follows from equating these two versions of $T_{4}(n)$ and solving for
$\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}T_{4}(n-2i)$. ∎

######  Corollary A.5.

The number of perfect matchings of $L_{4,n+m}$ is given by

$\displaystyle T_{4}(m+n)$
$\displaystyle=T_{4}(m)T_{4}(n)+T_{4}(m-1)T_{4}(n-1)$
$\displaystyle+\frac{2(T_{4}(m+1)-T_{4}(m-2))(T_{4}(n+1)-T_{4}(n-2))}{25}$
$\displaystyle+f(m+1)f(n+1)$ $\displaystyle+f(m)f(n).$

Where
$f(n)=-\frac{2}{5}T_{4}(n)+4T_{4}(n-2)+\frac{7}{5}T_{4}(n-3)-T_{4}(n-4)$.

###### Proof.

$\displaystyle T_{4}(m+n)$ $\displaystyle=\sum_{B}T_{4}(m\sqcup_{0,B}n)$
$\displaystyle=T_{4}(m)T_{4}(n)+4(0)+2\frac{(T_{4}(m+1)-T_{4}(m-2))(T_{4}(n+1)-T_{4}(n-2))}{25}$
$\displaystyle+f(m+1)f(n+1)$ $\displaystyle+f(m)f(n)$
$\displaystyle+4(0)+T_{4}(m-1)T_{4}(n-1).$

∎

######  Proposition A.6.

The number of ways to tile $L_{4,n}$ with dominoes is given by the explicit
formula

$\displaystyle\frac{\frac{6}{b}+5-\frac{1}{b^{3}}}{(1-\frac{1}{b^{2}})(1-\frac{b}{a})(1-ab)}b^{n}-\frac{6b+5-b^{3}}{(1-\frac{1}{b^{2}})(1-\frac{b}{a})(1-ab)}(\frac{1}{b})^{n}$
$\displaystyle+\frac{\frac{6}{a}+5-\frac{1}{a^{3}}}{(1-\frac{1}{a^{2}})(1-\frac{a}{b})(1-ab)}a^{n}-\frac{6a+5-a^{3}}{(1-\frac{1}{a^{2}})(1-\frac{a}{b})(1-ab)}(\frac{1}{a})^{n},$

where $a=\frac{1+\sqrt{29}+\sqrt{14+2\sqrt{29}}}{4}$ and
$b=\frac{1-\sqrt{29}-\sqrt{14-2\sqrt{29}}}{4}$.

###### Proof.

Use the same method as for the proof of Proposition A.2. ∎

We conjecture that for every positive integer $k$, there exists a real number
$x\in\mathbb{R}$ such that the solutions to the equation
$\frac{x^{5}+1}{x^{2}(x+1)}=\frac{y^{5}+1}{y^{2}(y+1)}$, which are at most two
pairs of reciprocal numbers, denoted
$y_{1},\frac{1}{y_{1}},y_{2},\frac{1}{y_{2}}$ allow us to define functions
$f_{k,1}(y_{1},y_{2}),f_{k,2}(y_{1},y_{2}),f_{k,3}(y_{1},y_{2}),f_{k,4}(y_{1},y_{2})$
such that
$T_{k}(n)=f_{k,1}(y_{1},y_{2})y_{1}^{n}+f_{k,2}(y_{1},y_{2})\frac{1}{y_{1}}^{n}+f_{k,3}(y_{1},y_{2})y_{2}^{n}+f_{k,4}(y_{1},y_{2})\frac{1}{y_{2}}^{n}$,
where $T_{k}(n)$ is an explicit formula for the number of ways to tile
$L_{k,n}$.

## References