How to solve a system of linear equations

This post explains how to find the solutions of any system of linear equations with an arbitrary number of variables, if solutions exist. The method consists of the following three steps:

Using Gauss elimination we write the system in triangular form.
In this format, we see whether the system has either no solution, exactly one solution or infinitely many solutions.
If there are solutions, we determine them by simple insertions.

We start with a system of $m$ linear equations in $n$ variables $x_1,...,x_n$ :

$a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n} = b_{1},\\ a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n} = b_{2},\\ \vdots\\ a_{m1}x_{1}+a_{m2}x_{2}+...+a_{mn}x_{n} = b_{m}$

The $a_{ij}$ and $b_j$ are elements of a given field, for example the real numbers. We want to solve the system for each of the $x_i$ if possible.

Simple insertions

Let us at first consider a very basic strategy: We solve one of the equations for one of the variables, say $x_n$ . Then we insert the result for $x_n$ into the other equations and pick one of them to solve for the next variable, and so on. For very simple systems, this is indeed all we need to do. For example in

$\begin{array}{ccccc} x_1 & + & 2x_2 & = & 7\\ & & 4x_2 & = & 8 \end{array}$

we solve the second equation to obtain $x_2=2.$ Inserting this into the first equation gives $x_1 + 4 = 7$ from which we easily obtain $x_1 = 3$ . We have arrived at the unique solution of the system.

This was so easy, because the second equation depends on less variables than the first one. This tells us, that we should start solving with the second one and it also tell us, that the basic method of insertions will lead to some result. However, many linear systems are not that simple. In particular, there are cases which do not have a solution at all, for example

$\begin{array}{ccccc} x_1 & + & x_2 & = & 3\\ 2x_1& + & 2x_2 & = & 3. \end{array}$

These two equations contradict each other, so there are no values for $x_1,x_2$ which satisfy both of them. In this case, it is still easy to see that there is no solution. However, for more complicated systems, it can by much less obvious whether solutions exist. One can try to find out by the basic method of insertions as above, but this can get messy very easily. It also can be frustrating to do many insertions just to find out that there is no solution at all.

Triangular shape

Therefore we follow a different strategy for complicated systems: Before we do the insertions, we try to bring the system into a shape where every equation depends on less variables than the previous one. This is often called triangular shape, even though it does not have to look like a triangle like the simple example above. It is fine if the last equation still depends on several variables, as long as it depends on less than the previous one. For example we would be happy with the shape

$\begin{array}{cccccccccc} x_1 & + & x_2 & - & 9x_3 & - & x_4 & = & 2\\ & & 5x_2 & + & x_3 & + & 5x_4 & = & 7\\ & & & & x_3 & - & 2x_4 & = & 2. \end{array}$

If a system is in this shape, we can easily use the basic method of insertions successively, starting with the last equation, and we will find solutions. In this example, we decide whether we solve the last equation for $x_3$ or $x_4$ and leave the other variable as it is. This undetermined variable may take any value, so we arrive at an infinite number of solutions in such a case.

If we are given a system, which is not in this shape, there is still good news: There is a method called Gauss elimination, by which any system can be manipulated such that it either takes triangular shape or produces an obvious contradiction. In the first case, it can be solved by insertions and in the latter case, there is no solution.

How does Gauss elimination work?

Gauss elimination uses the fact that we may manipulate any system of linear equations by the following three operations without changing its solutions:

We obviously may change the order of the equations.
We may multiply an equation with any number which is not zero.
We may add an equation to another one (keeping this equation in the system as well).

The following simple example shows how these operations can help to get to a triangular shape. We consider the system

$\begin{array}{ccccc} x_1 & + & 2x_2 & = & 4\\ 3x_1& - & 5x_2 & = & 1. \end{array}$

This system is not in triangular shape. In particular, the second equation has a factor 3 in front of $x_1$ . If this factor would be zero instead, we would have a triangular shape and could proceed with simple insertions. The trick is now to force this factor to become zero by the mentioned operations. Each of the three operations alone do not help: Changing the order does not do anything here, multiplying with a number (unequal zero) does not make this factor vanish, and if we add the first equation to the second one, it does not help either. However, if we combine these operations, we are getting what we want. We take the first equation times $-3$ and then add it to the second one. In this way we obtain:

