15.1 LU Factorization without Pivoting

#Type/Definition #Topic/Linear_Algebra

Types: N/A
Examples: 15.2 Review of Nonsingular Gravity Model, 15.3 4-by-4 LU Factorization
Constructions: N/A
Generalizations: N/A

Properties: N/A
Sufficiencies: N/A
Questions: N/A

LU Factorization without Pivoting

Let $A \in R^{n \times n}$ be a "given" 12.3 Regular Matrix with non-zero values on the main diagonal elements. An LU factorization of $A$ is given by

A = L U

$L \in R^{n \times n}$ is a 8.8 Unit Lower-Triangular Matrix with all of its diagonal entries equal to 1.
$U \in R^{n \times n}$ is an 8.9 Upper-Triangular Matrix with nonzero diagonal elements.

Remark. LU factorization can be thought of as turning a regular matrix into the product of an upper-triangular and lower-triangular matrix.
$⧫$

Remark. Using 8.4 Special Sparsity Notation, we can visualize LU factorization.

\underset{A}{\underset{⏟}{[\begin{matrix} \times & \times & \dots & \times \\ \times & \times & \dots & \times \\ ⋮ & ⋮ & ⋱ & \times \\ \times & \times & \dots & \times \end{matrix}]}} = \underset{L}{\underset{⏟}{[\begin{matrix} 1 \\ \times & 1 \\ ⋮ & ⋱ & ⋱ \\ \times & \dots & \times & 1 \end{matrix}]}} \underset{U}{\underset{⏟}{[\begin{matrix} ⋆ & \times & \dots & \times \\ ⋆ & ⋱ & ⋮ \\ ⋱ & \times \\ ⋆ \end{matrix}]}}

$⧫$

Lemma

If $A, B$ are nonsingular, then $A B$ is nonsingular and

(A \cdot B)^{- 1} = B^{- 1} \cdot A^{- 1} ⟺ (A \cdot B) \cdot (A \cdot B)^{- 1} = I_{n}

Consider:

\begin{aligned} (A \cdot B) \cdot (B^{- 1} \cdot A^{- 1}) & = A \cdot (B \cdot B^{- 1}) A^{- 1} \\ = A \cdot I_{n} \cdot A^{- 1} \\ = A \cdot A^{- 1} \\ = I_{n} ⟹ (A \cdot B)^{- 1} = B^{- 1} \cdot A^{- 1} \end{aligned}