Chapter 5

Linear Algebra

The exalted position held by linear algebra is based upon the subject’s ubiquitous utility and ease of application. The basic theory is developed here in full generality, i.e., modules are defined over an arbitrary ring R and not just over a field. The elementary facts about cosets, quotients, and homomorphisms follow the same pattern as in the chapters on groups and rings. We give a simple proof that if R is a commutative ring and f : R^{n} → R^{n} is a surjective R-module homomorphism, then f is an isomorphism. This shows that finitely generated free R-modules have a well defined dimension, and simplifies some of the development of linear algebra. It is in this chapter that the concepts about functions, solutions of equations, matrices, and generating sets come together in one unified theory.

After the general theory, we restrict our attention to vector spaces, i.e., modules over a field. The key theorem is that any vector space V has a free basis, and thus if V is finitely generated, it has a well defined dimension, and incredible as it may seem, this single integer determines V up to isomorphism. Also any endomorphism f : V → V may be represented by a matrix, and any change of basis corresponds to conjugation of that matrix. One of the goals in linear algebra is to select a basis so that the matrix representing f has a simple form. For example, if f is not injective, then f may be represented by a matrix whose first column is zero. As another example, if f is nilpotent, then f may be represented by a strictly upper triangular matrix. The theorem on Jordan canonical form is not proved in this chapter, and should not be considered part of this chapter. It is stated here in full generality only for reference and completeness. The proof is given in the Appendix. This chapter concludes with the study of real inner product spaces, and with the beautiful theory relating orthogonal matrices and symmetric matrices.

Definition Suppose R is a ring and M is an additive abelian group. The statement that M is a right R-module means there is a scalar multiplication

M × R → M satisfying (a_{1} + a_{2})r = a_{1}r + a_{2}r
(m, r) → mr a(r_{1} + r_{2}) = ar_{1} + ar_{2}
a(r_{1} · r_{2}) = (ar_{1})r_{2}
a¯1 = a

for all a, a_{1}, a_{2} ∈ M and r, r_{1}, r_{2} ∈ R.

The statement that M is a left R-module means there is a scalar multiplication

R × M → M satisfying r(a_{1} + a_{2}) = ra_{1} + ra_{2} (r, m) → rm (r_{1} + r_{2})a = r_{1}a + r_{2}a

(r_{1} · r_{2})a = r_{1}(r_{2}a)
¯1a = a

Note that the plus sign is used ambiguously, as addition in M and as addition in R.

Notation The fact that M is a right (left) R-module will be denoted by M = M_{R} (M = _{R}M). If R is commutative and M = M_{R} then left scalar multiplication defined by ra = ar makes M into a left R-module. Thus for commutative rings, we may write the scalars on either side. In this text we stick to right R-modules.

Convention Unless otherwise stated, it is assumed that R is a ring and the word “R-module” (or sometimes just “module”) means “right R-module”.

Theorem Suppose M is an R-module.

1) If r ∈ R, then f : M → M defined by f(a) = ar is a homomorphism of additive groups. In particular (¯0_{M})r = ¯0_{M}.

2) If a ∈ M, a¯0_{R} = ¯0_{M}.
3) If a ∈ M and r ∈ R, then (−a)r = −(ar) = a(−r).

Proof This is a good exercise in using the axioms for an R-module.

Submodules If M is an R-module, the statement that a subset N ⊂ M is a submodule means it is a subgroup which is closed under scalar multiplication, i.e., if a ∈ N and r ∈ R, then ar ∈ N. In this case N will be an R-module because the axioms will automatically be satisfied. Note that ¯0 and M are submodules, called the improper submodules of M.

Theorem Suppose M is an R-module, T is an index set, and for each t ∈ T, N_{t} is a submodule of M.

1) ⋂_{t∈T}N_{t} is a submodule of M.
2) If {N_{t}} is a monotonic collection, ⋃_{t∈T} N_{t} is a submodule.
3) +_{t∈T} N_{t} = {all finite sums a_{1} + · · +a_{m}: each a_{i} belongs

to some N_{t}} is a submodule. If T = {1, 2, .., n}, then this submodule may be written as N_{1} + N_{2} + · · +N_{n} = {a_{1} + a_{2} + · · +a_{n} : each a_{i} ∈ N_{i}}.

Proof We know from page 22 that versions of 1) and 2) hold for subgroups, and in particular for subgroups of additive abelian groups. To finish the proofs it is only necessary to check scalar multiplication, which is immediate. Also the proof of 3) is immediate. Note that if N_{1} and N_{2} are submodules of M, N_{1} + N_{2} is the smallest submodule of M containing N_{1} ∪ N_{2}.

Exercise Suppose T is a non-void set, N is an R-module, and N^{T} is the collection of all functions f : T → N with addition defined by (f +g)(t) = f(t)+g(t), and scalar multiplication defined by (fr)(t) = f(t)r. Show N^{T} is an R-module. (We know from the last exercise in Chapter 2 that N^{T} is a group, and so it is only necessary to check scalar multiplication.) This simple fact is quite useful in linear algebra. For example, in 5) of the theorem below, it is stated that Hom_{R}(M, N) forms an abelian group. So it is only necessary to show that Hom_{R}(M, N) is a subgroup of N^{M}. Also in 8) it is only necessary to show that Hom_{R}(M, N) is a submodule of N^{M}.

Homomorphisms

Suppose M and N are R-modules. A function f : M → N is a homomorphism (i.e., an R-module homomorphism) provided it is a group homomorphism and if a ∈ M and r ∈ R, f(ar) = f(a)r. On the left, scalar multiplication is in M and on the right it is in N. The basic facts about homomorphisms are listed below. Much of this work has already been done in the chapter on groups (see page 28).

Theorem

1) The zero map M → N is a homomorphism.

2) The identity map I : M → M is a homomorphism.

3) The composition of homomorphisms is a homomorphism.

4) The sum of homomorphisms is a homomorphism. If f, g : M → N are homomorphisms, define (f + g) : M → N by (f + g)(a) = f(a) + g(a). Then f + g is a homomorphism. Also (−f) defined by (−f)(a) = −f(a) is a homomorphism. If h : N → P is a homomorphism, h ∘ (f + g) = (h ∘ f) + (h ∘ g). If k : P → M is a homomorphism, (f + g) ∘ k = (f ∘ k) + (g ∘ k).

5) Hom_{R}(M, N) = Hom(M_{R}, N_{R}), the set of all homomorphisms from M to N, forms an abelian group under addition. Hom_{R}(M, M), with multiplication defined to be composition, is a ring.

6) If a bijection f : M → N is a homomorphism, then f^{−1} : N → M is also a homomorphism. In this case f and f^{−1} are called isomorphisms. A homomorphism f : M → M is called an endomorphism. An isomorphism f : M → M is called an automorphism. The units of the endomorphism ring Hom_{R}(M, M) are the automorphisms. Thus the automorphisms on M form a group under composition. We will see later that if M = R^{n}, Hom_{R}(R^{n}, R^{n}) is just the matrix ring R_{n} and the automorphisms are merely the invertible matrices.

7) If R is commutative and r ∈ R, then g : M → M defined by g(a) = ar is a homomorphism. Furthermore, if f : M → N is a homomorphism, fr defined by (fr)(a) = f(ar) = f(a)r is a homomorphism.

8) If R is commutative, Hom_{R}(M, N) is an R-module.

9) Suppose f : M → N is a homomorphism, G ⊂ M is a submodule, and H ⊂ N is a submodule. Then f(G) is a submodule of N and f^{−1}(H) is a submodule of M. In particular, image(f) is a submodule of N and ker(f) = f^{−1}(¯0) is a submodule of M.

Proof This is just a series of observations.

Abelian groups are Z-modules On page 21, it is shown that any additive group M admits a scalar multiplication by integers, and if M is abelian, the properties are satisfied to make M a Z-module. Note that this is the only way M can be a Zmodule, because a1 = a, a2 = a + a, etc. Furthermore, if f : M → N is a group homomorphism of abelian groups, then f is also a Z-module homomorphism.

Summary Additive abelian groups are “the same things” as Z-modules. While group theory in general is quite separate from linear algebra, the study of additive abelian groups is a special case of the study of R-modules.

Exercise R-modules are also Z-modules and R-module homomorphisms are also Z-module homomorphisms. If M and N are Q-modules and f : M → N is a Z-module homomorphism, must it also be a Q-module homomorphism?

Homomorphisms on R^{n}

R^{n} as an R-module On page 54 it was shown that the additive abelian group R_{m,n} admits a scalar multiplication by elements in R. The properties listed there were exactly those needed to make R_{m,n} an R-module. Of particular importance is the case R^{n} = R ⊕ · · ⊕R = R_{n,1} (see page 53). We begin with the case n = 1.

R as a right R-module Let M = R and define scalar multiplication on the right by ar = a · r. That is, scalar multiplication is just ring multiplication. This makes R a right R-module denoted by R_{R} (or just R). This is the same as the definition before for R^{n} when n = 1.

Theorem Suppose R is a ring and N is a subset of R. Then N is a submodule of R_{R} (_{R}R) iff N is a right (left) ideal of R.

Proof The definitions are the same except expressed in different language.

Theorem Suppose M = M_{R} and f, g : R → M are homomorphisms with f(¯1) = g(¯1). Then f = g. Furthermore, if m ∈ M, ∃! homomorphism h : R → M with h(¯1) = m. In other words, Hom_{R}(R, M) ≈ M.

Proof Suppose f(¯1) = g(¯1). Then f(r) = f(¯1 · r) = f(¯1)r = g(¯1)r = g(¯1 · r) = g(r). Given m ∈ M, h : R → M defined by h(r) = mr is a homomorphism. Thus evaluation at ¯1 gives a bijection from Hom_{R}(R, M) to M, and this bijection is clearly a group isomorphism. If R is commutative, it is an isomorphism of R-modules.

In the case M = R, the above theorem states that multiplication on left by some m ∈ R defines a right R-module homomorphism from R to R, and every module homomorphism is of this form. The element m should be thought of as a 1 × 1 matrix. We now consider the case where the domain is R^{n}.

Homomorphisms on R^{n} Define e_{i} ∈ R^{n} by e_{i} = ( ¯0 ; · ; ¯1_{i} ; · ; ¯0 ). Note that any ( \begin{matrix}r_{1} \\ · \\ · \\ r_{n} \end{matrix} )

can be written uniquely as e_{1}r_{1} + · · +e_{n}r_{n}. The sequence {e_{1}, .., e_{n}} is called the canonical free basis or standard basis for R^{n}.

Theorem Suppose M = M_{R} and f, g : R^{n} → M are homomorphisms with f(e_{i}) = g(e_{i}) for 1 ≤ i ≤ n. Then f = g. Furthermore, if m_{1}, m_{2}, ..., m_{n} ∈ M, ∃! homomorphism h : R^{n} → M with h(e_{i}) = m_{i} for 1 ≤ i ≤ m. The homomorphism h is defined by h(e_{1}r_{1} + · · +e_{n}r_{n}) = m_{1}r_{1} + · · +m_{n}r_{n}.

