В данной работе исследуется сложность умножения матриц. Ф. Штрассен в 1969 году [1] построил алгоритм для умножения двух матриц порядка n с числом арифметических операций O ( n log2 7 ) , что асимптотически лучше, чем сложность порядка n 3 стандартного алгоритма умножения матриц «строка на столбец». В последующие годы проводились активные исследования минимальной сложности различных алгебраических операций. Результаты исследований в этой области хорошо отражены в книге [2]. Ситуация в задаче об умножении матриц оказалась достаточно тяжелой. К концу 1980-х годов усилиями многих математиков сложность умно- жения матриц удалось понизить до O ( n 2.38) [3], но с тех пор существенных продвижений в этой задаче нет. Для того, чтобы лучше понять проблемы, возникающие при поиске быстрых алгоритмов умножения матриц, эта задача исследуется в разных направлениях. Одним из таких направлений является исследование мини- мальной сложности умножения матриц малых размеров. Эти исследова- ния имеют самостоятельный интерес, а также связаны с тем, что быстрые алгоритмы для умножения матриц малых размеров могут рекурсивно ис- пользоваться для умножения матриц больших размеров. В частности, алгоритм Штрассена основан на рекурсивном использовании найденного им алгоритма умножения двух матриц порядка 2 с 7 умножениями, а не с 8, как в стандартном алгоритме. Можно обратить внимание на 2 особенности алгоритма Штрассена. Во-первых, на асимптотическую оценку сложности алгоритма умножения больших матриц, построенного рекурсивно, влияет только число умножений в алгоритме умножения маленьких матриц, используемых для рекурсии. Во-вторых, при рекурсии элементы маленьких матриц сами являются матрицами и поэтому могут не коммутировать между собой. Эти 2 осо- бенности породили исследования билинейной сложности умножения матриц и умножения в других алгебрах. В билинейных алгоритмах сначала должны вычисляться несколько произведений линейных комбинаций эле- ментов первого сомножителя на линейные комбинации элементов второго сомножителя. А затем из этих произведений линейными комбинациями должны получаться все требуемые выражения. При этом число произведений называют билинейной сложностью билинейного алгоритма, а мини- мум билинейной сложности по всем билинейным алгоритмам, решающим данную задачу, называют билинейной сложностью задачи. Установить точное значение билинейной сложности редко удается даже в задачах перемножения двух матриц малого размера. Например, для задачи перемножения двух матриц размера 3 × 3 к настоящему момен- ту известно только, что билинейная сложность заключена между 19 и 23 [4, 5]. Несложно установить точное значение билинейной сложности умножения двух матриц, если хотя бы в одной из них всего одна строка или один столбец. В данной работе исследуется билинейная сложность умножения матрицы размера m × 2 на матрицу размера 2 × 2 над произвольным полем. Точное значение билинейной сложности для умножения таких матриц над произвольным полем известно только при m = 2, 3, 4 [6, 7, 8]. Из результа- та Штрассена можно несложно получить, что билинейная сложность этой задачи не превосходит ⌈ 7m 2 ⌉ для произвольного поля. В работе [9] была по- лучена такая же нижняя оценка, но только для поля из 2 элементов. Для произвольных полей в работе [5] для этой задачи получена нижняя оценка 3m + 1. В данной статье доказано, что билинейная сложность умножения матрицы размера m×2 на матрицу размера 2×2 над произвольным полем при m ≥ 3 не может быть меньше чем 3m + 2.
In this paper we investigate the complexity of matrix multiplication. V. Strassen in 1969 [1] constructed an algorithm to multiply two matrices of order n with the number of arithmetic operations O ( n log2 7 ) , which is asymptotically better than the complexity of the order n 3 of standard matrix multiplication algorithm “line by column”. In subsequent years, active investigations were carried on minimal complexity of various algebraic operations. The results of the researches in this field are well reflected in the book [2]. The situation in the problem of matrix multiplication is quite hard. By the end of the 1980s, with the efforts of many mathematicians complexity of matrix multiplication was reduced to O ( n 2.38) [3], but since then there is no significant progress in this problem. In order to better understand the problems associated with finding fast algorithms for matrix multiplication, this problem is investigated in different directions. One such area is the study minimal complexity of matrix multiplication for small sizes. This study is of interest in itself, but is also linked to the fact that the fast algorithms for matrix multiplication of small size can be recursively used for matrix multiplication of large size. In particular, Strassen’s algorithm uses recursively algorithm for multiplication of two matrices of order 2 with 7 multiplications rather than 8 as in standard algorithm. One can note two special properties of Strassen’s algorithm. Firstly, only the number of multiplications in the algorithm for multiplication of small matrices used for recursion affects the asymptotic complexity of algorithm for multiplication of large matrices. Secondly, matrix elements in recursion are themselves matrices and therefore they do not commute. These two properties have generated studies of bilinear complexity of multiplication of matrices and multiplication in other algebras. The bilinear algorithm must first calculate several products of linear combination of the elements of the first factor by linear combination of the elements of the second factor. Then, all the required expressions must be obtained by linear combinations of these products. The number of products is called bilinear complexity of the algorithm, and the minimum bilinear complexity of all bilinear algorithms that solve this problem is called the bilinear complexity of the problem. It is rather difficult to establish the exact value of the bilinear complexity even for multiplication of two matrices of small size. For example, for the problem of multiplying two 3×3 matrices so far we only know that the bilinear complexity lies between 19 and 23 [4, 5]. It is not difficult to establish the exact value of the bilinear complexity of multiplication of two matrices if at least one of them is only one row or one column. In this paper we investigate the bilinear complexity of multiplication of matrix of size m × 2 by matrix of size 2 × 2 over an arbitrary field. The exact value for the bilinear complexity for the multiplication of such matrices over an arbitrary field is known only when m = 2, 3, 4 [6, 7, 8]. From the result of Strassen it can be easy to get that the bilinear complexity of this problem does not exceed ⌈ 7m 2 ⌉ for an arbitrary field. The same lower bound was obtained in the paper [9], but only for the field with two elements. For arbitrary fields the lower bound 3m + 1 for this problem was obtained in [5]. In this article it is proved that for m ≥ 3 the bilinear complexity of multiplication of m × 2 matrix by 2 × 2 matrix over an arbitrary field can not be less than 3m + 2.