# Exploring Spectral Graph Theory

In this article, I’ll explore spectral properties of graphs using Linear Algebra. I will make this article as self contained as possible. But, having prior knowledge of Linear Algebra is important. I’ll introduce any background needed.

## Set Theory

Mathematics is a language. The definitions of concepts in mathematics are defined precisely. It allows us to reason about them with proofs. The concepts are explained through set theory. Set theory could be used as a possible foundation for mathematics. There is a rigirous treatment of set theory itself called Zermalo-Fraenkel Set Theory. I’ll introduce enough set theory to explain graphs.

**Definition**: A **set** is a collection of objects. We could denote the elements of a set in a comma separated list that is enclosed with braces.

Ex:

A = {1, 2, 3, 4}

We could specify an element belongs to a set. The expression 1 \(\varepsilon\) A is read as 1 is a member of A.

### Subset

A set can be contained in another set. This relationship is defined by a subset.

**Definition**: Assume we have two sets A and B. A is a **subset** of A if every element of A is an element of B. In other words, A is contained in B. This is denoted as A \(\subseteq\) B.

There are two possiblities for subsets. First, A and B could be equal or B could have more elements than A. The case where B has more elements than A is referred to as a proper subset.

**Definition**: Assume we have two sets A and B and A not equal to B. A is a **proper subset** of B. B is called the **superset** of A. This is denoted as A \(\subset\) B.

This diagram shows this relationship among the two sets.

There are basic operations that can be performed on a set. We could take the union and intersection of sets.

### Union

**Definition**: Assume we have two sets A and B. The **union** of A and B is the set of all elements that are in A or B. This written in set builder notation as \(A \cup B = \{\,x\mid x \in A \lor x \in B\,\}\).

In this diagram, we have a universal set where \(A \subset U\) and \(B \subset U\). The area highlighted above is the set \(A \cup B\).

### Intersection

**Definition**: Assume we have two sets A and B. The **intersection** of A and B is the set of all elements that are in A and B. This written in set builder notation as \(A \cap B = \{\,x\mid x \in A \land x \in B\,\}\).

### Ordered Pairs

Lastly, we’ll define an ordered pair.

**Definition**: An **ordered pair** is a pair of objects denoted as (a, b). The ordered pair (a, b) is different from (b, a) unless a == b. On the other hand, an **unordered pair** is (a, b) does not enforce any ordering.

We could use ordered pairs to define the cartesian product of two sets.

### Cartesian Product

**Definition**: Suppose we have two sets A and B. Their **cartesian product** is defined as \(A \times B = \{\,(x,y)\mid x \in A \land y \in B \}\) It is the set of all ordered pairs (x, y) such that x is an element of A and y is an element of B.

There are many more topics in set theory. But, this is enough to define a graph and explore their properties.

## Graphs

**Definition**: A **graph** is an ordered pair G = (V, E). V is the set of all vertices in the graph. E is the set of all edges. \(E \subset \{\,(x,y)\mid x \in V^2 \land x \neq y\}\). \(V^2\) is the set of all vertices that is defined as \(V^2 = V \times V\).

### Undirected Graph

As you could from this definition, we are using set theory to define a simple concept of a set. Here is an example of a graph.

This graph has the vertices V = {A, B, C} and edges E = {(A, B), (B, C)}. This is an example of an undirected graph. There isn’t direction indicated in the connections betweens the vertices. The ordered pairs in the set of edges is unordered.

### Directed Graph

Here is an example of a directed graph.

There is directional arrow specified in the edges. This graph has the vertices V = {A, B, C} and the edges E = {(B, A), (A, C), (C, B)}. These are ordered pairs.

### Adjaceny Matrix

We could also represent a graph as a matrix, which a rectangular array of numbers. A matrix could defined with various levels of abstraction. Here is a simple definition that suffices for our dicussion.

**Definition**: A **matrix** is a rectangular array of numbers. It is enclosed in brackets. A is an *m* x *n* matrix with elements at \(a_{mn}\). The subscripts m and n represent the column and row the element is located. Both *m* and *n* are positive integers.

A = \(\begin{bmatrix} a_{11} & a_{12} & ... & a_{1n}\\ a_{21} & a_{22} & ... & a_{2n}\\ a_{31} & a_{32} & ... & a_{3n}\\ ... & ... & ... & ... \\ a_{m1} & a_{m2} & ... & a_{mn}\\ \end{bmatrix}\)

