# Boundary Value Problems for Dirac Operators on Graphs

Alberto Richtsfeld  Institut für Mathematik,
Universität Potsdam,
D-14476, Potsdam, Germany
<EMAIL_ADDRESS>
###### Abstract

We carry the index theory for manifolds with boundary of Bär and Ballmann over
to first order differential operators on metric graphs. This results in an
elegant proof for the index of such operators. Then the self-adjoint
extensions and the spectrum of the Dirac operator on the complex line bundle
are studied. We also introduce two types of boundary conditions for the Dirac
operator, whose spectrum encodes information of the underlying topology of the
graph.

##  1 Introduction

Schrödinger operators on metric graphs, known as quantum graphs, have a long
history of study with applications in many fields, including mathematics,
physics and engineering. They provide toy models for quantum mechanics, but
also describe the motion of particles through thin metallic wires called
nanowires. We will mainly focus on the following mathematical aspects of the
theory of quantum graphs, namely self-adjoint extensions, which are realised
by imposing boundary conditions at each vertex, and the index theory of these
operators. A full treatment of self-adjoint extensions can be found in [9, 10,
12, 13], which is summarised by Kuchment [14], the take-away being that for
the Schrödinger operator self-adjoint extensions are given by a combination of
Dirichlet, von Neumann and Robin boundary conditions. Index theory for quantum
graphs was treated by Fulling, Kuchment and Wilson [9], relating the index to
heat kernel asymptotics. A nice overview of the study of quantum graphs is
given for example by Kuchment [14].

In order to study the effect of spin on the quantum mechanics of graphs, the
Dirac operator has to be considered. The first ones to study a two-
dimensional, quantum-mechanical Dirac operator on graphs were Bulla and
Trenkler [3]. They studied self-adjoint extensions of the Dirac operator on
directed graphs and computed its spectrum on a junction of three wires, a
graph for which the Schrödinger operator had previously been considered by
Exner and Šeba [8]. Bolte and Harrison [2] considered this Dirac operator in a
similar way to the approach taken in this paper: the graph under consideration
is metric in the sense that each edge has an associated length, and its
boundary conditions are given by a unitary matrix describing complex
transition probability amplitudes. Post [15] introduced a discrete notion of
the Dirac operator and computed the index of the discrete and metric Dirac
operators, by finding that it is equal to the Euler-characteristic of the
graph. For more information on the study of Dirac operators on graphs, see the
survey article [11] written by Harrison.

The point of view in this paper is as follows: A metric graph can be
reinterpreted as a one-dimensional Riemannian manifold with boundary, where
each connected component is isomorphic to a closed interval. We then consider
the Dirac operator on this one-dimensional manifold, subject to boundary
conditions that respect the underlying graph structure. The aim is to study
the self-adjoint extensions and the index of this operator, and to find
interesting boundary conditions.

The index theory of Dirac operators on manifolds with boundary was initiated
by the seminal paper of Atiyah, Patodi and Singer [1], whose main achievement
was the discovery of a non-local boundary condition, formulated in terms of
the spectrum of the boundary operator. The theory centred on boundary value
problems for Dirac operators was then simplified and unified by Bär and
Ballmann [4, 5], in which they characterised all extensions of the Dirac
operators with linear subspaces of the czech-space, a Banach space formed from
the eigenspaces of the boundary operator. These results were then extended by
Bär and Bandara [6] to general first-order differential operators. We will
work in the spirit of the Bär-Ballmann framework, but the theory does not
apply directly to the one-dimensional case, since there is no notion of a
boundary operator in this case, since the boundary is zero-dimensional.

The paper is structured as follows: First, we consider general first-order
differential operators over metric graphs with coefficients in a general
bundle, without specifying the boundary conditions. Using techniques developed
by Bär and Ballmann, we quickly obtain a general index formula for such
operators. We then turn our attention to the scalar-valued Dirac operator and
explore properties of its spectrum. In the last part we discuss two types of
boundary conditions. The first is given by certain permutation matrices which
encode decompositions of the underlying graph into directed trails, the
spectrum of the Dirac operator is then explicitly calculable and is fully
determined by the lengths of the trails appearing in the decomposition. The
second boundary condition is given by the directed adjacency matrix, which
distributes the inflow at a vertex evenly among the outgoing edges. This
boundary conditions is in general no longer self-adjoint, but it links the
spectrum of the Dirac operator to the appearance of cycles in the graph. Thus,
both types of boundary conditions reveal properties of the cycles and trails
present in the graph, linking its topology to the spectrum of the Dirac
operator.

##  2 Preliminaries

A metric graph $G=(V,E,l)$ is given by a directed multigraph with vertex set
$V$ and edge set $E$ and a length function $l:E\rightarrow(0,\infty)$,
$e\mapsto l_{e}$. For each edge $e\in E$ we denote by $\partial_{-}e$ the tail
of $e$ and by $\partial_{+}e$ the head of $e$. We then interprete $G$ as the
following topological space

$G=\bigsqcup_{e\in E}[0,l_{e}]/_{\sim},$

where $x\sim y$ iff $\psi(x)=\psi(y)$ with

$\psi:\bigsqcup_{e\in E}\\{0,l_{e}\\}\rightarrow V\qquad
0_{e}\mapsto\partial_{-}e,\quad l_{e}\mapsto\partial_{+}e.$

We denote the coordinate on the egde $e$ by $x_{e}$. For our purposes, we will
always assume that our metric graph is finite and has no isolated vertices.

We define now the following function spaces on $G$:

$L^{2}(G,\mathbb{C}^{r})=\bigoplus_{e\in
E}L^{2}([0,l_{e}],\mathbb{C}^{r}),\quad
H^{1}(G,\mathbb{C}^{r})=\bigoplus_{e\in E}H^{1}([0,l_{e}],\mathbb{C}^{r}),$
$C^{\infty}(G,\mathbb{C}^{r})=\bigoplus_{e\in
E}C^{\infty}([0,l_{e}],\mathbb{C}^{r}).$

Standard Sobolev estimates now tell us that each function in
$H^{1}(G,\mathbb{C}^{r})$ is continuous when restricted to a single edge and
that there is a well-defined bounded operator

$\operatorname{tr}:H^{1}(G,\mathbb{C}^{r})\rightarrow\mathbb{C}^{r}[G]\qquad
f\mapsto\sum_{e\in E}f(0_{e})e_{-}+f(l_{e})e_{+}$

where $\mathbb{C}^{r}[G]\cong\mathbb{C}^{r\lvert
E\rvert}\oplus\mathbb{C}^{r\lvert E\rvert}$. This allows us to introduce
boundary conditions on the graph: A boundary condition is a linear subspace
$B\subseteq\mathbb{C}^{r}[G]$, we then denote the space of $H^{1}$-functions
which fulfill the boundary condition $B$ by

$H^{1}_{B}(G,\mathbb{C}^{r})=\\{f\in
H^{1}(G,\mathbb{C}^{r})\mid\operatorname{tr}(f)\in B\\}.$

If $B=\\{0\\}$, we write $H^{1}_{0}(G,\mathbb{C}^{r})$ instead. Letting

$\mathbb{C}^{r,V}:=\left\\{\sum_{v\in V}c_{v}\cdot v\mid
c_{v}\in\mathbb{C}^{r}\right\\},$

for a vertex $v\in V$, we can define
$\mathbb{C}_{v}^{r}[G]:=\psi_{G}^{-1}(\operatorname{span}(v))$, where
$\psi_{G}:\mathbb{C}^{r}[G]\rightarrow\mathbb{C}^{V}$ is the linear map
mapping $e_{-}\mapsto\partial_{-}e$ and $e_{+}\mapsto\partial_{+}e$. We now
say that a boundary condition $B$ is local iff there are linear subspaces
$B_{v}\subseteq\mathbb{C}_{v}^{r}[G]$, such that

$B=\bigoplus_{v\in V}B_{v}.$

Furthermore, we define the following spaces:

$\displaystyle\mathbb{C}^{r,G}$ $\displaystyle:=\left\\{\sum c_{e}\cdot e\mid
c_{e}\in\mathbb{C}^{r}\right\\}$ $\displaystyle\mathbb{C}_{+}^{r}(G,v)$
$\displaystyle:=\operatorname{span}(\\{e\mid e\text{ ends at
}v\\})\subseteq\mathbb{C}^{r,G}$ $\displaystyle\mathbb{C}_{-}^{r}(G,v)$
$\displaystyle:=\operatorname{span}(\\{e\mid e\text{ starts at
}v\\})\subseteq\mathbb{C}^{r,G}$

In the case that $r=1$, we omit $r$ in the above definitions. Note that there
are canonical inclusions
$\iota_{\pm}:\mathbb{C}^{r,G}\rightarrow\mathbb{C}^{r}[G]$ sending $e$ to
$e_{\pm}$ and that $\mathbb{C}^{r,V}$ is equal to the direct sum
$\iota_{+}(\mathbb{C}_{+}^{r}(G,v))\oplus\iota_{-}(\mathbb{C}_{-}^{r}(G,v))$.
We equip all so far defined vector spaces with the canonical inner products
making any two elements of the generating sets orthonormal to each other.

