Matrici fortemente ridotte per righe. Operazioni elementari di riga

LEZIONE 3
3.1. Matrici fortemente ridotte per righe.
Nella precedente lezione abbiamo introdotto la nozione di soluzione di un sistema di equazioni lineari. In questa lezione ci poniamo il problema di descrivere
un metodo efficiente per la determinazione della totalità delle soluzioni di un tale
sistema.
A tale scopo iniziamo considerando un semplice esempio.
Esempio 3.1.1. Si consideri il sistema


 a + b + 2c + e = 1
−b + d + g = 0


3b + f + 3g = −2.
(3.1.1.1)
Il Sistema (3.1.1.1) si scrive nella forma matriciale

1
0
0
1
−1
3
 
a
b


  
1
2 0 1 0 0 c
 
0 1 0 0 1d =  0 .
 
0 0 0 1 3 e
−2
 
f
g
Il Sistema (3.1.1.1) ha una proprietà “notevole”: in ogni sua equazione c’è un’incognita con coefficiente non nullo che non figura in nessuna delle altre equazioni.
Questo ci permette di risolvere il sistema in maniera veloce. In ogni equazione
si sceglie un’incognita che non figura nelle rimanenti equazioni del sistema e la si
esplicita in funzione delle altre incognite dell’equazione stessa.
Per esempio nella prima equazione scegliamo l’incognita a, e si ha
a = 1 − b − 2c − e,
nella seconda l’incognita d, e si ha
d = b − g,
Typeset by AMS-TEX
1
2
3.1. MATRICI FORTEMENTE RIDOTTE PER RIGHE
nella terza l’incognita f , e si ha
f = −2 − 3b − 3g.
Dunque le soluzioni del Sistema (3.1.1.1) sono necessariamente tutte e sole le
matrici in R7,1 della forma
t
( 1 − b − 2c − e b
c
b−g
e −2 − 3b − 3g
g)
al variare di b, c, e, g in R. Per esempio, scelti b = c = e = g = 0, si ottiene la
soluzione t ( 1 0 0 0 0 −2 0 ). Invece, scelti b = 1, c = 0, e = −2, g = 1,
si ottiene la soluzione t ( 2 1 0 0 −2 −8 1 ).
Il fatto che in ogni equazione del Sistema (3.1.1.1) c’è un’incognita che non
figura in nessuna delle altre equazioni può essere tradotto in linguaggio matriciale
osservando che in ogni riga della sua matrice (incompleta) c’è un’entrata non nulla
che è l’unica entrata non nulla nella sua colonna.
A tutti i sistemi la cui matrice incompleta ha questa proprietà si può applicare il
metodo descritto nell’esempio precedente ottenendo facilmente la soluzione generale.
Per questo motivo è utile dare un nome a tale tipo di matrici.
Definizione 3.1.2. La matrice A = (ai,j ) 1≤i≤m ∈ Rm,n si dice fortemente ridotta
1≤j≤n
per righe se valgono le seguenti proprietà:
(FR1) se la riga di indice i0 contiene entrate non nulle allora esiste una sua entrata
ai0 ,j0 , detta pivot (della riga di indice i0 ), che vale 1 e tale che ai,j0 = 0
per ogni i 6= i0 ;
(FR2) se tutte le entrate della riga di indice i0 sono nulle allora le entrate di ogni
riga di indice i > i0 sono anch’esse nulle.
Quindi il metodo sopra descritto si può applicare ogni volta si abbia a che fare
con un sistema la cui matrice incompleta sia fortemente ridotta per righe.
Esempio 3.1.2. Si considerino le matrici
1 −2
 0
2
A1 = 

0
4
0
0

0 0 0 0 0
0 0 0 0 0
,
0 5 −1 1 2
1 0 2 0 4

0
1
A2 = 
0
0

0
−2
2
4
0
0
1
0
0
5
0
0
0
−1
2
0

1
0
A3 = 
0
0
0
1
0
0

0
2
,

4
0
−2 0
2 0
4 1
0 0
0 0
5 −1
0 2
0 0

0 0
2 2
.
0 4
0 0
A1 è fortemente ridotta per righe, mentre A2 ed A3 non lo sono.
Spesso è utile lavorare con matrici aventi delle proprietà simili ma un po’ più
deboli.
LEZIONE 3
3
Definizione 3.1.4. La matrice A = (ai,j ) 1≤i≤m ∈ Rm,n si dice ridotta per righe
1≤j≤n
se vale la seguente proprietà: se la riga di indice i0 < m contiene entrate non nulle
allora esiste una sua entrata ai0 ,j0 6= 0, detta pivot (della riga di indice i0 ), tale
che ai,j0 = 0 per ogni i > i0 .
Chiaramente ogni matrice fortemente ridotta per righe è ridotta per righe, ma
non vale il viceversa come mostra il seguente esempio.
Esempio 3.1.5. Si considerino le matrici

1 −2

2
 0
A1 = 
 0
4
0
5

1 −2
0 2
A2 = 
0 4
4 5
3
0
1
0
3
0
1
0
0
5
0
0
0
−1
2
0
0 0 3
5 −1 2
0 2 0
0 0 0

3 0

2 2

0 4
0 0

0
2
.
4
0
La matrice A1 è ridotta per righe ma non fortemente ridotta per righe. Invece la
matrice A2 non è ridotta per righe, dunque non lo è neanche fortemente.
3.2. Operazioni elementari di riga.
Dato un sistema di equazioni lineari però, in generale, la sua matrice non è
fortemente ridotta per righe, o anche solo ridotta per righe. Per esempio la matrice
completa del sistema
(3.2.1)
x+y+z =1
x − y + 2z = −3
è
1
1
1
−1
1 1
2 −3
che non è ridotta per righe.
Un possibile metodo di soluzione è quello di trasformare il Sistema (3.2.1) in un
nuovo sistema con le stesse soluzioni e che abbia una matrice fortemente ridotta
per righe e risolvere quest’ultimo invece di quello di partenza.
Per esempio, se nel Sistema (3.2.1) si sostituisce alla seconda equazione la
somma delle due equazioni, si ottiene il nuovo sistema
(3.2.2)
x+y+z =1
2x + 3z = −2
4
3.2. OPERAZIONI ELEMENTARI DI RIGA
la cui matrice completa è
1
2
1
0
1 1
3 −2
che è ridotta per righe. Chiaramente se t ( x0 y0 z0 ) è soluzione del Sistema
(3.2.1) si ha
x0 + y0 + z0 − 1 = 0, x0 − y0 + 2z0 + 3 = 0,
dunque
x0 + y0 + z0 − 1 = 0,
2x0 + 3z0 + 2 = (x0 + y0 + z0 − 1) + (x0 − y0 + 2z0 + 3) = 0,
sicché t ( x0 y0 z0 ) è anche soluzione del Sistema (3.2.2): concludiamo che
l’insieme delle soluzioni del Sistema (3.2.1) è contenuto in quello del Sistema
(3.2.2).
Poiché, viceversa, il Sistema (3.2.1) si può ottenere dal Sistema (3.2.2) sostituendo alla sua seconda equazione la seconda equazione meno la prima anche l’insieme
delle soluzioni del Sistema (3.2.2) è contenuto in quello del Sistema (3.2.1),dunque
tali insiemi coincidono, cioè i due Sistemi (3.2.1) e (3.2.2) hanno le stesse soluzioni,
ovvero sono equivalenti nel senso della seguente
Definizione 3.2.3. Due sistemi di equazioni (non necessariamente lineari) si dicono equivalenti se hanno lo stesso insieme di soluzioni.
Proseguendo con il Sistema (3.2.2), dividendo la seconda equazione per 2 otteniamo il sistema
x+y+z =1
(3.2.4)
x + 3z/2 = −1
la cui matrice completa è
1
1
1
0
1 1
.
3 −1
È facile osservare che il Sistema (3.2.4) è ancora equivalente al Sistema (3.2.1)
di partenza. Sottraendo, infine, alla prima equazione del sistema cosı̀ ottenuto la
seconda otteniamo
y − z/2 = 2
(3.2.5)
x + 3z/2 = −1
la cui matrice completa è
0
1
1
0
−1/2 2
3 −1
che è fortemente ridotta per righe. Ragionando analogamente a quanto fatto
prima osserviamo che il Sistema (3.2.5) è equivalente al Sistema (3.2.2), dunque
LEZIONE 3
5
al Sistema (3.2.1). Risolvendo il Sistema (3.2.5) come spiegato nell’Esempio 3.1.1
otteniamo che la soluzione generale del Sistema (3.2.5) e, perciò, del Sistema (3.2.1)
è
t
( −1 − 3z/2 2 + z/2 z ) | z ∈ R .
Si noti che ogni operazione fatta sulle equazioni del sistema corrisponde ad
un’analoga operazione fra le righe della matrice completa del sistema stesso: questa
è la tecnica generale per risolvere un qualsiasi sistema di equazioni lineari. Per
enunciare il risultato generale introduciamo la definizione di operazioni elementari
di riga.
Definizione 3.2.6. Sia A ∈ Rm,n . Le operazioni elementari di riga su A sono:
(E1) sommare ad una riga di A un multiplo di un’altra riga di A (se si somma
alla riga di indice i la riga di indice i0 6= i moltiplicata per α ∈ R tale
operazione viene spesso indicata con Ri → Ri + αRi0 );
(E2) moltiplicare una riga di A per una costante non nulla α ∈ R (se si moltiplica
la riga di indice i per α tale operazione viene spesso indicata con Ri →
αRi );
(E3) scambiare due righe di A (se si scambiano le riga di indici i e i0 tale
operazione viene spesso indicata con Ri ↔ Ri0 ).
Il risultato fondamentale di questo paragrafo è il seguente.
Proposizione 3.2.7. Sia A ∈ Rm,n . Allora esiste una successione finita di operazioni elementari di riga che trasforma A in una matrice A0 ∈ Rm,n (fortemente)
ridotta per righe.
Dimostrazione. Supponiamo che A = (ai,j ) 1≤i≤m . Supponiamo che A 6= 0m,n
1≤j≤n
(altrimenti non c’è nulla da dimostrare). Sia i0 il più piccolo indice per cui esiste
ai0 ,j0 6= 0. Moltiplicando la riga di indice i0 per a−1
i0 ,j0 (cioè Ri0 → Ri0 /ai0 ,j0 )
0
trasformiamo la matrice A in una nuova matrice A avente l’entrata 1 in posizione
(i0 , j0 ).
Per ogni i 6= i0 si sostituisca la riga di indice i con la sua somma alla riga
di indice i0 moltiplicata per ai,j0 (cioè Ri → Ri − ai,j0 Ri0 ). In questo modo
trasformiamo la matrice A0 in una nuova matrice A00 = (a00i,j ) 1≤i≤m la cui colonna
1≤j≤n
di indice j0 contiene un’unica entrata non nulla che vale 1 in posizione (i0 , j0 ).
A questo punto si presentano due possibilità. Nel primo caso tutte le righe di
indice i 6= i0 sono nulle: scambiando la riga di indice i0 con la riga di indice 1
(cioè R1 ↔ Ri0 ) trasformiamo A00 in una nuova matrice A000 = (a000
la cui
i,j ) 1≤i≤m
1≤j≤n
colonna di indice j0 contiene un’unica entrata non nulla che vale 1 in posizione
000
(1, j0 ) e tale che a000
i,j = 0 per ogni i > 1. Quindi A è fortemente ridotta per righe.
Nel secondo caso ripetiamo lo stesso procedimento con il più piccolo indice i1 > i0
per cui esiste a00i1 ,j1 6= 0. Poiché a00i,j0 = 0 per i 6= i0 segue che j1 6= j0 .
In questo modo dopo al più m passi (uno per ogni riga) otteniamo una matrice
fortemente ridotta per righe. 6
3.3. RISOLUZIONE DI SISTEMI
Esempio 3.2.8. Si consideri la matrice

