Consider an undirected graph $G$ with $N$ vertices and its adjacency matrix $n_{ij}$: $n_{ij} = 1$ if vertices $i$ and $j$ are connected by an edge and $n_{ij} = 0$ otherwise. Consider $A_{ij} \equiv \left(\sum_{k=1}^N n_{ik}\right)\delta_{ij} – n_{ij}$ and its LDL decomposition
\begin{equation}
A = L D L^T,
\end{equation}
where $L$ is lower triangular with unit on the diagonal, and $D$ is diagonal.
Suppose now that $G$ is connected: Then it can be shown that $A$ has only one zero eigenvalue, which we denote by $\lambda_1$, and that there is only one zero diagonal entry in $D$, which we denote by $D_{11}$. By diagonalizing $A$ numerically for multiple $G$s, I find heuristically that the following equation
\begin{equation}
\prod_{i=2}^N \lambda_i = N \prod_{i=2}^N D_i
\end{equation}
is numerically satistified.
Is this equation true in general? If it is, do you have any idea of how to prove it?
Thanks
Best Answer
More generally, the following appears to be true. Suppose $A$ is a real $N \times N$ symmetric matrix with rank $N-1$ and $A b = 0$ where $b \ne 0$. Let $A = LDL^T$ be the $LDL^T$ decomposition of $A$ (assuming no pivoting needed), and $d_1, \ldots, d_N$ the diagonal entries of $D$, where $d_N = 0$. If $c_1$ is the coefficient of $\lambda$ in the characteristic polynomial $\det(A - \lambda I)$of $A$, then $$c_1 = d_1 \ldots d_{N-1} \sum_{i=1}^N (b_i/b_N)^2 $$
EDIT: Here is a proof.
Let $L$ be a lower triangular matrix with diagonal entries $1$, $D$ a diagonal matrix with diagonal entries $d_1, \ldots, d_N$ where $d_N = 0$, and $A = L D L^T$. Then $b = (L^T)^{-1} e_N$ is in the null space of $A$, and $\sum_{i=1}^N b_i^2 = b^T b = (L^{-1} (L^T)^{-1} )_{NN} = \left((L^T L)^{-1}\right)_{NN}$. By Cramer's rule that is $\det(C_{NN})$, where $C_{NN}$ is the upper left $(N-1) \times (N-1)$ submatrix of $L^T L$ (note that $\det(L^T L) = (\det L)^2 = 1$). On the other hand, $b_N = 1$ (because $(L^T)^{-1}$ is upper triangular with $1$ on the diagonal).
Now by Sylvester's determinant theorem the characteristic polynomial of $A = L D L^T$ is also the characteristic polynomial of $D L^T L$. Since the last row of $D L^T L$ is $0$, we expand along the last row and find that the coefficient of $\lambda$ in the characteristic polynomial is the determinant of the upper left $(N-1) \times (N-1)$ submatrix of $D L^T L$. This submatrix is the product of the upper left $(N-1) \times (N-1)$ submatrices of $D$ and $L^T L$, so its determinant is the product of the determinants of those, namely $d_1 \ldots d_{N-1} \det(C_{NN})$.