Matrix Factorization

Matrix factorization decomposes a matrix into simpler components to solve linear systems efficiently. At MathMultiverse, we dive into LU decomposition, a key technique for numerical linear algebra, with examples, visualizations, and applications in engineering and AI.

Why factorization? It reduces computational complexity for systems \( Ax = b \), enabling faster solutions for multiple \( b \)-vectors, crucial for simulations and data analysis.

LU Decomposition

LU decomposition expresses \( A = LU \), where \( L \) is lower triangular (unit diagonal) and \( U \) is upper triangular. For \( Ax = b \):

\[ LUx = b \]

Solve via:

  • Forward substitution: \( Ly = b \)
  • Back substitution: \( Ux = y \)

For \( A = \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} \):

\[ L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix}, \ U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}, \quad l_{21} = \frac{a_{21}}{a_{11}}, \quad u_{22} = a_{22} - \frac{a_{21} a_{12}}{a_{11}} \]

Pivoting (PA = LU) ensures stability. Complexity: \( O(n^3) \) for factorization, \( O(n^2) \) per solve.

Examples

2x2 System

For \( 2x + y = 5 \), \( x + 3y = 7 \), \( A = \begin{bmatrix} 2 & 1 \\ 1 & 3 \end{bmatrix} \), \( b = \begin{bmatrix} 5 \\ 7 \end{bmatrix} \):

\[ L = \begin{bmatrix} 1 & 0 \\ 0.5 & 1 \end{bmatrix}, \ U = \begin{bmatrix} 2 & 1 \\ 0 & 2.5 \end{bmatrix} \]

Solve \( Ly = b \): \( y = \begin{bmatrix} 5 \\ 4.5 \end{bmatrix} \). Solve \( Ux = y \): \( x = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \).

3x3 System

For \( A = \begin{bmatrix} 4 & -1 & 1 \\ -1 & 3 & -1 \\ 1 & -1 & 5 \end{bmatrix} \), \( b = \begin{bmatrix} 7 \\ 4 \\ 6 \end{bmatrix} \):

\[ L = \begin{bmatrix} 1 & 0 & 0 \\ -0.25 & 1 & 0 \\ 0.25 & -0.2857 & 1 \end{bmatrix}, \ U = \begin{bmatrix} 4 & -1 & 1 \\ 0 & 2.75 & -0.75 \\ 0 & 0 & 4.5714 \end{bmatrix} \]

Solve: \( x = \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix} \).

Matrix Condition Number

Visualizing condition number impact on numerical stability.

Applications

  • Circuit Analysis: Solve Kirchhoff’s equations efficiently.
  • Image Processing: SVD for compression:
    \[ A \approx U \Sigma V^T \]
  • Simulations: Sparse LU for finite element methods.
  • Machine Learning: Recommendation systems via low-rank factorization.