Anzahl Matrizen mit tr=1 det=1 < Matrizen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:58 Do 21.01.2010 | | Autor: | valoo |
| Aufgabe | Sei [mm] \IF_{2} [/mm] der Körper mit zwei Elementen. Bestimmen Sie die für alle [mm] n\in \IN [/mm] Anzahl der nxn Matrizen über [mm] \IF_{2} [/mm] mit
a) det(M)=1
b) trace(M)=1 |
Hat doch nur was mit Kombinatorik zu tun... Kann doch so schwer nicht sein...
Bei b) glaube ich, dass das die Hälfte aller Matrizen ist (also [mm] 2^{n^{2}-1}) [/mm] denn die Spur ist gerade 1, wenn die Anzahl der Einseinträge auf der Diagonalen ungerade ist. Ich hoffe, dass es genauso viele von denen gibt wie von den mit gerader Anzahl Einseinträge auf der Diagonalen. Doch wie sollte man das beweisen, wenn dem so ist?
Zu a): Da habe ich noch nicht wirklich einen Ansatz zu. Die Determinante (besonders von beliebigen nxn Matritzen ist zu kompliziert, als das mir da was einfallen würde...) Oder kann ich die Matritzen irgendwie in Ähnlichkeitsklassen aufteilen und mir angucken, wie viele von denen die Determinante 1 haben?
|
|
| |
|
> Sei [mm]\IF_{2}[/mm] der Körper mit zwei Elementen. Bestimmen Sie
> die für alle [mm]n\in \IN[/mm] Anzahl der nxn Matrizen über
> [mm]\IF_{2}[/mm] mit
> a) det(M)=1
> b) trace(M)=1
> Hat doch nur was mit Kombinatorik zu tun... Kann doch so
> schwer nicht sein...
> Bei b) glaube ich, dass das die Hälfte aller Matrizen ist
> (also [mm]2^{n^{2}-1})[/mm] denn die Spur ist gerade 1, wenn die
> Anzahl der Einseinträge auf der Diagonalen ungerade ist.
> Ich hoffe, dass es genauso viele von denen gibt wie von den
> mit gerader Anzahl Einseinträge auf der Diagonalen. Doch
> wie sollte man das beweisen, wenn dem so ist?
> Zu a): Da habe ich noch nicht wirklich einen Ansatz zu.
> Die Determinante (besonders von beliebigen nxn Matritzen
> ist zu kompliziert, als das mir da was einfallen würde...)
> Oder kann ich die Matritzen irgendwie in
> Ähnlichkeitsklassen aufteilen und mir angucken, wie viele
> von denen die Determinante 1 haben?
Hallo valoo,
die Aufgabe b) ist wirklich nur einfache Kombinatorik,
und deine Vermutung ist richtig. Da die [mm] n^2 [/mm] Elemente
unabhängig voneinander beliebig mit 1 oder 0 belegt
werden können, genügt es, die n Elemente der Dia-
gonalen zu betrachten. Und unter den Variationen
mit Wiederholung der Länge n aus [mm] \{0,1\} [/mm] gibt es wirk-
lich gleich viele mit gerader bzw. ungerader Anzahl
Einsen. Dies könnte man z.B. mit vollständiger
Induktion nach n beweisen.
Zu a) ist mir bisher auch noch nichts nützliches
eingefallen. Allerdings kann ja die Determinante
in [mm] \IF_2 [/mm] auch nur die Werte 0 oder 1 annehmen.
Die gleiche einfache "halbe-halbe-Symmetrie" gilt
aber offenbar nicht, wie man schon im Fall n=2
erkennen kann.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:54 Do 21.01.2010 | | Autor: | SEcki |
> Bei b) glaube ich, dass das die Hälfte aller Matrizen ist
> (also [mm]2^{n^{2}-1})[/mm] denn die Spur ist gerade 1, wenn die
> Anzahl der Einseinträge auf der Diagonalen ungerade ist.
> Ich hoffe, dass es genauso viele von denen gibt wie von den
> mit gerader Anzahl Einseinträge auf der Diagonalen. Doch
> wie sollte man das beweisen, wenn dem so ist?
Kann man auch anders machen - die Spur ist ein surjektiver Homomorphismus, also sind die Urbilder der Elemente alle gleichmächtig.
> Zu a): Da habe ich noch nicht wirklich einen Ansatz zu.
> Die Determinante (besonders von beliebigen nxn Matritzen
> ist zu kompliziert, als das mir da was einfallen würde...)
> Oder kann ich die Matritzen irgendwie in
> Ähnlichkeitsklassen aufteilen und mir angucken, wie viele
> von denen die Determinante 1 haben?
Hm, eine Idee, die jedenfalls funktioniert: die Matrix hat genau dann det 1, wenn die Matrix invertierbar ist. Zu den inv.baren Matirzen: der erste Vektor darf jeder außer der 0 sein, der zweite jeder, der weder 0 noch der gewählte ist, der dritte darf nicht im Spann der ersten beiden liegen - also der k-te Vektor darf nicht im Spann von den (k-1) vorherigen liegen. Also Kombinatorik benutzen + wieviel Elemente hat ein k-dim. VR über [m]\IF_2[/m].
SEcki
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:49 Sa 23.01.2010 | | Autor: | valoo |
> Hm, eine Idee, die jedenfalls funktioniert: die Matrix hat
> genau dann det 1, wenn die Matrix invertierbar ist. Zu den
> inv.baren Matirzen: der erste Vektor darf jeder außer der
> 0 sein, der zweite jeder, der weder 0 noch der gewählte
> ist, der dritte darf nicht im Spann der ersten beiden
> liegen - also der k-te Vektor darf nicht im Spann von den
> (k-1) vorherigen liegen. Also Kombinatorik benutzen +
> wieviel Elemente hat ein k-dim. VR über [m]\IF_2[/m].
Das heißt also, für den ersten Vektor habe ich [mm] 2^{n}-1 [/mm] Möglichkeiten, für den zweiten noch [mm] 2^{n}-2, [/mm] aber wie setzt sich das fort? Durch ein Beispiel bin ich bis jetzt so weit gekommen:
[mm] (2^{n}-1)*(2^{n}-2)*(2^{n}-4)*(2^{n}-8)*(2^{n}-16)*...
[/mm]
Die Formel stimmt zumindest für n=2.
Es ist doch so, dass ich für den k-ten Faktor immer die Anzahl möglicher "Ziehungen" ohne Beachtung der Reihenfolge von 1 bis k-1 Elementen aus einer Menge von k-1 Elementen zusätzlich zu k von [mm] 2^{n} [/mm] abziehe, oder? Leider war ich in Stochastik noch nie besonders gut. Wie stelle ich die Faktoren denn in Abhängigkeit von k da?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:01 Sa 23.01.2010 | | Autor: | SEcki |
> Das heißt also, für den ersten Vektor habe ich [mm]2^{n}-1[/mm]
> Möglichkeiten, für den zweiten noch [mm]2^{n}-2,[/mm] aber wie
> setzt sich das fort?
Wie du es fortgesetzt hast!
Durch ein Beispiel bin ich bis jetzt
> so weit gekommen:
> [mm](2^{n}-1)*(2^{n}-2)*(2^{n}-4)*(2^{n}-8)*(2^{n}-16)*...[/mm]
Genauso ... musst du nur beweisen!
> Es ist doch so, dass ich für den k-ten Faktor immer die
> Anzahl möglicher "Ziehungen" ohne Beachtung der
> Reihenfolge von 1 bis k-1 Elementen aus einer Menge von
> k-1 Elementen zusätzlich zu k von [mm]2^{n}[/mm] abziehe, oder?
Häh? Ich verstehe nur Bahnhof ... der (k+1)-te Vektor darf nicht im Spann der vorherigen k Vektoren sein, die nach Ind.ann. einen k-dim. VR aufspannen, und daher [m]2^k[/m] Elemente haben (warum?). Also bleiben noch [m]2^n-2^k[/m] Möglichkeiten übrig.
> Leider war ich in Stochastik noch nie besonders gut. Wie
> stelle ich die Faktoren denn in Abhängigkeit von k da?
Welche Faktoren?
SEcki
|
|
|
|
