When you do row operations on a matrix, there is an ultimate conclusion. It is called the row reduced echelon form. We show here that every matrix has such a row reduced echelon form and that this row reduced echelon form is unique. The significance is that it becomes possible to use the definite article in referring to the row reduced echelon form. Hence important conclusions about the original matrix may be logically deduced from an examination of its unique row reduced echelon form. First we need the following definition.
Definition A.7.1 Define special column vectors e_{i} as follows.

Recall that ^{T} says to take the transpose. Thus e_{i} is the column vector which has all zero entries except for a 1 in the i^{th} position down from the top.
Now here is the description of the row reduced echelon form.
Definition A.7.2 An m × n matrix is said to be in row reduced echelon form if, in viewing successive columns from left to right, the first nonzero column encountered is e_{1} and if, in viewing the columns of the matrix from left to right, you have encountered e_{1},e_{2},
Example A.7.3 The following matrices are in row reduced echelon form.

Definition A.7.4 Given a matrix A, row reduction produces one and only one row reduced matrix B with A ∼ B. See Corollary A.7.9. We call B the row reduced echelon form of A.
Theorem A.7.5 Let A be an m×n matrix. Then A has a row reduced echelon form determined by a simple process.
Proof. Viewing the columns of A from left to right, take the first nonzero column. Pick a nonzero entry in this column and switch the row containing this entry with the top row of A. Now divide this new top row by the value of this nonzero entry to get a 1 in this position and then use row operations to make all entries below this equal to zero. Thus the first nonzero column is now e_{1}. Denote the resulting matrix by A_{1}. Consider the submatrix of A_{1} to the right of this column and below the first row. Do exactly the same thing for this submatrix that was done for A. This time the e_{1} will refer to F^{m−1}. Use the first 1 obtained by the above process which is in the top row of this submatrix and row operations, to produce a zero in place of every entry above it and below it. Call the resulting matrix A_{2}. Thus A_{2} satisfies the conditions of the above definition up to the column just encountered. Continue this way till every column has been dealt with and the result must be in row reduced echelon form. ■
Here is some terminology about pivot columns.
Definition A.7.6 The first pivot column of A is the first nonzero column of A which becomes e_{1} in the row reduced echelon form. The next pivot column is the first column after this which becomes e_{2} in the row reduced echelon form. The third is the next column which becomes e_{3} in the row reduced echelon form and so forth.
The algorithm just described for obtaining a row reduced echelon form shows that these columns are well defined, but we will deal with this issue more carefully in Corollary A.7.9 where we show that every matrix corresponds to exactly one row reduced echelon form.
Definition A.7.7 Two matrices A,B are said to be row equivalent if B can be obtained from A by a sequence of row operations. When A is row equivalent to B, we write A ∼ B.
Proposition A.7.8 In the notation of Definition A.7.7. A ∼ A. If A ∼ B, then B ∼ A. If A ∼ B and B ∼ C, then A ∼ C.
Proof.That A ∼ A is obvious. Consider the second claim. By Theorem A.6.6, there exist elementary matrices E_{1},E_{2},

It follows from Lemma A.6.8 that


By Theorem A.6.6, each E_{k}^{−1} is an elementary matrix. By Theorem A.6.6 again, the above shows that A results from a sequence of row operations applied to B. The last claim is left for an exercise. This proves the proposition. ■
There are three choices for row operations at each step in Theorem A.7.5. A natural question is whether the same row reduced echelon matrix always results in the end from following any sequence of row operations.
We have already made use of the following observation in finding a linear relationship between the columns of the matrix A, but here it is stated more formally.

so to say two column vectors are equal, is to say the column vectors are the same linear combination of the special vectors e_{j}.
Corollary A.7.9 The row reduced echelon form is unique. That is if B,C are two matrices in row reduced echelon form and both are obtained from A by a sequence of row operations, then B = C.
Proof.Suppose B and C are both row reduced echelon forms for the matrix A. It follows that B and C have zero columns in the same positions because row operations do not affect zero columns. By Proposition A.7.8, B and C are row equivalent. In reading from left to right in B, suppose e_{1},
Now with the above corollary, here is a very fundamental observation. The number of nonzero rows in the row reduced echelon form is the same as the number of pivot columns. Namely, this number is r in both cases where e_{1},
Consider a matrix which looks like this: (More columns than rows.)
Corollary A.7.10 Suppose A is an m × n matrix and that m < n. That is, the number of rows is less than the number of columns. Then one of the columns of A is a linear combination of the preceding columns of A. Also, there exists x ∈ F^{n} such that x≠0 and Ax = 0.
Proof: Since m < n, not all the columns of A can be pivot columns. In reading from left to right, pick the first one which is not a pivot column. Then from the description of the row reduced echelon form, this column is a linear combination of the preceding columns. Say

Therefore, from the way we multiply a matrix times a vector,
