Matrix Algebra: Matrix Factorizations and the LU Factorization Method

Definition of Matrix Factorization: A factorization of a matrix $A$ is an equation that expresses $A$ as a product of two or more matrices.
Synthesis vs. Analysis of Data:
- Synthesis: Matrix multiplication involves the synthesis of data, combining the effects of two or more linear transformations into a single matrix.
- Analysis: Matrix factorization is considered an analysis of data, as it breaks down a complex matrix into simpler, constituent components.

Industrial and Business Application: The LU factorization is motivated by the common problem of solving a sequence of equations that all share the same coefficient matrix:
1. $Ax = b_{1}$
2. $Ax = b_{2}$
3. $\dots$
4. $Ax = b_{p}$
Efficiency Considerations:
- If $A$ is invertible, one theoretically could compute $A^{-1}$ and then calculate each $x = A^{-1}b$ .
- However, it is significantly more efficient to solve the first equation ( $Ax = b_{1}$ ) using row reduction and obtain the LU factorization of $A$ simultaneously.
- The remaining equations in the sequence ( $Ax = b_{2}$ through $Ax = b_{p}$ ) are then solved using the established LU factorization.

Structural Assumptions: Assume $A$ is an $m \times n$ matrix that can be reduced to echelon form without requiring any row interchanges.
The Factorization Equation: $A = LU$ .
Characteristics of the Matrices:
- Matrix L (Unit Lower Triangular): $L$ is an $m \times m$ lower triangular matrix. It is called a "unit lower triangular matrix" because it features $1$ 's on its main diagonal. Matrix $L$ is always invertible.
- Matrix U (Echelon Form): $U$ is an $m \times n$ matrix that represents an echelon form of $A$ .

Two-Step Process: When $A = LU$ , the equation $Ax = b$ can be rewritten as $L(Ux) = b$ . By substituting $y = Ux$ , the solution is found by solving two triangular systems:
1. Forward Substitution: Solve $Ly = b$ for $y$ .
2. Back Substitution: Solve $Ux = y$ for $x$ .
Computational Ease: Because both $L$ and $U$ are triangular matrices, these equations are computationally simple to solve.

Flop (Floating Point Operation): An arithmetic operation (addition, subtraction, multiplication, or division).
Example 1 Analysis:
- Solving $Ly = b$ : Requires only $6$ multiplications and $6$ additions, as arithmetic only occurs in column $5$ (the constants column).
- Solving $Ux = y$ : The "backward" phase of row reduction requires $4$ divisions, $6$ multiplications, and $6$ additions.
- Creating Zeros in Column 4: To create zeros in column $4$ of the augmented matrix for $Ux = y$ requires $1$ division in row $4$ and $3$ multiplication-addition pairs to adjust the rows above it.
- Total Cost to Find x: Finding $x$ using a pre-computed LU factorization requires a total of $28$ arithmetic operations.
- Comparison: Standard row reduction of the augmented matrix $[A \, b]$ takes $62$ operations. Thus, using LU factorization is significantly more efficient for solving systems.

Reduction Condition: Suppose $A$ can be reduced to an echelon form $U$ utilizing only row replacement operations (adding a multiple of one row to another row below it).
Elementary Matrices: In this scenario, there exist unit lower triangular elementary matrices $E_{1}, \dots, E_{p}$ such that: $E_{p} \dots E_{1}A = U$
Inversion and Product: The matrix $A$ can then be expressed as: $A = (E_{p} \dots E_{1})^{-1}U = LU$ Where: $L = (E_{p} \dots E_{1})^{-1}$
Properties of L: Because products and inverses of unit lower triangular matrices are themselves unit lower triangular, $L$ is guaranteed to be unit lower triangular.
Algorithm Steps:
1. Reduce $A$ to an echelon form $U$ by a sequence of row replacement operations (if possible).
2. Construct $L$ by placing entries such that the same sequence of row operations that reduced $A$ to $U$ would reduce $L$ to the identity matrix $I$ .

Example Problem: Find the LU factorization of $A = \begin{pmatrix} 2 & 4 & -1 & 5 & -2 \\ -4 & -5 & 3 & -8 & 1 \\ 2 & -5 & -4 & 1 & 8 \\ -6 & 0 & 7 & -3 & 1 \end{pmatrix}$
Determining L: Since $A$ has four rows, $L$ must be a $4 \times 4$ matrix.
- Column 1 of L: Take the first column of $A$ and divide it by the top pivot entry ( $2$ ). First Column of A: $\begin{pmatrix} 2 \\ -4 \\ 2 \\ -6 \end{pmatrix}$ . Divided by $2$ : $\begin{pmatrix} 1 \\ -2 \\ 1 \\ -3 \end{pmatrix}$ . These become the entries for the first column of $L$ .
Iterative Process: Highlight the entries in each matrix used to determine the row operations transforming $A$ to $U$ . At each pivot column, divide the entries below the pivot (including the pivot itself) by the pivot value and place the results in the corresponding column of $L$ .
Final Matrices:
- $L = \begin{pmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ 1 & -3 & 1 & 0 \\ -3 & 4 & 2 & 1 \end{pmatrix}$
- $U = \begin{pmatrix} 2 & 4 & -1 & 5 & -2 \\ 0 & 3 & 1 & 2 & -3 \\ 0 & 0 & 0 & 2 & 1 \\ 0 & 0 & 0 & 0 & 5 \end{pmatrix}$
Verification: Calculating the product $LU$ recovers the original matrix $A$ .