Elimination Matrices

See Elimination for a walkthrough of elimination. This regards the computation of elimination matrices, which are a method of computing elimination.

Contents

  1. Elimination Matrices
    1. Introduction
    2. Formulation
    3. Factorization
    4. Permutation

Introduction

Consider the below system of equations: 

x + 2y + z = 2
3x + 8y + z = 12
4y + z = 2

Formulation

The first step of elimination involves the elimination of the cell at row 2 column 1 (henceforward cell (2,1)). 

[1] 2 1    [1] 2  1
 3  8 1 ->  0  2 -2
 0  4 1     0  4  1

This can instead be formulated in 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   1

This elimination matrix is called E2 1 because is eliminated cell (2,1). An elimination matrix is always the identity matrix with the negative of the multiplier in the elimination position.

Completing the elimination process: 

[1]  2   1    [1]  2   1
 0  [2] -2 ->  0  [2] -2
 0   4   1     0   0   5

This can be formulated as E3 2 (E2 1 A) = U. Note that this is equivalent to (E3 2 E2 1) A = U. 

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

Factorization

It is preferable to refactor (E3 2 E2 1) A = U into A = L U. L can be trivially solved to be E2 1-1 E3 2-1. Furthermore, because elimination matrices are modifications of the inverse matrix, their inverses are also trivial to solve. Note that these are simply the identity matrix with the (normal, non-negative) multiplier in the elimination position 

                  ┌      ┐
            -1    │ 1 0 0│
  E       E     = │ 0 1 0│
   2,3     2,3    │ 0 0 1│
                  └      ┘
┌       ┐         ┌      ┐
│  1 0 0│   -1    │ 1 0 0│
│ -3 1 0│ E     = │ 0 1 0│
│  0 0 1│  2,3    │ 0 0 1│
└       ┘         └      ┘
                  ┌      ┐
            -1    │ 1 0 0│
          E     = │ 3 1 0│
           2,3    │ 0 0 1│
                  └      ┘

The fundamental reason for factorization is that the singular product of E3 2 E2 1 is messier than that of E2 1-1 E3 2-1 

   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│
└      ┘└      ┘   └      ┘

In particular, cell (3,1) is a 0 in L but is 6 in E3 2 E2 1.

Permutation

If a zero pivot is reached, rows must be exchanged. This can be expressed with matrices as P A = L U.

See Permutation Matrices for more information on these matrices and their properties.

CategoryRicottone