Carré latin

En combinatoire et en conception expérimentale , un carré latin est un tableau n × n rempli de n symboles différents, chacun apparaissant exactement une fois dans chaque ligne et exactement une fois dans chaque colonne. Un exemple de carré latin 3 × 3 est

Le nom « carré latin » a été inspiré par les articles mathématiques de Leonhard Euler (1707–1783), qui utilisait les caractères latins comme symboles, mais n'importe quel ensemble de symboles peut être utilisé : dans l'exemple ci-dessus, la séquence alphabétique A, B, C peut être remplacée par la séquence entière 1, 2, 3. Euler a commencé la théorie générale des carrés latins.

Le mathématicien coréen Choi Seok-jeong fut le premier à publier un exemple de carrés latins d'ordre neuf, afin de construire un carré magique en 1700, précédant Leonhard Euler de 67 ans.

On dit qu'un carré latin est réduit (également normalisé ou sous forme standard ) si sa première ligne et sa première colonne sont dans leur ordre naturel. Par exemple, le carré latin ci-dessus n'est pas réduit car sa première colonne est A, C, B plutôt que A, B, C.

Tout carré latin peut être réduit en permutant (c'est-à-dire en réorganisant) les lignes et les colonnes. Ici, l'inversion des deuxième et troisième lignes de la matrice ci-dessus donne le carré suivant :

Ce carré latin est réduit ; sa première ligne et sa première colonne sont classées par ordre alphabétique A, B, C.

Si chaque entrée d'un carré latin n × n est écrite sous la forme d'un triplet ( r , c , s ), où r est la ligne, c est la colonne et s est le symbole, nous obtenons un ensemble de n ² triplets appelé représentation orthogonale du carré. Par exemple, la représentation orthogonale du carré latin

est

{ (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) },

où par exemple le triple (2, 3, 1) signifie que dans la ligne 2 et la colonne 3 se trouve le symbole 1. Les tableaux orthogonaux sont généralement écrits sous forme de tableau où les triplets sont les lignes, comme par exemple :

La définition d'un carré latin peut s'écrire en termes de tableaux orthogonaux :

• Un carré latin est un ensemble de n ² triplets ( r , c , s ), où 1 ≤ r , c , s ≤ n , tels que toutes les paires ordonnées ( r , c ) sont distinctes, toutes les paires ordonnées ( r , s ) sont distinctes et toutes les paires ordonnées ( c , s ) sont distinctes.

Cela signifie que les n ² paires ordonnées ( r , c ) sont toutes les paires ( i , j ) avec 1 ≤ i , j ≤ n , une fois chacune. Il en va de même pour les paires ordonnées ( r , s ) et les paires ordonnées ( c , s ).

La représentation du tableau orthogonal montre que les lignes, les colonnes et les symboles jouent des rôles assez similaires, comme cela sera expliqué ci-dessous.

De nombreuses opérations sur un carré latin produisent un autre carré latin (par exemple, le retourner).

Si l'on permute les lignes, si l'on permute les colonnes ou si l'on permute les noms des symboles d'un carré latin, on obtient un nouveau carré latin dit isotopique au premier. L'isotopisme est une relation d'équivalence , donc l'ensemble de tous les carrés latins est divisé en sous-ensembles, appelés classes d'isotopie , tels que deux carrés de la même classe soient isotopiques et deux carrés de classes différentes ne le soient pas.

Un autre type d'opération est plus facile à expliquer en utilisant la représentation orthogonale du carré latin. Si nous réorganisons systématiquement et de manière cohérente les trois éléments de chaque triplet (c'est-à-dire, si nous permutons les trois colonnes sous forme de tableau), un autre tableau orthogonal (et donc un autre carré latin) est obtenu. Par exemple, nous pouvons remplacer chaque triplet ( r , c , s ) par ( c , r , s ) qui correspond à la transposition du carré (en réfléchissant par rapport à sa diagonale principale), ou nous pouvons remplacer chaque triplet ( r , c , s ) par ( c , s , r ), ce qui est une opération plus compliquée. Au total, il existe 6 possibilités, y compris « ne rien faire », ce qui nous donne 6 carrés latins appelés les conjugués (également parastrophes ) du carré d'origine.