The representation of a graph is called an adjanceny matrix. Each element of the matrix is indicates whether there is an edge from one vertex to another. This graph’s matrix is the following.

A = \(\begin{bmatrix} 0 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 0\\ \end{bmatrix}\)

**Definition**: Assume we have a graph G = (V, E). The values in the adjanceny matrix is described as follows.

\(a_{ij} = \begin{cases}
1 & \text{Edge between vertices}\\
0 & \text{No edge between vertices}\\
\end{cases}\)

The adjancey matrix allows us to use Linear Algebra to study the spectral properties of the graph.

### Symmetry

An interesting feature of an undirected graph’s adjaceny matrix is that it is symmetric. A matrix is symmetrix if it is equal to its transpose.

**Definition**: Suppose we have an *m* x *n* matrix labeled A. The **transpose** of A is the matrix *n* x *m* which is labeled \(A^{T}\).

Example:

A = \(\begin{bmatrix} 1 & 2\\ 3 & 4\\\end{bmatrix}\)

A^{T} = \(\begin{bmatrix} 1 & 3\\ 2 & 4\\\end{bmatrix}\)

**Theorem**: The adjaceny matrix for an undirected graph is symmetric. But, this is not true for a directed graph.

This is the adjaceny matrix of the undirect graph we looked at earlier.

A = \(\begin{bmatrix} 0 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 0\\ \end{bmatrix}\)

Its transpose is the same.

A^{T} = \(\begin{bmatrix} 0 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 0\\ \end{bmatrix}\)

### Graph Walks

**Definition**: Suppose we have a graph G = (V, E). A **walk** from one vertex to another is a sequence of vertices. (v_{i}, v_{j}),(v_{j}, v_{k}),…, (v_{m}, v_{n}) is a walk from a vertex v_{i} to v_{n}. The length of the walk is the number of pairs in the sequence.

Example

The sequence (A, B), (B, C) is a walk from A to C.

**Theorem**: Assume G = (V, E) with adjancey matrix A_{G}. If we raise A_{G} to an n-th power, the a_{ij} element of the matrix gives us the number of walks from v_{i} and v_{j} of length n. The value of n is a positive integer.

Example

If we square the adjacency matrix for the undirected graph above, we get the following matrix.

A = \(\begin{bmatrix} 0 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 0\\ \end{bmatrix}\)

A^{2} = \(\begin{bmatrix} 1 & 0 & 1\\ 0 & 2 & 0\\ 1 & 0 & 1\\ \end{bmatrix}\)

In the matrix A^{2}, there is a value of 1 at the location a_{00}. This indicates that there is one walk of length 2 from the vertex A to itself. It is (A, B), (B, A).

The value at location a_{11} is 2. This means there are 2 walks of length 2 from B to itself. They are (B, C), (C, B) and (B, A) and (A, B).

If we were take powers of A to 3 and higher, we would get a resultant matrix which tells us the number of walk form one vertex to another vertex of length 3 or higher.

### Complete Graph

**Definition**: A **complete graph** is a graph each pair of vertices is connected by an edge. It is denoted as M_{n} where n is the number of vertices.

Example

M_{3} =

This complete graph has 3 vertices. Its adjacency matrix is the following.

A = \(\begin{bmatrix} 0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 0\\ \end{bmatrix}\)

The spectrum of this graph M_{3} is the eigenvalues of the adjacency matrix and their multiplicities.

### Eigenvalues & Eigenvector

**Definition**: If A is an *n* x *n* matrix, then a nonzero vector **x** in R^{n} is called an **eigenvector** of A if Ax = λx for some scalar λ. The scalar λ is called an **eigenvalue** of A, and x is said to be an eigenvector of A corresponding to λ. _{1}

The characteristic equation det(λI – A) = 0, where I is the identity matrix, is used to find the eigenvalues. The left part of the characteristic equation det(λI – A) is called the characteristic polynomial of A.

The characteristic polynomial of M_{3}(the adjacency matrix of M_{3}) is the following.

Equating the characteristic polynomial to 0 and finding the roots of the polynomial gives the eigenvalues of A.

λ^{3} - 3λ - 2 = 0

(λ - 2)(λ + 1)^{2} = 0

(λ - 2)(λ + 1)(λ + 1) = 0

