4. Laplacian Matrices

We have that \[ \bs{Q}(i, j) = \bs{M}(i, :) \bs{M}^T(:, j) = \sum_{k=1}^m \bs{M}(i, k)\bs{M}^T(k,j) = \sum_{k=1}^m \bs{M}(i, k)\bs{M}(j, k) \] If \(i=j\) then \[ \bs{Q}(i, i) = \sum_{k=1}^m \bs{M}(i, k)\bs{M}(i, k) = \sum_{k=1}^m\bs{M}(i,k) = \deg(v_i). \] On the other hand, if \(i\neq j\) then \(\bs{Q}(i, j)\) is the product of the \(i\)th row and the \(j\)th row of \(\bs{M}\), and the only possibly non-zero product is when \(\bs{M}(i,:)\) and \(\bs{M}(j,:)\) have a non-zero entry in the same column, which corresponds to \(v_i\) and \(v_j\) incident with the same edge.

The proof is similar to the that of the signless Laplacian matrix. That \(\bs{L}\) is independent of the orientation follows since \(\bs{D}\) and \(\bs{A}\) are independent of any orientation.

Since \(\bs{Z}\) is symmetric, there exists an orthonormal basis \(\bs{x}_1,\bs{x}_2,\ldots,\bs{x}_n\) of \(\real^n\) consisting of eigenvectors of \(\bs{Z}\). Thus, \(\bs{x}_i^T\bs{x}_j=0\) if \(i\neq j\) and \(\bs{x}_i^T\bs{x}_i^T=1\). Let \(\lambda_1,\lambda_2,\ldots,\lambda_n\) denote the corresponding eigenvalues, that is, \(\bs{Z}\bs{x}_i = \lambda_i \bs{x}_i\). Suppose that \(\bs{Z}\) is positive definite (the proof for positive semi-definiteness is identical). Then \(\bs{x}^T\bs{Z}\bs{x} \gt 0\) for all non-zero \(\bs{x}\). Now, \[ \bs{x}_i^T \bs{Z} \bs{x}_i = \bs{x}_i ^T (\lambda_i \bs{x}_i) = \lambda_i \bs{x}_i^T \bs{x}_i = \lambda_i \] Therefore, \(\lambda_i = \bs{x}_i^T \bs{Z}\bs{x}_i \gt 0\) is positive. This shows that if \(\bs{Z}\) is positive definite then all eigenvalues of \(\bs{Z}\) are positive. Conversely, suppose that \(\bs{Z}\) has all positive eigenvalues and let \(\bs{x}\) be an arbitrary non-zero vector. Since \(\bs{x}_1,\bs{x}_2,\ldots,\bs{x}_n\) is a basis for \(\real^n\), there are constants \(c_1,\ldots,c_n\), not all zero, such that \(\bs{x}=c_1\bs{x}_1+c_2\bs{x}_2+\cdots+c_n\bs{x}_n\). Then, \[ \bs{x}^T \bs{Z} \bs{x} = c_1^2\lambda_1+c_2^2\lambda_2+\cdots+c_n^2\lambda_n \] and since at least one \(c_i\) is non-zero and all eigenvalues are positive, we conclude that \(\bs{x}^T\bs{Z}\bs{x} \gt 0\).

Recall that \(\bs{L}\bs{e}=\bs{0}\) and thus \(\bs{e}^T\bs{L}\bs{e}=0\). Now, by definition of \(\bs{L}\), for any vector \(\bs{x}\) we have \[ \bs{x} ^T\bs{L} \bs{x} = \bs{x}^T \bs{N} \bs{N}^T \bs{x} = (\bs{N}^T \bs{x})^T \cdot (\bs{N}^T \bs{x}) = \| \bs{N}^T\bs{x} \|^2 \geq 0. \] We conclude that \(\bs{x}^T \bs{L} \bs{x} \geq 0\) for all \(\bs{x}\), and therefore \(\bs{L}\) is positive semi-definite. The proof for \(\bs{Q}\) is identical.

We first recall that \(\bs{e}\) is an eigenvector of \(\bs{L}\) with eigenvalue \(\mu_1=0\). Suppose that \(G=G_1\oplus G_2\oplus \cdots\oplus G_k\). For any vector \(\bs{x}\) we have \[ \bs{x}^T \bs{L} \bs{x} = \bs{x}^T\bs{N}\bs{N}^T\bs{x} = \|\bs{N}^T\bs{x}\|^2 = \sum_{v_iv_j\in E} (x_i - x_j)^2. \] Since \(E(G) = E(G_1)\sqcup E(G_2)\sqcup \cdots \sqcup E(G_k)\) (where \(\sqcup\) denotes disjoint union) we can write \[ \bs{x}\bs{L}^T\bs{x} = \sum_{v_iv_j\in E(G_1)} (x_i - x_j)^2 + \sum_{v_iv_j\in E(G_2)} (x_i - x_j)^2 + \cdots + \sum_{v_iv_j\in E(G_k)} (x_i - x_j)^2 \] Suppose now that \(\bs{L}\bs{x}=\bs{0}\), that is, \(\bs{x}\) is an eigenvector of \(\bs{L}\) with eigenvalue \(\mu_1\). Then \(\bs{x}^T\bs{L}\bs{x} = 0\) and from our computation above we deduce that \(\sum_{v_iv_j\in E(G_a)} (x_i - x_j)^2 = 0\) for each component \(G_a\) of \(G\). Hence, the entries of \(\bs{x}\) are equal on each component of \(G\). If \(G\) is connected then \(\bs{x}\) has all entries equal and thus \(\bs{x}\) is a multiple of \(\bs{e}\). This proves that the geometric multiplicity, and thus the algebraic multiplicity, of \(\mu_1\) is one and thus \(\mu_1\) is a simple eigenvalue. Conversely, assume that \(G\) is disconnected with components \(G_1, G_2, \ldots, G_k\) where \(k\geq 2\), and let \(n=|V(G)|\). Let \(\bs{z}_i \in\real^n\) be the vector with entries equal to 1 on each vertex of component \(G_i\) and zero elsewhere. Then \(\bs{N}^T \bs{z}_i = \bs{0}\) and therefore \(\bs{L}\bs{z}_i = \bs{N}\bs{N}^T \bs{z}_i = \bs{0}\). Since \(\bs{z}_1, \bs{z}_2, \ldots, \bs{z}_k\) is a linearly independent set of vectors, this proves that the multiplicity of \(\mu_1\) is at least \(k\). However, since each component \(G_i\) is by definition connected and we have proved that a connected graph has \(\mu_1\) as a simple eigenvalue, \(\mu_1\) has algebraic multiplicity exactly \(k\).

