Contare bandiere spazio vettoriale
Stavo pensando alla domanda sul contare le flag nel caso di spazio vettoriale finito (fatta qui https://www.matematicamente.it/forum/vi ... 7&t=204205) e mi è venuto in mente un modo in cui si potrebbe procedere.
Intanto concordiamo le definizioni:
Dato un $k$-spazio vettoriale $V$ (nota)[nota]di dimensione al più numerabile, come mi ha fatto notare arnett[/nota]
Una flag è una successione al più numerabile e strettamente crescente di sottospazi vettoriali che parte da $0$ e "finisce" con $V$.
In formule \(\mathcal{F}=\{ W_i \}_{i \in \mathbb{N}}\) con
\(W_i \subsetneq W_{i+1}\)
$W_0=0$
$\bigcup_{i \in mathbb{N}}W_i=V$
Si vede che è possibile ordinare le flag rispetto al contenimento, rendendo l'insieme delle flag un poset.
C'ho messo un po' a capire che era una cosa sensata
Avvalendosi del lemma di Zorn (certo dovremmo verificare le ipotesi
) si vede che esistono flag massimali.
Inoltre osserviamo che possono essere caratterizzate come le flag che sono indotte da una base (questo non dovrebbe essere difficile da dimostrare).
Nota: le basi saranno sempre basi ordinate, anche se a volte mi dimenticherò di scriverlo.
Adesso mettiamoci nel contesto che piace a noi
Ovvero $V$ $k$-sp. vett. di dimensione finita con $k=F_q$ campo con $q$ elementi dove $q$ potenza di un primo.
Vogliamo contare le flag massimali.
Contate queste, contare tutte le flag dovrebbe essere abbastanza facile, perché le posso vedere come una scelta di sottospazi in una flag massimale (Sotto a questa cosa ci sta il fatto che ogni flag la posso estendere a flag massimale).
Ora vediamo che basi diverse possono indurre la stessa flag, ma come si capisce se due basi inducono la stessa flag? La risposta che mi sono dato è la seguente:
Lemma due basi $B_1$ e $B_2$ inducono la stessa flag se e solo se la matrice di cambio di base $M_{B_1, B_2}$ è triangolare.
Adesso si dimostra che ( \(B_1 \sim B_2 \leftrightarrow M_{B_1, B_2}\) è triangolare) è una relazione di equivalenza sull'insieme delle basi (ordinate) di $V$.
Ci siamo quindi ridotti, per il nostro problema, a contare la cardinalità di \(X/\sim\) dove $X$ è l'insieme delle basi (ordinate) di $V$ e \(\sim\) è la relazione di equivalenza introdotta.
Nota: mi rendo conto adesso che si può rileggere tutto in termini di azione del gruppo delle matrici triangolari sull'insieme $X$, e quello a cui ci siamo ridotti è contare le orbite.
Intanto concordiamo le definizioni:
Dato un $k$-spazio vettoriale $V$ (nota)[nota]di dimensione al più numerabile, come mi ha fatto notare arnett[/nota]
Una flag è una successione al più numerabile e strettamente crescente di sottospazi vettoriali che parte da $0$ e "finisce" con $V$.
In formule \(\mathcal{F}=\{ W_i \}_{i \in \mathbb{N}}\) con
\(W_i \subsetneq W_{i+1}\)
$W_0=0$
$\bigcup_{i \in mathbb{N}}W_i=V$
Si vede che è possibile ordinare le flag rispetto al contenimento, rendendo l'insieme delle flag un poset.
C'ho messo un po' a capire che era una cosa sensata
Avvalendosi del lemma di Zorn (certo dovremmo verificare le ipotesi
) si vede che esistono flag massimali.Inoltre osserviamo che possono essere caratterizzate come le flag che sono indotte da una base (questo non dovrebbe essere difficile da dimostrare).
Nota: le basi saranno sempre basi ordinate, anche se a volte mi dimenticherò di scriverlo.
Adesso mettiamoci nel contesto che piace a noi
Ovvero $V$ $k$-sp. vett. di dimensione finita con $k=F_q$ campo con $q$ elementi dove $q$ potenza di un primo.
Vogliamo contare le flag massimali.
Contate queste, contare tutte le flag dovrebbe essere abbastanza facile, perché le posso vedere come una scelta di sottospazi in una flag massimale (Sotto a questa cosa ci sta il fatto che ogni flag la posso estendere a flag massimale).
Ora vediamo che basi diverse possono indurre la stessa flag, ma come si capisce se due basi inducono la stessa flag? La risposta che mi sono dato è la seguente:
Lemma due basi $B_1$ e $B_2$ inducono la stessa flag se e solo se la matrice di cambio di base $M_{B_1, B_2}$ è triangolare.
.Adesso si dimostra che ( \(B_1 \sim B_2 \leftrightarrow M_{B_1, B_2}\) è triangolare) è una relazione di equivalenza sull'insieme delle basi (ordinate) di $V$.
Ci siamo quindi ridotti, per il nostro problema, a contare la cardinalità di \(X/\sim\) dove $X$ è l'insieme delle basi (ordinate) di $V$ e \(\sim\) è la relazione di equivalenza introdotta.
Nota: mi rendo conto adesso che si può rileggere tutto in termini di azione del gruppo delle matrici triangolari sull'insieme $X$, e quello a cui ci siamo ridotti è contare le orbite.
Risposte
Come ti ho detto per messaggio privato, esiste un ordine parziale naturale sull'insieme delle bandiere di \(V\), quando guardi una bandiera come una funzione monotona da \(\Delta[n]\) a \(\mathsf{S}(V)\) (i sottospazi di \(V\)).
Questo ordine parziale è per raffinamento: una bandiera ne raffina un'altra se ogni elemento della seconda è elemento della prima (questo si può formalizzare come ti ho scritto).
In questo ordine parziale \(\preceq\), le bandiere massimali (che wikipedia chiama "complete") sono gli elementi massimali.
Tu adesso vuoi dimostrare due cose:
- La prima è che due basi inducono la stessa bandiera se e solo se il cambio di coordinate è una matrice triangolare superiore. Questo si formalizza come segue: il gruppo generale lineare agisce su una bandiera mandando la tupla di vettori \((v_1,\dots,v_k)\) e l'automorfismo \(A\in GL(V)\) in \((Av_1,\dots,Av_k)\). Ciò che vuoi dimostrare tu equivale a dire che lo stabilizzatore per questa azione è il sottogruppo delle matrici triangolari superiori (cosa che viene detta essere vera su wikipedia, senza però dimostrazione).
Supponi che \(A\) fissi una bandiera completa: allora è triangolare nella (in ogni) base adattata alla bandiera perché il fatto che \(A\) fissi la bandiera significa che la fissa termine a termine; quindi \(A.(v_1,\dots,v_k)\le (v_1,\dots,v_k)\), cosa che implica che nella base adattata della bandiera \(A\) si scrive come matrice triangolare; il viceversa è più facile: se \(A\) è triangolare in una base adattata alla bandiera, è evidente che \(A.(v_1,\dots, v_k) \le (v_1,\dots,v_k)\) per ogni indice \(k\) degli elementi della bandiera.
L'altra cosa che vuoi dimostrare è che quella che scrivi è una relazione di equivalenza; l'unica cosa non esattamente ovvia è che l'inversa di una matrice triangolare superiore è ancora triangolare superiore: per dimostrarlo si può usare la formula di Laplace, oppure osservare che se un prodotto di matrici \(LK\) è triangolare superiore, e \(L\) è triangolare superiore, tale è anche \(K\) (scrivi il prodotto di matrici esplicitamente).
Questo ordine parziale è per raffinamento: una bandiera ne raffina un'altra se ogni elemento della seconda è elemento della prima (questo si può formalizzare come ti ho scritto).
In questo ordine parziale \(\preceq\), le bandiere massimali (che wikipedia chiama "complete") sono gli elementi massimali.
Tu adesso vuoi dimostrare due cose:
- La prima è che due basi inducono la stessa bandiera se e solo se il cambio di coordinate è una matrice triangolare superiore. Questo si formalizza come segue: il gruppo generale lineare agisce su una bandiera mandando la tupla di vettori \((v_1,\dots,v_k)\) e l'automorfismo \(A\in GL(V)\) in \((Av_1,\dots,Av_k)\). Ciò che vuoi dimostrare tu equivale a dire che lo stabilizzatore per questa azione è il sottogruppo delle matrici triangolari superiori (cosa che viene detta essere vera su wikipedia, senza però dimostrazione).
Supponi che \(A\) fissi una bandiera completa: allora è triangolare nella (in ogni) base adattata alla bandiera perché il fatto che \(A\) fissi la bandiera significa che la fissa termine a termine; quindi \(A.(v_1,\dots,v_k)\le (v_1,\dots,v_k)\), cosa che implica che nella base adattata della bandiera \(A\) si scrive come matrice triangolare; il viceversa è più facile: se \(A\) è triangolare in una base adattata alla bandiera, è evidente che \(A.(v_1,\dots, v_k) \le (v_1,\dots,v_k)\) per ogni indice \(k\) degli elementi della bandiera.
L'altra cosa che vuoi dimostrare è che quella che scrivi è una relazione di equivalenza; l'unica cosa non esattamente ovvia è che l'inversa di una matrice triangolare superiore è ancora triangolare superiore: per dimostrarlo si può usare la formula di Laplace, oppure osservare che se un prodotto di matrici \(LK\) è triangolare superiore, e \(L\) è triangolare superiore, tale è anche \(K\) (scrivi il prodotto di matrici esplicitamente).
"arnett":
1. Stai ammettendo al massimo flag numerabili. Ma se lo spazio vettoriale ha dimensione infinita non numerabile? Diciamo che non ammette flag? (Poiché una flag numerabile non arriva mai a saturare lo spazio).
Beh sì hai ragione. Diciamo che dovevo partire dicendo che sto definendo le flag per spazi con base al più numerabile.
"arnett":
2. Sono d'accordo che l'intersezione di flag è flag, sono più dubbioso sull''unione.
Infatti hai proprio ragione, mi sono fatto prendere dall'entusiasmo e ho scritto una minchiata
Grazie per le osservazioni!
"solaàl":
Come ti ho detto per messaggio privato, esiste un ordine parziale naturale sull'insieme delle bandiere di V
Non so se dici a me o a arnett, ma io non ho ricevuto messaggi privati.
Grazie comunque per i suggerimenti
Ad ogni modo non volevo un aiuto a dimostrare queste cose, volevo solo proporlo perché ho trovato interessante pensarci!
Non so se dici a me o a arnett, ma io non ho ricevuto messaggi privati.
Oh, sì, forse ho pensato fossi la stessa persona che aveva fatto la domanda.
Non so se dici a me o a arnett, ma io non ho ricevuto messaggi privati.
Oh, sì, forse ho pensato fossi la stessa persona che aveva fatto la domanda.
"arnett":E questo non è precisamente l'ordine indotto dall'inclusione?[/quote]
[quote="solaàl"]
Questo ordine parziale è per raffinamento: una bandiera ne raffina un'altra se ogni elemento della seconda è elemento della prima (questo si può formalizzare come ti ho scritto).
No, non lo è: con ordine!
1. Una bandiera (anche detta "catena") in \(P\) è una funzione monotòna \(f : [n] \to P\) dove \([n]\) o \(\Delta[n]\) è l'insieme totalmente ordinato \(\{1<\cdots
2. Sull'insieme \(\text{flg}(P)\) di queste funzioni definisco una relazione d'ordine parziale: date \(f : [n] \to P\) e \(g : [m]\to P\) dico che \(f\preceq g\) (si legge: "\(g\) raffina \(f\)") se esiste una funzione iniettiva \(i : [n] \to [m]\) (nota che quindi deve essere \(n\le m\)) tale che \(g\circ i =f\).
3. Le catene massimali sono gli elementi \(\preceq\)-massimali.
(Non c'entra con la questione, ma mi sembra che questa descrizione permette di mostrare che in \(\text{flg}(P)\) ogni [url=https://proofwiki.org/wiki/Definition:Initial_Segment]segmento iniziale[/url] ammette un minimale: ogni funzione \(f : [n]\to P\) si fattorizza come una composizione \([n] \xrightarrow{r} [k] \xrightarrow{f'} P\) dove \(f'\) è iniettiva e \(r\) è suriettiva; allora una qualsiasi inversa destra a \(r : [n]\to [k]\) mostra che \(f'\preceq f\); ti lascio dimostrare che \(f'\) è minimale nel segmento iniziale \([f]_\downarrow := \{h\in P\mid h\prec f\}\))
In generale, uno spazio vettoriale di dimensione finita \(L\) si può spezzare in indecomponibili (esattamente i sottospazi di dimensione 1) e una catena massimale si ottiene a partire da una base di \(L\) aggiungendo uno ad uno i vettori di una sua base; dicevo per messaggio privato a marco2132k[nota]Che ha aperto diversi thread sul contare e caratterizzare le bandiere, e con cui credevo di stare parlando ancora.[/nota] che questo è un elemento massimale di \((\text{flg}(L), \preceq)\) (\(\text{flg}(L)=\text{flg}(\textsf{S}(L))\), le bandiere nel reticolo dei sottospazi di \(L\)), semplicemente perché se \((0)\le M\le \langle e\rangle\) allora o \(M=0\) oppure \(M = \langle e\rangle\) (il caso generale è un corollario di questo quando passi ai quozienti: se \(L_i \le M\le L_{i+1}\) allora \((0) \le M/L_i \le L_{i+1}/L_i \cong \langle e_{i+1}\rangle\)).
"arnett":No, una bandiera è esattamente l'insieme delle sue immagini, nello stesso senso in cui una funzione \(f : X \to A\) è l'insieme \((a_x)\) dei valori che assume al variare di \(x\in X\).
Ho scritto un post per dire che continuavo a non capire che cosa volessi dire, ma poi forse ho capito. Tu mi stai dicendo che è vietata l'identificazione di una bandiera $\mathcal{F}:[n]\to\mathsf{S}(V)$ con l'insieme delle sue immagini, cioè che è sbagliato scrivere $\mathcal{F}=\{W_i\}_{i=1, \cdots , n}$? È questo il punto?
Credo di capire pure che la ragione di questo è che quando una bandiera ne raffina un'altra, i sottospazi che stanno nell'immagine di $\mathcal{F}_2$ ma non nell'immagine di $\mathcal{F}_1$ si pongono tra i sottospazi (che stanno nell'immagine) di $\mathcal{F}_1,$ alla maniera seguente:Sì, certo!
\[\mathcal{F}_1: 0=W_1 \subsetneq W_2 \subsetneq W_3 \subsetneq \dots \dots \subsetneq W_n\]
\[\mathcal{F}_2: 0=W_1 \subsetneq W_{11} \subsetneq \dots \subsetneq W_{1m_1} \subsetneq W_2 \subsetneq W_{21} \subsetneq \dots \subsetneq W_{2m_2} \subsetneq \dots \subsetneq W_{n} \subsetneq W_{n1} \subsetneq \dots \subsetneq W_{nm_n}.\]
Osservo pure che però tu ammetti solo bandiere finite. È perché al momento stiamo parlando solo di spazi vettoriali di dimensione finita o hai altre ragioni per farlo?Nulla vieta a una catena di essere infinita: in quel caso, invece di \([n]\), dovrai prendere un ordinale infinito più grande.
Scusate se ho maleducatamente abbandonato il mio post ma ho avuto degli impegni.
Comunque ho capito la definizione di solaàl e mi sembra più elegante di quella che avevo dato io nel primo post, ma continua a sembrarmi equivalente.
Potresti mostrarmi un esempio che distingue il tuo ordine dal mio?
Magari è evidente ma io non sono riuscito a figurarmelo.
Comunque ho capito la definizione di solaàl e mi sembra più elegante di quella che avevo dato io nel primo post, ma continua a sembrarmi equivalente.
Potresti mostrarmi un esempio che distingue il tuo ordine dal mio?
Magari è evidente ma io non sono riuscito a figurarmelo.
"solaàl":No, una bandiera è esattamente l'insieme delle sue immagini, nello stesso senso in cui una funzione \(f : X \to A\) è l'insieme \((a_x)\) dei valori che assume al variare di \(x\in X\).
[quote="arnett"]Ho scritto un post per dire che continuavo a non capire che cosa volessi dire, ma poi forse ho capito. Tu mi stai dicendo che è vietata l'identificazione di una bandiera $\mathcal{F}:[n]\to\mathsf{S}(V)$ con l'insieme delle sue immagini, cioè che è sbagliato scrivere $\mathcal{F}=\{W_i\}_{i=1, \cdots , n}$? È questo il punto?
[/quote]
Io direi che sono lo stesso ordine, e il motivo è ciò che tu dici qui.
Il fatto è che non capisco cosa significhi formalmente \(\mathcal F_1\subset \mathcal F_2\), se non guardandolo come abuso di notazione per indicare la condizione di raffinamento... notate che un raffinamento banale di \(\mathcal F\) si ottiene ripetendo alcuni degli elementi della catena. In quel caso però \(\mathcal F \) e il suo raffinamento sono lo stesso insieme, perché gli insiemi non sono multiinsiemi.
Questo per dire che una catena non è la collezione degli elementi che la compongono, ma l'ordine totale che essi formano, ossia (appunto) la funzione monotona \(\kappa \to P\) (\(\kappa\) un ordinale a caso) che definiscono.
Questo per dire che una catena non è la collezione degli elementi che la compongono, ma l'ordine totale che essi formano, ossia (appunto) la funzione monotona \(\kappa \to P\) (\(\kappa\) un ordinale a caso) che definiscono.
"jinsang":
Adesso mettiamoci nel contesto che piace a noi
Ovvero $V$ $k$-sp. vett. di dimensione finita con $k=F_q$ campo con $q$ elementi dove $q$ potenza di un primo.
Vogliamo contare le flag massimali.
Contate queste, contare tutte le flag dovrebbe essere abbastanza facile, perché le posso vedere come una scelta di sottospazi in una flag massimale (Sotto a questa cosa ci sta il fatto che ogni flag la posso estendere a flag massimale).
Scusate se mi intrometto, ma vorrei vedere la risposta a questa domanda, è stata data? Forse me la sono persa? (In questo thread, la domanda sopra è l'unica che ammette una risposta concreta sotto forma di un numero, ed è quindi la più importante, stando all'"advice to young mathematicians" di Georges Elencwajg. Mi dispiacerebbe se venisse snobbata).
"dissonance":
[quote="jinsang"]
Adesso mettiamoci nel contesto che piace a noi
Ovvero $ V $ $ k $-sp. vett. di dimensione finita con $ k=F_q $ campo con $ q $ elementi dove $ q $ potenza di un primo.
Vogliamo contare le flag massimali.
Contate queste, contare tutte le flag dovrebbe essere abbastanza facile, perché le posso vedere come una scelta di sottospazi in una flag massimale (Sotto a questa cosa ci sta il fatto che ogni flag la posso estendere a flag massimale).
Scusate se mi intrometto, ma vorrei vedere la risposta a questa domanda, è stata data? Forse me la sono persa? (In questo thread, la domanda sopra è l'unica che ammette una risposta concreta sotto forma di un numero, ed è quindi la più importante, stando all'"advice to young mathematicians" di Georges Elencwajg. Mi dispiacerebbe se venisse snobbata).[/quote]
No infatti hai ragione.
Provo a darla adesso:
Diciamo che $dimV=n$
Considero l'azione
\[Gl(V)\rightarrow \mathfrak{S}(flag(V)) \\
g\mapsto \phi_g:flag(V)\rightarrow flag(V)\\
\phi_g(W_0\subsetneq ... \subsetneq W_k)= g(W_0)\subsetneq ... \subsetneq g(W_k)\]
Si può vedere che la successione delle dimensioni dei sottospazi è un invariante completo per l'azione (nel senso che due bandiere sono nella stessa orbita se e solo se hanno la stessa successione delle dimensioni).
Dunque le bandiere massimali rappresentano un'orbita (quella che ha successione delle dimensioni $0<1<...
Per un noto fatto di algebra, dato un generico \(\mathcal{F} \in flag(V)\), abbiamo la bigezione:
\[orb(\mathcal{F}) \leftrightarrow Gl(V)/stab(\mathcal{F})\]
Quindi se troviamo la cardinalità di $Gl(V)$ e di \(stab(\mathcal{F})\) (dove \(\mathcal{F}\) è una bandiera massimale) sappiamo quante sono le bandiere massimali.
Poniamo \(\mathcal{F}=(0 \subsetneq span\{e_1 \} \subsetneq ... \subsetneq span\{e_1,...,e_n\})\)
Vediamo che \(g \in stab(\mathcal{F}) \Leftrightarrow g(e_i) \in span \{e_1,...,e_i\} \ \ \forall i \)
Questo è equivalente a dire che $g$ si rappresenta come matrice triangolare nella base \(\{e_1,...,e_n\}\)
Siamo arrivati perché:
\[ \#Gl(V)=(q^n-1)(q^n-q)...(q^n-q^{n-1})=q^{n(n-1)/2}\prod_{1\leq j \leq n} (q^j-1) \]
\[ \#stab(\mathcal{F})=(q-1)^nq^{n(n-1)/2}\]
Perciò
\[ \#orb(\mathcal{F})= \frac{\#Gl(V)}{\#stab(\mathcal{F})} = \frac{\prod_{1\leq j \leq n} (q^j-1)}{(q-1)^n}=\prod_{1\leq j \leq n}\frac{(q^j-1)}{(q-1)}=\prod_{1\leq j \leq n}\sum_{0\leq i < j}q^i \]
Per il caso generale (bandiere non necessariamente massimali) si ragiona come sopra, solo che gli stabilizzatori saranno matrici triangolari a blocchi. Sarà un pochino più difficile contare ma non difficilissimo, basta osservare che i blocchi sulla diagonale sono matrici invertibili (che sappiamo contare) e sopra la diagonale a blocchi posso mettere cosa mi pare.
Ammetto di aver cambiato un po' punto di vista sul problema, i conti che vengono fuori sono gli stessi che mi venivano fuori con l'approccio descritto nel primo post, però l'idea di azione di gruppo mi piace di più e poi secondo me fa anche capire meglio cosa si sta facendo.
[ot] (anche nel senso che ci sono risposte concretissime, ma auguri a far venire fuori un numero...)[/ot]
è l'unica che ammette una risposta concreta sotto forma di un numeroCi sono molte risposte concrete che però non parlano di numeri, è una analogia capziosa quella tra "lo posso calcolare" e "posso far venire fuori un numero"
(anche nel senso che ci sono risposte concretissime, ma auguri a far venire fuori un numero...)[/ot]
"arnett":confligga con quest'altro:
Mi pare che questo: [quote="solaàl"]...
"solaàl":[/quote]
...
Ho capito: sì, probabilmente sono lo stesso ordine. Da un lato, rappresentare le catene come funzioni monotona da un ordinale permette di sapere immediatamente qual è la "giusta" definizione per l'ordine da mettere sull'insieme delle catene della stessa lunghezza.
Tu però vuoi una relazione d'ordine su tutte le catene a codominio costante; questo penso si faccia mettendo una relazione d'ordine su \(\bigcup_{[n]\in\omega}\text{Pos}([n],P)\).
"jinsang":Più che altro ho aperto io la discussione... Però è un po' out of reach per me quindi sto zitto
Scusate se ho maleducatamente abbandonato il mio post ma ho avuto degli impegni.
"jinsang":
Perciò
\[ \#orb(\mathcal{F})= \frac{\#Gl(V)}{\#stab(\mathcal{F})} = \frac{\prod_{1\leq j \leq n} (q^j-1)}{(q-1)^n}=\prod_{1\leq j \leq n}\frac{(q^j-1)}{(q-1)}=\prod_{1\leq j \leq n}\sum_{0\leq i < j}q^i \]
Troppo buoni!
Poi magari ci trovate qualche errore e me la smontate
Poi magari ci trovate qualche errore e me la smontate
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo