Lemma di Steinitz

Lemma di Steinitz — Dimostrazione completa

Sia $V$ uno spazio vettoriale di dimensione finita.
Siano $S=\{s_1,\dots ,s_m\}$ un insieme generatore di $V$ e $L=\{w_1,\dots ,w_r\}$ un insieme linearmente indipendente in $V$.

Enunciato (forma di scambio)

Vale $r\le m$ e si possono sostituire $r$ vettori di $S$ con $w_1,\dots ,w_r$ ottenendo ancora un insieme generatore di $V$. In particolare, se $\dim V=n$, ogni famiglia indipendente di $n$ vettori è una base; ogni famiglia di più di $n$ vettori è dipendente.

---

Dimostrazione

Procediamo per induzione su $k=1,\dots ,r$.
Induttivamente costruiremo insiemi

$$S_k=\{w_1,\dots ,w_k\}\cup \{s_i\mid i\notin J_k\},$$

dove $J_k\subseteq \{1,\dots ,m\}$, $|J_k|=k$, tali che $S_k$ genera $V$. In particolare, gli indici in $J_k$ sono esattamente quelli dei vettori di $S$ che abbiamo “scambiato” con $w_1,\dots ,w_k$.

Passo base ($k=1$)

Poiché $S$ genera $V$, esistono scalari ${\alpha }_1,\dots ,{\alpha }_m$ con

$$w_1=\sum _{i=1}^m{\alpha }_i{s}_i.$$

Sia $j$ un indice con ${\alpha }_j\ne 0$. Consideriamo

$$S_1:=\{w_1\}\cup \{s_i\mid i\ne j\}.$$

Mostriamo che $S_1$ genera $V$. Dalla relazione sopra,

$${\alpha }_j{s}_j=w_1-\sum _{i\ne j}{\alpha }_i{s}_i\Rightarrow s_j=\frac{1}{{\alpha }_j}{w}_1-\sum _{i\ne j}\frac{{\alpha }_i}{{\alpha }_j}{s}_i.$$

Quindi $s_j\in \mathrm{Span}(S_1)$ e dunque $\mathrm{Span}(S)\subseteq \mathrm{Span}(S_1)$. Ma $S$ generava $V$, quindi $\mathrm{Span}(S_1)=V$.

Passo induttivo ($k\to k+1$)

Assumiamo costruito $S_k$ che genera $V$. Poiché $S_k$ genera $V$, possiamo scrivere

$$w_{k+1}=\sum _{t=1}^k{\beta }_t{w}_t+\sum _{i\notin J_k}{\gamma }_i{s}_i.$$

Se tutti i coefficienti ${\gamma }_i$ fossero nulli, avremmo $w_{k+1}\in \mathrm{Span}\{w_1,\dots ,w_k\}$, contraddicendo l’indipendenza lineare di $L$.
Dunque esiste almeno un indice $j\notin J_k$ con ${\gamma }_j\ne 0$. Definiamo

$$S_{k+1}:=\{w_1,\dots ,w_{k+1}\}\cup \{s_i\mid i\notin J_k\cup \{j\}\}.$$

Dalla relazione precedente,

$${\gamma }_j{s}_j=w_{k+1}-\sum _{t=1}^k{\beta }_t{w}_t-\sum _{i\notin J_k,i\ne j}{\gamma }_i{s}_i,$$

perciò

$$s_j\in \mathrm{Span}(S_{k+1}).$$

Ne segue $\mathrm{Span}(S_k)\subseteq \mathrm{Span}(S_{k+1})$ e quindi, poiché $S_k$ generava $V$, anche $S_{k+1}$ genera $V$.

Chiusura

Iterando per $k=1,\dots ,r$ otteniamo $S_r$, ottenuto sostituendo $r$ elementi di $S$ con $w_1,\dots ,w_r$, che genera ancora $V$. In particolare $r\le m$ (abbiamo sostituito $r$ indici distinti tra $1,\dots ,m$).

---

Conseguenze immediate

1. Se $\dim V=n$ e $L=\{w_1,\dots ,w_n\}$ è indipendente, allora per Steinitz $n\le m$ per ogni generatore $S$; scegliendo $S$ una base di $n$ elementi, si ottiene che $L$ genera $V$. Quindi $L$ è una base.
2. Qualsiasi insieme con più di $n$ vettori in $V$ è dipendente (non può essere indipendente per il punto 1).
3. La versione di scambio è alla base del completamento (un insieme indipendente si estende a base) e del teorema di esistenza (da un generatore finito si estrae una base).

---

Nota operativa (lettura “a colonne”)

Se disponi i vettori di $S$ come colonne di una matrice che genera ${\mathbb{K}}^n$, l’operazione di scambio sopra corrisponde a sostituire una colonna non pivot con una nuova colonna $w_k$ (con coefficiente non nullo su quella posizione), mantenendo lo span delle colonne invariato. È la base concettuale della riduzione di Gauss vista come “gestione dello span”.