12.4. НИЖНЯЯ ГРАНИЦА ДЛЯ ЧИСЛА УМНОЖЕНИЙ, СВЯЗАННАЯ С РАНГОМ ПО СТРОКАМ

Определение. Пусть поле и формальные переменные. Обозначим через -мерное пространство векторов с компонентами из пусть будет -мерным пространством векторов с компонентами из Множество векторов из называется линейно независимым по модулю если для любых из соотношение влечет за собой, что все равны нулю. Если векторы не являются линейно независимыми по модулю то их называют зависимыми по модулю

Линейную независимость по модулю можно трактовать иначе, рассмотрев факторпространство классов эквивалентности векторов из (Векторы из эквивалентны тогда и только тогда, когда разность принадлежит Линейная независимость по модулю означает линейную независимость классов эквивалентности из

Пример 12.6. Пусть поле вещественных чисел, а формальные переменные. Тогда три вектора

из зависимы по модулю поскольку

принадлежит

С другой стороны, векторы

линейно независимы по модулю В самом деле, пусть

Тогда Поскольку ни а, ни не принадлежит то Кроме того, соотношение влечет за собой Следовательно, линейно независимы по модулю

Пусть обозначает -матрицу с элементами из Число линейно независимых строк в матрице равно числу ее линейно независимых столбцов. Но если элементы матрицы принадлежат то число линейно независимых строк по модулю вообще говоря, не равно числу линейно независимых столбцов в по модулю Например, в -матрице одна строка линейно независима по модулю и три столбца линейно независимы по модулю Рангом по строкам матрицы по модулю называется число строк в линейно независимых по модулю Ранг по столбцам матрицы по модулю определяется аналогично.

В оставшейся части раздела и в двух следующих мы будем употреблять такие обозначения:

2) - непересекающиеся множества формальных переменных,

3) есть -матрица с элементами из

— вектор-столбец

Теорема 12.1. Пусть — матрица с элементами из вектор-столбец Предположим, что ранг по строкам матрицы равен Тогда любое вычисление произведения требует не менее умножений.

Доказательство. Предположим, не умаляя общности, что имеет строк. (В противном случае можно вычеркнуть все строки матрицы кроме линейно независимых, и получить некоторую матрицу Любое вычисление произведения будет вычислением и для Отсюда следует, что если требует умножений, то и требует умножений.)

Допустим, что в данном вычислении произведения необходимы умножений. Пусть выражения, вычисляемые

на каждом из шагов с умножением. Тогда можно представить в виде линейной функции от и формальных переменных, т. е.

где вектор а компоненты вектора представляют собой линейные функции только от Все элементы -матрицы принадлежат полю

Теперь допустим, что Это значит, что строки матрицы линейно зависимы (элементарный факт из линейной алгебры) Таким образом, существует такой вектор из что Умножив (12.1) на получим

Из (12.2) видно, что произведение равно т. е. является линейной функцией от формальных переменных. Так как компоненты вектора различные формальные переменные, то вектор-строка должна состоять только из элементов поля а иначе в нашлось бы слагаемое, состоящее из произведения формальных переменных, и, значит, такое слагаемое было бы и в а это противоречит тому, что линейная функция от формальных переменных. Поскольку то строки матрицы зависимы по модулю вопреки условию. Поэтому и теорема доказана.

Пример 12.7. В разд. 12.2 мы рассмотрели вычисление трех выражений простым рекурсивным алгоритмом умножения целых чисел. Все три умножения можно записать в виде умножения матрицы на вектор, а именно

Пусть поле вещественных чисел. В примере 12.6 было показано, что три строки матрицы в (12.3) линейно независимы по модулю следовательно, любое вычисление этих трех выражений над вещественным полем требует трех умножений вещественных чисел.