Chapter 3 Bases

3.1 Spanning

Definition 3.1 Let \(V\) be a vector space over a field \(F\). Let \(x_1, \dots, x_n \in V\).

An element \(x \in V\) is called a linear combination of \(x_1, \dots, x_n\) if there are \(a_1, \dots, a_n \in F\) such that \(x = a_1x_1 + \dots + a_nx_n\).
The subset of \(V\) consisting of all linear combinations of \(x_1, \dots, x_n\) is called the span of \(x_1, \dots, x_n\) and is denoted by \(\mathrm{Span}(x_1, \dots, x_n)\) (or \(\mathrm{Span}_F(x_1, \dots, x_n)\)); i.e. \[ \mathrm{Span}(x_1, \dots, x_n) = \{ a_1x_1 + \dots + a_nx_n \mid a_1, \dots, a_n \in F \}. \]
We say that \(x_1, \dots, x_n\) span \(V\), or that \(x_1, \dots x_n\) form a spanning set of \(V\), if \(V = \mathrm{Span}(x_1, \dots, x_n)\), i.e. every \(x \in V\) is a linear combination of \(x_1, \dots, x_n\).

(See also Section 6.3 of L.A.I.)

Example 3.2

Let \(V := M_{n \times m}(F)\) be the vector space of \((n \times m)\)-matrices with entries in \(F\). For \(i \in \{1, \dots, n \}\) and \(j \in \{1, \dots, m\}\), let \(E_{ij}\) denote the \((n \times m)\)-matrix with zeroes everywhere except at \((ij)\) where it has the entry \(1\). Then the matrices \(E_{ij}; i=1, \dots, n ; j=1, \dots, m\) form a spanning set of \(V\).
Proof: Let \(A = (a_{ij}) \in M_{n \times m}(F)\) be an arbitrary matrix. Then \(A = \sum_{i=1}^n \sum_{j=1}^m a_{ij} E_{ij}\).
For example: \(\left(\begin{smallmatrix} 2 & 3 \\ -1 & 5 \end{smallmatrix}\right) = 2 \left(\begin{smallmatrix} 1 & 0 \\ 0 & 0 \end{smallmatrix}\right) + 3 \left(\begin{smallmatrix} 0 & 1 \\ 0 & 0 \end{smallmatrix}\right) + (-1) \left(\begin{smallmatrix} 0 & 0 \\ 1 & 0 \end{smallmatrix}\right) + 5 \left(\begin{smallmatrix} 0 & 0 \\ 0 & 1 \end{smallmatrix}\right)\) \(= 2E_{11}+3E_{12}+(-1)E_{21}+5E_{22}.\)
Do the vectors \(\begin{pmatrix} 1 \\ i \end{pmatrix}, \begin{pmatrix} i \\ 2 \end{pmatrix} \in \mathbb{C}^2\) span the vector space \(\mathbb{C}^2\) over \(\mathbb{C}\)?
Solution: Let \(\begin{pmatrix} w \\ z \end{pmatrix} \in \mathbb{C}^2\) be an arbitrary vector.
We want to know if we can find \(a_1, a_2 \in \mathbb{C}\) such that \(a_1 \begin{pmatrix} 1 \\ i \end{pmatrix} + a_2 \begin{pmatrix} i \\ 2 \end{pmatrix} = \begin{pmatrix} w \\ z \end{pmatrix}\).
Hence \(\left( \begin{array}{ c c | c } 1 & i & w \\ i & 2 & z \end{array} \right) \xrightarrow{R2 \mapsto R2 - iR1} \left( \begin{array}{ c c | c } 1 & i & w \\ 0 & 3 & z-iw \end{array} \right)\).
As in Linear Algebra I we conclude that this system is solvable. (Theorem 3.15 of L.A.I.)
Thus \(\begin{pmatrix} 1 \\ i \end{pmatrix}, \begin{pmatrix} i \\ 2 \end{pmatrix}\) span \(\mathbb{C}^2\).
\(\mathbb{P}_n = \mathrm{Span}(t^0,t^1,t^2, \dots, t^n) = \mathrm{Span}(1,t,t^2, \dots, t^n)\) (c.f. 2.10(d)(iv)).

Proposition 3.3 Let \(V\) be a vector space over a field \(F\). Let \(x_1, \dots, x_n \in V\). Then \(\mathrm{Span}(x_1, \dots, x_n)\) is the smallest subspace of \(V\) that contains \(x_1, \dots, x_n\). Furthermore:

If \(x \in \mathrm{Span}(x_1, \dots ,x_n)\) then \(\mathrm{Span}(x_1, \dots, x_n,x) = \mathrm{Span}(x_1, \dots, x_n)\).
For any \(a_2, \dots, a_n \in F\) we have \(\mathrm{Span}(x_1, \dots, x_n) = \mathrm{Span}(x_1, x_2-a_2x_1, \dots, x_n- a_nx_1)\).

