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.A.E. Brouwer & J.H. van Lint, Strongly regular graphs and partial geometries, in: Enumeration and Design - Proc. Silver Jubilee Conf. on Combinatorics, Waterloo, 1982, D.M. Jackson & S.A. Vanstone (eds.) Academic Press, Toronto (1984) 108.
Hoffman died on January 18, 2021, at the age of 96.Biography of Alan J. HoffmanCameron Counts: Alan Hoffman
Early life 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.
Education 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] 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 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."
Early career 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."
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 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 office in the heart of Manhattan.