Proof The proof is straightforward. Note this theorem gives a bijection from Hom_{R}(R^{n}, M) to M^{n} = M × M × · · ×M and this bijection is a group isomorphism. We will see later that the product M^{n} is an R-module with scalar multiplication defined by (m_{1}, m_{2}, .., m_{n})r = (m_{1}r, m_{2}r, .., m_{n}r). If R is commutative so that Hom_{R}(R^{n}, M) is an R-module, this theorem gives an R-module isomorphism from Hom_{R}(R^{n}, M) to M^{n}.

This theorem reveals some of the great simplicity of linear algebra. It does not matter how complicated the ring R is, or which R-module M is selected. Any R-module homomorphism from R^{n} to M is determined by its values on the basis, and any function from that basis to M extends uniquely to a homomorphism from R^{n} to M.

Exercise Suppose R is a field and f : R_{R} → M is a non-zero homomorphism. Show f is injective.

Now let’s examine the special case M = R^{m} and show Hom_{R}(R^{n}, R^{m}) ≈ R_{m,n}.

Theorem Suppose A = (a_{i,j}) ∈ R_{m,n}. Then f : R^{n} → R^{m} defined by f(B) = AB is a homomorphism with f(e_{i}) = column i of A. Conversely, if v_{1}, …, v_{n} ∈ R^{m}, define A ∈ R_{m,n} to be the matrix with column i = v_{i}. Then f defined by f(B) = AB is the unique homomorphism from R^{n} to R^{m} with f(e_{i}) = v_{i}.

Even though this follows easily from the previous theorem and properties of matrices, it is one of the great classical facts of linear algebra. Matrices over R give R-module homomorphisms! Furthermore, addition of matrices corresponds to addition of homomorphisms, and multiplication of matrices corresponds to composition of homomorphisms. These properties are made explicit in the next two theorems.

Theorem If f, g : R^{n} → R^{m} are given by matrices A, C ∈ R_{m,n}, then f + g is given by the matrix A+C. Thus Hom_{R}(R^{n}, R^{m}) and R_{m,n} are isomorphic as additive groups. If R is commutative, they are isomorphic as R-modules.

Theorem If f: R^{n} → R^{m} is the homomorphism given by A ∈ R_{m,n} and g : R^{m} → R^{p} is the homomorphism given by C ∈ R_{p,m}, then g ∘ f : R^{n} → R^{p} is given by CA ∈ R_{p,n}. That is, composition of homomorphisms corresponds to multiplication of matrices.

Proof This is just the associative law of matrix multiplication, C(AB) = (CA)B.

The previous theorem reveals where matrix multiplication comes from. It is the matrix which represents the composition of the functions. In the case where the domain and range are the same, we have the following elegant corollary.

Corollary Hom_{R}(R^{n}, R^{n}) and R_{n} are isomorphic as rings. The automorphisms correspond to the invertible matrices.

This corollary shows one way non-commutative rings arise, namely as endomorphism rings. Even if R is commutative, R_{n} is never commutative unless n = 1.

We now return to the general theory of modules (over some given ring R).

Cosets and Quotient Modules

After seeing quotient groups and quotient rings, quotient modules go through without a hitch. As before, R is a ring and module means R-module.

Theorem Suppose M is a module and N ⊂ M is a submodule. Since N is a normal subgroup of M, the additive abelian quotient group M/N is defined. Scalar multiplication defined by (a + N)r = (ar + N) is well-defined and gives M/N the structure of an R-module. The natural projection π : M → M/N is a surjective homomorphism with kernel N. Furthermore, if f : M → M̄ is a surjective homomorphism with ker(f) = N, then M/N ≈ M̄ (see below).

Proof On the group level, this is all known from Chapter 2 (see pages 27 and 29). It is only necessary to check the scalar multiplication, which is obvious.

The relationship between quotients and homomorphisms for modules is the same as for groups and rings, as shown by the next theorem.

Theorem Suppose f : M → M̄ is a homomorphism and N is a submodule of M. If N ⊂ ker(f), then f̄: (M/N) → M̄ defined by f̄(a + N) = f(a) is a well-defined homomorphism making the following diagram commute.

[figure: M; M̄; M/N; f; π; f̄]

Thus defining a homomorphism on a quotient module is the same as defining a homomorphism on the numerator that sends the denominator to ¯0. The image of f̄ is the image of f, and the kernel of f̄ is ker(f)/N. Thus if N = ker(f), f̄ is injective, and thus (M/N) ≈ image(f). Therefore for any homomorphism f, (domain(f)/ker(f)) ≈ image(f).

Proof On the group level this is all known from Chapter 2 (see page 29). It is only necessary to check that f̄ is a module homomorphism, and this is immediate.

Theorem Suppose M is an R-module and K and L are submodules of M.

i) The natural homomorphism K → (K + L)/L is surjective with kernel K ∩ L. Thus (K/K ∩ L) →^{≈} (K + L)/L is an isomorphism.

ii) Suppose K ⊂ L. The natural homomorphism M/K → M/L is surjective with kernel L/K. Thus (M/K)/(L/K) →^{≈} M/L is an isomorphism.

Examples These two examples are for the case R = Z, i.e., for abelian groups.

1) M = Z K = 3Z L = 5Z K ∩ L = 15Z K + L = Z
K/K ∩ L = 3Z/15Z ≈ Z/5Z = (K + L)/L
2) M = Z K = 6Z L = 3Z (K ⊂ L)
(M/K)/(L/K) = (Z/6Z)/(3Z/6Z) ≈ Z/3Z = M/L

Products and Coproducts

Infinite products work fine for modules, just as they do for groups and rings. This is stated below in full generality, although the student should think of the finite case. In the finite case something important holds for modules that does not hold for non-abelian groups or rings – namely, the finite product is also a coproduct. This makes the structure of module homomorphisms much more simple. For the finite case we may use either the product or sum notation, i.e., M_{1} × M_{2} × · · ×M_{n} = M_{1} ⊕ M_{2} ⊕ · · ⊕M_{n}.

Theorem Suppose T is an index set and for each t ∈ T, M_{t} is an R-module. On the additive abelian group ∏_{t∈T} M_{t} = ∏ M_{t} define scalar multiplication by {m_{t}}r =

{m_{t}r}. Then ∏ M_{t} is an R-module and, for each s ∈ T, the natural projection π_{s} : ∏ M_{t} → M_{s} is a homomorphism. Suppose M is a module. Under the natural 1-1 correspondence from {functions f : M → ∏ M_{t}} to {sequence of functions {f_{t}}_{t∈T} where f_{t} : M → M_{t}}, f is a homomorphism iff each f_{t} is a homomorphism.

Proof We already know from Chapter 2 that f is a group homomorphism iff each f_{t} is a group homomorphism. Since scalar multiplication is defined coordinatewise, f is a module homomorphism iff each f_{t} is a module homomorphism.

Definition If T is finite, the coproduct and product are the same module. If T is infinite, the coproduct or sum ∐_{t∈T} M_{t} = ⨁_{t∈T} M_{t} = ⊕M_{t} is the submodule of ∏ M_{t}

consisting of all sequences {m_{t}} with only a finite number of non-zero terms. For each s ∈ T, the inclusion homomorphisms i_{s} : M_{s} → ⊕M_{t} is defined by i_{s}(a) = {a_{t}} where a_{t} = ¯0 if t ≠ s and a_{s} = a. Thus each M_{s} may be considered to be a submodule of ⊕M_{t}.

Theorem Suppose M is an R-module. There is a 1-1 correspondence from {homomorphisms g : ⊕M_{t} → M} and {sequences of homomorphisms {g_{t}}_{t∈T} where g_{t} : M_{t} → M} . Given g, g_{t} is defined by g_{t} = g ∘ i_{t}. Given {g_{t}}, g is defined by g({m_{t}}) = ∑_{t} g_{t}(m_{t}). Since there are only a finite number of non-zero terms, this

sum is well defined.

For T = {1, 2} the product and sum properties are displayed in the following commutative diagrams.

[figure: M_{1} ⊕ M_{2}; M_{1}; M_{2}; M_{1}; M_{2}; M_{1} ⊕ M_{2}; M; M; π_{1}; i_{1}; π_{2}; i_{2}; f; g; f_{1}; f_{2}; g_{1}; g_{2}]

Theorem For finite T, the 1-1 correspondences in the above theorems actually produce group isomorphisms. If R is commutative, they give isomorphisms of Rmodules.

Hom_{R}(M, M_{1} ⊕ · · ⊕M_{n}) ≈ Hom_{R}(M, M_{1}) ⊕ · · ⊕Hom_{R}(M, M_{n}) and

Hom_{R}(M_{1} ⊕ · · ⊕M_{n}, M) ≈ Hom_{R}(M_{1}, M) ⊕ · · ⊕Hom_{R}(M_{n}, M)

Proof Let’s look at this theorem for products with n = 2. All it says is that if f = (f_{1}, f_{2}) and h = (h_{1}, h_{2}), then f + h = (f_{1} + h_{1}, f_{2} + h_{2}). If R is commutative, so that the objects are R-modules and not merely additive groups, then the isomorphisms are module isomorphisms. This says merely that fr = (f_{1}, f_{2})r = (f_{1}r, f_{2}r).

Exercise Suppose M and N are R-modules. Show that M ⊕ N is isomorphic to N ⊕ M. Now suppose A ⊂ M, B ⊂ N are submodules and show (M ⊕ N)/(A ⊕ B) is isomorphic to (M/A) ⊕ (N/B). In particular, if a ∈ R and b ∈ R, then (R ⊕ R)/(aR ⊕ bR) is isomorphic to (R/aR) ⊕ (R/bR). For example, the abelian group (Z ⊕ Z)/(2Z ⊕ 3Z) is isomorphic to Z_{2} ⊕ Z_{3}. These isomorphisms are transparent and are used routinely in algebra without comment (see Th 4, page 118).

Exercise Suppose R is a commutative ring, M is an R-module, and n ≥ 1. Define a function α : Hom_{R}(R^{n}, M) → M^{n} which is a R-module isomorphism.

Summands

One basic question in algebra is “When does a module split as the sum of two modules?”. Before defining summand, here are two theorems for background.

Theorem Consider M_{1} = M_{1}⊕¯0 as a submodule of M_{1}⊕M_{2}. Then the projection map π_{2} : M_{1} ⊕ M_{2} → M_{2} is a surjective homomorphism with kernel M_{1}. Thus (M_{1} ⊕ M_{2})/M_{1} is isomorphic to M_{2}. (See page 35 for the group version.)

This is exactly what you would expect, and the next theorem is almost as intuitive.

Theorem Suppose K and L are submodules of M and f : K ⊕ L → M is the natural homomorphism, f(k, l) = k + l. Then the image of f is K + L and the kernel of f is {(a, −a) : a ∈ K ∩ L}. Thus f is an isomorphism iff K + L = M and K ∩ L = ¯0. In this case we write K ⊕ L = M. This abuse of notation allows us to avoid talking about “internal” and “external” direct sums.

