metodo di Gauss

Consideriamo il sistema di equazioni lineari $AX=B$.

Chiamiamo matrice completa $(A\mid B)\in {\mathcal{M}}_{m,n+1}$ la matrice che si ottiene accostando orizzontalmente la matrice $A$ dei coefficienti e il vettore $B$ delle indeterminate.

Esempio:

$$A=\left(\begin{array}{cc}1& 2\\ 3& 4\\ 5& 6\end{array}\right)\in {\mathcal{M}}_{3,2}B=\left(\begin{array}{c}7\\ 8\\ 9\end{array}\right)\in {\mathcal{M}}_{3,1}A\mid B=\left(\begin{array}{ccc}1& 2& 7\\ 3& 4& 8\\ 5& 6& 9\end{array}\right)\in {\mathcal{M}}_{3,3}$$

Ricordiamo che risolvere $AX=B$ equivale a trovare tutti gli $X=\left(\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right)$ con $AX=B$.

Definizioni preliminari all’algoritmo

Operazioni elementari lecite sulle righe della matrice completa

• Sostituire una riga con la somma tra se stessa e un’altra riga;
• moltiplicare una riga per uno scalare non nullo;
• scambiare due righe.

Applicare una singola o una qualsiasi sequenza di queste operazioni mantiene invariato in rango della matrice completa.

Relazioni $\sim$ e $\genfrac{}{}{0ex}{}{⌣}{⌢}$

• Definiamo la relazione $\sim$ tra matrici complete come segue: $(A\mid B)\sim (A^{\prime }\mid B^{\prime })⟺\text{Sol}(A\mid B)=\text{Sol}(A^{\prime }\mid B^{\prime })$;
• Definiamo la relazione $\genfrac{}{}{0ex}{}{⌣}{⌢}$ come segue: $(A\mid B)\genfrac{}{}{0ex}{}{⌣}{⌢}(A^{\prime }\mid B^{\prime })$ se posso ottenere la seconda dalla prima applicando un numero finito di operazioni elementari lecite sulle righe (o “la matrice a destra è costruibile lecitamente da quella a sinistra”);

Osservazione: $\genfrac{}{}{0ex}{}{⌣}{⌢}$ è una relazione d’equivalenza.

Osservazione: $A\genfrac{}{}{0ex}{}{⌣}{⌢}B⟹\text{rg}(A)=\text{rg}(B)$.

Matrice a gradini o scalini

Una matrice completa è detta a gradini o a scalini se è come questa

$$\left(\begin{array}{ccccccccccccc}0& 0& 0& 1& \ast & \ast & \ast & \ast & \ast & \ast & \ast & \ast & \ast \\ 0& 0& 0& 0& 0& 1& \ast & \ast & \ast & \ast & \ast & \ast & \ast \\ 0& 0& 0& 0& 0& 0& 1& \ast & \ast & \ast & \ast & \ast & \ast \\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& \ast & \ast \\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& \ast \end{array}\right)$$

oppure con una o più righe composte solo da zeri sia sopra che sotto; inoltre la riga del primo gradino può anche avere un $1$ a sinistra senza alcuno zero. Una matrice a gradini banale contiene solo zeri.

Matrice in forma ridotta

Una matrice a gradini si dice ridotta se sopra a tutti gli $1$ ci sono zeri, ad esempio:

$$\left(\begin{array}{ccccccccccccc}0& 0& 0& 1& \ast & 0& 0& \ast & \ast & \ast & 0& 0& \ast \\ 0& 0& 0& 0& 0& 1& 0& \ast & \ast & \ast & 0& 0& \ast \\ 0& 0& 0& 0& 0& 0& 1& \ast & \ast & \ast & 0& 0& \ast \\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& \ast \\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& \ast \end{array}\right)$$

Gli $1$ che definiscono i gradini vengono chiamati pivot.

Il rango è il numero di righe non nulle della matrice portata in forma ridotta.

Teorema di Gauss

