Sandbox:DavidKohler/Relativized Alon Conjecture/Eigenvalue (graph)

There are several ways to obtain eigenvalues for a given graph G. We review those here.

Adjacency eigenvalues

Given a graph G and an ordering {v₁, ..., v_n} of its vertices we can define its adjacency matrix as the n×n matrix A_G where the i, j coefficient is the number of directed edges (in the underlying directed graph) whose tail is the vertex v_i and whose head is the vertex v_j and that we call the adjacency eigenvalues of the graph G.

The matrix that is obtained is always symmetric, due to the involution and since it is real, the spectral theorem guarantees the existence of n real eigenvalues (with multiplicity) that we denote by λ₁, ..., λ_n.

The eigenvalues are the solutions, λ, of the equation

$\displaystyle \det[A_{G}-\lambda I]=0$

Properties

• We have |λ_i| ≤ Δ_G (the maximum degree of the graph)
• When the graph is d-regular, then we have precisely λ₁ = d and with multiplicity the number of connected component of the graph G.
• We have λ₁ = λ_n when the graph is bipartite.

Adjacency eigenvectors

An adjacency eigenvector for a graph G is a function f in the space ℓ(G) of all complex-valued functions defined on the vertices of the graph G.

$\displaystyle \ell (G)=\{\,f\mid f:V_{G}\to \mathbb {C} \,\}$

If the function f ∈ ℓ(G) is an eigenvector for the eigenvalue λ, then by definition we have that

$\displaystyle A_{G}f=\lambda f$

which can be rewritten as

$\displaystyle \sum _{e\in t_{G}^{-1}(v)}f(h_{G}(e))=\lambda f(v)$

for any vertex v ∈ V_G. Note that the here we consider the underlying directed edges (this makes it clear why the contribution of a whole-loop is twice that of a half-loop). We can interpret the above relation as follow: an eigenvector represents a weight on each vertex and for any vertex, consider the sum of all the weights of the vertices that are the heads of edges whose tail are the considered vertex; this sum equals the weight of the vertex multiplied by the eigenvalue.

Example

To do
	add an example here, maybe some picture

Irreducible eigenvalues

The adjacency matrix can be understood as counting walks in the graph: if you take the k^th power of the adjacency matrix, the (i,j) entry is the number of walks of length k going from vertex i to vertex j. We want to encode a similar information about irreducible walks, that is walks that do not backtrack along an edge. This information is encoded in the line graph associated to the graph G. We call the adjacency eigenvalues of the line graph the irreducible eigenvalues of the graph G.

Example

To do
	Given a graph, show the line graph and the irreducible eigenvalues. An examples where the graph is d-regular might be a good idea.

Properties

Let G be a d-regular graph on n vertices, then there are exactly dn irreducible eigenvalues (up to multiplicity) which are described as follow:

• Given an adjacency eigenvalue, λ, of the graph G, there are two (in multiplicity) associated irreducible eigenvalues given by

$\displaystyle \mu _{1,2}(\lambda )={\frac {\lambda \pm {\sqrt {\lambda ^{2}-4(d-1)}}}{2}}$

• additionally, 1 and -1 are irreducible eigenvalues, each of multiplicity ${\frac {n(d-2)}{2}}$.

As a corollary, we obtain that the trace of the Hashimoto matrix is the same as the trace of the adjacency matrix.

Proof

Recall Bass' formula $\displaystyle \det[H_{G}-\mu I]=(\mu ^{2}-1)^{\chi (G)}\cdot \det[(\mu ^{2}+d-1)I-\mu A_{G}]$ Thus, there are clearly two cases to look at. For μ to be an eigenvalue, then either we have μ2 = 1 with multiplicity χ(G), where $\displaystyle \chi (G)={\frac {nd}{2}}-n={\frac {n(d-2)}{2}}$ or μ is a solution of the equation $\displaystyle \det[(\mu ^{2}+d-1)I-\mu A_{G}]=0$ Obviously, μ = 0 is not a solution, so we can assume μ is non-zero and write $\displaystyle \det[(\mu ^{2}+d-1)I-\mu A_{G}]=-\mu \det[A_{G}-(\mu +{\frac {d-1}{\mu }})I]$ and conclude that if μ is an irreducible eigenvalue, then the quantity $\displaystyle \mu +{\frac {d-1}{\mu }}$ is an eigenvalue, λ, of the adjacency matrix AG satisfying $\displaystyle \mu ^{2}-\lambda \mu +d-1=0$ and so we have two irreducible eigenvalues μ1 and μ2 $\displaystyle \mu _{1,2}={\frac {\lambda \pm {\sqrt {\lambda ^{2}-4(d-1)}}}{2}}$ for each adjacency eigenvalue λ; which concludes our proof.