Articles

4.4: Latin Squares - Mathematics


Definition: Latin square

A Latin square of order (n) is an (n imes n) grid filled with (n) symbols so that each symbol appears once in each row and column.

Example (PageIndex{1})

Here is a Latin square of order 4:

Usually we use the integers (1ldots n) for the symbols. There are many, many Latin squares of order (n), so it pays to limit the number by agreeing not to count Latin squares that are "really the same'' as different. The simplest way to do this is to consider reduced Latin squares. A reduced Latin square is one in which the first row is (1ldots n) (in order) and the first column is likewise (1ldots n).

Example (PageIndex{2})

Consider this Latin square:

4231
2413
1342
3124

The order of the rows and columns is not really important to the idea of a Latin square. If we reorder the rows and columns, we can consider the result to be in essence the same Latin square. By reordering the columns, we can turn the square above into this:

1234
3412
2341
4123

Then we can swap rows two and three:

1234
2341
3412
4123

This Latin square is in reduced form, and is essentially the same as the original.

Another simple way to change the appearance of a Latin square without changing its essential structure is to interchange the symbols.

Example (PageIndex{3})

Starting with the same Latin square as before:

4231
2413
1342
3124

we can interchange the symbols 1 and 4 to get:

1234
2143
4312
3421

Now if we swap rows three and four we get:

1234
2143
3421
4312

Notice that this Latin square is in reduced form, but it is not the same as the reduced form from the previous example, even though we started with the same Latin square. Thus, we may want to consider some reduced Latin squares to be the same as each other.

Definition: isotopic and Isotopy Classes

Two Latin squares are isotopic if each can be turned into the other by permuting the rows, columns, and symbols. This isotopy relation is an equivalence relation; the equivalence classes are the isotopy classes.

Latin squares are apparently quite difficult to count without substantial computing power. The number of Latin squares is known only up to (n=11). Here are the first few values for all Latin squares, reduced Latin squares, and non-isotopic Latin squares (that is, the number of isotopy classes):

(n)AllReducedNon-isotopic
1111
2211
31211
457642
5161280562

How can we produce a Latin square? If you know what a group is, you should know that the multiplication table of any finite group is a Latin square. (Also, any Latin square is the multiplication table of a quasigroup.) Even if you have not encountered groups by that name, you may know of some. For example, considering the integers modulo (n) under addition, the addition table is a Latin square.

Example (PageIndex{4})

Example 4.3.6 Here is the addition table for the integers modulo 6:

012345
123450
234501
345012
450123
501234

Example 4.3.7 Here is another way to potentially generate many Latin squares. Start with first row (1,ldots, n). Consider the sets (A_i=[n]ackslash{i}). From exercise 1 in section 4.1 we know that this set system has many sdrs; if (x_1,x_2,ldots,x_n) is an sdr, we may use it for row two. In general, after we have chosen rows (1,ldots,j), we let (A_i) be the set of integers that have not yet been chosen for column (i). This set system has an sdr, which we use for row (j+1).

Definition 4.3.8 Suppose (A) and (B) are two Latin squares of order (n), with entries (A_{i,j}) and (B_{i,j}) in row (i) and column (j). Form the matrix (M) with entries (M_{i,j}=(A_{i,j},B_{i,j})); we will denote this operation as (M=Acup B). We say that (A) and (B) are orthogonal if (M) contains all (n^2) ordered pairs ((a,b)), (1le ale n), (1le ble n), that is, all elements of ({0,1,ldots,n-1} imes{0,1,ldots,n-1}).

As we will see, it is easy to find orthogonal Latin squares of order (n) if (n) is odd; not too hard to find orthogonal Latin squares of order (4k), and difficult but possible to find orthogonal Latin squares of order (4k+2), with the exception of orders (2) and (6). In the 1700s, Euler showed that there are orthogonal Latin squares of all orders except of order (4k+2), and he conjectured that there are no orthogonal Latin squares of of order (6). In 1901, the amateur mathematician Gaston Tarry showed that indeed there are none of order (6), by showing that all possibilities for such Latin squares failed to be orthogonal. In 1959 it was finally shown that there are orthogonal Latin squares of all other orders.

Theorem 4.3.9

There are pairs of orthogonal Latin squares of order (n) when (n) is odd.

Proof

This proof can be shortened by using ideas of group theory, but we will present a self-contained version. Consider the addition table for addition mod (n):

