Elimination with Matrices

May 20, 2019

Elimination

A pivot in a matrix is the first non-zero element in each row. Later we have pivot row and pivot column and row echelon form. But let’s just assume this simple definition for now. We want the column position of a pivot is equal to its row position, i.e., we want the pivot in row 1 in column 1, in row 2 in column 2 etc. If we cannot find a pivot for each row, then it’s not a good sign.

So our task it to do operations between or among rows to achieve the ideal situation where the pivots are in their positions.

Exmaple:

Let’s care about matrix $A$ for now. I have labeled each row as $r1,r2,r3$. As the first number in $r1$ is non-zero, the pivot for this row is found automatically. Then we find the pivot of second row. To do so, we do $r2-r1\cdot3$, and this results in

Then we found the second pivot by eliminating $3$ in $r2$. Note that the first element in $r3$ is zero, so we don’t have to do extra steps to eliminate it. If it were non-zero, we still have to make it zero in order to find the third pivot $r3$. Right now to find the third pivot, we just need to do

where I coined the new $r2$ as $r2'$. Then finally we have found the final upper triangle matrix $U$. This is the ideal form we want to achieve. But don’t forget that we also need to do same operations on $b$, which leads to $\left[\begin{matrix} 2\\ 6\\ -10 \end{matrix}\right]$ and this final constant vector we call it $\mathbf{c}$. The new equation is then $U\mathbf x=\mathbf{c}$. In general, we want to augment the coefficient matrix $A$ in case we forgot the steps to obtain $U$, that is, to attach $\mathbf{b}$ into it

Back Substitution

Right now our equations are

First we see $z=-2$ from the last row. And substitute $z$ into the second row we get $y=1$. And finally $x=2$.

Matrix Operations

Before we start, note that multiplying a constant with any matrices is equal to multiply a diagonal matrix(one with only non-zero values in the diagonal line) with the constant lies on the diagonal:

where $I$ is the identity matrix. This is also true when we put $\lambda$ on the right side of the matrix.

Column

This was mentioned on the preliminaries. When multiplying a vector on the right of a matrix, we are manipulating its columns:

Note each column is 3 x 1 so the final answer is a vector of 3 x 1. If it’s a matrix not a vector:

each column on the matrix to the right of multiplication is controlling the column in the product matrix.

Row

Row operations are similar:

Note the output vector is 1 x 3.

Thus if we want to reproduce the elimination on $(2)$, we can do

the second row of the left matrix is producing the same effect of $r2-3*r1$ on row exchange on the original matrix. Let’s call this matrix $E_{21}$ because it anchors the r2c1 element(though I prefer to call it $E_{22}$). Learning from this, we can add another matrix $E_{32}$ to simulate the second elimination step in $(2)$

Permutation

Inverse Preview

In summary, to express the whole operations, it is

By associative law,

But notice that we cannot mess around the order of the multiplication when multiplying matrices. So to find the elimination matrix $E$ which does the whole job of converting $A$ to $U$, there’s two way, we can multiply $E_{32}$ with $E_{21}$, or, the way the professor introduces, do Inverse. We can find the inverse. We will introduce the simple concept here.

To find the inverse of a matrix, we find the matrix that can offset its effect let’s say we want to find the inverse of $E_{21}=\left[\begin{matrix} 1 & 0 & 0\\ -3 & 1 & 0\\ 0 & 0 & 1 \end{matrix}\right]$

we offset the effect of substracting three $r1$ by adding three of it back.