Wie kann man beweisen, dass eine Matrixmultiplikation von zwei 2x2-Matrizen nicht mit weniger als 7 Multiplikationen durchgeführt werden kann?

In Strassens Matrixmultiplikation stellen wir eine merkwürdige (zumindest für mich) Tatsache fest, dass eine Matrixmultiplikation von zwei 2 × 2 eine 7-Multiplikation erfordert.

Frage: Wie kann man beweisen, dass es unmöglich ist, zwei 2 x 2-Matrizen in 6 Multiplikationen zu multiplizieren?

Bitte beachten Sie, dass Matrizen über ganzen Zahlen liegen.

Dies ist ein klassisches Ergebnis von Winograd: Bei der Multiplikation von 2x2-Matrizen .

$n\times n$$O(n^\alpha)$$\langle n,n,n \rangle$$n\times n$$O(n^\alpha)$$O(n^{\log_27})$$R(\langle 2,2,2 \rangle) \leq 7$

$R(\langle 2,2,2 \rangle)=7$$\langle 2,2,2 \rangle$

Das Ergebnis finden Sie unter:

S. Winograd, Nach Multiplikation von 2 × 2 Matrizen , Linearer Algebra und Appl. 4 (1971), 381–388, MR0297115 (45: 6173).