This is the lecture note for a micro-seminar of ChatGPT.

Graphs and Matrices

Introduction

We start with a lovely algebra problem.

Problem. Let $n > 1$ be a positive integer. Consider the polynomial defined by

F_{n} (x) = \sum_{i = 1}^{n} x^{gcd (i, n)}

Prove that $F_{n} (x) + 1$ is irreducible over $Z$ .

The last time you've seen this polynomial might be in a number theory problem that says $n$ divides $F_{n} (x)$ for every positive integer $x$ . (The standard solution is to use induction on $n$ .) Actually this problem has a combinatorial solution: $\frac{F_{n} (x)}{n}$ is the number of distinct necklaces made up of $n$ balls in $x$ distinct colors up to a rotation, hence an integer.

Back to this problem. Let's first try some standard methods. Eisenstein's criterion seems not to work. Perron's criterion could solve some cases, by considering the reciprocal polynomial of $F_{p^{k}} (x) + 1$ , where $p$ is a prime. General irreducibility criterions cannot bring us further.

We turn to find some special properties of the polynomial $F_{n}$ . As we said before, $F_{n}$ has the special property that $n ∣ F_{n} (x)$ for every integer $x$ . In particular, if there is a linear factor of $F_{n} (x) + 1$ , let $α$ be its root, then we have $0 = F_{n} (α) + 1 \equiv 1 (\mod n)$ , which can only happen when $n = 1$ .

We can rule out other factors by exactly the same way:

Lemma. For every monic polynomial $P$ with integer coefficients, if $α_{1}, α_{2}, \dots, α_{d}$ are all its (complex) roots, then we have the property

n ⏐ \sum_{i = 1}^{d} F_{n} (α_{i}) .

While it is not so difficult for one to come up with an algebraic or number theoretic proof of this lemma, the truly interesting thing is, there is a combinatorial proof of it.

Proof, but combinatorial. We still use the idea of counting necklaces, but this time, we cannot choose colors at our will. Let $G (V, E)$ be a directed multigraph. This time, we use $E$ as our set of colors. A necklace is called valid, if it is made up of balls of color $e_{1}, e_{2}, \dots, e_{n}$ in this order, such that $e_{1}, e_{2}, \dots, e_{n}$ generates a directed closed walk in $G$ in the same order. We count the number of valid necklaces up to rotation. By Burnside's lemma the number is

\frac{1}{n} \sum_{i = 1}^{n} (number of directed closed walk in G with length gcd (i, n)) .

So we need to count the number of closed walks in a directed graph. This is where matrices shows up. Let $A$ be the adjacency matrix of $G$ , then the number of directed closed walk in $G$ with length $ℓ$ is exactly $tr A^{ℓ}$ . Therefore,

n ⏐ \sum_{i = 1}^{n} tr A^{gcd (i, n)} .

Let the eigenvalues of $A$ be $λ_{1}, λ_{2}, \dots, λ_{d}$ . Then

tr A^{ℓ} = \sum_{i = 1}^{d} λ_{i}^{ℓ} .

Therefore

n ⏐ \sum_{i = 1}^{n} \sum_{j = 1}^{d} λ_{j}^{gcd (i, n)} = \sum_{j = 1}^{d} F_{n} (λ_{j}) .

To complete the proof, let $P$ be an arbitrary monic polynomial with integer coefficients. Let $A$ be its companion matrix, i.e. a matrix that has $P$ as its characteristic polynomial. Since we're doing things modulo $n$ , we can add some $n$ 's to every entry of $A$ , making it a matrix with non-negative integer entries. Thus $A$ can be seen as the adjacency matrix of some directed multigraph $G$ , and the lemma follows.

We will see that this lemma easily implies the irreducibility of $F_{n} (x) + 1$ . If $P (x)$ is a factor of $F_{n} (x) + 1$ , let $α_{1}, \dots, α_{d}$ be all its complex roots, and we have

0 = \sum_{i = 1}^{d} (F_{n} (α_{i}) + 1) = \sum_{i = 1}^{d} F_{n} (α_{i}) + d \equiv d (\mod n)

This can only happen if $d = 0$ or $d = n$ , which means $P \equiv 1$ or $P = F_{n} + 1$ , hence the irreducibility.

I really like this problem because it perfectly combines different aspects of combinatorics, algebra and number theory. It also shows the marvellous relation between graph theory and matrices, specifically eigenvalues of the adjacency matrix, a.k.a. the spectrum of a graph. This lecture will show some of my favourite topics in spectral graph theory.

Calculation of Spectra

Before studying spectra, we first discuss how to calculate spectra.

Proposition. The spectrum of the cycle $C_{n}$ is

{2 \cos \frac{2 π k}{n} : k = 1, 2, \dots, n} .

Discussion. Give a combinatorial interpretation of spectra.

Discussion. Calculate the spectrum of a path, $P_{n}$ . Observe that the spectrum of $P_{n}$ is contained in the spectrum of $C_{2 n + 2}$ . Can you prove this observation combinatorially? Give a sequence of graphs $G_{1} \subset G_{2} \subset \dots$ such that the spectrum of $G_{i + 1}$ contains the spectrum of $G_{i}$ .

Discussion. Prove that the eigenvalues of $G \times H$ are given by $λ + μ$ , where $λ$ runs over the eigenvalues of $G$ and $μ$ runs over the eigenvalues of $H$ , multiplicities counted.

Bounds Related to the Spectrum

Subgraphs

The first question we might want to ask is: how does the spectrum of a subgraph relate to that of the original graph? This is equivalent as asking, how does the eigenvalues of a principal submatrix relate to those of the original matrix?

The following theorem gives a nice inequality about these:

Cauchy's Interlace Theorem. If $λ_{1} \leq \dots \leq λ_{n}$ are eigenvalues of a symmetric real matrix $A$ and $μ_{1} \leq \dots \leq μ_{n - 1}$ are eigenvalues of $B$ , a principal minor of $A$ . Then

λ_{1} \leq μ_{1} \leq \dots \leq μ_{n - 1} \leq λ_{1} .

This theorem gives us bounds on the spectra of subgraphs.

We now see how the spectrum can give us bounds of graphic properties.

Degree

We often denote the largest eigenvalue and the smallest eigenvalue of $G$ by $λ_{1} (G)$ and $λ_{n} (G)$ , respectively.

Discussion. Prove that

Δ (G) \geq λ_{1} (G) .

Hint. Use the combinatorial interpretation.

In the above theorem, we can actually replace the adjacency matrix $A$ by any matrix that is obtained by replacing some $1$ 's in $A$ by $- 1$ .

As an interesting application, let's prove a theorem, which appeared as a lemma used to prove the sensitivity conjecture:

Theorem. (Hao Huang) Let $H$ be an arbitrary induced graph of the hupercube $Q_{n}$ with $2^{n - 1} + 1$ vertices. Then

Δ (H) \geq \sqrt{n} .

Hint. Don't use the ordinary adjacency matrix; use

A_{1} = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}), A_{n} = (\begin{matrix} A_{n - 1} & I \\ I & - A_{n - 1} \end{matrix}) .

There is also a trivial upper bound on the minimal degree:

Proposition. $δ (G) \leq λ_{1} (G)$ .