Study Guides / Linear Algebra / Exercise session 6
EXERCISE SESSION 6 · ETH ZURICH · HS19 · linalg

Vector Spaces, Basis and Linear Independence

Vector spaces, subspace, closed, linear combination, span, generating set, orthogonal complement, linear (in)dependence, basis

SB
Steven Battilana Quant · ex-ETH

Vector Spaces

Definition

A set E\mathbb{E} together with two operations

+:E×E→E,(x,y)↦x+y(addition)⋅:E×E→E,(x,y)↦x⋅y(multiplication)\begin{aligned} +:& \quad \mathbb{E} \times \mathbb{E} \to \mathbb{E}, \quad (x,y) \mapsto x + y \quad\quad &\text{(addition)}\\ \cdot:& \quad \mathbb{E} \times \mathbb{E} \to \mathbb{E}, \quad (x,y) \mapsto x \cdot y \quad\quad &\text{(multiplication)} \end{aligned}

is called a field if the following holds ∀x,y,z∈E\forall x,y,z \in \mathbb{E}:

K1 E\mathbb{E} together with the addition ++ is an abelian group.
(Its neutral element is denoted by 00, the inverse element of a∈Ea \in \mathbb{E} by −a-a; cf. Discrete Mathematics, 5. Algebra, Definitions 5.7 and 5.8: ⟨E;+⟩\langle \mathbb{E}; + \rangle is an abelian group):

  • (i) (associativity) (x+y)+z=x+(y+z)\quad (x+y)+z = x+(y+z)
  • (ii) (neutral element) ∃e∈E:x+e=e+x=x\quad \exists e \in \mathbb{E}: \quad x + e = e + x = x
  • (iii) (inverse element) ∃x′∈E:x+x′=x′+x=e\quad \exists x' \in \mathbb{E}: \quad x+x'=x'+x= e
  • (iv) (abelian ⇔\Leftrightarrow commutativity) x+y=y+x\quad x+y = y+x

K2 Writing E∗:=E∖{0}\mathbb{E}^* := \mathbb{E} \setminus \{0\}, for x,y∈E∗x,y \in \mathbb{E}^* we also have x⋅y∈E∗x\cdot y \in \mathbb{E}^*, and E∗\mathbb{E}^* together with the multiplication obtained this way is an abelian group.
(Its neutral element is denoted by 11, the inverse element of x∈E∗x \in \mathbb{E}^* by x−1x^{-1} or 1/x1/x. One writes y/x=x−1y=yx−1y/x =x^{-1}y=yx^{-1}.
Cf. Discrete Mathematics, 5. Algebra, Definitions 5.7 and 5.8: ⟨E;⋅⟩\langle \mathbb{E}; \cdot \rangle is an abelian group)

(cf. Discrete Mathematics, 5. Algebra: Definition 5.26 and Theorem 5.23)

Remark

Most of the time we will work with the fields R\mathbb{R} or C\mathbb{C}. Another field that we computer scientists know well is the smallest finite field Z2\mathbb{Z}_2, which contains only {0,1}\{0,1\}.

Definition

A vector space VV over E\mathbb{E} (or E\mathbb{E}-vector space; VS) is a non-empty set VV together with two operations:

+:V×V→V,(x,y)↦x+y(addition)⋅:E×V→V,(α,x)↦αx(scalar multiplication)\begin{aligned} +:& \quad V \times V \to V, \quad (x,y) \mapsto x + y \quad\quad &\text{(addition)}\\ \cdot:& \quad \mathbb{E} \times V \to V, \quad (\alpha,x) \mapsto \alpha x \quad\quad &\text{(scalar multiplication)} \end{aligned}

such that ∀x,y,z∈V\forall x,y,z \in V and ∀α,β∈E\forall \alpha, \beta \in \mathbb{E}:

