О билинейной сложности умножения матриц размеров $m\times 2$ и $2\times 2$

В данной работе исследуется сложность умножения матриц. Ф. Штрассен в 1969 году [1] построил алгоритм для умножения двух матриц порядка $n$ с числом арифметических операций $O\left( n^{\log_27}\right)$, что асимптотически лучше, чем сложность порядка $n^3$ стандартного алгоритма умножения матриц «строка на столбец». В последующие годы проводились активные исследования минимальной сложности различных алгебраических операций. Результаты исследований в этой области хорошо отражены в книге [2].
Ситуация в задаче об умножении матриц оказалась достаточно тяжелой. К концу 1980-х годов усилиями многих математиков сложность умножения матриц удалось понизить до $O\left( n^{2.38}\right)$ [3], но с тех пор существенных продвижений в этой задаче нет.
Для того, чтобы лучше понять проблемы, возникающие при поиске быстрых алгоритмов умножения матриц, эта задача исследуется в разных направлениях. Одним из таких направлений является исследование минимальной сложности умножения матриц малых размеров. Эти исследования имеют самостоятельный интерес, а также связаны с тем, что быстрые алгоритмы для умножения матриц малых размеров могут рекурсивно использоваться для умножения матриц больших размеров. В частности, алгоритм Штрассена основан на рекурсивном использовании найденного им алгоритма умножения двух матриц порядка 2 с 7 умножениями, а не с 8, как в стандартном алгоритме.
Можно обратить внимание на 2 особенности алгоритма Штрассена.
Во-первых, на асимптотическую оценку сложности алгоритма умножения больших матриц, построенного рекурсивно, влияет только число умножений в алгоритме умножения маленьких матриц, используемых для рекурсии.
Во-вторых, при рекурсии элементы маленьких матриц сами являются матрицами и поэтому могут не коммутировать между собой. Эти 2 особенности породили исследования билинейной сложности умножения матриц и умножения в других алгебрах. В билинейных алгоритмах сначала должны вычисляться несколько произведений линейных комбинаций элементов первого сомножителя на линейные комбинации элементов второго сомножителя. А затем из этих произведений линейными комбинациями должны получаться все требуемые выражения. При этом число произведений называют билинейной сложностью билинейного алгоритма, а минимум билинейной сложности по всем билинейным алгоритмам, решающим данную задачу, называют билинейной сложностью задачи.
Установить точное значение билинейной сложности редко удается даже в задачах перемножения двух матриц малого размера. Например, для задачи перемножения двух матриц размера $3\times 3$ к настоящему моменту известно только, что билинейная сложность заключена между 19 и 23 [4, 5]. Несложно установить точное значение билинейной сложности умножения двух матриц, если хотя бы в одной из них всего одна строка или один столбец.
В данной работе исследуется билинейная сложность умножения матрицы размера $m\times 2$ на матрицу размера $2\times 2$ над произвольным полем. Точное значение билинейной сложности для умножения таких матриц над произвольным полем известно только при $m=2,3,4$ [6, 7, 8]. Из результата Штрассена можно несложно получить, что билинейная сложность этой задачи не превосходит $\lceil\frac{7m}{2}\rceil$ для произвольного поля. В работе [9] была получена такая же нижняя оценка, но только для поля из 2 элементов. Для произвольных полей в работе [5] для этой задачи получена нижняя оценка $3m+1$. В данной статье доказано, что билинейная сложность умножения матрицы размера $m\times 2$ на матрицу размера $2\times 2$ над произвольным полем при $m\geq 3$ не может быть меньше чем $3m+2$.
Библиография: 15 названий.