# Lecture 02 Elimination with Matrices

Today's lecture contains:
1. Elimination <br/>
2. Explaination of elimination <br/>
3. Permutation <br/>
4. Inverse Matrix <br/>


## 1. Elimination

Suppose we have equations with 3 unknown:
\begin{align}
\begin{cases}x&+2y&+z&=2\\3x&+8y&+z&=12\\&4y&+z&=2\end{cases}
\end{align}

Such equation can be expressed in the format of 
\begin{align}
Ax=b
\end{align}
which is:
\begin{align}
\begin{bmatrix}1&2&1\\3&8&1\\0&4&1\end{bmatrix}\begin{bmatrix}x\\y\\z\end{bmatrix}=\begin{bmatrix}2\\12\\2\end{bmatrix}
\end{align}

### 1.1 Process of elimination
The objective of elimination is to acquire an upper triangular matrix from $A$. What does it look like? It looks something like this:
\begin{align}
U(Upper Triangular Matrix): \begin{bmatrix}1&2&1\\0&8&1\\0&0&1\end{bmatrix}
\end{align}
Lower triangular matrix looks like this:
\begin{align}
L(Lower Triangular Matrix): \begin{bmatrix}1&0&0\\3&8&0\\2&6&1\end{bmatrix}
\end{align}


* (1) We wish we can eliminate all the $x$ from second and third equations. Taking the matrix $A$ as an example:
\begin{align}
A=\begin{bmatrix}\underline{1}&2&1\\3&8&1\\0&4&1\end{bmatrix}
\end{align}


The number with underscore is called **pivot** which is the coefficient of $x$ in the first equation. And we need to eliminate all the $x$ below which means **all numbers below pivot should be eliminated to zero**. Apparently, we can take $row_2$-**3**$row_1$

Therefore, the first step is:
\begin{align}
\begin{bmatrix}\underline{1}&2&1\\3&8&1\\0&4&1\end{bmatrix}\xrightarrow{row_2-3row_1}\begin{bmatrix}\underline{1}&2&1\\0&2&-2\\0&4&1\end{bmatrix}
\end{align}



* (2) In light of above logic, next step is to eliminate the second pivot which stands for $y$. That would be $row_3$-**2**$row_2$
\begin{align}
\begin{bmatrix}\underline{1}&2&1\\0&\underline{2}&-2\\0&4&1\end{bmatrix}\xrightarrow{row_3-2row_2}\begin{bmatrix}\underline{1}&2&1\\0&\underline{2}&-2\\0&0&\underline{5}\end{bmatrix}
\end{align}

* (3) Because we want to make step(1) and step(2) more intuitive, so we don't take $b$ into account for a moment. In the end , we can add the right hand side $b$ back to the above logic. This step is called **back substitution** and the matrix in the following format called **augmented matrix**.

\begin{align}
\left[\begin{array}{c|c}A&b\end{array}\right]=\left[\begin{array}{ccc|c}1&2&1&2\\3&8&1&12\\0&4&1&2\end{array}\right]\to\left[\begin{array}{ccc|c}1&2&1&2\\0&2&-2&6\\0&4&1&2\end{array}\right]\to\left[\begin{array}{ccc|c}1&2&1&2\\0&2&-2&6\\0&0&5&-10\end{array}\right]
\end{align}

* (4) In the end, we can convert matrix to equation.

\begin{align}
\begin{cases}x&+2y&+z&=2\\&2y&-2z&=6\\&&5z&=-10\end{cases}
\end{align}

$x$,$y$,$z$ can be easily solved:
\begin{align}
x=2, y=1, z=-2
\end{align}

### 1.2 Shape of multiplication
$matrix×column=column$
\begin{align}
\begin{bmatrix}...&...&...\\...&...&...\\...&...&...\end{bmatrix}\begin{bmatrix}x\\y\\z\end{bmatrix}=\begin{bmatrix}...\\...\\...\end{bmatrix}
\end{align}


$vector×matrix=vector$
\begin{align}
\begin{bmatrix}x&y&z\end{bmatrix}\begin{bmatrix}...&...&...\\...&...&...\\...&...&...\end{bmatrix}=\begin{bmatrix}...&...&...\end{bmatrix}
\end{align}


Sometime vector can be looked as 1×3 matrix.

## 2. Detail explaination of elimination

Before jumping into the explaination, we first need to figure out **how matrix multiply**?

Taking the following mutiplication as an example, where $I$ stands for **identity matrix**. One matrix multiple Identity matrix is itself.
\begin{align}
IA=A
\end{align}

\begin{align}
\begin{bmatrix}1&0&0\\0&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\\3&8&1\\0&4&1\end{bmatrix}
\end{align}

So what is going on in the above matrix multiplication?
* (1) Let's look from the perspective of the first matrix from the left.
\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix} 
can be decomposed to 
\begin{bmatrix}1&0&0\end{bmatrix} 
\begin{bmatrix}0&1&0\end{bmatrix}
\begin{bmatrix}0&0&1\end{bmatrix}