V1 VV together with the addition is an abelian (commutative) group (the neutral element is called the zero vector and is denoted by 0\boldsymbol{0}, and the negative is denoted by −x-x; cf. Discrete Mathematics, 5. Algebra: ⟨V;+⟩\langle V; + \rangle is an abelian group):

  • (i) (associativity) (x+y)+z=x+(y+z)\quad (x+y)+z = x+(y+z)
  • (ii) (neutral element) ∃e∈V:x+e=e+x=x\quad \exists e \in V: \quad x + e = e + x = x
  • (iii) (inverse element) ∃x′∈V:x+x′=x′+x=e\quad \exists x' \in V: \quad x+x'=x'+x= e
  • (iv) (abelian ⇔\Leftrightarrow commutativity) x+y=y+x\quad x+y = y+x

V2 Multiplication by scalars must be compatible with the other operations as follows:

  • (i) (distributivity I) (α+β)x=αx+βx\quad (\alpha + \beta) x = \alpha x + \beta x
  • (ii) (distributivity II) α(x+y)=αx+αy\quad \alpha (x+y) = \alpha x + \alpha y
  • (iii) (associativity) (αβ)x=α(βx)\quad (\alpha \beta) x = \alpha (\beta x)
  • (iv) (compatibility with 11) 1x=x\quad 1x = x
Example 1
  1. nn-dimensional vectors form a vector space over E\mathbb{E}.
  2. m×nm \times n matrices form a vector space over E\mathbb{E}.
  3. Pn:={\mathcal{P}_n := \{polynomials in one variable with coefficients in E\mathbb{E} of degree at most n}n \} form a vector space over E\mathbb{E}.
Definition

Let VV be a vector space, U⊆V, U≠{}U \subseteq V, \, U \neq \{\}. UU is called a subspace (vector subspace, linear subspace) if it is closed under addition and scalar multiplication, i.e. if ∀x,y∈U\forall x,y \in U and ∀α∈E\forall \alpha \in \mathbb{E}:

U1 x+y∈Ux + y \in U

U2 αx∈U\alpha x \in U.

Remark

Every subspace UU contains the zero vector, i.e.

U0 0∈U\boldsymbol{0} \in U.

Satz

Every subspace is a vector space.

Example 2

To show: W={(x1x2x3)∈R3∣x1+x2+x3=0}W = \left\{ \left. \begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix} \in \mathbb{R}^3 \right| x_1+x_2+x_3 = 0 \right\} is a vector space.

Remark
We have two options:

  1. Check whether V1 and V2 of the vector space definition are satisfied
  2. Use the theorem above and only show U1 and U2
Show solutionHide solution

Proof:
We carry out the proof using the second option. By the theorem it therefore suffices to show that WW is a subspace.
Let x=(x1x2x3),y=(y1y2y3)∈W,λ∈Ex = \begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix}, y = \begin{pmatrix} y_1\\ y_2\\ y_3 \end{pmatrix} \in W, \lambda \in \mathbb{E}

U0 (000)∈W\begin{pmatrix} 0\\ 0\\ 0 \end{pmatrix} \in W, since 0+0+0=00+0+0=0, (U0 follows trivially)

U1 x+y=(x1+y1x2+y2x3+y3)∈Wx+y = \begin{pmatrix} x_1+y_1\\ x_2+y_2\\ x_3+y_3 \end{pmatrix} \in W,
since (x1+y1)+(x2+y2)+(x3+y3)=(x1+x2+x3)⏟x1+x2+x3=0+(y1+y2+y3)⏟y1+y2+y3=0=0(x_1+y_1)+(x_2+y_2)+(x_3+y_3) = \underbrace{(x_1+x_2+x_3)}_{x_1+x_2+x_3=0} + \underbrace{(y_1+y_2+y_3)}_{y_1+y_2+y_3 = 0} = 0

U2 λx=(λx1λx2λx3)∈W\lambda x = \begin{pmatrix} \lambda x_1\\ \lambda x_2\\ \lambda x_3 \end{pmatrix} \in W, since λx1+λx2+λx3=λ(x1+x2+x3)⏟x1+x2+x3=0=0\lambda x_1 + \lambda x_2 + \lambda x_3 = \lambda \underbrace{(x_1+x_2+x_3)}_{x_1+x_2+x_3=0} = 0

