Line 22: | Line 22: | ||
Matrix form: | Matrix form: | ||
− | * | + | * <math>\underbrace{\begin{bmatrix} |
1 & 2 & 1\\ | 1 & 2 & 1\\ | ||
3 & 8 & 1\\ | 3 & 8 & 1\\ | ||
Line 31: | Line 31: | ||
\underbrace{\begin{bmatrix} | \underbrace{\begin{bmatrix} | ||
2 \\ 12 \\ 2 | 2 \\ 12 \\ 2 | ||
− | \end{bmatrix}}_{\mathbf b} | + | \end{bmatrix}}_{\mathbf b}</math> |
Line 38: | Line 38: | ||
So, first let's see how elimination works | So, first let's see how elimination works | ||
* i.e. concentrate only on the matrix $A$ | * i.e. concentrate only on the matrix $A$ | ||
− | * | + | * <math>A = \begin{bmatrix} |
1 & 2 & 1\\ | 1 & 2 & 1\\ | ||
3 & 8 & 1\\ | 3 & 8 & 1\\ | ||
0 & 4 & 1 | 0 & 4 & 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
Line 50: | Line 50: | ||
** s.t. there's 0 for the first column in all other rows | ** s.t. there's 0 for the first column in all other rows | ||
** so we want to knock out the $x_i$ part of the equation, or "eliminate" $x_i$ | ** so we want to knock out the $x_i$ part of the equation, or "eliminate" $x_i$ | ||
− | * | + | * <math>\begin{bmatrix} |
\boxed 1 & 2 & 1\\ | \boxed 1 & 2 & 1\\ | ||
3 & 8 & 1\\ | 3 & 8 & 1\\ | ||
0 & 4 & 1 | 0 & 4 & 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math>. $\boxed 1$ is the 1st pivot |
* step 2.1: clean cell $a_{21}$: | * step 2.1: clean cell $a_{21}$: | ||
− | ** | + | ** <math>\begin{bmatrix} |
\boxed 1 & 2 & 1\\ | \boxed 1 & 2 & 1\\ | ||
3 & 8 & 1\\ | 3 & 8 & 1\\ | ||
Line 64: | Line 64: | ||
0 & 2 & -2\\ | 0 & 2 & -2\\ | ||
0 & 4 & 1 | 0 & 4 & 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* multiplying row 1 by 3 will knock out $x$ from the 2nd equation | * multiplying row 1 by 3 will knock out $x$ from the 2nd equation | ||
* step 3.1: clean cell $a_{21}$ | * step 3.1: clean cell $a_{21}$ | ||
** already 0, continuing | ** already 0, continuing | ||
− | * | + | * <math>\begin{bmatrix} |
\boxed 1 & 2 & 1\\ | \boxed 1 & 2 & 1\\ | ||
0 & \boxed 2 & -2\\ | 0 & \boxed 2 & -2\\ | ||
0 & 4 & 1 | 0 & 4 & 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math>, $\boxed 2$ is the 2nd pivot |
* step 3.2 | * step 3.2 | ||
− | ** | + | ** <math>\begin{bmatrix} |
\boxed 1 & 2 & 1\\ | \boxed 1 & 2 & 1\\ | ||
0 & \boxed 2 & -2\\ | 0 & \boxed 2 & -2\\ | ||
Line 82: | Line 82: | ||
0 & \boxed 2 & -2\\ | 0 & \boxed 2 & -2\\ | ||
0 & 0 & \boxed 5 | 0 & 0 & \boxed 5 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
− | * | + | * <math>\begin{bmatrix} |
\boxed 1 & 2 & 1\\ | \boxed 1 & 2 & 1\\ | ||
0 & \boxed 2 & -2\\ | 0 & \boxed 2 & -2\\ | ||
0 & 0 & \boxed 5 | 0 & 0 & \boxed 5 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math>, $\boxed 5$ - it's 3rd pivot |
Line 93: | Line 93: | ||
− | === When | + | === When does it fail? === |
Not always we are able to do the forward elimination | Not always we are able to do the forward elimination | ||
0 at a Pivot position: | 0 at a Pivot position: | ||
* suppose the first pivot is 0: | * suppose the first pivot is 0: | ||
− | * | + | * <math>\begin{bmatrix} |
\boxed 0 & 2 & 1\\ | \boxed 0 & 2 & 1\\ | ||
3 & 8 & 1\\ | 3 & 8 & 1\\ | ||
0 & 4 & 1 | 0 & 4 & 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* But here it doesn't mean that we can't solve the system: we can switch the rows and continue: | * But here it doesn't mean that we can't solve the system: we can switch the rows and continue: | ||
− | * | + | * <math>\begin{bmatrix} |
\boxed 3 & 8 & 1\\ | \boxed 3 & 8 & 1\\ | ||
0 & 2 & 1\\ | 0 & 2 & 1\\ | ||
0 & 4 & 1 | 0 & 4 & 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* so, if there's a 0 at the pivot position, try to exchange rows | * so, if there's a 0 at the pivot position, try to exchange rows | ||
* if there's no rows with non-zero values at the pivot position - the elimination fails | * if there's no rows with non-zero values at the pivot position - the elimination fails | ||
Line 116: | Line 116: | ||
=== Augmented Matrix === | === Augmented Matrix === | ||
But we shouldn't forget about $\mathbf b$! | But we shouldn't forget about $\mathbf b$! | ||
− | * $A$ augmented is | + | * $A$ augmented is <math>\begin{bmatrix} |
\mathop{a_1}\limits_|^| \mathop{a_2}\limits_|^| ... \mathop{a_n}\limits_|^| \ \Bigg| \ \mathop{\mathbf b}\limits_|^| | \mathop{a_1}\limits_|^| \mathop{a_2}\limits_|^| ... \mathop{a_n}\limits_|^| \ \Bigg| \ \mathop{\mathbf b}\limits_|^| | ||
− | \end{bmatrix} | + | \end{bmatrix}</math>: matrix $A$ with column $\mathbf b$ stacked to the right |
− | * $A$ augmented: | + | * $A$ augmented: <math>\left[\begin{array}{ccc|c} |
1 & 2 & 1 & 2\\ | 1 & 2 & 1 & 2\\ | ||
3 & 8 & 1 & 12\\ | 3 & 8 & 1 & 12\\ | ||
0 & 4 & 1 & 2 | 0 & 4 & 1 & 2 | ||
− | \end{array}\right] | + | \end{array}\right]</math> |
* the right part $\mathbf b$ also changes as we go through elimination | * the right part $\mathbf b$ also changes as we go through elimination | ||
− | * | + | * <math>\left[\begin{array}{ccc|c} |
1 & 2 & 1 & 2\\ | 1 & 2 & 1 & 2\\ | ||
3 & 8 & 1 & 12\\ | 3 & 8 & 1 & 12\\ | ||
Line 137: | Line 137: | ||
0 & 2 & -6 & 6\\ | 0 & 2 & -6 & 6\\ | ||
0 & 0 & 5 & -10 | 0 & 0 & 5 & -10 | ||
− | \end{array}\right] | + | \end{array}\right]</math> |
* let $\mathbf c$ be the result of applying elimination to $\mathbf b$ | * let $\mathbf c$ be the result of applying elimination to $\mathbf b$ | ||
Line 144: | Line 144: | ||
After we forward-eliminated variables of augmented $A$, we can do back substitution: | After we forward-eliminated variables of augmented $A$, we can do back substitution: | ||
* Our matrix is | * Our matrix is | ||
− | + | <math>\left[\begin{array}{ccc|c} | |
1 & 2 & 1 & 2\\ | 1 & 2 & 1 & 2\\ | ||
0 & 2 & -6 & 6\\ | 0 & 2 & -6 & 6\\ | ||
0 & 0 & 5 & -10 | 0 & 0 & 5 & -10 | ||
− | \end{array}\right] | + | \end{array}\right]</math> |
* It means that our system is | * It means that our system is | ||
− | + | <math>\left\{\begin{array}{rl} | |
x + 2y + z & = 2\\ | x + 2y + z & = 2\\ | ||
2y - 2z & = 6 \\ | 2y - 2z & = 6 \\ | ||
5z & = -10 | 5z & = -10 | ||
− | \end{array}\right. | + | \end{array}\right.</math> |
Now we just go backwards and solve: first for $z$, then for $y$, and finally for $x$ | Now we just go backwards and solve: first for $z$, then for $y$, and finally for $x$ | ||
Line 165: | Line 165: | ||
=== Elimination: Matrix Form === | === Elimination: Matrix Form === | ||
We can write these elimination steps in matrix form | We can write these elimination steps in matrix form | ||
− | * | + | * <math>\begin{bmatrix} |
1 & 2 & 1\\ | 1 & 2 & 1\\ | ||
3 & 8 & 1\\ | 3 & 8 & 1\\ | ||
0 & 4 & 1 | 0 & 4 & 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* the first step of the elimination was to take first and last rows unchanged, and subtract 3 times 1st row from the second. | * the first step of the elimination was to take first and last rows unchanged, and subtract 3 times 1st row from the second. | ||
* Can we write it with [[Matrix Multiplication]]? | * Can we write it with [[Matrix Multiplication]]? | ||
− | ** | + | ** <math>\begin{bmatrix} |
1 & 0 & 0\\ | 1 & 0 & 0\\ | ||
? & ? & ?\\ | ? & ? & ?\\ | ||
Line 180: | Line 180: | ||
3 & 8 & 1\\ | 3 & 8 & 1\\ | ||
0 & 4 & 1 | 0 & 4 & 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
− | ** The first and last rows remain unchanged - hence we have | + | ** The first and last rows remain unchanged - hence we have <math>\begin{bmatrix} |
1\\ | 1\\ | ||
?\\ | ?\\ | ||
0 | 0 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> and <math>\begin{bmatrix} |
0\\ | 0\\ | ||
?\\ | ?\\ | ||
1 | 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
** what should we put instead of $[? \ ? \ ?]$ so multiplication takes us from one matrix to another? | ** what should we put instead of $[? \ ? \ ?]$ so multiplication takes us from one matrix to another? | ||
− | ** | + | ** <math>\begin{bmatrix} |
1 & 0 & 0\\ | 1 & 0 & 0\\ | ||
\boxed{-3} & 1 & 0\\ | \boxed{-3} & 1 & 0\\ | ||
0 & 0 & 1 | 0 & 0 & 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
** we want to subtract 3 times row 1 from row 2: | ** we want to subtract 3 times row 1 from row 2: | ||
− | ** | + | ** <math>\begin{bmatrix} |
1 & 0 & 0\\ | 1 & 0 & 0\\ | ||
\boxed{-3} & 1 & 0\\ | \boxed{-3} & 1 & 0\\ | ||
Line 209: | Line 209: | ||
0 & 2 & -2\\ | 0 & 2 & -2\\ | ||
0 & 4 & 1 | 0 & 4 & 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* let $E_{21}$ be the matrix that's used for step 2,1 of the elimination | * let $E_{21}$ be the matrix that's used for step 2,1 of the elimination | ||
− | ** | + | ** <math>E_{21} A = \begin{bmatrix} |
1 & 2 & 1\\ | 1 & 2 & 1\\ | ||
0 & 2 & -2\\ | 0 & 2 & -2\\ | ||
0 & 4 & 1 | 0 & 4 & 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* we continue this way until we transform $A$ to $U$ | * we continue this way until we transform $A$ to $U$ | ||
** so we have $E_{21} (E_{21} A) = U$ | ** so we have $E_{21} (E_{21} A) = U$ |
Gaussian Elimination or Row Reduction is a method for solving a System of Linear Equations
We have the following system with 3 equations and 3 unknowns:
$\left\{\begin{array}{l} x + 2y + z = 2\\ 3x + 8y + z = 12 \\ 4y + z = 2 \end{array}\right.$
Matrix form:
So, first let's see how elimination works
Let's proceed
The matrix is now in the upper-triangular form $U$
Not always we are able to do the forward elimination
0 at a Pivot position:
But we shouldn't forget about $\mathbf b$!
After we forward-eliminated variables of augmented $A$, we can do back substitution:
[math]\left[\begin{array}{ccc|c} 1 & 2 & 1 & 2\\ 0 & 2 & -6 & 6\\ 0 & 0 & 5 & -10 \end{array}\right][/math]
[math]\left\{\begin{array}{rl}
x + 2y + z & = 2\\
2y - 2z & = 6 \\
5z & = -10
\end{array}\right.[/math]
Now we just go backwards and solve: first for $z$, then for $y$, and finally for $x$
We can write these elimination steps in matrix form
What if we need to exchange rows?