Notes:

The first statement means:
1. \(\mathrm{Span}(x_1, \dots, x_n)\) is a subspace of \(V\) that contains \(x_1, \dots, x_n\), and
2. among all the subspaces of \(V\) with this property it is the smallest;
  in other words if \(W\) is a subspace of \(V\) that contains \(x_1, \dots, x_n\), then \(\mathrm{Span}(x_1, \dots x_n) \subseteq W\).
The statement (b) implies that the span of the column vectors of any matrix does not change when performing (standard) column operations.

Proof: \(\mathrm{Span}(x_1, \dots, x_n)\) is a subspace of \(V\):

We have \(0_{V} = 0_{F}x_1 + \dots + 0_{F}x_n \in \mathrm{Span}(x_1, \dots, x_n)\).
Let \(x,y \in \mathrm{Span}(x_1, \dots, x_n)\).
\(\implies \exists a_1, \dots, a_n \in F, \ \exists b_1, \dots b_n \in F\) such that     \(x= a_1x_1 + \dots + a_nx_n\) and \(y = b_1x_1 + \dots + b_nx_n\);
\(\implies x+y = (a_1x_1 + \dots + a_nx_n) + (b_1x_1 + \dots + b_nx_n)\)
    \(= (a_1x_1 + b_1x_1) + \dots + (a_nx_n + b_nx_n)\) (using commutativity and associativity)
    \(= (a_1 + b_1)x_1 + \dots + (a_n + b_n)x_n\) (using first distributivity law)
    \(\in \mathrm{Span}(x_1, \dots, x_n)\) (by definition of Span)
Let \(x \in \mathrm{Span}(x_1, \dots, x_n)\) and \(a \in F\).
Write \(x= a_1x_1 + \dots a_nx_n\) with \(a_1, \dots, a_n \in F\) as above.
\(\implies ax = a(a_1x_1 + \dots + a_nx_n)\)     \(= a(a_1x_1) + \dots + a(a_nx_n)\) (using distributivity)
    \(= (a a_1)x_1 + \dots + (a a_n)x_n\) (by axiom 2.4(iii))
    \(\in \mathrm{Span}(x_1, \dots, x_n)\) (by definition of Span)

\(\mathrm{Span}(x_1, \dots, x_n)\) contains \(x_1, \dots, x_n\):
… because \(x_{i} = 0_{F}\cdot x_1 + \dots 0_{F}\cdot x_{i-1} + 1 \cdot x_{i} + 0_{F}\cdot x_{i+1} + \dots + 0_{F}\cdot x_n\) \(\in \mathrm{Span}(x_1,\dots,x_n)\).

\(\mathrm{Span}(x_1, \dots, x_n\)) is the smallest:
     Let \(W\) be a subspace of \(V\) such that \(x_1, \dots, x_n \in W\).
     Let \(x \in \mathrm{Span}(x_1, \dots, x_n)\). Write \(x = a_1x_1 + \dots + a_nx_n\) with \(a_1, \dots a_n \in F\).
     \(\implies\) \(a_1x_1, \dots, a_nx_n \in W\) (by condition 2.8(c))
     \(\implies\) \(x = a_1x_1 + \dots + a_nx_n \in W\). (by condition 2.8(b))
     \(\implies\) \(\mathrm{Span}(x_1,\dots,x_n)\subseteq W\).

Part (a): \(\mathrm{Span}(x_1, \dots, x_n) \subseteq \mathrm{Span}(x_1, \dots, x_n,x) =: W\)
  (because \(W\) is a subspace of \(V\) and \(x_1, \dots, x_n \in W\))
     \(\mathrm{Span}(x_1, \dots, x_n,x) \subseteq \mathrm{Span}(x_1, \dots, x_n) =: \widetilde{W}\)
  (because \(\widetilde{W}\) is a subspace of \(V\) and \(x_1, \dots, x_n,x \in \widetilde{W}\))

Part (b): \(\mathrm{Span}(x_1, \dots, x_n) \subseteq \mathrm{Span}(x_1, x_2-a_2x_1, \dots, x_n-a_nx_1) =: W\)
  (because \(W\) is a subspace of \(V\) and \(x_1, \dots, x_n \in W\))
     \(\mathrm{Span}(x_1, x_2-a_2x_1, \dots, x_n-a_nx_1) \subseteq \mathrm{Span}(x_1, \dots, x_n) =: \widetilde{W}\)
  (because \(\widetilde{W}\) is a subspace of \(V\) and \(x_1\in \widetilde{W}\) and for \(i=2,\dots,n\) also \(x_i-a_ix_1 \in \widetilde{W}\))\(\square\)

3.2 Linear independence

Definition 3.4 Let \(V\) be a vector space over a field \(F\). Let \(x_1, \dots, x_n \in V\). We say that \(x_1, \dots, x_n\) are linearly independent (over \(F\)) if the following condition holds:

if \(a_1, \dots, a_n \in F\) and \(a_1x_1 + \dots + a_nx_n = 0_V\) then \(a_1 = \dots = a_n = 0_F\).

Otherwise we say that \(x_1, \dots, x_n\) are linearly dependent. A linear combination \(a_1x_1+\dots+a_nx_n\) is called trivial if \(a_1=\dots=a_n=0\), otherwise it is called non-trivial. (See also Section 6.5 of L.A.I.)

Note: \(x_1,\dots,x_n\) are linearly dependent \(\iff\) \(\exists a_1,\dots,a_n\in F\), not all zero, such that \(a_1x_1+\dots+a_nx_n=0_V\). In other words, \(\iff\) there exists a non-trivial linear combination of \(x_1,\dots,x_n\) which equals \(0_V\).

Example 3.5

Examples as seen in Linear Algebra I. (Section 6.5 of L.A.I.)
The three vectors \(\underline{x}_1 = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}\), \(\underline{x}_2 = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}\), \(\underline{x}_3 = \begin{pmatrix} 0 \\ -1 \\ 1 \end{pmatrix} \in F^3\) are not linearly independent because \(\underline{x}_1 - \underline{x}_2 - \underline{x}_3 = \underline{0}\).
Determine all vectors \(\begin{pmatrix} c_1 \\ c_2 \\ c_3 \end{pmatrix} \in \mathbb{C}^3\) such that \(\underline{x}_1:= \begin{pmatrix} 1 \\ i \\ 1 \end{pmatrix}\), \(\underline{x}_2:= \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}\), \(\underline{x}_3:= \begin{pmatrix} c_1 \\ c_2 \\ c_3 \end{pmatrix} \in \mathbb{C}^3\) are linearly dependent.
Solution: We apply Gaussian elimination: \[\begin{pmatrix} 1 & 0 & c_1 \\ i & 1 & c_2 \\ 1 & 0 & c_3 \end{pmatrix} \xrightarrow[R2 \mapsto R2 - iR1]{R3 \mapsto R3 - R1} \begin{pmatrix} 1 & 0 & c_1 \\ 0 & 1 & c_2 - ic_1 \\ 0 & 0 & c_3 - c_1 \end{pmatrix}\]
    \(\implies\) The equation \(a_1\underline{x}_1 + a_2\underline{x}_2 + a_3\underline{x}_3 = \underline{0}\) has a non-trivial solution \((a_1, a_2, a_3)\)
                    if and only if \(c_3 - c_1 = 0\).
    \(\implies\) \(\underline{x}_1, \underline{x}_2, \underline{x}_3\) are linearly dependent if and only if \(c_1 = c_3\).
The two functions \(\sin , \cos \in \mathbb{R}^{\mathbb{R}}\) are linearly independent.
Proof: Let \(a,b \in \mathbb{R}\) such that \(a \sin + b \cos = \underline{0}\) in \(\mathbb{R}^{\mathbb{R}}\).
\(\implies\) For all \(s\in \mathbb{R}\) we have \(a\cdot\sin(s) + b\cdot \cos(s) = \underline{0}(s) = 0\).
\(\implies \begin{cases} a\cdot \sin (0) + b\cdot \cos (0) = 0 \implies a \cdot 0 + b \cdot 1 = 0 \implies b=0 \\ a\cdot \sin (\frac{\pi}2) + b\cdot \cos (\frac{\pi}2) = 0 \implies a \cdot 1 + b \cdot 0 = 0 \implies a=0 \end{cases}\) \(\square\)
Let \(I \subseteq \mathbb{R}\) be a non-empty open interval. Recall from 2.10(d)(iv) that for any \(i \in \mathbb{N}_{0}\), we denote \(t^{i}\) the polynomial function \(I \rightarrow \mathbb{R}, s \mapsto s^{i}\).
The vectors \(t^0,t^1,t^2, \dots, t^n\) are linearly independent in \(\mathbb{R}^{I}\).
Proof: Let \(a_{0}, \dots, a_n \in \mathbb{R}\) such that \(a_{0}t^0 + a_1t^1 + \dots + a_nt^n = \underline{0}\)
\(\implies a_{0} + a_1s + \dots + a_ns^n = 0\) for all \(s \in I\)
\(\implies a_{0} = \dots = a_n = 0\), because any non-zero real polynomial of degree \(n\) has at most \(n\) real roots. (This follows from the Fundamental Theorem of Algebra. Alternatively, it can be proved by induction and using long division.)

Proposition 3.6 Let \(V\) be a vector space over a field \(F\).

