Completamento a base

Da Wikipedia, l'enciclopedia libera.

Il completamento a base è un algoritmo utile in algebra lineare a completare un insieme di vettori linearmente indipendenti in uno spazio vettoriale ad una base.

Indice

1 Il teorema
2 Dimostrazione e algoritmo
3 Esempio
4 Voci correlate

[modifica] Il teorema

Sia $V$ uno spazio vettoriale su un campo $K$ , di dimensione $n$ . Il teorema di completamento a base (o teorema della base incompleta) asserisce che:

Se $v_1, \ldots, v_k$ sono vettori linearmente indipendenti in $V$ , allora:

$k$ è minore o uguale a $n$ ,
se $k < n$ , esistono $n - k$ vettori $v_{k+1},\ldots, v_n$ tali che l'insieme ordinato $v_1,\ldots, v_n$ è una base.

[modifica] Dimostrazione e algoritmo

La dimostrazione fornisce un algoritmo che consente di trovare concretamente i vettori $v_{k+1},\ldots, v_n$ .

L'algoritmo funziona nel modo seguente: si aggiunga all'insieme $v_1,\ldots, v_k$ una base nota $w_1,\ldots,w_n$ dello spazio $V$ (ad esempio, questa può essere la base canonica se $V = K n$ ). Si ottiene quindi l'insieme ordinato

$S = (v_1,\ldots,v_k,w_1,\ldots,w_n)$ .

L'insieme $S$ genera tutto lo spazio $V$ , poiché contiene dei generatori $w_1,\ldots, w_n$ . Si applica quindi ad $S$ l'algoritmo di estrazione di una base. Questo algoritmo elimina, partendo da sinistra, quei vettori che sono dipendenti dai vettori precedenti. Poiché i primi $k$ sono indipendenti, l'algoritmo eliminerà soltanto alcuni dei vettori $w i$ : il risultato è quindi una base contenente $v_1,\ldots,v_k$ .

[modifica] Esempio

I vettori $(2,1,0)$ e $(1, - 1,0)$ in $\R^3$ sono indipendenti. Quindi esiste un terzo vettore che forma una base con questi due, e può essere trovato usando l'algoritmo di completamento. Si aggiunge quindi ai due vettori la base canonica:

$\begin{pmatrix} 2 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ -1 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}.$

L'algoritmo di estrazione mantiene i primi due vettori, quindi elimina il terzo e il quarto (entrambi generati dai primi due), e tiene di conseguenza il quinto. Si ottiene quindi la base

$\begin{pmatrix} 2 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ -1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}.$