Apprentice Linear Algebra, 1st day, 6/27/05

REU 2005

Instructor: László Babai Scribe: Eric Patterson

Definitions 1.1. • An abelian group is a set G with the following properties: (i) (∀a, b ∈ G)(∃!a + b ∈ G) (ii) the addition in (i) is associative (iii) (∃0)(∀a ∈ G)(a + 0 = a) (iv) (∀a)(∃b)(a + b = 0)

(v) a + b = b + a

• A vector space is an abelian group (V, +) with a multiplication by scalars: – (∀α ∈ ℝ)(∀a ∈ V)(∃!αa ∈ V)

– (αβ)a = α(βa)

– (α + β)a = αa + βa

– α(a + b) = αa + αb Theorem 1.2. αa = 0 ⇔ α = 0 or a = 0. Corollary 1.3. (−1)a = −a. Examples 1.4. Some examples of vector spaces.

1. ℝ^{n}

2. geometric vectors in 2 or 3 dimensions

3. k × ℓ matrices

4. C[0, 1], the continuous functions from [0, 1] to ℝ

5. the space of infinite sequences

6. ℝ^{Ω}, the functions from Ω to ℝ • Ω = {1, …, n} is example 1 above

• Ω = {1, …, k} × {1, …, ℓ} is example 3

• Ω = [0, 1] contains example 4

• Ω = ℕ is example 5

Definitions 1.5. • A linear combination of a_{1}, …, a_{k} ∈ V is a sum ∑_{i=1}^{k} α_{i}a_{i} for some α_{1}, …, α_{k} ∈ ℝ.

• The span of a_{1}, …, a_{k}, written Span(a_{1}, …, a_{k}), is the set of all linear combinations of a_{1}, …, a_{k}. More generally, for a possibly infinite subset S of V, Span(S) is the set of all linear combinations of all finite subsets. By convention, Span(∅) = {0}.

• A subspace of V is a subset W which is a vector space under the same operations. This is written W ≤ V. Equivalently, a subset W is a subspace if it is nonempty and closed under addition and multiplication by scalars:

1. W ≠ ∅

2. (∀a, b ∈ W)(a + b ∈ W)

3. (∀a ∈ W)(∀λ ∈ ℝ)(λa ∈ W).

Equivalently, a subspace is a nonempty subset closed under linear combinations.

Corollary 1.6. W ≤ V iff Span(W) = W.

Exercise 1.7. If S ⊆ W, then Span(S) ≤ W.

• The vectors a_{1}, …, a_{k} are linearly independent if (∀α_{1}, … α_{k} ∈ ℝ)(∑_{i=1}^{k} α_{i}a_{i} = 0 ⇒ α_{1} = ⋯ = α_{k} = 0). An infinite set of vectors is linearly independent if all finite subsets are linearly independent. If a set of vectors is not linearly independent, it is linearly dependent.

Examples 1.8. Some more examples of vector spaces.

• ℝ[x] = {polynomials with real coefficients}.

• ℝ(x) = \{rational functions with real coefficients\}. That is, the set of \frac{p}{q} with p, q ∈ ℝ[x], q ≠ 0, and \frac{p_{1}}{q_{1}} = \frac{p_{2}}{q_{2}} iff p_{1}q_{2} = p_{2}q_{1}.

Claim 1.9. \{\frac{1}{x−α} : α ∈ ℝ\} is linearly independent in ℝ(x).

Definitions 1.10. • Let S ⊆ V. The rank of S, rk(S), is the maximum number of linearly independent vectors in S.

• Let W ≤ V. The dimension of W, dim(W), is the rank of W.

• Let B ⊆ W ≤ V. B is a basis of W if (i) Span(B) = W and (ii) B is linearly independent.

• A vector a depends on a set S ⊆ V if a ∈ Span(S).

Corollary 1.11. {a_{1}, …, a_{k}} is a basis of W if (∀w ∈ W) (∃!α_{1}, ⋯, α_{k} ∈ ℝ)(∑ α_{i}a_{i} = w).

If {a_{1}, …, a_{k}} is a basis for W and w ∈ W, then the coordinates of w with respect to the basis {a_{1}, …, a_{k}} is the column vector of the unique α_{i} given by the corollary; we write

[w]_{{a_{1},...,a_{k}}} = [ α_{1} ; ⋮ ; α_{k} ] .

The coordinates of w depend on the choice of basis for W. Later we shall see how coordinate vectors change under change of basis.

Observation 1.12. A set of vectors S is linearly dependent iff there is a member which depends on the rest.

Note 1.13. A set containing 0 is never linearly independent. Also, a sequence of vectors with repetitions is never linearly independent.

