Как доказать, что матричное умножение двух матриц 2x2 не может быть выполнено менее чем за 7 умножений?

В матричном умножении Штрассена мы констатируем один странный (по крайней мере для меня) факт, что умножение матрицы на два 2 x 2 требует 7 умножения.

Вопрос: Как доказать, что невозможно умножить две матрицы 2 x 2 на 6 умножений?

Обратите внимание, что матрицы над целыми числами.

Это классический результат Винограда: О умножении матриц 2х2 .

Штрассен показал, что показатель степени умножения матриц совпадает с показателем степени тензора ранг тензоров умножения матриц: алгебраическая сложность умножения матриц равна тогда и только тогда, когда ранг тензоров равен (тензор умножения матриц, соответствующий умножению двух матриц) - это . Алгоритм Штрассена использует простое направление, чтобы вывести из верхней границы .О ( п α ) ⟨ п , п , п ⟩ п × п O ( п α ) О ( п войти 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$

Из результата Винограда следует, что . Ландсберг показал, что граничный ранг также равен 7, и Bläser et al. недавно расширил это, чтобы поддержать ранг и границу поддержки ранга. Пограничный ранг и поддержка ранг является более слабым (= меньшим) понятием ранга , которые были использованы (в случае пограничного ранга) или предлагаемый (в случае поддержки ранга) в алгоритмах умножения быстрых матриц.⟨ 2 , 2 , 2 $R(\langle 2,2,2 \rangle)=7$$\langle 2,2,2 \rangle$

Вы можете найти результат по адресу:

С. Виноград, О умножении матриц 2 × 2 , Линейная алгебра и Appl. 4 (1971), 381–388, MR0297115 (45: 6173).