Basis and Dimension

Basis

Definition 1. A basis $\beta$ for $V$ is a linearly independent subset of $V$ such that <$\beta$> = $V$.

    generating set은 해당 벡터 공간의 정보를 알려주는 집합이고, 이때 최대한 그 크기를 줄인 집합이 linearly independent set이었다. 즉 두 조건을 모두 만족시키는 집합이야말로 벡터 공간을 다루기에 가장 좋은 집합이므로, 기저라는 이름으로 정의한다.

Remark

Remark.
(a) A basis can be infinite.
(b) Since <$\emptyset$> = $\{\mathbf{0}\}$ and $\emptyset$ is linearly independent, $\emptyset$ is a basis for $\{\mathbf{0}\}$. 
(c) In $F^n$, let $e_1 = (1, 0, ..., 0), e_2 = (0, 1, ..., 0), ..., e_n = (0, 0, ..., 1)$. Then the set $\{e_1, e_2, ..., e_n\}$ is a basis for $F^n$ and is called the standard basis for $F^n$.

---

Theorem 1

Theorem 1. Let $\beta = \{u_1, u_2, ..., u_n\} \subseteq V$.
Then $\beta$ is a basis for $V$ $\Longleftrightarrow$ $\forall v \in V, ! \exists a_i \in F(i = 1, ..., n)$ such that $v = \sum_{i=1}^n a_iu_i$.

Proof.
$(\Longrightarrow)$ Since <$\beta$> = $V$, it suffices to check the uniqueness. Let $v \in V$. Suppose that $v$ can be represented as two different ways: $v = \sum a_iu_i$ and $v = \sum b_iu_i$ for $a_i, b_i \in F$. Then $\mathbf{0} = \sum (a_i - b_i)u_i$. Since $\beta$ is linearly independent, $a_i - b_i = 0 \Longleftrightarrow a_i = b_i$. Hence $v$ is uniquely expressible as a linear combination of the vectors of $\beta$.

$(\Longleftarrow)$
Clearly <$\beta$> = $V$.
- Sol 1)
Suppose that $\beta$ is linearly dependent. Then $\mathbf{0} = \sum a_iu_i$ for $a_i \in F$, not all zero. Then $\mathbf{0} = \mathbf{0} + \mathbf{0} = \sum a_iu_i + \sum a_iu_i = \sum (2a_i)u_i$. Since $\mathbf{0} \in V$, $\mathbf{0}$ uniquely expressed by vectors of $\beta$. Thus $a_i = 2a_i \Longleftrightarrow a_i = 0 \bigotimes$ Hence $\beta$ is linearly independent and so $\beta$ is a basis for $V$.
- Sol 2)
Suppose that $\beta$ is linearly dependent and that $! \exists a_i \in F (i = 1, ..., n)$ such that $\mathbf{0} = \sum_{i=1}^{n} a_iu_i$. Then some $a_i$, says $a_1$, is nonzero, so we have $u_1 = \sum_{j=2}^{n} (-\frac{a_j}{a_1})u_j \Longrightarrow u_1 \in$ <$\beta \, \backslash \, \{u_1\}$>. Thus <$\beta \, \backslash \, \{u_1\}$> = $V$. $\Longrightarrow ! \exists b_j \in F (j = 1, ..., n)$ such that $\mathbf{0} = \sum_{j=2}^{n} b_ju_j$. Then we have two different representations of $\mathbf{0}$ as a linear combination of the vectors of $\beta$. $\bigotimes$ Hence $\beta$ is linearly independent and so $\beta$ is a basis for $V$. $\blacksquare$

    $\beta$가 $V$의 기저일 때, 각 $v \in V$마다 $(a_1, ..., a_n)$이 유일하게 정해지므로 bijection인 $T: v \longmapsto (a_1, ..., a_n)$가 존재한다. 즉 $V \simeq F^n$임을 알 수 있다.

---

Theorem 2

Theorem 2. If $V$ is generated by a finite set $S$, then some subset of $S$ is a basis for $V$. 