Instead of showing U1 and U2 separately, you can also show the "all in one" variant:

U1/U2 x−λy=(x1−λy1x2−λy2x3−λy3)∈Wx-\lambda y = \begin{pmatrix} x_1 - \lambda y_1\\ x_2 - \lambda y_2\\ x_3 - \lambda y_3 \end{pmatrix} \in W,
since (x1−λy1)+(x2−λy2)+(x3−λy3)=(x1+x2+x3)⏟x1+x2+x3=0−λ(y1+y2+y3)⏟y1+y2+y3=0=0□(x_1 - \lambda y_1) + (x_2 - \lambda y_2) + (x_3 - \lambda y_3) = \underbrace{(x_1+x_2+x_3)}_{x_1+x_2+x_3=0} - \lambda \underbrace{(y_1+y_2+y_3)}_{y_1+y_2+y_3 = 0} = 0 \quad\quad\quad\quad \square

Bases, Dimensions and Linear (In)dependence

Remark

For this section we assume the following. Let VV be a vector space over a field E\mathbb{E} and (vi)i∈I(v_i)_{i \in I} a family (set) of vectors vi∈Vv_i \in V. If I={1,...,r}I = \{1, ..., r\}, you have vectors v1,...,vrv_1, ..., v_r.

Definition

Let v1,...,vr∈Vv_1, ..., v_r \in V be chosen vectors. A vector of the form

x:=λ1v1+...+λrvr=∑k=1rλkvkx := \lambda_1 v_1+ ...+ \lambda_r v_r = \sum_{k=1}^r \lambda_k v_k

with λ1,...,λr∈E\lambda_1, ..., \lambda_r \in \mathbb{E} is called a linear combination of v1,...,vrv_1, ..., v_r.

Definition

For general II one defines

spanE(vi)i∈I\text{span}_\mathbb{E} (v_i)_{i \in I}

as the set of all v∈Vv \in V that can be written as a linear combination of a finite subfamily (subset) of (vi)i∈I(v_i)_{i \in I} (depending on vv).
spanE(vi)i∈I\text{span}_\mathbb{E} (v_i)_{i \in I} is called the space spanned (or generated) by the family (set). For a finite family (v1,...,vr)(v_1, ..., v_r) one often uses the more suggestive notation:

spanE(v1,...,vr):=Ev1+...+Evn={v∈V∣∃λ1,...,λr∈E with v=λ1v1+...+λrvr}.\begin{aligned} \text{span}_\mathbb{E}(v_1, ..., v_r) :&= \mathbb{E} v_1 + ... + \mathbb{E} v_n\\ &= \{ v \in V \quad | \quad \exists \lambda_1, ..., \lambda_r \in \mathbb{E} \text{ with } v = \lambda_1 v_1+ ...+ \lambda_r v_r \}. \end{aligned}
Remark

The following notations are equivalent: spanE(v1,...,vr)⇔spanE{v1,...,vr}⇔⟨v1,...,vr⟩\text{span}_\mathbb{E}(v_1, ..., v_r) \Leftrightarrow \text{span}_\mathbb{E}\{v_1, ..., v_r\} \Leftrightarrow \langle v_1, ..., v_r \rangle.

Definition

A family B=(vi)i∈I\mathcal{B} = (v_i)_{i \in I} in a vector space VV is called a spanning set of VV if

V=span(vi)i∈I,V = \text{span}(v_i)_{i \in I},

i.e. if every v∈Vv \in V is a linear combination of finitely many viv_i.

Remark

If it is clear which field is meant, one writes just span instead of spanE\text{span}_\mathbb{E}.

Remark

