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?



1 Answer 1


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})$.

  • $\begingroup$ Thank you. Do you know how to prove this? It would be enough if you could please send me a reference where I could see the proof. $\endgroup$
    – James
    Sep 24, 2014 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.