Definition Suppose K is a submodule of M. The statement that K is a summand of M means ∃ a submodule L of M with K ⊕ L = M. According to the previous theorem, this is the same as there exists a submodule L with K + L = M and K ∩ L = ¯0. If such an L exists, it need not be unique, but it will be unique up to isomorphism, because L ≈ M/K. Of course, M and ¯0 are always summands of M.

Exercise Suppose M is a module and K = {(m, m) : m ∈ M} ⊂ M ⊕ M. Show K is a submodule of M ⊕ M which is a summand.

Exercise R is a module over Q, and Q ⊂ R is a submodule. Is Q a summand of R? With the material at hand, this is not an easy question. Later on, it will be easy.

Exercise Answer the following questions about abelian groups, i.e., Z-modules. (See the third exercise on page 35.)

1) Is 2Z a summand of Z?

2) Is 2Z_{4} a summand of Z_{4}?

3) Is 3Z_{12} a summand of Z_{12}?

4) Suppose m, n > 1. When is nZ_{mn} a summand of Z_{mn}?

Exercise If T is a ring, define the center of T to be the subring {t : ts = st for all s ∈ T }. Let R be a commutative ring and T = R_{n}. There is a exercise on page 57 to show that the center of T is the subring of scalar matrices. Show R^{n} is a left T -module and find Hom_{T} (R^{n}, R^{n}).

Independence, Generating Sets, and Free Basis

This section is a generalization and abstraction of the brief section Homomorphisms on R^{n}. These concepts work fine for an infinite index set T because linear combination means finite linear combination. However, to avoid dizziness, the student should first consider the case where T is finite.

Definition Suppose M is an R-module, T is an index set, and for each t ∈ T, s_{t} ∈ M. Let S be the sequence {s_{t}}_{t∈T} = {s_{t}}. The statement that S is dependent means ∃ a finite number of distinct elements t_{1}, ..., t_{n} in T, and elements r_{1}, .., r_{n} in R, not all zero, such that the linear combination s_{t_{1}}r_{1} + · · +s_{t_{n}}r_{n} = ¯0. Otherwise, S is independent. Note that if some s_{t} = ¯0, then S is dependent. Also if ∃ distinct elements t_{1} and t_{2} in T with s_{t_{1}} = s_{t_{2}}, then S is dependent.

Let SR be the set of all linear combinations s_{t_{1}}r_{1} + · · +s_{t_{n}}r_{n}. SR is a submodule of M called the submodule generated by S. If S is independent and generates M, then S is said to be a basis or free basis for M. In this case any v ∈ M can be written uniquely as a linear combination of elements in S. An R-module M is said to be a free R-module if it is zero or if it has a basis. The next two theorems are obvious, except for the confusing notation. You might try first the case T = {1, 2, ..., n} and ⊕R_{t} = R^{n} (see p 72).

Theorem For each t ∈ T, let R_{t} = R_{R} and for each c ∈ T, let e_{c} ∈ ⊕R_{t} = ⨁_{t∈T} R_{t}

be e_{c} = {r_{t}} where r_{c} = l̄ and r_{t} = ¯0 if t ≠ c. Then {e_{c}}_{c∈T} is a basis for ⊕R_{t} called the canonical basis or standard basis.

Theorem Suppose N is an R-module and M is a free R-module with a basis {s_{t}}. Then ∃ a 1-1 correspondence from the set of all functions g:{s_{t}} → N and the set of all homomorphisms f : M → N. Given g, define f by f(s_{t_{1}}r_{1} + · · +s_{t_{n}}r_{n}) = g(s_{t_{1}})r_{1} + · · +g(s_{t_{n}})r_{n}. Given f, define g by g(s_{t}) = f(s_{t}). In other words, f is completely determined by what it does on the basis S, and you are “free” to send the basis any place you wish and extend to a homomorphism.

Recall that we have already had the preceding theorem in the case S is the canonical basis for M = R^{n} (p 72). The next theorem is so basic in linear algebra that it is used without comment. Although the proof is easy, it should be worked carefully.

Theorem Suppose N is a module, M is a free module with basis S = {s_{t}}, and f : M → N is a homomorphism. Let f(S) be the sequence {f(s_{t})} in N.

1) f(S) generates N iff f is surjective.

2) f(S) is independent in N iff f is injective.

3) f(S) is a basis for N iff f is an isomorphism.

4) If h : M → N is a homomorphism, then f = h iff f | S = h | S.

Exercise Let (A_{1}, .., A_{n}) be a sequence of n vectors with each A_{i} ∈ Z^{n}. Show this sequence is linearly independent over Z iff it is linearly independent over Q. Is it true the sequence is linearly independent over Z iff it is linearly independent over R? This question is difficult until we learn more linear algebra.

Characterization of Free Modules

Any free R-module is isomorphic to one of the canonical free R-modules ⊕R_{t}. This is just an observation, but it is a central fact in linear algebra.

Theorem A non-zero R-module M is free iff ∃ an index set T such that M ≈ ⨁_{t∈T} R_{t}. In particular, M has a finite free basis of n elements iff M ≈ R^{n}.

Proof If M is isomorphic to ⊕R_{t} then M is certainly free. So now suppose M has a free basis {s_{t}}. Then the homomorphism f : M → ⊕R_{t} with f(s_{t}) = e_{t} sends the basis for M to the canonical basis for ⊕R_{t}. By 3) in the preceding theorem, f is an isomorphism.

Exercise Suppose R is a commutative ring, A ∈ R_{n}, and the homomorphism f : R^{n} → R^{n} defined by f(B) = AB is surjective. Show f is an isomorphism, i.e., show A is invertible. This is a key theorem in linear algebra, although it is usually stated only for the case where R is a field. Use the fact that {e_{1}, .., e_{n}} is a free basis for R^{n}.

The next exercise is routine, but still informative.

Exercise Let R = Z, A = ( \begin{matrix}2 & 1 & 0 \\ 3 & 2 & −5 \end{matrix} ) and f: Z^{3} → Z^{2} be the group homo-

morphism defined by A. Find a non-trivial linear combination of the columns of A which is ¯0. Also find a non-zero element of kernel(f).

If R is a commutative ring, you can relate properties of R as an R-module to properties of R as a ring.

Exercise Suppose R is a commutative ring and v ∈ R, v ≠ ¯0.

1) v is independent iff v is .

2) v is a basis for R iff v generates R iff v is .

Note that 2) here is essentially the first exercise for the case n = 1. That is, if f : R → R is a surjective R-module homomorphism, then f is an isomorphism.

Relating these concepts to matrices

The theorem stated below gives a summary of results we have already had. It shows that certain concepts about matrices, linear independence, injective homomorphisms, and solutions of equations, are all the same — they are merely stated in different language. Suppose A ∈ R_{m,n} and f : R^{n} → R^{m} is the homomorphism associated with A, i.e., f(B) = AB. Let v_{1}, .., v_{n} ∈ R^{m} be the columns of A, i.e., f(e_{i}) = v_{i}

= column i of A. Let B = ( \begin{matrix}b_{1} \\ . \\ b_{n} \end{matrix} ) represent an element of R^{n} and C = ( \begin{matrix}c_{1} \\ . \\ c_{m} \end{matrix} )

Chapter 5 Linear Algebra 81

represent an element of R^{m}.

Theorem

1) The element f(B) is a linear combination of the columns of A, that is f(B) = f(e_{1}b_{1} + · · +e_{n}b_{n}) = v_{1}b_{1} + · · +v_{n}b_{n}. Thus the image of f is generated by the columns of A. (See bottom of page 89.)

2) {v_{1}, .., v_{n}} generates R^{m} iff f is surjective iff (for any C ∈ R^{m}, AX = C has a solution).

3) {v_{1}, .., v_{n}} is independent iff f is injective iff AX = ¯0 has a unique solution iff (∃ C ∈ R^{m} such that AX = C has a unique solution).

4) {v_{1}, .., v_{n}} is a basis for R^{m} iff f is an isomorphism iff (for any C ∈ R^{m}, AX = C has a unique solution).

Relating these concepts to square matrices

We now look at the preceding theorem in the special case where n = m and R is a commutative ring. So far in this chapter we have just been cataloging. Now we prove something more substantial, namely that if f : R^{n} → R^{n} is surjective, then f is injective. Later on we will prove that if R is a field, injective implies surjective.

Theorem Suppose R is a commutative ring, A ∈ R_{n}, and f : R^{n} → R^{n} is defined by f(B) = AB. Let v_{1}, .., v_{n} ∈ R^{n} be the columns of A, and w_{1}, .., w_{n} ∈ R^{n} = R_{1,n} be the rows of A. Then the following are equivalent.

1) f is an automorphism.

2) A is invertible, i.e., | A | is a unit in R.

3) {v_{1}, .., v_{n}} is a basis for R^{n}.

4) {v_{1}, .., v_{n}} generates R^{n}.

5) f is surjective. 2^{t}) A^{t} is invertible, i.e., | A^{t} | is a unit in R. 3^{t}) {w_{1}, .., w_{n}} is a basis for R^{n}.

4^{t}) {w_{1}, .., w_{n}} generates R^{n}.

Proof Suppose 5) is true and show 2). Since f is onto, ∃ u_{1}, ..., u_{n} ∈ R^{n} with f(u_{i}) = e_{i}. Let g : R^{n} → R^{n} be the homomorphism satisfying g(e_{i}) = u_{i}. Then f ∘ g is the identity. Now g comes from some matrix D and thus AD = I. This shows that A has a right inverse and is thus invertible. Recall that the proof of this fact uses determinant, which requires that R be commutative (see the exercise on page 64).

We already know the first three properties are equivalent, 4) and 5) are equivalent, and 3) implies 4). Thus the first five are equivalent. Furthermore, applying this result to A^{t} shows that the last three properties are equivalent to each other. Since | A |=| A^{t} |, 2) and 2^{t}) are equivalent.

Uniqueness of Dimension

There exists a ring R with R^{2} ≈ R^{3} as R-modules, but this is of little interest. If R is commutative, this is impossible, as shown below. First we make a convention.

Convention For the remainder of this chapter, R will be a commutative ring.

Theorem If f : R^{m} → R^{n} is a surjective R-module homomorphism, then m ≥ n.

Proof Suppose k = n − m is positive. Define h : (R^{m} ⊕ R^{k} = R^{n}) → R^{n} by h(u, v) = f(u). Then h is a surjective homomorphism, and by the previous section, also injective. This is a contradiction and thus m ≥ n.

Corollary If f : R^{m} → R^{n} is an isomorphism, then m = n.

Proof Each of f and f^{−1} is surjective, so m = n by the previous theorem.

Corollary If {v_{1}, .., v_{m}} generates R^{n}, then m ≥ n.

Proof The hypothesis implies there is a surjective homomorphism R^{m} → R^{n}. So this follows from the first theorem.

Lemma Suppose M is a f.g. module (i.e., a finite generated R-module). Then if M has a basis, that basis is finite.

Proof Suppose U ⊂ M is a finite generating set and S is a basis. Then any element of U is a finite linear combination of elements of S, and thus S is finite.

