4. Laplacian Matrices

We have that $$ If $$ then $$ On the other hand, if $$ then $$ is the product of the $$th row and the $$th row of $$, and the only possibly non-zero product is when $$ and $$ have a non-zero entry in the same column, which corresponds to $$ and $$ incident with the same edge.

The proof is similar to the that of the signless Laplacian matrix. That $$ is independent of the orientation follows since $$ and $$ are independent of any orientation.

Since $$ is symmetric, there exists an orthonormal basis $$ of $$ consisting of eigenvectors of $$. Thus, $$ if $$ and $$. Let $$ denote the corresponding eigenvalues, that is, $$. Suppose that $$ is positive definite (the proof for positive semi-definiteness is identical). Then $$ for all non-zero $$. Now, $$ Therefore, $$ is positive. This shows that if $$ is positive definite then all eigenvalues of $$ are positive. Conversely, suppose that $$ has all positive eigenvalues and let $$ be an arbitrary non-zero vector. Since $$ is a basis for $$, there are constants $$, not all zero, such that $$. Then, $$ and since at least one $$ is non-zero and all eigenvalues are positive, we conclude that $$.

Recall that $$ and thus $$. Now, by definition of $$, for any vector $$ we have $$ We conclude that $$ for all $$, and therefore $$ is positive semi-definite. The proof for $$ is identical.

We first recall that $$ is an eigenvector of $$ with eigenvalue $$. Suppose that $$. For any vector $$ we have $$ Since $$ (where $$ denotes disjoint union) we can write $$ Suppose now that $$, that is, $$ is an eigenvector of $$ with eigenvalue $$. Then $$ and from our computation above we deduce that $$ for each component $$ of $$. Hence, the entries of $$ are equal on each component of $$. If $$ is connected then $$ has all entries equal and thus $$ is a multiple of $$. This proves that the geometric multiplicity, and thus the algebraic multiplicity, of $$ is one and thus $$ is a simple eigenvalue. Conversely, assume that $$ is disconnected with components $$ where $$, and let $$. Let $$ be the vector with entries equal to 1 on each vertex of component $$ and zero elsewhere. Then $$ and therefore $$. Since $$ is a linearly independent set of vectors, this proves that the multiplicity of $$ is at least $$. However, since each component $$ is by definition connected and we have proved that a connected graph has $$ as a simple eigenvalue, $$ has algebraic multiplicity exactly $$.

As in the proof for the Laplacian matrix, for any $$ we have $$ Suppose that $$ is an eigenvector of $$ with eigenvalue $$. Then $$ and therefore $$ for every edge $$. Let $$, $$, and $$. Since $$ is a non-zero vector, $$ and $$ are non-empty, and moreover $$. Any vertex in $$ is not adjacent to any vertex in $$ or $$. Indeed, if $$ and $$ then necessarily $$ and thus $$. Since $$ is connected this implies that $$. This proves that $$ and $$ is a partition of $$. Moreover, if $$ and $$ then necessarily $$, and vice-versa. This proves that $$ is a bipartition of $$, and thus $$ is bipartite. Now suppose that $$ is bipartite and let $$ be a bipartition of $$. Let $$ and let $$ be the vector whose entries on $$ are $$ and on $$ are $$. Thus, if $$ denotes the incidence matrix of $$ then $$. Therefore $$ and thus $$ is an eigenvector of $$ with eigenvalue $$. Now suppose that $$ is another eigenvector of $$ with eigenvalue $$. Then $$ implies that $$ for $$. Since $$ is connected, $$ is completely determined by its value at $$ since there is a path from $$ to any vertex in $$. Thus $$ is a multiple of $$, and this proves that $$ is a simple eigenvalue.

If $$ has a spanning tree $$ then clearly $$ is connected since any path in $$ is a path in $$. Now suppose that $$ is connected. If $$ then $$ and then clearly $$ has a spanning tree. Assume that every connected graph with $$ edges has a spanning tree. Let $$ be a connected graph with $$ edges. If $$ is a tree we are done so suppose $$ is not a tree. Pick any cycle $$ in $$ and delete any edge $$ in $$. Then $$ is connected and has $$ edges. By induction, $$ has a spanning tree, say $$, and $$ is then a spanning tree for $$.

Using the fact that $$ and $$ we obtain $$. Suppose that $$ is connected. Then any vector in the kernel of $$ is a multiple of $$. Now since $$, it follows that each row of $$ is a multiple of the all ones vector $$, i.e., each row of $$ is constant. Since $$ is symmetric, this implies that $$ is a constant matrix, i.e., $$ for some integer $$. If $$ is disconnected, then the kernel of $$ is at least two-dimensional and therefore $$. This implies that every cofactor of $$ is zero. Hence, in this case $$.