1 1
1 1
 1 3 −2 1
A=
2 4 −1 2
1 −1 2 5
1
2
3
7


.
Allora
1 1
1 1
2 −3 0
R →R2 −R1  0
A 2 −→

2 4 −1 2
1 −1 2 5


1
1
1 1 1
R3 →R3 −R2

2 −3 0 1  R4 →R4 +R2  0
 −→ 
2 −3 0 1
0
−2 1 4 6
0

1
0
−→ 
0
0


1
R →R −2R
1  R34 →R34 −R11
−→

3
7
1
2
0
0
1
−3
0
−2
1
0
0
4

1
1
b:
=A
0
7
tale matrice è ridotta per righe. Proseguendo

1 1
1
1
1
R2 →R2 +3R4 /2
1/2  R
 0 1 −3/2 0
1 →R1 −R4
−→ 
−→

0 0
0
0
0
0 0
1
−2 −7/2



1 0 0 6
37/4
3
9/2
−3 −19/4  R1 →R1 −R2  0 1 0 −3 −19/4  R3 ↔R4
−→
 −→


0
0
0 0 0 0
0
−2 −7/2
0 0 1 −2 −7/2


1
0
0
6
37/4
 0
1
0 −3 −19/4 
 = A0 ,
−→ 


0
0
1 −2 −7/2
0
0
0
0
0

