1.2 Solving Linear Systems via Gaussian Elimination

1Reading¶

Material related to this page, as well as additional exercises, can be found in ALA Ch. 1.1, LAA Ch 1.1, and ILA Ch. 2.2. These notes are mostly based on ALA Ch 1.1.

2Learning Objectives¶

By the end of this page, you should know:

what a linear equation is, how to identify one, and how they combine to form a system of linear equations (also called a linear system)
what a solution set is, and the kinds of solution sets a linear system can have
how to solve most small systems of linear equations by hand using Gaussian Elimination

3Terminology¶

A linear equation^[1] in the variables $x_1,\dots,x_n$ is an equation that can be written in the form

a_1x_1 + a_2x_2+\cdots+a_nx_n = b,

(1)

where $b$ and the coefficients $a_1,a_2,\dots,a_n$ are real or complex numbers^[2] that are typically known in advance. The subscript $n$ is a positive integer, and encodes how many variables appear in the linear equation. When we ask you to solve problems by hand, $n$ is typically 2 or 3, but we will see and solve problems where $n$ is in the hundreds or even thousands!

A system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables, say $x_1,\dots,x_n$ . An example is

\begin{align*} x_1+2x_2+x_3 & = 2,\\ 2x_1+6x_2+x_3 & =7,\\ x_1+x_2+4x_3 & =3, \end{align*}

(2)

which is a system of three equations in three unknowns.

A solution of the system is a list $(s_1,s_2,\dots,s_n)$ of numbers that makes each equation a true statement when the values $s_1,\dots,s_n$ are substituted for $x_1,\dots,x_n$ , respectively. For instance, $(-3,2,1)$ is a solution of system (2) because, when these values are substituted in (2) for $x_1,x_2,x_3$ , respectively, the equations simplify to $2=2$ , $7=7$ , and $3=3$ . The set of all possible solutions is called the solution set of the linear system. We state an important fact regarding the solution set of linear systems that we will understand very deeply by the end of this chapter:

4Solving Linear Systems¶

We start with a simple observation: we know how to solve equations that look like

\frac{5}{2}x_1 = 6, \ 5-x_3 = 12, \ 1 + 3x_2 = -4.

(3)

These equations are ``easy’’ to solve because they only involved one unknown, that we can solve for using simple algebra. Our strategy will be to develop a systematic way of reducing linear systems, like the example (2) above, into an equivalent system of equations that are easy to solve.

To illustrate, let’s start with the system of three linear equations (2) we introduced above:

\begin{align*} x_1+2x_2+x_3 & = 2,\\ 2x_1+6x_2+x_3 & =7,\\ x_1+x_2+4x_3 & =3, \end{align*}

(4)

Our strategy will be to systematically employ the following very useful observation:

Before continuing, you might try to convince yourself that this observation is true. Our goal is to apply Observation 1 judiciously to transform the system of linear equations (4) into a much simpler one that is easy to solve but still has the same solutions as the original. Any linear system that is derived from the original system by successive application of such operations will be called an equivalent system. An important property is that equivalent systems have the same solutions.

Our strategy will be to successively eliminate variables in our equations in order of appearance. So, here, our first step is to eliminate the first variable, $x_1$ , from the second equation. We’ll do that by subtracting twice the first equation from the second:

\begin{array}{lrl} \text{[second equation]} & 2x_1+6x_2+x_3 & =7 \\ \text{-2[first equation]} & -2\left[x_1+2x_2+x_3 \right. & \left. = 2\right]\\ \hline \\ \text{[updated equation]} & 0x_1 + 2x_2 - x_3 & = 3, \end{array}

(5)

so that now, our equivalent system of linear equations is given by

\begin{align*} x_1+2x_2+x_3 & = 2,\\ 2x_2-x_3 & =3,\\ x_1+x_2+4x_3 & =3. \end{align*}

(6)

This system of equations is simpler than (4) because $x_1$ no longer appears in the second equation. We can eliminate $x_1$ from the third equation by subtracting the first equation from it, giving

\begin{align*} x_1+2x_2+x_3 & = 2,\\ 2x_2-x_3 & =3,\\ -x_2+3x_3 & =1. \end{align*}

(7)

The equivalent system (7) is even simpler than the original (4): notice that the second and third equations do not involve $x_1$ (by design), and so constitute a system of two linear equations in two unknowns. Moreover, once we have solved this subsystem for $x_2$ and $x_3$ , we can substitute the answer into the first equation, and we need only solve a single linear equation for $x_1$ .

We continue on, with our goal in this next phase to eliminate the second variable, $x_2$ , from the third equation by adding $1/2$ the second equation to it. The result is

\begin{align*} x_1+2x_2+x_3 & = 2,\\ 2x_2-x_3 & =3,\\ \frac{5}{2}x_3 & =\frac{5}{2}, \end{align*}

(8)

