anzahl der nicht-invertierbaren matrizen

27.12.2005, 17:52

penizillin

anzahl der nicht-invertierbaren matrizen

hallo.

sitze gerade an folgendem:

K sei ein körper mit 5 elementen

wie finde ich heraus, wieviele nicht-invertierbare matrizen es in $\begin{eqnarray*} K^(2x2) \end{eqnarray*}$ gibt, ohne dabei auf die determinante zurückzugreifen?

mir fehlt der ansatz - geht es um irgendeine bestimmte art linearer abbildungen?

würd mich über einen denkanstoß freuen.

gruß

p.

27.12.2005, 17:59

JochenX

Auf diesen Beitrag antworten »

gibt ja nur 5^4 matrizen, kannst ja alle einzeln betrachten *duck*

was spricht eigentlich gegen determinanten?
es gilt doch: sei R Ring, A nxn-matrix über R
A invertierbar <=> det(A) invertierbar (z.b. in Z: matrizen mit det 1 oder -1 invertierbar)

da du hier einen körper hast (alle elemente <>0 invertierbar), gilt auch hier: A invertbar <=> det(A)<>0

lässt sich da nix machen!?

27.12.2005, 18:03

20_Cent

Auf diesen Beitrag antworten »

aber es gibt auch sehr viele möglichkeiten für die determinante, mit probieren dauerts ne weile... geht das irgendwie schneller?
(wir hatten letztens die gleiche aufgabe mit dem Körper mit 2 elementen, da ging probieren so grade noch...)
mfG 20

27.12.2005, 18:07

penizillin

Auf diesen Beitrag antworten »

du kennst doch sicherlich das dilemma - nur das benutzen, was man bis jetzt durchgenommen hat... :-/

ansonsten hab ich mir auch schon überlegt: $\begin{eqnarray*} det(A) \neq 0 \end{eqnarray*}$
$\begin{eqnarray*} <=> ad-bc \neq 0 \end{eqnarray*}$
$\begin{eqnarray*} <=> ad \neq bc \end{eqnarray*}$

da es insgesamt 625 matrizen gibt, ziehe ich die ab, bei denen ad = bc gilt. das müssten meiner überlegung nach $\begin{eqnarray*} 5^2 = 25 \end{eqnarray*}$ sein. aber stimmte denn das überhaupt? gegenbeispielähnliches argument:

$\begin{eqnarray*} 2*3 - 1*6 = 0 \end{eqnarray*}$
aber
$\begin{eqnarray*} 2 \neq 1, 2 \neq 6, etc... \end{eqnarray*}$

27.12.2005, 18:30

JochenX

Auf diesen Beitrag antworten »

Zitat:

Original von penizillin
$\begin{eqnarray*} 2*3 - 1*6 = 0 \end{eqnarray*}$

was ist denn 6!?
körperlemente ={0,1,2,3,4} oder nicht!?

hier könnte ich mir das ganze wirklich kombinatorisch "abgezählt" vorstellen
belege a und d (25 kombis, die du nicht alle betrachten brauchst, wegen symmetrie) und schaue, wieviele b,c es je gibt
sollten mehr als 25 sein

27.12.2005, 18:40

20_Cent

Auf diesen Beitrag antworten »

Zitat:

Original von penizillin
du kennst doch sicherlich das dilemma - nur das benutzen, was man bis jetzt durchgenommen hat... :-/

dann nenne es nicht determinante.
berechne einfach die inverse matrix allgemein. Du wirst feststellen, sie gibt es nur, wenn ad-bc ungleich 0 ist.
mfG 20

27.12.2005, 19:08

penizillin

Auf diesen Beitrag antworten »

sollte nur ein beispiel aus IR sein, mit dem ich meine eigene vermutung wiederlegen kann, dass aus

$\begin{eqnarray*} ad-bc = 0 \end{eqnarray*}$
nicht direkt
$\begin{eqnarray*} a=b, d=c \end{eqnarray*}$

gefolgert werden darf.

aber ich danke dir, ich versuchs später so, wie du es beschrieben hast.

27.12.2005, 19:25

Leopold

Auf diesen Beitrag antworten »

Folgender Vorschlag:

Eine Matrix ist genau dann nichtregulär, wenn ihre Spaltenvektoren linear abhängig sind.

Da würde ich folgende Typen nichtregulärer 2×2-Matrizen unterscheiden.

Typ I
Die Nullmatrix

Typ II
Genau ein Spaltenvektor ist der Nullvektor.

Typ III
Kein Spaltenvektor ist der Nullvektor.
In diesem Fall ist die zweite Spalte ein $\begin{eqnarray*} \lambda \end{eqnarray*}$ -faches der ersten mit $\begin{eqnarray*} \lambda \neq 0 \end{eqnarray*}$ .

