Determinante berechnen in gleicher Zeit wie Matrixmultiplikation

06/01/2008 - 18:27 von Philipp Zumstein | Report spam
Strassen hat als erster gezeigt, dass man zwei nxn Matrixen
zusammenmultiplizieren kann, wobei man weniger als n^3 viele
Multiplikationen braucht. Momentan der beste Algorithmus benötigt
O(n^2.376) viele Multiplikationen.

"Es ist bekannt, dass man die Determinante (und auch Inverse) einer
quadratischen Matrix in gleicher Zeit wie Matrixmultiplikation berechnen
kann." Wieso gilt das? Ich habe den Satz schon ein paar mal gelesen und
glaube ihn natürlich, aber wie kann man dies beweisen?

Vielen Dank für jegliche Hinweise.
Grüsse,
Philipp
 

Lesen sie die antworten

#1 Christian Kortes
06/01/2008 - 18:55 | Warnen spam
Philipp Zumstein wrote:
Strassen hat als erster gezeigt, dass man zwei nxn Matrixen
zusammenmultiplizieren kann, wobei man weniger als n^3 viele
Multiplikationen braucht. Momentan der beste Algorithmus benötigt
O(n^2.376) viele Multiplikationen.

"Es ist bekannt, dass man die Determinante (und auch Inverse) einer
quadratischen Matrix in gleicher Zeit wie Matrixmultiplikation berechnen
kann." Wieso gilt das?



Also in O(n^3) geht's mit Gauß-Elimination.

Ähnliche fragen