How To Calculate The Rank of a Matrix

    행렬의 랭크는 주어진 행렬을 다루기 쉬운 꼴로 변환함으로써 쉽게 계산해 낼 수 있다. 행렬을 RREF로 변환하는 데 성공했다면 자연스럽게 linearly independent column들을 쉽게 찾아낼 수 있으므로, 단순히 그 개수를 셈으로써 행렬의 랭크를 계산할 수 있다.

Theorem 1

Theorem 1. The rank of any matrix equals the maximum number of its linearly independent columns.

Proof. Let $A \in M_{m \times n}(F)$. Consider $B := \{L_A(e_1), ..., L_A(e_n)\} = \{[A]^1, ..., [A]^n\}$ where $[A]^i$ is the $i$th column of $A$.
Denote $\forall v \in F^n, v = (v_1 \cdots v_n)^t$. Then $L_A(v) = \sum v_i[A]^i \in \langle B \rangle$, i.e., R($L_A$) $\subseteq \langle B \rangle$. Clearly, $\langle B \rangle \subseteq R(L_A)$. Thus $\langle B \rangle = R(L_A)$. 
$\Longrightarrow$ $\exists  C \subseteq B$ such that $C$ is a basis for R($L_A$).
$\Longrightarrow$ $|C| =$ rank($L_A$) = rank($A$). 
Note that $|C|$ is the maximum number of linearly independet columns of $A$. $\blacksquare$

Corollary. Let $A \in M_{m \times n}(F)$. Then rank($A$) = 0 $\Longleftrightarrow$ $A = O$.

Theorem 2

Theorem 2. Let $A \in M_{m \times n}(F)$ such that rank($A$) = $r$. Then
(1) $r \leq m, r \leq n$,
(2) By means of a finite number of elementary operations, $A$ can be transformed into the matrix $$D = \begin{pmatrix} I_r & O_1\\ O_2 & O_3 \end{pmatrix}$$ where $O_1, O_2, O_3$ are zero matrices.

Proof. If $A = O$, then $r = 0$. Thus $D = A = O$. Suppose that $A \neq O$ and $r > 0$.
The proof is by the mathematical induction on $m$.

i) $m = 1$ 
By means of at most one type 1 column operation and at most one type 2 column operation, and at most $n - 1$ type 3 column operation, $A$ can be transformed into $\begin{pmatrix} 1 & 0 & \cdots & 0 \end{pmatrix}$.

ii) $m - 1$
Assume that the theorem holds for any matrix with at most $m - 1$ rows for some $m > 1$.

iii) $m$
If $n = 1$, then the theorem can be established in a manner analogous to the case $m = 1$.
Now suppose that $n > 1$. Since $A \neq O, A_{ij} \neq 0$ for some $i, j$. By means of at most one type 1 row and column operations, at most on type 2 operation, and at most $m - 1, n - 1$ type 3 row and column operations, respectively, we can transform $A$ into $B = \begin{bmatrix}     \begin{array}{c|c}   1 & 0 \quad \cdots \quad 0 \\   \hline   0 \\   \vdots & B' \\   0     \end{array}   \end{bmatrix}$, where $B' \in B_{(m-1) \times (n-1)}(F)$.

-Claim: rank($B'$) = $r - 1$.
: Note that the first column of $B$ is one of the linearly independent columns. Since rank($B$) = $r$, there is the $r - 1$ linearly independent columns in other columns of $B$. Thus rank($B'$) = $r - 1$.

Then $r - 1 \leq m - 1, r - 1 \leq n - 1$
$\Longrightarrow$ $r \leq m, r \leq n$
Also, $B'$ can be transformed into $D' = \begin{pmatrix} I_{r-1} & O_4 \\ O_5 & O_6 \end{pmatrix}$. 
Let $D = \begin{bmatrix}     \begin{array}{c|c}   1 & 0 \quad \cdots \quad 0 \\   \hline   0 \\   \vdots & D' \\   0     \end{array}   \end{bmatrix}$. Then we can transform $B$ into $D$ by means of finite elementary operations. Hence $A$ can be transformed into $D = \begin{pmatrix} I_r & O_1\\ O_2 & O_3 \end{pmatrix}$. $\blacksquare$

Corollary 1

Corollary 1. Let $A \in M_{m \times n}(F)$ such that rank($A$) = $r$. Then $\exists B \in M_{m \times m}(F), C \in M_{n \times n}(F)$ such that $B, C$ are invertible and $D = BAC$, where $D = \begin{pmatrix} I_r & O_1 \\ O_2 & O_3 \end{pmatrix}.$

Proof. By The Thm 2, we can transform $A$ into $D$ by means of a finite number of elementary row and column operations. Then we can write as $D = R_p(I_m) \cdots R_1(I_m) A C_1(I_n) \cdots C_q(I_n)$. Define $B := R_p(I_m) \cdots R_1(I_m)$ and $C := C_1(I_n) \cdots C_q(I_n)$. Then $D = BAC$. Since elementary matrix is invertible, $B$ and $C$ are invertible. $\blacksquare$

    위 정리들을 이용해 정리 1과 같이 행렬의 column 뿐만 아니라 row를 통해서도 동일한 방법으로 랭크를 계산할 수 있다. 

Corollary 2

Corollary 2. Let $A \in M_{m \times n}(F)$. Then
(a) rank($A^t$) = rank($A$),
(b) The rank of any matrix equals the maximum number of its linearly independent rows,
(c) The rows and columns of any matrix generate subspaces of the same dimension.

Proof. 
(a) By Corollary 1, $\exists B \in M_{m \times m}(F), C \in M_{n \times n}(F)$ such that $B, C$ are invertible and $D = BAC$, where $D = \begin{pmatrix} I_r & O_1 \\ O_2 & O_3 \end{pmatrix}$ ($r$ = rank($A$)). 
$\Longrightarrow D^t = C^tA^tB^t.$ Since $C^t, B^t$ are invertible, rank($D^t$) = rank($C^tA^tB^t$) = rank($A^t$). Note that $D^t$ is an $n \times m$ matrix with the form of $D$. Thus rank($A^t$) = rank($D^t$) = rank($D$) = rank($A$) = r. 
(b), (c) By (a), it is clear. $\blacksquare$

Corollary 3

Corollary 3. Every invertible matrix is a product of elementary matrices.

Proof. Let $A$ be invertible $n \times n$ matrix. Then rank($A$) = n. By corollary 1, $\exists$ invertible matrices $B, C$ such that $D = BAC = I_n$. Actually, $B = R_p(I_m) \cdots R_1(I_m)$ and $C = C_1(I_n) \cdots C_q(I_n)$. Then $A = B^{-1}DC^{-1} = R^{-1}_1(I_m) \cdots R^{-1}_p(I_m)DC^{-1}_q(I_n) \cdots C^{-1}_1(I_n).$ Thus $A$ is a product of elementary matrices. $\blacksquare$