Dantzig G., Thapa M. Linear programming. Vol.1. Introduction

Подождите немного. Документ загружается.

342 LINEAR EQUATIONS

Deﬁnition (Solution of a System of Equations): In general, suppose we have

a system of m equations in n variables,

Ax = b, (B.3)

where A is an m ×n matrix. A solution of the ith equation is a vector x



( x



,... ,x



)

such that



+ a



+ ···+ a



= b

The vector x



is said to be a solution of a system of equations provided x



a solution of each equation of the system.

Example B.2 (Solution Set) As we noted earlier, forming the product of a matrix and

a vector amounts to taking a linear combination of the columns of the matrix. Since the

ﬁrst two columns of the coeﬃcient matrix in (B.1) are linearly independent, they span the

entire space 

. Hence, every right-hand side b can be represented as a linear combination

of the columns of A and hence a solution to (B.1) exists whatever the right-hand side

might be. In other words, every right-hand side belongs to the range space (or column

space) of A. However, note that there are fewer equations than unknowns, and thus there

will be inﬁnitely many solutions, as can be seen by writing x

and x

in terms of x

and

as follows:

=11− 2x

− 3x

=14− 4x

− 6x

The aggregate of solutions of a system is called its solution set. The full solution set

for (B.1) can be represented by































−2

−4















−3

−6









by choosing various values for the parameters x



and x



. The vectors







−2

−4







and z







−3

−6







are linearly independent and are orthogonal to the rows of A, as can be easily veriﬁed.

That is, in other words, Az

= 0 and Az

= 0, and the vectors z

and z

are said to lie in

the null space of the rows of A (or simply the null space of A). Note that the row space

of A belongs to 

. Recalling the deﬁnition of vector spaces given in Section A.6, the

dimension of the row space of A in our example is 2 and, as expected, the dimension of

the null space of A in this example is (4 − 2), which is also 2.

B.2 SYSTEMS OF EQUATIONS WITH THE SAME SOLUTION SETS 343

Example B.3 (Incompatible, or Inconsistent, Systems) If the coeﬃcient matrix

A in the example above is changed so that we have



1023

2046



















the number of independent columns is reduced to 1. Thus, there will no longer be a

solution for every right-hand side. For example, the right-hand side b

=(1, 0)

cannot

be represented as a linear combination of the columns of A and thus there is no solution

x that satisﬁes Ax = b. In this example, the row space of A has rank or row dimension 1,

and thus the dimension of its null space will be (4 − 1)=3.

Deﬁnition (Inconsistent, Unsolvable, or Incompatible): If the right-hand side

of a system of equations Ax = b cannot be represented as a linear combination

of the columns of A, the system of equations is said to be inconsistent,or

unsolvable,orincompatible. A system of equations is said to be consistent,or

solvable,orcompatible, if the right-hand side b lies in the column space of the

matrix A.

Deﬁnition (Empty Solution Set): If the system is inconsistent, the solution

set is said to be empty.

B.2 SYSTEMS OF EQUATIONS WITH THE

SAME SOLUTION SETS

We start by illustrating how to generate an equation with the same solution set as

the original system of equations.

Example B.4 (Same Solution Set) Given a system of equations such as (B.1) it is

easy to construct a new equation from it that has the property that every solution of (B.1)

is also a solution of the new equation. The new equation shown in (B.4) below was formed

by multiplying Equation B.1(a) by 2 and Equation B.1(b) by 3 and summing.

+3x

+16x

+24x

=64. (B.4)

Thus the solution (11, 14, 0, 0) of the system of equations (B.1) is also a solution of the

new equation.

A scheme for generating a new equation whose solution set includes (among

others) all the solutions of a general linear system Ax = b, is shown in (B.5).

For each equation i an arbitrary number k

is chosen; the new equation is formed

by multiplying the ith equation by k

and summing. In matrix notation, with

=(k

,... ,k

), this is

Ax = k

b, or (B.5)

x = α, (B.6)

344 LINEAR EQUATIONS

where

= k

+ k

+ ···+ k

for j =1,...,n,

α = k

+ k

+ ···+ k

(B.7)