0(cdots)(j)(cdots)(n-1)
00(cdots)(j)(cdots)(n-1)
(vdots)
(i)(i)(cdots)(i+j)(cdots)(n+i-1)
(vdots)
(n-1)(n-1)(cdots)(n+j-1)(cdots)(n-2)

We claim first that this (without the first row and column, of course) is a Latin square with symbols (0,1,ldots,n-1). Consider two entries in row (i), say (i+j) and (i+k). If (i+jequiv i+j pmod{n}), then (jequiv k), so (j=k). Thus, all entries of row (i) are distinct, so each of (0,1,ldots,n-1) appears exactly once in row (i). The proof that each appears once in any column is similar. Call this Latin square (A). (Note that so far everything is true whether (n) is odd or even.)

Now form a new square (B) with entries (B_{i,j}=A_{2i,j}=2i+j), where by (2i) and (2i+j) we mean those values mod (n). Thus row (i) of (B) is the same as row (2i) of (A). Now we claim that in fact the rows of (B) are exactly the rows of (A), in a different order. To do this, it suffices to show that if (2iequiv 2kpmod{n}), then (i=k). This implies that all the rows of (B) are distinct, and hence must be all the rows of (A).

Suppose without loss of generality that (ige k). If (2iequiv 2kpmod{n}) then (ndivides 2(i-k)). Since (n) is odd, (ndivides (i-k)). Since (i) and (k) are in (0,1,ldots,n-1), (0le i-kle n-1). Of these values, only (0) is divisible by (n), so (i-k=0). Thus (B) is also a Latin square.

To show that (Acup B) contains all (n^2) elements of ({0,1,ldots,n-1} imes{0,1,ldots,n-1}), it suffices to show that no two elements of (Acup B) are the same. Suppose that ((i_1+j_1,2i_1+j_1)=(i_2+j_2,2i_2+j_2)) (arithmetic is mod (n)). Then by subtracting equations, (i_1=i_2); with the first equation this implies (j_1=j_2).

(square)

Example 4.3.10 When (n=3), $$left[matrix{ 0&1&2cr 1&2&0cr 2&0&1cr} ight]cup left[matrix{ 0&1&2cr 2&0&1cr 1&2&0cr} ight]= left[matrix{ (0,0)&(1,1)&(2,2)cr (1,2)&(2,0)&(0,1)cr (2,1)&(0,2)&(1,0)cr} ight]. $$

One obvious approach to constructing Latin squares, and pairs of orthogonal Latin squares, is to start with smaller Latin squares and use them to produce larger ones. We will produce a Latin square of order (mn) from a Latin square of order (m) and one of order (n).

Let (A) be a Latin square of order (m) with symbols (1,ldots,m), and (B) one of order (n) with symbols (1,ldots,n). Let (c_{i,j}), (1le ile m), (1le jle n), be (mn) new symbols. Form an (mn imes mn) grid by replacing each entry of (B) with a copy of (A). Then replace each entry (i) in this copy of (A) with (c_{i,j}), where (j) is the entry of (B) that was replaced. We denote this new Latin square (A imes B). Here is an example, combining a (4 imes 4) Latin square with a (3 imes 3) Latin square to form a (12 imes 12) Latin square: }

