Search for probability and statistics terms on Statlect
StatLect

Row equivalence

by , PhD

This lecture defines the concept of row equivalence and proves some propositions about row equivalent matrices that lie at the heart of many important results in linear algebra.

Table of Contents

Definition

We start with a definition of row equivalence.

Definition Let A and $B$ be two $K	imes L$ matrices. We say that A is row equivalent to $B$ if and only if there exist $K	imes K$ elementary matrices [eq1] such that[eq2]

Remember that pre-multiplying A by an elementary matrix is the same as performing an elementary row operation on A. Therefore, A is row equivalent to $B$ if and only if A can be transformed into $B$ by performing a sequence of elementary row operations on A.

Equivalence relation

Row equivalence is an equivalence relation because it is:

Proof

Suppose A is row equivalent to $B$. Since an elementary matrix is invertible and its inverse is an elementary matrix, we have that [eq3]where [eq4] are elementary matrices. Therefore, $B$ is equivalent to A. This proves symmetry. If A is equivalent to $B$ and $B$ is equivalent to $C$, then[eq2]and[eq6]where [eq7] and [eq8] are elementary matrices. Now, pre-multiply both sides of the first equation by [eq9]:[eq10]Then, A is equivalent to $C$, that is, row equivalence is transitive. Finally, for any elementary matrix E, we can write[eq11]Since $E^{-1}$ is elementary, this means that we can transform A into itself by means of elementary row operations. As a consequence, row equivalence is reflexive.

Column correspondence property

The next proposition states an important property of row equivalence, known as column correspondence property.

Proposition Let A and $B$ be two $K	imes L$ matrices. Let A be row equivalent to $B$. Denote by $A_{ullet l}$ and $B_{ullet l}$ the $l$-th columns of A and $B$ respectively. Then, [eq12]for an $L	imes 1$ vector $v$ if and only if[eq13]

Proof

Since A is row equivalent to $B$, we have that[eq14]where E is a product of elementary matrices:[eq15]Furthermore, by the very definition of matrix product (see also here):[eq16]Thus, we can substitute[eq17]and[eq18]in the equation[eq19]so as to obtain[eq20]By pre-multiplying both sides by E, we get[eq21]Thus, we have proved that $A_{ullet l}=Av$ implies $B_{ullet l}=Bv$. The opposite implication ($B_{ullet l}=Bv$ implies $A_{ullet l}=Av$), can be proved analogously.

In other words, when A and $B$ are row equivalent, the $l$-th column of A can be written as a linear combination of a given set of columns of A itself, with coefficients taken from the vector $v$, if and only if the $l$-th column of $B$ is a linear combination of the corresponding set of columns of $B$, with coefficients taken from the same vector $v$.

A useful corollary of the previous proposition follows.

Proposition Let A and $B$ be two row equivalent matrices. Then, a set of columns of A is linearly independent if and only if the corresponding set of columns of $B$ is linearly independent.

Proof

The proof is by contradiction. Suppose that a set of columns of A is linearly independent, but the corresponding columns of $B$ are linearly dependent. It follows that a column $B_{ullet l}$ can be written as a linear combination of other columns:[eq22]where $v
eq 0$. In particular, there are some non-zero entries of $v$ corresponding to the columns in the set we are considering. But by the previous proposition, this implies that [eq19]In other words, the set of columns of A is not linearly independent, a contradiction. Therefore, if a set of columns of A is linearly independent, then the corresponding columns of $B$ must be linearly independent. The opposite implication can be proved analogously.

Dominant columns

This section introduces the concept of dominant columns, which will be used below to study the properties of row equivalent matrices.

Definition Let A be a $K	imes L$ matrix. Denote its $l$-th column by $A_{ullet l}$. We say that $A_{ullet l}$ is a dominant column if and only if it cannot be written as a linear combination of the columns to its left.

A first simple result about dominant columns follows.

Proposition Two equivalent matrices A and $B$ have the same set of dominant columns, that is, the set of indices of the dominant columns of A coincides with the set of indices of the dominant columns of $B$.

Proof

