Graeco-Latin square

In combinatorics, a Graeco-Latin square or Euler square or pair of 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.

* Orthogonal Latin squares
* Order 3

* Order 4

* Order 5

The arrangement of the s-coordinates by themselves (which may be thought of as Latin characters) and of the t-coordinates (the Greek characters) each forms a Latin square. A Graeco-Latin 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

* 1 History
* 1.1 Euler's conjecture and disproof
* 2 Applications
* 3 Mutually orthogonal Latin squares
* 3.1 The number of mutually orthogonal latin squares
* 3.2 Orthogonal arrays
* 4 See also
* 5 References
* 6 Bibliography
* 7 Further reading
* 8 External links

## History

Orthogonal Latin squares have been known to predate Euler. As described by Donald Knuth in Volume 4A, p. 3 of TAOCP,[1] the construction of 4x4 set was published by Jacques Ozanam in 1725 (in Recreation mathematiques et physiques, Vol. IV)[2] 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.

According to Martin Gardner, who featured this problem in his November 1959 Mathematical Games column, the number of distinct solutions was incorrectly stated to be 72 by Rouse Ball. This mistake persisted for many years until the correct value of 144 was found by Kathleen Ollerenshaw. Each of the 144 solutions has eight reflections and rotations, giving 1152 solutions in total. The 144×8 solutions can be categorized into the following two equivalence classes:

Solution  | Normal form

|

Solution #1  | Template:♠ Template:♥ Template:♦ Template:♣
Template:♣ Template:♦ Template:♥ Template:♠
Template:♥ Template:♠ Template:♣ Template:♦
Template:♦ Template:♣ Template:♠ Template:♥

Solution #2  | Template:♠ Template:♥ Template:♦ Template:♣
Template:♦ Template:♣ Template:♠ Template:♥
Template:♣ Template:♦ Template:♥ Template:♠
Template:♥ Template:♠ Template:♣ Template:♦

For each of the two solutions, 24×24 = 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:

1. Without loss of generality, let us choose the card in the top left corner to be Template:♠.
2. In the second row, the first two cells can be neither ace nor spades, due to being on the same column or diagonal respectively. Therefore, one of the remaining two cells must be an ace, and the other must be a spade, since the card Template:♠ itself cannot be repeated.
3. If we choose the cell in the second row, third column to be an ace, and propagate the constraints, we get Solution #1 above, up to a permutation of the remaining suits and face values.
4. Conversely, if we choose the (2,3) cell to be a spade, and propagate the constraints, we get Solution #2 above, up to a permutation of the remaining suits and face values.
5. Since no other possibilities exist for (2,3), the solution set is complete.

### Euler's conjecture and disproof

Orthogonal Latin squares were studied in detail by Leonhard Euler, who took the two sets to be S = {A, B, C, …}, the first n upper-case letters from the Latin alphabet, and T = {α , β, γ, …}, the first n lower-case letters from the Greek alphabet--hence the name Graeco-Latin square.

In the 1780s Euler demonstrated methods for constructing Graeco-Latin squares where n is odd or a multiple of 4.[3] Observing that no order-2 square exists and being unable to construct an order-6 square (see thirty-six officers problem), he conjectured that none exist for any oddly even number n ≡ 2 (mod 4). The non-existence of order-6 squares was confirmed in 1901 by Gaston Tarry through a proof by exhaustion. However, Euler's conjecture resisted solution until the late 1950s.

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 using a one-hour computer search on a UNIVAC 1206 Military Computer while working at the UNIVAC division of Remington Rand (this was one of the earliest combinatorics problems solved on a digital computer).

In April 1959, Parker, Bose, and Shrikhande presented their paper showing Euler's conjecture to be false for all n ≥ 10. Thus, Graeco-Latin squares exist for all orders n ≥ 3 except n = 6.

## Applications

Graeco-Latin 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 Graeco-Latin square.

## Mutually orthogonal Latin squares

A set of Latin squares is called mutually orthogonal or pairwise orthogonal if each Latin square in the set is pairwise orthogonal to all other Latin squares of the set.

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 four 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), sans-serif (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. These properties may be thought of as dimensions along which a value may vary.

Due to mutual orthogonality, 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 of distinct "dimensions" are represented exactly once each.

The above table therefore allows for testing five values in each of four different "dimensions" in only 25 observations instead of 625 (= 54) observations. Also note that the five 6-letter 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 four neighbors (four neighbors in the same row with nothing else in common, four in the same column, etc.), giving 6 * 4 = 24 neighbors, which makes it a complete graph with six different edge colors.

### The number of mutually orthogonal latin squares

The number of mutually orthogonal Latin squares (MOLS) 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 n − 1, and this upper bound is achieved when n is a power of a prime number. A set of n \- 1 MOLS is equivalent to a finite projective plane of order n. The minimum is known to be 2 for all n except for n = 2 or 6, where it is 1. For large enough n, the number of MOLS is greater than [math]\displaystyle{ \sqrt[14.8]{n} }[/math], thus for every k, there are only a finite number of n such that the number of MOLS is k.[4] Moreover, the minimum is 6 for all n > 90\. 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 the OEIS).