(1)(2)(3)(4)
(2)(3)(4)(1)
(3)(4)(1)(2)
(4)(1)(2)(3)
( imes)
(1)(2)(3)
(2)(3)(1)
(3)(1)(2)
(=)
(c_{1,1})(c_{2,1})(c_{3,1})(c_{4,1})
(c_{2,1})(c_{3,1})(c_{4,1})(c_{1,1})
(c_{3,1})(c_{4,1})(c_{1,1})(c_{2,1})
(c_{4,1})(c_{1,1})(c_{2,1})(c_{3,1})
(c_{1,2})(c_{2,2})(c_{3,2})(c_{4,2})
(c_{2,2})(c_{3,2})(c_{4,2})(c_{1,2})
(c_{3,2})(c_{4,2})(c_{1,2})(c_{2,2})
(c_{4,2})(c_{1,2})(c_{2,2})(c_{3,2})
(c_{1,3})(c_{2,3})(c_{3,3})(c_{4,3})
(c_{2,3})(c_{3,3})(c_{4,3})(c_{1,3})
(c_{3,3})(c_{4,3})(c_{1,3})(c_{2,3})
(c_{4,3})(c_{1,3})(c_{2,3})(c_{3,3})
(c_{1,2})(c_{2,2})(c_{3,2})(c_{4,2})
(c_{2,2})(c_{3,2})(c_{4,2})(c_{1,2})
(c_{3,2})(c_{4,2})(c_{1,2})(c_{2,2})
(c_{4,2})(c_{1,2})(c_{2,2})(c_{3,2})
(c_{1,3})(c_{2,3})(c_{3,3})(c_{4,3})
(c_{2,3})(c_{3,3})(c_{4,3})(c_{1,3})
(c_{3,3})(c_{4,3})(c_{1,3})(c_{2,3})
(c_{4,3})(c_{1,3})(c_{2,3})(c_{3,3})
(c_{1,1})(c_{2,1})(c_{3,1})(c_{4,1})
(c_{2,1})(c_{3,1})(c_{4,1})(c_{1,1})
(c_{3,1})(c_{4,1})(c_{1,1})(c_{2,1})
(c_{4,1})(c_{1,1})(c_{2,1})(c_{3,1})
(c_{1,3})(c_{2,3})(c_{3,3})(c_{4,3})
(c_{2,3})(c_{3,3})(c_{4,3})(c_{1,3})
(c_{3,3})(c_{4,3})(c_{1,3})(c_{2,3})
(c_{4,3})(c_{1,3})(c_{2,3})(c_{3,3})
(c_{1,1})(c_{2,1})(c_{3,1})(c_{4,1})
(c_{2,1})(c_{3,1})(c_{4,1})(c_{1,1})
(c_{3,1})(c_{4,1})(c_{1,1})(c_{2,1})
(c_{4,1})(c_{1,1})(c_{2,1})(c_{3,1})
(c_{1,2})(c_{2,2})(c_{3,2})(c_{4,2})
(c_{2,2})(c_{3,2})(c_{4,2})(c_{1,2})
(c_{3,2})(c_{4,2})(c_{1,2})(c_{2,2})
(c_{4,2})(c_{1,2})(c_{2,2})(c_{3,2})

Theorem 4.3.11

f (A) and (B) are Latin squares, so is (A imes B).

Proof

Consider two symbols (c_{i,j}) and (c_{k,l}) in the same row. If the positions containing these symbols are in the same copy of (A), then (i ot=k), since (A) is a Latin square, and so the symbols (c_{i,j}) and (c_{k,l}) are distinct. Otherwise, (j ot=l), since (B) is a Latin square. The argument is the same for columns.

(square)

Remarkably, this operation preserves orthogonality:

Theorem 4.3.12

If (A_1) and (A_2) are Latin squares of order (m), (B_1) and (B_2) are Latin squares of order (n), (A_1) and (A_2) are orthogonal, and (B_1) and (B_2) are orthogonal, then (A_1 imes B_1) is orthogonal to (A_1 imes B_2).

Proof

We denote the contents of (A_i imes B_i) by (C_i(w,x,y,z)), meaning the entry in row (w) and column (x) of the copy of (A_i) that replaced the entry in row (y) and column (z) of (B_i), which we denote (B_i(y,z)). We use (A_i(w,x)) to denote the entry in row (w) and column (x) of (A_i).

Suppose that ((C_1(w,x,y,z),C_2(w,x,y,z))=(C_1(w',x',y',z'),C_2(w',x',y',z'))), where ((w,x,y,z) ot=(w',x',y',z')). Either ((w,x) ot=(w',x')) or ((y,z) ot=(y',z')). If the latter, then ((B_1(y,z),B_2(y,z))= (B_1(y',z'),B_2(y',z'))), a contradiction, since (B_1) is orthogonal to (B_2). Hence ((y,z)=(y',z')) and ((w,x) ot=(w',x')). But this implies that ((A_1(w,x),A_2(w,x))=(A_1(w',x'),A_2(w',x'))), a contradiction. Hence (A_1 imes B_1) is orthogonal to (A_1 imes B_2).

(square)

We want to construct orthogonal Latin squares of order (4k). Write (4k=2^mcdot n), where (n) is odd and (mge 2). We know there are orthogonal Latin squares of order (n), by theorem 4.3.9. If there are orthogonal Latin squares of order (2^m), then by theorem 4.3.12 we can construct orthogonal Latin squares of order (4k=2^mcdot n).

