1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Based on this answer I should be looking for "Hurwitz" criterion. $\endgroup$ – Greg Doyle Mar 10 '15 at 0:16
  • $\begingroup$ 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. $\endgroup$ – Greg Doyle Mar 10 '15 at 1:23
1
$\begingroup$

I've found an easier way to accomplish what I want.

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

$\endgroup$
0
$\begingroup$

I think I've found the answer. According to this source authored by James Carrell, UBC, page 67 - if a nonsingular matrix M has an LDU decomposition, then by row reducing M to an upper triangular matrix we will have DU. If we don't transpose any rows, then M will be row equivalent to DU, and hence their determinants will be the same.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Greg Doyle Mar 11 '15 at 15:48

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.