which is the simple system we have been working towards. It is in what is called triangular form: the first equation depends on all three variables, the second only depends on the second and third variables, and the last equation involves only the last variable. The process we went through of transforming the original system (4) to the triangular system (8) is an example of Forward Elimination: we work our way down the equations, eliminating variables as we go. Once a system is in triangular form, it can be straightforwardly solved by the method of Back Substitution. As the name suggests, we work backwards, solving the last equation first, which requires that $x_3=1$ . We substitute the result back into the middle equation, which becomes $2x_2-1=3$ , with solution $x_2=2$ . We finally substitute the two values $x_2=2$ and $x_3=1$ into the first equation, which becomes $x_1+5=2$ , and so the solution to the triangular system (8) is

x_1=-3, \quad x_2=2, \quad x_3=1.

(9)

Even more exciting is that recalling Observation 1, we know that the triangular system (8) is equivalent to our original system (4), which means that this is also the solution to our original system of equations (you can check). We note that in this case, system (4) has a unique, meaning one and only one, solution. We’ll understand why this is the case later in the semester.

This process was incredibly simple and intuitive: add equations together to eliminate ``downstairs’’ variables until you have found an equivalent triangular system, which can then be readily solved via back substitution. Amazingly, barring a few minor complications that can come up from time to time, this is essentially all there is to Gaussian Elimination. This incredibly simple algorithm is also unbelievably important and powerful. After a brief detour to remind ourselves about matrix and vector notation, we’ll revisit Gaussian Elimination through the lens of matrix factorization, which will allow us to easily automate and scale out these ideas to systems with hundreds or even thousands of variables.

5Worked Examples¶

Exercise 2 (Finding coefficients)

Find the coefficients $(a, b, c)$ for the set of equations

\begin{align*} ax + by + cz & = 3,\\ ax + y + cz & =2,\\ x - by - cz & =1, \end{align*}

(10)

so that a solution is $x = -1, y = 1, z = 2$ .

Solution to Exercise 2

Substituting $x = -1, y = 1, z = 2$ in (10), we get the set of equations

\begin{align*} -a + b + 2c &= 3,\\ -a + 1 + 2c &=2 \Rightarrow -a + 2c &= 1,\\ -1 - b - 2c &=1 \Rightarrow -b - 2c &= 0, \end{align*}

(11)

The unknowns are $(a, b, c)$ in (11). We use the forward elimination method to first eliminate $a$ by subtracting the first equation from the second equation to get

\begin{align*} -a + b + 2c &= 3, \\ -b &= -2,\\ - b - 2c &= 0, \end{align*}

(12)

From (12), we already have a triangular system which is clear after rearranging as given below

\begin{align*} -a + 2c + b &= 3, \\ - 2c - b &= 0,\\ -b &= -2, \end{align*}

(13)

Now, using back substitution, we get $b=2$ , $- 2c - b = 0 \Rightarrow c = -1$ and $-a + 2c + b = 3 \Rightarrow a = -3$ . Hence, the solution is ( $a = -3, b = 2, c = -1$ )

Exercise 3 (Finding solution(s))

Find the solution for the below set of equations using forward elimination and back substitution

\begin{align*} x + 2y + 3z &= 1, \\ 3x + 2y + z &= 1, \\ 7x + 2y − 3z &= 1 \end{align*}

(14)

Solution to Exercise 3

We first eliminate $x$ from the second and third equations by doing [second eqn] $\gets$ [second eqn] - 3[first eqn] and [third eqn] $\gets$ [third eqn] - 7[first eqn] to get

\begin{align*} x + 2y + 3z &= 1, \\ -4y - 8z &= -2, \\ -12y − 24z &= -6 \end{align*}

(15)

Next, we eliminate $y$ from the third equation by doing [third eqn] $\gets$ [third eqn] - 3[second eqn] and get

\begin{align*} x + 2y + 3z &= 1, \\ -4y - 8z &= -2, \\ 0 &= 0 \end{align*}

(16)

In (16), the third equation is just a universal fact ( $0=0$ !). The second equation $-4y - 8z = -2$ has infinitely many solutions. For example, if $y=0$ , then $z = \frac{1}{4}$ . Given some value for $y$ , we can always find a value for $z$ as $z = \frac{1 - 2y}{4}$ . Substituting the corresponding value of $(y, z)$ in the first equation, we can always find a value for $x$ as $x = 1 - 2y - 3z$ .

Footnotes¶

We’ll see later exactly why we call these equations linear, and the deep implications that linearity has on science and engineering. For now, it’s enough to think of an equation as being linear if the unknowns only appear to the first power, and there are no product terms like $x_1x_2$ or $x_1x_2x_3$ , in it.
↩
Almost all equations that we will encounter in this class will be defined in terms of real numbers. In certain settings, we will need to use complex numbers, but don’t worry, we’ll go over how to work with complex numbers carefully then.
↩

Ch 1 Linear Algebraic Systems

1.1 Why Linear Systems?

Ch 1 Linear Algebraic Systems

1.3 Matrices and Vectors