A single vector \(x \in V\) is linearly independent if and only if \(x \neq 0_{V}\).
Every subset of any set of linearly independent vectors is linearly independent again. (This is equivalent to: If a subset of a set of vectors is linearly dependent, then the set itself is linearly dependent.)
Let \(x_1, \dots, x_n \in V\) and suppose that \(x_{i} = 0_{V}\) for some \(i \in \{1, \dots, n \}\), or that \(x_{i} = x_{j}\) for some \(i \neq j\). Then \(x_1, \dots, x_n\) are linearly dependent.
If \(x_1, \dots, x_n \in V\) are linearly dependent then at least one vector \(x_{i}\) among \(x_1, \dots, x_n\) is a linear combination of the other ones.
Let \(x_1, \dots, x_n \in V\) and \(x \in \mathrm{Span}(x_1, \dots, x_n)\). Then \(x_1, \dots, x_n, x\) are linearly dependent.

Proof:

“\(\Rightarrow\)”: If \(x=0_{V}\) then \(1 \cdot x = 0_{V}\) is a non-trivial linear combination of \(x\).
“\(\Leftarrow\)”: Let \(x \neq 0_{V}\) and let \(a \in F\) such that \(ax = 0_{V}\). Then \(a=0\) by 2.6(c).
Let \(x_1, \dots, x_n \in V\) be linearly independent and let \(y_1, \dots, y_m\) be a subset of \(x_1, \dots, x_n\) for some \(m \leq n\).
Proceed by contradiction: Suppose that \(\exists b_1, \dots, b_m \in F\), not all zero, such that \(b_1y_1 + \dots + b_my_m = 0_{V}\).
Extending the list \(b_1, \dots, b_m\) by zeroes we get \(a_1, \dots, a_n \in F\), not all zero, such that \(a_1x_1 + \dots + a_nx_n = 0_{V}\).
So \(x_1, \dots, x_n\) are linearly dependent, a contradiction.
If \(x_{i} = 0_{V}\) then \(x_1, \dots, x_n\) are linearly dependent by (a) and (b).
If \(x_{i} = x_{j}\) for some \(i \neq j\), then \(x_{i}, x_{j}\) are linearly dependent, because \(1x_{i} + (-1)x_{j} = 0_{V}\). Now apply (b).
\(\exists a_1, \dots, a_n \in F\), not all zero, such that \(a_1x_1 + \dots + a_nx_n = 0_{V}\).
After reordering we may assume \(a_n \neq 0\).
\(\implies x_n = -a_n^{-1} (a_1x_1 + \dots + a_nx_n)\) \(= (-a_n^{-1} a_1)x_1 + \dots + (-a_n^{-1} a_{n-1})x_{n-1}\)
\(\implies\) \(x_n\) is a linear combination of \(x_1, \dots, x_{n-1}\).
Let \(x\in\mathrm{Span}(x_1,\dots,x_n)\).
\(\implies\) \(\exists a_1, \dots, a_n \in F\), such that \(x = a_1x_1 + \dots + a_nx_n\).
\(\implies 0_{V} = a_1x_1 + \dots + a_nx_n + (-1)x\)
\(\implies\) We have a a non-trivial linear combination of \(x_1, \dots, x_n,x\) which equals \(0_V\).
(Because \(-1\not=0\) in any field.) \(\square\)

3.3 Bases

Definition 3.7 Let \(V\) be a vector space over a field \(F\). Let \(x_1, \dots, x_n \in V\). We say that \(x_1, \dots, x_n\) form a basis of \(V\) if \(x_1, \dots, x_n\) both span \(V\) and are linearly independent. (Compare Definition 6.40 of L.A.I.)

Example 3.8

