Apprentice Linear Algebra, 3rd day, 07/06/05

REU 2005

Instructor: László Babai Scribe: Mohammed Abouzaid

Notes revised: July 8, 2005

3 Linear Maps

Definition 3.1. Given two vector spaces V and W we say that a function f : V → W is linear if:

(∀a, b ∈ V)(f(a + b) = f(a) + f(b))
(∀a ∈ V)(∀λ ∈ ℝ)(f(λa) = λf(a)).

Equivalently we may combine these two conditions into one:

(∀a_{1}, …, a_{n} ∈ V)(∀λ_{1}, …, λ_{n} ∈ ℝ) (f (∑_{i=1}^{n} λ_{i}a_{i}) = ∑_{i=1}^{n} λ_{i}f(a_{i}))

Such a function is called a linear map or a homomorphism. If V = W, we may also call f a linear transformation or a linear operator. As an immediate Corollary, we obtain:

Corollary 3.2.

f(0) = 0

Proof:

f(0) = f(0 · 0) = 0 · f(0) = f(0).

Regarding the entire discussion of vector spaces and their properties, we may replace ℝ by any field F, and define vector space “over F ” for which F is the domain of scalars. Note that it only makes sense to consider linear maps between vector spaces over the same field.

We are already familiar with the field of real numbers ℝ, but also with rational numbers ℚ, complex numbers ℂ, and the finite fields 𝔽_{p} (integers mod p) for primes p.

Example 3.3. 𝔽_{p}^{n} is a vector space over 𝔽_{p} with p^{n} elements.

We will now consider some examples of linear maps.

Example 3.4. If F [x] is the space of polynomials over F (considered as a vector space over F) the differentiation operator:

D = \frac{d}{dx} : f ↦ f′

is a linear map (Check this).

3.1 Geometric Transformations

Geometric transformations also provide examples of linear maps. Since a linear map must fix the origin, we will only consider geometric transformations with this property:

Example 3.5. Isometries of the plane (congruences) which fix the origin are linear maps. Examples include reflection across an axis that passes through the origin and rotation by a prescribed angle θ about the origin.

Exercise 3.6. Prove that every congruence of the plane fixing the origin is either a rotation or a reflection.

Note that since rotations preserve orientation, while reflections reverse it, these two possibilities are mutually exclusive. We will call transformations which preserve orientation sense preserving, while those that do not preserve orientation will be called sense reversing. Use the following Lemma to give an elegant solution to the previous exercise.

Lemma 3.7. If r_{1} and r_{2} are reflections about two axes that are angle θ apart, then r_{1} ∘ r_{2} is a rotation by 2θ.

We would like to extend these results to congruence in 3-dimensional space. Note that we have rotations about axes, and reflections across planes. (Note: Reflection through a line corresponds to 180 degree rotation.) Note that these reflections fix all points of a plane, while the rotations fix all points of a line. We have the following Lemma which extends the previous result from dimension 2 to 3:

Lemma 3.8. The composition of reflections in two planes which are at an angle θ is the rotation by 2θ about their line of intersection.

Unlike the 2-dimensional case, these transformations do not exhaust the isometries of space. Indeed, consider the transformation

C : ℝ^{3} → ℝ^{3}
x ↦ −x

which correspond geometrically to reflection through the origin. Since the only fixed point of this transformation is the origin, it cannot be the same as one of the above examples. It is clear geometrically that this transformation is sense reversing. In fact, we can obtain is as the composition of 3 reflection through mutually orthogonal planes. More generally:

Exercise 3.9. (a) Every sense reversing congruence of the 3-dimensional space that fixes the origin is the composition of 3 reflections in planes that contain the origin. (b) Every sense reversing congruence of the 3-dimensional space is the composition of 3 reflections. (Note that no fixed points are assumed.)

You should use the following Theorem in order to prove part (a) of the the above exercise:

Theorem 3.10. Every sense-preserving congruence of ℝ^{3} which fixes the origin is a rotation.

