1.4. SYSTEMATIC SOLUTION OF LINEAR SYSTEMS. 9

Back

The process is repeated and will eventually stop after r steps, either

because we run out of rows, or because we run out of non{zero columns. In

general, the ¯nal matrix will be in reduced row{echelon form and will have

r non{zero rows, with leading entries 1 in columns c1; : : : ; cr, respectively.

EXAMPLE 1.3.1

2

4

0 0 4 0

2 2 ¡2 5

5 5 ¡1 5

3

5 R1 $ R2

2

4

2 2 ¡2 5

0 0 4 0

5 5 ¡1 5

3

5

R1 ! 1

2R1

2

4

1 1 ¡1 5

2

0 0 4 0

5 5 ¡1 5

3

5 R3 ! R3 ¡ 5R1

2

4

1 1 ¡1 5

2

0 0 4 0

0 0 4 ¡15

2

3

5

R2 ! 1

4R2

2

4

1 1 ¡1 5

2

0 0 1 0

0 0 4 ¡15

2

3

5

½

R1 ! R1 + R2

R3 ! R3 ¡ 4R2

2

4

1 1 0 5

2

0 0 1 0

0 0 0 ¡15

2

3

5

R3 ! ¡2

15 R3

2

4

1 1 0 5

2

0 0 1 0

0 0 0 1

3

5 R1 ! R1 ¡ 5

2R3

2

4

1 1 0 0

0 0 1 0

0 0 0 1

3

5

The last matrix is in reduced row{echelon form.

REMARK 1.3.1 It is possible to show that a given matrix over an ar-

bitrary ¯eld is row{equivalent to precisely one matrix which is in reduced

row{echelon form.

A °ow{chart for the Gauss{Jordan algorithm, based on [1, page 83] is pre-

sented in ¯gure 1.1 below.

1.4 Systematic solution of linear systems.

Suppose a system of m linear equations in n unknowns x1; ¢ ¢ ¢ ; xn has aug-

mented matrix A and that A is row{equivalent to a matrix B which is in

reduced row{echelon form, via the Gauss{Jordan algorithm. Then A and B

are m £ (n + 1). Suppose that B has r non{zero rows and that the leading

entry 1 in row i occurs in column number ci, for 1 · i · r. Then

1 · c1 < c2 < ¢ ¢ ¢ ; < cr · n + 1:

10 CHAPTER 1. LINEAR EQUATIONS

START

?

Input A; m; n

?

i = 1; j = 1

- ? ¾

?

Are the elements in the

jth column on and below

the ith row all zero?

@ j = j + 1

@

@

@@

No R Yes

?

Is j = n?

Yes

No

-

6

Let apj be the ¯rst non{zero

element in column j on or

below the ith row

?

Is p = i?

Yes

?

PPPPP q No

Interchange the

pth and ith rows

©© ©© ©© ©

¼

Divide the ith row by aij

?

Subtract aqj times the ith

row from the qth row for

for q = 1; : : : ;m(q 6= i)

?

Set ci = j

?

Is i = m?

´

´

´+

¾ Is j = n?

i = i + 1

j = j + 1

6

No

No

Yes

Yes -

-

6

?

Print A,

c1; : : : ; ci

?

STOP

Figure 1.1: Gauss{Jordan algorithm.

1.4. SYSTEMATIC SOLUTION OF LINEAR SYSTEMS. 11

Also assume that the remaining column numbers are cr+1; ¢ ¢ ¢ ; cn+1, where

1 · cr+1 < cr+2 < ¢ ¢ ¢ < cn · n + 1:

Case 1: cr = n + 1. The system is inconsistent. For the last non{zero

row of B is [0; 0; ¢ ¢ ¢ ; 1] and the corresponding equation is

0x1 + 0x2 + ¢ ¢ ¢ + 0xn = 1;

which has no solutions. Consequently the original system has no solutions.

Case 2: cr · n. The system of equations corresponding to the non{zero

rows of B is consistent. First notice that r · n here.

If r = n, then c1 = 1; c2 = 2; ¢ ¢ ¢ ; cn = n and

B =

2

66666666664

1 0 ¢ ¢ ¢ 0 d1

0 1 ¢ ¢ ¢ 0 d2

...

...

0 0 ¢ ¢ ¢ 1 dn

0 0 ¢ ¢ ¢ 0 0

...

...

0 0 ¢ ¢ ¢ 0 0

3

77777777775

:

There is a unique solution x1 = d1; x2 = d2; ¢ ¢ ¢ ; xn = dn.

If r < n, there will be more than one solution (in¯nitely many if the

¯eld is in¯nite). For all solutions are obtained by taking the unknowns

xc1 ; ¢ ¢ ¢ ; xcr as dependent unknowns and using the r equations correspond-

ing to the non{zero rows of B to express these unknowns in terms of the

remaining independent unknowns xcr+1; : : : ; xcn, which can take on arbi-

trary values:

xc1 = b1 n+1 ¡ b1cr+1xcr+1 ¡ ¢ ¢ ¢ ¡ b1cnxcn

...

xcr = br n+1 ¡ brcr+1xcr+1 ¡ ¢ ¢ ¢ ¡ brcnxcn:

In particular, taking xcr+1 = 0; : : : ; xcn¡1 = 0 and xcn = 0; 1 respectively,

produces at least two solutions.

EXAMPLE 1.4.1 Solve the system

x + y = 0

x ¡ y = 1

4x + 2y = 1:

12 CHAPTER 1. LINEAR EQUATIONS

Solution. The augmented matrix of the system is

A =

2

4

1 1 0

1 ¡1 1

4 2 1

3

5

which is row equivalent to

B =

2

4

1 0 1

2

0 1 ¡1

2

0 0 0

3

5 :

We read o® the unique solution x = 1

2 ; y = ¡1

2 .

(Here n = 2; r = 2; c1 = 1; c2 = 2. Also cr = c2 = 2 < 3 = n + 1 and

r = n.)

EXAMPLE 1.4.2 Solve the system

2x1 + 2x2 ¡ 2x3 = 5

7x1 + 7x2 + x3 = 10

5x1 + 5x2 ¡ x3 = 5.

Solution. The augmented matrix is

A =

2

4

2 2 ¡2 5

7 7 1 10

5 5 ¡1 5

3

5

which is row equivalent to

B =

2

4

1 1 0 0

0 0 1 0

0 0 0 1

3

5 :

We read o® inconsistency for the original system.

(Here n = 3; r = 3; c1 = 1; c2 = 3. Also cr = c3 = 4 = n + 1.)

EXAMPLE 1.4.3 Solve the system

x1 ¡ x2 + x3 = 1

x1 + x2 ¡ x3 = 2:

1.4. SYSTEMATIC SOLUTION OF LINEAR SYSTEMS. 13

Solution. The augmented matrix is

A =

·

1 ¡1 1 1

1 1 ¡1 2

¸

which is row equivalent to

B =

·

1 0 0 3

2

0 1 ¡1 1

2

¸

:

The complete solution is x1 = 3

2 ; x2 = 1

2 + x3, with x3 arbitrary.

(Here n = 3; r = 2; c1 = 1; c2 = 2. Also cr = c2 = 2 < 4 = n + 1 and

r < n.)

EXAMPLE 1.4.4 Solve the system

6x3 + 2x4 ¡ 4x5 ¡ 8x6 = 8

3x3 + x4 ¡ 2x5 ¡ 4x6 = 4

2x1 ¡ 3x2 + x3 + 4x4 ¡ 7x5 + x6 = 2

6x1 ¡ 9x2 + 11x4 ¡ 19x5 + 3x6 = 1:

Solution. The augmented matrix is

A =

2

664

0 0 6 2 ¡4 ¡8 8

0 0 3 1 ¡2 ¡4 4

2 ¡3 1 4 ¡7 1 2

6 ¡9 0 11 ¡19 3 1

3

775

which is row equivalent to

B =

2

664

1 ¡3

2 0 11

6 ¡19

6 0 1

24

0 0 1 1

3 ¡2

3 0 5

3

0 0 0 0 0 1 1

4

0 0 0 0 0 0 0

3

775

:

The complete solution is

x1 = 1

24 + 3

2x2 ¡ 11

6 x4 + 19

6 x5,

x3 = 5

3 ¡ 1

3x4 + 2

3x5,

x6 = 1

4 ,

with x2; x4; x5 arbitrary.

(Here n = 6; r = 3; c1 = 1; c2 = 3; c3 = 6; cr = c3 = 6 < 7 = n + 1; r < n.)

14 CHAPTER 1. LINEAR EQUATIONS

EXAMPLE 1.4.5 Find the rational number t for which the following sys-

tem is consistent and solve the system for this value of t.

x + y = 2

x ¡ y = 0

3x ¡ y = t:

Solution. The augmented matrix of the system is

A =

2

4

1 1 2

1 ¡1 0

3 ¡1 t

3

5

which is row{equivalent to the simpler matrix

B =

2

4

1 1 2

0 1 1

0 0 t ¡ 2

3

5 :

Hence if t 6= 2 the system is inconsistent. If t = 2 the system is consistent

and

B =

2

4

1 1 2

0 1 1

0 0 0

3

5 !

2

4

1 0 1

0 1 1

0 0 0

3

5 :

We read o® the solution x = 1; y = 1.

EXAMPLE 1.4.6 For which rationals a and b does the following system

have (i) no solution, (ii) a unique solution, (iii) in¯nitely many solutions?

x ¡ 2y + 3z = 4

2x ¡ 3y + az = 5

3x ¡ 4y + 5z = b:

Solution. The augmented matrix of the system is

A =

2

4

1 ¡2 3 4

2 ¡3 a 5

3 ¡4 5 b

3

5

1.4. SYSTEMATIC SOLUTION OF LINEAR SYSTEMS. 15

½

R2 ! R2 ¡ 2R1

R3 ! R3 ¡ 3R1

2

4

1 ¡2 3 4

0 1 a ¡ 6 ¡3

0 2 ¡4 b ¡ 12

3

5

R3 ! R3 ¡ 2R2

2

4

1 ¡2 3 4

0 1 a ¡ 6 ¡3

0 0 ¡2a + 8 b ¡ 6

3

5 = B:

Case 1. a 6= 4. Then ¡2a + 8 6= 0 and we see that B can be reduced to

a matrix of the form 2

4

1 0 0 u

0 1 0 v

0 0 1 b¡6

¡2a+8

3

5

and we have the unique solution x = u; y = v; z = (b ¡ 6)=(¡2a + 8).

Case 2. a = 4. Then

B =

2

4

1 ¡2 3 4

0 1 ¡2 ¡3

0 0 0 b ¡ 6

3

5 :

If b 6= 6 we get no solution, whereas if b = 6 then

B =

2

4

1 ¡2 3 4

0 1 ¡2 ¡3

0 0 0 0

3

5 R1 ! R1 + 2R2

2

4

1 0 ¡1 ¡2

0 1 ¡2 ¡3

0 0 0 0

3

5. We

read o® the complete solution x = ¡2 + z; y = ¡3 + 2z, with z arbitrary.

EXAMPLE 1.4.7 Find the reduced row{echelon form of the following ma-

trix over Z3: ·

2 1 2 1

2 2 1 0

¸

:

Hence solve the system

2x + y + 2z = 1

2x + 2y + z = 0

over Z3.

Solution.

16 CHAPTER 1. LINEAR EQUATIONS

·

2 1 2 1

2 2 1 0

¸

R2 ! R2 ¡ R1

·

2 1 2 1

0 1 ¡1 ¡1

¸

=

·

2 1 2 1

0 1 2 2

¸

R1 ! 2R1

·

1 2 1 2

0 1 2 2

¸

R1 ! R1 + R2

·

1 0 0 1

0 1 2 2

¸

.

The last matrix is in reduced row{echelon form.

To solve the system of equations whose augmented matrix is the given

matrix over Z3, we see from the reduced row{echelon form that x = 1 and

y = 2 ¡ 2z = 2 + z, where z = 0; 1; 2. Hence there are three solutions

to the given system of linear equations: (x; y; z) = (1; 2; 0); (1; 0; 1) and

(1; 1; 2).

Навигация