Two matrices and over a field are said to be *row equivalent* if there is a sequence of elementary row operations which transforms into . Prove that row equivalence is an equivalence relation.

Recall that the elementary row operations (for matrices over a field ) are as follows:

- Interchange two rows
- Add an -multiple of one row to another
- Multiply a row by a nonzero element of

We claim that (1) two of these are redundant and (2) elementary row operations can be achieved using multiplication by certain class of invertible “elementary matrices”, which happens to be closed under matrix inversion.

First, we show that row operation 1 (interchange two rows) can be achieved using a series of operations of types 2 and 3. Suppose we have a matrix whose rows are , and we wish to interchange and . Let’s write . We will perform a sequence of row operations of type 2 and 3, keeping track of the rows after each step.

Operation | Type | Rows |
---|---|---|

Start | ||

Add -1 times row to row . | 2 | |

Add 1 times row to row . | 2 | |

Add -1 times row to row . | 2 | |

Multiply row by -1. | 3 |

Note that we have achieved the same effect as a single application of operation 1. In addition, we only needed to use the elements 1 and -1 in , which always exist. (In fact, we have 1 and -1 in any ring with 1, which is a useful generalization.)

We can think of a type 3 operation as a special case of a type 2 operation if we allow the same row to play both parts in a type 2 operation. Thus we can say that two matrices are row equivalent if there is a sequence of type 2 row operations turning one into the other.

Now define, over a field , the elementary matrix as follows: , where if , if and , and 0 otherwise. Letting , we see that . If , then except when , so that this sum is just . If and , then except when . In this case, this sum is . If and , then except when , and the sum is . In either case, the matrix is simply after having row replaced by row plus times row or after having row multiplied by .

That is, two matrices and are row equivalent if and only if there is a matrix such that .

Note that, if , then . In this sum, if , then unless . Then the sum is 0 unless , in which case it is 1. If , then unless . . If , this sum is 1. if , this sum is . Otherwise, the sum is 0. Hence . In particular, is invertible and .

Now note that . In this sum, if , then unless . If , then the sum is 1, and otherwise is 0. If , then unless . Then the sum is 0 unless , in which case it is . Thus is invertible and we have .

Thus the matrix in our definition of row equivalence is invertible. Moreover, is also a product of elementary matrices.

Now it is easy to show that row equivalence is an equivalence relation.

- (Reflexive) The identiy matrix is elementary. Specifically, . Thus every matrix is row equivalent to itself.
- (Symmetric) Suppose can be row reduced to . Then there is a product of elementary matrices such that . Then . Since is a product of elementary matrices, can be row reduced to .
- (Transitive) Suppose can be row reduced to and to . Then there exist products and of elementary matrices such that and . Now is a product of elementary matrices, and . Thus can be row reduced to .

(It turns out that is generated by these elementary matrices, so that we can simply say and are row equivalent if there is an *invertible* matrix such that , rather than specifying that be a product of elementary matrices. We will prove this later.)