Gaussian Elimination
=====
###### tags: '154'
Let's solve the following system, first using Gaussian elimination, then using full Gauss-Jordan elimination.

$$
\begin{align*}
5x + 12y + \hphantom{00}z &= -3\\
2x + \hphantom{0}5y + 22z &= -3\\
\hphantom{0}x + \hphantom{0}2y - \hphantom{0}3z &= \hphantom{-}3
\end{align*}
$$

This gives us the augmented matrix:
$$
\begin{bmatrix}
5&12&1&-3\\
2&5&11&-3\\
1&2&-3&3
\end{bmatrix}
$$
Our first goal is to make the top left entry the only non-zero entry in the first column using valid row operations. Since it is simplest to use 1 to "kill off" other coefficients, let's begin by swapping rows 1 and 3 to give the **equivalent** system, this is denoted $R_1\leftrightarrow R_3$:
$$
\begin{bmatrix}
\color{red}{1}&2&-3&3\\
2&5&2&-3\\
5&12&1&-3
\end{bmatrix}
$$
Now lets multiply row 1 by 2, subtract from row 2 and replace row 2, this is denoted $R_2 \leftarrow R_2 - 2R_1$ (This is a valid row opperation: "add a non-zero multiple of row~i~ to row~j~ and replace row~j~" denoted $R_j\leftarrow R_j+\alpha R_i$). This yields:
$$
\begin{bmatrix}
\color{red}{1}&2&-3&3\\
0&1&8&-9\\
5&12&1&-3
\end{bmatrix}
$$
Now perform $R_3\leftarrow R_3-5R_1$:
$$
\begin{bmatrix}
\color{red}{1}&2&-3&3\\
0&\color{red}{1}&8&-9\\
0&2&16&-18
\end{bmatrix}
$$
Now move over to the next column and do $R_3\leftarrow R_3-2R_2$:
$$
\begin{bmatrix}
\color{red}{1}&2&-3&9\\
0&\color{red}{1}&8&-9\\
0&0&0&0
\end{bmatrix}
$$
This is in echelon form, that is, the "pivots", first non-zero entries in the rows form a descending from left to right pattern.

At this point you can rewrite the system and solve by back substitution using $z=t$ for $t$ an arbitrary real value.
$$
\begin{align*}
x+2y-3t&=9\\
y + 8t &= -9
\end{align*}
$$
Now use back substitution on this "triangular system""

$$
\begin{align*}
y &= -9 - 8t\\
x &= 9 -2(-9 - 8t)+3t = 27 + 19t
\end{align*}
$$

This yields $(x,y,z) = (17+19t,-9-8t,t)=(17,-9,0)+t(19,-8,1)$ for solutions. Thus the solutions set is the line through $(17,-9,0)$ in the direction $(19,-8,1)$.

To complete Gauss-Jordan we would start working right-to-left/bottom-to-top on the pivot columns, to make the pivots, the only non-zero items in a column. To do this in this example just do $R_1\leftarrow R_1-2R_2$
$$
\begin{bmatrix}
\color{red}{1}&0&-19&27\\
0&\color{red}{1}&8&-9\\
0&0&0&0
\end{bmatrix}
$$
This is the reduced row-echelon form (at least as far as the "coefficient" part of the augmented matrix is concerned.)

From this one can just read off the solution and it is exactly as above, namely:
$$
\begin{align*}
y &= -9 - 8z\\
x &= 27 + 19z
\end{align*}
$$
where $z$ can be any real number $t$. This means that the solutions are of the form $(x,y,z) = (27+19t, -9 - 8t, t)$ and we see that the solution is a line in $\mathbb{R}^3$ containing the point $P=(27,-9,0)$ and having direction determined by $\vec{v}=(19,-8,1)$ having the form
$$
P+t\vec v= (27,-9,0) + t(19,-8,1)
$$