Determinanten

Ich lerne gerade Determinanten.

Unter anderem verwende ich folgende Website dazu:
http://de.wikipedia.org/wiki/Determinante#Eigenschaften

Erstens: Wie verwende ich die Leibniz-Formel (Beispiel bitte)

Zweitens:

Eigenschaften von Determinanten
Bei wiki steht:
***********
Es ist einfach zu sehen, dass det(rI_n)=r^n und somit
det(rA) = r^n det(A) für alle n×n Matrizen A und alle Skalare r.
***********
--> det(rI_n)=r^n <-- Wie ist das zu interpretieren? (Beispiel bitte)

Walli

Zu erstens:
Die Leibnitz-Formel ist viel zu unhandlich. In der Praxis benutzt man für Determinanten oft erstmal den Gauß (ausser für 2x2 bzw. 3x3, da gibt es Abkürzungen) und berechnet dann die Determinante der Dreiecksmatrix (sehr einfach, weil nur aufmultiplizieren der Hauptdiagonalen).

Zu zweitens:
Das bedeutet einfach nur, dass man den skalaren Faktor r vor die Matrix ziehen kann, bevor man sich ans Berechnen der Determinante begibt, wenn man ihn mit n potenziert (r² bei 2x2, r³ bei 3x3, ...).
Die Herleitung ist einfach: $I_n$ ist im Beispiel nur die Einheitsmatrix vom Grad n. Da sie bei der Matrix-Multiplikation das neutrale Element ist kann man sagen $det(r\,A) = det(r\,I\_n\,A) = det(r\,I\_n)\,det(A)=r^n\,det(A)$ .

EDIT: Herleitung

MaSTaH schrieb:

Zu erstens:
Die Leibnitz-Formel ist viel zu unhandlich. In der Praxis benutzt man für Determinanten oft erstmal den Gauß (ausser für 2x2 bzw. 3x3, da gibt es Abkürzungen) und berechnet dann die Determinante der Dreiecksmatrix (sehr einfach, weil nur aufmultiplizieren der Hauptdiagonalen).

Ein Beispiel?
Dann seh ich zumindest, dass die Formel unhandlich ist und deshalb nicht zu gebrauchen ist .

fubar

Hier wird es für n=2 und n=3 beschrieben:
http://www.mat.univie.ac.at/~kriegl/Skripten/Math4Ilak1/node13.html

Es gilt ja:

det(A)^-1 = det(A^-1)

Wer kann das beweisen mit Herleitung?
Ein Beispiel habe ich gemacht und habe dabei gesehen dass die Gleichung stimmt. Die Herleitung konnte ich jedoch nicht finden.

fubar

$1=det(I)=det(AA^{-1})=det(A)det(A^{-1})$
Hoffe, das stimmt so ...

Edit: Übrigens hättest du auch auf den Link von oben klicken können, wie ich gerade gesehen habe

fubar schrieb:

$1=det(I)=det(AA^{-1})=det(A)det(A^{-1})$
Hoffe, das stimmt so ...

Edit: Übrigens hättest du auch auf den Link von oben klicken können, wie ich gerade gesehen habe

Ja, das stimmt, sehe ich auch so. Aber das ist doch nicht etwa der Beweis für meine Aussage??!
Aussage war:
det(A^-1)=det(A)-1

Das kommt in deinen Umformungen gar nicht vor.

fubar

Ääh, ja, das stimmt natürlich, aber teile doch mal bei der Gleichung $1=det(A)det(A^{-1})$ beide Seiten durch det(A), dann steht da doch das gewünschte Ergebnis, oder bin ich mal wieder

fubar schrieb:

Ääh, ja, das stimmt natürlich, aber teile doch mal bei der Gleichung $1=det(A)det(A^{-1})$ beide Seiten durch det(A), dann steht da doch das gewünschte Ergebnis, oder bin ich mal wieder

Jetzt ist's klar .

Krugman

Ist es nicht so, dass wenn eine Spalte oder Zeile = 0 ist, dann auch keine inverse Matrix exestiert.

mata

ja, dann gilt ja auch det = 0

Zur Leibniz Formel zurück:

Mein Ziel ist es ein kleines C++ Programm zu schreiben, dass mir den Determinantenwert mit Hilfe der Leibniz Formel berechnet.

Das Verfahren:
Ich bilde alle möglichen Permutationen. Dann muss ich für jede Permutation herausfinden, ob das vorzeichen + oder - ist. Vorzeichen ist + wenn Permutation gerade ist, und - wenn Permutation ungerade ist. Am schlusse summiere ich alle Permutationen und das Resultat ist berechnet.

Wie kann ich schnell und effektiv herausfinden ob eine Permutation gerade oder ungerade ist??
Gibt es eine Funktion, die das kann? Oder muss ich selber Hand anlegen (Implementierung krieg ich hin)?

Wie bilde ich alle Permutationen der Zahlen (1,2,...,n)? Gibt es eine Funktion, die das kann? Falls nein, wie lautet der Algorithmus?

fubar

