Carré latin

Vitrail situé au Gonville and Caius college représentant un carré latin coloré 7x7. Ce vitrail a été retiré en 2020 à cause des positions eugénistes du statisticien Ronald Aylmer Fisher qu'il honorait^[1].

En combinatoire, un carré latin d'ordre ${\displaystyle n}$ est un tableau carré de ${\displaystyle n}$ lignes (donc de ${\displaystyle n}$ colonnes) remplies de ${\displaystyle n}$ éléments distincts dont chaque ligne et chaque colonne ne contient qu'un seul exemplaire.

On obtient facilement un carré latin, dit cyclique, de tout ordre, en permutant circulairement successivement les lignes en partant de la première. Pour l'ordre 3 :

A	B	C	D
B	C	D	A
C	D	A	B
D	A	B	C

Cet autre carré latin d'ordre 3 :

A	B	C	D
B	A	D	C
C	D	A	B
D	C	B	A

ne peut être obtenu en permutant des éléments, des lignes ou des colonnes à partir du précédent.

Les carré latins, par l'intermédiaire des carrés gréco-latins, permettent de construire des carrés magiques^[2].

Histoire

Le carré SATOR figuré ci-contre, datant de l'antiquité, d'ordre 5 mais faisant intervenir plus de 5 caractères, n'est pas un carré latin au sens ci-dessus.

Le mathématicien coréen Choi Seok-jeong fut le premier en 1700 à publier un exemple de carré latin d'ordre neuf, afin de construire un carré magique^[3].

67 ans plus tard, le mathématicien suisse Leonhard Euler (1707 - 1783) a débuté l'étude des carrés latins, qu'il a ainsi nommés car il utilisait des caractères latins pour les écrire^[4],[5],[6].

Aujourd'hui, le carré latin est très populaire sous la forme du Sudoku^[5].

En mathématiques

Forme réduite

Comme Euler^[4], on peut considérer que les ${\displaystyle n}$ éléments du carré latin sont les entiers de 1 à ${\displaystyle n}$.

Une permutation sur les colonnes ou sur les lignes ne changeant pas le caractère latin du carré, une des ${\displaystyle n!}$ permutations des colonnes permet d'obtenir un carré latin de première ligne ${\displaystyle 1,2,\cdots ,n}$ dans cet ordre, puis l'une des ${\displaystyle (n-1)!}$ permutations des ${\displaystyle n-1}$ autres lignes permet d'obtenir un carré de première colonne ${\displaystyle 1,2,\cdots ,n}$ dans cet ordre.

Un tel carré est dit réduit ou normalisé^[2], et tout carré latin possède une unique forme réduite.

Le nombre ${\displaystyle L_{n}}$ de carrés latins d'ordre ${\displaystyle n}$ est donc égal à ${\displaystyle n!(n-1)!}$ fois le nombre ${\displaystyle L'_{n}}$ de carrés latins normalisé. En voici les premières valeurs :

