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 E_{2 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 E_{3 2} (E_{2 1} A) = U. This is equivalent to (E_{3 2} E_{2 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 (E_{3 2} E_{2 1}) A = U into A = L U. L can be trivially solved to be E_{2 1}^-1 E_{3 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 E_{3 2} E_{2 1} is messier than that of E_{2 1}^-1 E_{3 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 E_{3 2} E_{2 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