Theorem 1.1(cancellation law):

x, y, z ∈ V ; x + z = y + z ⇒ x = y

Theorem 1.3: V is a vector space and W ⊆ V . Then W is a subspace of V if and only if

1. x, y ∈ W ⇒ x + y ∈ W and 2. a ∈ F, x ∈ W ⇒ ax ∈ W .

V = P (F ), W = P_{n}(F ) = {polynomials
of degree n or less}

V = R^{∞}, W ={convergent sequences}

Theorem 1.4: Any intersection of subspaces of a vector space V is a subspace of V .

The union of two subspaces of a vector space V is not a subspace in general.

example: V = R^{3},

U_{1} = {(a_{1}, 0, a_{3}) : a_{1}, a_{3} ∈ R}, U2 = {(a_{1}, a_{2}, 0) : a_{1}, a_{2} ∈ R}

are subspaces.

U_{1} T U_{2} = {(a_{1}, 0, 0) : a_{1} ∈ R} is a
subspace.

U_{1} S U_{2} is not a subspace because
(a_{1}, 0, a_{3}) + (a_{1}, a_{2}, 0) /∈ U_{1} S U_{2}.

Linear combination

linear combination of u_{1}, · · · , u_{k} ∈ V : v = a_{1}u_{1} + · · · + a_{k}u_{k},
a_{i} ∈ F

span of S: the set of all linear combinations of the vectors in S

notation: span(S)

span(∅)= {0} for conve- nience

example

V = R^{3},

span({(1, 0, 0), (0, 1, 0)})= {(a_{1}, a_{2}, 0) : a_{1}, a_{2} ∈ R}

Theorem 1.5: V is a vector space; W is its subspace; and S ⊆ V . Then

1. span(S) is a subspace of V , and 2. S ⊆ W ⇒ span(S)⊆ W .

generating set S for V : span(S)= V

R^{3} = span({(1, 0, 0), (0, 1, 0), (0, 0, 1)})

R^{3} = span({(1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 1)})

A smallest generating set which generates a vector space V . (smallest → linearly independent → basis)

Linear dependence and linear independence

linearly dependent S ∈ V (F ):

For u_{1}, · · · , u_{k} ∈ S, and ∃a_{1}, · · · , a_{k} ∈ F , not all zero, such that
a_{1}u_{1} + · · · + a_{k}u_{k} = 0.

– a_{i} 6= 0 ⇒ u_{i} = a^{−1}_{i} (−a_{1})u_{1} + · · · + a^{−1}_{i} (−a_{i−1})u_{i−1} +
a^{−1}_{i} (−a_{i+1})u_{i+1} + · · · + a^{−1}_{i} (−a_{k})u_{k}

– 0 ∈ S ⇒ S is linearly dependent. [a0 = 0]

linearly independent S ∈ V (F ): not linearly dependent

equivalent definition: ∀u_{1}, · · · , u_{k} ∈ S,

a_{1}u_{1} + · · · + a_{k}u_{k} = 0 ⇒ a_{1} = · · · = a_{k} = 0

∅ is linearly independent. [convention]

A set containing a single nonzero vector is linearly indep.

Basis and dimension

basis for V : linearly independent generating set for V

A basis is a ‘smallest’generating set for V .

{(1, 0, 0), (0, 1, 0), (0, 0, 1)}:

a basis for R^{3}.

{(1, 0, 0), (0, 1, 0), 0, 0, 1),
(1, 1, 1)}: not a basis for R^{3}.

{(1, 1, 0), (1, 0, 1)} a basis
for R^{2}.

example:

{(1, 0, 0), (0, 1, 0), (0, 0, 1)} is the “standard basis” for R^{3}.

{(1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 1)} is not a basis for R^{3}.

{(1, 1, 0), (1, 0, 1), (0, 1, 1)} is a basis for R^{3}.

{1, x, x^{2}} is the “standard basis” for P_{2}(R).

{x^{2} + 3x − 2, 2x^{2} − 3, 5x, x + 1, −x^{2} − 4x + 4} is not a basis
for P_{2}(R).

{x^{2} + 3x − 2, 2x^{2} − 3, x + 1} is a basis for P_{2}(R).