Ich komme so mit einfachen kombinatorischen Überlegungen auf 145 nicht invertierbare Matrizen. (Über dem Körper mit $\begin{eqnarray*} q \end{eqnarray*}$ Elementen sind es $\begin{eqnarray*} q (q^2 + q - 1) \end{eqnarray*}$ nichtreguläre Matrizen.)

28.12.2005, 15:09

penizillin

Auf diesen Beitrag antworten »

genau mit dem gleichen gedanken bin ich heute früh aufgewacht:

$\begin{eqnarray*} A \in K^{nxn} \end{eqnarray*}$ invertierbar <=> $\begin{eqnarray*} Rang(A) = n \end{eqnarray*}$

dann zähle ich:

Typ I: eine matrix

Typ II: 48 matrizen. denn:
wenn eine spalte der nullvektor ist, hat die matrix die form $\begin{eqnarray*} \begin{pmatrix} 0 & a \\ 0 & b \end{pmatrix} \end{eqnarray*}$ . da der körper 5 elemente hat, kann ich 25 verschiedene kombinationen aus a und b für die zweite spalte basteln. minus der nullvektor (weil die null-matrix schon gezählt wurde) - macht 24. und weil ich die erste und die zweite spalte vertauschen darf - mal zwei. macht: 48. soweit korrekt?

Typ III: erste spalte kann auf 24 arten kombiniert werden (s. oben). das vielfache davon bilden, ohne einen nullvektor zu produzieren, bedeutet $\begin{eqnarray*} 24 * 4 = 96 \end{eqnarray*}$ matrizen bilden. da ich beide spalten wiederum vertauschen kann, erhalte ich $\begin{eqnarray*} 96*2 = 192 \end{eqnarray*}$ matrizen. da ich aber jeden der 24 vektoren ein mal mit dem einselement multipliziere, produziere ich matrizen von der form $\begin{eqnarray*} \begin{pmatrix} a & a \\ b & b \end{pmatrix} \end{eqnarray*}$ , für die das vertauschen der spalten keinen sinn macht, darum ziehe ich diese anzahl ab: $\begin{eqnarray*} 192-24 = 168 \end{eqnarray*}$ .

-----------------

insgesamt macht das $\begin{eqnarray*} 1+48+168 = 217 \end{eqnarray*}$ matrizen, deren spalten linear abhängig sind und somit ihr rang = 1 ist. diese sind demnach nicht invertierbar.

ist das soweit sinnig, oder habe ich mich beim zählen vertan? habe schließlich viel mehr als Leopold rausbekommen.

28.12.2005, 18:08

Leopold

Auf diesen Beitrag antworten »

Die Berechnung beim Typ III ist nicht ganz richtig. Durch die Wahl des ersten vom Nullvektor verschiedenen Vektors und anschließendes Durchgehen der Möglichkeiten für den zweiten Vektor hast du bereits alle Möglichkeiten erfaßt. Da ist nichts mehr mit 2 zu multiplizieren oder Ähnliches.

Nach deiner Zählmethode würde z.B. die Matrix

$\begin{eqnarray*} \begin{pmatrix} 1 & 2 \\ 3 & 1 \end{pmatrix} \end{eqnarray*}$

zweimal gezählt:

- einmal, wenn $\begin{eqnarray*} \begin{pmatrix} 1 \\ 3 \end{pmatrix} \end{eqnarray*}$ als erster Vektor und der Faktor $\begin{eqnarray*} \lambda = 2 \end{eqnarray*}$ gewählt wird

- und einmal, wenn $\begin{eqnarray*} \begin{pmatrix} 2 \\ 1 \end{pmatrix} \end{eqnarray*}$ als zweiter Vektor und der Faktor $\begin{eqnarray*} \lambda = 3 \end{eqnarray*}$ gewählt wird

29.12.2005, 03:25

Ace Piet

Auf diesen Beitrag antworten »

Die 145 von Leopold möchte ich mit ff. Abzählmethode bestätigen:

Ich typisiere über die Anzahl Nullen der Matrix. - Eingängig ist, wenn man die Matrixtypen kurz hinschreibt und die Ergebnisse in einer Tabelle (inv.bar/ nicht inv.bar) zusammenträgt...

4 Nullen:
---------
1x (nicht inv.bar)

3 Nullen:
---------
Also 1 Eintrag != 0, der an 4 Stellen stehen darf, ergibt 4 x 4 = 16 sämtlich nicht inv.bare Matrizen.

2 Nullen:
---------
Genau 2 Nullen spendiere ich der Matrix auf 6 Weisen.

