Essay 1

In this essay we will talk about graphs and a way to represent them via matrices, we will then study some elementary properties of these matrices. We start our discussion off with some fundamental definitions for graph theory.

Graph

A graph is an ordered pair

G = (V, E)

of sets where

E \subseteq {{x, y} : x, y \in V, x \neq y}

We call $E$ the set of edges and $V$ the vertices, also note that edges don't have an order to them, as we know that ${x, y} = {y, x}$ , sometimes we want them to have a direction, and in that case we have this definition:

Directed Graph

A directed graph is an ordered pair

G = (V, E)

of sets where

E \subseteq {(x, y) : x, y \in V, x \neq y}

Throughout this entire discussion we will assume our graphs to be finite, unless otherwise stated.

When working graphs it's useful to talk about the way vertices are related to eachother, the first one we'll look at is when two vertices have an edge between them:

Neighboring Vertices

Given a graph

G = (V, E)

and

x, y \in V

then we say that

x, y

are neighbors if

{x, y} \in G

Set of Neighbors of a Vertex

Given a graph

G = (V, E)

and

x \in V

then we denote the set of neighbors of

x

nbs (x)

Degree of a Vertex

Given a graph

G = (V, E)

and

x \in V

then we denote degree of

x

\deg (x) = | nbs (x) |

With these defintions in place we can define matrices that encode a graph entirely:

Adjacency Matrix

Given a graph

G = (V, E)

then we denote the adjacency matrix of the graph

G

A_{G}

where

