Gauss Transform with $LU$ factorization

Consider a symmetric matrix $A$, i.e. $A = A^T$.

a.) Consider the use of Gauss Transforms to factor $A = LU$ where $L$ is unit lower triangular and $U$ is upper triangular. You may assume that the factorization does not fail. Show that $A = LDL^T$ where $L$ is unit lower triangular and $D$ is matrix with nonzeros on the main diagonal.

b.) For an arbitrary factorization matrix the $LDL^T$ factorization will not always exist due to the possibility of $0$ in the $(i,i)$ position of the transformed matrix that defines the $i$-th Gauss transform. Suppose, however that $A$ is positive definite symmetric matrix,i.e., $x^tAx > 0$ for any vector $x\neq 0$. Show that the diagonal element of the transformed matrix $A$ that is used to define the vector $l_i$ that determines the Gauss transform on step $i$, $M_i^{-1} = I - l_ie_i^{T}$, is always positive and therefore the factorization will not fail. Combine this with the existence of the $LDL^T$ factorization to show that, in this case, the nonzero elements of $D$ are in fact positive.

Solution a.) Define $$A = LU = LD\tilde{U}$$ where $L$ is unite lower triangular, $D$ is a matrix with nonzeros on the main diagonal, and $\tilde{U}$ is unit upper triangular. Since $A$ is symmetric we have $$A = LD\tilde{U} = A^T = \tilde{U}^T D L^T$$ multiply $L^{-1}$ and $(L^T)^{-1}$ to both sides and we get $$D\tilde{U}(L^T)^{-1} = L^{-1}\tilde{U}^T D$$ The left side is upper triangular and the right side is lower triangular this implies that for them to be equal, both have to be diagonal. Since all of the triangular matrices are unit triangular it follows that the diagonal matrix $D$ has to be itself. Therefore we have $$D = D\tilde{U}(L^T)^{-1}$$ thus multiplying this by $L^T$ we get $$DL^T = D\tilde{U}$$ and we have $$A = LD\tilde{U} = LDL^T$$

Solution b.) (As suggested by AJ) Assume $A = LU$ exists and denote by subscripts $k$ the $k\times k$ leading submatrix. Then $A_k = L_k U_k$ and hence $$\det(A_k) = \det(L_k)\det(U_k) = \det(U_k) = d_1 d_2\ldots d_k$$ In other words, the product of the first $k$ pivots for Gaussian elimination. Now assume $\det(A_k)\neq 0$ for $1\leq k \leq n-1$ then $A_k$ is singular. After $k$ steps of Gaussian elimination we have $$M^{-1}_{k},\ldots M^{-1}_{1}A_{1}^{(1)} = U_{k}$$ Not really sure where to go from here...

• What is a Gauss Transform? I've personally never heard of it, and looking online didn't reveal anything particularly relevant. – NoseKnowsAll Jul 2 '16 at 23:44
• @NoseKnowsAll Apologies, the Gauss transform is just the Gauss transform matrix $M$, i.e. $M$ is used to perform the Gaussian elimination method. For example $M_{n-1}^{-1},\ldots,M_{1}^{-1}A = U$ – Wolfy Jul 3 '16 at 0:09
• You cannot start the proof with assuming that $LU$ factorization exists if you wish to prove that it exists. It sounds weird, don't you think so? Look at $4\times 4$ case. If the first column elimination is possible then look at the determinant positivity and conclude that the second column pivot is not zero. Continue by induction. – A.Γ. Jul 8 '16 at 13:54

Solution a) looks right, but can be simplified. Just taking $A=LU$ and pre and post-multiplying as you did gives $$L^{-1}AL^{-T}=UL^{-T}.$$ LHS is symmetric while RHS is upper-triangluar, hence, it is a diagonal matrix. Call it $D$.

Hint for Solution b): Denote by subscript $k$ the $k\times k$ leading principal submatrix. Assume $A=LU$ exists. Then $A_k=L_kU_k$ and, hence, $\det A_k=\det U_k=d_1d_2\ldots d_k$, i.e. the product of the first $k$ pivots for Gauss eliminations. Use induction to prove that if all $\det A_k$ for $k=1$ to $n-1$ are nonzero then $LU$ factorization is possible. Then use the fact that a positive definite matrix $A$ must have all $A_k$ positive definite too, thus, $\det A_k\ne 0$.

1. Lemma: if $\det A_k\ne 0$ for $1\le k\le n-1$ then $A=LU$ exists. Proof: $\det A_1=a_{11}\ne 0$ then it is possible to eliminate the first column. Now assume that you have eliminated first $k$ columns. Look at the matrices you have got at the step $k$. You may look at the case $n=4$, but just to understand what happens in general. When you've understood that, you consider the general case and conclude from the matrix structure that even after $k$ steps of the partial Gauss elimination it holds $A_{k+1}=L_{k+1}U_{k+1}$, which leads (from the relation above) to the $d_{k+1}$ pivot being nonzero, thus, next column elimination is possible. It is called the mathematical induction.
2. If $A$ is pos. def. then by definition for all $z=[x\ \ y]^T\ne 0$ $$z^TAz= \begin{bmatrix} x^T & y^T \end{bmatrix} \begin{bmatrix} A_k & *\\* & * \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}>0.$$ Now set $y=0$ to obtain the definition of $A_k$ being pos. def. Finally, if $A$ pos. def. then $\det A\ne 0$. Proof: assume that $\det A=0$, then there exists $x\ne 0$ such that $Ax=0$ $\Rightarrow$ $x^TAX=0$, contradiction!
• why is the $\det(A_k) = \det(U_k)$? – Wolfy Jul 3 '16 at 15:48
• @Wolfy $\det (A_k)=\det(L_k)\det(U_k)$, but $L_k$ diagonal with identities on the main diagonal, thus $\det(L_k)=1$. – A.Γ. Jul 3 '16 at 17:53
• Right, sorry needed my morning coffee, I knew that. Now we need to show that for $k = 1$ to $k = n-1$ that the $\det(A_k)$ is nonzero, thus proving it is nonsingular. Then since $A$ is a symmetric positive definite matrix then so is $A_k$ and therefore the factorization will not fail? – Wolfy Jul 3 '16 at 18:01
• @Wolfy Yes. You need to prove two lemmas: if all $\det A_k\ne 0$ then $LU$ factorization exists. It is proved by induction: do Gauss elimination up to the step $k$ and then use the determinant relation above to see that the next pivot is nonzero. The second lemma is basically an easy implication of the Sylvester criterion: from positive-definite to $\det A_k>0$. It can be proved by definition of positive-definiteness $x^TAx>0$, just set the tail of $x$ to zero. – A.Γ. Jul 3 '16 at 18:09
• I see, should I use an example for say $n = 4$ to do the Gaussian elimination up to step $k$? I am not exactly sure how to perform Gaussian elimination on an arbitrary matrix unless I just define one. Couldn't I just say that the $\det(A_k)$ is nonzero since $A$ is a symmetric positive definite? I guess I am still a little confused on how to solve this problem. – Wolfy Jul 3 '16 at 18:16