5 Sistemi lineari: regola di Cramer e Rouchè-Capelli
5.1 Regola di Cramer
La regola di Cramer1, è una metodo che consente di risolvere teoricamente un sistema lineare con n equazioni e n incognite, a condizione che la matrice dei coefficienti sia non singolare.
Consideriamo un sistema lineare che può essere scritto in forma matriciale compatta come:
\bm{A} \bm{x} = \bm{b}
Il vettore \bm{b} può essere espresso come una combinazione lineare delle colonne di \bm{A}:
\bm{b} = \bm{A} \bm{x} = \bm{A}_{\bullet,1}x_1 + \bm{A}_{\bullet,2}x_2 + \cdots + \bm{A}_{\bullet,n}x_n = \sum_{j=1}^n \bm{A}_{\bullet,j}x_j
dove \bm{x} è il vettore delle incognite e \bm{A}_{\bullet,j} rappresenta la j-esima colonna di \bm{A}.
Per calcolare l’incognita x_i, consideriamo il determinante della matrice ottenuta sostituendo la i-esima colonna di \bm{A} con \bm{b}:
\begin{aligned} &\mathcal{D}(\bm{A}_{\bullet,1}, \ldots, \bm{A}_{\bullet,i-1}, \bm{b}, \bm{A}_{\bullet,i+1}, \ldots, \bm{A}_{\bullet,n}) \\ &\qquad= \mathcal{D}\left(\bm{A}_{\bullet,1}, \ldots, \bm{A}_{\bullet,i-1}, \sum_{j=1}^n \bm{A}_{\bullet,j}x_j, \bm{A}_{\bullet,i+1}, \ldots, \bm{A}_{\bullet,n}\right) \\ &\qquad= \sum_{j=1}^n x_j \mathcal{D}(\bm{A}_{\bullet,1}, \ldots, \bm{A}_{\bullet,i-1}, \bm{A}_{\bullet,j}, \bm{A}_{\bullet,i+1}, \ldots, \bm{A}_{\bullet,n}) \\ &\qquad= x_i \mathcal{D}(\bm{A}_{\bullet,1}, \ldots, \bm{A}_{\bullet,i-1}, \bm{A}_{\bullet,i}, \bm{A}_{\bullet,i+1}, \ldots, \bm{A}_{\bullet,n}) \end{aligned}
Da questa espressione, possiamo ricavare x_i come:
x_i = \frac{\mathcal{D}(\bm{A}_{\bullet,1}, \ldots, \bm{A}_{\bullet,i-1}, \bm{b}, \bm{A}_{\bullet,i+1}, \ldots, \bm{A}_{\bullet,n})}{\mathcal{D}(\bm{A}_{\bullet,1}, \ldots, \bm{A}_{\bullet,n})}
La regola di Cramer è applicabile solo se la matrice \bm{A} è non singolare, cioè se:
\mathcal{D}(\bm{A}) = \mathcal{D}(\bm{A}_{\bullet,1}, \ldots, \bm{A}_{\bullet,n}) \neq 0
5.2 Il teorema di Rouchè3-Capelli4
Utilizzando i teoremi introdotti finora, possiamo definire dei criteri per determinare se un sistema di equazioni lineari ammette soluzioni. Consideriamo il sistema:
\bm{A}\bm{x} = \bm{b},
dove \bm{A} \in \Bbb{K}^{m \times n} è una matrice, \bm{x} \in \Bbb{K}^n è un vettore di variabili incognite e \bm{b} \in \Bbb{K}^m è un vettore noto.
Supponiamo che \bm{x} sia una soluzione del sistema (non preoccupiamoci per ora della sua unicità). In tal caso, possiamo esprimere il vettore \bm{b} come una combinazione lineare delle colonne di \bm{A}:
\bm{b} = x_1 \bm{A}_{\bullet,1} + x_2 \bm{A}_{\bullet,2} + \cdots + x_n \bm{A}_{\bullet,n},
dove x_1, x_2, \dots, x_n sono i componenti del vettore \bm{x}, e \bm{A}_{\bullet,1}, \bm{A}_{\bullet,2}, \dots, \bm{A}_{\bullet,n} sono le colonne della matrice \bm{A}.
Questo significa che \bm{b} è una combinazione lineare delle colonne di \bm{A}. Pertanto, il numero di vettori linearmente indipendenti tra le colonne \bm{A}_{\bullet,1}, \bm{A}_{\bullet,2}, \dots, \bm{A}_{\bullet,n} è lo stesso di quello delle colonne \bm{A}_{\bullet,1}, \bm{A}_{\bullet,2}, \dots, \bm{A}_{\bullet,n}, \bm{b}.
In simboli, possiamo scrivere:
\text{rank}(\bm{A}) = \text{rank}(\bm{A}, \bm{b}),
dove \text{rank}(\bm{A}, \bm{b}) indica il rango della matrice estesa
\begin{pmatrix}\bm{A}_{\bullet,1}, \bm{A}_{\bullet,2}, \dots, \bm{A}_{\bullet,n}, \bm{b}\end{pmatrix},
ossia la matrice formata dalle colonne di \bm{A} con in aggiunta il vettore colonna \bm{b}.
Viceversa, se il sistema non ammette soluzioni, il vettore \bm{b} non può essere scritto come una combinazione lineare delle colonne di \bm{A}. In tal caso, \bm{b} è linearmente indipendente dalle colonne di \bm{A}, e quindi il numero di vettori colonna linearmente indipendenti di \bm{A}_{\bullet,1}, \bm{A}_{\bullet,2}, \dots, \bm{A}_{\bullet,n} è inferiore a quello delle colonne \bm{A}_{\bullet,1}, \bm{A}_{\bullet,2}, \dots, \bm{A}_{\bullet,n}, \bm{b}.
In simboli, ciò si esprime come:
\text{rank}(\bm{A}) < \text{rank}(\bm{A}, \bm{b}).
Questi risultati possono essere riassunti nel seguente teorema:
Theorem 5.1 (Rouché-Capelli versione compatta) Sia dato il sistema
\bm{A}\bm{x} = \bm{b},
dove \bm{A} \in \Bbb{K}^{m \times n}, \bm{x} \in \Bbb{K}^n e \bm{b} \in \Bbb{K}^m. Il sistema ammette soluzioni se e solo se:
\text{rank}(\bm{A}) = \text{rank}(\bm{A}, \bm{b}).
I risultati sui determinanti permettono di dare una forma operativa del teorema Theorem 5.1, infatti
Teorema di Rouchè-Capelli (versione estesa)
Sia dato il sistema
\bm{A}\bm{x}=\bm{b},
dove \bm{A}\in\Bbb{K}^{m\times n}, \bm{x}\in\Bbb{K}^{n} e \bm{b}\in\Bbb{K}^{m}. Allora il sistema ha soluzione se e solo se il massimo ordine dei minori non nulli della matrice \bm{A} è lo stesso della matrice (\bm{A},\bm{b}).
Proof. Basta applicare il teorema seguente dimostrato negli appunti sui determinanti.
Theorem 5.2 (Minori e Indipendenza Lineare) Se i k vettori \bm{v}_{1},\,\bm{v}_{2},\ldots,\bm{v}_{k}\in\Bbb{K}^n sono linearmente indipendenti e k \leq n, allora esiste almeno un minore di ordine k non nullo della matrice \bm{A} \in \Bbb{K}^{k \times k} con n \geq k, definita come
\bm{A} = \begin{pmatrix} \bm{v}_{1}, \bm{v}_{2}, \ldots, \bm{v}_{k} \end{pmatrix}.
Sia \bm{x}\in\Bbb{K}^n una soluzione del sistema lineare \bm{A}\bm{x}=\bm{b}, con \bm{A}\in\Bbb{K}^{m\times n} e \bm{b}\in\Bbb{K}^m, con \bm{b}\neq\bm{0}, e \tilde{\bm{x}}\in\Bbb{K}^n una soluzione del sistema lineare omogeneo \bm{A}\tilde{\bm{x}}=0.
É interessante notare che \bm{x}+\tilde{\bm{x}} è ancora soluzione del sistema lineare non omogeneo:
\bm{A}(\bm{x}+\tilde{\bm{x}}) = \bm{A}\bm{x} + \bm{A}\tilde{\bm{x}} = \bm{b} + \bm{0} = \bm{b}.
Quindi, data una soluzione particolare \bm{x} del sistema lineare non omogeneo — \bm{b}\neq\bm{0} — per ogni soluzione \tilde{\bm{x}} del sistema lineare omogeneo si ottiene una diversa soluzione del problema non omogeneo della forma \bm{x}+\tilde{\bm{x}}.
È intuitivo che la soluzione di un sistema lineare non omogeneo – una volta che ne sia ammessa l’esistenza – è unica solo nei casi in cui possiamo garantire che sia sempre \tilde{\bm{x}}=\bm{0}, cioè che l’unica soluzione possibile del sistema lineare omogeneo \bm{A}\tilde{\bm{x}}=\bm{0} sia il vettore nullo.
Formalizziamo questa considerazione nel seguente teorema per matrici quadrate.
Esistenza e unicità per sistemi lineari
Theorem 5.3 Sia \bm{A}\in\Bbb{K}^{n\times n}, tale che \textrm{rank}(\bm{A})=n. Allora la soluzione \bm{x}\in\Bbb{K}^n del problema \bm{A}\bm{x}=\bm{b}, con \bm{b}\in\Bbb{K}^n vettore assegnato, esiste ed è unica.
Proof. Dimostriamo separatamente prima l’esistenza e poi l’unicità.
- Esistenza. Poiché in \Bbb{K}^n possiamo avere al massimo n vettori linearmente indipendenti, \textrm{rank}(\bm{A})=n implica che \textrm{rank}(\bm{A},\bm{b})=n, e l’esistenza segue dal teorema Theorem 5.3
- Unicità. Essendo la matrice \bm{A} quadrata di ordine n uguale al suo rango, si deduce immediatamente che le sue colonne \bm{A}_{\bullet,1},\bm{A}_{\bullet,2},\ldots,\bm{A}_{\bullet,n}, sono vettori linearmente indipendenti. Supponiamo ora di avere due soluzioni possibili del sistema lineare non omogeneo, che indichiamo con \bm{x}_{1} e \bm{x}_{2}, per cui possiamo scrivere \bm{A}\bm{x}_{1}=\bm{A}\bm{x}_{2}=\bm{b}. Per differenza si ottiene \bm{A}(\bm{x}_{1}-\bm{x}_{2})=0, da cui segue che \bm{x}_{1}-\bm{x}_{2}=\bm{0}, cioè \bm{x}_{1}=\bm{x}_{2}.
Che cosa succede se la matrice è rettangolare?
La notazione \mathcal{O}(g(n)) rappresenta l’insieme delle funzioni h(n) tali che h(n) \leq C \cdot g(n) per n \geq n_0, dove C è una costante non negativa indipendente da n. L’espressione f = \mathcal{O}(g) indica che f è dell’ordine di g, e rappresenta un abuso notazionale per f \in \mathcal{O}(g).↩︎