$$

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{array}{rl}x+y+z+w+u& =3,\\ x+2y+2z+2w+2u& =4,\\ x+3y+3z+4w+4u& =5.\end{array}$$

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

$\mathbf{b}$. By setting

$$A=\left[\begin{array}{ccccc}1& 1& 1& 1& 1\\ 1& 2& 2& 2& 2\\ 1& 3& 3& 4& 4\end{array}\right],\mathbf{x}=\left[\begin{array}{c}x\\ y\\ z\\ w\\ u\end{array}\right],\text{ and }\mathbf{b}=\left[\begin{array}{c}3\\ 4\\ 5\end{array}\right],$$

we know the system of linear equations is equivalent to

$A\mathbf{x}=\mathbf{b}$, and we may represent this system by the augmented matrix

$$\left[\begin{array}{cc}A& \mathbf{b}\end{array}\right]=\left[\begin{array}{cccccc}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}{cccccc}1& 1& 1& 1& 1& 3\\ 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 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 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}{cccccc}1& 0& 0& 0& 0& 2\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 0& 1& 1& 0\end{array}\right].$$

Step 3: Recognize the leading variables and the free variables

The echelon form we used above is equivalent to

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

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

$$\mathbf{p}=\left[\begin{array}{c}2\\ 1\\ 0\\ 0\\ 0\end{array}\right],$$

we call it as a special solution of the

$A\mathbf{x}=\mathbf{b}$, 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

$$\left[\begin{array}{c}x\\ y\\ z\\ w\\ u\end{array}\right]=\left[\begin{array}{ccc}2& & \\ 1& -c_1& \\ 0& c_1& \\ 0& & -c_2\\ 0& & c_2\end{array}\right]=\left[\begin{array}{c}2\\ 1\\ 0\\ 0\\ 0\end{array}\right]+c_1\left[\begin{array}{c}0\\ -1\\ 1\\ 0\\ 0\end{array}\right]+c_2\left[\begin{array}{c}0\\ 0\\ 0\\ -1\\ 1\end{array}\right]=\mathbf{p}+c_1{\mathbf{h}}_1+c_2{\mathbf{h}}_2.$$

Note that

${\mathbf{h}}_1$ is usually not a solution of

$A\mathbf{x}=\mathbf{b}$; instead, it is a solution of

$A\mathbf{x}=\mathbf{0}$. This is not suprising after a second thought. By assigning

$z=0$ and

$u=0$, we get the solution

$\mathbf{p}$, so

$A\mathbf{p}=\mathbf{b}$. By assigning

$z=1$ and

$u=0$, we get the solution

$\mathbf{p}+{\mathbf{h}}_1$, so

$A(\mathbf{p}+{\mathbf{h}}_1)=\mathbf{b}$. Combining these two facts along with some algebra, it is straightforward to see

$$A{\mathbf{h}}_1=A(\mathbf{p}+{\mathbf{h}}_1)-A\mathbf{p}=\mathbf{b}-\mathbf{b}=\mathbf{0}.$$

Indeed,

${\mathbf{h}}_1$ is the unique solution of

$A\mathbf{x}=\mathbf{0}$ with

$z=1$ and

$u=0$. Therefore, here is another way to obtain

${\mathbf{h}}_1$. First, consider the homogeneous equation

$A\mathbf{x}=\mathbf{0}$. By running the Gaussian elimination, we know it is equivalent to

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

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

$${\mathbf{h}}_1=\left[\begin{array}{c}0\\ -1\\ 1\\ 0\\ 0\end{array}\right].$$

In a similar way, one may obtain

${\mathbf{h}}_2$ without calculating all the parametrization. (Give it a try!)

Now, the set

$$\mathrm{span}(\{{\mathbf{h}}_1,{\mathbf{h}}_2\})=\{c_1{\mathbf{h}}_1+c_2{\mathbf{h}}_2:c_1,c_2\in \mathbb{R}\}$$

is the solution set of

$A\mathbf{x}=\mathbf{0}$. It is also called the homogeneous solution of

$A\mathbf{x}=\mathbf{b}$, since we have to replace

$\mathbf{b}$ by

$\mathbf{0}$. On the other hand, the set

$$\mathbf{p}+\mathrm{span}(\{{\mathbf{h}}_1,{\mathbf{h}}_2\})=\{\mathbf{p}+c_1{\mathbf{h}}_1+c_2{\mathbf{h}}_2:c_1,c_2\in \mathbb{R}\}$$

is the solution set of

$A\mathbf{x}=\mathbf{b}$. It is also called the general solution of

$A\mathbf{x}=\mathbf{b}$, 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.