Theorem Suppose M is a f.g. module. If M has a basis, that basis is finite and any other basis has the same number of elements. This number is denoted by dim(M), the dimension of M. (By convention, ¯0 is a free module of dimension 0.)

Proof By the previous lemma, any basis for M must be finite. M has a basis of n elements iff M ≈ R^{n}. The result follows because R^{n} ≈ R^{m} iff n = m.

Change of Basis

Before changing basis, we recall what a basis is. Previously we defined generating, independence, and basis for sequences, not for collections. For the concept of generating it matters not whether you use sequences or collections, but for independence and basis, you must use sequences. Consider the columns of the real matrix

A = ( \begin{matrix}2 & 3 & 2 \\ 1 & 4 & 1 \end{matrix} ). If we consider the column vectors of A as a collection, there are

only two of them, yet we certainly don’t wish to say the columns of A form a basis for R^{2}. In a set or collection, there is no concept of repetition. In order to make sense, we must consider the columns of A as an ordered triple of vectors, and this sequence is dependent. In the definition of basis on page 78, basis is defined for sequences, not for sets or collections.

Two sequences cannot begin to be equal unless they have the same index set. Here we follow the classical convention that an index set with n elements will be {1, 2, .., n}, and thus a basis for M with n elements is a sequence S = {u_{1}, .., u_{n}} or if you wish, S = (u_{1}, .., u_{n}) ∈ M^{n}. Suppose M is an R-module with a basis of n elements. Recall there is a bijection α: Hom_{R}(R^{n}, M) → M^{n} defined by α(h) = (h(e_{1}), .., h(e_{n})). Now h : R^{n} → M is an isomorphism iff α(h) is a basis for M.

Summary The point of all this is that selecting a basis of n elements for M is the same as selecting an isomorphism from R^{n} to M, and from this viewpoint, change of basis can be displayed by the diagram below.

Endomorphisms on R^{n} are represented by square matrices, and thus have a determinant and trace. Now suppose M is a f.g. free module and f : M → M is a homomorphism. In order to represent f by a matrix, we must select a basis for M (i.e., an isomorphism with R^{n}). We will show that this matrix is well defined up to similarity, and thus the determinant, trace, and characteristic polynomial of f are well-defined.

Definition Suppose M is a free module, S = {u_{1}, .., u_{n}} is a basis for M, and f : M → M is a homomorphism. The matrix A = (a_{i,j}) ∈ R_{n} of f w.r.t. the basis S is defined by f(u_{i}) = u_{1}a_{1,i} + · · +u_{n}a_{n,i}. (Note that if M = R^{n} and u_{i} = e_{i}, A is the usual matrix associated with f).

Theorem Suppose T = {v_{1}, .., v_{n}} is another basis for M and B ∈ R_{n} is the matrix of f w.r.t. T. Define C = (c_{i,j}) ∈ R_{n} by v_{i} = u_{1}c_{1,i} + · · +u_{n}c_{n,i}. Then C is invertible and B = C^{−1}AC, i.e., A and B are similar. Therefore |A| = |B|, trace(A)=trace(B), and A and B have the same characteristic polynomial (see page 66 of chapter 4).

Conversely, suppose C = (c_{i,j}) ∈ R_{n} is invertible. Define T = {v_{1}, .., v_{n}} by v_{i} = u_{1}c_{1,i} + · · +u_{n}c_{n,i}. Then T is a basis for M and the matrix of f w.r.t. T is B = C^{−1}AC. In other words, conjugation of matrices corresponds to change of basis.

Proof The proof follows by seeing that the following diagram is commutative.

[figure: R^{n}; R^{n}; R^{n}; R^{n}; M; M; C; C; A; B; ≈; ≈; ≈; ≈; ≈; ≈; e_{i}; v_{i}; e_{i}; u_{i}; v_{i}; e_{i}; u_{i}; e_{i}; f]

The diagram also explains what it means for A to be the matrix of f w.r.t. the basis S. Let h : R^{n} → M be the isomorphism with h(e_{i}) = u_{i} for 1 ≤ i ≤ n. Then the matrix A ∈ R_{n} is the one determined by the endomorphism h^{−1} ∘f ∘h : R^{n} → R^{n}. In other words, column i of A is h^{−1}(f(h(e_{i}))).

An important special case is where M = R^{n} and f : R^{n} → R^{n} is given by some matrix W. Then h is given by the matrix U whose i^{th} column is u_{i} and A = U^{−1}W U. In other words, W represents f w.r.t. the standard basis, and U^{−1}W U represents f w.r.t. the basis {u_{1}, .., u_{n}}.

Definition Suppose M is a f.g. free module and f : M → M is a homomorphism. Define |f| to be |A|, trace(f) to be trace(A), and CP_{f}(x) to be CP_{A}(x), where A is the matrix of f w.r.t. some basis. By the previous theorem, all three are well-defined, i.e., do not depend upon the choice of basis.

Exercise Let R = Z and f : Z^{2} → Z^{2} be defined by f(D) = ( \begin{matrix}3 & 3 \\ 0 & −1 \end{matrix} ) D.

Find the matrix of f w.r.t. the basis \{( \begin{matrix}2 \\ 1 \end{matrix} ) , ( \begin{matrix}3 \\ 1 \end{matrix} )\}.

Exercise Let L ⊂ R^{2} be the line L = {(r, 2r)^{t} : r ∈ R}. Show there is one and only one homomorphism f : R^{2} → R^{2} which is the identity on L and has f((−1, 1)^{t}) = (1, −1)^{t}. Find the matrix A ∈ R_{2} which represents f with respect to the basis {(1, 2)^{t}, (−1, 1)^{t}}. Find the determinant, trace, and characteristic polynomial of f. Also find the matrix B ∈ R_{2} which represents f with respect to the standard basis. Finally, find an invertible matrix C ∈ R_{2} with B = C^{−1}AC.

Vector Spaces

So far in this chapter we have been developing the theory of linear algebra in general. The previous theorem, for example, holds for any commutative ring R, but it must be assumed that the module M is free. Endomorphisms in general will not have a determinant, trace, or characteristic polynomial. We now focus on the case where R is a field F, and show that in this case, every F -module is free. Thus any finitely generated F -module will have a well-defined dimension, and endomorphisms on it will have well-defined determinant, trace, and characteristic polynomial.

In this section, F is a field. F -modules may also be called vector spaces and F -module homomorphisms may also be called linear transformations.

Theorem Suppose M is an F -module and v ∈ M. Then v ≠ ¯0 iff v is independent. That is, if v ∈ V and r ∈ F, vr = ¯0 implies v = ¯0 in M or r = ¯0 in F.

Proof Suppose vr = ¯0 and r ≠ ¯0. Then ¯0= (vr)r^{−1} = v¯1 = v.

Theorem Suppose M ≠ ¯0 is an F -module and v ∈ M. Then v generates M iff v is a basis for M. Furthermore, if these conditions hold, then M ≈ F_{F}, any non-zero element of M is a basis, and any two elements of M are dependent.

Proof Suppose v generates M. Then v ≠ ¯0 and is thus independent by the previous theorem. In this case M ≈ F, and any non-zero element of F is a basis, and any two elements of F are dependent.

Theorem Suppose M ≠ ¯0 is a finitely generated F -module. If S = {v_{1}, .., v_{m}} generates M, then any maximal independent subsequence of S is a basis for M. Thus any finite independent sequence can be extended to a basis. In particular, M has a finite free basis, and thus is a free F -module.

Proof Suppose, for notational convenience, that {v_{1}, .., v_{n}} is a maximal independent subsequence of S, and n < i ≤ m. It must be shown that v_{i} is a linear combination of {v_{1}, .., v_{n}}. Since {v_{1}, .., v_{n}, v_{i}} is dependent, ∃ r_{1}, ..., r_{n}, r_{i} not all zero, such that v_{1}r_{1} +··+v_{n}r_{n} +v_{i}r_{i} = ¯0. Then r_{i} ≠ ¯0 and v_{i} = −(v_{1}r_{1} +··+v_{n}r_{n})r_{i}^{−1}. Thus {v_{1}, .., v_{n}} generates S and thus all of M. Now suppose T is a finite independent sequence. T may be extended to a finite generating sequence, and inside that sequence it may be extended to a maximal independent sequence. Thus T extends to a basis.

After so many routine theorems, it is nice to have one with real power. It not only says any finite independent sequence can be extended to a basis, but it can be extended to a basis inside any finite generating set containing it. This is one of the theorems that makes linear algebra tick. The key hypothesis here is that the ring is a field. If R = Z, then Z is a free module over itself, and the element 2 of Z is independent. However it certainly cannot be extended to a basis. Also the finiteness hypothesis in this theorem is only for convenience, as will be seen momentarily.

Since F is a commutative ring, any two bases of M must have the same number of elements, and thus the dimension of M is well defined (see theorem on page 83).

Theorem Suppose M is an F -module of dimension n, and {v_{1}, ..., v_{m}} is an independent sequence in M. Then m ≤ n and if m = n, {v_{1}, .., v_{m}} is a basis.

Proof {v_{1}, .., v_{m}} extends to a basis with n elements.

The next theorem is just a collection of observations.

Theorem Suppose M and N are finitely generated F -modules.

1) M ≈ F^{n} iff dim(M) = n.

2) M ≈ N iff dim(M) = dim(N).

3) F^{m} ≈ F^{n} iff n = m.

4) dim(M ⊕ N) = dim(M) + dim(N).

Here is the basic theorem for vector spaces in full generality.

Theorem Suppose M ≠ ¯0 is an F -module and S = {v_{t}}_{t∈T} generates M.

1) Any maximal independent subsequence of S is a basis for M.

2) Any independent subsequence of S may be extended to a maximal independent subsequence of S, and thus to a basis for M.

3) Any independent subsequence of M can be extended to a basis for M. In particular, M has a free basis, and thus is a free F -module.

Proof The proof of 1) is the same as in the case where S is finite. Part 2) will follow from the Hausdorff Maximality Principle. An independent subsequence of S is contained in a maximal monotonic tower of independent subsequences. The union of these independent subsequences is still independent, and so the result follows. Part 3) follows from 2) because an independent sequence can always be extended to a generating sequence.

Theorem Suppose M is an F -module and K ⊂ M is a submodule.

1) K is a summand of M, i.e., ∃ a submodule L of M with K ⊕ L = M.

2) If M is f.g., then dim(K) ≤ dim(M) and K = M iff dim(K) = dim(M).

Proof Let T be a basis for K. Extend T to a basis S for M. Then S −T generates a submodule L with K ⊕ L = M. Part 2) follows from 1).

Corollary Q is a summand of R. In other words, ∃ a Q-submodule V ⊂ R with Q ⊕ V = R as Q-modules. (See exercise on page 77.)

Proof Q is a field, R is a Q-module, and Q is a submodule of R.

Corollary Suppose M is a f.g. F -module, N is an F -module, and f : M → N is a homomorphism. Then dim(M) = dim(ker(f)) + dim(image(f)).

