LU Decomposition
LU decomposition is another approach to Gauss-Jordan elimination. It is generalized as A = LU.
Elimination Matrices
Using the same problem as seen here:
x + 2y + z = 2 3x + 8y + z = 12 4y + z = 2
The Gauss-Jordan approach begins with identifying the pivot and transforming this:
┌ ┐ │ [1] 2 1│ │ 3 8 1│ │ 0 4 1│ └ ┘
...into this:
┌ ┐ │ [1] 2 1│ │ 0 2 -2│ │ 0 4 1│ └ ┘
This transformation was ultimately a linear combination of rows: subtracting three of row 1 from row 2. This can be reformulated with matrices.
julia> A = [1 2 1; 3 8 1; 0 4 1]
3×3 Matrix{Int64}:
1 2 1
3 8 1
0 4 1
julia> E2_1 = [1 0 0; -3 1 0; 0 0 1]
3×3 Matrix{Int64}:
1 0 0
-3 1 0
0 0 1
julia> E2_1 * A
3×3 Matrix{Int64}:
1 2 1
0 2 -2
0 4 1This elimination matrix is called E2 1 because it eliminated cell (2,1), the elimination cell. An elimination matrix is always the identity matrix with the negated multiplier in the elimination cell.
The Gauss-Jordan approach continues with subtracting two of row 2 from row 3. Formulated as matrices instead:
julia> E3_2 = [1 0 0; 0 1 0; 0 -2 1]
3×3 Matrix{Int64}:
1 0 0
0 1 0
0 -2 1
julia> E3_2 * E2_1 * A
3×3 Matrix{Int64}:
1 2 1
0 2 -2
0 0 5
Decomposition
In this specific example, elimination can be written out as (E3 2E2 1)A = U.
A preferable form is A = LU, where L takes on the role of all elimination matrices. L may be a lower triangular matrix. In this specific example, L = E2 1-1E3 2-1.
See below how E3 2E2 1 is messier than E2 1-1E3 2-1 despite needing to compute inverses:
E E = ?
3,2 2,1
┌ ┐┌ ┐ ┌ ┐
│ 1 0 0││ 1 0 0│ │ 1 0 0│
│ 0 1 0││ -3 1 0│ = │ -3 1 0│
│ 0 -2 1││ 0 0 1│ │ 6 -2 1│
└ ┘└ ┘ └ ┘
-1 -1
E E = L
2,1 3,2
┌ ┐┌ ┐ ┌ ┐
│ 1 0 0││ 1 0 0│ │ 1 0 0│
│ 3 1 0││ 0 1 0│ = │ 3 1 0│
│ 0 0 1││ 0 2 1│ │ 0 2 1│
└ ┘└ ┘ └ ┘Furthermore, in this expression, elimination matrices are iteratively appended instead of prepended.