Suppose $A_{ullet l}$ is a dominant column of A. Then, there is no vector [eq24]such that [eq19]By the column correspondence property above, this is possible if and only if there is no such vector satisfying[eq26]As a consequence, $B_{ullet l}$ cannot be written as a linear combination of the columns to its left. Hence it is dominant. We have just proved that $A_{ullet l}$ is dominant only if $B_{ullet l}$ is dominant. The proof of the opposite implication is analogous. This holds for any $l$. Therefore, the columns that are dominant in A are dominant also in $B$ and vice versa.

For instance, if the dominant columns of A are the second, third and fifth, then the dominant columns of $B$ are the second, third and fifth.

Row equivalent matrices in reduced row echelon form

The propositions above allow us to prove some properties of matrices in reduced row echelon form.

Remember that a matrix is in reduced row echelon form (RREF) if and only if:

Furthermore, the Gauss-Jordan elimination algorithm can be used to transform any matrix into an RREF matrix by elementary row operations. Therefore, any matrix is row equivalent to an RREF matrix.

Remember that a basic column is a column containing a pivot, while a non-basic column does not contain any pivot.

The basic columns of an RREF matrix are vectors of the canonical basis, that is, they have one entry equal to 1 and all the other entries equal to zero. Furthermore, if an RREF matrix has $b$ basic columns, then those columns are the first $b$ vectors of the canonical basis, as stated by the following proposition.

Proposition Let $R$ be a matrix in reduced row echelon form. Then, the $l$-th basic column of $R$, counting from the left, is equal to the $l$-th vector of the canonical basis, that is, it has a 1 in position $l$ and all its other entries are equal to 0.

Proof

By the definition of RREF matrix, the basic columns of $R$ are vectors of the canonical basis (they have one entry equal to 1 and all other entries equal to 0). Furthermore, all non-zero rows contain a pivot. Therefore, the $l$-th basic column contains the $l$-th pivot, which is located on the $l$-th row. In other words, the pivot, which is equal to 1, is the $l$-th entry of the $l$-th basic column.

We now state some simple results concerning basic and non-basic columns.

Proposition A basic column of a matrix in reduced row echelon form is a dominant column.

Proof

A basic column contains a pivot, equal to 1, and all the entries to the left of the pivot are equal to 0. Therefore, the basic column cannot be written as a linear combination of the columns to its left (no linear combination of 0s can be equal to 1). Hence, it is a dominant column.

Proposition A non-basic column of a matrix in reduced row echelon form is not a dominant column.

Proof

If a column $R_{ullet l}$ is non-basic, that is, it has no pivot, then it can be written as[eq27]where k is the number of basic columns to its left (the entries below the k-th must be zero because the $m$-th pivot, with $m>k$, has only 0s to its left). Therefore, the non-basic column $R_{ullet l}$ can be written as a linear combination of the columns to its left. For example, if $k=3$ and the first, third and fourth columns are basic, then[eq28]Thus, if a column $R_{ullet l}$ is non-basic it is not linearly independent from the columns to its left. Hence, it is not a dominant column.

By combining the two simple propositions above, we get the following one.

Proposition If a matrix is in reduced row echelon form, then one of its columns is basic if and only if it is dominant, and it is non-basic if and only if it is not dominant.

Proof

By the previous proposition, if a column is dominant, then it cannot be non-basic. Therefore, it is basic. We have already established the opposite implication (basic implies dominant). Therefore, a column is dominant if and only if it is basic. The proof of equivalence for non-dominant columns is analogous.

Thus, when a matrix is in reduced row echelon form, we can use the concepts of basic and dominant column interchangeably.

We are now ready to state the most important proposition of this lecture.

Proposition Any matrix is row equivalent to a unique matrix in reduced row echelon form.

Proof

