{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

# How to solve a system of linear equations?

In high school, we have seen many system of linear equations with a unique solution, and we know how to solve it. Here we are going to learn how to obtain _all_ solutions of a system of linear equation when its solution is not unique.

Consider the system of linear equations

$$
\begin{aligned}
x + y + z + w + u &= 3, \\
x + 2y + 2z + 2w + 2u &= 4, \\
x + 3y + 3z + 4w + 4u &= 5. \\
\end{aligned}
$$

**Step 1: Transform the system into the augmented matrix**

We may record the coefficients on the left into a matrix $A$ and the constants on the right into a vector $\bb$. By setting

$$
A = \begin{bmatrix}
1 & 1 & 1 & 1 & 1 \\
1 & 2 & 2 & 2 & 2 \\
1 & 3 & 3 & 4 & 4 \\
\end{bmatrix},\
\bx = \begin{bmatrix} x \\ y \\ z \\ w \\ u \end{bmatrix}, \text{ and }
\bb = \begin{bmatrix} 3 \\ 4 \\ 5 \end{bmatrix},
$$

we know the system of linear equations is equivalent to $A\bx = \bb$, and we may represent this system by the **augmented matrix**

$$
\left[\begin{array}{c|c}
A & \bb
\end{array}\right] =
\left[\begin{array}{ccccc|c}
1 & 1 & 1 & 1 & 1 & 3 \\
1 & 2 & 2 & 2 & 2 & 4 \\
1 & 3 & 3 & 4 & 4 & 5 \\
\end{array}\right].
$$

**Step 2: Make it into an echelon form**

By running Gaussian elimination, which is a sequence of row operations, we may obtain

$$
\left[\begin{array}{ccccc|c}
{\color{red}1} & 1 & 1 & 1 & 1 & 3 \\
0 & {\color{red}1} & {\color{red}1} & 1 & 1 & 1 \\
0 & 0 & 0 & {\color{red}1} & {\color{red}1} & {\color{red}0} \\
\end{array}\right].
$$

This stair-like structure is called an **echelon form** . The term _echelon_ is a way to arrange the troops in military; see the pictures in [Wikipedia: Echelon formation](https://en.wikipedia.org/wiki/Echelon_formation) to get a better sense of this name.

Note that, if preferred, one may run Gaussian elimination further to get the **reduced echelon form**

$$
\left[\begin{array}{ccccc|c}
{\color{red}1} & 0 & 0 & 0 & 0 & 2 \\
0 & {\color{red}1} & {\color{red}1} & 0 & 0 & 1 \\
0 & 0 & 0 & {\color{red}1} & {\color{red}1} & {\color{red}0} \\
\end{array}\right].
$$

**Step 3: Recognize the leading variables and the free variables**

The echelon form we used above is equivalent to

$$
\begin{aligned}
x + & y + z + & w + u &= 3, \\
~ & y + z + & w + u &= 1, \\
~ & ~ & w + u &= 0. \\
\end{aligned}
$$

The first (left-most) variable with nonzero coefficient on each equation is called a **leading variable** . In this case, we have three leading variables $x$, $y$, and $w$. Any variable that is not a leading variable is called a **free variable** . In this case, $z$ and $u$ are the free variables.

Note that given any numbers for the free variables, the leading variables are uniquely determined, as we will see in the next two steps.

**Step 4: Find a special solution**

For example, we may assign $z = 0$ and $u = 0$. Thus, we solve, from right to left, that $w = 0$, $y = 1$, and $x = 2$. Recording these numbers as a vector

$$
\bp = \begin{bmatrix} 2 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix},
$$

we call it as a **special solution** of the $A\bx = \bb$, which means it is one of the solution.

**Step 5: Find the homogeneous solutions**

In fact, we may assign $z = c_1$ and $u = c_2$ to get all solutions. Thus, we have

$$
\begin{bmatrix} x \\ y \\ z \\ w \\ u \end{bmatrix} =
\begin{bmatrix}
2 & & \\
1 & -c_1 & \\
0 & c_1 & \\
0 & & -c_2 \\
0 & & c_2 \\
\end{bmatrix} =
\begin{bmatrix} 2 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} +
c_1\begin{bmatrix} 0 \\ -1 \\ 1 \\ 0 \\ 0 \end{bmatrix} +
c_2\begin{bmatrix} 0 \\ 0 \\ 0 \\ -1 \\ 1 \end{bmatrix} =
\bp + c_1\bh_1 + c_2\bh_2.
$$

Note that $\bh_1$ is usually _not_ a solution of $A\bx = \bb$; instead, it is a solution of $A\bx = \bzero$. This is not suprising after a second thought. By assigning $z = 0$ and $u = 0$, we get the solution $\bp$, so $A\bp = \bb$. By assigning $z = 1$ and $u = 0$, we get the solution $\bp + \bh_1$, so $A(\bp + \bh_1) = \bb$. Combining these two facts along with some algebra, it is straightforward to see

$$
A\bh_1 = A(\bp + \bh_1) - A\bp = \bb - \bb = \bzero.
$$

Indeed, $\bh_1$ is the unique solution of $A\bx = \bzero$ with $z = 1$ and $u = 0$. Therefore, here is another way to obtain $\bh_1$. First, consider the **homogeneous equation** $A\bx = \bzero$. By running the Gaussian elimination, we know it is equivalent to

$$
\begin{aligned}
x + & y + z + & w + u &= 0, \\
~ & y + z + & w + u &= 0, \\
~ & ~ & w + u &= 0, \\
\end{aligned}
$$

which are the same equations we have been using except that the constants on the right are replaced by zeros. By solving this homogeneous system with $z = 1$ and $u = 0$, we see again that

$$
\bh_1 = \begin{bmatrix} 0 \\ -1 \\ 1 \\ 0 \\ 0 \end{bmatrix}.
$$

In a similar way, one may obtain $\bh_2$ without calculating all the parametrization. (Give it a try!)

Now, the set

$$
\vspan(\{\bh_1, \bh_2\}) = \{c_1\bh_1 + c_2\bh_2: c_1, c_2\in\mathbb{R}\}
$$

is the solution set of $A\bx = \bzero$. It is also called the **homogeneous solution** of $A\bx = \bb$, since we have to replace $\bb$ by $\bzero$. On the other hand, the set

$$
\bp + \vspan(\{\bh_1, \bh_2\}) = \{\bp + c_1\bh_1 + c_2\bh_2: c_1, c_2\in\mathbb{R}\}
$$

is the solution set of $A\bx = \bb$. It is also called the **general solution** of $A\bx = \bb$, in contrast to a special solution.

As a summary, the general solution is equal to a special solution plus the homogeneous solution.

*This note can be found at Course website > Learning resources.*