Given two endomorphism fields $\sigma,A\in C^{\infty}(G,\mathbb{C}^{r\times
r})$ we can define a first order differential operator

$D:C^{\infty}(G,\mathbb{C}^{r})\rightarrow C^{\infty}(G,\mathbb{C}^{r}),\qquad
f\mapsto\sigma f^{\prime}+Af.$

We will always assume that the differential operator $D$ is elliptic, i.e.
that $\sigma$ is non-singular at every point. $D$ naturally extends to a
bounded operator

$D_{\max}:H^{1}(G,\mathbb{C}^{r})\rightarrow L^{2}(G,\mathbb{C}^{r})$

and consequently for a boundary condition $B$ we can restrict $D_{\max}$ to
$H^{1}_{B}(G,\mathbb{C}^{r})$, yielding the operator $D_{B}$. If $B=\\{0\\}$,
write $D_{\min}$ instead. These operators will be the center of our study.

It is straightforward to check that the unbounded operator

$D_{B}:H^{1}_{B}(G,\mathbb{C}^{r})\subseteq L^{2}(G,\mathbb{C}^{r})\rightarrow
L^{2}(G,\mathbb{C}^{r})$

is closed, densely defined and a Fredholm operator. Furthermore, we have the
following Green’s formula:

######  2.1 Lemma.

For $f,g\in H^{1}(G,\mathbb{C}^{r})$, we have that

$\langle D_{\max}f,g\rangle-\langle
f,D_{\max}^{\dagger}g\rangle=\langle\sigma_{0}\operatorname{tr}(f),\operatorname{tr}(g)\rangle,$

where $D^{\dagger}$ is the formal adjoint of $D$ and

$\sigma_{0}:\mathbb{C}^{r}[G]\rightarrow\mathbb{C}^{r}[G],\qquad\sum_{e\in
E}a_{e}e_{-}+b_{e}e_{+}\mapsto\sum_{e\in
E}-\sigma(0_{e})a_{e}e_{-}+\sigma(l_{e})b_{e}e_{+}.$

We directly obtain

######  2.2 Proposition.

Let $B$ be a boundary condition, define the adjoint boundary condition by

$B^{\mathrm{ad}}:=\\{y\in\mathbb{C}^{r}[G]\mid\forall b\in
B:\langle\sigma_{0}b,y\rangle=0\\}.$

Then, the adjoint of $D_{B}$ is given by $D_{B^{\mathrm{ad}}}^{\dagger}$. In
particular, $D_{B}$ is self-adjoint iff $D$ is formally self-adjoint and
$B=B^{\mathrm{ad}}$.

######  2.3 Corollary.

The adjoint of $D_{\max}$ is $D^{\dagger}_{\min}$ and the adjoint of
$D_{\min}$ is $D^{\dagger}_{\max}$.

##  3 The index of $D_{B}$

By elementary ODE-theory we can solve the equation

$D_{max}f=g$

on each edge separetely for any $g\in L^{2}(G,\mathbb{C}^{r})$ . Hence
$D_{\max}$ is surjective. Furthermore, it is easily seen that the dimension of
the solution space of the equation

$D_{\max}f=0$

is equal to $r$ on each single edge, and since the kernel of $D_{\max}$ is
just the direct sum of the kernels of the single edges, we obtain

$\dim\ker D_{\max}=r\lvert E\rvert.$

We have therefore proven

######  3.1 Lemma.

The following equations hold:

$\operatorname{ind}D_{\max}=r\lvert
E\rvert,\qquad\operatorname{ind}D_{\min}=-r\lvert E\rvert$

In order to prove the general index formula, we pursue the approach developed
by Bär and Ballmann. We need the following proposition:

######  3.2 Proposition.

Let $H$ be a Hilbert space, $E$ and $F$ Banach spaces and let $L:H\rightarrow
E$ and $P:H\rightarrow F$ be bounded linear maps. Assume that $P:H\rightarrow
F$ is onto. Then, $L|_{\ker P}:\ker P\rightarrow E$ is Fredholm of index $k$
if and only if $L\oplus P:H\rightarrow E\oplus F$ is Fredholm of index $k$.

###### Proof.

See [4, Proposition A.1]. ∎

Analogous to [4, Corollary 8.7], we have:

######  3.3 Lemma.

Let $B$ be a subspace of $\mathbb{C}^{r}[G]$, $B^{\perp}$ be the orthogonal
complement to $B$ and let $P:\mathbb{C}^{r}[G]\rightarrow\mathbb{C}^{r}[G]$ be
the orthogonal projection onto $B^{\perp}$. Then,

$\displaystyle L:H^{1}(G,\mathbb{C}^{r})$ $\displaystyle\rightarrow
L^{2}(G,\mathbb{C}^{r})\oplus B^{\perp}$ $\displaystyle g$
$\displaystyle\mapsto(D_{\max}g,P\operatorname{tr}g)$

is a Fredholm operator with the same index as $D_{B}$.

###### Proof.

The kernel of $P\operatorname{tr}$ is equal to $H^{1}_{B}(G,\mathbb{C}^{r})$.
The statement then follows directly from Proposition 3.2. ∎

As in [4, Corollary 8.8], we go on to obtain:

######  3.4 Lemma.

Let $B_{1}\subseteq B_{2}\subseteq\mathbb{C}^{r}[G]$ be boundary conditions.
Then,

$\operatorname{ind}D_{B_{2}}=\operatorname{ind}D_{B_{1}}+\dim B_{2}/B_{1}.$

###### Proof.

Since $B_{1}$ is a subspace of $B_{2}$, the orthogonal complement
$B_{2}^{\perp}$ is a subspace of $B_{1}^{\perp}$. Denote the inclusion of
$B_{2}^{\perp}$ into $B_{1}^{\perp}$ by $\iota$. The diagram

---
$\textstyle{L^{2}(G,\mathbb{C}^{r})\oplus
B_{2}^{\perp}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\operatorname{id}\oplus\iota}$$\textstyle{H^{1}(G,\mathbb{C}^{r})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(D,Q_{2})}$$\scriptstyle{(D,Q_{1})}$$\textstyle{L^{2}(G,\mathbb{C}^{r})\oplus
B_{1}^{\perp}}$

commutes, where, as in Lemma 3.3, the operator $Q_{i}$ is the composition of
$\operatorname{tr}$ with the orthogonal projection onto $B_{i}^{\perp}$.
Clearly, $\operatorname{id}\oplus\iota$ is a Fredholm operator with index

$\operatorname{ind}(\operatorname{id}\oplus\iota)=\operatorname{ind}(\iota)=-\dim(B^{\perp}_{1}/B^{\perp}_{2})=-\dim(B_{2}/B_{1}).$

Since the index is additive, we have

$\displaystyle\operatorname{ind}D_{B_{1}}$
$\displaystyle=\operatorname{ind}(D,Q_{1})$
$\displaystyle=\operatorname{ind}(D,Q_{2})+\operatorname{ind}\operatorname{id}\oplus
i$ $\displaystyle=\operatorname{ind}D_{B_{2}}-\dim B_{2}/B_{1}.\qed$

######  3.5 Theorem.

For any boundary condition $B$, the following formula for the index of $D_{B}$
holds:

$\operatorname{ind}(D_{B})=\dim B-r|E|.$ (1)

###### Proof.

Applying Lemma 3.4, the index of $D_{B}$ is given by

$\displaystyle\dim D_{B}$ $\displaystyle=\dim B+\operatorname{ind}D_{0}$
$\displaystyle=\dim B+\operatorname{ind}D_{\min}$ $\displaystyle=\dim
B-r|E|.\qed$

##  4 The scalar Dirac operator

For the rest of the paper, we will focus on the scalar Dirac operator, that
is, we take $r=1$ and set $D=i\frac{d}{dx}$. We will first study its self-
adjoint extensions:

###  4.1 Self-adjoint extensions

Let $A:\mathbb{C}^{G}\rightarrow\mathbb{C}^{G}$ be a linear map, we can then
define an associated boundary condition

$\Gamma(A):=\left\\{\iota_{+}(x)+\iota_{-}(Ax)\mid
x\in\mathbb{C}^{G}\right\\}$

which we call the graph of $A$. We say that $A$ is a $G$-endomorphism, if
$\Gamma(A)$ is a local boundary condition. In this case for each $v\in V$, $A$
restricts to a homomorphism
$A_{v}:\mathbb{C}_{+}(G,v)\rightarrow\mathbb{C}_{-}(G,v)$.

######  4.1 Theorem.

Let $B$ be a local boundary condition on $G$. Then, $D_{B}$ is self-adjoint
iff there exists a unitary $G$-endomorphism $A$, such that $B=\Gamma(A)$.

###### Proof.

Let $B$ be such that $D_{B}$ is self-adjoint. Since the index of a self-
adjoint operator is zero, by Theorem 3.5, the dimension of $B$ is equal to the
amount of edges, denoted by $n$. Choosing a basis $b_{1},...,b_{n}$ of $B$,
let