• In ogni classe di equivalenza della $\genfrac{}{}{0ex}{}{⌣}{⌢}$ di matrici complete $(A\mid B)$ esiste un’unica matrice a gradini ridotta.
• $(A\mid B)\genfrac{}{}{0ex}{}{⌣}{⌢}(A^{\prime }\mid B^{\prime })⟹(A\mid B)\sim (A^{\prime }\mid B^{\prime })$.

N.B.: Contro-intuitivamente, l’algoritmo di Gauss per trovare la matrice inversa è la dimostrazione di questo teorema, non il contrario.

Esercizio (con $V={\mathbb{R}}^4,K=\mathbb{R}$)

$$(A\mid B)=\left(\begin{array}{ccccc}1& 1& -1& -2& 4\\ 1& 0& -1& 0& 0\\ 0& 1& 0& 1& -2\end{array}\right)=\{\begin{array}{l}x+y-z-3t=4\\ x-z=0\\ y+t=-2\end{array}$$

Applichiamo a catena le operazioni elementari lecite sulle righe, annotando quella usata sotto il simbolo “di costruzione di matrici” $\genfrac{}{}{0ex}{}{⌣}{⌢}$, fino a raggiungere una matrice ridotta.

$$\left(\begin{array}{ccccc}1& 1& -1& -2& 4\\ 1& 0& -1& 0& 0\\ 0& 1& 0& 1& -2\end{array}\right)\underset{R_2\to R_2-R_1}{\genfrac{}{}{0ex}{}{⌣}{⌢}}\left(\begin{array}{ccccc}1& 1& -1& -2& 4\\ 0& -1& 0& 2& -4\\ 0& 1& 0& 1& -2\end{array}\right)\underset{R_3\to R_3+R_2}{\genfrac{}{}{0ex}{}{⌣}{⌢}}\dots$$ $$\dots \left(\begin{array}{ccccc}1& 1& -1& -2& 4\\ 0& -1& 0& 2& -4\\ 0& 0& 0& 3& -6\end{array}\right)\underset{\genfrac{}{}{0ex}{}{R_2\to -R_2}{R_3\to \frac{1}{3}{R}_3}}{\genfrac{}{}{0ex}{}{⌣}{⌢}}\left(\begin{array}{ccccc}1& 1& -1& 0& 0\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& -2\end{array}\right)\underset{\genfrac{}{}{0ex}{}{R_2\to R_2+2R_3}{R_1\to R_1+2R_3}}{\genfrac{}{}{0ex}{}{⌣}{⌢}}\dots$$ $$\dots \underset{R_1\to R_1-R_2}{\genfrac{}{}{0ex}{}{⌣}{⌢}}\left(\begin{array}{ccccc}1& 0& -1& 0& 0\\ 0& -1& 0& 0& 0\\ 0& 0& 0& 1& -2\end{array}\right)$$

Il sistema associato ha infinite soluzioni su una retta vettoriale, in quanto le soluzioni si differenziano solo per il parametro $x$.

$$\{\begin{array}{l}1x+0y-1z+0t=0\\ 0x-1y+0z+0t=0\\ 0x+0y+0z+1t=-2\end{array}=\{\begin{array}{l}x-z=0\\ y=0\\ t=-2\end{array}=\left\{\left(\begin{array}{c}x\\ 0\\ x\\ -2\end{array}\right):x\in \mathbb{R}\right\}$$

Che si può anche vedere come

$$\left(\begin{array}{c}0\\ 0\\ 0\\ -2\end{array}\right)+\mathbb{R}\left(\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}\right)=\left\{\left(\begin{array}{c}0\\ 0\\ 0\\ -2\end{array}\right)+x\cdot \left(\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}\right):x\in \mathbb{R}\right\}$$

Questo tra l’altro ci porta al teorema

$$\text{Sol}(A\mid B)=x_0+\text{Sol}(A\mid 0)$$

dove $x_0$ è la soluzione particolare del sistema lineare $(A\mid B)$ e $\text{Sol}(A\mid 0)$ è il sottospazio vettoriale delle soluzioni del sistema $(A\mid B)$.