MML Study Note

6. Basis and Rank

 
  • Jul 04, 2022

Basis and Rank

벡터 공간 $V$ 에서, 우리는 특히 $\mathcal{A}$ 에 있는 벡터들의 선형 결합으로 어떤 벡터 $\boldsymbol{v} \in V$ 를 얻을 수 있다는 속성을 가진 벡터 집합 $\mathcal{A}$ 에 관심이 있습니다. 이러한 벡터들은 특수한 벡터들이며, 이들에 대해서 살펴보도록 하겠습니다.

Generating Set and Basis

Definition 2.13 (Genearting Set and Span). Vector space $V = (\mathcal{V}, +, \cdot)$ 과 벡터 집합 $\mathcal{A} = \lbrace \boldsymbol{x}_1, \cdots, \boldsymbol{x}_k \rbrace \subseteq \mathcal{V}$ 를 고려해보도록 하겠습니다. 만약 $\mathcal{V}$ 에 속하는 모든 벡터 $\boldsymbol{v} \in \mathcal{V}$ 가 $\boldsymbol{x}_1, \cdots, \boldsymbol{x}_k$ 의 선형 결합으로 표현될 수 있을 때, 벡터 집합 $\mathcal{A}$ 를 $V$ 의 generating set (생성 집합) 이라고 부릅니다. 그리고 $\mathcal{A}$ 에 속하는 벡터들의 모든 선형 결합의 집합을 $\mathcal{A}$ 의 span 이라고 부릅니다. 만약 $\mathcal{A}$ 를 벡터 공간 $V$ 로 span한다면, $V = \text{span}\lbrack\mathcal{A}\rbrack$ 또는 $V = \text{span}\lbrack\boldsymbol{x}_1, \dotsc, \boldsymbol{x}_k\rbrack$ 로 작성합니다.

Generating sets는 vector (sub)spaces로 span하는 벡터 집합입니다. 즉, generating sets의 모든 벡터는 해당 벡터들의 선형 결합으로 표현할 수 있습니다.

Definition 2.14 (Basis). $V = (\mathcal{V}, +, \cdot)$ 과 $\mathcal{A} \in \mathcal{V}$ 인 vector space를 살펴봅시다. 만약 $\tilde{\mathcal{A}} \subseteq \mathcal{A} \subseteq \mathcal{V}$ 이면서 $V$ 를 span 하는 가장 작은 집합 $\tilde{\mathcal{A}}$ 가 존재하지 않는다면 $V$ 의 generating set $\mathcal{A}$ 는 minimal이라고 부릅니다. $V$ 의 선형 독립인 모든 생성 generating set은 minimal이며, 이를 $V$ 의 basis (기저) 라고 부릅니다.

$V = (\mathcal{V}, +, \cdot)$ 를 vector space라고 하고, $\mathcal{B} \subseteq \mathcal{V}, \mathcal{B} \neq \emptyset$ 이라고 가정하면, 다음의 문장들의 의미는 모두 동일합니다.

  • $\mathcal{B}$ 는 $V$의 basis(기저).
  • $\mathcal{B}$ 는 minimal generating set.
  • $\mathcal{B}$ is a maximal linearly independent set of vectors in $V$ . 즉, 이 집합에 다른 어떠한 벡터를 더하면 선형 종속이 됩니다.
  • $\boldsymbol{x} \in V$ 인 모든 벡터 $\boldsymbol{x}$ 는 $\mathcal{B}$ 에 대한 선형 결합이고 모든 선형 결합은 유일합니다. 즉,
\[\boldsymbol{x} = \sum_{i=1}^k \lambda_i\boldsymbol{b}_i = \sum_{i=1}^k \psi_i \boldsymbol{b}_i, \quad \lambda_i, \psi_i \in \mathbb{R}, \boldsymbol{b}_i \in \mathcal{B}, \lambda_i = \psi_i, i = 1, \dotsc, k \tag{2.77}\]

Example 2.16

  • $\mathcal{R}^3$ 에서 canonical/standard basis(표준 기저)는 다음과 같습니다.
\[\mathcal{B} = \left\lbrace \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} \right\rbrace\tag{2.78}\]
  • $\mathcal{R}^3$ 의 다른 기저로는 다음이 있습니다.
\[\mathcal{B}_1 = \left\lbrace \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} \right\rbrace, \quad \mathcal{B}_2 = \left\lbrace \begin{bmatrix} 0.5 \\ 0.8 \\ 0.4 \end{bmatrix}, \begin{bmatrix} 1.8 \\ 0.3 \\ 0.3 \end{bmatrix}, \begin{bmatrix} -2.2 \\ -1.3 \\ 3.5 \end{bmatrix} \right\rbrace \tag{2.79}\]
  • 다음 집합은 linearly independent 입니다.
\[\mathcal{A} = \left\lbrace \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix}, \begin{bmatrix} 2 \\ -1 \\ 0 \\ 2 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ 0 \\ -4 \end{bmatrix} \right\rbrace \tag{2.80}\]

