I was reading a graph theory by Adrian Bondy and U S R Murty. In this textbook it is mentioned that for a simple finite graph $G,$ the Laplacian matrix $\mathbf{L}$ is a square symmetric matrix which is always positive semidefinite. Further the algebraic multiplicity of its zero eigenvalue equals the number of connected components of $G.$ In particular, if $G$ is connected, then the eigenvalue zero appears only once and remaining all other eigenvalues are positive. Further $\mathbf{L}$ is always diagonalizable as it is symmetric. Moreover $\mathbf{L}=\mathbf{UDU}^T,$ where $\mathbf{U}$ is an orthogonal matrix whose columns are eigenvectors of $\mathbf{L},$ $\mathbf{D}$ is a diagonal matrix with principal diagonal entries are the eigenvalues of $\mathbf{L}$ which are all nonnegative, $\mathbf{UU}^T=\mathbf{U}^T\mathbf{U}=\mathbf{I},$ $\mathbf{U}^T=\mathbf{U}^{-1}.$
Further I verified the following with some examples.
(1). All other remaining positive eigenvalues in $\mathbf{L}$ are not necessarily distinct.
(2). If we remove any one row and corresponding column in $\mathbf{L},$ then the submatrix will have a determinant equals a positive integer which represents the number of spanning trees in $G.$ I got this submatrix is positive definite and all its positive eigenvalues are not necessarily distinct.
(3). I removed more than one row and corresponding columns in $\mathbf{L}$. The submatrix is still be positive definite and not necessarily have distinct positive eigenvalues.
(4). Now I considered the random walk normalized Laplacian matrix $\Delta^{-1}\mathbf{L},$ where $\Delta$ is the degree matrix of a connected graph $G,$ then $\Delta^{-1}\mathbf{L}$ need not be symmetric, but has one of its eigenvalue zero [since $\text{det}(\Delta^{-1}\mathbf{L})=(\text{det}(\Delta))^{-1}\text{det}(\mathbf{L})=0, \,\text{as}\, \mathbf{L}\, \text{is singular always}]$. Next I considered the submatrix in this random walk normalized Laplacian $\Delta^{-1}\mathbf{L}$ just like in (2) and (3), then again I got this submatrix is positive definite and not necessarily have distinct positive eigenvalues.
Now my questions are
(a). Does the submatrix in (2), (3) and (4) will always be positive definite?
(b). The algebraic multiplicity of the zero eigenvalue in $\Delta^{-1}\mathbf{L}$ represents what?
(c). The random walk normalized Laplacian $\Delta^{-1}\mathbf{L}$ will always be diagonalizable? (Note that $\mathbf{L}$ is always diagonalizable because of symmetricity.)
(d). What can be said about the diagonalizability of the submatrices chosen in (2), (3) and (4)?
Best Answer
For (a), yes, the matrices in (2) and (3) are positive definite (assuming $G$ was connected). They are easily seen to be PSD as any principal submatrix of a PSD matrix is also PSD; however, the matrix-tree theorem you cite implies the determinant submatrix in (2) is a positive integer as any connected graph has at least one spanning tree, so the matrix is PSD and nonsingular, therefore positive definite. This implies that the matrices in (3) are also positive definite by applying Cauchy's interlacing theorem. Of course, symmetry alone here implies diagonalizability.
The matrix in (4) is not positive semi-definite in the traditional sense as it is not symmetric, but nonethless is diagonalizable and has nonnegative eigenvalues (see (c)).
For (b), the algebraic multiplicity of the zero eigenvalue of $\Delta^{-1}\mathbf{L}$ is the same as the algebraic multiplicity of the zero eigenvalue of $\mathbf{L}$ (because assuming $G$ has no isolated vertices, $\Delta^{-1}$ is full-rank), which is equal to the number of connected components.
For (c), again, assuming no isolated vertices, then $\Delta^{-1}\mathbf{L}$ is similar to $\Delta^{-1/2}\mathbf{L}\Delta^{-1/2}$, which is easily seen to be PSD by inspecting the quadratic form and applying a change of variables. Thus, $\Delta^{-1}\mathbf{L}$ is similar to a diagonalizable matrix with nonnegative eigenvalues, so the same holds.
For (d), see the above answers.