The Upper bound Spectral Theorem

The Upper bound Spectral Theorem

In my theorem telling that the k-th largest eigenvalue \lambda_k for the Kirchhoff Laplacian K of a finite simple graph satisfies the bound

\lambda_k \leq d_k + d_{k-1}

I use a lemma which generalizes the Andrson-Morley super symmetry result of 1985. That paper had provided a ground breaking upper bound for the spectral radius \lambda_n \leq d_n + d_{n-1}. The proof of that result is very simple if one has the idea: the Laplacian K is the divergence F^* of the gradient F. In other words K = F^T F. From linear algebra, we know that K_1 = F F^T has the same non-zero eigenvalues than K_0 = F^T F. While K_0 is the 0-form Laplacian acting on functions on vertices, K_1 is the 1-form Laplacian acting on functions on edges. The entry K_1(e,f) = \pm 1 if e,f are different edges which intersect and K_1(e,e)=2. The spectral radius of K_1 is of course the same than the spectral radius of K_0 and can be estimated from above by \max_{e \in E} \sum_{e \in E} |K_1(e,f)| \leq 2+ (d_n-1) + (d_{n-1}-1) = d_n+d_{n-1}. This is the Anderson-Morley proof which is the special case k=n of my theorem of May 2022. In order to prove the theorem, I use the Cauchy interlace theorem, induction and an upgrade of Anderson-Morley to principal sub-matrices of Kirchhoff matrices. A principal submatrix of a square matrix is obtained by deleting a few rows and corresponding columns of the matrix. I explained this upgrade either using Cauchy again or then using deformation. There is a more elegant way to see this again using super symmetry and I will make an other video on that: in a nutshell, we can extend the super symmetry result to Kirchhoff matrices of non-simple graphs with self-loops. A principal sub-matrix of a Kirchhoff matrix can always be interpreted as a Kirchhoff matrix of a non-simple graph. We still have K_0 = F^T F and have a super symmetric partner K_1 = F F^T for which we can estimate the spectral radius as d_n + d_{n-1} where d_k are the diagonal entries ordered in non-descending way. These diagonal entries can be understood as generalized vertex degrees. Every self-loop adds 1 to a diagonal. Seen in this way, the upgrade of Anderson-Morley has the same proof than the actual Anderson-Morley result from 1985. I will add this to the paper in the final version. In the youtube talk, I talked a bit about the proof which is essentially just a talk about some matrix algebra. I hope during the weekend to be able to talk about the multi-graph case.


The fact that F^T F and F F^T have the same non-zero eigenvalues can be seen from my generalized Cauchy-Binet formula which gives the coefficients of the characteristic polynomial of the product of F^T G of two arbitrary n \times m matrices F and G: (Journal version 2014 , ArXiv version 2013-2014)

\det(1+x F^T G) = \sum_{P} x^{|P|}\det(F_P) \det(G_P)\; \; \; (*)

Here P is a pattern, a sub-matrix indexed by finite subsets of \{ 1, \cdots, \min(m,n)\} of the same cardinality which also can be empty. The notation \det(F_P) is a minor. In the case, where P is the empty pattern, the minor is defined to be 1. It is in general useful to declare the determinant of a 0 \times 0 matrix to be 1. This works nicely also for say partitioned matrices. Note that my determinant formula (*) above could be massaged to get the characteristic polynomial by multiplying with x^{-n} to get \det(\lambda+F^T G) with \lambda= x^{-1}. In the case x=1 this is equal to \sum_P \det(F_P) \det(G_P)/ In the case F=G, this gives the Pythagorean identity \det(1+F^T F) = \sum_{P} \det(F_P)^2 which has as an application the Matrix forest theorem. An analog result deals with the pseudo determinant {\rm Det}(F^T G) = \sum_{|P|=k} \det(F_P) \det(F_Q) where k depends on F and G. The later is just a special case, dealing with the first non-zero entry in the characteristic polynomial as this is the pseudo determinant up to a sign. Now also this has a Pythagorean aspect. If F=G, then {\rm Det}(F^T F) = \sum_{|P|=k} \det(F_P)^2. In the case, where F is a square matrix, then the integer k is just the rank of F. That Pythagorean identity immediately implies the matrix tree theorem telling that the number of rooted spanning trees in a graph is the pseudo determinant of the Kirchhoff matrix K. In the case where F is a n \times m matrix and the rank is maximal k=min(m,n), then the formula \det(F^T G) = \sum_{|P|=k}  \det(F_P) \det(G_P) is the classical Cauchy-Binet result which one can find in many text books. In the case n=m=k, then this is the usual determinant product formula \det(F^T G) = \det(F) \det(G) which is always covered in any linear algebra course.