그러나 $\mathbb{R}^4$ 의 generating sets과 basis는 아닙니다. 예를 들어, 벡터 $\lbrack 1, 0, 0, 0 \rbrack^\top$ 은 $\mathcal{A}$ 의 요소들의 선형 결합으로 얻을 수 없습니다.

Remark. 모든 vector space $V$ 에는 basis $\mathcal{B}$ 가 있습니다. 위 예제는 vector space $V$ 에 많은 basis가 있다는 것을 보여주고 있습니다. 즉, basis는 유일하지 않습니다. 그러나 모든 basis는 같은 수의 요소를 가지며, 이를 basis vectors라고 합니다.

유한한 차원의 vector space $V$ 를 고려해봅시다. 이 경우 $V$ 의 차원은 $V$ 의 basis vector의 수가 되며, 이를 $\text{dim}(V)$ 라고 씁니다. 만약 $U$ 가 $V$ 의 subspace( $U \subseteq V$ )라면, $\text{dim}(U) \leq \text{dim}(V)$ 이며, 오직 $U = V$ 일 때만 $\text{dim}(U) = \text{dim}(V)$ 입니다. 직관적으로 vector space의 차원은 vector space 에서의 독립적인 방향의 개수라고 생각할 수 있습니다.

Remark. vector space의 차원이 반드시 벡터의 요소 개수인 것은 아닙니다. 예를 들어, vector space $V = \text{span}\lbrack\begin{bmatrix} 0 \\ 1 \end{bmatrix}\rbrack$ 는 1차원이지만 basis vector는 2개의 요소를 가지고 있습니다.


Remark. subspace $U = \text{span}\lbrack\boldsymbol{x}_1, \dotsc, \boldsymbol{x}_m\rbrack \subseteq \mathbb{R}^n$ 의 basis는 다음의 단계를 통해 찾을 수 있습니다.
  1. spanning vectors를 행렬 $\boldsymbol{A}$ 의 열로 둡니다.
  2. $\boldsymbol{A}$ 의 row-echelon form을 결정합니다.
  3. pivot columns과 연관된 spanning vectors가 $U$ 의 basis 입니다.

Example 2.17 (Determining a Basis) 아래 벡터들에 의해 span된 vector subspace $U \subseteq \mathbb{R}^5$ 에서 어떤 벡터가 $U$ 의 basis 인지 찾아보도록 하겠습니다.

\[\boldsymbol{x}_1 = \begin{bmatrix} 1 \\ 2 \\ -1 \\ -1 \\ -1 \end{bmatrix}, \quad \boldsymbol{x}_2 = \begin{bmatrix} 2 \\ -1 \\ 1 \\ 2 \\ -2 \end{bmatrix}, \quad \boldsymbol{x}_3 = \begin{bmatrix} 3 \\ -4 \\ 3 \\ 5 \\ -3 \end{bmatrix}, \quad \boldsymbol{x}_4 = \begin{bmatrix} -1 \\ 8 \\ -5 \\ -6 \\ 1 \end{bmatrix} \in \mathbb{R}^5 \tag{2.81}\]

basis를 찾기 위해서, 먼저 $\boldsymbol{x}_1, \dotsc, \boldsymbol{x}_4$ 가 linearly independent 인지 확인할 필요가 있습니다. 따라서, 아래의 식을 풀어야 합니다.

\[\sum_{i=1}^4 \lambda_i \boldsymbol{x}_i = \boldsymbol{0} \tag{2.82}\]

위 식은 homogeneous system of equations을 행렬로 나타내어 풀 수 있습니다.

\[\lbrack \boldsymbol{x}_1, \boldsymbol{x}_2, \boldsymbol{x}_3, \boldsymbol{x}_4 \rbrack = \begin{bmatrix} 1 & 2 & 3 & -1 \\ 2 & -1 & -4 & 8 \\ -1 & 1 & 3 & -5 \\ -1 & 2 & 5 & -6 \\ -1 & -2 & -3 & 1 \end{bmatrix} \tag{2.83}\]

기본 변환 공식을 통해 row-echelon form으로 변환하면 다음과 같습니다.

\[\begin{bmatrix} 1 & 2 & 3 & -1 \\ 2 & -1 & -4 & 8 \\ -1 & 1 & 3 & -5 \\ -1 & 2 & 5 & -6 \\ -1 & -2 & -3 & 1 \end{bmatrix} \rightsquigarrow \cdots \rightsquigarrow \begin{bmatrix} 1 & 2 & 3 & -1 \\ 0 & 1 & 2 & -2 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}\]

pivot columns는 해당 벡터의 집합이 선형 독립이라는 것을 가리키기 때문에 우리는 row-echelon for을 통해 $\boldsymbol{x}_1, \boldsymbol{x}_2, \boldsymbol{x}_4$ 가 선형 독립이라는 것을 알 수 있습니다. ($\lambda_1\boldsymbol{x}_1 + \lambda_2\boldsymbol{x}_2 + \lambda_4\boldsymbol{x}_4 = \boldsymbol{0}$ 이 오직 $\lambda_1 = \lambda_2 = \lambda_4 = 0$ 일 때 풀리기 때문)