Let V be an E\mathbb{E}-vector space and (vi)i∈I(v_i)_{i \in I} a family (set) of elements of V with I={1,...,r}I = \{1, ..., r\}. Then:

  1. span(v1,...,vr)\text{span}(v_1, ..., v_r) is a subspace
  2. If W⊂VW \subset V is a subspace and vi∈Wv_i \in W for all i∈{1,...,r}i \in \{1, ..., r\}, then span(v1,...,vr)⊂W\text{span}(v_1, ..., v_r) \subset W.
Example 3
  • span(1,x,x2,x3)=P3\text{span}(1, x, x^2, x^3) = \mathcal{P}_3
  • span(x3+x2,x2−1,x,x−1,1000)=P3\text{span}(x^3+x^2, x^2-1, x, x-1, 1000) = \mathcal{P}_3

⇒\Rightarrow a spanning set is not unique.

Definition

v1,...,vr∈Vv_1, ..., v_r \in V are called linearly independent if:

∑k=1rλkvk=λ1v1+...+λrvr=0⇒λ1=...=λr=0\sum_{k=1}^r \lambda_k v_k = \lambda_1 v_1 + ... + \lambda_r v_r = 0 \quad \Rightarrow \quad \lambda_1 = ... = \lambda_r = 0

and otherwise they are called linearly dependent.

Remark

v1,...,vr∈Vv_1, ..., v_r \in V are linearly independent if and only if no viv_i can be written as a linear combination of the other vjv_j with j≠ij\neq i. (E.g. v1v_1 cannot be written as a linear combination of v2,...,vrv_2, ..., v_r).

Example 4
  • (123)\begin{pmatrix} 1\\ 2\\ 3 \end{pmatrix} is linearly dependent on (246)\begin{pmatrix} 2\\ 4\\ 6 \end{pmatrix}, because 2⋅(123)=(246)\quad 2 \cdot \begin{pmatrix} 1\\ 2\\ 3 \end{pmatrix} = \begin{pmatrix} 2\\ 4\\ 6 \end{pmatrix}.
  • (123)\begin{pmatrix} 1\\ 2\\ 3 \end{pmatrix} is linearly independent of (023)\begin{pmatrix} 0\\ 2\\ 3 \end{pmatrix}.
    With componentwise multiplication you never get 00 in the first coordinate if you want to keep 22 and 33.
Definition

Let B=(bi)i∈I⊆V\mathcal{B} = (b_i)_{i \in I} \subseteq V. B\mathcal{B} is called a basis of VV if

V=span(B)(V is spanned by B)B=(bi)i∈I (all bi are mutually linearly independent).\begin{aligned} V &= \text{span}(\mathcal{B}) \quad (V \text{ is spanned by } \mathcal{B})\\ \mathcal{B} &= (b_i)_{i \in I} \quad \text{ (all } b_i \text{ are mutually linearly independent).} \end{aligned}
Satz

B\mathcal{B} is a minimal spanning set, i.e.

span(B)=V, but span(B∖{bi})≠V,∀bi∈B.\text{span}(\mathcal{B}) = V, \text{ but span}(\mathcal{B} \setminus \{b_i\}) \neq V, \quad \forall b_i \in \mathcal{B}.
Satz

B\mathcal{B} is a maximal linearly independent subset of VV, i.e. (bi)i∈I(b_i)_{i \in I} are linearly independent but (bi)i∈I∪{v}(b_i)_{i \in I} \cup \{v\} are no longer linearly independent, ∀v∈V∖B\forall v \in V \setminus \mathcal{B}.

Remark

If B1\mathcal{B}_1 and B2\mathcal{B}_2 are bases of VV, then ∣B1∣=∣B2∣|\mathcal{B}_1| = |\mathcal{B}_2|. Every vector space has a basis.

Definition

