On the multiplicity of the eigenvalue 0 of the adjacency matrix?

Question

Preliminaries:
-Laplacian matrix of graph $G$ is defined as follows:
$$L=D-A $$ where $D$ is the degree matrix and $A$ is the adjacency matrix of the graph.

-The algebraic connectivity of a graph $G$ is the second-smallest eigenvalue of the Laplacian matrix of $G$.

It well known that the multiplicity of the eigenvalue 0 of the Laplacian matrix (or algebraic connectivity) is equal to the number of connected components in the graph.

Question:
Is there any significance for the multiplicity of the eigenvalue 0 of the adjacency matrix? In other words is there any relation with the parameters of the graph (like the independence number of the graph, number of connected components,...).

Any idea will be useful!

Answer 1

This question arises regularly. So far nobody has been to say anything useful about the multiplicity of zero in general. For special classes, there can be something. Thus for trees the multiplicity of zero is the number of vertices not covered by a matching of maximum size.

Answer 2

As Chris Godsil points out, the multiplicity of zero as an eigenvalue of the adjacency matrix of a tree does have a graph theoretic significance. It can be understood as follows:

The determinant of an matrix is a sum over all permutations (of, essentially, graph vertices), of a product of matrix entries. Every such permutation can be decomposed into disjoint cycles.

Suppose such a cycle is of length three or more. Then if we consider the matrix entries corresponding to the permuted elements in this cycle, at least one of them must be zero? Why? Because the matrix entries are nonzero only for graph edges. If all the entries were nonzero, this would correspond to a (graph) cycle of length three or more, which we know we don't have, because it's a tree.

Therefore, the product of the matrix element for the whole cycle (in the permutation sense) is zero. And therefore so is the product for the whole permutation.

So the determinant is a sum over permutations, where the permutation consists only of swapped pairs and fixed points. Furthermore, the swapped pairs must correspond to two vertices joined by an edge. Therefore, any such permutation is a collection of graph edges and isolated vertices. In other words, a partial matching of the graph.

Now, given such a permutation, what does the corresponding term of the determinant look like? Each edge contributes two factors, which are off-diagonal matrix entries, so both of them 1. Each fixed point or isolated vertex contributes a single entry from the diagonal of the matrix, in other words $-\lambda$. So the number of isolated vertices is the multiplicity of the root 0 for that particular term.

When all the terms are added the multiplicity of the root 0 is the minimum multiplicity of 0 in any of the individual terms (since no amount of terms 1 can produce a sum $\lambda$ or vice versa). So this gives the smallest number of isolated vertices in any graph matching.

From this result we can perhaps speculate on what this measure would tell us about a graph with cycles, if anything. For each such cycle we would have to add in additional terms to the characteristic polynomial where the permutation includes that cycle.