The eigenvalues are λ_{0} = -1, λ_{1} = -1 and λ_{2} = 2. The algebraic multiplicities of the roots are m(λ_{0}) = 2 and m(λ_{2}) = 1. The eigenvalues of A and their multiplicities form the spectrum of the complete graph M_{3}.

### Graph spectrum

**Definition**: The **spectrum** of a graph is the set of numbers which are eigenvalues of A, together with their multiplicities. If the distinct eigenvalues A are λ_{0} > λ_{1} > … > λ_{s-1}, and their multiplicities are m(λ_{0}), m(λ_{1}),…,m(λ_{s-1}), then we shall write.

Spectrum = \(\begin{pmatrix} λ_{0} & λ_{1} & .. & λ_{s-1}\\ m(λ_{0}) & m(λ_{1}) & .. & m(λ_{s-1}) \end{pmatrix}\) _{2}

Example:

M_{3} =

The spectrum of graph M_{3} is the following matrix.

Spectrum M_{3} = \(\begin{pmatrix} -1 & 2 \\ 2 & 1 \end{pmatrix}\)

### Spectrum Analysis

If we write the characteristic polynomial of M_{3} in the form

λ^{n} + c_{1}λ^{n-1} + c_{2}λ^{n-2} + c_{3}λ^{n-3} + … + c_{n}

We could observe information about the sum of the eigenvalues and the trace of the adjacency matrix of M_{3}.

The characteristic polynomial of M_{3} in this form is

λ^{3} + (-0)λ^{2} + (-3)λ^{1} + (-2)

- The coefficient c
_{1}is 0 which is the sum of the eigenvalues. λ_{0}+ λ_{1}+ λ_{2}= -1 + -1 + 2 = 0. - The coefficient c
_{1}is also the trace of (the adjacency matrix of M_{3}).

This is true in general for complete graphs. The trace of the adjacency of complete graphs is c1 and sum of the eigenvalues will be the coefficient -c1.

**Theorem**: The coefficients of the characteristic polynomial of a graph G satisfy the following properties.

1. c1 = 0.

2. –c2 is the number of edges of G.

3. –c3 is twice the number of triangles in G. _{2}

Example:

The coefficients of the characteristic polynomial of a graph M_{3} satisfy the following.

- c
_{1}= 0. - –c
_{2}is the number of edges of G. - –c
_{3}is twice the number of triangles in G.

This theorem is true for complete graphs with at least three vertices. In the characteristic polynomial equation of the adjacency matrix of M_{3}.

λ^{3} + (-0)λ^{2} + (-3)λ^{1} + (-2)

- c
_{1}= 0 - -c
_{2}= -(-3) = 3 —> The number of edges in the graph M_{3}. - –c
_{3}= -(-2)= 2 —> The number of triangles in M_{3}is 1. The coefficient –c_{3}= -(-2)= 2 is twice the number of triangles in M_{3}.

### Regular graph

**Definition**: A regular graph is a graph whose vertices all have equal degrees. A m-regular graph is a
regular graph whose common degree is m.

Example:

This is an example of a regular of degree 3. Each node has 3 connections in the graph. There are several properties concerning the eigenvalues of regular graphs.

### Regular graph spectrum

**Definition**: If the simple graph G is m-regular, then

(1) m is an eigenvalue of G

(2) the multiplicity of the eigenvalue m is 1, provided G is connected

(3) \(\mid λ \mid \leq m\) for any eigenvalue of G._{2}

Example:

This is an example of a 2-regular graph. Its graph’s adjacency matrix is the following.

A = \(\begin{bmatrix} 0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 0\\ \end{bmatrix}\)

The characteristic polynomial of this matrix was found to be λ^{3} - 3λ - 2. The eigenvalues are λ_{0} = -1, λ_{1} = -1 and λ_{2} = 2. The multiplicieties of these eigenvalues are m(λ_{0}) = 2 and m(λ_{2}) = 1.

We could observe from the eigenvalues that k (the common degree of the graph) which is 2 is an eigenvalue and its multiplicity is 1. We could also observe that the absolute value of the eigenvalues λ_{0}, λ_{1}, λ_{2} are less than or equal 2 which is the common degree of the regular graph G. We have confirmed by example properties 1, 2 and 3 hold for a regular graph.

I hope you found this article useful for learning algebraic graph theory.