$b_{i}^{\pm}=\pi_{\pm}(b_{i})\in\mathbb{C}^{G}$

for $i=1,...,n$, where $\pi_{\pm}:\mathbb{C}[G]\rightarrow\mathbb{C}^{G}$ is
the map sending $e_{\pm}$ to $e$ and $e_{\mp}$ to $0$. Now, assume that there
exist $\lambda_{1},...,\lambda_{n}$, such that

$\sum_{i=1}^{n}\lambda_{i}b^{+}_{i}=0.$

Letting

$b=\sum_{i=1}^{n}\lambda_{i}b_{i},$

we arrive at $\pi_{+}(b)=0$. Since $B$ is equal to its adjoint boundary
condition, by propositon 2.2 we have

$\displaystyle
0=\langle\sigma_{0}(b),b\rangle=i\langle\pi_{-}(b),\pi_{-}(b)\rangle-i\langle\pi_{+}(b),\pi_{+}(b)\rangle=i\langle\pi_{-}(b),\pi_{-}(b)\rangle.$

Therefore, $\pi_{-}(b)$ is also zero, which implies that $b$ is equal to zero.
Since $b_{1},..,b_{n}$ is a basis of $B$,

$\lambda_{1}=...=\lambda_{n}=0$

follows. Consequently, the vectors $b^{+}_{1},...,b^{+}_{n}$ are linearly
independent. Considering that the dimension of $\mathbb{C}^{G}$ is equal to
$n$, it follows that $b^{+}_{1},...,b^{+}_{n}$ forms a basis of
$\mathbb{C}^{G}$. W.l.o.g., $b_{1},...,b_{n}$ can be chosen such that
$b^{+}_{1},...,b^{+}_{n}$ is an orthonormal basis of $\mathbb{C}^{G}$. Define
$A$ as the linear map sending $b^{+}_{i}$ to $b^{-}_{i}$ for
$i\in\\{1,...,n\\}$. Since $B=B^{\operatorname{ad}}$, we have

$\langle\sigma_{0}(b_{i}),b_{j}\rangle=0$

for $i,j\in\\{1,...,n\\}$, hence

$i\langle b^{-}_{i},b^{-}_{j}\rangle-i\langle b^{+}_{i},b^{+}_{j}\rangle=0.$

Rearranging this equation and using the definition of $A$, this yields

$\displaystyle\langle b^{+}_{i},b^{+}_{j}\rangle=\langle
Ab^{+}_{i},Ab^{+}_{j}\rangle,$

which proves that $A$ is unitary. It is easily checked that $A$ is a
$G$-endomorphism. Therefore, each $b_{i}$ is contained in $\Gamma(A)$ for
$i\in\\{1,...,n\\}$ and, consequently, the same can be said for $B$. Equality,
then, holds by equality of dimensions.

Conversely, it is easily checked that for a given unitary $G$-endomorphism
$A$, the graph $\Gamma(A)$ is a local boundary condition for $G$ such that
$\Gamma(A)^{\operatorname{ad}}=\Gamma(A)$. ∎

Unfortunately, the existence of self-adjoint boundary conditions poses quite
some restrictions on the graph itself:

######  4.2 Proposition.

If there exists a boundary condition $B$ on $G$ such that $D_{B}$ is self-
adjoint, then every connected component of $G$ is a Eulerian digraph.

###### Proof.

By Theorem 4.1, there exists a unitary $G$-endomorphism $A$ such that $B$ is
the graph of $A$. Restricting $A$ to each vertex space, we then obtain
isometries $A_{v}$ from $\mathbb{C}_{+}(G,v)$ to $\mathbb{C}_{-}(G,v)$, and
hence the dimensions of the two spaces must be equal, implying that each
vertex has as many ingoing as outgoing edges. ∎

###  4.2 The spectrum of the Dirac operator

We proceed with the study of the spectrum $\sigma(D_{B})$ of $D_{B}$ and start
with some general properties:

######  4.3 Proposition.

Let $B$ be a boundary condition on $G$. If the dimension of $B$ is not equal
to the number of edges $n$ of $G$, then the spectrum of $D_{B}$ is equal to
$\mathbb{C}$. Otherwise, the spectrum of $D_{B}$ is equal to the point
spectrum, i.e. $\sigma(D_{B})=\sigma_{p}(D_{B})$.

###### Proof.

Assume that $\lambda$ is an element of the resolvent set of $D_{B}$. Then the
operator $D-\lambda I$ is bijective, and hence the index of $(D-\lambda
I)_{B}=D_{B}-\lambda I$ must be zero. Theorem 3.5 implies that the dimension
of $B$ is equal to $n$. Consequently, if the dimension of $B$ is not equal to
$n$, the resolvent set of $D_{B}$ is empty.

Now, let the dimension of $B$ be equal to $n$. We have to show that
injectivity of $D_{B}-\lambda I$ implies surjectivity. Assuming that
$D_{B}-\lambda I$ is injective, by Theorem 3.5, the codimension of
$\operatorname{ran}D_{B}-\lambda I$ is zero. Furthermore, $D_{B}-\lambda I$
has closed range since it is Fredholm. Together, this implies that
$D_{B}-\lambda I$ is surjective. ∎

We now turn to boundary conditions given by $G$-endomorphisms. The spectrum of
the Dirac operator under such boundary conditions is closely related to the
eigenvalues of the defining $G$-endomorphism. However, the different lengths
of the edges distort the powers of the variables in the characteristic
polynomial, such that it is necessary to introduce a multi-dimensional
version:

######  4.4 Definition.

For a $G$-endomorphism $A$ define the multi-dimensional characteristic
polynomial $P_{A}$ of $A$ to be the polynomial in the variables $\\{x_{e}\mid
e\in E(G)\\}$ given by

$P_{A}(x)=\det\left(\operatorname{diag}(x)-A\right),$

where $diag(x)$ is the linear map on $\mathbb{C}^{G}$ given by $\sum_{e\in
E}x_{e}e\otimes e^{\ast}$. The characteristic function
$P_{A,l}:\mathbb{C}\rightarrow\mathbb{C}$ with respect to the length function
$l$ is given by

$P_{A,l}(\lambda)=P_{A}(\exp(i\lambda l)),$

where $\exp(i\lambda l)=\sum_{e\in E}\exp(i\lambda l_{e})e$.

The following Lemma allows us to delete vertices that have exactly one in-
coming and one outgoing edge when dealing with the multi-dimensional
characteristic polynomial. This will facilitate future arguments and
calculations regarding the spectrum of the Dirac operator.

######  4.5 Lemma.

Let $A$ be a $G$-endomorphism and let $v\in V(G)$ be a vertex of $G$ with both
in- and out-degrees equal to one, such that the ingoing edge is different from
the outgoing edge. Enumerate the edges of $G$ by $e_{1},e_{2},...,e_{n}$ such
that $e_{1}$ is the ingoing and $e_{2}$ is the outgoing edge at $v$, defining
a basis of $\mathbb{C}^{G}$. Let $\tilde{G}$ be the graph obtained out of $G$
by replacing $e_{1}$ and $e_{2}$ with a single edge $e$ running from the tail
of $e_{1}$ to the head of $e_{2}$. The transformation matrix of $A$ with
respect to the basis is then given by

$A=\scalebox{0.9}{$\left(\begin{array}[]{@{}c
c@{}}\begin{matrix}0&\alpha_{12}\\\
\alpha&0\end{matrix}&\begin{matrix}\ldots&\alpha_{1n}\\\
\ldots&0\end{matrix}\\\ \begin{matrix}0&\alpha_{32}\\\ \vdots&\vdots\\\
0&\alpha_{n2}\end{matrix}&\hat{A}\end{array}\right)$}.$

Revising $A$, we arrive at the following matrix $\tilde{A}$, which defines a
$\tilde{G}$-automorphism with respect to the basis $e,e_{3},...,e_{n}$:

$\tilde{A}=\left(\begin{array}[]{@{}c
c@{}}\alpha\alpha_{12}&\begin{matrix}\ldots&\alpha\alpha_{1n}\end{matrix}\\\
\begin{matrix}\alpha_{32}\\\ \vdots\\\
\alpha_{n2}\end{matrix}&\hat{A}\end{array}\right)$

For the multi-dimensional characteristic polynomials, then

$P_{A}(x_{1},x_{2},...,x_{n})=P_{\tilde{A}}(x_{1}x_{2},...,x_{n})$

holds. In particular, if the length of $e$ is the sum of the lengths of
$e_{1}$ and $e_{2}$, then $P_{A,l}$ is equal to $P_{\tilde{A},\tilde{l}}$,
where $\tilde{l}$ is the induced length function on $\tilde{G}$.

###### Proof.

The lemma follows from a quick calculation using the Laplace expansion along
the first column and the multilinearity of determinants:

$\displaystyle P_{A}(x_{1},x_{2},...,x_{n})$
$\displaystyle=\det\scalebox{0.9}{$\left(\begin{array}[]{@{}c
c@{}}\begin{matrix}x_{1}&-\alpha_{12}\\\
-\alpha&x_{2}\end{matrix}&\begin{matrix}\ldots&-\alpha_{1n}\\\
\ldots&0\end{matrix}\\\ \begin{matrix}0&-\alpha_{32}\\\ \vdots&\vdots\\\
0&-\alpha_{n2}\end{matrix}&\operatorname{diag}(\hat{x})-\hat{A}\end{array}\right)$}$
$\displaystyle=x_{1}\left(\begin{array}[]{@{}c
c@{}}x_{2}&\begin{matrix}0&\ldots&0\end{matrix}\\\
\begin{matrix}-\alpha_{32}\\\ \vdots\\\
-\alpha_{n2}\end{matrix}&\operatorname{diag}(\hat{x})-\hat{A}\end{array}\right)+\alpha\left(\begin{array}[]{@{}c
c@{}}-\alpha_{12}&\begin{matrix}\ldots&-\alpha_{1n}\end{matrix}\\\
\begin{matrix}-\alpha_{32}\\\ \vdots\\\
-\alpha_{n2}\end{matrix}&\operatorname{diag}(\hat{x})-\hat{A}\end{array}\right)$
$\displaystyle=\left(\begin{array}[]{@{}c
c@{}}x_{1}x_{2}-\alpha\alpha_{12}&\begin{matrix}\ldots&-\alpha\alpha_{1n}\end{matrix}\\\
\begin{matrix}-\alpha_{32}\\\ \vdots\\\
-\alpha_{n2}\end{matrix}&\operatorname{diag}(\hat{x})-\hat{A}\end{array}\right)=P_{\tilde{A}}(x_{1}x_{2},...,x_{n}).$

It is easily checked that $\tilde{A}$ indeed defines a
$\tilde{G}$-automorphism. The equality of the characteristic functions follows
from

$P_{A,l}(\lambda)=P_{A}(e^{i\lambda l_{1}},e^{i\lambda l_{2}},...,e^{i\lambda
l_{n}})=P_{\tilde{A}}(e^{i\lambda(l_{1}+l_{2})},...,e^{i\lambda
l_{n}})=P_{\tilde{A},\tilde{l}}(\lambda).$

∎

The next proposition relates the eigenvalues of the Dirac operator to the
zeroes of the characteristic function of $A$. However, if the lengths of the
edges are incommensurable, i.e. they have no common rational divisor, the
characteristic function can no longer be related to a polynomial, which makes
the solution of this problem very difficult.

######  4.6 Proposition.

Let $A$ be a $G$-endomorphism. Then the spectrum of $D_{\Gamma(A)}$ is equal
to the set of zeroes of $P_{A,l}$, i.e.

$\sigma(D_{\Gamma(A)})=P_{A,l}^{-1}(\\{0\\}).$

The multiplicity of an eigenvalue $\lambda$ is given by), which will be also
referred to as the canonical Dirac operator

$m_{\Gamma(A)}(\lambda)=\dim\ker(\operatorname{diag}(\exp(i\lambda l))-A).$

######  Remark.

Note that $P_{A,l}(\lambda)$ does not capture the kernel of $A$. For instance,
if $A=0$, then the spectrum of $D_{\Gamma(0)}$ is empty.

###### Proof.

Let $\lambda\in\sigma(D_{\Gamma(A)})$. Since the dimension of $\Gamma(A)$ is
equal to the number of edges of $G$, by Proposition 4.3, there exists an
eigenvector $\phi\in C^{\infty}(G)$ to the eigenvalue $\lambda$, i.e. $\phi$
fulfills

$D\phi=\lambda\phi,\qquad\operatorname{tr}\phi\in\Gamma(A).$

The first condition implies that on each edge $\phi$ is of the form
$w_{e}\exp(-i\lambda x_{e})$ for some $w_{e}\in\mathbb{C}$ and together with
the second condition we obtain the equation

$A\sum w_{e}\exp(-i\lambda l_{e})e=\sum w_{e}e,$

which is equivalent to $P_{A,l}(\lambda)=0$. It is easy to see that any
element of $\ker(\operatorname{diag}(\exp(i\lambda l))-A)$ defines a
eigenfunction to the eigenvalue $\lambda$. This then implies the equivalence
of the first statement and proves the assertion on the multiplicity. ∎

If all edges of the digraph have the same length, the spectrum of
$D_{\Gamma(A)}$ is particularly easy to compute:

######  4.7 Corollary.

Let all edges have the same length $l$ and $A$ be a $G$-endomorphism. Let
$\mu_{1},...,\mu_{m}$ be the non-zero eigenvalues of $A$. Then, there exist
unique $\alpha_{1},...,\alpha_{m}\in\mathbb{R}$ and
$\varphi_{1},...,\varphi_{m}\in[0,2\pi)$ such that

$\mu_{j}=\exp(\alpha_{j}+i\varphi_{j}).$

The spectrum of $D_{\Gamma(A)}$ is then given by

$\sigma(D_{\Gamma(A)})=\left\\{(\varphi_{j}-i\alpha_{j}+2\pi k)/l\mid
j\in\\{1,...,m\\}\text{, }k\in\mathbb{Z}\right\\}.$

###### Proof.

By Proposition 4.6, $\lambda$ is an eigenvalue of $D_{\Gamma(A)}$ if and only
if $e^{i\lambda l}\in\mathbb{C}$ is an eigenvalue of $A$. This proves the
corollary. ∎

A matrix $A$ is reducible if there exists a permutation matrix $P$ such that
$P^{-1}AP$ is of the form

$\left(\begin{array}[]{c c}X&0\\\ Y&Z\\\ \end{array}\right),$

where $X$ and $Z$ are square matrices. Otherwise, $A$ is said to be
irreducible [7, p.18]. We transfer this definition to linear maps on $G$:

######  4.8 Definition.

A $G$-endomorphism $A$ is said to be reducible with respect to a proper subset
$\Delta$ of $E(G)$ if $A$ maps
$\mathbb{C}^{\Delta}:=\\{\sum_{e\in\Delta}c_{e}\cdot e\mid
c_{e}\in\mathbb{C}\\}$ into itself. If no such $\Delta$ exists, $A$ is said to
be irreducible.

This is always the case when $G$ is disconnected. If $G^{\prime}$ is a
connected component of $G$, then all $G$-endomorphisms $A$ are reducible with
respect to $E(G^{\prime})$.

Given $\Delta\subseteq E(G)$, we denote its complement by $\Delta^{c}$ and by
$G[\Delta]$ the subgraph of $G$ induced by $\Delta$.

######  4.9 Proposition.

Let $A$ be a $G$-endomorphism. If $A$ is reducible with respect to
$\Delta\subsetneq E(G)$, then the spectrum of $D_{\Gamma(A)}$ is given by

$\sigma(D_{\Gamma(A)})=\sigma(D_{\Gamma(A_{1})}^{1})\cup\sigma(D_{\Gamma(A_{2})}^{2}),$

where $A_{1}$ is the restriction of $A$ to $\mathbb{C}^{\Delta}$ and $A_{2}$
is the restriction of $A$ to $\mathbb{C}^{\Delta^{c}}$. The operators $D^{1}$
and $D^{2}$ are the Dirac operators on $G[\Delta]$ and $G[\Delta^{c}]$,
respectively.

###### Proof.

Enumerate the edges $e_{1},...,e_{n}$ of $G$ such that
$\\{e_{1},...,e_{k}\\}=\Delta$. Then, the transformation matrix of $A$ with
respect to this basis is of the form

$\left(\begin{array}[]{c c}A_{1}&C\\\ 0&A_{2}\\\ \end{array}\right),$

where $A_{1}$ and $A_{2}$ are square matrices. The matrix $A_{1}$ represents
the restriction of $A$ to $\mathbb{C}^{\Delta}$ and $A_{2}$ represents $A$
restricted to $\mathbb{C}^{\Delta^{c}}$. These matrices give boundary
conditions on $G[\Delta]$ and $G[\Delta^{c}]$, respectively. Denote the
induced length function on $G[\Delta]$ and $G[\Delta^{c}]$ by $l_{1}$ and
$l_{2}$, respectively. We then have

$\displaystyle P_{A,l}(\lambda)$ $\displaystyle=\det\left(\begin{array}[]{c
c}\operatorname{diag}(\exp(i\lambda l_{1}))-A_{1}&-C\\\
0&\operatorname{diag}(\exp(i\lambda l_{2}))-A_{2}\\\ \end{array}\right)$
$\displaystyle=P_{A_{1},l_{1}}(\lambda)\cdot P_{A_{2},l_{2}}(\lambda).$

Therefore, $P_{A,l}(\lambda)$ is zero if either $P_{A_{1},l_{1}}(\lambda)$ or
$P_{A_{2},l_{2}}(\lambda)$ is zero and, hence,

$\sigma(D_{A})=\sigma(D_{\Gamma(A_{1})}^{1})\cup\sigma(D_{\Gamma(A_{2})}^{2}).$

∎

######  4.10 Example.

