У. Питерсон - Коды, исправляющие ошибки (1267328), страница 10
Текст из файла (страница 10)
д. В любом пространстве число линейно независимых векторов, порождаюШих пространство, называется размерностью пространства. Совокупность А линейно независимых векторов, порождающих А-мерное пространство, называется базисом пространства. Из теоремы 2.7 следует, что любая совокупность, содержащая более чем й векторов из я-мерного векторного пространства, линейно зависима. Из теоремы 2.6 следует, что не существует совокупности менее чем из й векторов, порождающей й-мерное пространство, Теорема 2.8. Если ч' есть Ь-мерное векторное пространство, то любая совокупность из й линейно независимых векторов, принадлежащих т', является базисом К Доказательство.
Пусть чп чт...,, чь — совокупность линейно независимых векторов из Г. Если они не порождают пространство 'т', то должен существовать некоторый элемент ч из $', который нельзя представить в виде линейной комбинации векторов чь чм ... ..., и„. Поэтому совокупность й+ 1 векторов ч, ч„чм ..., ч„из пространства Г является линейно независимой. Это противоречит теореме 2.6, и поэтому векторы чь чм ..., чь должны порождать пространство К Ч. т. д. Теорема 2.9. Если векторное пространство т', содержится в векторном пространстве тт и оба пространства имеют одну и ту же размерность А, то эти пространства совпадают.
Доказательство. Базис пространства У~ является совокупностью А линейно независимых векторов в пространстве чм Следовательно, каждый вектор из Гт принадлежит также Уь Ч. т. д. Скалярным произведением двух последовательностей длины и называется скзляр, определяемый как (а„..., а„) (Ь„..., Ь„)=а,Ь, + ... +а„Ь„. Легко показать, что и ч = ч.п и что тч.
(и+ч) = в и+и.ч. Если скалярное произведение двух векторов равно нулю, то говорят, что эти векторы ортогональны. 2.6. Матрицы В этом разделе излагаются в общих чертах некоторые вопросы теории матриц, находящие приложения к кодам, рассматриваемым в следующих трех главах; при этом для большей части результа- в приводятся доказательства, однако материал этого раздела „редставляет собой лишь обзор необходимых разделов теории матриц.
Матрицей размерности пк, т называется упорядоченное мпоество из пгп элементов, расположенных в виде прямоугольной аблицы, содержашей и строк и пг столбцов: ап а, ... а, а 22 а2 = 1а,Д. а„, о„т...а„ Элементами матрицы могут быть, вообще говоря, элементы любого кольца, но в этой книге находят приложения только матрицы с элементами из полей. Строки матрицы можно рассматривать как и наборов длины гп или как и векторов; аналогично и столбцов матрицы могут интерпретироваться как векторы. Совокупность элементов аи, у которых номер строки и номер столбца равны друг другу, называется главной диагональю матрицы. Пространством строк матрицы М размерности п,к' ,т называется совокупность всех линейных комбинаций вектор-строк матрицы М.
Оно образует подпространство векторного пространства наборов длины пг. Размерность пространства строк называется рангом по строкам. Аналогично совокупность всех линейных комбинаций вектор-столбцов матрицы образует пространство столбцов матрицы, размерность которого называется рангом по столбцам. Для любых матриц существует следующая совокупность элементарных операций над строками: 1. Перестановка любых двух строк.
2. Умножение любой строки на ненулевой элемент поля. 3. Прибавление произведения одной из строк матрицы на ненулевой элемент поля к другой строке матрицы. Операция, обратная каждой из элементарных операций над строками, является, очевидно, элементарной операпией того же вида. Теорема 2.10. Если одна матрица получается из другой путем тоследовательного выполнения элементарных операций над строками, то пространства строк этих двух матриц совпадают.
Доказательство. Если теорема верна для каждой элементарной эперации над строками„ то, очевидно, она верна и для последовательного применения таких операций. Для операций 1 и 2 утверждение теоремы очевидно. Предположим, что матрица М' получена зз матрицы М применением элементарной операции 3. Тогда, так гак измененная строка матрицы М' является линейной комбина«ией двух строк матрицы М, то любая линейная комбинация строк матрицы М' также является линейной комбинацией строк матрицы М, так что пространство строк матрицы М' содержится в пространстве строк матрицы М. Но матрица М может быть получена из М' с помощью обратной операции, которая тоже является элементарной операцией типа 3, так что пространство строк матрицы М должно содержаться в пространстве строк матрицы М'.
Поэтому пространства совпадают. Ч. т. д, Элементарные операции над строками могут быть использованы для упрощения матрицы и приведения ее к стандартному виду. Матрица имеет ступенчатую каноническую форму, если: 1) первый ненулевой элемент каждой ненулевой строки равен 1; 2) каждый столбец, содержащий первый ненулевой элемент некоторой строки, в качестве всех остальных элементов содержит нули; 3) первый ненулевой элемент каждой строки стоит правее первого ненулевого элемента каждой предыдущей строки.
Все нулевые строки расположены ниже всех ненулевых строк. Процедура приведения матрицы к ступенчатой канонической форме по существу эквивалентна решению системы линейных уравнений путем последовательного исключения неизвестных. Лучше всего показать это на примере. Рассмотрим следующую матрицу, элементами которой являются действительные числа: 002202 226848 1!5625 113427 Цля того чтобы упростить матрицу, нужно сачала найти первый венулевой столбец, переставить строки, если это необходимо для гого, чтобы переместить ненулевой элемент столбца в первую .троку, и умножить строку на элемент, обратный этому ненулевому влементу, чтобы получить на его месте !.
Переставляя первую и вторую строки матрицы и деля на 2, получаем 113424 002202 115625 113427 "ледующий шаг состоит в вычитании строк, кратных первой строке, из каждой следующей строки для того, чтобы сделать нулевым остаток столбца, соответствующего первому ненулевому элементу первой строки; 1!3424 002202 002201 000003 Затем, не обращая внимания на первую строку, снова найдем первый ненулевой столбец и переставим строки, если зто необходимо, так, чтобы во второй строке этого столбца стоял ненулевой элемент.
После этого умножим вторую строку на элемент, обратный ее первому ненулевому элементу, чтобы получить на его месте 1. В матрице, записанной выше, это соответствует делению второй строки на 2. Затем подходящие кратные этой строки вычитаются из всех остальных строк, с тем чтобы сделать нулями все остальные элементы столбца, содержащего первый ненулевой элемент второй строки. В результате получается матрица 11012 1 00110 1 00000 — 1 00000 3 Следующий шаг процесса приводит к матрице 110120 001100 000001 000000 В результате этого процесса всегда будет получаться матрица в ступенчатой канонической форме. Ненулевые строки матрицы в ступенчатой канонической форме линейно независимы, и, таким образом, число ненулевых строк совпадает с размерностью пространства строк. Можно показать, что каждому заданному пространству строк соответствует только одна матрица в ступенчатой канонической форме.
Е сли все строки квадратной матрицы размерности п линейно тезависнмы, то говорит, что матрица является невырожденной. После приведения такой матрицы к ступенчатой канонической рорме должно тем не менее остаться а линейно независимых '-трок, и поэтому любая строка должна содержать единицу. Это !улет иметь место только в том случае, когда в приведенной матрице н на главной диагонали стоят единицы, а всюду вне главной шагонали — нули, Матрица такого вида называется единичной и обозначается через Е Итак, любая иевырождеиная матрица может быть преобразована в единичную матрицу с помощью элементарных операций над строками. Матрицей, транспонированной к матрице М размерности п Х т называется матрица, обозначаемая через Мт, размерности т Х л, строками которой являются столбцы матрицы М и поэтому столбцами — строки матрицы М. Матрицей, транспонированной к матрице [аа], является мзтрица [ан]. Две матрицы размерности пХт можно складывать поэлементно: [аа]+ [Ьц] = [ап+ Ь;!] Легко доказать, что при этом определении матрицы образуют абелеву группу относительно сложения.
Матрица [ац] размерности а Хй и матрица [Ьа] размерности й Х т могут быть перемножены, причем матрица-произведение [с„.] размерности п Х т получается по следующему правилу: сы — — ~„амЬп. Е ! Прямым вычислением можно показать, что при таком определении умножения матриц выполняется ассоциативный закон и операции умножения и сложения матриц удовлетворяют дистрибутивному закону. Элемент с;; произведения матриц является скалярным произведением Ьй строки матрицы [ап] и !-го столбца матрицы [Ьп]. Кроме того, Ья вектор-строка произведения [сп] является линейной комбинацией векторов-строк матрицы [Ьп], в которую Ья строка этой матрицы входит с коэффициентом аа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