b
A
R2 →R2 /2
R4 →−R4 /2
1 1 0
0 1 0
−→ 
0 0 0
0 0 1

che è fortemente ridotta per righe.
3.3. Risoluzione di sistemi.
Supponiamo che AX = B sia un sistema di equazioni lineari. Ad esso associamo
la sua matrice completa (A|B). Per la Proposizione 3.2.7 sappiamo di poter
trasformare, con operazioni elementari di riga, la matrice A in una nuova matrice
A0 fortemente ridotta per righe: con le stesse operazioni elementari si ottiene
una nuova matrice (A0 |B 0 ) corrispondente, in generale, ad un nuovo sistema di
equazioni lineari A0 X = B 0 , diverso dal precedente ma ad esso equivalente. Risolvendo, se possibile, tale sistema con il metodo descritto nell’Esempio 3.1.1 si ottiene
l’insieme delle soluzioni del sistema da cui siamo partiti.
LEZIONE 3
7
Se A0 X = B 0 è compatibile, il numero delle incognite espresse in funzione delle
rimanenti è esattamente il numero dei pivot, cioè il numero delle righe contenenti
entrate non nulle. È chiaro che da ogni matrice A con operazioni elementari di
riga, si potranno ottenere varie matrici fortemente ridotte per righe, anche molto
diverse: infatti, ad ogni passo, bisogna fare una scelta del pivot. Si può, però,
dimostrare che
Proposizione 3.3.1. Sia A ∈ Rm,n e siano A0 ed A00 due matrici ridotte per
righe ottenute da A con una successione finita di operazioni elementari di riga.
Allora i numeri di righe di A0 e di A00 contenenti entrate non nulle coincidono.
Dimostrazione. Omettiamo la dimostrazione. Vedremo nella Lezione 16 che tale
numero dipende solo da A (coincide con un numero chiamato “dimensione dello
spazio riga di A”) e non dalla riduzione operata. Si comprende che tale numero riveste un’importanza particolare nell’algebra
delle matrici, pertanto merita un nome particolare.
Definizione 3.3.2. Sia A ∈ Rm,n e sia A0 una matrice ridotta per righe ottenuta
da A con una successione finita di operazioni elementari di riga. Il numeri di righe
di A0 contenenti entrate non nulle viene detto rango di A ed indicato con il simbolo
rk(A).
In particolare rk(A) ≤ m per definizione. Inoltre rk(A) coincide con il numero
di pivot di una forma fortemente ridotta per righe di A: ognuno di essi si trova
necessariamente in una colonna diversa, quindi si ha anche rk(A) ≤ n. Abbiamo
perciò dimostrato che
Proposizione 3.3.3. Sia A ∈ Rm,n . Allora rk(A) ≤ min{ m, n }.
Esempio 3.3.4. Si consideri la matrice
1
1
A=
2
1

1
3
4
−1
1 1
−2 1
−1 2
2 5

1
2
.
3
7
Poiché con operazioni elementari di riga A può essere trasformata in una delle due
matrici




1 1 1 1 1
1 0 0 6
37/4
0 2 −3 0 1 
 0 1 0 −3 −19/4 
b=
A
A0 = 