Let $C_{n}$ be the directed cycle with $n$ edges and let $A$ be a unitary
$C_{n}$-endomorphism. Enumerating the edges $e_{1},...,e_{n}$ in cyclic order,
it is easily seen that there exists $\varphi_{1},...,\varphi_{n}\in[0,2\pi)$
such that the transformation matrix with respect to this basis is of the form

$A=\left(\begin{array}[]{ l l l l }0&&&e^{i\varphi_{n}}\\\
e^{i\varphi_{1}}&0&&\\\ &&\ddots&\\\
&&e^{i\varphi_{n-1}}&0\end{array}\right).$

By removing all vertices but one, according to Lemma 4.5, the multi-
dimensional characteristic polynomial is of the form

$\displaystyle P_{A}(x_{1},...,x_{n})$ $\displaystyle=x_{1}\cdot...\cdot
x_{n}-\exp(i\varphi_{1})\cdot...\cdot\exp(i\varphi_{n})$
$\displaystyle=\prod_{i=1}^{n}x_{i}-\exp\left(i\sum_{i=1}^{n}\varphi_{i}\right).$

Hence, the characteristic function is given by

$\displaystyle
P_{A,l}(\lambda)=\exp\left(i\lambda\sum_{j=1}^{n}l_{j}\right)-\exp\left(i\sum_{j=1}^{n}\varphi_{j}\right).$

This implies that the spectrum of the canonical Dirac operator with respect to
the boundary condition $\Gamma(A)$ is given by

$\lambda_{k}=\frac{1}{L}\left(\sum_{j=1}^{n}\varphi_{j}+2\pi k\right)\text{
for }k\in\mathbb{Z},$ (2)

where $L=\sum_{j=1}^{n}l_{j}$. By deleting the last column of
$\operatorname{diag}(e^{i\lambda_{k}l})-A$, we obtain a matrix of the form

$\tilde{A}_{k}=\left(\begin{array}[]{c c c c}e^{i\lambda_{k}l_{1}}&&&\\\
-e^{i\varphi_{1}}&e^{i\lambda_{k}l_{2}}&&\\\ &-e^{i\varphi_{2}}&\ddots&\\\
&&&e^{i\lambda_{k}l_{n-1}}\\\ &&&-e^{i\varphi_{n-1}}\end{array}\right).$

Clearly, $\tilde{A}_{k}$ has rank $n-1$. Thus, the kernel of
$\operatorname{diag}(e^{i\lambda_{k}l})-A$ can only be one-dimensional, which
implies that the multiplicity of $\lambda_{k}$ is one.

##  5 Boundary conditions

###  5.1 Decompositions of Eulerian Digraphs

Recall that a directed walk is an alternating sequence of edges

$W:=e_{1},e_{2},\cdots,e_{k}$

where $\partial_{+}e_{i-1}=\partial_{-}e_{i}$. Denote by $E(W)$ the set of
edges appearing in $W$. A directed walk is said to be closed if
$\partial_{+}e_{k}=\partial_{-}e_{0}$. A trail is a walk in which all edges
are distinct. A closed directed trail that does not pass a vertex twice,
except for $\partial_{-}e_{0}$, is called a cycle. A cycle/trail decomposition
of $G$ is a family

$S=\\{C_{1},...,C_{m}\\}$

of cycles/trails such that every edge of $G$ appears in a unique cycle/trail
of $S$.

######  5.1 Definition.

Let $G$ be a digraph. We call a bijective map $P:E(G)\rightarrow E(G)$ a
permutation of the edges of $G$, the set of permutations of its edges are
denoted by $\mathfrak{S}(E(G))$. If $P$ satisfies that $P(e)=e^{\prime}$
implies $\partial_{+}e=\partial_{-}e^{\prime}$, then $P$ is called a
$G$-permutation. We denote the set of all $G$-permutations by
$\mathfrak{S}(G)$.

######  Remark.

We have $\mathfrak{S}(G)\subseteq\mathfrak{S}(E(G))$. By enumerating $E(G)$,
we assign to every permutation $P\in\mathfrak{S}(E(G))$ a corresponding
element in the symmetric group $\mathfrak{S}_{n}$, where $n$ is the amount of
edges of $G$.

######  5.2 Lemma.

A permutation $P\in\mathfrak{S}(G)$ of $G$ induces for each vertex $v$ a
bijection $P_{v}$ from the ingoing edges of $v$ to the outgoing edges of $v$.
In particular, $\mathfrak{S}(G)$ is empty if $G$ is not a Eulerian digraph.

###### Proof.

Fix $v\in V(G)$. Let $e$ be an ingoing vertex at $v$. By the definition of
$G$-permutations, $P(e)$ is then an outgoing vertex of $v$. Therefore, $P_{v}$
is well-defined. Injectivity of $P$ implies injectivity of $P_{v}$ and, since
$P$ is surjective, for every outgoing edge $e^{\prime}$ at $v$, there exists
an edge $e$ of $G$ mapped by $P$ onto $e^{\prime}$. This implies that the head
of $e$ is the tail of $e^{\prime}$. Therefore, $e$ is an ingoing edge of $v$
and $P_{v}$ maps $e$ onto $e^{\prime}$, which proves that $P_{v}$ is
bijective. ∎

It is clear that every $G$-permutation $P\in\mathfrak{S}(G)$ induces a unitary
$G$-endomorphism, and hence, a local self adjoint boundary condition. We will
now investigate the spectrum of the Dirac operator subject to such a boundary
condition.

To this end, recall the following facts concerning permutations: for every
permutation $\pi\in\mathfrak{S}_{n}$ and $x\in\\{1,...,n\\}$ there exists a
$k\in\mathbb{N}$ such that $\pi^{k}(x)=x$. If $k$ is the smallest such
integer, then $x,\pi(x),\pi^{2}(x),...,\pi^{k-1}(x)$ is said to be a $k$-cycle
in $\pi$. Every permutation can be decomposed into a disjoint union of its
cycles.

######  5.3 Theorem.

Let $G$ be a Eulerian digraph. Every decomposition of the digraph into
directed closed trails corresponds to a $G$-permutation $P$ and vice versa.
Each trail of length $k$ then corresponds to a $k$-cycle of $P$, i.e. the
trail containing the edge $e$ is given by

$e,P(e),P^{2}(e),...,P^{k-1}(e).$

###### Proof.

Given a decomposition of the digraph into closed directed trails, define a map
$P:E(G)\rightarrow E(G)$ by $P(e)=e^{\prime}$, where $e^{\prime}$ is the edge
that comes after $e$ in the closed trail containing $e$. In order to show that
$P$ is a permutation, it remains to be shown that it is injective. Hence,
assume that

$P(e)=e^{\prime}=P(\tilde{e})$

and, therefore, there is a trail $C$ that contains $e$ and a trail $\tilde{C}$
that contains $\tilde{e}$ such that $e^{\prime}$ is the subsequent edge in
both trails. Hence, $C$ and $\tilde{C}$ both contain $e^{\prime}$ and, since
the decomposition demands the trails be disjoint, we get $C=\tilde{C}$. A
trail cannot contain an edge twice and, therefore, $e$ is equal to
$\tilde{e}$. Consequently, injectivity of $P$ follows.

Now, let $P$ be a $G$-permutation. For an edge $e$, define a directed walk

$T(e)=e,P(e),P^{2}(e),...,P^{k-1}(e),$ ($\heartsuit$)

where $k$ is the minimum number such that $P^{k}(e)=e$. The fact that $P$ is a
permutation of the set of edges of $G$ ensures that such a $k$ exists. It is,
indeed, a directed walk since, by definition of $P$, the head of $P^{i}(e)$ is
the tail of $P^{i+1}(e)$. It is closed, since the head of $P^{k-1}(e)$ is the
tail of $P^{k}(e)=e$. It remains to be shown that it is a trail, i.e. that
there exists no $l<j$ in $\\{0,...,k-1\\}$ such that $P^{l}(e)=P^{j}(e)$. This
would imply $P^{j-l}(e)=e$, which would contradict the definition of $k$,
since $j-l<k$.

Hence, equation ($\heartsuit$ ‣ 5.1) defines for every edge a directed closed
trail that contains this edge. To show that these trails are a decomposition
of the digraph, it remains to be proven that two distinct trails do not share
any edges. So, let

$\displaystyle T_{1}$ $\displaystyle=e,P(e),P^{2}(e),...,P^{k_{1}}(e)$
$\displaystyle T_{2}$
$\displaystyle=e^{\prime},P(e^{\prime}),P^{2}(e^{\prime}),...,P^{k_{2}}(e^{\prime})$

be two trails that share an edge, i.e. $P^{m_{1}}(e)=P^{m_{2}}(e^{\prime})$
for some $1\leq m_{i}\leq k_{i}$. W.l.o.g., let $m_{1}\geq m_{2}$. We then
arrive at $P^{m_{1}-m_{2}}(e)=e^{\prime}$. Applying $P^{k_{1}}$, which
commutes with $P^{m_{1}-m_{2}}$, to both sides of this equation, we see that

$P^{m_{1}-m_{2}}(e)=P^{k_{1}}(e^{\prime}).$