Proof Let K = ker(f) and L ⊂ M be a submodule with K ⊕ L = M. Then f | L : L → image(f) is an isomorphism.

Exercise Suppose R is a domain with the property that, for R-modules, every submodule is a summand. Show R is a field.

Exercise Find a free Z-module which has a generating set containing no basis.

Exercise The real vector space R^{2} is generated by the sequence S = {(π, 0), (2, 1), (3, 2)}. Show there are three maximal independent subsequences of S, and each is a basis for R^{2}. (Row vectors are used here just for convenience.)

The real vector space R^{3} is generated by S = {(1, 1, 2), (1, 2, 1), (3, 4, 5), (1, 2, 0)}. Show there are three maximal independent subsequences of S and each is a basis for R^{3}. You may use determinant.

Square matrices over fields

This theorem is just a summary of what we have for square matrices over fields.

Theorem Suppose A ∈ F_{n} and f : F^{n} → F^{n} is defined by f(B) = AB. Let v_{1}, .., v_{n} ∈ F^{n} be the columns of A, and w_{1}, .., w_{n} ∈ F^{n} = F_{1,n} be the rows of A. Then the following are equivalent.

1) {v_{1}, .., v_{n}} is independent, i.e., f is injective.
2) {v_{1}, .., v_{n}} is a basis for F^{n}, i.e., f is an automorphism, i.e., A is

invertible, i.e., | A |≠ ¯0.

3) {v_{1}, .., v_{n}} generates F^{n}, i.e., f is surjective.

1^{t}) {w_{1}, .., w_{n}} is independent.

2^{t}) {w_{1}, .., w_{n}} is a basis for F^{n}, i.e., A^{t} is invertible, i.e., | A^{t} |≠ ¯0.

3^{t}) {w_{1}, .., w_{n}} generates F^{n}.

Proof Except for 1) and 1^{t}), this theorem holds for any commutative ring R. (See the section Relating these concepts to square matrices, pages 81 and 82.) Parts 1) and 1^{t}) follow from the preceding section.

Exercise Add to this theorem more equivalent statements in terms of solutions of n equations in n unknowns.

Overview Suppose each of X and Y is a set with n elements and f : X → Y is a function. By the pigeonhole principle, f is injective iff f is bijective iff f is surjective. Now suppose each of U and V is a vector space of dimension n and f : U → V is a linear transformation. It follows from the work done so far that f is injective iff f is bijective iff f is surjective. This shows some of the simple and definitive nature of linear algebra.

Exercise Let A = (A_{1}, .., A_{n}) be an n × n matrix over Z with column i = A_{i} ∈ Z^{n}. Let f : Z^{n} → Z^{n} be defined by f(B) = AB and f̄ : R^{n} → R^{n} be defined by f̄(C) = AC. Show the following are equivalent. (See the exercise on page 79.)

1) f : Z^{n} → Z^{n} is injective.

2) The sequence (A_{1}, .., A_{n}) is linearly independent over Z.

3) |A| ≠ 0.

4) f̄: R^{n} → R^{n} is injective.

5) The sequence (A_{1}, .., A_{n}) is linearly independent over R.

Rank of a matrix Suppose A ∈ F_{m,n}. The row (column) rank of A is defined to be the dimension of the submodule of F^{n} (F^{m}) generated by the rows (columns) of A.

Theorem If C ∈ F_{m} and D ∈ F_{n} are invertible, then the row (column) rank of A is the same as the row (column) rank of CAD.

Proof Suppose f : F^{n} → F^{m} is defined by f(B) = AB. Each column of A is a vector in the range F^{m}, and we know from page 81 that each f(B) is a linear combination of those vectors. Thus the image of f is the submodule of F^{m} generated by the columns of A, and its dimension is the column rank of A. This dimension is the same as the dimension of the image of g ∘ f ∘ h : F^{n} → F^{m}, where h is any automorphism on F^{n} and g is any automorphism on F^{m}. This proves the theorem for column rank. The theorem for row rank follows using transpose.

Theorem If A ∈ F_{m,n}, the row rank and the column rank of A are equal. This number is called the rank of A and is ≤ min{m, n}.

Proof By the theorem above, elementary row and column operations change neither the row rank nor the column rank. By row and column operations, A may be changed to a matrix H where h_{1,1} = ·· = h_{t,t} = ¯1 and all other entries are ¯0 (see the first exercise on page 59). Thus row rank = t = column rank.

Exercise Suppose A has rank t. Show that it is possible to select t rows and t columns of A such that the determined t × t matrix is invertible. Show that the rank of A is the largest integer t such that this is possible.

Exercise Suppose A ∈ F_{m,n} has rank t. What is the dimension of the solution set of AX = ¯0?

Definition If N and M are finite dimensional vector spaces and f : N → M is a linear transformation, the rank of f is the dimension of the image of f. If f : F^{n} → F^{m} is given by a matrix A, then the rank of f is the same as the rank of the matrix A.

Geometric Interpretation of Determinant

Suppose V ⊂ R^{n} is some nice subset. For example, if n = 2, V might be the interior of a square or circle. There is a concept of the n-dimensional volume of V. For n = 1, it is length. For n = 2, it is area, and for n = 3 it is “ordinary volume”. Suppose A ∈ R_{n} and f : R^{n} → R^{n} is the homomorphism given by A. The volume of V does not change under translation, i.e., V and V + p have the same volume. Thus f(V) and f(V +p) = f(V)+f(p) have the same volume. In street language, the next theorem says that “f multiplies volume by the absolute value of its determinant”.

Theorem The n-dimensional volume of f(V) is ±|A|(the n-dimensional volume of V). Thus if |A| = ±1, f preserves volume.

Proof If |A| = 0, image(f) has dimension < n and thus f(V) has n-dimensional volume 0. If |A| ≠ 0 then A is the product of elementary matrices (see page 59) and for elementary matrices, the theorem is obvious. The result follows because the determinant of the composition is the product of the determinants.

Corollary If P is the n-dimensional parallelepiped determined by the columns v_{1}, .. , v_{n} of A, then the n-dimensional volume of P is ±|A|.

Proof Let V = [0, 1] × · · ×[0, 1] = {e_{1}t_{1} + · · +e_{n}t_{n} : 0 ≤ t_{i} ≤ 1}. Then P = f(V) = {v_{1}t_{1} + · · +v_{n}t_{n} : 0 ≤ t_{i} ≤ 1}.

Linear functions approximate differentiable functions locally

We continue with the special case F = R. Linear functions arise naturally in business, science, and mathematics. However this is not the only reason that linear algebra is so useful. It is a central fact that smooth phenomena may be approximated locally by linear phenomena. Without this great simplification, the world of technology as we know it today would not exist. Of course, linear transformations send the origin to the origin, so they must be adjusted by a translation. As a simple example, suppose h : R → R is differentiable and p is a real number. Let f : R → R be the linear transformation f(x) = h′(p)x. Then h is approximated near p by g(x) = h(p) + f(x − p) = h(p) + h′(p)(x − p).

Now suppose V ⊂ R^{2} is some nice subset and h = (h_{1}, h_{2}) : V → R^{2} is injective

and differentiable. Define the Jacobian by J(h)(x, y) = ( \begin{matrix}\frac{∂h_{1}}{∂x} & \frac{∂h_{1}}{∂y} \\ \frac{∂h_{2}}{∂x} & \frac{∂h_{2}}{∂y} \end{matrix} ) and for each

(x, y) ∈ V, let f(x, y) : R^{2} → R^{2} be the homomorphism defined by J(h)(x, y). Then for any (p_{1}, p_{2}) ∈ V, h is approximated near (p_{1}, p_{2}) (after translation) by f(p_{1}, p_{2}). The area of V is ∫ ∫_{V} 1dxdy. From the previous section we know that any homomorphism f multiplies area by | f |. The student may now understand the following theorem from calculus. (Note that if h is the restriction of a linear transformation from R^{2} to R^{2}, this theorem is immediate from the previous section.)

Theorem Suppose the determinant of J(h)(x, y) is non-negative for each (x, y) ∈ V. Then the area of h(V) is ∫ ∫_{V} | J(h) | dxdy.

The Transpose Principle

We now return to the case where F is a field (of arbitrary characteristic). F - modules may also be called vector spaces and submodules may be called subspaces. The study of R-modules in general is important and complex. However the study of F -modules is short and simple – every vector space is free and every subspace is a summand. The core of classical linear algebra is not the study of vector spaces, but the study of homomorphisms, and in particular, of endomorphisms. One goal is to show that if f : V → V is a homomorphism with some given property, there exists a basis of V so that the matrix representing f displays that property in a prominent manner. The next theorem is an illustration of this.

Theorem Let F be a field and n be a positive integer.

1) Suppose V is an n-dimensional vector space and f : V → V is a homomorphism with |f| = ¯0. Then ∃ a basis of V such that the matrix representing f has its first row zero.

2) Suppose A ∈ F_{n} has |A| = ¯0. Then ∃ an invertible matrix C such that C^{−1}AC has its first row zero.

3) Suppose V is an n-dimensional vector space and f : V → V is a homomorphism with |f| = 0. Then ∃ a basis of V such that the matrix representing f has its first column zero.

4) Suppose A ∈ F_{n} has |A| = ¯0. Then ∃ an invertible matrix D such that D^{−1}AD has its first column zero.

We first wish to show that these 4 statements are equivalent. We know that 1) and 2) are equivalent and also that 3) and 4) are equivalent because change of basis corresponds to conjugation of the matrix. Now suppose 2) is true and show 4) is true. Suppose |A| = ¯0. Then |A^{t}| = ¯0 and by 2) ∃ C such that C^{−1}A^{t}C has first row zero. Thus (C^{−1}A^{t}C)^{t} = C^{t}A(C^{t})^{−1} has first row column zero. The result follows by defining D = (C^{t})^{−1}. Also 4) implies 2).

This is an example of the transpose principle. Loosely stated, it is that theorems about change of basis correspond to theorems about conjugation of matrices and theorems about the rows of a matrix correspond to theorems about the columns of a matrix, using transpose. In the remainder of this chapter, this will be used without further comment.

Proof of the theorem We are free to select any of the 4 parts, and we select part 3). Since | f |= 0, f is not injective and ∃ a non-zero v_{1} ∈ V with f(v_{1}) = ¯0. Now v_{1} is independent and extends to a basis {v_{1}, .., v_{n}}. Then the matrix of f w.r.t this basis has first column zero.

Exercise Let A = ( \begin{matrix}3π & 6 \\ 2π & 4 \end{matrix} ). Find an invertible matrix C ∈ R_{2} so that C^{−1}AC

has first row zero. Also let A = ( \begin{matrix}0 & 0 & 0 \\ 1 & 3 & 4 \\ 2 & 1 & 4 \end{matrix} ) and find an invertible matrix D ∈ R_{3}

so that D^{−1}AD has first column zero.

Exercise Suppose M is an n-dimensional vector space over a field F, k is an integer with 0 < k < n, and f : M → M is an endomorphism of rank k. Show there is a basis for M so that the matrix representing f has its first n − k rows zero. Also show there is a basis for M so that the matrix representing f has its first n − k columns zero. Work these out directly without using the transpose principle.

