Data Mining e Analisi Multivariata PDF

Data Mining e Analisi Multivariata Elementi di Algebra Lineare Le note sono state redatte principalmente sulla base del file intitolato Estratto_libro_regr.pdf messo a dispozione dal Prof. Riani alla pagina http://www.riani.it/ADM/lucidi/Estratto_libro_regr.pdf....

Data Mining e Analisi Multivariata Elementi di Algebra Lineare Le note sono state redatte principalmente sulla base del file intitolato Estratto_libro_regr.pdf messo a dispozione dal Prof. Riani alla pagina http://www.riani.it/ADM/lucidi/Estratto_libro_regr.pdf. Natalia Golini CLEST - 2023-2024 - Università degli Studi di Torino 1/36 Cosa impareremo? Matrici Operazioni con le matrici Il determinante e la matrice inversa Matrici idempotenti e ortogonali Vettori linearmente indipendenti e rango di una matrice Traccia e sue proprietà 2/36 Definizione di matrice ↭ Una matrice è un insieme di numeri reali ordinati per righe e per colonne. ↭ Le matrici vengono generalmente indicate con le lettere maiuscole. ↭ Per maggiore chiarezza di esposizione a volte come pedice riportiamo il numero di righe e di colonne della matrice. ↭ Ciascun elemento della matrice è indicato con una lettera minuscola accompagnata dal numero della riga e dal numero della colonna in cui esso si trova. aij è l’elemento situato all’incrocio della i-esima riga e j-esima colonna. Ad esempio, data la seguente matrice A:   1 2 3 8 A = 3 1 2 4 3→4 4 5 6 9 a14 = 8, a22 = 1, a32 = 5,... 3/36 Vettore riga e vettore colonna Il vettore riga non è altro che una matrice di dimensioni 1 → n, cioè una matrice i cui elementi sono disposti su una sola riga. % & a↑ = 1 3 4 1→3 Il vettore colonna è una matrice di dimensione n → 1, cioè una matrice i cui elementi sono disposti su una sola colonna.   1 a = 3 3→1 4 Tutte le volte che si parla genericamente di un vettore ci si riferisce sempre al vettore colonna. 4/36 Matrice quadrata Una matrice il cui numero di righe e di colonne è uguale è detta matrice quadrata. L’ordine di una matrice quadrata può essere indicato con un solo numero. Ad esempio: ( ' 1 2 B = 2→2 3 4 B 2 è una matrice quadrata 2 → 2.   1 2 3 C = 3 1 2 3→3 4 5 6 C 3 è una matrice quadrata 3 → 3. 5/36 Diagonale principale di una matrice quadrata Data una matrice quadrata A di ordine m, la diagonale principale di A è l’insieme degli elementi aij per i quali i = j. Ad esempio, data la matrice quandrata C di ordine 3   1 2 3 C = 3 1 2 3→3 4 5 6 gli elementi sulla diagonale principale sono costituiti da 1, 1 e 6. 6/36 Tipi particolari di matrici quadrate ↭ matrice simmetrica: in cui aij = aji per ogni i e j = 1, 2,.... Cioè, gli elementi della prima riga sono uguali ai corrispondenti elementi della prima colonna, gli elementi della seconda riga sono uguali ai corrispondenti elementi della seconda colonna e così via per ogni riga e colonna della matrice. ↭ matrice diagonale: dove aij = 0 per i ↑= j. In matrice diagonale gli elementi che non si trovano sulla diagonale principale sono tutti uguali a 0. 7/36 Esempio Matrice simmetrica:   1 2 3 A = 2 4 7 3 7 5 Matrici diagonali:   ' ( 3 0 0 1 0 D= E = 0 8 0 0 4 0 0 6 Talvolta, le matrici diagonali sono indicate con il simbolo diag(a11 ,... , amm ). Ad esempio, le matrice D ed E potevano essere indicate rispettivamente con D = diag(1, 4) e E = diag(3, 8, 6). In R la diagonale di una matrice viene ottenuta con la funzione diag(). 8/36 Matrice trasposta L’operazione di trasposizione consiste nel sostituire alle righe di una matrice le sue colonne e viceversa. L’operazione di trasposizione si indica con un apice ↑. Ad esempio, se     1 3 4 1 2 3 8 2 1 5 A = 3 1 2 4 A = ↑ 3  2 6 4 5 6 9 8 4 9 oppure se   2 % & a = ↓3 ↑ a = 2 ↓3 1 1 9/36 Matrice trasposta (Cont.) Se trasportiamo una matrice trasposta essa ritorna la matrice di partenza In R l’operazione di trasposizione viene e!ettuata utilizzando la funzione t(). Se l’operazione di trasposizione viene applicata due volte, il risultato è la matrice originale: (A↑ )↑ = A     1 3 4   1 2 3 8 2 1 2 3 8 1 5 A = 3 1 2 4 A = ↑ 3  (A↑ )↑ = 3 1 2 4 = A 2 6 4 5 6 9 4 5 6 9 8 4 9 Se la matrice trasposta è uguale alla matrice originaria (A = A↑ ), allora la matrice è simmetrica. 10/36 Somma di matrici e di vettori Se due matrici (vettori) presentano la stessa dimensione la loro somma si e!ettua aggiungendo i rispettivi elementi. Ad esempio, se       ↓2 5 3 ↓2 1 3 A= 3 1 , B =4 5 , A+B =7 6 7 ↓6 10 ↓3 17 ↓9 In R l’operazione di trasposizione viene e!ettuata utilizzando l’operatore +. 11/36 Moltiplicazione di matrici e di vettori A"nché il prodotto di due matrici A e B sia definito, è necessario che il numero di colonne della matrice A (matrice premoltiplicante) sia uguale al numero di righe della matrice B (matrice postmoltiplicante). Se questa condizione è verificata, le matrici si dicono conformabili. L’elemento che si trova all’incrocio della riga i-esima e della colonna j-esima della matrice C = A → B è dato da: + cij = aik bkj k 12/36 Moltiplicazione di matrici e di vettori (Cont.) In altri termini, cij è la somma dei prodotti della riga i-esima di A e della colonna j-esima di B. Nella moltiplicazione matriciale, quindi, moltiplichiamo ogni riga di A per ogni colonna di B. La dimensione della matrice prodotto C = AB avrà un numero di righe uguale a quello della matrice A ed un numero di colonne uguale a quello della matrice B. Quindi, se A , B , allora A B = C. n→m m→p n→mm→p n→p In R l’operazione di prodotto matriciale viene e!ettuata utilizzando l’operatore %*%. 13/36 Esempio: prodotto matriciale Date le matrici:   2 1 3   4 1 4 6 5 A= 7  e B = 2 6 2 3 3 8 1 3 2 Allora     2·1+1·2+3·3 2·4+1·6+3·8 13 38 4 · 1 + 6 · 2 + 5 · 3 4 · 4 + 6 · 6 + 5 · 8 31 92 C = AB =   =  20  20 64 64 13 38 13 38 Si noti che A ha dimensione 4 → 3, B ha dimensione 3 → 2. La matrice prodotto C presenta dimensione 4 → 2. In questo caso quindi, la matrice C presenta una dimensione diversa da quelle di A e B. 14/36 Proprietà del prodotto matriciale Il prodotto matriciale gode della proprietà distributiva sull’addizione e sulla sottrazione: A(B + C ) = AB + AC A(B ↓ C ) = AB ↓ AC (A + B)C = AC + BC (A ↓ B)C = AC ↓ BC Utilizzando la legge distributiva, possiamo espandere prodotti del tipo: (A ↓ B)(C ↓ D) come: (A ↓ B)(C ↓ D) = (A ↓ B)C ↓ (A ↓ B)D = AC ↓ BC ↓ AD + BD La trasposta di un prodotto tra due matrici è uguale al prodotto delle trasposte cambiate di ordine: (AB)↑ = B ↑ A↑. 15/36 Matrice identità Preliminarmente allo sviluppo del determinante e della matrice inversa occorre introdurre una particolare matrice quadrata nota con il nome di matrice identità. La matrice identità non è altro che una matrice diagonale in cui gli elementi sulla diagonale principale sono tutti uguali ad 1. In simboli: aij = 0 per i ↑= j e aii = 1. La matrice identità viene indicata con il simbolo I. Essa può essere indicata con il simbolo Im anziché con I in modo da specificarne in maniera compatta l’ordine. Esempi:   ' ( 1 0 0 1 0 I2 = e I 3 = 0 1 0 0 1 0 0 1 16/36 Matrice identità La matrice identità, svolge nell’algebra lineare, una funzione analoga a quella svolta dal numero 1 nell’algebra tradizionale. Ad esempio, date le due matrici diagonali   '( 3 0 0 1 0 D= E = 0 8 0 0 4 0 0 6 è facile controllare che: DI 2 = I 2 D = D oppure E I 3 = I 3 E = E , In generale, data una matrice quadrata A di ordine m, esiste sempre una matrice I m tale per cui AI m = I m A = A. 17/36 Determinante di una matrice quadrata Data una matrice A quadrata di ordine m, il determinante (indicato con det(A) oppure con |A|) è uno scalare che si ottiene come funzione di tutti gli elementi di A. Più precisamente, data una matrice A quadrata di ordine m, si considerano tutti i gruppi di m elementi che si possono formare con gli m2 elementi della matrice A, mettendo in ciascun gruppo un solo elemento per ciascuna delle m righe e per ognuna delle m colonne. Ad esempio, con m = 3, data   a11 a12 a13 A = a21 a22 a23  a31 a32 a33 avremo: a11 a22 a33 ; a11 a32 a23 ; a12 a21 a33 ; a12 a23 a31 ; a13 a21 a32 ; a13 a22 a31. 18/36 Determinante di una matrice quadrata (Cont.) In generale, il numero di gruppi che si possono formare nel modo suddetto da una matrice quadrata di ordine m è dato dalle permutazioni di m elementi: m! = m(m ↓ 1)(m ↓ 2) · · · 1 Il passo successivo consiste nell’attribuire un segno ai gruppi di elementi così formati. Per fare questo, disponiamo gli elementi all’interno di ciascun gruppo secondo l’ordine crescente del primo deponente: a11 a22 a33 ; a11 a23 a32 ; a12 a21 a33 ; a12 a23 a31 ; a13 a21 a32 ; a13 a22 a31. Contiamo per ciascun gruppo le inversioni che si verificano nell’ordine crescente del secondo deponente, contiamo cioè quante volte il secondo deponente di un elemento è maggiore del secondo deponente di uno degli elementi che lo seguono in uno stesso gruppo. 19/36 Determinante di una matrice quadrata (Cont.) Considerati i i sei gruppi formati dalla matrice A, avremo il seguente risultato: ↭ nessuna inversione per il primo gruppo; ↭ un’inversione per il secondo gruppo; ↭ un’inversione e 2, 2, 3, inversioni rispettivamente, per i rimanenti. Attribuiamo segno + a quei gruppi che hanno un numero pari di inversioni ed un segno ↓ a quei gruppi che hanno un numero dispari di inversioni: a11 a22 a33 ↓ a11 a23 a32 ↓ a12 a21 a33 + a12 a23 a31 + a13 a21 a32 ↓ a13 a22 a31. La somma algebrica dei prodotti degli elementi contenuti in ciascun gruppo è il valore del determinante. 20/36 Esempio: calcolo del determinante Date le matrici:     '( 10 1 1 1 2 3 6 5 A= , B =  3 2 1 , C = 4 5 6 1 1 1 6 9 7 8 9 avremo: |A| = 6 · 1 ↓ 1 · 5 = 1 |B| = 10 · 2 · 9 ↓ 10 · 1 · 6 ↓ 1 · 3 · 9 + 1 · 1 · 1 + 1 · 3 · 6 ↓ 1 · 2 · 1 = 110 |C | = 0 La matrice il cui determinante è pari a 0 si dice singolare. 21/36 Proprietà del determinante ↭ Il determinante di A è uguale al determinante di A↑ , cioè: |A| = |A↑ |. ↭ Se tutti gli elementi di A di ordine n sono moltiplicati per una costante c il determinante di A risulta moltiplicato per c n. Se gli elementi di una riga o di una colonna di A sono moltiplicati per una costante c, il determinante di A risulta moltiplicato per c. ↭ Se una matrice ha una riga (colonna) con tutti gli elementi uguali a zero il determinante di A è uguale a 0. ↭ Date due matrici quadrate A e B di ordine m, si ha che: |A||B| = |AB|. 22/36 Considerazioni sul determinante In R determinante di una matrice si calcola con la funzione det(). Una matrice il cui determiante è vicino a 0 vine detta quasi singolare. Il determinante di una matrice trova molteplici applicazioni in geometria per il calcolo dei volumi, in algebra lineare nel calcolo della matrice inversa e per verificare la dipendenza lineare di un insieme di vettori. 23/36 Matrice inversa E’ un’operazione su matrici che corrisponde alla divisione nell’algebra elementare: c( c1 ) = 1, dove c è un numero reale diverso da 0. Data una matrice A di ordine n → n, il problema è quello di trovare una matrice, che indicheremo con A↓1 che è detta matrice inversa di A, tale per cui: A↓1 A = AA↓1 = I n. L’inversione di una matrice, come il calcolo del suo determinante, è un’operazione molto laboriosa anche per matrici di dimensioni ridotte, per cui si deve ricorrere al calcolatore. L’espressione esplicita del calcolo dell’inversa è una funzione che ha il determinante della matrice stessa al denominatore. Questo significa che una matrice ammette l’inversa se e solo il suo determinante è diverso da 0. 24/36 Esempio: matrice inversa Data la matrice A definita come segue:   5 4 1 A = 3 2 0 4 2 1 utilizzando la funzione di R, solve() si ottiene:   ↓0.5 0.5 0.5 A↓1 =  0.75 ↓0.25 ↓0.75 0.50 ↓1.5 0.5 E’ immediato controllare che   1 0 0 AA↓1 = 0 1 0 = I 3 0 0 1 25/36 Proprietà della matrice inversa (A↓1 )↓1 = A; (AB)↓1 = B ↓1 A↓1 ; (A↑ )↓1 = (A↓1 )↑ ; 1 |A↓1 | = |A|. Inoltre, se esiste una matrice A↓1 tale per cui A↓1 A = AA↓1 = I allora essa è unica. Il calcolo dell’inversa trova molteplici applicazioni in statistica. Vediamo un esempio di applicazione dell’inversa per la risoluzione di un sistema di equazioni lineari. 26/36 Esempio: utilizzo della matrice inversa Si calcoli la soluzione del seguente sistema di equazioni lineari:  5x1 + 4x2 + x3  =1 3x1 + 2x2 =2   4x1 + 2x2 + x3 = 1. Il sistema può essere scritto in forma matriciale come segue: Ax = b dove       5 4 1 x1 1 A = 3 2 0 x =  x2  b = 2 4 2 1 x3 1 27/36 Esempio: utilizzo della matrice inversa (Cont.) Prendendo l’inversa di ambo i membri dell’equazione Ax = b otteniamo che: x = A↓1 b Utilizzando la funzione di R det() si ottiene che il determinante della matrice A è pari a ↓4 e quindi possiamo a!ermare che l’inversa di A esiste. Utilizzando la funzione di R solve() otteniamo la matrice A↓1. Moltiplicando l’inversa A↓1 per il vettore dei coe"cienti b tramite la funzione di R %*% otteniamo che:      ↓0.5 0.5 0.5 1 1 x = A↓1 b =  0.75 ↓0.25 ↓0.75 2 = ↓0.5. 0.5 ↓1.5 0.5 1 ↓2 28/36 Matrice idempotente Una matrice quadrata A si dice idempotente se AA = A Ad esempio, una qualsiasi matrice X di dimensioni n → p tale per cui l’inversa di X ↑ X esiste, allora la matrice H = X (X ↑ X )↓1 X ↑ è idempotente in quanto: HH = X (X ↑ X )↓1 X ↑ X (X ↑ X )↓1 X ↑ = X (X ↑ X )↓1 X ↑ = H 29/36 Matrice ortogonale Una matrice quadrata V di ordine n si dice ortogonale se la sua trasposta è uguale alla sua inversa: (V ↑ = V ↓1 ). Ciò implica che V V ↑ = V ↑V = I n. 30/36 Vettori linearmente indipendenti Dati k vettori x 1 ,... , x k , ciascuno dei quali aventi n elementi, il vettore y = c1 x 1 + c2 x 2 +... + ck x k dove c1 ,... , ck sono numeri reali, è una combinazione lineare dei vettori x 1,... , x k. Tali vettori si dicono linearmente indipendenti quando ogni possibile combinazione lineare è diversa dal vettore nullo (cioè dal vettore i cui elementi sono tutti uguali a zero), fatta eccezione per il caso banale in cui c1 = c2 =... = ck = 0. In modo equivalente si può dire che i vettori x 1 ,... , x k sono linearmente indipendenti se: c1 x 1 + c2 x 2 +... + ck x k = 0 implica che c1 = c2 =... = ck = 0. 31/36 Esempi: vettori linearmente indipendenti e dipendenti Ad esempio, i vettori bidimensionali → → x 1 = (1 0) e x 2 = (0 1) sono linearmente indipendenti. Infatti: ' ( ' ( ' ( 1 0 0 c1 + c2 = implica c1 = c2 = 0. 0 1 0 I vettori bidimensionali → → x 1 = (1 2) e x 2 = (2 4) invece sono linearmente dipendenti poichè: ' ( ' ( ' ( 1 2 0 c1 + c2 = se (ad esempio) c1 = ↓2c2 = 1. 2 4 0 Si noti, infatti, che gli elementi del vettore x 2 sono il doppio dei corrispondenti elementi del vettore x 1. 32/36 Base di uno spazio vettoriale La base di uno spazio vettoriale è un insieme di p vettori linearmente indipendenti che generano lo spazio. Un scelta comune di una base con p = 4 è la seguente:         1 0 0 0 0 1 0 0  , , ,  0 0 1 0 0 0 0 1 In modo equivalente, ogni elemento dello spazio vettoriale può essere scritto in modo unico come combinazione lineare dei vettori appartenenti alla base.           1 0 0 0 x1 0 1 0 0 x2  x1   + x2   + x3   + x4        = =x 0 x3  0 0 1 0 0 0 1 x4 33/36 Rango di una matrice Data una matrice di ordine m → n il rango di riga (colonna) di A è definito come il massimo numero di righe (colonne) linearmente indipendenti. Se tutte le righe (colonne) di A sono linearmente indipendenti, allora si dice che la matrice A ha rango massimo o pieno. Si può dimostrare che il rango di colonna ed il rango di riga di ogni matrice A di ordine m → n coincidono. In una matrice di dimensione m → n il rango massimo è pari al minimo tra m ed n. È lecito, quindi, parlare semplicemente di rango di A. Una matrice A quadrata di ordine n ammette l’inversa se e solo se ha rango massimo. Se A è una matrice n → n il cui determinante è nullo (|A| = 0), allora il rango di A è minore di n. In tal caso la matrice non è invertibile, è cioè una matrice singolare. 34/36 La traccia di una matrice La traccia di una matrice A di dimensione n → n è definita come la somma dei suoi elementi sulla diagonale principale: n + tr (A) = aii i=1 In R la traccia di una matrice viene calcolata attraverso la combinazioni di funzione sum(diag(matrice)). 35/36 Proprietà della traccia ↭ la traccia di uno scalare k è pari allo scalare stesso tr (k) = k; ↭ la traccia del prodotto scalare kA è pari a k volte la traccia, cioè: tr (kA) = ktr (A); ↭ la traccia della somma di due matrici è uguale alla somma delle singole tracce, cioè: tr (A + B) = tr (A) + tr (B) dove A e B sono matrici quadrate dello stesso ordine; ↭ le tracce delle matrici prodotto AB e BA sono uguali: tr (AB) = tr (BA) (A e B sono di ordine tale che entrambe le matrici prodotto esistono). Si verifica facilmente, infatti, che entrambe le tracce sono uguali a ++ aij bji , i j dove la sommatoria della i va da 1 al numero di righe della matrice A (= numero di colonne della matrice B) e la sommatoria della j va da 1 al numero delle colonne della matrice A (= numero di righe della matrice B). 36/36