 GraecoLatin square

In mathematics, a GraecoLatin square or Euler square or orthogonal Latin squares of order n over two sets S and T, each consisting of n symbols, is an n×n arrangement of cells, each cell containing an ordered pair (s,t), where s is in S and t is in T, such that every row and every column contains each element of S and each element of T exactly once, and that no two cells contain the same ordered pair.
The arrangement of the Latin characters alone and of the Greek characters alone each forms a Latin square. A GraecoLatin square can therefore be decomposed into two "orthogonal" Latin squares. Orthogonality here means that every pair (s, t) from the Cartesian product S×T occurs exactly once.
Contents
History
Orthogonal Latin squares have been known to predate Euler. As described by Donald Knuth in Volume 4 of TAOCP, the construction of 4x4 set was published by Jacques Ozanam in 1725 (in Recreation mathematiques et physiques) as a puzzle involving playing cards. The problem was to take all aces, kings, queens and jacks from a standard deck of cards, and arrange them in a 4x4 grid such that each row and each column contained all four suits as well as one of each face value. This problem has several solutions.
A common variant of this problem was to arrange the 16 cards so that, in addition to the row and column constraints, each diagonal contains all four face values and all four suits as well. As described by Martin Gardner in Gardner's Workout, the number of distinct solutions to this problem was incorrectly estimated by Rouse Ball to be 72, and persisted many years before it was shown to be 144 by Kathleen Ollerenshaw. Each of the 144 solutions has 8 reflections and rotations, giving 1152 solutions in total. The 144x8 solutions can be categorized into the following two classes:
Solution Normal form Solution #1 A♠ K♥ Q♦ J♣
Q♣ J♦ A♥ K♠
J♥ Q♠ K♣ A♦
K♦ A♣ J♠ Q♥Solution #2 A♠ K♥ Q♦ J♣
J♦ Q♣ K♠ A♥
K♣ A♦ J♥ Q♠
Q♥ J♠ A♣ K♦For each of the two solutions, 24x24 = 576 solutions can be derived by permuting the four suits and the four face values independently. No permutation will convert the two solutions into each other.
The solution set can be seen to be complete through this proof outline:
 Without loss of generality, let us choose the card in the top left corner to be A♠.
 Now, in the second row, the first two squares can be neither ace nor spades, due to being on the same column or diagonal respectively. Therefore, one of the remaining two squares must be an ace, and the other must be a spade, since the card A♠ itself cannot be repeated.
 If we choose the cell in the second row, third column to be an ace, and propagate the constraints, we will get Solution #1 above, up to a permutation of the remaining suits and face values.
 Conversely, if we choose the (2,3) cell to be a spade, and propagate the constraints, we will get Solution #2 above, up to a permutation of the remaining suits and face values.
 Since no other possibilities exist for (2,3), the solution set is complete.
Euler's work and conjecture
Orthogonal Latin squares were studied in detail by Leonhard Euler, who took the two sets to be S = {A, B, C, …}, the first n uppercase letters from the Latin alphabet, and T = {α , β, γ, …}, the first n lowercase letters from the Greek alphabet—hence the name GraecoLatin square.
In the 1780s Euler demonstrated methods for constructing GraecoLatin squares where n is odd or a multiple of 4. Observing that no order2 square exists and unable to construct an order6 square (see thirtysix officers problem), he conjectured that none exist for any oddly even number n ≡ 2 (mod 4). Indeed, the nonexistence of order6 squares was definitely confirmed in 1901 by Gaston Tarry through exhaustive enumeration of all possible arrangements of symbols. However, Euler's conjecture resisted solution for a very long time.
Counterexamples to the conjecture of Euler
In 1959, R.C. Bose and S. S. Shrikhande constructed some counterexamples (dubbed the Euler spoilers) of order 22 using mathematical insights. Then E. T. Parker found a counterexample of order 10 through computer search on UNIVAC (this was one of the earliest combinatorics problems solved on a digital computer).
In 1960, Parker, Bose, and Shrikhande showed Euler's conjecture to be false for all n ≥ 10. Thus, GraecoLatin squares exist for all orders n ≥ 3 except n = 6.
Applications
GraecoLatin squares are used in the design of experiments, tournament scheduling and constructing magic squares. The French writer Georges Perec structured his 1978 novel Life: A User's Manual around a 10×10 orthogonal square.
Mutually orthogonal Latin squares
Mutually orthogonal Latin squares arise in various problems. A set of Latin squares is called mutually orthogonal if every pair of its element Latin squares is orthogonal to each other.
Any two of text, foreground color, background color and typeface form a pair of orthogonal Latin squares: fjords jawbox phlegm qiviut zincky zincky fjords jawbox phlegm qiviut qiviut zincky fjords jawbox phlegm phlegm qiviut zincky fjords jawbox jawbox phlegm qiviut zincky fjords The above table shows 4 mutually orthogonal Latin squares of order 5, representing respectively:
 the text: fjords, jawbox, phlegm, qiviut, and zincky
 the foreground color: white, red, lime, blue, and yellow
 the background color: black, maroon, teal, navy, and silver
 the typeface: serif (Georgia / Times Roman), sansserif (Verdana / Helvetica), monospace (Courier New), cursive (Comic Sans), and fantasy (Impact).
