REU 2005 - LINEAR ALGEBRA - LECTURE 2

Instructor: László Babai Scribe: Justin Noel June 29, 2005.

2. Lecture 2

2.1. Rank, Magic #1.

V is a vector space, that is, (V,+) is an abelian group and we have a map ℝ × V → V, (λ,a) ↦ λa. Definition 2.1. A set a_{1},...,a_{k} ∈ V are linearly independent if (∀α_{i} ∈ ℝ)(∑ _{i=1}^{k} α_{i}a_{i} = 0 ⟹ α_{1} = ···= α_{k} = 0). In other words, only the trivial linear combination gives zero. Definition 2.2. A set b_{1},...,b_{s} ∈ V span (or generate) V iff (∀a ∈ V)(∃β_{1},...,β_{s} ∈ ℝ)(∑ _{i=1}^{s} β_{i}b_{i} = a). Definition 2.3. Span(b_{1},...,b_{s}) = {∑ _{i=1}^{s} β_{i}b_{i} |β_{i} ∈ ℝ} .

We say that v depends on b_{1},...,b_{s} if v ∈ Span(b_{1},...,b_{s}). Proposition 2.4. Transitivity of linear dependence: If a_{1},...,a_{k} each depends on b_{1},...,b_{ℓ} and b_{1},...,b_{ℓ} each depends on c_{1},...,c_{m} then a_{1},...,a_{k} each depends on c_{1},...,c_{m}. In other words, if A,B,C ⊆ V, A ⊆ SpanB and B ⊆ SpanC then A ⊆ SpanC. Exercise 2.5. Span(Span(C)) = SpanC. Definition 2.6. W ⩽ V is a subspace if W ⊆ V and W is a vector space under the same operations. Equivalently W ⩽ V iff W ≠ ∅ and W is closed under addition and multiplication by scalars (i.e. it is closed under linear combinations). Corollary 2.7. W ⩽ V ⟺ W = Span(W). Corollary 2.8. For any set A of vectors in V, Span(A) ⩽ V. Moreover, Span(A) is the smallest subspace containing A: If W ⩽ V and A ⊆ W ⟹ SpanA ⊆ W. Corollary 2.9. SpanA = ⋂ _{A⊆W ⩽V}W. Proposition 2.10. If v_{1},...,v_{k} are linearly independent and v_{1},...,v_{k},v_{k+1} are linearly dependent then v_{k+1} depends on v_{1},...,v_{k}. In other words v_{k+1} ∈ Span(v_{1},...,v_{k}), i.e. (∃α_{1},..,α_{k} ∈ ℝ)(v_{k+1} = ∑ _{i=1}^{k} α_{ik}v_{i}). Theorem 2.11 (Magic #1). If v_{1},...,v_{k} are linearly independent and each depends on w_{1},...,w_{ℓ} then k ≤ ℓ.

The proof is based on the Theorem 2.12 (Steinitz Exchange Principle). If a_{1},...,a_{k} are linearly independent and each depends on b_{1},...,b_{ℓ} then ∃j such that b_{j},a_{2},...,a_{k} are linearly independent.

Proof. We proceed by contradiction. Suppose ∀j we have b_{j},a_{2},...,a_{k} are linearly dependent, i.e. (∀j)(b_{j} ∈ Span{a_{2},...,a_{k}}. Since a_{1} ∈ Span{b_{1},...,b_{ℓ}} ⊆ Span{a_{1},...,a_{k}} we have a_{1} ∈ Span{a_{2},...,a_{k}}. But this is a contradiction since a_{1},...,a_{k} are linearly independent. □

Corollary 2.13. If a_{1},...,a_{k} are linearly independent and (∀i)(a_{i} ∈ Span{b_{1},...,b_{ℓ}}) then (∀i)(∃j)(a_{1},...,a_{i−1} ,b_{j},a_{i+1} ,...,a_{k}) are linearly independent).

Proof. (Of Magic #1) By repeatedly applying 2.13 we can replace v_{1} with some w_{j_{1}} and then v_{2} with some w_{j_{2}} and so on. At each stage w_{j_{1}},...,w_{j_{i}},v_{i+1} ...,v_{k} are linearly independent. And we have that w_{j_{1}},...,w_{j_{k}} are linearly independent and therefore distinct. So among the w_{1},...,w_{ℓ} there are k distinct vectors and therefore k ≤ ℓ. □

Definition 2.14. If v_{1},...,v_{m} ∈ V we say that v_{i_{1}},...,v_{i_{k}} is a basis of v_{1},...,v_{k}if (1) v_{i_{1}},...,v_{i_{k}} are linearly independent .

(2) (∀j)v_{j} ∈ Span{v_{i_{1}},...,v_{i_{k}}}.

Exercise 2.15. If v_{i_{1}},...,v_{i_{t}} are linearly independent then they can be extended to a basis of v_{1},...,v_{m}.

Exercise 2.16. Every maximal linearly independent set of v_{i} is a basis of v_{1},...,v_{m}.

Theorem 2.17. All bases of v_{1},...,v_{m} have the same size.

Definition 2.18. This size is called the rank of v_{1},...,v_{m}.

Definition 2.19. The row-rank (resp. the col-rank) of a matrix (α_{ij}) is defined to be the rank of the row vectors, v_{1} = (α_{11},...,α_{1n}),...,v_{n} = (α_{n1},...,α_{nn}) (resp. the column vectors, w_{1} = (α_{11},...,α_{n1}),...,w_{n} = (α_{1n},...,α_{nn}).

2.2. Column-rank and Row-rank of matrices.

Theorem 2.20 (Magic #2). For a matrix row-rank=col-rank.

Example 2.21. Diagonal matrices: A = (α_{ij}) such that if i ≠ j then α_{ij} = 0.

( \begin{matrix}α_{11} & 0 & 0 & 0 \\ 0 & α_{22} & 0 & 0 \\ 0 & 0 & α_{33} & 0 \end{matrix} ) .

We have that the rank of A = diag(α_{11},...,α_{kk}) is the number of nonzero diagonal entries.

Definition 2.22. The transpose, A^{T}, of a matrix A = (α_{ij}) is defined as A^{T} = (α_{ji}).

Since the transpose of a diagonal matrix is diagonal we see that Magic #2 is true for diagonal matrices.

Definition 2.23. There are two elementary row operations:

(1) ( a_{1} ⋮ a_{k} ) a_{i} := a_{i} + λa_{j}, λ ∈ ℝ and j ≠ i.

(2) Permutation of rows.

Theorem 2.24 (Row-rank invariance). Elementary row operations do not change the rowrank or the column-rank.

Proof. (Hints) After applying an elementary operation every row vector remains in the span of the row vectors before the operation. So by Magic #1 the row-rank can only get smaller. Since the inverse of an elementary operation is another elementary operation, we have that the row-rank must not change under elementary operations

For column rank invariance we check that if the column vectors b_{1},..,b_{s} are linearly dependent before applying a row operation they remain linearly dependent after and satisfy the same nontrivial linear relation. □

2.3. Linear algebra methods in combinatorics.

2.3.1. Fisher’s Inequality.

Theorem 2.25 (Fisher’s Inequality). If A_{1},..,A_{m}⊆ {1,...,n}, t ≥ 1 and (∀i ≠ j)(|A_{i}∩ A_{j} |= t) then m ≤ n.

Proof. (Hint) Under these conditions the incidence vectors of the A_{i} are linearly independent (see proof below). So we have m linearly independent vectors in ℝ^{n} ⟹ m ≤ n by Magic #1. □

Definition 2.26. A ⊆ {1,...,n}. The incidence vector of A, γ_{A} = (γ_{1},...,γ_{n}) ∈ ℝ^{n}, is

defined by γ_{i} = \{ \begin{matrix}1 & i ∈ A \\ 0 & i ∉ A \end{matrix}.

Definition 2.27 (Inner Product in ℝ^{n}). If a = (α_{1},...,α_{n}) and b = (β_{1},...,β_{n}) then a·b = ∑ _{i=1}^{n} α_{i}β_{i}.

This inner product satisfies the following formulae:

(1) a · (b + c) = a · b + a · c

(2) a · (∑ _{i=1}^{k} γ_{i}c_{i}) = ∑ _{i=1}^{k} γ_{i}a · c_{i}.

(3) a · b = b · a

Proposition 2.28. If A,B ⊆ {1,...,n} and v_{A},v_{B} are their respective incidence vectors then v_{A}· v_{B} = |A ∩ B|.

Example 2.29. Let A = {1,2,5},B = {2,3,5} then v_{A}= (1,1,0,0,1), v_{B} = (0,1,1,0,1) and v_{A}· v_{B} = 1 · 0 + 1 · 1 + 0 · 1 + 0 · 0 + 1 · 1 = 2 = |A ∩ B|.

Notation 2.30. Under Fisher’s conditions with incidence vectors v_{1} = v_{A_{1}},...,v_{m} = v_{A_{m}}∈ ℝ^{n} for i ≠ j, v_{i}· v_{j} = t and v_{i}· v_{i} = |A_{i}|= k_{i}.

Definition 2.31. A_{1},...,A_{m} is a sunflower if (∃C)(∀i ≠ j)(A_{i} ∩ A_{j} = C). C is called the kernel of the sunflower.

Proof. (Of 2.25 continued) □

Case 1. (∃i_{0})(k_{i_{0}} = t) ⟹ (∀j)(A_{j} ⊇ A_{i_{0}}) . In this case, we have a sunflower and it is easy to very that the v_{i} are linearly independent.

Case 2. (∀i)(k_{i} > t) v_{1},..,v_{m} ∈ ℝ^{n}, i ≠ j, v_{i}· v_{j} = t and v_{i}· v_{i} = k_{i} > t.

Lemma 2.32. If v_{1},...,v_{m} ∈ ℝ^{n}, t ∈ ℝ, (∀i ≠ j)(v_{i} · v_{j} = t) and (∀i)(v_{i} · v_{i} > t) then v_{1},...,v_{m} are linearly independent.

Note. We no longer assume that the v_{i} are incidence vectors or that t and k_{i} = v_{i} · v_{i} are integers.

Proof. Suppose ∑ _{i=1}^{m} α_{i}v_{i} = 0. We want to show that α_{1} = ···= α_{m}= 0.

We have

0 = v_{1}· ( ∑_{i=1}^{m} α_{i}v_{i}) = ∑_{i=1}^{m} α_{i}(v_{1}· v_{i})= t ∑_{i=1}^{m} α_{i}− tα_{1}+ α_{1}k_{1}

= t ( ∑_{i=1}^{m} α_{i}) + α_{1}(k_{1}− t)

so t (∑ _{i=1}^{m} α_{i}) = −α_{1}(k_{1}− t). So ∀j we have

(2.1)  α_{j} = −\frac{t (∑ _{i=1}^{m} α_{i})}{k_{j} − t}.

If ∑ _{i=1}^{m} α_{i} = 0 then (∀j)(α_{j} = 0). Assume now ∑ _{i=1}^{m} α_{i} ≠ 0. Let us add 2.1 for j = 1 to m:

∑_{j=1}^{m} α_{j} = −t ∑_{j=1}^{m} \frac{1}{k_{j} − t} · ∑_{i=1}^{m} α_{i}.

Dividing both sides by ∑ _{j=1}^{m} α_{j} we obtain 1 = −t ∑ _{j=1}^{m} \frac{1}{k_{j}−t} < 0 which is absurd.

□

This is an example of proving a combinatorial inequality using Linear Algebra. The method was initiated by R.C. Bose in 1949 who proved a special case of 2.25 (he assumed |A_{i}|= ···= |A_{m}|). To learn about other appilications of the method see Babai-Frankl’s book Linear Algebra Methods in Combinatorics.

2.3.2. Eventown and Oddtown. There are n citizens in Eventown. They are forming a collection of clubs. No two clubs are permitted to have identical membership. So we have 2^{n} possible clubs if we allow the empty club. But in Eventown there are additional rules on the formation of clubs. Namely, the number of people in a given club A_{i} must be even and the number of people belonging to any two clubs is even. (i.e. (∀i,j)(|A_{i}|and |A_{i}∩ A_{j} |are even)).

Exercise 2.33. Show that the number of even subsets of a given set is equal to the number of odd subsets. Give a “combinatorial proof” (explicit matching) and an “algebra proof” (use the binomial theorem).

Exercise 2.34. For what n is it the case that the number of subsets of size divisible by 4 is 2^{n−2} .

Hint: Use complex numbers and the binomial theorem.

Exercise 2.35. Generalize this.

One way to saitsfy the Eventown rules is to pair up the citizens and insist that each pair join exactly the same clubs. This “married couples” solution yields 2^{⌊^{\frac{n}{2}}⌋} clubs.

Exercise 2.36. * Show that 2^{⌊^{\frac{n}{2}}⌋} is the maximum number of possible clubs under Eventown rules.

Exercise 2.37. * Show that there exists 2^{⌊^{\frac{n}{2}}⌋} possible clubs under Eventown rules that isn’t given by a “married couples” solution.

Oddtown is also forming a collection of clubs {A_{i}}. In Oddtown the rules dictate that for all i,j |A_{i}|is odd and |A_{i}∩ A_{j} |is even.

Exercise 2.38. There are at least 2^{\frac{n^{2}}{8}} ways to form n clubs in Oddtown. Exercise 2.39. (Oddtown Theorem) Under Oddtown rules, m ≤ n, (where m is the number of clubs and n is the number of citizens). Definition 2.40. Informally a field is a set with the usual notions of addition, subtraction, multiplication and division. Example 2.41. The following are fields ℝ,ℂ,ℚ and 𝔽_{p} for p a prime. Exercise 2.42. A,B are k × ℓ matrices over a field 𝔽 show that rank(A + B) ≤ rankA + rankB. Exercise 2.43. A is a k×ℓ matrix and B is an ℓ×m matrix then rank(AB) ≤ min(rankA,rankB). And therefore

rank(AA^{T}) ≤ rankA.

Exercise 2.44. Over ℝ: rank(AA^{T}) = rankA. Exercise 2.45. Show that this is false 𝔽 = ℂor 𝔽 = 𝔽_{p} for all primes p. In fact, over each of these fields, there exist matrices A of large rank such that AA^{T} = 0.