[I should add that (*) is quite a fantastic result as it is in an area of pure linear algebra, where 200 years of heavy research have been done. That no formula for the coefficients of the characteristic polynomial of a product of matrices have appeared is astounding and actually, I spent a lot of time trying to locate such a result (more time than actually finding and proving the theorem). The literature part is not an easy task as there are hundreds of linear algebra and matrix analysis books which cover Cauchy-Binet and because there are thousands of research articles on the subject. This is not just a result about a special class of matrices or some new structure which has been found in the 20th century; it is a result about a topic which is 200 years old (1812 is the date), where Cauchy and Binet independently found the first case and proved det(A B) = det(A) det(B) without having a notion of matrices yet (!) and which is under heavy investigation since, due to the vast amount of applicability of determinants and matrices in sciences. I myself got exposed to the history of Cauchy-Binet by a conversation with Shlomo Sternberg from 2007 and have tried to track down things a bit in 2009. Shlomo had been interested to locate the exact time when matrix multiplication first appeared. It was definitely past the introduction of determinants which origins from the 17th century (Seki and Leibniz independently). But matrix analysis only appeared in the 18th century. There is an article of Knobloch from 2013 which illuminates a bit the history. Leibniz has worked in particular in the case up to n=4 and saw recursive notions or properties like that that interchanging rows or columns changes the sign.]

