изведением матриц А и В, обозначаемым Ах В, называется матрица, содержащая строк и KL столбцов, у которой на пересечении строки с номером (i - 1) У -f / и столбца с номером (ft - \) L + I стоит элемент

Cij. 61 = iAi-

Кронекеровское произведение представляет собой (/х/С)-таб-лицу, состоящую из (Ух£)-блоков, (i, *)-й из которых равен a,jB. Непосредственно из определения вытекает, что кронекеровское произведение матриц некоммутативно, но ассоциативно:

А X В ?t В X А, (А X В) X С = А (В X С).

Элементы матрицы АхВ те же, что и у .матрицы ВхА, но упорядочены по-другому. Очевидно также, что кронекеровское произведение дистрибутивно относительно обычного сложения матриц.

Наиболее известным примером кронекеровского произведения является внешнее произведение двух векторов. Предположим, что А и В обе представляют собой векторы-столбцы, скажем, а = (Oi, a,Y и Ь = (fci, Ьу соответственно. Тогда К = = L = 1, и ахЬ является (/х/)-матрицей, на пересечении 1-й строки и /-Г0 столбца которой стоит элемент Ujb. Оно обозначается просто через ab, так как в этом случае кронекеровское произведение совпадает с обычным произведением матриц.

Следующая полезная теорема утверждает, что кронекеровское произведение произведений матриц равно матричному произведению кронекеровских произведений соответствующих матриц.

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

(А X В) (С X D) = (АС) X (BD). Доказательство. Пусть матрицы А, В, С и D имеют соответственно размеры lxf(, JxL, КхМ и LxN. Так как матрица Ах В содержит KL столбцов, а матрица CxD содержит KL строк, то матричное произведение (АX В) (CxD) определено. Оно содержит и строк, которые мы занумеруем парами ((, j),kMN столбцов, которые мы занумеруем napakln (m, п). Элемент, стоящий на пересечении строки (i. j) и столбца (т, л), равен S аЬцСт <iin-

Так как матрица АС содержит / строк и М столбцов, а матрица BD содержит / строк и L столбцов, то матрица (АС) х (BD) также является (/Ух/С.)-матрицей. Стоящий на пересечении строки ((, /) и столбца (т, п) элемент этой матрицы равен

что и завершает доказательство. □

(лхл)-матрица, в которой ац = аг, если < - / = i называется теплицевой (пхп)-матрицей. Теплицева матрица имеет вид

~ Оо Ol а, .. Яп-

do

вдоль любой ее диагонали стоит один и тот же элемент.

Элементарными операциями над строками матрицы называются следующие действия:

1) перестановка двух произвольных строк;

2) умножение произвольной строки на ненулевой элемент поля;

3) замена произвольной строки на су.чму ее самой и некоторого кратного любой другой\троки.

Каждая элементарная операция над строками (лхт)-ма-трицы А может быть выполнена путем левого умножения А на соответствующим образом подобранную так называемую элементарную (лх п)-матрицу Е, Элементарные матрицы определяются как следующие модификации единичной матрицы:

Каждая элементарная операция над строками обратима, и обратная операция имеет такой же вид.

Элементарные операции над строками используются для приведения матрицы к стандартному виду, называемому каноническим ступенчатым видом и определяемому следующим образом:

1) ведущий ненулевой элемент каждой ненулевой строки равен единице;

2) все остальные элементы каждого столбца, содержащего такой ведущий элемент, равны нулю;

3) ведущий элемент любой строки находится правее любого ведущего элемента любой расположенной выше строки. Нулевые строки расположены ниже всех ненулевых строк.

Примером матрицы, приведенной к каноническому ступенчатому виду, является

