стр. 30 |

in the corresponding row echelon augmented matrix B. This translates into the

equation

Ox, + Ox2 + + Ox,, = bвЂ™ (21)

with bвЂ™ nonzero. Consequently, the row echelon system has no solution and

therefore the original system has no solution.

On the other hand, if the TOW echelon form of the augmented matrix contains

no row corresponding to equation (21), that is, if rankA = rank,& then there is

nothing to stop Gauss-Jordan elimination from finding a general solution to the

original system. As the discussion in the last section indicates, one can easily

read off the solution directly from the reduced row echelon form. Some basic

variables will be uniquely determined; others will be linear expressions of the

free variables. W

If a system with a solution has free variables, then these variables can take on

any value in the gcncral solution of the system. Consequently, the original system

has infinitely many solutions. If there are no free variables, then every variable is

a basic variable. In this case, Gaussian or Gauss-Jordan elimination determines a

unique value for every variable: that is; there is only one solution to the system.

We can summarize these observations.

Fact 7.3. A linear system of equations must have either no solution, one solution,

or infinitely many solutions. Thus. if a system has more than one solution, it has

infinitely many.

Let us look carefully at the case where there are no free variables in the system

under study. Since cvcry variable must be a basic variable, each column contains

exactly one pivot. Since tech nonzero row contains a pivot too, there must be at

least as many rows as columns. (Thcrc may be some all-zero rows at the bottom

of the row echelon matrix.) This proves:

Fact 7.4. If a system has exactly one solution, then the coefficient matrix A has

at least as many rows as columns. In other words. a system with a unique solution

must have at lcast as many equations as unknowns.

Fact 7.4 can be expressed another way.

Fact 7.5. If a system of linear equations has mwe unknowns than equations. it

must have either no solution or infinitely many solutions.

Consider a system in which all the bjвЂ™s on the right-hand side are 0:

O,pcl + вЂќ + Lzl,.r,, =0

UZIXj + вЂњвЂ™ + cbвЂќX,, = 0

: :

Such a system is called homogeneous. As we shall see later, homogeneous sys-

tems play an especially important role in the study of linear equations. Any

homogeneous system has at least one solution:

x, = x2 = = x,, = вЂќ

The following statement is an immediate consequence of Fact 7.5

Fact 7.6. A homogcncous system of linear equations which has mme unknowns

than equations must have infinitely many distinct solutions.

We now turn to the answers of Questions 3, 4, and 5 of the previous section.

In many economic models, the b;вЂ˜s on the right-hand side of a system of linear

equations can be considered as exogenous variables which vary from problem

to problem. For each choice of h,вЂ˜s on the right-hand side, one solves the linear

system to find the corresponding\,alucs of the cndog:cnousvariablcsn-,, , I,,. For

example, in the input-output example in Chapter 6. for each choice of consumption

amounts LвЂ™,, (;,, co. one wants to compute the required outputs x,, I,,. In

the linear IS-I.M model otвЂ™Chapter h. for each choice of policy variables G and M,

and parameters IвЂ™вЂќ and MвЂ˜, one wants to compute the corresponding equilibrium

GNP Y and interest mtc IвЂ™. Thus. it hccomcs cspccially important to understand

what properties of a system will guarantee that it has at least one solution or. better

yet. exactly one solution for or?\ right-hand side (RHS) h,. h:. h,,,. Again the

answers Row directly from ii careful look at reduced row echelon matrices. First

we answer Question 3.

Fact 7.7. A system of linear equations with coefficient matrix ,A will have a

solution for every choice of RIIS 11,. b,,, if and only if

rank/l = number of rows ofA

/вЂ˜roof (If): If rankA equals the number of rows ofA, then the row echelon matrix

B of .A has no all-zero rows. I.et h,. [I,,, he a choice of RIIS in system (2).

Lei b be the row echelon form of the corresponding augmented matrix. By

the remarks at the hcginning of this section. b is an augmented matrix for B,

L7.41 145

RA NK- TH E FUNDAMENTALCRITERION

and hence B will have no all-zero rows either. Thus,

rankA = #rows ofA = #rows ofA = rankA

By Fact 7.2, our system has a solution.

(Only If): If rankA is less than the number of rows ofA, then the last row,

A

row m, in the row echelon matrix B of will contain only LCIOS. Since B is in

row echelon form,

B

Augment by a column of 1s to make B:

The system corresponding to B can have MI solution because nothing satisfies

the equation described by the last row of !?: 0 = I. Starting now with L?, rcvcrsc

in turn each row operation that was applied in transforming A to R. The result

is an augmented matrix A whose coefficient matrix is our original matrix A.

The systems of equations A and b are equivalent since one was obtained from

the other by a scqucncc of row operations. Since the system corresponding to

!? has no solution. neither doss the system corresponding to A. Since A is an

forA.

augmented matrix we have found a right-hand side for which the system

matrix A

with cozfticient 1x1s no solution under the assumption that the rank of

n

A is less than the number of rows ofA. This finishes the proof of Fact 7.7.

If a system of equation\ has fewer unknowns than equations, then the correspond-

ing coctficicnt matrix has fcwcr columns than rows. Since the rank is less than or

equal to the number of columns, which i\ less than the number of rows, Fact 7.7

ensures that thcrc arc RIISs for which the corresponding system has no solutions.

We summarize this observation as Fact 7.8.

Fact 7.8. If a system of lincx equations has more equations than unknowns.

then there is a right-hand side such that the resulting system has no solutions.

Next we turn to Ouestion 1 and state B condition that guarantees that OUT system

will have at most one solution, that is; will never have infinitely many solutions.

for irr˜v choice of RHS II,, h ,,,.

146 OF EQUATDNS 171

SYSTEMS LINEAR

Fact 7.9. Any system of linear equations havingA as its coefficient matrix will

have at most one solution for every choice of RHS h,, , b,, if and only if

rankA = number of columns ofA.

Proof (If): If rankA equals the number of columns of A, then there are as many

стр. 30 |