# How prove that the elementary operations don't change the rank of a matrix [duplicate]

One considers certain operations, called elementary row operations, that are applied to a matrix $$A$$ to obtain a new matrix $$B$$ of the same size.

These are the following:

1. exchange rows $$i_1$$ and $$i_2$$ of $$A$$ (where $$i_1\neq i_2$$);
2. replace row $$i_1$$ of $$A$$ by itself plus the scalar $$c$$ times row $$i_2$$ (where $$i_1\neq i_2$$);
3. multiply row $$i$$ of $$A$$ by the non-zero scalar $$\lambda$$.

Naturally this operations can be implemented on a column and so we would call the analogous operations on the columns "elementary column operations".

Theorem

If $$B$$ is the matrix obtained by applying an elementary row/column operation to $$A$$, then these two matrix has the same rank.

Unfortunately I'm not able to prove the previous theorem, so could someone help me, please?

• The rank is the dimension of the space spanned by the rows of the matrix. Does exchanging the order of rows change the space spanned, etc.? – J. W. Tanner Jul 17 at 20:26
• (i) Show that multiplying a matrix by an invertible matrix does not change the rank. (ii) Show that the ERO/ECO operations are invertible. – copper.hat Jul 17 at 20:26
• An elementary row operation (1) does not change the space spanned by the rows and (2) does not change linear dependencies among the columns. – Alexey Jul 17 at 20:39
• Does this post or this post answer your question? – twosigma Jul 17 at 20:49

The most important fact is that elementary row operations are realized as multiplication (on the left) by an invertible matrix.

Once you know this fact, you can proceed as follows. Suppose $$A$$ and $$B$$ are $$m\times n$$ and there exists an invertible $$m\times m$$ matrix $$F$$ such that $$A=FB$$. Denote by $$a_1,a_2,\dots,a_n$$ and $$b_1,b_2,\dots,b_n$$ the columns of $$A$$ and $$B$$ respectively.

Consider indices $$i_1,i_2,\dots,i_k$$ such that $$1\le i_1. Then the columns $$a_{i_1},a_{i_2},\dots,a_{i_k}$$ are linearly independent if and only if $$b_{i_1},b_{i_2},\dots,b_{i_k}$$ are linearly independent.

It's sufficient to prove one implication, because $$B=F^{-1}A$$. So, suppose the columns $$a_{i_1},a_{i_2},\dots,a_{i_k}$$ are linearly independent and that $$\alpha_1b_{i_1}+\alpha_2b_{i_2}+\dots+\alpha_kb_{i_k}=0$$ Then we can multiply both sides by $$F$$ and get $$\alpha_1Fb_{i_1}+\alpha_2Fb_{i_2}+\dots+\alpha_kFb_{i_k}=0$$ Since $$Fb_i=a_i$$, by definition of matrix product, we obtain $$\alpha_1a_{i_1}+\alpha_2a_{i_2}+\dots+\alpha_ka_{i_k}=0$$ so $$\alpha_1=\alpha_2=\dots=\alpha_k=0$$.

In a similar way, we see that a column $$a_i$$ of $$A$$ is a linear combination of the columns $$a_{i_1},a_{i_2},\dots,a_{i_k}$$ if and only if $$b_i$$ is a linear combination of $$b_{i_1},b_{i_2},\dots,b_{i_k}$$, with the same coefficients.

As a consequence, $$a_{i_1},a_{i_2},\dots,a_{i_k}$$ is a basis of the column space of $$A$$ if and only if $$b_{i_1},b_{i_2},\dots,b_{i_k}$$ is a basis of the column space of $$B$$.

In particular, the column space of $$A$$ has the same dimension as the column space of $$B$$. Therefore $$A$$ and $$B$$ have the same column rank (the dimension is the maximum number of linearly independent columns, of course, because the columns are, by definition, generators of the column space).

This has other important consequences. When you find a row echelon form $$U$$ for $$A$$, it's easy to see that the pivot columns of $$U$$ form a basis of the column space of $$U$$. Therefore, the columns of $$A$$ corresponding to the pivot columns form a basis of the column space of $$A$$. This provides an algorithm for extracting a basis from the columns of $$A$$.

Not only this. If $$U$$ is the reduced row echelon form, we see that a nonpivot column is the linear combination of the pivot columns with lower column index and the coefficients in the nonpivot column are exactly those needed to write it as a linear combination.

Thus the same coefficients can be used to express the columns of $$A$$ corresponding to nonpivot columns as linear combination of the already found basis for the column space of $$A$$. Thus the reduced row echelon form of $$A$$ is unique, because its entries only depend on the linear relations between the columns of $$A$$.

Elementary row operations also preserve the row rank (dimension of the row space or maximum number of linearly independent rows). This is easier, because the row space is unchanged by elementary row operations.

This is obvious if the operation is swapping two rows. If the operation is multiplying a row by a nonzero constant, then the original row is a multiple of the new row, and conversely.

If the operation is of the form $$r_i+kr_j$$, then $$r_i=(r_i+kr_j)-kr_j$$, and conversely.

• Only a elementary question. You proved the theorem for elementary column operations but naturally the the proof for the elementary row operations is completely analogous so much that it can be obtained from the one above only substituting the words, right? – Antonio Maria Di Mauro Jul 17 at 21:09
• @AntonioMariaDiMauro I proved it for elementary row operations. – egreg Jul 17 at 21:18
• Okay, but you have chosen a linear combination of column vectors: so could you explain to me this? Forgive my confusion. – Antonio Maria Di Mauro Jul 17 at 21:20
• @AntonioMariaDiMauro How do you define the rank to begin with? – egreg Jul 17 at 21:30
• My text (Algebra lineare and geometria by Francesco Bottacin) defines the row/column rank as the maximum number of the vector rows/columns that are linearly independent. – Antonio Maria Di Mauro Jul 17 at 21:35

This is a super important linear algebra theorem. The basic idea of the proof is that each of these operations is equivalent to right-multiplication by a matrix of full rank. I'll give an example of each operation in the 2 by 2 case:

1. Swap the rows by multiplying on the right by $$\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$
2. Add the top row to the bottom with $$\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$$
3. Scale the top row by $$c$$ using $$\begin{pmatrix} c & 0 \\ 0 & 1 \end{pmatrix}$$

Since multiplying by a matrix of full rank preserves rank, it follows that the elementary row operations are rank-preserving.

The elementary operations have elementary matrices associated to them.

These matrices are invertible, thus the product of your original matrix by one of these does not change its rank, since the number of linearly independent row\column vectors is conserved by invertible linear transformations.

That is because if $$B$$ is obtained from $$A$$ by an elementary operation $$\rho$$, $$B$$ can be reduced to the same RREF as $$A$$ (just use $$\rho^{-1}$$ as the first operation when reducing $$B$$) and the rank of each matrix is the number of pivots in the RREF.

• I'm loking for formal answer. I grasp your answer, but I'd like if you prove that $B$ can reduced to the same $RREF$ as $A$. – Antonio Maria Di Mauro Jul 17 at 20:38
• @AntonioMariaDiMauro That's not a good reason to downvote an answer though. JCAA validly answered to the original question. – Ottavio Bartenor Jul 17 at 20:43
• @OttavioBartenor Okay, excuse me. Perhaps I'm autodidact: I'm looking for a formal question so that I don't like colloquial proof. – Antonio Maria Di Mauro Jul 17 at 20:46