Matematica Discreta Lezione del giorno 19 novembre 2008 Inversioni e parità di una permutazione Abbiamo introdotto il concetto di permutazione di n elementi a

Matematica Discreta

Lezione del giorno 19 novembre 2008 Inversioni e parità di una permutazione

Abbiamo introdotto il concetto di permutazione di n elementi a 1 ,a 2 ,…,a n di un generico insieme A.

Ora studieremo il caso particolare in cui si tratti di una permutazione dei primi n numeri naturali consecutivi 1,2,….,n .

Data una permutazione dei primi n numeri naturali consecutivi 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 1 2 … n, corrispondente alla funzione identica, 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. 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 il 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.

Regole pratiche per i casi particolari n=2, n=3 Il caso 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: 21; 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” /)

Il caso 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, detto metodo di Laplace, 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

Il metodo di Laplace per il calcolo del determinante si basa sul seguente Teorema (di cui non esporremo la dimostrazione):

Teorema: Data una qualunque matrice quadrata nxn, il suo determinante si può calcolare fissando a piacere una riga o una colonna e sommando tutti i prodotti degli elementi della riga (o della colonna) moltiplicati per i loro rispettivi complementi algebrici.

Quando si applica tale Teorema per calcolare il determinante si parla di sviluppo di Laplace secondo una riga (o secondo una colonna).

Poiché i complementi algebrici sono (a meno del segno) determinanti di matrici con 1 riga e 1 colonna in meno, il calcolo del determinante viene ricondotto a matrici con un numero sempre più piccolo di righe e colonne, fino a pervenire a matrici 3x3, a cui si può applicare la regola pratica di Sarrus.

E’ ovvio che, da un punto di vista strategico, conviene fissare una riga o una colonna con molti elementi nulli, perché il loro prodotto con i rispettivi complementi algebrici sarà 0.

Esempio: calcoliamo il determinante della seguente matrice 4x4:

M =



 









 









 1 1 2 1

2 1 0 2

1 3 0 1

3 2 3 1

Fissata la seconda colonna (che contiene 2 zeri) basta sommare i prodotti degli elementi non nulli della colonna (che sono i numeri 3 e 2) per i loro complementi algebrici.

Si ottiene il seguente calcolo:

det(M) = -3∙det

 







 









 1 1 1

2 1 2

1 3 1

+2∙det

 







 







2 1 2

1 - 3 1

3 2 1

Il calcolo si può poi completare applicando la regola di Sarrus alle due matrici 3x3 ottenute sopra.

Se per esempio si deve calcolare il determinante di una matrice 5x5, lo sviluppo di Laplace

riconduce il calcolo a quello di 5 (al più) determinanti di matrici 4x4, ognuno dei quali a sua volta

comporta il calcolo di 4 (al più) determinanti di matrici 3x3: in totale basta calcolare 20 (al più)

determinanti di matrici 3x3.