Lagrange polynomials f_{i}(x) = Π^{n}_{j=0,j6=i}_{c}^{x−c}^{j}

i−c_{j}, i = 0, · · · , n,
where c_{i} 6= c_{j} for i 6= j, form a basis for P_{n}(R).

[determined by n + 1 coefficients c_{i}, i = 0, · · · , n]

Theorem 1.8: representation theorem
β = {u_{1}, · · · , u_{n}} is a basis for V

⇔ ∀v ∈ V , ∃ unique (a_{1}, · · · , a_{n}) such that
v = a_{1}u_{1} + · · · + a_{n}u_{n}.

proof: “⇒”: Let β is a basis for V .

⇒ V =span(β) [basis]

⇒ ∀v ∈ V , v = a_{1}u_{1} + · · · + a_{n}u_{n} for some a_{1}, · · · , a_{n}
Show uniqueness:

Let also v = b_{1}u_{1} + · · · + b_{n}u_{n}.

⇒ 0 = (a_{1} − b_{1})u_{1} + · · · + (a_{n} − b_{n})u_{n}

⇒ a_{1} = b_{1}, · · · , a_{n}b_{n} [β is lin indep]

“⇐”: Assume ∀v ∈ V , ∃ unique a_{1}, · · · , a_{n} such that
v = a_{1}u_{1} + · · · + a_{n}u_{n}

⇒ β = {u_{1}, · · · , u_{n}} generates V .
Show linear independence:

Let 0 = c_{1}u_{1} + · · · + c_{n}u_{n}.

⇒ c_{1} = 0, · · · , c_{n} = 0 [0u_{1} + · · · + 0u_{n} = 0, uniqueness]

This theorem means that given a vector space V (F ) and its
basis β, whatever kind of vector space it may be, each vector v
in V is uniquely represented by (a_{1}, · · · , a_{n}).

Given a basis, there is a one-to-one correspondence between V
and F^{n}.

[v]_{β} = (a_{1}, · · · , a_{n})^{t} is called the (n-tuple) representation of
v in β or relative to β.

example:

β = {1, x, x^{2}}, a_{0} + a_{1}x + a_{2}x^{2} → (a_{0}, a_{1}, a_{2})

β = {1, 1 + x, 1 + x + x^{2}},

a_{0} + a_{1}x + a_{2}x^{2} → (a_{0} − a_{1}, a_{1} − a_{2}, a_{2})

β = 1 0

0 0 , 0 1

0 0 , 0 0

1 0 , 0 0

0 1 , , a b

c d →

(a, b, c, d)

β = {e^{i2πkf}^{0}^{t} : k = · · · , −1, 0, 1, · · · },
f (t) = P_{∞}

k=−∞ a_{k}e^{i2πkf}^{0}^{t} → (· · · , a_{−1}, a_{0}, a_{1}, · · · )

periodic function with frequency f_{0} → Fourier coefficients

Theorem 1.9: A finite generating set S for V can be reduced to a basis for V .

proof:

(i) If S = ∅ or S = {0}, they generate V={ 0 }.

Henceβ = ∅ is considered a basis for V .

(ii) If S has non-zero vectors, let β = {u_{1}, · · · , u_{k}} be a largest
linearly independent subset of S.

⇒ span(β) ⊆ span(S) = V [subset, generating set]

To show V =span(S) ⊆ span(β), we show S ⊆ span(β).

v ∈ S ⇒ v ∈ β or v /∈ β[If v ∈ β then v ∈ span(β), done.]

v /∈ β ⇒ v S β is lin dep. [β is a largest lin indep subset]

⇒ v ∈ span(β) [Thm 1.7]

⇒ S ⊆ span(β) ⇒ span(S) ⊆ span(β) [Thm 1.5]

example:

{x^{2} + 3x − 2, 2x^{2} − 3, 5x, x + 1, −x^{2} − 4x + 4} spans P_{2}(R).

{x^{2} + 3x − 2, 2x^{2} − 3, 5x} is a basis for P_{2}(R).

{(1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 1)} spans R^{3}.
{(0, 1, 0), (0, 0, 1), (1, 1, 1)} is a basis for R^{3}.

Theorem 1.10(replacement theorem):

G ⊆ V is a generating set for V and has n elements;

L ⊆ V is a linearly independent set and has m elements. Then 1. m ≤ n, and

2. L can be extended to a generating set for V by adding n − m elements from G.

Proof by induction:

Let the set of the n − m elements be H.

(i) If |L| = m = 0, then 1. 0 ≤ n and

2. H = G generates V .

(ii) Assume the theorem holds for |L| = m. That is, assume 1. m ≤ n, and

2. ∃H ⊆ G such that |H| = n − m and L S H generates V .
(iii) To show that the theorem also holds for |L^{0}| = m + 1,

let L = {v_{1}, · · · , v_{m+1}} be linearly independent, and let L =
{v_{1}, · · · , v_{m}}.

⇒ L is linearly independent. [Thm 1.6]

⇒ m ≤ n and ∃H = {u_{1}, · · · , u_{n−m}} such that L S H generates
V .[(ii)]

⇒ v_{m+1} = a_{1}v_{1} + · · · + a_{m}v_{m} + b_{1}u_{1} + · · · + b_{n−m}u_{n−m}
If m = n

⇒ v_{m+1} = a_{1}v_{1} + · · · + a_{m}v_{m}: contradiction [L^{0} is lin indep]

⇒ m < n [(ii): m ≤ n]

⇒ m + 1 ≤ n : “1”

b_{i} 6= 0 for some i [L^{0} is lin indep], and by rearranging we can let
i = 1 such that b_{1} 6= 0.

⇒ u_{1} = (−b^{−1}_{1} a_{1})v_{1}+· · ·+(−b^{−1}_{1} a_{m})v_{m}+(b^{−1}_{1} )v_{m+1}+(−b^{−1}_{1} b_{2})u_{2}+

· · · + (−b^{−1}_{1} b_{n−m})u_{n−m}: (1)
Let H^{0} = {u_{2}, · · · , u_{n−m}}.

⇒ L S H = {v_{1}, · · · , v_{m}, v_{m+1}, u_{2}, · · · , u_{n−m}}
L S H = {v_{1}, · · · , v_{m}, u_{1}, u_{2}, · · · , u_{n−m}}

⇒ V =span(L S H) ⊆ span(L^{0} S H)=span(L^{0} S H^{0}) ⊆ V.

(by Thm 1.5)

example:

G = {x^{2}+ 3x − 2, 2x^{2}− 3, 5x, x + 1, −x^{2}− 4x + 4} ⊆ P_{2}((R)).

L = {1, x} ⇒ H = {5x, x + 1, −x^{2} − 4x + 4}

G = {(1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 1, )} generates (R)^{3}.
L = {(1, 1, 0)} ⇒ H = {(1, 0, 0), (0, 1, 0), (0, 0, 1)}

In these examples, H can be any three elements from G.

basis for V : linearly independent generating set for V

{(1, 0, 0), (0, 1, 0), (0, 0, 1)} is the “standard basis” for R^{3}.

{(1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 1)} is not a basis for R^{3}.

{(1, 1, 0), (1, 0, 1)} is not a basis for R^{3}.

Theorem 1.8: representation theorem
β = {u_{1}, · · · , u_{n}} is a basis for V

⇔ ∀v ∈ V , ∃ unique (a_{1}, · · · , a_{n}) such that
v = a_{1}u_{1} + · · · + a_{n}u_{n}.

⇒ [v]_{β} = (a_{1}, · · · , a_{n})^{t} is called the (n-tuple) representation of
v in β or relative to β.

Theorem 1.9: A finite generating set G for V can be reduced to a basis for V , that is, a basis β is a subset of G.

Theorem 1.10(replacement theorem):

Corollary 1.10.1: If V has a finite basis, then every basis for V contains the same number of vectors.

proof: Let β and γ be bases for V .

⇒ |γ| ≤ |β|. [γ is lin indep; β spans V ; Thm 1.10]

⇒ |β| ≤ |γ|. [β is lin indep; γ spans V ; Thm 1.10]

dimension: the number of vectors in a basis

The dimension can be either finite or infinite.

This definition of dimension applies to all spaces with algebraic structure-vector, normed linear, inner product, Banach, Hilbert, and Euclidean spaces.

There are other kinds of dimensions, eg topological or fractal, but they are not our concern.

example:

dim({0}) = 0

dim(F^{n}) = n

dim(M_{m×n}) = mn

dim(P_{n}) = n + 1

The space of complex numbers can be

1. a vector space of dimension 1 when the field is complex.

2. a vector space of dimension 2 when the field is real.

Corollary 1.10.2, expanded: Let dim(V )=n.

1. S generates V.

⇒ |S| ≥ n

⇒ S can be reduced to a basis for V . [Thm 1.9]

2. S generates V and |S| = n.

⇒ S is a basis for V . 3. S is linearly independent.

⇒ |S| ≤ n

⇒ S can be extended to a basis for V . 4. S is linearly independent and |S| = n.

⇒ S is a basis for V .

Note that

|S| ≥ n ; S generates V .

|S| ≤ n ; S is linearly independent.

|S| = n ; S is a basis for V .

Theorem 1.11: dim(V ) < ∞; W is a subspace of V . Then 1. dim(W ) ≤ dim(V )

2. dim(W )=dim(V ) ⇒ W = V . proof: Let α be a basis for W .

”1”: dim(W ) = |α| ≤ dim(V ). [α is lin indep; Corol 1.10.2]

”2”: If |α|=dim(V ),

⇒ α is a basis for V . [α is lin indep; Corol 1.10.2]

Corollary 1.11: dim(V ) < ∞; W is a subspace of V . Then any basis for W can be extended to a basis for V .

proof: Let α be a basis for W .

⇒ α is linearly independent.

⇒ α can be extended to a basis for V . [Corol 1.10.2]

So the best way to describe a vector space V and its subspace
W is to find a basis {u_{1}, · · · , u_{m}} for W and extend it to a basis
{u_{1}, · · · , u_{m}, u_{m+1}, · · · , u_{n}} for V .

example:

Though our discussion considers mainly finite-dimensional vector spaces, the discussion can be generalized to infinite-dimensional vector spaces.

Chapter 2 Linear transformation and Matrices

Let us now consider a function from a vector space to another, satisfying linearity, and call it a linear transformation.

linear transformation T : V → W for vector spaces V (F ) and W (F ) : ∀x, y ∈ V and ∀a ∈ F ,

1. T (x + y) = T (x) + T (y) and 2. T (ax) = aT (x)

The two linearity conditions can be replaced by one:

∀x, y ∈ V and ∀a, b ∈ F , T (ax + by) = aT (x) + bT (y)

T is linear ⇒ T (0) = 0

Note that the first 0 is the zero vector of V and the second is that of W .

Why linear? Linearity of the transformation matches linearity of vector spaces (closed under linear combination).

A subspace is mapped to a subspace.

A linear transformation has a matrix representation (will be explained).

It allows simpler computation, systematic analyses, and more applications (reguiring linearization at a local region in space or time).

terms related to linear transformation:

function f : X → Y : ∀x ∈ X, ∃ unique f (x) ∈ Y

domain of f : X

codomain of f : Y

range of f : f (X) = {f (x) : x ∈ X}

image of A under f : f (A) = {f (x) : x ∈ A}

preimage of B under f : f^{−1}(B) = {x : f (x) ∈ B};

also called as inverse image

onto: f (X) = Y

one-to-one: f (u) = f (v) ⇒ u = v

inverse of f : f^{−1} : Y → X such that

∀x ∈ X, f^{−1}(f (x)) = x; and ∀y ∈ Y, f (f^{−1}(y)) = y

invertible f : f^{−1} exists (⇔ one-to-one and onto)

restriction of f to A: f_{A} : A → Y such that

∀x ∈ A, f_{A} = f (x)

composite or composition of f : f : X → Y and g : Y → Z:

g ◦ f : X → Z such that ∀x ∈ X, (g ◦ f )(x) = g(f (x)) (We will use the notation gf in place of g ◦ f .)