invertierbare Matrizen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 11:37 Di 31.08.2004 | | Autor: | thongsong |
Hallo!
Wie lässt sich eigentlich die Menge aller invertierbaren n*n Matrizen (binäre) berechnen. Nehmen wir als Beispiel die 2*2 Matrix. Aufzählen kann man das ja, aber gibt es denn dafür keine Formel?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:41 Di 31.08.2004 | | Autor: | Marc |
Hallo thongsong!
> Wie lässt sich eigentlich die Menge aller invertierbaren
> n*n Matrizen (binäre) berechnen. Nehmen wir als Beispiel
> die 2*2 Matrix. Aufzählen kann man das ja, aber gibt es
> denn dafür keine Formel?
Meinst du hier Matrizen, die nur 0 und 1 als Einträge haben, also Matrizen aus [mm] $\IZ_2^{n\times n}$?
[/mm]
In diesem Fall müßte die Anzahl der invertierbaren Matrizen gerade mit der Anzahl der geordneten Basen in [mm] $\IZ_2^n$ [/mm] identisch sein, weil man dann die Basisvektoren als Spaltenvektoren der Matrix nehmen kann und auf jeden Fall eine invertierbare Matrix entsteht. Umgekehrt bilden auch die Spaltenvektoren einer invertierbaren Matrix eine Basis.
(Die entscheidenden Begründungen dafür kann du ja bitte nachliefern  )
Die Anzahl der ungeordneten Basen wurde hier im Forum auch schon mal berechnet. Ich verrate jetzt erst mal nicht mehr, vielleicht findest du ja noch alleine auf den rechten Weg...
Allerdings kenne ich die genaue Formel auch noch nicht.
Viele Grüße,
Marc
|
|
|
| |
|
Genau die binären Matrizen meine ich, aber ich weiß die Formel immer noch nicht. Na ja, wahrscheinlich gibt es sie ja auch nicht...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:53 Di 31.08.2004 | | Autor: | Stefan |
Hallo thongsong!
Doch, man eine Formel recht leicht herleiten:
Wir wollen also die invertierbaren Matrizen in [mm] $\mbox{Mat}(n,n,\IZ_2)$ [/mm] bestimmen. Da eine $n [mm] \times [/mm] n$-Matrix über einem Körper $K$ genau dann invertierbar ist, wenn die Spalten eine Basis des [mm] $K^n$ [/mm] bilden, müssen wir die Anzahl der geordneten Basen in [mm] $\IZ_2^n$ [/mm] ermitteln.
Für das erste Basiselement gibt es offenbar [mm] $2^n [/mm] - [mm] 2^0$ [/mm] Möglichkeiten (alle Elemente des [mm] $\IZ_2$-Vektorraums $\IZ_2^n$ [/mm] ohne das Nullelement). Für das zweite Basiselement gibt es [mm] $2^n [/mm] - [mm] 2^1$ [/mm] Möglichkeiten (alle Elemente des [mm] $\IZ_2$-Vektorraums $\IZ_2^n$ [/mm] ohne die Vielfachen des ersten gewählten Basisvektors). Für das dritte Basiselement gibt es [mm] $2^n [/mm] - [mm] 2^2$ [/mm] Möglichkeiten (alle Elemente des [mm] $\IZ_2$-Vektorraums $\IZ_2^n$ [/mm] ohne die Linearkombinationen des ersten und zweiten gewählten Basisvektors). Für das vierte Basiselement gibt es [mm] $2^n [/mm] - [mm] 2^3$ [/mm] Möglichkeiten (alle Elemente des [mm] $\IZ_2$-Vektorraums $\IZ_2^n$ [/mm] ohne die Linearkombinationen des ersten, zweiten und dritten gewählten Basisvektors). Usw.
Insgesamt gibt es also:
[mm] $\prod\limits_{i=0}^{n-1} (2^n-2^i)$
[/mm]
invertierbare Matrizen in [mm] $\mbox{Mat}(n,n,\IZ_2)$.
[/mm]
Probe:
Für $n=2$ müssten das dann [mm] $3\cdot [/mm] 2=6$ invertierbare Matrizen sein.
Und, klar, das stimmt auch:
[mm] $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$.
[/mm]
Ich habe die Matrizen extra in der "richtigen" Reihenfolge hingeschrieben, sprich so, dass man die obige Überlegung sehr gut nachvollziehen kann, wie ich hoffe. 
Melde dich einfach bei weiteren Fragen wieder.
Übungsaufgabe für dich: Versuche die Formel für beliebige Primkörper zu verallgemeinern...
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:11 Di 31.08.2004 | | Autor: | thongsong |
Vielen Dank Stefan und natürlich auch Marc!
|
|
|
|