Enfin, on peut combiner ces deux opérations d'équivalence : deux carrés latins sont dits paratopiques , et également isotopiques de classe principale , si l'un d'eux est isotopique à un conjugué de l'autre. Il s'agit là encore d'une relation d'équivalence, les classes d'équivalence étant appelées classes principales , espèces ou classes de paratopie . Chaque classe principale contient jusqu'à six classes d'isotopie.

Il n'existe pas de formule connue et facilement calculable pour le nombre L _n de n × n carrés latins de symboles 1, 2, ..., n . Les bornes supérieures et inférieures les plus précises connues pour un grand n sont très éloignées. Un résultat classique est que

Une formule simple et explicite pour le nombre de carrés latins a été publiée en 1992, mais elle n'est toujours pas facilement calculable en raison de l'augmentation exponentielle du nombre de termes. Cette formule pour le nombre L _n de n × n carrés latins est où B _n est l'ensemble de toutes les matrices n × n {0, 1}, σ ₀ ( A ) est le nombre d'éléments nuls dans la matrice A , et per( A ) est la permanente de la matrice A .

Le tableau ci-dessous contient toutes les valeurs exactes connues. On peut constater que les nombres augmentent extrêmement rapidement. Pour chaque n , le nombre total de carrés latins (séquence A002860 dans l' OEIS ) est n ! ( n − 1)! fois le nombre de carrés latins réduits (séquence A000315 dans l' OEIS ).

Pour chaque n , chaque classe d'isotopie (séquence A040082 dans l' OEIS ) contient jusqu'à ( n !) ³ carrés latins (le nombre exact varie), tandis que chaque classe principale (séquence A003090 dans l' OEIS ) contient soit 1, 2, 3 ou 6 classes d'isotopie.

