www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Lineare Algebra - Moduln und Vektorräume" - Kombinatorik Anzahl UVR von VR
Kombinatorik Anzahl UVR von VR < Moduln/Vektorraum < Lineare Algebra < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Lineare Algebra - Moduln und Vektorräume"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Kombinatorik Anzahl UVR von VR: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:05 Sa 02.01.2010
Autor: steppenhahn

Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)

Aufgabe
Sei K ein endlicher Körper mit q\in\IN Elementen. V sei ein K-VR der Dimension n\in\IN.

a) Wieviel Elemente hat GL(n,K)?
b) Wieviele Untervektorräume der Dimension m\in\N_{0} gibt es in V?

Hallo!

Die beiden obigen Fragestellungen bereiten mir Probleme. Bei der ersten habe ich eine Idee, wollte aber fragen ob die richtig ist:

Es gibt ja insgesamt q^{n} verschiedene Vektoren in V. (Aus Dimension n folgt n verschiedene Basisvektoren; jede Linearkombination der Basisvektoren stellt eindeutig einen Vektor von V dar; die Skalare können q verschiedene Werte annehmen).

Aufgabe a):

GL(n,K) ist ja die Gruppe der invertierbaren nxn Matrizen mit Koeffizienten aus K. Ich habe mir nun überlegt: Für den ersten Spaltenvektor der Matrix habe ich (n^{n}-1) Möglichkeiten (alle Vektoren außer der Nullvektor).

Für den zweiten Spaltenvektor habe ich nun nur noch (n^{n}-n) Möglichkeiten, weil schon q verschiedene Vektoren von dem ersten Vektor erzeugt werden, die ich jetzt nicht mehr wählen darf, weil die beiden Vektoren sonst linear abhängig wären (--> Matrix nicht invertierbar).

Für den dritten dann (n^{n}-n^{2}), usw. Insgesamt komme ich also auf:

$(n^{n}-1)*(n^{n}-n)*...*(n^{n}-n^{n-1}}) = n^{\frac{(n-1)*n}{2}}*\produkt_{k=1}^{n}(n^{k}-1)$

Elemente in GL(n,K).

Frage: Stimmt das? Wenn nicht, was muss ich dann für einen Ansatz machen?

Aufgabe b):

Ich weiß schonmal, dass es jeweils nur 1 UVR mit Dimension 1 und n gibt.
Ein UVR der Dimension m wird ja von m Basisvektoren erzeugt. Das heißt, ich müsste die Anzahl der Mengen mit m linear unabhängigen Vektoren aus V bestimmen.

Aber wie genau kann ich das machen? Jetzt ist es ja "ohne Beachtung der Reihenfolge"...

Grüße und danke für Eure Hilfe,
Stefan

        
Bezug
Kombinatorik Anzahl UVR von VR: Antwort
Status: (Antwort) fertig Status 
Datum: 11:58 Sa 02.01.2010
Autor: angela.h.b.


> Sei K ein endlicher Körper mit [mm]q\in\IN[/mm] Elementen. V sei
> ein K-VR der Dimension [mm]n\in\IN.[/mm]
>  
> a) Wieviel Elemente hat GL(n,K)?
>  b) Wieviele Untervektorräume der Dimension [mm]m\in\N_{0}[/mm]
> gibt es in V?
>  Hallo!
>  
> Die beiden obigen Fragestellungen bereiten mir Probleme.
> Bei der ersten habe ich eine Idee, wollte aber fragen ob
> die richtig ist:
>  
> Es gibt ja insgesamt [mm]q^{n}[/mm] verschiedene Vektoren in V. (Aus
> Dimension n folgt n verschiedene Basisvektoren; jede
> Linearkombination der Basisvektoren stellt eindeutig einen
> Vektor von V dar; die Skalare können q verschiedene Werte
> annehmen).
>  
> Aufgabe a):
>  
> GL(n,K) ist ja die Gruppe der invertierbaren nxn Matrizen
> mit Koeffizienten aus K. Ich habe mir nun überlegt: Für
> den ersten Spaltenvektor der Matrix habe ich [mm](n^{n}-1)[/mm]
> Möglichkeiten (alle Vektoren außer der Nullvektor).
>  
> Für den zweiten Spaltenvektor habe ich nun nur noch
> [mm](n^{n}-n)[/mm] Möglichkeiten, weil schon q verschiedene
> Vektoren von dem ersten Vektor erzeugt werden, die ich
> jetzt nicht mehr wählen darf, weil die beiden Vektoren
> sonst linear abhängig wären (--> Matrix nicht
> invertierbar).
>  
> Für den dritten dann [mm](n^{n}-n^{2}),[/mm] usw. Insgesamt komme
> ich also auf:
>  
> [mm](n^{n}-1)*(n^{n}-n)*...*(n^{n}-n^{n-1}}) = n^{\frac{(n-1)*n}{2}}*\produkt_{k=1}^{n}(n^{k}-1)[/mm]
>  
> Elemente in GL(n,K).
>  
> Frage: Stimmt das? Wenn nicht, was muss ich dann für einen
> Ansatz machen?

