# Gaussian Elimination

Consider the system of linear equations:

(1)If we take what is known as the **augmented matrix** of this system, that is, the matrix corresponding the coefficients and constants of the system, $\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & b_1\\ a_{21} & a_{22} & \cdots & a_{2n} & b_2\\ \vdots & \vdots & & \vdots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & b_{m} \end{bmatrix}$ and reduce it to Row Echelon Form, then we will be able to solve the system rather easily.

For example, consider the following system of linear equations:

(2)The augmented matrix for this system is $\begin{bmatrix} 2 & 3 & -1 & 2\\ 2 & 4 & 1 & 4\\ 1 & 2 & 1 & 1 \end{bmatrix}$. If we reduce this matrix to REF, we obtain the following matrix (as you should verify):

(3)From this matrix we can extract the following set of linear equations that is much easier to work with:

(4)Clearly we can see a solution $(x, y, z) = (-9, 6, -2)$ to the original system of linear equations. Sometimes we may have to use the algebraic technique of back substitution as well which we will now describe.

# Back Substitution

Consider the following augmented matrix for a system of 3 linear equations and 4 unknowns $x_1, x_2, x_3, x_4$ that has already been put into REF:

(5)From this we obtain the following linear equations:

(6)The variables $x_1, x_2, x_3$ correspond to leading $1$s in the matrix, so we call them **leading variables**, while the variable $x_4$ is called a **free variable** or a **pivot**.

To solve this system, we let our free variables equal some arbitrary value, say $t$. So let $x_4 = t$ for $t \in \mathbb{R}$. Therefore we obtain a general solution:

(7)That is for all $t \in \mathbb{R}$, there exists a solution $(x_1, x_2, x_3, x_4) = (-1 - 4t, 6 - 2t, 2 - 3t, t)$. For for any value of $t \in \mathbb{R}$ we get a corresponding solution to the system, and so this system has infinitely many solutions.

## Example 1

**Given the following REF matrix that represents a system of 3 linear equations in 3 variables $x_1, x_2, x_3$, find a solution.**

We obtain the following system of linear equations:

(9)We first note that $x_3 = 4$. We can back-substitute this into the second equation to get that:

(10)Therefore $x_2 = -2$. Lastly, we can substitute this information into the first equation to get that:

(11)Therefore we have one solution to our system, namely $(x_1, x_2, x_3) = (6, -2, 4)$