Solving Systems of Linear Equations

Recall that we introduced the notion of matrices as a way of standardizing the expression of systems of
linear equations . In today’s lecture I shall show how this matrix machinery can also be used to solve such
systems. However, before we embark on solving systems of equations via matrices, let me remind you of
what such solutions should look like.

1. The Geometry of Linear Systems

Consider a linear system of m equations and n unknowns:

What does the solution set look like? Let’s examine this question case by case, in a setting where we can
easily visualize the solution sets.

• 0 equations in 3 unknowns. This would correspond to a situation where you have 3 variables x 1, x2, x3
with no relations between them. Being free to choose whatever value we want for each of the 3
variables, it’s clear that the solutions set is just R3, the 3-dimensional space of ordered sets of 3 real
numbers .

• 1 equation in 3 unknowns. In this case, use the equation to express one variable, say xn, in terms of
the other variables;

The remaining variables x1, and x2 are then unrestricted. Letting these variables range freely over
R will then fill out a 2-dimensional plane in R2. Thus, in the case of 1 equation in 3 unknowns we
have a two dimensional plane as a solution space.

• 2 equations in 2 unknowns. As in the preceding example , the solution set of each individual equation
will be a 2-dimensional plane. The solution set of the pair of equation will be the intersection of
these two planes. (For points common to both solution sets will be points corresponding to the
solutions of both equations.) Here there will be three possibilities:

1. The two planes do not intersect. In other words, the two planes are parallel but distinct.
Since they share no common point, there is no simultaneous solutoin of both equations.
2. The intersection of the two planes is a line. This is the generic case.
3. The two planes coincide. In this case, the two equations must be somehow redundant.

Thus we have either no solution, a 1-dimensional solution space (i.e. a line) or a 2-dimensional
solution space.

• 3 equations and 3 unknowns. In this case, the solution set will correspond to the intersection of the
three planes corresponding to the 3 equations. We will have four possiblities:
1. The three planes share no common point. In this case there will be no solution.
2. The three planes have one point in common. This will be the generic situation.
3. The three planes share a single line.
4. The three planes all coincide.

Thus, we either have no solution, a 0-dimensional solution (i.e., a point), a 1-dimensional solution
(i.e. a line) or a 2-dimensional solution.

We now summarize and generalize this discusion as follows.
Theorem 5.1. Consider a linear system of m equations and n unknowns:

The solution set of such a system is either:
1. The empty set {}; i.e., there is no solution.
2. A hyperplane of dimension greater than or equal to (n −m).

2. Elementary Row Operations

In the preceding lecture we remarked that our new-fangled matrix algebra allowed us to represent linear
systems such as (5.1) succintly as matrix equations:

For example the linear system

can be represented as

Now, when solving linear systems like (5.3) it is very common to create new, but equivalent, equations by,
for example, mulitplying by a constant, or adding one equation to another. In fact, we have

Theorem 5.2. Let S be a system of m linear equations in n unknowns and let S' be another system of m
equations in n unknowns obtained from S by applying some combination of the following operations:

• interchanging the order of two equations
multiplying one equation by a non-zero constant
• replacing a equation with the sum of itself and a multiple of another equation in the system.

Then the solution sets of S ane S' are identical.

In particular, the solution set of (5.3) is equivalent to solution set of

(where we have multiplied the second equation by -1), as well as the solution set of

(where we have replaced the second row in (5.5) by its sum with the first row), as well as the solution of

(where we have replaced the first row in (5.6) with its sum with −3 times the second row). We can thus
solve a linear system by means of the elementary operations described in the theorem above.

Now because there is a matrix equation corresponding to every system of linear equations, each of the
operations described in the theorem above corresponds to an matrix operation. To convert these operations
in our matrix language, we first associate with a linear system

an augmented matrix

The augmented matrices corresponding to equations (5.5), (5.6), and (5.7) are thus, respectively

From this example, we can see that the operations in Theorem translate to the following operations on the
corresponding augmented matrices:

• Row Interchange: the interchange of two row of the augmented matrix
• Row Scaling: multiplication of a row by a non-zero scalar
• Row Addition: replacing a row by its sum with s multiple of another row

Henceforth, we shall refer to these operations as Elementary Row Operations

3. Solving Linear Equations

Let’s now reverse directions and think about how to recognize when the system of equations corresponding
to a given matrix is easily solved. (To keep our discussion simple , in the examples given below we consider
systems of n equations in n unknowns.)

3.1. Diagonal Matrices. A matrix equation Ax = b is trivial to solve if the matrix A is purely
diagonal. For then the augmented matrix has the form

the corresponding system of equations reduces to

3.2. Lower Triangular Matrices. If the coefficient matrix A has the form

(with zeros everywhere above the diagonal from a11 to ann), then it is called lower triangular. A matrix
equation Ax = b in which A is lower triangular is also fairly easy to solve. For it is equivalent ot a system
of equations of the form

To find the solution of such a system one solves the first equation for x1 and then substitutes its solution
b1/a11 for the variable x1 in the second equation

One can now substitute the numerical expressions for x1, and x2 into the third equation and get a numerical
expression for x3. Continuing in this manner we can solve the system completely. We call this method
solution by forward substitution.

3.3. Upper Triangular Matrices. We can do a similar thing for systems of equations characterized
by an upper triangular matrices A

(that is to say, a matrix with zero’s everywhere below and to the left of the diagonal), then the corresponding
system of equations will be

which can be solved by substituting the solution of the last equation

into the preceding equation and solving for xn−1

and then substituting this result into the third from last equation, etc. This method is called solution
by back-substitution.

3.4. Solution via Row Reduction. In the general case a matrix will be neither be upper triangular or
lower triangular and so neither forward- or back-substituiton can be used to solve the corresponding system
of equations. However, using the elementary row operations discussed in the preceding section we can always
convert the augmented matrix of a (self-consistent) system of linear equations into an equivalent matrix
that is upper triangular; and having done that we can then use back-substitution to solve the corresponding
set of equations. We call this method Gaussian reduction. Let me demonstate the Gaussian method with
an example.

Example 5.3. Solve the following system of equations using Gaussian reduction.

First we write down the corresponding augmented matrix.

We now use elementary row operations to convert this matrix into one that is upper triangular.
Adding -1 times the first row to the second row produces

Adding -2 times the first row to the second row produces

Adding −3/2 times the second row to the third row produces

The augmented matrix is now in upper triangular form. It corresponds to the following system of equations

which can easily be solved via back-substitution:

In summary, solution by Gaussian reduction consists of the following steps

1. Write down the augmented matrix corresponding to the system of linear equations to be solved.
2. Use elementary row operations to convert the augmented matrix into one that is upper triangular.
This is acheived by systematically using the first row to eliminate the first entries in the rows below
it, the second row to eliminate the second entries in the row below it, etc.
3. Once the augmented matrix has been reduced to upper triangular form, write down the corresponding
set of linear equations and use back-substitution to complete the solution.

Prev Next