[110 13 0 00 1100 00000 1

[о о о о о о

Заметим, что нулевая строка расположена снизу и что если удалить последнюю строку, то все столбцы единичной (Зх 3)-матрицы появятся среди столбцов матрицы, но в разбросанном виде. В общем случае если имеется k ненулевых строк и по меньщей мере такое же количество столбцов, то матрица в каноническом ступенчатом виде будет содержать все столбцы единичной (АхА)-ма-трицы, но в разбросанном виде.

Строки (лХт)-матрицы А над полем F являются подмножеством векторов пространства F, т. е. векторами с тп компонентами. Пространством строк матрицы А называется множество всех линейных комбинаций строк матрицы А. Пространство строк образует подпространство в F . Размерность пространства строк называется рангом матрицы по строкам. Аналогично, столбцы матрицы А можно рассматривать как множество векторов в пространстве F векторов с п компонентами. Пpocmpaticmeo столбцов матрицы А определяется как множество всех линейных комбинаций столбцов матрицы А, и размерность этого пространства называется рангом матрицы по столбцам. Множество векторов v, таких что Av = О, называется нулевым пространством матрицы А. Нулевое пространство, очевидно, является векторным подпространством пространства F . В частности, нулевое пространство матрицы А является ортогональным дополнением пространства строк матрицы А, так как нулевое пространство может быть описано как множество всех векторов, ортогональных ко всем векторам пространства строк матрицы.

Теорема 2.5.6. Если две матрицы А и А переводятся друг в друга некоторой последовательностью элементарных операций над строками, то они имеют одно и то же пространство строк.

Доказательство. Каждая строка матрицы А является линейной комбинацией строк матрицы А; следовательно, любая линейная комбинация строк матрицы А также является линейной комбинацией строк матрицы А, и тем самым пространство строк матрицы А содержит пространство строк матрицы А. Но А может быть получена из А с помощью обратных операций, и, следовательно, пространство строк матрицы А содержит пространство строк матрицы А. Следовательно, пространства строк матриц А и А равны. □

Теорема 2.5.7, Если матрицы А и А связаны последовательностью элементарных операций над строками, то любое множество линейно независимых столбцов матрицы А является также линейно независимым в А.

Доказательство. Теорема очевидна ля первой и второй элементарных операций, так что достаточно провести доказательство для единственной третьей операции. Итак, пусть А получается из А прибавлением строки а, умноженной на элемент поля к строке р. Если в А имеется некоторая линейная зависимость столбцов, то она приводит к нулевой линейной комбинации соответствующих элементов строки а, которая поэтому jiHKaK не сказывается на строке р. Следовательно, это множество столбцов в А также линейно зависимо. D

Теорема 2.5.8. Если к строк {кхп)-матрицы А линейно независимы, то эта матрица содержит к линейно независимых столбцов.

Доказательство. Приведе матрицу А к каноническому ступенчатому виду А. Так как строки линейно независимы, то ни одна строка не будет нулевой. Следовательно, для каждой строки найдется столбец, который в пересечении с этой строкой содержит единицу, а во всех остальных позициях - нуль. Это множество из к столбцов матрицы А линейно независимо, и, следовательно, по теореме 2.5.7 в матрице А это же множество столбцов также линейно независимо. □

Теорема 2.5.9. Ранг матрицы по строкам равен ее рангу по столбцам и оба равны размерам любой наибольшей квадратной подматрицы, определитель которой отличен от нуля. (Эта величина называется просто рангом матрицы.)

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

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

С другой стороны, выберем произвольное множество из k линейно независимых строк. Согласно теореме 2.5.7, образованная этими строками матрица содержит k линейно независимых столбцов. Выбирая эти k столбцов на рассматриваемых k строках, получаем подматрицу с ненулевым определителем. Следовательно, размер наибольшей квадратной невырожденной подматрицы по меньшей мере столь же велик, сколь ранг матрицы А по строкам. Это завершает доказательство. □

2.6. Кольцо целых чисел

Целые числа (положительные, отрицательные и нуль) образуют обманчиво простое математическое множество. Ничего, кажется, не может быть более регулярного и равномерного, чем целые числа, но присмотревшись пристальнее, можно увидеть сложные внутренние связи и модели этого множества. Разумный конструктор использует эти свойства множества целых чисел при построении эффективных алгоритмов цифровой обработки сигналов.

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

Говорят, что целое число s делится на целое число г, или что г делит S, или что г является делителем s, если s = га для некоторого целого числа а. Этот факт записывается символом г s, который читается г делит s . Если г и делит s, и делится на S, то л = ±s. Действительно, л = sa и s = гЬ для некоторых целых чисел аиЬ. Следовательно, г = rab п ab должно равняться 1. Так как а к b оба целые, то они равны 1 или -I.

Положительное целое число р > \, которое делится только на ±р или ±1, называется простым. Наименьшими простыми числами являются 2, 3, 5, 7, 11, 13, число 1 не является простым. Не являющееся простым положительное целое число называется составным. Наибо.ьший общий делитель двух целых чисел г и s обозначается НОД 1г, sl и определяется как наибольшее положительное число, которое делит оба из них. Наименьшее общее кратное двух положительных чисел г и s обозначается НОК [г, sl и определяется как наименьшее положительное число, которое делится на оба из них. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1.

В кольце целых чисел всегда возможно сокращение; если са ~ сЬ н с отлично от нуля, то а = Ь. В кольце целых чисел имеется также слабая форма деления, известная под названием деления с остатком или алгоритма деления.

Теорема 2.6.1 (Алгоритм деления). Для каждого целого числа с и положительного целого числа d найдется единственная пара целых чисел Q (частное) и s (остаток), таких что с = dO + s, гйе О < s < d.

Частное иногда обозначается

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

S = с (mod d).

Выражение этого вида называется сравнением и читается так; S сравнимо с с по модулю d. В сравнении ни s, ни с не должны быть обязательно меньше d. Мы больше интересуемся остатком. Остаток записывается в виде равенства

которое читается так: s равно остатку от деления с на d, или s равно вычету с по модулю d. Мы будем также пользоваться скобками ((c)) для обозначения этих же величин; в этом случае d ясно из контекста. Еще одним обозначением является

S = с (mod d),

в котором вместо знака сравнения стоит знак равенства. Теперь это не сравнение, а остаток от деления с на d.

Вычисление остатка от сложного выражения облегчается следующей теоремой, которая утверждает, что можно менять последовательность выполнения операции вычисления остатка со сложением и умножением.

Теорема 2.6.2. Для фиксированного модуля d

(1) la + b] = R, [R [a] -f [b]],

(ii) [a-b\ = R,\RAa]-RAb\].

Доказательство предоставляется читателю в качестве упражнения.

Наибольший общий делитель двух заданных положительных чисел S и t может быть вычислен с помощью итеративного применения алгоритма деления. Эта процедура известна как алгоритм Евклида. Предположим, что ( < s; алгоритм Евклида сводится к последовательности шагов