Therefore, $P^{k_{1}}(e^{\prime})$ is equal to $e^{\prime}$, which implies
that $k_{1}\geq k_{2}$. The inequality $k_{2}\geq k_{1}$ follows analogously,
which shows that $k_{1}=k_{2}$. Therefore, $P^{m_{1}-m_{2}}$ gives a bijection
between the edges of $T_{1}$ and $T_{2}$. Therefore, they are the same trail.

It is clear that these constructions are inverse to each other and, hence,
this correspondence is one to one. ∎

######  5.4 Proposition.

Let $P$ be a $G$-permutation. Then, the trace of $P$ is equal to the number of
loops in the decomposition of $G$ that corresponds to $P$.

###### Proof.

The trace of $P$ is equal to

$\operatorname{tr}P=\sum_{e\in E(G)}\langle e,P(e)\rangle$

and further

$\langle e,P(e)\rangle=\begin{cases}1\quad\text{if }P(e)=e\\\
0\quad\text{else}\end{cases}$

Hence, the trace of $P$ is equal to the number of edges such that $P(e)=e$.
For this to hold, $e$ must be a loop, and furthermore by the proof of Theorem
5.3, it is the closed trail containing $e$. ∎

Given a closed trail $T=e_{1},...,e_{k}$, let its length by

$L_{T}=\sum_{i=1}^{k}l_{e_{i}}.$

######  5.5 Lemma.

Let $P$ be a $G$-permutation. Then, for each closed trail $T$ in the
decomposition defined by $P$, $P$ is reducible with respect to $E(T)$.

###### Proof.

Let $T$ be a closed trail in the decomposition defined by $P$ and let $e$ be
an edge that appears in $T$. Then, by definition of $T$, $P(e)$ is again an
edge that appears in $T$, which shows that $P$ is reducible with respect to
$E(T)$. ∎

We say that $\alpha\in\mathbb{R}$ is divisible by $\beta\in\mathbb{R}$ if
there exists a $k\in\mathbb{Z}$ such that $\alpha=k\cdot\beta$.

######  5.6 Theorem.

Let $G$ be a Eulerian digraph and let $P$ be a linear $G$-permutation. If
$T_{1},...,T_{m}$ are the closed trails of the decomposition defined by $P$,
then the spectrum of $D_{\Gamma(P)}$ is given by

$\lambda_{k,i}=\frac{2\pi k}{L_{i}}\text{ with }i\in\\{1,...,m\\}\text{,
}k\in\mathbb{Z},$

where $L_{j}$ is the length of $T_{j}$. The multiplicity $m(\lambda_{k,i})$
is, for $k\neq 0$, equal to the amount of cycles whose length is divisible by
$L_{i}/k$. Furthermore, $m(0)$ is equal to the total amount of closed trails
in the decomposition defined by $P$.

######  Remark.

If we choose all edges to have unit length, then $L_{j}$ is the actual amount
of edges appearing in the closed trail $T_{j}$.

###### Proof.

By Lemma 5.5, $P$ is reducible with respect to each $T_{i}$ and, hence, by
Proposition 4.9, we have that

$\sigma(D_{\Gamma(P)})=\bigcup_{i=1}^{n}\sigma(D_{\Gamma(P_{i})}),$

where $P_{i}$ is the restriction of $P$ to $E(T_{i})$. Hence we can assume
that we have only one trail $T$.

Enumerate the edges of $T$ in such a way that $P(e_{i})=e_{i+1\mod L_{T}}$.
The transformation matrix of $P$ with respect to the basis
$e_{0},...,e_{L_{T}-1}$ is equal to

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

As in Example 4.10, the spectrum of $P$ can be easily calculated to be

$\sigma(D_{\Gamma(P)})=\left\\{\frac{2\pi k}{L}\mid k\in\mathbb{Z}\right\\},$

with each eigenvalue having multiplicity one. ∎

######  5.7 Corollary.

Let $P$ be a $G$-permutation. Let $\lambda_{0}$ be the smallest positive
eigenvalue of $D_{\Gamma(P)}$. Then,

$L=\frac{2\pi}{\lambda_{0}}$

is the length of the longest cycle in the decomposition associated with $P$.
The multiplicity of $\lambda$ is equal to the amount of cycles of length $L$.

###### Proof.

Let $\lambda_{0}$ be the smallest positive eigenvalue of $D_{\Gamma(P)}$. By
Theorem 5.6, it is of the form

$\lambda_{0}=\frac{2\pi k}{L},$

where $k$ is an integer and $L$ is the length of a closed trail appearing in
the decomposition defined by $P$. In order for $\lambda_{0}$ to be the
smallest positive eigenvalue, $k$ has to be one and $L$ must be the maximum of
the lengths of the closed trails. ∎

###  5.2 The directed adjacency matrix

As we have seen, the spectrum of the Dirac operator is closely tied to the
boundary condition it is subjected to. Boundary conditions involve choices
which are a priori not canonical. In order to obtain a theory that ties the
spectrum of the Dirac operator to properties of the underlying graph, we need
to come up with a canonical boundary condition. By Proposition 4.2, this
boundary condition will not be self adjoint. However, canonical matrices on
graphs are given by directed adjacency matrices:

######  5.8 Definition.

The directed adjacency matrix $\mathcal{A}(G)$ of a digraph $G$ is given by

