Sandbox:DavidKohler/Alon try 1/Irreducible eigenvalues

Given a directed graph one can define its irreducible eigenvalues as the eigenvalues of the graph describing irreducible walks in the graph.

Definition

Irreducible eigenvalues are eigenvalues of a corresponding graph in which we only keep track of irreducible (or non-backtracking) walks. We'll define this here for directed graphs, for undirected graphs and for variable-length graphs.

For a directed graph

Let G be a directed graph, we associate to this graph a new graph that we call its graph of irreducible walks and denote by G_$Irred$. This graph is constructed as follow: its vertices are all the directed edges of the graph G and there is an edge from a directed edge e₁ to another directed edge e₂ if the directed path e₁e₂ is irreducible (or non-backtracking). Note that walks in this new graph do indeed correspond to irreducible walks in the original graph. We define the irreducible eigenvalues of the graph G to be the eigenvalues of the graph G_$Irred$ and will denote by λ_$Irred$(G) the largest irreducible eigenvalue of the graph G.

For an undirected graph

If G is an undirected graph, we define its irreducible eigenvalues as the irreducible eigenvalues of its corresponding directed graph (where for each undirected edge we create a pair of opposed directed edges).

For a VLG

Let G be a variable-length graph, then we can define G_$Irred$ as a variable-length graph as well by using the same construction as above and making the length of an edge in the graph G_$Irred$ be the length of the corresponding irreducible walk in the graph G.

Example

Consider the directed graph G on four vertices arranged as a basis (v₁, v₂, v₃, v₄) with adjacency matrix (in this basis):

A_{G}=\left({\begin{array}{cccc}0&1&0&0\\1&0&1&1\\0&1&0&1\\0&1&1&0\end{array}}\right)

Then the irreducible graph G_$Irred$ has eight vertices (the eight directed edges of the graph G) which we'll arrange in the basis (e₁₂, e₂₁, e₂₃, e₃₂, e₂₄, e₄₂, e₃₄, e₄₃) in which the adjacency matrix is:

A_{G_{\textit {Irred}}}=\left({\begin{array}{cccccccc}0&0&1&0&1&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&0&0&1&0\\0&1&0&0&1&0&0&0\\0&0&0&0&0&0&0&1\\0&1&1&0&0&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&1&0&0&0&0\\\end{array}}\right)