Hallo,

Deine Überlegungen stimmen. Irgendwie allerdings hast Du unterwegs aus dem q ein n gemacht.

Vielleicht habe ich heute nicht meinen allerhellsten Tag: ich seh grad nicht, wie das [mm] n^{\frac{(n-1)*n}{2}} [/mm] bzw. [mm] q^{\frac{(n-1)*n}{2}} [/mm] vor das Produkt gekommen ist.

[mm] \produkt_{k=0}^{n-1}(q^{n}-q^k) [/mm] wäre jedenfalls richtig, das ist ja auch das, was Du vor dem Gleichheitszeichen stehen haben wolltest.



>  
> Aufgabe b):
>  
> Ich weiß schonmal, dass es jeweils nur 1 UVR mit Dimension
> 1 und n gibt.
>  Ein UVR der Dimension m wird ja von m Basisvektoren
> erzeugt. Das heißt, ich müsste die Anzahl der Mengen mit
> m linear unabhängigen Vektoren aus V bestimmen.

Ja, genau.

Damit hast Du dann sämtliche Basen von m-dimensionalen Unterräumen gesammelt.

Und wieviele verschiedene Basen jeder m-dimensionale VR über dem Körper K mit q Elementen hat, weißt Du ja dank Aufgabe a) auch,

Also: passend dividieren.

Gruß v. Angela


Bezug
                
Bezug
Kombinatorik Anzahl UVR von VR: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:40 Sa 02.01.2010
Autor: steppenhahn

Hallo Angela,

erstmal vielen Dank für deine Antwort!

> > Für den dritten dann [mm](n^{n}-n^{2}),[/mm] usw. Insgesamt komme
> > ich also auf:
>  >  
> > [mm](n^{n}-1)*(n^{n}-n)*...*(n^{n}-n^{n-1}}) = n^{\frac{(n-1)*n}{2}}*\produkt_{k=1}^{n}(n^{k}-1)[/mm]
>  
> >  

> > Elemente in GL(n,K).

> Hallo,
>  
> Deine Überlegungen stimmen. Irgendwie allerdings hast Du
> unterwegs aus dem q ein n gemacht.

Du hast recht, da habe ich mir selbst irgendwas eingeredet...
  

> Vielleicht habe ich heute nicht meinen allerhellsten Tag:
> ich seh grad nicht, wie das [mm]n^{\frac{(n-1)*n}{2}}[/mm] bzw.
> [mm]q^{\frac{(n-1)*n}{2}}[/mm] vor das Produkt gekommen ist.
>  
> [mm]\produkt_{k=0}^{n-1}(q^{n}-q^k)[/mm] wäre jedenfalls richtig,
> das ist ja auch das, was Du vor dem Gleichheitszeichen
> stehen haben wolltest.

Genau, vor dem Gleichheitszeichen steht dann

[mm] $\produkt_{k=0}^{n-1}(q^{n}-q^k)$ [/mm]

Dann habe ich noch die vielleicht sinnlose Umformung gemacht, aus jeder Klammer [mm] n^{k} [/mm] auszuklammmern. Also:

[mm] $(q^{n}-1)*[q^{1}*(q^{n-1}-1)]*[q^{2}*(q^{n-2}-1)]*...*[q^{n-1}*(q-1)]$ [/mm]

Und diese ganzen Potenzen von q habe ich dann zu einer zusammengefasst, deren Exponent 1+2+...+(n-1) = [mm] \frac{n*(n-1)}{2} [/mm] ist.

?


> Also: passend dividieren.

Hierzu habe ich noch eine Frage: In a) habe ich doch aber sozusagen "Tupel" von linear unabhängigen Vektoren aus V gezählt, nun aber habe ich ja "Mengen", das heißt die Reihenfolge ist egal. Ist das nicht ein Problem?
Mit anderen Worten: In a) waren

[mm] \pmat{1& 0\\ 0& 1} [/mm] und [mm] \pmat{0& 1\\ 1& 0} [/mm]

zwei verschiedene Elemente und wurden beide gezählt, aber letztendlich erzeugen sie ja beide denselben UVR.

Ich weiß also, dass es insgesamt mit Beachtung der Reihenfolge

[mm] \produkt_{k=0}^{m-1}(q^{n}-q^{k}) [/mm]

verschiedene linear unabhängige m-Tupel von Vektoren aus V (Dimension n) über Körper K mit q Elementen gibt.
Und ich weiß, dass ein VR mit Dimension m über K mit q Elementen

[mm] \produkt_{k=0}^{m-1}(q^{m}-q^{k}) [/mm]

verschiedene Basen-Tupel hat.

Wenn ich jetzt dividiere:

[mm] \frac{\produkt_{k=0}^{m-1}(q^{n}-q^{k})}{ \produkt_{k=0}^{m-1}(q^{m}-q^{k})} [/mm]

behebe ich dann das oben angesprochene Problem und das ist die gesuchte Lösung?

Bitte um erneute Hilfe :-)

Grüße,
Stefan

Bezug
                        
Bezug
Kombinatorik Anzahl UVR von VR: Antwort
Status: (Antwort) fertig Status 
Datum: 14:48 Sa 02.01.2010
Autor: angela.h.b.


> Hallo Angela,
>  
> erstmal vielen Dank für deine Antwort!
>  
> > > Für den dritten dann [mm](n^{n}-n^{2}),[/mm] usw. Insgesamt komme
> > > ich also auf:
>  >  >  
> > > [mm](n^{n}-1)*(n^{n}-n)*...*(n^{n}-n^{n-1}}) = n^{\frac{(n-1)*n}{2}}*\produkt_{k=1}^{n}(n^{k}-1)[/mm]
>  
> >  

> > >  

> > > Elemente in GL(n,K).
>  
> > Hallo,
>  >  
> > Deine Überlegungen stimmen. Irgendwie allerdings hast Du
> > unterwegs aus dem q ein n gemacht.
>  
> Du hast recht, da habe ich mir selbst irgendwas
> eingeredet...
>    
> > Vielleicht habe ich heute nicht meinen allerhellsten Tag:
> > ich seh grad nicht, wie das [mm]n^{\frac{(n-1)*n}{2}}[/mm] bzw.
> > [mm]q^{\frac{(n-1)*n}{2}}[/mm] vor das Produkt gekommen ist.
>  >  
> > [mm]\produkt_{k=0}^{n-1}(q^{n}-q^k)[/mm] wäre jedenfalls richtig,
> > das ist ja auch das, was Du vor dem Gleichheitszeichen
> > stehen haben wolltest.
>  
> Genau, vor dem Gleichheitszeichen steht dann
>
> [mm]\produkt_{k=0}^{n-1}(q^{n}-q^k)[/mm]
>  
> Dann habe ich noch die vielleicht sinnlose Umformung
> gemacht, aus jeder Klammer [mm]n^{k}[/mm] auszuklammmern. Also:
>  
> [mm](q^{n}-1)*[q^{1}*(q^{n-1}-1)]*[q^{2}*(q^{n-2}-1)]*...*[q^{n-1}*(q-1)][/mm]
>  
> Und diese ganzen Potenzen von q habe ich dann zu einer
> zusammengefasst, deren Exponent 1+2+...+(n-1) =
> [mm]\frac{n*(n-1)}{2}[/mm] ist.
>  
> ?

