Passa al tema normale
Discussioni su problemi, esercizi e teoremi che riguardano la geometria, l'algebra lineare e la topologia

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

Lemma di scambio e induzione

21/07/2019, 15:18

Ciao. Generi \( A=\left\{v_1,\dots,v_n\right\} \) lo spazio vettoriale \( V \), e sia \( B=\left\{w_1,\dots,w_r\right\} \) linearmente indipendente. Allora \( r\leqq n \).

Dimostrazione. L'idea è di provare che \( A^{'}=\left\{w_1,v_2,\dots,v_n\right\} \), \( A^{''}=\left\{w_1,w_2,v_3\dots,v_n\right\} \), ecc. generano ancora lo spazio. Una volta provato che \( \langle A'\rangle=V \), discende \( \langle A^{''}\rangle=V \), e così via.

Ciò che non riesco a formalizzarmi è il "e così via": ho sempre glissato su questa cosa, ma... non mi convince.

Evito di esporre i miei ragionamenti (riformulare in qualche modo l'enunciato), tanto non li legge nessuno :-)

Re: Lemma di scambio e induzione

21/07/2019, 16:02

Dovrebbe essere il lemma di Steinitz giusto?
Prova a leggere qui https://it.wikipedia.org/wiki/Lemma_di_Steinitz

Re: Lemma di scambio e induzione

21/07/2019, 17:00

Grazie per la risposta! È esattamente ciò che ho provato a fare io.

Occorre che io provi che per ogni spazio vettoriale \( n \)-generato \( V \), un insieme (finto1) linearmente indipendente ha cardinalità \( r \) non maggiore di \( n \). A occhio, procederei per induzione sul numero di vettori linearmente indipendenti. Il caso \( r=0 \) è banalmente verificato. Sia il claim vero per un naturale \( r>0 \) (sto cioè supponendo che per ogni spazio \( n \)-generato \( V \), ogni insieme finito linearmente indipendente abbia cardinalità minore di \( n \)); considerati \( r+1 \) vettori \( w_{1}^{'},\dots,w_{r+1}^{'} \) linearmente indipendenti, assumere \( r+1>n \) è contraddittorio: abbiamo infatti che esiste almeno un \( w_i^{'} \) tra costoro, tale che \( w_i^{'}=\sum_{j\neq i}\alpha_jv_j \), con ovvio significato dei simboli, dove i \( v_i \) sono i suddetti generatori. Ordunque, per considerazioni di servizio, \( \langle \left\{w_i\right\}\cup\left\{v_j\right\}_{j\neq i}\rangle \) è proprio lo spazio, che si rivela così generato da \( n \) elementi. \( \square \)

La domanda iniziale si può quindi rifrasare come (ed è di fatto quello che volevo chiedere): "È un argomento simile a quello di cui sopra ad essere adoperato ogniqualvolta capitino scritte come `iterando il procedimento \( n \) volte si ottiene come insieme di generatori [...]', che compaiono ad esempio nel link sul lemma di Steinitz?"

Note

  1. Si dimostrerà poi che se \( V \) è finitamente generato, anche ogni insieme linearmente indipendente deve essere finito.

Re: Lemma di scambio e induzione

21/07/2019, 18:17

Premetto che forse non ho capito fino in fondo la domanda e non so se posso rispondere nel modo più corretto.

In ogni caso, il procedimento di iterare affonda le sue radici nel principio di induzione. Definiamo questa funzione
\[
P : \mathbb{N}_{0}\to \{vero,falso\} \qquad P(r)="\mbox{$\forall S_{r}\subset V_{n}$ l.i, $|S_{r}|=r$ $\Rightarrow$ $r\le n$}"
\]
dove $S_{r}$ è un sistema di vettori e $V_{n}$ è uno spazio vettoriale $n$-dimensionale. Abbiamo $P(0)=\mbox{vero}$ e $P(r)=\mbox{vero}$ ogniqualvolta $P(r-1)=\mbox{vero}$: però, come hai mostrato, $P(r)=\mbox{falso}$ per ogni $r\ge n+1$. Pertanto si è pensato bene di procedere per assurdo e fare uso del principio di induzione.

Dovrebbe essere l'idea opposta della discesa all'infinito https://it.wikipedia.org/wiki/Discesa_infinita

Re: Lemma di scambio e induzione

21/07/2019, 19:02

Sì, posto \( P(r) \) (o \( P(r-1) \), è lo stesso ovviamente) vero, ho provato che assumere \( P(r+1)=\text{falso} \) genera un assurdo.

Non conoscevo la "discesa all'infinito", grazie per la segnalazione. Mi sembra interessante, provo a pensarci un attimo.

Re: Lemma di scambio e induzione

22/07/2019, 16:59

Voglio un attimo chiarire quel
marco2132k ha scritto:Si dimostrerà poi che se \( V \) è finitamente generato, anche ogni insieme linearmente indipendente deve essere finito


Sia \( V \) uno spazio vettoriale finitamente generato. Dico che un sottoinsieme \( A\subset V \) (eventualmente infinito) è linearmente indipendente se per ogni \( v\in A \) è \( v\not\in\langle A\setminus\{v\}\rangle \).

Allora vale la cosa in giallo. Dimostrazione. Sia \( A \) un sottoinsieme infinito e linearmente indipendente di uno spazio \( V \) finitamente generato da \( m \) vettori. Non è difficile far vedere che anche ogni parte finita di \( A \) è linearmente indipendente; e di qui si ricava un assurdo, perché ogni insieme infinito contiene, per ogni \( n\in\mathbb{N} \), un sottoinsieme di \( n \) elementi. \( \square \).

La mia domanda è, ora: è superflua una tale proposizione? Che detto meglio vuol dire: ciò che viene provato discende in qualche modo che mi sfugge da un altro dei tanti teoremini sul numero di elementi di sottospazi, basi, ecc. che compaiono in un libro di algebra lineare?

Re: Lemma di scambio e induzione

29/07/2019, 00:49

Ci ho riflettuto un attimo, sulla dimostrazione del lemma di scambio, e sono giunto alla gaia conclusione che probabilmente domenica scorsa ero sballato. Credo sia doveroso riportare quella corretta.

Proposizione (Lemma di scambio). Sia \( V \) uno spazio vettoriale finitamente generato sul campo \( C \), da un insieme \( \left\{v_1,\dots,v_n\right\} \) di \( n \) vettori. Allora, ogni sottoinsieme \( \left\{w_1,\dots,w_r\right\}\subset V \) di \( r>m \) elementi è linearmente dipendente.
Dimostrazione. L'idea è di procedere per assurdo, assumendo i \( w_1,\dots, w_r \) linearmente indipendenti, per un \( r>n \). Un generatore \( v_i \) appartiene, in tal caso, allo spazio generato da \( w_1 \) e dai vettori \( v_j \), per \( j\neq i \); a meno di una permutazione degli indici, tale vettore è \( v_1 \). Come d'altronde ogni dimostrazione di questo fatto avanza, ne deriva che l'insieme \( \left\{w_1,v_2,\dots,v_n\right\} \) è un genratore. Nella nostra ipotesi, conviene infatti che si dimostri che \( V \) è ancora generato, per ogni \( 1\leqq k<m \), da un insieme \( \left\{w_1,\dots,w_k,v_{k+1},\dots,v_m\right\} \). Più formalmente, quello che conviene dimostrare è che, per ogni naturale \( k \), se vale la catena di disuguaglianze \( 1\leqq k<m \), i vettori \( w_1\dots,w_k,v_{k+1},\dots,v_m \) ancora generano lo spazio (è un'affermazione sensata, ché i vettori dell'insieme che qui è assunto linearmente indipendente, sono in numero maggiore dei generatori). L'ipotesi per \( k=1 \) già è stata confermata. Se la cosa regge per un \( k \) naturale qualunque, sarà lecito scrivere il vettore \( w_{r+1} \) come
\[
w_{r+1}=\sum_{i=1}^k\alpha_iw_i+\sum_{i=k+1}^n\beta_iv_i
\] per \( \alpha_1,\dots,\alpha_k \) e \( \beta_{k+1},\dots,\beta_n \) elementi di \( C \). Un coefficiente \( \beta_i \) sarà non nullo per considerazioni di servizio, e la conclusione di tale fatto1 è l'appartenenza del vettore \( v_{k+1} \) allo span di \( w_1,\dots,w_{k+1}, v_{k+2},\dots,v_n \). Una contraddizione sembra seguire da sola. \( \square \)

Note

  1. Nel linguaggio dei post, funzione \( P\colon\mathbb{N}\to\left\{\mathrm{vero},\mathrm{falso}\right\} \) che \[ P\colon k\mapsto\begin{cases}\mathrm{vero}&\text{se $ 1\leqq k<n\implies \langle w_1,\dots,w_k,v_{k+1}\dots,v_n\rangle=V $}\\ \mathrm{falso}&\text{altrimenti}\end{cases} \] ha per immagine \( \left\{\mathrm{vero}\right\} \), ed è stato provato per induzione
Rispondi al messaggio