We will see in a future class how this Theorem follows from the fact that every real polynomial of degree 3 has a real root. In fact, we have the more general result:

Lemma 3.11. Every odd degree real polynomial has a real root.

Proof: Use the continuity of polynomials, and the fact that the limit in one direction is +∞ and −∞ in the other.

Definition 3.12. A rotational reflection is the composition of a rotation and the central reflection C.

The the central reflection is given by multiplication by −1, it commutes with every linear transformation, hence the order of composition in the previous definition is not an issue. An alternative definition goes as follows:

Consider a plane P and a line L perpendicular to it. A rotational reflection is the composition of a rotation about the line with a reflection through the plane.

To see that these two notions are the same, we express the central reflection as the composition of reflections through mutually orthogonal planes:

C = r_{1} ∘ r_{2} ∘ r_{3}.

We may choose r_{3} to be the reflection through P, while r_{2} and r_{1} are reflection through planes P_{2} and P_{1} whose intersection is L. In particular, using Lemma 3.8, we may express the rotation by angle θ about the line L as the composition

r_{0} ∘ r_{1}

where r_{0} is reflection through some plane P_{0} which passes through L and such that the angle between P_{0} and P_{1} is \frac{θ}{2}. Our original definition of a rotational reflection is a transformation of the form:

(r_{0} ∘ r_{1}) ∘ C = r_{0} ∘ r_{1} ∘ r_{1} ∘ r_{2} ∘ r_{3} = r_{0} ∘ r_{2} ∘ r_{3}.

Note that r_{0} ∘ r_{2} is a rotation (about the line L) with angle π + θ so the expression

(r_{0} ∘ r_{2}) ∘ r_{3}

is exactly that of a rotational reflection according to our second definition. We can now go through the entire argument “backward” by inserting r_{1} ∘ r_{1} in order to conclude that the two notions are indeed equivalent.

Note that the trick in the above argument is two choose the expression for a rotation as a product of reflection “appropriately.”

Exercise 3.13. (Use Theorem 3.10) All sense-reversing congruences of ℝ^{3} which fix the origin are rotational reflections.

Note that rotational reflections include reflections in a plane when the rotation angle is 0.

Examples 3.14. We list further geometric examples of linear transformations.

• Orthogonal projection onto a line.

• Skew projection onto a line. (This means choosing a direction along which the projection occurs; this direction is not necessarily perpendicular to the chosen line.)

• Shearing. In coordinates, this is given by the transformation

(x, y) ↦ (x + αy, y),

where α is a given real number. This transformation fixes the x-axis and moves a point in the x-direction by an amount proportional to its y coordinate (like tilting a deck of cards).

• Vertical stretching / shrinking, which is given in coordinates by:

(x, y) ↦ (x, αy)

for some real number α. This transformation will map circles to ellipses and axis-parallel squares to rectangles. One may also compose vertical stretching/shrinking with horizontal stretching/shrinking.

We will now return to an abstract point of view:

3.2 Linear Maps: Rank, Kernel

Theorem 3.15. If e_{1}, …, e_{n} is a basis of V and w_{1}, …, w_{n} are arbitrary elements of W then there exists a unique linear map f : V → W such that f(e_{i}) = w_{i}.

We emphasise the fact that the choice of w_{1}, …, w_{n} is arbitrary, and that V and W do not necessarily have the same dimension. Proof: We first prove uniqueness:

Given v ∈ V we may write v = ∑_{i=1}^{n} α_{i}e_{i} for a unique choice α_{i} of scalars. If f is a linear function satisfying the conditions of the theorem, we can compute that:

f(v) = f (∑_{i=1}^{n} α_{i}e_{i}) = ∑_{i=1}^{n} α_{i}f(e_{i}) = ∑_{i=1}^{n} α_{i}w_{i},

which is indeed a uniquely determined value.

In order to prove existence, we use our result for uniqueness in order to define:

f(v) := ∑_{i=1}^{n} α_{i}w_{i},

