| Alan Hoffman | |
| Birth Date: | May 30, 1924[1] |
| Birth Place: | New York City, New York, U.S. |
| Nationality: | American |
| Fields: | Mathematics |
| Workplaces: | Thomas J. Watson Research Center City University of New York |
| Alma Mater: | Columbia University |
| Doctoral Advisor: | Edgar Lorch |
| Doctoral Students: | Lennox Superville |
| Thesis Title: | On the Foundations of Inversion Geometry |
| Thesis Year: | 1950 |
| Awards: | John von Neumann Theory Prize (1992) |
Alan Jerome Hoffman (May 30, 1924 – January 18, 2021) was an American mathematician and IBM Fellow emeritus, T. J. Watson Research Center, IBM, in Yorktown Heights, New York. He was the founding editor of the journal Linear Algebra and its Applications, and held several patents. He contributed to combinatorial optimization and the eigenvalue theory of graphs. Hoffman and Robert Singleton constructed the Hoffman–Singleton graph, which is the unique Moore graph of degree 7 and diameter 2.[2]
Hoffman died on January 18, 2021, at the age of 96.[3] [4]
Alan Hoffman was born and raised in New York City, residing first in Bensonhurst, Brooklyn and then on the Upper West Side of Manhattan, with his sister Mildred and his parents Muriel and Jesse. Alan knew from an early age that he wanted a career in mathematics. He was a good student in all disciplines, finding inspiration in both the liberal arts and the sciences. But he was enthralled by the rigor of deductive reasoning found in mathematics. He graduated from the George Washington High School in 1940 and entered Columbia University that fall, on a Pulitzer scholarship in 1940 at the age of 16.
At Columbia, Hoffman joined the Debate Council, in part to overcome his fear of public speaking, and was active in both movements to increase American support for the Allies in the growing war against the Axis, and in the movement to have America directly enter the war. Although his coursework consisted primarily of mathematics, including small classes with luminaries in the field, he also studied philosophy, literature, and the history of governments.
World War II interrupted Hoffman's studies but not his interest in mathematics. He was called to service in February 1943 and served in the U.S. Army from 1943 to 1946, spending time in both Europe and the Pacific. Hoffman eloquently refers to these three years as "the climatic event of my life, with adventure magnified by the sensibilities of youth."
While in basic training in the anti-aircraft artillery school he considered the possibility of developing axioms for the geometry of circles. Unable to draw, he carried in his head a vision of the configurations in space – points, circles and spheres – depicting phenomena analogous to the geometry of lines. These ideas would later become the genesis of his doctoral dissertation on the foundations of inversion geometry. The experience of developing ideas in the mind rather than on paper or the chalkboard remained a practice throughout his career – a practice he did not recommend to others but which served his unique mind remarkably well.
After additional Army training, Hoffman became an instructor at the anti-aircraft metrology [IL1] [2] school, teaching basic trigonometry used to track balloons to plot deduce winds aloft. Following additional training in Electrical Engineering at the University of Maine and on the rudiments of long-lines telephony Hoffman was assigned to the 3186th Signal Service Battalion and sent to the European theatre in December 1944, as the war there was nearing its end. He spent a brief period in the Pacific theatre before returning home in February 1946. During his time abroad he and others taught some mathematics in small self-organized courses and he recorded his forays into circular geometry to share with faculty back at Columbia.
Upon returning to Columbia in the Fall of 1946, Hoffman was assigned to teach a mathematical survey course to the Columbia College of Pharmacy. He viewed this as an opportunity to improve his pedagogical[3] skills and determine whether the planned career in university teaching would be the most suitable choice. During that academic year, he gained confidence and skills in his teaching, crystallized his ideas on axioms for circular geometry, and proposed marriage to Esther Walker, the sister of an Army friend. Hoffman began graduate studies at Columbia, in the Fall of 1947, "brimming with confidence."
Following successful completion of exams and defense of his doctoral dissertation on the foundations of inversion geometry in 1950, Hoffman spent a postdoctoral year at the Institute for Advanced Study in Princeton sponsored by the Office of Naval Research. During this year he established a rhythm for his work, based on the mantra "You are a mathematician, you do mathematics."[5]
At the end of the postdoctoral year, having not secured an academic appointment anywhere he would want to live, Hoffman joined the Applied Mathematics Division of the National Bureau of Standards (NBS, now the National Institute of Standards and Technology) in Washington DC. This, choice, advocated against by friends and colleagues, was fortuitous. "The entire arc of my career is based on the experience of the five years I spent in Washington at NBS." Hoffman had been hired to help fulfill a contract (Project SCOOP) with the Office of the Air Controller of the United States Air Force to pursue a program of research and computing in an area he had never heard of: linear programming. Hoffman found the new (both to him and the world) subject "a delicious combination of challenge and fun."
Hoffman learned linear programming from George Dantzig, who believed that their work would help organizations operate more efficiently through the use of mathematics – a concept that is now, 70 years later, continuing to be realized[IL4]. Through this work Hoffman became exposed to business concepts from management consulting, manufacturing, and finance, areas he enjoyed, but never felt fully at home in. Through Project SCOOP Hoffman became acquainted with other operations research notables such as Richard Bellman and Harold Kuhn. Although the code he wrote in 1951 "just didn't run," an experience disheartening enough that he never wrote another program, Hoffman and coauthors published a paper showing, based on experiments, that the simplex method was computationally superior to its contemporary competitors. This paper contained the first computational experiments with the simplex method and serves as a model for doing computational experiments in mathematical programming.
During these early years at NBS Hoffman developed the first example of cycling in the simplex method, an example which appears in numerous textbooks on the subject. A short NBS technical paper, apparently not widely circulated, showed that a point which "almost" satisfies a set of linear inequalities is "close: to some other point that does, under any reasonable definitions of "almost" and "close." The implications for linear programming algorithms that consider "lazy" or "soft" constraints, or for which the constraint data (matrix coefficients and right-hand side) are subject to noise are worth considering.
Hoffman was a key organizer of the influential Second Symposium in Linear Programming, held at the Bureau in January 1955. NBS's paper on the simplex method, ("How to solve a linear programming problem," Proc. Second Linear Programming Symposium, 1955) was widely distributed to other groups working on their own codes for the simplex algorithm. In 2020 this paper is a fascinating glimpse into the challenges of solving linear programs on tiny (by today's standards) computers. Hoffman's work at NBS included failed attempts to use linear programming to solve a combinatorial procurement auction problem. Combinatorial auctions remain challenging to this day, due to the overwhelming computational burden associated with computing optimal solutions[IL5]. The NBS effort used an approach which resembles branch-and-bound, which is now the standard method for solving integer programming problems.
With the German mathematician Helmut Wielandt, Hoffman used linear programming to estimate how distant the eigenvalues of one normal matrix were from the eigenvalues of another normal matrix, in terms of how distant the two matrices were from each other. The result relies on the observation that every doubly stochastic matrix is the convex hull of permutation matrices. For the Operations Research community, this result implies that for the subclass of linear programming problems which are called transportation problems, if the data (right hand side, or supply and demand values) consists of integers, then there is an optimal solution taking only integer values. The general result is known as the Hoffman-Wielandt Theorem and there are mathematicians who know Hoffman only through this result.
At NBS Hoffman explored the connection between linear programming duality and other combinatorial problems. This led to a simple but elegant proof to the König-Egerváry Theorem which states that for a 0-1 matrix, the maximum number of 1s that appear in different rows and columns is equal to the minimum number of rows and columns that in combination include all of the 1s in the matrix. This early work at NBS, and Hoffman's continued interest using linear equalities to prove combinatorial theorems led to collaborations with Harold Kuhn, David Gale and Al Tucker and to the birth of a subfield that later became known as polyhedral combinatorics. Hoffman was influential in later bringing Jack Edmonds to NBS (1959-1969), where the subject flourished.
While at NBS, Joe Kruskal and Hoffman showed that total unimodularity (the concept, not the name) provided an explanation of why some linear programs with integer data have integer solutions, and some do not. They also identified some sufficient conditions for a matrix to have the required property.
Hoffman also wrote about Lipschitz conditions for systems of linear inequalities, bounds on eigenvalues of normal matrices and the properties of smooth patterns of production. In 1956, Hoffman left the Bureau and moved to England with Esther and two young daughters, Eleanor (then 2) and Elizabeth (then less than 6 months) for the glamorous role of Scientific Liaison Officer (mathematics) at the London branch of the Office of Naval Research, with the mission of reestablishing connections between American and European mathematicians. This was a year of listening and learning, establishing and renewing friendships, and of course, doing mathematics. He did mathematics across Europe, discovering on a train to Frankfurt a beautiful theorem (but a flawed proof, later corrected by Jeff Kahn) connecting a topic in algebra to his early work on the geometry of circles. Another paper produced during this period further explores consequences of total unimodularity, and introduces the concept of a circulation in a directed graph as n generalization of the concept of an s-t flow, in which two of the graph's nodes play a special role.
As the year abroad came to a close Hoffman investigated two industrial positions in New York, one in a tiny mathematical research group at the nascent IBM Research Lab in northern Westchester county and the other teaching and providing general operations research support for GE employees at the Manhattan headquarters of the company. Hoffman choose the role in the larger, more established organization due to the location, the salary, and the opportunity to see if he, and the field of operations research could succeed in business. Hoffman found the job fascinating and, in many respects, satisfying. He was allowed by management to do mathematics, as long as it did not interfere with his assigned duties. Hoffman continued his research, most of which was orthogonal to the mission of the Management Consulting group, in an elegant office in the heart of Manhattan.
In the summer of 1960, Hoffman participated in a summer workshop on Combinatorics hosted by the mathematics department at IBM Research. He was dazzled by the atmosphere and "people all around doing mathematics." In 1961 he accepted the invitation of Herman Goldstine, Herb Greenberg, and Ralph Gomory to join IBM Research, thinking that it would be a great place to work, but that it probably wouldn't last, and in a few years he would get a "real job" in academia. Although Hoffman served as a visiting or adjunct professor at Technion Israel Institute of Technology (which awarded him an honorary doctorate), Yale, Stanford (where he spent cold winters for almost a decade), Rutgers, the Georgia Institute of Technology, Yeshiva University, the New School, and the City University of New York and supervised Ph.D. dissertations at City University of New York, Stanford, Yale and Princeton, he remained a member of the Mathematics Department at IBM Research until his retirement as an IBM Fellow in 2002.
Upon joining IBM, Hoffman was one of the oldest members of the department, which was composed primarily of new Ph.D.’s. Despite being a mere 11 years post-PhD, Hoffman quickly assumed the role of mentor to these young researchers, discussing their work and interest and providing guidance. He served briefly as director of the department and was appointed IBM Fellow in 1977. Over the course of his career he published upwards of 200 academic papers, more than a third of them with coauthors. His mathematical range spanned numerous areas in both Algebra and Operations Research. He co-authored papers with many of his IBM colleagues, collaborating effectively with everyone from his fellow IBM Fellows) to summer interns and postdocs. Hoffman's humor, enthusiasm for math, music and puns, kindness and generosity were appreciated by all who encountered him.
Summary of Mathematical Contributions (from his notes in Selected Papers of Alan Hoffman)[6] ----Hoffman's work in Geometry, beginning with his dissertation "On the foundations of inversion geometry," included proofs of properties of affine planes, and the study of points of correlation of finite projective planes, conditions on patterns of the union and intersection of cones (derived largely from his generalization of his earlier results on the rank of real matrices). He produced an alternate proof, based on axioms for certain abstract systems of convex sets, of a result (by Scarf and others) on the number of inequalities required to specify a solution to an integer programming problem. A theorem about this abstract system appears closely related to antimatroids (also known as convex geometries), although the connect has not been fully explored.
Hoffman's work in combinatorics extended our understanding of several classes of graphs. A 1956 lecture by G. Hajós on interval graphs led to Hoffman's characterization of comparability graphs, and later, through collaboration with Paul Gilmore, the GH theorem (also attributed to A. Ghouia-Houri). Motivated by Edmonds' matching algorithm, Hoffman collaborated with Ray Fulkerson and M. McAndrew Hoffman to characterize sets of integers that could correspond to the degrees and bounds on each vertex-pair edge counts of such a graph. They further considered which graphs in the class of all graphs having a prescribed set of degrees and edge count bounds could be transformed by a specific set of interchanges to any other set in the class. The proofs relate intimately to an important concept of Hilbert basis. The paper on self-orthogonal Latin squares, with IBM co-authors Don Coppersmith and R. Brayton, was inspired by a request to schedule a spouse avoiding mixed doubles tournament for a local racquet club. It has the distinction of being the only paper Hoffman would discuss outside of the mathematics community.
Partially ordered sets were a frequent topic of study for Hoffman. The 1977 paper with D. E. Schwartz uses linear programming duality to generalize Green and Kleitman's 1976 generalization of Dilworth's theorem on the decomposition of partially ordered sets, in yet another example of the unifying role duality plays in many combinatorial results.
Throughout his career Hoffman sought simple elegant alternative proofs to established theorems. These alternate proofs often gave rise to generalizations and extensions. In the late 1990s he collaborated with Cao, Chvátal and Vince to develop an alternate proof, using elementary methods rather than linear algebra or Ryser's theorem about square 0-1 matrices.
Hoffman's work on matrix inequalities and eigenvalues are staples in any course on matrix theory. Of particular charm, and in keeping with his fondness for unifying approaches is his 1975 paper on Linear G-Functions. While the proof of the specified Gerschgorin Variation is longer and more complex than others, it covers all the Ostrowski variations and many additional variations as special cases.
Hoffman was an encouraging elder but not an active participant in IBM's development of a series of linear and integer programming products. He did, however, continue research on combinatorial and algebraic aspects of linear programming and linear inequalities, including a delightful abstraction of linear programming duality (1963). He also continued to use properties of linear inequalities to prove (or re-prove, more elegantly) results in convexity.
A collaboration with Shmuel Winograd, also an IBM Fellow in the Mathematics department, produced an efficient algorithm for finding all shortest distances in a directed network, using pseudo-multiplication of matrices. A series of papers on lattice polyhedral (some with Don Schwarts) introduced the concept of lattice polyhedral, which gave rise to yet another instance of combinatorial duality.
Following a collaboration with Ray Fulkerson and Rosa Oppenheim on balanced matrices, Hoffman generalized the Ford-Fulkerson Max Flow – Min Cut result to other cases (flow at nodes, undirected arcs, etc.) by providing a proof of which all previously known instances were special cases. This paper also introduced the concept of (but again, not the name) of total dual integrality, an idea behind most uses of linear programming to prove extremal combinatorial theorems.
Over his career Hoffman studied the class of integer programming problems that were solvable by successively maximizing the variables in some order. One such instance is the complete transportation problem, in the case where the cost coefficient exhibit a particular property discovered more than a century earlier by the French Mathematician Gaspard Monge. This approach, called simply "simple" in the Hoffman paper, was later deemed "greedy" by Edmonds and Fulkerson. The Monge property gives rise to an antimatroid, and through the use of that antimatroid, Hoffman's result is easily extended to the case of incomplete transportation problems. Hoffman re-used the term "greedy" to describe a subclass of 0-1 matrices for which the dual linear program can be solved by the greedy algorithm for all right-hand sides and all objective functions with decreasing (in the variable index) coefficients. Together with Kolen and Sakarovitch he showed that for these matrices, the corresponding integer program has an integer optimal solution for integer data. The elegant and brief 1992 paper provides a characterization on 0-1 matrices for which packing and covering problems can be solved through a greedy approach. It provides a unification of results for shortest path and minimum spanning tree problems. His final paper on this topic "On greedy algorithms, partially ordered sets and submodular functions," co-authored with Dietrich, appeared in 2003.
Hoffman visited and revisited the topic of Graph Spectra, addressing the uniqueness of the triangular association scheme in a 1959 paper, Moore Graphs with diameters 2 and 3 in 1960 (with R Singleton), the polynomial of a graph in 1963, the line graph of a symmetric balanced incomplete block design (with Ray-Chaudhuri) in 1965, connections between Eigenvalues and colorings of a graph (in 1970), connections between Eigenvalues and partitionings of the edges in a Graph in 1972, and many more, including exploring properties of the edge versus path incidence matrix of series parallel graphs (related to greedy packings) with Schieber in 2002.
Hoffman was elected to the National Academy of Sciences in 1982, to the American Academy of Arts and Sciences in 1987, and to the inaugural class of INFORMS Fellows in 2002. Over his long career, Hoffman served on the editorial board of eleven journals and as the founding editor of Linear Algebra and its Applications. In 1992, together with Phillip Wolfe (also of IBM) he was awarded the John von Neumann Theory Prize by ORSA and TIMS[6], predecessors of INFORMS[7]. In presenting the award George Nemhauser recognized Hoffman and Wolfe as the intellectual leaders of the mathematical programming group at IBM. He cited Hoffman for his work in combinatorics and linear programming and for his early work on the computational efficiency of the simplex method during his time at NBS. In August 2000, Hoffman was honored by the Mathematical Programming Society as one of 10 recipients (3 from IBM) of the Founders Award.
In a biography published in an issue of Linear Algebra and its Applications dedicated to Hoffman on the occasion of his sixty-fifth birthday, Uriel Rothblum wrote that "Above and beyond his scholarly and professional contributions, Hoffman has unparalleled ability to enjoy everything he does. He enjoys singing, ping pong, puns, witty stories, and -- possibly as much as anything else -- doing mathematics."
Esther Hoffman died of a blood disease in summer of 1988. Alan married Elinor Hershaft, an interior designer, in 1990. They divorced in 2014. Elinor died in October 2020. Hoffman spent his last years at The Osborn retirement community in Rye, New York. He is survived by his daughters, Eleanor and Elizabeth.
----
Alan Hoffman was a recipient of a number of awards.[7]