Exercise 1.14. Prove that these functions are linearly independent in ℝ^{ℝ}: 1, cos x, sin x, cos 2x, sin 2x, …, cos nx, sin nx, . . ..

Theorem 1.15 (Magic #1). If u_{1}, …, u_{k} ∈ Span(v_{1}, …, v_{ℓ}) and u_{1}, …, u_{k} are linearly independent, then k ≤ ℓ.

(Prove later.)

Corollary 1.16. If B_{1} and B_{2} are bases of W, then |B_{1}| = |B_{2}|.

Exercise 1.17. Every vector space has a basis. In fact, every set of generators contains a basis, and every linearly independent set can be extended to a basis.

Exercise 1.18. Let L ⊆ G ⊆ W, and suppose Span(G) = W. If L is linearly independent, then there is a basis B such that L ⊆ B ⊆ G.

Lemma 1.19. If a_{1}, …, a_{k} are linearly independent but a_{1}, …, a_{k+1} are linearly dependent then a_{k+1} ∈ Span(a_{1}, …, a_{k}).

The polynomials 1, x, x^{2}, … are a basis for ℝ[x], showing that dim ℝ[x] is countable. However, dim ℝ(x) is uncountable since \{\frac{1}{x−α} : α ∈ ℝ\} is linearly independent and uncountable.

A sequence (α_{0}, α_{1}, α_{2}, …) is a Fibonacci-type sequence if for n ≥ 2, α_{n} = α_{n−1} + α_{n−2}. Let F be the set of all Fibonacci-type sequences. The Fibonacci-type sequence with α_{0} = 0 and α_{1} = 1 is called the Fibonacci sequence, f = (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …).

Claim 1.20. F is a 2-dimensional subspace of ℝ^{ℕ}.

A geometric sequence is one of the form (1, q, q^{2}, …). Can a geometric sequence be a Fibonaccitype sequence?

Exercise 1.21. The sequence (1, q, q^{2}, …) is Fibonacci-type iff 1 + q = q^{2}.

The equation q^{2} = q + 1 has two solutions: \frac{1±\sqrt{5}}{2}. The two geometric sequences (1, \frac{1+\sqrt{5}}{2}, …) and (1, \frac{1−\sqrt{5}}{2}, …) are linearly independent and, thus, a basis for F.

Corollary 1.22. The Fibonacci sequence is a linear combination of these two geometric sequences.

Exercise 1.23. The nth term in the Fibonacci sequence is

f_{n} = \frac{1}{\sqrt{5}} ((\frac{1 + \sqrt{5}}{2})^{n} − (\frac{1 − \sqrt{5}}{2})^{n}) .

Exercise 1.24.

f_{n} = ⌊\frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^{n}⌉

where ⌊x⌉ means round x to the nearest integer.

Definitions 1.25. A k × ℓ matrix can be considered a set of ℓ columns, [a_{1}, …, a_{ℓ}], or a set of k rows, [b_{1}, …, b_{k}]. The row space of the matrix is the span of these rows: Span(b_{1}, …, b_{k}) ≤ ℝ^{ℓ}. Similarly, the column space of the matrix is the span of the columns: Span(a_{1}, …, a_{ℓ}) ≤ ℝ^{k}. The row-rank of the matrix is the dimension of the row space, and the column-rank of the matrix is the dimension of the column space.

Theorem 1.26 (Magic #2). For any k × ℓ matrix, the column rank and the row rank are equal.

Exercise 1.27. Prove. (Do not use determinants).

Fisher’s Inequality

Let t ≥ 1. Let A_{1}, …, A_{m} be subsets of {1, …, n} such that

(∀i ≠ j)(|A_{i} ∩ A_{j}| = t).  (1)

How big can m be? If t = 1, we can find n such sets.

Examples 1.28. • Let A_{i} = {i, n} for i = 1, …, n − 1 and A_{n} = {1, …, n − 1}.

• For n = 7, the Fano Plane is a remarkable set of 7 subsets of size 3 of {1, …, 7} with pairwise intersection size t = 1.

Theorem 1.29 (Fisher’s Inequality). Condition (1) implies m ≤ n.

Definition 1.30. For A ⊆ {1, …, n}, define the incidence vector v_{A} as v_{A} = (α_{1}, …, α_{n}) ∈ ℝ^{n}

where α_{i} = \{ \begin{matrix}1 & if i ∈ A \\ 0 & if i ∉ A \end{matrix}

Fisher’s Inequality follows from Magic #1 and the following exercise. Exercise 1.31. Let a_{1}, …, a_{m} be incidence vectors for sets A_{1}, …, A_{m} such that (∀i ≠ j)(|A_{i} ∩ A_{j}| = t). Then a_{1}, …, a_{m} are linearly independent in ℝ^{n}.