$\displaystyle\mathcal{A}(G)$ $\displaystyle=\sum_{e,e^{\prime}\in
E}I_{e,e^{\prime}}e\otimes(e^{\prime})^{\ast}\in\mathbb{C}^{G}\otimes(\mathbb{C}^{G})^{\ast}=\mathrm{End}(\mathbb{C}^{G}),$
$\displaystyle I_{e,e^{\prime}}$
$\displaystyle=\left\\{\begin{subarray}{c}1\quad\text{if
}\partial_{+}e^{\prime}=\partial_{-}e\\\
0\quad\text{otherwise}\end{subarray}\right.$

######  5.9 Lemma.

The directed adjacency matrix $\mathcal{A}(G)$ is a $G$-endomorphism.

###### Proof.

Let $v\in V$ be a vertex of $G$ and $e^{\prime}$ be an edge in
$\mathbb{C}_{+}(G,v)$. Therefore, $\partial_{+}e^{\prime}=v$, and

$\mathcal{A}(G)e^{\prime}=\sum_{e\in
E(G)}I_{e,e^{\prime}}e=\sum_{\begin{subarray}{c}e\\\
\partial_{-}e=v\end{subarray}}e\in\mathbb{C}_{-}(G,v),$

which proves the lemma, since $\mathbb{C}_{+}(G,v)$ is spanned by
$\\{e^{\prime}\mid\partial_{+}e^{\prime}=v\\}$. ∎

Lemma 5.9 shows that the adjacency matrix defines a boundary condition for the
Dirac operator. We denote the Dirac operator subject to the boundary condition
$\Gamma(\mathcal{A}(G))$ by $D_{G}$. As we will see, the spectrum of $D_{G}$
highly depends on the directed cycles present in $G$. We use the notation
$G^{\prime}\subseteq G$ to say that $G^{\prime}$ is a subgraph of $G$ with no
isolated vertices.

######  5.10 Definition.

A disjoint collection of cycles is a digraph $C$, whose connected components
consist of directed cycles. The size $\alpha(C)$ of $C$ is the amount of
connected components, the total length $\eta(C)$ of $C$ is the amount of edges
of $C$. For a digraph $G$, define

$\mathcal{C}(G):=\\{C\subseteq G\mid C\text{ is a disjoint collection of
cycles}\\}.$

######  Remark.

The empty subgraph $\varnothing$ with no vertices and edges is always an
element of $\mathcal{C}(G)$. Its size and length equal zero.

The following lemma gives a characterization of disjoint collections of
cycles:

######  5.11 Lemma.

If $G$ is a digraph such that for every vertex $v\in V(G)$ the in-degree
$id(v)$ and the out-degree $od(v)$ are both equal to one, then $G$ is a
disjoint collection of cycles.

###### Proof.

It is easily checked that, in this case, $\mathcal{A}(G)$ is a
$G$-permutation. By Theorem 5.3, the directed adjacency matrix defines a
decomposition $S$ of $G$ into directed trails. However, if a trail in $S$
passes a vertex twice or two distinct trails intersect at a vertex, then the
in- and out-degrees of the vertex would be greater than one, which would
contradict the assumption. Consequently, $G$ is a disjoint collection of
cycles. ∎

######  5.12 Proposition.

The directed adjacency matrix $\mathcal{A}(G)$ of $G$ is non-singular if and
only if $G$ is a disjoint collection of directed cycles. In this case, the
determinant of $\mathcal{A}(G)$ is given by the formula

$\det\mathcal{A}(G)=(-1)^{\alpha(G)-\eta(G)}.$

###### Proof.

Let $v$ be a vertex of $G$. If the in-degree/out-degree of $v$ is equal to
zero, then the out-degree/in-degree must be unequal zero as $G$ has no
isolated vertices. Then, for every edge $e$ starting/ending in $v$, the
row/column of $\mathcal{A}(G)$ that corresponds to $e$ is equal to zero, which
implies that $\mathcal{A}(G)$ is singular. Therefore, in order for
$\mathcal{A}(G)$ to be non-singular, the in-degree and the out-degree of every
vertex of $G$ must be greater or equal to one.

Now, assume that the in-degree/out-degree of a vertex $v$ is greater than or
equal to two and let $e_{1}$ and $e_{2}$ be two edges ending/starting in $v$.
Then, the columns/rows of $\mathcal{A}(G)$ that correspond to $e_{1}$ and
$e_{2}$ are equal, which implies that $\mathcal{A}(G)$ is singular.
Consequently, $\mathcal{A}(G)$ can only be non-singular if the in-degree and
the out-degree of all vertices are equal to one.

Lemma 5.11 implies that $G$ is a disjoint collection of cycles and
$\mathcal{A}(G)$ is a $G$-permutation, where each cycle of $G$ corresponds to
a cycle of $\mathcal{A}(G)$ of the same length. Writing $G$ as the disjoint
union of cycles

$G=C_{k_{1}}\sqcup...\sqcup C_{k_{s}},$

where $\alpha(G)=s$ and $\eta(G)=k_{1}+...+k_{s}$, it follows that
$\mathcal{A}(G)$ is the product of cycles of length $k_{1},...,k_{s}$. Since
the signature of a cycle of length $k$ is given by $(-1)^{k-1}$, the signature
$\operatorname{sgn}(\mathcal{A}(G))$ of $\mathcal{A}(G)$ is given by $-1$ to
the power of

$\sum_{i=1}^{s}k_{i}-1=\eta(G)-\alpha(G).$

The determinant of a permutation matrix is equal to the signature of the
underlying permutation, which implies that

$\det\mathcal{A}(G)=\operatorname{sgn}(\mathcal{A}(G))=(-1)^{\eta(G)-\alpha(G)}=(-1)^{\alpha(G)-\eta(G)},$

and proves the proposition. ∎

For a subgraph $H$ of $G$, define a monomial in the polynomial ring over the
variables $\\{x_{e}\mid e\in E(G)\\}$ by

$x^{H}:=\prod_{e\not\in E(H)}x_{e}.$

It seems counter-intuitive to multiply over the edges that are not contained
in $E(H)$, however, it is the most convenient notation for the next theorem:

######  5.13 Theorem.

The multi-dimensional characteristic polynomial $P_{\mathcal{A}(G)}$ of the
directed adjacency matrix $\mathcal{A}(G)$ is given by

$P_{\mathcal{A}(G)}(x)=\sum_{C\in\mathcal{C}(G)}(-1)^{\alpha(C)}x^{C}.$ (3)

###### Proof.

First, assume that $G$ has no loops. The multi-dimensional characteristic
polynomial is given by

$\displaystyle P_{\mathcal{A}(G)}(x)$
$\displaystyle=\det(\operatorname{diag}(x)-\mathcal{A}(G))$
$\displaystyle=\sum_{\sigma\in\mathfrak{S}(E(G))}\operatorname{sgn}(\sigma)\prod_{e\in
E(G)}(\operatorname{diag}(x)-\mathcal{A}(G))_{\sigma(e),e}.$

For a subgraph $H\subseteq G$, let $\mathfrak{S}_{H}$ be the subset of
$\mathfrak{S}(E(G))$, which consists of all permutation whose fixed point set
is equal to $E(G)\setminus E(H)$. We can regard $\mathfrak{S}_{H}$ as the
subset of $\mathfrak{S}(E(H))$ of permutations without fixed points. We can
rewrite $P_{\mathcal{A}(G)}$ as

$P_{\mathcal{A}(G)}(x)=\sum_{H\subseteq G}\prod_{e\notin
E(H)}(x_{e}-I_{e,e})\sum_{\sigma\in\mathfrak{S}_{H}}\operatorname{sgn}(\sigma)\prod_{e\in
E(H)}(-I_{\sigma(e),e}),$

where we sum over all induced subgraphs of $G$. Since $G$ has no loops,
$I_{e,e}$ is always zero, which simplifies the above formula to

$P_{\mathcal{A}(G)}(x)=\sum_{H\subseteq
G}(-1)^{|E(H)|}x^{H}\sum_{\sigma\in\mathfrak{S}_{H}}\operatorname{sgn}(\sigma)\prod_{e\in
E(H)}\mathcal{A}(G)_{\sigma(e),e}.$

Moreover, whenever a permutation $\sigma\in\mathfrak{S}(E(H))$ has a fixed
point, the product $\prod\limits_{e\in E(H)}\mathcal{A}(G)_{\sigma(e),e}$ is
equal to zero. Therefore, we can sum over all $\sigma\in\mathfrak{S}(E(H))$
instead of $\mathfrak{S}_{H}$. Further, the restriction of $\mathcal{A}(G)$ to
the edges of $H$ gives us the directed adjacency matrix of $H$, i.e.

$I(H)=\sum_{e,e^{\prime}\in E(H)}I_{e,e^{\prime}}e\otimes e^{\prime}.$

Altogether, this implies that

$P_{\mathcal{A}(G)}=\sum_{H\subseteq G}(-1)^{|E(H)|}x^{H}\det I(H).$

Using Proposition 5.12, the multi-dimensional characteristic polynomial takes
the form

$P_{\mathcal{A}(G)}=\sum_{C\in\mathcal{C}(G)}(-1)^{\eta(C)}x^{C}(-1)^{\alpha(C)-\eta(C)}=\sum_{C\in\mathcal{C}(G)}(-1)^{\alpha(C)}x^{C},$

which proves the theorem for the case in which $G$ has no loops.

Now, assume that $G$ has exactly one loop $e$. Split the loop into two edges
$e_{1},e_{2}$ by adding a vertex $v$ to the loop to obtain a loopless graph
$H$, see Figure 1. We want to use Lemma 4.5: note that the graph $\tilde{H}$
obtained by removing $v$ is equal to $G$ and, moreover, the reduction of
$I(H)$ to $G$ is equal to the directed adjacency matrix of $G$. We therefore
have that

$P_{\mathcal{A}(G)}(x_{e},x_{3},...,x_{n})=P_{I(H)}(x_{e},1,x_{3},...,x_{n})=\sum_{\hat{C}\in\mathcal{C}(H)}(-1)^{\alpha(\hat{C})}(x_{e},1,x_{3},...,x_{n})^{\hat{C}}.$

By replacing the cycle $e_{1},e_{2}$ with $e$, it is clear that every
collection of disjoint cycles $\hat{C}\in\mathcal{C}(H)$ corresponds to a
unique collection $C\in\mathcal{C}(G)$ of same size such that $e_{1},e_{2}$ is
a cycle in $\hat{C}$ if and only if $e$ is a cycle in $C$.

Figure 1: Adding a vertex $v$ to a loop $e$.

Then, the monomial $(x_{e},x_{3},...,x_{n})^{C}$ is equal to
$(x_{e},1,x_{3},...,x_{n})^{\hat{C}}$ and, consequently, we conclude that

$\displaystyle P_{\mathcal{A}(G)}(x_{e},x_{3},...,x_{n})$
$\displaystyle=\sum_{\hat{C}\in\mathcal{C}(H)}(-1)^{\alpha(\hat{C})}(x_{e},1,x_{3},...,x_{n})^{\hat{C}}$
$\displaystyle=\sum_{C\in\mathcal{C}(G)}(-1)^{\alpha(C)}(x_{e},x_{3},...,x_{n})^{C}.$

If $G$ has multiple loops, by repeating this argument inductively, one can
prove the theorem for the most general case. ∎

We continue by examining the consequences of formula (3) for the spectrum of
$D_{G}$. Unfortunately, a complete characterization of $\sigma(D_{G})$ cannot
be given. However, it only depends on the structure of $\mathcal{C}(G)$ and
the lengths of the cycles present in $G$. The total length of a subgraph $H$
of $G$ is given by the sum of the lengths of the edges of $H$, i.e.

$L_{H}=\sum_{e\in E(H)}l_{e}.$

######  5.14 Corollary.

The characteristic function $P_{\mathcal{A}(G),l}$ of the directed adjacency
matrix is given by

$P_{\mathcal{A}(G),l}(\lambda)=\sum_{C\in\mathcal{C}(G)}(-1)^{\alpha(C)}\exp(i\lambda(L_{G}-L_{C})).$

The spectrum of $D_{G}$ is given by the solutions to the equation

$\sum_{C\in\mathcal{C}(G)}(-1)^{\alpha(C)}\exp(-i\lambda L_{C})=0.$

###### Proof.

The first statement follows from a short calculation that uses formula (3):

$\displaystyle P_{\mathcal{A}(G),l}(\lambda)$
$\displaystyle=\sum_{C\in\mathcal{C}(G)}(-1)^{\alpha(C)}\prod_{e\notin
E(C)}\exp(i\lambda l_{e})$
$\displaystyle=\sum_{C\in\mathcal{C}(G)}(-1)^{\alpha(C)}\exp(i\lambda(L_{G}-L_{C})).$

The second statement then follows by multiplying the equation
$P_{\mathcal{A}(G),l}(\lambda)=0$ by $\exp(-i\lambda L_{G})$. ∎

If all edges have length $1$ the characteristic function of the directed
adjacency matrix is determined by the characteristic polynomial
$p_{\mathcal{A}(G)}$ of $\mathcal{A}(G)$ by

$P_{\mathcal{A}(G),1}(\lambda)=p_{\mathcal{A}(G)}(e^{i\lambda})$

and we can obtain the characteristic polynomial from the multi-dimensional
characteristic polynomial by

$p_{\mathcal{A}(G)}(t)=P_{\mathcal{A}(G)}(t,...,t).$

This is a well-known object in spectral graph theory (see e.g. [16]), we will
prove a few basic facts to illustrate the connection of the characteristic
polynomial and hence the spectrum of the Dirac operator to the topology of the
graph.

######  5.15 Corollary.

Let $G$ be a digraph with $n$ edges. The characteristic polynomial
$p_{\mathcal{A}(G)}$ of the directed adjacency matrix is given by

$p_{\mathcal{A}(G)}(t)=\sum_{C\in\mathcal{C}(G)}(-1)^{\alpha(C)}t^{n-\eta(C)}.$

###### Proof.

The corollary follows directly from formula (3). ∎

By expressing the characteristic polynomial in the usual form

$p_{\mathcal{A}(G)}(t)=\sum_{k=0}^{n}a_{k}t^{k},$

Corollary 5.15 implies that the $k$-th coefficient of $p_{\mathcal{A}(G)}(t)$
is given by

$a_{k}=\sum_{\begin{subarray}{c}C\in\mathcal{C}(G)\\\
\eta(C)=n-k\end{subarray}}(-1)^{\alpha(C)}.$

Recall that the girth $g(G)$ is the length of the shortest directed cycle in
$G$ and that the edge-connectivity of $G$ is equal to $k$ if $k$ is the least
number of edges that have to be removed such that the remaining graph is
disconnected or consists of an isolated vertex. In this case, we say that $G$
is $k$-connected.

######  5.16 Proposition.

Let $G$ be a digraph with $n$ edges that contains at least one cycle. The
girth of $G$ is given by

$g(G)=\min\\{l\in\\{1,...,n\\}\mid a_{n-l}\neq 0\\}.$

Moreover, $-a_{n-l}$ is equal to the number of cycles of length $l$ in $G$ for
$0\leq l<2g(G)$. Furthermore, if $G$ is $k$-connected, then, for $0\leq l<k$,
the coefficient $a_{l}$ is the negative of the amount of cycles of length
$n-l$ in $G$.

###### Proof.

Let $l<g(G)$ and assume that $a_{n-l}$ is not equal to zero. Then, there
exists a collection of disjoint cycles $C\in\mathcal{C}(G)$ of length $l$.
Consequently, $C$ contains a cycle whose length is less than $g(G)$, which is
a contradiction. Therefore, $a_{n-l}$ must be zero.

If a disjoint collection of cycles $C\in\mathcal{C}(G)$ is of length $l$,
where $l$ satisfies $0\leq l<2g(G)$, then the size of $C$ must be equal to
one, otherwise it would contain a cycle of length smaller than $g(G)$.
Consequently,

$a_{n-l}=\sum_{\begin{subarray}{c}C\in\mathcal{C}(G)\\\
\eta(C)=l\end{subarray}}-1=-\\#\\{\text{cycles of length }l\\}.$

Now, let $G$ be $k$-connected and let $0\leq l<k$. If $C\in\mathcal{C}(G)$ is
of length $n-l$, then $C$ cannot be disconnected, since only $l$ edges have
been removed from $G$ in order to obtain $C$. Therefore, $C$ is a cycle and

$a_{l}=\sum_{\begin{subarray}{c}C\in\mathcal{C}(G)\\\
\eta(C)=n-l\end{subarray}}-1=-\\#\\{\text{cycles of length }n-l\\}.$

∎

We now characterize some high-order coefficients of the characteristic
polynomial.

######  5.17 Corollary.

Let $G$ be a graph with $n$ edges. For the following coefficients of
$p_{\mathcal{A}(G)}$, the following holds:

  * •

$a_{n}=1$

  * •

$a_{n-1}=-\\#\\{\text{loops in }G\\}$

  * •

$a_{n-2}=-\\#\\{2\text{-cycles}\\}+\\#\\{\text{disjoint pairs of loops}\\}$

  * •

$a_{n-3}=-\\#\\{3\text{-cycles}\\}+\\#\\{\text{disjoint pairs of loops and
}2\text{-cycles}\\}\\\ -\\#\\{\text{disjoint triples of loops}\\}$

