Jak udowodnić, że mnożenia macierzy dwóch macierzy 2x2 nie można wykonać w mniej niż 7 multiplikacjach?

W mnożeniu macierzy Strassena stwierdzamy jeden dziwny (przynajmniej dla mnie) fakt, że mnożenie macierzy dwóch 2 x 2 wymaga mnożenia 7.

Pytanie: Jak udowodnić, że niemożliwe jest pomnożenie dwóch macierzy 2 x 2 w 6 pomnożeniach?

Należy pamiętać, że macierze są ponad liczbami całkowitymi.

Jest to klasyczny wynik Winogradu: Mnożenie macierzy 2x2 .

Strassen wykazał, że wykładnik mnożenia macierzy jest taki sam, jak wykładnik stopnia tensora tensorów mnożenia macierzy: algebraiczna złożoność mnożenia macierzy wynosi i ranga tensora (tensor mnożenia macierzy odpowiadający mnożeniu dwóch macierzy) to . Algorytm Strassena używa łatwego kierunku, aby wydedukować z górnej granicy .O ( N α ) ⟨ n , n , n ⟩ n x n O ( N α ) O ( n log 2 7 ) R ( ⟨ 2 , 2 , 2 ⟩ ) ≤ $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$

Wynik Winograda sugeruje, że . Landsberg wykazał, że granica rangi wynosi również 7, a Bläser i in. Niedawno rozszerzyłem to w celu wspierania rangi i rangi wsparcia granic. Ranga granicy i ranga wsparcia to słabsze (= mniejsze) pojęcia rangi, które zostały użyte (w przypadku rangi granicznej) lub zaproponowane (w przypadku rangi wsparcia) w algorytmach szybkiego mnożenia macierzy.⟨ 2 , 2 , 2 $R(\langle 2,2,2 \rangle)=7$$\langle 2,2,2 \rangle$

Możesz znaleźć wynik na:

S.Winograd, O mnożeniu macierzy 2 × 2 , Algebra liniowa i Appl. 4 (1971), 381–388, MR0297115 (45: 6173).