Let \(F\) be a field. The vectors \(\underline{e}_1\) \(:= (1,0, \dots, 0)\); … ; \(\underline{e}_n\) \(:= (0, \dots, 0,1)\) form a basis \(F^n\), called the standard basis of \(F^n\) (as in Linear Algebra I (Ex 6.41(a)).
The polynomials \(1,t, \dots, t^n\) form a basis of \(\mathbb{P}_n\). (see 2.10(d)(iv), 3.2(c)).
\(1,i\) form a basis of the vector space \(\mathbb{C}\) over \(\mathbb{R}\) (cf 2.5(b)).
Determine a basis of the nullspace \(N(A) \subseteq \mathbb{R}^4\) of the matrix \[ A := \begin{pmatrix} 1 & -1 & 3 & 2 \\ 2 & -1 & 6 & 7 \\ 3 & -2 & 9 & 9 \\ -2 & 0 & -6 & -10 \end{pmatrix} \in M_{4 \times 4}(\mathbb{R}).\]
Solution: We perform Gaussian elimination until the reduced lower echelon form (row operations): \[\begin{align*} A = \begin{pmatrix} 1 & -1 & 3 & 2 \\ 2 & -1 & 6 & 7 \\ 3 & -2 & 9 & 9 \\ -2 & 0 & -6 & -10 \end{pmatrix} &\xrightarrow[\substack{R3 \mapsto R3 - 3R1 \\ R4 \mapsto R4 + 2R1}]{R2 \mapsto R2 - 2R1} \begin{pmatrix} 1 & -1 & 3 & 2 \\ 0 & 1 & 0 & 3 \\ 0 & 1 & 0 & 3 \\ 0 & -2 & 0 & -6 \end{pmatrix} \\ &\xrightarrow[\substack{R3 \mapsto R3 - R2 \\ R4 \mapsto R4 + 2R2}]{R1 \mapsto R1 + R2} \begin{pmatrix} 1 & 0 & 3 & 5 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} =: \widetilde{A} \end{align*}\] Because performing row operations does not change the nullspace of a matrix (see Note below), we have: \[\begin{align*} N(A) &= N(\widetilde{A}) = \{ \underline{x} \in \mathbb{R}^4 : \widetilde{A} \underline{x} = \underline{0} \} \\ & = \left\{ \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} \in \mathbb{R}^4 : x_1 = -3x_3 - 5x_4 ; \ x_2 = -3x_4 \right\} \\ & = \left\{ \begin{pmatrix} -3x_3 - 5x_4 \\ -3x_4 \\ x_3 \\ x_4 \end{pmatrix} : x_3, x_4 \in \mathbb{R} \right\} \\ & = \left\{ x_3 \begin{pmatrix} -3 \\ 0 \\ 1 \\ 0 \end{pmatrix} + x_4 \begin{pmatrix} -5 \\ -3 \\ 0 \\ 1 \end{pmatrix} : x_3, x_4 \in \mathbb{R} \right\} \\ & = \mathrm{Span}\left( \begin{pmatrix} -3 \\ 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} -5 \\ -3 \\ 0 \\ 1 \end{pmatrix} \right). \end{align*}\] (Denote \(\underline{u}_1=(-3,0,1,0)^T\), \(\underline{u}_2=(-5,-3,0,1)^T\)).
\(\bullet\) \(\underline{u}_1\) and \(\underline{u}_2\) are also linearly independent (because they are not multiples of each other).
\(\implies\) \(\underline{u}_1\) and \(\underline{u}_2\) form a basis of \(N(A)\).

Let \(A \in M_{n \times n}(\mathbb{R})\). Then:
\(A\) invertible \(\iff\) The columns of \(A\) form a basis of \(\mathbb{R}^n\) (for a proof see Theorem 5.6).

Note: Row operations do not change the nullspace of a matrix (say \(A\)). This is because vectors \(\underline{x}\) are in \(N(A)\) exactly if they are solutions to \(A\underline{x}=\underline{0}\), i.e. solutions to the homogeneous system of linear equations described by the matrix \(A\). Row operations on \(A\) correspond to the “allowed” operations on the linear system of equations.

Proposition 3.9 Let \(V\) be a vector space over a field \(F\). Let \(x_1, \dots, x_n \in V\). The following statements are equivalent:

\(x_1, \dots, x_n\) form a basis of \(V\).
\(x_1, \dots, x_n\) form a minimal spanning set of \(V\) (i.e. \(x_1, \dots, x_n\) span \(V\) and after removing any vector from \(x_1, \dots, x_n\) the remaining ones don’t span \(V\) anymore). (Compare Def 6.23 of L.A.I.)
\(x_1, \dots, x_n\) form a maximal linearly independent subset of \(V\) (i.e. \(x_1, \dots, x_n\) are linearly independent and for any \(x \in V\) the \(n+1\) vectors \(x_1, \dots, x_n,x\) are linearly dependent).
Every vector \(x \in V\) can be written in the form \[ x = a_1x_1 + \dots + a_nx_n \] with coefficients \(a_1, \dots, a_n \in F\) uniquely determined by x.

Proof: “(a) \(\implies\) (b)”: 1/Spanning: \(x_1, \dots, x_n\) span \(V\) by definition of a basis.
2/Minimality: Suppose that the spanning set \(x_1, \dots, x_n\) is not minimal.
\(\implies\) After reordering we may assume that \(x_1, \dots, x_{n-1}\) span \(V\).
\(\implies x_n \in V = \mathrm{Span}(x_1, \dots, x_{n-1})\).
\(\implies x_1, \dots, x_{n-1},x_n\) are linearly dependent (by 3.6(e)). Contradiction.

(b) \(\implies\) (c): 1/Independence: Suppose that \(x_1, \dots, x_n\) are linearly dependent.
\(\implies\) After reordering we have \(x_n \in \mathrm{Span}(x_1, \dots, x_{n-1})\) (by 3.6(d))
\(\implies\) \(V = \mathrm{Span}(x_1, \dots, x_n) = \mathrm{Span}(x_1, \dots, x_{n-1})\) (by 3.3(a))
This contradicts the minimality assumed in (b).
2/Maximality: Let \(x \in V = \mathrm{Span}(x_1, \dots, x_n)\)
\(\implies x_1, \dots, x_n, x\) are linearly dependent (by 3.6(c)).