Nilpotent Homomorphisms

In this section it is shown that an endomorphism f is nilpotent iff all of its characteristic roots are ¯0 iff it may be represented by a strictly upper triangular matrix.

Definition An endomorphism f : V → V is nilpotent if ∃ m with f^{m} = ¯0. Any f represented by a strictly upper triangular matrix is nilpotent (see page 56).

Theorem Suppose V is an n-dimensional vector space and f : V → V is a nilpotent homomorphism. Then f^{n} = ¯0 and ∃ a basis of V such that the matrix representing f w.r.t. this basis is strictly upper triangular. Thus the characteristic polynomial of f is CP_{f}(x) = x^{n}.

Proof Suppose f ≠ ¯0 is nilpotent. Let t be the largest positive integer with f^{t} ≠ ¯0. Then f^{t}(V) ⊂ f^{t−1}(V) ⊂ ·· ⊂ f(V) ⊂ V. Since f is nilpotent, all of these inclusions are proper. Therefore t < n and f^{n} = ¯0. Construct a basis for V by starting with a basis for f^{t}(V), extending it to a basis for f^{t−1}(V), etc. Then the matrix of f w.r.t. this basis is strictly upper triangular.

Note To obtain a matrix which is strictly lower triangular, reverse the order of the basis.

Exercise Use the transpose principle to write 3 other versions of this theorem.

Theorem Suppose V is an n-dimensional vector space and f : V → V is a homomorphism. Then f is nilpotent iff CP_{f}(x) = x^{n}. (See the exercise at the end of Chapter 4 for the case n = 2.)

Proof Suppose CP_{f}(x) = x^{n}. For n = 1 this implies f = ¯0, so suppose n > 1. Since the constant term of CP_{f}(x) is ¯0, the determinant of f is ¯0. Thus ∃ a basis of V such that the matrix A representing f has its first column zero. Let B ∈ F_{n−1} be the matrix obtained from A by removing its first row and first column. Now CP_{A}(x) = x^{n} = xCP_{B}(x). Thus CP_{B}(x) = x^{n−1} and by induction on n, B is nilpotent and so ∃ C such that C^{−1}BC is strictly upper triangular. Then

( \begin{matrix}1 & 0 · · 0 \\ 0 \\ · & C^{−1} \\ · \\ 0 \end{matrix} ) ( \begin{matrix}0 & ∗ · · ∗ \\ · \\ & B \\ · \\ 0 \end{matrix} ) ( \begin{matrix}1 & 0 · · 0 \\ 0 \\ · & C \\ · \\ 0 \end{matrix} ) = ( \begin{matrix}0 & ∗ · · ∗ \\ 0 \\ · & C^{−1}BC \\ · \\ 0 \end{matrix} )

is strictly upper triangular.

Exercise Suppose F is a field, A ∈ F_{3} is a strictly lower triangular matrix of

rank 2, and B = ( \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} ). Using conjugation by elementary matrices, show there

is an invertible matrix C so that C^{−1}AC = B. Now suppose V is a 3-dimensional vector space and f : V → V is a nilpotent endomorphism of rank 2. We know f can be represented by a strictly lower triangular matrix. Show there is a basis {v_{1}, v_{2}, v_{3}} for V so that B is the matrix representing f. Also show that f(v_{1}) = v_{2}, f(v_{2}) = v_{3}, and f(v_{3}) = ¯0. In other words, there is a basis for V of the form {v, f(v), f^{2}(v)} with f^{3}(v) = ¯0.

Exercise Suppose V is a 3-dimensional vector space and f : V → V is a nilpotent endomorphism of rank 1. Show there is a basis for V so that the matrix representing

f is ( \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ).

Eigenvalues

Our standing hypothesis is that V is an n-dimensional vector space over a field F and f : V → V is a homomorphism.

Definition An element λ ∈ F is an eigenvalue of f if ∃ a non-zero v ∈ V with f(v) = λv. Any such v is called an eigenvector. E_{λ} ⊂ V is defined to be the set of all eigenvectors for λ (plus ¯0). Note that E_{λ} = ker(λI − f) is a subspace of V. The next theorem shows the eigenvalues of f are just the characteristic roots of f.

Theorem If λ ∈ F then the following are equivalent.

1) λ is an eigenvalue of f, i.e., (λI − f) : V → V is not injective.

2) | (λI − f) |= ¯0.

3) λ is a characteristic root of f, i.e., a root of the characteristic polynomial CP_{f}(x) = | (xI − A) |, where A is any matrix representing f.

Proof It is immediate that 1) and 2) are equivalent, so let’s show 2) and 3) are equivalent. The evaluation map F [x] → F which sends h(x) to h(λ) is a ring homomorphism (see theorem on page 47). So evaluating (xI − A) at x = λ and taking determinant gives the same result as taking the determinant of (xI − A) and evaluating at x = λ. Thus 2) and 3) are equivalent.

The nicest thing you can say about a matrix is that it is similar to a diagonal matrix. Here is one case where that happens.

Theorem Suppose λ_{1}, .., λ_{k} are distinct eigenvalues of f, and v_{i} is an eigenvector of λ_{i} for 1 ≤ i ≤ k. Then the following hold.

1) {v_{1}, .., v_{k}} is independent.

2) If k = n, i.e., if CP_{f}(x) = (x − λ_{1}) ⋯ (x − λ_{n}), then {v_{1}, .., v_{n}} is a basis for V. The matrix of f w.r.t. this basis is the diagonal matrix whose (i, i) term is λ_{i}.

Proof Suppose {v_{1}, .., v_{k}} is dependent. Suppose t is the smallest positive integer such that {v_{1}, .., v_{t}} is dependent, and v_{1}r_{1} + · · +v_{t}r_{t} = ¯0 is a non-trivial linear combination. Note that at least two of the coefficients must be non-zero. Now (f − λ_{t})(v_{1}r_{1} + · · +v_{t}r_{t}) = v_{1}(λ_{1} − λ_{t})r_{1} + · · +v_{t−1}(λ_{t−1} − λ_{t})r_{t−1} + ¯0 = ¯0 is a shorter non-trivial linear combination. This is a contradiction and proves 1). Part 2) follows from 1) because dim(V) = n.

Exercise Let A = ( \begin{matrix}0 & 1 \\ −1 & 0 \end{matrix} ) ∈ R_{2}. Find an invertible C ∈ C_{2} such that

C^{−1}AC is diagonal. Show that C cannot be selected in R_{2}. Find the characteristic polynomial of A.

Exercise Suppose V is a 3-dimensional vector space and f : V → V is an endomorphism with CP_{f}(x) = (x − λ)^{3}. Show that (f − λI) has characteristic polynomial x^{3} and is thus a nilpotent endomorphism. Show there is a basis for V so that the

matrix representing f is ( \begin{matrix}λ & 0 & 0 \\ 1 & λ & 0 \\ 0 & 1 & λ \end{matrix} ), ( \begin{matrix}λ & 0 & 0 \\ 1 & λ & 0 \\ 0 & 0 & λ \end{matrix} ) or ( \begin{matrix}λ & 0 & 0 \\ 0 & λ & 0 \\ 0 & 0 & λ \end{matrix} ).

We could continue and finally give an ad hoc proof of the Jordan canonical form, but in this chapter we prefer to press on to inner product spaces. The Jordan form will be developed in Chapter 6 as part of the general theory of finitely generated modules over Euclidean domains. The next section is included only as a convenient reference.

Jordan Canonical Form

This section should be just skimmed or omitted entirely. It is unnecessary for the rest of this chapter, and is not properly part of the flow of the chapter. The basic facts of Jordan form are summarized here simply for reference.

The statement that a square matrix B over a field F is a Jordan block means that ∃ λ ∈ F such that B is a lower triangular matrix of the form

B = ( \begin{matrix}λ & & & & 0 \\ 1 & λ \\ & & · \\ & & & · \\ 0 & & & 1 & λ \end{matrix} ). B gives a homomorphism g : F^{m} → F^{m} with g(e_{m}) = λe_{m}

and g(e_{i}) = e_{i+1} + λe_{i} for 1 ≤ i < m. Note that CP_{B}(x) = (x − λ)^{m} and so λ is the only eigenvalue of B, and B satisfies its characteristic polynomial, i.e., CP_{B}(B) = ¯0.

Definition A matrix D ∈ F_{n} is in Jordan form if ∃ Jordan blocks B_{1}, .. , B_{t} such

that D = ( \begin{matrix}B_{1} \\ & B_{2} & & & 0 \\ & & · \\ & & & · \\ & 0 \\ & & & & & B_{t} \end{matrix} ). Suppose D is of this form and B_{i} ∈ F_{n_{i}} has

eigenvalue λ_{i}. Then n_{1} + · · +n_{t} = n and CP_{D}(x) = (x − λ_{1})^{n_{1}} · ·(x − λ_{t})^{n_{t}}. Note that a diagonal matrix is a special case of Jordan form. D is a diagonal matrix iff each n_{i} = 1, i.e., iff each Jordan block is a 1 × 1 matrix.

Theorem If A ∈ F_{n}, the following are equivalent.

1) ∃ an invertible C ∈ F_{n} such that C^{−1}AC is in Jordan form.

2) ∃ λ_{1}, .., λ_{n} ∈ F (not necessarily distinct) such that CP_{A}(x) = (x − λ_{1}) · · (x − λ_{n}). (In this case we say that all the eigenvalues of A belong to F.)

Theorem Jordan form (when it exists) is unique. This means that if A and D are similar matrices in Jordan form, they have the same Jordan blocks, except possibly in different order.

The reader should use the transpose principle to write three other versions of the first theorem. Also note that we know one special case of this theorem, namely that if A has n distinct eigenvalues in F, then A is similar to a diagonal matrix. Later on it will be shown that if A is a symmetric real matrix, then A is similar to a diagonal matrix.

Let’s look at the classical case A ∈ R_{n}. The complex numbers are algebraically closed. This means that CP_{A}(x) will factor completely in C[x], and thus ∃ C ∈ C_{n} with C^{−1}AC in Jordan form. C may be selected to be in R_{n} iff all the eigenvalues of A are real.

Exercise Find all real matrices in Jordan form that have the following characteristic polynomials: x(x − 2), (x − 2)^{2}, (x − 2)(x − 3)(x − 4), (x − 2)(x − 3)^{2}, (x − 2)^{2}(x − 3)^{2}, (x − 2)(x − 3)^{3}.

Exercise Suppose D ∈ F_{n} is in Jordan form and has characteristic polynomial a_{0} + a_{1}x + · · +x^{n}. Show a_{0}I + a_{1}D + · · +D^{n} = ¯0, i.e., show CP_{D}(D) = ¯0.

Exercise (Cayley-Hamilton Theorem) Suppose E is a field and A ∈ E_{n}. Assume the theorem that there is a field F containing E such that CP_{A}(x) factors completely in F [x]. Thus ∃ an invertible C ∈ F_{n} such that D = C^{−1}AC is in Jordan form. Use this to show CP_{A}(A) = ¯0. (See the second exercise on page 66.)