In the case x=1, which was a case I had been particularly interested, one gets a Fredholm determinant \det(1+F^T G) and Fredholm determinants are especially dear to me as they behave nicely in infinite limits, because they lead to connection matrices which are unimodular. (By the way, Sajal Mukherjee and Sudip Bera have found an other, more elegant proof of the unimodularity theorem in 2018.) The formula (*) immediately implies that we can replace F and G with its transpose. While F^T G and G^T F almost trivially have the same eigenvalues as they are transposes of each other. The matrices F^T G and F G^T have different size and the fact that their non-zero eigenvalues agree is less trivial. Percy Deift wrote in 1978 an entire paper devoted to the applicability of this commutation formula. The formula appears for example in the theory of integrable systems (a topic I worked in my PhD thesis too, in particular with Toda systems which are discrete versions of KdV systems.). In quantum mechanics knows how to compute the spectrum of the quantum harmonic oscillator: if F = (D+X)/\sqrt{2} and F^T = (-D+X)/\sqrt{2} are the creation and annihilation operators, (where $\latex D f (x) = f'(x)$ is the differential operator giving the derivative related to the momentum operator P=-iD and Xf=xf is the position operator), then the Hamiltonian H = -D^2+X^2 = P^2+X^2 of the quantum harmonic oscillator can be written as H=F F^T -1/2=F^T F+1/2, the commutation formula for the quantum harmonic oscillator. Since F^T F and F F^T have the same non-zero eigenvalues, we can from the commutation formula see that the eigenvalues are 1/2+n, where n is a non-negative integer. Given the ground state exp(-x^2/2) one can get the other eigenfunctions by bootstrapping using the creation operator. The relation [F,F^T] = F^T F - F F^T=1 is a version of the canonical commuation relation like [Q,P] = i between momentum P and position Q. Note however that in our case where we deal with incidence matrices F of graphs, the matrices F are not square matrices if the number of vertices and edges are not the same. Still there is a quantum field aspect of calculus if one uses the N \times N matrix d which acts on all differential forms (all functions on simplices). Now d^2 = 0 and $(d^*)^2=0$ like for annihilation and creation operators. The operator D = d+d^* is the Dirac matrix which in the graph case again is a N \times N matrix where N is the number of complete subgraphs. Now L = D^2 = d d^* + d^* d is the Hodge Laplacian, which is block diagonal and which contains the form Laplacians as blocks. The first block is the Kirchhoff matrix K! McKean-Singer noticed a symmetry: the non-zero eigenvalues of the even forms are the non-zero eigenvalues of the odd forms. If one looks at the skeleton complex of a graph which only consists of vertices and edges (a castration of graphs which unfortunately has been performed in most textbooks of graph theory in the 20th century who consider graphs to be one-dimensional simplicial complexes. There is so much more to them!), then there the 0-form Laplacian K and the 1-form Laplacian K_1 have the same non-zero eigenvalues. This is well known in linear algebra. The matrices F^T F and F F^T always have the same non-zero eigenvalues. In the Laplacian case K = d^* d = div grad and K_1 =d d* is the 1-form Laplacian. In the Kirchhoff case, the operation which K performs is first mapping a 0-form into a 1-form and then pushing it back to be a 0-form. In the 1-form case, a 1-form is first pushed to be a 0-form and then back to be a 1-form. In general, if the lobotomy on graphs has not been done and the full Whitney complex has been taken, then the Laplacian on 1-forms is d_0 d_0^* + d_1^* d_1 since we have now two possibilities: we can apply the annihilation operator first to get to a 0-form then apply the creation operator to get a 1-form again. Or then, we can apply the creation operator to get a 2-form and then apply the annihilation operator to get back a 1-form.


The fact that the non-zero eigenvalues of the 0-form Laplacian K_0 = F^T F and the 1-form Laplacian K_1 = F F^T are the same is a special case of McKean-Singer super symmetry. I talked about this a lot in this blog or youtube videos too but there is a completely analog Hodge theory in the graph case than in the continuum. Define differential forms as functions on simplices and define exsterior derivatives as Poincare or Betti did but write this exterior derivative d as a N \times N matrix if N is the number of simplices (=complete subgraphs = cliques) in the graph. Now D=d+d^* is the Dirac operator of the graph. [ By the way, it is a bit vexing why the founders of algebraic topology have only looked at the individual incidence matrices and not the full matrix D=d+d^*. If yes, Hodge theory could have been invented much earlier. Atiyah showed how explosive the mix of Hodge theory and Dirac theory can become. He has mused once in a talk how lucky he was that Hodge and Dirac who were office neighbors in the same department but rarely talked to each other, allowing him to take these explosive ingredients and combine them to explosions like the Atiyah-Singer index theorem.] Now L = D^2 = (d+d^*)^2 = d d^* + d^* d is the Hodge Laplacian. This is a block diagonal matrix. If K_k are the blocks, then the nullity of K_k is the k’th Betti number. The kernel of K_k, the space of harmonic k-forms is the k-th cohomology group of the graph. Of course, if G has as a geometric realization a smooth manifold, then these is the cohomology of the manifold. The McKean-Singer supersymmetry result deals with the operator K^{even} = \oplus_{k even} K_k and K^{odd} = \oplus_{k odd} K_k. Let \sigma_+(A) denote the set of non-zero eigenvalues of a matrix A. This is the non-zero spectrum. The McKean-Singer super symmetry assures

\sigma_0(L^{even}) = \sigma_0(L^{odd})

This implies {\rm str}(L^m) = 0 for all $m$, where str is the super trace. The Euler characteristic \chi(G) of the graph is \chi(G) = str(1). The McKean-Singer formula is now

\chi(G) = {\rm str}(\exp(-t L))

The above mentioned fact that the non-zero eigenvalues of K_0 and K_1 agree is the McKean-Singer super symmetry in the case when dealing only with a simplicial complexes which are one-dimensional.