Mathematical analysis : linear and metric structures and continuity

--+

= ax + by 'Ix, y E JR..

JR. is linear if and only if there exist a, b E JR. such that

1.23 'If. Show that

1.2 Matrices and Linear Operators

15

Figure 1.3. Some linear transformations of the plane. In the figure the possible images of the square [0,1] x [O,lJ are in shadow.

d. Image and kernel Let A E Mm,n(JK) and let A(x) := Ax, x E OCn be the linear associated operator. The kernel and the image of A (or A) are respectively defined by ker A = ker A := {x E OC n IA(x) =

ImA = ImA:= {Y E OC m

o},

I:J x E OCn

such that A(x) =

y}.

Trivially, ker A is a linear subspace of the source space OC n , and it easy to see that the following three claims are equivalent: (i) A is injective, (ii) ker A = {O}, (iii) aI, a2, ... , an are linearly independent in OCm . If one of the previous claims holds, we say that A is nonsingular, although in the current literature nonsingular usually refers to square matrices. Also observe that A may be nonsingular only if m ::::: n. Also 1m A = 1m A is a linear subspace of the target space OCm , and by definition 1m A = Span {aI, a2, ... , an}. The dimension ofIm A = 1m A is called the rank of A (or of A) and is denoted by Rank A (or Rank A). By definition Rank A is the maximal number of linearly independent columns of A, in particular RankA :::; min(n, m). Moreover, it is easy to see that the following claims are equivalent

16

1. Vectors, Matrices and Linear Systems

(i) A is surjective, (ii) 1m A = ][{m, (iii) Rank A = m. Therefore A may be surjective only if m ::; n. The following theorem is crucial.

1.25 Theorem (Rank formula). For every matrix A E Mm,n(][{) we have dim 1m A = n - dimker A. Proof. Let (VI, V2, ... , Vk) be a basis of ker A. According to Theorem 1.7 we can choose (n - k) vectors ek+I, ... , en of the standard basis of OC n in such a way that VI, V2, ... , Vk, ek+lo ... ,en form a basis of OC n . Then one easily checks that (A(ek+I),'" ,A(en)) is a basis of ImA, thus concluding that dim 1m A = n - k. 0

A first trivial consequence of the rank formula is the following. 1.26 Corollary. Let A E Mm,n(][{)' (i) If m < n, then dimker A> a. (ii) If m ;::: n, then A is nonsingular, z.e., ker A = {a}, if and only if Rank A is maximal, Rank A = n. (iii) If m = n, i. e., A is a square matrix, then the following two equivalent claims hold: a) Let A(x) := Ax be the associated linear map. Then A is surjective if and only if A is injective. b) Ax = b is solvable for any choice of b E ][{m if and only if A(x) = a has zero as a unique solution. Proof. (i) From the rank formula we have dim ker A = n - dim 1m A 2: n - m

> O.

(ii) Again from the rank formula, dim 1m A = n - dim ker A = n = min(n, m). (iii) (a) Observe that A is injective if and only if ker A = {O}, equivalently if and only if dim ker A = 0, and that A is surjective if and only if 1m A = OC m , i.e., dim 1m A = m = n. The conclusion follows from the rank formula.

o

(iii) (b) The equivalence between (iii) (a) and (iii) (b) is trivial.

Notice that (i) and (ii) imply that A : surjective only if n = m. 1.27~.

][{n ----; ][{m

may be injective and

Show the following.

Proposition. Let A E Mn,n (OC) and A(x) := Ax. The following claims are equivalent:

(i) (ii) (iii) (iv) (v) (vi)

A is injective and surjective, A is nonsingular, i.e., ker A = {O}, A is surjective, there exists B E Mn,n(OC) such that BA = Id n , there exists B E Mn,n(OC) such that AB = Id n , A is invertible, i.e., there exists a matrix BE Mn,n(OC) such that BA Id n .

=

AB

=

1.2 Matrices and Linear Operators

17

An important and less trivial consequence of the rank formula is the following. 1.28 Theorem (Rank of the transpose). Let A E Mm,n. Then we have

(i) the maximum number of linearly independent columns and the maximum number of linearly independent rows are equal, z.e., RankA = Rank AT,

(ii) let p

:= RankA. Then there exists a nonsingular p x p square submatrix of A.

Proof. (i) Let A = [a;J, let aI, a2, ... , an be the columns of A and let p:= RankA. We assume without loss of generality that the first p columns of A are linearly independent and we define B as the mxp submatrix formed by these columns, B := [al I a21 ... lap]. Since the remaining columns of A depend linearly on the columns of B, we have Vk

= 1, ... , m,

Vj

= p + 1, ... , n

for some R = [r;] E Mp,n-p(lK). In terms of matrices,

hence Taking the transposes, we have AT E Mn,m(lK), BT E Mp,m(lK) and

(1.6)

Since [Id p IR]T is trivially injective, we infer that ker AT = ker B T , hence by the rank formula Rank AT = m - dimkerA T = m - dim ker B T = RankB T , and we conclude that Rank AT

= RankB T

::; min(m,p)

= p = RankA.

Finally, by applying the above to the matrix AT, we get the opposite inequality Rank A = Rank (AT)T ::; Rank AT, hence the conclusion. (ii) With the previous notation, we have Rank B T = Rank B = p. Thus B has a set of p independent rows. The submatrix S of B made by these rows is a square p X P matrix with RankS = RankS T = p, hence nonsingular. 0 1.29 -,r. Let A E Mm.n(lK), let A(x) := Ax and let (VI, V2, ... , v n ) be a basis of lK n . Show the following: (i) A is injective if and only if the vectors A(vI), A(V2), .. . , A(v n ) of lK m are linearly independent, (ii) A is surjective if and only if {A(VI),A(V2)"" ,A(vn )} spans lKm , (iii) A is bijective iff {A(VI),A(V2)' ... ,A(vn )} is a basis of lK m .

18

1. Vectors, Matrices and Linear Systems

e. Grassmann's formula Let U and V be two linear subspaces of OC n . Clearly, both U n V and U

+V

:= {x E OC

n

Ix = u + v for some u E U and v E V}

are linear subspaces of OC n . When U n V = {O}, we say that U + V is the direct sum of U and V and we write U EB V for U + V. If moreover U EB V = OCn , we say that U and V are supplementary subspaces. The following formula is very useful. 1.30 Proposition (Grassmann's formula). Let U and V be linear subspaces of OC n . Then dim(U

+ V) + dim(U n V) = dim U + dim V.

Proof. Let (Ul' U2,.' ., Uh) and (Vi, V2, ... , Vk) be two bases of U and V respectively. The vectors Ul, U2, ... , Uh, Vi, V2, ... , Vk span U + V, and a subset of them form a basis of U + V. In particular, dim(U + V) = RankL where L is the n x (h + k) matrix defined by L :=

[Ul

Moreover, a vector x = Z=~l such that

I.. ,I I- I... IUh

XiUi

E

OC n

Vi

is in

un V

Vk] .

if and only if there exist unique

yl, y2, ... , yk

x = X1Ul

+ ... xhUh

thus, if and only if the vector w longs to ker L. Consequently, the

= ylvl

+ ... + yk vk ,

:= (_xl, _x 2 , ... , _x h , yl, y2, .. . , yk) linear map : OC h + k --; OCn ,

E OC h + k be-

h

(x,y) :=

2::xiUi i=l

is injective and surjective from ker L onto Un V. It follows that dim(U n V) = dim ker L and, by the rank formula,

dim(U

n V) + dim(U + V)

= dim ker L + RankL = h + k = dimU + dim V. o

1.31 ,. Notice that the proof of Grassmann's formula is in fact a procedure to compute two bases of U + V and un V starting from two bases of U and V. The reader is invited to choose two subspaces U and V of ocn and to compute the basis of U + V and of Unv.

f. Parametric and implicit equations of a subspace 1.32 Parametric equation of a straight line in ocn . Let a 1= 0 and let q be two vectors in OC n . The parametric equation of a straight line through q and direction a is the map r : OC --; OC n given by r(>..) := >"a + q, >.. E IK. The image of r { x E lR,n 13>" such that x = >"a + q} is the straight line through q and direction a.

1.2 Matrices and Linear Operators

19

Figure 1.4. Straight line through q and direction a.

We have r(O) = q and r(l) = a + q. In other words, r(t) passes through q and a + q. Moreover, x is on the straight line passing through q and a + q if and only if there exists t E lK such that x = t a + b, or, more explicitly

XI=ta l + ql , x 2 =ta2 +q2, (1.7)

!

x n = tan

+ qn. := ta + q

In kinematics, lK = jR and the map t -+ r(t) gives the position at time t of a point moving with constant vector velocity a starting at q at time t = 0 on the straight line through q and a + q.

1.33 Implicit equation of a straight line in lK n • We want to find a representation of the straight line (1.7) which makes no use of the free parameter t. Since a i= 0, one of its components is nonzero. Assume for instance a l i= 0, we can solve the first equation in (1.7) to get t = (ql - xl )ja l and, substituting the result into the last (n - 1) equations, we find a system of (n - 1) constraints on the variable x = (xl, x 2 , ..• , x n ) E lKn ,

x3

l (ql_x )

a2 + q2 , = (ql-x l )a3 +q3 ,

X2 =

!

xn =

~

~

~an+qn. a

The previous linear system can be written as A(x - q) the matrix defined by -1

0 -1

0 0

-a~jal

0 0

0

-1

_an ja l

0

0

0

[ -a'ja' 3 l -a ja

A

=

=0

where A E Mn-l,n(lK) is

~l

1.34'. Show that there are several parametric equations of a given straight line. A parametric equation of the straight line through a and b E jRn is given by t -+ r(t) := a + t(b - a), t E lR. 1.35 Parametric and implicit equations of a 2-plane in lK 3 • Given two linearly independent vectors VI, V2 in jR3 and a point q E jR3, we call the parametric equation

20

1. Vectors, Matrices and Linear Systems

of the plane directed by VI, V2 and passing through q, the map 'I' : by '1'((0, ,8» := OVI + ,8v2 + q, or in matrix notation

I

'1'((0, ,8» = [VI V2] (;)

nc2 ~ nc3 d.efined

+ q.

Of course 'I' is linear iff q = 0. The 2-plane determined by this parametrization is defined by II:= 1m 'I' = Suppose VI

= (a, b, c)

and V2

{x E R.3Ix- q E ImA}.

= (d, e, f)

so that

Because of Theorem 1.28, there is a nonsingular 2 x 2 submatrix B of A and, without loss of generality, we can suppose that B =

(~ ~). We can then solve the system

°

in the unknown (0, ,8), thus finding and ,8 as linear functions of xl - ql and x 2 q2. Then, substituting into the third equation, we can eliminate (0,,8) from the last equation, obtaining an implicit equation, or constraint, on the independent variables, of the form r (xl _ ql) + S (x 2 _ q2) + t (x 3 _ q3) = 0, that describes the 2-plane without any further reference to the free parameters (0, ,8).

More generally, let W be a linear subspace of dimension k in JKn, also called a k-plane (through the origin) of JKn. If VI, V2, ... , Vk is a basis of W, we can write W = 1m L where

We call x -> L(x) := Lx the parametric equation of W generated by (VI, V2, ... , Vk). Of course a different basis of W yields a different parametrization. We can also write any subspace W of dimension k as W = ker A where A E Mn-k,n(JK). We call it an implicit representation of W. Notice that since ker A = W, we have Rank AT = Rank A = n - k by Theorem 1. 28 and the rank formula. Hence the rows of A are n - k linearly independent vectors of JKn. 1.36 Remark. A k-dimensional subspace of JKn is represented by means of k free parameters, i.e., the image of JKk through a nondegenerate parametric equation, or by a set of independent (n - k) constraints given by linearly independent scalar equations in the ambient variables.

1.2 Matrices and Linear Operators

21

1.37 Parametric and implicit representations. One can go back and forth from the parametric to the implicit representation in several ways. For instance, start with W = ImL where L E M n ,k(lK) has maximal rank, RankL = k. By Theorem 1.28 there is a k x k nonsingular matrix submatrix M of L. Assume that M is made by the first few rows of L so that

M L=

N where N E Mn-k,k (IK). Writing x as x = (x', x") with x' E IK k and x" E Kn-k, the parametric equation x = Lt, t E IKk , writes as

X' {

=Mt,

(1.8)

x" =Nt.

As M is invertible,

We then conclude that x E ImL if and only if NM-1x' = x". The latter is an implicit equation for W, that we may write as Ax = 0 if we define A E M n -k,n(lK) by

A=EJB· Conversely, let W = ker A where A E Mn,k (IK) has Rank A = n - k. Select n - k independent columns, say the first n - k on the left, call B E M n - k ,n-k(lK) the square matrix made by these columns, and split x as x = (x', x") where x' E IK n - k and x" E IKk . Thus Ax = 0 rewrites as

G

8(::,)=0,

or

Bx' +Cx" =0.

As B is invertible, the last equation rewrites as x' = -B-1Cx", Therefore x E ker A if and only if

x=

i.e., W = ImL.

x" :=Lx",

22

1. Vectors, Matrices and Linear Systems

1.3 Matrices and Linear Systems a. Linear systems and the language of linear algebra Matrices and linear operators are strongly tied to linear systems. A linear system of m equations and n unknowns has the form

at

+ a~x2 + '" + a;,x n = bl , ar xl + a~x2 + ... + a;x n = b2, Xl

(1.9)

The m-tuple (b l , ... ,bm ) is the given right-hand side, the n-tuple (Xl, ... , x n ) is the unknown and the numbers {aj}, i = 1, ... ,m, j = 1, ... ,n are given and called the coefficients of the system. If we think of the coefficients as the entries of a matrix A,

.

A:= raj] =

I

ar:

a2l a22

a~a2 )

am 2

am n

C am I

n

.

,

(1.10)

and we set b:= (b\ b2, ... , bm ) E ocm , x:= (xl, x 2, ... , x n ) E OC n , then the system can be written in a compact way as Ax=b.

(1.11)

Introducing the linear map A(x) := Ax, (1.9) can be seen as a functional equation (1.12) A(x) = b or, denoting by aI, a2, ... , an the n-columns of A indexed from left to right, as xlal + x2a2 + .. ,+ xnan = b. (1.13) Thus, the discussion of linear systems, linear independence, matrices and linear maps are essentially the same, in different languages. The next proposition collects these equivalences. 1.38 Proposition. With the previous notation we have:

(i) Ax is a linear combination of the columns of A. (ii) The following three claims are equivalent: a) the system (1.11) or (1.9), is solvable, i.e., there exists x E OC n such that Ax = b; b) b is a linear combination of all a2,···, an; c)bElmA. (iii) The following four claims are equivalent:

1.3 Matrices and Linear Systems

23

a) Ax = b has at most one solution, b) Ax = 0 implies x = 0, c) A(x) = 0 has a unique solution, d) ker A = {OJ, e) aI, az, ... , an are linearly independent. (iv) ker A is the set of all solutions of the system Ax = O. (v) 1m A is the set of all b's such that the system Ax = b has at least one solution. (vi) Let Xo E OC n be a solution ofAxo = b. Then the set of all solutions of Ax = b is the set

{xo }

+ ker A

:=

{x

E

OC n Ix - Xo E ker A}.

With the previous notation, we see that b is linearly dependent of aI, az, ... , an if and only if

Thus from Proposition 1.38 (ii) we infer the following. 1.39 Proposition (Rollche-Capelli). With the previous notation, the system (1.9) or (1.11) is solvable if and only if

The m x (n

+ 1)

matrix

is often called the complete matrix of the system (1.9). 1.40

-,r.

Prove all claims in this section.

1.41 Solving linear systems. Let us return to the problem of solving Ax=b,

where

A E M""n (IK), b E IK"'.

If n = m and A is nonsingular, then the unique solution is xo := A -lb. In the general case, according to Proposition 1.39, the system is solvable if and only if Rank A = Rank [A I b], and if xo E IK n is a solution, the set of all solutions is given by {xo}+ker A. Let r := Rank A. Since Rank AT = r, we may assume without loss of generality that the first r rows of A are linearly independent and the other rows depend linearly on the first r rows. Therefore, if we solve the system of r equations

24

1. Vectors, Matrices and Linear Systems

a~) (Xl)

a;

x2

·· ·

.. .

a~

xn

l

b2

(b.) , ..

(1.14)

br

the remaining equations are automatically fulfilled. So it is enough to solve Ax = b in the case where A E Mr,n(OC) and Rank AT = Rank A = r. We have two cases. If r = n, then A E Mr,r is nonsingular, consequently Ax = b has a unique solution x = A-I b. If r < n, then A has r linearly independent columns, say the first r. Denote by R the r x r nonsingular matrix made by these columns, and decompose x = (x', x") with x' E ocr and x" E oc n - r . Then Ax = b writes as

EJ 8 (::,)

i.e., Rx'

+ Sx" =

= b,

b, or x' = R-l(b - Rx"). Therefore,

x= Id n -

r

concluding that the set of all solutions of the system Ax = b is

{x I x -

XQ

I

E ker A} = {x x -

XQ

E ImL}.

b. The Gauss elimination method As we have seen, linear algebra yields a proper language to discuss linear systems, and conversely, most of the constructions in linear algebra reduce to solving systems. Moreover, the proofs we have presented are constructive and become useful from a numerical point of view if one is able to efficiently solve the following two questions: (i) find the solution of a nonsingular square system Ax = b, (ii) given a set of vectors T c OC n , find a subset SeT such that Span S = SpanT. In this section we illustrate the classical Gauss elimination method which efficiently solves both questions. 1.42 Example. Let us begin with an example of how to solve a linear system. Consider the linear system

6x + 18y +6z 3x + 8y +6z { 2x +y + z where x:= (x,y,x), b:=

(h,b2,b3)

and

or

Ax=b

1.3 Matrices and Linear Systems

25

We subtract from the second and third equations the first one multiplied by 1/2 and 1/3 respectively to get the new equivalent system:

6x + 18y + 6z 3x + 8y + 6z - ~(6x + 18y + 6z) { 2x + y + z - ~(6x + 18y + 6z)

= bl, = -~bl +b2, = -~bl +b3,

i.e.,

6x

+ 18y + 6z -y+3z -5y-z

{

= bl, = -~bl +b2, =-~bl+b3.

(1.15)

This essentially requires us to solve the system of the last two equations

= -~bl = -~bl

-y+3z -5y-z

{

+ b2, + b3·

We now apply the same argument to this last system, i.e., we subtract from the last equation the first one multiplied by 5 to get

6x {

+ 18y + 6z

= bl, = -~bl = -~bl

-y+3z -5y - z - 5( -y + 3z)

+ b2, + b3 -

5(-~bl

+ b2),

i.e., 6x

+ 18y + 6z -y+3z -16z

{

= bl, = -~bl + b2, = 2bI - 5b2 +b3.

This system has exactly the same solution as the original one and, moreover, it is easily solvable starting from the last equation. Finally, we notice that the previous method produced two matrices

U:=

(~o ~~ ~) 0

,

-16

U is upper triangular and L is lower triangular with 1 in the principal diagonal, so the original system Ax = b rewrites as Ux=Lb.

Since L = [1}J is invertible (I: = 1 Vi) and x is arbitrary, we can rewrite the last formula as a decomposition formula for A, A = L-lU.

The algorithm we have just described in Example 1.42, that transforms the proposed 3 x 3 square system into a triangular system, extends to systems with an arbitrary number of unknowns and equations, and it is called the Gauss elimination method. Moreover, it is particularly efficient, but does have some drawbacks from a numerical point of view.

26

1. Vectors, Matrices and Linear Systems

Let (1.16)

Ax=O

be a linear homogeneous system with m equations, n unknowns and a coefficient matrix given by

A =

a2

a~ a22

a~a )

am 2

am n

2 n

C .1

am 1

Starting from the left, we denote by ]1 the index of the first column of A that has at least one nonzero element. Then we reorder the rows into a new matrix B of the same dimensions, in such a way that the element bJ1 is nonzero and all columns with index less than]1 are zero,

.

B ~ [b,] ~

(0;

0

1 0 b)1 0 *

* *

0

*

*

where * denotes the unspecified entries. We then set P1 := bJ1' and for i = 2, ... , m we subtract from the ith row of B the first row of B multiplied by -b))P1. The resulting matrix therefore has the following form

o

P1

*

00* 00* where P1 i= 0, below P1 all entries are zero and * denotes the unspecified entries. We then transform A 1 into A 2 , A 2 into A 3 , and so on, operating as previously, but on the submatrix of A 1 of rows of index respectively larger than 2, 3, .... The algorithm of course stops when there are no more rows and/or columns. The resulting matrix produced this way is not uniquely determined as there is freedom in exchanging the rows. However, a resulting matrix that we call a Gauss reduced matrix, is clearly upper triangular if A is a square matrix, m = n, and in general has the following stair-shaped form

1.3 Matrices and Linear Systems

-

~ "'~"" '"

~

27

1l1l.tt < ~ -~ct

u.tl1lt.

ItttlltlJft

Figure 1.5. Two pages of the Japanese mathematician Takakazu Seki (1642-1708) who apparently dealt with determinants before Gauss.

GA:=

0 0 0 0

PI

0 0 0

*

0 0 0

* * *

P2 0 0

0 0

00000

* * P3 0

* * *

0

* * * Pr

000

(1.17) where * denotes the unspecified entries; the nonzero numbers PI, P2, ... , Pr are called the pivots of the stair-shaped matrix GA. Finally, since o multiplying one of the equations of the system Ax = 0 by a nonzero scalar, o exchanging the order of the equations, o summing a multiple of one equation and another equation, produces a linear system with the same solution as the initial system, and observing that the Gauss elimination procedure operates with transformations of this type, we conclude that GAX = 0 has the same solution as the initial system. We now discuss the solvability of the system Lx = b, if L is stairshaped. 1.43 Proposition. Let L be a stair-shaped m x n matrix. Suppose that L has r pivots, r :::; min( n, m). Then a basis of 1m L is given by the r columns containing the pivots, and the system Lx = b, b = (b l , b2 , ... , bm ) T, has a solution if and only if br +! = ... = bm = o. Proof. Since there are r pivots and at most one pivot per row, the last rows of L are identically zero, hence 1m L C {b E IK m I b = (bl, b2, . .. , br , 0, ... , On. Consequently,

28

1. Vectors, Matrices and Linear Systems

Figure 1.6. Takakazu Seki (1642-1708).

dimlmL S; r. On the other hand the r columns that contain the pivots are in ImL and are linearly independent, hence Rank L = r, and 1m L = {(b I , b2 , •.. , br , 0, ... ,0) I bi E IKVi,i=l, ... ,r}. 0

The Gauss elimination procedure preserves several properties of the original matrix A. 1.44 Theorem. Let A E Mm,n(lK) and let G A be one of the matrices resulting from the Gauss elimination procedure. Then (i) ker A

= ker GA,

(ii) Rank A = RankGA = number of pivots ofGA, (iii) letjl,j2, .. ' ,jr be the indices of the columns of the pivots ofGA, then the columns of A with the same indices are linearly independent, Proof. (i) is a rewriting of the equivalence of Ax = 0 with GAX = O. (ii) Because of (i), the rank formula yields Rank A = RankGA, and RankGA equals the number of pivots by Proposition 1.43. (iii) Let A = [al I a21 ... Ian] and let

Following the Gauss elimination procedure we used on A, we easily see that the columns of B transform into the columns of the pivots which are linearly independent. By (i) ~B=M.

0

1.45~. Let A E M m ,n(IK). Show a procedure to find a basis for Rank A and Rank AT. 1.46~. Let W = Span {VI, V2, ... , vd be a subspace of IKn . Show a procedure to find a basis of W among the vectors VI, V2, ... , Vk. 1.41~.

Let A E M m ,n(IK). Show a procedure to find a basis of ker A.

1.3 Matrices and Linear Systems

29

1.48~. Let VI, V2, ... , Vk E IK m be k linearly independent vectors. Show a procedure to complete them with n - k vectors of the canonical basis of IR n in order to form a new basis of IR n . [Hint: Apply the Gauss elimination procedure on the matrix

0 1

o

o 0

1

1

o

1.49~.

o

)1

Show that A E Mn,n(IK) is invertible if and only if a Gauss reduced matrix of

A has n pivots.

c. The Gauss elimination procedure for nonhomogeneous linear systems Now consider the problem of solving A(x) = b, where A E Mm,n(JK), x E lK n and b E lK m. We can equivalently write it as Xl

x2 a 21

a~ a 22

a~ a 32

C a"{'

a2'

a n1 a n2

1 0

am n

a'3

0

0 1

xn _b 1 _b 2

:)

0

=0.

_bm

If one computes a Gauss reduced form of the m x (n a

I

B := [A Idn ] =

1 2

+ m)

a~ a~

an a n2

1 0 0 1

a 2m

am n

0

C

1

:1

am 1

0

matrix

r)

we find, on account of Theorem 1.44, that

GB~G8 where G A E Mm,n(lK) is a Gauss reduced matrix of A and S E Mm,m(lK). Moreover, if the elimination procedure has been carried out without any permutation of the rows, then S is a lower triangular matrix with 1 as entries in the principal diagonal, hence it is invertible. Since for every b the system Ax = b is equivalent to GAX = Sb, we then have GAx = Sb = SAx 't/x E lK n , thus concluding that A

= S-lG A . In particular,

30

1. Vectors, Matrices and Linear Systems

1.50 Proposition (LR decomposition). Let A E Mn,n(JK) be a square

matrix. If the elimination procedure proceeds without any permutation of the rows, we can decompose A as A = LR, where R = GA is the resulting Gauss reduced matrix and L is a suitable lower triangular matrix with 1 as entries in the principal diagonal of L. In general, howewer, the permutation of the rows must be taken into account. For this purpose, let us fix some notation. Recall that a permutation of {1, ... ,m} is a one-to-one map ( j : {1, ... ,m} --+ {1, ... ,m}. The set of all permutations of m elements is denoted by Pm. For every permutation (j of m elements, define the associated permutation matrix R a E Mm,m(JK) by

where (el, e2, ... , em) is the canonical basis of oc m. Let A E Mm,n(OC). If (j permutes the indices of the rows of A, then the resulting matrix is RaA. Now denote by 9(A) the Gauss reduced matrix, if it exists, obtained by the Gauss elimination procedure starting from the top row and proceeding without any permutation of the rows. Let GA be a Gauss reduced form of A. Then GA = 9(Ra A) for some permutation (j of m elements. Now fix a Gauss reduced form GA of A, and let (j be such that GA = 9(Ra A). Write Ax = Y as (RaA)x = RaY = Idm(Ray) and let

Then Band RaA may be reduced without any permutation of the rows, hence by the above

where S is lower triangular with all entries in the principal diagonal equal to 1. Therefore GAX = SRaY = SRaAx 't/x, that is,

(1.18) When A E Mn,n(OC) is a square matrix, (1.18) shows that A is invertible if and only if a Gauss reduced form G A of A is invertible and A-I

= GAlSRa .

In practice, let (el, e2, ... , en) be the canonical basis of oc n and let A-I =: [VI I v21 ... Iv n ]. Let i = 1, ... n. To compute Vi, we observe that Vi = A -lei, i.e., AVi = ei. Thus, using the Gauss elimination procedure, from (1.18) Vi is a solution of G A Vi = SRaei. Now, since GA is upper triangular, this last system is easily solved by inductively computing the components of Vi starting from the last, upward.

1.4 Determinants

31

(0,1 t-----,

Figure 1.7. The area transformation.

1.4 Determinants The notion of determinant originated with the observation of Gabriel Cramer (1704-1752) and Carl Friedrich Gauss (1777-1855) that the process of elimination of unknowns when solving a linear system of equations amounts to operating with the indices of the associated matrix. Developments of this observation due to Pierre-Simon Laplace (1749-1827), Alexandre Vandermonde (1735-1796), Joseph-Louis Lagrange (1736-1813) and Carl Friedrich Gauss (1777-1855), who introduced the word determinant, were then accomplished with a refined study of the properties of the determinant by Augustin-Louis Cauchy (1789-1857) and Jacques Binet (1786-1856). Here we illustrate the main properties of the determinant. 1.51 Determinant and area in

]R2.

Let

A = (:

(1.19)

:)

be a 2 x 2 matrix. It is easily seen that A is not singular, i.e., the linear homogeneous system

ax + by = 0, { ex + dy = 0 has zero, (x, y) = (0,0), as a unique solution if and only if ad - be ad - be is the determinant of the matrix A, det A

=

det (:

:):=

#

O. The number

ad - be.

One immediately notices the combinatorial characteristic of this definition: if A = [a;], then det A = ata~ - a~aiLet a := (a, c) and b := (b, d) be the two columns of the matrix A in (1.19). The elementary area of the parallelogram spanned by a and b with vertices (0,0), (a, c), (b, d) and (a + b, c + d), is given by Area (T) =

lallbll sin 01

where 0 is the angle ;1;, irrespective of the orientation, see Figure 1. 7. On the other hand, by Carnot's formula lallbl cos 0 = ab + cd, hence

32

1. Vectors, Matrices and Linear Systems

..

MANUA[.I HOSP[.I

ELEMENTARY TREATI &

ERNESTO PASCAL arGIwtIo . . . a.llall'UW&
;Jaf-Il

I DETERMINA TI

DETERMI S/J/ULTANIIOUS L/NUR

A

T

6QU4TI()~'S

J.."D ALOZ8lUICAL OJll:)JlI!:TRY.

CBA.RLB~

OLRICO HOEPLI II:DlTOflIt-1.lIU10 P&U.A .LIlI.

L. DODOBON. H.A.

"'llIhl:

~,\

)U,CklLUlC o\)fD

WILA:"'lO

-

co.

uu

Figure 1.8. Frontispieces of two books on determinants respectively by Ernesto Pascal and Charles L. Dodgson, better known as Lewis Carollo

Area (T)2 = (a 2 + c 2 )(b 2 + d 2 )(1 - cos 2 0) = a 2b2 + a 2d 2 + b2c 2 + c 2d 2 _ (ab + cd)2 = a 2d 2 + b2c 2 - 2abcd = (ad - bc)2 = det A 2 , Le.)

Area(T) = IdetAI. We may think of det A as of the area of T with sign. In fact, the sign of det A may be used to define the sign of the angle formed by the vectors a and b. The angle ;;J; is positively (negatively) oriented if det[a IbJ > 0 (det[a I bJ < 0). Angles with sign in geometry are also modelled by complex multiplication, identifying ]R2 with iC. Using the previous notation, setting z := a + ib, w = c + id we have zw = (a + ib)(c - id) = (ac +bd) +i(bc - ad) = (ae b )1R2 +idetA.

Let vi, V2 E ]R.2. As we have seen, the determinant of the matrix [Vi IV2] is not zero iff Vi and V2 are linearly independent. Actually, for any n ~ I there is a real function defined on n x n matrices that tells us whether the n columns of the matrix are linearly independent: the determinant. One of the simplest ways to define it is as follows. We recall that a permutation of {I, ... , n} is a one-to-one map a : {l, ... ,n} -> {l, ... ,n}. The set of permutations of n objects, denoted by Pn is a group with respect to the operation of composition. A permutation that exchanges two adjacent indices and leaves the other indices unchanged is called a transposition. Transpositions are elementary permutations in the sense that each permutation a can be obtained by composing

1.4 Determinants

33

subsequent transpositions. Of course, there are several ways to decompose a given permutation into elementary transpositions, but the parity or oddity of the number of transpositions needed to realize a given permutation a depends only on the permutation a. We define the signature, or sign, of the permutation a the number

(-1)""

:=

{+1 -1

if a decomposes in an even number of transpositions, if a decomposes in an odd number of transpositions.

1.52 Definition. Let A is then defined by

=

det A:=

[a;] E Mn,n(JK), n 2 1. The determinant of A

I: (-1)"" a~(l)a;(2) ... a~(n)'

(1.20)

,,"EPn

Notice that det A is a sum of products and each product contains just one element from each row and each column, and the sum, apart from the sign, is extended to all possible choices. 1.53 Example. Of course for matrix A in (1.19) we again get det A = ad - be. Going back to the area, one shows that given 3 vectors VI, V2, V3 E IR3 and denoting by T the polyhedra generated by these vectors, we still have VoI3(T) = Idet[vi [v21 v3]1·

For n vectors VI, V2, ... , Vn E IRn, let

and let L(x) := Lx. If Q is the unit cube of IR n ,

Q:= {x = (xl, x 2 , ... , x n )

IO:S: xi :s:

1 Vi},

we define the n-dimensional volume of T := L(Q) by Voln(T):= IdetL[.

It is useful to think of the determinant as a function of the columns of the matrix. In fact, we have the following.

1.54 Theorem. The determinant on n x n matrices is the unique function det : Mn,n(JK) -+ OC such that, when seen as a function of columns, it is (i)

(LINEAR ON EACH FACTOR): >. E OC

det [ . ..

for all

a~, a~' E

OCn , i

=

1, ... , n, and

I~ + a~' I... ] = det [. .. Ia~ I ] + det [. .. Ia~' I ... ],

I I... ] =

det [ .. , >'ai

>. det [ . .. Iai I

],

34

1. Vectors, Matrices and Linear Systems

(ii) (ALTERNATING): by exchanging two adjacent columns the determinant changes sign, det [ ...

1ai I ai+l I ... ] = - det [ .. ·1 ai+1 I ai I ... ],

(iii) (NORMALIZED): det Idn

= 1.

Notice that because of (i) the alternating property can be equivalently formulated by saying that det A = 0 if A has two equal columns. Proof. Clearly the right-hand side of (1.20) fulfills the conditions (i), (ii), (iii). To prove uniqueness, suppose that D : Mn,n(II() ---t II( fulfills (i), (ii), (iii) of Theorem 1.54. Write A = raj] E Mn,n(II() as A = tal I a2! ... Ian] where n

ai

=

L a{ej, j=l

(el, e2, ... , en) being the canonical basis of II(n. Then by (i) D(A) =

L

a;(l)a;(2) ... a~(n)D([el I '"

Ien])

O"(l), ... ,O"(n)

where 17(1),17(2), ... , a(n) vary in {I, ... , n}. Since by (ii) D(A) = 0 if A has two equal columns, we infer that a(i) 1= a(j) if i 1= j, i.e., that a is a permutation of (1,2, ... ,n). Since D([eO"(l) I ... I eO"(n)]) = (-1)0" D([el I ... I en]) and D([el I .. , I en]) = 1, we conclude that D(A) agrees with the right-hand side of (1.20), hence D(A) = det A. 0

The determinant can also be computed by means of an inductive formula.

1.55 Definition. Let A = [a;] E Mn,n(lK), n 2: 1. A r-minor of A is a r x r submatrix of A, that is a matrix obtained by choosing the common entries of a choice of r rows and r columns of A and relabeling the indices from 1 to r. For i,j = 1, ... , n we define the complementing (i,j)-minor of the matrix A, denoted by M{(A), as the (n -1) x (n -I)-minor obtained by removing the ith row and the jth column from A. 1.56 Theorem (Laplace). Let A E Mn,n(lK), n 2: 1. Then detA :=

A

if n = 1,

{ 2:7=1 (-I)J+1 a] det M](A) if n > 1.

(1.21 )

Proof. Denote by D(A) the right-hand side of (1.21). Let us prove that D(A) fulfills the conditions (i), (ii) and (iii) of Theorem 1.54, thus D(A) = det A. The conditions (i) and (ii) of Theorem 1.54 are trivially fulfilled by D(A). Let us also show that (iii) holds, i.e., if aj = aj+l for some j, then D(A) = O. We proceed by induction on j. By the induction step, det M); (A) = 0 for h 1= j,j + 1, hence D(A) = (-I)i+ l a] det M] (A) + (-I)ja]+l detM]+l(A). Since a] = a]+l' and, consequently, M](A) = M]+l(A), we conclude that D(A) = O. 0

From (1.20) we immediately infer the following.

1.4 Determinants

35

1.57 Theorem (Determinant of the transpose). We have

detA T = detA

for all A E Mn,n(lK).

One then shows the following important theorem.

1.58 Theorem (Binet's formula). Let A and B be two n x n matrices. Then det(BA) = det B det A. Proof. Let A = [a;J = [al I ... [an], B = [b;J = [bl the canonical basis of lK n . Since n

n

2)BA){ ej j=l

=

I ... I b n ] and

let (el, ... , en) be

n

L Il?ai ej = L aibr, j,r=l

r=l

we have n

det(BA)=det([Lalbrl···1 r=l

=

L

n

La~br]) r=l

a~(I)a;(2)'" a~(n) det[bu(l)

I ...

[bu(n)J

uEPn

=

L

(-1)Ua~(I)a;(2)" .a~(n) detB = detAdetB.

uEP n

o As stated in the beginning, the determinant gives us a criterion to decide whether a matrix is nonsingular or, equivalently, whether n vectors are linearly independent.

1.59 Theorem. A n x n matrix A is nonsingular if and only if det A

-I- O.

Proof. If A is nonsingular, there is aBE Mn,n(lK) such that AB = Id n , see Exercise 1.27; by Binet's formula det A det B = 1. In particular det A of O. Conversely, if the columns of A are linearly dependent, then it is not difficult to see that det A = 0 by using Theorem 1.54. 0

Let A = [a)] be an m x n matrix. We say that the characteristic of A is r if all p-minors with p > r have zero determinant and there exists a r-minor with nonzero determinant.

1.60 Theorem (Kronecker). The rank and the characteristic of a matrix are the same. Proof. Let A E Mm,n(lK) and let r := RankA. For any minor B, trivially RankB ::; Rank A = r, hence every p-minor is singular, Le., has zero determinant, if p > n. On the other hand, Theorem 1.28 implies that there exists a nonsingular r-minor B of A, hence with det B of O. 0

The defining inductive formula (1.21) requires us to compute the determinant of the complementing minors of the elements of the first row; on account of the alternance, we can use any row, and on account of Theorem 1.57, we can use any column. More precisely,

36

1. Vectors, Matrices and Linear Systems

1.61 Theorem (Laplace's formulas). Let A be an n x n matrix. We have for all h, k = 1, ... , n

n 8kh detA = ~)-l)h+jajdetM;(A), j=l

n

8kh detA = ~) _l)i+ha~ detM,,(A), i=l

where 8hk is Kronecker's symbol. 1.62 ... To compute the determinant of a square n x n matrix A we can use a Gauss reduced matrix GA of A. Show that det A = (-1)" n?=l (GA)~ where a is the permutation of rows needed to compute GA, and the product is the product of the pivots.

It is useful to rewrite Laplace's formulas using matrix multiplication. Denote by cof(A) = [cj] the square n x n matrix, called the matrix of cofactors of A, defined by

Notice the exchange between the row and column indices: the (i,j) entry of cof(A) is (-l)i+j times the determinant of the complementing (j, i)-minor. Using the cofactor matrix, Laplace's formulas in Theorem 1.61 rewrite in matrix form as 1.63 Theorem (Laplace's formulas). Let A be an n x n matrix. Then we have (1.22) cof(A) A = A cof(A) = det A Id n .

We immediately infer the following. 1.64 Proposition. Let A

= [all a21 ... I an]

E

Mn,n(JK) be nonsingular.

(i) We have A

(ii)

(CRAMER'S RULE)

-1

1

= det A cof(A).

The system Ax

= h, hE OC n , has a unique solu-

tion given by 1 2 ... ,xn) , x= ( x,x,

where

i

x

det B i

= detA'

1.5 Exercises

37

Proof. (i) follows immediately from (1.22). (ii) follows from (i), but it is better shown using linearity and the alternating property of the determinant. In fact, solving Ax = b is equivalent to finding x = (xl, X 2 , ... , xn) such that b = 2::7=1 xiai' Now, linearity and the alternating property of the determninant yield detBi =det [ .. ·Iai-ll txjaj lai+ll .. ·] = txjdet [ .. ·lai-lJaj Jai+lJ ... ]. j=l j=l Since the only nonzero addend on the right-hand side is the one with j = i, we infer detBi=xidet[all··· Jai-l[aiJai+lJ ... Jan] =

Xi

detA.

o 1.65~. Show that detcof(A) = (detA)n-l.

1.5 Exercises 1.66~. Find the values of x, y E JR for which the three vectors (1,1,1), (1, x, x 2 ), (1, y, y2) form a basis of JR3. 1.67~. Let 0<1,0<2 E C be distinct and nonzero. Show that eart, e a2t , t E JR, are linearly independent on C. [Hint: See [GM2] Corollary 5.54.] 1.68~.

Write the parametric equation of a straight line (i) through b = (1,1,1) and with direction a = (1,0,0), (ii) through a = (1,1,1) and b = (1,0,0).

1.69~. Describe in a parametric or implicit way in JR3,

o o o o o o o

a straight line through two points, the intersection of a plane and a straight line, a straight line that is parallel to a given plane, a straight line on a plane, a plane through three points, a plane through a point containing a given straight line, a plane perpendicular to a straight line.

1. 70 ~ Affine transformations. An affine tmnsformation

~.

n P2

Let PI and P2 be two (n - I)-planes in JRn. Show that either PI = P2 or = 0 or PI n P2 has dimension n - 2.

1. 72~. In JR4 find (i) two 2-planes through the origin that meet only at the origin, (ii) two 2-planes through the origin that meet along a straight line. 1.73 ~. In JR2 write the 2 x 2 matrix associated with the counterclockwise rotations of angles rr /2, rr, 3rr /2, and, in general, () E JR.

38

1. Vectors, Matrices and Linear Systems

1.14'. Write the matrix associated with the axial symmetry in IR3 and to plane symmetries. 1.15 ,. Write down explicit linear systems of 3,4,5 equations with 4 or 5 unknowns, and use the Gauss elimination procedure to solve them. 1.16'. Let A E Mn,n(lK). Show that if AB = 0 VB E Mn,n(lK), then A = O.

1.11'. Let A =

(~

-1 -1

~) and B =

-1

(:

2

~). Compute A + B, V2A + B.

1.18'. Let

A=

(~

-1

3 2

2 0

o

1

:) 1

~ (~ ~:).

B

2

5

1.19'. Let

Show that AB = O. 1.80'. Let A, B E Mn,n(lK). Show that if AB = 0 and A is invertible, then B = O. 1.81'. Let

B (0 i) :=

i

0

'

C (i 0). :=

0

-i

Show that o o o o

A2 = B2 = C2 = - Id, AB=-BA=C, BC = -CB = Id, CA=-AC=B.

1.82'. Let A,B E Mn,n. We say that A is symmetric if A = AT. Show that, if A is symmetric, then AB is symmetric if and only if A and B commute, i.e., AB = BA. 1.83'. Let M E Mn,n(lK) be an upper triangular matrix with all entries in the principal diagonal equal to 1. Suppose that for some k we have M k = MM·· . M = Id n . Show that M = Id n . 1.84'. Let A, B E Mn,n(lK). In general AB =I- BA. The n x n matrix [A, B] .AB - BA is called the commutator or the Lie brocket of A and B. Show that (i) [A, B] = -[B, A], (ii) (JACOBI'S IDENTITY) [[A, B], C] + [[B,C],A] + [[C,A],B] = 0, (iii) the trace of [A, B] is zero. The troce of a n x n matrix A = [a~] is defined as tr A :=

Ei a~ =

O.

1.5 Exercises

1.85~.

1.86

~

39

Let A E Mn,n be diagonal. Show that B is diagonal if and only if [A, BJ = O. Block matrices. Write a n x n matrix as

A~) A~

A = (Ai Ai

where Ai is the submatrix of the first k rows and h columns, A~ is the submatrix of the first k rows and n - h columns, etc. Show that 1 1 1 B1 A11A1) 2 (B 12 B1) _ (A1 +2 A1B2 1 ( Ai A~ Bi B~ AiBi + A~Bi 1.87~.

Let A E Mk,k(lK), BE Mn,n(lK) and

Compute det C. 1.88~.

Let A E Mk,dlK), B E Mn,n(lK), C E Mk,n(lK) and

M=(~ ~). Compute det M. 1.89 ~ Vandermonde determinant. Let >'1, >'2, ... , >'n ElK and

A:=

1

1

1

1

>'1 >.2 1 >.31

>'2 >.2 2 >.3 2

>'3 >.2 3 >.3 3

>'n

>'1

>.~

>'3

>.~

>.2n >.3n

Prove that det A = TIi<j (>'i - >'j). [Hint: Proceed by induction on n. Notice that det A is a polynomial in >'n and use the principle of identity for polynomials.] 1.90~.

Compute the rank of the following matrices

(!

1 1 3 4

3 -3 1 -2

nu 3 1 2 5

1 -1 2 3

~) (111!)

1.91 ~. Solve the following linear systems

2x + 4y + 3z - 2t = 3,

+ 2z + t = 1, x + 2y - z + 2t = 2, x - 5y + 4z - 3t = 1,

3X - y {

2x + 2y - 3z + 3t = 3, x

+ 2y -

z

+ 3t =

2,

x - 3y + 2z + 2t = -4, 4x + y - 2z

+ 8t =

1.

2. Vector Spaces and Linear Maps

The linear structure of lK n is shared by several mathematical objects. We have already noticed that the set of m x n matrices satisfies the laws of sum and multiplication by scalars. The aim of this chapter is to introduce abstract language and illustrate some facts related to linear structure. In particular, we shall see that in every finite-dimensional vector space we can introduce the coordinates related to a basis and explain how the coordinates description of intrinsic objects changes when we change the coordinates, i.e., the basis.

2.1 Vector Spaces and Linear Maps a. Definition Let lK be a commutative field, here it will be either

~

or
2.1 Definition. A vector space over the field lK is a set X endowed with (i) an operation + : X x X -+ X, called the sum, that makes X a commutative group, i.e., a) (x+y)+z=x+(y+z), x+y=y+x, 'Vx,yEX, b) there exists an element 0 E X called the zero element, such that x+O=O+x=x'VxEX, c) for every x E X there exists -x E X such that x + (-x) = 0, (ii) an operation of multiplication by a scalar· : lK x X -+ X that associates to every A E lK and x E X an element of X denoted by AX such that a) A(X + y) = AX + Ay, (A + JL)x = AX + JLX, b) A(JLX) = (AJL)X, 1· x = x. In particular, (-l)x = -x "Ix E X; we therefore write x - y instead of

x

+ (-y).

The elements of a vector space over lK are called vectors, and the elements of lK are called scalars. The product of a vector by scalars allows us to regard a vector at all scales.

42

2. Vector Spaces and Linear Maps

2.2 Example. As we have seen, IK n for n :::: 1, and all the linear subspaces of IK n are vector spaces over IK. Also, the space of m x n matrices with entries in IK, Mm,n(IK), is a vector space over IK, with the two operations of sum of matrices and multiplication of a matrix by a scalar, see Section 1.2. 2.3 Example. Let X be any set. Then the class F(X, IK) of all functions <.p : X - t IK is a vector space with the two operations of sum and multiplication by scalars defined by

(<.p + 'lj;)(x) := <.p(x)

+ 'lj;(x),

(A<.p)(X) := A<.p(X)

'VxEX.

Several subclasses of functions are vector spaces, actually linear subspaces of F(X, IK). For instance, o the set CO([O, 1]' JR.) of all continuous functions <.p : [O,IJ - t JR., the set of kdifferentiable functions from [0,1] into JR., the set Ck([O, 1], JR.) of all functions with continuous derivatives up to the order k, the set COO([O, 1]' JR.) of infinitely differentiable functions, o the set of polynomials of degree less than k, the set of all polynomials, o the set of all complex trigonometric polynomials, o the set of Riemann summable functions in ]0,1[, o the set of all sequences with values in IK.

We now begin the study of properties that depend only on the linear structure of a vector space, independently of specific examples.

b. Subspaces, linear combinations and bases 2.4 Definition. A subset W of a vector space X is called a linear subspace, or shortly a subspace of X, if

(i) 0 E W, (ii) 'V x, yEW we have x + yEW, (iii) 'V x E W and 'V A E lK we have AX E W. Obviously the element 0 is the zero element of X and the operations of sum and multiplication by scalars are as those in X. In a vector space we may consider the finite linear combinations of elements of X with coefficients in lK, i.e., n

where AI, A2 ,00., An ElK and VI, V2,oo., V n E X. Notice that we have indexed both the vectors and the relative coefficients, and we use the standard notation on the indices: a list of vectors has lower indices and a list of coefficients has upper indices. It is readily seen that a subset W c X is a subspace of X if and only if all finite linear combinations of elements of X with coefficients in lK belong to W. Moreover, given a set SeX, the family of all finite linear combinations of elements of S is a subspace of X called the span of Sand denoted by Span S. We say that a finite number of vectors are linearly dependent if there are scalars, not all zero, such that

2.1 Vector Spaces and Linear Maps

Q

43

TER

..

_,......-....._--...

,..

TAil .Oy ..... Ul.tt AC,.DUIY.

OUJI.Uf 1100011 .Aii'D OaA.nOIl.ITlKJrr. _IMITtI, _ n_--. UlIIDOIf ..."1I1.D_c:o.,,,'t"JltlIlA,,,,,, c.IoIlIll"'~'~

I'"~

Figure 2.1. Arthur Cayley (1821-1895) and the Lectures on Quatemions by William R. Hamilton (1805-1865).

>.lVl

+ ... + >.n Vn = 0,

or, in other words, if one vector is a linear combination of the others. If n vectors are not linearly dependent, we say that they are linearly independent. More generally, we say that a set 5 of vectors is a set of linearly independent vectors whenever any finite list of elements of 5 is made by linearly independent vectors. Of course linearly independent vectors are distinct and nonzero.

2.5 Definition. Let X be a vector space. A set 5 of linearly independent vectors such that Span 5 = X is called a basis of X. A set A c X is a maximal independent set of X if A is a set of linearly independent vectors and, whenever we add to it a vector w E X\A, Au{ w} is not a set of linearly independent vectors. Thus a basis of X is a subset 5

c

X such that

(i) every x E X is a finite linear combination of some elements of 5. Equivalently, for every x E X there is a map >. : 5 --; K such that x = EVEs >.(v)v and >.(v) = 0 except for a finite number of elements (depending on x) of 5, (ii) each finite subset of 5 is a set of linearly independent vectors.

It is easy to prove that for every x E X the representation x = EVEs >.( v)v is unique if 5 is a basis of X. Using the same proof as in Proposition 1.5 we then infer 2.6 Proposition. Let X be a vector space over K. Then 5 of X if and only if 5 is a maximal independent set.

c

X is a basis

44

2. Vector Spaces and Linear Maps

Using Zorn's lemma, see [GM2], one can also show the following.

2.7 Theorem. Every vector space X has a basis. Moreover, two bases have the same cardinality. 2.8 Definition. A vector space X is finite dimensional if X has a finite basis. In the most interesting infinite-dimensional vector spaces, one can show the basis has nondenumerable cardinality. Later, we shall see that the introduction of the notion of limit, Le., of a new structure on X, improves the way of describing vectors. Instead of trying to see every x E X as a finite linear combination of elements of a nondenumerable basis, it is better to approximate it by a suitable sequence of finite linear combinations of a suitable countable set. For finite-dimensional vector spaces, Theorem 2.7 can be proved more directly, as we shall see later. 2.9'. Show that the space of all polynomials and CD([O, 1]' IR) are infinite-dimensional vector spaces.

c. Li1!ear maps 2.10 Definition. Let X and Y be two vector spaces over lK. A map rp : X -> Y is called lK-linear, or linear for short, if

rp(x + y)

= rp(x) + rp(y)

and

rp( >.x)

= >.rp(x)

for any x, y E X and>. E K A linear map that is injective and surjective is called a (linear) isomorphism. Of course, if rp : X

->

Y is linear, we have rp(O)

2.11 Proposition. Let rp : X rp(

->

= 0 and, by induction,

Y be linear. Then

k

k

i=l

i=l

L >.iei ) = L >.irp(ei)

for any>.!, >.2, ... , >.n ElK and el, e2,"" en EX. In particular, a linear map is fixed by the values it takes on a basis. The space of linear maps rp : X -> Y between two vector spaces X and Y, denoted by £(X, Y), is a vector space over lK with the operations of sum and multiplication by scalars defined in terms of the op~rations on Y by (rp + ~)(x) := rp(x) + ~(y), (>.rp)(x) = >.rp(x) for all rp, ~ E £(X, Y) and>. E R Notice also that the composition oflinear maps is again a linear map, and that, if rp : X -> Y is an isomorphism, then the inverse map rp-l : Y -> X is also an isomorphism. It is easy to check the following.

2.1 Vector Spaces and Linear Maps

2.12 Proposition. Let 'P : X

--+

45

Y be a linear map.

(i) If SeX spans W C X, then 'P(S) spans 'P(W). (ii) If el, e2, ... , en are linearly dependent in X, then 'P(el), ... , 'P(e n ) are linearly dependent in Y. (iii) 'P is injective if and only if any list (el' e2, ... , en) of linearly independent vectors in X is mapped into a list ('P(eI) , 'P(e2), ... , 'P(e n )) of linearly independent vectors in X. (iv) The following claims are equivalent a) 'P is an isomorphism, b) Sex is a basis of X if and only if 'P(S) is a basis of Y. 2.13~.

Show that the following maps are linear (i) the derivation map D : C 1 ([0,1]) ---+ CO ([0, 1]) that maps a C 1 -function into its derivative, I ---+ I'· (ii) the map that associates to every function of class CO([O, 1]) its integral over [0,1],

1---+

fa1 I(t) dt,

(iii) the primitive map CO ([0, 1]) ---+ C 1 ([O, 1]) that associates to every continuous function the primitive function

f

x

I(x)

---+

F(x)

:=

I(t) dt.

° 2.14 Definition. Let'P : X --+ Y be a linear map. The kernel of'P and the image of'P are respectively

I

ker'P:= {x E X 'P(x) = Im'P:= {y E Y

o},

I:J x EX: 'P(x) =

y}.

It is easily seen that ker'P is a linear subspace of the source space X and that ker'P = {o} if and only if 'P is injective. Also, Im'P is a linear subspace of the target space Y, and Im'P = Y if and only if 'P is surjective. If 1m 'P has finite dimension, its dimension is called the rank of 'P and denoted by Rank 'P. Of course 'P is surjective if and only if dim Y = Rank 'P, provided dim 1m 'P < +00. d. Coordinates in a finite-dimensional vector space Let X be a finite-dimensional vector space over lK and let (er, e2,"" en) be an ordered basis on X. Then every vector x E X writes uniquely as x = L~=l xiei, where Xl, X2,.·., Xn ElK. Then (el' e2, ... , en) defines a map E : X --+ lKn characterized by n

if and only if

X = Lxiei'

i=l

46

2. Vector Spaces and Linear Maps

h

7 £

£-1

Figure 2.2. Coordinate system in a finite-dimensional vector space.

It is trivial to verify that £ is linear, injective and surjective, hence an isomorphism, together with its inverse n

£-l(x)

= Lxiei'

x

= (xl,

x 2, ... , x n ).

i=l

We call £ the coordinate system related to the ordered basis (el' e2, .. ·, en) and refer to £(x) as to the coordinate vector of x with respect to the basis (el' e2, ... , en). Notice that £ maps ei to the ith vector ei of the canonical basis of lKn . Also notice that ordered bases and isomorphims £ : X -+ lKn are in one-to-one correspondence. In particular, any isomorphism £ : X -+ lKn is a coordinate system related to a suitable basis. In fact, the vectors el, e2, ... , en of X defined for i = 1, ... ,n by ei:= £-l(ei) form a basis of X by Proposition 2.12 (iii) and it is easy to check that n

if and only if

X

= Lxiei'

i=l

The use of a basis, or, equivalently, of a coordinate system, allows us to transfer definitions and results in lKn to similar definitions and claims in X. We have the following. 2.15 Proposition. Let X be a finite-dimensional vector space. (i) Let (er, e2, ... , en) be an ordered basis of X and let VI, V2, ... , vp E X, P ~ n, be p linearly independent vectors. Then we can choose n - p elements among el, e2, ... , en, say el, e2,"" e n - p, such that (VI, V2,"" vp,el, e2, .. ·, e n - p) is a basis of X. (ii) Assume that VI, V2, . .. , Vk spans X. Possibly eliminating some of the VI, V2, ... , Vk, we get a basis of X. (iii) Any two bases of X have the same number of elements.

The number of elements of a basis of a finite-dimensional space X is called the dimension of X and denoted by dim X. The following corollaries follow from Proposition 2.15.

2.1 Vector Spaces and Linear Maps

47

2.16 Corollary. Let X be a vector space of dimension n, let E : X _ OCn be a coordinate system on X and let W be a subspace of X. Then E(W) is a subspace ofOC n and dim W = dimE(W). 2.17 Corollary. Let X be a vector space of dimension n. Then

(i) n linearly independent vectors of X form a basis of X, (ii) if k > n, then k vectors of X are always linearly dependent, (iii) for every subspace W of X we have dim W ::; n, (iv) let V, W be two subspaces of X. Then V = W if and only if V C W and dim V = dim W. Let U and V be two subspaces of a vector space X. Then both U n V and U + V := { x E X I x = U + v, U E U, v E V} are linear subspaces of X. When Un V = {O}, we say that U + V is the direct sum of U and V and we write U EB V instead of U + V. Moreover if X = U EB V, we say that U and V are supplementary. Thus X = U EB V means that every x E X decomposes uniquely as x = u+w, u E U, v E V.

2.18 Corollary (Grassmann's formula). Let U and V be two finitedimensional subspaces of a vector space X. Then dim U + dim V

= dim(U n V) + dim(U + V).

2.19 'If. Show that every n-dimensional vector space is the direct sum of n subspaces of dimension 1. 2.20 'If. Let el, e2, ... , en be distinct vectors of X and let 1 < P < n. Then, trivially, Span {eI' e2, ... , ep} + Span{ep+I, ... ,en} = Span {eI' e2, ... , en}. Show that, if the ei's are linearly independent, then

2.21 'If. Let VI, V2 be two subspaces of a vector space V of finite dimension and assume that V = VI El7 V2. Then every vector v E V decomposes uniquely as v = VI + V2 with Vi E V. Show that the coordinate maps 1ri : V ---+ Vi, i = 1,2, 1ri(V) = Vi, are linear. 2.22 ,. Let 'P : X ---+ Y be an isomorphism from X onto Y. Show that dim X

= dim Y.

e. Matrices associated to a linear map Let X, Y be two vector spaces of dimension nand m respectively. We shall now show that every choice of an oriented basis, equivalently of a coordinate system, in X and Y yields an identification between linear maps and matrices. Let (el' e2, ... , en) be an oriented basis in X, (h, 12, ... , fm) be an oriented basis in Y and let E : X _ OCn , F : Y _ ocm be the corresponding

48

2. Vector Spaces and Linear Maps

Dl AlIIdeh.n

bre

'·011

1844

Die llneale Ausdehnungslehre

_

... ... _...... ••••• 11-0'11•

............

....... I'WIl,"".......

~

-

~

. ...

~

""fOII I,t.

Figure 2.3. Hermann Grassmann (1808-

1877) and his Ausdenungslehre.

coordinate systems. To every linear map f : X linear map L : ][(n -> ][(m defined by

->

Y one associates the (2.1)

see Figure 2.4, that maps the coordinates of a vector x EX, relative to the basis (el' e2, ... , en), into the coordinates of f(x) E Y, relative to the basis (fI, 12,···, 1m), and then, see Proposition 1.18, an m x n matrix L such that L(x) = Lx. We call Land L respectively, the map and the matrix associated to f using the coordinate systems £ and F, or, equivalently, using (eI, e2,···, en) and (fI, 12,·.·, 1m) as a basis in X and in Y, respectively. Since £-1 maps the ith vector ei of the canonical basis of ][(n to ei, L(ei) is the coordinate vector of £(ei) in the basis (fI, 12,···, 1m), hence L = [L;J where n

f(ej) =

L Ljk

(2.2)

i=l

Equivalently, see Proposition 1.18,

Since £ : X have

-> ][(n

and F : Y

£(ker £)

= ker L,

-> ][(m

are isomorphisms, we trivially

F(lm f)

= 1m L.

Hence, recalling Theorem 1.25, we have the following.

2.1 Vector Spaces and Linear Maps

49

.<....--/X~7 L Figure 2.4. The matrix associated to a linear map.

2.23 Theorem (Rank formula). Let £ : X --. Y be a linear map between linear spaces. If X is finite dimensional, then Rank £ = dimlm£

= dim X

- dimker£.

Proof. Let (el' e2, ... , en) be a basis of X. Then Ime = Span {e(el), ... ,e(en )}, hence dimlme < +00. Now choose a basis (ft, 12, ... , 1m) of Ime and consider the linear associated map L : IKn ---> IK m using the two bases (et, e2, . .. , en) on X and (ft, 12,· .. , 1m) on 1m e. Then Theorem 1.25 yields dimlme = dim 1m L = n - dimker L = n - dimkere.

o f. The space £(X, Y) Let X and Y be vector spaces of dimension nand m, and let (eI, e2,.··, en) and (fl, 12,···, fm) be two bases in X and Y. Then (2.2) defines a map M : .c(X, Y) --. Mm,n(lK) which is trivially injective and surjective. Since M is also linear, we deduce that .c(X, Y) and Mm,n(lK) are isomorphic. In particular, the vector space .c(X, Y) has dimension mn. A basis of .c(X, Y) is given by the mn maps {'f'~}, j = 1, ... , n, i = 1, ... ,m, defined in terms of the bases as if k

=1=

if k

= i,

i,

k

=

1, ... ,n.

'f';

The matrix associated to is the m x n matrix with all entries 0 except for the entry (i,j) where we have 1. Of course the matrix M(£) associated to £ depends on the coordinate systems we use on X and Y. When we want to emphasize such a dependence, we write

M[(£) to denote the matrix associated to £ : X --. Y using the coordinate systems t: on the source space and :F in the target space. The product of composition of linear maps corresponds to the product of composition of linear maps at the level of coordinates, hence to the product row by columns of the corresponding matrices. More precisely, we have the following.

50

2. Vector Spaces and Linear Maps

2.24 Proposition. Let

-+ Z -+ IK k

be two linear maps, be three systems of

rows by columns. Proof. In fact,

o A special case arises if X = Y = Z. In this case, the space £(X, X) of the linear maps from X into itself, also known as the space of endomorphisms of X and sometimes denoted by End (X), is closed under the operations of sum, multiplication by scalars and product of composition. We say that £(X, X) is an algebra with respect to these operations and, for any coordinate system £ on X, M~ : £(X, X) -+ Mn,n(IK) is an isomorphism of algebras. The set of isomorphisms from X into itself, called the automorphisms of X and denoted by Aut (X), is a group with respect to the composition. If dim X = nand £ : X -+ IK n is a coordinate system, then M~(Aut (X)) coincides with the group GL(n, IK) of all nonsingular n x n matrices,

I

GL(n, IK) := {L E Mn,n(IK) det L

:f- O}.

g. Linear abstract equations Let X, Y be two vector spaces over K A linear (abstract) equation in the unknown x is an equation of the form
=

y,

where

(2.3)

= 0 is

(i) the set of all solutions of the associate linear homogeneous equation
I

{ x E X x - Xo E ker
Taking into account the rank formula, we infer the following. 2.25 Corollary. Let X, Y be finite dimensional of dimension nand m respectively, and let

2.1 Vector Spaces and Linear Maps

51

(i) ifm < n, then dimkercp > 0, (ii) if m 2 n, then cp is injective iff Rank cp = n, (iii) if n = m, then cp is injective if and only if cp is surjective. The claim (iii) of Corollary 2.25 is one of the forms of Fredholm's alternative theorem: either cp(x) = y is solvable for every y E Y or cp(x) = 0 has a nonzero solution. 2.26 Example. A second order linear equation

ay" +by' +cy =

f,

a,b,c E IR,

can be seen as an abstract linear equation
f E CO(IR),

f by introducing the linear map

y .......
(2.4)

+ by' + cy.

(2.5)

f E CO(IR), see [GM1J,

°

(i) the set of all solutions of the associated homogeneous equation ay" +by' +cy = is a linear space, actually ker
Moreover, consider the map 'Y : 1R2 ....... C2(1R) that maps each (a, f3) E 1R2 to the unique solution of the initial value problem

ay" + by' + cy = 0, { yeO) = a, y' (0) = f3. It is easy to show that 'Y : 1R2 ....... C2(1R) is linear, and by definition, Im'Y = ker
°

h. Changing coordinates The coordinates of a vector depend on the chosen coordinate system. Let us discuss how they change. Let X be a vector space of dimension n, and let £ : X -+ ][{n and F : X -+ ][{n be two coordinate systems on X, that we label respectively as the old system and the new system. Denote by (e1' e2, ... , en) and (ft, 12, ... , fn) the bases associated respectively to the old coordinate system £ and to the new coordinate system F. The linear map L := F 0 £-1 : ][{n -+ ][{n maps the old £-coordinate vector of x E X to the new F-coordinate vector of x, see Figure 2.5. The matrix L associated to L in the basis (ell e2, ... , en) is

52

2. Vector Spaces and Linear Maps

L

Figure 2.5. Changing the basis.

We say that L or L changes coordinates from £ to :F. Remember that the ith column of L is the new .r-coordinate vector of the ith vector of the old basis, i.e, see (2.2), L = [Lj] where n ej

=

LL~k

(2.6)

i=l

Let m : X ....... X be the linear map defined by m(ei) := Ii Vi = 1, ... , m. Then the associated matrix M = [Mj] to m using the basis £ is M :=

[fUr) I£(12) 1···1 fUn)]

or, n

!J = LMjei' i=l

Therefore, comparing with (2.6), M = L -1. In conclusion (i) L maps the old coordinates to the new coordinates,

(ii) L -1 maps the old basis to the new basis. Thus L acts differently on the basis and on the coordinates. We say that the coordinates change in a contravariant way. This is nothing mysterious; for instance, 7000 g = 7 Kg: if the unit measure f 1 is, say 1000 times the unit measure el, then we expect that the number of units el associated to a measure will be 1/1000 of the number of units fl. 2.27 Example. Suppose we want to change from the canonical basis (er, e2) to a new one given by the vectors (1,2) and (3,4) in ]R2. The matrix that changes the basis from el = (1,0), e2 = (0,1) into !I = (el + 2 e2), h = (3 el + 4 e2) is

The old coordinates of a vector P can easily be obtained from the new ones, as P = x er

+ ye2 = ex !I + j3 h,

2.1 Vector Spaces and Linear Maps

53

thus, in the old coordinates,

and, conversely, we have

i. The associated matrix under changes of basis

Let X and Y be two vector spaces of dimension nand m. As before, the matrix associated to a linear map depends on the chosen coordinates on X and Y. Let £ : X ---... JKn, £' : X ---... JKn be two coordinate systems on X, and let F : X ---... JKn, F' : X ---... JKn be two coordinate systems on Y. Of course, for every map £ we have £ = Id y 0 £ 0 Id x , consequently

or, in other words, we can state the following.

2.28 Proposition. Given the previous notation, let R E Mn,n(JK) be the matrix that changes coordinates from £ to £', let S E Mm,m(JK) be the matrix that changes coordinates from F to F', let A A' be the matrices that represent £ respectively, in the systems of coordinates £ and F and in the systems £' and F'. Then

2.29 Corollary. Let A E Mn,n(JK) and let A: JKn ---... JKn be the associated linear operator A(x) := Ax. Let (f1 , f 2 , ... , fn ) be a basis ofJKn. Then the matrix associated to A using the basis (f1 , f 2 , ... , fn ), both in the source and the target JKn, is the matrix

A':= S-lAS where

Proof. Let (e1, e2, ... , en) be the canonical basis of OCn , then Se; = f; are the coordinates of f; in the basis (e1, e2, ... , en), ASe; = Af; is the coordinate vector of A (f;) in canonical coordinates and, finally, S -1 ASe; is the coordinate vector of A (f;) in the (f1, f2, ... , f n ) basis. 0

54

2. Vector Spaces and Linear Maps

j. The dual space £(X, lK) Linear maps from X into lK play a special role. Let X be a vector space over lK with dim X = n. Linear maps from X into lK are also called linear forms or coveetors, and the space of linear forms, £(X, lK), also denoted by X*, is called the dual space of X. Suppose X is finite dimensional. Then, as we have seen, X* has dimension nand, if (el' e2, ... , en) is a basis of X, then every linear form £ : X ----t lK is represented as a 1 x n matrix L that maps the coordinates x of x E X to £(x), i.e., n

X= Lxiei' x=(x l ,x2, ... ,xn )

if

Lx = £(x)

i=l

or, L = (ir

Ihi··· /lnl

and n

£(x)

=

\-I

vx

Llixi,

=

(1. X , X 2 , ••• ,

x n) .

i=l

Consider now the linear maps e l , e 2 , ... , en : X

----t

lK defined by

(2.7)

"fi,j = 1, ... ,n.

2.30 Proposition. We have = 1, ... ,n, the map e i of x, so that

(i) for i

:

X

----t

lK maps x E X to the ith coordinate

n

X= L

"fxEX,

ei(x)ei

i=l

(ii) (e\ e 2, ... , en) is a basis on X*, (iii) if x = L:~l xiei E X and £ = L:~=l liei E X*, then £(x) = L:~l lixi. Proof. (i) If x = 2::?=1 xiei, then ej(x) = 2::~1 xiej(ei) = xj. (ii) Let f. := 2::';=1 pje j . Then f.(e;) = Pi Vi. Thus, if f.(x) = 0 'Ix we trivially have Pi = 0 Vi. (iii) In fact,

f.(x)

=

= tljej(txiei)

(t1jej)(I>iei) j=l i=l n

n

= LL:Zjxiej(ei) i=l j=l

j=l n

n

i=l n

= LLljxioij = L1i xi . i=l j=l

i=l D

The system of linear maps (e l , e 2 , .•• , en) characterized by (2.7) is called the dual basis of (el' e2, ... , en) in X*.

2.1 Vector Spaces and Linear Maps

55

CALCOLO

GEO 1ETRICO _n~ll_

O,£lUI051 DELU IASIC> DEDOtllTA

_om.,,. _.. _ ,IAICO

....

" " ..,

"" •

U'ht"

_

IWIU1

T01UNO

-

PRATSI,LI ROCCA eDITORE

h~=_~

h!i!EU

,......,~ ..,'

. . =M..

'-i~.

'ISO

Figure 2.6. Giuseppe Peano (1858-1932) and the frontispiece of his Calcolo Geometrico.

2.31 Remark. Coordinates of vectors or covectors of a vector space X of dimension n are both n-tuples. However, to distinguish them, it is useful to index the coordinates of covectors with lower indices. We can reinforce this notation even more by writing the coordinates of vectors as column vectors and coordinates of covectors as row vectors.

k. The bidual space Of course, we may consider also the space of linear forms on X*, denoted by X** and called the bidual of X. Every v E X identifies a linear form on .c(X*,IK), by defining v** : X* -+ IK by v**(l) := l(v). The map , : X -+ X**, x -+ ,(x):= x** we have just defined is linear and injective. Since dimX** = dimX* = dimX, , is surjective, hence an isomorphism, and we call it natural since it does not depend on other structures on X, as does the choice of a basis. Since X** and X are naturally isomorphic, there is a "symmetry" between the two spaces X and X*. To emphasize this symmetry, it is usual to write instead of if

< , >: X* x X

-+

IK,

<
>:=
2.32'. Let X be a vector space and let X' be its dual. A duality between X and X' is a map < , >: X' X X -+ lK that is

56

2. Vector Spaces and Linear Maps

(i) linear in each factor,

< 'P, ax + /3y > = a < 'P, x> +/3 < 'P, Y >, < a'P + /3'IjJ, x> = a < 'P, x> +/3 < 'IjJ, x>, for all a, /3 E IK, x, Y E X and 'P, 'IjJ E X*, (ii) nondegenemte i.e., if <'P,x>=OVx, then'P=O, if

< 'P, x > = 0 V'P, then x = O. -+ < 'P, x > that evaluates a linear map 'P : X

Show that the evaluation map ('P, x) at x E X is a duality.

-+

IK

1. Adjoint or dual maps Let X, Y be vector spaces, X* and Y* their duals and < , > x and < , >y the evaluation maps on X* x X and Y* x Y. For every linear map £ : X ---+ Y, one also has a map £* : Y* ---+ X* defined by

< £*(y*),x >:=< y*,£(x) >

Vx E X, Vy* E Y*.

It turns out that £* is linear. Now if (el' e2, , en) and (fI,···, fm) are bases in X and Y respectively, and (e l , e2, , en) and (J1, fm) are the dual bases in X* and Y*, then the associated matrices L = [LJ] E Mm,n(lK) and M = [MJ] E Mn,m(lK), associated respectively to £ and £*, are defined by

p, ... ,

n

m

£(ei) =

"L L? fh,

£*(Jh) =

"L Mh ei . i=l

h=l By duality,

Mh = < £*(Jh), ei > = < fh, £(ei) > = L? i.e., M = LT. Therefore we conclude that ifL is the matrix associated to £ in a given basis, then L T is the matrix associated to £* in the dual basis. We can now discuss how coordinate changes in X reflect on the dual space. Let X be a vector space of dimension n, X* its dual space, (el, ... , en), (El' E2, ... , En) two bases on X and (e l , e2, ... , en) and (E l , E2, ... , En) the corresponding dual bases on X*. Let £ : X ---+ X be the linear map defined by £(ei) := Ei Vi = 1, ... , n. Then by duality

< £*(Ei),ej > = < Ei,£(ej) > = < Ei,Ej > =

Oij

= < ei,ej >

Vi,j,

£*(Ei ) = ei Vi = 1, ... , n. If Land L T are the associated matrices to £ and £*, L changes basis from (el' e2, ... , en) to (El' E2, ... , En) in X, and L T changes basis in the dual space from (E l , E2 , ... , En) to (e l , e2, ... , en), n

Ei = "LLjei' i=l

n

ei

= "L(LT){E j . j=l

2.2 Eigenvectors and Similar Matrices

n

n

n

57

n

Lbiei = LLbi(LT){E j = Lai ei . i=l

i=l j=l

i=l

or

a=bL.

In other words, the coordinates in X* change according to the change of basis. We say that the change of coordinates in X* is covariant.

2.2 Eigenvectors and Similar Matrices Let A : X ~ X be a linear operator on a vector space. How can we describe the properties of A that are invariant by isomorphisms? Since isomorphims amount to changing basis, we can put it in another way. Suppose X is finite dimensional, dim X = n, then we may consider the matrix A associated to A using a basis (we use the same basis both in the source and the target X). But how can we catch the properties of A that are independent of the basis? One possibility is to try to choose an "optimal" basis in which, say, the matrix A takes the simplest form. As we have seen, if we choose two coordinate systems £ and F on X, and S is the matrix that changes coordinates from £ to F, then the matrices A and B that represent A respectively in the basis £ and F are related by

B = SAS- 1 . Therefore we are asking for a nonsingular matrix S such that S-l AS has the simplest possible form: this is the problem of reducing a matrix to a canonical form. Let us try to make the meaning of "simplest" for a matrix more precise. Suppose that in X there are two supplementary invariant subspaces under A

Then every x E X splits uniquely as x = Xl + X2 with Xl E W 1, X2 E W2, and A(x) = A(X1) + A(X2) with A(xt} E W 1 and A(X2) E W 2. In other words, A splits into two operators A 1 : W 1 ~ W 1, A : W 2 ~ W 2 that are the restrictions of A to W 1 and W 2 . Now suppose that dimX = n and let (e1' e2, ... , ek) and (ft, 12, ... , fn-k) be two bases respectively of W 1 and W 2 . Then the matrix associated to A in the basis (e1' e2,···, ek,ft, 12,···, fn-k) of X has the form

58

2. Vector Spaces and Linear Maps

where some of the entries are zero. If we pursue this approach, the optimum would be the decomposition of X into n supplementary invariant subspaces WI, W2,.'" W n under A of dimension 1,

In this case, A acts on each Wi as a dilation: A(x) = AiX Vx E Wi for some Ai E K Morever, if (el' e2, ... , en) is a basis of X such that ei E Wi for each i, then the matrix associated to A in this basis is the diagonal matrix

2.2.1 Eigenvectors a. Eigenvectors and eigenvalues As usual, lK denotes the field lR or C. 2.33 Definition. Let A : X - t X be a linear operator on a vector space X over lK. We say that x E X is an eigenvector of A if Ax = AX for some A E K If x is a nonzero eigenvector, the number A for which A(x) = AX is called an eigenvalue of A, or more precisely, the eigenvalue of A relative to x. The set of eigenvalues of A is called the spectrum of A. If A E Mn,n(lK), we refer to eigenvalues and eigenvectors of the associated linear operator A : lKn - t lKn , A(x) := Ax, as the eigenvalues and the eigenvectors of A. From the definition, A is an eigenvalue of A if and only if ker(A Id A) =1= {O}, equivalently, if and only if AId - A is not invertible. If A is an eigenvalue, the subspace of all eigenvectors with eigenvalue A

VA

:= {xEXIA(x) =AX}

=ker(AId-A)

is called the eigenspace of A relative to A. 2.34 Example. let X = Coo ([0, 1r]) be the linear space of smooth functions that vanish at 0 and 1r and let D2 : X -> X be the linear operator D 2 (J) := f" that maps every function f into its second derivative. Nonzero eigenvectors of the operator D 2 , that is, the nonidentically zero functions y E Coo [0, IJ such that D 2 y(x) = AY(X) for some A E ~, are called eigenfunctions. 2.35 Example. Let X be the set Pn of polynomials of degree less than n. Then, each P k C Pn k = 0, ... ,n is an invariant subspace for the operator of differentiation. It has zero as a unique eigenvalue.

2.2 Eigenvectors and Similar Matrices

59

2.36'. Show that the rotation in ]R2 by an angle () has no nonzero eigenvectors if 0,11", since in this case there are no invariant lines.

() f=

2.37 Definition. Let A : X ---? X be a linear operator on X. A subspace We X is invariant (under A) if A(W) c W. In the following proposition we collect some simple properties of eigenvectors.

2.38 Proposition. Let A : X

---?

X be a linear operator on X.

(i) x i= 0 is an eigenvector if and only if Span {x} is an invariant subspace under A. (ii) Let A be an eigenvector of A and let VA be the corresponding eigenspace. Then every subspace W C VA is an invariant subspace under A, i.e., A(W) C W. (iii) dim ker(A Id - A) > 0 if and only if A is an eigenvalue for A. (iv) Let W C X be an invariant subspace under A and let A be an eigenvalue for A 1w . Then A is an eigenvalue for A : X ---? X. (v) A is an eigenvalue for A if and only if 0 is an eigenvalue for AId - A. (vi) Let cp : X ---? Y be an isomorphism and let A : X ---? X be an operator. Then x E X is an eigenvector for A if and only if cp( x) is an eigenvector for cp 0 A 0 cp-l, and x and cp(x) have the same eigenvalue. (vii) Nonzero eigenvectors with different eigenvalues are linearly independent. Proof. (i), ... , (vi) are trivial. To prove (vii) we proceed by induction on the number k of eigenvectors. For k = 1 the claim is trivial. Now assume by induction that the claim holds for k - 1 nonzero eigenvectors, and let el, e2, ... , ek be such that ei f= 0 Vi = 1, ... ,k, A(ej) = Ajej Vj = 1, ... ,k with Aj f= Ai Vi f= j. Let (2.8) be a linear combination of q, e2, ... , ek' From (2.8), multiplying by Al and applying A we get alAlel alAlq

+ a2Ale2 + + a2A2e2 +

+ akAlek = 0, + akAkek = 0,

consequently k

L)Aj - Al)ajej = O. j=2 By the inductive assumption, aj(Aj - AI) = 0 Vj = 2, ... , n, hence aj = 0 for all j :2: 2. We then conclude from (2.8) that we also have al = 0, i.e., that q, e2, . .. , ek are linearly independent. 0

Let A : X ---? X be a linear operator on X of dimension n, and let A be the associated matrix in a coordinate system £ : X ---? JKn. Then (vi) implies that x E X is an eigenvector of A if and only if x := £(x) is an eigenvector for x ---? Ax and x and x have the same eigenvalue. From (vii) Proposition 2.38 we infer the following.

60

2. Vector Spaces and Linear Maps

2.39 Corollary. Let A : X -> X be a linear operator on a vector space X of dimension n. If A has n different eigenvalues, then X has a basis formed by eigenvectors of A.

b. Similar matrices Let A : X -> X be a linear operator on a vector space X of dimension n. As we have seen, if we fix a basis, we can represent A by an n x n matrix. If A and A' E Mn,n(lK) are two such matrices that represent A in two different bases (e1' e2,"" en) and (E1' E2, ... , En), then by Proposition 2.28 A' = S-l AS where S is the matrix that changes basis from (el' e2,.'" en) to (El' E2,"" En). 2.40 Definition. Two matrices A, B E M n n(lK) are said to be similar if there exists S E GL(n, lK) such that B = S-i AS. It turns out that the similarity relation is an equivalence relation on matrices, thus n x n matrices are partitioned into classes of similar matrices. Since matrices associated to a linear operator A : X -> X, dim X = n, are similar, we can associate to A a unique class of similar matrices. It follows that if a property is preserved by similarity equivalence, then it can be taken as a property of the linear operator to which the class is referred. For instance, let A : X -> X be a linear operator, and let A, B be such that B = S-lAS. By Binet's formula, we have

det B

= det S-l det A det S =

_1_ det A det S = det A. detS

Thus we may define the determinant of the linear map A : X

->

X by

detA:= detA where A is any matrix associated to A. c. The characteristic polynomial Let X be a vector space of dimension n, and let A : X operator. The function

A -> PA(A) := det(AId - A),

->

X be a linear

A E lK,

is called the characteristic polynomial of A. It can be computed by representing A by a matrix A in a coordinate system and computing PA(A) as the characteristic polynomial of any of the matrices A representing A,

PA(A) = PA(A) = det(AId - A). In particular, it follows that PA( ) : lK -> lK is a polynomial in A of degree n, and that the roots of PA(A) are the eigenvalues of A or of A. Moreover, we can state

2.2 Eigenvectors and Similar Matrices

61

2.41 Proposition. We have the following.

(i) Two similar matrices A, B have the same eigenvalues and the same characteristic polynomials.

(ii) If A has the form

where for i = 1, ... ,k, each block Ai is a square matrix of dimension k i with principal diagonal on the principal diagonal of A, then

PA(S) = PA1(S)' PA2(S)., ·PAk(S). (iii) We have det(sId - A) = sn - trAs n- 1

+ ... + (-l)ndetA

n

=

sn

+ 2)-1)k aks n-k k=1

where tr A := 2:7=1 Ai is the trace of the matrix A, and ak is the sum of the determinants of the k x k submatrices of A with principal diagonal on the principal diagonal of A. Proof. (i) If B = SAS-l, S E GL(n,IK), then sId - B = S(sId - A)S-I, hence det(sId - B) = detSdet(sId - A)(detS)-1 = det(sId - A). (ii) The matrix sId - A is a block matrix of the same form

sId-AI

0

o

o

I'Id-A, I

o

o

0

hence det(s Id - A) = n:=1 det(s Id - Ai)' (iii) We leave it to the reader. D

Notice that there exist matrices with the same eigenvalues that are not similar, see Exercise 2.73.

62

2. Vector Spaces and Linear Maps

d. Algebraic and geometric multiplicity 2.42 Definition. Let A : X ~ X be a linear operator, and let A E IK be an eigenvalue of A. We say that A has geometric multiplicity kEN if dimker(Ald - A) = k. Let PA(S) be the characteristic polynomial of A. We say that A has algebraic multiplicity k if where q(A)

1= o.

2.43 Proposition. Let A : X ~ X be a linear operator on a vector space of dimension n and let A be an eigenvalue of A of algebraic multiplicity m. Then dim ker(A Id - A) :::; m. Proof. Let us choose a basis (el, e2, ... , en) in X such that (el, e2, ... , ek) is a basis for VA := ker(.\ Id - A). The matrix A associated to A in this basis has the form

AId

C

o

D

A=

where the first block, AId, is a k x k matrix of dimension k = dim VA. Thus Proposition 2.41 (ii) yields PA(S) = det(sId - A) = (s - A)kpD(s), and the multiplicity of A is at least k. 0

e. Diagonizable matrices 2.44 Definition. We say that A E M n ,n(lK) is diagonizable, if A is similar to a diagonal matrix. 2.45 Theorem. Let A : X ~ X be a linear operator on a vector space of dimension n, and let (el' e2, ... , en) be a basis of X. The following claims are equivalent.

(i) el, e2, ... , en are eigenvectors of A and AI, A2, ... , An are the relative eigenvalues.

(ii) We have A(x) = 2:~=1 Aixiei for all x E X if x = 2:~1 xiei. (iii) The matrix that represents A in the basis (el' e2, ... , en) is diag (AI, A2, ... , An).

(iv) If A is the matrix associated to A in the basis (fl, fz,···, in), then

S-l AS = diag (AI, A2' ... , An) where S is the matrix that changes basis from (iI, fz,···, in) to (el' e2, ... , en), i.e., the ith column of S is the coordinate vector of the eigenvector ei in the basis (iI, fz,···, fn).

2.2 Eigenvectors and Similar Matrices

Proof. (i) ¢} (ii) by linearity and (iii) Finally (iii) ¢} (iv) by Corollary 2.29.

¢}

63

(i) since (iii) is equivalent to A(ei) = Aiei. 0

2.46 Corollary. Let A: X -- X be a linear operator on a vector space of dimension n. Then the following claims are equivalent.

(i) X splits as the direct sum of n one-dimensional invariant subspaces (under A), X

= WI EB··· EB Wn .

(ii) X has a basis made of eigenvectors of A. (iii) Let AI, A2,' .. , Ak be all distinct eigenvalues of A, and let VAl' ... , VAk be the corresponding eigenspaces. Then k

LdimVAi =n. i=l

(iv) If A is the matrix associated to A in a basis, then A is diagonizable. Proof. (i) implies (ii) since any nonzero vector in any of the Wi'S is an eigenvector. Denoting by (el, e2, ... , en) a basis of eigenvectors, the spaces Wi := Span {ei} are supplementary spaces of dimension one, hence (ii) implies (i). (iii) is a rewriting of (i) since for each eigenvalue A, VA is the direct sum of the Wi'S that have A as the corresponding eigenvalue. Finally (ii) and (iii) are equivalent by Theorem 2.45. 0

2.47 Linear equations. The existence of a basis of X of eigenvectors of an operator A : X -- X makes solving the linear equation A(x) = y trivial. Let (el' e2, ... , en) be a basis of X of eigenvectors of A and let AI, A2,"" An be the corresponding eigenvalues. Writing x, y E X in this basis, n X

=

Lxiei' i=l

=y

we rewrite the equation A(x)

as

n

L(AiXi - yi)ei i=l

i.e., as the diagonal system AlXl = yl, A2X2 = y2,

!

... , AnXn

Therefore

= yn.

=

0,

64

2. Vector Spaces and Linear Maps

(i) suppose that 0 solution

IS

not an eigenvalue, then A(x) n X

=

y has a unique

.

L

y'

):"e i .

i=1

'

(ii) let 0 be an eigenvalue, and let Vo = Span { el, e2, ... , ed. Then A(x) = y is solvable if and only if yl = ... = yk = 0 and a solution of A(x) = y is Xo := L:7=k+l By linearity, the space of all

fei.

solutions is the set {x E X

Ix -

Xo E ker A = Vo }.

2.48~.

Let A : X --+ X be a linear operator on a finite-dimensional space. Show that A is invertible if and only if 0 is not an eigenvalue for A. In this case show that 1/>.. is an eigenvalue for A-I if and only if>" is an eigenvalue for A.

f. Triangularizable matrices First, we notice that the eigenvalues of a triangular matrix are the entries of the principal diagonal. We can then state the following.

2.49 Theorem. Let A E Mn,n(lK). If the characteristic polynomial decomposes as a product of factors of first degree, i.e., if there are (not necessarily distinct) numbers AI, A2, ... , An E lK such that

then A is similar to an upper triangular matrix. Proof. Let us prove the following equivalent claim. Let A : X --+ X be a linear operator on a vector space of dimension n. If PA(>") factorizes as a product of factors of first degree, then there exists a basis (Ul' U2, ... , un) of X such that Span {uI}, Span {UI, U2}, Span {Ul, U2, U3}, ... , Span {Ul, U2, .. · Un} are invariant subspaces under A. In this case we have for the linear operator A(x) = Ax associated to A

(

a~ul,

AUI

= A(uI) =

AU2

= A(U2) = a~ul + a~u2,

~un = A(un) = a~ul + a~u2 + ... + a~Un,

i.e., the matrix A associated to A using the basis (UI, U2, ... , Un) is upper triangular,

A=

(

~~ .

o

o

2.2 Eigenvectors and Similar Matrices

65

We proceed by induction on the dimension of X. If dim X = 1, the claim is trivial. Now suppose that the claim holds for any linear operator on a vector space of dimension n - 1, and let us prove the claim for A. From

PA(A) = det(A Id - A) = (A - A1) ... (A - An), A1 is an eigenvalue of A, hence there is a corresponding nonzero eigenvalue U1 and Span {ut} is an invariant subspace under A. Now we complete {ut} as a basis by adding vectors V2, . .. Vn, and let B be the restriction of the operator A to Span {V2, ... Vn }. Let B be the matrix associated to B in the basis (V2, ... , v n ), and let A be the matrix associated to A in the basis (u 1, u2, . .. , Un). Then

A=

where

o

at = A1.

B

Thus

PA(A)

= PA(A) =

(A - A1) PB(A)

=

(A - Ad PB(A).

It follows that the characteristic polynomial of B is PB(A) = (A - A2) the inductive hypothesis, there exists a basis (U2, ... un) of Span {V2,

(A - An). By ,Vn} such that

Span {U2}, Span {U2, U3}, ... , Span {U2, .. . , un} are invariant subspaces under B, hence

are invariant subspaces under A.

o

2.2.2 Complex matrices When lK = te, a significant simplification arises. Because of the fundamental theorem of algebra, the characteristic polynomial PA(A) of every linear operator A : X - t X over a complex vector space X of dimension n, factorizes as product of n factors of first degree. In particular, A has n eigenvalues, if we count them with their multiplicities. From Theorem 2.49 we conclude the following at once.

2.50 Corollary. Let A E Mn,n(C) be a complex matrix. Then A is similar to an upper triangular matrix, that is, there exists a nonsingular matrix S E Mn,n(C) such that S-l AS is upper triangular. Moreover,

2.51 Corollary. LetA E Mn,n(C)be a matrix. Then A is diagonizable (as a complex matrix) if and only if the geometric and algebraic multiplicities of each eigenvalue agree.

66

2. Vector Spaces and Linear Maps

Proof. Let A1, A2, ... , Ak be the distinct eigenvalues of A, for each i = 1, ... k, let and VA; respectively be the algebraic multiplicity and the eigenspace of Ai. If dim VA; = mi Vi, then by the fundamental theorem of algebra

mi

n

k

2..= dim VA; = 2..= mi = i=l

n.

i=l

Hence A is diagonizable, by Corollary 2.46. Conversely, if A is diagonizable, then L:f=l dim VA; = n, hence by Proposition 2.43 dim VA; :::: mi, hence k

n

= 2..= mi 2':

i=l

k

2..= dim VA; i=l

= n. o

2.52 Remark (Real and complex eigenvalues). If A E Mn,n(J~), its eigenvalues are by definition the real solutions of the polynomial equation det(.\Id - A) = O. But A is also a matrix with complex entries, A E Mn,n(C) and it has as eigenvalues which are the complex solutions of det(.\Id - A) = O. It is customary to call eigenvalues of A the complex solutions of det(.\ Id - A) = 0 even if A has real entries, while the real solutions of the same equation, which are the eigenvalues of the real matrix A following Definition 2.33, are called real eigenvalues. The further developments we want to discuss depend on some relationships among polynomials and matrices that we now want to illustrate.

a. The Cayley-Hamilton theorem Given a polynomial f(t) = I:~=l aktk, to every n x n matrix A we can associate a new matrix f (A) defined by n

n

f(A):= aoId + Lak Ak =: LakAk,

k=l

k=O

if we set A 0 := Id. It is easily seen that, if a polynomial f(t) factors as f(t) = p(t)q(t), then the matrices p(A) and q(A) commute, and we have f(A) = p(A)q(A) = q(A)p(A).

2.53 Proposition. Let A E Mn(C), and let p(t) be a polynomial. Then

(i) if.\ is an eigenvalue of A, then p(.\) is an eigenvalue of p(A), (ii) if J.t is an eigenvalue of p(A), then J.t = p(.\) for some eigenvalue .\ ofA. Proof. (i) follows observing that A k , kEN, is an eigenvalue of A k if A is an eigenvalue

of A.

(ii) Since J1 is an eigenvalue of p(A), the matrix p(A) - J1 Id is singular. Let p(t) = be of degree k, ak l' O. By the fundamental theorem of algebra we have

L:f=l ai ti

2.2 Eigenvectors and Similar Matrices

67

n k

p(t) - J.t = ak

(t - ri),

i=l

hence p(A) - J.tld = akrr~=l(A - riId) and, since p(A) - J.tId is singular, at least one of its factors, say A - rl Id, is singular. Consequently, rl is an eigenvalue of A and trivially, p(rl) - J.t = O. 0

Now consider two polynomials P(t) := Lj Pjt j and Q(t) := Lk Qktk with n x n matrices as coefficients. Trivially, the product polynomial R(t) := P(t)Q(t) is given by R(t) := LPjQktj+k. j,k

2.54 Lemma. Using the previous notation, if A E Mn,n((C) commutes with the coefficients of Q(t), then R(A) = P(A)Q(A). Proof. In fact, R(A)

= L:::PjQkAJ+k = L:::(PjAj)(QkAk) j,k

=

j,k

(L:::PjAj) (L:::QkAk) j

= P(A)Q(A).

k

o

2.55 Theorem (Cayley-Hamilton). Let A E Mn,n((C) and let PA(S) be its characteristic polynomial, PA(S) := det(s Id - A). Then PA(A) = O. Proof. Set Q(s) := sId - A, sEC, and denote by cofQ(s) the matrix of cofactors of Q(s). By Laplace's formulas, see (1.22), cofQ(s) Q(s) = Q(s) cofQ(s) = det Q(s) Id = PA(S) Id. Since A trivially commutes with the coefficents Id and A of Q(s), Lemma 2.54 yields PA(A) = PA(A) Id = cofQ(A) Q(A) = cofQ(A)· 0 =

o. o

b. Factorization and invariant subspaces Given two polynomials PI, Pz with deg PI :::: deg Pz , we may divide PI by Pz , i.e., uniquely decompose PI as PI = QPz + R where deg R < deg Pz . This allows us to define the greatest common divisor (g.c.d.) of two polynomials that is defined up to a scalar factor, and compute it by Euclid's algorithm. Moreover, since complex polynomials factor with irreducible factors of degree 1, the g.c.d. of two complex polynomials is a constant polynomial if and only if the two polynomials have no common root. We also have 2.56 Lemma. Let p(t) and q(t) be two polynomials with no common zeros. Then there exist polynomials a(t) and b(t) such that a(t) p(t) + b(t) q(t) = 1 "It E C.

68

2. Vector Spaces and Linear Maps

We refer the readers to [GM2], but for their convenience we add the proof of Lemma 2.56 Proof. Let P := {r(t) := a(t)p(t)

+ b(t)q(t) Ia(t), b(t)

are polynOmials}

and let d = Cip + fJq be the nonzero polynomial of minimum degree in P. We claim that d divides both P and q. Otherwise, dividing p by d we would get a nonzero polynomial r := p - md and, since p and d are in P, r = p - md E P also, hence a contradiction, since r has degree strictly less than d. Then we claim that the degree of d is zero. Otherwise, d would have a root that should be common to p and q since d divides both p and q. In conclusion, d is a nonzero constant polynomial. 0

2.57 Proposition. For every polynomial p, the kernel of p(A) is an invariant subspace for A E Mn,n(C). Proof. Let w E ker p(A). Since t p(t) = p(t) t, we infer Ap(A) = p(A)A. Therefore

p(A)(Aw)

= (p(A) A)w = (Ap(A))w = Ap(A)w = AO = o. o

Hence Aw E kerp(A).

2.58 Proposition. Let p be the product of two coprime polynomials, p(t) = PI (t)p2(t), and let A E Mn,n(C). Then kerp(A) := kerpl(A) EB kerp2(A). Proof. By Lemma 2.56, there exist two polynomials aI, a2 such that al (t)PI (t) a2(t)p2(t) = 1. Hence

+

(2.9) Set WI := kerpI(A),

W2 := kerp2(A),

W:= kerp(A).

Now for every x E W, we have al (A)PI (A)x E W2 since P2(A)adA)PI(A)x = P2(A)(Id - a2 (A)P2 (A))x = (Id - a2 (A)p2 (A))p2 (A)x = al(A)pdA)P2(A)x = adA)p(A)x =

and, similarly, a2(A)p2(A)x E WI. Thus W = WI fact, if y E WI n W2, then by (2.9), we have y

+ W2.

o.

Finally W = WI EB W2. In

= al (A)PI (A)y + a2 (A)P2 (A)y = 0 + 0 = O. o

c. Generalized eigenvectors and the spectral theorem 2.59 Definition. Let A E Mn,n(C), and let ..\ be an eigenvalue of A of multiplicity k. We call generalized eigenvectors of A relative to the eigenvalue ..\ the elements of

W

:=

ker(..\Id - A)k.

Of course, (i) eigenvectors relative to ..\ are generalized eigenvectors relative to ..\, (ii) the spaces of generalized eigenvectors are invariant subspaces for A.

2.2 Eigenvectors and Similar Matrices

69

2.60 Theorem. Let A E Mn,n(C). Let AI, A2,"" Ak be the eigenvalues of A with multiplicities ml, m2, ... , mk and let WI, W2, ... , Wk be the subspaces of the relative generalized eigenvectors, Wi := ker(Ai Id - A). Then (i) the spaces WI, W 2, ... , W k are supplementary, consequently there is a basis of en of generalized eigenvectors of A, (ii) dim Wi = mi. Consequently, if we choose A' E Mn,n(JK) using a basis (el, e2,···, en) where the the first ml elements span WI, the following m2 elements span W 2 and the last mk elements span Wk. We can then write the matrix A' in the new basis similar to A where A' has the form

o A/ =

~ o

where for every i = 1, ... , k, the block Ai is a mi x mi matrix with Ai as the only eigenvector with multiplicity mi and, of course, (Ai Id - Ai)m i = O. Proof. (i) Clearly the polynomials Pl(S) := (AI - s)m 1 , P2(S) := (A2 - s)m 2 , ••. , Pk(S) := (Ak - s)m k factorize PA and are coprime. Set N i := PiCA) and notice that Wi = kerN i . Repeatedly applying Proposition 2.58, we then get

kerpA(A)

= ker(N l N2 ... N k ) = ker(N l ) EB ker(N2N3'" Nk) = ... = WI EB W2 EB ... EB Wk·

en.

(i) then follows from the Cayley-Hamilton theorem, kerpA(A) =

(ii) It remains to show that dim Wi = mi Vi. Let (et, e2, ... , en) be a basis such that the first hI elements span WI, the following h2 elements span W2 and the last hk elements span Wk. A is therefore similar to a block matrix

o A'=

o where the block Ai is a square matrix of dimension hi := dim Wi. On the other hand, the qi x qi matrix (Ai Id - Ai)m i = 0 hence all the eigenvalues of Ai Id - Ai are zero. Therefore Ai has a unique eigenvalue Ai with multiplicity hi, and PA i (s) := (s - Ai)h i . We then have k

PA(S) = PA'(S) =

k

I1 PA (s) = I1 (s i

i=l

A)h i

,

i=l

and the uniqueness of the factorization yields hi = mi. The rest of the claim is trivial.

o

70

2. Vector Spaces and Linear Maps

Another proof of dim Wi = mi goes as follows. First we show the following. 2.61 Lemma. If 0 is an eigenvalue of BE Mn.n(C) with multiplicity m, the 0 is an eigenvalue for Bm with multiplicity m.

Proof. The function 1 - Am, A E C, can be factorized as 1- Am = f1~(/ (wi - A) where w := e i 2." 1m is a root of unity (the two polynomials have the same degree and take the same values at the m roots of the unity and at 0). For z, tEe

hence

n

m-l

zmld - B m = zmld _B m =

(wizld - B).

i=O If we set qo(z):= f1~ol q(wiz), we have qo(O)

n

f=

0, and

m-l

PBm (zm) := det(zm Id - B m ) =

n

m-l

PB(WiZ) =

i=O

2

(wi z)mq(w i z) = zm qo(z).

i=O

On the other hand PBm = sTq1(r) for some ql with ql(O) following (2.10) PBm(S) = smq1(s), i.e., 0 is an eigenvalue of multiplicity m for Bm.

f=

(2.10) 0 and some r ;::: 1. Thus,

o

Another proof that dim Wi = mi in Theorem 2.60. Since

n n Lmi = LdimWi =dimX, i=l

i=l

it suffices to show that dim Wi ~ mi "Ii. Since 0 is an eigenvalue of B := Ai Id - A of multiplicity m := mi, 0 is an eigenvalue of multiplicity m for B m by Lemma 2.61. Since Wi is the eigenspace corresponding to the eigenvalue 0 of B m , it follows from Proposition 2.43 that dim Wi ~ m. 0

d. Jordan's canonical form 2.62 Definition. A matrix B E Mn,n(l[{) is said to be nilpotent if there exists k ;::: 0 such that B k = o. Let BE Mq,q(C) be a nilpotent matrix and let k be such that B k = 0, but B k- l =I- o. Fix a basis (el' e2, ... , e s ) of ker B, and, for each i = 1, ... , s, k . . 1 set et := ei and define e~, e;, ... ,ei i to solve the systems Be~ := e~- for j = 2,3 ... as long as possible. Let {e{}, j = 1, ... ,ki , i = 1, ... ,q, be the family of vectors obtained this way.

2.63 Theorem (Canonical form of a nilpotent matrix). Let B be a q x q nilpotent matrix. Using the previous notation, {e)} is a basis of C q. Consequently, if we write B with respect to this basis, we get a q X q matrix B' similar to B of the form

2.2 Eigenvectors and Similar Matrices

o o

o

~

B'=

71

(2.11)

o where each block B i has dimension k i and, if k i

0 1 0 ... 0 0 1 ... 0 0 0 ...

> 1, it has the form

0 0 0

(2.12)

1

0 0 0

... 0

The reduced matrix B' is called the canonical Jordan form of the nilpotent matrix B. Proof. The kernels Hj := ker Bj of Bj, j = 1, ... , k, form a strictly increasing sequence of subspaces {O} = Ho C HI C Hz C ... C Hk-l C H k := C q . The claim then follows by iteratively applying the following lemma.

o

2.64 Lemma. For j = 1,2, ... , k -1, let (el' e2,"" ep) be a basis of H j and let Xl, X2, , Xr be all possible solutions of BXj = ej, j = 1, ... ,po Then (el' e2, , ep,xI, X2,"" x r ) is a basis for H j + l . Proof. In fact, it is easily seen that el, ez, ... , e p , Xl, XZ,

o the vectors o {el)

e2, ... , ep,Xl, X2, ... , X r }

. .. , Xr

are linearly independent,

C Hj +1 ,

o the image of H j + l by B is contained in Hj. Thus r, which is the number of elements ei in the image of B, is the dimension of the image of Hj+l by B. The rank formula then yields dimHj+l

= dimHj + dim (1mB n Hj+l) = P + r. o

Now consider a generic matrix A E Mn,nUC), We first rewrite A using a basis of generalized eigenvectors to get a new matrix A' similar to A of the form

o A'=

5J o

o o

\Akl

(2.13)

72

2. Vector Spaces and Linear Maps

where each block Ai has the dimension of the algebraic multiplicity mi of the eigenvalue Ai and a unique eigenvalue Ai. Moreover, the matrix C i := Ai Id - Ai is nilpotent, and precisely C7'i = 0 and C7'l-l =I- O. Applying Theorem 2.63 to each C i , we then show that Ai is similar to Ai Id + B' where B' is as (2.11). Therefore, we conclude the following.

2.65 Theorem (Jordan's canonical form). Let AI, A2,"" Ak be all distinct eigenvalues of A E Mn,n(C). For every i = 1, ... , k

(i) let (Ui,l, ... , Ui,p,) be a basis of the eigenspace VAi (as we know, Pi S; ni), (ii) consider the generalized eigenvectors relative to Ai defined as follows: for any j = 1,2, ... ,Pi, a) set el,j := Ui,j, b) set e~j to be a solution of a= 2, ... ,

(2.14)

as long as the system (2.14) is solvable. c) denote by a(i,j) the number of solved systems plus 1. Then for every i = 1, ... , k the list (e~j) with j = 1, ... ,Pi and a = 1, ... , a(i,j) is a basis for the generalized eigenspace Wi relative to Ai. Hence the full list

(2.15)

i = 1.... ,k,j = 1, ... ,pi,a = 1, ... ,a(i,j)

is a basis of en. By the definition of the

{e~j}'

if we set

'- [1 2 1 2 1 2 ] S .e11,e11,· .. ,e12,e12, .. ·,e21,e21,'''' "

"

"

the matrix J := S-l AS, that represents x the form

-t

Ax in the basis (2.15), has \

J=

where i

J 1,1

0

0

0

0

0

IJ 1 I

0

0

0

0

0

B

0

0

0

0

0

0

Jk,Pk

,Pl

= 1, ... , k, j = 1, ... ,Pi,

Ji,j

has dimension a(i,j) and

2.2 Eigenvectors and Similar Matrices

Ai

Ji,j

=

if dim Ji,j

Ai

1

0

0

0

0

Ai

1

0

0

0

0

Ai

1

0

0

0

0

Ai

1

0

0

0

0

Ai

73

= 1,

otherwise.

A basis with the properties of the basis in (2.15) is called a Jordan basis, and the matrix J that represents A in a Jordan basis is called a canonical Jordan form of A. 2.66 Example. Find a canonical Jordan form of

A=

0 2 1 0 0

(i

0 0 2 1 0

~)

0 0 0 3 1

A is lower triangular hence the eigenvalues of A are 2 with multiplicity 3 and 3 with multiplictiy 2. We then have

A - 2Id

=

(1 ~ ; ;

J

A - 2Id has rank 4 since the columns of A of indices 1, 2, 3 and 5 are linearly independent. Therefore the eigenspace V2 has dimension 5 - 4 = 1 by the rank formula. We now compute a nonzero eigenvalue,

(A - 2Id) (;)

(.

u

~,)

x+t+u

(1) . 0

For instance, one eigenvector is 81 := (O,O,I,-I,I)T. We now compute the Jordan basis relative to this eigenvalue. We have eLl = 81 and it is possible to solve

:

( ) (~) z

+t

x+t+u

for instance,

82

:=

ei,l

-1

1

= (0,1,0, -1, 2)T is a solution. Hence we compute a solution of

74

2. Vector Spaces and Linear Maps

( : J (~J z +t x+t+u

-1 2

hence 83:= er,l = (1,0,0,-1,2)T. Looking now at the other eigenvalue, -1

A-31d~ ~

°

-1 1

(

° °

A is of rank 4 since the columns of indices 1, 2, 3 and 4 are linearly independent. Thus by the rank formula, the eigenspace relative to the eigenvalue 2 has dimension 1. We now compute an eigenvector with eigenvalue 2. We need to solve

and a nonzero solution is, for instance, 84 := (0,0,0,0, l)T. Finally, we compute Jordan's basis relative to this eigenvalue. A solution of

is given by

85

= e§,l = (0,0,0,1, O)T. Thus,

we conclude that the matrix

is nonsingular, since the columns are linearly independent, and by construction

2.2 Eigenvectors and Similar Matrices

75

e. Elementary divisors As we have seen, the characteristic polynomial det(s Id - A),

s E OC,

is invariant by similarity transformations. However, in general the equality of two characteristic polynomials does not imply that the two matrices be similar.

2.67 Example. The unique eigenvalue of the matrix AI-' =

(AOJL

0) is AO and has

AO

multiplicity 2. The corresponding eigenspace is given by the solutions of the system 0.X 1 +O.X 2 =0,

°. 1= °

{ JLX 1 +

x 2 = 0.

If JL 1= 0, then V"Q,I-' has dimension 1. Notice that Ao is diagonal, while AI-' is not diagonal. Moreover, Ao and AI-' with JL are not similar.

It would be interesting to find a complete set of invariants that characterizes the class of similarity of a matrix, without going explictly into Jordan's reduction algorithm. Here we mention a few results in this direction. Let A E Mn,n(C). The determinants of the minors of order k of the matrix sId - A form a subset D k of polynomials in the s variable. Denote by Dk(S) the g.c.d. of these polynomials whose coefficient of the maximal degree term is normalized to 1. Moreover set Do(s) := 1. Using Laplace's formula, one sees that D k - 1 (s) divides D k (s) for all k = 1, ... , n. The polynommts k

=

1, ... ,n,

are called the elementary divisors of A. They form a compl€te set of invariants that describe the complex similarity class of A. In fact, the following holds. 2.68 Theorem. The following claims are equivalent

(i) A and B are similar as complex matrices, (ii) A (,u%d B have the same Jordan's canonical form (up to permutations of rows and columns), (iii) A and B have the same elementary divisors.

76

2. Vector Spaces and Linear Maps

2.3 Exercises 2.69~. Write a few 3 x 3 real matrices and interpret them as linear maps from lR 3 into lR 3 . For each of these linear maps, choose a new basis of]R3 and write the associate matrix with respect to the new basis both in the source and the target lR3 . 2.70~. Let VI, V2, ... , Vn be finite-dimensional vector spaces, and let 10, II, linear maps such that

... ,In

be

Show that, ifIm (Ii) = ker(fi+1) Vi = 0, ... , n - 1, then I:?=1 (_I)i dim Vi = O. 2.71 ~. Consider lR as a vector space over iQi. Show that 1 and ~ are linearly independent if and only if ~ is irrational, ~ ~ iQi. Give reasons to support that lR as a vector space over iQi is not finite dimensional. 2. 72

~

I :X

-->

Lagrange multipliers. Let X, Y and Z be three vector spaces over IK and let Y, 9 : X --> Z be two linear maps. Show that ker 9 C ker I if and only if there exists a linear map f : Z --> Y such that 1:= fog. 2.73'. Show that the matrices

c ~), have the same eigenvalues but are not similar. 2.74'. Let .AI, .A2, ... , .An be the eigenvalues of A E Mn,n(C), possibly repeated with their multiplicities. Show that tr A = .AI + ... +.A n and det A = ;"1 . .A2 ... .An. 2. 75 ~. Show that p( s) = Sn the n x n matrix

+ an -1 Sn -1 + ... + ao 1

o

o

1

is the characteristic polynomial of

-a1

2.76~. Let A E Mk,k(IK), B E Mn,n(IK), C E Mk,n(IK). Compute the characteristic polynomial of the matrix

M:=(~ ~). 2.77'. Let f : cn --> cn be defined by f(ei) := ei+1 if i = 1, ... , n -1 and f(en) = e1, where e1, e2, ... , en is the canonical basis of en. Show that the associated matrix L is diagonizable and that the eigenvalues are all distinct. [Hint: Compute thJ characteristic polynomial.]

2.3 Exercises

77

2.78~. Let A E Mn,n(lR) and suppose A 2 = Id. Show that A is similar to \

o

-

Idn-k

for some k, 1::; k ::; n. [Hint: Consider the subspaces V+ := {x I Ax = x} and V_ := {x I Ax = -x} and show that V+ EEl V_ = lR n . J

2. 79~. Let A, BE Mn,n(lR) be two matrices such that A 2 = B 2 = Id and tr A = tr B. Show that A and B are similar. [Hint: Use Exercise 2.78.] 2.80~. Show that the diagonizable matrices span Mn,n(lR). [Hint: Consider the matrices Mij = diag (1, 2, ... , n) + Ei,j where Ei,j has value 1 at entry (i, j) and value zero otherwise.]

2.81 ~. Let A, B E Mn,n(lR) and let B be symmetric. Show that the polynomial -+ det(A + tB) has degree less than Rank B.

t

2.82~. Show that any linear operator A : lR n dimension 1 or 2.

-+

lR n has an invariant subspace of

2.83 ~ Fitting decomposition. Let f : X -+ X be a linear operator of a finitedimensional vector space and set fk := f 0 . . . 0 f k-times. Show that there exists k, 1 ::; k ::; n such that

(i) ker(fk) = ker(fk+ 1 ), (ii) 1m (fk) = 1m (fk+ 1 ), (iii) film (fk) : 1m (fk) -+ 1m (fk) is an isomorphism, (iv) f(ker fk) C ker(fk), (v) f, ker(fk) : ker(fk) -+ ker(fk) is nilpotent, (vi) V = ker(fk) EEl 1m (fk). 2.84~.

2.85

~.

A is nilpotent if and only if all its eigenvalues are zero.

Consider the linear operators in the linear space of polynomials A(P)(t) := pI (t),

B(P)(t) = tP(t).

Compute the operator AB - BA. 2.86~.

Let A, B be linear operators on lR n . Show that

(i) tr (AB) = tr (BA), (ii) AB - BA =J Id. 2.87~. Show that a linear operator C : lR 2 -+ lR 2 can be written as C = AB - BA where A, B : lR 2 -+ lR 2 are linear operators if and only if tr C = o.

78

2.88~.

2. Vector Spaces and Linear Maps

Show that the Jordan canonical form of the matrix

A{ with a~a5 ... a;:-l

a 21

a 31

a 0

a 32 a

0

0

a n2 a 3n

·"1 a

f. 0 is

[:

1 a 0

0 1 a

0

0

~)

3. Euclidean and Hermitian Spaces

3.1 The Geometry of Euclidean and Hermitian Spaces Until now we have introduced several different languages, linear independence, matrices and products, linear maps that are connected in several ways to linear systems and stated some results. The structure we used is essentially linearity. A new structure, the inner product, provides a richer framework that we shall illustrate in this chapter.

a. Euclidean spaces 3.1 Definition. Let X be a real vector space. An inner product on X is a map ( I ) : X x X ----- lR which is o (BILINEAR)

(x, y) ----- (xly) is linear in each factor, i.e., (Ax + fLylz) = A(xlz) (xlAy + fLz) = A(xly)

+ fL(ylz), + fL(xlz),

for all x,y,z E X, for all A,fL E R o (SYMMETRIC) (xly) = (ylx) for all x, y E o (POSITIVE DEFINITE) (xix) ~ 0 Vx and (xix)

x.

= 0 if and only if x = o.

The nonnegative real number

Ixl :=

J(xlx)

is called the norm of x EX.

A finite-dimensional vector space X with an inner product is called an Euclidean vector space, and the inner product of X is called the scalar product of X. 3.2 Example. The map ( I ) : ffi.n n

(xly) := x. y =

2:= xiyi, i=l

X

ffi.n

--->

ffi. defined by

80

3. Euclidean and Hermitian Spaces

is an inner product on JR n , called the standard scalar product of JR n , and JRn with this scalar product is an Euclidean space. In some sense, as we shall see later, see Proposition 3.25, it is the unique Euclidean space of dimension n. Other examples of inner products on jRn can be obtained by weighing the coordinates by nonnegative real numbers. Let A1, A2, . .. , An be positive real numbers. Then n

(xly)

:=

L

Aixiyi,

i=l

is an inner product on JRn. Other examples of inner products in infinite-dimensional vector spaces can be found in Chapter 10.

Let X be a vector space with an inner product. From the bilinearity of the inner product we deduce that

Ix + yl2 = (x + ylx + y) = (xix + y) + (ylx + y) = (xix) + 2(xly) + (yly) = Ixl 2 + 2(xly) + !y12

(3.1)

from which we infer the following.

3.3 Theorem. The following hold.

(i)

(PARALLELOGRAM IDENTITY)

Ix + Yl2 + Ix (ii) (POLARITY FORMULA)

We have

yl2 = 2 (lxl 2 + lyl2) We have

~ (Ix + yj2 -Ix _

(xly) =

Vx,y E X.

y12)

Vx,y E X,

hence we can get the scalar product of x and y by computing two norms. (iii) (CAUCHY-SCHWARZ INEQUALITY) The following inequality holds l(xly)1 :::;

Ixllyl,

Vx,y E Xj

moreover, (xly) = Ixllyl if and only if either y = 0 or x = >..y for some>" E JR, >.. ;:::: o. Proof. (i), (ii) follow trivially from (3.1). Let us prove (iii). If y = 0, the claim is trivial. If y =f 0, the function t -> Ix + tyl2, t E JR, is a second order nonnegative polynomial since

o~

Ix + tyl2 = (x

+ tylx + tV)

= (x

+ tylx) + (x + tylty)

= Ixl

2 + 2(xly) t + !y12 t 2;

hence its discriminant is nonpositive, thus ((xly))2 -lx[2Iy[2 ~ O. If (xly) = Ixllyl, then the discriminant of t -> Ix + tyl2 vanishes. If y =f 0, then for some t E JR we have Ix + ty[2 = 0, i.e., x = -tV. Finally, -t is nonnegative since

-t(yly)

= (xly) = Ixllyl

;::: o.

0

3.4 Definition. Let X be a vector space with an inner product. Two vectors x, y E X are said to be orthogonal, and we write x -.l y, if (xly) = o.

3.1 The Geometry of Euclidean and Hermitian Spaces

81

From (3.1) we immediately infer the following. 3.5 Proposition (Pythagorean theorem). Let X be a vector space with an inner product. Then two vectors x, y E X are orthogonal if and only if 3.6 Carnot's formula. Let x, y E 1R 2 be two nonzero vectors of 1R2, that we think of as the plane of Euclidean geometry with an orthogonal Cartesian reference. Setting x := (a, b), y := (c, d), and denoting by 0 the angle between Ox and Oy, it is easy to see that lxi, Iyl are the lengths of the two segments Ox and Oy, and that x.y := ac + bd = Ixllyl cosO. Thus (3.1) reads as Carnot's formula

Ix + yl2 = Ixl2

+ lyl2 + 21xllyl

cos o.

E IR n ,

In general, given two vectors x, y we have by Cauchy-Schwarz inequality Ix. y I :::::: Ixllyl, hence there exists a 0 E IR such that x.y Ixllyl =: cos O.

ois called the angle between x and y and denoted by xy. In this way (3.1) rewrites as Carnot's formula Ix + yl2 = Ixl 2 + lyl2 + 21xllyl cosO. Notice that the angle 0 is defined up to the sign, since cos 0 is an even function. 3.7 Proposition. Let X be a Euclidean vector space and let ( inner product. The norm of x EX,

I ) be

its

Ixl := J(xlx) is a function

I I:X

-+

IR with the following properties

(i) Ixl E IR+ Vx E X. (ii)

(iii) (iv)

(NONDEGENERACY) Ixl = 0 if and only if x = O. (I-HOMOGENEITY) = IAllxl VA E IR, Vx E X. (TRIANGULAR INEQUALITY) Ix yl :::::: Ixl Iyl Vx, y

I>.xl

+

+

EX.

Proof. (i), (ii), (iii) are trivial. (iv) follows from the Cauchy-Schwarz inequality since Ix + yl2 = Ixl 2 + lyl2 + 2(ylx) ::; [x[2 + ly[2 + 21(ylx)[

::; Ixl 2 + [Y12

+ 2 [x[ Iyl =

([x[

+ lyI)2). o

Finally, we call the distance between x and y E X the number d(x, y) := Ix - yl. It is trivial to check, using Proposition 3.7, that the distance function d : X x X -+ IR defined by d(x, y) := Ix - yl, has the following properties

82

3. Euclidean and Hermitian Spaces

(i) (NONDEGENERACY) d(x, y) ~ 0 Vx, Y E X and d(x, y) = 0 if and only if x = y. (ii) (SYMMETRY) d(x, y) = d(y, x) Vx, Y E X. (iii) (TRIANGULAR INEQUALITY) d(x,y)::::; d(x,z) +d(z,y) Vx,y,z E X. We refer to d as the distance in X induced by the inner product. 3.8 Inner products in coordinates. Let X be a Euclidean space, denote by ( I ) its inner product, and let (el' e2,"" en) be a basis of X. If x = L~=l xiei, y = L~=l yi ei E X, then by linearity

(xly) = Lxiyj(eil ej ). i,j

The matrix

G = [gij],

gij = (eilej)

is called the Gram matrix of the scalar product in the basis (el, e3,.·., en). Introducing the coordinate column vectors x = (xl, x 2, ... , x n )T and y = (yl, y2, ... , yn)T E IR.n and denoting by . e' the standard scalar product in IR.n, we have (xly) = xeGy = xTGy rows by columns. We notice that (i) G is symmetric, GT = G, since the scalar product is symmetric, (ii) G is positive definite, i.e., xTGx ~ 0 Vx E IR.n and xTGx = 0 if and only if x = 0, in particular, G is invertible. b. Hermitian spaces A similar structure exists on complex vector spaces. 3.9 Definition. Let X be a vector space over C which is (i) (SESQUILINEAR), i.e.,

+ ,8wlz) = a(vlz) + ,8(wlz), (vlaw + ,8z) = a(vlw) + j3(vlz)

(av

Vv, w, z EX, Va,,8 E
Izi := ~

is called the norm of z E X.

3.10 Definition. A finite-dimensional complex space with a Hermitian product is called a Hermitian space.

3.1 The Geometry of Euclidean and Hermitian Spaces

83

3.11 Example. Of course the product (z, w) -> (zlw) := wz is a Hermitian product on e. More generally, the map ( I ) : x -> e defined by

en en

n

(zlw):= z.w

:=

Lzjw j j=l

en,

en.

is a Hermitian product on called the standard Hermitian product of As we shall see later, see Proposition 3.25, equipped with the standard Hermitian product is in a sense the only Hermitian space of dimension n.

en

Let X be a complex vector space with a Hermitian product ( the properties of the Hermitian product we deduce

1 ).

From

Iz + wl 2 = (z + wlz + w) = (zlz + w) + (wlz + w) 2 2 = (zlz) + (zlw) + (wlz) + (wlw) = Izl + Iwl + 2R(zlw)

(3.2)

from which we infer at once the following.

3.12 Theorem.

(i) We have

R(zlw) = ~ (Iz + wl 2 -lzl 2 -l wI2 )

Vz,w E X.

(ii) (PARALLELOGRAM IDENTITY) We have

Iz + wl 2 + Iz - wl 2

=

2(lzl 2 + Iw1 2 )

Vz,w E X.

(iii) (POLARITY FORMULA) We have 4(zlw)

= (Iz + wl 2 -Iz - w1 2 ) + i(lz + iwl 2 -Iz -

iWI2),

for all z,w E X. We therefore can compute the Hermitian product of z and w by computing four norms. (iv) (CAUCHY-SCHWARZ INEQUALITY) The following inequality holds Vz,w E X; l(zjw)1 ::; Izllwl, Izllwl if and only if either w =

moreover (zlw) = some A E JR., A 2: o.

0, or

z=

AW for

Proof. (i), (ii), (iii) follow trivially from (3.2). Let us prove (iv). Let z, w E X and te i6 , t, (J E R. From (3.2)

oX =

"It ER,

hence its discriminant is nonpositive, thus 1~(e-i6(zlw))1 :::;

Izllwl. Since (J is arbitrary, we conclude l(zlw)1 :::; Izllwl. The second part of the claim then follows as in the real case. If (zlw) = Izllwl, then the discriminant ofthe real polynomial t -> Iz + twl 2 , t E R, vanishes. If w =1= 0, for some t E R we have Iz + twl 2 = 0, i.e., z = -two Finally, -t is nonnegative since -t(wlw) = (zlw) = Izllwl ~ O. 0

84

3. Euclidean and Hermitian Spaces

3.13 4V. Let X be a complex vector space with a Hermitian product and let z, w E X. Show that l(zlw)1 = Izllwl if and only if either w = 0 or there exists A E C such that z = AW.

3.14 Definition. Let X be a complex vector space with a Hermitian product ( I ). Two vectors z, w E X are said to be orthogonal, and we write z J.. w, if (zlw) = o. From (3.2) we immediately infer the following. 3.15 Proposition (Pythagorean theorem). Let X be a complex vector space with a Hermitian product ( I ). If z, wE X are orthogonal, then

We see here a difference between the real and the complex cases. Contrary to the real case, two complex vectors, such that Iz+wl 2 = Iz1 2 + Iwl 2 holds, need not be orthogonal. For instance, choose X := C, (zlw) := wz, and let z = 1 and w = i. 3.16 Proposition. Let X be a complex vector space with a Hermitian product on it. The norm of z EX,

Izl:=~, is a real-valued function

(i) Izl E lR+ Vz E X. (ii) (NONDEGENERACY) (iii) (iv)

I I:X

-->

lR with the following properties

Izi = 0 if and only if z = O. IAzl IAlizl VA E C, Vz E X. Iz + wi :::; Izl + Iwl Vz, wE X.

(I-HOMOGENEITY) = (TRIANGULAR INEQUALITY)

Proof. (i), (ii), (iii) are trivial. (iv) follows from the Cauchy-Schwarz inequality since

Iz + wl 2

=

Izl 2+ Iwl 2+ 2~(zlw) ::::: Izl 2+ Iwl 2+ 21(zlw)1 ::::: Izl2 + Iwl 2+ 21zllwl = (izi + Iwlf)· o

Finally, we call distance between two points z, w of X the real number d(z, w) := Iz - wi. It is trivial to check, using Proposition 3.16, that the distance function d : X x X --> lR defined by d(z, w) := Iz - wi has the following properties (i) (NONDEGENERACY) d(z, w) ~ 0 Vz, w E X and d(z, w) = 0 if and only if z = w. (ii) (SYMMETRY) d(z, w) = d(w, z) Vz, wE X. (iii) (TRIANGULAR INEQUALITY) d(z,w):::; d(z,x)+d(x,w) Vw,x,z E X. We refer to d as to the distance on X induced by the Hermitian product.

3.1 The Geometry of Euclidean and Hermitian Spaces

85

3.17 Hermitian products in coordinates. If X is a Hermitian space, the Gram matrix associated to the Hermitian product is defined by setting

Using linearity n

(zlw) =

L

(ei[ej)ziwj = zTGw

i,j=I

I W2 , ... , Wn) E trn Z, Z 2 , ... , Z n) , W - (W, II..are th e coord'Inat e I'f Z -- (I vector columns of z and w in the basis (eI, e2, ... , en). Notice that T

(i) G is a Hermitian matrix, G = G, (ii) G is positive definite, i.e., zT Gz 2: 0 Vz E en and ZT Gz = 0 if and only if z = 0, in particular, G is invertible.

c. Orthonormal basis and the Gram-Schmidt algorithm 3.18 Definition. Let X be a Euclidean space with scalar product ( I ) or a Hermitian vector space with Hermitian product ( [ ). A system of vectors {ea } aEA C X is called orthonormal if Va, f3 E A. Orthonormal vectors are linearly independent. In particular, n orthonormal vectors in a Euclidean or Hermitian vector space of dimension n form a basis, called an orthonormal basis. 3.19 Example. The canonical basis (el, e2, ... , en) ofjRn is an orthonormal basis for the standard inner product in jRn. Similarly, the canonical basis (el, e2, ... , en) of en is an orthonormal basis for the standard Hermitian product in

en.

3.20'. Let ( [ ) be an inner (Hermitian) product on a Euclidean (Hermitian) space X of dimension n and let G be the associated Gram matrix in a basis (el, e2, ... , en). Show that G = Id n if and only if (er, e2, . .. , en) is orthonormal.

Starting from a denumerable system of linearly independent vectors, we can construct a new denumerable system of orthonormal vectors that span the same subspaces by means of the Gram-Schmidt algorithm. 3.21 Theorem (Gram-Schmidt). Let X be a real (complex) vector space with inner (Hermitian) product ( I ). Let VI, V2, ... , Vk, ... be a denumerable set of linearly independent vectors in X. Then there exist a set of orthonormal vectors WI, W2, ... , Wk, ... such that for each k = 1,2, ... Span { WI, W2, ... , Wk}

= Span { VI, V2,···, vk}.

86

3. Euclidean and Hermitian Spaces

Proof. We proceed by induction. In fact, the algorithm W~ = VI, W'

1

W'1·I

_

Wp -

Iw~I' Vp -

,<,P-I(

LJj=I

I .) .

V p W) W)'

W' W·p'-

never stops since

w~

#

P

Iw~I'

0 Vp = 1,2,3, ... and produces the claimed orthonormal basis.

o

3.22 Proposition (Pythagorean theorem). Let X be a real (complex) vector space with inner (Hermitian) product ( I ). Let (el' e2, ... , ek) be an orthonormal basis of X. Then k

= 2)xlej)ej

X

XEX,

i=l

that is the i th coordinate of x in the basis (e 1, e2, ... , en) is the cosine director (xlei) of x with respect to ei' Therefore we compute k

(xjy)

= ~)xlei) (ylei)

if X is Euclidean,

i=l

k

(xly)

= ~)xlei) (ylei)

if X is Hermitian,

i=l

so that in both cases Pythagoras's theorem holds: k

Ixl = (xix) = L l(xlei)1 2 . 2

i=l

Proof. In fact, by linearity, for j

(xlej)

= 1, ... , k

and x

= 2:r=I Xiei

we have

= Cf::xiei Iej) = I=xi(eilej) = I=xirSij = xj. i=l

i=l

i=l

Similarly, using linearity and assuming X is Hermitian, we have

(xly)

I

= (I=xiei (I=yjej) = i=l

j=l

n

=

L

I=

xiyj(eilej)

i,j=l

k

xiyjrSij = 2:>iif, i=l

i,j=l

hence, by the first part, n

(xly) = L(xlei) (ylei)' i=l

o

3.1 The Geometry of Euclidean and Hermitian Spaces

87

d. Isometries 3.23 Definition. Let X, Y be two real (complex) vector spaces with inner (Hermitian) products ( I )x and ( I )y. We say that a linear map A : X -> Y is an isometry if and only if IA(x)ly =

Ixlx

"Ix E X,

or, equivalently, compare the polar formula, if (A(x)IA(y))y

= (xly)X

"Ix,y E X.

Isometries are trivially injective, but not surjective. If there exists a surjective isometry between two Euclidean (Hermitian) spaces, then X and Yare said to be isometric. 3.24'. Let X, Y be two real (complex) vector spaces with inner (Hermitian) products ( I )x and ( I )y and let A : X ---> Y be a linear map. Show that the following claims are equivalent

(i) A is an isometry, (ii) B c X is an orthonormal basis if and only if A(B) is an orthonormal basis for A(X).

Let X be a real vector space with inner product ( I ) or a complex vector space with Hermitian product ( I ). Let (el' ez, ... , en) be a basis in X and £ : X -> OC n , (OC = lR. of OC = q be the corresponding system of coordinates. Proposition 3.22 implies that the following claims are equivalent.

(i) (e 1, ez, ... , en) is an orthonormal basis, (ii) £(x) = ((xlel),"" (xle n )), (iii) £ is an isometry between X and the Euclidean space lR.n with the standard scalar product (or en with the standard Hermitian product). In this way, the Gram-Schmidt algorithm yields the following.

3.25 Proposition. Let X be a real vector space with inner product ( I ) (or a complex vector space with Hermitian product ( I )) of dimension n. Then X is isometric to lR.n with the standard scalar product (respectively, to en with the standard Hermitian product), the isometry being the coordinate system associated to an orthonormal basis. In other words, using an orthonormal basis on X is the same as identifying X with lR.n (or with en) with the canonical inner (Hermitian) product. 3.26 Isometries in coordinates. Let us compute the matrix associated to an isometry R : X ---> Y between two Euclidean spaces of dimension nand m respectively, in an orthonormal basis (so that X and Yare respectively isometric to IR n (C n ) and IR m (C m ) by means of the associated coordinate system) . It is therefore sufficient to discuss real isometries R : IR n ---> IR m and complex isometries R : en ---> em. Let R : IR n ---> jRm be linear and let R E M m ,n(lR) be the associated matrix, R(x) = Rx, x E IR n . Denoting by (el, e2, ... , en) the canonical basis of IR n ,

88

3. Euclidean and Hermitian Spaces

ri = Rei Vi. Since (el, e2, ... , en) is orthonormal, R is an isometry if and only if are orthonormal. In particular, m 2 nand

(rr,

r2, ... , r n )

i.e., the matrix R is an orthogonal matrix,

When m = n, the isometries R : lR n --> lR n are necessarily surjective being injective, and form a group under composition. As above, we deduce that the group of isometries of lR n is isomorphic to the orthogonal group O(n) defined by

I

O(n) := {R E Mn,n(lR) RTR = Id n

}.

Observe that a square orthogonal matrix R is invertible with R- 1 = RT. If follows that RRT = Id and Idet RI = 1. Similarly, consider en as a Hermitian space with the standard Hermitian product. Let R : en --> em be linear and let R E Mm,n(C) be such that R(z) = Rz. Denoting by (el, e2, ... , en) the canonical basis of lR n ,

R

= [rr Ir21

I

... r n ]

ri = Rei Vi = 1, ... , m.

,

Since (er, e2, ... , en) is orthonormal, R is an isometry if and only if rr, r2, ... , r n are orthonormal. In particular, m 2 nand

i.e., the matrix R is a unitary matrix,

When m = n, the isometries R : en --> en are necessarily surjective being injective, moreover they form a group under composition. From the above, we deduce that the group of isometries of en is isomorphic to the unitary group U (n) defined by

Observe that a square unitary matrix R is invertible with R

RR

T

-1

= RT .

It follows that

= Id and I det RI = 1.

e. The projection theorem Let X be a real (complex) vector space with inner (Hermitian) product ( [ ) that is not necessarily finite dimensional, let V c X be a finitedimensional linear subspace of X of dimension k and let (e1, e2,"" ek) be an orthonormal basis of V. We say that x E X is orthogonal to V if (xlv) = 0 \::Iv E V. As (e1, e2, ... , ek) is a basis of V, x..l V if and only if (xlei) = o\::Ii = 1, ... ,k. For all x EX, the vector k

Pv(x)

:=

I)xlei)ei E V i=l

3.1 The Geometry of Euclidean and Hermitian Spaces

89

is called the orthogonal projection of x in V, and the map Pv : X ~ V, x ~ Pv(x), the projection map onto V. By Proposition 3.22, Pv(x) = x if x E V, hence ImP = V and p 2 = P. By Proposition 3.22 we also have IPv(x)1 2 = L:7=II(xleiW, The next theorem explains the name for Pv(x) and shows that in fact Pv(x) is well defined as it does not depend on the chosen basis (el' e2,···, ek)'

3.27 Theorem (of orthogonal projection). With the previous notation, there exists a unique z E V such that x - z is orthogonal to V, i.e., (x - zjv) = 0 Vv E V. Moreover, the following claims are equivalent.

(i) x - z is orthogonal to V, i.e., (x - zlv) = 0 Vv E V, (ii) z E V is the orthogonal projection of x onto V, z = Pv(x), (iii) z is the point in V of minimum distance from x, i.e.,

Ix - zl < Ix - vi

Vv E V, v =I- z.

In particular, Pv(x) is well defined as it does not depend on the chosen orthonormal basis and there is a unique minimizer of the function v ~ Ix - vi, v E V, the vector z = Pv(x). Proof. We first prove uniqueness. If Zl, Z2 E V are such that (x - zilv) then (Zl - Z2[V) = 0 Vv E V, in particular IZl - Z2!2 = o. (i)

= 0 for i = 1,2,

'* (ii). From (i) we have (xlei) = (Zlei) Vi = 1, ... ,k. By Proposition 3.22 k

k

Z = I)zlei)ei

= 2)x!ei)ei = Pv(x). i=l

i=l

This also shows existence of a point Z such that x - Z is orthogonal to V and that the definition of Pv(x) is independent of the chosen orthonormal basis (el, e2, ... , ek).

'* (i). If Z = Pv(x), we have for every j

(ii)

=

1, ... , k

k

(x - z[ej)

= (xlej) -

2)xlei)(ei[ej)

= (xlej)

- (x[ej)

= 0,

i=l

hence (x - zlv) = 0 Vv. (i)

'* (iii). Let v E V. Since (x Ix -

vl 2 =

Ix -

z[v) = 0 we have z

+z -

v[2 =

Ix -

zl2

+ Iz -

v1 2 ,

hence (iii). (iii) t =

'* (i). Let v E V. The function t

o.

Since

Ix -

z

+ tvl 2 = Ix -

->

Ix -

zl2

z

+ tv[2,

+ 2t~(x -

t E JR, has a minimum point at

zlv)

+ t 2 1v1 2 ,

necessarily ~(x - z[v) = O. If X is a real vector space, this means (x - zlv) = 0, hence (i). If X is a complex vector space, from ~(x - z[v) = 0 Vv E V, we also have ~(e-i(i(x - z[v)) = 0 '<;j() E JR Vv E V, hence (x - z[v) = 0 Vv E V and thus (ii). 0

We can discuss linear independence in terms of an orthogonal projection. In fact, for any finite-dimensional space V eX, x E V if and only if x - Pv(x) = 0, equivalently, the equation x - Pv(x) = 0 is an implicit equation that characterizes V as the kernel of Id - Pv.

90

3. Euclidean and Hermitian Spaces

3.28'. Let W = Span {VI, V2, ... , vd be a subspace of ]Kn. Describe a procedure that uses the orthogonal projection theorem to find a basis of W. 3.29'. Given A E Mm,n(lR), describe a procedure that uses the orthogonal projection theorem in order to select a maximal system of independent rows and columns of A. 3.30'. Let A E Mm,n(lR). Describe a procedure to find a basis of ker A. 3.31 ,. Given k linear independent vectors, choose among the vectors (el, e2, ... , en) of lR n (n - k) vectors that together with v!, V2, ... , Vk form a basis of lR n . 3.32 Projections in coordinates. Let X be a Euclidean (Hermitian) space of dimension n and let V C X be a subspace of dimension k. Let us compute the matrix associated to the orthogonal projection operator P v : X -> X in an orthonormal basis. Of course, it suffices to think of Pv as of the orthogonal projection on a subspace of lR n (en in the complex case). Let (el, e2, ... , en) be the canonical basis of lR n and V C lR n . Let VI, V2,.··, Vk be an orthonormal basis of V and denote by V = [vj J the n x k nonsingular matrix

so that Vj = L:~=l v}ej' Let P be the n x n matrix associated to the orthogonal projection onto V, Pv(x) = Px, or,

I

I

Pi=Pei, i=l, ... ,n.

P = [PI P21 ... Pn], Then

Pi = Pdei) =

k

k

j=l

j=l

2:( ei .Vj ) Vj = 2: v}Vj

i.e.,

(3.3)

p=vvT . The complex case is similar. With the same notation, instead of (3.3) we have k

Pi = Pv(ei) =

k

2:( ei .Vj) Vj = 2: vjVj j=l

k

j=l n

n

(3.4)

" '~ "~ h = '~(VV " T ) ih eh, = '~ vjVjeh j=lh=l

Le.,

h=l

-

T

P=VV.

f. Orthogonal subspaces Let X be a real vector space with inner product ( I ) or a complex vector space with Hermitian product ( I ). Suppose X is finite dimensional and let W C X be a linear subspace of X. The subset

I

Wi- := {x E X (xly) = 0 Vy E W} is called the orthogonal of W in X.

3.1 The Geometry of Euclidean and Hermitian Spaces

91

3.33 Proposition. We have

(i) WJ... is a linear subspace of X, (ii) W n WJ... = {O}, (iii) (wJ...)J...=w, (iv) Wand WJ... are supplementary, hence dim W + dim WJ... = n, (v) if Pw and PW-L are respectively, the orthogonal projections onto W and WJ... seen as linear maps from X into itself, then PW-L = Idx -

Pw· Proof. We prove (iv) and leave the rest to the reader. Let (Vi, V2, ... , Vk) be a basis of W. Then we can complete (Vi, V2, ... , Vk) with n - k vectors of the canonical basis to get a new basis of X. Then the Gram-Schmidt procedure yields an orthonormal basis

(Wi, W2, ... , w n ) of X such that W = Span {Wi, W2, ... , Wk}. On the other hand wk+i, ... ,Wn E W-L, hence dim W-L = n - k.

0

g. Riesz's theorem 3.34 Theorem (Riesz). Let X be a Euclidean or Hermitian space of dimension n. For any L E X* there is a unique XL E X such that \:Ix E X.

(3.5)

Proof. Assume for instance, that X is Hermitian. Suppose L -=f. 0, otherwise we choose = 0, and observe that dim 1m L = 1, and V := ker L has dimension n - 1 if dimX = n. Fix Xo E V-L with Ixol = 1, then every x E X decomposes as XL

x = x'

+ .Axo,

x' E ker L, .A = (xlxo).

Consequently,

L(x) = L(x')

+ .AL(xo) =

and the claim follows choosing

XL :=

(xlxo)L(xo) = (xIL(xo)xo)

o

L(xo)xo.

The map {3 : X* --+ X, L --+ XL defined by the Riesz theorem is called the Riesz map. Notice that {3 is linear if X is Euclidean and antilinear if X is Hermitian. 3.35 The Riesz map in coordinates. Let X be a Euclidean (Hermitian) space with inner (Hermitian) product ( I ), fix a basis and denote by x = (xl, x 2 , ... , x n ) the coordinates of x, and by G the Gram matrix of the inner (Hermitian) product. Let LEX· and let L be the associated matrix, L(x) = Lx. From (3.5) xTGxL

if X is Euclidean,

= xTGxL

if X is Hermitian,

= G-1L T

if X is Euclidean,

Lx = L(x) = (xlxd = Lx = L(x) =

(XIXL)

i.e., GXL GXL

= LT =

j?

or or

XL XL

= G-1I:

T

if X is Hermitian.

In particular, if the chosen basis (et, e2, ... , en) is orthonormal, then G = Id and XL =L XL

T

-T

= L

if X is Euclidean, if X is Hermitian.

92

3. Euclidean and Hermitian Spaces

Figure 3.1. Dynamometer.

3.36 Example (Work and forces). Suppose a mass m is fixed to a dynamometer. If B is the inclination of the dynamometer, the dynamometer shows the number

L = mg cos B,

(3.6)

where 9 is a suitable constant. Notice that we need no coordinates in JR3 to read the dynamometer. We may model the lecture of the dynamometer as a map of the direction v of the dynamometer, that is, as a map L : S2 ----> JR from the unit sphere S2 = {x E JR3 , Ixl

= I}

of the ambient space V into lR. Moreover, extending L homogeneously to

the entire space V by setting L(v) := Ivl L(v/lvl), v E JR3 \ {O}, we see that such an extension is linear because of the simple dependence of L from the inclination. Thus we can model the elementary work done on the mass m, the measures made using the dynamometer, by a linear map L : V ----> JR. Thinking of the ambient space V as Euclidean, by Riesz's theorem we can represent L as a scalar product, introducing a vector F := XL E V such that (vIF)

= L(v)

"Iv E V.

We interpret such a vector as the force whose action on the mass produces the elementary work L(v). Now fix a basis (el, e2, e3) of V. If F = (F 1, F2, F3)T is the column vector of the force coordinates and L = (L 1 , L 2 , L3) is the 1 x 3 matrix of the coordinates of L in the dual basis, that is, the three readings L; = L(e;), i = 1,2,3, of the dynamometer in the directions el, e2, e3, then, as we have seen,

In particular, if (e 1, e2 , e3) is an orthonormal basis,

h. The adjoint operator Let X, Y be two vector spaces both on IK. = lR. or IK. = C with inner (Hermitian) products ( I )x and ( I )y and let A : X -+ Y be a linear map. For any y E Y the map x -+ (A(x)ly)y

3.1 The Geometry of Euclidean and Hermitian Spaces

93

defines a linear map on X, hence by Riesz's theorem there is a unique A*(y) E X such that (A(x)ly)y

= (yIA*(x))x

Vx E X, Vy E Y.

(3.7)

It is easily seen that the map y --+ A*(y) from Y into X defined by (3.7) is linear: it is called the adjoint of A. Moreover,

(i) let A, B : X --+ Y be two linear maps between two Euclidean or Hermitian spaces. Then (A + B)* = A* + B*, (ii) (.\A)* = .\A* if .\ E IR and A : X --+ Y is a linear map between two Euclidean spaces, (iii) (.\A)* = ~A* if.\ E C and A : X --+ Y is a linear map between two Hermitian spaces, (iv) (B 0 A)* = A* 0 B* if A : X --+ Y and B : Y --+ Z are linear maps between Euclidean (Hermitian) spaces, (v) (A*)* = A if A: X --+ Y is a linear map. 3.37~. Let X, Y be vector spaces. We have already defined an adjoint with no use of inner or Hermitian products,

< A(y*), x >=< y*,A(x) >

A: y*

->

X*

"Ix E X, Vy* E Y*.

If X and Yare Euclidean (Hermitian) spaces, denote by {3x : X* -> X, {3y : y* -> Y the Riesz isomorphisms and by A* the adjoint of A defined by (3.7). Show that A* = 1 {3x oAo{3y . 3.38 The adjoint operator in coordinates. Let X, Y be two Euclidean (Hermitian) spaces with inner (Hermitian) products ( I )x and ( I )y. Fix two bases in X and Y, and denote the Gram matrices of the inner (Hermitian) products on X and Y respectively, by G and H. Denote by x the coordinates of a vector x. Let A : X -> Y be a linear map, A * be the adjoint map and let A, A * be respectively, the associated matrices. Then we have

(A(x)ly)y

=

x T ATHy,

(xIA*(y)) = xTGA*y,

if X and Y are Euclidean and

if X and Yare Hermitian. Therefore

GA* =ATH

if X and Yare Euclidean,

GA* =ATH

if X and Yare Hermitian,

or, recalling that G T = G, (G-l)T = G-l, HT = H if X and Yare Euclidean and that aT = G, (G-l)T = G-l, and lIT = H if X and Yare Hermitian, we find

A* = G-1ATH

if X and Yare Euclidean,

A* = G-1ATH

if X and Yare Hermitian.

In particular, in the Euclidean case, in the Hermitian case if and only if the chosen bases in X and Y are orthonormal.

(3.8)

94

3. Euclidean and Hermitian Spaces

3.39 Theorem. Let A : X ---7 Y be a linear operator between two Euclidean or two Hermitian spaces and let A* : Y ---7 X be its adjoint. Then RankA* = RankA. Moreover,

= ker A*, (1m A*)l- = ker A, (1m A)l-

= (ker A*)l-, ImA* = (ker A)l-.

1m A

Proof. Fix two orthonormal bases on X and Y, and let A be the matrix associated to A using these bases. Then, see (3.8), the matrix associated to A * is AT, hence RankA*

= Rank AT = Rank A = Rank A,

= dim Y

- dimker A*

and dim(ker A*)J.

= RankA* = Rank A = dimlmA.

On the other hand, 1m A C (ker A*)J. since, if y = A(x) and A*(v) = 0, then (ylv) = (A(x)[v) = (xIA*(v)) = O. We then conclude that (ker A*)J. = ImA. The other claims 0 easily follow. In fact, they are all equivalent to 1m A = (ker A*)J..

As an immediate consequence of Theorem 3.39 we have the following.

3.40 Theorem (The alternative theorem). Let A : X ---7 Y be a linear operator between two Euclidean or two Hermitian spaces and let A* : Y ---7 X be its adjoint. Then AlkerA-'- : (ker A)l- ---7 ImA and Ailm A : 1m A ---7 (ker A)l- are injective and onto, hence isomorphisms. Moreover,

(i) A(x) = y has at least a solution if and only if y zs orthogonal to ker A*, (ii) y is orthogonal to 1m A if and only if A * (y) = 0, (iii) A is injective if and only if A * is surjective, (iv) A is surjective if and only if A* is injective. 3.41 . A more direct proof of the equality ker A = (ImA*)l- is the following. For simplicity, consider the real case. Clearly, it suffices to work in coordinates and by choosing an orthonormal basis, it is enough to show that ImA = (ker AT)l- for every matrix A E Mm,n(lR). Let A = (a)) E Mm,n(lK) and let al, a 2 , ... , am be the rows of A, equivalently the columns of AT,

Then,

3.2 Metrics on Real Vector Spaces

2

a§x + ara~xlX1 ++ a~x2 +

Ax=

a

-

·· ·

(

(a

n

+ a;,x ) + a~Xn

al'x 1 + a2 x2 + ... + a~xn

Consequently, x E ker A if and only if a i ker A

eX

1 2

ex) eX

.. . am eX

.

= 0 't/i = 1, ... , m,

= Span {aI, a 2, ... , am} 1. =

95

Le.,

(ImAT)1..

(3.9)

3.2 Metrics on Real Vector Spaces In this section, we discuss bilinear forms on real vector spaces. One can develop similar considerations in the complex setting, but we refrain from doing it.

a. Bilinear forms and linear operators 3.42 Definition. Let X be a real linear space. A bilinear form on X is a map b : X x X -.., JR that is linear in each factor, i. e.,

b(ax + (3y, z) = a b(x, z) b(x, ay + (3z) = a b(x, y)

+ (3 b(y, z), + (3 b(z, z),

for all x, y, X E X and all a, (3 E JR. We denote the space of all bilinear forms on X by B(X). Observe that, if bE B(X), then b(O,x) = b(O,y) = 0 't/x,y E X. The class of bilinear forms becomes a vector space if we set

(b 1 + b2)(x, y) := b1 (x, y) + b2(x, y), (.\b)(x, y) := b(.\x, y) = b(x, A, y). Suppose that X is a linear space with an inner product denoted by If b E B(X), then for every y E X the map x -7 b(x, y) is linear, consequently, by Riesz's theorem there is a unique B := B(y) E X such that (3.10) 't/x E X. b(x, y) = (xIB(y))

( I ).

It is easily seen that the map y -7 B(y) from Y into X defined by (3.10) is linear. Thus (3.10) defines a one-to-one correspondence between B(X) and the space of linear operators £(X, X), and it is easy to see this correspondence is a linear isomorphism between B(X) and £(X, X).

96

3. Euclidean and Hermitian Spaces

c_ mtlrie.u 0"""'- r

di. B;rpoLh...", wei b d 0

Hypothe

d

n

'. II .......

a.

e1cl1e dar Gcom Irie zu Grond Ii

lat.,

.1..... c••" ... ..., .. a.-.n. .....,w . . ..".,

B.:11

.......

~

'.

,... •

J:/IM

u.. ...

pk

~_

....-&1Icbft

I'f_~

,..

v

Vllf~

.:,.

u .....

e-.~_

..

.u-

~

»-.Wal . . .

... ..-_ "' . . a..v ~ hdt. ·fIdori .... u- Ouuu.., _,... _ I.UI . . . _r L'anlh ..

B. Ri.manu.

-*"

~

• .tn .......

..,..,.,.,~ ~.

\I.a-.wn

...,~. ~

,

.. - . W1IIkIw M

MU.lbM . . . 0na4 . . . . . .

.... . , .J1p'" ~ - - - . . ~ ~ . QI't wi· __

.~

~1l1iIJL1dI

... • t .... __-.

•.....-1Uft a..... u.w.

~

~

pMIlt. . . ..,w_~h

.ue---

~

Gtt-"'"'"

-'~I~ lo-'.. l»4_ :r...... _~~~

..

........... ,.

GOUIA.IU, I•

.. "

~

t• .di:6II •

...'

DI.lullfl'u'

.

"""lJiW.II

....

.. ....,.,..

c

"*-....,._

w _ ,.............r....... r_ .. "

~

a--j

ill

~

'

1...

,",p."lIhlll. I

Figure 3.2. Frontispiece and a page of the celebrated dissertation of G. F. Bernhard Riemann (1826--1866).

3.43 Bilinear forms in coordinates. Let X be a finite-dimensional vector space and let (e I, e2, ... , en) be a basis of X. Let us denote by B the n x n matrix, sometimes called the Gram matrix of b,

Recall that the first index from the left is the row index. Then by linearity, if for every x, y, x = (xl, x 2 , .. . , xn)T and y = (yl, y2, . .. , yn)T E jRn are respectively, the column vectors of the coordinates of x and y, we have n

b(x, y)

=

L

bijXiyi

=

x T • (By)

= xTBy.

i)j=l

In particular, a coordinate system induces a one-to-one correspondence between bilinear forms in X and bilinear forms in jRn. Notice that the entries of the matrix B have two lower indices that sum with the indices of the coordinates of the vectors x, y that have upper indices. This also reminds us that B is not the matrix associated to a linear operator B related to B. In fact, if instead N is the associated linear operator to b, b(x, y) = (xIN(y))

Vx,y E X,

then yTBx = b(x, y) = (xIN(y)) = yTNTGx

where we have denoted by G the Gram matrix associated to the inner product on X, G = (gij], gij = (eilej), and by N the n x n matrix associated to N : X -> X in the basis (el, e2, . .. , en). Thus or, recalling that G is symmetric and invertible,

3.2 Metrics on Real Vector Spaces

97

b. Symmetric bilinear forms or metrics 3.44 Definition. Let X be a real vector space. A bilinear form b E l3(X) is said to be (i) symmetric or a metric, ifb(x,y) = b(y,x) Vx,y E X, (ii) antisymmetric ifb(x,y) = -b(y,x) Vx,y E X. The space of symmetric bilinear forms is denoted by Sym(X). 3.45~. Let b E B(X). Show that bs(x,y):= ~(b(x,y) +b(y,x)), x,y E X, is a symmetric bilinear form and bA(X, y) := ~(b(x, y) - bey, x)), x, y E X, is an antisymmetric bilinear form. In particular, one has the natural decomposition

b(x, y) = bs(x, y)

+ bA(X, y)

of b into its symmetric and antisymmetric parts. Show that b is symmetric if and only if b = bs, and that b is antisymmetric if and only if b = bA. 3.46~.

Let bE B(X) be a symmetric form, and let B be the associated Gram matrix. Show that b is symmetric if and only if B T = B. 3.47~. Let b E B(X) and let N be the associated linear operator, see (3.10). Show that N is self-adjoint, N* = N, if and only if bE Sym(X). Show that N* = -N if and only if b is antisymmetric.

c. Sylvester's theorem 3.48 Definition. Let X be a real vector space. We say that a metric on X, i. e., a bilinear symmetric form g : X x X ----> IR is (i) nondegenerate ifVx E X, x -I- 0 there is y E X such that b(x,y) andVy E X, y -I- 0 there is x E X such that b(x,y) -I- 0, (ii) positively definite ifb(x,x) > 0 Vx E X, x -I- 0, (iii) negatively definite if b(x, x) < 0 Vx E X, x -I- o.

-I- 0

3.49~. Show that the scalar product (xly) on X is a symmetric and nondegenerate bilinear form. We shall see later, Theorems 3.52 and 3.53, that any symmetric, nondegenerate and positive bilinear form on a finite-dimensional space is actually an inner product.

3.50 Definition. Let X be a vector space of dimension n and let g E Sym(X) be a metric on X. (i) We say that a basis (ell e2,"" en) is g-orthogonal if g(ei,ej) Vi, j = 1, ... ,n, i -I- j. (ii) The radical of g is defined as the linear space rad (g) := {x E X I g(x, y) = 0 Vy EX}. (iii) The range of the metric g is r(g) := n - dimradg.

=

0

98

3. Euclidean and Hermitian Spaces

Figure 3.3. Jorgen Gram (1850--1916) and James Joseph Sylvester (1814-1897).

(iv) The signature of the metric 9 is the triplet of numbers (i+ (g), i_ (g), io(g)) where i+ (g) := maximum of the dimensions of the subspaces V C X on which 9 is positive definite, g(v, v) > 0 I::/v E V, v#- 0, L (g) := maximum of the dimensions of the subspaces V C X on which 9 is negative definite, g(v, v) < 0 I::/v E V, v #- 0, io(g):= dimrad(g).

One immediately sees the following.

3.51 Proposition. We have

(i) The matrix associated to 9 in a basis (el' e2,'." en) is diagonal if and only if (el' e2, ... , en) is g-orthogonal, (ii) 9 is nondegenemte if and only ifrad(g) = {O}, (iii) if G is the matrix associated to 9 in a basis, then x E radg if and only if its coordinate vector belongs to ker G; thus r(g) = Rank G and 9 is nondegenemte if and only if G is not singular, (iv) if X is Euclidean and G E £(X, X) is the linear opemtor associated to g, by g(x, y) = (xIG(y)) I::/x, y E X, then rad (G) = kerG, hence r(g) = Rank G and 9 is nondegenemte if and only if G is invertible.

3.52 Theorem (Sylvester). Let X be a finite-dimensional vector space and let (el' e2, ... , en) be a g-orthogonal basis for a metric 9 on X. Denote by n+, n_ and no the numbers of elements in the basis such that respectively, we have g(ei, ei) > 0, g(ei, ei) < 0, g(ei, ei) = o. Then n+ = i+(g), n_ = L (g) and no = i o(g). In particular, n+, n_, no do not depend on the chosen g-orthogonal basis, and

i+(g)

+ L(g) + io(g) = n.

3.2 Metrics on Real Vector Spaces

Proof. Suppose that g(ei, ei)

>0

99

for i = 1, ... , n+. For each v = L~l viei, we have

n+ g(v, v) = ""' L....J

Ivi I2 g(ei, ei) > 0,

i=l

hence dim Span {q, e2, ... , e n +} ::; i+ (g). On the other hand, if W C X is a subspace of dimension i+(g) such that g(v, v) > 0 "Iv E W, we have WnSpan{en++l,

,e n } = {o}

since g(v, v) ::; 0 for all v E Span{en++l, ,e n }. Therefore we also have i+(g) ::; n - (n - n+) = n+. Similarly, one proves that n_ = L(g). Finally, since G:= [g(ei,ej)] is the matrix associated to 9 in the basis (el' e2, ... , en), we have io(g) = dimrad(g) = dimkerG, and, since G is diagonal, dim ker G = no. 0

d. Existence of g-orthogonal bases The Gram-Schmidt algorithm yields the existence of an orthonormal basis in a Euclidean space X. We now see that a slight modification of the GramSchmidt algorithm allows us to construct in a finite-dimensional space a g-orthogonal basis for a given metric g. 3.53 Theorem (Gram-Schmidt). Let 9 be a metric on a finite-dimensional real vector space X. Then 9 has a g-orthogonal basis. Proof. Let r be the rank of g, r:= n-dimrad (g), and let (Wi, W2, ... , w n - r ) be a basis of rad (g). If V denotes a supplementary subspace of rad (g), then V is g-orthogonal to radg and dim V = r. Moreover, for every v E V there is z E X such that g(v, z) i= 0. Decomposing z as z = W + t, W E V, t E rad (g), we then have g(v, w) = g(v, w) + g(v, t) = g(v, z) i= 0, i.e., 9 is nondegenerate on V. Since trivially, (Wi, W2, ... , Wn - r ) is g-orthogonal and V is g-orthogonal to (Wi, W2, ... , Wn - r ), in order to conclude it suffices to complete the basis (Wi, W2, ... , w n - r ) with a g-orthogonal basis of V; in other words, it suffices to prove the claim under the further assumption that 9 be nondegenerate. We proceed by induction on the dimension of X. Let (fl, 12, ... , In) be a basis of X. We claim that there exists el E X with g(el,q) i= 0. In fact, iffor some Ii we have 9(fi,!i) i= 0, we simply choose el := Ii, otherwise, if g(fi, lil = for all i, for some k i= we must have g(fl,lk) i= 0, since by assumption rad(g) = {O}. In this case, we choose q := fl +!k as

°

°

Now it is easily seen that the subspace

I

Vi := {v E X g(el'v) =

o}

supplements Span {q}, and we find a basis (V2,' .. , Vn) of Vi such that g(Vj, el) = for all j = 2, ... ,n by setting

°

Since 9 is nondegenerate on Vi, by the induction assumption we find a g-orthogonal basis (e2, ... , en) of Vi, and the vectors (q, e2, ... , en) form a g-orthogonal basis of X. 0

100

3. Euclidean and Hermitian Spaces

A variant of the Gram-Schmidt procedure is the following one due to Carl Jacobi (1804-1851). Let 9 : X x X --+ IR be a metric on X. Let (!I, 12,.··, fn) be a basis of X, let G be the matrix associated to 9 in this basis, G = [gij], gij = g(Ji, fj)· Set D.o = 1 and for k = 1, ... ,n D.k := detGk where G k is the k x k submatrix of the first k rows and k columns. 3.54 Proposition (Jacobi). If D.k i= 0 for all k = 1, ... ,n, there exists a g-orthogonal basis (el' e2, ... , en) of X; moreover 9 (ek, ek )

D.k-l :=--s:;;.

Proof. We look for a basis (el, e2, . .. , en) so that

:: : ::;: '+ alj, \ en = a;!r + ... + a':;fn or, equivalently, k

ek :=

L: ai.,Ji,

k = 1, .. . ,n,

(3.11)

i=1

as in the Gram-Schmidt procedure, such that g(ei,ej) =0 for i i' j. At first sight the system g(ei, ej) = 0, i i' j, is a system in the unknowns ai.,. However, if we impose that for all k's g(ek,f;) = 0 Iii = 1, ... , k - 1, (3.12) by linearity g(ek,ei) = 0 for i < k, and by symmetry g(ek,ei) = 0 for i > k. It suffices then to fulfill (3.12) Le., solve the system of k-1 equations in k unknowns a~, a~, ... , at k

L: g(Jj, fd a{ = 0,

Iii = 1, .. , , k - 1.

(3.13)

j=1 If we add the normalization condition k

L:g(Jj,!k)a~ = 1, (3.14) j=1 we get a system of k equations in k unknowns of the type Gkx = b, where G k = [gij], gij := g(Ji,fj), x = (a~, ... ,at)T and b = (O,O, ... ,l)T. Since detGk = Ll k and Llk i' 0 by assumption, the system is solvable. Due to the arbitrarity of k, we are able to find a g-orthogonal basis of type (3.11). It remains to compute g(ek, ek)' From (3.13) and (3.14) we get g(ek,ek) =

k

k

k

k

i,j=1

j=1

i=1

j=1

L: a~a~g(Ji,Ji) = L:a{(L:g(Ji,fj)ai.,) = L:a~8jk = at,

and we compute at by Cramer's formula,

k

Llk-l

ak=~'

o

3.2 Metrics on Real Vector Spaces

101

3.55 Remark. Notice that Jacobi's method is a rewriting of the GramSchmidt procedure in the case where g(Ji, fi) =I 0 for all i's. In terms of Gram's matrix G:= [g(ei,ej)], we have also proved that

TTGT = diag

{~~:l }

for a suitable triangular matrix T.

3.56 Corollary (Sylvester). Suppose that ~l,"" ~k =I O. Then the metric 9 is nondegenerate. Moreover, L (g) equals the number of changes of sign in the sequence (1, ~l, ~2,"" ~n). In particular, if ~k > 0 for all k's, then 9 is positive definite. Let (eI, e2, ... , en) be a g-orthogonal basis of X. By reordering the basis in such a way that

>0 ifj = 1, ... ,i+(g), <0 if j = i+(g) + 1, ... , i+(g) =0 otherwise;

+ i_(g),

and setting

we get

g(fj,Jj)

~{

1 -1

o

if j = 1, ... , i+(g), if j = i+ (g) + 1, ... , i+ (g) otherwise.

+L

(g),

e. Congruent matrices It is worth seeing now how the matrix associated to a bilinear form changes when we change bases. Let (el' e2, ... , en) and (II, 12,.··, fn) be two bases of X and let R be the matrix associated to the map R : X -+ X, R(ei) := fi in the basis (el' e2,"" en), that is

where r i is the column vector of the coordinates of fi in the basis (e 1, e2, ... , en). As we know, if x and x' are the column vectors of the coordinates of x respectively, in the basis (el' e2,"" en) and (II, 12,···, fn), then x = Rx'. Denote by Band B' the matrices associated to b respectively, in the coordinates (eI, e2, ... , en) and (II, 12,.··, fn). Then we have

102

3. Euclidean and Hermitian Spaces

b(x, y) = x,TB,y', b(x,y) = xTBy = X,TRTBRy', hence

B' =RTBR.

(3.15)

The previous argument can be of course reversed. If (3.15) holds, then B and B' are the Gram matrices of the same metric b on JRn in different coordinates b(x, y) = xTb'y = (RxfB(Ry). 3.57 Definition. Two matrices A, B E Mn,n(JR) are said to be congruent if there exists a nonsingular matrix R E Mn,n(JR) such that B = R TAR. It turns out that the congruence relation is an equivalence relation on matrices, thus the n x n matrices are partitioned into classes of congruent matrices. Since the matrices associated to a bilinear form in different basis are congruent, to any bilinear form corresponds a unique class of congruent matrices. The above then reads as saying that two matrices A, BE Mn,n(JR) are congruent if and only if they represent the same bilinear form in different coordinates. Thus, the existence of a g-orthogonal basis is equivalent to the following.

3.58 Theorem. A symmetric matrix A E Mn,n(JR) is congruent to a diagonal matrix. Moreover, Sylvester's theorem reads equivalently as the following. 3.59 Theorem. Two diagonal matrices I, J E Mn,n(JR) are congruent if and only if they have the same number of positive, negative and zero entries in the diagonal. If, moreover, a symmetric matrix A E Mn,n(JR) is congruent to

1=

Boo o 1- 1 o

Idb

0

0

0

then (a, b, n - a - b) is the signature of the metric yT Ax. Thus the existence of a g-orthogonal matrix in conjunction with Sylvester's theorem reads as the following.

3.60 Theorem. Two symmetric matrices A, B E Mn,n(JR) are congruent if and only if the metrics yTAx and yTBx on JRn have the same signature (a, b, r). In this case, A and B are congruent to

3.2 Metrics on Real Vector Spaces

103

Go o 1- I

0

1=

0

Id b

0

0

0

f. Classification of real metrics Since reordering the basis elements is a linear change of coordinates, we can now reformulate Sylvester's theorem in conjunction with the existence of a g-orthonormal basis as follows. Let X, Y be two real vector spaces, and let g, h be two metrics respectively, on X and Y. We say that (X, g) and (Y, h) are isometric if and only if there is an isomorphism L : X ----* Y such that h(L(x), L(y)) = g(x, y) Vx, Y E X. Observing that two metrics are isometric if and only if, in coordinates, their Gram matrices are congruent, from Theorem 3.60 we infer the following.

3.61 Theorem. (X, g) and (Y, h) are isometric if and only if 9 and h have the same signature,

Moreover, if X has dimension n and the metric 9 on X has signature (a,b,r), a+b+r = n, then (X,g) is isometric to (lR n , h) where h(x,y):= xTHyand

Go

H=

o o

o

1- Id 1 0 b

0

o

According to the above, the metrics over a real finite-dimensional vector space X are classified, modulus isometries, by their signature. Some of them have names: (i) The Euclidean metric: i+(g) = n, i_(g) = io(g) a scalar product. (ii) The pseudoeuclidean metrics: L(g) = O. (iii) The Lorenz metric or Minkowski metric: i+(g) io(g) = O. (iv) The Artin metric i+(g) = L(g) = p, io(g) = O.

= 0; =

in this case 9 is

n - 1, L(g)

=

1,

3.62~. Show that a bilinear form 9 on a finite-dimensional space X is an inner product on X if and only if 9 is symmetric and positive definite.

104

3. Euclidean and Hermitian Spaces

g. Quadratic forms • Let X be a finite-dimensional vector space over JR and let b E B(X) be a bilinear form on X. The quadratic form ¢> : X --> JR associated to b is defined by ¢>(x) = b(x, x), x E X.

Observe that ¢> is fixed only by the symmetric part of b 1

bs(x, y) := 2(b(x, y)

+ b(y, x))

since b(x, x) = bs(x, x) Vx E X. Moreover one can recover bs from ¢> since bs is symmetric,

bs(x, y) =

~ (¢>(x + y) -

¢>(x) - ¢>(y)).

Another important relation between a bilinear form b E B(X) and its quadratic form ¢> is the following. Let x and v EX. Since

¢>( x + tv) = ¢>( x) we have

d

dt ¢>(x

+ t (b(x, v) + b( v, x)) + t 2 ¢>( v), + tV)lt==o

= 2 bs(x, v).

(3.16)

We refer to (3.16) saying that the symmetric part bs of b is the first variation of the associated quadratic form. 3.63 Homogeneous polynomials of degree two. Let B = [b ij ] E Mn,n(JR) and let n

L

b(x,y) := xTBy =

bijxiyj

i,j==l

be the bilinear form defined by B on JRn, (yl, y2, ... , yn). Clearly,

X

=

(xl, x 2 , ... , x n ), y

n

¢>(x) = b(x, x) = xTBx =

L

bijXiX

j

i,j==l

is a homogeneous polynomial of degree two. Conversely, any homogeneous polynomial of degree two

P(x) =

L

bijxiX j = xTBx

i,j=l,n iSj

defines a unique symmetric bilinear form in JRn by

b(x, y) :=

~ (P(x + y) -

with associated quadratic form P.

P(x) - P(Y))

3.2 Metrics on Real Vector Spaces

3.64 Example. Let (x, y) be the standard coordinates in mial

ax

2

+ bxy + cy2 =

]R2.

105

The quadratic polyno-

b~2) (:)

(x, y) (b;2

is the quadratic form of the metrics

3.65 Derivatives of a quadratic form. From (3.16) we can compute the partial derivatives of the quadratic form ¢(x) := xTGy. In fact, choosing v = eh, we have

hence, arranging the partial derivatives in a 1 x n matrix, called the Jacobian matrix of ¢,

I

a¢ D¢(x):= [ -a¢ 1 (x) 2 (x) ax ax

I... I-(x) a¢ ] ax n

we have or, taking the transpose,

'V¢(x) := (D¢(x))T = (G

+ GT)x.

h. Reducing to a sum of squares Let 9 be a metric on a real vector space X of dimension n and let ¢ be the associated quadratic form. Then, choosing a basis (el' e2, ... , en) we have n

¢(x)

= g(x,x) = ~)xi)2g(ei,ei) i=l

if and only if (el' e2, ... , en) is g-orthogonal, and the number of positive, negative and zero coefficients is the signature of g. Thus, Sylvester's theorem in conjunction with the fact that we can always find a g-orthogonal basis can be rephrased as follows.

3.66 Theorem (Sylvester's law of inertia). Let ¢(x) = g(x, x) be the quadratic form associated to a metric 9 on an n-dimensional real vector space.

(i) There exists a basis (fl, 12, ... , in) of X such that i+(g)

¢(x)

L(g)

= L (X i )2 - L (x i )2, i=l

n X

i=l

where (i+(g), L(g), io(g)) is the signature of g.

=

Lxiii, i=l

106

3. Euclidean and Hermitian Spaces

(ii) If for some basis (el' e2, ... , en) n

n

¢(x)

= L ¢(ei)lx i I 2,

x:= Lxiei'

(3.17)

i=l

i=l

then the numbers n+, n_ and no respectively, of positive, negative and zero ¢( ei) 's are the signature (i+ (g), i - (g), i o(g)) of g. 3.67 Example. In order to reduce a quadratic form ¢J to the canonical form (3.17), we may use Gram-Schmidt's algorithm. Let us repeat it focusing this time on the change of coordinates instead of on the change of basis. Suppose we want to reduce to a sum of squares by changing coordinates, the quadratic form n

¢J(x) =

L

aijXjx\

i,j=l

where at least one of the aij'S is not zero. We first look for a coefficient akk that is not zero. If we find it, we go further, otherwise if all akk vanish, at least one of the mixed terms, say al2, is nonzero; the change of variables

transforms a12x l x 2 into al2((yl)2 - (y2)2), and since all = a22 = 0, in the new coordinates (yl, y2, ... , yn) the coefficient of (yl)2 is not zero. Thus, possibly after a linear change of variables, we write ¢J as

We now complete the square and set Y l = allyl { yJ = yJ

+ '2:,']=2

for j = 2, ... , n.

so that ¢J(x) = _1_ (allyl all

fyj,

+

t

a2j yj)2 j=2 2

+C

= _1_(yl)2 all

+C

where C contains only products of y2, ... , yn. The process can then be iterated. 3.68 Example. Show that Jacobi's method in Proposition 3.54 transforms ¢J in ~o 1 2 ¢J(x) = - ( x ) ~l

+

~l 2 2 -(x) ~2

+ ... + -~2 ( x n ) 2 , ~3

if x = I:~=l xiei, for a suitable g-orthogonal basis (el' e2,.··, en). 3.69 Example (Classification of conics). The conics in the plane are the zeros of a second degree polynomial in two variables P(x,y) := ax 2 + 2bxy

+ cy2 + dx + ey+ f

= 0,

(x,y) E ]R2,

(3.18)

3.2 Metrics on Real Vector Spaces

107

where a, b, c, d, e, f E JR. Choose a new system of coordinates (X, Y), X = ax + (3y, Y = + 8y in which the quadratic part of P transforms into a sum of squares

"(x

ax 2 + bxy + cy2 = pX 2 + qy 2 , consequently, Pinto

pX 2

+ q y 2 + 2r X + 2s Y + f

= 0.

Now we can classify the conics in terms of the signs of p, q and the conic reduces to the straight line

If p

'I

2rX

°

+ 2sY + f

f.

If p, q are zero,

= 0.

and q = 0, then, completing the square, the conic becomes r p(X - XO)2 + 2sY + f = 0, Xo =-, p

i.e., a parabola with vertex in (Xo,O) and axis parallel to the axis of Y. Similarly, if p = and q 'I 0, the conic is a parabola with vertex in (0, Yo), Yo := slq, and axis parallel to the X axis. Finally, if pq 'I 0, completing the square, the conic is

°

p(X - XO)2

+ q(Y -

YO)2

+f

= 0,

Xo

= rip,

Yo

= slq,

i.e., it is o a hyperbola if f 'I and pq < 0, o two straight lines if f = and pq < 0, o an ellipse if sgn (I) = -sgn (p) and pq > 0, o a point if f = and pq > 0, o the empty set if sgn (I) = sgn (p) and pq > 0. Since we have operated with linear changes of coordinates that map straight lines into straight lines, ellipses into ellipses, and hyperbolas into hyperbolas, we conclude the following.

°

° °

3.70 Proposition. The conics in the plane are classified in terms of the signature of their quadmtic part and of the sign of the zero term. 3. 71 ~. The equation of a quadric i.e., of the zeros of a second order polynomial in n variables, see Figure 3.4 for n = 3, has the form
°

°

p

¢(x)='L X ; i=l

n

'L X; =1. i=p+l

(v) Suppose detA = 0. Since A = AT, we have kerA = (lmA)-L. Choosing a basis in which the first k elements generate 1m A and the last n - k ker A, then A writes as

([;J :)

108

3. Euclidean and Hermitian Spaces

(c), (k), (q)

(b)

~~ (g)

(h)

V

./

(z)

(j)

.~ (n)

cJ (p)

Figure 3.4. Quadrics: (a) ellipsoid: a2x2+b2y2+c2z2 = 1; (b) point: a2x2+b2y2+c2z2 = 0; (c) imaginary ellipsoid: a 2 x 2 + b2y 2 + c 2 z 2 = -1; (d) hyperboloid of one sheet:

a 2x 2 + b2 y 2 _ c 2 z2 = 1; (e) cone: a 2x 2 + b2y 2 - c 2 z2 = 0; (f) hyperboloid of two sheets: _a 2 x 2 - b2 y 2 + c 2 z 2 = 1; (g) paraboloid: a 2 x 2 + b2 y 2 - 2cz = 0, c > 0; (h) saddle: a 2 x 2 - b2 y 2 - 2cz = 0, c > 0; (i) elliptic cylinder: a 2x 2 + b2 y 2 = 1; (j) straight line: a 2 x 2 + b2y 2 = 0; (k) imaginary straight line: a 2 x 2 + b2 y 2 = -1; (I) hyperbolic cylinder: a 2 x 2 - b2 y 2 = 1; (m) nonparallel planes: a 2 x 2 - b2 y 2 = 0; (n) parabolic cylinder: a 2 x 2 - 2cz, c > 0; (0) parallel planes: a 2x 2 = 1; (p) plane: a 2 x 2 = 0; (q) imaginary plane: a 2 x 2 = -1.

3.3 Exercises

109

in this new basis and the quadric can be written as

+ 2(b'lx') + 2(b"lx") + C2 = 0 ker A, x = x' + x", b = b' + b" and

¢(x) = (X')T A'x'

where X', b' E Im A, x", b" E Applying the argument in (iii) to

(x,)TA'x'+2b'.x'

det A'

=I

O.

+C2,

we may further transform the quadric into

¢(x)

= (x')T A'x' + C3 + 2b" .x" = 0,

and, writing y' := -2b" .x" - C3, that is, by means of an affine transformation that does not change the variable x', we end up with ¢( x) = (x') T A'x' - y' = o.

3.3 Exercises 3.72'. Starting from specific lines or planes expressed in parametric or implicit way in IR3, write o the straight line through the origin perpendicular to a plane, o the plane through the origin perpendicular to a straight line, o the distance of a point from a straight line and from a plane, o the distance between two straight lines, o the perpendicular straight line to two given nonintersecting lines, o the symmetric of a point with respect to a line and to a plane, o the symmetric of a line with respect to a plane. 3.73'. Let X, Y be two Euclidean spaces with inner products respectively, ( ( I )y. Show that X x Y is an Euclidean space with inner product

I )x

and

(Xl,X2), (Yl,Y2) E X x Y. Notice that X x {O} and {O} x Yare orthogonal subspaces of X x Y. 3.74'. Let X,Y E IRn . Show that x..l Y if and only if Ix - ayl 21xl Va E R 3.75'. The graph of the map A(x)

:=

Ax, A E Mm,n(IR) is defined as

GA:= {(x,y) Ix E IR n , y E IRk, Y = A(x)} C IR n x IRk. Show that G A is a linear subspace of IRn+k of dimension n and that it is generated by the column vectors of the (k + n) x n

no

3. Euclidean and Hermitian Spaces

Also show that the row vectors of the k x (n

+ k)

matrix

(08) generates the orthogonal to GA. 3.76'. Write in the standard basis of lR4 the matrices of the orthogonal projection on specific subspaces of dimension 2 and 3. 3.77 ,. Let X be Euclidean or Hermitian and let V, W be subspaces of X. Show that V.L n W.L = (V + W).L. 3.78'. Let f : Mn,n(lK) --. lK be a linear map such that f(AB) = f(BA) VA, B E Mn,n(lK). Show that there is >. E lK such that f(X) = >. tr X for all X E Mn,n(lK) where tr X := L~=l xl if X = [xj]. 3.79'. Show that the bilinear form b: Mn,n(lR) x Mn,n(lR) --.lR given by n

"T i b(A, B) := tr (A T B):= " L.)A B)i i=l

defines an inner product on the real vector space Mn,n(lR). Find the orthogonal of the symmetric matrices. 3.80'. Given n + 1 points Zl, Z2, ... , Zn+l in C, show that there exists a unique polynomial of degree at most n with prescribed values at Zl, Z2, .. " Zn+l. [Hint: If P n is the set of complex polynomials of degree at most n, consider the map : P n --. C n + l given by (P) := (P(Zl), P(Z2), ... ,P(Zn)).] 3.81 , Discrete integration. Let tl, t2, ... , t n be n points in fa, bJ C R Show that there are constants al, a2, .•. , an such that

for every polynomial of degree at most n - 1. 3.82'. Let

Q := [0, l]n =

{x E lR

n

I°~ Xi ~ 1,

i = 1, ... ,

n}

be the cube of side one in lR n . Show that its diagonal has length ,;n. Denote by the vertices of Q and by x := (1/2,1/2, ... ,1/2) the center of Q. Show that the balls around x that do not intersect the balls B(Xi, 1/2), i = 1, ... , 2 n , necessarily have radius at most R n := (,;n - 2)/2. Conclude that for n > 4, B(x, R n ) is not contained in Q. Xl, ... , X2n

3.83'. Give a few explicit metrics in lR 3 and find the corresponding orthogonal bases. 3.84'. Reduce a few explicit quadratic forms in lR 3 and lR 4 to their canonical form.

4. Self-Adjoint Operators

In this chapter, we deal with self-adjoint operators on a Euclidean or Hermitian space, and, more precisely, with the spectral theory for self-adjoint and normal operators. In the last section, we shall see methods and results of linear algebra at work on some specific examples and problems.

4.1 Elements of Spectral Theory 4.1.1 Self-adjoint operators a. Self-adjoint operators 4.1 Definition. Let X be a Euclidean or Hermitian space X. A linear operator A : X -+ X is called self-adjoint if A * = A. As we can see, if A is the matrix associated to A in an orthonormal basis, then AT and AT are the matrices associated to A* in the same basis according to whether X is Euclidean or Hermitian. In particular, A is self-adjoint if and only if A = AT in the Euclidean case and A = AT in the Hermitian case. Moreover, as a consequence of the alternative theorem we have X = ker A EB 1m A,

ker A 1.. ImA

if A : X -+ X is self-adjoint. Finally, notice that the space of self-adjoint operators is a subalgebra of £(X, X). Typical examples of self-adjoint operators are the orthogonal projection operators. In fact, we have the following.

4.2 Proposition. Let X be a Euclidean or Hermitian space and let P : X -+ X be a linear operator. P is the orthogonal projection onto its image if and only if P* = P and PoP = P.

112

4. Self-Adjoint Operators

Proof. This follows, for instance, from 3.32. Here we present a more direct proof. Suppose P is the orthogonal projection onto its image. Then for every y E X (y-P(y)lz) = 0 'liz E 1m P. Thus y = P(y) if Y E 1m P, that is P(x) = PoP(x) = p 2 (x) 'lix E X. Moreover, for x,y E X 0= (x - P(x)lP(y)) = (xIP(y)) - (P(x)IP(y)), 0= (P(x)ly - P(y)) = (P(x)ly) - (P(x)IP(y)), hence,

(P(x)ly) = (xlP(y)), Conversely, if P* = P and p2 = P we have (x - P(x)IP(z))

= (P*(x -

P(x))lz)

Le.,

= (P(x)

P* = P.

- p 2 (x)lz)

= (P(x)

- P(x)lz)

=0

for all z EX.

0

b. The spectral theorem The following theorem, as we shall see, yields a characterization of the self-adjoint operators. 4.3 Theorem (Spectral theorem). Let A : X ----+ X be a self-adjoint operator on the Euclidean or Hermitian space X. Then X has an orthonormal basis made of eigenvectors of X. In order to prove Theorem 4.3 let us first state the following.

4.4 Proposition. Under the hypothesis of Theorem 4.3 we have

(i) A has n real eigenvalues, if counted with multiplicity, (ii) if V C ~n is an invariant subspace under A, then V 1- is also invariant under A, (iii) eigenvectors corresponding to distinct eigenvalues are orthogonal. Proof. (i) Assume X is Hermitian and let A E Mn,n(l~) be the matrix associated to A in an orthonormal basis. Then A = AT, and A has n complex eigenvalues, if counted with multiplicity. Let z E en be an eigenvector with eigenvalue .\ E iC. Then

Az = Az = .\z = Xz. Consequently, if A = (aj), z = (zl, z2, ... , zn), we have

.\lzl2 = ",n .\zi Zi = ",n (Az)i Zi = ",n . ai zj Zi ' L...z=l L...t=l L...t,J=l J 2 { 'I ""n "\ i i ~n i......-lA· ""n i -J' i J A Z = L...i=l A Z Z = L...i=l Z Z = L...i,j=l a j Z Z ,= "",,n L...i,j=l a i 1

Z

j

i

Z .

Since aj = a{ for all i, j = 1, ... ,n, we conclude that i.e.,

In the Euclidean case, AT = A = A, also. (ii) Let w E V.L. For every v E V we have (A(w)lv) = (wIA(v)) = 0 since A(v) E V and w E V.L. Thus A(w) 1. V. (iii) Let x, y be eigenvectors of A with eigenvalues .\, J.l, respectively. Then .\ and J.l are real and (.\ - J.l)(xly) = (.\xly) - (xlJ.lY) = (A(x)ly) - (xIA(y)) = O. o Thus (xly) = 0 if .\ i- J.l.

4.1 Elements of Spectral Theory

113

Proof of Theorem 4.3. We proceed by induction on the dimension n of X. On account of Proposition 4.4 (i), the claim trivially holds if dim X = 1. Suppose the theorem has been proved for all self-adjoint operators on H when dim H = n - 1 and let us prove it for A. Because of (i) Proposition 4.4, all eigenvalues of A are real, hence there exists at least an eigenvector Ul of A with norm one. Let H := Span {Ul}l- and let B := AIR be the restriction of A to H. Because of (ii) Proposition 4.4, B(H) C H, hence B : H - t H is a linear operator on H (whose dimension is n - 1); moreover, B is self-adjoint, since it is the restriction to a subspace of a self-adjoint operator. Therefore, by the inductive assumption, there is an orthonormal basis (U2, ... , Un) of H made by eigenvectors of B, hence of A. Since U2, ... ,Un are orthogonal to U 1, (u 1, U2, ... , Un) is an orthonormal basis of X made by eigenvectors of A. 0

The next proposition expresses the existence of an orthonormal basis of eigenvectors in several different ways, see Theorem 2.45. We leave its simple proof to the reader.

4.5 Proposition. Let A : X -+ X be a linear operator on a Euclidean or Hermitian space X of dimension n. Let (UI' U2,"" un) be a basis of X and let AI, A2,"" An be real numbers. The following claims are equivalent

(i) (UI, U2, ... , Un) is an orthonormal basis of X and each Uj is an eigenvector of A with eigenvalue Aj, i. e., Vi,j=l, ... ,n,

(ii) (Ul, U2, ... , un) is an orthonormal basis and n

A(x)

=L

Aj(xluj) Uj

VxEX,

j=l

(iii) (UI, U2, ... , un) is an orthonormal basis and for all x, y

E X

if X is Euclidean, if X is Hermitian. Moreover, we have the following, compare with Theorem 2.45.

4.6 Proposition. Let A : X -+ X be a self-adjoint operator in a Euclidean or Hermitian space X of dimension n and let A E Mn,n(JK) be the matrix associated to A in a given orthonormal basis. Then A is similar to a diagonal matrix. More precisely, let (UI' U2,"" un) be a basis of X of eigenvectors of A, let AI, A2,"" An E IR be the corresponding eigenvalues and let S E M n ,n(lR) be the matrix that has the n-tuple of components of Ui in the given orthonormal basis as the i th column,

Then STS

=

Id

and

114

4. Self-Adjoint Operators

if X is Euclidean, and and if X is Hermitian. Proof. Since the columns of S are orthonormal, it follows that STS = Id if X is Euclidean or ST S = Id if X is Hermitian. The rest of the proof is contained in Theorem 2.45.

o

c. Spectral resolution Let A : X ----. X be a self-adjoint operator on a Euclidean or Hermitian space X of dimension n, let (UI' Uz, ... , un) be an orthonormal basis of eigenvectors of A, let )'1, Az, ... , Ak be the distinct eigenvalues of A and VI, Vz ,·.·, Vk the corresponding eigenspaces. Let P;, : X ----. Vi be the projector on Vi so that

P;,(x) =

L

(xIUj) Uj,

UjEVi

and by (ii) Proposition 4.4 k

A(x) = L AiPi(X). i=l

As we have seen, by (iii) Proposition 4.4, we have Vi -.L Yj if i =1= j and, by the spectral theorem, I:~=1 dim Vi = n. In other words, we can say that {Vih is a decomposition of X in orthogonal subspaces or state the following.

4.7 Theorem. Let A : X ----. X be self-adjoint on a Euclidean or Hermitian space X of dimension n. Then there exists a unique family of projectors PI, Pz , ... , Pk and distinct real numbers AI, Az, ... , Ak such that k

k

LP;' = Id i=l

and A

= LAiPi. i=l

Finally, we can easily complete the spectral theorem as follows.

4.8 Proposition. Let X be a Euclidean or Hermitian space. A linear opertor A : X ----. X is self-adjoint if and only if the eigenvalues of A are real and there exists an orthonormal basis of X made of eigenvectors of A.

4.1 Elements of Spectral Theory

d. Quadratic forms To a self-adjoint operator A : X a: X x X -> JK,

->

115

X we may associate the bilinear form

a(x, y) := (A(x)[y),

x,yEX,

which is symmetric if X is Euclidean and sesquilinear, a(x, y) = a(y, x), if X is Hermitian.

4.9 Theorem. Let A: X -> X be a self-adjoint operator, (el' e2, ... , en) an orthonormal basis of X of eigenvectors of A and AI, A2, ... , An be the corresponding eigenvalues. Then n

(A(x)[x) =

L Ai[(xleiW

Vx E X.

(4.1)

i=l

In particular, if Amin and eigenvalues of A, then Amin

A max

are respectively, the smallest and largest

Ixl 2 :::; (A(x)[x)

:::;

A max

lxl 2

Vx E X.

Moreover, we have (A(x)[x) = Amin Ixl 2 (resp. (A(x)[x) = A max and only if x is an eigenvector with eigenvalue Amin (resp. AmaxJ.

Ix1 2 )

if

Proof. Proposition 4.5 yields (4.1) hence n

Amin L

n

[(xlei)1 2

:::;

(A(x)lx) :::; Amax L

i=l

I(x[ei)f,

i=l

and, since [x[2 = I:~11(xlei)12 "Ix E X, the first part of the claim is proved. Let us prove that (A(x)lx) = Aminlxf if and only if x is an eigenvector with eigenvalue Amin. If x is an eigenvector of A with eigenvalue Amin, then A(x) = Amin x hence (A(x)lx) = (AminX[X) = Amin Ix1 2. Conversely, suppose (el, e2, ... , en) is a basis of X made by eigenvectors of A and the eigenspace VA . is spanned by (q, e2, ... , ek)' From (A(x)lx) = Aminl x l2 , we infer that mm n

0= (A(x)[x) - Aminlxl2 = L(Ai - Amin)l(xlei)[2 i=l

and, as AiAmin 2: 0, we get that (xlei) = 0 Vi We proceed similarly for Amax.

> k,

thus x E VAmin •

o

All eigenvalues can, in fact, be characterized as in Theorem 4.9. Let us order the eigenvalues, counted with their multiplicity, as

and let (el' e2, vectors (el' e2,

, en) be an orthonormal basis of corresponding eigen, en), A(ei) = Aiei Vi = 1, ... ,n; finally, set

116

4. Self-Adjoint Operators

Since Vk , Wk are invariant subspaces under A and Vk.l = Wk+1, byapplying Theorem 4.9 to the restriction of (A(x)lx) on Vk and Wk, we find

(4.2)

Al = min (A(x)lx), Ixl=l

Ak

= max{ (A(x)lx) jlxl = 1,

x E Vk}

= min{ (A(x)lx) Ilxl = 1,

if k

x E Wk}

= 2, ... , n - 1,

An = max(A(x)lx). Ixl=l

Moreover, if S is a subspace of dimension n-k+ 1, we have SnVk then there is Xo E S n Vk with Ixol = 1; thus min{ (A(x)lx)

Ilxl = 1, XES} :S

=1=

{O},

(A(xo)lxo)

:S max{ (A(x)lx) Ilxl = 1, x

E

Vk } = Ak.

Since dim Wk = n - k + 1 and minxEwk(A(x)lx) = Ak, we conclude with the min-max characterization of eigenvalues that makes no reference to eigenvectors.

4.10 Proposition (Courant). Let A be a self-adjoint operator on a Euclidean or Hermitian space X of dimension n and let Al :S A2 :S ... :S An be the eigenvalues of A in nondecreasing order and counted with multiplicity. Then

Ak = . max min{(A(x)lx) dlmS=n-k+1

Ilxl = 1, XES}

= dlmS=k .min max{(A(x)lx)

Ilxl

=

1, XES}.

4.11 A variational algorithm for the eigenvectors. From (4.2) we know that

Ak := min{ (A(x)lx)

Ilxl =

1, x E Vk-:' 1 },

k = 1 ...

,n,

(4.3)

where V-I = {O}. This yields an iterative procedure to compute the eigenvalues of A. For j = 1 define

Al = min(A(x)lx), Ixl=l

and for j

= 1, ... , n -

1 set

Yj := eigenspace of Aj,

Wj {

:=

Aj+1

(VI EB V2 EB··· EB Yj).l,

:=

min{ (A(x)lx)

Ilxl

=

1, x E W j

}.

4.1 Elements of Spectral Theory

117

Notice that such an algorithm yields an alternative proof of the spectral theorem. We shall see in Chapter 10 that this procedure extends to certain classes of self-adjoint operators in infinite-dimensional spaces. Finally, notice that Sylvester's theorem, Gram-Schmidt's procedure or the other variants for reducing a quadratic form to a canonical form, see Chapter 3, allow us to find the numbers of positive, negative and null eigenvalues (with multiplicity) without computing them explicitly. e. Positive operators A self-adjoint operator A : X --; X is called positive (resp. nonnegative) if the quadratic form ¢(x) := (Axlx) is positive for x =I- 0 (resp. nonnegative). From the results about metrics, see Corollary 3.56, or directly from Theorem 4.9, we have the following. 4.12 Proposition. Let A : X --; X be self-adjoint. A is positive (nonnegative) if and only if all eigenvalues of A are positive (nonnegative) or iff there is A > 0 (A 2: 0) such that (Axlx) 2: A[x[2. 4.13 Corollary. A : X --; X is positive self-adjoint if and only if a(x,y) = (A(x)ly) is an inner (Hermitian) product on X. 4.14 Proposition (Simultaneous diagonalization). Let A, M : X --; X be linear self-adjoint operators on X. Suppose M is positive. Then there exists a basis (el' e2, ... , en) of X and real numbers AI, A2,"" An such that (4.4) Proof. The metric g(x, y) :== (M(x)[y) is a scalar (Hermitian) product on X and the linear operator M-IA : X ....... X is self-adjoint with respect to 9 since g(M- 1A(x), y) == (M M-1A(x)ly) == (A(x)[y) == (x[A(y)

== (xjM M- 1 A(y») == (MxIM- 1 A(y) == g(x, M- 1 A(y». Therefore, M- 1 A has real eigenvalues and, by the spectral theorem, there is a gorthonormal basis of X made of eigenvectors of M- 1 A, M- 1 A(ej) == Ajej Vi,j == 1, ... , n.

o 4.15 Remark. We cannot drop the positivity assumption tion 4.14. For instance, if

and we have det(A Id - M- I A)

A:=

III

Proposi-

(~ ~)

= A2 + 1, hence M- 1 A has no real eig~nvalue.

118

4. Self-Adjoint Operators

4.16'. Show the following.

Proposition. Let X be a Euclidean space and let g, b : X x X ---> lR be two metrics on X. Suppose g is positive. Then there exists a basis of X that is both g-orthogonal and b-orthogonal. 4.17'. Let A, M be linear self-adjoint operators and let M be positive. Then M-l A is self-adjoint with respect to the inner product g(x,y) := (M(x)ly). Show that the eigenvalues AI, A2, ... , An of M-l A are iteratively given by .

Al =

mm

g(x,x)=l

geM

-1

. (A(x)lx) A(x»x = mm ( ()I) x,eo M x x

and for j = 1, ... , n - 1

Yj {

:= eigenspace of

M-l A relative to Aj,

Wj := (VI EEl V2 EEl··· EEl Yj).L, Aj+l := min{(A(x)lx) 1 (M(x)lx) = 1, x E Wj},

where V.L denotes the orthogonal to V with respect to the inner product g. 4.18'. Show the following.

Proposition. Let T be a linear operator on oc n . If T + T- is positive (nonnegative), then all eigenvalues of T have positive (nonnegative) real part.

f. The operators A * A and AA * Let A : X ~ Y be a linear operator between X and Y that we assume are either both Euclidean or both Hermitian. From now on we shall write Ax instead of A(x) for the sake of simplicity. As usual, A* : Y ~ X denotes the adjoint of A.

4.19 Proposition. The operator A* A: X

~

X is

(i) self-adjoint, (ii) nonnegative, (iii) Ax, A* Ax and (A* Axlx) are all nonzero or all zero, in particular A - A is positive if and only if A is injective, (iv) if U1, U2, , Un are eigenvectors of A- A respectively, with eigenvalues A1' A2, , An, then

in particular, if U1, U2, ... , Un are orthogonal to each other, then AU1' ... ,Aun are orthogonal to each other as well. Proof. (i) In fact, (A- A)-

= A- A-- = A- A.

(ii) and (iii) If Ax = 0, then trivially A- Ax = 0, and if A- Ax = 0, then (A- Axlx) On the other hand, (A- Axlx) = (AxIAx) = IAxl 2 hence Ax = 0 if (A- Axlx) = O. (iv) In fact, (AUiIAuj)

= (A- AUiluj) = Ai(Uiluj) = Ailuil28ij.

= O. 0

4.1 Elements of Spectral Theory

119

4.20 Proposition. The operator AA * : Y ----. Y is

(i) self-adjoint, (ii) nonnegative, (iii) A*x, AA*x and (AA*xlx) are either all nonzero or all zero, in particular AA * is positive if and only if ker A * = {O}, equivalently if and only if A is surjective. (iv) if U1, U2, ... , Un are eigenvectors of AA* with eigenvalues respectively, AI, A2' ... , An, then

in particular, if U1, U2, ... , Un are orthogonal to each other, then A*U1,.'" A*un are orthogonal to each other as well. Moreover, AA* and A* A have the same nonzero eigenvalues and

RankAA*

= RankA* A = Rank A = RankA*.

In particular, RankAA* = RankA* A

~

min(dimX,dim Y).

Proof. The claims (i) (ii) (iii) and (iv) are proved as in Proposition 4.19. To prove that A* A and AA* have the same nonzero eigenvalues, notice that if x E X, x # 0, is an eigenvalue for A* A with eigenvalue A # 0, A* Ax = AX, then Ax # by (iii) Proposition 4.19 and AA*(Ax) = A(A* Ax) = A(AX) = AAx, i.e., Ax is a nonzero eigenvector for AA* with the same eigenvalue A. Similarly, one proves that if yolO is an eigenvector for AA* with eigenvalue A # 0, then by (iii) A*y # and A*y is an eigenvector for A * A with eigenvalue A. Finally, from the alternative theorem, we have

°

°

RankAA*

= RankA* = Rank A = RankA* A. o

g. Powers of a self-adjoint operator Let A : X ----. X be self-adjoint. By the spectral theorem, there is an orthonormal basis (el, e2, ... , en) of X and real numbers AI, A2,"" An such that n Ax

=

LAj(x[ej)ej

"Ix E X.

j=l

By induction, one easily computes, using the eigenvectors el, e2,"" en and the eigenvalues AI, A2,"" An of A the k-power of A, Ak := Ao·· ·oA k times, 'Vk ~ 2, as n

Akx

=

L(Ai)k(xlei) ei

(4.5)

"Ix E X.

i=l

4.21 Proposition. Let A : X ----. X be self-adjoint and k

~

1. Then

(i) Ak is self-adjoint, (ii) A is an eigenvalue for A if and only if Ak is an eigenvalue for Ak,

120

4. Self-Adjoint Operators

(iii)

E X is an eigenvector of A with eigenvalue ..\ if and only if x is an eigenvector for A k with eigenvalue ..\k. In particular, the eigenspaces of A relative to ..\ and of Ak relative to ..\k coincide. (iv) If A is invertible, equivalently, if all eigenvalues of A are nonzero, then X

"Ix E X. 4.22~.

Let A: X

--->

X be self-adjoint. Show that

If p(t) = 2:;;=1 aktk is a polynomial of degree m, then (4.5) yields m

p(A)(x)

=L k=l

m

akAk(x)

n

n

=L

L ak..\j(xjej)ej k=l j=l

= LP(..\j)(xlej)ej.

(4.6)

j=l

4.23 Proposition. Let A : X --> X be a nonnegative self-adjoint operator and let kEN, k ?: 1. There exists a unique nonnegative self-adjoint operator B : X --> X such that B 2k = A. Moreover, B is positive if A is positive.

The operator B such that B 2k denoted by 2t0i'.

= A is called the 2kth root of A and is

Proof. If A(x) = ~'J=l Aj (x[ej )ej, (4.5) yields B 2k = A for n

B(x)

:=

L

2V\j(xlej)ej.

j=l

Uniqueness remains to be shown. Suppose Band C are self-adjoint, nonnegative and such that A = B 2k = C2k. Then B and C have the same eigenvalues and the same eigenspaces by Proposition 4.21, hence B = C. 0

In particular, if A : X --> X is nonnegative and self-adjoint, the operator square root of A is defined by n

VA(x) :=

L 0\J(x!ej)ej,

XEX,

i=l

if A has the spectral decomposition Ax

= 2:7=1 ..\j(x[ej)ej.

4.24~.

Prove Proposition 4.14 by noticing that, if A and M are self-adjoint and M is positive, then M-I/2 AM- 1 / 2 : X ---> X is well defined and self-adjoint.

4.25~.

Let A, B be self-adjoint and let A be positive. Show that B is positive if

S := AB + BA is positive. [Hint: Consider A-I/ 2 BA- 1 / 2 and apply Exercise 4.18.]

4.1 Elements of Spectral Theory

121

4.1.2 Normal operators a. Simultaneous spectral decompositions 4.26 Theorem. Let X be a Euclidean or Hermitian space. If A and B are two self-adjoint operators on X that commute, A=A*,

B=B*,

AB=BA,

then there exists an orthonormal basis (el' e2, ... , en) on X of eigenvectors of A and B, hence n Z

n

= ~)z!ei)ei' i=l

Az

= L Ai(zlei)ei,

n

Bz

i=l

=

LJ.li(z!ei)ei, i=l

AI, A2, ... , An E lR and J.ll, J.l2,"" J.ln E lR being the eigenvalues respectively of A and B. This is proved by induction as in Theorem 4.3 on account of the following.

4.27 Proposition. Under the hypoteses of Theorem 4.26, we have (i) A and B have a common nonzero eigenvector,

(ii) if V is invariant under A and B, then V 1- is invariant under A and B as well. Proof. (i) Let>. be all y E VA we have consequently, there (ii) For every w E (Bw[z) = (wIBz) =

an eigenvalue of A and let VA be the corresponding eigenspace. For ABy = BAy = >.By, i.e., By E VA' Thus VA is invariant under B, is an eigenvector w E VA of B IVA ' i.e., common to A and B. V.L and z E V, we have Az, Bz E V and (Aw[z) = (wIAz) = 0, 0, i.e., Aw,Bw E V.L. 0

4.28'. Show that two symmetric matrices A, B are simultaneously diagonizable if and only if they commute AB = BA.

b. Normal operators on Hermitian spaces A linear operator on a Euclidean or Hermitian space is called normal if N N* = N* N. Of course, if we fix an orthonormal basis in X, we may represent N with an n x n matrix N E Mn,n(C) and N is normal if and T only if NN = NT N if X is Hermitian or NN T = NTN if X is Euclidean. The class of normal operators, though not trivial from the algebraic point of view (it is not closed for the operations of sum and composition), is interesting as it contains several families of important operators as subclasses. For instance, self-adjoint operators N = N*, anti-self-adjoint operators N* = - N, and isometric operators, N* N = Id, are normal operators. Moreover, normal operators in a Hermitian space are exactly the ones that are diagonizable. In fact, we have the following.

122

4. Self-Adjoint Operators

4.29 Theorem (Spectral theorem). Let X be a Hermitian space of dimension n and let N : X ~ X be a linear operator. Then N is normal if and only if there exists an orthonormal basis of X made by eigenvectors ofN. Proof. Let (el, e2, ... , en) be an orthonormal basis of X made by eigenvectors of N. Then for every z E X n

n

N* z = L Aj (zlej )ej j=l

Nz = LAj(zlej)ej, j=l hence NN*z = Ej=IIAjI2(zlej)ej = N* Nz. Conversely, let

N +N* A:=---,

N - N* B:=---.

2 2i It is easily seen that A and B are self-adjoint and commute. Theorem 4.26 then yields a basis of orthonormal eigenvectors of A and B and therefore of eigenvectors of N :=

A+iBandN*=A-iB. 4.30'. Show that N : eigenspaces.

en

0 ~

en

is normal if and only if Nand N* have the same

c. Normal operators on Euclidean spaces Let us translate the information contained in the spectral theorem for normal operators on Hermitian spaces into information about normal operators on Euclidean spaces. In order to do that, let us first make a few remarks. As usual, in en we write z = x+iy, x, Y E IR n for z = (Xl +iYl,.·., X n + iYn)' If W is a subspace of IR n , the subspace of en

W e1 iW := { z E en I z = x

+ iy,

x, YEW}

is called the complexijied of W. Trivially, dimc(We1 iW) if V is a subspace of en, set

4.31 Lemma. A subspace V W if and only if V = V. Proof. If V = W EEl iW, trivially vectors

z+z

V

x:=-2-'

c

= dimIR W. Also,

en is the complexijied of a real subspace

= V. Conversely, if z E V is such that

z

-z

y:=~=

z E V,

the

(z/i) +~ 2

have real coordinates. Set

W :=

{x Ell~n Ix= z: z, zE V};

then it is easily seen that V = W EEl iW if V =

V.

o

4.1 Elements of Spectral Theory

123

For N : lRn --+ lRn we define its complexified as the (complex) linear operator Nc : en --+ en defined by Nc(z) := Nx+iNy if z = x+iy. Then we easily see that (i) oX is an eigenvalue of N if and only if oX is an eigenvalue of N c , (ii) N is respectively, a self-adjoint, anti-self-adjoint, isometric or normal operator if and only if N c is respectively, a self-adjoint, anti-selfadjoint, isometric or normal operator on en, (iii) the eigenvalues of N are either real, or pairwise complex conjugate; in the latter case the conjugate eigenvalues oX and "X have the same multiplicity. 4.32 Proposition. Let N : lRn --+ lRn be a normal operator. Every real eigenvalue oX of N of multiplicity k has an eigenspace V..\ of dimension k. In particular, V..\ has an orthonormal basis made of eigenvectors. Proof. Let A be a real eigenvalue for Ne, Nez = AZ. We have Nez

= Nx -

iNy

= Nez = AZ = >..z,

en

i.e., Z E is an eigenvector of Ne with eigenvalue A if and only if Z is also an eigenvector with eigenvalue A. The eigenspace E).. of Ne relative to >.. is then closed under conjugation and by Lemma 4.31 E).. := W).. EB iW).., where W)..:={xElRnlx=z;z, ZEE)..}, and dimlR W).. = dime E)... Since Ne is diagonizable in

e and W)..

C V).., we have

k = dime E).. = dim W).. :::; dimlR V)...

o

As dim V).. :::; k, see Proposition 2.43, the claim follows.

4.33 Proposition. Let oX be a nonreal eigenvalue of the normal operator N : lRn --+ lRn with multiplicity k. Then there exist k planes of dimension 2 that are invariant under N. More precisely, if e1, e2, ... , en E en are k orthonormal eigenvectors that span the eigenspace E..\ of N c relative to oX and we set . U 2j-1·=

e·J +e:-J

V2 '

U

.

2j·=

e·-e:J J

V2i '

then U1, U2, . .. , U2k are orthonormal in lR n , and for j = 1, ... ,k the plane Span {U2j-1, U2j}, is invariant under N; more precisely we have N(U2 j -d = aU2j-1 - (JU2j, { N(U2j) = (JU2j-1 + aU2j where oX =: a

+ i{J.

Proof. Let E).., ~ be the eigenspaces of Ne relative to >.. and X. Since Ne is diagonizable on e, then dime E).. = dime ~ = k, On the other hand, for

Z

E E)..

124

4. Self-Adjoint Operators

Nez = Nx - iNy = Nez = Xz. Therefore, z E E>. if and only ifz E EX' The complex subspace F>. := E>. EBEX oH: n has dimension 2k and is closed under conjugation; Lemma 4.31 then yields F>. = W>. EB iW>. where

W>.:={XEJRnlx=Z;z, ZEE>.}

and

dimIRW>.=dimeE=2k.

(4.7)

If (el, e2, ... , ek) is an orthonormal basis of E>., ("el, 'e2, ... , ek) is an orthonormal basis of Ex; since V2ej =: U2j-1

+ iU2j,

V2ej =: U2j-1 -

iU2j,

we see that {Uj} is an orthonormal basis of W>.. Finally, if>' := a

+ i{3, we compute

e.+e:-) >.e+Xe:N(U2j-d = Ne ( ::lj?- = ~ = ... = aU2j-1 - (3u2j, { N(U2j)=N(e~:) = >.ej';/"i ="'={3u2j-l+ aU2j, i.e., Span {U2j-l, U2j} is invariant under N.

o

Observing that the eigenspaces of the real eigenvalues and the eigenspaces of the complex conjugate eigenvectors are pairwise orthogonal, from Propositions 4.32 and 4.33 we infer the following. 4.34 Theorem. Let N be a normal operator on JR.n. Then JR.n is the direct sum of I-dimensional and 2-dimensional subspaces that are pairwise orthogonal and invariant under N. In other words, there is an orthonormal basis such that the matrix N associated to N in this basis has the block structure

o

5J

N'=

o

o

To each real eigenvalue A of multiplicity k correspond k blocks A of dimension 1 x 1. To each couple of complex conjugate eigenvalues oX, X of multiplicity k correspond k 2 x 2 blocks of the form

where

0:

+ i(3 := A.

4.35 Corollary. Let N : JR.n ........ JR.n be a normal operator. Then

(i) N is self-adjoint if and only if all its eigenvalues are real, (ii) N is anti-self-adjoint if and only if all its eigenvalues are purely imaginary (or zero),

(iii) N is an isometry if and only if all its eigenvalues have modulus one. 4.36~.

Show Corollary 4.35.

4.1 Elements of Spectral Theory

125

4.1.3 Some representation formulas a. The operator A * A Let A : X ---. Y be a linear operator between two Euclidean spaces or two Hermitian spaces and let A * : Y ---. X be its adjoint. As we have seen, A* A : X ---. X is self-adjoint, nonnegative and can be written as n

A* Ax

=

I>i(xlei)

ei

i=l

where (el' e2, , en) is a basis of X made of eigenvectors of A* A and for each i = 1, , n Ai is the eigenvalue relative to ei; accordingly, we also have n

(A*A)1/2 X := L/-li(x!ei)ei, i=l

where /-li := ,;>:;,. The operator (A* A)1/2 and its eigenvalues /-ll, ... ,/-In, called the singular values of A, play an important role in the description of A. 4.37'. Let A E Mm,n(JR). Show that IIAII := sUPlxl=l value of A. [Hint: IAxl 2 = (A * Ax) • x .J

IAxl

is the greatest singular

4.38 Theorem (Polar decomposition). Let A: X ---. Y be an operator between two Euclidean or two Hermitian spaces.

(i) If dim X ~ dimY, then there exists an isometry U: X ---. Y, i.e., U* U = Id, such that A = U(A* A)1/2. Moreover, if A = US with U*U = Id and S* = S, then S = (A* A)1/2 and U is uniquely defined on ker SJ.. = ker AJ... (ii) IfdimX ~ dimY, then there exists an isometry U: Y ---. X, i.e., U* U = Id such that A = (AA*)1/2U*. Moreover, if A = SU with U*U = Id and S* = S, then S = (AA*)1/2 and U is uniquely defined on ker SJ.. = 1m A. Proof. Let us show (i). Set n := dimX and N := dim Y. First let us prove uniqueness. If A = US where U*U = Id and S* = S, then A*A = S*U*US = S*S = S2, i.e., S = (A* A)1/2. Now from A = U(A* A)1/2, we infer for i = 1, ... ,n

if (e1, e2, ... , en) is an orthonormal basis of X of eigenvectors of (A* A)1/2 with relative eigenvalues 1'01,1'02, ... , I'on. Hence, U(ei) = :; A(e;) if I'oi =I 0, i.e., U is uniquely defined by A on the direct sum of the eigenspaces relative to nonzero eigenvalues of (A* A)1/2, that is, on the orthogonal of ker(A* A)1/2 = ker A. Now we shall exhibit U. The vectors A(e1),'" ,A(en) are orthogonal and IA(ei)1 = I'oi as

126

4. Self-Adjoint Operators

(A(e;)IA(ej)) = (A* A(ei)lej) = Ili(eilej) = lliOij. Let us reorder the eigenvectors and the corresponding eigenvalues in such a way that for some k, 1 S; k S; n, the vectors A(e1),.'" A(ek) are not zero and A(ek+d = ... =

111::ll

A(en ) = O. For i = 1, ... , k we set Vi := and we complete V1, V2, . .. , Vk to form a new orthonormal basis (V1, V2, ... , VN) of Y. Now consider U : X ---> Y defined by i = 1, ... ,n.

By construction (U(ei)IU(ej)) = Oij, i.e., U*U = Id, and, since Ili = IA(ei)1 = 0 for i > k, we conclude for every i = 1, ... , n

(ii) follows by applying (i) to A *.

0

b. Singular value decomposition Combining polar decomposition and the spectral theorem we deduce the so-called singular value decomposition of a matrix A. We discuss only the real case, since the complex one requires only a few straightforward changes. Let A E MN,n(IR) with n :::; N. The polar decomposition yields A

= U(AT A)1/2

with

On the other hand, since ATA is symmetric, the spectral theorem yields S E Mn,n(IR) such that

where /11, /12, ... , /1n are the squares of the singular values of A. Recall that the ith column of S is the eigenvector of (A * A)1/2 relative to the eigenvalue /1i' In conclusion, if we set T := US T E MN,n (IR), then TTT = Id, STS = Id and A = Tdiag (/11, /12,"" /1n) S. This is the singular value decomposition of A, that is implemented in most computer libraries on linear algebra. Starting from the singular value decomposition of A, we can easily compute, of course, (AT A)1/2, and the polar decomposition of A. 4.39. We notice that the singular value decomposition can be written in a more symmetric form if we extend T to a square orthogonal matrix Y E MN,N(lR), yTy = Id and extending diag (Ill, 1l2, ... , Iln) to a N x n matrix by adding N - n null rows at the bottom. Then, again A = Yll.S where Y E MNxN(lR), yTy

=

Id, S E M n ,n(IR), STS

=

Id and

4.1 Elements of Spectral Theory

o o

j1.i

0

0

j1.2

0 0

0 0

j1.n

0

0

o

~=

127

o

c. The Moore-Penrose inverse

Let A : X -+ Y be a linear operator between two Euclidean or two Hermitian spaces of dimension respectively, nand m. Denote by P :X

-+

ker A.l

and

Q:Y-+lmA

the orthogonal projections operators to ker A.l and ImA. Of course Ax = Qy has at least a solution x E X for any y E Y. Equivalently, there exists x E X such that y - Ax ..L 1m A. Since the set of solutions of Ax = Qy is a translate of ker A, we conclude that there exists a unique x := At y E X such that y - Ax ..L ImA, { x E ker A.l, The linear map At : Y

Ax = Qy, { x=Px.

equivalently,

-+

X, y

-+

(4.8)

At y , defined this way, i.e.,

is called the Moore-Penrose inverse of A: X

-+

Y. From the definition

= Q, AtA = P, ker At = ImA.l = kerQ, 1m At = ker A.l . AAt

j

4.40 Proposition. At is the unique linear map B : Y

AB=Q,

BA=P

and

ker B

-+

X such that

= kerQ;

(4.9)

moreover we have

A * AA t = At AA * = A *.

(4.10)

128

4. Self-Adjoint Operators

Proof. We prove that B = At by showing for all y E Y the vector x := By satisfies (4.8). The first equality in (4.9) yields Ax = ABy = Qy and the last two imply x = By = BQy = BAx = Px. Finally, from AAt = Q and At A = P, we infer that A*AAt=A*Q=A*, using also that A*Q = A* and PA* (ker A*)i. and ImA* = ker Ai..

=

AtAA*=PA*=A*, A* since A and A* are such that 1m A = 0

The equation (4.10) allow us to compute At easily when A is injective or surjective.

4.41 Corollary. Let A : X -> Y be a linear map between Euclidean or Hermitian spaces of dimension nand m, respectively.

(i) IfkerA = {O}, then n

~

m, A*A is invertible and At = (A* A)-l A*;

moreover, if A = U(A* A)1/2 is the polar decomposition of A, then At = (A* A)-1/2U*. (ii) Ifker A* = {O}, then n 2:: m, AA* is invertible, and

moreover, if A = (AA*)1/2U* is the polar decomposition of A, then At = U(AA*)-1/2.

For more on the Moore-Penrose inverse, see Chapter 10.

4.2 Some Applications In this final section, we illustrate methods of linear algebra in a few specific examples.

4.2.1 The method of least squares a. The method of least squares Suppose we have m experimental data Yl, Y2, ... , Ym when performing an experiment of which we have a mathematical model that imposes that the data should be functions,
4.2 Some Applications

129

model as a map ¢ : X - t lRm . Then, we introduce a cost function C = C(¢(x), y) that evaluates the error between the expected result when the parameter is x, and the experimental data. Our problem then becomes that of finding a minimizer of the cost function C. If we choose (i) the model of the data to be linear, Le., X is a vector space of dimension nand ¢ = A : X - t lRm is a linear operator, (ii) as cost function, the function square distance between the expected and the experimental data, (4.11)

C(x) = lAx - yl2 = (Ax - ylAx - y), we talk of the (linear) least squares problem. 4.42 Theorem. Let X and Y be Euclidean spaces, A : X map, y E Y and C : X - t lR the function

C(x) := lAx - yl~,

-t

Y a linear

xE X.

The following claims are equivalent (i) x is a minimizer of C, (ii) y - Ax 1. lmA, (iii) x solves the canonical equation

A*(Ax - y)

= O.

(4.12)

Consequently C has at least a minimizer in X and the space of minimizers of C is a translate of ker A. Proof. Clearly minimizing is equivalent to finding z = Ax E 1m A of least distance from y. By the orthogonal projection theorem, x is a minimizer if and only if Ax is the orthogonal projection of y onto 1m A. We therefore deduce that a minimizer x E X for C exists, that for two minimizers Xl, X2 of C we have AXl = AX2, Le., Xl - X2 E ker A and that (i) and (ii) are equivalent. Finally, since 1m Ai- = ker A*, (ii) and (iii) are clearly equivalent. 0

4.43 Remark. The equation (4.12) expresses the fact that the function x -+ IAx-b[2 is stationary at a minimizer. In fact, compare 3.65, since V' x(z[x) = z and V' x(Lx[x) = 2Lx if L is self-adjoint, we have 2 [Ax - bl 2 = Ibl 2 - 2(bIAx) + IAxI , V'(bIAx) = V'(A*b[x) = A*b,

V'x[AxI 2

= V'x(A* Axlx) = 2A* Ax

hence V'xlb- Axl 2 = 2A*(Ax - b).

As a consequence of Theorem 4.42 on account of (4.8) we can state the following 4.44 Corollary. The unique minimizer of C(x) ker AJ.. is x = At y .

= [Ax -

y[~ in lmA*

=

130

4. Self-Adjoint Operators

b. The function of linear regression Given m vectors Xl, X2, ... , Xm in a Euclidean space X and m corresponding numbers Yl, Y2, ... , Ym, we want to find a linear map L : X -+ IR that minimizes the quantity m

F(L) :=

L IYi -

2 L(Xi)1 .

i=l

This is in fact a dual formulation of the linear least squares problem. By Riesz's theorem, to every linear map L : X -+ IR corresponds a unique vector w LEX such that L(y) := (ylw L), and conversely. Therefore, we need to find w E X such that m

L IYi -

C(w) :=

(xil w )1 2

-+

min.

i=l

If Y := (YI' Y2, ... , Ym) E IR m and A : X

-+

we are again seeking a minimizer of C : X

IR m is the linear map

-+

IR wE X.

Theorem 4.42 tells us that the set of minimizers is nonempty, it is a translate ofker A and the unique minimizer ofC in ker Ai- = ImA* is w:= At y . Notice that n

A*a

= Laixi, i=l

hence, w E 1m A * = ker Ai-if and only if w is a linear combination of X2, ... , Xm . We therefore conclude that At y is the unique minimizer of the cost function C that is a linear combination of Xl, X2,.'" Xm . The corresponding linear map L(x) := (xIAt y ) is called the function of linear regression.

Xl,

4.2.2 Trigonometric polynomials Let us reconsider in the more abstract setting of vector spaces some of the results about trigonometric polynomials, see e.g., Section 5.4.1 of [GM2]. Let Pn,21r be the class of trigonometric polynomials of degree m with complex coefficients n

P n ,21r :=

{P(x)

=

L k=-n

Ck

eikx

ICk

E C,

k

=

-n, ... ,n}.

4.2 Some Applications

131

Recall that the vector (C n , ... , cn) E C2n +1 is called the spectrum of P(x) = :E~=-n Ckeikx. Clearly, Pn ,21r is a vector space over C of dimension at most 2n + 1. The function (PIQ) : P n ,21r X P n ,27r -----> C defined by (PIQ) := - 1 j1r P(t)Q(t) dt 27f -1r

is a Hermitian product on P n ,21r that makes P n ,21r a Hermitian space. Since

see Lemma 5.45 of [GM2], we have the following.

4.45 Proposition. The trigonometric polynomials {e i kx h=-n,n form an orthonormal set of 2n + 1 vectors in P n ,27r and we have the following.

(i) P n ,21r is a Hermitian space of dimension 2n + 1. (ii) The map ~: Pn ,27r -----> C2n+l, that maps a trigonometric polynomial to its spectrum is well defined since it is the coordinate system in Pn,21r relative to the orthonormal basis {e i kX}. In particular ~ : Pn,21r -----> 2n+l is a (complex) isometry. (iii) (FOURIER COEFFICIENTS) For k = -n, ... , n we have

c

Ck = (Ple ikx ) =

~ j1r 27f

P(t)e- ikt dt.

-1r

(iv) (ENERGY IDENTITY)

2~

i

1r IP(tW dt =

IIPI1 2 := (PIP)

=

t

I(PleikxW =

k=-n

1r

t

ICkI 2 •

k=-n

a. Spectrum and products Let P(x) = :E~=-n Ckeikx and Q(x) = :E~=-n dke ikx be two trigonometric polynomials of order n. Their product is the trigonometric polynomial of order 2n n n n P(x)Q(x) = Ck eikx dk eikx = Chdkei(h+k)x k=-n k=-n h,k=-n 2n iPX = Chdk )e . p=-2n h+k=p

L

L

L

L (L

If we denote by {cd * {dd the product in the sense of Cauchy of the spectra of P and Q, we can state the following.

132

4. Self-Adjoint Operators

4.46 Proposition. The spectrum of P(x)Q(x) is the product in the sense of Cauchy of the spectra of P and Q

4.47 Definition. The convolution product of P and Q is defined by P

* Q(x) := - 1

211"

j1r P(x + t)Q(t) dt. -1r

Notice that the operation (P, Q) -... P antilinear in the second one. We have

* Q is linear in the first

factor and

4.48 Proposition. P*Q is a trigonometric polynomial of degree n. Moreover the spectrum of P * Q is the term-by-term product of the spectra of P and Q,

Proof. In fact for h, k = -n, ... ,n, we have

n

n

L L

P*Q(x) =

n

L

chdkdhkeikx =

Ckdk eikx .

k=-n

h=-nk=-n

o b. Sampling of trigonometric polynomials A trigonometric polynomial of degree n can be reconstructed from its values on a suitable choice of its values on 2n + 1 points, see Section 5.4.1 of [GM2]. Set Xj := 2;~lj, j = -n, ... , n, then the sampling map

C .p . n,21r

-...1f"'2n+1 \l...

C(P) := (P(x- n ), ... , P(x n ))

,

is invertible, in fact, see Theorem 5.49 of [GM2],

1 n P(x) := 2n + 1 L

P(xj)Dn(x - Xj)

j=-n

where Dn(t) is the Dirichlet kernel of order n n

Dn(t):= L k=-n

n

eikt=1+2Lcoskt. k=l

4.2 Some Applications

Trigonometric polynomials of degree n

133

Spectrum

..

C 2n + 1 ikt 2:~=-n Cke '-----------'

Samplings c2n+l

Figure

4.1. The scenario of trigonometric polynomials, spectra and samples.

4.49 Proposition. v'2~+1 C and its inverse J2n + 1C- 1 Pn,21f given by

are isometries between P n ,21f and C2n + 1 • Proof. In fact, C maps e i kt, k =

t

(C(e i ht)IC(e ikt )) =

.

exp

J=-n

-n, ... ,n,

to an orthonormal basis of C 2n + 1:

(i 21r(h - k) j) = D n (~(h 2n + 1 2n + 1

k)) = (2n

+ l)<>hk. o

From the samples, we can directly compute the spectrum of P. 4.50 Proposition. Let P(x) E P n ,21f and Then

-

1

J1f

21f

P(t)e- ikt dt

-1f

:= 2~~lj, j = -n, ... ,n.

L

= -1-

2n + 1

Xj

n

P(x)e- ikxj .

k=-n

(4.13)

J

Proof. Since (4.13) is linear in P, it suffices to prove it when P(x) -n, ... , n. In this case, we have 2~ J~" P(t)e- i kt dt = <>hk and 1

n

1

n

' " ei(h-k)xj = - - ' " D ( ) <> 2n+1.L.J 2n+1 L.J nXh-k = hk, J=-n

since Dn(xj)

= °for j

j=-n

of- 0, j E [-n,n] and Dn(O)

= 2n+ 1.

o

134

4. Self-Adjoint Operators

c. The discrete Fourier transform The relation between the values {P( tj)} of PEPn,21r at the 2n + 1 points tj and the spectrum P of P in the previous paragraph is a special case of the so-called discrete Fourier transform. For each positive integer N, consider the 21r-periodic function EN(t) : lR -+ e given by N-l

EN(t) := ~ e ~

ikt

{

=

N

if t is a multiple of 21r,

k=O

otherwise.

Let w = ei~ and let 1,w,w2 , ... ,w N hE Z we have

~

I:

w hk

=

k=O

(4.14)

iN'

l-e l-e i t

{I°

1

be the Nth roots of one. For

if h is a multiple of N,

(4.15)

otherwise,

in particular, N-l

1 ~ hk N ~w =8 hk

if - N

< h < N.

(4.16)

k=O

The discrete Fourier transform of order N, DFTN defined by DFTN(y) := Uy rows by column, where

U

= [U]],

eN

= 0, ... , N -

Vi,j

-+

1.

The inverse discrete Fourier transform of order N, IDFTN : eN is defined by IDFTN(z) := Vz where

Vi,j

eN, is

-+

eN,

= O,N-1.

4.51 Proposition. IDFTN is the inverse of DFTN . Moreover, the operators VNDFTN and J-NIDFTN are isometries of eN. Proof. In fact, by (4.16)

(VV)j

=~ N

N-I

L:

k=O

w-ikw kj

=~ N

N-I

L:

i.e., V = V-I and, by the definition of V and V,

itV-I.

w(j-i)k

= 8j,

k=O

uT = it V,

hence

UT =

it V

= 0

4.2 Some Applications

135

Notice that, according to their definitions, we need N 2 multiplications to compute DFTN (or IDFTN ). There is an algorithm, that we shall not describe here, called the Fast Fourier Transform that, using the redundance of some multiplications, computes DFTN (or IDFTN ) with only N multiplications with a performance of O(N log N). Let P(t) = I:~=-n Ckeikx E Pn,271: and let N 2: 2n + 1. A computation similar to the one in Proposition 4.50 shows that

A=

1

2rr

171: -71: P(t)e- kt dt =

1

N-l

N ~ P(Xj )e-

ikxj

=

DFTNy

(4.17)

where y := (P(xo), ... , P(XN)) and Xj := 't; j, -N < j < N. Thus the spectrum of P is the DFTN of its values at Xj if n < N /2. On the other hand, if z := (zo, ... , ZN-l) is the vector defined by if 0

~

k

~

n,

if n < k < N/2, if N/2 ~ k ~ N/2+n, if N /2 + n < k < N and we recall that IDFTN is the inverse of DFTN, we have

i.e., the values of Pat Xj are the IDFTN of the spectrum of P. 4.52 Frequency spectrum. In applications, the DFTN and IDFTN may appear slightly differently. If f is a To-periodic function, one lets T o/ N be the period of sampling, so that tj := ~ j = jT, j = 0,1, ... , N - 1, are the sampling points and DTFN produces the sequence

1 Ck := N

L f(jT)e'N"k).

N-l

.2"

.

j=o In other words, the values of {cd are regarded as the values of the component of frequency I/k := kA = );T' i.e., as the samples of the so-called

frequency spectrum

i: lR --+ C of f, defined by 1(1/)

:=

{Ck

o

if 1/ = I/k = otherwise.

);T'

The discrete Fourier transform and its inverse then rewrite as

136

4. Self-Adjoint Operators

l(;T) =

N-l

~

L f(jT)e-i~jk,

j=o N-l

f(kT) =

.

L l(~T)eiZ;jk.

j=O

4.2.3 Systems of difference equations Linear difference equations of first and second order are discussed e.g., in [GM2]. Here we shall discuss systems of linear difference equations.

a. Systems of linear difference equations First let us consider systems of first order. Let A E Mk,k(C)' The homogeneous linear recurrence for the sequence in C k

Xn+l = AXn , n 2: 0, { X o given has the unique solution X n := An X o "In, as one can easily check.

4.53 Proposition. Given {Fn } in C k , the recurrence

Xn+l = AXn + Fn+l1 { X given o

n 2: 0,

has the solution n

X n := AnXo + LAn-jFj j=O

where we assume Fo := 0. Proof. In fact, for n X n +l = A n +1Xo

~

0 we have n+l

+L

A n+1-j F j = A n +1Xo

j=O

=

A AnXo +A

tAn-j F j j=O

= AXn

n

+L

A n +1-j Fj

+ F n +1

j=O

+

F n+l = A(Anxo

+

tAn-jFj)

+ Fn+l

j=O

+ Fn+ 1 • o

4.2 Some Applications

137

4.54 Higher order linear difference equations. Every equation Xn+k

+ ak-1 Xn+k-l + ... + aox n =

n~O

fn+I,

(4.18)

can be transformed into a k x k system of difference equations of first order. In fact, if X n := (X n ,Xn +l, ... ,Xn +k_l)T E C k ,

Fn

:=

(0,0, ... ,0, fnf

E

Ck ,

and A is the k x k matrix 1 0

0 0

0 1

0 0

A:=

(4.19)

0

0

0

1

-aD

-al

-a2

-ak-l

it is easily seen that X n+1 = AXn

+ Fn+1

(4.20)

and conversely, if {X n } solves (4.20), then {x n }, Xn := Xi; \:In, solves (4.18). In this way the theory of higher order linear difference equations is subsumed to that of first order systems. In this respect, one computes for the matrix A in (4.19) that k-l

det(>.Id - A)

= >.k + I>j>.j. j=O

This polynomial in >. is called the characteristic polynomial of the difference equation (4.18). b. Power of a matrix Let us compute the power of A in an efficient way. To do this we remark the following. (i) If B is similar to A, A

and, by induction,

=

S-1 BS for some S with det S =j:. 0, then

138

4. Self-Adjoint Operators

(ii) If B is a block matrix with square blocks in the principal diagonal

Go

°

°G

B=

0

then

0

0

~o Bn

0

oEJ

=

G 0

0

0

6

Let .AI, .A2,' .. , .Ak be the distinct eigenvalues of A with multiplicities ml, m2,"" mk. For every k, let Pk be the dimension of the eigenspace relative to .Ak (the geometric multiplicity). Then, see Theorem 2.65, there exists a nonsingular matrix S E Mk,k(C) such that J := S-l AS has the Jordan form

Boo B o

J=

0

0

0

o o

0

where i = 1, ... , k, j = 1, ... ,Pi and if Ji,j has dimension 1,

.Ai

Ji,j

=

.Ai

1

0

.Ai

0 1

0 0

0 0

otherwise. 0 0

0 0

0 0

.Ai 0

1 .Ai

4.2 Some Applications

139

Consequently An = SJnS-l, and

I J1,l I

a

a

a

a

I J 1,21

a

a

a

a

a

@;]

In =

k,Pk

It remains to compute the power of each Jordan block. If J' = Ji,j = (A) has dimension one, then Jm = An. If instead J' = J i,j is a block of dimension q at least two,

A

1

a

a

a

A

1

0

J' =

a o

A 1 o A

0

0

then

B ji

J' = Ald+B,

._;: . - Ui+l,j·

Since

we have Bq

(BT)i

= {<5T+i,j if r < q,

J

if r 2: q,

a

= O. Thus Newton's binomial formula yields

i.e.,

1 nl.oX

J,n

=

G) ;2 nl.

0

1

0

0

1

0

0

0

oX

An

1

140

4. Self-Adjoint Operators

Notice that each element of An

= SJ n S- 1 has the form

k

LAjpj(n) j=l

where AI, A2,"" An are the eigenvalues of A and Pj(t) is a polynomial of degree at most Pj -1, where Pj is the algebraic multiplicity of Aj. It follows that for p > maxi (IAiI) there is a constant Cp such that every solution of X n+1 = AXn satisfies

In particular we have the following. 4.55 Theorem. If all eigenvalues of A have modulus less than one, then every solution of Xn+l = AXn converges to zero as n --+ +00. Proof. Fix (T > 0 such that maxi=l.n I>"i I < (T < 1. As we have seen, there exists a constant Cu such that if Xn is a solution of Xn+l = AXn Vn, then

Since 0 <

(T

< 1,

(Tn

->

0, and the claim is proved.

0

4.56 Example (Fibonacci numbers). Consider the sequence of Fibonacci numbers

In+2 = In+1 + In { 10 = 0, h = 1,

n:::: 0,

(4.21)

that is given by

n:::: 0, see e.g., [GM2J. Let us find it again as an application of the above. Set

Fn :=

(

In ) In+l

then

F n+l { Fo

=

=

(In+l) In+2

=

(In+l ) In + In+l

(~)

and,

where

A=(~ ~).

(0

1

(4.22)

4.2 Some Applications

141

The characteristic polynomial of A is det(oXId - A) = oX(oX - 1) - 1, hence A has two distinct eigenvalues oX := 1 + v'5, fJ-:= 1 - v'5. 2 2 An eigenvalue relative to oX is (1, oX) and an eigenvector relative to fJ- is (1, fJ-). The matrix A is diagonizable as A = S~S-l where s:=

(~

:),

It follows that F

e; :n) (~1)

n n(~) =s~nS-l (~) oX~fJ-S =A

=

=oX~fJ-(~

:)(:;n).

Consequently,

4.2.4 An ODE system: small oscillations Let Xl, X2, ... , XN be N point masses in IR 3 each respectively, to a nonzero mass ml, m2, ... , mN. Assume that each point exerts a force on the other points according to Hooke's law, i.e., the force exerted by the mass at Xj on Xi is proportional to the distance of Xj from Xi and directed along the line through Xi and Xj, j

1= i.

By Newton's reaction law, the force exerted by Xi on Xj is equal and opposite in direction, hi = - lij, consequently the elastic constants k ij , i 1= j, satisfy the symmetry condition k ij = k ji . In conclusion, the total force exerted by the system on the mass at Xi is N

fi = - L

kij(xj-xd=- L

j=:~"t

where we set k ii := -

kijxj+( L

j=:~"t 2:j=l.N

j=F i

kij)Xi=-LkijXj

j=:~·t

j=l

kij. Newton's equation then takes the form i

= 1, ... ,N,

(4.23)

with the particularity that the jth component of the force depends only on the jth component of the mass. The system then splits into 3 systems of N equations of second order, one for each coordinate. If we use the matrix notation, things simplify. Denote by M := diag {ml' m2, ... , mN}

142

4. Self-Adjoint Operators

the positive diagonal matrix of masses, by K := (k ij ) E MN,N(lR) the symmetric matrix of elastic contants, and by X(t) E lR N the jth coordinates of the points Xl, ... , XN Xi

=:

(x},x;,xf),

i.e., the columns of the matrix

Then (4.23) transforms into the system of equations

MX"(t) + KX(t) = 0

(4.24)

where the product is the product rows by columns. Finally, ifX"(t) denotes the matrix of second derivatives of the entries of X(t), the system (4.23) can be written as X"(t) + M-lKX(t) = 0, (4.25) in the unknown X : lR ---t MN,n(lR). Since M-lK is symmetric, there is an orthonormal basis of lR N made by eigenvalues of M- l K and real numbers AI, A2, ... , AN such that and notice that Ul, U2,'." UN are pairwise orthonormal vectors since M is diagonal. Denoting by P j the projection operator onto Span {Uj} we also have N

M-lK

=

I: AjP

j .

j=l

Thus, projecting (4.25) onto Span {Uj} we find

0= Pj(O) = Pj(X" + M- 1 KX) = (PjX)" + Aj(PjX),

Vj

= 1, ... ,N,

i.e., the system (4.25) splits into N second order equations each in the unknowns of the matrix PjX(t). Since K is positive, the eigenvalues are positive, consequently each element of the matrix PjX(t) is a solution of the harmonic oscillator

n-

y(t) = cos( V Ajt)y(O) +

sin(.Jf0t) , n- y (0), V Aj

hence

In conclusion, since Id = L:f=l Pj , we have

4.3 Exercises

143

N

X(t)

=

L PjX(t) j=l

(4.26)

The numbers ';>:;/(21f) , ... ..;J:;;/(21f) are called the proper frequencies of the system. We may also use a functional notation A2n+l

00

sin A := L(-lt ( )" 2n+ 1 . k=O

00

cos A :=

A 2n

L(-lt (2n)! k=O

and we can write (4.26) as X(t)

= cos(tVA)X(O) + sin~f~)x'(O),

where A:= M-1K.

4.3 Exercises 4.57~.

Let A be an n x n matrix and let A be its eigenvalue of greatest modulus. Show that IAI :::; sUPi(lail + la~1 + ... + la~I). 4.58 ~ Gram matrix. Let {II, 12, ... , 1m} be m vectors in lR n . The matrix G = [9ij] E Mm,n(lR) defined by gij = (lil/j) is called Gmm's matrix. Show that G is nonnegative and it is positive if and only if II, 12, ... , 1m are linearly independent. 4.59~. Let A, B : en ---> en be self-adjoint and let A be positive. Show that the eigenvalues of A -1 B are real. Show also that A -1 B is positive if B is positive.

4.60~. Let A = [ail E M n ,n(lK) be self-adjoint and positive. Show that detA :::; (trA/n)n and deduce detA:::; n~=1a:. [Hint: Use the inequality between geometric and aritmethic means, see [GM1].] 4.61 ~. Let A E M n ,n(lK) and let aI, a2, ... , an E IK n be the columns of A. Prove Hadamard's lormula detA:::; n~=1Iail. [Hint: Consider H = A·A.] 4.62~.

Let A, BE Mn,n(lR) be symmetric and suppose that A is positive. Then the number of positive, negative and zero eigenvalues, counted with their multiplicity, of AB and of B coincide. 4.63~. Show that liN· Nil = IlNI1 2 if N is normal.

144

4. Self-Adjoint Operators

4.64 , Discrete Fourier transform. Let T : eN -> eN be the cycling forward shifting operator T((zo, Zl, ... ,ZN-1)) := (zt, Z2, ... ,ZN -1, zo). Show that (i) T is self-adjoint, (ii) the N eigenvalues of T are the Nth roots of 1, (iii) the vectors

._

Uk·-

1 (1 ,w,w k 2k , ... ,w k(N-1)) , VN

·2"

W

:= etN', k = 0, ... ,N - 1,

form an orthonormal basis of eN of eigenvectors of T; finally the cosine directions (zluk) of z E eN with respect to the basis (uo, ... , UN,) are given by the Discrete Fourier transform of z. 4.65'. Let A, B : X -> X be two self-adjoint operators on a Euclidean or Hermitian space. Suppose that all eigenvalues of A - B are strictly positive. Order the eigenvalues ).,1, ).,2, , ).,n of A and J1.1, J1.2, ... , J1.n of B in a nondecreasing order. Show that ).,i < J1.i Vi = 1, , n. [Hint: Use the variational characterization of the eigenvalues.] 4.66'. Let A : X -> X be self-adjoint on a Euclidean or Hermitian space. Let ).,t, ).,2, ... , ).,n and J1.1, J1.2,· .. , J1.n be respectively, the eigenvalues and the singular values of A that we think of as ordered as 1).,11 ::; 1).,21 ::; ... ::; I).,nl and J1.1 ::; J1.2 ::; ... ::; J1.n· Show that I).,il = J1.i Vi = 1, ... , n. [Hint: A* A = A2.J 4.67'. Let A : X -> X be a linear operator on a Euclidean or Hermitian space. Let m, M be respectively the smallest and the greatest singular value of A. Show that m::; 1).,1 ::; M for any eigenvalue)., of A. 4.68'. Let A: X spaces. Show that

->

Y be a linear operator between two Euclidean or two Hermitian

(i) (A* A)1/2 maps ker A to {O}, (ii) (A* A)1/2 is an isomorphism from ker A.L onto itself, (iii) (AA*)1/2 is an isomorphism from ImA onto itself. 4.69'. Let A : X -> Y be a linear operator between two Euclidean or two Hermitian spaces. Let (ut, U2, ... , Un) and J1.1, J1.2, ... , J1.n, J1.i 2: 0 be such that (ut, U2,···, Un) is an orthonormal basis of X and (A* A)1/2 x = Li J1.i(xlui)ui' Show that

(i) AA*y = Ll"i#oJ1.i(yIAui)Aui Vy E Y, (ii) If B denotes the restriction of (A* A)1/2 to ker A.L, see Exercise 4.68, then "Ix E kerA.L,

(iii) If C denotes the restriction of (AA*)1/2 to 1m A, see Exercise 4.68, then C- 1y =

L

1 -(yIAui)Aui l"i#O J1.i

Vy E ImA.

4.70'. Let A E MN,n(lI(), N 2: n, with Rank A = n. Select n vectors Ut, U2, ... , Un E J!(n such that AU1, ... , AUn E J!(N are orthonormal. [Hint: Find U E Mn,n(J!() such that AU is an isometry.]

4.3 Exercises

145

4.71 ,. Let A E MN,n(IR) and A = ULlY, where U E O(N), Y E O(n). According to 4.39, show that At = y T Ll'UT where ...L

Ll'=

0

0

0

0

0

0

0 ...L

0

0

...L

0

0

0

0

0

0

0

0

1-'1

1-'2

I-'k

J1.1, J1.2, .•• , J1.k being the nonzero singular values of A.

4.72 ,. For u : IR.

->

IR. 2 , discuss the system of equations

-1) 2

u = O.

4.73'. Let A E Mn,n(IR.) be a symmetric matrix. Discuss the following systems of ODEs x' (t)

+ Ax(t) = 0, + Ax(t) =

- ix'(t)

x" (t)

+ Ax(t) =

0,

0, where Ais positive definite

and show that the solutions are given respectively by 17

cos(tv A)x(O)

+

sin(tv'A) , v'A x (0).

4.74'. Let A be symmetric. Show that for the solutions of x"(t) + Ax(t) = 0 the energy is conserved. Assuming A positive, show that Ix(t)1 ::; E/>-l where E is the energy of x(t) and >- the smallest eigenvalue of A. 4.75'. Let A be a Hermitian matrix. Show that Ix(t)1 = const if x(t) solves the Schrodinger equation ix' + Ax = O.

Part II

Metrics and Topology

Felix Hausdorff (1869-1942), Maurice Frechet 1932).

(1878~1973) and

Rene-Louis Baire (1874-

5. Metric Spaces and Continuous Functions

The rethinking process of infinitesimal calculus, that was started with the definition of the limit of a sequence by Bernhard Bolzano (1781-1848) and Augustin-Louis Cauchy (1789-1857) at the beginning of the XIX century and was carried on with the introduction of the system of real numbers by Richard Dedekind (1831-1916) and Georg Cantor (1845-1918) and of the system of complex numbers with the parallel development of the theory of functions by Camille Jordan (1838-1922), Karl Weierstrass (18151897), J. Henri Poincare (1854-1912), G. F. Bernhard Riemann (18261866), Jacques Hadamard (1865-1963), Emile Borel (1871-1956), ReneLouis Baire (1874-1932), Henri Lebesgue (1875-1941) during the whole of the XIX and beginning of the XX century, led to the introduction of new concepts such as open and closed sets, the point of accumulation and the compact set. These notions found their natural collocation and their correct generalization in the notion of a metric space, introduced by Maurice Frechet (1878-1973) in 1906 and eventually developed by Felix Hausdorff (1869-1942) together with the more general notion of topological space. The intuitive notion of a "continuous function" probably dates back to the classical age. It corresponds to the notion of deformation without "tearing". A function from X to Y is more or less considered to be continuous if, when x varies slightly, the target point y = f(x) also varies slightly. The critical analysis of this intuitive idea also led, with Bernhard Bolzano (1781-1848) and Augustin-Louis Cauchy (1789-1857), to the correct definition of continuity and the limit of a function and to the study of the properties of continuous functions. We owe the theorem of intermediate values to Bolzano and Cauchy, around 1860 Karl Weierstrass proved that continuous functions take on maximum and minimum values in a closed and limited interval, and in 1870 Eduard Heine (1821-1881) studied uniform continuity. The notion of a continuous function also appears in the work of J. Henri Poincare (1854-1912) in an apparently totally different context, in the so-called analysis situs, which is today's topology and algebraic topology. For Henri Poincare, analysis situs is the science that enables us to know the qualitative properties of geometrical figures. Poincare referred to the properties that are preserved when geometrical figures undergo any kind of deformation except those that introduce tearing and glueing of points. An intuitive idea for some of these aspects may be provided by the following examples.

150

5. Metric Spaces and Continuous Functions

.ou.K1lJlIblItO:'oO(j.... PIIIDIt..U.T'IIOIlI.DU~'

...........(1I"' ..._

....

~

•• a.

GRl'XDZ'CGE D••

ME

1

E P CE AB TRAIT F£~U ....n _ H.....,....

LERRE

llH DORPF

'f ..... N:I

'''''15n co:. I1rH'n'il'U

Oo\ll'1l1.lMtI· U.UM

..-.nn_

. . . . . . . a.Uj <10.

0JJ0,,0,4.~.

I. ~' ......... ' "...... ~11 .1

O;U{,.,.l

LEIPZTG fl:IT" COil". IlL.

~O:ll

Figure 5.1. Frontispieces of Les espaces abstraits by Maurice Frechet (1878-1973) and of the Mengenlehre by Felix Hausdorff (1869-1942).

o Let us draw a disc on a rubber sheet. No matter how one pulls at the rubber sheet, without tearing it, the disc stays whole. Similarly, if one draws a ring, any way one pulls the rubber sheet without tearing or glueing any points, the central hole is preserved. Let us think of a loop of string that surrounds an infinite pole. In order to separate the string from the pole one has to break one of the two. Even more, if the string is wrappped several times around the pole, the linking number between string and pole is constant, regardless of the shape of the coils. o We have already seen Euler's formula for polyhedra in [GMl]. It is a remarkable formula whose context is not classical geometry. It was Poincare who extended it to all surfaces of the type of the sphere, Le., surfaces that can be obtained as continuous deformations of a sphere without tearing or glueing. o lR, lR 2 , lR3 are clearly different objects as linear vectorspaces. As we have seen, they have the same cardinality and are thus undistinguishable as sets. Therefore it is impossible to give meaning to the concept of dimension if one stays inside the theory of sets. One can show, instead, that their algebraic dimension is preserved by deformations without tearing or glueing. At the core of this analysis of geometrical figures we have the notion of a continuous deformation that corresponds to the notion of of a continuous one-to-one map whose inverse is also continuous, called homeomorphisms. We have already discussed some relevant properties of continuous functions f : lR --; lR e f : lR2 --; lR in [GMl] and [GM2]. Here we shall discuss continuity in a sufficiently general context, though not in the most general.

5.1 Metric Spaces

151

Poincare himself was convinced of the enormous importance of extending the methods and ideas of his analysis situs to more than three dimensions. .,. L 'analysis situs Ii plus de trois dimensions presente des difficultes enormes; il faut pour tenter de les surmonter etre bien persuade de l'extreme importance de cette science. Si cette importance n'est pas bien comprise de tout Ie monde, c 'est que tout Ie monde n'y a pas suffisamment rejiechi. 1

In the first twenty years of this century with the contribution, among others, of David Hilbert (1862-1943), Maurice Frechet (1878-1973), Felix Hausdorff (1869-1942), Pavel Alexandroff (1896-1982) and Pavel Urysohn (1898-1924), the fundamental role of the notion of an open set in the study of continuity was made clear, and general topology was developed as the study of the properties of geometrical figures that are invariant with respect to homeomorphisms, thus linking back to Euler who, in 1739, had solved the famous problem of Konigsberg's bridges with a topological method. There are innumerable successive applications, so much so that continuity and the structures related to it have become one of the most pervasive languages of mathematics. In this chapter and in the next, we shall discuss topological notions and continuity in the context of metric spaces.

5.1 Metric Spaces 5.1.1 Basic definitions a. Metrics 5.1 Definition. Let X be a set. A distance or metric on X is a map d : X x X -+ lR.+ for which the following conditions hold: (i) (IDENTITY) d(x,y) > 0 if x -=1= y E X, and d(x, x) = 0 "Ix E X. (ii) (SYMMETRY) d(x, y) = d(y, x) "Ix, y EX. (iii) (TRIANGLE INEQUALITY) d(x, y) :s: d(x, z) + d(z, y), V x, y, z E X. A metric space is a set X with a distance d. Formally we say that (X, d) is a metric space if X is a set and d is a distance on X.

The properties (i), (ii) and (iii) are often called metric axioms.

1

The analysis situs in more than three dimensions presents enormous difficulties; in order to overcome them one has to be strongly convinced of the extreme importance of this science. If its importance is not well understood by everyone, it is because they have not sufficiently thought about it.

152

5. Metric Spaces and Continuous Functions

A

B Figure 5.2. Time as distance.

5.2 Example. The Euclidean distance d(x, y) := Ix - yl, x, y E JR, is a distance on JR. On JR2 and JR3 distances are defined by the Euclidean distance, given for n = 2,3 by n

dE(x,y):=

{

~(Xi - Yi)2

} 1/2

,

where x := (Xl, X2), Y := (Y1, Y2) if n = 2, or x := (Xl, X2, X3), Y := (Y1, Y2, Y3) if n = 3. In other words, JR, JR2, JR3 are metric spaces with the Euclidean distance. 5.3 Example. Imagine JR3 as a union of strips ~n:= {(X1,X2,X3) In ~ X3 < n + I}, made by materials of different indices of refractions Vn. The time teA, B) needed for a light ray to go from A to B in JR3 defines a distance on JR3, see Figure 5.2. 5.4 Example. In the infinite cylinder C = {(x, Y, z) I x 2 + y 2 = I} C JR3, we may define a distance between two points P and Q as the minimal length of the line on C, or geodesic, connecting P and Q. Observe that we can always cut the cylinder along a directrix in such a way that the curve is not touched. If we unfold the cut cylinder to a plane, the distance between P and Q is the Euclidean distance of the two image points. 5.5~. Of course lOOlx - yl is also a distance on JR, only the scale factor has changed. More generally, if I: JR -> JR is an injective map, then d(x,y) := I/(x) - l(y)1 is again a distance on IR.

5.6 Definition. Let (X, d) be a metric space. The open ball or spherical open neighborhood centered at Xo E X of radius p > 0 is the set

B(xo, p)

:=

{x

E

X I d(x, xo) < p}.

Figure 5.3. Metrics on a cylinder and on the boundary of a cube.

5.1 Metric Spaces

153

Notice the strict inequality in the definition of B(x,r). In~, ~2, ~3 with the Euclidean metric, B(xo, r) is respectively, the open interval ]xor, Xo + r[, the open disc of center Xo E ~2 and radius r > 0, and the ball bounded by the sphere of ~3 of center Xo E ~3 and radius r > O. We say that a subset E C X of a metric space is bounded if it is contained in some open ball. The diameter of E C X is given by diamE := su p { d(x, y) I x,

YE E},

and, trivially, E is bounded iff diam E < +00. Despite the suggestive language, the open balls of a metric space need not be either round nor convex; however they have some of the usual properties of discs in ~2. For instance B(xo, r) C B(xo, s) Vxo E X and 0 < r < s, Ur>oB(xo,r) = X Vxo E X, nr>oB(xo, r) = {xo} Vxo E X, Vxo E X and Vz E B(xo, r) the open ball centered at z and radius p := r - d(xo, z) > 0 is contained in B(xo, r), (v) for every couple of balls B(x,r) and B(y,s) with a nonvoid intersection and Vz E B(x,r) n B(y,s), there exists t > 0 such that B(z, t) C B(x, r) n B(y, s), in fact t := min(r - d(x, z), s - d(y, z)), (vi) for every x, y E X with x i= y the balls B(x, rd and B(y, r2) are disjoint if rl + r2 S d(x, y).

(i) (ii) (iii) (iv)

5.7 -,r. Prove the previous claims. Notice how essential the strict inequality in the definition of B(xo, p) is.

b. Convergence A distance d on a set X allow us to define the notion of convergent sequence in X in a natural way. 5.8 Definition. Let (X, d) be a metric space. We say that the sequence {x n } C X converges to x E X, and we write X n -+ x, if d(xn,x) -+ 0 in ~, that is , if for any r > 0 there exists n such that d( x n , x) < r for all

n? n.

The metric axioms at once yield that the basic facts we know for limits of sequences of real numbers also hold for limits of sequences in an arbitrary metric space. We have (i) the limit of a sequence {x n } is unique, if it exists, (ii) if {x n } converges, then {x n } is bounded, (iii) computing the limit of {x n } consists in having a candidate x E X and then showing that the sequence of nonnegative real numbers { d( x n , x)} converges to zero, (iv) if X n -+ x, then any subsequence of {x n } has the same limit x.

154

5. Metric Spaces and Continuous Functions

Thus, the choice of a distance on a given set X suffices to pass to the limit in X (in the sense specified by the metric d). However, given a set X, there is no distance on X that is reasonably absolute (even in IR), but we may consider different distances in X. The corresponding convergences have different meanings and can be suited to treat specific problems. They all use the same general language, but the exact meaning of what convergence means is hidden in the definition of the distance. This flexibility makes the language of metric spaces useful in a large context.

5.1.2 Examples of metric spaces Relevant examples of distances are provided by linear vector spaces on the fields OC = IR or C in which we have defined a norm.

5.9 Definition. Let X be a linear space over OC = IR or C. A norm on X is a function II II : X ----+ IR+ satisfying the following properties

Vx X. Ilxll = 0 if and only if x = O. IIAxl1 IAlllxl1 Vx E X, VA E OC. (iv) Ilx + yll ::; Ilxll + Ilyll Vx, y E X. If 11·11 is a norm on X, we say that (X, II II) is a linear normed space or simply that X is a normed space with norm II II. Let X be a linear space with norm II II. It is easy to show that the (i) (ii) (iii)

Ilxll Ilxll

(FINITENESS) E IR E (IDENTITY) ~ 0 and (I-HOMOGENEITY) = (TRIANGLE INEQUALITY)

function d : X x X

----+

IR+ given by

d(x, y) :=

Ilx - yll,

x,yEX,

satisfies the metric axioms, hence defines a distance on X, called the natural distance in the normed space (X, II II). Obviously, such a distance is translation invariant, i.e., d(x + z, Y + z) = d(x, y) Vx, y, z E X. Trivial examples of metric spaces are provided by the nonempty subsets of a metric space. If A is a subset of a metric space (X, d), then the restriction of d to A x A is trivially, a distance on A. We say that A is a metric space with the induced distance from X. 5.10~. For instance, the cylinder C := {(x, y, z) E ]R31 x 2 + y2 = I} is a metric space with the Euclidean distance that, for x,y E C, yields d(x,y) :=length of the chord joining x and y. The geodesic distance d g of Example 5.4, that is the length of the shortest path in C between x and y, defines another distance. C with the geodesic distance d g has to be considered as another metric space different from C with the Euclidean distance. A simple calculation shows that 1r

Ilx-yll:S: dg(x,y):S: "2llx-yll.

We shall now illustrate a few examples of metric spaces.

5.1 Metric Spaces

155

Figure 5.4. The ball centered at (0,0) of radius 1 in JR2 respectively, for the metrics d1, dl.3, d2 and d7. The unit ball centered at (0,0) of radius one for the metric doc is the square] - 1, l[x] - 1,1[.

a. Metrics on finite-dimensional vector spaces 5.11'. As we have already seen, JRn with the Euclidean distance Ix - yl is a metric space. More generally, any Euclidean or Hermitian vector space X is a normed space with norm given by Ilxll := J(xlx) cf. Chapter 3. X is therefore a metric space with the induced distance

d(x,y):= Ilx - yll, called the Euclidean distance of X. 5.12 , oo-distance. Set for x = (Xl, X2, .. . , Xn) E JRn

Ilxll oc := max(l x 11, IX21,···, Ixnl). Show that X --> Ilxlloc is a norm on JRn. Hence, JRn, equipped with the distance doc(x,y) := Ilx - ylloc, is a metric space different from the standard JRn with the Euclidean distance of Exercise 5.11. In JR 2 , the unit ball centered at (0,0) of radius one for the metric doc is the square] - 1, l[x] - 1,1[, see Figure 5.4.

5.13' p-distance. Given a real number P 2: 1, we set for x E JRn n

Ilxll p := (:ElxiI P )

1/ p.

i=l

Show that Ilxll p is a norm on JR n , hence dp(x, y) := Ilx - yllp is a distance on JRn. Observe that II 112 and d2 are the Euclidean norm and distance in JRn. In JR2, the unit ball centered at (0,0) of radius one for the metric dp for some values of p is shown in Figure 5.4. [Hint: The triangle inequality for the p-norm is called Minkowski's discrete inequality

156

5. Metric Spaces and Continuous Functions

which follows for instance from Minkowski's inequality for integral norms, see [GM1]. Alternatively, we can proceed as follows. Suppose a and b are nonzero, otherwise the inequality is trivial, apply the convexity inequality f(>'x+(l->')y) :'S >'f(x)+(l->')f(y) to f(t) = t P with x := a;/lla[[p, y := b;/llb[[p, >. := Iiallp/(Ilalip + [[blip), and sum on i from 1 to n, to get

lI a + bllp <1.] Iialip + Ilbll p 5.14' Product spaces. Let (XI,d(1)), (X2,d(2)), ... (Xn,d(n)) be n metric spaces and let Y = Xl X X2 X ... X X n be the Cartesian product of Xl, ... , X n . Show that each of the functions defined on X x Y by

dp(X, y) := (2:~=1 d(i) (Xi, y;)P riP, if p { d oo (x, y) := max { d(i) (Xi, Yi) = 1, ... , n}

Ii

> 1,

for x = (xl, x 2 , ... , xn), y = (y l , y2, ... , yn) E Y, are distances on Y. Notice that if Xl = ... = X n =]R with the Euclidean distance, Y is ]Rn, then the distances dp(x,y) are just the distances in Exercises 5.13 and 5.12. Also show that if {xd C Y, Xk := (xl;, x~, . .. xi:) V'k, and x = (xl, x 2 , . .. , x n ), then the following claims are equivalent. (i) There exists p :::: 1 such that dp(Xk' x)

->

0,

(ii) dp(Xk, x) -> 0 Vp :::: 1, (iii) doo(Xk,X) -> 0 Vp:::: 1, (iv) V'i=l, ... ,ndi(x~,xi)->O. 5.15 , Discrete distance. Let X be any set. The discrete distance on X is given by

d(x, y) =

{I

o

if xi- y, if x = y.

Show that the balls for the discrete distance are

I

B(x,r) = {y E X d(x,y)

< r}

=

{~}

if r :'S 1, if r :::: 1,

and that convergent sequences with respect to the discrete distance reduce to sequences that are definitively constant.

5.16' Codes distance. Let X be a set that we think of as a set of symbols, and let X n = X X X x ... x X the space of ordered words on n symbols. Given two words x = (Xl, X2, ... , xn) and y = (Yl, Y2, ... , Yn) E X n , let

d(x, y) :=

#{ i IXi i- Yi}

be the number of bits in x and y that are different. Show that d(x, y) defines a distance in Characterize the balls of relative to that distance. [Hint: Write d(x,y) = 2:~=1 d(Xi, Yi) where d is the discrete distance in X.J

xn.

xn

5.1 Metric Spaces

157

Tl IIEllaRlE E COIIUNICAZIONL

~IATEM

CIRC LO

... .IiI .... '.. ' ... III(""")')

TICO

01 PALERMO 11llrlOOVCT10II'

.............. '_ --, • QI,,,. . . -

,.... .. _

.... --,..-,--..-1111.......

_

........ -,..,..

rAooot-.~

.......-

_

__ 11

" - " - . ..

llOlV_ _

..

,

....

Jt~(~

_

--

_~

........ .-...,•

.......1I...-, ...1I ....

_ ...... ............ ........ - - ..--...-,...,..-..0 r..

....

.)...-_

1-._

.. .....--"--..... -~"

,.. •

_,.....

ea.,-

~IIen

c..,.

_ , - ...

-

,....,.

__

__

'n.._""f_ .....

.......

., ........ - -

...

-

_ _ I ..........

-" _~( ............. _...... _ r.,. .. c-.. _4

Gucer"

TOMO XXIt

..-

....--

--.~._-_

(It

DanTDn G •

..-.

1fI'I_

&.0_

...-e.-

,_J- •

-...

-..

-

~·-

....-.

__ -)

U q(4l.a_ "--of;

1

PALEawo, UQ, DIU" fOcurA

---.... ..

""'--

_"'-,,~

-'''--

.....

Figure 5.5. The first page of the These at the Faculty of Sciences of Paris by Maurice Frechet (1878-1973), published on the Rendiconti del Circolo Matematico di Palermo.

b. Metrics on spaces of sequences We now introduce some distances and norms on infinite-dimensional vector spaces. 5.11 Example (£00 space). Consider the space of all real (or complex) sequences x:= (Xl, ... ). For x = {x n }, y:= {Yn}, set

IIxlloo := sup n

Ixnl,

doo(x, y) := Ilx - ylloo.

It is easy to show that X -+ IIxlioo satisfies the axioms of a norm apart from the fact that it may take the value +00. Thus X -+ Ilxlioo is a norm in the space

£00 :=

{x = {Xn} 111x ll 00 < +oo},

that is, on the linear vector space of bounded sequences. Consequently,

is a distance on £00' called the uniform distance. Convergence of {xd in the uniform norm, called the uniform convergence, amounts to

IIxk - xll oo = sup Ixi.: i

xii

-+

0

as k

-+

c

£00 to x E £00 (5.1)

00,

where Xk = (xL x~, ... ) and x = (xl, x2 , ... ). Notice that the uniform convergence in (5.1) is stronger than the pointwise convergence as k For instance, let t.p(t)

:=

-+ 00.

te- t , t E R+, and consider the sequence of sequences {xd

where Xi:= {xi}n, xi:= t.p(~). Then Vi we have xi.: = ie-ilk

I

i )k i = 0,1,... Ilxk - 01100 = sup { ,/-'

}=

-+

0 as k

~1 '" O.

-+

00, while

158

5. Metric Spaces and Continuous Functions

Of course JRn with the metric d oo in Exercise 5.12 is a subset of f. oo endowed with the induced metric d oo . This follows from the identification (x1, ... ,x n )

(x1, ... ,xn,O, ... ,O, ... ).

+-+

5.18 Example (f.p spaces, p 2: 1). Consider the space of all real (or complex) sequences x:= (Xl, ... ). For 1 ::; p::; 00, x = {x n } and y:= {Yn} set

Trivially, IIxllip = 0 if and only if any element of the sequence x is zero, moreover Minkowski's inequality holds as it follows from Exercise 5.13 (passing to the limit as n -+ 00 in Minkowski's inequality in JRn). Thus II Ili p satisfies the metric axioms apart from the fact that it may take the value +00. Hence, II 1lip is a norm in the linear space of sequences f. p :=

{x =

{x n } IlIxllip

< +oo}.

Consequently, dip(X,y) := IIx - yllip is a distance on f. p . Convergence of {Xk} C f. p to x E f. p amounts to 00

L 14 - xil

P -+

0

as k

-+ 00,

i=l

where Xk = (xLx~, ... ) and x = (x l ,x 2 , ... ). Notice that JRn with the metric dp in Exercise 5.13 is a subset of f. p endowed with the induced metric dip' This follows for instance from the identification

Finally, observe that IIxlliq ::; Ilxllip Yx if 1::; P ::; q, hence

Since there exist sequences x = {x n } such that Ilxlliq < q, as for instance

<

+00

while Ilxllip =

+00

if

P

._ {~}l/P ,

X.-

n

the inclusions (5.2) are strict if 1 < P < q. The case p = 2 is particularly relevant since the f.2 norm is induced by the scalar product 00

(XIY)i2 := Lxiyi, i=l

f.2

is called the Hilbert coordinate space, and the set

the Hilbert cube.

5.1 Metric Spaces

159

I

Figure

5.6. Tubular neighborhood of the graph of I.

c. Metrics on spaces of functions The language of metric spaces is particularly relevant in dealing with different types of convergences of functions. As examples of metric spaces of functions, we then introduce a few normed spaces that are relevant in the sequel. 5.19 Example (Continuous functions). Denote by CO([O, 1]) the space of all continuous functions I : [O,IJ -+ JR.. For I : [0,1] -+ JR. set

11/1100,[0,1]:= sup I/(x)l· XE[O,l)

We have (i) 11/1100,[0,lJ

< +00 by Weierstrass's theorem, (ii) 11f1100,[0,l) = a iff I(x) = a "Ix, (iii) IIA 11100,[0,1) = IAlll/lloo,[o,l], (iv) III + glloo,[o,l) ::; 11/1100,[0,1) + Ilglloo,[o,l]' To prove (iv) for instance, observe that for all x E [0,1], we have I/(x)

+ g(x)1 ::; I/(x)1 + Ig(x)1 ::; 11/1100,[0,1] + Ilglloo,[o,l]

hence the right-hand side is an upperbound for the values of I + g. The map I -+ 11/1100,[0,1] is then a norm on CO([O, 1]), called the unilorm or infinity norm. Consequently CO ([0, 1]) is a normed space and a metric space with the unilorm distance

I,g E CO([O, 1]).

doo(f,g) := III - glloo [0 1] = max I/(t) - g(t)l, "

tE[O,l]

I

In this space, the ball B(f, €) of center functions 9 E CO([O, 1]) such that

Ig(x) - l(x)1

and radius € >

<€

a is the

set of all continuous

V x E [O,IJ

or the family of all continuous functions with graphs in the tubular neighborhood of radius € of the graph of I

U(f, €) := {(x, y) I x E [0,1], y E JR.,

Iy -

l(x)1

< €},

(5.3)

see Figure 5.6. The unilorm convergence in CO ([0, 1]), that is the convergence in the uniform norm, of Ud c CO([O, 1]) to I E CO([O, 1]) amounts to computing Mk

:= IIIk - 11100 [0 1J = max IIk(t) - l(t)1 "

for every k = 1,2, ... and to showing that Mk

tEIO,l) -+

a as

k

-+

+00.

160

5. Metric Spaces and Continuous Functions

k

-1

Figure 5.7. The function Ik in (5.4).

5.20 Example (Functions of class C 1 ([0, 1])). Denote by C 1 ([0, 1]) the space of all functions f: [0, 1] ~ lR of class Cr, see [GMl]. For f E C 1 ([0, 1]), set IlfIIC1([0,1]):=

+

sup [f(x)[ xE[O,l]

sup If'(x)! = Ilfl[oo,[o,l]

+ [If'IIoo,[o,l]'

xE[O,l]

It is easy to check that f ~ IIfII C 1([0,1]) is a norm in the vector space C1([0, 1]). Consequently, d C 1([0,1])(f,g):= Ilf - gl ([0,1])

Icr

defines a distance in C 1 ([0,1]). In this case, a function 9 E C 1 has a distance less than I" from f if Ilf - glloo,[o,lJ + IIf' - g'IIoo,[o,l] < 1"; equivalently, if the graph of 9 is in the tubular neighborhood U(f, q) of the graph of f, and the graph of g' is in the tubular neighborhood U(f', 1"2) of f' with q + 1"2 = 1", see (5.3). Moreover, convergence in the C1([0, 1])-norm of Ud c C 1([0, 1]) to f E C1([0, 1]), [Ifk - fIIC1([0,1]) ~ 0, amounts to

fk ~f { f~ ~f'

uniformly in [0,1], uniformly in [O,IJ.

Figures 5.8 and 5.9 show graphs of Lipschitz functions and functions of class C1 ([0, 1]) that are closer and closer to zero in the uniform norm, but with uniform norm of the derivatives larger than one.

5.21 Example (Integral metrics). Another norm and corresponding distance in CO ([0, 1]) is given by the distance in the mean

1

1

1

IIfl[L1([0,1]) :=

[f(t)[ dt,

d L 1([0,1])(f,g):= [1f-gllL1(0,1):= ![f-gl dX .

° 5.22 ~. Show that the L1- norm in CO ([0, 1]) satisfies the norm axioms. Convergence with respect to the L 1 -distance differs from the uniform one. For instance, for k = 1, 2, . .. set

Ik(x) =

{-ka

3

(IX I -

-b)

< -b, -b ::; Ixl < 1.

if 0< Ixl if

(5.4)

We have IIlklloo,[o,lj = 1(0) = k ~ +00 while IllkIIL1([0,1]) = 1/(2k) ~ 0, cf. Figure 5.7. More generally, the LP([O, 1])-norm, 1 ::; p < 00, on CO([O, 1]), is defined by

5.1 Metric Spaces

161

Figure 5.8. The Lebesgue example.

rl

11/[[LP(o,l):= ( Jo I/(x)[P dx

1---> 1[/IILP(o,l)

It turns out that

) lip

.

satisfies the axioms of a norm, hence lip

1

d LP ([o,1])(I, g) :=

III -

gliLv([o,l]) :=

(! II -

glP dx )

°

is a distance in CO([O, 1]); it is called the U([O, 1])-distance. 5.23'. Show that the LP([O, 1])-norm in CO([O, 1]) satisfies the norm axioms. [Hint: The triangle inequality is in fact Minkowski's inequality, see [GMl].]

5.1.3 Continuity and limits in metric spaces a. Lipschitz-continuous maps between metric spaces 5.24 Definition. Let (X, d x ) and (Y, dy ) be two metric spaces and let o < a :::; 1. We say that a junction f : X ----+ Y is a-Halder-continuous ij there exists L > 0 such that

dy(l(x),j(y)):::; Ldx(x,y)O:,

't/ x,yEX.

(5.5)

I-Holder-continuous junctions are also called Lipschitz continuous. The smallest constant L jor which (5.5) holds is called the a-Holder constant of f, often denoted by [f]o:. When a = 1, the I-Holder constant is also called the Lipschitz constant oj f and denoted by [f] 1, Lip f or Lip (I). 5.25 Example (The distance function). Let (X, d) be a metric space. For any xo E X, the function I(x) := d(x,xo) : X ---> lR is a Lipschitz-continuous function with Lip (I) = 1. In fact, from the triangle inequality, we get

I/(y) - I(x)[ = Id(y, xo) - d(x, xo)1 hence

I is Lipschitz continuous with Lip (I)

s d(x, y)

'tx,y E X,

s 1. Choosing x =

Xo, we have

I/(y) - l(xo)1 = Id(y, xo) - d(xo, xo)[ = dey, xo), thus Lip (I)

~

1.

162

5. Metric Spaces and Continuous Functions

Figure 5.9. On the left, the sequence A(x) := k- 1 cos(kx) that converges uniformly to zero with slopes equibounded by one. On the right, 9k(X) := k- 1 cos(k 2 x), that converges uniformly to zero, but with slopes that diverge to infinity. Given any function fECI ([0,1]), a similar phenomenon occurs for the sequences A(x) := f(kx)/k, 9k(X) = f(k 2 x)/k.

5.26 , Distance from a set. Let (X, d) be a metric space. The distance function from x E X to a nonempty subset A C X is defined by d(x, A) := inf{ d(x, y)

It is easy to show that f(x) := d(x, A) : X Lip (f) =

{o 1

-->

lYE A}.

lR is a Lipschitz-continuous function with

if d(x, A) = otherwise.

°

Vx,

If d(x, A) is identically zero, then the claim is trivial. On the other hand, for any x, y E X and z E A we have d(x, z) ~ d(x, y) + dey, z) hence, taking the infimum in z,

d(x, A) - dey, A) ~ d(x, y)

and interchanging x and y, Id(x, A) - dey, A)I ~ d(x, y),

that is, x --> d(x, A) is Lipschitz continuous with Lipschitz constant less than one. Since there exists a x ¢ A such that d(x, A) > 0, there exists a sequence {Zn} C A such that d(x,zn) 1 + ;;;. 1 Th ~ d(x,A) < erelore, Id(x, A) - d(x n , A)I = d(x, A) ~ n

from which we infer that the Lipschitz constant of x than one.

n

+ 1 d(x, Xn), -->

d(x, A) must not be smaller

b. Continuous maps in metric spaces The notion of continuity that we introduced in [GMl], [GM2] for functions on one real variable can be extended in the context of the abstract metric structure. In fact, by paraphrasing the definition of continuity of functions f : IR - t 1R+ we get

5.1 Metric Spaces

163

5.27 Definition. Let (X, d x ) and (Y, dy ) be two metric spaces. We say that f : X --+ Y is continuous at Xo if ' 0 there exists 5 > 0 such that dy(f(x),f(xo)) < f whenever dx(x,xo) < 5, i.e.,

' 0 :35> 0 such that f(Bx(xo, 5))

C By(f(xo), f).

(5.6)

We say that f : X ---> Y is continuous in E C X if f is continuous at every point Xo E E. When E = X and f : X --+ Y is continuous at any point of X, we simply say that f : X --+ Y is continuous. 5.28 'If. Show that a-Holder-continuous functions, 0 < a ~ 1, in particular Lipschitzcontinuous functions, between two metric spaces are continuous.

Let (X, d x ) and (Y, dy) be two metric spaces and E C X. Since E is a metric space with the induced distance of X, Definition 5.27 also applies to the function f : E ---> Y. Thus f : E --+ Y is continuous at Xo E E if

' 0 :35 > 0 such that f(Bx(xo, 5) n E) c By(f(xo), f) and we say that f any point Xo E E.

:E

--+

Y is continuous if

f :E

--+

(5.7)

Y is continuous at

5.29 Remark. As in the case of functions of one real variable, the domain of the function f is relevant in order to decide if f is continuous or not. For instance, f : X ---> Y is continuous in E C X if ' 0 :35> 0 such that f(Bx(xo, 5)) C By(f(xo), f), while the restriction fiE: E

--->

(5.8)

Y of f to E is continuous in E if

' 0 :35 > 0 such that f(Bx(xo, 5) n E) c By(f(xo), f). (5.9) We deduce that the restriction property holds: if f : X --+ Y is continuous in E, then its restriction fiE: E --+ Y to E is continuous. The opposite is in general false, as simple examples show.

5.30 Proposition. Let X, Y, Z be three metric spaces, and Xo EX. If f : X ---> Y is continuous at Xo and 9 : Y --+ Z is continuous at f (xo), then 9 0 f : X ---> Z is continuous at xo. In particular, the composition of two continuous functions is continuous. Proof. Let t > O. Since 9 is continuous at f(xo), there exists a > 0 such that g(By(f(xo),a)) C Bz(g(f(xo)),t). Since f is continuous at xo, there exists 8 > 0 such that f(B x (xo,8)) C By(f(xo), a), consequently go f(B x (xo, 8)) C g(By (f(xo), a)) C Bz(g

0

f(xo), t).

o Continuity can be expressed in terms of convergent sequences. As in the proof of Theorem 2.46 of [GM2], one shows

5.31 Theorem. Let (X, dx) and (Y, d y ) be two metric spaces. f : X --+ Y is continuous at Xo E X if and only if f(x n ) ---> f(xo) in (Y, d y ) whenever {x n } C X, Xn --+ Xo in (X,d x ).

164

5. Metric Spaces and Continuous Functions

c. Limits in metric spaces Related to the notion of continuity is the notion of the limit. Again, we want to rephrase f (x) ----. Yo as x ----. xo. For that we need f to be defined near xo, but not necessarily at xo. For this purpose we introduce the 5.32 Definition. Let X be a metric space and A eX. We say that Xo E X is an accumulation point of A if each ball centered at Xo contains at least one point of A distinct from xo,

Vr > 0 B(xo,r) nA \ {xo} I- 0. Accumulation points are also called cluster points. 5.33'. Consider R with the Euclidean metric. Show that (i) the set of points of accumulation of A :=]a, b[, B = [a, b], C = [a, b[ is the closed interval [a, b], (ii) the set of points of accumulation of A :=]0, 1[U{2}, B = [0, 1JU{2}, C = [0,1[U{2} is the closed interval [0, 1], (iii) the set of points of accumulation of the rational numbers and of the irrational numbers is the whole R.

We shall return to this notion, but for the moment the definition suffices.

5.34 Definition. Let (X, d x ) and (Y, dy ) be two metric spaces, let E C X and let Xo E X be a point of accumulation of E. Given f : E \ {xo} ----. Y, we say that Yo E Y is the limit of f(x) as x ----. Xo, x E E, and we write f (x) ----. Yo as x ----. Xo,

or

lim f(x)

X-XQ

= Yo

xEE

if for any E > 0 there exists 15 > 0 such that dy(J(x), Yo) < x E E and 0 < dx(x, xo) < 15. Equivalently,

E

whenever

VE > 0:315 > 0 such that f(Bx(xo, 15) nE\ {xo}) C By(yo, E). Notice that, while in order to deal with the continuity of f at Xo we only need f to be defined at Xo; when we deal with the notion of limit we only need that Xo be a point of accumulation of E. These two requirements are unrelated, since not all points of E are points of accumulation and not all points of accumulation of E are in E, see, e.g., Exercise 5.33. Moreover, the condition 0 < dx(x, xo) in the definition of limit expresses the fact that we can disregard the value of fat Xo (in case f is defined at xo). Also notice that the limit is unique if it exists, and that limits are preserved by restriction. To be precise, we have

5.35 Proposition. Let (X, d x ) and (Y, dy ) be two metric spaces. Suppose FeE c X and let Xo E X be a point of accumulation for F. If f(x) ----. y as x ----. Xo, x E E, then f(x) ----. y as x ----. Xo, x E F. 5.36'. As for functions of one variable, the notions of limit and continuity are strongly related. Show the following.

5.1 Metric Spaces

165

Proposition. Let X and Y be two metric spaces, E C X and xo EX. (i) If Xo belongs to E and is not a point of accumulation of E, then every function f : E -+ Y is continuous at xo. (ii) Suppose that xo belongs to E and is a point of accumulation for E. Then a) f : E -+ Y is continuous at Xo if and only if f(x) -+ f(xo) as x -+ xo, xE E, b) f(x) -+ y as x -+ XO, x E E, if and only if the function g : E U {xo} -+ Y defined by g(x) := {yf(X)

if x E E \ {xo}, if x = xo

is continuous at xo.

We conclude with a change of variable theorem for limits, see e.g., Proposition 2.27 of [GMl] and Example 2.49 of [GM2]. 5.37 Proposition. Let X, Y, Z be metric spaces, E C X and let Xo be a point of accumulation for E. Let f : E -+ Y, 9 : f(E) -+ Z be two functions and suppose that f(xo) is an accumulation point of f(E). If

(i) g(y) -+ L as y -+ Yo, Y E f(E), (ii) f(x) -+ Yo as x -+ XO, x E E, (iii) either f(xo) = Yo, or f(x) -j. Yo for all x then g(f(x))

-+

L as x

-+

E E and x

-j. xo,

Xo, x E E.

d. The junction property A property we have just hinted at in the case of real functions is the junction property, see Section 2.1.2 of [GMl], which is more significant for functions of several variables. Let X be a set. We say that a family {Uo:} of subsets of a metric space is locally finite at a point Xo E X if there exists r > 0 such that B(xo, r) meets at most a finite number of the U0: 'so 5.38 Proposition. Let (X, d x ), (Y, dy) be metric spaces, f : X -+ Y a function, Xo EX, and let {Uo:} be a family of subsets of X locally finite at Xo·

(i) Suppose that Xo is a point of accumulation of Uo: and that f(x) -+ y as x -+ XO, x E uo:, for all 0:. Then f(x) -+ y as x -+ XO, x E X. (ii) If Xo E no:uo: and f : Uo: C X -+ Y is continuous at Xo for all 0:, then f : X -+ Y is continuous at Xo. 5.39'. Prove Proposition 5.38. 5.40 Example. An assumption on the covering is necessary in order that the conclusions of Proposition 5.38 hold. Set A := {(x, y) I x 2 < Y <,2x 2 } C ]R2 and

f(x,y):=

{I

o

if (x,y) E A, otherwise.

166

5. Metric Spaces and Continuous Functions

The function f is discontinuous at XQ := (0,0), since its oscillation is one in every ball centered at XQ. Denote by Um the straight line through the origin

Um := {(x,y) Iy = mx},

Uoo := {(x, y) I x = O}.

mE JR,

The Un'S, Q E lR U {oo} form a covering of JR2 that is not locally finite at XQ and for any Q E JR U 00, the restriction of f to each Un is zero near the origin. In particular, each restricition flu n : Un ----; JR is continuous at the origin.

5.1.4 Functions from IRn into IRm It is important to be acquainted with the limit notion we have just introduced in an abstract context. For this purpose, in this section, we shall focus on mappings between Euclidean spaces and illustrate with a few examples some of the abstract notions previously introduced.

a. The vector space CO (A, jRnt) Denote by ei : jRn -> jR the linear map that maps x = (xl, x 2, ... , Xn ) E jRn into its ith component, ei(x) := Xi. Any map f : X -7 jRn from a set X into jRn writes as an n-tuple of real-valued functions f(x) = (P(x), r(x)), where for any i = 1, ... , n the function fi : X -7 jR is given by fi(x) := ei(f(x)). From 00"

n

IYII,IY21,oo·,!Ynl::; Iyl::; LIYi!

Y E jRn

i=l

we readily infer the following.

5.41 Proposition. The following claims hold.

(i) The maps e i : jRn -7 jR, i = 1, ... , n, are Lipschitz continuous. (ii) Let (X, d) be a metric space. Then a) f : X -7 IRn is continuous at Xo E X if and only if all its components fl, f2, ... , fn are continuous at xo, b) if f,g: X -7 IRn are continuous at xo, then f + g: X -7 IRn is continuous at xo, c) if f : X -7 IRn and A : X -7 IR are continuous at Xo then the map Af : X -7 IRn defined by Af(x) := A(x)f(x), is continuous at xo. 5.42 Example. The function f : JR3 ----; JR, f(x, y, x) := sin(x 2y) + x 2 is continuous at JR3. In fact, ifxQ:= (xQ,YQ,zQ), then the coordinate functions x = (x,y,lZ) ----; x, x ----; y, x ----; Z are continuous at XQ by Proposition 5.41. By Proposition 5.41 (iii), x ----; x 2 y and x ----; z2 are continuous at XQ, and by (ii) Proposition 5.41, x ----; x 2 y + z2 is continuous at XQ. Finally sin(x 2 y + x 2 ) is continuous since sin is continuous.

5.43 Definition. Let X and Y be two metric spaces. We denote by CO(X, Y) the class of all continuous function f : X -7 Y.

5.1 Metric Spaces

167

As a consequence of Proposition 5.41 CO (X, jRm) is a vector space. Moreover, if A E CO(X, jR) and f E CO(X, jRm), then Af : X ~ jRn given by Af(x) := A(x)f(x), x E X, belongs to cO(X,jRm). In particular,

5.44 Corollary. Polynomials in n variables belong to CO (jRn , jR). Therefore, maps f : jRn ~ jRm whose components are polynomials of n variables are continuous. In particular, linear maps L E £(jRn, jRm) are continuous. It is worth noticing that in fact

5.45 Proposition. Let L : jRn tinuous in jRn.

~

jRm be linear. Then L is Lipschitz con-

Proof. As L is linear, we have Lip(J) : =

sup [[L(x) - L(Y)[[JR'" x,yElRn Ilx - YllJRn x'!y

=

IIL(x - y)IIJR'" = sup IIL(z)IIJR'" =: [[LII. Ilx - YllJRn O#EJRn IlzIIJRn

sup x,yElR n

x'!y

Let us prove that jlLl1 < +00. Since L is continuous at zero by Corollary 5.44, there exists 8 > 0 such that IIL(w)[[ < 1 whenever Ilwll < 8. For any nonzero z E lR n , set w := 2 Since Ilw[1 < 8, we have [IL(w)[[ < 1. Therefore, writing z = 211zl1 wand using the linearity of L

f,=w

IIL(z)[[

=

1121~zll L(w)11 = 21~zIIIIL(w)11 < ~ Ilzll

hence IIL[[

2

:s; ;5 < +00. o

For a more detailed description of linear maps in normed spaces, see Chapters 9 and 10.

b. Some nonlinear continuous transformations from jRn into jRN We now present a few examples of nonlinear continuous transformations between Euclidean spaces. 5.46 Example. For k = 0,1, ... consider the map

Uk () t

=

(cos kt, sin kt) { (1,0)

Uk : ] -

1,1[---> lR2 given by

if t E]O, 21l"/k[, otherwise.

This is a Lipschitz function whose graph is given in Figure 5.10. Notice that the graph of Uk = {(t, Uk (t))} is a curve that "converges" as k ---> 00 to a horizontal line plus a vertical circle at O. Compare with the function sgn x from lR to R

168

5. Metric Spaces and Continuous Functions

y

21r/k

Figure S.10. The function

Uk

in Example 5.46.

5.47 Example (Stereographic projection). Let

sn := { X E

jRn+1 Ilxl = 1}

be the unit sphere in jRn+ 1. If x = (Xl, xn , xn + 1) E jRn+ 1 , let us denote the coordinates of x by (y, z) where y = (Xl, X2, , x n ) E jRn and z = X n +1 E R With this notation, sn = {(y, z) E jRn x jR IIyl2 + z2 = I}. Furthermore, denote by Ps = (0, -1) E sn the South pole of sn. The stereographic projection (from the South pole) is the map that projects from the South pole the sphere onto the {z = O} plane, (7:

Sn \ iPs} C

JRn+1 -+ jRn,

(y,z)

-+

-y-. l+z

It is easily seen that (7 is injective, surjective and continuous with a continuous inverse given by (7-1: jRn -+

Sn \ iPs},

(7

-1

(x):=

(2 1-lxI2) 1 + Ixl 2x , 1 + Ixl 2

that maps x E jRn into the point of sn lying in the segment joining the South pole of sn with x, see Figure 5.11.

5.48 Example (Polar coordinates). The transformation (7: 2;:=

I

{(p,B) p

> 0,

0 -:;

B < 21r}

(p,B)

-+ jR2,

-+

(pcosB,psinB)

defines a map that is injective and continuous with range jR2 \ {O}. The extension of the map to the third coordinate (j: 2; X jR -+ jR2 X jR,..., jR3,

(p,B,z)

-+

(pcosB,psinB,z)

defines the so-called cylindrical coordinates in jR3.

5.49 Example (Spherical coordinates). The representation of points (x, y, z) E jR3 as X = psin
z=pcos
see Figure 5.12, defines the spherical coordinates in jR3. This in turn defines a continuous transformation (p, B,
> 0,0 -:; B < 21r, 0 -:;