### Orthogonal arrays

An orthogonal array of strength 2 and index 1 is a tabular form used to represent sets of MOLS. More general orthogonal arrays represent generalizations of the concept of MOLS, such as mutually orthogonal Latin cubes.

## See also

* Block design
* Blocking (statistics)
* Combinatorial design
* Design of experiments
* Hyper-Graeco-Latin square design
* Orthogonal array
* Randomized block design

## References

1. ↑ The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Orthogonal latin squares.
2. ↑ Recreation mathematiques et physiques, Vol. IV, p. 434, the solution is in Fig. 35
3. ↑ Euler: Recherches sur une nouvelle espece de quarres magiques, written in 1779, published in 1782
4. ↑ Lenz, H.; Jungnickel, D.; Beth, Thomas (November 1999). "Design Theory by Thomas Beth". doi:10.1017/cbo9781139507660. https://www.cambridge.org/core/books/design-theory/0DED6E91AC297F825256C649C76D87F8.

## 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.
* Combinatorics of Experimental Design. Oxford U. P. [Clarendon]. 1987. pp. 400+xiv. ISBN 0-19-853256-3.

## Further reading

* Martin Gardner's New Mathematical Diversions from Scientific American, Fireside, 1966, pp. 162–172, 0-671-20913-2

## External links

* Euler's work on Latin Squares and Euler Squares at Convergence
* Java Tool which assists in constructing Graeco-Latin squares (it does not construct them by itself) at cut-the-knot
* Anything but square: from magic squares to Sudoku
* Historical facts and correlation with Magic Squares, Javascript Application to solve Graeco-Latin Squares from size 1x1 to 10x10 and related source code (Javascript in Firefox browser and HTML5 mobile devices)

* v
* t
* e

Design of experiments

Scientific
method|

* Scientific experiment
* Statistical design
* Control
* Internal and external validity
* Experimental unit
* Blinding

* Optimal design: Bayesian
* Random assignment
* Randomization
* Restricted randomization
* Replication versus subsampling
* Sample size

Treatment
and blocking|

* Treatment
* Effect size
* Contrast
* Interaction
* Confounding
* Orthogonality
* Blocking
* Covariate
* Nuisance variable

Models
and inference|

* Linear regression
* Ordinary least squares
* Bayesian

* Random effect
* Mixed model
* Hierarchical model: Bayesian

* Analysis of variance (Anova)
* Cochran's theorem
* Manova (multivariate)
* Ancova (covariance)

* Compare means
* Multiple comparison

Designs

Completely
randomized|

* Factorial
* Fractional factorial
* Plackett-Burman
* Taguchi

* Response surface methodology
* Polynomial and rational modeling
* Box-Behnken
* Central composite

* Block
* Generalized randomized block design (GRBD)
* Latin square
* Graeco-Latin square
* Orthogonal array
* Latin hypercube
Repeated measures design
* Crossover study

* Randomized controlled trial
* Sequential analysis
* Sequential probability ratio test

* Glossary
* Category
*   * Statistical outline
* Statistical topics

* v
* t
* e

Statistics

* Outline
* Index

Descriptive statistics

| Continuous data|

| Center|

* Mean
* arithmetic
* geometric
* harmonic
* Median
* Mode

|

Dispersion|

* Variance
* Standard deviation
* Coefficient of variation
* Percentile
* Range
* Interquartile range

Shape|

* Central limit theorem
* Moments
* Skewness
* Kurtosis
* L-moments

Count data|

* Index of dispersion

Summary tables|

* Grouped data
* Frequency distribution
* Contingency table

Dependence|

* Pearson product-moment correlation
* Rank correlation
* Spearman's rho
* Kendall's tau
* Partial correlation
* Scatter plot

Graphics|

* Bar chart
* Biplot
* Box plot
* Control chart
* Correlogram
* Fan chart
* Forest plot
* Histogram
* Pie chart
* Q–Q plot
* Run chart
* Scatter plot
* Stem-and-leaf display
* Radar chart
* Violin plot

Data collection

| Study design|

* Population
* Statistic
* Effect size
* Statistical power
* Optimal design
* Sample size determination
* Replication
* Missing data

|

Survey methodology|

* Sampling
* stratified
* cluster
* Standard error
* Opinion poll
* Questionnaire

Controlled experiments|

* Scientific control
* Randomized experiment
* Randomized controlled trial
* Random assignment
* Blocking
* Interaction
* Factorial experiment

Adaptive Designs|

* Adaptive clinical trial
* Up-and-Down Designs
* Stochastic approximation

Observational Studies|

* Cross-sectional study
* Cohort study
* Natural experiment
* Quasi-experiment

Statistical inference

| Statistical theory|

