1.4: Uniqueness of the Reduced Row-Echelon Form

As we have seen in earlier sections, we know that every matrix can be brought into reduced row-echelon form by a sequence of elementary row operations. Here we will prove that the resulting matrix is unique; in other words, the resulting matrix in reduced row-echelon does not depend upon the particular sequence of elementary row operations or the order in which they were performed.

Let $A$ be the augmented matrix of a homogeneous system of linear equations in the variables $x_1, x_2, \cdots, x_n$ which is also in reduced row-echelon form. The matrix $A$ divides the set of variables in two different types. We say that $x_i$ is a basic variable whenever $A$ has a leading $1$ in column number $i$, in other words, when column $i$ is a pivot column. Otherwise we say that $x_i$ is a free variable.

Recall Example 1.3.8.

Example $\PageIndex{1}$: Basic and Free Variables

Find the basic and free variables in the system $$\begin{array}{c} x+2y-z+w=3 \\ x+y-z+w=1 \\ x+3y-z+w=5 \end{array}\nonumber$$

Solution

Recall from the solution of Example 1.3.8 that the row-echelon form of the augmented matrix of this system is given by $$\left [ \begin{array}{rrrr|r} 1 & 2 & -1 & 1 & 3 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right ]\nonumber$$ You can see that columns $1$ and $2$ are pivot columns. These columns correspond to variables $x$ and $y$, making these the basic variables. Columns $3$ and $4$ are not pivot columns, which means that $z$ and $w$ are free variables.

We can write the solution to this system as $$\begin{array}{c} x=-1+s-t \\ y=2 \\ z=s \\ w=t \end{array}\nonumber$$

Here the free variables are written as parameters, and the basic variables are given by linear functions of these parameters.

In general, all solutions can be written in terms of the free variables. In such a description, the free variables can take any values (they become parameters), while the basic variables become simple linear functions of these parameters. Indeed, a basic variable $x_i$ is a linear function of only those free variables $x_j$ with $j>i$. This leads to the following observation.

Proposition $\PageIndex{1}$: Basic and Free Variables

If $x_i$ is a basic variable of a homogeneous system of linear equations, then any solution of the system with $x_j=0$ for all those free variables $x_j$ with $j>i$ must also have $x_i=0$.

Using this proposition, we prove a lemma which will be used in the proof of the main result of this section below.

Lemma $\PageIndex{1}$: Solutions and the Reduced Row-Echelon Form of a Matrix

Let $A$ and $B$ be two distinct augmented matrices for two homogeneous systems of $m$ equations in $n$ variables, such that $A$ and $B$ are each in reduced row-echelon. Then, the two systems do not have exactly the same solutions.

Proof

With respect to the linear systems associated with the matrices $A$ and $B$, there are two cases to consider:

• Case $1$: the two systems have the same basic variables
• Case $2$: the two systems do not have the same basic variables

In case $1$, the two matrices will have exactly the same pivot positions. However, since $A$ and $B$ are not identical, there is some row of $A$ which is different from the corresponding row of $B$ and yet the rows each have a pivot in the same column position. Let $i$ be the index of this column position. Since the matrices are in reduced row-echelon form, the two rows must differ at some entry in a column $j>i$. Let these entries be $a$ in $A$ and $b$ in $B$, where $a \neq b$. Since $A$ is in reduced row-echelon form, if $x_j$ were a basic variable for its linear system, we would have $a=0$. Similarly, if $x_j$ were a basic variable for the linear system of the matrix $B$, we would have $b=0$. Since $a$ and $b$ are unequal, they cannot both be equal to $0$, and hence $x_j$ cannot be a basic variable for both linear systems. However, since the systems have the same basic variables, $x_j$ must then be a free variable for each system. We now look at the solutions of the systems in which $x_j$ is set equal to $1$ and all other free variables are set equal to $0$. For this choice of parameters, the solution of the system for matrix $A$ has $x_j=-a$, while the solution of the system for matrix $B$ has $x_j=-b$, so that the two systems have different solutions.

In case $2$, there is a variable $x_i$ which is a basic variable for one matrix, let’s say $A$, and a free variable for the other matrix $B$. The system for matrix $B$ has a solution in which $x_i=1$ and $x_j=0$ for all other free variables $x_j$. However, by Proposition $\PageIndex{1}$this cannot be a solution of the system for the matrix $A$. This completes the proof of case $2$.

Now, we say that the matrix $B$ is equivalent to the matrix $A$ provided that $B$ can be obtained from $A$ by performing a sequence of elementary row operations beginning with $A$. The importance of this concept lies in the following result.

Theorem $\PageIndex{1}$: Equivalent Matrices

The two linear systems of equations corresponding to two equivalent augmented matrices have exactly the same solutions.

Proof

The proof of this theorem is left as an exercise.

Now, we can use Lemma $\PageIndex{1}$ and Theorem $\PageIndex{1}$ to prove the main result of this section.

Theorem $\PageIndex{2}$: Uniqueness of the Reduced Row-Echelon Form

Every matrix $A$ is equivalent to a unique matrix in reduced row-echelon form.

Proof

Let $A$ be an $m \times n$ matrix and let $B$ and $C$ be matrices in reduced row-echelon form, each equivalent to $A$. It suffices to show that $B=C$.

Let $A^{+}$ be the matrix $A$ augmented with a new rightmost column consisting entirely of zeros. Similarly, augment matrices $B$ and $C$ each with a rightmost column of zeros to obtain $B^{+}$ and $C^{+}$. Note that $B^{+}$ and $C^{+}$ are matrices in reduced row-echelon form which are obtained from $A^{+}$ by respectively applying the same sequence of elementary row operations which were used to obtain $B$ and $C$ from $A$.

Now, $A^{+}$, $B^{+}$, and $C^{+}$ can all be considered as augmented matrices of homogeneous linear systems in the variables $x_1, x_2, \cdots, x_n$. Because $B^{+}$ and $C^{+}$ are each equivalent to $A^{+}$, Theorem $\PageIndex{1}$ ensures that all three homogeneous linear systems have exactly the same solutions. By Lemma $\PageIndex{1}$ we conclude that $B^{+}=C^{+}$. By construction, we must also have $B=C$.

According to this theorem we can say that each matrix $A$ has a unique reduced row-echelon form.