(c) \(\implies\) (d): 1/Existence: Let \(x \in V\).
\(\implies \exists b_1, \dots, b_n, b \in F\), not all zero, with \(b_1x_1 + \dots + b_nx_n + bx = 0\).
(because \(x_1, \dots, x_n,x\) are linearly dependent)
\(\implies b \neq 0\) (because \(x_1, \dots, x_n\) are linearly independent)
\(\implies x = a_1x_1 + \dots + a_nx_n\), where \(a_{i} := -b^{-1}b_{i}\).
2/Uniqueness: Suppose \(x = a_1x_1 + \dots + a_nx_n = b_1x_1 + \dots + b_nx_n\) for some \(a_1,\dots,a_n,b_1,\dots,b_n\in F\).
\(\implies 0_{V} = x-x = (a_1 - b_1)x_1 + \dots + (a_n - b_n)x_n\)
\(\implies a_1 = b_1, \dots, a_n=b_n\). (because \(x_1, \dots, x_n\) are linearly independent)

(d) \(\implies\) (a): 1/Spanning: Directly from (d).
2/Independence: Let \(a_1, \dots, a_n \in F\) such that \(a_1x_1 + \dots a_nx_n = 0_{V}\).
\(\implies a_1 = \dots = a_n = 0\). (from uniqueness, because also \(0x_1 + \dots + 0x_n = 0_{V}\)) \(\square\)

Corollary 3.10 Let \(V\) be a vector space over a field \(F\). Suppose \(V = \mathrm{Span}(x_1, \dots, x_n)\) for some \(x_1, \dots x_n \in V\). Then a subset of \(x_1, \dots, x_n\) forms a basis of \(V\). In particular \(V\) has a basis.

Proof: By successively removing vectors from \(x_1, \dots, x_n\) we arrive at a minimal spanning set \(y_1, \dots, y_m\) for some \(m \leq n\). Then \(y_1, \dots, y_m\) form a basis of \(V\) (by 3.9 (b) \(\implies\) (a)). \(\square\)

3.4 Dimension

Theorem 3.11 (This Theorem allows us to define the dimension of a vector space.)
Let \(V\) be a vector space over a field \(F\). Suppose \(x_1, \dots, x_n\) and \(y_1, \dots, y_m\) both form a basis of \(V\). Then \(m = n\). (Compare Thm 6.44 from L.A.I.)

Definition 3.12 Let \(V\) be a vector space over a field \(F\). If the vectors \(x_1, \dots, x_n \in V\) form a basis of \(V\), we say that \(V\) is of finite dimension, and call \(n\) the dimension of \(V\). We write \(\mathrm{dim}_{F}(V)\) or just \(\mathrm{dim}(V)\) for \(n\). Note that \(n\) does not depend on the chosen basis \(x_1, \dots, x_n\) by 3.11.

Example 3.13

\(\mathrm{dim}_{F}(F^n)=n\) (by Example 3.8(a)).
\(\mathrm{dim}_{\mathbb{R}}(\mathbb{P}_n) = n + 1\) (by Example 3.8(b)).
\(\mathrm{dim}_{\mathbb{R}}(\mathbb{C}) = 2\) (by Example 3.8(c)).
\(\mathrm{dim}_{\mathbb{C}}(\mathbb{C}^3) = 3\), \(\mathrm{dim}_{\mathbb{R}}(\mathbb{C}^3) = 6\). In general \(\mathrm{dim}_{\mathbb{C}}(\mathbb{C}^n) = n\), \(\mathrm{dim}_{\mathbb{R}}(\mathbb{C}^n) = 2n\).
\(\mathbb{R}\) as a vector space over \(\mathbb{Q}\) is not finite dimensional (see 2.5(b)).
\(\mathrm{dim}_{\mathbb{R}}(M_{n \times m}(\mathbb{R})) = nm\).
\(\mathrm{dim}_{\mathbb{Q}}(\mathbb{Q}(\sqrt{-3})) = 2\) (see Coursework 2).
About \(\mathrm{dim}_F(\mathrm{Span}(x_1,\dots,x_n))\). We determine its dimension by finding a basis, i.e. subset of \(x_1,\dots,x_n\) which still spans \(\mathrm{Span}(x_1,\dots,x_n)\), and it is linearly independent. For example:
Let \(x_1 \in V, \ x_1 \neq 0 \implies \mathrm{dim}_{F}(\mathrm{Span}(x_1)) = 1\).
Let \(x_2\) be another vector in \(V\).
\(\implies \mathrm{dim}_{F}(\mathrm{Span}(x_1,x_2)) = \begin{cases} 2 & \text{if } x_1,x_2 \text{ are linearly independent} \\ 1 & \text{if } x_1,x_2 \text{ are linearly dependent} \end{cases}\)

Proof of Theorem 3.11: It follows from the following Proposition. \(\square\)

Proposition 3.14 Let \(V\) be a vector space over a field \(F\). Let \(x_1, \dots, x_n \in V\) and \(y_1, \dots, y_m \in V\).
Suppose \(x_1, \dots, x_n\) span \(V\). If \(y_1, \dots, y_m\) are linearly independent then \(m \leq n\).