Exercise Suppose A ∈ F_{n} is in Jordan form. Show A is nilpotent iff A^{n} = ¯0 iff CP_{A}(x) = x^{n}. (Note how easy this is in Jordan form.)

Inner Product Spaces

The two most important fields for mathematics and science in general are the real numbers and the complex numbers. Finitely generated vector spaces over R or C support inner products and are thus geometric as well as algebraic objects. The theories for the real and complex cases are quite similar, and both could have been treated here. However, for simplicity, attention is restricted to the case F = R. In the remainder of this chapter, the power and elegance of linear algebra become transparent for all to see.

Definition Suppose V is a real vector space. An inner product (or dot product) on V is a function V × V → R which sends (u, v) to u · v and satisfies

1) (u_{1}r_{1} + u_{2}r_{2}) · v = (u_{1} · v)r_{1} + (u_{2} · v)r_{2} for all u_{1}, u_{2}, v ∈ V v · (u_{1}r_{1} + u_{2}r_{2}) = (v · u_{1})r_{1} + (v · u_{2})r_{2} and r_{1}, r_{2} ∈ R.

2) u · v = v · u for all u, v ∈ V.

3) u · u ≥ 0 and u · u = 0 iff u = ¯0 for all u ∈ V.

Theorem Suppose V has an inner product.

1) If v ∈ V, f : V → R defined by f(u) = u · v is a homomorphism. Thus ¯0 · v = 0.

2) Schwarz’ inequality. If u, v ∈ V, (u · v)^{2} ≤ (u · u)(v · v).

Proof of 2) Let a = \sqrt{v · v} and b = \sqrt{u · u}. If a or b is 0, the result is obvious. Suppose neither a nor b is 0. Now 0 ≤ (ua ± vb) · (ua ± vb) = (u · u)a^{2} ± 2ab(u · v)+ (v ·v)b^{2} = b^{2}a^{2} ±2ab(u·v)+a^{2}b^{2}. Dividing by 2ab yields 0 ≤ ab±(u·v) or | u·v |≤ ab.

Theorem Suppose V has an inner product. Define the norm or length of a vector v by ∥v∥ = \sqrt{v · v}. The following properties hold.

1) ∥v∥ = 0 iff v = ¯0.
2) ∥vr∥ = ∥v∥ | r |.
3) | u · v | ≤ ∥u∥∥v∥. (Schwarz’ inequality)
4) ∥u + v∥ ≤ ∥u∥ + ∥v∥. (The triangle inequality)

Proof of 4) ∥u + v∥^{2} = (u + v) · (u + v) = ∥u∥^{2} + 2(u · v) + ∥v∥^{2} ≤ ∥u∥^{2} + 2∥u∥∥v∥ + ∥v∥^{2} = (∥u∥ + ∥v∥)^{2}.

Definition An Inner Product Space (IPS) is a real vector space with an inner product. Suppose V is an IPS. A sequence {v_{1}, .., v_{n}} is orthogonal provided v_{i} · v_{j} = 0 when i ≠ j. The sequence is orthonormal if it is orthogonal and each vector has length 1, i.e., v_{i} · v_{j} = δ_{i,j} for 1 ≤ i, j ≤ n.

Theorem If S = {v_{1}, .., v_{n}} is an orthogonal sequence of non-zero vectors in an

IPS V, then S is independent. Furthermore \{\frac{v_{1}}{∥v_{1}∥}, ⋯, \frac{v_{n}}{∥v_{n}∥}\} is orthonormal.

Proof Suppose v_{1}r_{1} + · · +v_{n}r_{n} = ¯0. Then 0 = (v_{1}r_{1} + · · +v_{n}r_{n}) · v_{i} = r_{i}(v_{i} · v_{i}) and thus r_{i} = 0. Thus S is independent. The second statement is transparent.

It is easy to define an inner product, as is shown by the following theorem.

Theorem Suppose V is a real vector space with a basis S = {v_{1}, .., v_{n}}. Then there is a unique inner product on V which makes S an orthornormal basis. It is given by the formula (v_{1}r_{1} + · · +v_{n}r_{n}) · (v_{1}s_{1} + · · +v_{n}s_{n}) = r_{1}s_{1} + · · +r_{n}s_{n}.

Convention R^{n} will be assumed to have the standard inner product defined by (r_{1}, .., r_{n})^{t} · (s_{1}, .., s_{n})^{t} = r_{1}s_{1} + · · +r_{n}s_{n}. S = {e_{1}, .., e_{n}} will be called the canonical or standard orthonormal basis (see page 72). The next theorem shows that this inner product has an amazing geometry.

Theorem If u, v ∈ R^{n}, u · v = ∥u∥∥v∥ cos Θ where Θ is the angle between u and v.

Proof Let u = (r_{1}, .., r_{n}) and v = (s_{1}, .., s_{n}). By the law of cosines ∥u − v∥^{2} = ∥u∥^{2} + ∥v∥^{2} − 2∥u∥∥v∥ cos Θ. So (r_{1} − s_{1})^{2} + · · +(r_{n} − s_{n})^{2} = r_{1}^{2} + · · +r_{n}^{2} + s_{1}^{2} + · · +s_{n}^{2} − 2∥u∥∥v∥ cos Θ. Thus r_{1}s_{1} + · · +r_{n}s_{n} = ∥u∥∥v∥ cos Θ.

Exercise This is a simple exercise to observe that hyperplanes in R^{n} are cosets. Suppose f : R^{n} → R is a non-zero homomorphism given by a matrix A = (a_{1}, .., a_{n}) ∈ R_{1,n}. Then L = ker(f) is the set of all solutions to a_{1}x_{1} + · · +a_{n}x_{n} = 0, i.e., the

set of all vectors perpendicular to A. Now suppose b ∈ R and C = ( \begin{matrix}c_{1} \\ · \\ · \\ c_{n} \end{matrix} ) ∈ R^{n}

has f(C) = b. Then f^{−1}(b) is the set of all solutions to a_{1}x_{1} + · · +a_{n}x_{n} = b which is the coset L+C, and this the set of all solutions to a_{1}(x_{1} −c_{1})+··+a_{n}(x_{n} −c_{n}) = 0.

Gram-Schmidt orthonormalization

Theorem (Fourier series) Suppose W is an IPS with an orthonormal basis {w_{1}, .., w_{n}}. Then if v ∈ W, v = w_{1}(v · w_{1}) + · · +w_{n}(v · w_{n}).

Proof v = w_{1}r_{1} + · · +w_{n}r_{n} and v · w_{i} = (w_{1}r_{1} + · · +w_{n}r_{n}) · w_{i} = r_{i}

Theorem Suppose W is an IPS, Y ⊂ W is a subspace with an orthonormal basis {w_{1}, .., w_{k}}, and v ∈ W −Y. Define the projection of v onto Y by p(v) = w_{1}(v·w_{1})+·· +w_{k}(v·w_{k}), and let w = v−p(v). Then (w·w_{i}) = (v−w_{1}(v·w_{1})··−w_{k}(v·w_{k}))·w_{i} = 0. Thus if w_{k+1} = \frac{w}{∥w∥}, then \{w_{1}, .., w_{k+1}\} is an orthonormal basis for the subspace

generated by {w_{1}, .., w_{k}, v}. If {w_{1}, .., w_{k}, v} is already orthonormal, w_{k+1} = v.

Theorem (Gram-Schmidt) Suppose W is an IPS with a basis {v_{1}, .., v_{n}}. Then W has an orthonormal basis {w_{1}, .., w_{n}}. Moreover, any orthonormal sequence in W extends to an orthonormal basis of W.

Proof Let w_{1} = \frac{v_{1}}{∥v_{1}∥}. Suppose inductively that \{w_{1}, .., w_{k}\} is an orthonormal

basis for Y, the subspace generated by {v_{1}, .., v_{k}}. Let w = v_{k+1} − p(v_{k+1}) and w_{k+1} = \frac{w}{∥w∥}. Then by the previous theorem, \{w_{1}, .., w_{k+1}\} is an orthonormal basis

for the subspace generated by {w_{1}, .., w_{k}, v_{k+1}}. In this manner an orthonormal basis for W is constructed. Notice that this construction defines a function h which sends a basis for W to an orthonormal basis for W (see topology exercise on page 103).

Now suppose W has dimension n and {w_{1}, .., w_{k}} is an orthonormal sequence in W. Since this sequence is independent, it extends to a basis {w_{1}, .., w_{k}, v_{k+1}, .., v_{n}}. The process above may be used to modify this to an orthonormal basis {w_{1}, .., w_{n}}.

Exercise Let f : R^{3} → R be the homomorphism defined by the matrix (2,1,3). Find an orthonormal basis for the kernel of f. Find the projection of (e_{1} + e_{2}) onto ker(f). Find the angle between e_{1} + e_{2} and the plane ker(f).

Exercise Let W = R^{3} have the standard inner product and Y ⊂ W be the subspace generated by {w_{1}, w_{2}} where w_{1} = (1, 0, 0)^{t} and w_{2} = (0, 1, 0)^{t}. W is generated by the sequence {w_{1}, w_{2}, v} where v = (1, 2, 3)^{t}. As in the first theorem of this section, let w = v − p(v), where p(v) is the projection of v onto Y, and set w_{3} = \frac{w}{∥w∥}. Find w_{3} and show that for any t with 0 ≤ t ≤ 1, \{w_{1}, w_{2}, (1 − t)v + tw_{3}\}

is a basis for W. This is a key observation for an exercise on page 103 showing O(n) is a deformation retract of GL_{n}(R).

Isometries Suppose each of U and V is an IPS. A homomorphism f : U → V is said to be an isometry provided it is an isomorphism and for any u_{1}, u_{2} in U, (u_{1} · u_{2})_{U} = (f(u_{1}) · f(u_{2}))_{V}.

Theorem Suppose each of U and V is an n-dimensional IPS, {u_{1}, .., u_{n}} is an orthonormal basis for U, and f : U → V is a homomorphism. Then f is an isometry iff {f(u_{1}), .., f(u_{n})} is an orthonormal sequence in V.

Proof Isometries certainly preserve orthonormal sequences. So suppose T = {f(u_{1}), .., f(u_{n})} is an orthonormal sequence in V. Then T is independent and thus T is a basis for V and thus f is an isomorphism (see the second theorem on page 79). It is easy to check that f preserves inner products.

We now come to one of the definitive theorems in linear algebra. It is that, up to isometry, there is only one inner product space for each dimension.

Theorem Suppose each of U and V is an n-dimensional IPS. Then ∃ an isometry f : U → V. In particular, U is isometric to R^{n} with its standard inner product.

Proof There exist orthonormal bases {u_{1}, .., u_{n}} for U and {v_{1}, .., v_{n}} for V. By the first theorem on page 79, there exists a homomorphism f : U → V with f(u_{i}) = v_{i}, and by the previous theorem, f is an isometry.

