(ii) Suppose that ± : Rm ’ Rp is a linear map and that its matrix with

respect to the standard basis is A = (aij ). Show how ± might be calculated.

(If you know about Lagrange multipliers this gives you an opportunity to

apply them.)

We discuss this problem further in Exercises K.99 to K.101.

Exercise K.99. [6.2, T] A linear map ± : Rm ’ Rm is called symmetric if

±(x), y = x, ±(y)

for all x, y ∈ Rm . Show that ± : Rm ’ Rm is symmetric if and only if its

matrix (aij ) with respect to the standard bases is symmetric, that is aij = aji

for all i and j.

In algebra courses (and, indeed, in Exercise K.30) it is shown that the

linear map ± : Rm ’ Rm is symmetric if and only if it has m orthonormal

eigenvectors. Show that a symmetric linear map ± : Rm ’ Rm has operator

norm equal to the largest absolute value of its eigenvalues, that is to say,

± = max{|»| : » an eigenvalue of ±}. (†)

By considering the linear map ± : R2 ’ R2 with matrix

01

A= ,

00

or otherwise, show that the equality (†) may fail if ± is not symmetric.

482 A COMPANION TO ANALYSIS

Exercise K.100. [6.2, T, ‘ ] Question K.99 tells us that the operator norm

of a symmetric linear map ± : Rm ’ Rm is the largest absolute value of its

eigenvalues but does not tell us how to ¬nd this value.

(i) Our ¬rst thought might be to look at the roots of the characteris-

tic polynomial. Examine the kind of calculations involved when m = 50.

(Actually matters are even worse than they look at ¬rst sight.)

(ii) Suppose ± has eigenvalues »j with associated orthonormal eigenvec-

tors ej . Choose an x0 ∈ V and de¬ne yk = xk ’1 xk (if xk = 0 the process

terminates) and xk+1 = ±(yk ). If »1 > |»j | [2 ¤ j ¤ m] show that, except in

a special case to be speci¬ed, the process does not terminate and

x k ’ » 1 , y k ’ e1 ’ 0

as k ’ ∞.

How must your answer be modi¬ed if ’»1 > |»j | [2 ¤ j ¤ m].

(iii) Now suppose simply that ± = 0 and |»1 | ≥ |»j | [2 ¤ j ¤ m]. Show

that it remains true that, except in a special case to be speci¬ed, the process

does not terminate and

xk ’ |»1 |.

as k ’ ∞.

If ± = 0, all the »j are positive and »1 ≥ »j [2 ¤ j ¤ m] show that,

except in a special case to be speci¬ed, the process does not terminate and

xk tends to a limit. Show that this limit is an eigenvector but (unless »1 > »j

[2 ¤ j ¤ m]) this eigenvector need not be a multiple of e1 .

(iv) We thus have an algorithm for computing the largest absolute value

of the eigenvalues of ± by applying the iterative procedure described in (ii).

The reader may raise various objections.

(a) ˜The randomly chosen x0 ∈ V may be such that the process fails.™

Suppose that V = R50 and you are use your favourite computer and your

favourite random number generator. Estimate the probability that a ran-

domly chosen x0 will be such that the process fails. Recalling that computers

use ¬nite precision arithmetic discuss the e¬ect of errors on the process.

(b) ˜We give an iterative procedure rather than an exact formula.™ Re-

member that if V = R50 we are seeking a root of a polynomial of degree 50.

How do you propose to ¬nd an exact formula for such an object?

(c) ˜We may have to make many iterations.™ Estimate the number of

operations required for each iteration if the matrix A associated with ± is

given and conclude that, unless m is very large, each iteration will be so fast

that the number of iterations hardly matters.

483

Please send corrections however trivial to twk@dpmms.cam.ac.uk

(v) The method is (usually) quite e¬ective for ¬nding the largest (abso-

lute value) of the eigenvalues. Sometimes it is less e¬ective in ¬nding the

associated eigenvector. Why should this be?

(vi) Discuss how you might go about ¬nding the second largest (absolute

value) of the eigenvalues.

(vi) Suppose that ± is a linear map ± : Cm ’ Cm whose eigenvalues

satisfy |»1 | > |»j | [2 ¤ j ¤ m]. Show that the method outlined above will

continue to work.

(vii) Let e1 and e2 be linearly independent vectors in R2 with e1 ’ e2

small. Let ± : R2 ’ R2 be the linear map such that ±e1 = e1 , ±e2 = ’e2

Set

’1

x = e 1 ’ e2 (e1 ’ e2 ).

and examine the the behaviour of ±r x.

(viii) Explain why our algorithm may fail for an ± : Cm ’ Cm whose

eigenvalues merely satisfy |»1 | ≥ |»j | [2 ¤ j ¤ m].

(vii) Explain why the method of (vii) may prove very slow even if |»1 | >

|»j | [2 ¤ j ¤ m]. Why did we not have the problem in the real symmetric

case?

Exercise K.101. [6.2, T, ‘ ] We now consider general linear maps ± :

Rm ’ Rm . In this general case mathematicians remain very interested in

¬nding the largest absolute value of its eigenvalues. (Some of the reasons

for this are set out in Exercises K.282 to K.286.) However, they are much

less interested in ¬nding ± which, as I have stressed, is mainly used as a

convenient theoretical tool.

If you really need to obtain ± , this exercise justi¬es one method of

going about it. Recall that ±— is the linear map ±— : Rm ’ Rm whose matrix

A— = (bij ) with respect to the standard bases is given by bij = aji for all i

and j (where A = (aij ) is the matrix of ± with respect to the same basis).

(i) Show that

±x, y = x, ±— y

for all x, y ∈ Rm .

(ii) Explain why

x, ±— ±x = ±x 2

for all x ∈ Rm . Deduce that

±— ± ≥ ± 2

484 A COMPANION TO ANALYSIS

and so ±— ≥ ± .

(iv) Show that, in fact, ±— = ± and

±— ± = ± 2 .

Show that ±— ± is a symmetric linear map all of whose eigenvalues are positive.

(v) Use the results of (ii) and Exercise K.100 to give a method of obtaining

±.

(vi) Estimate the number of operations required if the matrix A associated

with ± is given. What step requires the bulk of the calculations?

(vii) Find A— A in the special case

11

A= .

02

What are the eigenvalues of A and AA— ? What is A ?

Exercise K.102. [6.3, P] We work in R2 . Let

¯

B = {x : x < 1}, B = {x : x ¤ 1} and ‚B = {x : x = 1}.

¯

Suppose that f : B ’ R is a continuous function which is di¬erentiable on B.

Show that, if f (x) = 0 for all x ∈ ‚B, there exists a c ∈ B with Df (c) = 0.

¯

Construct a continuous function g : B ’ R which is di¬erentiable on B

but such that we cannot ¬nd a linear map ± : R2 ’ R such that f ’ ± is

constant on ‚B. [Hint: This is easy.]

Discuss the foregoing results in the light of Rolle™s theorem (Theorem 4.4.4)

and the proof of the one dimensional mean value theorem given in Exer-

cise 4.4.5.

Exercise K.103. [7.1, P, S] Suppose that q1 , q2 , . . . is a strictly increasing

∞ 1

sequence of strictly positive integers such that n=1 qn diverges. Show that

∞ ∞

1 1 1

log 1 ’ log 1 ’

diverges but + converges.

qn qn qn

n=1 n=1

Exercise K.104. [7.3, P] (This question has low theoretical interest but

tests your power of clear organisation.) Find the maximum of

ax2 + bx + c

on the interval [0, 10] where a, b and c are real constants.

485

Please send corrections however trivial to twk@dpmms.cam.ac.uk

Exercise K.105. (Routh™s rule.) [7.3, T] It is Routh™s misfortune to be

known chie¬‚y as the man who beat Maxwell in the Cambridge mathematics

examinations, but he was an able mathematician and teacher7 . Part (v) of

this question gives his method for determining if a real symmetric matrix

A = (aij )1¤i,j¤n is positive de¬nite.

(i) We said that A is positive de¬nite if all its eigenvalues are strictly posi-

tive. It is more usual to say that A is positive de¬nite if n n

j=1 xi aij xj > 0

i=1

for all x = 0. Show that the two de¬nitions are equivalent. [Think about

the map x ’ xT Ax (with x as a column vector).]

(ii) By choosing a particular x, show that, if A is positive de¬nite, then

a11 > 0.

(iii) If a11 = 0, show that (whether A is positive de¬nite or not)

n n n n

2

xi aij xj = a11 y1 + xi bij xj

i=1 j=1 i=2 j=2

where y1 = x1 + a’1 a12 x2 + a’1 a13 x3 + · · · + a’1 a1n xn , and

11 11 11

aij a11 ’ a1i a1j

a1i a1j

bij = aij ’ = .

a11 a11

Hence, or otherwise, show carefully that A is positive de¬nite if and only if

a11 > 0 and the matrix B = (bij )2¤i,j¤n is positive de¬nite. (Of course, we

must perform the very simple veri¬cation that B is a real symmetric matrix.)

The matrix B is called the Schur complement of a11 in A.

(iv) By considering the e¬ect of row operations of the form

[new ith row] = [old ith row] ’ ai1 a’1 [old 1st row]

11

on A, or otherwise, show that det A = a11 det B.

(v) Use (iii), ideas based on (iv) and induction on n to prove Routh™s

rule:“ The real symmetric matrix A is positive de¬nite if and only if the

determinants of the n leading minors

«

a11 a12 a13

a11 a12

, det a21 a22 a23 , . . . , det A

a11 = det(a11 ), det

a21 a22

a31 a32 a33

are all strictly positive.

(vi) Show that A is negative de¬nite if and only if ’A is positive de¬nite.

7

He was one of the two greatest Cambridge coaches (people who tried to make students

do slightly better in mathematics examinations than they should, an occupation which I

have always felt to be fairly harmless, if not terribly useful).

486 A COMPANION TO ANALYSIS

Figure K.2: Shortest road system for vertices of a square

Exercise K.106. [7.3, P] (i) Let A(t) be a 2 — 2 real symmetric matrix

with

a(t) b(t)

A(t) =

b(t) c(t)

Suppose that a, b, c : R ’ R are continuous. Show that, if A(t) has

eigenvalues »1 (t) and »2 (t) with »1 (t) ≥ »2 (t), then »1 and »2 are continuous.

Show that, if A(0) is positive de¬nite and A(1) is negative de¬nite, then there

exists an ± ∈ (0, 1) with A(±) singular. Show, more strongly, that, either

we can ¬nd ±1 and ±2 with 1 > ±1 > ±2 > 0 and A(±1 ), A(±2 ) singular, or

there exists an ± ∈ (0, 1) with A(±) the zero matrix.

(ii) State and prove a result along the lines of Exercise 7.3.19 (ii).

(iii) Find a 2 — 2 real matrix B(t) = (bij (t))1¤i,j¤2 such that the entries

bij : R ’ R are continuous, B(0) = I and B(π) = ’I but B(t) is nowhere

singular. [Think rotations.]

Exercise K.107. [7.3, M!] Four towns lie on the vertices A, B, C, D of

a square. Find the shortest total length of the system of roads shown in

Figure K.2 where the diagram is symmetric about lines through the centres

of opposite sides of the square. By formal or informal arguments, show that

this arrangement gives the shortest total length of a system of roads joining

all four towns. (You should, at least, convince yourself of this.) Is the

arrangement unique?

The interesting point here is that the most highly symmetric road systems

do not give the best answer.

Exercise K.108. [7.3, P] We continue with the notation of Exercise 7.3.12.

Show that, if g is continuously di¬erentiable, then f is di¬erentiable except

at (0, 0) (there are various ways of doing this but, whichever one you choose,

be careful), and has directional derivatives in all directions at (0, 0). For

which functions g is f di¬erentiable at (0, 0)?

487

Please send corrections however trivial to twk@dpmms.cam.ac.uk

Exercise K.109. [7.3, P] (i) Let a > b > 0 and de¬ne f : R2 ’ R by

f (x, y) = (y ’ ax2 )(y ’ bx2 ).

Sketch the set E = {(x, y) : f (x, y) > 0}. Show that f has a minimum

at (0, 0) along each straight line through the origin. (Formally, if ± and β

are real numbers which are not both zero, the function g : R ’ R given by

g(t) = f (±t, βt) has a strict local minimum at 0.) Show, however, that f has

no minimum at (0, 0). Does f have any minima?

(ii) Suppose F : R2 ’ R is twice continuously di¬erentiable with a non-

singular Hessian at (0, 0). Show that F has a minimum at (0, 0) if and only if

it has a minimum at (0, 0) along each straight line through the origin. Why

is this result consistent with part (i)?

[Like many examples in this subject, part (i) is due to Peano.]

Exercise K.110. [8.2, P] (i) Let F be the function given in Exercise 8.2.23.

By considering F ’ 1 , or otherwise, show that if a bounded function f :

2

[a, b] ’ R is not Riemann integrable, it does not follow that |f | is not

Riemann integrable. If a bounded function f : [a, b] ’ R is such that |f |

is not Riemann integrable, does it follow that f is not Riemann integrable?

Give a proof or counterexample.

(ii) Let f, g : [a, b] ’ R be bounded functions. If both f and g are not

Riemann integrable, does it follow that f + g is not Riemann integrable? If

both f and g are not Riemann integrable, does it follow that f +g is Riemann

integrable? If f is Riemann integrable but g is not Riemann integrable, does

it follow that f +g is not Riemann integrable? If f is Riemann integrable but

g is not Riemann integrable, does it follow that f + g is Riemann integrable?

(Give proofs or counterexamples.)

(iii) Compose and answer similar questions for the product f g and for »f

where » is a non-zero real number.

Exercise K.111. [8.2, P] De¬ne f : [0, 1] ’ R by f (p/q) = 1/q when p

and q are coprime integers with 1 ¤ p < q and f (x) = 0 otherwise.

1

(i) Show that f is Riemann integrable and ¬nd 0 f (x) dx.

(ii) At which points, if any, is f continuous? Prove your answer.

(iii) At which points, if any, is f di¬erentiable? Prove your answer.

Use the ideas of this exercise to de¬ne a function g : R ’ R which is

unbounded on every interval [a, b] with b > a.

Exercise K.112. [8.2, P] Suppose that f : [0, 1] ’ R is Riemann inte-

grable. Show that, if we write gn (x) = f (xn ), then gn : [0, 1] ’ R is Riemann

488 A COMPANION TO ANALYSIS

integrable. State, with appropriate proof, which of the following conditions

imply that

1

f (xn ) dx ’ f (0)

0

as n ’ ∞.

(i) f is continuous on [0, 1].

(ii) f is continuous at 0.

(iii) No further condition on f .

Exercise K.113. [8.2, H] (i) Let

D = {x0 , x1 , . . . , xn } with a = x0 ¤ x1 ¤ x2 ¤ · · · ¤ xn = b

be a dissection of [a, b] and let > 0. Show that there exists a δ > 0

depending on and D such that, if

D = {y0 , y1 , . . . , ym } with a = y0 ¤ y1 ¤ y2 ¤ · · · ¤ ym = b

is a dissection of [a, b] with |yj ’ yj’1 | < δ for all j, then the total length

of those intervals [yk’1 , yk ] not completely contained in some [xi’1 , xi ] is less

than . More formally,

n

|yk ’ yk’1 | < .

i=1 [yk’1 ,yk ] [xi’1 ,xi ]=…

(ii) Show that, if f : [a, b] ’ R is a function with |f (t)| ¤ M for all t, D

is a dissection of [a, b] and > 0, we can ¬nd an · > 0 (depending on M ,

and D) such that if

D = {y0 , y1 , . . . , ym } with a = y0 ¤ y1 ¤ y2 ¤ · · · ¤ ym = b

is a dissection of [a, b] with |yj ’yj’1 | < · for all j, then S(f, D ) < S(f, D)+

and S(f, D) > s(f, D) ’ .

(iii) Show that a bounded function f : [a, b] ’ R is Riemann integrable

with integral I if and only if, given any > 0 we can ¬nd an · > 0 such that,

if

D = {x0 , x1 , . . . , xn } with a = x0 ¤ x1 ¤ x2 ¤ · · · ¤ xn = b

is a dissection of [a, b] with |xj ’ xj’1 | < · for all j, then

S(f, D) ’ s(f, D) < , and |S(f, D) ’ I| ¤ .

489

Please send corrections however trivial to twk@dpmms.cam.ac.uk

(iv) Show that a bounded function f : [a, b] ’ R is Riemann integrable

with integral I if and only if, given any > 0, we can ¬nd a positive integer

N such that, if n ≥ N and

D = {x0 , x1 , . . . , xn } with xj = a + j(b ’ a)/N,

then

S(f, D) ’ s(f, D) < , and |S(f, D) ’ I| ¤ .

(v) Show that, if f : [a, b] ’ R is Riemann integrable, then

n’1 b

b’a

f (a + j(b ’ a)/n) ’ f (t) dt

n a

j=0

as N ’ ∞. Why is this result compatible with Dirichlet™s counterexample

(Exercise 8.2.23)?

Exercise K.114. [8.2, H] (This exercise is best treated informally.) If we

insist on considering the integral as the area under a curve, then our de¬nition

of the Riemann integral of a function which can be negative looks a bit odd.

We could restrict ourselves initially to positive bounded functions and then

extend to general functions in (at least) two ways.

(A) If f : [a, b] ’ R is bounded, we can write f (t) = f+ (t) ’ f’ (t) with

f+ and f’ positive. We set

b b b

f+ (t) dt ’

f (t) dt = f’ (t) dt

a a a

if the right hand side of the equation exists.

(B) If f : [a, b] ’ R is bounded we can write f (t) = fκ (t) ’ κ with fκ

positive and κ a real number. We set

b b

fκ (t) dt ’ κ(b ’ a).

f (t) dt =

a a

Run through the checks that you must make to see that these de¬nitions

work as expected. For example, if we use (B), we must check that the value

of the integral is independent of the value of κ chosen. In both cases we must

check that, if f and g are integrable, so is f g.

Explain why we get the same integrable functions and the same integrals

from the three de¬nitions considered (the one we actually used, (A) and (B)).

490 A COMPANION TO ANALYSIS

Exercise K.115. [8.2, H] No modern mathematician would expect any

reasonable theory of integration on the rationals for the following reason.

Since the rationals are countable we can enumerate the elements of [0, 1] © Q.

Enumerate them as x1 , x2 , . . . . Let Jr be an interval of length 2’r’1 con-

taining xr . We observe that the union of the Jr covers [0, 1] © Q but that the

total length of the intervals is only ∞ 2’r’1 = 1/2.

r=1

(i) Show that, given any > 0, we can ¬nd intervals J1 , J2 , . . . of total

length less than with ∞ Jr ⊇ Q.