벡터 $x_1, ..., x_n \in \mathbb{R}^m$이 주어졌을 때 이 벡터들이 linearly independent한지 그 여부를 알기 위해서 다음과 같은 방정식의 해를 구하면 되었었다. $$\begin{bmatrix} | & & | \\ x_1 & \cdots & x_n \\ | & & | \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \vdots \\ \alpha_n \end{bmatrix} = \mathbf{0}$$ 이때 nonzero solution $(\alpha_1, ..., \alpha_n)$이 존재한다면 $x_1, ..., x_n$은 linearly dependent하고, 오직 trivial solution밖에 존재하지 않는다면 linearly independent하다. 따라서 선형 종속, 독립 여부를 판단하는 문제가 벡터 공간 $\mathbb{R}^m$에서는 선형 연립 방정식을 푸는 문제로 바뀌는 것이다.
Theorem
Theorem. Let \( \begin{bmatrix} | & & | \\ x_1 & \cdots & x_n \\ | & & | \end{bmatrix} \in \mathbb{M}_{m \times n}(\mathbb{R}) \), where each \( x_i \in \mathbb{R}^m \).
(1) \( \{ x_1, \dots, x_n \} \) is linearly independent \( \Longleftrightarrow Ax = 0 \) has the only trivial solution $x = (0, ..., 0)$.
(2) The nonzero rows of any rectangular matrix in the (reduced) row-echelon form are linearly independent, and so are the columns that contain leading 1's.
(3) If \( U \) is the (reduced) row-echelon form of \( A \), then the columns of \( U \) are linearly independent \( \Longleftrightarrow \) the columns of \( A \) are linearly independent.
(4) If \( n > m \), then \( \{ x_1, \dots, x_n \} \) is linearly dependent in \( \mathbb{R}^m \).
어떤 행렬의 RREF의 nonzero row들은 항상 linearly independent하고(leading 1을 포함하고 있기 때문에), 같은 논리로 leading 1을 포함하고 있는 column들도 linearly independent하다. 그리고 이 column들에 대응되는 원래 행렬의 column들도 linaerly independent하다. 조금더 형식적으로 적으면 다음과 같다.
Theorem
Theorem. Let $A \in M_{m \times n}(F)$ such that rank($A$) = $r > 0$, and let $B$ be the RREF of $A$. Then the followings hold:
(a) $\forall i \in \{1, ..., r\}, \exists$ $[B]^{j_i}$ such that $[B]^{j_i} = e_i$, where $e_i$ is the standard ordered basis vector of $\mathbb{R}^r$.
(b) $\{[A]^{j_1}, \cdots, [A]^{j_r}\}$ are linearly independent.
(c) $\forall k \in \{1, ..., n\}$, if $[B]^k = \sum_{i=1}^r d_ie_i$, then $[A]^k = \sum_{i=1}^r d_i[A]^{j_i}$.
Proof.
(a) Since rank($B$) = $r$, there is $r$ linearly independent columns in $B$. By the definition of RREF, each column is equal to $e_i$. Thus for each $i = 1, ..., r, \exists [B]^{j_i}$ such that $[B]^{j_i} = e_i$.
(b) Suppose that $\sum_{i=1}^r c_i[A]^{j_i} = \mathbf{0}$ for some $c_i \in F$. Since $B$ is the RREF of $A$, we denote that $B = R_p \cdots R_1 (A) = R_p(I) \cdots R_1(I)A = MA$, where $M := R_p(I) \cdots R_1(I)A$. Note that $[B]^{j_i} = M[A]^{j_i} (i = 1, ..., r)$. Thus $$M(\sum_{i=1}^r c_i[A]^{j_i}) = \sum_{i=1}^r c_i[B]^{j_i} = \sum_{i=1}^r c_ie_i = (c_1, \cdots, c_r)^t = \mathbf{0} \\ \Longrightarrow c_1 = \cdots = c_r = 0.$$ Hence $\{[A]^{j_1}, \cdots, [A]^{j_r}\}$ is linearly independent.
(c) Note that $A = M^{-1}B$, i.e., $[A]^k = M^{-1}[B]^k (k = 1, ..., n)$. Since $[B]^k = \sum_{i=1}^r d_ie_i$, $[A]^k = M^{-1}\sum_{i=1}^r d_ie_i = M^{-1} \sum_{i=1}^r d_i[B]^{j_i} = \sum_{i=1}^r d_i[A]^{j_i}$. $\blacksquare$
Row and Column Spaces
Definition. Let \( A \in \mathbb{M}_{m \times n}(\mathbb{R}) \), i.e., \( A = \begin{bmatrix} | & & | \\ c_1 & \cdots & c_n \\ | & & | \end{bmatrix} = \begin{bmatrix} - & r_1 & - \\ & \vdots & \\ - & r_m & - \end{bmatrix} \), where \( c_i \in \mathbb{R}^m \) and \( r_j \in \mathbb{R}^n \).
(i) The row space of \( A \), denoted by \( \mathcal{R}(A) \), is the subspace of \( \mathbb{R}^n \) spanned by \( \{ r_1, \dots, r_m \} \), i.e., \( \mathcal{R}(A) = \langle r_1, \dots, r_m \rangle \).
(ii) The column space of \( A \), denoted by \( \mathcal{C}(A) \), is the subspace of \( \mathbb{R}^m \) spanned by \( \{ c_1, \dots, c_n \} \), i.e., \( \mathcal{C}(A) = \langle c_1, \dots, c_n \rangle \).
(iii) The null space of \( A \), denoted by \( \mathcal{N}(A) \), is the solution set of the system \( Ax = 0 \), i.e., \[ \mathcal{N}(A) = \left\{ \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix} \in \mathbb{R}^n \,\middle|\, A \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix} = 0 \right\}. \]
Remark
Remark. (i) \( \mathcal{R}(A) = \mathcal{C}(A^T) \) and \( \mathcal{C}(A) = \mathcal{R}(A^T) \).
(ii) \( Ax = \begin{bmatrix} | & & | \\ c_1 & \cdots & c_n \\ | & & | \end{bmatrix} \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix} = x_1 a_1 + \cdots + x_n a_n \), for all \( x \in \mathbb{R}^n \) \[ \Rightarrow Ax \in \mathcal{C}(A), \quad \Rightarrow \mathcal{C}(A) = \{ Ax \mid x \in \mathbb{R}^n \} \subseteq \mathbb{K}^m. \]
(iii) If \( A \) and \( B \) are row-equivalent, then \( \mathcal{R}(A) = \mathcal{R}(B) \) and \( \mathcal{N}(A) = \mathcal{N}(B) \), but \( \mathcal{C}(A) \neq \mathcal{C}(B) \) in general.
위 정의는 left multiplication $L_A(x) = Ax$와 연관지어 생각해 볼만한 가치가 있다. Remark (ii)에서도 알 수 있듯이 $L_A$의 image $R(L_A)$에 대해서 $R(L_A) = \mathcal{C}(A)$가 성립한다. 그리고 자명하게 $\mathcal{N}(L_A) = \mathcal{N}(A)$가 성립한다.
위 Theorem에 의해서 $\mathcal{R}(A), \mathcal{C}(A), \mathcal{N}(A)$의 기저는 다음 알고리즘에 의해서 쉽게 찾을 수 있다.
Algorithm
Algorithm. Let \( A \in \mathbb{M}_{m \times n}(\mathbb{R}) \) and \( U \) be the (reduced) row echelon form of \( A \). Then:
(i) The set of the nonzero rows of \( U \) is a basis for \( \mathcal{R}(A) \).
(ii) The set of the lin. indep. sols of \( Ux = 0 \) is a basis for \( \mathcal{N}(A) \).
(iii) The set of the columns of \( A \) corresponding to the columns of \( U \) containing the leading 1's is a basis for \( \mathcal{C}(A) \).
Span 조건은 column, row, null space의 정의에서 주어지므로 linearly independent 조건만 충족해주면 된다. 따라서 위 Theorem에 의해서 그 조건이 주어지므로 위와 같은 알고리즘을 통해서 각 공간의 기저를 구할 수 있다. 그리고 이 공간의 차원을 다음과 같은 이름으로 특별하게 불러준다.
Remark
Remark. Let \( A \in \mathbb{M}_{m \times n}(\mathbb{R}) \).
(i) $\dim(\mathcal{C}(A)) = \dim(\mathcal{R}(A))$, and it is the number of leading 1's and also the number of basic variables.
(ii) $\dim(\mathcal{N}(A))$ is the number of free variables.
Rank and Nullity
Definition. Let \( A \in \mathbb{M}_{m \times n}(\mathbb{R}) \).
(i) We call \( \dim(\mathcal{R}(A)) = \dim(\mathcal{C}(A)) \) the rank of \( A \), denoted by rank($A$).
(ii) We call \( \dim(\mathcal{N}(A)) \) the nullity of \( A \), denoted by nullity($A$).
따라서 위 Remark와 basic variable과 free variable의 합은 전체 unknown, 다시 말해 행의 계수라는 사실에 의해 행렬 버전의 dimension theorem $$\text{rank}(A) + \text{nullity}(A) = n$$을 얻는다.
Theorem
Theorem.
(1) rank($I_n$) $= n$,
(2) \( A \) is invertible $\Longleftrightarrow$ rank($A$) $= n$ where $A \in \mathbb{M}_{n \times n}(\mathbb{R})$
(3) For \( A \in \mathbb{M}_{m \times n}(\mathbb{R}) \),
(i) rank($A$) $\leq \min\{m, n\}$
(ii) rank($A$) $+$ nullity($A$) $= n$
(iii) rank($A^T$) $+$ nullity($A^T$) $= m$
(iv) rank($A^T$) $=$ rank($A$)
또한 자명하게 알 수 있는 사실은, left muliplication transformation에 관점에서 생각하면 rank를 다음과 같이도 정의할 수 있다.
Definition. Let $A \in M_{m \times n}(F)$. We define the rank of $A$, denoted rank($A$), to be the rank of $L_A: F^n \longrightarrow F^m$.
Linear transformation의 rank는 image set의 dimension으로 정의하므로 rank를 어떻게 정의하건 본질적으로 두 정의는 동치임을 알 수 있다. 이때 다음의 정리가 성립한다.
Theorem
Theorem 1. Let $T \in \mathcal{L}(V, W)$, and let $\beta$ and $\gamma$ be oredered bases for $V, W$, respectively. Then rank($T$) = rank($[T]_{\beta}^{\gamma}$).
Proof. Define $A = [T]_{\beta}^{\gamma}$. Then rank($T$) = rank($L_A$) = rank($A$). $\blacksquare$
Theorem
Theorem. Let $T \in \mathcal{L}(V, W)$ and $U \in \mathcal{L}(W, Z)$ where $V, W$ and $Z$ are finite-dimensional vector space, and let $A, B$ be matrices such that $AB$ is defined. Then
(a) rank$(UT) \leq$ rank($U$),
(b) rank$(UT) \leq$ rank($T$),
(c) rank$(AB) \leq$ rank($A$),
(d) rank$(AB) \leq$ rank($B$).
(e) $\mathcal{N}(B) \subset \mathcal{N}(AB)$,
(f) $\mathcal{C}(AB) \subset \mathcal{C}(A)$,
(g) $\mathcal{R}(AB) \subset \mathcal{R}(B)$.
Proof. Let $A = [U]_{\beta}^{\gamma}, B = [T]_{\alpha}^{\beta}$, where $\alpha, \beta$ and $\gamma$ are ordered bases for $V, W$ and $Z$.
(a) Note that R($UT$) = $UT(V)$ = $U$(R($T$)) $\subseteq$ $U(W)$ = R($U$). $\Longrightarrow$ rank($UT$) = dim(R($UT$)) $\leq$ dim(R($U$)) = rank($U$).
(c) rank($AB$) = rank($L_AL_B$) $\leq$ rank($L_A$) = rank($A$) by (a).
(d) rank($AB$) = rank($B^tA^t$) $\leq$ rank($B^t$) = rank($B$) by (c).
(b) rank($UT$) = rank($[UT]_{\alpha}^{\gamma}$) = rank($[U]_{\beta}^{\gamma}[T]_{\alpha}^{\beta}$) = rank($AB$) $\leq$ rank($B$) = rank($[T]_{\alpha}^{\beta}$) = rank($T$) by (d). $\blacksquare$
위 정리와 같이, 두 행렬을 곱한 행렬의 랭크는 일반적으로 각 행렬의 랭크보다 작거나 같다. 선형 변환의 관점에서 본다면, 아니 그보다 더 근본적인 함수라는 개념의 관점에서 본다면 지극히 당연한 정리이다. 합성을 하면 할수록 일반적으로 치역, 즉 range의 크기가 점점 작아질 것이고, 그에 따라 rank 또한 작아질 것이기 때문이다. 그리고 선형 변환은 행렬과 수학적으로 동일한 역할을 수행하는 것으로 여길 수 있으므로 이러한 관계는 행렬에도 동일하게 적용된다. 이때 랭크가 같을 조건을 아래의 정리가 말해준다.
Theorem
Theorem. Let $A \in M_{m \times n}(F)$, and let $P \in M_{m \times m}(F), Q \in M_{n \times n}(F)$ such that $P$ and $Q$ are invertible. Then
(a) rank($AQ$) = rank($A$),
(b) rank($PA$) = rank($A$),
(c) rank($PAQ$) = rank($A$).
Proof. (a) Note that R($L_{AQ}$) = R($L_AL_Q$) = $L_AL_Q(F^n)$ = $L_A(F^n)$ = R($L_A$). $\Longrightarrow$ rank($AQ$) = rank($A$).
(b) Note that R($L_A$) $\leq F^m$. Then rank($PA$) = dim($L_PL_A(F^n)$) = dim($L_P$(R($L_A$))) = dim(R($L_A$)) = rank($A$).
(c) By (a) and (b), it is clear. $\blacksquare$
즉 임의의 행렬에 가역행렬을 아무리 곱해도 원래 행렬의 랭크에 영향을 미치지 못한다는 뜻이다. elementary matrix는 가역행렬이고, 동일한 기본 연산을 행렬에 수행하는 것은 elementary matrix를 행렬에 곱하는 것과 동일하기 때문에 위 정리에 따라 elementary operation은 행렬의 랭크에 아무런 영향을 미치지 못한다는 사실을 알 수 있다. 함수의 관점에서 볼 때, invertible은 곧 bijective이고 이는 함수의 정의역과 치역을 완벽하게 보존하고 일대일 대응시킨다는 뜻이므로 rank가 보존된다고 이해할 수 있다.
Corollary
Corollary. Elementary operations on a matrix are rank-preserving.
정리해보자. 임의의 행렬 $A$의 rank는 $A$의 row space $\mathcal{R}(A)$ 혹은 column space $\mathcal{C}(A)$의 dimension으로 정의가 된다. 그리고 이는 본질적으로 left multiplication transformation $L_A$의 image set의 dimension과 같다.
이때 행렬 $A$에 invertible matrix를 좌우에 아무리 곱해도 rank는 변하지 않고, elementary operation은 elementary matrix를 곱하는 것과 동일한 효과를 준다. 따라서 주어진 행렬 $A$를 elementary row operation을 통해 RREF로 변환하면 leading 1을 쉽게 찾을 수 있고, 이 leading 1을 가지고 있는 column에 대응되는 원래 행렬 $A$의 column들은 linearly independent한다. 따라서 $A$의 linearly independent한 column들을 찾을 수 있고, 이 행들이 바로 column space $\mathcal{C}(A)$의 기저이다. 그리고 이 기저의 크기가 바로 차원이고, 이는 rank이므로 위와 같은 방식을 통해 임의의 행렬의 rank를 구할 수 있다.
물론, 위의 방법을 통해 '항상' linearly independent column을 찾아내서 rank를 구할 수 있다는 것이지, 딱보고 바로 선형독립인 행들을 찾아낼 수 있다면 가장 좋다.
Theorem
Theorem. Let \( A \in \mathbb{M}_{m \times n}(\mathbb{R}) \) and let rank($A$) $= r$. Then
(1) For every submatrix \( B \) of \( A \), rank($B$) $\leq$ rank($A$) $= r$.
(2) There exists a submatrix \( C \) of \( A \) such that \( C \) is invertible, so that rank($C$) $= r$.
Existence
Theorem. Let \( A \in \mathbb{M}_{m \times n}(\mathbb{K}) \). Then the following are equivalent:
(1) \( \forall b \in \mathbb{K}^m \), \( \exists x \in \mathbb{K}^n \) such that \( Ax = b \)
(2) \( \mathcal{C}(A) = \mathbb{R}^m \)
(3) \( \mathrm{rank}(A) = m \)
(4) \( A \) has a right inverse
(5) The rows of \( A \) are linearly independent
Uniqueness
Theorem. Let \( A \in \mathbb{M}_{m \times n}(\mathbb{K}) \). Then the following are equivalent:
(1) \( \forall b \in \mathbb{K}^m \), \( Ax = b \) has at most one solution \( x \in \mathbb{R}^n \)
(2) The columns of \( A \) are linearly independent
(3) \( \dim(\mathcal{C}(A)) = n = \mathrm{rank}(A) \)
(4) \( \mathcal{R}(A) = \mathbb{R}^n \)
(5) \( \mathcal{N}(A) = \{ \mathbf{0} \} \)
(6) \( A \) has a left inverse
Invertibility Theorem
Theorem. Let \( A \in \mathbb{M}_{n \times n}(\mathbb{R}) \). Then the following are equivalent:
(1) \( A \) is invertible
(2) \( \det(A) \neq 0 \)
(3) \( A \) is row-equivalent to \( I_n \)
(4) \( A \) is a product of elementary matrices
(5) \( Ax = b \) has a solution for every \( b \in \mathbb{R}^n \)
(6) \( Ax = 0 \) has only the trivial solution
(7) \( \mathcal{N}(A) = \{ \mathbf{0} \} \)
(8) The columns of \( A \) are linearly independent
(9) \( \mathcal{C}(A) = \mathbb{R}^n \)
(10) \( A \) has a right inverse
(11) \( \mathrm{rank}(A) = n \)
(12) The rows of \( A \) are linearly independent
(13) \( \mathcal{R}(A) = \mathbb{R}^n \)
(14) \( A \) has a left inverse