sistema di equazioni lineari

Dato un campo $K$, un sistema lineare di $M$ equazioni e $n$ indeterminate a coefficienti in $K$, è un sistema di equazioni del tipo:

$$\ast =\{\begin{array}{l}{a}_{11}{x}_1+a_{12}+\cdots +a_{1n}{x}_n=b_1\\ a_{21}{x}_1+a_{22}+\cdots +a_{2n}{x}_n=b_2\\ \dots \\ a_{M1}{x}_1+a_{M2}+\cdots +a_{Mn}{x}_n=b_M\end{array}$$

Dove $b_{ij}$ sono termini costanti e $x_j$ le indeterminate.

Notazione compatta con le matrici

Siano le matrici:

$$A=(a_{ij}{)}_{1\le j\le m,1\le j\le n}\in {\mathcal{M}}_{m,n}(K)X:=\left(\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right)\in {\mathcal{M}}_{m,n}(K)B:=\left(\begin{array}{c}{b}_1\\ ⋮\\ b_M\end{array}\right)\in {\mathcal{M}}_{m,n}(K)$$

• $A$ = matrice dei coefficienti dei polinomi
• $X$ = matrice colonna delle indeterminate
• $B$ = matrice colonna delle costanti a destra dell’uguale

Il sistema $\ast$ si scrive:

$$AX=B$$ $$AX=\left(\begin{array}{c}{A}_1\\ ⋮\\ A_M\end{array}\right)X=\left(\begin{array}{c}⟨A_1,X⟩\\ ⋮\\ ⟨A_M,X⟩\end{array}\right)$$

Esempio 1

$$\{\begin{array}{l}2x_1+x_2-3x_3+x_4=1\\ x_3+x_4=5\\ x_1-x_2-x_3-2x_4=0\end{array}$$ $$B=\left(\begin{array}{c}1\\ 5\\ 0\end{array}\right)X=\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right)A\in {\mathcal{M}}_{3,4}(\mathbb{R})$$ $$A=\left(\begin{array}{cccc}2& 1& -3& 1\\ 0& 0& 1& 1\\ 1& -1& -1& -2\end{array}\right)$$

Esempio 2

$A\in G{L}_n(K)$ su $B=K^n$

$(\square )AX=BX=\left(\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right)$

Claim: $\text{Sol}(\square )$ è un singleton.

1. $A$ è una matrice quadrata: $A\in G{L}_n(K)={\mathcal{M}}_{n,n}(K)⟹\exists A^{-1}\in G{L}_n(K)$ unicamente determinata, tale che $A^{-1}A=A{A}^{-1}=I_n$ (abbiamo usato il fatto che le matrici quadrate sono invertibili).
2. Consideriamo $AX=B$. Moltiplichiamo a sinistra per $A^{-1}$, quindi $A^{-1}AX=A^{-1}B\to X=A^{-1}B$.
3. $\text{Sol}(\square )=\{A^{-1}X\}$.

Risoluzione dei sistemi

Risolvere un sistema lineare vuol dire “descrivere” l’insieme delle sue soluzioni

$$\text{Sol}(\ast )=\left\{\left(\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right)\in K^n:\ast \text{eˋ verificato}\right\}$$

Se $\text{Sol}(\ast )=\varnothing$ allora si dice che il sistema è incompatibile o impossibile; in caso contrario si dice compatibile. Ad esempio $\{\begin{array}{l}{x}_1=0\\ x_1=1\end{array}$ è incompatibile.

Metodo di Gauss

Consideriamo un sistema lineare $(\ast )AX=B$.

Chiamiamo matrice completa $(A\mid B)\in {\mathcal{M}}_{m,n+1}$ todo esempio

Ricordiamo che risolvere $\ast$ equivale a trovare tutti gli $X\in {\mathcal{M}}_{n,1}(K)$ con $AX=B$.

Definizioni preliminari all’algoritmo

Operazioni elementari lecite sulle righe della matrice completa ($A\mid B$)

• Permutare righe;
• Sostituire una riga con un suo multiplo scalare non nullo $r\mapsto \lambda r$ con $\lambda \in K^X$;
• Sostituire una riga con la stessa più un multiplo scalare di un altra $r\mapsto r+\lambda r^{\prime }$;

Convenzioni di notazione

• Scriviamo $(A\mid B)\sim (A^{\prime }\mid B^{\prime })⟺\text{Sol}(A\mid B)=\text{Sol}(A^{\prime }\mid B^{\prime })$;
• Scriviamo inoltre $(A\mid B)\genfrac{}{}{0ex}{}{⌣}{⌢}(A^{\prime }\mid B^{\prime })$ se posso ottenere la seconda dalla prima applicando un minimo finito di operazioni elementari lecite sulle righe (“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)$.

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 riga del primo gradino può anche avere un $1$ a sinistra senza alcuno zero. Una matrice a gradini banale contiene solo zeri.

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.

Teorema di Gauss

• In ogni classe di $\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 è la dimostrazione di questo teorema, non il contrario.

Esercizi

1.

$$(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 completa e 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 è

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

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\{\begin{array}{c}\left(\begin{array}{c}0\\ 0\\ 0\\ -2\end{array}\right)+x\left(\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}\right):x\in \mathbb{R}\end{array}\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)$.