BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR92-1273
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: From the Buffon Needle Problem to the Kreiss Matrix Theorem
AUTHOR:: Wegert, Elias 
AUTHOR:: Trefethen, Lloyd N.  
DATE:: March 1992
PAGES:: 12
ABSTRACT:: 
In this paper we present a theorem concerning the arc length on the Riemann 
sphere of the image of the unit circle under a rational function. But our 
larger purpose is to tell a story. We thought at first that the story began 
in 1962 with the Kreiss matrix theorem, the application that originally 
motivated us. However, our arc length question turns out to be more 
interesting than that. The story goes back to the famous ``Buffon needle 
problem'' of 1777.
END:: CORNELLCS//TR92-1273
BODY::
From the Bufton Needle Problem
to the Kreiss Matrix Theorem
Elias Wegert
Lloyd N. Tretethen
TR 92-1273
March 1992
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
?rom the Buffon Needle Problem
to the Kreiss Matrix Theorem
Elias Wegert and Lloyd N. Trefethen
In this paper we present a theorem concerning the arc length on the Riemann sphere
of the image of the unit circle under a rational function. But our larger purpose is to
tell a story. We thought at first that the story began in 1962 with the Kreiss matrix
theorem, the application that originally motivated us. However, our arc length question
turns out to be more interesting than that. The story goes back to the famous "Buffon
needle problem" of 1777.
SPIJKER'S LEMMA IN THE COMPLEX PLANE, Let r be a rational function
of order n, that is, a quotient of two potynomials of degree at most n. Let 5 denote the
unit circle fz Ei C : Izi = 1?, and let II 11i'll 112' and II IIoo denote the 1-, 2-, and
co-norms on 5,
11f111 = Is If(z)I IdzI, 1lfll92 = f? If(z)12 IdzI, Ilfil0o = su?P5 If(z)I.
Then the arc length of the curve r(S) in the complex plane, which we denote by Lc(r(S)),
can be represented compadly by the formula
:= IIr'IIi.
If r is multiplied by a constant cr, Lc(r(S)) changes by the factor loLl. However, this
scale-dependence can be eliminated by considering the ratio
L?(r(S)) / llrll?.
Revised 3/18/92. To appear in the American Mathematical Monthly.
(1)
In 1984, building on earlier work by Laptev, Strang, and Tadmor, LeVeque and Trefethen
[9] observed that a bound on (1) could be used to derive a sharp form of the Kreiss matrix
theorem (which we shall discuss at the end). They therefore posed the question, what
is the maximum possible value of (1)?
It is easy to see that the value 2:rn can be attained; just take r(z) to be z? or
z??. If r is restricted to be a polynomial, it follows from Bernstein's inequality that
2:rn is the maximum possible. It is also easy to see that 2rn is the maximum value for
rational functions in the special case n = 1 (the reader can supply the proof!). Based
on these facts and on computer experiments, it was conjectured in [9] that 2'rn is the
maximum value (1) for all rational functions r and all n. Howe?rer, only the bound 4?n
was proved, and the task of eliminating this gap of a factor of 2 was presented as an
Advanced Problem in this Monthly [10].
Just one response to the Monthly problem was received, from James C. Smith, of
the University of South Alabama, who improved the bound to 2(2 + r)n [16].
Five years later, Marc Spijker of the University of Leiden finally settled the conjecture
in the affirmative [17]:
Theorem 1. Lc(r(S)) / IIrII? ? 2rn.			(4Sp4ker)? lemma")
SPIJKER'S LEMMA ON THE RIEMANN SPHERE. The simplicity of The-
orem 1 is marred by the need for the normalization by IIrIIoo. In looking for a cleaner
formulation one may ask, what is the anatogous result for the Riemaun sphere? Let S
denote the Riemaun sphere [x ? R3 : Ixi = 1], with the north and south poles corre-
sponding to the points oc and 0 in C, respectively, according to the usual stereographic
projection, and the equator corresponding to the unit circle S. This identification of C
and S is discussed in many books on complex analysis [1], and it is readily shown that
a unit of arc length IdzI at a position z E C is expanded by the factor 2/(1 + 1zi2) in
being projected onto S. It follows that if r(?) is considered as a closed curve on S, with
Ls(r(S)) denoting its arc length on S, then we have
I 2r'/(1 + 1r12) Iii			(2)
2
Now, the trivial scale-dependence has been eliminated from the problem. It makes sense
simply to ask, what is the maximum possible value of Ls(r(S))?
The new result of this paper is the following answer to this question:
Theorem 2. Ls(r(S)) ? 2rn. ("Spi5ker's lemma on the Riemann sphere")
The proof of Theorem 2 will emerge in the following pages. For the moment, we note
first of all that like Theorem 1, Theorem 2 is obviously sharp, with equality attained
for any r that maps S with winding number n onto a great circle of S. (For example,
r(z) = z? maps 5 with winding number n onto the equator, and r(z) =
maps 5 with winding number n onto the Greenwich meridian.) A more important
observation is that for any r with IIrII? ? 1, we have L?(r(S)) ? Ls(r(5)). This
follows from (2), since 2/(1 t 1ri2) > 1 when Iri < 1. Consequently, Theorem 2 implies
Theorem 1 as a corollary. Thus Spijker's lemma on the Riemaun sphere is both simpler
and stronger than Spijker's lemma in the complex plane, and perhaps it should be
considered the more fundamental result.
FROM THE NEEDLE PROBLEM TO POINCARE'S FORMULA. The
reader has undoubtedly encountered the Buffon needle problem, published by the Comte
de Buffon in 1777. Suppose a needle of length 1 is thrown at random on a plane ruled
by parallel lines at a distance 1 apart. What is the probability that the needle will land
in a position that crosses a line? Easy calculus shows that the answer is
Probability of intersection
7r
Buffon, incidentally, was the leading French naturalist of the eighteenth century and also
a translator of Newton. He worked on his "proble'me de l'aiguille" long before publishing
it as an appendix on "moral arithmetic" in his 44-volume treatise on natural history [3]
The needle problem became well known, especially among the French, and was gen-
eralized. Laplace, without referencing Buffon, solved the analogous problem for a square
grid (The'orie Analytique des Probabdites, 1812). A more important generalization was
3
to consider the slightly modified question: if the needle has length L, possibly greater
than 1, what is the expected number of intersections? The answer is easily seen to be
Expected number of intersections = 2L			(3)
7r
And from here it is a small step mathematically, but a big one conceptually, to note
that the same formula (3) is valid also for a paper clip. Various steps in this direction
were taken by Cauchy, Lam6, and Barbier, among others [2]. In fact, if any rectifiable
curve F of arc length L is thrown at random on the parallel grid, the expected number
of intersections is (3). (A curve is rectifiable if its real and imaginary parts are functions
of bounded variation [1].) The idea behind this result is that F can be thought of as a
concatenation of infinitesimal straight segments, each satisfying (3) for an appropriate
infinitesimal value of L. Now it may seem at first that the expected number of inter-
sections for F should be more complicated than the sum of the expected numbers for
the segments F is composed of, since after all, the segments do not fall on the grid inde-
pendently. However, independence is not relevant unless one cares about the efficiency
of (3) as a method for approximating ir. It is a basic fact of statistics that the expec-
tation of a sum of random variables is equal to the sum of the expectations, regardless
of whether or not they are independent. This observation seems elementary to us now,
but its application to the needle problem was evidently not obvious in the nineteenth
century.
Taking the paper clip to be a circle of radius 2 gives an easy way to remember
Buffon's result and its generalization (3). For this choice of F, L is 7r and the number of
intersections is exactly 2, no matter how the paper clip falls.
We now want to move from the plane to the sphere, a step taken as early as 1860
by Barbier [2]. Consider a `?spherical paper clip" that is, a curve F embeddable in the
Riemaun sphere. Suppose F is oriented at random on S. What is the expected number
of intersections with the equator? The answer is again essentially a matter of combining
calculus with elementary statistics:
L
Expected number of intersections on the sphere = --H?. (4)
4
Or one can skip the calculus and remember this result by thinking of the case in which
F is itself a great circle. In this case L = 2r and the number of intersections is again
exactly 2 unless F happens to land exactly on the equator, an event of probability zero.
A final development completes this brief history. After Barbier, other mathemati-
cians generalized these results further, including Poincare', who referenced neither Bulfon
nor Barbier (Calcul des Probabdite%? 1896 [12]). By this time it was clear that although
the needle problem and its generalizations had conventionally been formulated as prob-
lems of probability, that interpretation could be dispensed with. Instead of orienting I'
at random on S and asking for the expected number of intersections with a fixed equator,
one can consider F to be fixed on S and compute its arc length Ls(I') as an integral
of the number of intersections with all great circles. To be precise, for any rectifiable
curve F C S and any x = (x1,x2,x3) E S, let ii(I',x) denote the number of points of
intersedion of F with the great circle on S consisting of points equidistant from the
antipodes +x. (When this number is infinite, the definition of v(F, x) does not matter,
for the set of such points has measure zero.) One obtains the following elegant result:
Lemn?a 1. Ls(F) = ?41f i'(F,x)dx. (`Toincare"sformula")
The integral is taken with respect to area measure on
Lemma 1 can be expressed in words as follows. To find the arc length of a curve
on the Riemann sphere, integrate its numbers of intersections over all great circles, then
divide by 4. Or, equivalently, since the sphere has surface area 47r, take the average
number of intersections and multiply by 7r. This latter paraphrase of Lemma 1 makes
plain its equivalence to (4).
Poincare's formula has far-reaching generalizations described in the book by Santal6
[15], which the reader may consult for a wealth of related ideas as well as for the rigor
lacking in the discussion above. It forms a centerpiece of the field known earlier as
`?geometric probability" but now as "integral geometry."
5
PROOF OF SPIJKER'S LEMMA. Is it obvious now how to prove Theorem 2?
All we need is the following lemma, whose proof we shall spell out though it might
equally well have been left as an exercise. As above, i'(r(S), x) denotes the number
of intersection points of the curve r(S) with the great circle on the Riemaun sphere S
defined by the points +x.
Lemma 2. If r is a rational function of order n, then v(r(S), x) < 2n for all x E S
with the possible exception of a single pair x +XO) XO E S.
Proof Since any point of S can be rotated to any other by a M5bius transformation,
leaving the set of rational functions of order n invariant, we are free to choose a particular
value of x for convenience. Let us take x to be the north pole, so that the great circle
in question is the equator, i.e., the image of S on S. If r(z) p(z)/q(z) for polynomials
p and q of degree < n, then for z E S
2
Ir(z)12 =			p(z)			_ p(z)p(z) _ p(z)p*(z)
q(z)			--H q(z) q(5) --H q(z) q*(z)'
where p*(z) znp(z?l) and q*(z) := znq(z?l) The condition Ir(z)12 = 1 is thus a
polynomial equation in z of degree at most 2n. Therefore r(S) intersects the equator in
at most 2n points, counted with multiplicity, unless it lies along the equator exactly. In
the latter case it is obviously only the north and south poles for which the intersection
number is infinite. ?
Since the surface area of S is 47r and since ? 2n			= 2rn, Theorem 2 is an
4
immediate consequence of Lemmas 1 and 2.
Spijker's original proof of Theorem 1, though derived independently, can be inter-
preted as a planar version of the same argument just given to establish Theorem 2.
In particular, equation (6) of [17] is a kind of Poincare. formula for the complex plane,
expressed in terms of lengths of one-dimensional projections instead of numbers of inter-
sections. Apparently this formula was first worked out by Cauchy in 1832 and published
by him in 1841 [5].
6
THE KREISS MATRIX THEOREM. What does all this have to do with the
Kreiss matrix theorem? Let A be an n x n matrix, and let I II denote the matrix norm
induced by the vector norm II 112. The Kreiss matrix theorem, originally published in
1962 [8], concerns the the problem of characterizing matrices and families of matrices
that are power-bounded. Let us define
p(A) = 5??>Po IlAkil, r(A) = s?u>P1 (Izi --H 1) II(zI --H A)?'ll.
The current, sharp form of the theorem reads as follows [17]:
Theorem 3. r(A) ? p(A) ? enr(A)
(aAyeiss matrix Iheorem")
In words, a matrix A is power-bounded (p(A) < oc) if and only if the norm of its
resolvent (zI --H A)--H increases at most inverse-linearly as z approaches the unit circle
from the outside (r(A) < oc). Moreover, the gap between p(A) and r(A) is a factor of
at most e (= 2.718...) times n, so the same conclusion applies to families of matrices
[A?) of fixed dimension that satisfy uniform bounds on p(A?) and r(A?).
The first inequality of Theorem 3 asserts that if IlAkil < C for k > 0 then II(zI --H
A)--H1II < C/(IzI --H 1) for Izi> 1. This is easy to prove by making use of the power series
(zI --H A)--H1 = z??I t z?2A t z?3A2$.... The more interesting inequality is the second
one, which asserts that if (zi--H A)--H1 < C/(IzI --H 1) for Izi > 1, then Ak ? enC for
k > 0. According to Tadmor's remarks in [18] for the earlier developments, the history
of successive improvements toward this constant en involves no fewer than nine steps,
though the earlier authors in the list w&e certainly not concerned with optimizing the
constant:
Kreiss `62:
Morton `64: N 6?(n t 4)5n
Miller & Strang `66: N ?fl
Miller `67: e9?2
7
Laptev `75 I Strang `78: 32en2/r
Tadmor `81: 32en/r
LeVeque & Trefethen `84: 2en
Smith `85: e(1+4)n
Spijker `91: en
History, thank goodness, stops here. It is shown in [9] that the constant en is best
possible.
As the estimates have become sharper, the proofs have become mercifully simpler
and have ceased to depend upon the explicit manipulation of eigenvalues and normal
forms of matrices. We reproduce now the argument from [9] that shows how the constant
en follows from Spijker's lemma.
Proof of the second inequality of Theorem 3. According to the calculus of resolvents
described for example in [7], the matrix Ak can be written as the Cauchy integral
Ak			2rli fo zk(zI --H A)--H' dz,
where G is any curve enclosing the eigenvalues of A, which must lie in [z E C: Izi < 1]
if r(A) < 00. Let u and v be arbitrary n-vectors with lull2 = 1lvil2 = 1. Then
v*Aku = 2rtif0zkq(z)dz,
where v* denotes the conjugate transpose of v and q(z) is the function v*(zI --H
which can be shown to be a rational function of order n. Integration by parts gives
v*Aku =			lzk+lqt(z)dz
2ri(ktl)o
Let the contour of integration be taken as G = tz e C: Izi = 1 t (kt 1)--H'J. On this
contour we have Izk+lI < e and hence
Iv*Akul < 2?(k?t1) Jo q'(z) ldzl.
8
This integral can be interpreted as the arc length of q over the circte G. By a trivial
change of variables it might as well be an arc length over the unit circle S. Theorem 1
therefore implies
Iv*Akul < 2r(k?t1) (2rn) 5z??PG Iq(z)I,
and therefore, since the supremum of Iq(z) on G is at most (k? 1)r(A), by the definition
of r(A), we have
Iv*Akul ? enr(A).
Finally, we note that since IlAkil is the supremum of Iv*Akul over all vectors u and v
with IIt112 = 11v112 = 1, this last inequality proves the theorem. ?
The Kreiss matrix theorem has been a fixture of numerical analysis since its ap-
pearance in 1962 and dissemination in the well-known book by Richtmyer and Morton
[14]. It is one of the fundamental results available for establishing numerical stability of
discrete processes.
CONCLUSION. From Buffon to Spijker to Kreiss, the pieces of our story fit together
so neatly that it may seem there can be nothing more to say. Nevertheless, matters
related to the Kreiss matrix theorem are subjects of active interest today, and in con-
clusion, we would like to mention a recent generalization of Theorem 3 and an open
question.
The generalization concerns the problem of numerical stability of the "method of
lines." When time-dependent partial differential equations are solved numerically by
discretization, it is common to simplify the process by constructing the space discretiza-
tion and the time discretization independently. For example, the Crank-Nicolson formula
for solving parabolic PDEs, of which the prototype is the heat equation u? = Uzz, can
be viewed as a second-order centered finite difference with respect to x coupled with the
"trapezoid formula" with respect to 1. In more realistic problems the space discretization
might involve more complicated finite difference, finite element, or spectral approxima-
tions and the time discretization might be accomplished by any of the familiar methods
for ODEs such as Runge-Kutta or Adams-Bashforth formulas [6].
9
According to the celebrated Lax Equivalence Theorem, the numerical solution com-
puted by a consistent discretization of a well-posed linear partial differential equation
will converge to the solution of the PDE as the mesh size shrinks to 0 if and only if the
discretization is numerically stable [14]. (We ignore the effects of rounding errors.) But
how does one test for numerical stability? It has recently been shown that for method of
lines calculations, one can do it by a transplantation of the Kreiss matrix theorem from
the unit disk to the subset of C known as the stability region of the ODE formula [13].
One replaces the monomial Ak in the term p(A) of Theorem 3 by the solution to a more
general matrix recurrence relation, and the unit disk in the term r(A) of Theorem 3
by the stability region. The condition for stability is that the norm of the resolvent of
an appropriate spatial discretization matrix must increase at most inverse-linearly as z
approaches the boundary of the stability region from the outside. For numerical ana-
lysts, to whom stability regions of ODE formulas are as familiar as simple groups are to
algebraists, this result provides an easy means of applying the Kreiss matrix theorem to
a wide range of practical problems. In particular it is applicable to the stability analysis
of the high-accuracy numerical techniques known as spectral methods [4], where the ma-
trices that anse are often far from normal and difficult to analyze by more elementary
techniques.
The open question is, what happens to Theorem 3 if r(A) is viewed as a constant
rather than a variable? If r(A) = 1, then it can be shown that the field of values of
A, that is, the set of R?ayleigh quotients u*Au/11u1122, must lie in the closed unit disk.
By a result due originally to Lax and Wendroff and subsequently sharpened by Halmos,
Berger, and Pearcy [14], it follows that when r(A) = 1 we have p(A) < 2, or in other
words, the factor en of Theorem 3 can be replaced by the constant 2, independently of
n. Now, what if r(A) is a constant greater than 1? For example, what can be said about
p(A) if r(A) = 2? It is known that p(A) can no longer be bounded by a constant [11],
but beyond this for example, whether en can be improved to a quantity that grows
only logarithmically in n--Hnothing is known.
10
ACKNOWLEDGMENTS. The problem of generalizing Spijker's lemma to the Riemann sphere
was raised by the second author at a meeting in Oberwolfach in February, 1991. The proof presented
here was devised by the first author, who is grateful to D. Stoyan for pointing out the connections with
integral geometry. Subsequently A. I. Aptekarev of the Keldysh Institute of Applied Mathematics in
Moscow has communicated to us a different and equally simple proof based on induction in n.
We are grateful also for advice from a number of others, especially Marc Spijker.
This paper was written during a visit by the second author to the Universite' Pierre et Marie Curie
in Paris, across the street from the Jardin des Plantes where Buffon served as Director 250 years ago
and his statue stands today.
REFERENCES
1. L. Ahlfors, Complex Analysis, McGraw-Hill, 1966.
2. E. Barbier, Note sur le probleme de l'aiguille et le jeu du joint couvert, J. Math. Pttres Appi., 5
(1860) 273--H286.
3. G. Buffon, Essai d'arithme'tiqne morale, Supplement a' l'Histoire Naturelle, v. 4,1777.
4. C. Canuto, NI. Y. Hussaini, A. Quarteroni, and T. A. Zang, Spectral Methods in Flnid Dynamics,
Springer-Verlag, 1988.
5. A. Cauchy, Note sur divers theoremes relatifs a' la rectification des courbes, et a' Ia quadrature
des surfaces, Comptes Rendns, 13 (1841), p. 1060, reprinted in A. Cauchy, Oenvres, Serie I, v. 6,
pp. 369--H375, Gauthier-Villars, Paris, 1888.
6. E. Hairer, 5. P. N?rsett, and G. Wanner, Solving Ordinary Differential Equations, Springer-Verlag,
1987 (v. 1) and 1991 (v. 2).
7. T. Kato, Perturbahon Theory for Linear Operators, 2nd ed., Springer-Verlag, 1976.
8. H. 0. Kreiss, U?ber die Stabilita?tsdefinition fiir Differeuzengleichungen die partielle Differenzialgle-
ichungen approximieren, BIT, 2 (1962)153--H181.
9. R. J. LeVeque and L. N. Trefethen, On the resolvent condition in the Kreiss Matrix Theorem, BIT,
24 (1984) 584--H591.
10. R. J. LeVeque and L. N. Trefethen, Problem #6462, Advanced Problems, Amer. Math. Monthly,
91(1984) 371.
11. C. A. McCarthy and J. Schwartz, On the norm of a finite Boolean algebra of projections, and
applications to the theorems of Kreiss and Morton, Comm. Pure Appl. Math., 18 (1965)191--H201.
12. H. Poincare', Calcul des Probabihte's, Gauthier-Villars, Paris, 1896.
13. 8. C. Reddy and L. N. Trefethen, Stability of the method of lines, Numer. Math., to appear.
14. R. D. Richtmyer and K. W. Morton, Difference Methods for Initial- Value Problems, 2nd ed., Wiley-
Interscience, 1967.
11
15. L. A. Santal6, Integral Geometry and Geomeiric Probability, Addison-Wesley, 1976.
16. J. C. Smith, An inequality for rational functions, Solutions of Advanced Problems, Amer. Alath.
Alonthly, 92 (1985) 740--H741.
17. M. N. Spijker, On a conjecture by LeVeque and Trefethen related to the Kreiss matrix theorem,
BIT, 31(1991) 551--H555.
18. E. Tadmor, The equivalence of L2-stability, the resolvent condition, and strict H-stability, Lin. Alg.
Applics., 41(1981)151--H159.
Faclibereich Mathematik			Department of Compnter Science
Bergakademie Freiberg			Cornell University
D-O-9?OO Freibery			Ithaca, NY 1?85?
Germany			USA
wegert?mathe. ba-freibery. dbp. de			lntG?cs. cornell. edn
12
