# $LDL^T$ decompositon of a symmetric matrix and a matrix determinant expression for the lower triangular entries

Let $n$ be a positive integer, and let $M$ be an integral, symmetric, nonsingular matrix. As $M$ is nonsingular, there exists an $LDL^T$ decomposition such that $D = (d_j)$ is diagonal and $L=(\ell_{ij})_{i < j}$ is a unit lower triangular matrix. (We have adopted the convention that $i < j$ for notational convenience.)

For $j=1, \ldots, n$ we let $M_j$ denote the $j^{th}$ leading principal submatrix of $M$. Similarly, we let $m_j = \det(M_j)$ denote the $j^{th}$ leading principal minor of $M$. For convenience, we set $m_0 = 1$. For both $D$ and $L$ we let $D_j$ and $L_j$ denote the $j^{th}$ leading principal submatrix of these matrices, respectively.

Further, for $i < j$, we let $M_i[i,j]$ denote the $i^{th}$ leading principal submatrix of the matrix obtained by interchanging columns $i$ and $j$ in $M$.

For example, if $M=(t_{ij})$ then $M_2[2,3] = \left(\begin{array}{cc} t_{11} & t_{13}\\ t_{12} & t_{23}\end{array}\right)$ (where due to symmetry the matrix notation pertains only to the upper triangular entries.)

It is known that $L_j D_j (L_j)^T = M_j$. (See, e.g: http://heim.ifi.uio.no/~tom/luslides.pdf - slide 14.)

Hence, we may deduce that for $j=1, \ldots, n$; $\displaystyle d_j = \frac{m_j}{m_{j-1}}$.

In order to determine the $\ell_{ij}$'s, we may use forward substitution, Cholesky decomposition, etc...

However, I seem to have stumbled upon a more explicit determination which I cannot find a resource for, and which I cannot prove the general case.

I claim that, for $i < j$, we have that: $\displaystyle \ell_{ij} = \frac{\det(M_i[i,j])}{m_i}$.

Here is my approach for proving this:

Let $M=(t_{ij})$.

For $i < j$, consider the matrix \begin{eqnarray*} LD_i[i,j] = \left(\begin{array}{cccc} d_1 & 0 & \cdots & t_{1j}\\ \vdots & \ddots & 0 & \vdots\\ \vdots & & d_{i-1} & t_{i-1 j}\\ d_1 \ell_{1i} & \cdots & d_{i-1}\ell_{i-1 i} & t_{ij}\end{array}\right), \end{eqnarray*} that is, the $i^{th}$ leading principal submatrix of the matrix $LD$, where the $i^{th}$ column of $LD$ has been interchanged with the $j^{th}$ column from $M$. Hence, from Cramer's rule, and $(LD)L^T = M$ we deduce that \begin{eqnarray*} \ell_{ij} = \frac{\det(LD_i[i,j])}{m_j}. \end{eqnarray*} Hence, it remains to show that $\displaystyle \det(LD_i[i,j]) = \det(M_i[i,j])$. We may take the determinant of each of these matrices by expanding along the $i^{th}$ column. As the $i^{th}$ column is equal in both matrices, it suffices to show that for $1 \leq k \leq i$, the $(k,i)^{th}$ minor of each matrix is the same. As we are taking minors with respect to the $i^{th}$ column, it is also sufficient to show that $(k,i)^{th}$ minor of $LD_i$ is the same as the $(k,i)^{th}$ minor of $M_i$.

--

I'm not too sure how to proceed from here. I checked that this works manually up to a 4x4 matrix. Proving it inductively doesn't seem to work, as there's a bunch of cancellations that don't scale properly.

I'm quite confident my claim will hold, but I'm unable to find a proper resource which shows this. This claim results due to my research into quadratic forms, and most of the quadratic form literature is concerned with the spectral decomposition of $M$, rather than an $LDL^T$ decomposition.

Any source or avenue for proving my claim would be greatly appreciated! (Or a counter-example would work.)

• Based on this answer I should be looking for "Hurwitz" criterion. – Greg Doyle Mar 10 '15 at 0:16
• In a paper by Demmel, et. al. called "Computing the Singular Value Decomposition with High Relative Accuracy", there's a lemma that states that the lower triangular values are given as ratios of minors from M. I will look for the book this lemma is based on at the University library. It seems this is given somewhere, though not necessarily well known. – Greg Doyle Mar 10 '15 at 1:23

Start with the integral symmetric matrix $M$. For $i=1, \ldots, n-1$ we can row-reduce each row using only scalar multiplication (of an integer) and adding a multiple of one row to the other. We row reduce each row until we have an upper triangular matrix. (That is, start by row-reducing to eliminate entry (2,1); then move down to eliminate entries (3,1) and (3,2) in that order. The $i^{th}$ row reduction will see entry (i,1) eliminated, then (i,2), etc...up to entry (i,i-1).)
In this fashion, one will be left with an upper triangular matrix whose $i^{th}$ diagonal entry will be the $i^{th}$ leading principal minor. Continue in this fashion until $i=n$. At the final iteration, if the determinant of the form is 0, as each diagonal entry is known, we must have that the $n^{th}$ diagonal entry of $D$ is 0. As we know an $LDL^T$ decomposition exists, we can replace the $n^{th}$ diagonal position of our upper triangular matrix with 1. Otherwise, the $n^{th}$ diagonal position of our upper triangular matrix will be the determinant.
Due to our method of row-reduction, every strictly upper triangular entry will be an integer. We divide each row by the minor on the diagonal (or 1 in the $n^{th}$ position possibly.) This will yield a unit upper triangular matrix which, due to uniqueness, must be equal to $L^T$. Hence, every strictly upper triangular element in row $i$ will be a rational number with common denominator $m_i$.
• I don't know if this is accurate enough. We know that the determinants of $DU$ and $M$ will be the same, but this is redundant, as $DU$ is upper triangular, and the determinant is again the product of the diagonal entries. What we need is a way to guarantee the minors of two row-equivalent matrices will be the same. I think this should follow, but I will have to do a bit of work to make sure this is accurate – Greg Doyle Mar 11 '15 at 15:48