Two row equivalent and reduced row echelon matrices are equal

Let A and C be matrices of the same dimension over a field F. Prove that if A and C are in reduced row echelon form and row equivalent, then A = C.


[I read this proof by Christian Roettger, and took a lemma. Ultimately this strategy went in a slightly different direction.]

We begin with some lemmas.

Lemma 1 (unused?): If A and C are row equivalent matrices over a field F, then Ax = 0 if and only if Cx = 0. Proof: Recall that, since A and C are row equivalent, there exists an invertible matix P such that PA = C. We may consider A, C, and P to be linear transformations V \rightarrow W and W \rightarrow W respectively. Fix appropriate bases so that A = M^E_B(\varphi), C = M^E_B(\psi), and P = M^E_E(\theta). Then we have \theta \circ \varphi = \psi. In particular, \mathsf{ker}\ \varphi \subseteq \mathsf{ker}\ \psi. Similarly, \varphi = \theta^{-1} \circ \psi, so that \mathsf{ker}\ \psi \subseteq \mathsf{ker}\ \varphi. So \mathsf{ker}\ \varphi = \mathsf{ker}\ \psi, and the conclusion follows. \square

Lemma 2: If A and C are row equivalent matrices of dimension n \times m over a field F, then the jth column of A is zero if and only if the jth column of C is zero. Proof: It suffices to show that the elementary row operations do not alter columns of zeros; this is clear. \square

Now we will proceed by induction on the number of rows.

For the base case, suppose A and C are 1 \times m matrices over F which are row equivalent and in reduced row echelon form. If A = 0 and C = 0, then certainly A = C. Suppose A \neq 0; using Lemma 2, we have C \neq 0. Moreover, A and C have the same pivot. Since A and C are row equivalent, there exists a 1 \times 1 matrix P over F (i.e. an element of F) such that PA = C. Say P = [\alpha]; since A and C have the same pivot, we have \alpha \cdot 1 = 1, so that \alpha = 1 and thus A = C.

For the inductive step, suppose that if A and C are row equivalent matrices in reduced row echelon form having n rows, then A = C. Let A = \left[ \begin{array}{c|c|c} 0 & 1 & V \\ \hline 0 & 0 & A_2 \end{array} \right] and C = \left[ \begin{array}{c|c|c} 0 & 1 & W \\ \hline 0 & 0 & C_2 \end{array} \right] be (n+1) \times m matrices in reduced row echelon form. Suppose A and C are row equivalent via the invertible matrix P = \left[ \begin{array}{c|c} P_{1,1} & P_{1,2} \\ \hline P_{2,1} & P_{2,2} \end{array} \right], where P_{1,1} has dimension 1 \times 1 and P_{2,2} has dimension n \times n (and the dimensions of P_{1,2} and P_{2,1} are as required.) In particular, by Lemma 2, A_2 and C_2 have the same dimension since A and C must have the same number of leading zero columns.

Using the structural lemmas in this previous exercise, from PA = C we have the following.

\left[ \begin{array}{c|c|c} 0 & P_{1,1}1 & P_{1,1}V + P_{1,2}A_2 \\ \hline 0 & P_{2,1}1 & P_{2,1}V + P_{2,2}A_2 \end{array} \right] = \left[ \begin{array}{c|c|c} 0 & 1 & W \\ \hline 0 & 0 & C_2 \end{array} \right]

In particular, note that P_{1,1}1 = 1, so that P_{1,1} = [1]. Similarly, Since P_{2,1}1 = 0, we have P_{2,1} = 0. Thus P_{2,2}A_2 = C_2. We claim that P_{2,2} is invertible. To see this, note that since P is invertible, there exists a matrix Q = \left[ \begin{array}{c|c} Q_{1,1} & Q_{1,2} \\ \hline Q_{2,1} & Q_{2,2} \end{array} \right] such that PQ = \left[ \begin{array}{c|c} Q_{1,1} + P_{1,2}Q_{2,1} & Q_{1,2} + P_{1,2}Q_{2,2} \\ \hline P_{2,2}Q_{2,1} & P_{2,2}Q_{2,2} \end{array} \right] = \left[ \begin{array}{c|c} 1 & 0 \\ \hline 0 & I \end{array} \right]. In particular, P_{2,2} is invertible. Note that at this point we have not proven that every invertible matrix is a product of elementary matrices- however, this is true, and we will assume it for now. We have shown, then, that A_2 and C_2 are row equivalent. They are also in reduced row echelon form, by our recursive definition of reduced row echelon form. Thus A_2 = C_2, and in fact P_{2,2} = I. That is, we have P = \left[ \begin{array}{c|c} 1 & P_{1,2} \\ \hline 0 & I \end{array} \right], where P_{1,2} has dimension 1 \times n.

In particular, we can see that P is a product of elementary matrices of the form E_{1,t}(\alpha), where t > 1. (See our previous discussion about elementary matrices.) To see this, note that

\left[ \begin{array}{c|c|c} I  & V & W \\ \hline 0 & I & 0 \\ \hline 0 & 0 & I \end{array} \right] = \left[ \begin{array}{c|c|c} I & V & 0 \\ \hline 0 & I & 0 \\ \hline 0 & 0 & I \end{array} \right] \left[ \begin{array}{c|c|c} I & 0 & W \\ \hline 0 & I & 0 \\ \hline 0 & 0 & I \end{array} \right]

and use induction.

It remains to be seen that V = W. To see this, say V (and W) have dimension 1 \times (m-k). Recall that every row in A either has a pivot or is 0. If the tth row of A is 0, then the elementary matrix E_{1,t}(\alpha) in the decomposition of P has no effect. That is, we can say P_{1,t} = 0. If the tth row of A has a pivot, say in column k+j, then the (1,j) entry of V is zero. Moreover, the (1,j) entry of W is simply the (1,t) entry of P. Note, however, that the tth row of C also has a pivot in column k+j. So in fact the (1,t) entry of P is 0. Thus we have P = I, and so A = C.

About these ads
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 210 other followers

%d bloggers like this: