May 2011 Contents
For subscribers, read recent issues online (Requires MAA Membership)
Francis’s AlgorithmDavid S.Watkins
John Francis’s implicitly shifted QR algorithm turned the problem of matrix eigenvalue computation from difficult to routine almost overnight about fifty years ago. It was named one of the top ten algorithms of the twentieth century by Dongarra and Sullivan, and it deserves to be more widely known and understood by the general mathematical community. This article provides an efficient introduction to Francis’s algorithm that follows a novel path. Efficiency is gained by omitting the traditional but wholly unnecessary detour through the basic QR algorithm. A brief history of the algorithm is also included. It was not a one-man show; some other important names are Rutishauser, Wilkinson, and Kublanovskaya. Francis was never a specialist in matrix computations. He was employed in the early computer industry, spent some time on the problem of eigenvalue computation and did amazing work, and then moved on to other things. He never looked back, and he remained unaware of the huge impact of his work until many years later.
Where Are Limits Needed in Calculus?R. Michael Range
A method introduced in the 17th century by Descartes and van Schooten for finding tangents to classical curves is combined with the point-slope form of a line in order to develop the differential calculus of all functions considered in the 17th and 18th centuries based on simple purely algebraic techniques. This elementary approach avoids infinitesimals, differentials, and similar vague concepts, and it does not require any limits. Furthermore, it is shown how this method naturally generalizes to the modern definition of differentiability.
Maximal Independent Sets and Separating CoversVincent Vatter
In 1973, Katona raised the problem of determining the maximum number of subsets in a separating cover on n elements. The answer to Katona’s question turns out to be the inverse to the answer to a much simpler question: what is the largest integer which is the product of positive integers with sum n? We give a combinatorial explanation for this relationship, via Moon and Moser’s answer to a question of Erdös: how many maximal independent sets can a graph on n vertices have? We conclude by showing how Moon and Moser’s solution also sheds light on a problem of Mahler and Popken’s about the complexity of integers.
Packing a Cake into a BoxM. Skopenkov
Given a triangular cake and a box in the shape of its mirror image, how can the cake be cut into a minimal number of pieces so that it can be put into the box? The cake has icing, so we are not allowed to put it into the box upside down. V. G. Boltyansky asked this question in 1977 and showed that three pieces always suffice. In this paper we provide examples of cakes that cannot be cut into two pieces to be put into the box. This shows that three is the answer to Boltyansky’s question. We also give examples of cakes which can be cut into two pieces.
What Every Mathematician Should Know about Standards-Based TestsAlan Tucker
This article examines serious psychometric-based problems that caused the New York Math A graduation test introduced in 1999 to produce a 70% failure rate in 2003. In discussing this test, we highlight potential difficulties with all standards-based tests.
NOTESCauchy’s Theorem and Sylow’s Theorem from the Cyclic Case
Geoffrey R. Robinson
We give a simultaneous proof of Cauchy’s theorem and Sylow’s theorem by reducing to the case of cyclic groups.
A Really Simple Elementary Proof of the Uniform Boundedness TheoremAlan D. Sokal
I give a proof of the uniform boundedness theorem that is elementary (i.e., does not use any version of the Baire category theorem) and also extremely simple.
On the Group of Automorphisms of a GroupMarian Deaconescu and Gary L.Walls
This note gives a generalization of the classical result asserting that if the center of a group G is trivial, then so is the center of its automorphism group Aut(G).
The Unreasonable Slightness of E2 Over Imaginary Quadratic RingsBogdan Nica
It is almost always the case that the elementary matrices generate the special linear group SLn over a ring of integers in a number field. The only exceptions to this rule occur for SL2 over rings of integers in imaginary quadratic fields. The surprise is compounded by the fact that, in these cases when elementary generation fails, it actually fails rather badly: the group E2 generated by the elementary 2-by-2 matrices turns out to be an infinite-index, non-normal subgroup of SL2. We give an elementary proof of this strong failure of elementary generation for SL2 over imaginary quadratic rings.
REVIEWSMathematics in Historical Context.
Reviewed by Peggy Aldrich Kidwell