To get a Latin square of order (2^m), we also use theorem 4.3.12. It suffices to find two orthogonal Latin squares of order (4=2^2) and two of order (8=2^3). Then repeated application of theorem 4.3.12 allows us to build orthogonal Latin squares of order (2^m), (mge 2).

Two orthogonal Latin squares of order 4:

$$left[matrix{ 1&2&3&4cr 2&1&4&3cr 3&4&1&2cr 4&3&2&1cr} ight] left[matrix{ 1&2&3&4cr 3&4&1&2cr 4&3&2&1cr 2&1&4&3cr } ight], $$

and two of order 8:

$$ left[matrix{ 1&3&4&5&6&7&8&2cr 5&2&7&1&8&4&6&3cr 6&4&3&8&1&2&5&7cr 7&8&5&4&2&1&3&6cr 8&7&2&6&5&3&1&4cr 2&5&8&3&7&6&4&1cr 3&1&6&2&4&8&7&5cr 4&6&1&7&3&5&2&8cr } ight] left[matrix{ 1&4&5&6&7&8&2&3cr 8&2&6&5&3&1&4&7cr 2&8&3&7&6&4&1&5cr 3&6&2&4&8&7&5&1cr 4&1&7&3&5&2&8&6cr 5&7&1&8&4&6&3&2cr 6&3&8&1&2&5&7&4cr 7&5&4&2&1&3&6&8cr } ight]. $$


The 4x4 Latin Squares and Alphabetical Patterns

The fundamental 4x4 magic carpet can be represented by dots and spaces. Any line in any direction of length four contains two dots, i.e., it sums to 2 any selected 4x4 area is a pan-magic pattern. We can take four samples of this large carpet, rotate two of them, and make the only four possible order four magic carpets.

Alphabetical Subsitution.

Because they look somewhat like letters of the alphabet they are given a letter to identify them.

The Composite Alphabetical Magic Carpet

The dot in each of the above squares is replaced with its own letter. The four squares are then combined to make the composite square on the left and then the larger carpet on the right.

Only one composite pattern exists. This one composite square underlies all order 4 pan-magic squares. Any 4x4 area contains each letter twice in every row, every line, and every diagonal. To make an actual 4x4 magic square the letters in this square would be replaced, respectively by 8, 4, 2, and 1 (see Main 4x4 Page).

Neat Pattern.

When the pattern is repeated, a large magic carpet emerges - pleasing and symmetrical - which makes the interesting colored pattern on the left.

Not a Latin Square

Strictly speaking this is not a "Latin Square". A Latin Square for order N uses N letters N times and each row and each column contains one of each letter. The above square can be converted into two Latin Squares.

Two 4x4 Latin Squares

The illustration below combines two 4x4 Latin Squares into a single, so-called Graeco-Latin square For convenience it employs Upper and Lower case Roman letters instead of using both Roman and Greek characters. The letters in the new square are derived from the square above:

A when neither S nor N are present
B when N is present
C when S is present
D when both S and N are present
a when neither C nor A are present
b when C is present
c when A is present
d when both C and A are present

A B C D
C D A B
B A D C
D C B A
+
a d c b
d a b c
b c d a
c b a d
=
Aa Bd Cc Db
Cd Da Ab Bc
Bb Ac Dd Ca
Dc Cb Ba Ad

Not Pan-Magic.

Inspection of the resulting Graeco-Latin shows that that the rows and columns are inevitably " Magic " - they do contain one of each letter. This is, however, not true for any of the diagonals they can only add up to the magic sum for appropriately selected numerical substitutions.

Limited Value for 4x4 Latin Squares.

Because of this limitation, Latin Squares are of only limited use in constructing 4x4 pan-magic squares. There are two other possible 4x4 alphabetical squares and all three are shown below. The third is not even Latin in that, now, only the diagonals contain one of each letter.


Alternative versions of orthogonality

(f) Mutually orthogonal partial latin squares

Two partial latin squares (not necessarily distinct) are orthogonal if, when they are juxtaposed, no ordered pair of elements appears more than once. A collection of partial latin squares is called r-compatible if each has r occupied cells and these occupied cells are in corresponding positions.

It follows that, in particular, a partial latin square of order n which has only n of its cells occupied is orthogonal to and n-compatible with itself. Thus, most interest is in partial n × n latin squares which have more than n cells filled. This concept, which is due to Abdel-Ghaffar(1996) , arose in connection with coding theory: namely, in minimizing the retrieval time for items belonging to a large file of data stored on several disks.

