<< . .

. 54
( : 70)



. . >>

through the algebra in detail.)
(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.

<< . .

. 54
( : 70)



. . >>