Adjacency, degrees, graph Laplacian, and spectral notation

PDF p. 6: Section 1.2; PDF p. 18: Section 3 opening

Let $G=(V,E)$ be a finite undirected graph with nonempty vertex set $V$, $n=\mathrm{\mid }V\mathrm{\mid }$, and at most one edge between each pair of vertices, allowing a self-loop at a vertex. Thus $E$ is a set of unordered pairs $\{x,y\}$ with $x,y\in V$; $x=y$ represents a self-loop. Its adjacency matrix $A=(A_{xy}{)}_{x,y\in V}$ has $A_{xy}=1$ when $\{x,y\}\in E$ and $A_{xy}=0$ otherwise. It is a symmetric matrix in $\{0,1{\}}^{n\times n}$ after an ordering of $V$.

The degree of $x$ is $d(x)={\sum }_{y\in V}{A}_{xy}$, so a self-loop contributes once. The degree matrix $D$ is diagonal with $D_{xx}=d(x)$, and the graph Laplacian is $L=D-A$. Put $d_{\min }={\min }_{x\in V}d(x)$ and $d_{\max }={\max }_{x\in V}d(x)$. The graph is $d$-regular when $d(x)=d$ for every $x\in V$.

An eigenvalue of $A$ is a scalar $\lambda$ for which $Af=\lambda f$ for some nonzero vector $f\in {\mathbb{C}}^V$. List the real eigenvalues with algebraic multiplicity in nonincreasing order as ${\lambda }_1(A)\ge \cdots \ge {\lambda }_n(A)$. Write $\mathbf{1}\in {\mathbb{C}}^V$ for the vector whose entries are all $1$, $J={\mathbf{11}}^{\mathrm{\top }}$ for the all-ones matrix, and $I$ for the identity matrix of the appropriate size.

Finite symmetric networks and loop removal

Finite vertex Hilbert space in the article convention

Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely

The unordered pair {x,y} and the singleton {x} = {x,x}

Algebraic multiplicity as the exponent of x-λ in χ_T, and geometric multiplicity as dim E_λ(T)

An endomorphism is diagonalisable if and only if its characteristic polynomial splits and every eigenvalue's geometric multiplicity equals its algebraic multiplicity

Given: A finite nonempty undirected graph with binary adjacency and possible self-loops, as specified above.

Goal: Verify that the degree, Laplacian, eigenvalue ordering and matrix notation are well defined.

1.1 By [F4], $\{x,y\}=\{y,x\}$, including $\{x,x\}=\{x\}$ for a loop, so $A_{xy}=A_{yx}$ and $A$ is a symmetric nonnegative binary matrix. Thus [F1] applies: each row sum is a finite degree, a diagonal entry contributes once, and $D-A$ is the corresponding network Laplacian. Since $V$ is finite and nonempty, its degrees have a minimum and maximum. The regularity condition is equality of these finite row sums to the specified number $d$. [given, F1, F4]

2.1 By [F2], $A$ acts on the finite-dimensional complex vertex space and is self-adjoint, hence normal. By [F3] it has an orthonormal eigenbasis. Each associated eigenvalue $\lambda$ is real: for a unit eigenvector $f$, the self-adjoint identity gives $⟨f,Af⟩=\overline{⟨f,Af⟩}$, while $⟨f,Af⟩=\lambda$. The eigenbasis diagonalizes $A$. In these coordinates, the equation $Af=\lambda f$ forces all coordinates with diagonal entry different from $\lambda$ to vanish; hence the eigenbasis vectors with diagonal entry $\lambda$ form a basis of its eigenspace. By [F5] and [F6], their number is the algebraic multiplicity of $\lambda$. Thus the $n$ diagonal entries give all eigenvalues counted with algebraic multiplicity, and this finite list of real numbers can be sorted nonincreasingly. The outer product ${\mathbf{11}}^{\mathrm{\top }}$ has every entry equal to $1$, and $I$ acts by leaving each vector unchanged. This establishes the notation. [F2, F3, F5, F6, step 1.1, algebra] ∎

The article's notation and its convention of counting a self-loop once are attributed to Expander graphs are globally synchronizing, Section 1.2 and the opening of Section 3. The justification above does not use the article as a proof.