Queste note sono basate sugli appunti fatti con Gianmarco Manzini negli anni 1995-2005

Sistemi lineari: regola di Cramer e Rouchè-Capelli

Autore/Autrice

Affiliazione

Enrico Bertolazzi

University of Trento, Department of Industrial Engineering

Regola di Cramer

La regola di Cramer¹, è 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:

\boldsymbol{A}\boldsymbol{x}= \boldsymbol{b}

Il vettore \boldsymbol{b} può essere espresso come una combinazione lineare delle colonne di \boldsymbol{A}:

\boldsymbol{b}= \boldsymbol{A}\boldsymbol{x}= \boldsymbol{A}_{\bullet,1}x_1 + \boldsymbol{A}_{\bullet,2}x_2 + \cdots + \boldsymbol{A}_{\bullet,n}x_n = \sum_{j=1}^n \boldsymbol{A}_{\bullet,j}x_j

dove \boldsymbol{x} è il vettore delle incognite e \boldsymbol{A}_{\bullet,j} rappresenta la j-esima colonna di \boldsymbol{A}.

Per calcolare l’incognita x_i, consideriamo il determinante della matrice ottenuta sostituendo la i-esima colonna di \boldsymbol{A} con \boldsymbol{b}:

\begin{aligned} &\mathcal{D}(\boldsymbol{A}_{\bullet,1}, \ldots, \boldsymbol{A}_{\bullet,i-1}, \boldsymbol{b}, \boldsymbol{A}_{\bullet,i+1}, \ldots, \boldsymbol{A}_{\bullet,n}) \\ &\qquad= \mathcal{D}\left(\boldsymbol{A}_{\bullet,1}, \ldots, \boldsymbol{A}_{\bullet,i-1}, \sum_{j=1}^n \boldsymbol{A}_{\bullet,j}x_j, \boldsymbol{A}_{\bullet,i+1}, \ldots, \boldsymbol{A}_{\bullet,n}\right) \\ &\qquad= \sum_{j=1}^n x_j \mathcal{D}(\boldsymbol{A}_{\bullet,1}, \ldots, \boldsymbol{A}_{\bullet,i-1}, \boldsymbol{A}_{\bullet,j}, \boldsymbol{A}_{\bullet,i+1}, \ldots, \boldsymbol{A}_{\bullet,n}) \\ &\qquad= x_i \mathcal{D}(\boldsymbol{A}_{\bullet,1}, \ldots, \boldsymbol{A}_{\bullet,i-1}, \boldsymbol{A}_{\bullet,i}, \boldsymbol{A}_{\bullet,i+1}, \ldots, \boldsymbol{A}_{\bullet,n}) \end{aligned}

Da questa espressione, possiamo ricavare x_i come:

x_i = \frac{\mathcal{D}(\boldsymbol{A}_{\bullet,1}, \ldots, \boldsymbol{A}_{\bullet,i-1}, \boldsymbol{b}, \boldsymbol{A}_{\bullet,i+1}, \ldots, \boldsymbol{A}_{\bullet,n})}{\mathcal{D}(\boldsymbol{A}_{\bullet,1}, \ldots, \boldsymbol{A}_{\bullet,n})}

La regola di Cramer è applicabile solo se la matrice \boldsymbol{A} è non singolare, cioè se:

\mathcal{D}(\boldsymbol{A}) = \mathcal{D}(\boldsymbol{A}_{\bullet,1}, \ldots, \boldsymbol{A}_{\bullet,n}) \neq 0

Osservazione

La regola di Cramer richiede il calcolo di n+1 determinanti, ognuno dei quali implica n! somme e prodotti, per un totale di (n+1)! operazioni aritmetiche. In confronto, esistono metodi di risoluzione dei sistemi lineari che hanno un costo computazionale di \mathcal{O}(n^3) operazioni².

Per valori di n più grandi, la crescita fattoriale del costo rende la regola di Cramer impraticabile, limitandone l’uso a scopi essenzialmente teorici.

Il teorema di Rouchè³-Capelli⁴

Utilizzando i teoremi introdotti finora, possiamo definire dei criteri per determinare se un sistema di equazioni lineari ammette soluzioni. Consideriamo il sistema:

\boldsymbol{A}\boldsymbol{x}= \boldsymbol{b},

dove \boldsymbol{A}\in \Bbb{K}^{m \times n} è una matrice, \boldsymbol{x}\in \Bbb{K}^n è un vettore di variabili incognite e \boldsymbol{b}\in \Bbb{K}^m è un vettore noto.

Supponiamo che \boldsymbol{x} sia una soluzione del sistema (non preoccupiamoci per ora della sua unicità). In tal caso, possiamo esprimere il vettore \boldsymbol{b} come una combinazione lineare delle colonne di \boldsymbol{A}:

