Definition

Let $A$ be an $m \times n$. Any one of the following three operations on the rows [columns] of $A$ is called an elementary row [column] operation

interchanging any two rows [columns] of $A$;
multiplying any row [column] of $A$ by a non-zero scalar;
adding any scalar multiple of a row [column] of $A$ to another row [column].

Definition

An $n \times n$ elementary matrix is a matrix obtained by performing an elementary operation on $I_n$. The elementary matrix is said to be of type 1, 2 or 3 according to whether the elementary operation performed on $I_n$ is of type 1, 2 or 3 operation, respectively.

Theorem 3.1

Let $A \in M_{n \times n}(\mathbf{F})$ and suppose that $B$ is obtained from $A$ by performing an elementary row [column] operation. Then, there exists an $m \times m [n \times n]$ elementary matrix $E$ such that $B = EA [B = AE]$. In fact, $E$ is obtained from $I_m [I_n]$ by performing the same elementary row [column] operation as that which was performed on $A$ to obtain $B$. Conversely, if $E$ is an elementary $m \times m [n \times n]$ matrix, then $EA [AE]$ is the matrix obtained from $A$ by performing the same elementary row operation.

Theorem 3.2

Elementary matrices are invertible, and the inverse of an elementary matrix is an elementary matrix of the same type.

Proof

Let $E$ be an elementary $n \times n$ matrix. Then $E$ can be obtained by an elementary row operation on $I_n$ by definition. Reverse the steps used to transform $I_n$ into $E$ to get $I_n$ back. The result is that $I_n$ can be obtained from $E$ by an elementary row operation of the same type. By Theorem 3.1, there is an elementary matrix $\overline{E}$ such that $\overline{E}E = I_n$. But since $\overline{E}E = I_n$, then by Exercise 10 from 2.4, $\overline{E}$ and $E$ are invertible and we have $E^{-1} = \overline{E}$. $\ \blacksquare$

Definition

If $A \in M_{n \times n}(\mathbf{F})$ we define the rank of $A$, denoted $\text{rank}(A)$, to be the rank of the linear transformation $L_A: \mathbf{F}^n \rightarrow \mathbf{F}^m$

One important implication here is that an $n \times n$ matrix is invertible if and only if its rank is $n$.

Theorem 3.3

Let $T: V \rightarrow W$ be a linear transformation between finite-dimensional vector spaces, and let $\beta$ and $\gamma$ be ordered bases for $V$ and $W$, respectively. Then $rank(T) = rank([T]_{\beta}^{\gamma})$

The rank of a linear transformation is the same as the rank of one its matrix representations.

Theorem 3.4

Let $A$ be an $m \times n$ matrix. If $P$ and $Q$ are invertible $m \times m$ and $n \times n$ matrices, respectively, then

$\text{rank}(AQ) = \text{rank}(A)$,
$\text{rank}(PA) = \text{rank}(A)$ and therefore,
$\text{rank}(PAQ) = \text{rank}(A)$

Proof

(a) Observe that

$$ \begin{align*} R(L_{AQ}) &= R(L_AL_Q) \\ &= L_AL_Q(\mathbf{F}) \quad \text{(to get the range, we apply the linear map)}\\ &= L_A(L_Q(\mathbf{F})) \quad \text{(we apply $L_Q$ first)}\\ &= L_A(\mathbf{F}) \quad \text{(because $L_Q$ is onto)}\\ &= R(L_A) \end{align*} $$

Therefore,

$$ \begin{align*} \text{rank}(AQ) &= \dim(R(L_{AQ})) \quad \text{(the rank is the dimension of the range)} \\ &= \dim(R(L_A)) \quad \text{(by the previous result)} \\ &= rank(A). \end{align*} $$

Theorem 3.4 (Corollary)

Elementary row and column operations on a matrix are rank-preserving.

Theorem 3.5

The rank of any matrix equals the maximum number of its linearly independent columns; that is, the rank of a matrix is the dimension of the subspace generated by its columns.

Proof

For any $A \in M_{m \times n}(\mathbf{F})$,

$$ \begin{align*} \text{rank}(A) = \text{rank}(L_A) = \dim(R(L_A)) \end{align*} $$

Let $\beta$ be the standard ordered basis for $\mathbf{F}^n$. Then $\beta$ spans $\mathbf{F}^n$. Theorem 2.2 assets that $R(T) = \text(T(\beta))$ so

$$ \begin{align*} R(L_A) &= \text{span}(L_A(\beta)) \quad \text{(by Theorem 2.2)} \\ &= \text{span}(\{L_A(e_1),...,L_A(e_n)\}) \end{align*} $$

By theorem 2.13(b) $L_A(e_j) = Ae_j = a_j$ where $a_j$ is the $j$th column of $A$. So

$$ \begin{align*} R(L_A) &= \text{span}(\{a_1,...,a_n\}) \end{align*} $$

Therefore

$$ \begin{align*} \text{rank}(A) &= \dim(R(L_A)) = \dim(\text{span}(\{a_1,...,a_n\})) \ \blacksquare \end{align*} $$

Note: If you’ve forgotten 2.13 which you just did. Remember that by definition, matrix-vector multiplication $Av$ is defined as $a_1v_1 + a_2v_2 +...+ a_nv_n$ where $a_1,...,a_n$ are the columns of $A$ and $v_1,...,v_n$ are the entries of the vector $v$. Therefore, if you multiply $Ae_j$ where $e_j$ is from the standard basis, then we know that vector is all zeros except for the $j$th entry. So this means that $Ae_j = a_j$.

Theorem 3.6

Let $A$ be an $m \times n $ matrix of rank $r$. Then $r \leq m, r \leq n$, and by means of a finite number of elementary row and column operations, $A$ can be transformed into the matrix $$ \begin{align*} D = \begin{pmatrix} I_r & O_1 \\ O_2 & O_3 \end{pmatrix} \end{align*} $$ where $O_1$, $O_2$ and $O_3$ are zero matrices. Thus $D_{ii} = 1$ for $i \leq r$ and $D_{ij} = 0$ otherwise.

Theorem 3.6 (Corollary 1)

Let $A$ be an $m \times n $ matrix of rank $r$. Then there exists invertible matrices $B$ and $C$ of sizes $m \times m $ and $n \times n$ respectively, such that $D = BAC$ where $$ \begin{align*} D = \begin{pmatrix} I_r & O_1 \\ O_2 & O_3 \end{pmatrix} \end{align*} $$ is the $m \times n$ in which $O_1$, $O_2$ and $O_3$ are zero matrices.

Proof TODO

Theorem 3.6 (Corollary 2)

Let $A$ be $m \times n$ matrices. Then

Proof TODO

Theorem 3.6 (Corollary 3)

Every invertible matrix is a product of elementary matrices

Proof TODO

References

Linear Algebra 5th Edition