Two Harpur College math professors have taken the concept of a magic square — a mathematical challenge where every row and column in a square add up to the same number — to the ninth level. In doing so they achieved a new world record.
Matthias Beck, visiting assistant professor, and Dennis Pixton, associate professor, teamed up to compute the volume of a doubly stochastic matrix, also known as a Birkhoff polytope, of size nine. It took them six days and the power of 30 desktop computers to accomplish the task.
Even though making sure that the rows and columns added up to one at each end looks like arithmetic, the puzzle that Beck and Pixton solved was geometrical. Calculating these numbers reveals the volume of the Birkhoff polytope, Beck explained.
“You tell me the size of the square, such as five-by-five squares,” Beck said, “and I’ll give you back the volume, so I want to have a formula that gives you the volume depending on the size.”
Beck said some mathematicians believe there would never be such a formula, but BU’s duo believed otherwise based on what other math researchers had accomplished. Two Princeton researchers developed such a formula for a matrix of eight. With that in mind the two BU mathematicians decided to take the formula one step further.
To do this kind of calculation by hand simply isn’t possible, Beck said, so an algorithm had to be created. That’s where Pixton’s computer expertise came to the rescue.
Pixton started by creating a program that replicated the volume of the eighth Birkhoff polytope and then took it up one more level which greatly expands the computational challenge. “The computational complexity explodes,” said Beck.
Using the Linux operating system, the two linked the math department’s computers to do the computation. Using their newly devised algorithm, Pixton and Beck split the major problem into 1,400 smaller problems to speed the process. What otherwise would have taken nearly a week of computer time took only a few hours.
“What’s interesting is that I don’t think more than one or two people in the department have even noticed that somebody is using their machine to do some very heavy duty calculations,” said Pixton. “The typical computer only uses 1 percent of its capability, so I’m just using idle space.”
As for practical applications of the Birkhoff polytope, Beck observed that a statistician would appreciate that everything adds up to one, which would be considered equal to 100 percent.
And, even if there was no immediate use for the math behind the solution, Erik Pedersen, department chair, noted, “Some extremely theoretical mathematics that developed 350 years ago only started to get some practical applications in the last 10 to 20 years. Now they are the basis for every secret transmission between banks.
“When I started learning mathematics in my first year of University, I thought, ‘There is nothing more useless than this!’ and boy, was I ever wrong!”
The two have written a paper describing their work, and have submitted it to Discrete and Computational Geometry for publication.