,
,
0 0 0 0 0
0 0 1 −2 −7/2
0 0 −2 4 7
0 0 0 0
0
b = rk(A0 ) = 3.
segue che rk(A) = rk(A)
Siamo ora pronti ad enunciare e dimostrare il principale risultato sulla teoria
dei sistemi di equazioni lineari, detto Teorema di Rouché–Capelli.
8
3.3. RISOLUZIONE DI SISTEMI
Proposizione 3.3.5. Siano A ∈ Rm,n , B ∈ Rm,1 e si considerino i sistemi
(3.3.5.1)
AX = B,
(3.3.5.2)
AX = 0m,1 .
i) Il Sistema (3.3.5.1) è compatibile se e solo se rk(A) = rk(A|B).
ii) Se il Sistema (3.3.5.1) è compatibile allora le sue soluzioni dipendono da n −
rk(A) parametri liberi.
iii) Se il Sistema (3.3.5.1) è compatibile e X0 è una sua soluzione fissata allora ogni
altra sua soluzione X è della forma X = X0 + Y ove Y appartiene all’insieme
delle soluzioni del Sistema (3.3.5.2).
Dimostrazione. Iniziamo con il dimostrare l’affermazione i). Per quanto visto
sopra possiamo sempre assumere che A sia una matrice fortemente ridotta per
righe. Si possono presentare due situazioni per le righe della matrice completa
(A|B).
Il primo caso è quello in cui esiste una riga di A, diciamo quella di indice i, con
entrate tutte nulle che si prolunga in (A|B) a una riga con entrate non tutte nulle:
chiaramente l’entrata non nulla deve essere l’i–esima entrata di B, cioè bi 6= 0.
Ciò significa che nel Sistema (3.3.5.1) figura un’equazione della forma 0 = bi che,
per l’ipotesi bi 6= 0, non ha soluzioni. Quindi il Sistema (3.3.5.1) è, in questo caso,
incompatibile: inoltre i numeri di righe di A e di (A|B) contenenti entrate non
nulle differiscono di 1, cioè rk(A) = rk(A|B) − 1, dunque rk(A) 6= rk(A|B).
Nel secondo caso ogni riga di A con entrate tutte nulle si prolunga in (A|B) a
una riga con entrate tutte nulle. In questo caso si può risolvere il Sistema (3.3.5.1)
come spiegato nell’Esempio 3.1.1. Quindi il Sistema (3.3.5.1) è, in questo caso,
compatibile: inoltre i numeri di righe di A e di (A|B) contenenti entrate non nulle
coincidono, cioè rk(A) = rk(A|B).
Ciò conclude la dimostrazione dell’affermazione i) e dimostra anche l’affermazione ii): infatti possiamo esprimere le incognite i cui coefficienti sono i pivot (in
totale rk(A)) in funzione delle rimanenti (in totale n − rk(A)), cui possiamo dare
valori arbitrari.
Passiamo alla dimostrazione dell’affermazione iii). A tale scopo si tenga conto
che AX0 = B.
Sia X ∈ Rn,1 una soluzione del Sistema (3.3.5.1), cioè tale che AX = B: posto
Y = X − X0 si ha
AY = A(X − X0 ) = AX + A(−X0 ) =
= AX + A(−1)X0 = AX − AX0 = B − B = 0m,1 ,
quindi Y è soluzione del Sistema (3.3.5.2).
Viceversa sia Y ∈ Rn,1 una soluzione del Sistema (3.3.5.2), cioè tale che AY =
0m,1 : posto X = Y + X0 si ha
AX = A(Y + X0 ) = AY + AX0 = 0m,1 + B = B,
quindi X è soluzione del Sistema (3.3.5.1).
LEZIONE 3
9
Esempio 3.3.6. Si consideri il sistema
1
1

2
1

1
3
4
−1
1
−2
−1
2
 
 
 a
1 1
0
b
1 2  0
c =  .
1
2 3  
d
0
5 7
e
Le matrici incompleta e completa del sistema sono
1
1
A=
2
1

1
3
4
−1
1
−2
−1
2
1
1
(A|B) = 
2
1

1 1
1 2
,
2 3
5 7

1
3
4
−1
1
−2
−1
2

1 1 0
1 2 0
.
2 3 1
5 7 0
Ricordando quanto visto nell’Esempio 3.2.8, con operazioni elementari di riga A
si riduce alla matrice ridotta per righe
1
0
b=
A

0
0

1
2
0
0
1 1
−3 0
0 0
−2 4

1
1
.
0
7
Applichiamo le stesse operazioni di riga alla matrice completa (A|B): poiché l’effetto di tali operazioni sulla parte a sinistra della sbarra verticale lo conosciamo
(otteniamo A0 ), limitiamoci ad indicare l’operazione e l’effetto su B.



