Diskussion:Algorithmus von Faddejew-Leverrier

Komplexität des Algorithmus?

Welche Komplexität hat der Algorithmus? --Enantiodromie 21:14, 28. Jun. 2009 (CEST)

Der Algorithmus hat eine Komplexität von ${\mathcal {O}}(n^{4})$. Ich habe dies sowie einen Vergleich mit anderen Methoden im Artikel noch ergänzt -- Hightower74 14:15, 2. Aug. 2009 (CEST)

Danke so habe ich mir das vorgestellt. -- Enantiodromie 21:58, 5. Aug. 2009 (CEST)

Grundlagen

Die Grundlagen sind meiner Meinung nach zu kurz. Wenn ich von den Grundkenntnissen einer Lineare-Algebra-Vorlesung (Eigenwerte, charakteristisches Polynom, geometrische Vielfachheit, Cayley-Hamilton) ausgehe, stellen sich mir folgende Fragen: Was ist die grundsätzliche Intuition hinter dem Algorithmus? In welchen Fällen findet er Anwendung, wann kommen andere Verfahren zum Zuge, welche Vor- und Nachteile bringt er mit sich? Dazu wäre es eben auch gut, nicht direkt in die Diskussion des Algorithmus' hineinzustürzen, sondern die allgemeine Problemstellung nochmal zu vertiefen. Den Verweis auf einen ausführlicheren Beweis/Herleitung hätte ich im Grundlagen-Teil erwartet. --W.pseudon (Diskussion) 10:08, 13. Apr. 2020 (CEST)

Hallo W.pseudon

Vielen Dank für Dein Feedback, das ich leider erst verspätet gesehen habe (mein Mail-Account war längere Zeit inaktiv).

Jetzt habe ich endlich mal Zeit gefunden, die von Dir gewünschte Motivation noch einzubauen. Vor- und Nachteile bzw. Anwendungsbereiche finden sich ebenfalls im Artikel wieder. --Hightower74 (Diskussion) 23:25, 17. Feb. 2022 (CET)

Ist der Algorithmus von Faddejew-Leverrier auch für quadratische Binärmatritzen anwendbar?

In der englischen Version dieses Artikels gibt es keine Einschränkungen zur Klasse, aus der die Matrixelemente der quadratischen Matrix A sein sollen. In der deutschen Version dieses Artikels wird zwar das Symbol "C" verwendet, welches üblicherweise für die komplexen Zahlen steht, es wird aber nirgens wörtlich erwähnt, dass es komplexe Matrixelemente sein müssen. Wenn es aber keine Einschränkungen für den Körper gibt, aus dem die Elemente der quadratischen Matrix stammen sollen, was ich annehme, könnte man da stattdessen ein "K" für den Matrixelementkörper verwenden, um Irritationen mit dem komplexen Zahlenkörper "C" zu vermeiden?

Da der Trace(Binärmatrix M) als Ergebnis wieder ein Resultat aus {0,1} liefern muss, gehe ich mal davon aus, dass der Trace(Binärmatrix M) gleich der Anzahl der Einsen auf der Hauptdiagonale von der Binärmatrix M modulo 2 ist.

Wie aber habe ich den Ausdruck (1/k) für die Berechnung der Koeffizienten c[n-k] zu interpretieren, wenn ich mit Binärmatritzen arbeite und jeder der zu berechnenden Koeffizienten c[n-k] wieder aus {0,1} stammen soll? Ignoriere ich diesen Ausdruck komplett, erhalte ich zwar irgendwelche Koeffizienten c[n-k] aus {0,1} aber letztendlich nicht das gewünschte charakteristische Polynom der Binärmatrix A, weil weder der Koeffizient c[0] immer der Determinante von A entspricht, noch der Koeffizient c[n-1] immer die Spur von A ergibt.

--Aragorn321 (Diskussion) 18:36, 4. Mai 2020 (CEST)

Hallo Aragom321

Ich habe jetzt nach längere Zeit endlich Gelegenheit gefunden, den Artikel zu überarbeiten.

Insbesondere bin ich dabei auch auf Deine Frage eingegangen, die in der Präambel sowie auch in einem eigenen Abschnitt erschöpfend beantwortet wird. --Hightower74 (Diskussion) 23:27, 17. Feb. 2022 (CET)