All Science Fair Projects

Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

Latin square

A Latin square is an n × n table filled with n different symbols in such a way that each symbol occurs exactly once in each row and exactly once in each column. Here are two examples.

$\begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ \end{bmatrix} \quad\quad \begin{bmatrix} a & b & d & c \\ b & c & a & d \\ c & d & b & a \\ d & a & c & b \end{bmatrix}$

Latin squares occur as the multiplication tables of a quasigroup. They have applications in the design of experiments.

The name Latin square originates from Leonard Euler who used Latin characters as symbols.

A Latin square is said to be reduced (also, normalized or in standard form) if its first row and first column are in natural order. For example, the first Latin square above is reduced because both its first row and its first column are 1,2,3 (rather than 3,1,2 or some other order). We can make any Latin square reduced by permuting (reordering) the rows and permuting the columns.

 Contents

Orthogonal array representation

If each entry of an n × n Latin square is written as a triple (r,c,s), where r is the row, c is the column, and s is the symbol, we obtain a set of n2 triples called the orthogonal array representation of the square. For example, the orthogonal array representation of the first Latin square displayed above is

{ (1,1,1),(1,2,2),(1,3,3),(2,1,2),(2,2,3),(2,3,1),(3,1,3),(3,2,1),(3,3,2) },

where for example the triple (2,3,1) means that in row 2 and column 3 there is the symbol 1. The definition of a Latin square can be written in terms of orthogonal arrays as follows:

• There are n2 triples of the form (r,c,s), where 1 ≤ r, c, sn.
• All of the pairs (r,c) are different, all the pairs (r,s) are different, and all the pairs (c,s) are different.

The orthogonal array representation shows that rows, columns and symbols play rather similar roles, as will be made clear below.

Equivalence classes of Latin squares

Many operations on a Latin square produce another Latin square (for example, turning it upside down).

If we permute the rows, permute the columns, and permute the names of the symbols of a Latin square, we obtain a new Latin square said to be isotopic to the first. Isotopism is an equivalence relation, so the set of all Latin squares is divided into subsets, called isotopy classes, such that two squares in the same class are isotopic and two squares in different classes are not isotopic.

Another type of operation is easiest to explain using the orthogonal array representation of the Latin square. If we systematically and consistently reorder the three items in each triple, another orthogonal array (and, thus, another Latin square) is obtained. For example, we can replace each triple (r,c,s) by (c,r,s) which corresponds to transposing the square (reflecting about its main diagonal), or we could replace each triple (r,c,s) by (c,s,r), which is a more complicated operation. Altogether there are 6 possibilities including "do nothing", giving us 6 Latin squares called the conjugates (also parastrophes ) of the original square.

Finally, we can combine these two equivalence operations: two Latin squares are said to be paratopic , also main class isotopic , if one of them is isotopic to a conjugate of the other. This is again an equivalence relation, with the equivalence classes called main classes , species, or paratopy classes . Each main class contains up to 6 isotopy classes.

The number of Latin squares

There is no known easily-computable formula for the number of n × n Latin squares with symbols 1,2,...,n, and even the best estimates for large n are very rough. Here we will give all the known exact values. It can be seen that the numbers grow exceedingly quickly.

For each n, the number of Latin squares altogether (A002860 in OEIS) is n! (n-1)! times the number of reduced Latin squares (A000315 in OEIS).

 n reduced Latin squares of size n all Latin squares of size n 1 1 1 2 1 2 3 1 12 4 4 576 5 56 161280 6 9408 812851200 7 16942080 61479419904000 8 535281401856 108776032459082956800 9 377597570964258816 5524751496156892842531225600 10 7580721483160132811489280 9982437658213039871725064756920320000 11 5363937773277371298119673540771840 776966836171770144107444346734230682311065600000

For each n, each isotopy class (A040082 in OEIS) contains up to (n!)3 Latin squares (the exact number varies), while each main class (A003090 in OEIS) contains either 1, 2, 3 or 6 isotopy classes.

 n main classes isotopy classes 1 1 1 2 1 1 3 1 1 4 2 2 5 2 2 6 12 22 7 147 564 8 283657 1676267 9 19270853541 115618721533 10 34817397894749939 208904371354363006

Examples

We give one example of a Latin square from each main class up to order 5.

$\begin{bmatrix} 1 \end{bmatrix} \quad \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix} \quad \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{bmatrix}$

$\begin{bmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \end{bmatrix} \quad \begin{bmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \\ 3 & 1 & 4 & 2 \\ 4 & 3 & 2 & 1 \end{bmatrix}$

$\begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 5 & 1 & 4 \\ 3 & 5 & 4 & 2 & 1 \\ 4 & 1 & 2 & 5 & 3 \\ 5 & 4 & 1 & 3 & 2 \end{bmatrix} \quad \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \\ 3 & 5 & 4 & 2 & 1 \\ 4 & 1 & 5 & 3 & 2 \\ 5 & 3 & 2 & 1 & 4 \end{bmatrix}$

External links

Last updated: 10-15-2005 21:41:59
03-10-2013 05:06:04
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
Science kits, science lessons, science toys, maths toys, hobby kits, science games and books - these are some of many products that can help give your kid an edge in their science fair projects, and develop a tremendous interest in the study of science. When shopping for a science kit or other supplies, make sure that you carefully review the features and quality of the products. Compare prices by going to several online stores. Read product reviews online or refer to magazines.

Start by looking for your science kit review or science toy review. Compare prices but remember, Price \$ is not everything. Quality does matter.
 Science Fair Coach What do science fair judges look out for? ScienceHound Science Fair Projects for students of all ages
 All Science Fair Projects.com Site All Science Fair Projects Homepage Search | Browse | Links | From-our-Editor | Books | Help | Contact | Privacy | Disclaimer | Copyright Notice