Proof. If $S = \emptyset$ or $S = \{\mathbf{0}\}$, then $V =$ <$S$> = $ \{\mathbf{0}\}$ and $\emptyset$ is a subset of $S$ that is a basis for $V$.
Suppose that $S$ contains a nonzero vector $u_1$. Then $\{u_1\}$ is a linearly independent set. Continue, if possible, choose vectors $u_2, ..., u_k \in S$ such that $\{u_1, u_2, ..., u_k\}$ is linearly independent. Since $S$ is a finite set, we must eventually reach a stage at which $\beta = \{u_1, u_2, ..., u_k\}$ is a linearly independent subset of $S$, but adjoining to $\beta$ any vector in $S$, not in $\beta$, produces a linearly dependent set. (Note that Theorem 2) Since $\beta$ is linearly independent, it suffices to show that <$\beta$> = $V$.
Since <$\beta$> $\subseteq$ <$S$> = $V$, we need to show $S$ $\subseteq$ <$\beta$>.
Let $v \in S$. If $v \in \beta$, then clearly $v \in$ <$\beta$>. Otherwise, if $v \notin \beta$, then $\beta \cup \{v\}$ is linearly dependent on the preceding construction. So $v \in$ <$\beta$> by Theorem 2. Thus $S \subseteq$ <$\beta$> $\Longrightarrow$ <$S$> $\subseteq$ <$\beta$> $\Longrightarrow$ <$\beta$> = <$S$> = $V$. Thus $\beta$ is a basis for $V$. $\blacksquare$

    앞서 말했듯 기저는 결국 generating set중 가장 크기가 작은 집합이므로, 뒤집으면 임의의 generating set이 주어지면 그 안에서 적당히 벡터를 골라내어서 기저를 잡아낼 수 있다는 것이다. 

---

Theorem 3 (Replacement Theorem)

Theorem 3. (Replacement Theorem) Let $V$ be generated by a set $G$ containing exactly $n$ vectors, and let $L$ be a linearly independent subset of $V$ containing exactly $m$ vectors. Then $m \leq n$ and $\exists H \subseteq G$ containing exactly $n-m$ vectors such that $L \cup H$ generates $V$.

Figure 1 (출처: Linear Algebra 4th ed. (S. Friedberg) 49p)

    기저란 generating set과 linearly independent set 모두를 만족하는 집합이다. 이때 기저에서 크기를 키우면 linearly independent의 조건이 사라지고, 크기를 줄이면 generate의 조건이 사라진다. 즉 두 조건의 경계가 기저가 됨을 알 수 있다. '기저 대체 정리'라고도 불리는 replacement theorem은 이러한 generating set과 linearly independent set 사이의 관계를 보여준다.

Proof. Apply the mathematical induction on $m$.
(i) $m = 0$
Clearly $0 \leq n$, and since $L = \emptyset$, we can take $H = G$.

(ii) $m = k$
Suppose that the theorem is true for some integer $k > 0$. That is, $k \leq n$ and for the linearly independent subset $L' = \{v_1, ..., v_k\}$ of $V$, $\exists H' \subseteq G$ containing exactly $n - k$ vectors such that $L' \cup H'$ generates $V$. Let take $H' = \{u_1, ..., u_{n-k}\}$.

(iii) $m = k+1$
Let $L = \{v_1, ..., v_k, v_{k+1}\}$ be a linearly independent subset of $V$. Since $v_{k+1} \in V$, $$v_{k+1} = \sum_{i=1}^k a_iv_i + \sum_{j=1}^{n-k} b_ju_j$$ for $a_i, b_j \in F (i = 1, ..., k, j = 1, ..., n - k)$.
Note that
(1) $n \neq k$,
(2) some $b_j$, say $b_1$, is nonzero. (($\because$) Otherwise, $L$ is linearly dependent $\bigotimes$.) 
Thus 
(1) $k < n \Longrightarrow k+1 \leq n$,
(2) $$u_1 = \sum_{i=1}^k (-\frac{a_i}{b_1})v_i + \frac{1}{b_1}v_{k+1} + \sum_{j=2}^{n-k} (-\frac{b_j}{b_1})u_j.$$
Let $H = \{u_2, ..., u_{n-k}\}$. Then $u_1 \in$ <$L \cup H$>. Note that $L' \cup H' \subseteq$ <$L \cup H$> $\Longrightarrow V = $<$L' \cup H'$> $\subseteq$ <$L \cup H$>. Clearly <$L \cup H$> $\subseteq V$. Thus $L \cup H$ generates $V$. $\blacksquare$

Corollary 3 - 1

Corollary 3 - 1. Let $V$ be a vector space having a finite basis. Then every basis for $V$ contains the same number of vectors. 

Proof. Let $\beta$ be a finite basis for $V$ that contains exactly $n$ vectors, and let $\gamma$ be any other basis for $V$. If $\gamma$ contains more than $n$ vectors, then we can select a subset $S$ of $\gamma$ containing exactly $n+1$ vectors. Since $S$ is linearly independent ($\gamma$ is a basis for $V$) and $\beta$ generates $V$, the replacement theorem implies that $n+1 \leq n. \bigotimes$
Therefore $\gamma$ is finite, and the number $m$ of vectors in $\gamma$ satisfies $m \leq n$. Reversing the roles of $\beta$ and $\gamma$ and arguing as above, we obtain $n \leq m$. Hence $m = n$. $\blacksquare$