* (2) Each row of the left matrix stands for the coeffient of each row of the right matrix.

$\begin{bmatrix}1&0&0\end{bmatrix}$ means take $1$×$\begin{bmatrix}1&2&1\end{bmatrix}$, $0$×$\begin{bmatrix}3&8&1\end{bmatrix}$, $0$×$\begin{bmatrix}0&4&1\end{bmatrix}$

$\begin{bmatrix}0&1&0\end{bmatrix}$ means take $0$×$\begin{bmatrix}1&2&1\end{bmatrix}$, $1$×$\begin{bmatrix}3&8&1\end{bmatrix}$, $0$×$\begin{bmatrix}0&4&1\end{bmatrix}$


$\begin{bmatrix}0&0&1\end{bmatrix}$ means take $0$×$\begin{bmatrix}1&2&1\end{bmatrix}$, $0$×$\begin{bmatrix}3&8&1\end{bmatrix}$, $1$×$\begin{bmatrix}0&4&1\end{bmatrix}$


And sum them vertically!


### 2.1 Step(1)
So we look back to the elimination in part 1. 
\begin{align}
\Bigg[\quad ?\quad \Bigg]\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}
\end{align}

We can easily understand the above multiplication should be the following:

\begin{align}
\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}
\end{align}


In the meantime, we denote $\begin{bmatrix}1&0&0\\-3&1&0\\0&0&1\end{bmatrix}$ as $E_{21}$ since it eliminates all the component below the second row and first column.

### 2.2 Step(2)

The second elimination is:

\begin{align}
\Bigg[\quad ?\quad \Bigg]\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}
\end{align}

And we can easily see that:

\begin{align}
\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}
\end{align}

We can denoted $\begin{bmatrix}1&0&0\\0&1&0\\0&-2&1\end{bmatrix}$ as $E_{32}$ since it eliminates all the component below the third row and second column.

### 2.3 Summary
Finally, the whole process can be written as followed:

\begin{align}
E_{32}(E_{12}A)=U
\end{align}

where $U$ stands for the right hand side from step two. $\begin{bmatrix}1&2&1\\0&2&-2\\0&0&5\end{bmatrix}$ **Upper triangular matrix**.

In the meantime, you may wonder **why the order of above multiplication starts from the right to left**? 

It is $E_{32}(E_{12}A)$ rather than $A E_{12}E_{32}$?

Intuitively, I **think of this order as an order of function**. Like $g(f(x))$, we first apply $f(x)$ then $g()$. This is very similar to the syntax of Wolfram language.

## 3. Permutation

### 3.1	Exchange row1 and row2

Giving above knowledge, how can we do that:
\begin{align}
\Bigg[\quad ?\quad \Bigg]\begin{bmatrix}a&b\\c&d\end{bmatrix}=\begin{bmatrix}c&d\\a&b\end{bmatrix}
\end{align}

Very simple, that is:
\begin{align}
\begin{bmatrix}0&1\\1&0\end{bmatrix}\begin{bmatrix}a&b\\c&d\end{bmatrix}=\begin{bmatrix}c&d\\a&b\end{bmatrix}
\end{align}

### 3.2	Exchange column1 and column2
\begin{align}
\Bigg[\quad ?\quad \Bigg]\begin{bmatrix}a&b\\c&d\end{bmatrix}=\begin{bmatrix}b&a\\d&c\end{bmatrix}
\end{align}


That is impossible! While if we switch the position, and we can **see it in a column perspective**.
\begin{align}
\begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}0&1\\1&0\end{bmatrix}=\begin{bmatrix}b&a\\d&c\end{bmatrix}
\end{align}

$\begin{bmatrix}\underline{0}&1\\\underline{1}&0\end{bmatrix}$ means take 0 first column and 1 second column.


## 4. Inverse Matrix
We take $E_{21}$ as example, What should be:
\begin{align}
\Bigg[\quad ?\quad \Bigg]\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}
\end{align}

We can easily solve:
\begin{align}
\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}
\end{align}

We denote the inverse matrix of $E$ as $E^{-1}$. That said, $E^{-1}E=I$.

82a83ff6488e5dcfbcb658797a11c37a1d9c0c20
ipynb
Jupyter Notebook
Lecture 02 Elimination with Matrices.ipynb
XingxinHE/Linear_Algebra
7d6b78699f8653ece60e07765fd485dd36b26194
MIT
2021-04-24T17:23:50.000Z
2021-11-27T11:00:04.000Z
Lecture 02 Elimination with Matrices.ipynb
XingxinHE/Linear_Algebra
7d6b78699f8653ece60e07765fd485dd36b26194
MIT
Lecture 02 Elimination with Matrices.ipynb
XingxinHE/Linear_Algebra
7d6b78699f8653ece60e07765fd485dd36b26194
MIT
Qwen/Qwen-72B
1. YES
2. YES