We have already explained that any matrix A is row equivalent to a matrix in reduced row echelon form which can be derived by using the Gauss-Jordan elimination algorithm. We need to prove uniqueness. Suppose that two matrices $R_{A}$ and $S_{A}$ are in reduced row echelon form and that they are both row equivalent to A. Since row equivalence is transitive and symmetric, $R_{A}$ and $S_{A}$ are row equivalent. Therefore, the positions of their dominant columns coincide. Equivalently, the positions of their basic columns coincide. But we have proved above that the $l$-th basic column of an RREF matrix, counting from the left, is equal to the $l$-th vector of the canonical basis. Therefore, not only the basic columns of $R_{A}$ and $S_{A}$ have the same positions, but their corresponding entries coincide. The non-basic columns are linear combinations of the basic ones. By the column correspondence property above, the coefficients of the linear combinations are the same for $R_{A}$ and $S_{A}$. But also the vectors being combined linearly coincide because the basic columns of $R_{A}$ and $S_{A}$ coincide. As a consequence, each non-basic column of $R_{A}$ is equal to the corresponding non-basic column of $S_{A}$. Thus, $R_{A}=S_{A}$, which proves that the row equivalent RREF of a matrix is unique.

A consequence of this uniqueness result is that if two matrices are row equivalent, then they are equivalent to the same RREF matrix.

Proposition Let A be row equivalent to $B$. Then, A and $B$ are equivalent to the same RREF matrix $R_{A}$.

Proof

Denote by $R_{A}$ and $R_{B}$ the RREF matrices that are row equivalent to $A $ and $B$ respectively:[eq29]where $E_{A}$ and $E_{B}$ are products of elementary matrices. Furthermore, A is row equivalent to $B$, so that[eq30]where $E_{AB}$ is a product of elementary matrices. We pre-multiply both sides of eq. (3) by $E_{B}$, so as to get[eq31]Since $E_{B}E_{AB}$ is a product of elementary matrices, $R_{B}$ is an RREF matrix row equivalent to A. But the RREF row equivalent matrix is unique. Therefore, $R_{A}=R_{B}$.

Rank and equivalence

In this section we present some corollaries of the results we have proved in the previous sections.

Proposition Let A be a $K	imes K$ invertible matrix. Then, A is row equivalent to the $K	imes K$ identity matrix I.

Proof

By the results above, we know that A is row equivalent to a unique RREF matrix $R$. Furthermore, A can be transformed into $R$ by elementary row operations, that is, by pre-multiplying A by an invertible matrix E (equal to the product of the elementary matrices used to perform the row operations):[eq32]But we know that pre-multiplication by an invertible (i.e., full-rank) matrix does not alter the rank. Therefore, $R$ is full-rank. As a consequence, all the columns of $R$ are basic (there cannot be non-basic columns because the columns of a full-rank matrix are all linearly independent from each other). But this means that the K columns of $R$ are the K vectors of the canonical basis of the space of K-dimensional vectors. In other words, they are the K columns of the $K	imes K$ identity matrix. Hence, $R=I$.

Clearly, since the identity matrix I is a matrix in reduced row echelon form, any invertible matrix is equivalent to the unique RREF matrix I.

An immediate consequence of the previous proposition follows.

Proposition Let A be a $K	imes K$ invertible matrix. Then, A can be written as a product of elementary matrices:[eq33]where [eq7] are elementary matrices.

Proof

By the previous proposition, the identity matrix I is row equivalent to A. So, by the definition of row equivalent matrix, we have that[eq35]where [eq7] are elementary matrices.

While the previous two propositions concern square invertible matrices, the following proposition applies to matrices that can be non-square and non-invertible.

Proposition Let $R$ be an RREF matrix that is row equivalent to a matrix A. Then A and $R$ have the same rank. The rank is equal to 1) the number of non-zero rows of $R$ or, equivalently, to 2) the number of basic columns of $R$.

Proof

First of all, remember that pre-multiplying a matrix A by an invertible matrix E does not change the rank of A. As a consequence, if E (an invertible product of elementary matrices) transforms A into a row equivalent RREF matrix $R=EA$, we have that[eq37]The rank of $R$ is equal to the maximum number of linearly independent columns of $R$. The basic columns of $R$ are linearly independent, while the non-basic columns can be written as linear combinations of the basic ones. Therefore, the rank of $R$ is equal to the number of basic columns of $R$. Furthermore, each basic columns contains a pivot and each non-zero row contains a pivot. As a consequence, the rank is also equal to the number of non-zero rows of $R$.

How to cite

Please cite as:

Taboga, Marco (2021). "Row equivalence", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/row-equivalence.

The books

Most of the learning materials found on this website are now available in a traditional textbook format.