ñòð. 29 |

00010w01w

00001w0Iw

i 0 0 0 0 0 0 I I w1

The final solution will have the form

x, = a , ˜ 02x2 - a+, a&j,

x4 = b, - kc,>

- C&,

x5 = c,

x, = d,.

Here x7 is the only variable which is unambiguously determined. The variables

x2, x3, and x6 are free to take on any values; once v&˜es have been selcctcd for

these three variables; then values for +, , x4; and x5 are automatically determined.

Some more vocabulary is helpful here. If the jth column of the row echelon

matrix Ij contains a pivot. we call xj a basic variable. If the jth column of B does

not contain a pivot. we call xi a free or nonbasic variable. In this terminology,

Gauss-Jordan elimination determines a solution of the system in which each basic

variable is either unambiguously determined or a lincar expression of the fret

variables. The free variables are free to take on any value. Once one chooses

values for the free variahlcs, values for the basic variables are determined.

As in the example above, the free variables arc often placed on the right-

hand side of the equations to emphasirc that their values are not determined by the

system; rather, they act as parameters in determining values for the basic variables.

In a given problem which variables are free and which are basic may depend

on the order of the operations used in the Gaussian elimination process and on the

order in which the variables are indexed.

EXERCISES

7.13 Reduce the following matrices to TOW cchclan and reduced TOW echelon fomms:

-4x+hy+4z=4

7.14 Solve the system of equations

{ zr- y+ z=l.

7.15 Use Gauss-Jordan elimination to determine for what values of the parameter k the

system

x,+ x*=1

x, -kx2 = 1

has no solutions, one solution, and more than one solution.

7.16 Use Gauss-Jordan elimination to solve the following four systems of linear equations.

Which variables are free and which are basic in each solution?

w- x+3ym z=o

&9+2x+ y - z=l

w+4xm y+ z=3

3w- x - y+22=3

a) b) 3w+7x+ y+ z=6

x+ y- r=l

2w + 3x + 3y 32 = 3; 3w+2*+5y- z= 3;

3

w+2x+3y- w+ x- y+22=

z=l

2w+2x-2y+42=

x+2y+3z=2 6

-w+

4 -3wm3x+3y-6z=

C) -9

3wm x+ y+22=2

-2wm 2x+ 2y - 4z = -6.

2w+3x- y+ z = I ;

7.17 a) Use the flexibility of the free variable to findpositive integers which satisfy the

system

z= 13

x+ y+

x + 5y + 1nz = 61

b) Suppose you hand a cashier a dollar bill for a ¢ piece of candy and receive

16 coins as your change-all pennies, nickels. and dimes. How many coins of

each type do you receive? [Hint: See part a.]

7.18 For what values of the parameter a does the following system of equations have a

solution?

6x +y= 7

3 x+ y=4

-61˜ 2y = a.

7.19 From Chapter 6, the stationary distribution in the Markov model of unemployment

satisfies the linear system

(y 1)x + /?y = 0

(l-q)x-/?y==o

x+ y=l.

7.4 RANK-THE FUNDAMENTAL CRITERION

WC now answer the five basic questions about existence and uniqueness of solu-

that were posed in Section 7.3. The main criterion involved in the answers

tions

to these questions is the rank of a matrix. First, note that we say a row of a matrix

is nonzero if and only if it contains at least one nonzcro entry.

Definition The rank of a matrix is the numhcr of nonze˜o rows in its row

echelon form.

Since can reduce any matrix to scvcral different row echelon matrices (if

WC

we interchange rows), we need to show that this definition of rank is indcpcndcnt

of which row echelon matrix we compute. We will save this for Chapter 27, where

we will also discuss the rank of a matrix from a diffcrcnt. more geometric point

of view.

A and/i be the coefficient matrix and augmented matrix respectively of a

Let

system of linear equations. Let R and B hc their corresponding row cchclon forms.

B as in reducing A to B no matter

One goes through the same steps in rcducingA to

what the last column ofi is. heceuse the choices of elementary row operations in

going from A to I? ncvcr involve the last column of the augmented matrix. In other

word\; B is itself an augmcntcd matrix for 13.

We first relate the rank of ii coefficient matrix A to the rank of a corresponding

augmented matrix end to the numhcr of rows and columns of.4. Note that the rank

of the sugmcntcd matrix must he at least as big as the rank of the coefticicnt matrix

hccause if a row in the augmented matrix contidns only zeros. then so does the

corresponding tow of the coefficient matrix. Furthermore. the dctinition of rank

requires that the rank is Icss than or equal to the number of rows of the cocfticicnt

matrix. Since each nonxr˜, row in the row echelon form contains exactly one

pivot; rhc rank is equal to the numhcr of pivots. Since each column of4 can have

at ˜IOSI one pivot. the rank is idso Icss than or equal to the numhcr of columns ot

the cocfficicnt matrix. Fact 7. I summxizcs the observations in this paragraph.

Fact 7.1. Let .4 he the coefticicnt matrix and let .i he the corrccponding aog-

mentcd matrix. Then.

( a ) rank/l 5 rank,%

<ICA. and

(/I) rank,< 5 numhcr of IOM˜S

(c) rank.4 5 number of columns of A.

The following fxr relates the ranks of.4 and of,,i to the cxistcnce otâ€™ a solution

of the system in question and gives us our tint answer to Oue?tion I ahovc.

Fact 7.2. A system of linear equations with coefficient matrix A and augmented

matrix/i has a solution if and only if

rankii = rankA

The proof of this statement follows easily from a careful consideration

Proof

1of the TOW echelon form b of A. If ranka > rankA, then there is a zero row

ñòð. 29 |