Question

Question 8: Use Exercise 7 to show that if A is positive definite, then A has a LU factorization, \(A = LU\), where U has positive pivots on its diagonal. (The converse is true, too).

Short answer

It is proved that A has a LU factorization \(A = LU\).

Step-by-step solution

QR factorization

Theorem 12 in section 6.4states that when \(A\) is a \(m \times n\) matrix that islinearly independent columns, then \(A\) may be factored as \(A = QR\), with \(Q\) is a \(m \times n\) matrix wherein columns provide an orthonormal basisfor \({\mathop{\rm Col}\nolimits} A\), and \(R\) is an \(n \times n\) upper triangular invertible matrix which has positive entries on its diagonal.

Show that if A is positive definite, then A has a LU factorization \(A = LU\)

Assume that \(A\) is positive definite, and suppose that Cholesky factorization of \(A = {R^T}R\) where \(R\) is an upper triangular and having positive diagonal entries. Consider that \(D\) as the diagonal matrix with diagonal entries equal to diagonal entries of \(R\). The matrix \(L = {R^T}{D^{ - 1}}\) is lower triangular wherein 1’s on its diagonal because right-multiply by a diagonal matrix scales the columns of the matrix on its left.

When \(U = DR\) then \(A = {R^T}{D^{ - 1}}DR = LU\).

Conversely, consider that A contains a LU factorization, that is \(A = LU\), where \(U\) contains positive pivots on its diagonal. Consider \(D\) as the diagonal matrix and \(\sqrt {{u_{11}}} , \ldots ,\sqrt {{u_{nn}}} \) on its diagonal. The matrix \(V = {\left( {{D^2}} \right)^{ - 1}}U\) is upper triangular wherein 1’s on its diagonal because multiply by a diagonal matrix on its left scales the rows of the matrix on its right and we obtain \(A = L{D^2}V\). As \(A\) is symmetric, then \({A^T} = {\left( {L{D^2}V} \right)^T} = {V^T}{D^2}{L^T} = A\), and \(L = {V^T}\). When \(R = DV = {D^{ - 1}}U\) then \(A = {V^T}DDV = {\left( {DV} \right)^T}\left( {DV} \right) = {R^T}R\).

Hence, it is proved that A has a LU factorization \(A = LU\).