Due to the Latin square property, each row and each column has all five texts, all five foregrounds, all five backgrounds, and all five typefaces.
Due to the mutually orthogonal property, there is exactly one instance somewhere in the table for any pair of elements, such as (white foreground, monospace), or (fjords, navy background) etc., and also all possible such pairs of values and dimensions are represented exactly once each.
The above table therefore allows for testing 5 values each of 4 different dimensions in only 25 observations instead of 625 observations. Note that the five 6letter words (fjords, jawbox, phlegm, qiviut, and zincky) between them cover all 26 letters of the alphabet at least once each. The table therefore allows for examining each letter of the alphabet in five different typefaces, foreground colors, and background colors.
Due to a close relation between orthogonal Latin squares and combinatorial designs, every pair of distinct cells in the 5x5 table will have exactly one of the following properties in common:
 a common row, or
 a common column, or
 a common text, or
 a common typeface, or
 a common background color, or
 a common foreground color.
In each category, every cell has 4 neighbors (4 neighbors in the same row with nothing else in common, 4 in the same column, etc.), giving 6 * 4 = 24 neighbors, which makes it a complete graph with 6 different edge colors.
The number of mutually orthogonal latin squares
The number of mutually orthogonal Latin squares that may exist for a given order n is not known for general n, and is an area of research in combinatorics. It is known that the maximum number of MOLS for any n cannot exceed (n1), and this upper bound is achieved when n is a power of a prime number. The minimum is known to be 2 for all n except for n = 1, 2 or 6, where it is 1. For general composite numbers, the number of MOLS is not known. The first few values starting with n = 2, 3, 4... are 1, 2, 3, 4, 1, 6, 7, 8, ... (sequence A001438 in OEIS).
See also
Bibliography
 Raghavarao, Damaraju (1988). Constructions and Combinatorial Problems in Design of Experiments (corrected reprint of the 1971 Wiley ed.). New York: Dover.
 Raghavarao, Damaraju and Padgett, L.V. (2005). Block Designs: Analysis, Combinatorics and Applications. World Scientific.
 Street, Anne Penfold and Street, Deborah J. (1987). Combinatorics of Experimental Design. Oxford U. P. [Clarendon]. pp. 400+xiv. ISBN 0198532563.
External links
 Euler's work on Latin Squares and Euler Squares at Convergence
 Java Tool which assists in constructing GraecoLatin squares (it does not construct them by itself) at cuttheknot
 Anything but square: from magic squares to Sudoku
Statistics Descriptive statistics Summary tablesPearson productmoment correlation · Rank correlation (Spearman's rho, Kendall's tau) · Partial correlation · Scatter plotBar chart · Biplot · Box plot · Control chart · Correlogram · Forest plot · Histogram · QQ plot · Run chart · Scatter plot · Stemplot · Radar chartData collection Designing studiesDesign of experiments · Factorial experiment · Randomized experiment · Random assignment · Replication · Blocking · Optimal designUncontrolled studiesStatistical inference Frequentist inferenceSpecific testsZtest (normal) · Student's ttest · Ftest · Pearson's chisquared test · Wald test · Mann–Whitney U · Shapiro–Wilk · Signedrank · Kolmogorov–Smirnov testCorrelation and regression analysis Errors and residuals · Regression model validation · Mixed effects models · Simultaneous equations modelsNonstandard predictorsPartition of varianceCategorical, multivariate, timeseries, or survival analysis Decomposition (Trend · Stationary process) · ARMA model · ARIMA model · Vector autoregression · Spectral density estimationApplications Categories: Latin squares
 Design of experiments
Wikimedia Foundation. 2010.
Look at other dictionaries:
HyperGraecoLatin square design — In the design of experiments, hyper Graeco Latin squares are efficient designs to study the effect of one primary (treatment) factor in the presence of 4 blocking (nuisance) factors. They are restricted, however, to the case in which all the… … Wikipedia
Latin square — A Latin square is an n times; 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 is an example: egin{bmatrix} 1 2 3 2 3 1 3 1 2 end{bmatrix} Latin squares… … Wikipedia
Latin hypercube sampling — (LHS) is a statistical method for generating a distribution of plausible collections of parameter values from a multidimensional distribution. The sampling method is often applied in uncertainty analysis. The technique was first described by… … Wikipedia
Randomized block design — In the statistical theory of the design of experiments, blocking is the arranging of experimental units in groups (blocks) that are similar to one another. Typically, a blocking factor is a source of variability that is not of primary interest to … Wikipedia
List of statistics topics — Please add any Wikipedia articles related to statistics that are not already on this list.The Related changes link in the margin of this page (below search) leads to a list of the most recent changes to the articles listed below. To see the most… … Wikipedia
Combinatorial design — theory is the part of combinatorial mathematics that deals with the existence and construction of systems of finite sets whose intersections have specified numerical properties. For instance, a balanced incomplete block design (usually called for … Wikipedia
Effect size — In statistics, an effect size is a measure of the strength of the relationship between two variables in a statistical population, or a sample based estimate of that quantity. An effect size calculated from data is a descriptive statistic that… … Wikipedia
Raj Chandra Bose — (June 19, 1901 October 31, 1987) Indian mathematician and statistician best known for his work in design theory and the theory of error correcting codes in which the class of BCH codes is partly named after him. He was notable for his work along… … Wikipedia
план — 3.1.14 план: Вид сверху или горизонтальный разрез здания или сооружения. Источник: ГОСТ Р 21.1101 2013: Система проектной документации для строительства. Основные требования к проектной и рабочей документации … Словарьсправочник терминов нормативнотехнической документации
Analysis of variance — In statistics, analysis of variance (ANOVA) is a collection of statistical models, and their associated procedures, in which the observed variance in a particular variable is partitioned into components attributable to different sources of… … Wikipedia