Determinanten_11 schrieb:

Mein Ziel ist es ein kleines C++ Programm zu schreiben, dass mir den Determinantenwert mit Hilfe der Leibniz Formel berechnet.

Daß du für die Berechnung der Derterminante einer Matrix mit dem Leibniz-Verfahren jeweils n! Summanden berechnen mußt und die Formel für große n damit unbrauchbar wird, hat MaSTaH ja schon erwähnt. Falls du das nur zu Lernzwecken programmieren willst, ist das bestimmt eine gute Übung, ansonsten berechne die LU-Zerlegung der Matrix, da bekommst du die Determinante quasi geschenkt ...
[Zum Vergleich: hier werden ca. 1/3n³⁺ⁿ2-1/3n "wesentliche" Rechenop. benötigt]

Determinanten_11 schrieb:

Wie kann ich schnell und effektiv herausfinden ob eine Permutation gerade oder ungerade ist??
Gibt es eine Funktion, die das kann? Oder muss ich selber Hand anlegen

Hmm, ich wüßte so keine Fkt., die das kann.

Determinanten_11 schrieb:

Wie bilde ich alle Permutationen der Zahlen (1,2,...,n)? Gibt es eine Funktion, die das kann? Falls nein, wie lautet der Algorithmus?

http://www.sgi.com/tech/stl/next_permutation.html

mata

es gilt doch:

permutation grade: gerade anzahl fehlstände (fehlstand = p(i) > p(j) und i < j)
permutation ungrade: sonst

kann man doch recht einfach umsetzen, oder?

mata schrieb:

es gilt doch:

permutation grade: gerade anzahl fehlstände (fehlstand = p(i) > p(j) und i < j)
permutation ungrade: sonst

kann man doch recht einfach umsetzen, oder?

Klar (hab ja gesagt, dass ich das kann).

Wenns bereits eine Standard Funktion für etwas gibt, dann nehme ich diese und codiere nicht selber was Neues.

Jester

Das riecht aber nach O(n^2), weil Du jedes mit jedem Vergleichen mußt. Vielleicht könnte man das auch einfach sortieren und die Anzahl der Vertauschungen zählen... das wäre dann wenigstens O(n*log(n)).

MfG Jester

mata

man kann permutationen ja auch in zykelschreibweise schreiben:

1 2 3 4
4 3 1 2

ist dann (1423) - dieses Zykel hat 4 Stellen, gerade -> signum der Permutation -1 (sonst 1). Wenn mehrere Zykel entstehen, kann man das signum multiplizieren und erhält das signum der Permutation:

1 2 3 4
2 1 4 3

ist (12)(34) => signum = -1*-1 = 1 => Permutation gerade.

sign p =  1 => permutation grade
         -1 => permutation ungrade

damit sollte man es doch mit O(n) hinkriegen, oder täusch ich mich?

mata schrieb:

man kann permutationen ja auch in zykelschreibweise schreiben:

1 2 3 4
4 3 1 2

ist dann (1423) - dieses Zykel hat 4 Stellen, gerade -> signum der Permutation -1 (sonst 1). Wenn mehrere Zykel entstehen, kann man das signum multiplizieren und erhält das signum der Permutation:

1 2 3 4
2 1 4 3

ist (12)(34) => signum = -1*-1 = 1 => Permutation gerade.
sign p =  1 => permutation grade
         -1 => permutation ungrade
damit sollte man es doch mit O(n) hinkriegen, oder täusch ich mich?

@Masta: Dein Text hört sich sehr intelligent an. Nur verstehe ich ihn nicht ganz.
Kannst du deine Idee noch weiter ausführen oder gleich ein kleines Code Sample posten?

Jester

mata: wenn Du annimmst, daß Du die Zykelschreibweise in O(n) hinkriegst kannste das machen. Die Frage ist nur, ob das geht.

Angenommen es ginge. Ich hab hier ne beliebige Permutation. Dann würde ich die einfach in Zykelschreibweise machen O(n) und die Zykel dann möglicherweise ebenfalls mit Aufwand O(n) rückwärts ausführen. Dann hätte ich mit O(n) sortiert...

Man muß also zumindest genau nachschaun, ob das so geht. Zumindest müßtest Du noch verraten wo Du die Zykelschreibweise so schnell herkriegst.

MfG Jester

Jester schrieb:

mata: wenn Du annimmst, daß Du die Zykelschreibweise in O(n) hinkriegst kannste das machen. Die Frage ist nur, ob das geht.

Angenommen es ginge. Ich hab hier ne beliebige Permutation. Dann würde ich die einfach in Zykelschreibweise machen O(n) und die Zykel dann möglicherweise ebenfalls mit Aufwand O(n) rückwärts ausführen. Dann hätte ich mit O(n) sortiert...

Man muß also zumindest genau nachschaun, ob das so geht. Zumindest müßtest Du noch verraten wo Du die Zykelschreibweise so schnell herkriegst.

MfG Jester

Ich denke am einfachsten ist es, wenn uns masta ein kleines Code Sample postet.