Let Mn(r) denote the maximum number of pairwise orthogonal r-compatible partial Latin squares. For the above application, Abdel-Ghaffar was interested in finding bounds for Mn(r) when r > n. He showed that, for n + 1 ≤ rn 2 ,

Note that this result implies in particular that Mn(n 2 ) ≤ n − 1. Abdel-Ghaffar showed further that, for n +1 ≤ r ≤ 2n, Mn(r) = ⌊r(r − 1)/2(rn)⌋ − 2 and he constructed squares which meet the latter bound.

In the coding theory application mentioned earlier, the above bounds on Mn(r) give bounds on the best possible retrieval time.


4.4: Latin Squares - Mathematics

As a reminder, we should mention here that the order of a magic square is the number of cells on one of its sides.

Recall that the earliest recorded fourth-order magic square appears to have been found in an inscription at Khajuraho, India dating to about 1000-1100 A.D. It was of the form

We will examine a method to create a 44 magic square however, this method does not generate the square found in India. (This is not the only way, but it is quick and sure.) We begin by creating a 44 square matrix and then we draw two diagonal lines to get a figure as follows.


We then start at the upper left corner to put the number 1,2,3. 14,15,16 into the cells. However, we do not put a number in any cell where the diagonal line appears. We start with 1, but that cell has a diagonal line in it, so we go to the next cell which is blank and enter a 2, then we put a 3 in the next cell. The last cell in the first row has a diagonal line, so we do not write in the 4. We go to the next row and enter 5 in the first cell, which is blank, the next two cells have a diagonal line, so we skip 6 and 7. We continue this pattern until we get to the last cell in the last row. Our square will look like this:

Now we begin in the lower right-hand corner and work our way back using the numbers 1,4,6,7,10,11,13, and 16. We put these number in the cells which originally had the diagonal lines starting with 1 in the lower right-hand corner. Our finished product looks like this:

We see that in our finished square every row, column and diagonal sums to the magic number 34, which is found, as we mentioned above, by calculating 4(4 2 + 1)/2.

Once we have this square, we can carefully rearrange the rows and columns to get other 44 magic squares. Below are some rearrangements of our original 44 magic square.

Notice in the rearrangement that the numbers in our original 44 magic square stay together. That is, the numbers 16,2,3,13 that appear in the first row will always be together, in some order, in a row or column of a new square. This is true of all of the other sets of four numbers. For example, if you have a row or column that contains the numbers 3 and 6, that row or column must also have the numbers 10 and 15.

In our rearranged examples above, the last magic square is of particular historical interest in mathematics and art. This magic square appears in the background of the engraving Melencolia by Albrecht Dürer, which he did in 1514. Notice the numbers 15 and 14 (the date of the engraving) appear together in the center of the bottom row. This engraving can be seen in many places. A convenient one is the WebMuseum. If this link does not get you there try the front door. The main entry point to the WebMuseum is the Pyramide.


Exercises 4.3

Ex 4.3.1 Show that there is only one reduced Latin square of order 3.

Ex 4.3.2 Verify that the isotopy relation is an equivalence relation.

Ex 4.3.3 Find all 4 reduced Latin squares of order 4. Show that there are at most 2 isotopy classes for order 4.

Ex 4.3.4 Show that the second set system defined in example 4.3.7 has an sdr as claimed.

Ex 4.3.5 Show that there are no orthogonal Latin squares of order 2.

Ex 4.3.6 Find the two orthogonal Latin squares of order $5$ as described in theorem 4.3.9. Show your answer as in example 4.3.10.

Ex 4.3.7 Prove that to construct orthogonal Latin squares of order $2^m$, $mge2$, it suffices to find two orthogonal Latin squares of order $4=2^2$ and two of order $8=2^3$.

Ex 4.3.8 An $n imes n$ Latin square $A$ is symmetric if it is symmetric around the main diagonal, that is, $A_=A_$ for all $i$ and $j$. It is easy to find symmetric Latin squares: every addition table modulo $n$ is an example, as in example 4.3.6. A Latin square is idempotent if every symbol appears on the main diagonal. Show that if $A$ is both symmetric and idempotent, then $n$ is odd. Find a $5 imes 5$ symmetric, idempotent Latin square.

Ex 4.3.9 The transpose $A^ op$ of a Latin square $A$ is the reflection of $A$ across the main diagonal, so that $A_^ op=A_$. A Latin square is self-orthogonal if $A$ is orthogonal to $A^ op$. Show that there is no self-orthogonal Latin square of order 3. Find one of order 4.