where the scalars α_{i} are uniquely determined by the equation

v = ∑_{i=1}^{n} α_{i}e_{i}

Exercise 3.16. Complete the proof of existence (i.e: Check the above map f is linear).

Definition 3.17. The image of f is the subset of W:

Im(f) = {f(v) : v ∈ V }.

Exercise 3.18.

Im(f) ≤ W

Definition 3.19. The rank of f is

rk(f) = dim(Im(f)).

Exercise 3.20.

rk(f) ≤ dim V

Proof: Since

Im(f) = Span{f(e_{i}) | i = 1, …, n},

we know that Im(f) has a spanning set which consists of n elements. Therefore, its dimension is less than or equal to n by Magic #1.

Definition 3.21. The kernel of f is:

ker(f) = f^{−1}(0).

Exercise 3.22.

ker(f) ≤ V

Example 3.23. The kernel of the differentiation map on F [x] consists of the subspace of constant polynomials.

One of the main theorems of this theory is:

Theorem 3.24.

dim ker(f) + rk(f) = dim V

Proof: Let k be the dimension of ker(f), and choose e_{1}, …, e_{k} a basis of ker(f). Note that these vectors are linearly independent in V (though they may not span it), so we may extend them to a basis (i.e: choose e_{k+1}, …, e_{n} vectors in V such that e_{1}, …, e_{k}, e_{k+1}, …, e_{n} is a basis of V).

Claim 3.25. f(e_{k+1}), …, f(e_{n}) is a basis of Im(f).

Note that an immediate consequence of this claim is the Corollary

Corollary 3.26. dim(Im(f)) = n − k

from which the theorem immediately follows. So it suffices to prove the claim. This is itself done in two parts:

1. The vectors span Im(f): We know that Im(f) is spanned by {f(e_{1}), …, f(e_{n})}. Since f(e_{1}) = … = f(e_{k}) = 0, we conclude that:

Im(f) = Span{f(e_{1}), …, f(e_{n})} = Span{f(e_{k+1}), …, f(e_{n})}.

2. Linear independence: Suppose

∑_{i=k+1}^{n} α_{i}f(e_{i}) = 0,

and recall that the desired conclusion is that all scalars α_{i} vanish. Let g = ∑_{i=k+1}^{n} α_{i}e_{i}. Since f is linear, we have

f(g) = f ( ∑_{i=k+1}^{n} α_{i}e_{i}) = ∑_{i=k+1}^{n} α_{i}f(e_{i}) = 0,

so that g ∈ ker(f). But e_{1}, … e_{k} span the kernel of f, so there are scalars β_{j} such that

g = ∑_{j=1}^{k} β_{j}e_{j}.

Equating our two expressions for g we conclude that

∑_{i=k+1}^{n} α_{i}e_{i} − ∑_{j=1}^{k} β_{j}e_{j} = 0.

Since the set {e_{1}, …, e_{n}} is linearly independent, we conclude that all scalar coefficients vanish, and, in particular, that all the scalars α_{i} are zero, which was the desired conclusion.

3.3 Systems of Linear Equations

We shall now explore some consequences of this theorem. Let A be a k × ℓ matrix over a field F. Given a column vector x ∈ F^{ℓ} we can use the matrix A to produce

Ax = y ∈ F^{k}.

The map

f : F^{ℓ} → F^{k}
x ↦ Ax

is a linear map by the distributivity of matrix multiplication.

Exercise 3.27. Prove that the rank of f is the rank of the matrix A (Hint: Use the column rank of A, and try to show that the image of f is the span of the column vectors of A).

One can do the previous exercise explicitly by writing A = [ a_{1} ⋯ a_{ℓ} ] where a_{i} is the ith column of A, and hence an element of F^{k}. Using this notation, we may express the product:

Ax = [ a_{1} ⋯ a_{ℓ} ] [ x_{1} ; ⋮ ; x_{ℓ} ] = ∑_{i=1}^{ℓ} x_{i}a_{i}