... 0
0
R3 →R3 −R2
R3 →R3 −2R1
0  R4 →R4 −R1  . . . 0  R4 →R4 +R2
−→

 −→

... 1
1
0
... 0


1 1 1 1 1 0
 0 2 −3 0 1 0 
b
b
−→ (A|B) = 
.
0 0 0 0 0 1
0 0 −2 4 7 0
...
R →R2 −R1  . . .
(A|B) 2 −→

...
...

b = 3 mentre rk(A|B) = rk(A|
b B)
b = 4: da questo
Si noti che rk(A) = rk(A)
deduciamo che il sistema AX = B è incompatibile.
Esempio 3.3.7. Si consideri ora il sistema
1
1

2
1

1
3
4
−1
1
−2
−1
2
 
 a
 
1 1
0
b
1 2  0
c =  .
2 3  
0
d
5 7
1
e
10
3.3. RISOLUZIONE DI SISTEMI
Le matrici incompleta e completa del sistema sono
1
1
A=
2
1

1
3
4
−1
1
−2
−1
2

1 1
1 2
,
2 3
5 7
1
1
(A|B) = 
2
1

1
3
4
−1
1
−2
−1
2
1
1
2
5
1
2
3
7

0
0
.
0
1
Ricordando quanto visto nell’Esempio 3.2.8, con operazioni elementari di riga A
si riduce alla matrice fortemente ridotta per righe
1 0 0 6
 0 1 0 −3
A0 = 
0 0 1 −2
0 0 0 0


37/4
−19/4 
.
−7/2
0
Applichiamo le stesse operazioni di riga alla matrice completa (A|B): risulta



... 0
0
R
→R
−2R
R3 →R3 −R2
3
3
1
0  R4 →R4 −R1  . . . 0  R4 →R4 +R2
−→

 −→

... 0
0
1
... 1


1 1 1 1 1 0
 0 2 −3 0 1 0 
b
b
−→ (A|B) = 
.
0 0 0 0 0 0
0 0 −2 4 7 1
...
R2 →R2 −R1  . . .
(A|B) −→

...
...

b = 3 = rk(A|
b B)
b = rk(A|B) segue che il sistema in esame
Poiché rk(A) = rk(A)
è compatibile. Ha senso, perciò, proseguire con le operazioni elementari di riga
riducendo fortemente la matrice completa del sistema.



... 0
. . . 1/2
R2 →R2 +3R4 /2
 . . . 0  R1 →R1 −R4  . . . 0  R1 →R1 −R2
−→
−→




... 0
... 0
. . . −1/2
. . . −1/2



1/2
1 0 0 6
37/4 5/4
−3/4  R3 ↔R4  0 1 0 −3 −19/4 −3/4 
 −→ 
.
0
0 0 1 −2 −7/2 −1/2
−1/2
0 0 0 0
0
0

b B)
b
(A|
R2 →R2 /2
R4 →−R4 /2
−→
...
...
−→ 
...
...

Quindi il sistema AX = B è equivalente al sistema A0 X = B 0 , che è compatibile
perché rk(A) = rk(A0 ) = 3 = rk(A0 |B 0 ) = rk(A|B).
In particolare le incognite corrispondenti ai pivot sono a, b, c e si ha
a = 5/4 − 6d − 37e/4,
b = −3/4 + 3d + 19e/4,
c = −1/2 + 2d + 7e/2.
LEZIONE 3
11
L’insieme delle sue soluzioni è
t
( 5/4 − 6d − 37e/4
−3/4 + 3d + 19e/4
−1/2 + 2d + 7e/2
d
e) |
d, e ∈ R
.
Per esempio in corrsipondenza a d = e = 0 otteniamo la soluzione particolare
X0 = t ( 5/4 −3/4 −1/2 0 0 ). Si noti che ogni altra soluzione è della forma





−37/4
−6
5/4
 19/4 
 3 
 −3/4 






 −1/2  + d  2  + e  7/2 






0
1
0
1
0
0

al variare di d e e in R. Si verifichi che le soluzioni del sistema AX = 0m,1 sono
tutte e sole le matrici della forma



−37/4
−6
 19/4 
 3 




d  2  + e  7/2 




0
1
1
0

al variare di d e e in R.