Siano A={a 1 , a 2,….., a n }, B={b 1 , b 2,….., b n } due insiemi finiti di eguale cardinalità n, e sia f: A  B una funzione biunivoca.

Matematica Discreta

Lezione del giorno 18 novembre 2008 Permutazioni

Siano A={a 1 , a 2,….., a n }, B={b 1 , b 2,….., b n } due insiemi finiti di eguale cardinalità n, e sia f: A  B una funzione biunivoca.

Possiamo rappresentare la funzione f in modo sintetico costruendo 2 righe: nella prima vi sono gli elementi di A (in un certo ordine fissato) e nella seconda, sotto ogni elemento di A, vi è il suo corrispondente in B (tramite la funzione f):

f = _



 





) f(a . . ) f(a ) f(a

a . . a a

n 2

1

n 2

1

Essendo f surgettiva, nella seconda riga sono presenti tutti gli elementi b 1 , b 2,….., b n di B, disposti in un certo ordine.

Definiremo permutazione degli elementi b

, b

, ….., b

un qualunque modo di disporre ordinatamente gli elementi b 1 , b 2 , ….., b n (quindi una qualunque delle seconde righe che si ottengono rappresentando le diverse funzioni biunivoche f: A  B ).

Ne segue che le permutazioni possibili di b 1 , b 2 , ….., b n sono tante quante le possibili funzioni biunivoche f: A  B, quindi sono in numero di n! .

Esempio:

Se n=3, A={a 1 , a 2 , a 3 }, B={b 1 , b 2 , b 3 }, si ottengono 3!=6 funzioni biunivoche f: A  B e in corrispondenza 6 permutazioni degli elementi b 1 , b 2 , b 3 :

b 1 b 2 b 3 , b 1 b 3 b 2 , b 2 b 1 b 3 , b 2 b 3 b 1 , b 3 b 2 b 1 , b 3 b 1 b 2

Consideriamo ora il caso particolare in cui A coincida con B, ed entrambi contengano i primi n numeri naturali consecutivi: A = B = { 1,2,…..,n }.

Data una permutazione dei numeri naturali 1, 2, ….., n, e fissati due numeri distinti i,j compresi fra 1 ed n, diremo che la permutazione ha una inversione in i,j se nella permutazione i numeri compaiono in ordine opposto a quello naturale (ossia se il maggiore dei 2 compare a sinistra del minore).

Per esempio la seguente permutazione dei numeri 1,2,3,4,5:

21453

presenta una inversione in 2,1, una inversione in 4,3, una inversione in 5,3.

Una permutazione dei numeri naturali 1, 2, ….., n è detta di classe pari o di classe dispari a secondo se il numero totale di inversioni che presenta è pari o dispari (la permutazione “identica” 1 2 … n, che presenta 0 inversioni, si considera di classe pari).

Per esempio, la permutazione 21453 dei numeri 1,2,3,4,5 dell’esempio precedente è di classe dispari, perché ha 3 inversioni.

Determinante di una matrice quadrata

Consideriamo una matrice con n righe ed m colonne (brevemente la chiameremo matrice nxm):

essa è una tabella di nxm caselle disposte in n righe ed m colonne; nelle caselle supporremo che vi siano valori numerici (o più in generale valori scelti in un campo, dove per la definizione di

“campo” si rimanda al corso di Geometria). Si dice che la matrice è quadrata se n=m (cioè se ha

lo stesso numero di righe e di colonne).

In una matrice generica nxm indicheremo con il simbolo a ij l’elemento della matrice nella casella all’incrocio tra la riga i e la colonna j. Con tale convenzione, una generica matrice quadrata nxn sarà rappresentata da:

M =

 

 

 

 





 

 

 

 





nn n2

n1

3n 32

31

2n 22

21

1n 12

11

a . . . a a

. . . . . .

. . . . . .

a a

a

a a

a

a a

a

Sia data una generica matrice quadrata nxn, rappresentata come sopra.

Consideriamo nella matrice nxn un prodotto di n fattori, dove i fattori sono scelti fra gli elementi della matrice ma in modo che essi si trovino tutti su righe e colonne diverse. Per costruire uno di tali prodotti potremmo procedere come segue: il primo fattore è scelto fra gli elementi della prima riga, il secondo fra gli elementi della seconda riga (ma in una colonna diversa da quella del primo fattore), etc…., l’ultimo fattore fra gli elementi della riga numero n (ma in una colonna diversa da quella dei primi n-1 fattori)

Dunque uno di tali prodotti si può indicare formalmente con:

a 1? a 2? a 3? …..a n?

dove i punti interrogativi ‘?’ messi come secondi indici sono quelli delle diverse colonne in cui si sceglieranno i fattori del prodotto. Poiché le colonne devono essere diverse tra loro, i punti interrogativi ‘?’ saranno tutti i numeri naturali da 1 ad n in un certo ordine. Quindi il prodotto costruito con tale criterio avrà la forma:

a 1j

a 1j

a 1j

...a 1j

dove gli indici di colonna j 1 , j 2 , j 3 , …., j n formano una permutazione dei numeri naturali 1,2,…,n.

In totale, facendo variare la permutazione degli indici di colonna, si ottengono n! possibili prodotti costruiti con il criterio precedente.

Esempio: In una matrice 3x3:

 







 







33 32 31

23 22 21

13 12 11

a a a

a a a

a a a

si ottengono 3!=6 prodotti possibili, ed esattamente i seguenti:

33 22 11 a a

a , a 13 a 21 a 32 , a 12 a 23 a 31 , a 11 a 23 a 32 , a 13 a 22 a 31 a ₁₂ a ₂₁ a ₃₃

corrispondenti rispettivamente alle 6 permutazioni di indici di colonna: 123, 312, 231, 132, 321, 213.

Definiremo determinante della matrice quadrata nxn quel numero ottenuto sommando gli n!

prodotti di n fattori (costruiti come sopra), e dove ogni prodotto é preso con il suo segno se la permutazione degli indici di colonna corrispondente è di classe pari, e con il segno opposto se la permutazione degli indici di colonna corrispondente è di classe dispari.

Se M è una matrice nxn, det(M) indicherà il suo determinante.

I casi particolari n=2, n=3

n=2: in una generica matrice matrice 2x2:

M = _



 





22 21

12 11

a a

a a

i possibili prodotti di 2 fattori da considerare sono i numero di 2!=2 e sono i seguenti:

a 11 a 22 (permutazione degli indici di colonna: 12; numero inversioni: 0; classe: pari) a 12 a 21 (permutazione degli indici di colonna: 12; numero inversioni: 1; classe: dispari) dunque il determinante è in questo caso:

det(M)=a 11 a 22 – a 12 a 21 .

Questo porta alla seguente regola pratica per il calcolo del determinante di una matrice 2x2:

basta calcolare la differenza dei prodotti “in croce”, cioè dei prodotti degli elementi che si trovano lungo le diagonali (differenza fra il prodotto degli elementi della diagonale “principale” \ e il prodotto di quelli della diagonale “secondaria” /)

n=3: in una generica matrice 3x3:

M=   





 







33 32 31

23 22 21

13 12 11

a a a

a a a

a a a

i possibili prodotti di 3 fattori da considerare sono i numero di 3!=6 e sono i seguenti:

33 22 11 a a

a (permutazione degli indici di colonna: 123; numero inversioni: 0, classe: pari)

32 21 13 a a

a (permutazione degli indici di colonna: 312; numero inversioni: 2, classe: pari)

31 23 12 a a

a (permutazione degli indici di colonna: 231; numero inversioni: 2, classe: pari)

32 23 11 a a

a (permutazione degli indici di colonna: 132; numero inversioni: 1, classe: dispari)

31 22 13 a a

a (permutazione degli indici di colonna: 321; numero inversioni: 3, classe: dispari)

33 21 12 a a

a (permutazione degli indici di colonna: 213; numero inversioni: 1, classe: dispari) dunque il determinante è in questo caso:

det(M)=a 11 a 22 a 33 +a 13 a 21 a 32 +a 12 a 23 a 31 -a 11 a 23 a 32 -a 13 a 22 a 31 -a 12 a 21 a 33 .

Anche per calcolare il determinante delle matrici 3x3 esiste una regola pratica (detta di Sarrus): si ricopiano le prime due righe sotto la terza e si sommano i 6 prodotti nelle diagonali (quelle che contengono 3 termini ciascuna), con il loro segno quelli lungo le diagonali \ da sinistra in alto verso destra in basso, e con il segno opposto quelli lungo le altre diagonali / :

M=   





 







33 32 31

23 22 21

13 12 11

a a a

a a a

a a a

a 11 a 12 a 13

a 21 a 22 a 23

Per le matrici nxn con n>3, può essere complicato calcolare il determinante usando la semplice definizione (per esempio in una matrice 4x4 vi sono 4!=24 prodotti da sommare), quindi si usa un metodo di calcolo, che si basa sui concetti di minore complementare e di complemento algebrico.

Sia M una matrice nxn (quadrata) e si fissi un elemento a ij nella matrice : l’elemento si trova dunque nella riga i e nella colonna j.

Si definisce minore complementare dell’elemento a

il determinante della matrice quadrata ottenuta cancellando, nella matrice data, la riga i e la colonna j (quindi è il determinante di una matrice quadrata (n-1)x(n-1)) .

Esempio. Nella seguente matrice 3x3:

M =   





 







33 32 31

23 22 21

13 12 11

a a a

a a a

a a a

il minore complementare dell’elemento a 23 è il determinante della matrice 2x2 ottenuta cancellando la riga 2 e la colonna 3, quindi è il seguente determinante:

 

 





32 31

12 11

a a

a

det a = a 11 a 32 – a 12 a 31

Si definisce invece complemento algebrico dell’elemento a

il minore complementare dell’elemento a ij nel modo seguente: se i+j è pari il complemento algebrico coincide con il minore complementare, mentre se i+j è dispari il complemento algebrico coincide con l’opposto del minore complementare.

Nell’esempio precedente, essendo i+j=2+3=5 dispari, il minore complementare dell’elemento a 23 è l’opposto del minore complementare:

- (a 11 a 32 – a 12 a 31 ) = - a 11 a 32 + a 12 a 31 .