Quadrato latino

In matematica, in particolare in combinatoria, un quadrato latino è una tabella quadrata di lato n con un simbolo su ogni casella, disposti in modo che ognuno di essi compaia una e una sola volta in ogni riga e in ogni colonna. Un quadrato latino di ordine n può anche essere visto come una particolare matrice n × n a componenti in un insieme S con n elementi, come {1,...,n}.

Le tavole di composizione dei quasigruppi con n elementi (in particolare di gruppi finiti) sono quadrati latini di ordine n e viceversa: ogni quadrato latino di ordine n definisce una struttura di quasigruppo sull'insieme S dei suoi simboli.

In particolare, poiché esistono gruppi finiti di ogni cardinalità, esistono anche quadrati latini di ogni ordine.

I quadrati latini a fianco sono ottenuti dalle tavole di composizione del gruppo ciclico ${\displaystyle \mathbb {Z} /4\mathbb {Z} }$ e del gruppo di Klein ${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /2\mathbb {Z} }$.

Continuando il parallelo con le tavole di composizione, un quadrato latino su S={1,...,n} può dunque essere identificato con la relazione ternaria R su S³, definita dalle triple (i,j,k) per cui «nella casella (i,j) c'è il simbolo k».

Per la definizione di quadrato latino, ogni proiezione di R su due coordinate è iniettiva, ovvero per ogni scelta di due coordinate esiste una e una sola tripla (i,j,k) in R con quelle due coordinate. Equivalentemente, un quadrato latino su S è costituito da n² triple, tali che in ciascuna coppia di indici le possibile coppie di simboli compaiano una e una sola volta:

• in ogni casella c'è esattamente un simbolo;
• in ogni riga ogni simbolo compare esattamente una volta;
• in ogni colonna ogni simbolo compare esattamente una volta.

Scambiando tra loro due righe, due colonne, o due simboli (o più in generale applicando loro una trasposizione o una permutazione) di un quadrato latino si ottiene di nuovo un quadrato latino. Due quadrati latini che possono essere ottenuti l'uno dall'altro tramite queste operazioni si dicono isotopi. L'isotopia è dunque una relazione di equivalenza.

Nella rappresentazione come relazione R si possono inoltre permutare tra loro i tre indici di riga, colonna e simbolo. In particolare lo scambio dei primi due corrisponde alla trasposizione della matrice.

Una variante del quadrato latino è il quadrato greco-latino: una scacchiera quadrata di lato n con coppie di simboli su ogni casella, disposti in modo che ogni simbolo compaia una e una sola volta in ogni riga e in ogni colonna, e che ogni coppia compaia una e una sola volta.

Ogni quadrato greco-latino è dato da una coppia di quadrati latini "ortogonali". In origine i due quadrati latini venivano riempiti rispettivamente con lettere dell'alfabeto greco e di quello latino, da cui il nome greco-latino.

Un quadrato greco-latino può essere rappresentato dalle quadruple di indici (i, j, k, l) per cui vale la relazione «nella casella (i, j) c'è la coppia (k, l)». Un quadrato greco-latino è costituito da n² quadruple, tali che in ciascuna coppia di indici le possibile coppie di simboli compaiano una e una sola volta.

Nel 1782^[1] Eulero propose il Problema degli ufficiali: disporre su una scacchiera 36 ufficiali appartenenti a 6 reggimenti diversi e con 6 gradi diversi, in modo che in ogni riga e in ogni colonna siano rappresentati tutti i reggimenti e tutti i ranghi. Il problema degli ufficiali è equivalente alla costruzione di un quadrato greco-latino di lato 6.

Si possono costruire quadrati greco-latini di lato n ogni n maggiore di 2 e diverso da 6. Eulero dimostrò che si possono costruire quadrati greco-latini di ordine n per ogni n dispari o multiplo di 4, congetturando che questo non fosse possibile per n=2 (mod 4). Nel 1901^[2] Tarry provò la congettura per n=6, mostrando quindi che il problema degli ufficiali non ammette soluzione. Nel 1960^[3] Bose, Parker e Shrikhande, dopo aver già confutato la congettura di Eulero, mostrarono che il problema ammette soluzione per ogni n=2 (mod 4) maggiore di 6.

La sestina lirica è una struttura poetica costituita da 6 stanze di 6 versi (più 3 di congedo). Una delle regole secondo cui viene costruita prevede che ogni verso termini con una tra 6 parole possibili, le quali non possono comparire due volte nella stessa stanza, né due volte nello stesso verso di stanze diverse. Scrivendo queste parole all'interno di un quadrato, in funzione della stanza e del verso in cui compaiono, si costruisce un quadrato latino.

Il romanzo La vita: istruzioni per l'uso dell'oulipista Georges Perec fa abbondante uso di quadrati greco-latini. In esso viene descritto un immobile parigino di 100 stanze disposte su 10 piani, come in una scacchiera quadrata di lato 10. Ogni capitolo è riservato alla narrazione di una singola stanza. Per scrivere il romanzo Perec, come spiega nel suo Cahier des charges, stila 42 liste di 10 elementi ciascuna, corrispondenti a vincoli narrativi (mobilio, persone, ecc.), le divide in 21 coppie e attribuisce ad ognuna un quadrato greco-latino di lato 10, le cui caselle corrispondono alle stanze dell'immobile. Ogni stanza è quindi caratterizzata da 42 vincoli narrativi.

• (EN) J. H. Dénes, A. D. Keedwell (1974): Latin Squares and their Applications, Academic Press
• (EN) J. H. Dénes, A. D. Keedwell (1991): Latin Squares. New developments in the theory and applications, Academic Press

• Quadrato magico
• Sestina
• Sudoku
• Tavola di composizione

• Wikimedia Commons contiene immagini o altri file su quadrato latino

• (EN) Latin square, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Quadrato latino, su MathWorld, Wolfram Research.
• (EN) Quadrato latino, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) Eric Zhi Chen, Complete Sets of MOLS (mutually orthogonal Latin squares), su moodle.tec.hkr.se. URL consultato il 10 novembre 2022 (archiviato dall'url originale il 25 dicembre 2012).
• (FR) Le liste de La vita: istruzioni per l'uso, su escarbille.free.fr.

V · D · M Combinatoria
Orientamento generale	Combinatoria · Storia della combinatoria · Matematica discreta · Sezione 05-XX di MSC
Nozioni introduttive	Permutazioni · Disposizioni · Combinazioni · Coefficienti binomiali · Partizioni di interi · Partizioni di insiemi finiti - Identità combinatorie e biiezioni · Principio dei cassetti
Configurazioni	Quadrati latini · Quadrati magici · Disegni a blocchi · Geometrie finite · Matroidi - Tassellazioni · Polimini
Teoria dei grafi	Alberi · Cammini sui grafi (euleriani, hamiltoniani) · Connessione nei grafi - Grafi planari · Colorazione dei grafi e teorema dei quattro colori) · Ipergrafi · Grafi e gruppi · Digrafo · Flussi su grafi · Passeggiate aleatorie su grafi · Omomorfismo fra grafi · Algoritmi sui grafi
Combinatoria algebrica	Tavola di Young · Funzioni simmetriche - Serie formale di potenze · Funzioni generatrici · Polinomi ortogonali · Azioni di un gruppo su strutture combinatorie - Aspetti combinatorici dell'algebra commutativa
Altre aree	Calcolo umbrale (sequenze polinomiali di tipo binomiale · sequenze di Sheffer) - Combinatoria estremale

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica