Elimination Matrices

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

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: 

┌       ┐┌      ┐   ┌       ┐
│  1 0 0││ 1 2 1│   │ 1 2  1│
│ -3 1 0││ 3 8 1│ = │ 0 2 -2│
│  0 0 1││ 0 4 1│   │ 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.

The full elimination process can be formulated as E3 2 (E2 1 A) = U. This is equivalent to (E3 2 E2 1) A = U. 

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

   E        E         A    =     U
    3,2      1,2
┌       ┐┌       ┐┌      ┐   ┌       ┐
│ 1  0 0││  1 0 0││ 1 2 1│   │ 1 2  1│
│ 0  1 0││ -3 1 0││ 3 8 1│ = │ 0 2 -2│
│ 0 -2 1││  0 0 1││ 0 4 1│   │ 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.

CategoryRicottone