Eigenvalues of combinatorial Laplacians

MAA Southwestern Section UTEP Apr. ’05 Eigenvalues of combinatorial Laplacians

Art Duval, University of Texas at El Paso

GRAPHS

[figure: 4; 2; 6; e; c; a; b; f; h; 5; g; 3; d; 1]

∂_{1} = \begin{aligned}& a & b & c & d & e & f & g & h \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 2 & −1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 3 & 0 & −1 & 0 & 0 & 0 & −1 & 0 & 0 \\ 4 & 0 & 0 & −1 & 0 & 0 & 0 & −1 & 0 \\ 5 & 0 & 0 & 0 & −1 & 0 & 0 & 0 & −1 \\ 6 & 0 & 0 & 0 & 0 & −1 & 0 & 0 & 0 \end{aligned}

∂_{1}∂_{1}^{T} = \begin{aligned}& 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 5 & −1 & −1 & −1 & −1 & −1 \\ 2 & −1 & 4 & −1 & −1 & −1 & 0 \\ 3 & −1 & −1 & 2 & 0 & 0 & 0 \\ 4 & −1 & −1 & 0 & 2 & 0 & 0 \\ 5 & −1 & −1 & 0 & 0 & 2 & 0 \\ 6 & −1 & 0 & 0 & 0 & 0 & 1 \end{aligned}

= D − A EIGENVALUES

[figure: 4; 2; 6; e; c; a; b; f; h; 5; g; 3; d; 1]

∂_{1}∂_{1}^{T} = 1 … 6 ; 1 ; ⋮ ; 6 e’vals 652210

∂_{1}^{T}∂_{1} = a … h ; a ; ⋮ ; h e’vals 65221000

∂_{1}^{T}∂_{1}(∂_{1}^{T}x) = ∂_{1}^{T}(∂_{1}∂_{1}^{T}x) = ∂_{1}^{T}(λx) = λ(∂_{1}^{T}x)

SIMPLICIAL COMPLEXES

[figure: 4; 2; 6; e; c; a; b; f; h; 5; g; 3; d; 1]

∂_{2}^{T} = \begin{aligned}& a & b & c & d & e & f & g & h \\ P & 1 & −1 & 0 & 0 & 0 & 1 & 0 & 0 \\ Q & 1 & 0 & −1 & 0 & 0 & 0 & 1 & 0 \end{aligned}

∂_{2}^{T}∂_{2} = \begin{aligned}& P & Q \\ P & 3 & 1 \\ Q & 1 & 3 \end{aligned} e’vals 42

∂_{2}∂_{2}^{T} = a … h ; a ; ⋮ ; h e’vals 42000000

LAPLACIAN

Defn: (1-dimensional) Laplacian

L_{1} = ∂_{1}^{T}∂_{1} + ∂_{2}∂_{2}^{T}.

But now note ∂_{1}∂_{2} = 0! (Because, for instance,

∂_{1}(∂_{2}(123)) = ∂_{1}(12 − 13 + 23)
= (1 − 2) − (1 − 3) + (2 − 3) = 0.)

So

(∂_{1}^{T}∂_{1})(∂_{2}∂_{2}^{T}) = (∂_{2}∂_{2}^{T})(∂_{1}^{T}∂_{1}) = 0

and so the non-zero eigenvectors of ∂_{1}^{T}∂_{1} are 0eigenvectors of ∂_{2}∂_{2}^{T} and vice versa. (Because

(∂_{2}∂_{2}^{T})x = (∂_{2}∂_{2}^{T})(∂_{1}^{T}∂_{1}x/λ) = 0.)

And then the multiset of eigenvalues of L_{1} is just the multiset union of the eigenvalues of ∂_{1}^{T}∂_{1} and ∂_{2}∂_{2}^{T}.

So, in example, e’vals of L_{1} are 65221 42 0

APPLICATIONS (eigenvalues of graphs)

If graph is “grid graph,” then Lx = λx is discrete version of (continuous) wave equation, using usual (continuous) Laplace operator (eigenvalues are notes of drum).

rank L = n − (#components ). So if graph is connected, then only one 0 eigenvalue (eigenvector is all 1’s vector). In fact, second smallest eigenvalue is “algebraic connectivity,” which is the right measure of connectivity sometimes. Also, number of 0 eigenvalues counts number of cycles (actually, dimension of vector space of cycles); this generalizes to higher dimensions.

In chemical applications, eigenvalues correlate with physical properties (sometimes better than more widely used adjacency matrix).

SHIFTED COMPLEXES

If F is a face of a shifted complex, then any new face you get by replacing a bigger vertex in F by a smaller vertex must also be in the complex.

[figure: 4; 2; 6; e; c; a; b; f; h; 5; g; 3; d; 1]

For example, because 25 is an edge, so is 13, 14, 15, 23, 24. And because 124 is a triangle, so is 123.

Note that this is not a total order; for instance 25 is incomparable to 16

MATROID COMPLEXES

Easiest way is to look at example, graphic matroid.

[figure: 1; 2; 3; 4; 5; 6]

Faces of (graphic) matroid complex are all sets of edges containing no cycles. (Note: vertices of complex are edges of original graph!)

1,2,3,4,5,6 12,13,…,56 123,124,…,356, [not 456] 1235, 1236, 1245, 1246, 1256, 1345, 1346, 1356, 2345, 2346, 2356

THEOREMS

(Kook-Reiner-Stanton ’00) eigenvalues of matroid complexes are integers (nice formula)

(D-Reiner ’02) eigenvalues of shifted complexes are integers (beautiful formula)

(D preprint ’03) eigenvalues of shifted complexes and matroid complexes satisfy the same recursion (deletion; contraction; error term = deletion mod contraction).