Researchers in combinatorial design theory and areas of statistics such as design and analysis of experiments. The book may also be of interest to amateur mathematicians interested in magic squares, in designing games tournaments and/or in latin squares related to Sudoku puzzles

Chapter 1: Elementary properties

  • 1.1 The multiplication table of a quasigroup
  • 1.2 The Cayley table of a group
  • 1.3 Isotopy
  • 1.4 Conjugacy and parastrophy
  • 1.5 Transversals and complete mappings
  • 1.6 Latin subsquares and subquasigroups

Chapter 2: Special types of latin square

  • 2.1 Quasigroup identities and latin squares
  • 2.2 Quasigroups of some special types and the concept of generalized associativity
  • 2.3 Triple systems and quasigroups
  • 2.4 Group-based latin squares and nuclei of loops
  • 2.5 Transversals in group-based latin squares
  • 2.6 Complete latin squares

Chapter 3: Partial latin squares and partial transversals

  • 3.1 Latin rectangles and row latin squares
  • 3.2 Critical sets and Sudoku puzzles
  • 3.3 Fuchs’ problems
  • 3.4 Incomplete latin squares and partial quasigroups
  • 3.5 Partial transversals and generalized transversals

Chapter 4: Classification and enumeration of latin squares and latin rectangles

  • 4.1 The autotopism group of a quasigroup
  • 4.2 Classification of latin squares
  • 4.3 History of the classification and enumeration of latin squares
  • 4.4 Enumeration of latin rectangles
  • 4.5 Enumeration of transversals
  • 4.6 Enumeration of subsquares

Chapter 5: The concept of orthogonality

  • 5.1 Existence questions for incomplete sets of orthogonal latin squares
  • 5.2 Complete sets of orthogonal latin squares and projective planes
  • 5.3 Sets of MOLS of maximum and minimum size
  • 5.4 Orthogonal quasigroups, groupoids and triple systems
  • 5.5 Self-orthogonal and other parastrophic orthogonal latin squares and quasigroups
  • 5.6 Orthogonality in other structures related to latin squares

Chapter 6: Connections between latin squares and magic squares

  • 6.1 Diagonal (or magic) latin squares
  • 6.2 Construction of magic squares with the aid of orthogonal latin squares
  • 6.3 Additional results on magic squares
  • 6.4 Room squares: their construction and uses

Chapter 7: Constructions of orthogonal latin squares which involve rearrangement of rows and columns


Case 3 Section

In this case, we have different levels of both the row and the column factors. Again, in our factory scenario, we would have different machines and different operators in the three replicates. In other words, both of these factors would be nested within the replicates of the experiment.

We would write this model as:

Here we have used nested terms for both of the block factors representing the fact that the levels of these factors are not the same in each of the replicates.

The analysis of variance table would include:


Anything but square: from magic squares to Sudoku

There is an ancient Chinese legend that goes something like this. Some three thousand years ago, a great flood happened in China. In order to calm the vexed river god, the people made an offering to the river Lo, but he could not be appeased. Each time they made an offering, a turtle would appear from the river. One day a boy noticed marks on the back of the turtle that seemed to represent the numbers 1 to 9. The numbers were arranged in such a way that each line added up to 15. Hence the people understood that their offering was not the right amount.

The markings on the back of the turtle were in fact a magic square. A magic square is a square grid filled with numbers, in such a way that each row, each column, and the two diagonals add up to the same number. Here's what the magic square from the Lo Shu would have looked like. It has three rows and three columns, and if you add up the numbers in any row, column or diagonal, you always get 15.

Here is a partial construction of a 5 by 5 magic square. Starting from 1, I have filled in the numbers up to 10. There is no space northeast of the 1, so I have put the 2 in the bottom row, followed by the 3. Again, because the 3 is on the edge, the 4 goes on the opposite side. The 6 should go in the cell where the 1 is, but because this cell is occupied, I put the 6 immediately below the 5 and continued up to 10. Try completing the square and then try making some of your own.

While this, known as the Siamese method, is probably the best known method for making magic squares, other methods do exist. The German schoolmaster Johann Faulhaber published a method similar to the Siamese method before it was discovered by De Le Loubere. Another way is the Lozenge method by John Horton Conway, a prolific British mathematician. Proving that these methods work can be done using algebra, but it's not easy!