Let B\mathcal{B} be a basis of VV. Then ∣B∣=dim(V)|\mathcal{B}| = \text{dim}(V) (=#(= \# basis vectors) is the dimension of VV, where ∣⋅∣=^| \cdot | \mathrel{\hat{=}} the cardinality of a set.

Remark

If dim(V)=n\text{dim}(V) = n, then in general:

  • If k<nk<n, v1,...,vk∈Vv_1, ..., v_k \in V are not spanning
  • If k>nk>n, v1,...,vk∈Vv_1, ..., v_k \in V are spanning and linearly dependent
Satz basis selection theorem

From every finite spanning set of a vector space you can select a basis. In particular, every finitely generated vector space has a finite basis.

Satz basis extension theorem

In a finitely generated vector space VV, let linearly independent vectors w1,...,wnw_1, ..., w_n be given. Then you can find wn+1,...,wrw_{n+1}, ..., w_r such that

B={w1,...,wn,wn+1,...,wr}\mathcal{B} = \{w_1, ..., w_n, w_{n+1}, ..., w_r\}

is a basis of VV.

Example 5
  • dim(Rn)=n=dim(Cn)\text{dim}(\mathbb{R}^n) = n = \text{dim}(\mathbb{C}^n)
  • dim(Pn)=n+1(B(Pn)={1,x,x2,...,xn⏟n+1 basis vectors})\text{dim}(\mathcal{P}_n) = n+1 \quad (\mathcal{B}(\mathcal{P}_n) = \{\underbrace{1,x,x^2, ..., x^n}_{n+1 \text{ basis vectors}}\})
  • dimR(C)=2\text{dim}_\mathbb{R}(\mathbb{C}) = 2 \quad (a basis of C\mathbb{C} over the field R\mathbb{R} is e.g. {1,i}\{1,i\})
  • dimC(C)=1\text{dim}_\mathbb{C}(\mathbb{C}) = 1 \quad (a basis of C\mathbb{C} over the field C\mathbb{C} is e.g. {1}\{1\})
Definition

In a finite-dimensional vector space VV with an inner product, the complementary subspace orthogonal to a proper subspace UU is called the orthogonal complement of UU and is denoted by U⊥U^\bot. It is characterised implicitly by the relation

V=U⊕U⊥,U⊥U⊥V = U \oplus U^\bot, \qquad U \bot U^\bot

or explicitly by

U⊥:={x∈V∣x⊥U}.U^\bot := \{x \in V | x \bot U \}.

We then call VV a direct sum of orthogonal complements.

Remark properties
  1. (U⊥)⊥=U(U^\bot)^\bot = U
  2. dim(U)+dim(U⊥)=dim(V)\text{dim}(U) + \text{dim}(U^\bot) = \text{dim}(V).
Remark calculation tricks (for questions about dimension, basis, linear dependence, etc.)

Given: v1,...,vk∈Vv_1, ..., v_k \in V
Wanted: dim(V)\text{dim}(V), span(v1,...,vk)\text{span}(v_1, ..., v_k) linearly independent?

  1. Write (v1T⋮vkT)=A\begin{pmatrix} v_1^T\\ \rule[.5ex]{3.5em}{0.4pt}\\ \vdots\\ \rule[.5ex]{3.5em}{0.4pt}\\ v_k^T \end{pmatrix} = A into a matrix with kk rows.

  2. Perform Gaussian elimination on AA until you have reached row echelon form.

  3. Draw conclusions:

    • rank(A)=dim(span(v1,...,vk))\text{rank}(A) = \text{dim}(\text{span}(v_1, ..., v_k))
    • rank(A)=k⇒v1,...,vk\text{rank}(A) = k \quad \Rightarrow \quad v_1, ..., v_k is linearly independent
    • rank(A)<k⇒v1,...,vk\text{rank}(A) < k \quad \Rightarrow \quad v_1, ..., v_k is linearly dependent
    • rank(A)=dim(V)⇒v1,...,vk\text{rank}(A) = \text{dim}(V) \quad \Rightarrow \quad v_1, ..., v_k is spanning
    • If rank(A)=dim(V)=k\text{rank}(A) = \text{dim}(V) = k, then v1,...,vkv_1, ..., v_k thus form a basis for VV
Example 6

To show: (201),(352),(01−1)∈R3\begin{pmatrix} 2\\ 0\\ 1 \end{pmatrix}, \begin{pmatrix} 3\\ 5\\ 2 \end{pmatrix}, \begin{pmatrix} 0\\ 1\\ -1 \end{pmatrix} \in \mathbb{R}^3 form a basis of R3\mathbb{R}^3.

Show solutionHide solution

Proof:
We know dim(R3)=3\text{dim}(\mathbb{R}^3) = 3, and we have 33 vectors.
Now we only need to show that the vectors are linearly independent.

(20135201−1)⇝(ii)−l21(i)(201051201−1)⇝(iii)−l32(ii)(201051200−1110)=A\begin{pmatrix} 2 & 0 & 1\\ 3 & 5 & 2\\ 0 & 1 & -1 \end{pmatrix} \stackrel{(ii) - l_{21}(i)}{\leadsto} \begin{pmatrix} 2 & 0 & 1\\ 0 & 5 & \frac{1}{2}\\ 0 & 1 & -1 \end{pmatrix} \stackrel{(iii) - l_{32}(ii)}{\leadsto} \begin{pmatrix} 2 & 0 & 1\\ 0 & 5 & \frac{1}{2}\\ 0 & 0 & -\frac{11}{10} \end{pmatrix} = A

⇒ rank(A)=3 full rank\Rightarrow \quad \text{ rank}(A) = 3 \quad \text{ full rank}
⇒\Rightarrow the vectors are linearly independent and therefore form a basis of R3\mathbb{R}^3. □\quad\quad\quad\quad\quad \square

Example 7

Is B={1,x,1+x2+x3}\mathcal{B} = \{1,x,1+x^2+x^3\} a basis of P3\mathcal{P}_3?
If yes, prove it; if no, extend it to a basis.

Show solutionHide solution

We know: dim(P3)=4\text{dim}(\mathcal{P}_3) = 4
B\mathcal{B} cannot be a, because dim(B)=3<4\text{dim}(\mathcal{B}) = 3 < 4.

Claim: B′={1,x,1+x2+x3,x2}\mathcal{B}' = \{1,x,1+x^2+x^3, x^2\} is a basis of P3\mathcal{P}_3.

Proof:

1=^e1x=^e2x2=^e3x3=^e41+x2+x3=^e1+e3+e4\begin{aligned} 1 &\mathrel{\hat{=}} e_1\\ x &\mathrel{\hat{=}} e_2\\ x^2 &\mathrel{\hat{=}} e_3\\ x^3 &\mathrel{\hat{=}} e_4\\ 1+x^2+x^3 &\mathrel{\hat{=}} e_1+e_3+e_4 \end{aligned}(1000010010110010)⇝⋯⇝(1000010000100001)\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 \end{pmatrix} \leadsto \cdots \leadsto \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \end{pmatrix}⇒linearly independent, so B′ is a basis of P3 □\Rightarrow \quad \text{linearly independent, so $\mathcal{B}'$ is a basis of $\mathcal{P}_3$ } \quad\quad\quad\quad\quad \square

Change of Basis, Coordinate Transformation (I)

Definition

Let A=(e1,...,en)\mathcal{A} = (e_1, ..., e_n) be the canonical basis of the vector space V and B=(b1,...,bn)\mathcal{B} = (b_1, ..., b_n) another basis of V, described in terms of the canonical basis. Then there exists a change-of-basis matrix with:

TAB=(b1∣⋯∣bn) with bi=TABei, i∈{1,...,n}.T_A^B = (b_1 | \cdots | b_n) \quad \text{ with } b_i = T_A^B e_i, \, i \in \{1, ..., n\}.VA→TBAVBV_\mathcal{A} \xrightarrow{\quad T_B^A \quad} V_\mathcal{B}
Remark

The following calculation rule holds: TBA=(TAB)−1\quad T_B^A = (T_A^B)^{-1}
With the definition above we therefore obtain: TBAbi=ei, i∈{1,...,n}\quad T_B^A b_i = e_i, \, i \in \{1, ..., n\}.