Deﬁnition (Linear Combination): An equation such as d

x = α that is

formed in the above manner is called a linear combination of the original

equations; and the numbers k

are called multipliers,orweights, of the linear

combination.

 Exercise B.1 Suppose a linear combination of the columns of A equals some other

column. Show that the same linear combination applied to





results in





, where

and α are deﬁned by (B.7).

Whenever a vector x =(x

,... ,x

)

constitutes a solution of (B.3), equa-

tion (B.6) becomes, upon substitution, a weighted sum of identities and hence an

identity itself. Therefore, every solution of a linear system is also a solution of any

linear combination of the equations of the system. Such an equation may therefore

be inserted into (or adjoined to) a system of equations without aﬀecting the solution

set. This fact is used in devising algorithms to solve systems of equations.

Deﬁnition (Dependent System, Redundancy, Vacuous Equation): Ifina

system of equations, an equation is a linear combination of the others, it is

said to be dependent upon them; the dependent equation is called redundant.

A vacuous equation is an equation of the form

+0x

+ ···+0x

=0. (B.8)

A system of equations consisting only of vacuous equations is also called re-

dundant.

Deﬁnition (Independent System): A system containing no redundancy is

called independent. In the theorems that follow about a system of equations

we assume that the system does not consist of only a single vacuous equation.

A linear system is clearly unsolvable,orinconsistent, if it is possible to exhibit

a linear combination of the equations of the system of the form

+0x

+ ···+0x

= d with d = 0 (B.9)

because any solution of the system would have to satisfy (B.9); but this is impossible

no matter what values are assigned to the variables. We shall refer to (B.9) as an

inconsistent equation.

B.3 HOW SYSTEMS ARE SOLVED 345

Example B.5 (Unsolvable System of Equations) The system

+ x

(B.10)

is unsolvable because the ﬁrst equation states that a sum of three numbers is 3, while the

second states that this same sum is 8. If we apply multipliers k

=1,k

= −1 to eliminate,

say, x

, we would obtain 0x = −5, which is clearly a contradiction.

In general, the process of elimination applied to an inconsistent system will always

lead in due course to an inconsistent equation, as we shall show in the next section.

 Exercise B.2 Show that the only single-equation inconsistent linear system is of the

form (B.9).

 Exercise B.3 Show that if a system of 2 or more equations contains a vacuous equation,

it is dependent.

B.3 HOW SYSTEMS ARE SOLVED

The usual “elimination” procedure for ﬁnding a solution of a system of equations is

to augment the system by generating new equations by taking linear combinations

in such a way that certain coeﬃcients are zero. This is usually followed by the

deletion of certain redundant equations.

Example B.6 (Augmentation of a System of Equations) For example, consider,

+ x

− x

− 2x

=2.

(B.11)

Multiplying the ﬁrst equation in (B.11) by k

= +1 and the second equation by k

= −1

and summing, the coeﬃcient of x

vanishes and we obtain

+3x

=2.

The system of equations (B.11) augmented by the above equation clearly has the same

solution set as the original system of equations (B.11).

It is interesting to note that the technique of taking linear combinations and

augmenting the original system can be used to easily detect whether any equation

of the original system is linearly dependent on the others. A second advantage is

that it is easy to state the set of all possible solutions, as we have already seen. It

turns out that these same basic ideas are used for solving systems of equations on

a computer through the use of LU factorizations.

In general, the method of solving a system of equations is one of augmentation

by linear combinations until in the enlarged system there is a subsystem whose

solution set is readily seen. Moreover, all other equations of the system are linearly

dependent on the subsystem. An example of a system whose solution set is readily

seen is (B.1) on page 341; it belongs to a class called canonical.

346 LINEAR EQUATIONS

Deﬁnition (Canonical Form): A system of m equations in n variables x

is said to be in canonical form with respect to an ordered set of variables

,...,x

) if and only if x

has a unit coeﬃcient in equation i and a

zero coeﬃcient in all other equations.

System (B.12) below, with x

=(x

,... ,x

)

and x

=(x

m+1

,... ,x

)

canonical because for each i, the variable x

has a unit coeﬃcient in the ith equation

and zero elsewhere:

= b. (B.12)

 Exercise B.4 Show how by arbitrarily choosing values for x

m+1

,...,x

, the class of

all solutions for (B.12) can be generated. How can (B.12) be used to check easily whether

or not another equation α

+ α

+ ···+ α

= α

is dependent upon it?

If by augmentation we can construct a subsystem that is in canonical form, then

it is easy to generate all possible solutions to the original system. When the original

system is unsolvable the canonical subsystem does not exist; but in this case the

process of generating the canonical form results in an infeasible equation, which

tells us that the original system is unsolvable.

Deletion of an equation that is a linear combination of the others is another

operation that does not aﬀect the solution set. If after an augmentation, one of the

original equations in the system is found to be a linear combination of the others,

it may be deleted. In eﬀect the new equation becomes a “substitute” for one of the

original equations. Although the limited capacity of electronic computers to store

information keeps growing year by year still there is likely always to be a practical

limit, and so this ability to throw away equations will remain important in the

future.

Deﬁnition (Equivalent Systems): Two systems are called equivalent if one

system may be derived from the other by inserting and deleting a redundant

equation or if one system may be derived from the other through a chain of

systems each linked to its predecessor by such insertions and deletions.

THEOREM B.1 (Same Solution Sets) Equivalent systems have the same

solution set.

 Exercise B.5 Prove Theorem B.1.

B.4 ELEMENTARY OPERATIONS

There are two simple but important types of linear combinations, called elementary

operations, that may be used to obtain equivalent systems.

B.4 ELEMENTARY OPERATIONS 347

Type I. Replacing any equation E

by the equation kE

with k = 0, and leaving

all remaining equations unchanged.

Type II. Replacing any equation E

by the equation E

+ kE

, where E

is any

other equation of the system, and leaving all remaining equations un-

changed.

To prove that an elementary operation of Type I results in an equivalent system,

insert kE

as a new equation after E

, then delete E

. Note that E

is a redundant

equation, for it can be formed from kE

by (1/k)kE

if k = 0. Similarly, to prove

that an elementary operation of Type II results in an equivalent system, insert

+ kE

after E

and then delete E

. Note that E

is a redundant equation, for it

is given by (E

+ kE

) − kE

Therefore one way to transform a system of equations into an equivalent system

is by a sequence of elementary operations. For example, system (B.14) is equiva-

lent to system (B.13) because it can be obtained from (B.13) by replacing (B.13b)

by subtracting from it 2 times (B.14a). Furthermore, system (B.15) is equivalent

to (B.14) because (B.15b



) can be obtained from (B.14b



) by dividing it by 3.

− x

+2x

= 4 (a)

+ x

− 2x

= 2 (b)

(B.13)

− x

+2x

=4 (a



) = (a)

− 6x

= −6(b



) = (b) − 2(a)

(B.14)

− x

+2x

=4 (a



)=(a



)

− 2x

= −2(b



)=(b



)/3

(B.15)

THEOREM B.2 (Inverse of a Sequence of Elementary Operations) Cor-

responding to a sequence of elementary operations is an inverse sequence of elemen-

tary operations of the same type by which a given system can be obtained from the

derived system.

 Exercise B.6 Prove Theorem B.2 by proving the following:

1. Show that the inverse operation of Type I is itself of Type I and is formed by

replacing equation E

by (1/k)E

with k =0.

2. Show that the inverse operation of Type II is itself of Type II and is formed by

replacing equation E

by E

− kE

 Exercise B.7 Perform the inverse operations on (B.15) and show that the result is the

original system (B.13).

348 LINEAR EQUATIONS

We can also see that if a system can be derived from a given system by a sequence

of elementary operations, this implies that it is possible to obtain each row of the

derived system in detached coeﬃcient form directly by a linear combination of the

rows of the given system. Conversely, each row of the given system is some linear

combination of the rows of the derived system.

THEOREM B.3 (Obtaining Rows of an Equivalent System) The rows

of two equivalent systems in detached coeﬃcient form can be obtained one from the

other by linear combinations.

