Kombinatorik Anzahl UVR von VR < Moduln/Vektorraum < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
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
|
|
|
|
> 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
|
|
|
|
|
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
|
|
|
|
|
> 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
|
|
|
|
|
Hallo Angela,
dann vielen Dank für deine Hilfe!
Allein wär ich da nie draufgekommen, aber jetzt hat's geklingelt
Grüße,
Stefan
|
|
|
|
|
Status: |
(Frage) beantwortet | 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...
|
|
|
|
|
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
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 23:59 So 03.01.2010 | Autor: | Nevanna |
Ok,genau das wollte ich wissen :) Danke!
|
|
|
|