###### Proof.

This follows directly from the above considerations. ∎

######  5.18 Example.

To conclude this chapter, we give some examples of characteristic polynomials
of graphs:

  * •

The characteristic polynomial of the $n$-rose $R_{n}$ is given by
$p_{\mathcal{A}(R_{n})}=t^{n}-nt^{n-1}$.

  * •

The characteristic polynomial of the $n$-cycle $C_{n}$ is given by
$p_{\mathcal{A}(C_{n})}=t^{n}-1$.

  * •

Let $G_{1}$ be the graph given in Figure 2. The characteristic polynomial of
$G_{1}$ is given by $p_{\mathcal{A}(G_{1})}=t^{4}-2t^{3}$. The reason that the
second-order coefficient is equal to zero is due to the fact that the cycle of
length $2$ in the middle cancels out the pair of peripheric loops.

Figure 2: The graph $G_{1}$

  * •

Let $G_{2}$ be the graph given in Figure 3. The characteristic polynomial of
$G_{2}$ is given by $p_{\mathcal{A}(G_{2})}=t^{4}-2t^{3}$ and, therefore, is
equal to the characteristic polynomial of $G_{1}$.

Figure 3: The graph $G_{2}$

  * •

Let $G_{3}$ be the graph given in Figure 4. The characteristic polynomial of
$G_{3}$ is given by $p_{\mathcal{A}(G_{3})}=t^{6}-3t^{4}-2t^{3}$, which, since
no two cycles of $G_{3}$ are disjoint, represents the cycles present in
$G_{3}$, i.e. we have three cycles of length $2$ and two cycles of length $3$.

Figure 4: The graph $G_{3}$

## References

  * [1] M. Atiyah, V. Patodi, and I. Singer.  Spectral asymmetry and riemannian geometry. i.  Math. Proc. Camb. Phil. Soc., 77:43–69, 1975.
  * [2] J. Bolte and J. Harrison.  Spectral statistics for the dirac operator on graphs.  J. Phys. A: Math. Gen., 36(2747), 2003.
  * [3] W. Bulla and T. Trenkler.  The free dirac operator on compact and noncompact graphs.  Journal of Mathematical Physics, 31(1157), 1990.
  * [4] C. Bär and W. Ballmann.  Boundary value problems for elliptic differential operators of first order.  Surveys in differential geometry, XVII:1–78, 2012.
  * [5] C. Bär and W. Ballmann.  Guide to elliptic boundary value problems for dirac-type operators.  In Arbeitstagung Bonn 2013, Progress in Mathematics, pages pp.43–80, Cham, 2016. Birkhäuser/Springer.
  * [6] C. Bär and L. Bandara.  Boundary value problems for general first-order elliptic differential operators.  Journal of Functional Analysis, 282(12):109445, Jun 2022.
  * [7] D. M. Cvetkovic, M. Doob, and H. Sachs.  Spectra of Graphs.  Academic Press, Inc., 1979.
  * [8] P. Exner and P. Šeba.  Free quantum motion on a branching graph.  Reports on Mathematical Physics, 28(1):7–26, 1989.
  * [9] S. Fulling, P. Kuchment, and J. Wilson.  Index theorems for quantum graphs.  J. Phys. A: Math. Theor., 40:14165–14180, 2007.
  * [10] M. Harmer.  Hermitian symplectic geometry and extension theory.  J. Phys. A: Math. Gen., 33:9193–9203, 2000.
  * [11] J. M. Harrison.  Quantum graphs with spin hamiltonians.  Proceedings of Symposia in Pure Mathematics, 77, 2008.
  * [12] V. Kostrykin and R. Schrader.  Kirchhoff’s rule for quantum wires.  J. Phys. A, 32:595–630, 1999.
  * [13] P. Kuchment.  Quantum graphs i. some basic structures.  In P. Kuchment, editor, Quantum graphs and their applications, a special issue of Waves in Random media, volume 14. 2014.
  * [14] Peter Kuchment.  Quantum graphs: an introduction and a brief survey.  arXiv preprint arXiv:0802.3442, 2008.
  * [15] O. Post.  First order approach and index theorems for discrete and metric graphs.  Ann. Henri Poincaré, 10:823–866, 2009.
  * [16] M. Rigo.  Advanced graph theory and combinatorics.  Computer Engineering Series. ISTE, London; John Wiley & Sons, Inc., Hoboken, NJ, 2016.  with a foreword by Vincent Blondel.