Hallo,

achso. Mit dieser Nachhilfe hab' ich's jetzt auch druchschaut. Vorteilhaft ist's aber nicht.

>  
>
> > Also: passend dividieren.
>  
> Hierzu habe ich noch eine Frage: In a) habe ich doch aber
> sozusagen "Tupel" von linear unabhängigen Vektoren aus V
> gezählt, nun aber habe ich ja "Mengen", das heißt die
> Reihenfolge ist egal. Ist das nicht ein Problem?
>  Mit anderen Worten: In a) waren
>  
> [mm]\pmat{1& 0\\ 0& 1}[/mm] und [mm]\pmat{0& 1\\ 1& 0}[/mm]
>  
> zwei verschiedene Elemente und wurden beide gezählt, aber
> letztendlich erzeugen sie ja beide denselben UVR.
>  
> Ich weiß also, dass es insgesamt mit Beachtung der
> Reihenfolge
>
> [mm]\produkt_{k=0}^{m-1}(q^{n}-q^{k})[/mm]
>  
> verschiedene linear unabhängige m-Tupel von Vektoren aus V
> (Dimension n) über Körper K mit q Elementen gibt.

Genau.

>  Und ich weiß, dass ein VR mit Dimension m über K mit q
> Elementen
>
> [mm]\produkt_{k=0}^{m-1}(q^{m}-q^{k})[/mm]
>  
> verschiedene Basen-Tupel hat.

Ja.

>  
> Wenn ich jetzt dividiere:
>  
> [mm]\frac{\produkt_{k=0}^{m-1}(q^{n}-q^{k})}{ \produkt_{k=0}^{m-1}(q^{m}-q^{k})}[/mm]
>  
> behebe ich dann das oben angesprochene Problem und das ist
> die gesuchte Lösung?

Ja. Wir stecken alle [mm] \produkt_{k=0}^{m-1}(q^{m}-q^{k}) [/mm] zusammengehörigen Basen in einen Sack und zählen dann die Säcke = Untervektorräume.

Gruß v. Angela

>  
> Bitte um erneute Hilfe :-)
>  
> Grüße,So hb' ich mir das gedacht.
>  Stefan


Bezug
                                
Bezug
Kombinatorik Anzahl UVR von VR: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:28 Sa 02.01.2010
Autor: steppenhahn

Hallo Angela,

dann vielen Dank für deine Hilfe!
Allein wär ich da nie draufgekommen, aber jetzt hat's geklingelt :-)

Grüße,
Stefan

Bezug
                                        
Bezug
Kombinatorik Anzahl UVR von VR: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:35 So 03.01.2010
Autor: Nevanna

Hallo!
Ich bin noch ein wenig verunsichert: Ich bin das alles durchgegangen und muss sagen: Ist ja logisch!

Aber nur nochmal zur Sicherheit (bin seit 5uhr heute morgen wach, also bitte verzeiht mir diese wahrscheinlich total doofe Frage):

Das wars? Also die Formel da oben ist unsere Lösung? Oder kann ich das noch irgendwie berechnen?

Denn zur Berechnung fällt mir so spontan nichts ein...

Bezug
                                                
Bezug
Kombinatorik Anzahl UVR von VR: Antwort
Status: (Antwort) fertig Status 
Datum: 22:13 So 03.01.2010
Autor: steppenhahn

Hallo Nevanna,

was meinst du mit "berechnen"? q, m und n sind unbekannt, "ausrechnen" geht also schonmal nicht. Und vereinfachen - lohnt sich meiner Meinung nach nicht wirklich, weil dadurch die schöne Struktur verlorengeht, die den Gedankengang offenbart. Außerdem wäre Vereinfachen ein ziemliches rumgefummel...

Grüße,
Stefan


Bezug
                                                        
Bezug
Kombinatorik Anzahl UVR von VR: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 23:59 So 03.01.2010
Autor: Nevanna

Ok,genau das wollte ich wissen :) Danke!

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Lineare Algebra - Moduln und Vektorräume"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]