A) Die nicht inv.baren sind genau die, wo einer der 4 Ränder ein Nullvektor ist. => 4 Ränder x 4 x 4 Nichtnullen => 64 nicht inv.bare

B) Die inv.baren haben eine Null-(Neben-)Diagonale. - 2 Diag. x 4 x 4 Nichtnullen => 32 inv.bare

1 Null
------
Die Null steht an 4 möglichen Stellen und ergibt sämtlich inv.bare (Dreiecks-) Matrizen für den Rest von 4x 4x 4 Nichtnullen. => 256 inv.bare Matrizen.

Kontrolle: Bislang haben wir 369 erfasst und es gibt 4x 4x 4x 4=256 Matrizen, die keine Null enthalten, in Summe 625 *hurra*.

0 Nullen
--------
A) Es gibt 4x 4 "erste Spalten", die keine Null enthalten. Die kann ich je 4x linear (!=) kombinieren. => 64 nicht inv.bare.

B) War nicht gefragt: 192 (unbewiesene) inv.bare.

Unterm Strich... 1 + 16 + 64 + 0 + 64 = 145 NICHT inv.bare Matrizen.

29.12.2005, 11:21

Leopold

Auf diesen Beitrag antworten »

Einfacher ist es vielleicht, die regulären Matrizen zu zählen, am besten gleich die $\begin{eqnarray*} n \end{eqnarray*}$ -reihigen über dem Körper $\begin{eqnarray*} K \end{eqnarray*}$ mit $\begin{eqnarray*} q \end{eqnarray*}$ Elementen. Anders gesagt geht es darum, sämtliche geordneten Basen des Vektorraums $\begin{eqnarray*} K^n \end{eqnarray*}$ zu bestimmen. Und Basen kann man sich schrittweise erzeugt denken.

erster Basisvektor:
jeder Vektor außer dem Nullvektor
$\begin{eqnarray*} q^n - 1 \end{eqnarray*}$ Möglichkeiten

zweiter Basisvektor:
jeder Vektor außer den Vielfachen des ersten Basisvektors
$\begin{eqnarray*} q^n - q \end{eqnarray*}$ Möglichkeiten

dritter Basisvektor:
jeder Vektor außer den Linearkombinationen der ersten beiden Basisvektoren
$\begin{eqnarray*} q^n - q^2 \end{eqnarray*}$ Möglichkeiten

usw.

$\begin{eqnarray*} n \end{eqnarray*}$ -ter Basisvektor:
jeder Vektor außer den Linearkombinationen der ersten $\begin{eqnarray*} n-1 \end{eqnarray*}$ Basisvektoren
$\begin{eqnarray*} q^n - q^{n-1} \end{eqnarray*}$ Möglichkeiten

Das sind insgesamt

$\begin{eqnarray*} \prod_{k=0}^{n-1}~\left( q^n - q^k \right) \ = \ q^{\frac{n(n-1)}{2}} \prod_{k=1}^{n}~\left( q^k - 1 \right) \ = \ q^{\frac{n(n-1)}{2}} (q-1)^n \prod_{k=1}^{n-1}~\left( 1 + q + q^2 + \ldots + q^k \right) \end{eqnarray*}$

Möglichkeiten. Und das ist somit die Gruppenordnung von $\begin{eqnarray*} \operatorname{GL}(n,K) \end{eqnarray*}$ .

Bei uns ist $\begin{eqnarray*} q = 5 \end{eqnarray*}$ und $\begin{eqnarray*} n = 2 \end{eqnarray*}$ . Die Formel liefert als Gruppenordnung $\begin{eqnarray*} 5 \cdot 4^2 \cdot 6 = 480 \end{eqnarray*}$ . Damit sind $\begin{eqnarray*} 5^4 - 480 = 145 \end{eqnarray*}$ Matrizen nicht regulär.

Und hoffentlich stimmt das alles, was ich da erzählt habe ...

29.12.2005, 16:42

Ace Piet

Auf diesen Beitrag antworten »

> Und hoffentlich stimmt das alles, was ich da erzählt habe ...

Sicherlich. Und mit der gegebenen Erklärung wird es auch verständlich (siehe auch):
http://de.wikipedia.org/wiki/Allgemeine_lineare_Gruppe -> Über endlichen Körpern

29.12.2005, 17:25

Leopold

Auf diesen Beitrag antworten »

Na, dann paßt ja alles.

29.12.2005, 19:43

penizillin

Auf diesen Beitrag antworten »

unglaublich, wieviele ansätze man findet... ich danke euch vielmals für eure zeit und mühe - das klingt alles verständlich und überzeugend. ich habe von euch viel neues gelernt. danke!

Neue Frage »

Antworten »

anzahl der nicht-invertierbaren matrizen

Verwandte Themen