Update Newsletter
May 1990, Volume 2, Number 4

Published by The Centre For Systems Science Simon Fraser University Burnaby, BC Canada V5A 1S6 604-291-3455 Editor: Barry Shell shell@cs.sfu.ca

Partying With A Latin Square

This problem actually delighted Kathy. She specializes in Discrete Mathematics-the study of ordinary numbers like 1, 2 and 3. The party game puzzle was a perfect opportunity to apply her favorite mathematical tool: the Latin Square.

To make one, you take some digits and place them in a square with the same number of rows as columns. Each row or column must have a different arrangement of the same numbers. For example, one possible Latin square for the number 4 would look like

1,3,4,2;
4,2,1,3;
2,4,3,1;
3,1,2,4.

As it turns out, this simple concept has tremendous problem solving power; not only for organizing party games, but for more complex tasks like communications networking, computer imaging and experimental design. But as for the party game puzzle, the Latin square told Kathy something else. "I knew that for 5 games and 10 couples I could find a solution. The same for 7 games and 14 couples. But it would be impossible to use Latin squares to find a solution for 12 couples playing 6 games."

It was way back in 1776 when the famous Swiss mathematician, Leonhard Euler (pronounced "Oiler"), pointed out the enigma of the six-digit Latin square. Part of the solution to the party problem involves arranging all the guests into neatly ordered pairs. By putting two Latin squares on top of each other, these pairs are easy to generate.

"Latin squares have a unique and powerful property," says Dr. Heinrich. "For almost any number, you can find two Latin squares that, when superimposed, will generate that number's complete set of ordered pairs. But curiously, this property, called orthogonality, does not exist for the number 6. (It also doesn't work for 2, but that's trivial.)"

Euler noticed this, and, at the time, could not find orthogonal Latin squares for the numbers 10 or 14 either. (It would take a lifetime to write down all the possible Latin squares for numbers this big.) His famous conjecture of 1776 stated that orthogonal Latin squares for all the numbers in the sequence 2,6,10,14,18...etc. (just keep adding 4) did not exist. This idea stood, unproven, for almost two-hundred years until, in 1959, an American mathematician, E. T. Parker, actually found two 10 digit Latin squares that were orthogonal! He and two other mathematicians subsequently developed a theorem proving that orthogonal Latin squares existed for all numbers except 2 and 6.

Such proofs give immense satisfaction to mathematicians like Kathy Heinrich who are comforted by the knowledge that certain arrangements of numbers just exist. But applied scientists need more. Engineers and computer programmers want to use the power of Latin squares to solve real-world problems. Kathy is currently collaborating with Kichul Kim and Prasanna Kumar, engineers at the University of Southern California in Los Angeles. They are using Latin squares to solve problems of memory management in massively parallel computing systems.

Today's most powerful computers are based on large numbers of numerical processors all working at once on extremely large amounts of complex data-images from modern medical body scanners or perhaps weather satellites. The processors and memory units are connected so that any processor can access any of the memory units, but only one at a time. In a single computer time segment, say one billionth of a second, all the processors will call on all the memory units in parallel for super fast computation and image manipulation. The idea is to organize things so that every simultaneous memory access connects each processor with a separate memory unit. A problem occurs in massively parallel systems when, during one time-slice, two processors need data stored in the same memory unit. Called conflicts by engineers, these inefficiencies really slow things down. But Latin squares can easily solve this problem.

Imagine 4 processors that need to access 4 memory units. (In practice the number can be as big as you want.) Say the data exists as a 4 x 4 array of 16 values and each memory unit holds 4 of them. Any Latin square of order 4 shows how to store data in the four memories so that any row or any column of the matrix can be accessed simultaneously by the four parallel processors. If the system needs to grab one row or one column to work on, you can be sure there will never be a conflict with a Latin square arrangement of memory units. But many processing operations require more. For some calculations, diagonals or subarrays within the matrix must be accessed at once. Again, Latin squares can be found that provide memory organizations for conflict free access. Dr. Heinrich and the USC engineers have found an easy way to generate these special Latin squares for any number (where subarray size is n x n and the whole array is n^2 x n^2).

Charles Coburn, a 1989 CSS visiting scientist from the University of Waterloo is working with Kathy on related Latin square problems in applied science. According to Charlie, many mathematicians are finding that engineers and computing scientists are a good source of interesting challenges. Similarly, applied scientists are discovering the wealth of algorithm design tools available from their friendly neighbourhood mathematician. Give her a call today.

More Volume 2

More Update