As in the proof for the Laplacian matrix, for any \(\bs{x}\in\real^n\) we have \[ \bs{x}^T\bs{Q}\bs{x} = \bs{x}^T\bs{M}\bs{M}^T\bs{x} = \|\bs{M}^T \bs{x}\|^2 = \sum_{v_iv_j\in E} (x_i + x_j)^2. \] Suppose that \(\bs{x}=(x_1,x_2,\ldots,x_n)\) is an eigenvector of \(\bs{Q}\) with eigenvalue \(q_1=0\). Then \(\bs{x}^T\bs{Q}\bs{x}=0\) and therefore \(x_i = -x_j\) for every edge \(v_iv_j\in E\). Let \(C_1 = \set{v_i\in V \;|\; x_i \gt 0}\), \(C_2 = \set{v_j\in V\;|\; x_j \lt 0}\), and \(C_3 = \set{v_k\in V\; |\; x_k = 0}\). Since \(\bs{x}\) is a non-zero vector, \(C_1\) and \(C_2\) are non-empty, and moreover \(C_1\cap C_2=\emptyset\). Any vertex in \(C_3\) is not adjacent to any vertex in \(C_1\) or \(C_2\). Indeed, if \(v_k \in C_3\) and \(v_k\sim v_i\) then necessarily \(0=x_k=-x_i=0\) and thus \(v_i\in C_3\). Since \(G\) is connected this implies that \(C_3=\emptyset\). This proves that \(C_1\) and \(C_2\) is a partition of \(V(G)\). Moreover, if \(v_iv_j\in E\) and \(v_i \in C_1\) then necessarily \(v_j \in C_2\), and vice-versa. This proves that \(\set{C_1,C_2}\) is a bipartition of \(G\), and thus \(G\) is bipartite. Now suppose that \(G\) is bipartite and let \(\set{X,Y}\) be a bipartition of \(G\). Let \(\alpha\neq 0\) and let \(\bs{x}\) be the vector whose entries on \(X\) are \(\alpha\) and on \(Y\) are \(-\alpha\). Thus, if \(\bs{M}\) denotes the incidence matrix of \(G\) then \(\bs{M}^T \bs{x} = \bs{0}\). Therefore \(\bs{Q}\bs{x} = \bs{M}\bs{M}^T\bs{x} = \bs{0}\) and thus \(\bs{x}\) is an eigenvector of \(\bs{Q}\) with eigenvalue \(q_1=0\). Now suppose that \(\bs{z}\) is another eigenvector of \(\bs{M}\) with eigenvalue \(q_1\). Then \(\bs{M}\bs{z}=\bs{0}\) implies that \(z_i = -z_j\) for \(v_iv_j\in E\). Since \(G\) is connected, \(\bs{z}\) is completely determined by its value at \(i\) since there is a path from \(v_i\) to any vertex in \(G\). Thus \(\bs{z}\) is a multiple of \(\bs{x}\), and this proves that \(q_1=0\) is a simple eigenvalue.

If \(G\) has a spanning tree \(H\) then clearly \(G\) is connected since any path in \(H\) is a path in \(G\). Now suppose that \(G\) is connected. If \(|E(G)| = 2\) then \(G=P_2\) and then clearly \(G\) has a spanning tree. Assume that every connected graph with \(m\geq 2\) edges has a spanning tree. Let \(G\) be a connected graph with \(m+1\) edges. If \(G\) is a tree we are done so suppose \(G\) is not a tree. Pick any cycle \(C_k\) in \(G\) and delete any edge \(e\) in \(C_k\). Then \(G-e\) is connected and has \(m\) edges. By induction, \(G-e\) has a spanning tree, say \(H\), and \(H\) is then a spanning tree for \(G\).

Using the fact that \(\det(\bs{L}) = 0\) and \eqref{eqn:cof} we obtain \(\bs{L} \cof(\bs{L})^T = \det(\bs{L})\bs{I} = \bs{0}\). Suppose that \(G\) is connected. Then any vector in the kernel of \(\bs{L}\) is a multiple of \(\bs{e}\). Now since \(\bs{L}\cof(\bs{L})^T = \bs{0}\), it follows that each row of \(\cof(\bs{L})\) is a multiple of the all ones vector \(\bs{e}\), i.e., each row of \(\cof(\bs{L})\) is constant. Since \(\cof(\bs{L})\) is symmetric, this implies that \(\cof(\bs{Z})\) is a constant matrix, i.e., \(\cof(\bs{L}) = \tau(G) \bs{J}\) for some integer \(\tau(G)\). If \(G\) is disconnected, then the kernel of \(\bs{L}\) is at least two-dimensional and therefore \(\text{rank}(\bs{L})\leq n-2\). This implies that every cofactor of \(\bs{L}\) is zero. Hence, in this case \(\tau(G) = 0\).