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

Объединим теоремы 12.1 и 12.2, чтобы доказать более сильный результат, чем тот, который получается, если рассматривать независимость строк и столбцов отдельно. Пусть будет -матрицей с элементами из как и раньше, и

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

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

где это -матрица с элементами из вектор, компоненты которого представляют собой линейные комбинации из

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

Поскольку можно разбить на две матрицы где состоит из первых столбцов матрицы из ее последних столбцов. Далее, пусть векторы, составленные из первых и последних элементов вектора

соответственно. Тогда можно записать (12.7) в виде

Так как имеет размер то найдется такой вектор из что Умножим (12.8) на

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

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

Применим теорему 12.3 к умножению двух комплексных чисел чтобы показать, что оно требует трех умножений вещественных чисел. Заметим, что каждая из теорем 12.1 и 12.2 в отдельности не достаточно сильна для этого.

Пример 12.10. Рассмотрим задачу умножения двух комплексных чисел а именно вычисления

Пусть сама матрица поле вещественных чисел и

— векторы из Допустим, что

— элемент поля Это произведение равно Если оно принадлежит полю то коэффициенты при должны равняться нулю. Поэтому

и

Допустим, что Тогда из (12.11) получаем Подставив это в (12.10) и умножив на находим, что Поскольку то значит, Тогда в силу Но равенства противоречат условию

Теперь допустим, что Если то противоречие возникает сразу. Если то, поменяв ролями в рассуждении, приведенном выше, получаем, что снова противоречие.

Таким образом, теорема 12.3 применима к при так что три вещественных умножения необходимы. Программа в примере 12.3 показывает, что три умножения и достаточны.

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

С учетом этих изменений каждую из теорем можно перенести на случай обеих мультипликативных операций вместо одного умножения. В теореме 12.2 определение активной мультипликативной операции или должно быть следующим: или значение одной из переменных включает в себя одну из формальных переменных а другой операнд не принадлежит или принадлежит включает в себя одну из формальных переменных и операцией является деление.