Exercise Let f : R^{3} → R be the homomorphism defined by the matrix (2,1,3). Find a linear transformation h : R^{2} → R^{3} which gives an isometry from R^{2} to ker(f).

Orthogonal Matrices

As noted earlier, linear algebra is not so much the study of vector spaces as it is the study of endomorphisms. We now wish to study isometries from R^{n} to R^{n}.

We know from a theorem on page 90 that an endomorphism preserves volume iff its determinant is ±1. Isometries preserve inner product, and thus preserve angle and distance, and so certainly preserve volume.

Theorem Suppose A ∈ R_{n} and f : R^{n} → R^{n} is the homomorphism defined by f(B) = AB. Then the following are equivalent.

1) The columns of A form an orthonormal basis for R^{n}, i.e., A^{t}A = I.

2) The rows of A form an orthonormal basis for R^{n}, i.e., AA^{t} = I.

3) f is an isometry.

Proof A left inverse of a matrix is also a right inverse (see the exercise on page 64). Thus 1) and 2) are equivalent because each of them says A is invertible with A^{−1} = A^{t}. Now {e_{1}, .., e_{n}} is the canonical orthonormal basis for R^{n}, and f(e_{i}) is column i of A. Thus by the previous section, 1) and 3) are equivalent.

Definition If A ∈ R_{n} satisfies these three conditions, A is said to be orthogonal. The set of all such A is denoted by O(n), and is called the orthogonal group.

Theorem

1) If A is orthogonal, | A |= ±1.

2) If A is orthogonal, A^{−1} is orthogonal. If A and C are orthogonal, AC is orthogonal. Thus O(n) is a multiplicative subgroup of GL_{n}(R).

3) Suppose A is orthogonal and f is defined by f(B) = AB. Then f preserves distances and angles. This means that if u, v ∈ R^{n}, ∥u − v∥ = ∥f(u)−f(v)∥ and the angle between u and v is equal to the angle between f(u) and f(v).

Proof Part 1) follows from |A|^{2} = |A| |A^{t}| = |I| = 1. Part 2) is immediate, because isometries clearly form a subgroup of the multiplicative group of all automorphisms. For part 3) assume f : R^{n} → R^{n} is an isometry. Then ∥u − v∥^{2} = (u − v) · (u − v) = f(u − v) · f(u − v) = ∥f(u − v)∥^{2} = ∥f(u) − f(v)∥^{2}. The proof that f preserves angles follows from u · v = ∥u∥∥v∥cosΘ.

Exercise Show that if A ∈ O(2) has |A| = 1, then A = ( \begin{matrix}cosΘ & −sinΘ \\ sinΘ & cosΘ \end{matrix} ) for

some number Θ. (See the exercise on page 56.)

Exercise (topology) Let R_{n} ≈ R^{n^{2}} have its usual metric topology. This means a sequence of matrices {A_{i}} converges to A iff it converges coordinatewise. Show GL_{n}(R) is an open subset and O(n) is closed and compact. Let h : GL_{n}(R) → O(n) be defined by Gram-Schmidt. Show H : GL_{n}(R) × [0, 1] → GL_{n}(R) defined by H(A, t) = (1 − t)A + th(A) is a deformation retract of GL_{n}(R) to O(n).

Diagonalization of Symmetric Matrices

We continue with the case F = R. Our goals are to prove that, if A is a symmetric matrix, all of its eigenvalues are real and that ∃ an orthogonal matrix C such that C^{−1}AC is diagonal. As background, we first note that symmetric is the same as self-adjoint.

Theorem Suppose A ∈ R_{n} and u, v ∈ R^{n}. Then (A^{t}u) · v = u · (Av).

Proof If y, z ∈ R^{n}, then the dot product y · z, is the matrix product y^{t}z, and matrix multiplication is associative. Thus (A^{t}u) · v = (u^{t}A)v = u^{t}(Av) = u · (Av).

Definition Suppose A ∈ R_{n}. A is said to be symmetric provided A^{t} = A. Note that any diagonal matrix is symmetric. A is said to be self-adjoint if (Au)·v = u·(Av) for all u, v ∈ R^{n}. The next theorem is just an exercise using the previous theorem.

Theorem A is symmetric iff A is self-adjoint.

Theorem Suppose A ∈ R_{n} is symmetric. Then ∃ real numbers λ_{1}, .., λ_{n} (not necessarily distinct) such that CP_{A}(x) = (x − λ_{1})(x − λ_{2}) ⋯ (x − λ_{n}). That is, all the eigenvalues of A are real.

Proof We know CP_{A}(x) factors into linears over C. If μ = a + bi is a complex number, its conjugate is defined by μ̄ = a − bi. If h : C → C is defined by h(μ) = μ̄, then h is a ring isomorphism which is the identity on R. If w = (a_{i,j}) is a complex matrix or vector, its conjugate is defined by w̄ = (ā_{i,j}). Since A ∈ R_{n} is a real symmetric matrix, A = A^{t} = Ā^{t}. Now suppose λ is a complex eigenvalue of A and v ∈ C^{n} is an eigenvector with Av = λv. Then λ(v^{t}v̄) = (λv)^{t}v̄ = (Av)^{t}v̄ = (v^{t}A)v̄ = v^{t}(Av̄) = v^{t}(\overline{Av}) = v^{t}(\overline{λv}) = λ̄(v^{t}v̄). Thus λ = λ̄ and λ ∈ R. Or you can define a complex inner product on C^{n} by (w · v) = w^{t}v̄. The proof then reads as λ(v · v) = (λv · v) = (Av · v) = (v · Av) = (v · λv) = λ̄(v · v). Either way, λ is a real number.

We know that eigenvectors belonging to distinct eigenvalues are linearly independent. For symmetric matrices, we show more, namely that they are perpendicular.

Theorem Suppose A is symmetric, λ_{1}, λ_{2} ∈ R are distinct eigenvalues of A, and Au = λ_{1}u and Av = λ_{2}v. Then u · v = 0.

Proof λ_{1}(u · v) = (Au) · v = u · (Av) = λ_{2}(u · v).

Review Suppose A ∈ R_{n} and f : R^{n} → R^{n} is defined by f(B) = AB. Then A represents f w.r.t. the canonical orthonormal basis. Let S = {v_{1}, .., v_{n}} be another basis and C ∈ R_{n} be the matrix with v_{i} as column i. Then C^{−1}AC is the matrix representing f w.r.t. S. Now S is an orthonormal basis iff C is an orthogonal matrix.

Summary Representing f w.r.t. an orthonormal basis is the same as conjugating A by an orthogonal matrix.

Theorem Suppose A ∈ R_{n} and C ∈ O(n). Then A is symmetric iff C^{−1}AC is symmetric.

Proof Suppose A is symmetric. Then (C^{−1}AC)^{t} = C^{t}A(C^{−1})^{t} = C^{−1}AC.

The next theorem has geometric and physical implications, but for us, just the incredibility of it all will suffice.

Theorem If A ∈ R_{n}, the following are equivalent.

1) A is symmetric.

2) ∃ C ∈ O(n) such that C^{−1}AC is diagonal.

Proof By the previous theorem, 2) ⇒ 1). Show 1) ⇒ 2). Suppose A is a symmetric 2 × 2 matrix. Let λ be an eigenvalue for A and {v_{1}, v_{2}} be an orthonormal basis for R^{2} with Av_{1} = λv_{1}. Then w.r.t this basis, the transformation determined

by A is represented by ( \begin{matrix}λ & b \\ 0 & d \end{matrix} ). Since this matrix is symmetric, b = 0.

Now suppose by induction that the theorem is true for symmetric matrices in R_{t} for t < n, and suppose A is a symmetric n × n matrix. Denote by λ_{1}, .., λ_{k} the distinct eigenvalues of A, k ≤ n. If k = n, the proof is immediate, because then there is a basis of eigenvectors of length 1, and they must form an orthonormal basis. So suppose k < n. Let v_{1}, .., v_{k} be eigenvectors for λ_{1}, .., λ_{k} with each ∥ v_{i} ∥= 1. They may be extended to an orthonormal basis v_{1}, .., v_{n}. With respect to this basis, the

transformation determined by A is represented by ( \begin{matrix}( \begin{matrix}λ_{1} \\ & · \\ & & · \\ & & & λ_{k} \end{matrix} ) & (B) \\ (0) & (D) \end{matrix} ).

Since this is a symmetric matrix, B = 0 and D is a symmetric matrix of smaller size. By induction, ∃ an orthogonal C such that C^{−1}DC is diagonal. Thus conjugating

by ( \begin{matrix}I & 0 \\ 0 & C \end{matrix} ) makes the entire matrix diagonal.

This theorem is so basic we state it again in different terminology. If V is an IPS, a linear transformation f : V → V is said to be self-adjoint provided (u·f(v)) = (f(u)·v) for all u, v ∈ V.

Theorem If V is an n-dimensional IPS and f : V → V is a linear transformation, then the following are equivalent.

1) f is self-adjoint.

2) ∃ an orthonormal basis {v_{1}, ..., v_{n}} for V with each v_{i} an eigenvector of f.

Exercise Let A = ( \begin{matrix}2 & 2 \\ 2 & 2 \end{matrix} ). Find an orthogonal C such that C^{−1}AC is diagonal.

Do the same for A = ( \begin{matrix}2 & 1 \\ 1 & 2 \end{matrix} ).

Exercise Suppose A, D ∈ R_{n} are symmetric. Under what conditions are A and D similar? Show that, if A and D are similar, ∃ an orthogonal C such that D = C^{−1}AC.

Exercise Suppose V is an n-dimensional real vector space. We know that V is isomorphic to R^{n}. Suppose f and g are isomorphisms from V to R^{n} and A is a subset of V. Show that f(A) is an open subset of R^{n} iff g(A) is an open subset of R^{n}. This shows that V, an algebraic object, has a god-given topology. Of course, if V has an inner product, it automatically has a metric, and this metric will determine that same topology. Finally, suppose V and W are finite-dimensional real vector spaces and h : V → W is a linear transformation. Show that h is continuous.

Exercise Define E : C_{n} → C_{n} by E(A) = e^{A} = I + A + (1/2!)A^{2} + ··. This series converges and thus E is a well defined function. If AB = BA, then E(A + B) = E(A)E(B). Since A and −A commute, I = E(¯0) = E(A − A) = E(A)E(−A), and thus E(A) is invertible with E(A)^{−1} = E(−A). Furthermore E(A^{t}) = E(A)^{t}, and if C is invertible, E(C^{−1}AC) = C^{−1}E(A)C. Now use the results of this section to prove the statements below. (For part 1, assume the Jordan form, i.e., assume any A ∈ C_{n} is similar to a lower triangular matrix.)

1) If A ∈ C_{n}, then | e^{A} |= e^{trace(A)}. Thus if A ∈ R_{n}, | e^{A} |= 1

iff trace(A) = 0.

2) ∃ a non-zero matrix N ∈ R_{2} with e^{N} = I.

3) If N ∈ R_{n} is symmetric, then e^{N} = I iff N = ¯0.

4) If A ∈ R_{n} and A^{t} = −A, then e^{A} ∈ O(n).