\boldsymbol{b}= x_1 \boldsymbol{A}_{\bullet,1} + x_2 \boldsymbol{A}_{\bullet,2} + \cdots + x_n \boldsymbol{A}_{\bullet,n},

dove x_1, x_2, \dots, x_n sono i componenti del vettore \boldsymbol{x}, e \boldsymbol{A}_{\bullet,1}, \boldsymbol{A}_{\bullet,2}, \dots, \boldsymbol{A}_{\bullet,n} sono le colonne della matrice \boldsymbol{A}.

Questo significa che \boldsymbol{b} è una combinazione lineare delle colonne di \boldsymbol{A}. Pertanto, il numero di vettori linearmente indipendenti tra le colonne \boldsymbol{A}_{\bullet,1}, \boldsymbol{A}_{\bullet,2}, \dots, \boldsymbol{A}_{\bullet,n} è lo stesso di quello delle colonne \boldsymbol{A}_{\bullet,1}, \boldsymbol{A}_{\bullet,2}, \dots, \boldsymbol{A}_{\bullet,n}, \boldsymbol{b}.

In simboli, possiamo scrivere:

\text{rank}(\boldsymbol{A}) = \text{rank}(\boldsymbol{A}, \boldsymbol{b}),

dove \text{rank}(\boldsymbol{A}, \boldsymbol{b}) indica il rango della matrice estesa

\begin{pmatrix}\boldsymbol{A}_{\bullet,1}, \boldsymbol{A}_{\bullet,2}, \dots, \boldsymbol{A}_{\bullet,n}, \boldsymbol{b}\end{pmatrix},

ossia la matrice formata dalle colonne di \boldsymbol{A} con in aggiunta il vettore colonna \boldsymbol{b}.

Viceversa, se il sistema non ammette soluzioni, il vettore \boldsymbol{b} non può essere scritto come una combinazione lineare delle colonne di \boldsymbol{A}. In tal caso, \boldsymbol{b} è linearmente indipendente dalle colonne di \boldsymbol{A}, e quindi il numero di vettori colonna linearmente indipendenti di \boldsymbol{A}_{\bullet,1}, \boldsymbol{A}_{\bullet,2}, \dots, \boldsymbol{A}_{\bullet,n} è inferiore a quello delle colonne \boldsymbol{A}_{\bullet,1}, \boldsymbol{A}_{\bullet,2}, \dots, \boldsymbol{A}_{\bullet,n}, \boldsymbol{b}.

In simboli, ciò si esprime come:

\text{rank}(\boldsymbol{A}) < \text{rank}(\boldsymbol{A}, \boldsymbol{b}).

Questi risultati possono essere riassunti nel seguente teorema:

Teorema 1 (Rouché-Capelli versione compatta) Sia dato il sistema

\boldsymbol{A}\boldsymbol{x}= \boldsymbol{b},

dove \boldsymbol{A}\in \Bbb{K}^{m \times n}, \boldsymbol{x}\in \Bbb{K}^n e \boldsymbol{b}\in \Bbb{K}^m. Il sistema ammette soluzioni se e solo se:

\text{rank}(\boldsymbol{A}) = \text{rank}(\boldsymbol{A}, \boldsymbol{b}).

I risultati sui determinanti permettono di dare una forma operativa del teorema Teorema 1, infatti

Teorema di Rouchè-Capelli (versione estesa)

Sia dato il sistema

\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b},

dove \boldsymbol{A}\in\Bbb{K}^{m\times n}, \boldsymbol{x}\in\Bbb{K}^{n} e \boldsymbol{b}\in\Bbb{K}^{m}. Allora il sistema ha soluzione se e solo se il massimo ordine dei minori non nulli della matrice \boldsymbol{A} è lo stesso della matrice \begin{pmatrix}\boldsymbol{A},\boldsymbol{b}\end{pmatrix}.

Dimostrazione. Basta applicare il teorema seguente dimostrato negli appunti sui determinanti.

Teorema 2 (Minori e Indipendenza Lineare) Se i k vettori \boldsymbol{v}_{1},\,\boldsymbol{v}_{2},\ldots,\boldsymbol{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 \boldsymbol{A}\in \Bbb{K}^{k \times k} con n \geq k, definita come

\boldsymbol{A}= \begin{pmatrix}\boldsymbol{v}_{1}, \boldsymbol{v}_{2}, \ldots, \boldsymbol{v}_{k}\end{pmatrix}.

Sia \boldsymbol{x}\in\Bbb{K}^n una soluzione del sistema lineare \boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}, con \boldsymbol{A}\in\Bbb{K}^{m\times n} e \boldsymbol{b}\in\Bbb{K}^m, con \boldsymbol{b}\neq\boldsymbol{0}, e \tilde{\boldsymbol{x}}\in\Bbb{K}^n una soluzione del sistema lineare omogeneo \boldsymbol{A}\tilde{\boldsymbol{x}}=0.