We will now relate this to the theory of systems of linear equations. Express A = (α_{ij})_{j=1,...,ℓ^{i=1,...,k}}, and x as a column vector as above. Consider the equation

Ax = 0  (1)

where A is a k × ℓ matrix and x ∈ F^{ℓ} is an unknown vector. We may expand this equation as the system of homogeneous linear equations (“homogoeneous” refers to the right hand side being zero):

\begin{aligned}α_{11}x_{1} + α_{12}x_{2} + ⋯ + α_{1ℓ}x_{ℓ} & = & 0 \\ α_{21}x_{1} + α_{22}x_{2} + ⋯ + α_{2ℓ}x_{ℓ} & = & 0 \\ ⋮ & ⋮ & ⋮ \\ α_{k1}x_{1} + α_{k2}x_{2} + ⋯ + α_{kℓ}x_{ℓ} & = & 0 \end{aligned}

Note that U = ker(f) = {x ∈ F^{ℓ} : Ax = 0} is exactly the set of solutions to this homogeneous system of k linear equations. This system of linear equations is succinctly contained in the matrix equation Ax = 0.

Geometric Examples: Note that if we have a system of equations in 3 variables over ℝ, then the solutions will form a plane if there is only one equation, a line if there are two, and a single point (the origin) if there are three or more (Unless some of the equations are redundant). We now generalize this to higher dimensions:

Claim 3.28. The set U of solutions to a system of homgeneous linear equations is a subspace: U ≤ F^{ℓ}.

Proof:

1. 0 ∈ U is clear since choosing all coordinates x_{i} to be zero yields a solutions to any homogeneous linear equations.

2. U is closed under addition since Ax = 0 and Ay = 0 imply that A(x+y) = Ax+Ay = 0.

3. ∀λ ∈ F, we have A(λx) = λAx = 0 if Ax = 0.

We are now ready to state the fundamental theorem of the theory of systems of linear equations:

Theorem 3.29. The dimension of the set of solutions of a system of homogeneous linear equations is the number of variables minus the rank of the system: dim(U) = ℓ − rk(A).

Proof: Consider the linear transformation f : x ↦ Ax. We have defined U to be the kernel of f. By Theorem 3.24,

dim U = dim V − rk(f) = ℓ − rk(f).

but Exercise 3.27 implies that rk(A) = rk(f), which yields the desired formula

We can interpret this to say that each non-redundant equation reduces the dimension of the space of solutions by 1. Physicists would say that we lose a degree of freedom which each nonredundant equation.

3.4 Orthogonality

We will now apply this theorem to determine the maximum number of clubs in Eventown.

Our tool will be a set of geometric concepts over an arbitrary field F (“geometric algebra”).

First, we introduce the dot product on F^{n} by the expression:

x · y = ∑_{i=1}^{n} x_{i}y_{i},

where (x_{i})_{i=1}^{n} and (y_{i})_{i=1}^{n} are the coordinates of x and y, respectively.

Definition 3.30. x is perpendicular to y (denoted x⊥y) if x · y = 0. Definition 3.31. A vector x is isotropic if x · x = 0. Example 3.32. The vector

( \begin{matrix}1 \\ i \end{matrix} )

an isotropic vector in ℂ^{2} since 1^{2} + i^{2} = 0.

There are no isotropic vectors in ℝ^{n}. But there are finite fields 𝔽_{p} for which there are isotropic vectors in 𝔽_{p}^{2}. Exercise 3.33. For what primes p does there exist isotropic vectors in 𝔽_{p}^{2}? (Hint: Experiment with small primes. Expect an answer of striking simplicity.) Definition 3.34. Given two subsets A and B is F^{n}, we say that A is perpendicular to B (denoted A⊥B) if

(∀a ∈ A)(∀b ∈ B)(a⊥b)

Definition 3.35. Given A ⊆ F^{n}, we define A^{⊥} (pronounced A-perp):

A^{⊥} := {b ∈ F^{n} : b⊥A}

