Главная > Помехоустойчивое кодирование > Теория и практика кодов, контролирующих ошибки
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.6. ЛИНЕЙНАЯ АЛГЕБРА

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

Определение 2.6.1. -матрицей А над кольцом называется прямоугольная таблица, состоящая из строк и столбцов и содержащая элементов из кольца

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

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

Две -матрицы над полем можно складывать по правилу

-матрицу А можно умножать на элемент поля по правилу

-матрицу А можно умножить на -матрицу В, получив результирующую -матрицу С, по правилу

Это произведение матриц обозначается через

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

где и — меньшие матрицы, размеры которых очевидным образом дополняют друг друга до размеров матрицы А. А именно сумма числа строк матрицы и числа строк матрицы равна числу строк матрицы аналогичное утверждение выполняется для столбцов. Матрицы можно перемножить поблочно, а именно если

и то при условии корректного выбора размеров блоков (корректного в том смысле, что все произведения и суммы матриц определены)

Такое разложение можно получить как простое следствие аксиом ассоциативности и дистрибутивности основного поля

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

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

где перестановка на множестве целых чисел равно ±1 в зависимости от четности или нечетности перестановки, а суммирование ведется по всем перестановкам.

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

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

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

Теорема 2.6.3.

(i) Если все элементы некоторой строки квадратной матрицы равны нулю, то определитель этой матрицы равен нулю.

(ii) Определитель матрицы равен определителю транспонированной матрицы.

(iii) Если две строки матрицы поменять местами, то ее определитель изменит знак.

(iv) Если две строки матрицы равны, то ее определитель равен нулю.

(v) Если все элементы одной строки матрицы умножить на элемент поля с, то определитель новой матрицы будет равен определителю исходной матрицы, умноженной на с.

(vi) Если матрицы отличаются только строкой, то сумма их определителей равна определителю матрицы строка которой равна сумме 1-х строк матриц а остальные строки равны соответствующим строкам матрицы А или В.

(vii) Если к элементам некоторой строки матрицы раз прибавить соответствующие элементы некоторой другой ее строки, то определитель матрицы не изменится. Доказательство: использовать свойства

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

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

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

Из способа задания определителя матрицы следует, что алгебраическое дополнение элемента является коэффициентом при в разложении определителя:

Это известная формула Лапласа для разложения определителей. дает выражение определителя -матрицы через определители -матриц. Формула разложения Лапласа лежит в основе рекуррентного способа вычисления определителей.

Если заменить на то получится сумма равная определителю новой матрицы, полученной из старой

заменой элементов строки элементами строки; этот определитель равен нулю, если Таким образом,

Поэтому если матрица имеет обратную, равную

Если то обратной матрицы не существует.

Строки -матрицы А над можно рассматривать как множество -мерных векторов над Пространство строк матрицы А определяется как множество всех линейных комбинаций векторов-строк матрицы А. Размерность пространства строк называется рангом матрицы по строкам. Аналогично столбцы матрицы А можно рассматривать как множество -мерных векторов над Пространство столбцов матрицы А определяется как множество всех линейных комбинаций векторов-столбцов матрицы А, а размерность пространства столбцов называется рангом матрицы по столбцам. Множество всех векторов V, таких, что называется нулевым пространством матрицы А. Ясно, что нулевое пространство является подпространством в В частности, нулевое пространство является ортогональным дополнением пространства строк матрицы А, так как нулевое пространство можно задать как множество всех векторов, ортогональных ко всем векторам пространства строк.

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

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

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

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

Каждая элементарная операция над строками обратима, и обратная операция имеет такой же вид. Каждая элементарная операция над строками -матрицы А может быть выполнена путем левого умножения А на соответствующим образом подобранную так называемую элементарную -матрицу

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

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

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

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

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

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

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

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

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

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

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

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

Теорема 2.6.6. -матрица строк которой линейно независимы, содержит линейно независимых столбцов.

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

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

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

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

Подматрица матрицы А получается выбрасыванием из А некоторого числа строк и столбцов. Пусть невырожденная квадратная подматрица матрицы А наибольшего размера. Согласно теореме 2.6.3 (viii), строки матрицы линейно независимы, и, следовательно, их продолжения до строк матрицы А также должны быть линейно независимыми. Следовательно, ранг матрицы А по строкам не меньше размера матрицы

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

Пусть А — квадратная -матрица с ненулевым определителем. Тогда, согласно теоремам 2.6.4 и 2.6.7, ее каноническая ступенчатая форма является -матрицей, все строки которой отличны от нулевой, и, следовательно, представляет собой единичную матрицу. Так как А может быть получена из I обращением последовательности элементарных операций над строками, то А можно записать через элементарные матрицы:

Теорема 2.6.8. Если в кольце -матриц над полем то

Доказательство. Шаг 1. Сначала покажем, что если или равны нулю, то и равен нулю. Предположим, что равен нулю; тогда по теореме 2.6.3 (viii) строки матрицы В линейно зависимы. Но строки матрицы являются линейными комбинациями строк матрицы В. Следовательно, строки матрицы С линейно зависимы и равен нулю. Анвлогично исследуется случай, когда равен нулю.

Шаг 2. Предположим, что не равен нулю. Тогда матрицу А можно записать в виде произведения элементарных матриц:

Каиедая из матриц соответствует элементарной операции над строками матрицы А, и, следовательно, согласно пп. (iii), (v) и (vii) теоремы 2.6.3, имеем

При это дает

Подставляя последнее равенство в формулу для случая произвольной В, получаем что и требовалось доказать. Одно из следствий этой теоремы состоит в том, что если то матрица С обратима тогда и только тогда, когда обе матрицы обратимы, так как квадратная матрица имеет обратную тогда и только тогда, когда определитель отличен от нуля.

Заканчивая данный параграф, завершим работу, оставшуюся от предыдущего параграфа.

Теорема 2.6.9. Если размерность подпространства векторного пространства всех -последовательностей равна то размерность его ортогонального дополнения равна

Доказательство. Пусть — базис подпространства определим матрицу равенством

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

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

должен записываться в виде линейной комбинации векторов

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

то

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

ЗАДАЧИ

(см. скан)

(см. скан)

(см. скан)

ЗАМЕЧАНИЯ

В этой главе рассматривался обычный материал современной алгебры. Можно указать много учебников, в которых этот материал излагается более детально. В качестве легко усваиваемого вводного курса, по уровню достаточного для данной книги, мы рекомендуем киту Биркгофа и Маклейна [1953]. Монография Ван дер Вардеиа [1930, 1953] представляет собой курс более высокого уровпя, адресованный в основном математикам и углубленно «влагающий многие вопросы. Материал по линейной алгебре и теории матриц можно найти также и в учебниках, специально посвященных этим разделам алгебры. Особенно подходящей является книга Трялля и Торнгейма [1957], так как она не предполагает никакой предварительной подготовки

Поля Галуа названы в честь Эвариста Галуа (1811—1832). Абелсвы группы названы в честь Нильса Хенрика Абеля (1802—1829).

<< Предыдущий параграф Следующий параграф >>
Оглавление