n	${\displaystyle L'_{n}}$ , nombre de carrés latins normalisé suite A000315 de l'OEIS	${\displaystyle L_{n}}$, nombre de carrés latins suite A002860 de l'OEIS
1	1	1
2	1	2
3	1	12=3!.2!
4	4	576=4!.3!.4
5	56	161 280=5!.4!.56

Isotopie

Deux carré latins sont dits isotopes si l'on peut passer de l'un à l'autre par permutation des lignes, permutation des colonnes et permutation des éléments^[7].

Deux carrés latins réduits distincts peuvent être isotopes comme

1	2	3	4
2	3	4	1
3	4	1	2
4	1	2	3

et

1	2	3	4
2	1	4	3
3	4	2	1
4	3	1	2

Pour passer du premier au deuxième, permuter les éléments 2 et 3, les lignes 2 et 3, et les colonnes 2 et 3.

Les 4 carrés latins réduits d'ordre 4 ne sont plus que 2 à isotopie près : ${\displaystyle {\begin{matrix}1&2&3&4\\2&3&4&1\\3&4&1&2\\4&1&2&3\\\end{matrix}}}$ (le carré cyclique) et ${\displaystyle {\begin{matrix}1&2&3&4\\2&1&4&3\\3&4&1&2\\4&3&2&1\\\end{matrix}}}$

et les 56 carrés latins réduits d'ordre 5 plus que 2 également : ${\displaystyle {\begin{matrix}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{matrix}}}$ (le carré cyclique) et ${\displaystyle {\begin{matrix}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{matrix}}}$.

Les nombres de classes d'isotopie des carrés latins sont donnés par la suite A040082 de l'OEIS.

Paratopie

Deux carrés latins sont dits paratopes s'ils sont isotopes et éventuellement image l'un de l'autre par symétrie par rapport à une diagonale^[8].

Il y a 22 classes d'isotopie des carrés latins d'ordre 6^[2], mais plus que 12 classes de paratopie.

Les nombres de classes de paratopie des carrés latins sont donnés par la suite A003090 de l'OEIS.

Lien avec les quasi-groupes finis, isomorphisme

Un carré latin peut être considéré comme la table de Cayley d'une loi de composition interne. La condition de latinité du carré se traduit par le fait que la loi est régulière (tout élément est simplifiable), ce qui constitue la définition d'un quasi-groupe^[2],[7]. Les carrés latins sont donc en bijection avec les quasi-groupes finis.

La condition d'isotopie de 2 carrés latins associés à des quasi-groupes ${\displaystyle (E,\perp _{1})}$ et ${\displaystyle (E,\perp _{2})}$ est qu'il existe trois bijections de ${\displaystyle E}$ : ${\displaystyle f,g,h}$ telles que ${\displaystyle h(x\perp _{1}y)=f(x)\perp _{2}g(y)}$^[7] (${\displaystyle f}$ correspond aux permutations des lignes, ${\displaystyle g}$ à celle des colonnes et ${\displaystyle h}$ à celle des éléments).

La condition de paratopie, plus forte, se traduit par la possibilité supplémentaire de commuter une loi (${\displaystyle x\perp _{2}y=y\perp _{1}x}$).

La notion classique d'isomorphisme, plus faible, correspond au cas où ${\displaystyle f=g=h}$^[7].

L'unique classe d'isotopie des carrés d'ordre 3, se décompose en 5 classes d'isomorphismes, représentées ci-dessous avec le nombre de carrés latins déduits :

${\displaystyle {\begin{matrix}1&2&3\\2&3&1\\3&1&2\\&(3)&\end{matrix}}\qquad \qquad {\begin{matrix}2&3&1\\1&2&3\\3&1&2\\&(3)&\end{matrix}}\qquad \qquad {\begin{matrix}2&1&3\\3&2&1\\1&3&2\\&(3)\end{matrix}}\qquad \qquad {\begin{matrix}3&2&1\\2&1&3\\1&3&2\\&(2)&\end{matrix}}\qquad \qquad {\begin{matrix}1&3&2\\3&2&1\\2&1&3\\&(1)&\end{matrix}}.}$

Les nombres de classes d'isomorphisme des carrés latins sont donnés par la suite A057991 de l'OEIS.

En littérature

L'écrivain Georges Perec a utilisé le carré latin comme ossature de deux de ses œuvres : La Vie mode d'emploi (ordre 10) et Lieux (ordre 12).

Héraldique

Un carré latin d'ordre 3 apparaît dans le blason de la Société statistique du Canada^[9] ainsi que dans le logo de la Société biométrique internationale^[10].

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Small Latin squares and quasigroups » (voir la liste des auteurs).

1. (en) Edwards, A.W.F, « Cancelled by his college », The Critic,‎ mars 2021 (lire en ligne)
2. Jacques Bouteloup, Carrés magiques, carrés latins et eulériens, Éditions du Choix, 1991, p. 18-20, 93-116, 125-137
3. (en) Colbourn, Charles J.; Dinitz, Jeffrey H., Handbook of Combinatorial Designs, CRC Press., 2006, p. 12
4. L. Euler, Recherches sur une nouvelle espèce de quarrés magiques, E530, présenté à l'Académie de Saint-Pétersbourg le 8 mars 1779. Fait remarquable, cet article d'Euler est écrit en français, et est le seul publié dans un journal néerlandais (en 1782).
5. Sudoku Anleitung
6. (en) Wallis, W. D.; George, J. C., Introduction to Combinatorics, CRC Press, 2011 (ISBN 978-1-4398-0623-4), p. 212
7. B. Monjardet, « Quasi-groupes finis, quasi-groupes orthogonaux, ensemble complet orthogonal », Mathématiques et sciences humaines, vol. 19 (1967), p. 13-2,‎ 1967, p. 13-20 (lire en ligne)
8. (en) Dénes, J.; Keedwell, A. D., Latin squares and their applications, Academic Press, 1974 (ISBN 0-12-209350-X), p. 126-129
9. Société statistique du Canada
10. The International Biometric Society

Voir aussi

Articles connexes

• Carré magique
• Carré gréco-latin - la combinaison de deux carrés latins orthogonaux
• Échantillonnage par hypercube latin
• Matrice (mathématiques)
• Sudoku (jeu qui s'inspire des carrés latins)

Lien externe

• Carrés latins et gréco-latins, un début vers les carrés magiques, sur villemin.gerard.free.fr