7 Gaussian elimination

7.1 A systematic way to solve systems of linear equations

Figure 7.1: Carl Friedrich Gauss. Painting by Christian Albrecht Jensen (approx. 1840).

You saw two ways of solving a small system of linear equations, graphically and algebraically. Of course, solving a system graphically gives us very limited capabilities, both in precision and in the number of dimensions (variables) we can handle. Algebraically solving a system of equations is accurate, but becomes more tedious the more variables there are. Unless you use a systematic way. The common systematic way to solve any system of linear equations is to use an algorithm named after Carl Friedrich Gauss¹ (Figure 7.1). The procedure is called Gaussian elimination with back-substitution. This algorithm is still used today, also in computer programs to solve systems of linear equations. Gaussian elimination is useful because it will also yield a number of fundamental facts about the solution set of the system of equations.

Gaussian elimination consists of a set of general rules by which we can manipulate a system of linear equations without changing its solution set, and a systematic way to apply these rules to approach the solution. The final goal of the manipulations in Gaussian elimination is to obtain a system of equations that has a (upper) triangular shape, like the system of equations Equation 7.1.

\[ \begin{align*} a_{11} x + a_{12} y + a_{13} z + \dots a_{1n} v & = b_1 \\ a_{22} y + a_{23} z + \dots a_{2n} v & = b_2 \\ a_{33} z + \dots a_{3n} v & = b_3 \\ \dots & = \dots \\ a_{nn} v & = b_n \end{align*} \tag{7.1}\]

Such a system can be more easily solved than the original set of equations. Calculating a value for each variable by so-called back-substitution starts from the bottom of the triangular set of equations. You first solve the last equation for \(v\), then substitute this value of \(v\) in the second to last equation and solve that one for the second to last variable. You continue working upwards in the list until you finally substitute all variables in the first equation and solve that one for \(x\). The way to obtain a triangular set of equations is to manipulate the equations using a set of operations that leaves the solution set of the system of equations intact. The rules for manipulating the equations are:

Any two equations may exchange position
Any equation can be multiplied by a non-zero scalar on both sides of the equal sign
Any equation can be added to (or subtracted from) any other equation in the system

These operations will not change the solution of the system of equations (see Section 7.3), so that the new set of equations is equivalent to the original set. The following scheme describes a systematic way (an algorithm) of carrying out these operations in order to reach a triangular system. Most people apply the rules intuitively, but here they are written out:

Procedure for Gaussian elimination

Set the first equation to be the operating equation, and the first variable to be the target variable.
If the operating equation is the last equation then stop, else continue with 3.
If the operating equation has a non-zero coefficient for the target variable then continue with 4, else continue with 6.
To each equation below the operating equation add or subtract a multiple of the operating equation so that the coefficient of the target variable becomes 0.
Set the equation immediately below the operating equation to be the new operating equation and the variable following the target variable to be the new target variable. Continue with 2.
Find the first equation below the operating equation for which the target variable has a non-zero coefficient. If there is an equation below the operating equation for which the coefficient of the target variable is not zero then exchange that equation with the target equation, make it the new target equation and continue with 4. Else if the target value is not the last variable make the next variable the target variable and continue with 4. Else stop.

We demonstrate this procedure by an example.

Example 7.1 (Gaussian elimination) \[ \begin{alignedat}{4} x & {}+{} & y & {}+{} & 3z &= 12\\ 2x & {}+{} & 2y & {}+{} & z &= 9\\ x & {}-{} & y & {}+{} & z &= 2 \end{alignedat} \]

The first equation is the operating equation and the first variable, \(x\) the target variable.The equations have to be manipulated in such a way that the \(x\) ’s disappear from the second and third equation (step 4). We subtract the first equation multiplied on both sides by 2 from the second equation and get:

\[ \begin{alignedat}{4} x & {}+{} & y & {}+{} & 3z &= 12 \\ & & & & -5z &= -15 \\ x & {}-{} & y & {}+{} & z &= 2 \end{alignedat} \]

and we subtract the first equation from the third equation:

\[ \begin{alignedat}{4} x & {}+{} & y & {}+{} & 3z &= 12 \\ & & & & -5z &= -15 \\ & & -2y & {}-{} & 2z &= -10 \end{alignedat} \]

Our new target variable is \(y\) , but the second equation has a coefficient equal to 0 for this variable, so we exchange it with the third equation:

\[ \begin{alignedat}{4} \textcolor{red}{1}x & {}+{} & y & {}+{} & 3z &= 12 \\ & & \textcolor{red}{-2}y & {}-{} & 2z &= -10 \\ & & & & \textcolor{red}{-5}z &= -15 \end{alignedat} \]

This system has a triangular shape, and we are finished! Now we can use back-substitution to obtain values for the variables. From the last equation we obtain \(z=3\) . Substituting that in the second equation we get \(-2y - 6 = -10\) , or \(2y = 4\) or \(y=2\) . Substituting \(z\) and \(y\) in the first equation we get \(x + 2 + 9 = 12\) , or \(x = 1\) . So, the solution is \((x,y,z) = (1,2,3)\) .

The leftmost coefficients in the triangular form, the ones that are printed in red above, are called the pivot elements of a system of linear equations. We will discuss these pivot elements more often. Their values are uniquely determined by the Gaussian elimination procedure.

Once you know the procedure of Gaussian elimination by heart, it is usually easier to make a few short-cuts, and adapt your notation somewhat. For example, writing down the variables each time is tedious. Since the coefficients provide all information needed, why not just write down only these? Also, a short-cut would be to eliminate the target variable in all following equations in one sweep. The sequence above could then be abbreviated as:

\[ \begin{array}{rrr|r} 1 & 1 & 3 & 12 \\ 2 & 2 & 1 & 9 \\ 1 & -1 & 1 & 2 \end{array} \quad\yields\quad \begin{array}{rrr|r} 1 & 1 & 3 & 12 \\ 0 & 0 & -5 & -15 \\ 0 & -2 & -2 & -10 \end{array} \quad\yields\quad \begin{array}{rrr|r} \textcolor{red}{1} & 1 & 3 & 12 \\ 0 & \textcolor{red}{-2} & -2 & -10 \\ 0 & 0 & \textcolor{red}{-5} & -15 \end{array} \]

We have used vertical lines to indicate the left- and right-hand sides of the equations.

7.2 What Gaussian elimination tells us about the solution set

To illustrate what Gaussian elimination can tell us about the solution set of system of equations we start with an example.

\[ \begin{alignedat}{8} v & {}+{} & 2w & {}+{} & x & {}+{} & 2y & = 2 \\ & & w & & & {}+{} & 2y & = 1 \\ v & {}+{} & w & {}+{} & x & & & = 1 \end{alignedat} \]

First of all, we can say that this is a system of 3 equations with 4 variables. So, we can already conclude that at least one of the variables can not be tied to a single value. This means that the solution set of this system will have at least one free variable, but perhaps even more, which we will find out now using Gaussian elimination.

\[ \begin{array}{rrrr|r} 1 & 2 & 1 & 2 & 2 \\ 0 & 1 & 0 & 2 & 1 \\ 1 & 1 & 1 & 0 & 1 \end{array} \quad\yields\quad \begin{array}{rrrr|r} 1 & 2 & 1 & 2 & 2\\ 0 & 1 & 0 & 2 & 1\\ 0 & -1 & 0 & -2 & -1 \end{array} \quad\yields\quad \begin{array}{rrrr|r} \textcolor{red}{1} & 2 & 1 & 2 & 2\\ 0 & \textcolor{red}{1} & 0 & 2 & 1\\ 0 & 0 & 0 & 0 & 0 \end{array} \]

This shows that the third equation drops out. Apparently it provides no extra information about the variables in addition to the first two equations. This must also mean that we have two free variables in the solution set, instead of the one that we expected based on the numbers of variables and equations. The two remaining equations only allow us to express two of the variables in terms of the two other, free variables. To be more concrete, we could express the variables \(v\) and \(w\) in terms of \(x\) and \(y\), as follows:

\[ \begin{align*} w & = 1 - 2y \\ v & = 2 - x - 2y - 2w = 2y - x \end{align*} \] Hence, the solution set is

\[ \{(v,w,x,y)| x \in \mathbb{R} \textrm{, } y \in \mathbb{R} \textrm{, } v = 2y - x \textrm{, } w = 1 - 2y \} \]

The pivot elements have been printed in red again. As you can see, the number of non-free variables equals the number of pivot elements after Gaussian elimination of a system of linear equations. Hence, the number of free variables equals the total number of variables minus the number of pivot elements.

A system of linear equations with \(n\) variables and \(m\) equations:

has at least \(n - m\) free variables.
after Gaussian elimination has at most \(m\) pivot elements.
has \(n - \#\text{pivots}\) free variables in its solution set.

7.3 Gaussian elimination does not change the solution set

This section is not really needed to understand Gaussian elimination, and you can skip it if you want. However, its consequences are essential, namely that the set of operations used for Gaussian elimination does not modify the solution set of the system of equations. Otherwise the method would clearly be invalid. Here, we provide an explanation for each of the three rules. However, a more fundamental proof for all three rules originates from the fact that Gaussian elimination can be regarded as a set of matrix multiplications of which each matrix has an inverse, as explained in Section 11.4.

It’s almost trivial why Gaussian elimination does not change the solution set when applying the first and second rules, but for the third rule, adding an equation to another, it is not immediately clear. We use the language and knowledge of set theory to demonstrate the validity of these rules. As we said above, the solution set of a system of equations is the intersection of the solution sets of the individual equations. Having \(n\) equations with solution sets \(A_1, A_2, \ldots A_n\) the solution set of the system is \(A_1 \cap A_2 \cap \ldots \cap A_n\) .

Rule 1: The first rule says that we can exchange the position of equations.

Proof. In terms of the solution set, this is equivalent to exchanging the positions of solution sets \(A_1, A_2, \ldots A_n\) in the intersection equation \(A_1 \cap A_2 \cap \ldots \cap A_n\) . This will not change the intersection of all individual solution sets, as you may easily conclude by drawing a few Venn diagrams, or from the following rules:

\(A \cap B = B \cap A\) and
\((A \cap B) \cap C = A \cap (B \cap C)\)

Rule 2: The second rule, multiplying an equation on both sides by a non-zero scalar will not change the solution set of that individual equation, and hence, it will not change the solution set of the system of equations either.

Proof. This is almost trivial, as the generating equation in the set comprehension notation of the solution set of an equation is the equation itself, and solution (sets) of an equation do not change by the multiplication of an equation by a non-zero constant on both sides of the equal sign.

What happens if you multiply both sides of an equation by 0? Is the original solution still valid? Did the solution set change? If so, in what way?

Rule 3: The third rule, adding one equation to another, will leave the intersection of the solution sets of these two equations unchanged, and will therefore also not change the intersection of all solution sets.

Proof. Suppose that \(A\) and \(B\) are the solution sets of the two equations and \(B'\) is the solution set of the sum of the first and second equation. Then we want to show that \(A \cap B = A \cap B'\).

Suppose that

\[\begin{align*} A & = \left\{(x_1,x_2,\ldots,x_n) | \sum_{i=1}^n a_{1i} x_i = b_1 \right\} \\ B & = \left\{(x_1,x_2,\ldots,x_n) | \sum_{i=1}^n a_{2i} x_i = b_2 \right\} \end{align*}\]

and the set-comprehension equation for \(B'\) is based on the sum of these two equations:

\[ B' = \left\{(x_1,x_2,\ldots,x_n) | \sum_{i=1}^{n} (a_{1i} + a_{2i}) x_i = b_1 + b_2 \right\} \]

where \(\sum_{i=1}^n a_{1i} x_i = b_1\) and \(\sum_{i=1}^n a_{2i} x_i = b_2\) are the most general forms of linear equations (in \(n\) variables \(x_1, \ldots, x_n\) ). Let’s deduce a set comprehension for the solution set \(A \cap B\) . From the first equation, we can express \(x_1\) in terms of the other variables.

\[ x_1 = \frac{b_1}{a_{11}} - \sum_{i=2}^{n} \frac{a_{1i}}{a_{11}} x_i \]

Substituting this in the second equation we get

\[ a_{21} \left( \frac{b_1}{a_{11}} - \sum_{i=2}^{n} \frac{a_{1i}}{a_{11}} x_i \right) + \sum_{i=2}^{n} a_{2i} x_i = b_2 \]

Multiplying both sides of the equation by \(a_{11}\) we get

\[ a_{21} b_1 - \sum_{i=2}^{n} a_{21} a_{1i} x_i + \sum_{i=2}^{n} a_{11} a_{2i} x_i = a_{11} b_2 \]

from which we finally obtain

\[ \sum_{i=2}^{n} \left(a_{11} a_{2i} - a_{21} a_{1i} \right) x_i = a_{11} b_2 - a_{21} b_1 \]

This equation describes the relation between variables \(x_2 \ldots x_n\) (\(x_1\) has been eliminated), and is the generating equation for the solution set \(A \cap B\) . The sum of these two equations can be written as (taking the term with \(x_1\) out of the \(\sum{}\) term)

\[ \left( a_{11} + a_{21} \right) x_1 + \sum_{i=2}^{n} (a_{1i} + a_{2i}) x_i = b_1 + b_2 \]

Again, we substitute the solution for \(x_1\) in terms of the other variables obtained from the first equation in this new second equation:

\[ \left( a_{11} + a_{21} \right) \frac{b_1}{a_{11}} - \sum_{i=2}^{n} \frac{a_{11} + a_{21}}{a_{11}} a_{1i} x_i + \sum_{i=2}^{n} \left( a_{1i} + a_{2i} \right)x_i = b_1 + b_2 \]

Multiplying both sides of the equation by \(a_{11}\) we get

\[ \left( a_{11} + a_{21} \right) b_1 - \sum_{i=2}^{n} \left( a_{11} + a_{21} \right) a_{1i} x_i + \sum_{i=2}^{n} a_{11} \left( a_{1i} + a_{2i} \right) x_i = a_{11} b_1 + a_{11} b_2 \]

Taking the \(\sum{}\) terms together and bringing the constant terms to the right side this becomes

\[ \sum_{i=2}^{n} \left( a_{11} a_{1i} + a_{11} a_{2i} - a_{11} a_{1i} - a_{21} a_{1i} \right) x_i = a_{11} b_1 + a_{11} b_2 - a_{11} b_1 - a_{21} b_1 \]

in which a few terms cancel to obtain:

\[ \sum_{i=2}^{n} \left( a_{11} a_{2i} - a_{21} a_{1i} \right) x_i = a_{11} b_2 - a_{21} b_1 \]

which is the generating equation for the intersection set \(A \cap B'\) . It is the same as the equation obtained before for \(A \cap B\) , therefore \(A \cap B = A \cap B'\).

7.4 Exercises

Gaussian elimination

Exercise 6.

Solve this system by Gaussian elimination, determine whether there is a unique solution, or an infinite solution set. \[ \begin{align*} x + y & = 0 \\ 3x - 5y & = 0 \end{align*} \]

Exercise 7.

Solve this system by Gaussian elimination, determine whether there is a unique solution, or an infinite solution set. \[ \begin{align*} 2x + y & = 5 \\ 4x + 2y & = 10 \end{align*} \]

Exercise 8.

Solve this system by Gaussian elimination, determine whether there is a unique solution, or an infinite solution set. \[ \begin{align*} x - 2y + z & = 5 \\ 3x + 2y - z & = 12 \\ -x + 2y + z & = 10 \end{align*} \]

Exercise 9.

Reduce the following system of equations by Gaussian elimination to upper-triangular form. Circle the pivots and solve by back-substitution of \(z\), \(y\) and \(x\). \[ \begin{align*} 2x + 3y + z = 8 \\ 4x + 7y - 5z = 20 \\ -2y + 2z = 0 \end{align*} \]

Exercise 10.

Solve the system and find the pivots when \[ \begin{align*} 2u + 3v & = 0 \\ 4u + 5v + w & = 3 \\ 2u - v - 3w & = 5 \end{align*} \]

Exercise 11.

Solve the system and find the pivots when \[ \begin{align*} 2u - v & = 0 \\ -u + 2 v - w & = 0 \\ -v + 2 w - z & = 0 \\ -w + 2 z & = 5 \end{align*} \]

Exercise 12.

Describe the intersection of the three planes \(u + v + w + z = 6\) and \(u + w + z = 4\) and \(u + w = 2\) (all in four-dimensional space) in geometrical terms. Is it a line or a point or an empty set? What is the intersection if the fourth plane \(u = -1\) is included?

Exercise 13.

We have the following set of equations \[ \begin{align*} u + \ v + \ w & = b_1 \\ u + 3 v + 3 w & = b_2 \\ u + 3 v + 5 w & = b_3 \end{align*} \] where \(b_1=2\), \(b_2=0\), and \(b_3=2\).

a. What is the triangular form of this system of equations?

b. What is the solution for \(u\), \(v\), and \(w\)?

c. Suppose that \(u=\ln{x}\), \(v=\ln{y}\) and \(w=\ln{z}\), where \(x, y, z \in \mathbb{R}^+\), where \(\mathbb{R}^+\) is the set of positive real numbers. What would be the constraints (if any) on \(b_1\), \(b_2\) and \(b_3\) to always obtain a unique (single) solution for \(x\), \(y\), and \(z\)?

Tip

Solve the set of equations while leaving \(b_1\), \(b_2\) and \(b_3\) as unknowns.

The Wikipedia lemma on this subject tells us that the name Gaussian elimination is due to a misunderstanding about the history of the method.↩︎