$\begin{array}{ccccc} x_1 & + & 2x_2 & = & 4\\ & - &11x_2 & = & -11. \end{array}$

Now we have a system in triangular shape and solving it is easy. (One obtains $x_2=1$ from the second equation and $x_1=2$ by insertion into the first one.) We have been a bit lucky in this example, because the factor of $x_1$ in the first equation is 1. So we only need to multiply with -3 before we add. However, if in the first equation there was a factor $a$ in front of $x_1$ , we would have to just multiply with $\frac{-3}{a}$ before adding it to the second one.

The algorithm

Gauss elimination combines the above steps systematically for all $m$ equations and $n$ variables until the system is in triangular form. The method can be formulated as the following algorithm:

Start with equation $i=1$ and variable $x_{j}=x_{1}.$
If $a_{ij}=0$ search for a $r>i$ for which $a_{rj}\neq0$ and exchange the order of equations $r$ and $i$ .
(This step moves equations downwards, which have missing variables from the beginning.)
If in step 2 no $r$ is found, set $j\rightarrow j+1$ and repeat from step 2. (End when $j=n+1$ .)
Equation $i$ is now beginning with $a_{ij}x_{j}+...$
Multiply this equation with $\frac{1}{a_{ij}}.$
(Now it starts with $x_{j}+...$ )
For all $r>i:$ Add $(-a_{rj})$ times the $i$ -th equation to the $r$ -th equation.
(This erases variable $x_j$ in the $r$ -th equation.)
Set $i\rightarrow i+1,$ $j\rightarrow j+1$ and repeat everything starting from step 2. End at $i=m+1$ or $j=n+1.$

After applying these steps, the system will be in triangular shape. Generally speaking we will always obtain:

$\begin{array}{ccccccccc} a_{1s_{1}}x_{s_{1}} & + &a_{1s_{2}}x_{s_{2}} & + & ... & + & a_{1n}x_{n} & = & b_{1},\\ & & a_{2s_{2}}x_{s_{2}}& + & ... & a_{2n}x_{n} & = & b_{2},\\ & & & & & & & \vdots &\\ & & a_{rs_{r}}x_{s_{r}} & + & ...& +& a_{rn}x_{n} & = & b_{r},\\ & & & & & & 0 & = & b_{r+1},\\ & & & & & & &\vdots &\\ & & & & & & 0 & = & b_{m},\\ \end{array}$

where $1\leq s_{1}<s_{2}<...<s_{r}\leq n.$ The number $r$ of non-trivial equations which still involve at least one variable is called the rank of the system.

How many solutions does the system have?

We can now determine the number of solutions from the rank $r$ . Recall that $m$ is the total number of equations and $n$ is the number of variables. The following cases are possible:

If $r<m$ Gauss elimination has produced some trivial equations $0=b_{r+1}, ..., 0=b_{m}$ at the end of the system. (This will always happen if $m>n$ but it can also happen in other cases.) The system has no solution if any of these trivial equations is wrong, meaning that any of the constants $b_{r+1}, ..., b_{m}$ would not be zero. It is one of the great advantages of Gauss elimination that all possible contradictions in a system of equations are reduced to such a simple form.
If $r=n$ the system has exactly one solution. This means that each variable can only take exactly one value in order to satisfy the system. This solution can now be found by the above method of simple insertions.
In the case of $r<n$ the system has infinitely many solutions. In order to express this space of solutions, we can choose $n-r$ variables which we just leave undetermined. Then we can use the method of simple insertions to express all the other variables in terms of the undetermined ones.

Example

Let us conclude this post with the example

$\begin{array}{ccccccc} & &3x_{2}&+& 6x_{3} &=&3,\\ 4x_{1}&+&8x_{2}&+&16x_{3}&=&16,\\ 2x_{1}&+&6x_{2}&+&4x_{3}&=&2\\ \end{array}$