Proof: We will show the contrapositive:

If \(m > n\) then there exist \(c_1, \dots, c_m \in F\), not all zero, such that \(c_1y_1 + \dots + c_my_m = 0\).

For every \(i \in \{1, \dots, m\}\) we can write \(y_{i} = a_{i1}x_1+ \dots +a_{in}x_n\) for some \(a_{i1}, \dots a_{in} \in F\).
(because \(x_1, \dots, x_n\) span \(V\))
\(\implies\) For all \(c_1, \dots, c_m \in F\) we have: (using the axioms of a vector space) \[\begin{align*} c_1y_1 + \dots + c_my_m &= c_1(a_{11}x_1 + \dots + a_{1n}x_n) + \dots + c_{m}(a_{m1}x_1 + \dots + a_{mn}x_n) \\ &= (a_{11}c_1 + \dots + a_{m1}c_m)x_1 + \dots + (a_{1n}c_1 + \dots + a_{mn}c_m)x_n \end{align*}\] \(\implies\) It suffices to show that the system of linear equations \[\begin{align*} a_{11}c_1 + a_{21}c_2 + \dots + a_{m1}c_m &= 0\\ &\vdots\\ a_{1n}c_1 + a_{2n}c_2 + \dots + a_{mn}c_m &= 0 \end{align*}\] has a solution \((c_1, \dots, c_m) \in F^m\) different from \((0, \dots, 0)\).
This follows from Gaussian elimination (as seen in Linear Algebra I for \(F=\mathbb{R}\) (Thm 3.15(b) from L.A.I.)): since \(m>n\), we have more unknowns than equations. \(\square\)

Corollary 3.15 (Two-out-of-three basis criterion.)
Let \(V\) be a vector space over a field \(F\). Let \(x_1, \dots x_n \in V\). Suppose two of the following three statements hold. Then \(x_1, \dots, x_n\) form a basis:

\(x_1, \dots, x_n\) are linearly independent.
\(x_1, \dots, x_n\) span \(V\).
\(n = \mathrm{dim}_{F}(V)\).

Proof: If (a) and (b) hold, then \(x_1, \dots, x_n\) form a basis by definition.
Suppose (a) and (c) hold. If \(x_1, \dots, x_n\) would not form a basis we could find an \(x \in V\) such that \(x_1, \dots, x_n,x\) are still linearly independent (by 3.9 (a) \(\iff\) (c)).
\(\implies\) \(n+1 \leq n\) by Proposition 3.14. Contradiction.
Suppose (b) and (c) hold. After reordering we may assume that \(x_1, \dots, x_m\) form a minimal spanning set, for some \(m \leq n\).
\(\implies x_1, \dots, x_m\) form a basis (by 3.9 (a) \(\iff\) (b)).
\(\implies m=n\) (by 3.11); i.e. \(x_1, \dots, x_n\) form a basis. \(\square\)

Example 3.16

The vectors \(\underline{x}_1:= \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix}\), \(\underline{x}_2:= \begin{pmatrix} -2 \\ 1 \\ 0 \end{pmatrix}\), \(\underline{x}_3:= \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}\) form a basis of the vector space \(\mathbb{Q}^3\) over \(\mathbb{Q}\), of the vector space \(\mathbb{R}^3\) over \(\mathbb{R}\) and of the vector space \(\mathbb{C}^3\) over \(\mathbb{C}\).

Proof: We first show that \(\underline{x}_1, \underline{x}_2, \underline{x}_3\) are linearly independent over \(\mathbb{C}\):
Let \(c_1, c_2, c_3 \in \mathbb{C}\) such that \(c_1 \underline{x}_1 + c_2 \underline{x}_2 + c_3 \underline{x}_3 =0\). \[ \implies \quad \begin{pmatrix} 1 & -2 & 1 \\ 2 & 1 & 0 \\ 3 & 0 & 1 \end{pmatrix} \begin{pmatrix} c_1 \\ c_2 \\ c_3 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}. \] Gaussian elimination yields: \[ A:= \begin{pmatrix} 1 & -2 & 1 \\ 2 & 1 & 0 \\ 3 & 0 & 1 \end{pmatrix} \xrightarrow[R3 \mapsto R3 - 3R1]{R2 \mapsto R2 - 2R1} \begin{pmatrix} 1 & -2 & 1 \\ 0 & 5 & -2 \\ 0 & 6 & -2 \end{pmatrix} \xrightarrow{R3 \mapsto R3 - \frac{6}5 R2} \begin{pmatrix} 1 & -2 & 1 \\ 0 & 5 & -2 \\ 0 & 0 & 2/5 \end{pmatrix} \] \(\implies\) \(\underline{c}= (c_1,c_2,c_3) = (0,0,0)\) is the only solution of \(A \underline{c} = 0\).
\(\implies\) \(\underline{x}_1, \underline{x}_2, \underline{x}_3\) are linearly independent over \(\mathbb{C}\) and then also over \(\mathbb{R}\) and \(\mathbb{Q}\).
\(\implies\) \(\underline{x}_1, \underline{x}_2, \underline{x}_3\) form a basis of \(\mathbb{C}^3\), \(\mathbb{R}^3\) and \(\mathbb{Q}^3\) over the respective fields.
(by 3.15 since \(3 = \mathrm{dim}_{\mathbb{C}}(\mathbb{C}^3) = \mathrm{dim}_{\mathbb{R}}(\mathbb{R}^3) = \mathrm{dim}_{\mathbb{Q}}(\mathbb{Q}^3)\)) \(\square\)
We view \(\mathbb{C}\) as a vector space over \(\mathbb{C}\), \(\mathbb{R}\) and \(\mathbb{Q}\) (see 2.5(b)).
Let \(x_1:=1, x_2:=2, x_3:=\sqrt2, x_4:=i, x_5:=i\sqrt3 \in \mathbb{C}\).
Determine \(\mathrm{dim}_{F}(\mathrm{Span}_{F}(x_1,x_2,x_3,x_4,x_5))\) for \(F = \mathbb{C}\), \(\mathbb{R}\) and \(\mathbb{Q}\).