Le nombre de carrés latins structurellement distincts (c'est-à-dire que les carrés ne peuvent pas être rendus identiques par rotation, réflexion et/ou permutation des symboles) pour n = 1 jusqu'à 7 est respectivement 1, 1, 1, 12, 192, 145164, 1524901344 (séquence A264603 dans l' OEIS ).

Nous donnons un exemple de carré latin de chaque classe principale jusqu'à l'ordre cinq.

Ils présentent respectivement les tables de multiplication des groupes suivants :

• {0} – le groupe trivial à 1 élément
• le dernier est un exemple de quasigroupe , ou plutôt de boucle , qui n'est pas associatif.

Une transversale dans un carré latin est un choix de n cellules, où chaque ligne contient une cellule, chaque colonne contient une cellule et il y a une cellule contenant chaque symbole.

On peut considérer un carré latin comme un graphe bipartite complet dans lequel les lignes sont des sommets d'une partie, les colonnes sont des sommets de l'autre partie, chaque cellule est une arête (entre sa ligne et sa colonne), et les symboles sont des couleurs. Les règles des carrés latins impliquent qu'il s'agit d'une coloration d'arête propre . Avec cette définition, une transversale latine est une correspondance dans laquelle chaque arête a une couleur différente ; une telle correspondance est appelée correspondance arc-en-ciel .

Par conséquent, de nombreux résultats sur les carrés/rectangles latins sont contenus dans des articles portant le terme « rainbow matching » dans leur titre, et vice versa.

Certains carrés latins n'ont pas de transversale. Par exemple, lorsque n est pair, un carré latin n x n dans lequel la valeur de la cellule i , j est ( i + j ) mod n n'a pas de transversale. Voici deux exemples : En 1967, HJ Ryser a conjecturé que, lorsque n est impair , tout carré latin n x n a une transversale.

En 1975, SK Stein et Brualdi ont conjecturé que, lorsque n est pair , tout carré latin de taille n x n possède une transversale partielle de taille n −1.

Une conjecture plus générale de Stein est qu'une transversale de taille n −1 existe non seulement dans les carrés latins mais aussi dans tout tableau n par n de n symboles, à condition que chaque symbole apparaisse exactement n fois.

Certaines versions plus faibles de ces conjectures ont été prouvées :

• Tout carré latin de taille n x n possède une transversale partielle de taille 2 n /3.
• Tout carré latin de taille n x n possède une transversale partielle de taille n − sqrt( n ).
• Tout carré latin de taille n x n possède une transversale partielle de taille n − 11 log²
  ₂( n ).
• Tout carré latin de taille n x n possède une transversale partielle de taille n − O(log n/loglog n).
• Tout carré latin n x n suffisamment grand possède une transversale partielle de taille n −1. (Préimpression)

Pour les petits carrés, il est possible de générer des permutations et de tester si la propriété du carré latin est respectée. Pour les carrés plus grands, l'algorithme de Jacobson et Matthews permet d'échantillonner à partir d'une distribution uniforme sur l'espace de n × n carrés latins.

• Dans la conception d'expériences , les carrés latins sont un cas particulier de plans ligne-colonne pour deux facteurs de blocage .
• En algèbre , les carrés latins sont apparentés aux généralisations de groupes ; en particulier, les carrés latins sont caractérisés comme étant les tables de multiplication ( tables de Cayley ) de quasi-groupes . Une opération binaire dont la table de valeurs forme un carré latin est dite obéir à la propriété du carré latin .

Les ensembles de carrés latins orthogonaux les uns aux autres ont trouvé une application en tant que codes correcteurs d'erreurs dans les situations où la communication est perturbée par plus de types de bruit que le simple bruit blanc , comme lors d'une tentative de transmission d'Internet à haut débit sur des lignes électriques.

Premièrement, le message est envoyé en utilisant plusieurs fréquences, ou canaux, une méthode courante qui rend le signal moins vulnérable au bruit à une fréquence donnée. Une lettre du message à envoyer est codée en envoyant une série de signaux à différentes fréquences à des intervalles de temps successifs. Dans l'exemple ci-dessous, les lettres A à L sont codées en envoyant des signaux à quatre fréquences différentes, dans quatre intervalles de temps. La lettre C, par exemple, est codée en envoyant d'abord à la fréquence 3, puis 4, 1 et 2.

Le codage des douze lettres est formé de trois carrés latins orthogonaux entre eux. Imaginons maintenant qu'il y ait du bruit ajouté dans les canaux 1 et 2 pendant toute la transmission. La lettre A serait alors captée comme suit :

En d'autres termes, dans le premier créneau, nous recevons des signaux provenant à la fois des fréquences 1 et 2, tandis que le troisième créneau reçoit des signaux provenant des fréquences 1, 2 et 3. À cause du bruit, nous ne pouvons plus dire si les deux premiers créneaux étaient 1,1 ou 1,2 ou 2,1 ou 2,2. Mais le cas 1,2 est le seul qui donne une séquence correspondant à une lettre du tableau ci-dessus, la lettre A. De même, nous pouvons imaginer une explosion de parasites sur toutes les fréquences dans le troisième créneau :

Là encore, nous pouvons déduire du tableau des codages que c'est la lettre A qui a été transmise. Le nombre d'erreurs que ce code peut détecter est inférieur d'une unité au nombre de créneaux horaires. Il a également été prouvé que si le nombre de fréquences est un nombre premier ou une puissance d'un nombre premier, les carrés latins orthogonaux produisent des codes de détection d'erreurs aussi efficaces que possible.

Le problème de déterminer si un carré partiellement rempli peut être complété pour former un carré latin est NP-complet .

Les puzzles de Sudoku populaires sont un cas particulier de cases latines ; toute solution à un puzzle de Sudoku est une case latine. Le Sudoku impose une restriction supplémentaire : neuf sous-cases adjacentes 3×3 particulières doivent également contenir les chiffres 1 à 9 (dans la version standard). Voir également Mathématiques du Sudoku .

Les puzzles plus récents KenKen et Strimko sont également des exemples de carrés latins.

Les carrés latins ont été utilisés comme base pour plusieurs jeux de société, notamment le populaire jeu de stratégie abstrait Kamisado .

Les carrés latins sont utilisés dans la conception d’expériences de recherche agronomique pour minimiser les erreurs expérimentales.

Le carré latin figure également dans les armes de la Société statistique du Canada , étant mentionné spécifiquement dans son blason . Il apparaît également dans le logo de la Société internationale de biométrie .

• Un rectangle latin est une généralisation d'un carré latin dans lequel il y a n colonnes et n valeurs possibles, mais le nombre de lignes peut être inférieur à n . Chaque valeur apparaît toujours au plus une fois dans chaque ligne et colonne.
• Un carré gréco-latin est une paire de deux carrés latins tels que, lorsque l'un est posé sur l'autre, chaque paire ordonnée de symboles apparaît exactement une fois.
• Un hypercube latin est une généralisation d'un carré latin de deux dimensions à plusieurs dimensions.