# Is the bandwidth of indefinite A equal to its factor L in LDL^T?

In George, Liu, and Ng's book Computer Solutions of Sparse Linear Systems, it has been shown that bandwidth of $A$ is equal to bandwidth of its factors in $LL^T$.(section 4.3) However, I guess this is proven only for $LL^T$ factorization for positive definite matrices. Is there a similar proof for indefinite matrices for factors in $LDL^T$, where $D$ is a block-diagonal matrix with at most $2\times 2$ blocks and assuming that such a factorization exists?

It is generally true for the $LU$ factorization of any matrix that the bandwidth of the factors equals the bandwidth of the original matrix. In fact, the result is stronger: that the skyline of the factors is contained in the skyline of the original matrix. This is actually not all that difficult to see if you consider the steps one has to take to compute the $LU$ factorization, which are equivalent to the first half of Gaussian elimination.
So if you ask for an $LDL^T$ factorization of a symmetric and possibly indefinite matrix $A$: Your $LU$ factors are $LD^{1/2}$ and $D^{1/2}L^T$ for which the bandwidth is at most that of the original matrix $A$. Consequently, the same can be said about the matrix $L$ as well.
• Quick remark though: for an indefinite matrix the $LU$ or $LDL^T$ factorization could be unstable without some form of pivoting, and pivoting destroys the band structure. – Federico Poloni Nov 27 '14 at 9:51
• @Armut Yes. Pivoting will usually enlarge the bandwidth of $A$ (and so that of $L$). It is easy to find examples when this happens. – Federico Poloni Dec 4 '14 at 6:45