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

Question

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?

Answer 1

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<i_2<\dots<i_k\le n$. 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.

Answer 2

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.

Answer 3

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.

Answer 4

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.