32.1 Linear Equations

Suppose we have a set of linear equations, for example

and we wish to find a solution, by which we mean to find the explicit values of x, y and z which make these equations all true.

The fundamental facts that allows us to find solutions are these:

1. Given any equation, you can multiply it (that is, multiply every term in it, both on the right and on the left) by any non-zero number without changing its implications.

2. Given any two equations we define their sum to be the equation whose left hand side is the sum of the two left hand sides, and whose right hand side is the sum of the two right hand sides.

Then you can replace either of the two equations by its sum with any multiple of the other without changing their implications.

Example: you can replace the top equation above by 3x + 4y = 6 by subtracting the third equation from it; (subtracting the equation is the same as adding -1 multiplied by it)

Exercise 32.1 Prove claim 2 here. Solution

You can solve the equations by using a sequence of manipulations of the kind just mentioned that put the equations into the form x = a, y = b, z = c, which is the solution to them.

What sequence of manipulations should you use to solve equations?

Notice that the subtraction made in the example above was chosen so that z does not appear in the subtracted equation, which was 3x + 4y = 6.

If we make an addition of an appropriate multiple of the third equation to the second one, again the z term in the resulting sum equation can be eliminated similarly; with result x - 3y = 6.

We started with three equations in three variables.

After these operations we have eliminated z from two of them and have two equations in two variables.

By a similar manipulation we can eliminate x, for example, by subtracting three times the second one from the first. The resulting equation is then 13y = -12.

Dividing this equation by 13 then gives us an expression for y.

We can substitute it for y into either of the previous two equations and solve the resulting equation for x.

We get Substituting both for x and y in any of the original equations then gives and we have a complete solution to our equations.

In general you can systematically eliminate one variable at a time from all equations, reducing n equations in n unknowns to (n - 1) equations in (n-1) unknowns, and repeat the process until you can solve one equation for one unknown, and then substitute back to find the others, one at a time.

This procedure is called "Gaussian elimination".

Exercise 32.2 Perform Gaussian elimination on the following set of equations to find a solution

Solution

Please notice that in doing these operations it is very easy to make a mistake, and it is wise to check your answer, once you have it, in all the original equations to see if they are satisfied.

Can this procedure fail?

If the equations that you start with are consistent, they will produce a unique solution unless when you try to eliminate one variable by subtracting a multiple of an equation from another, you eliminate the entire equation.

That is, at some stage one of your equations is a multiple of another and subtracting that multiple from it eliminates the entire equation.

This will happen if in the beginning one of your equations can be expressed as a sum of multiples of one or more of the others. (The simplest way this happens is when two of the equations are identical)

In this case the left hand sides of your equations are said to be linearly dependent.

Otherwise, when the equations have a unique solution, the left hand sides are said to be linearly independent.

When your equations are linearly dependent, (and you started with the same number of equations as you had unknowns,) you will find that you do not have enough equations to determine a unique solution.

This is not a disaster, but it means that there are lots of solutions, at least a whole line of them.

You can continue the Gaussian elimination process until you are down to one non-vanishing equation in now two or more variables. Then any solution to that equation is a solution to the original set of equations, which is said to be an underdetermined set of equations.

Suppose for example, your last equation with all other unknowns eliminated is x = 2y + 3.

Then you can choose any value you please for y, compute x and then go on to use your other equations to compute your other unknowns, and that will be a solution, though of course not the only possible one. Solutions to an equation like this one form a line in the xy plane.