Mathematics > Linear Algebra > LU Decomposition
LU Decomposition is a fundamental technique in linear algebra, pivotal for solving systems of linear equations, inverting matrices, and determining the determinant of a matrix. It involves decomposing a given matrix \( A \) into the product of two matrices: a lower triangular matrix \( L \) and an upper triangular matrix \( U \). The procedure can be mathematically expressed as:
\[ A = LU \]
where \( A \) is the original \( n \times n \) square matrix, \( L \) is an \( n \times n \) lower triangular matrix (all elements above the main diagonal are zero), and \( U \) is an \( n \times n \) upper triangular matrix (all elements below the main diagonal are zero).
Detailed Explanation
Lower and Upper Triangular Matrices:
- A lower triangular matrix \( L \) holds the form:
\[
L = \begin{pmatrix}
l_{11} & 0 & 0 & \cdots & 0 \\
l_{21} & l_{22} & 0 & \cdots & 0 \\
l_{31} & l_{32} & l_{33} & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
l_{n1} & l_{n2} & l_{n3} & \cdots & l_{nn}
\end{pmatrix}
\]
- An upper triangular matrix \( U \) holds the form: \[ U = \begin{pmatrix} u_{11} & u_{12} & u_{13} & \cdots & u_{1n} \\ 0 & u_{22} & u_{23} & \cdots & u_{2n} \\ 0 & 0 & u_{33} & \cdots & u_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & u_{nn} \end{pmatrix} \]
Process of Decomposition:
1. Forward Elimination: Begin by applying the process of Gaussian elimination to transform the matrix \( A \) into an upper triangular matrix \( U \). Each step of elimination is recorded and stored in corresponding entries of the matrix \( L \).
- Construct L and U: The multipliers used in the elimination process form the elements of \( L \). These multipliers ensure that when \( L \) and \( U \) are multiplied, the original matrix \( A \) is reconstructed.
Applications
Solving Linear Systems: Given a linear system \( Ax = b \), decompose \( A \) as \( LU \). The problem reduces to solving two simpler systems:
\[
Ly = b \quad \text{and} \quad Ux = y
\]
Solve for \( y \) in the lower triangular system and then for \( x \) in the upper triangular system.Matrix Inversion: Compute the inverse of a matrix \( A \) by performing LU decomposition and then solving \( AX = I \), where \( I \) is the identity matrix. The columns of \( X \) are found by solving the system one column vector at a time.
Determinant Calculation: The determinant of \( A \), if \( A = LU \), is computed as:
\[
\text{det}(A) = \text{det}(L) \cdot \text{det}(U)
\]
Given that \( L \) has ones on its diagonal, \( \text{det}(L) = 1 \), thus:
\[
\text{det}(A) = \prod_{i=1}^n u_{ii}
\]
where \( u_{ii} \) are the diagonal elements of \( U \).
LU Decomposition is valued for its efficiency and simplicity in numerical computations, making it an essential tool in linear algebra and applied mathematics.