É interessante notare che \boldsymbol{x}+\tilde{\boldsymbol{x}} è ancora soluzione del sistema lineare non omogeneo:

\boldsymbol{A}(\boldsymbol{x}+\tilde{\boldsymbol{x}}) = \boldsymbol{A}\boldsymbol{x}+ \boldsymbol{A}\tilde{\boldsymbol{x}} = \boldsymbol{b}+ \boldsymbol{0}= \boldsymbol{b}.

Quindi, data una soluzione particolare \boldsymbol{x} del sistema lineare non omogeneo — \boldsymbol{b}\neq\boldsymbol{0} — per ogni soluzione \tilde{\boldsymbol{x}} del sistema lineare omogeneo si ottiene una diversa soluzione del problema non omogeneo della forma \boldsymbol{x}+\tilde{\boldsymbol{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{\boldsymbol{x}}=\boldsymbol{0}, cioè che l’unica soluzione possibile del sistema lineare omogeneo \boldsymbol{A}\tilde{\boldsymbol{x}}=\boldsymbol{0} sia il vettore nullo.

Formalizziamo questa considerazione nel seguente teorema per matrici quadrate.

Esistenza e unicità per sistemi lineari

Teorema 3 Sia \boldsymbol{A}\in\Bbb{K}^{n\times n}, tale che \textrm{rank}(\boldsymbol{A})=n. Allora la soluzione \boldsymbol{x}\in\Bbb{K}^n del problema \boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}, con \boldsymbol{b}\in\Bbb{K}^n vettore assegnato, esiste ed è unica.

Dimostrazione. Dimostriamo separatamente prima l’esistenza e poi l’unicità.

• 1. Esistenza. Poiché in \Bbb{K}^n possiamo avere al massimo n vettori linearmente indipendenti, \textrm{rank}(\boldsymbol{A})=n implica che \textrm{rank}(\boldsymbol{A},\boldsymbol{b})=n, e l’esistenza segue dal teorema Teorema 3
• 2. Unicità. Essendo la matrice \boldsymbol{A} quadrata di ordine n uguale al suo rango, si deduce immediatamente che le sue colonne \boldsymbol{A}_{\bullet,1},\boldsymbol{A}_{\bullet,2},\ldots,\boldsymbol{A}_{\bullet,n}, sono vettori linearmente indipendenti. Supponiamo ora di avere due soluzioni possibili del sistema lineare non omogeneo, che indichiamo con \boldsymbol{x}_{1} e \boldsymbol{x}_{2}, per cui possiamo scrivere \boldsymbol{A}\boldsymbol{x}_{1}=\boldsymbol{A}\boldsymbol{x}_{2}=\boldsymbol{b}. Per differenza si ottiene \boldsymbol{A}(\boldsymbol{x}_{1}-\boldsymbol{x}_{2})=0, da cui segue che \boldsymbol{x}_{1}-\boldsymbol{x}_{2}=\boldsymbol{0}, cioè \boldsymbol{x}_{1}=\boldsymbol{x}_{2}.

Che cosa succede se la matrice è rettangolare?

Osservazione

Se la matrice \boldsymbol{A} è rettangolare con più colonne che righe (m < n), l’unicità della soluzione non è garantita. Infatti, il rango massimo della matrice è m, il che implica che almeno n - m colonne sono linearmente dipendenti dalle altre.

Di conseguenza, esistono almeno n - m vettori linearmente indipendenti in \Bbb{K}^n che rappresentano combinazioni lineari delle colonne di \boldsymbol{A}. Questi vettori costituiscono lo spazio delle soluzioni del problema omogeneo associato, rendendo la soluzione non unica.

Osservazione

Nel caso di matrici rettangolari con più righe che colonne (m > n), il massimo rango possibile è ovviamente n. Tuttavia, il sistema lineare ammette soluzioni solo se la condizione

\text{rank}(\boldsymbol{A}) = \text{rank}(\boldsymbol{A}, \boldsymbol{b})

è soddisfatta. In caso contrario, il sistema è sovradeterminato.

Questo significa che possiamo ridurre il sistema eliminando un certo numero di equazioni fino a ottenere una matrice quadrata o rettangolare con più colonne che righe. Se \text{rank}(\boldsymbol{A}) = n, possiamo eliminare opportunamente m - n equazioni per arrivare a una situazione che soddisfa il teorema @thm-sl:7b.

Se \text{rank}(\boldsymbol{A}) < n, dovremo eliminare un numero maggiore di equazioni e ci troveremo nella situazione descritta nell’osservazione precedente.

Note

1. Gabriel Cramer (1704-1752)

2. 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).

3. Eugène Rouché (1832-1910)

4. Alfredo Capelli (1855-1910)