In order to keep the computations relatively short, I use the following short-hand notation, which is very common in the context of Gauss elimination: For any system

$\begin{array}{ccccccccc} a_{11}x_{1} & + & a_{12}x_{2} &+& ... &+& a_{1n}x_{n} & = & b_{1},\\ a_{21}x_{1} & + & a_{22}x_{2} &+& ... &+& a_{2n}x_{n} & = & b_{2},\\ &&&&&&& \vdots &\\ \end{array}$

we only write the coefficients $a_{ij}$ and the constants $b_i$ in the following way:

$\left. \begin{array}{cccc} a_{11} & a_{12} & \ldots & a_{1n}\\ a_{21} & a_{22} & \ldots & a_{2n}\\ & \vdots&&\\ \end{array} \right| \begin{array}{c} b_{1}\\ b_{2}\\ \vdots\\ \end{array}$

By the position in this scheme we keep track of which coefficient belongs to which variable. In this notation our example becomes:

$\left. \begin{array}{ccc} & 3 & 6\\ 4 & 8 & 16\\ 2 & 6 & 12 \end{array} \right| \begin{array}{c} 3\\ 16\\ 14\\ \end{array}$

The system is not in triangular shape, so we start with the Gauss elimination algorithm. According to step 1 we consider $x_1$ at first. As the first equation does not depend on $x_1$ , but the second one does, we change the order of these equations according to step 2 and obtain

$\left. \begin{array}{ccc} 4 & 8 & 16\\ & 3 & 6\\ 2 & 6 & 12\\ \end{array} \right| \begin{array}{c} 16\\ 3\\ 14\\ \end{array}$

According to step 4 we now divide the first equation by the coefficient of $x_1$ and obtain

$\left. \begin{array}{ccc} 1 & 2 & 4\\ & 3 & 6\\ 2 & 6 & 12\\ \end{array} \right| \begin{array}{c} 4\\ 3\\ 14\\ \end{array}$

Following step 5 we multiply the first equation with $-2$ and add it to the third equation, such that this one does not depend on $x_1$ anymore:

$\left. \begin{array}{ccc} 1 & 2 & 4\\ & 3 & 6\\ & 2 & 4\\ \end{array}\right|\begin{array}{c} 4\\ 3\\ 6\\ \end{array}$

There is nothing left to do regarding the first variable and first equation, so by step 6 we proceed with $x_2$ and the second equation. Following step 4, we divide this equation by $3$ and obtain:

$\left. \begin{array}{ccc} 1 & 2 & 4\\ & 1 & 2\\ & 2 & 4\\ \end{array} \right| \begin{array}{c} 4\\ 1\\ 6\\ \end{array}$

According to step 5 we add $-2$ times the second equation to the third one and obtain:

$\left. \begin{array}{ccc} 1 & 2 & 4\\ & 1 & 2\\ & & 0\\ \end{array}\right|\begin{array}{c} 4\\ 1\\ 0\\ \end{array} \, \, \, \longrightarrow \, \, \, \begin{array}{ccccccc} x_1& +&2x_{2}&+& 4x_{3} &=&4,\\ &&x_{2}&+&2x_{3}&=&1,\\ &&&&0&=&0\\ \end{array}$

Now we are done. The system is in triangular shape. The last equation has become trivial, which means that it was just a linear combination of the previous two and therefore it actually didn’t add any restriction to the solutions. As this trivial equation $0=0$ is obviously true, we know that solutions exist. As we are left with two non-trivial equations, the rank of the system is $r=2$ . It is smaller than the number of variables $n=3$ . Therefore we have infinitely many solutions and we have to leave $n-r$ variables undetermined.

In order to determine the space of solutions, we apply simple insertions. Let us leave $x_3$ undetermined. Solving the second equation leads to $x_2=1-2x_3.$ Inserting this formula into the first equation, we obtain $x_1=2$ . Up to $x_3$ , which may take any value, these equations determine the solutions for the system.