Line 21: | Line 21: | ||
Let's do it: | Let's do it: | ||
− | * | + | * <math>\begin{bmatrix} |
\boxed 1 & 2 & 2 & 2 \\ | \boxed 1 & 2 & 2 & 2 \\ | ||
2 & 4 & 6 & 8 \\ | 2 & 4 & 6 & 8 \\ | ||
Line 30: | Line 30: | ||
0 & 0 & 2 & 4 \\ | 0 & 0 & 2 & 4 \\ | ||
0 & 0 & 2 & 4 \\ | 0 & 0 & 2 & 4 \\ | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* we have 0's in the second column, but in the next column there's a non-zero value - can take it as a pivot! | * we have 0's in the second column, but in the next column there's a non-zero value - can take it as a pivot! | ||
− | * | + | * <math>\begin{bmatrix} |
\boxed 1 & 2 & 2 & 2 \\ | \boxed 1 & 2 & 2 & 2 \\ | ||
0 & 0 & \boxed 2 & 4 \\ | 0 & 0 & \boxed 2 & 4 \\ | ||
Line 41: | Line 41: | ||
0 & 0 & \boxed 2 & 4 \\ | 0 & 0 & \boxed 2 & 4 \\ | ||
0 & 0 & 0 & 0 \\ | 0 & 0 & 0 & 0 \\ | ||
− | \end{bmatrix} = U | + | \end{bmatrix} = U</math> |
* it's not really an upper-triangular matrix, but we still can call it $U$ | * it's not really an upper-triangular matrix, but we still can call it $U$ | ||
* this $U$ is in the ''echelon form'' (or "staircase" form) | * this $U$ is in the ''echelon form'' (or "staircase" form) | ||
Line 52: | Line 52: | ||
During the elimination the nullspace $N(A)$ of $A$ doesn't change | During the elimination the nullspace $N(A)$ of $A$ doesn't change | ||
* so systems $A\mathbf x = \mathbf 0$ and $U \mathbf x = \mathbf 0$ have the same solutions $\mathbf x$ | * so systems $A\mathbf x = \mathbf 0$ and $U \mathbf x = \mathbf 0$ have the same solutions $\mathbf x$ | ||
− | * the column with pivot variables are called ''pivot columns'', there are $r$ of them | + | * the column with pivot variables are called ''pivot columns'', there are $r$ of them |
− | * the rest of the columns are called ''free columns'', there are $n - r$ of them | + | * the rest of the columns are called ''free columns'', there are $n - r$ of them |
* http://habrastorage.org/files/fcb/1dc/c9e/fcb1dcc9e07345df9fd4c6624d8038a7.png | * http://habrastorage.org/files/fcb/1dc/c9e/fcb1dcc9e07345df9fd4c6624d8038a7.png | ||
Line 68: | Line 68: | ||
* E.g. let's assign 1 and 0 to $x_2$ and $x_4$ | * E.g. let's assign 1 and 0 to $x_2$ and $x_4$ | ||
− | ** we have | + | ** we have <math>\mathbb x = \begin{bmatrix} |
x_1 \\ 1 \\ x_3 \\ 0 | x_1 \\ 1 \\ x_3 \\ 0 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math>, then we solve the system and get <math>\mathbb x = \begin{bmatrix} |
-2 \\ 1 \\ 0 \\ 0 | -2 \\ 1 \\ 0 \\ 0 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
− | ** we can also take any linear combination of this solution, so we should write | + | ** we can also take any linear combination of this solution, so we should write <math>\mathbb x = c_1 \cdot \begin{bmatrix} |
-2 \\ 1 \\ 0 \\ 0 | -2 \\ 1 \\ 0 \\ 0 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* what if we assign different values to $x_2$ and $x_4$? | * what if we assign different values to $x_2$ and $x_4$? | ||
− | ** Can assign this way: | + | ** Can assign this way: <math>\mathbb x = \begin{bmatrix} |
x_1 \\ 0 \\ x_3 \\ 1 | x_1 \\ 0 \\ x_3 \\ 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math>, then we solve and get <math>\mathbb x = \begin{bmatrix} |
2 \\ 0 \\ -2 \\ 1 | 2 \\ 0 \\ -2 \\ 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
− | ** so we have another "special" solution | + | ** so we have another "special" solution <math>\mathbb x = c_2 \cdot \begin{bmatrix} |
2 \\ 0 \\ -2 \\ 1 | 2 \\ 0 \\ -2 \\ 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* so the final solution to this system will be | * so the final solution to this system will be | ||
− | ** | + | ** <math>\mathbf x = c_1 \cdot \begin{bmatrix} |
-2 \\ 1 \\ 0 \\ 0 | -2 \\ 1 \\ 0 \\ 0 | ||
\end{bmatrix} + c_2 \cdot \begin{bmatrix} | \end{bmatrix} + c_2 \cdot \begin{bmatrix} | ||
2 \\ 0 \\ -2 \\ 1 | 2 \\ 0 \\ -2 \\ 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
** this is the Nullspace $N(A)$ of the matrix $A$ | ** this is the Nullspace $N(A)$ of the matrix $A$ | ||
Line 97: | Line 97: | ||
Can we do simpler? | Can we do simpler? | ||
− | Suppose we have matrix $A$ that we reduced to | + | Suppose we have matrix $A$ that we reduced to <math>U = \begin{bmatrix} |
\boxed 1 & 2 & 2 & 2 \\ | \boxed 1 & 2 & 2 & 2 \\ | ||
0 & 0 & \boxed 2 & 4 \\ | 0 & 0 & \boxed 2 & 4 \\ | ||
0 & 0 & 0 & 0 \\ | 0 & 0 & 0 & 0 \\ | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* can we clean it further? Can try to clean the pivot columns upwards - so there's only one 1 and the rest are 0's | * can we clean it further? Can try to clean the pivot columns upwards - so there's only one 1 and the rest are 0's | ||
− | * | + | * <math>U = \begin{bmatrix} |
\boxed 1 & 2 & 2 & 2 \\ | \boxed 1 & 2 & 2 & 2 \\ | ||
0 & 0 & \boxed 2 & 4 \\ | 0 & 0 & \boxed 2 & 4 \\ | ||
Line 112: | Line 112: | ||
0 & 0 & \boxed 1 & 4 \\ | 0 & 0 & \boxed 1 & 4 \\ | ||
0 & 0 & 0 & 0 \\ | 0 & 0 & 0 & 0 \\ | ||
− | \end{bmatrix} = R | + | \end{bmatrix} = R</math> |
* $R$ is a ''Row Reduced Echelon Form'' (RRFR) of $A$ | * $R$ is a ''Row Reduced Echelon Form'' (RRFR) of $A$ | ||
* http://habrastorage.org/files/d02/b71/666/d02b7166629a482fa5e29591cf5d6baf.png | * http://habrastorage.org/files/d02/b71/666/d02b7166629a482fa5e29591cf5d6baf.png | ||
− | * note that if we consider only the pivot rows and columns, we see that we have the identity matrix | + | * note that if we consider only the pivot rows and columns, we see that we have the identity matrix <math>\begin{bmatrix} |
1 & 0 \\ | 1 & 0 \\ | ||
0 & 1 \\ | 0 & 1 \\ | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
So now if we take a look at our new system, we have | So now if we take a look at our new system, we have | ||
− | * | + | * <math>\left\{\begin{array}{rl} |
x_1 + 2 x_2 - 2 x_4 & = 0 \\ | x_1 + 2 x_2 - 2 x_4 & = 0 \\ | ||
x_3 + 2 x_4 & = 0 \\ | x_3 + 2 x_4 & = 0 \\ | ||
− | \end{array}\right. | + | \end{array}\right.</math> |
* $A \mathbf x = \mathbf 0$, $U \mathbf x = \mathbf 0$ and $R \mathbf x = \mathbf 0$ - all have the same solutions $\mathbf x$! | * $A \mathbf x = \mathbf 0$, $U \mathbf x = \mathbf 0$ and $R \mathbf x = \mathbf 0$ - all have the same solutions $\mathbf x$! | ||
Let's rearrange columns in $R$ so first we have the pivot columns, and then the free columns | Let's rearrange columns in $R$ so first we have the pivot columns, and then the free columns | ||
− | * | + | * <math>\begin{bmatrix} |
1 & 0 & 2 & -2 \\ | 1 & 0 & 2 & -2 \\ | ||
0 & 1 & 0 & 2 \\ | 0 & 1 & 0 & 2 \\ | ||
0 & 0 & 0 & 0 \\ | 0 & 0 & 0 & 0 \\ | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* now can distinguish the $I$ part (identity) and the $F$ part (free) | * now can distinguish the $I$ part (identity) and the $F$ part (free) | ||
* http://habrastorage.org/files/13b/2e5/439/13b2e543918546ee99bb2ee4de2b5c9a.png | * http://habrastorage.org/files/13b/2e5/439/13b2e543918546ee99bb2ee4de2b5c9a.png | ||
Line 144: | Line 144: | ||
Why does it happen? | Why does it happen? | ||
− | * assume we have a RREF | + | * assume we have a RREF <math>R = \begin{bmatrix} |
I & F \\ | I & F \\ | ||
0 & 0 \\ | 0 & 0 \\ | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* we have $r$ pivot columns, $n-r$ free columns and $r$ pivot rows | * we have $r$ pivot columns, $n-r$ free columns and $r$ pivot rows | ||
* we want to solve $R\mathbf x = \mathbf 0$. What are the "special" solutions? | * we want to solve $R\mathbf x = \mathbf 0$. What are the "special" solutions? | ||
− | * let's create a ''Nullspace matrix'' $N$, | + | * let's create a ''Nullspace matrix'' $N$, <math>N = \begin{bmatrix} |
-F \\ I | -F \\ I | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* Columns of $N$ are our special solutions | * Columns of $N$ are our special solutions | ||
− | * let's take a closer look at one of these columns | + | * let's take a closer look at one of these columns <math>\begin{bmatrix} |
\mathop{\mathbf x_\text{pivot}}\limits_{|}^{|} \\ | \mathop{\mathbf x_\text{pivot}}\limits_{|}^{|} \\ | ||
\mathop{\mathbf x_\text{free}}\limits_{|}^{|} \\ | \mathop{\mathbf x_\text{free}}\limits_{|}^{|} \\ | ||
− | \end{bmatrix} | + | \end{bmatrix}</math>. The system is <math>\begin{bmatrix} |
I & F \\ | I & F \\ | ||
0 & 0 \\ | 0 & 0 \\ | ||
Line 163: | Line 163: | ||
\mathop{\mathbf x_\text{pivot}}\limits_{|}^{|} \\ | \mathop{\mathbf x_\text{pivot}}\limits_{|}^{|} \\ | ||
\mathop{\mathbf x_\text{free}}\limits_{|}^{|} \\ | \mathop{\mathbf x_\text{free}}\limits_{|}^{|} \\ | ||
− | \end{bmatrix} = \mathbf 0 | + | \end{bmatrix} = \mathbf 0</math> |
− | * | + | * <math>\Rightarrow I x_\text{pivot} + F x_\text{free} = \mathbf 0</math> or <math>x_\text{pivot} = - F x_\text{free}</math> |
* where for $x_\text{free}$ we use "special" choices $\mathbf e_1, \mathbf e_2, ...$ (columns of $I$) | * where for $x_\text{free}$ we use "special" choices $\mathbf e_1, \mathbf e_2, ...$ (columns of $I$) | ||
− | |||
Suppose we have a system $A\mathbf x = \mathbf 0$. Such a system is called homogeneous - because we have $\mathbf 0$ on the right side of the system.
How to solve such a system?
Suppose we have a matrix $A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \\ \end{bmatrix}$
Let's do it:
rank $r$ of a matrix is the number of Pivot variables in the echelon form
During the elimination the nullspace $N(A)$ of $A$ doesn't change
Now let's try to solve this system
$\left\{\begin{array}{rl}
x_1 + 2 x_2 + 2 x_3 + 2 x_4 & = 0 \\
2 x_3 + 4 x_4 & = 0 \\
\end{array}\right.$
We can find some solutions for pivot variables, but what to do with the free ones?
Can we do simpler?
Suppose we have matrix $A$ that we reduced to [math]U = \begin{bmatrix} \boxed 1 & 2 & 2 & 2 \\ 0 & 0 & \boxed 2 & 4 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix}[/math]
So now if we take a look at our new system, we have
Let's rearrange columns in $R$ so first we have the pivot columns, and then the free columns
Why does it happen?