따라서, $\lbrace \boldsymbol{x}_1, \boldsymbol{x}_2, \boldsymbol{x}_4 \rbrace$ 가 $U$ 의 basis 입니다.


Rank

행렬 $\boldsymbol{A} \in \mathbb{R}^{m \times n}$ 에서 선형 독립인 열의 갯수는 선형 독립인 행의 수와 같으며, 이를 $\boldsymbol{A}$ 의 rank라 하며 $\text{rk}(\boldsymbol{A})$ 로 표기합니다.

Remark. 행렬의 rank는 다음의 몇 가지 중요한 속성들을 가지고 있습니다.
  • $\text{rk}(\boldsymbol{A}) = \text{rk}(\boldsymbol{A}^\top)$ , 즉, column rank는 row rank와 같습니다.
  • ($m \times n$) 행렬 $\boldsymbol{A}$ ($\in \mathbb{R}^{m \times n}$)의 열은 $\text{dim}(U) = \text{rk}(\boldsymbol{A})$ 인 subspace $U \subseteq \mathbb{R}^m$ 을 span 합니다. 이러한 subspace를 image 또는 range 라고 부릅니다. $U$ 의 basis는 $\boldsymbol{A}$ 에 대해 가우스 소거법을 적용하여 찾을 수 있으며, pivot columns와 동일합니다.
  • ($m \times n$) 행렬 $\boldsymbol{A}$ ($\in \mathbb{R}^{m \times n}$)의 행은 $\text{dim}(W) = \text{rk}(\boldsymbol{A})$ 인 subspace $W \subseteq \mathbb{R}^n$ 을 span 합니다. $W$ 의 basis 역시 $\boldsymbol{A}$ 에 대해 가우스 소거법을 적용하여 찾을 수 있습니다.
  • 모든 ($n \times n$) 행렬 $\boldsymbol{A}$ ($\in \mathbb{R}^{n \times n}$) 에 대해, $\text{rk}(\boldsymbol{A}) = n$ 일 때만 $\boldsymbol{A}$ 는 regular(invertible) 입니다.
  • 모든 ($m \times n$) 행렬 $\boldsymbol{A}$ ($\in \mathbb{R}^{m \times n}$) 이고 all $\boldsymbol{b} \in \mathbb{R}^m$ 일 때, $\text{rk}(\boldsymbol{A}) = \text{rk}(\boldsymbol{A}|\boldsymbol{b})$ 이라면 선형연립방정식 $\boldsymbol{Ax} = \boldsymbol{b}$ 의 해를 구할 수 있습니다.
  • $\boldsymbol{A} \in \mathbb{R}^{m \times n}$ 에 대해, $\boldsymbol{Ax} = \boldsymbol{b}$ 에 대한 subspace의 solution의 차원은 $n - \text{rk}(\boldsymbol{A})$ 입니다. 이 subspace를 kernel 또는 null space 라고 부릅니다.
  • 행렬 $\boldsymbol{A} \in \mathbb{R}^{m \times n}$ 의 rank 가 같은 차원의 행렬 중에서 가질 수 있는 가장 큰 rank와 같을 때, 이 행렬을 full rank 라고 합니다. 이는 Full-rank matrix의 rank는 행의 갯수와 열의 갯수 중 더 작은 값, 즉, $\text{rk}(\boldsymbol{A}) = \min(m, n)$ 이라는 의미입니다. 만약 full rank가 아니라면 그 행렬은 rank deficient 라고 부릅니다.

    • Example 2.18 (Rank)

    \[\boldsymbol{A} = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix}\]

    위 행렬 $\boldsymbol{A}$ 는 2개의 선형독립인 행과 열을 가지고 있으므로, $\text{rk}(\boldsymbol{A}) = 2$ 입니다.

    \[\boldsymbol{A} = \begin{bmatrix} 1 & 2 & 1 \\ -2 & -3 & 1 \\ 3 & 5 & 0 \end{bmatrix}\]

    위 행렬의 rank를 찾기 위해 가우스 소거법을 사용하면, 다음과 같습니다.

    \[\begin{bmatrix} 1 & 2 & 1 \\ -2 & -3 & 1 \\ 3 & 5 & 0 \end{bmatrix} \rightsquigarrow \cdots \rightsquigarrow \begin{bmatrix} 1 & 2 & 1 \\ 0 & 1 & 3 \\ 0 & 0 & 0 \end{bmatrix} \tag{2.84}\]

    따라서, 선형독립인 행과 열이 2개 있으므로 $\text{rk}(\boldsymbol{A}) = 2$ 입니다.


    다음 장에서 배우는 linear transformation과 접목하면, rank는 해당 행렬의 transformation 결과의 dimension을 의미하게 됩니다.