MA2007B Linear Algebra I Lecture Note 14

Basis and dimension

Constructing a basis, as introduced in the previous lecture, can be challenging to analyze if the process never ends. While vector spaces can have infinite bases, we’ll focus on those with finite bases in this course. However, rather than assuming all vector spaces in our discussion have finite bases, we might adopt the weaker assumption that they are finitely generated. This approach is preferable because assuming a finite basis is a stronger condition than assuming finite generation, and we generally aim to start with the weaker assumption.

We should immediately define the basis for a vector space, as we’ve already begun to use this term.

Definition. A basis $β$ for a vector space $V$ is a linearly independent subset of $V$ that generates $V$ . If $β$ is a basis for $V$ , we shall often say that the elements of $β$ form a basis for $V$ .

Example. The standard basis for $F^{n}$ is the set ${(1, 0, \dots, 0), (0, 1, \dots, 0), \dots, (0, 0, \dots, 1)}$ . Example. ${(1, 1, 0), (0, 1, 1), (1, 0, 1)}$ forms a basis for $R^{3}$ .

Example. $P_{n} (F)$ has a basis ${1, x, x^{2}, \dots, x^{n}}$ .

Example. $P (F)$ has a basis ${1, x, x^{2} . \dots}$ .

Lemma. Let $S \subseteq V$ be a finite set that generates the vector space $V$ . Then $V$ has a finite basis.

proof. Let’s use the following process to construct a basis from $S = {x_{1}, \dots, x_{n}}$ .

S={x_1,...,x_n}
For i in (1,2,...,n)
  if x_i is in span(S\{x_i})
    remove x_i from S
return S

Since the elements that were removed are generated by other elements, the above algorithm returns a set that generates the vector space $V$ . The elements remaining in the set satisfy $x \notin span (S ∖ {x})$ . Therefore, if the resulting $S = {x_{1}, \dots, x_{n}}$ is linearly dependent, then there exist $a_{1}, \dots, a_{n} \in F$ , not all zero, such that

0 = a_{1} x_{1} + \dots + a_{n} x_{n}

Without loss of generality, we may assume $a_{1} = 1$ . Thus, $x_{1}$ is a linear combination of the other elements, which contradicts the property of $S$ . Therefore, $S$ is linearly independent and, consequently, a basis.

Lemma. Let $V$ be a vector space, and let $β$ be a basis for $V$ . If $S$ is a finite set for $V$ with $♯ S > ♯ β$ , then $S$ is linearly dependent.

Proof: Let $S = {y_{1}, \dots, y_{m}}$ and $β = {x_{1}, \dots, x_{n}}$ , where $m > n$ . Since $β$ is a basis for V, each $y_{i}$ can be expressed as a linear combination of the basis elements. That is, for each $y_{i}$ , there exist scalars $a_{i 1}, \dots, a_{i n} \in F$ such that

y_{i} = a_{i 1} x_{1} + \dots + a_{i n} x_{n}

Let’s consider the $m \times n$ matrix $A = (a_{i j})$ . Since $m > n$ , $A$ can be reduced to a triangular system through Gaussian elimination, resulting in a zero row vector at the bottom. This implies that $S$ is linearly dependent.

Lemma. Let $V$ be a vector space having a basis $β$ containing exactly $n$ elements. Let $S = {y_{1}, \dots, y_{m}}$ be a linearly independent subset of $V$ containing exactly $m$ elements, where $m \leq n$ . Then there exists a subset $S_{1}$ of $β$ containing exactly $n - m$ elements such that $S \cup S_{1}$ generates $V$ .

Proof. We proceed by induction. The statement is trivially true if $S$ is empty. For the inductive step, we assume the statement holds when $♯ S = m \leq n$ . We may assume $♯ S < n$ ; if $♯ S = n$ , then $S$ adjoining another element would become linearly dependent, so $S$ is already a basis. Now, we need to show that the statement holds when $♯ S = m + 1$ . Let $S = {y_{1}, \dots, y_{m}, y_{m + 1}}$ . By the induction hypothesis, there exists ${x_{1}, \dots, x_{k}} \subseteq β$ where $k = n - m$ such that ${y_{1}, \dots, y_{m}, x_{1}, \dots, x_{k}}$ is a basis. Furthermore, there exist scalars $a_{1}, \dots, a_{m}, b_{1}, \dots, b_{k} \in F$ such that

y_{n + 1} = a_{1} y_{1} + \dots + a_{n} y_{n} + b_{1} x_{1} + \dots + b_{k} x_{k} .

Note that $b_{1}, \dots, b_{k}$ are not all zero. Otherwise, $y_{n + 1}$ would be a linear combination of $y_{1}, \dots, y_{n}$ , contradicting the linear independence of $S$ . Without loss of generality, we may assume $b_{k} \neq 0$ . This implies

x_{k} = \frac{- a_{1}}{b_{k}} y_{1} + \dots + \frac{- a_{n}}{b_{k}} y_{n} + \frac{1}{b_{k}} y_{n + 1} + \frac{- b_{1}}{b_{k}} x_{1} + \dots + \frac{- b_{k - 1}}{b_{k}} x_{k - 1},

Thus, ${y_{1}, \dots, y_{k + 1}, x_{1}, \dots, x_{k - 1}}$ generates the vector space. We can therefore conclude that the statement holds by induction.