* Population
* Statistic
* Probability distribution
* Sampling distribution
* Order statistic
* Empirical distribution
* Density estimation
* Statistical model
* Model specification
* Lp space
* Parameter
* location
* scale
* shape
* Parametric family
* Likelihood (monotone)
* Location–scale family
* Exponential family
* Completeness
* Sufficiency
* Statistical functional
* Bootstrap
* U
* V
* Optimal decision
* loss function
* Efficiency
* Statistical distance
* divergence
* Asymptotics
* Robustness

|

Frequentist inference|

| Point estimation|

* Estimating equations
* Maximum likelihood
* Method of moments
* M-estimator
* Minimum distance
* Unbiased estimators
* Mean-unbiased minimum-variance
* Rao–Blackwellization
* Lehmann–Scheffé theorem
* Median unbiased
* Plug-in

|

Interval estimation|

* Confidence interval
* Pivot
* Likelihood interval
* Prediction interval
* Tolerance interval
* Resampling
* Bootstrap
* Jackknife

Testing hypotheses|

* 1- & 2-tails
* Power
* Uniformly most powerful test
* Permutation test
* Randomization test
* Multiple comparisons

Parametric tests|

* Likelihood-ratio
* Score/Lagrange multiplier
* Wald

Specific tests|

* Z-test (normal)
* Student's t-test
* F-test

Goodness of fit|

* Chi-squared
* G-test
* Kolmogorov–Smirnov
* Anderson–Darling
* Lilliefors
* Jarque–Bera
* Normality (Shapiro–Wilk)
* Likelihood-ratio test
* Model selection
* Cross validation
* AIC
* BIC

Rank statistics|

* Sign
* Sample median
* Signed rank (Wilcoxon)
* Hodges–Lehmann estimator
* Rank sum (Mann–Whitney)
* Nonparametric anova
* 1-way (Kruskal–Wallis)
* 2-way (Friedman)
* Ordered alternative (Jonckheere–Terpstra)

Bayesian inference|

* Bayesian probability
* prior
* posterior
* Credible interval
* Bayes factor
* Bayesian estimator
* Maximum posterior estimator

* Correlation
* Regression analysis

| Correlation|

* Pearson product-moment
* Partial correlation
* Confounding variable
* Coefficient of determination

|

Regression analysis|

* Errors and residuals
* Regression validation
* Mixed effects models
* Simultaneous equations models
* Multivariate adaptive regression splines (MARS)

Linear regression|

* Simple linear regression
* Ordinary least squares
* General linear model
* Bayesian regression

Non-standard predictors|

* Nonlinear regression
* Nonparametric
* Semiparametric
* Isotonic
* Robust
* Heteroscedasticity
* Homoscedasticity

Generalized linear model|

* Exponential families
* Logistic (Bernoulli) / Binomial / Poisson regressions

Partition of variance|

* Analysis of variance (ANOVA, anova)
* Analysis of covariance
* Multivariate ANOVA
* Degrees of freedom

Categorical / Multivariate / Time-series / Survival analysis

| Categorical|

* Cohen's kappa
* Contingency table
* Graphical model
* Log-linear model
* McNemar's test

|

Multivariate|

* Regression
* Manova
* Principal components
* Canonical correlation
* Discriminant analysis
* Cluster analysis
* Classification
* Structural equation model
* Factor analysis
* Multivariate distributions
* Elliptical distributions
* Normal

Time-series|

| General|

* Decomposition
* Trend
* Stationarity
* Seasonal adjustment
* Exponential smoothing
* Cointegration
* Structural break
* Granger causality

|

Specific tests|

* Dickey–Fuller
* Johansen
* Q-statistic (Ljung–Box)
* Durbin–Watson
* Breusch–Godfrey

Time domain|

* Autocorrelation (ACF)
* partial (PACF)
* Cross-correlation (XCF)
* ARMA model
* ARIMA model (Box–Jenkins)
* Autoregressive conditional heteroskedasticity (ARCH)
* Vector autoregression (VAR)

Frequency domain|

* Spectral density estimation
* Fourier analysis
* Wavelet
* Whittle likelihood

Survival|

| Survival function|

* Kaplan–Meier estimator (product limit)
* Proportional hazards models
* Accelerated failure time (AFT) model
* First hitting time

|

Hazard function|

* Nelson–Aalen estimator

Test|

* Log-rank test

Applications

| Biostatistics|

* Bioinformatics
* Clinical trials / studies
* Epidemiology
* Medical statistics

|

Engineering statistics|

* Chemometrics
* Methods engineering
* Probabilistic design
* Process / quality control
* Reliability
* System identification

Social statistics|

* Actuarial science
* Census
* Crime statistics
* Demography
* Econometrics
* Jurimetrics
* National accounts
* Official statistics
* Population statistics
* Psychometrics

Spatial statistics|

* Cartography
* Environmental statistics
* Geographic information system
* Geostatistics
* Kriging

* Category
* '
* Commons
* WikiProject

0.00

(0 votes)

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Graeco-Latin_square&oldid=2398786"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template