Vectors and Vector Operations



3.5 Uniqueness of Solutions to Linear Equations

Linear Independence and Linear Dependence

In Section 3.3 we saw that if a system of linear equations has more unknowns than equations then there is more than one solution, provided there is a solution. If there is only one solution to an equation or a system of equations then we say the solution is unique. If there is more than one solution we say the solution is not unique. In this section we want to look more closely at when the solution is unique and when it is not. When there is more than one solution we shall see that that the set of all solutions can be represented as the sum of a fixed vector and all linear combinations of one or more other vectors.

Even if there is the same number of unknowns as equations the solution might not be unique.

Example 1. Consider the following system of equations. We shall solve them both using the equations and using the augmented matrix so that we are more aware of what is happening when we just use the augmented matrix.

Equations Augmented matrix

(1) ) M =

We subtract 2 times equation 1 from equation 2 and 3 times equation 1 from equation 3. In terms of M we subtract 2 times row 1 from row 2 and 3 times row 1 from row 3. This gives

(2) ) M1 =

Normally at this point we would use equation 2 to eliminate y from equation 2. However, we don't have a y term in either equation 2 or equation 3. So we move on to the variable z and use equation 2 to eliminate z from equation 3. First we divide equation 2 by 2 to get the coefficient of z to be 1. In terms of the augmented matrix we divide row 2 by 2. This gives

) M2 =

Now we eliminate z from equations 1 and 3 by subtracting 3 times equation 2 from equations 1 and 3. In terms of the augmented matrix we subtract 3 times row 2 from rows 1 and 3. We get

(3) ) M3 =

We can solve the first equation for x in terms of y. We get

(4) x = 3 - 2y

z = 1

For any value of y we get a different solution to the original equations (1), so the solution is not unique. We can write the solutions in vector form as

(5) = = + y

or

(6) u = w + yv

where

(7) u = w = v =

So the set of solutions is a fixed vector w plus all multiples of another vector v.

We see that the non-uniqueness of the solution came from the fact that in the final set of equations we don't have an equation which specifies y as a number. So we can choose y to be any number. We say the variable y is free. Looking at the solution process, we see this came about at step (2) where y was missing from all the equations except equation 1. In terms of the augmented matrix all rows except the first have a 0 in column 2. This didn't stop the solution process. We just moved on to the variable z. In terms of the augmented matrix we moved on to the third column.

The final augmented matrix M3 = is an example of a matrix in what is called reduced row echelon form. A matrix in reduced row echelon form has the following four properties.

1. The first non-zero entry in each row is a 1, which is called a leading 1. A row can be all 0's.

2. The leading 1's move to the right as one moves down in the matrix.

3. All the row's that are all 0's are at the bottom of the matrix.

4. Above and below a leading 1 are 0's.

Here is another example of what the solutions to a system with a non-unique solution can look like.

Example 2. Solve the following system of equations.

- 2z + 8q = 12

2x + 4y - 10z + 6p + 12q = 28

2x + 4y - 5z + 6p - 8q = - 2

Here is the solution algorithm using the augmented matrix.

The final augmented matrix is in reduced row echelon form. We interpret back as equations.

x + 2y + 3p - 14q = - 16

z - 4q = - 6

0 = 0

y, p and q are the free variables. We solve for x and z in terms of them.

x = - 16 - 2y - 3p + 14q

z = - 6 + 4q

The solution written in vector form is

= = + y + p + q

or

(6) u = w + yv1 + pv2 + qv3

where

(7) u = w = v1 = v2 = v3 =

So the set of solutions is a fixed vector w plus all linear combinations of three other vectors v1, v2 and v3.

Using the elementary row operations any matrix can be transformed to reduced row echelon form. When we interpret an augmented matrix which is in reduced row echelon form as equations we can read off the solutions. This is done as follows.

Consider the jth variable. We look in the augmented matrix for a row with a leading 1 in column j. Suppose row i has a leading 1 in column j. Then we can use equation i to write the jth variable in terms of the constant on the left side minus the terms for the variables after the jth variable. If no row has a leading 1 in column j then variable j is free and the solution is non unique if there is a solution. To summarize

Theorem 1. Consider a system of equations Au = b and suppose we transform the original augmented matrix M to reduced row echelon form using elementary row operations. Call the reduced row echelon form matrix M'. If every column of M' has a row with a leading 1 in that column then the solution to the original system is unique provided there is a solution. Otherwise a solution to the original system is not unique and the solutions have the form u = w + uj1v1 + uj2v2 + ( + ujsvs where w, v1, v2, …, vs are fixed vectors and uj1, uj2, …, ujs are the free variables.

Example 3. Does the following system of equations have a solution?

Equations Augmented matrix

M =

Remark. These equations are equivalent to = or Au = b where A = , u = and b = . They are also equivalent to

x + y + z = or xv1 + yv2 + zv3 = b where v1 = , v2  =   and v3 = . To solve, we interchange the first and second equations.

Equations Augmented matrix

(9) M1 =

Subtract 3 times the first equation from the third giving

Equations Augmented matrix

) M2 =

Subtract 4 times the second equation from the third giving

Equations Augmented matrix

) M3 =

Add equation 2 to equation 1 giving

Equations Augmented matrix

) M6 =

The augmented matrix is now in reduced row echelon form. We can solve the first two equations for x and y in terms of z. One has

)

For every value of z we get a different solution. So the solution is not unique.

Homogeneous equations. There is another way to characterize when the solution to a system of linear equations is unique. It also leads to a general representation of the solution when it is not unique.

A system of linear equations is homogeneous if all the numbers to the right of the equal sign are zero. The system of equations (1) is not homogeneous, but the following system is.

x - y + 3z = 0

2x - y + 2z = 0

3x + y - 2z = 0

If we are given a system of equations that is not homogeneous, then the corresponding homogeneous system of equations is obtained by replacing all the numbers on the right of the equal signs by zero.

Example 4. For the system of equations (1), the corresponding homogeneous system is

(8) ) M =

In vector-matrix form, the system of equations (1) is Au = b where

A = b =

while the corresponding homogeneous system (8) is Au = 0.

One thing to note is that the zero vector u = 0 is always a solution to a homogeneous system Au = 0.

There is an interesting connection between the solutions of a system of equations and the solutions of the corresponding homogeneous system. This is mostly easily stated in vector-matrix form.

Theorem 2. Consider a system of equations

(9) Au = b

where A is a given matrix and b is a given vector and the problem is to find vectors u that satisfy the equation. Suppose w is a solution to (9), i.e. Aw = b. Then the set of all solutions to (9) consists of all vectors of the form u = w + q where Aq = 0.

Proof. Suppose Aq = 0 and u = w + q. Then Au = A(w + q) = Aw + Aq = b + 0 = b so u is a solution to (9). Conversely, suppose u is a solution to (9) and consider q = u – w. Then Aq = A(u - w) = Au - Aw = b - b = 0. So u = w + q where Aq = 0.

Example 2 (continued). Let's solve the homogeneous system (3). The steps are the same as in solving the inhomogeneous system (1) except we have 0's on the right side of the equation throughout. So instead of getting (3) – (5) as solutions we get

) M3 =

x = 2y

z = 0

q = = = y = yv

where

v =

So we see that the representation (5) for the solutions of (1) is in fact w + q where q is the set of solutions to the corresponding homogeneous equation.

In general, what do the set of solutions to a homogeneous system look like?

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download