a_{i, j} = {\begin{matrix} 1 & if {i, j} \in E \\ 0 & otherwise \end{matrix}

Laplacian Matrix

Given a graph

G = (V, E)

then we denote the Laplacian matrix of the graph

G

L_{G}

where

l_{i, j} = {\begin{matrix} - 1 & if {i, j} \in E \\ \deg (i) & if i = j \\ 0 & otherwise \end{matrix}

Note that both the adjacency matrix and laplacian iterate through all possible pairs of vertices, that is to say that the shape of both these matrices is $| V | \times | V |$

Note that if we focus on a row we are looking at elements of the form $l_{i, \cdot}$ where $i$ is fixed, and therefore for the diagonal element of that row we store the degree of $i$ and for each other element in that row we cout each neighbor with a $- 1$ and therefore the sum of each row is zero.

A Vertex Incident to an Edge

Given a graph

G = (V, E)

and some

v \in V

then we say it is incident to an edge

{x, y}

v \in {x, y}

Walk

A walk on a graph is an alternating series of vertices and edges beginning and ending with a vertex such that each edge is incident with the vertex directly before it and and directly after it.

Note that when we have a walk between two vertices $u, v$ we call it it a $u - v$ walk, moreover a walk from $v - u$ is different . Now we can connect a few of the above ideas together

The Entries of the Power of an Adjacency Matrix Represent Walks

Given a graph

G = ({1, \dots, m}, E)

where

m \in ℕ_{1}

then given an entry

a_{i, j}

of the matrix

A_{G}^{n}

equals the number of

i - j

walks of length

n

We go by induction, so for $n = 1$ then the $n$ -th power is just the regular adjacency matrix, additionally each $a_{i, j}$ represents if there is an edge between the two vertices, which is the same as the number of walks from $i$ to $j$ of length $1$ .

Now suppose that the statement holds true for any $n \in ℕ_{1}$ then let's prove that it holds true for $n + 1$ . Since it holds true on $n$ then we know that $A_{G}^{n}$ has the desired property, but note that $A_{G}^{n + 1} = A_{G}^{n} A_{G}$ .

If we denote the elements of $A_{G}^{n + 1}$ by $a_{i, j}$ , those of $A_{G}^{n}$ by $b_{i, j}$ and those of $A_{G}$ by $c_{i, j}$ then by the definition of matrix multiplication $a_{i, j} = \sum_{k = 1}^{m} b_{i, k} c_{k, j}$ by our induction hypothesis we know that $b_{i, k}$ are the number of $i - k$ walks of length $n$ and by the regular definition of $A_{G}$ we know that $c_{k, j}$ represents whether or not there is a edge connecting $k, j$ , that is, the value is either $0$ or $1$ .

If $c_{k, j} = 1$ then we can take each possible path of length $n$ from $i - k$ and then extend the path to $j$ via the edge ${k, j}$ , note that all path from $i - j$ are of this form for some $k$ therfore $\sum_{k = 1}^{m} b_{i, k} c_{k, j}$ represents the total number of $i - j$ walks of length $n + 1$ as needed. Therefore the statement holds true by induction.

Laplacian of an Edge

Suppose

G = ({1, 2, \dots, m}, E)

and

{u, v} \in E

then we define the Laplacian for the edge

{u, v}

L_{G_{{u, v}}}

l_{i, j} = {\begin{matrix} 1 & if i = j \land i \in {u, v} \\ - 1 & if {i, j} = {u, v} \\ 0 & otherwise \end{matrix}

The above matrix is mostly zeros, but along a diagonal element of the matrix $l_{k, k}$ if $k$ is part of the edge, then it is a $1$ and there will be exactly two cases where $l_{i, j} = - 1$ based on the definition.

The Laplacian Is the Sum of Edge Laplacians

L_{G} = \sum_{{u, v} \in E} L_{G_{{u, v}}}

TODO: Add the proof here.

Quadratic Form of the Edge Laplacian Is a Squared Difference

For any

x \in ℝ^{n}

we have

x^{T} L_{G_{{u, v}}} x = {(x_{u} - x_{v})}^{2}

TODO: Add the proof here.

Positive Semi-definite

Given an

n \times n

matrix

M

then it is positive-semidefinite if for any

x \in ℝ^{n}

we have

x^{T} M x \geq 0

The Laplacian Is Positive-semidefinite

As per title.

TODO: Add the proof here.

Every Eigenvalue of the Laplacian Is Non-negative

As per title.

Suppose that $λ$ is an eigen value, and $x \in ℝ^{n}$ an eigenvector for $λ$ (non-zero). We already know that $x^{T} L_{G} x \geq 0$ , but also note $x^{T} L_{G} x = x^{T} (λ x) = λ x^{T} x$

Since $x \neq 0$ then we have $x^{T} x > 0$ , therefore we must have that $γ \geq 0$ , as needed.

By the real spectral theorem we deduce now that $L_{G}$ has an orthonormal basis consisting of eigen vectors of $L_{G}$ , in that case denote them as $0 \leq λ_{1} \leq λ_{2} \leq \dots \leq λ_{n}$

Path

A path is a non-empty graph

P = (V, E)

of the form

V = {v_{0}, v_{1}, \dots, v_{n}}

and

E = {{v_{0}, v_{1}}, {v_{1}, v_{2}}, \dots, {v_{n - 1}, v_{n}}}

where the vertices

v_{i}

are distinct.

In other-words a path is just a walk such that you don't go over the same vertex.

Connected

Given a non-empty graph

G

we say that it is connected if given any two vertices in

G

there is a path between them.

We'll now start our exploration of eigenvalues of the laplacian and what they tell us about the original graph.

0 Is an Eigenvalue for the Laplacian

Let

G

be a graph then

0

is an eigenvalue of

L_{G}

Consider

x = (1, 1, \dots, 1)

then note that the column matrix

c = L_{G} x

has

c_{i} = \sum_{k = 1}^{n} l_{i, k}

equivalently this is the sum of a row of the laplacian and we've already mentioned that this value is 0, showing that

c = 0

and therefore

0

is an eigenvalue of

L_{G}

Here we have the first connection with the connectivity of a graph, note that this is quite an interesting property to have, as we can compute eigenvalues quickly and computers operate quickly on matrices, this can provide a speedup

There Is Only One Zero Eigen Value for the Laplacian of a Connected Graph

Let

G

be a connected graph then

0

is an eigenvalue and all other eigenvalues of

L_{G}

are positive

Let $z \in ℝ^{n}$ be a non-zero eigenvector, then note that $z^{T} L_{G} z = z^{T} 0 = 0$ and also that $z^{T} L_{G} z = \sum_{{u, v} \in E} {(z_{u} - z_{v})}^{2} = 0$ , in otherwords for each ${u, v} \in E$ we have $z_{u} = z_{v}$ .

Now since $G$ is connected, we know that given any $i, j \in V$ there is a path connecting $z_{i}$ to $z_{j}$ this means that for each edge in this path the two incident vertices are equal by what was just discussed, and therefore by transitivity of equality we see that $z_{i} = z_{j}$ , therefore we conclude that $z = α (1, 1, \dots, 1)$ , therefore the eigen space associated with the eigenvalue of 0 is $span ((1, 1, \dots, 1))$ .

From there we deduce that the multiplicity of the eigenvalue 0 is equal to $1$ thus we must have that $λ_{2} \neq 0$ for if it was equal to zero, then since as before the $0 = λ_{1} \leq λ_{2} \leq \dots \leq λ_{n}$ were the eigenvalues for an orthonormal basis then if $λ_{2} = 0$ we would get that the multiplicity would be $2$ , a contradiction, therefore $λ_{2} \neq 0$ , that is $λ_{2} > 0$ as needed.

Subgraph

Suppose

G = (V, E)

is a graph, then a subgraph

S

G

is a graph

S = (E^{'}, V^{'})

such that

V^{'} \subseteq V

and

E^{'} = {{x, y} : x, y \in V^{'} \land {x, y} \in E}

In other words a subgraph is a graph that's already a part of the original graph.

Connected Component

A connected component of a graph

G

is a subgraph

G^{'} = (V^{'}, E^{'})

such that

i, j \in V^{'}

are connected, but also that for any

k \in V ∖ V^{'}

we have that

i, k

are not connected.

A connected component is a component such that it itself is connected, but for any vertex outside of it, there is no way to get there, so a graph with 3 connected components would look like a graph with three parts to it, but no way to get from one part to another.

The Geometric Multiplicity of the Eigenvalue Zero of the Laplacian Is the Number of Connected Components

Let

G = (V, E)

be a graph, then the geometric multiplicity of

0

for

L_{G}

is equal to the number of connected components in

G

Suppose that

G_{i} = (V_{i}, E_{i})

for

i \in [k]

for some

k \in ℕ_{1}

are the connected components of a graph

G

then if we construct

k

vectors of the form w _ i \in \mathbb{ R } ^ \left\lvert V \right\rvert ParseError: Got function '\left' with no arguments as superscript at position 26: …\mathbb{ R } ^ \̲l̲e̲f̲t̲\lvert V \right… holding information about which vertices from the original graph exist in the component, that is:

{(w_{i})}_{j} = {\begin{matrix} 1 & if j \in V_{i} \\ 0 & otherwise \end{matrix}

Now given an non-zero eigenvector

x

L_{G}

then we know that

x_{i} = x_{j}

whenever

i, j \in V

are in the same connected component from the last proposition, therefore we deduce that the eigenspace for

0

span (w_{1}, w_{2}, \dots, w_{k})

, by construction, the collection

{w_{1}, w_{2}, \dots, w_{k}}

are linearly indpendent so the dimension of the eigenspace is

k

, that is to say that the geometric multiplicity of the eigenspace of

0

for

L_{G}

is the number of connected components.

Now we explore the eigenvalues and eigenvectors of some known graphs.

Complete

We say that a graph

G = (V, E)

is complete whenever

V = {1, 2, \dots, m}

and

E = {{i, j} : i \neq j \in V}

. In that case we refer to

G

K_{m}

The Eigenvalues of the Laplacian of a Connected Graph

The laplcian of

K_{m}

has

0

as an eigenvalue with geometric multiplicity

1

and

m

as an eigenvalue with geometric multiplicity

m - 1

We already know that since there is one connected component, then we should have that the geometric multiplicity of $0$ is $1$ .

Now since each vertex $K_{n}$ is connected to $n - 1$ other vertices, then we know that the laplacian of $K_{n}$ is such that $k_{i, j} = {\begin{matrix} - 1 if i \neq j \\ n - 1 if i = j \end{matrix}$ therefore $L_{K_{n}} - n I$ is a matrix of all -1's which has rank one and is not invertible, thus $n$ is an eigenvalue of the laplacian of $K_{n}$ , finally by the rank nullity theorem we conclude that $null (L_{K_{n}} - n I) = n - 1$ so then the eigenvalue $n$ has multiplicity $n - 1$

Cycle Graph

The cycle graph on

n

vertices is denoted by

C_{n}

is a graph

G = (V, E)

where

V = [n]

and

E = {{i, i + 1} : i \in [n]} \cup {{1, n}}

Laplacian of the Cycle Graph

L_{C_{n}} = (\begin{matrix} 2 & - 1 & 0 & \dots & - 1 \\ - 1 & 2 & - 1 & \dots & 0 \\ ⋮ & ⋱ & ⋮ \\ 0 & \dots & - 1 & 2 & - 1 \\ - 1 & \dots & 0 & - 1 & 2 \end{matrix})

TODO: Add the proof here.

An Eigenvector of the Laplacian of the Cycle Graph Yields More Eigenvectors by Its Cyclic Permutations

Suppose that

x \in ℝ^{n}

is an eigenvector of

L_{C_{n}}

, then for any

x^{'}

which is a cyclic permutation of

x

, then it is also an eigenvector of

L_{C_{n}}

If $L_{C_{n}} x = λ x$ then we have a series of equations, let us label these equations:

(Equation 1): $2 x_{1} - x_{2} - x_{n} = λ x_{1}$ also and
(Equation $n$ ): $- x_{1} - x_{n - 1} + 2 x_{n} = λ x_{n}$
For each $1 < k < n$ we have (Equation $k$ ): $- x_{k - 1} + 2 x_{k} - x_{k + 1} = λ x_{m}$

Now suppose that $x^{'}$ is a cyclic permutation of $x$ , ie, there is a bijection $f : [n] \to [n]$ such that $x_{f (i)} = x_{i}^{'}$ .

We want to prove that $x^{'}$ is an eigen vector for $λ$ , thus we must verify that $L_{C_{n}} x^{'} = λ x^{'}$ , but that generates another $n$ equations similar to those above, but note that given the $i$ -th equation generated by this situation of the form $- x_{i - 1}^{'} + 2 x_{i}^{'} - x_{i + 1}^{'} = λ x_{i}^{'}$ is equivalent to this equation $- x_{f (i - 1)} + 2 x_{f (i)} - x_{f (i + 1)} = λ x_{f (i)}$ which holds true due to our original equations from $L_{C_{n}} x = λ x$ , thus since all equations hold true then $x^{'}$ is an eigenvector.

Laplacian of the Cycle Graph Has Trigonometric Eigenvalues

The Laplacian of

C_{n}

has eigenvalues given by

2 - 2 \cos (\frac{2 π k}{n})

for

k \in ℤ

and associated eigenvectors of the form:

Suppose that $λ$ is an eigenvector of $L_{C_{n}}$ and $x$ an eigenvector for that eigenvalue,then recall from the previous proof we have:

(Equation 1): $2 x_{1} - x_{2} - x_{n} = λ x_{1}$ also and
(Equation $n$ ): $- x_{1} - x_{n - 1} + 2 x_{n} = λ x_{n}$
For each $1 < k < n$ we have (Equation $k$ ): $- x_{k - 1} + 2 x_{k} - x_{k + 1} = λ x_{m}$

We know that if $P$ is a cyclic permutation, then $P x$ is also an eigenvector for $λ$ . This means that $x, P x, \dots, P^{n - 1} x$ are all eigenvectors of $λ$ . However, the maximum dimension of any eigenspace is $n - 1$ because we already knew that 0 was an eigenvalue of multiplicity 1. So there must be some $j$ such that: $P^{j} x \in span ({x, P x, \dots, P^{j - 1} x})$ If $j$ happened to be one, then we would be saying that $P x = α x$ for some $α$ , meaning that we are able to multiply all the numbers in this vector by a constant, and it will "loop" them around, so we will assume that $x_{i} = a^{i}$ for some constant $a$ , and see if we get any progress. That is if we plug in a potential solution of this form into the equations we have: $\begin{matrix} 2 - a - a^{n - 1} & = λ \\ 2 - a^{1 - n} - a^{- 1} & = λ and \\ 2 - a^{- 1} - a & = λ for all 1 < i < n \end{matrix}$

If we add the third equation to the first we obtain that $- a^{n} - 1 + a^{- 1} = 0$ so that $a^{- 1} = a^{n - 1}$ therefore $1 = a^{n}$ which would imply that for each $a_{k} = e^{\frac{2 π k i}{n}}$ (where $i \in ℂ$ the imaginary number $i$ ), we see that $a_{k}$ is a solution to the above equations, in other words $x_{1} = a_{k}$ for each $k \in [n]$ with $x_{i} = {(x_{1})}^{i}$ (as assumed earlier) will produce a valid eigen vector.

For each of the $n$ eigen vectors, we can explicitly determine their eigenvalue, based on (Equation 1) we note that their associated eigenvalues are given by $λ_{k} = 2 - 2 \cos (\frac{2 π k}{n})$ , we note that these values are real, but $x$ may consist of complex coefficients. Writing our vector $x$ using Euler's formula it is of the form: $z_{m} (k) = \cos (\frac{2 π k m}{n}) + i \sin (\frac{2 π k m}{n})$ Since $L_{C_{n}} z (k) = λ_{k} z (k)$ and both $L_{C_{n}}$ and $λ_{k}$ are real, this means that both the real part and the imaginary part of $z (k)$ are invariant under $L_{C_{n}}$ because $L_{C_{n}}$ consists of real entries. Thus we can conclude that $x_{m} (k) = \cos (\frac{2 π k m}{n})$ and $y_{m} (k) = \sin (\frac{2 π k m}{n})$ are both eigenvectors for $λ_{k} = 2 - 2 \cos (\frac{2 π k}{n})$ . Then, for $k > \frac{n}{2}$ , $\begin{matrix} x (k) & \in Span ({x (1), x (2), \dots, x (j)}) (j \leq \frac{n}{2}), and \\ y (k) & \in Span ({y (1), y (2), \dots, y (j)}) (j \leq \frac{n}{2}) \end{matrix}$ So the eigenvalues are $2 - 2 \cos (\frac{2 π k}{n})$ with $k \leq \frac{n}{2}$ . The list above is exhaustive since we have formed $n$ independent eigenvectors correspondingly to these eigenvalues: When $n$ is odd, we have one eigenvector $x (0)$ for $λ_{0} = 0 (y (0) = \vec{0})$ , and two eigenvectors $x (k)$ and $y (k)$ for all $0 < k < \frac{n}{2}$ . When $n$ is even, we have one eigenvector $x (0)$ for $λ_{0} = 0 (y (0) = 0)$ and two eigenvectors $x (k)$ and $y (k)$ for all $0 < k < \frac{n}{2}$ and one eigenvector $x (\frac{n}{2})$ for $λ_{\frac{n}{2}} = 4$ ( $y (\frac{n}{2}) = \vec{0}$ ).

Essay 2

Continuing on with what I learned in my first essay I decided to look at these eigenvalues in more detail, making a detour on the proof of Courant-Fischer which helps us obtain some bounds on these eigenvalues. Knowing this is important because the smallest non-zero eigenvalue of the Laplacian of a graph tells us how connected a graph is. We start with some preliminaries:

Rayleigh Quotient

Given a vector

x \neq 0

and

M

a compatible matrix, then we define the Rayleigh quotient as

\frac{x^{T} M x}{x T x}

The Rayleigh Quotient of an Eigenvector Is Its Eigenvalue

As per title.

M x = μ x

, then

\frac{x^{T} M x}{x^{T} x} = \frac{x^{T} μ x}{x^{T} x} = μ

Quadradic Form as a Summation of Eigenvalues

Let

M

be a symmetric matrix with eigenvalues

μ_{1}, \dots, μ_{n}

and a corresponding orthonormal basis of eigenvectors

ψ_{1}, \dots, ψ_{n}

. Let

x

be a vector whose expansion in the eigenbasis is

x = \sum_{i = 1}^{n} c_{i} ψ_{i}

Then,

x^{T} M x = \sum_{i = 1}^{n} c_{i}^{2} μ_{i}

Note the following algebra, where

α_{i}

and

β_{i}

are temporary vector valued variables to help ease you into the next line:

\begin{matrix} x^{T} M x & = {(\sum_{i = 1}^{n} c_{i} ψ_{i})}^{T} M (\sum_{j = 1}^{n} c_{j} ψ_{j}) \\ = {(\sum_{i = 1}^{n} c_{i} ψ_{i})}^{T} (\sum_{j = 1}^{n} c_{j} μ_{j} ψ_{j}) \\ = {(\sum_{i = 1}^{n} α_{i})}^{T} (\sum_{j = 1}^{n} β_{j}) \\ = \sum_{i, j \in [n]} α_{i}^{T} β_{j} \\ = \sum_{i, j \in [n]} c_{i} c_{j} μ_{j} ψ_{i}^{T} ψ_{j} \end{matrix}

But we know that

ψ_{i}^{T} ψ_{j} = {\begin{matrix} 0 & for i \neq j \\ 1 & for i = j \end{matrix}

therefore

x^{T} M x = \sum_{i} c_{i}^{2} μ_{i}

The Courant-Fischer Theorem tells us that the vectors $x$ that maximize the Rayleigh quotient are exactly the eigenvectors of the largest eigenvalue of the given matrix.

Courant Fischer

Let

M

be a symmetric matrix with eigenvalues

μ_{1} \geq μ_{2} \geq \dots \geq μ_{n}

. Then,

\begin{matrix} μ_{k} & = \max_{\begin{matrix} S \subseteq 𝐑^{n} \\ \dim (S) = k \end{matrix}} \min_{\begin{matrix} x \in S \\ x \neq 0 \end{matrix}} \frac{x^{T} M x}{x^{T} x} \\ = \min_{\begin{matrix} T \subset 𝐑^{n} \\ \dim (T) = n - k + 1 \end{matrix}} \max_{\begin{matrix} x \in T \\ x \neq 𝟎 \end{matrix}} \frac{x^{T} M x}{x^{T} x} \end{matrix}

where the maximization and minimization are over subspaces

S

and

T

ℝ^{n}

Let $ψ_{1}, \dots, ψ_{n}$ be an orthonormal set of eigenvectors of $M$ corresponding to $μ_{1}, \dots, μ_{n}$ . We will only prove that $μ_{k} = \max_{\begin{matrix} S \subseteq 𝐑^{n} \\ \dim (S) = k \end{matrix}} \min_{\begin{matrix} x \in S \\ x \neq 0 \end{matrix}} \frac{x^{T} M x}{x^{T} x}$ Only because the other is symetrically similar.

In order to prove that $μ_{k}$ is achievable. Let $S$ be the span of $ψ_{1}, \dots, ψ_{k}$ . We can expand every $x \in S$ as $x = \sum_{i = 1}^{k} c_{i} ψ_{i}$ Now since $μ_{i} \geq μ_{k}$ for $i \in [k]$ we have that $\frac{x^{T} M x}{x^{T} x} = \frac{\sum_{i = 1}^{k} μ_{i} c_{i}^{2}}{\sum_{i = 1}^{k} c_{i}^{2}} \geq \frac{\sum_{i = 1}^{k} μ_{k} c_{i}^{2}}{\sum_{i = 1}^{k} c_{i}^{2}} = μ_{k}$ And thus a lower bound on the minimum value, that is: $\min_{x \in S} \frac{x^{T} M x}{x^{T} x} \geq μ_{k}$

To show that this is in fact the maximum, we will prove that for all subspaces $S$ of dimension $k$ , $\min_{x \in S} \frac{x^{T} M x}{x^{T} x} \leq μ_{k}$

Let $T$ be the span of $ψ_{k}, \dots, ψ_{m}$ . As $T$ has dimension $n - k + 1$ , every $S$ of dimension $k$ has an intersection with $T$ of dimension at least 1 because $(n - k + 1) + k = n + 1$ , therefore: $\min_{x \in S} \frac{x^{T} M x}{x^{T} x} \leq \min_{x \in S \cap T} \frac{x^{T} M x}{x^{T} x} \leq \max_{x \in T} \frac{x^{T} M x}{x^{T} x}$

Now recall $x$ in $T$ may be expressed as $x = \sum_{i = k}^{n} c_{i} ψ_{i}$ and so for $x$ in $T$ since $μ_{k} \geq μ_{i}$ where $k \leq i \leq n$ , we get: $\frac{x^{T} M x}{x^{T} x} = \frac{\sum_{i - k}^{n} μ_{i} c_{i}^{2}}{\sum_{i = k}^{n} c_{i}^{2}} \leq \frac{\sum_{i - k}^{n} μ_{k} c_{i}^{2}}{\sum_{i = k}^{n} c_{i}^{2}} = μ_{k}$ which shows that $\min_{x \in S} \frac{x^{T} M x}{x^{T} x} \leq μ_{k}$ so we conclude : $μ_{k} = \max_{\begin{matrix} S \subseteq 𝐑^{n} \\ \dim (S) = k \end{matrix}} \min_{\begin{matrix} x \in S \\ x \neq 0 \end{matrix}} \frac{x^{T} M x}{x^{T} x}$

For our purposes we will use a more speicific version of the theorem:

Courant Fischer Specific

Let

A

be an

n \times n

symmetric matrix and let

1 \leq k \leq n

. Let

λ_{1} \leq λ_{2} \leq \dots \leq λ_{n}

be the eigenvalues of

A

and

v_{1}, v_{2}, \dots, v_{n}

be the corresponding eigenvectors. Then,

\begin{matrix} λ_{1} & = \min_{x \neq 0} \frac{x^{T} A x}{x^{T} x} \\ λ_{2} & = \min_{x \neq 0 and x ⟂ v_{1}} \frac{x^{T} A x}{x^{T} x} \\ λ_{n} & = \max_{x \neq 0} \frac{x^{T} A x}{x^{T} x} \end{matrix}

TODO: Add the proof here.

With this new version of the theorem we can get a lower bound on the largest eigenvalue of the Laplacian of a graph. For the next theorem we will denote the $k$ -th eigen value of of the laplacian of a graph $G$ by $λ_{k} (G)$ , note that in the context of having $n$ eigenvalues since they were ordered in an non-decreasing way then $λ_{n} (G)$ is the largest eigenvalue.

The Largest Eigenvalue of the Laplacian of a Graph Is at Least as Large as the Degree of Any Vertex

Let

G = (V, E)

be a graph with

V = {1,2, \dots, n}

and

u \in V

. If

u

has degree

d

, then

λ_{n} (G) \geq d

By Courant-Fischer Theorem, $λ_{n} (G) = \max_{x \neq 0} \frac{x^{T} L_{G} x}{x^{T} x}$ By the combination of this corollary and this proposition we have $x^{T} L_{G} x = \sum_{{u, v} \in E} {(x_{u} - x_{v})}^{2}$

Note that $\sum_{{u, v} \in E} {({(e_{j})}_{u} - {(e_{j})}_{v})}^{2} = d$ because for each edge ${u, v} \in E$ such that $j$ is incident to that edge, ie $j \in {u, v}$ then we know that ${{(e_{j})}_{u}, {(e_{j})}_{v}} = {0, 1}$ and thus ${({(e_{j})}_{u} - {(e_{j})}_{v})}^{2} = 1$ , on the other hand the number of edges such that $j$ is incident to is simply the degree of $j$ thus said equation holds true.

Now using the information gathered in the last paragraph recall the standard basis: $e_{1}, e_{2}, \dots, e_{n}$ and consider $x = e_{j}$ for some $j \in [n]$ , we have: $\begin{matrix} \frac{e_{j}^{T} L_{G} e_{j}}{e_{u}^{T} e_{u}} & = \frac{\sum_{{u, v} \in E} {({(e_{j})}_{u} - {(e_{j})}_{v})}^{2}}{\sum {(e_{j})}_{u}^{2}} \\ = \frac{d}{1} \\ = d \end{matrix}$ So $λ_{n} (G) \geq \frac{x^{T} L_{G} x}{x^{T} \cdot x} = d$ .

Now we focus on the second smallest eigenvalue, whose importance we learned of in the first essay.

The Second Smallest Eigenvalue of the Laplacian of the Path Graph on N Vertices Is in the Big O of One Over N Squared

Let

P_{n}

be the path graph, then

λ_{2} (P_{n}) \in 𝒪 (\frac{1}{n^{2}})

We start by considering the vector

u

such that

u_{i} = (n + 1) - 2 i

, the reason why is so that it becomes perpendicular with

\vec{1}

, the vector of all ones:

u \cdot \vec{1} = \sum_{i = 1}^{n} ((n + 1) - 2 i) = \sup_{i = 1}^{n} (n + 1) + 2 \sum_{i = 1}^{n} i = 0

As seen earlier on

\vec{1}

spans the eigenspace for the eigenvalue

λ_{1} = 0

. Then by Courant-Fischer we get an upperbound:

\begin{matrix} λ_{2} (P_{n}) & = \min_{x ⟂ \vec{1}} \frac{x^{T} L_{P_{n}} x}{x^{T} x} \\ \leq \frac{u^{T} L_{P_{n}} u}{u^{T} u} \end{matrix}

We have also shown that:

x^{T} L_{G} x = \sum_{{u, v} \in E} {(x_{u} - x_{v})}^{2}

By the nature of

u

we have that

u_{i} - u_{i + 1} = (n + 1) - 2 i - ((n + 1) - 2 (i + 1)) = 2

So therefore:

\begin{matrix} \frac{u^{T} L_{P_{n}} u}{u^{T} u} & = \frac{\sum_{i = 1}^{n - 1} {(u_{i} - u_{i + 1})}^{2}}{\sum_{i} {(u_{i})}^{2}} \\ < \frac{n 2^{2}}{\sum_{i = 1}^{n - 1} {(n + 1 - 2 i)}^{2}} \end{matrix}

The denominator

\sum {(n + 1 - 2 i)}^{2} \in 𝒪 (n^{3})

, so we can conclude that

λ_{2} \in 𝒪 (\frac{1}{n^{2}})

This concludes my exploration of spectral graphs for the moment.