---

Dimension

Definition 2. A vector space is called finite-dimensional if it has a basis consisting of a finite number of vectors. This number is called the dimension of $V$, denoted dim($V$).
A vector space that is not finite-dimensional is called infinite-dimensional.

    corollary 1에 의해 유한한 크기의 기저를 가지는 각 벡터공간마다 고유한 숫자가 부여되고, 이를 벡터공간의 차원이라 정의한다. 주의할 점은, 벡터 공간에 주어진 field에 따라 차원이 달라질 수 있다. 예컨대 복소수 집합 $\mathbb{C}$는 $\mathbb{C}$ 위에서는 차원이 1이지만, $\mathbb{R}$ 위에서는 2이다.

---

Corollary 3 - 2

Corollary 3 - 2. Let dim($V$) = $n$. 
(a) Any finite generating set for $V$ contains at least $n$ vectors, and a generating set for $V$ that contains exactly $n$ vectors is a basis for $V$.
(b) Any linearly independent subset of $V$ contains at most $n$ vectors, and a linearly independent subset of $V$ that contains exactly $n$ vectors is a basis for $V$.
(c) Every linearly independent subset of $V$ can be extended to a basis for $V$.
(d) Every generating set for $V$ can be reduced to a basis for $V$.

Proof. 
(a) Let $G$ be a finite generating set for $V$. By Theorem 2, $\exists H \in G$ such that $H$ is a basis for $V$. Since $|H| = n$, $G$ contains at least $n$ vectors. If we take $|G| = n$, then we must have $H = G$.
(b) Let $L$ be a finite linearly independent subset of $V$, and let $\beta$ be a basis for $V$. By the replacement theorem, $L$ contains at most $n$ vectors. If we take $|L| = n$, then, it follows from the replacement theorem that there is a subset $H$ of $\beta$ containing $(n - n) = 0$ vectors, i.e., $H = \emptyset$, such that $H \cup L = L$ generates $V$. Hence $L$ is a basis for $V$.
(c) Let $L$ be a linearly independent subset of $V$ containing $m$ vectors, and let $\beta$ be a basis for $V$. The replacement theorem asserts that $m \leq n$ and $\exists$ $H \in \beta$ such that $|H| = n - m$ and $L \cup H$ generates $V$. Then $L \cup H$ contains at most $n$ vectors and also contains at least $n$ vectors by (a). Hence $|L \cup H| = n$ so that $L \cup H$ is a basis for $V$ by (a).
(d) By theorem 2, it holds. $\blacksquare$

---

Theorem 4

Theorem 4. Let $W \leq V$ (dim($V$) = $n$). Then $W$ is finite-dimensional and dim($W$) $\leq$ dim($V$). Moreover, if dim($W$) = dim($V$), then $V = W$. 

Proof.
- Sol 1)
Let $\alpha$ and $\beta$ be bases for $W$ and $V$, respectively. Then $\alpha$ is a linearly independent subset of $V$ and $\beta$ is a generating set for $V$. By the replacement theorem, $|\alpha|$ = dim($W$) $\leq$ dim($V$) = $|\beta|$. Since $V$ is finite-dimensional, so is $W$. Moreover, if dim($W$) = dim($V$), then $\alpha$ is a basis for $V$ by corollary 3 - 2 (b). Thus $V$ = <$\alpha$> = $W$.
- Sol 2)
Let $\beta$ be a basis for $V$. If $W = \{\mathbf{0}\}$, then clearly the theorem is true. Otherwise, a nonzero vector $u_1 \in W$. We can continue the process to choose the vectors in $W$ such that $\gamma = \{u_1, ..., u_k\}$ is linearly independent until adjoining other vectors in $W$ to $\gamma$ produces a linearly dependent set. Then by the replacement theorem, $k \leq n$.
Let $v \in W$ but $v \notin \gamma$. Then $\gamma \cup \{v\}$ is linearly dependent $\Longleftrightarrow$ $v \in $<$\gamma$>. Clearly $\gamma \subseteq $<$\gamma$> $\subseteq W$. Thus <$\gamma$> = $W$. Hence dim($W$) = $k$. $\blacksquare$

Corollary 4 - 1

Corollary 4 - 1. If $W \leq V$ ($V$ is finite-dimensional), then any basis for $W$ can be extended to a basis for $V$. 

Proof. Since a basis for $W$ is a linearly independent subset of $V$, it follows from Corollary 3 - 2 (c) that a basis for $W$ can be extended to a basis for $V$. $\blacksquare$

---

Reference is here: https://product.kyobobook.co.kr/detail/S000003155051

Linear Algebra | Stephen Friedberg - 교보문고