Magic squares of even order

Although the Siamese method can be used to generate a magic square for any odd number, there is no simple method that works for all magic squares of even order. Fortunately, there is a nice method that we can use if the order of the square is an even number divisible by 4. (For those that are interested, the LUX method was invented by J. H. Conway to deal with even numbers that are not divisible by 4).

Instead of saying "numbers that are divisible by 4", mathematicians usually say "numbers of the form 4k". For example, 12 is of the form 4k, because you can replace k with 3. Using the same idea, numbers that give a remainder of 2 when you divide them by 4 can be called numbers of the form 4k + 2.

So start by picking the order of the square, making sure that it's of the form 4k, and number the cells 1 to (4k) 2 starting at the top left and working along the rows. Then split the square up into 4 by 4 subsquares, and mark the numbers that lie on the main diagonals of each subsquare. In the example, these are the coloured numbers the order of the square is 4, so the only 4 by 4 subsquare is the square itself.

Now switch the lowest marked number with the highest marked number, the second lowest marked number with the second highest marked number, and so on. Another way of saying this is that if the magic square has order n, swap the numbers that add up to n 2 + 1. In this particular example, the order is 4, so we have to swap the numbers that add up to 17: 1 and 16, 4 and 13, 6 and 11, 7 and 10.

If you flip this magic square over, it is identical to the one drawn by the famous German artist, Albrecht Dürer. You can see it in the corner of his engraving Melencolia.

A Knight's Tale

As any chess player will know, an order 8 magic square has the same number of cells as a chessboard. This similarity means that we can create a special type of magic square based on the moves of a chesspiece.

The knight is an interesting piece, because unlike the other pieces, it does not move vertically, horizontally or diagonally along a straight line. Instead, the knight moves in an L-shape as shown in the diagram. But is it possible for a knight that moves in this way to visit every square on the chessboard exactly once?

Using the concept of the knight's tour William Beverley managed to produce a magic square, as shown below. Cells are numbered in sequence, as the knight visits them. Although the rows and columns all add up to 260, the main diagonals do not, so strictly speaking it is a semi-magic square. In fact, a magic square based on a knight's tour is often called a magic tour, so what Beverley produced in 1848 is a semi-magic tour!

At first glance, it seems that the following magic square by Feisthamel fits the bill. The rows, columns and diagonals all sum to 260. Unfortunately, it is only a partial knight's tour, as there is a jump from 32 to 33.

So when is it possible to turn a knight's tour into a magic square? In 2003, Stertenbrink and Meyrignac finally solved this problem by computing every possible combination. They found 140 semi-magic tours, but no magic tours. Checkmate!

Latin Squares

Latin squares are the true ancestors of Sudoku. You can find examples of Latin squares in Arabic literature over 700 years old. They were discovered by Euler a few centuries later, who saw them as a new type of magic square, and it's thanks to him that we call them Latin squares.

Latin squares are grids filled with numbers, letters or symbols, in such a way that no number appears twice in the same row or column. The difference between a magic square and a Latin square is the number of symbols used. For example, there are 16 different numbers in a 4 by 4 magic square, but you only need 4 different numbers or letters to make a 4 by 4 Latin square.

Now if we look at the bottom three boxes, one of the rows already has 6 numbers. I've called the empty cells A, B and C (in order from left to right), and the numbers that are missing are 3, 7 and 8. If you look at cell C, the only number that can go in it is 7. That's because the column that C lies in already contains 3 and 8.

Finding A and B is now pretty simple. There's already a 3 in the same column as B, so B has to be 8. That means A must be 3. Solving the rest of the puzzle is a bit trickier, but well worth the effort.

The Sudoku craze has swept across the globe, and it shows no signs of slowing. Several variations have developed from the basic theme, such as 16 by 16 versions and multi-grid combinations (you can try a duplex difference sudoku in the Plus puzzle). But as with magic squares and Latin squares, the popularity of Sudoku will depend on whether they can continue to offer new challenges.


Latin Squares Design

On this webpage, we describe the basic concepts of Latin Squares designs. Additional information can be found on the following webpages:

A Latin Square design has two nuisance factors (Rows and Cols) and one treatment factor, each of which has the same number of levels, denoted r. There are no replications and no interactions. If we denote the possible treatment effects by Latin letters, then all the rows and columns are permutations of these letters (with no repeated rows and no repeated columns).