THEOREM B.4 (Obtaining Equivalent Systems) If the rth equation of a

given system is replaced by a linear combination of the equations i with multipliers

where k

=0, an equivalent system is obtained.

 Exercise B.8 Prove Theorems B.3 and B.4. What is the inverse operation of a linear

combination performed in Theorem B.4.

 Exercise B.9 Show that if a second system of equations can be obtained from the

original system of equations by rearranging the order of equations, the two systems are

equivalent, i.e., one can be obtained from the other by elementary operations.

The most important property of a system derived by elementary operations is

that it has the same solution set as the system it was derived from.

An interesting converse question now arises. Are all systems of linear equations

with the same solution set obtained by a sequence of inserting and deleting of

redundant equations? As we will show in Section B.5, the answer is yes if the

solution set is nonempty but may be no if the solution set is empty, as can be easily

seen by comparing the two systems

{0x =1} and



0x =1

1x =1



;

both have empty, hence identical, solution sets. It is obvious that if these two

systems were equivalent, some multiple (linear combination) of the equation 0x =1

of the ﬁrst system would yield the equation 1x = 1 of the second system, but this

is clearly impossible.

THEOREM B.5 (Reversal of a Sequence of Elementary Operations) Let

S be a system of equations E

,... ,E

and let E

be formed from S by a linear

combination:

+ λ

+ ···+ λ

= E

where λ

are not all zero. Let S be a system of equations

,... ,

obtained

from S by a sequence of elementary operations. Then there exists

such that

+ ···+

= E

where

are not all zero.

B.5 CANONICAL FORMS, PIVOTING, AND SOLUTIONS 349

Proof. If we can show that the theorem is true for a single elementary operation

of Type I and a single elementary operation of Type II, then by induction, it will

be true for a sequence of such operations.

Suppose that E

is replaced by E



= kE

where k

= 0 (an elementary operation

of Type I). Then it is easy to verify that



+ λ

+ ···+ λ

= E

where λ

/k, λ

,...,λ

are not all zero.

Next suppose that E

is replaced by E



= E

+ kE

(an elementary operation

of Type II), then E

= E



− kE

and it is easy to verify that



+(λ

− λ

k)E

+ ···+ λ

= E

By induction the theorem holds for any number of elementary operations.

B.5 CANONICAL FORMS, PIVOTING, AND

SOLUTIONS

Suppose that we have a system of m equations in n variables with m ≤ n,

Ax = b, (B.16)

where A is an m × n matrix. We are interested in ways of replacing this system,

if possible, by an equivalent canonical system (see Section B.3 for a deﬁnition of

canonical):

b, (B.17)

where

A is m × (n − m). For square systems, it is clear that the canonical system

is simply of the form Ix =

b. In this form the solution set is evident and it is easy

to check whether or not any other system is equivalent to it.

REDUCTION TO A CANONICAL FORM

The standard procedure for reducing (if possible) a general system (B.16) to an

equivalent canonical form (B.17) will now be discussed. The principles are best

illustrated with an example and then generalized.

Example B.7 (Reduction to Canonical Form) Consider the 2 × 4 system

+ 2x

+2x

=10

− 2x

− x

+ x

=2.

(B.18)

Choose as “pivot element” any term with nonzero coeﬃcient such as the boldfaced term

in the ﬁrst equation. Next perform a Type I elementary operation by dividing its equation

350 LINEAR EQUATIONS

(the ﬁrst one) by the coeﬃcient of the boldfaced term, and then eliminating its corre-

sponding variable (x

) from the other equation(s) by means of elementary operation(s) of

Type II:

+ x

+ 1x

+ x

+3x

=12.

(B.19)

Next choose as pivot any term in the remaining equations (such as the boldfaced term in

the second equation above). Eliminate the corresponding variable (in this case x

) from all

the other equations. (Because x

happens to have a zero coeﬃcient in the ﬁrst equation,

no further work is required to perform the eliminations.) From this canonical system with

the ordered set of basic variables x

, x

, it is evident, by setting x

= x

= 0, that one

solution is x

= 12, x

=5,x

= x