Note that ∅^{⊥} = F^{n}. Exercise 3.36. A^{⊥} ≤ F^{n} (Hint: Use distributivity of the dot product). Theorem 3.37. If S ⊆ F^{n}, then

dim(S^{⊥}) = n − rk(S).

Proof: Note that if r = rk(S), then we may choose b_{1}, …, b_{r} such that

Span(S) = Span{b_{1}, …, b_{r}},

and that x⊥S if and only if b_{i} · x = 0 for all i = 1, … r, which yields a system of linear equations. Since the vectors {b_{i}}_{i=1}^{r} are linearly independent, the rank of this system is r, so the dimension of the space of solutions is n − r by the fundamental theorem of the theory of systems of linear equations. But the space of solutions is precisely S^{⊥}. Corollary 3.38. If U ≤ F^{n}, then dim U + dim U^{⊥} = n. Proof:

dim U^{⊥} = n − dim Span U = n − dim U

Corollary 3.39. If U ≤ F^{n}, then U^{⊥⊥} = U.

Proof: As usual, a proof of equality between two sets has two parts:

• U ⊆ U^{⊥⊥} is obvious from the definition of ⊥.

• To check that a subspace is equal to the full vector space, it suffices to check that they

have the same dimension. Therefore, we compute:

dim U^{⊥⊥} = n − dim U^{⊥} = n − (n − dim U) = dim U.

Definition 3.40. U is a totally isotropic subspace of F^{n} if U⊥U. Example 3.41. The 1-dimensional subspace generated by the vector

( \begin{matrix}1 \\ i \end{matrix} )

in ℂ^{2} is isotropic. Corollary 3.42. If U is a totally isotropic subspace of bF^{n} then

dim U ≤ ⌊n/2⌋

Proof: Observe that U is a totally isotropic if and only if U ⊆ U^{⊥}, which implies that dim U ≤ dim U^{⊥}. Since dim U + dim U^{⊥} = n, we conclude that 2 dim U ≤ n. Corollary 3.43. If S ⊆ F^{n} and S⊥S, then

rk(S) ≤ ⌊n/2⌋.

Proof: Let U = Span(S). Since S⊥S implies that U⊥U, we may use the previous Corollary to conclude that rk S = dim U ≤ ⌊n/2⌋. Corollary 3.44. If S ⊆ 𝔽_{p}^{n} and S⊥S, then

rk(S) ≤ p^{⌊n/2⌋}.

We now return to Eventown. Recall that to each club C (which is a subset of {1, …, n}) we assigned an incidence vector v_{C} = (α_{1}, …, α_{n}) where

α_{i} = \begin{cases}1 & i ∈ C \\ 0 & i ∉ C \end{cases}

Note that v_{A} · v_{B} = |A ∩ B|, and that, in particular, v_{A} · v_{A} = |A|. This suggests that we consider our incidence vectors in a vector space over 𝔽_{2}, so that the rules of Eventown become:

1. v_{A} · v_{A} = 0 for any club A, and

2. v_{A} · v_{B} = 0 for any two clubs A and B.

In other words, if S ⊆ 𝔽_{2}^{n} is the set of incidence vectors of Eventown clubs, then S⊥S. We can now apply the previous results (Corollary 3.44) to conclude: Corollary 3.45.

|S| ≤ 2^{⌊n/2⌋}.

We observe that every maximal system of Eventown clubs corresponds to a totally isotropic subspace of 𝔽_{2}^{n}. Exercise 3.46. Prove that if U ≤ 𝔽_{2}^{n} is totally isotropic then there exists W ≤ 𝔽_{2}^{n} which is also totally isotropic such that U ≤ W and dim W = ⌊n/2⌋. Corollary 3.47. Every maximal Eventown system of clubs is maximum (i. e., it consists of 2^{⌊n/2⌋} clubs).

Notice the contrast with the result we proved for Oddtown. Exercise 3.48. Using the previous Corollary, prove that there exists a maximal Eventown system of clubs which is not the “married couple” solution.