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

2.6. Матрицы

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

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

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

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

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

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

1. Перестановка любых двух строк.

2. Умножение любой строки на ненулевой элемент поля.

3. Прибавление произведения одной из строк матрицы на ненулевой элемент поля к другой строке матрицы.

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

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

Доказательство. Если теорема верна для каждой элементарной операции над строками, то, очевидно, она верна и для последовательного применения таких операций. Для операций 1 и 2 теорема верна очевидным образом. Предположим, что матрица получена из матрицы М применением элементарной операции 3. Тогда, так как измененная строка матрицы М является линейной комбинацией двух строк матрицы М, то любая линейная комбинация строк матрицы М также является линейной комбинацией строк матрицы М, так что пространство строк матрицы М содержится в пространстве строк матрицы М. Но матрица М может быть получена из М с помощью обратной операции, которая тоже является элементарной операцией типа 3, так что пространство строк матрицы М должно содержаться в пространстве строк матрицы Поэтому пространства совпадают. Ч. т. д.

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

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

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

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

Процедура приведения матрицы к ступенчатой канонической форме, по существу, эквивалентна решению системы линейных уравнений путем последовательного исключения неизвестных. Лучше всего показать это на примере. Рассмотрим следующую матрицу, элементами которой являются действительные числа:

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

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

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

столбца, содержащего первый ненулевой элемент второй строки. Это приводит к матрице

Следующий шаг процесса приводит к матрице

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

Ненулевые строки матрицы в ступенчатой канонической форме линейно независимы, и, таким образом, число ненулевых строк совпадает с размерностью пространства строк. Можно показать, что каждому заданному пространству строк соответствует только одна матрица в ступенчатой канонической форме.

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

Матрицей, транспонированной к матрице М размерности называется матрица, обозначаемая размерности строками которой являются столбцы матрицы М и поэтому столбцами — строки матрицы М. Транспонированной матрицей к матрице является матрица

Две матрицы размерности можно складывать поэлементно:

Легко доказать, что при этом определении матрицы образуют абелеву аддитивную группу.

Матрица размерности и матрица размерности могут быть перемножены, причем матрица — произведение

размерности получается по следующему правилу:

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

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

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

Теорема 2.11. Каждая невырожденная матрица обладает левой обратной матрицей, представимой в виде произведения элементарных матриц.

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

Таким образом, матрица является левой обратной матрицей к матрице М. Ч. т. д.

Теорема 2.12. Если матраца размерности невырожденная матрица размерности то произведение матриц имеет то же самое пространство строк, что и матрица М.

Доказательство. Строки произведения являются линейными комбинациями строк матрицы М, и поэтому пространство строк матрицы содержится в пространстве строк матрицы М. Но матрица обладает левой обратной матрицей и строки матрицы являются линейными комбинациями строк матрицы Следовательно, пространство строк матрицы М содержится в пространстве строк матрицы 5.44. Поэтому пространства должны совпадать. Ч. т. д.

Теорема 2.13. Совокупность всех последовательностей длины ортогональных подпространству последовательностей длины образует подпространство последовательностей длины Это подпространство называется нулевым пространством для

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

Теорема 2.14. Если вектор ортогонален каждому из векторов, порождающих подпространство то этот вектор принадлежит нулевому пространству для

Доказательство. Если векторы порождают то каждый вектор из может быть представлен в виде Тогда

и если вектор и ортогонален каждому из векторов то он ортогонален и вектору v. Ч. т. д.

Нулевое пространство для пространства строк матрицы называется нулевым пространством матрицы. Вектор принадлежит нулевому пространству матрицы, если он ортогонален каждой строке матрицы. Если последовательность длины рассматривать как матрицу размерности то принадлежит нулевому пространству

матрицы М размерности тогда и только тогда, когда

Теорема 2.15. Если размерность подпространства последовательностей длины равна то размерность нулевого пространства равна

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

Теорема 2.16. Если подпространство последовательностей длины нулевое пространство для то нулевое пространство для

Доказательство. Если подпространство имеет размерность к, то подпространство имеет размерность и нулевое пространство для имеет размерность Поскольку содержится в нулевом пространстве для и имеет ту же самую размерность, они совпадают. Ч. т. д.

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

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

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