Solution: For \(F=\mathbb{C}\):
We have \(\mathbb{C} = \mathrm{Span}_{\mathbb{C}}(x_1) \subseteq \mathrm{Span}_{\mathbb{C}}(x_1, \dots, x_5) \subseteq \mathbb{C}\).
\(\implies\) \(\mathrm{dim}_{\mathbb{C}}(\mathrm{Span}_{\mathbb{C}}(x_1, \dots, x_5))\) \(= \mathrm{dim}_{\mathbb{C}}(\mathbb{C}) = 1\).

For \(F=\mathbb{R}\):
\(x_1\) and \(x_4\) span \(\mathbb{C}\) as a vector space over \(\mathbb{R}\).
\(\implies\) \(\mathrm{Span}_{\mathbb{R}}(x_1, \dots, x_5) = \mathbb{C}\).
\(\implies\) \(\mathrm{dim}_{\mathbb{R}}(\mathrm{Span}(x_1, \dots, x_5))\) \(= \mathrm{dim}_{\mathbb{R}}(\mathbb{C}) = 2\).

For \(F=\mathbb{Q}\): Observations:
\(x_1,x_2\) are LD over \(\mathbb{Q}\) \(\implies\) \(\mathrm{Span}_\mathbb{Q}(x_1,\dots,x_5) = \mathrm{Span}_\mathbb{Q}(x_1,x_3,x_4,x_5)\).
Also \(x_1,x_3\) are LI over \(\mathbb{Q}\); \(x_1,x_4\) are LI over \(\mathbb{R}\).
\(\leadsto\) Let us try to prove that \(x_1,x_3,x_4,x_5\) are linearly independent over \(\mathbb{Q}\).
Let \(a_1,a_3,a_4,a_5\in\mathbb{Q}\) be such that \(a_1x_1+a_3x_3+a_4x_4+a_5x_5=0\).
\(\implies\) \((a_1 + a_3\sqrt2) + i(a_4 + a_5\sqrt3) = 0\).
\(\implies\) \(a_1+a_3\sqrt{2}=0\) and \(a_4+a_5\sqrt3=0\) (because \(1\) and \(i\) are linearly independent over \(\mathbb{Q}\))
\(\implies\) \(a_1=a_3=0\) (If \(a_3\not=0\) \(\implies\) \(\sqrt{2}=-\frac{a_1}{a_3}\in\mathbb{Q}\). Contradiction.)
and \(a_4=a_5=0\) (similarly).
\(\implies\) \(x_1, x_3,x_4,x_5\) are linearly independent, so form a basis of \(\mathrm{Span}_\mathbb{Q}(x_1,x_3,x_4,x_5)\).
\(\implies\) \(\mathrm{dim}_\mathbb{Q}(\mathrm{Span}_\mathbb{Q}(x_1,x_2,x_3,x_4,x_5)) =\) \(\mathrm{dim}_\mathbb{Q}(\mathrm{Span}_\mathbb{Q}(x_1,x_3,x_4,x_5)) = 4\).
Let \(V\) be a vector space of finite dimension over a field \(F\) and let \(W\) be a subspace of \(V\). Then \(\mathrm{dim}_{F}(W) \leq \dim_F(V)\).

Proof: If vectors are L.I. in \(W\), they are also L.I. in \(V\). (by def. of L.I.)
\(\implies\) Any L.I. subset of \(W\) has at most \(\mathrm{dim}(V)\) elements (use 3.14 and 3.9(a)\(\iff\)(c))
\(\implies\) \(\mathrm{dim}(W)\leq\mathrm{dim}(V)\) (by 3.9(a)\(\iff\)(c))