For r = 4 and r = 5, possible configurations are:

Figure 1 – Latin Square Configurations

Note that there are many possible 4 × 4 or larger configurations, although many of these are equivalent in the sense that one can be obtained from another by interchanging one or more rows and/or columns. In fact, there are 4 non-equivalent 4 × 4 configurations and 56 non-equivalent 5 × 5 configurations. It turns out that all the 3 × 3 configurations are equivalent.

Example 1: A factory wants to determine whether there is a significant difference between four different methods of manufacturing an airplane component, based on the number of millimeters of the part from the standard measurement. Four operators and four machines are assigned to the study. A Latin Squares design is used to account for operators and machines nuisance factors.

The representation of a Latin Squares design is shown in Figure 2 where A, B, C and D are the four manufacturing methods and the rows correspond to the operators and the columns correspond to the machines.

Figure 2 – Latin Squares Representation

For our purposes, we will use the following equivalent representations (see Figure 3):

Figure 3 – Latin Squares Design

The linear model of the Latin Squares design takes the form:

An Excel implementation of the design is shown in Figure 4.

Figure 4 – Latin Square Analysis

The left side of Figure 4 contains the data range in Excel format (equivalent to the left side of Figure 3). The middle part of Figure 4 contains the means of each of the factor levels. Representative formulas used are shown in Figure 5.

Cell Factor Formula
L4 Row =AVERAGE(H4:K4)
H8 Column =AVERAGE(H4:H7)
H11 Treatment =AVERAGEIF($B$8:$E$11,H10,$B$4:$E$7)

Figure 5 – Formulas for factor means

The right side of Figure 4 contains the ANOVA analysis. The degrees of freedom for all three factors is 3 (cells P4, P5, P6), equal to the number to r – 1, as calculated by =COUNT(B4:B7)-1. dfT = r 2 – 1 = 15, while dfE = (r–1)(r–2) = 6.

Formulas for the sum of squares (SS) terms are shown in Figure 6. The other values in Figure 4 are calculated in the usual way.

Cell Factor Formula
O5 Treatment =DEVSQ(H11:K11)*(P5+1)
O6 Rows =DEVSQ(L4:L7)*(P6+1)
O7 Columns =DEVSQ(H8:K8)*(P7+1)
O8 Error =O9-SUM(O5:O7)
O9 Total =DEVSQ(H4:K7)

Figure 6 – Formulas for sums of squares

We see from Figure 4 that there is a significant difference between the four methods (p-value = 0.03345 < .04 = α). There is no significant difference between the operators or between the machines, and so blocking on these factors may not have been necessary in this case.

The analysis is similar when the standard (i.e. stacked) input format is used (see Figure 7). E.g. the mean for row 1 (cell G4) can be calculated by the formula

The mean for treatment A (cell I4) can be calculated by using the formula

Figure 7 – Latin Square Analysis for stacked format

Observation: In the usual three-factor design, the minimum sample size would be 4 × 4 × 4 = 64, while in this design we only require a sample size of 4 × 4 = 16.

Observation: Latin Squares can also be used for a three-factor ANOVA when there are no replications, even when the row and column factors are not nuisance factors, but factors of interest.


Disclaimer

Registration on or use of this site constitutes acceptance of our User Agreement, Privacy Policy and Cookie Statement, and Your California Privacy Rights (User Agreement updated 1/1/21. Privacy Policy and Cookie Statement updated 5/1/2021).

© 2021 Advance Local Media LLC. All rights reserved (About Us).
The material on this site may not be reproduced, distributed, transmitted, cached or otherwise used, except with the prior written permission of Advance Local.

Community Rules apply to all content you upload or otherwise submit to this site.


Latin Square in C++

In this tutorial, we are going to learn about the Latin square.

The latin square is a matrix (3 x 3) in the form

If you carefully observe the pattern of the above matrix, then you will find out that the last number of the previous row comes as the first element of the next row.

We have to write the program that generates the above matrix for the input n.

Let's see the steps to write the program for the generation of the latin square.

  • Initialise the n with any number you like.
  • Initialise a number with the value n + 1 call it as mid.
  • Write a loop that iterates from 1 to n both inclusive.
    • Assign the value of mid to a temp variable.
    • Write a loop until temp reaches to the value n.
      • Print the temp.
      • Print the value.

      If you run the above code, then you will get the following result.


      Watch the video: Euler Squares - Numberphile (December 2021).