Quadrato latino

Da Wikipedia, l'enciclopedia libera.

In matematica, in particolare in combinatoria, un quadrato latino è una scacchiera quadrata di lato n con un simbolo su ogni casella, 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}.

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

Tavole di composizione[modifica | modifica sorgente]

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

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 \mathbb{Z}/4\mathbb{Z} e del gruppo di Klein \mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/2\mathbb{Z}.


Rappresentazione ternaria[modifica | modifica sorgente]

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 S3, 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 n2 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.

Equivalenze[modifica | modifica sorgente]

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.

Un quadrato greco-latino

Il quadrato greco-latino[modifica | modifica sorgente]

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 n2 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.

Il quadrato latino nella letteratura[modifica | modifica sorgente]

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.

Stanza 1 Stanza 2 Stanza 3 Stanza 4 Stanza 5 Stanza 6
Verso 1 A F C E D B
Verso 2 B A F C E D
Verso 3 C E D B A F
Verso 4 D B A F C E
Verso 5 E D B A F C
Verso 6 F C E D B A

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.

Note[modifica | modifica sorgente]

  1. ^ Euler, Leonhard, Recherches sur une Nouvelle Espece de Quarres Magiques, Verh. Genootsch. der Wet. Vlissingen, 9, 85-232 (1782).
  2. ^ Tarry, G., Le Problème de 36 Officiers, Comptes Rendu de l'Association Française pour l'Avancement de Science Naturel 1, 122-123 (1900); 2, 170-203 (1901).
  3. ^ Bose, R. C.; Shrikhande, S. S.; Parker, E. T., Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler's conjecture, Canad. J. Math. 12, 189-203 (1960).

Bibliografia[modifica | modifica sorgente]

  • (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

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

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