2. Elimination

Now let’s think about how to solve equations.

For example:

$$\begin{cases}x & +2y & +z &= 2 \quad &(1) \\3x & +8y & +z &= 12 \quad &(2) \\&\ \ 4y & +z &= 2 \quad &(3)\end{cases}$$

And the matrix $A=\begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix}$.

If we accept an equation, we can accept that if it multiplies a number or add a number.
For example:
If x + 2 = 3y, 2 \times (x + 2) = 2 \times 3y can be accepted too. So does 2 \times (x + 2) + z = 2 \times 3y + z.

So if (1) times a number and then add to (2), it won’t change the solutions of equations. If (1) times $-3$ and then add to (2), we will get 2y - 2z = 6, the $x$ is knocked out. This method is called elimination and it is a common way to solve equations.

If speaking in matrix words, this matrix operation is:$$\begin{bmatrix} \boxed{\color{red}{1}} & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix}\xrightarrow{row_2 \ – \ 3row_1}\begin{bmatrix} \boxed{\color{red}{1}} & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix}$$The boxed and red number 1 is the key number of this step. We call it pivot.

What about the right-hand vector $b$? Actually Matlab finishes up the left side $A$ and then go back to the right side $b$. So we can do with it later.

In (3), the coefficent of $x$ is already 0. If not, we can eliminate it in the same way.

Next step we can do it again to eliminate the $y$ in (3). In this step the second pivot is 2. Similarly, the thrid pivot is 5$$\begin{bmatrix} \boxed{\color{red}{1}} & 2 & 1 \\ 0 & \boxed{\color{green}{2}} & -2 \\ 0 & 4 & 1 \end{bmatrix}\xrightarrow{row_3 \ – \ 2row_2}\begin{bmatrix} \boxed{\color{red}{1}} & 2 & 1 \\ 0 & \boxed{\color{green}{2}} & -2 \\ 0 & 0 & \boxed{\color{blue}{5}} \end{bmatrix}$$In last step, we get a upper triangular matrix $U=\begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5 \end{bmatrix}$

So the purpose of elimination is to get from $A$ to $U$.

Note that pivots cannot be 0.

When does elimination fail?

If the first pivot is 0, does elimination fail? No. In last example, if we exchange the position of (1) and (3), the first pivot will be 0. But the solution of equations won’t be changed. So if the pivots is 0, try exchanging rows.

If $A=\begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & \boxed{-4} \end{bmatrix}$, in last step we will get a matrix $\begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 0 \end{bmatrix}$. Then the third pivot is 0. It means the equations have no solution. The elimination meets its failure. In this case matrix $A$ would have not been invertible.

Back subtitution

Consider $b$. We can place it to the extra column of $A$ to get a Augmented Matrix.$$[A|b]=\begin{bmatrix} \begin{array}{ccc | c}1 & 2 & 1 & 2 \\ 3 & 8 & 1 & 12 \\ 0 & 4 & 1 & 2 \\\end{array} \end{bmatrix}$$Then we do the same operations with this matrix:$$\begin{bmatrix} \begin{array}{ccc | c}1 & 2 & 1 & 2 \\ 3 & 8 & 1 & 12 \\ 0 & 4 & 1 & 2 \\\end{array} \end{bmatrix}\xrightarrow{row_2 \ – \ 3row_1}\begin{bmatrix} \begin{array}{ccc | c}1 & 2 & 1 & 2 \\ 0 & 2 & -2 & 6 \\ 0 & 4 & 1 & 2 \\\end{array} \end{bmatrix}\xrightarrow{row_3 \ – \ 2row_2}\begin{bmatrix} \begin{array}{ccc | c}1 & 2 & 1 & 2 \\ 0 & 2 & -2 & 6 \\ 0 & 0 & 5 & -10 \\\end{array} \end{bmatrix}$$

$b$ will be a new vector $c=\begin{bmatrix} 2 \\ 6 \\ -10 \end{bmatrix}$