=0.

 Exercise B.10 Show that system (B.19) is in canonical form with respect to basic

variables (x

). Show that it is not possible to get system (B.18) into canonical form

with respect to variables (x

) by ﬁrst choosing a pivot element in the ﬁrst equation

and then the second, etc., but that it is clearly possible by rearrangement of the order of

the equations. What are the elementary operations that would rearrange the order of the

equations?

PIVOTING

Pivoting forms the basis for the operations to reduce a system of equations to

canonical form and to maintain it in such form.

Deﬁnition (Pivot Operation):Apivot operation consists of m elementary

operations that replace a system by an equivalent system in which a speciﬁed

variable has a coeﬃcient of unity in one equation and zero elsewhere.

The detailed steps for pivoting on a term a

, called the pivot term, where a

=0

are as follows:

1. Perform a Type I elementary operation by replacing the rth equation by the

rth equation multiplied by (1/a

2. For each i =1,...,m except i = r, perform a Type II elementary operation

by replacing the ith equation by the sum of the ith equation and the replaced

rth equation multiplied by (−a

Pivoting can be easily explained in matrix notation as follows. Let (B.20a) and

(B.20b) denote the systems before and after pivoting.

(a) Ax = b

(b)

Ax =

(B.20)

The pivoting operations described above are the same as multiplying (B.20a) by

the elementary matrix M:

(a) M = I +

− A

•s

(b) M

−1

= I +(A

•s

− e

(B.21)

B.5 CANONICAL FORMS, PIVOTING, AND SOLUTIONS 351

where e

is the unit vector with 1 in row r and zero elsewhere.

 Exercise B.11 Show that (B.21b) is the inverse of M. Prove that multiplying (B.20b)

by (B.21b) restores the original problem (B.20a). Show by way of an example that multi-

plying (B.20b) by (B.21b) is not necessarily the same as performing a pivot on (B.20b).

 Exercise B.12 Show that

•s

is the same as e

. How may this be applied to show the

second part of Exercise B.11.

In general the reduction to a canonical form can be accomplished by a sequence

of pivot operations. For the ﬁrst pivot term select any term a

such that a

=0.

After the ﬁrst pivoting, the second pivot term is selected using a nonzero term from

any equation r



of the modiﬁed system except r. After pivoting, the third pivot term

is selected in the resulting modiﬁed m-equation system from any equation r



except

r and r



. In general, repeat the pivoting operation, always choosing the pivot term

from modiﬁed equations other than one corresponding to those previously selected.

Continue in this manner, terminating either when m pivots have been performed or

when, after selecting k<mpivot terms, it is not possible to ﬁnd a nonzero pivot

term in any equation except those corresponding to equations previously selected

because all coeﬃcients in the remaining equations are zero.

Let the successive pivoting be, for example, on variables x

,... ,x

in the

corresponding equations i =1,...,r, where r ≤ m; then the original system (B.16)

has been reduced to an equivalent system of form (B.22) below, which we will refer

to as the reduced system with respect to the basic variables x

,... ,x

. We shall

also refer to a system as reduced with respect to r basic variables if by changing

the order of the variables and equations, it can be put into form (B.22), where

=(x

,... ,x

)

and x

=(x

r+1

,... ,x

)

+0x

(B.22)

where

A is r × (n − r),

is of length r, and

is of length m − r.

Since (B.22) was obtained from (B.16) by a sequence of pivoting operations each

of which consists of m elementary operations, it follows that the reduced system is

(a) formed from linear combinations of the original system, and (b) equivalent to

the original system.

The original system (B.16) is solvable if and only if its reduced system (B.22) is

solvable, and (B.22) is solvable if and only if

= 0, i.e.,

r+1

r+2

= ···=

=0. (B.23)

If (B.23) holds, the solution set is immediately evident because any values of the

(independent) variables x

r+1

,...,x

determine corresponding values for the (depen-

dent) variables x

,...,x

. On the other hand, if

r+i

= 0 for some i, the solution

set is empty because the (r + i)th equation is clearly inconsistent; it states that

r+i

. In this case, the original system (B.16) and the reduced system (B.23)

are both inconsistent (unsolvable).