Matematica Discreta
Lezione del giorno 8 maggio 2009
Applicheremo alcuni risultati della teoria dei gruppi alla teoria dei quadrati latini e greco-latini.
Ricordiamo che un quadrato latino di ordine n è una matrice nxn i cui elementi sono scelti in un insieme A di cardinalità n, e tale che in nessuna riga e nessuna colonna vi siano due elementi uguali.
Dati 2 quadrati latini di ordine n:
X=(aij), Y=(bij) (con i=1,2,….,n; j=1,2,….,n)
si dice che essi sono ortogonali se la matrice nxn che ha nella casella della riga i e colonna j la coppia (aij,bij) contiene n2 coppie tutte diverse (tale matrice è detta quadrato greco-latino).
Dimostreremo, con la teoria dei gruppi finiti, che è possibile costruire per ogni naturale n>1 dispari coppie di quadrati latini ortogonali di ordine n.
Premettiamo un risultato:
Teorema. Se A è un gruppo commutativo finito di cardinalità dispari n, e se x,y sono elementi di A tali che x2=y2 si ha necessariamente x=y.
Dimostrazione:
Essendo n dispari, n-1 è pari, dunque n-1=2k con k numero naturale, cioè n=2k+1.
Calcolando le potenze xn+1, yn+1 con le regole sulle potenze, e tenendo conto che, per un Teorema precedente, elevando ogni elemento di A alla cardinalità n si ottiene l’elemento neutro di A, si ha:
xn+1 = xn*x1 = x ; yn+1 = yn*y1 = y D’altra parte da x2=y2 si ha :
x = xn+1 = x2k+2 = (x2)k*x2 = (y2)k*y2 = y2k+2 = yn+1 = y cioé la tesi.
Osservazione: poiché il Teorema usato nella dimostrazione (elevando ogni elemento di un gruppo finito alla cardinalità del gruppo si ottiene l’elemento neutro) vale anche nel caso di un gruppo non commutativo, anche il Teorema precedente vale nel caso di un gruppo non commutativo.
Sia A un gruppo commutativo finito di cardinalità n dispari. Costruiremo due quadrati latini ortogonali di ordine n che hanno elementi in A.
Siano a1, a2,….., an gli n elementi distinti di A.
Il primo quadrato è la tavola dell’operazione * di A: è la matrice nxn in cui nella casella in riga i e colonna j vi è l’elemento ai*aj. Sappiamo che tale matrice è un quadrato latino, come dimostrato in una delle lezioni precedenti, sfruttando le leggi di cancellazione valide in A.
Il secondo quadrato è costruito in modo simile: è la matrice nxn in cui nella casella in riga i e colonna j vi è l’elemento ai*aj’ (dove aj’ indica il simmetrico di aj) . Dimostriamo che tale matrice è un quadrato latino: se per assurdo nella riga i vi fossero 2 elementi uguali in colonne diverse j,k si avrebbe:
ai*aj’ = ai*ak’
dalla legge di cancellazione a sinistra seguirebbe aj’ = ak’, e calcolando il simmetrico di ambo i membri si avrebbe aj = ak, contraddizione perché a1, a2,….., an sono n elementi distinti.
Un’analoga contraddizione si otterrebbe supponendo per assurdo l’esistenza nella colonna j di 2 elementi uguali in righe diverse i,k.
Dimostriamo ora che i 2 quadrati latini costruiti sono ortogonali.
Se per assurdo così non fosse, nel quadrato delle coppie di elementi dei 2 quadrati vi sarebbero 2 coppie uguali in caselle diverse: dunque la coppia (ai*aj , ai*aj’) nella casella in riga i, colonna j, coinciderebbe con la coppia (ar*as , ar*as’) nella casella in riga r, colonna s, da cui le eguaglianze
ai*aj = ar*as ; ai*aj’ = ar*as’
Essendo le caselle diverse, dovrebbero essere diversi gli indici di riga i,r oppure gli indici di colonna j,s: supponiamo per esempio js (se è is si ragiona in modo analogo).
Dalla prima delle 2 eguaglianze, componendo a destra ambo i membri con aj’ si ha:
ai = ar*as*aj’
e sostituendo nella seconda eguaglianza si ha:
ar*as*aj’*aj’ = ar*as’
Dalla legge di cancellazione a sinistra segue:
as*aj’*aj’ = as’
e componendo a sinistra ambo i membri con as’:
aj’*aj’ = as’*as’
dunque (aj’)2 = (as’)2 e per il Teorema precedente aj’ = as’, da cui calcolando il simmetrico di ambo i membri si avrebbe aj = as, contraddizione perché a1, a2,….., an sono n elementi distinti.
Esempio. Costruiamo 2 quadrati latini ortogonali di ordine n=7. Fissiamo un gruppo commutativo finito di cardinalità 7, per esempio Z7 = {0,1,2,3,4,5,6} rispetto all’operazione di somma fra classi (identifichiamo ogni classe [a] con il suo rappresentante).
Il primo quadrato è la matrice nxn che rappresenta la tavola dell’operazione:
0 1 2 3 4 5 6
1 2 3 4 5 6 0
2 3 4 5 6 0 1
3 4 5 6 0 1 2
4 5 6 0 1 2 3
5 6 0 1 2 3 4
6 0 1 2 3 4 5
Il secondo quadrato è costruito in modo analogo, ma in ogni casella vi è la somma di un elemento e del simmetrico di un altro elemento (si deve ricordare che per una classe [a][0] il simmetrico è la classe [7-a]):
0 6 5 4 3 2 1 1 0 6 5 4 3 2 2 1 0 6 5 4 3 3 2 1 0 6 5 4 4 3 2 1 0 6 5 5 4 3 2 1 0 6 6 5 4 3 2 1 0
Il quadrato greco-latino ottenuto dalle coppie di elementi dei 2 quadrati è:
00 16 25 34 43 52 61 11 20 36 45 54 63 02 22 31 40 56 65 04 13 33 42 51 60 06 15 24 44 53 62 01 10 26 35 55 64 03 12 21 30 46 66 05 14 23 32 41 50
e come previsto tale quadrato contiene 49=72 coppie tutte diverse.
