1.2 Solving linear equations

Back

We show how to solve any system of linear equations over an arbitrary ¯eld,

using the GAUSS{JORDAN algorithm. We ¯rst need to de¯ne some terms.

DEFINITION 1.2.1 (Row{echelon form) A matrix is in row{echelon

form if

(i) all zero rows (if any) are at the bottom of the matrix and

(ii) if two successive rows are non{zero, the second row starts with more

zeros than the ¯rst (moving from left to right).

For example, the matrix 2

664

0 1 0 0

0 0 1 0

0 0 0 0

0 0 0 0

3

775

is in row{echelon form, whereas the matrix

2

664

0 1 0 0

0 1 0 0

0 0 0 0

0 0 0 0

3

775

is not in row{echelon form.

The zero matrix of any size is always in row{echelon form.

DEFINITION 1.2.2 (Reduced row{echelon form) A matrix is in re-

duced row{echelon form if

1. it is in row{echelon form,

2. the leading (leftmost non{zero) entry in each non{zero row is 1,

3. all other elements of the column in which the leading entry 1 occurs

are zeros.

For example the matrices

·

1 0

0 1

¸

and

2

664

0 1 2 0 0 2

0 0 0 1 0 3

0 0 0 0 1 4

0 0 0 0 0 0

3

775

1.2. SOLVING LINEAR EQUATIONS 7

are in reduced row{echelon form, whereas the matrices

2

4

1 0 0

0 1 0

0 0 2

3

5 and

2

4

1 2 0

0 1 0

0 0 0

3

5

are not in reduced row{echelon form, but are in row{echelon form.

The zero matrix of any size is always in reduced row{echelon form.

Notation. If a matrix is in reduced row{echelon form, it is useful to denote

the column numbers in which the leading entries 1 occur, by c1; c2; : : : ; cr,

with the remaining column numbers being denoted by cr+1; : : : ; cn, where

r is the number of non{zero rows. For example, in the 4 £ 6 matrix above,

we have r = 3; c1 = 2; c2 = 4; c3 = 5; c4 = 1; c5 = 3; c6 = 6.

The following operations are the ones used on systems of linear equations

and do not change the solutions.

DEFINITION 1.2.3 (Elementary row operations) There are three

types of elementary row operations that can be performed on matrices:

1. Interchanging two rows:

Ri $ Rj interchanges rows i and j.

2. Multiplying a row by a non{zero scalar:

Ri ! tRi multiplies row i by the non{zero scalar t.

3. Adding a multiple of one row to another row:

Rj ! Rj + tRi adds t times row i to row j.

DEFINITION 1.2.4 [Row equivalence]Matrix A is row{equivalent to ma-

trix B if B is obtained from A by a sequence of elementary row operations.

EXAMPLE 1.2.1 Working from left to right,

A =

2

4

1 2 0

2 1 1

1 ¡1 2

3

5 R2 ! R2 + 2R3

2

4

1 2 0

4 ¡1 5

1 ¡1 2

3

5

R2 $ R3

2

4

1 2 0

1 ¡1 2

4 ¡1 5

3

5 R1 ! 2R1

2

4

2 4 0

1 ¡1 2

4 ¡1 5

3

5 = B.

8 CHAPTER 1. LINEAR EQUATIONS

Thus A is row{equivalent to B. Clearly B is also row{equivalent to A, by

performing the inverse row{operations R1 ! 1

2R1; R2 $ R3; R2 ! R2¡2R3

on B.

It is not di±cult to prove that if A and B are row{equivalent augmented

matrices of two systems of linear equations, then the two systems have the

same solution sets { a solution of the one system is a solution of the other.

For example the systems whose augmented matrices are A and B in the

above example are respectively

8<

:

x + 2y = 0

2x + y = 1

x ¡ y = 2

and

8<

:

2x + 4y = 0

x ¡ y = 2

4x ¡ y = 5

and these systems have precisely the same solutions.

Навигация