Suggested languages for you:

Americas

Europe

Q8SE

Expert-verified
Found in: Page 395

### Linear Algebra and its Applications

Book edition 5th
Author(s) David C. Lay, Steven R. Lay and Judi J. McDonald
Pages 483 pages
ISBN 978-03219822384

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

It is proved that A has a LU factorization $$A = LU$$.

See the step by step solution

## Step 1: QR factorization

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

## Step 2: 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$$.