**Definition.** A system of m linear equations in the n
unknowns

is a system of the form:

**Note.** The above system can be written as
where A is the

coefficient matrix and is the vector of
variables. A solution to the

system is a vector such that
.

**Definition.** The augmented matrix for the above
system is

**Note. **We will perform certain operations on the
augmented matrix which

correspond to the fol lowing manipulations of the system of equations:

1. interchange two equations ,

2. multiply an equation by a non zero constant ,

3. replace an equation by the sum of itself and a multiple of another

equation.

**Definition. **The following are elementary row operations:

1. inter change row i and row j (denoted ),

2. multiplying the ith row by a nonzero scalar s (denoted
),

and

3. adding the ith row to s times the jth row (denoted
).

If matrix A can be obtained from matrix B by a series of elementary row

operations, then A is row equivalent to B , denoted A ~B or A → B.

**Notice. **These operations correspond to the above manipulations of the

equations and so:

**Theorem 1.6. Invariance of Solution Sets Under Row
Equivalence.**

If then the linear systems
and
have the

same solution sets.

**Definition 1.12.** A matrix is in row-echelon form if

(1) all rows containing only zeros appear below rows with nonzero entries,

and

(2) the first nonzero entry in any row appears in a column to the right of

the first nonzero entry in any preceeding row .

For such a matrix, the first nonzero entry in a row is the pivot for that

row.

**Example.** Which of the following is in row echelon form?

**Note.** If an augmented matrix is in row-echelon
form, we can use the

method of back substituton to find solutions .

**Example.** Consider the system

**Definition 1.13.** A linear system having no solution
is inconsistent. If

it has one or more solutions, it is consistent.

**Example. **Is this system consistent or inconsistent:

**Example. **Is this system consistent or inconsistent:

(HINT: This system has multiple solutions. Express the
solutions in terms

of an unknown parameter r).

**Note.** In the above example, r is a “free variable”
and the general

solution is in terms of this free variable.

**Note. Reducing a Matrix to Row-Echelon Form.**

(1) If the first column is all zeros, “mentally cross it off.” Repeat this

process as necessary.

(2a) Use row interchange if necessary to get a nonzero entry (pivot) p in

the top row of the remaining matrix.

(2b) For each row R below the row containing this entry p, add −r/p

times the row containing p to R where r is the entry of row R in the

column which contains pivot p. (This gives all zero entries below pivot p.)

(3) “Mentally cross off” the first row and first column to create a smaller

matrix. Repeat the process (1) - (3) until either no rows or no columns

remain.

**Example.** Page 68 number 2.

**Example.** Page 69 number 16. (Put the associated augmented matrix

in row-echelon form and then use substitution.)

**Note.** The above method is called Gauss reduction
with back substitution.

**Note.** The system
is equivalent to the
system

where is the ith
column matrix of A. Therefore,
is consistent

if and only if is in the span of
(the columns of A).

**Definition.** A matrix is in reduced row-echelon form
if all the pivots

are 1 and all entries above or below pivots are 0.

**Example.** Page 69 number 16 (again).

**Note. **The above method is the Gauss-Jordan method.

**Theorem 1.7. Solutions of
.**

Let **
**
be a linear system and let where H is in

row-echelon form.

(1) The system **
**
is inconsistent if and only if
has a row

with all entries equal to 0 to the left of the partition and a nonzero entry

to the right of the partition.

(2) If is consistent
and every column of H contains a pivot, the

system has a unique solution.

(3) If is consistent
and some column of H has no pivot, the

system has infinitely many solutions, with as many free variables as there

are pivot-free columns of H.

**Definition 1.14.** A matrix that can be obtained from an identity matrix

by means of one elementary row operation is an elementary matrix.

**Theorem 1.8.** Let A be an m × n matrix and let E be an m × m

elementary matrix. Multiplication of A **on the left **by E effects the

same elementary row operation on A that was performed on the identity

matrix to obtain E.

**Proof for Row-Interchange.** (This is page 71 number 52.) Suppose

E results from interchanging rows i and j:

Then the kth row of E is [0, 0, . . . , 0, 1, 0, . . . ,
0] where

(1) for the nonzero
entry if the kth entry,

(2) for k = i the nonzero entry is the jth entry, and

(3) for k = j the nonzero entry is the ith entry.

Let , and .
The kth row of B is

and

Now if then all
are 0 except for p = k and

Therefore for , the kth
row of B is the same as the kth row of

A. If k = i then all are 0 except for p = j
and

and the ith row of B is the same as the jth row of A.
Similarly, if k = j

then all are 0 except for p = i and

and the jth row of B is the same as the ith row of A.
Therefore

**Example. **Multiply some 3 × 3 matrix A by

to swap Row 1 and Row 2.

**Note.** If A is row equivalent to B, then we can find C such that CA = B

and C is a product of elementary matrices.

**Example.** Page 70 number 44.