Objectives

Latin Squares can be a very useful tool in the fields of combinatorics and experimental design.

This Tutorial will give a quick introduction to what Latin Squares are and why they are useful.

Goals:

1. Understand what a Latin Square is

2. Learn how Mutually Orthogonal Latin Squares can be combined to create Orthogonal Arrays

1

The definition of an Latin Square is as follows.

An n x n array with n different characters occuring exactly once in each row and column.

Because of it's simple yet strict definition Latin Squares are quite easy to understand.

Let's look at a small example.

2

A Latin Square of size n = 3

3

When the first row and column of a Latin Square are in their natural order the Latin Square is said to be reduced.

Note that Latin Squares of size n≤4 have more than 1 reduced form.

By permuting (reordering) the rows and columns of a Latin Square a different Latin Square can be created.

Let's take a look at how permutation can be used to get a Latin Square to it's reduced form.

4

A Latin Square of size n = 4

5

A Latin Square of size n = 4

6

A Latin Square of size n = 4

7

Here are four different reduced Latin Squares of size n = 4. Is there a way to permute one of these arrays into any of the others?

8

The answer is no. There is no way to permute a reduced Latin Square into a different reduced Latin Square.

9

Robert Mandl suggested using Latin Squares as a basis for designing tests for compilers.

To do this Mutually Orthogonal Latin Squares are needed.

Latin Squares are said to be orthogonal to each other if when one is superimposed on the other the ordered pairs formed by combining the corresponding entries consist of all possible pairs.

A simple example should help make this property more clear.

10

Here is an example of a set of two mutually orthogonal Latin Squares. It can be denoted MOLS(5,2) where 5 is the size of the Latin Squares and 2 is the number of squares in the set.

11

Superimposed MOLS(5,2)

12

When dealing with a Latin square with a size that is a prime number n then the size of the largest possible set of Mutually Orthogonal Latin Squares is equal to n-1.

Creating the set is actually fairly easy if you have a starting Latin Square.

By starting every Latin Square in the set with the first row being in its natural order and then for each of the following rows simple change their order.

Starting with the last example here is how to create the remaining 2 Latin Squares in the set.

13

A Latin Square of size n = 5

14

A Latin Square of size n = 5

15

A Latin Square of size n = 5

16

Following this pattern you can create the set MOLS(n,n-1) where n is a prime number. Here are the Latin Squares of size n = 5 using the fourth and fifth number respectivly.

17

Now by substituting the values of each Latin Square with some relevant parameter you can design a series of tests that check different combinations of those parameters.

This was the key idea within Robert Mandle's 1985 paper.

In his example the Orthogonal Latin Squares were used to create compiler tests. The idea was that testing combinations would be less costly than exhastive testing while being more structured than random testing.

The next step in this direction is to start using Orthogonal Arrays to generate tests (more detail about this later). For now a quick look at how they can be created by using Orthogonal Latin Squares.

18

Because of the property that all of the pairs formed by superimposing the set of MOLS are unique we can directly take those pairs and create rows of an Orthogonal Array out of them.

To further increase the size of the array add two columns to the orthogonal aray, one to represent which row and which column the pair is from on the original Latin Squares.

The dimensions for the new orthogonal array are N = number of pairwise combinations, k = number of mutually orthagonal latin squares plus 2, s = size of Latin Squares and t = strength of the test (in this case, t=2).

Let's take a look at what this orthogonal array will look like.

19

20

Recap.

This tutorial should give at least a basic understanding of reduced and Mutually Orthogonal Latin Squares.

Because of their simple definition they make a great reference point when heading into more advanced areas of research.

Next:

21