Latin and Euler Square

In combinatorial argument and experimental design, a Latin square is an n×n array filled with n different symbols in such a way that each symbol occurs exactly once in each row and once in each column. A lot of work has been dedicated towards Euler square. For the last seven to eight decades, it has been widely used in many fields of mathematical research.

The name “LATIN SQUARE “ was proposed by LEONHARD EULER, who used latin characters as symbols. If we move to the history of it, the Korean Mathematician CHOI-SEOKJEONG first published an example of latin square to construct a magic square, predating EULER.

Now, I'm constructing a latin square as an example. If we want to make a 3×3 latin square with three letters A, B, C then it will look like fig-1 below.

In general notation , an n×n Latin square is written as a triple (r, c, s) where r represents row, c represents column and s is the symbol on that box. Thus, we obtain a set of n2triples (in fig.1 n=3) called orthogonal array representation.

According to above square, orthogonal array is : {(1,1,A); (1,2,B); (1,3,C); (2,1,C); (2,2,A); (2,3,B); (3,1,B); (3,2,C); (3,3,A)}

(1,1,A) means in 1st row and 1st column, the symbol is A. So, Latin square is a set of n2 triples where 1≤r, c, s ≤ n such that all ordered pairs (r, c) are distinct, (r, s) are distinct and also (c, s) are distinct.

Now, I will come to the discussion about different arrangements related to this kind of squares such as,

(i) Latin rectangle: It is none other than a generalization of Latin square in where n columns and n different symbols are present but number of rows is ≤n . Each value still appears atmost once in each row and column. I have shown a example of latinrectangle in fig. 2 below.

The above example is of a 3×4 Latin rectangle in which each letter appears once in each rowand each column.

(ii) Graeco-Latin Square or Euler Square: It is a type of Latin square of order n over two sets A and B, each consisting of n symbols. It is an arrangement of n2 cells, each cell containing ordered pairs (a, b) such that a is from the set A and b is from the set B. There is an extra condition that neither a nor b will occur more than once in the main diagonals.

For instance, if A is a set of greek letters={ά,β,γ,δ} and B a set of numbers={1,2,3,4}, then Euler square of 4×4 will be like in fig. 3 below.

Here, I will mainly focus on the Euler square. Now,

we will see for what value of n an Euler square is possible. For n=2, an Euler square is impossible, because if we designed it like in fig. 4

Here, A and B appears once in each row and column, 1 and 2 also appears once in each rowand column but the diagonal elements are equal. So, Graeco Latin square (later known asEuler squares) of order 2×2 are impossible. For n=3, it is possible. This will be like fig. 5 below.

(K= King, Q=Queen, J=Jack and there is heart, spade, diamonds of cards) . Each of the combinations appears once in each row , column and main diagonal.For 4×4, I have shown am example in fig. 3 .

Obviously, the question arises in our mind, what will be for n=5 & 6. A 5×5 Euler square is possible and it

is shown below.

But for 6×6, it is quite difficult and so difficult that no one has been able to find a way to do it. Even the famous mathematician LEONHARD EULER tried hard to find an arrangement but failed. He designed squares for 7×7, 8×8 but failed to do anything for 6×6.

Now, I want to give you a glimpse of a problem closely related to EULER SQUARE: THE 36

OFFICERS PROBLEM. The statement is:“Suppose there is a war. Someone is the commander of an army that consists of six regiments, each containing six officers of six different ranks. Can one arrange the officers in a 6×6 square so that each row and each column of the square holds only one officer from each regiment and only one officer from each rank?”

Pictorial representation of this problem is nothing but a 6×6 Euler square which remains impossible to draw.

After observing that for n=2 & 6, it is impossible to design a Graeco-Latin square, Euler conjectured that "It is impossible to draw a n×n Graeco-Latin square where n is of the form 4k+2 (where k is a positive integer). But, there was no proof of that and it remained unproven for over 100 years until Gaston Tarry, a famous French mathematician, proved that 6×6 Euler square (Graeco-Latin square)is impossible. Before that Thomas Clausen, assistant of Heinrich Schumacher (Astronomer in Altona) divided latin square of order 6 into 17 families and did an exhaustive search in each family. After dividing latin square of 6×6 into 17 families, he gave the theorem "There is no pair of orthogonal Euler square of order 6". He also drew a 10×10 Euler square. In 1959, two famous Indian mathematicians, Raj Chandra Bose and S. S. Shrikhande, designed 14×14,18×18 & 22×22 Euler squares. So, it had already been proven that Euler's conjecture was wrong. Lastly, in 1960, Parker did some research on it and gave conjectured that “If n=(3q-1)/2 and q is a power of an odd prime and q-3 is divisible by 4, then there is a pair of orthogonal latin square of order n." There is no known easily computable formula for the numbers Ln ( n×n latin squares). But there is a upper and lower bound :

The latin square (more precisely, Euler square) has a wide range of applications:

(i) In group theory, latin squares are characterized as being the Cayley tables of quasi groups.

(ii) Latin square that are orthogonal to each other have an application as error correcting codes.

(iii) Mostly it is used in the field of Cryptography (Cryptographic Hash function)

(iv) The famous Sudoku puzzles are a special case of latin squares. The more recent Kenken puzzles too.

(v) It is also used in the popular abstract strategy game Kamisado.

(vi) It is widely used in the design of agronomic research experiments to minimise experimental errors.

(vii) It has also a wide range of applications in permutations over Galois field.

Thus modern game theory, linear algebra has a wiHopefully this will be used in development of modern combinatorics and also in different fields of mathematics and other subjects too.

REFERENCES

[1] Some History of Latin Squares in Experiments [ R. A. Bailey – University of St.Andrews]

[2] Further results on the construction of Mutually Orthogonal Latin Squares and Falsity of Euler's Conjecture [ Bose R. C., S. S. Shrikhande, E. T. Parker – Canadian Journal of Mathematics: Page –[189-203]

[3] Latin square in experimental design [ Lei Gao- Michigan State University]

[4] Latin square and its application in cryptography [ Nathan O. Schmidt]

[5] Classification of Latin squares [ Dr. Noda Lakic]

[6] Enumerating extensions of mutually orthogonal Latin squares [Simona Boyadzhiyska,Shagnick Das, Tibor Szabo]

[7] 36 Officers problem [ Marianne Freiberger]de range of applications of latin square.