And we can finally get new equations:$$\begin{cases}x & +2y & +z &= 2 \\&\ \ \ 2y & -2z &= 6 \\& &\ \ \ 5z &= -10\end{cases}$$Those are the equations $ U \mathbf{X} = c $.
And we can easily figure out that $z=-2, y=1, x=2$.

Using matrices multiplication to describe the matrices operations

How to use matrix language to describe this operation?

Last lecture we have learnt how to multiply a matrix by a column vector. Here is how to multiply a row vector by a matrix.$$\begin{equation}\begin{bmatrix} x & y & z \end{bmatrix}\begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix} =x \times \begin{bmatrix} a & b & c \end{bmatrix} + y \times \begin{bmatrix} e & f & g \end{bmatrix} + z \times \begin{bmatrix} h & i & j \end{bmatrix}\end{equation}$$This is a row operation.
So if the row vector is on the left, the matrix does row operation. If the column vector is on the right, the matrix does column operation.

If a 3×3 matrix is multipied by $I=\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$, the matrix would not be changed. $AI = IA = A$. It means this matrix operation do nothing with the matrix $A$. And the matrix $I$ is called identity matrix.

Step 1: Subtract $3 \times row_1$ from $row_2$$$\begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix} =\begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix}$$What does this multiplication means? Look at the row 2 of the left matrix. How does it affect the second matrix?

We know $\begin{equation}\begin{bmatrix} -3 & 1 & 0 \end{bmatrix}\begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix} =-3 \times \begin{bmatrix} 1 & 2 & 1 \end{bmatrix} + 2 \times \begin{bmatrix} 3 & 8 & 1 \end{bmatrix} + 0 \times \begin{bmatrix} 0 & 4 & 1 \end{bmatrix} =\begin{bmatrix} 0 & 2 & -2 \end{bmatrix}\end{equation}$

So $\begin{matrix}-3 & 1 & 0\end{matrix}$ means $-3 \times row_1 + 1 \times row_2 + 0 \times row_3$ produces the second row $\begin{matrix}0 & 2 & -2\end{matrix}$ of new matrix.

And the simple matrix $E_{21}=\begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $ which is used to operate the matrix $A$ is called Elementary Matrix.

$E_{21}$ means it will change the number to 0 on the position of row 2 and column 1.

Step 2: Subtract $2 \times row_2$ from $row_3$.

$$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -2 & 1 \end{bmatrix}\begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix} =\begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5 \end{bmatrix}$$

We use $E_{32}$ to represent the left matrix.

These two operations can be written as $E_{32}(E_{21}A)=U$

We use two elementary matrices to produce the matrix $U$. Can we use only one matrix to do that? The answer is yes.

$$E_{32}(E_{21}A)==(E_{32}E_{21})A=EA=U,\\\mathrm{composition\ matrix}\ E=E_{32}E_{21}$$

This method to change the parentheses is called associative law.

The composition matrix is the multiplication of two matrices. It mix two transformations into one. And this is the meaning of matrices multiplication.

Permutation Matrix

Another elementary matrix that exchanges two rows is called Permutation Matrix.

For example, if we want to exchange two rows of $\begin{bmatrix} a & b \\ c & d \end{bmatrix}$, what matrix can we use?

$$\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} a & b \\ c & d \end{bmatrix} =\begin{bmatrix} c & d \\ a & b \end{bmatrix}$$

How if we want to exchange two columns of matrix? Put the permutation matrix on the right.

$$\begin{bmatrix} a & b \\ c & d \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} =\begin{bmatrix} b & a \\ d & c \end{bmatrix}$$

According to this two examples, we know that $AB$ is not the same as $BA$. So the order of the matrices multiplication is important.

How to get from U back to A

See the matrix $\begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$. It subtract $3 \times row_1$ from $row_2$. How to undo this operation?
We know $IA=A$. So if we can find out a matrix $E^{-1}$ so that $E^{-1}E=I$, then $E^{-1}EA=IA=A$.

The matrix $E^{-1}$ is called $E$ inverse.

$$\begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}=\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$