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

Система линейных уравнений и линейные формы, определенные над конечным полем

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

(П.30)

Здесь — коэффициент, стоящий в уравнении при неизвестной; — свободный член.

Говорят, что система (П.30) определена над конечным полем, если для всех i и коэффициенты , так же как и — элементы конечного поля . Неизвестные величины часто называют независимыми переменными системы уравнений.

В тех случаях, когда число элементов конечного поля равно простому числу , систему (П.30) иногда называют системой сравнений по модулю и записывают в виде

Однако здесь мы будем придерживаться записи типа (П.30) как более общей и простой.

Левую часть -го уравнения системы (П.30) принято называть линейной формой, определенной (заданной) над конечным полем. Условимся кратко записывать её в виде

(П.31)

— означает, что сложение и умножение проводится по правилам, определенным для данного конечного поля. С учетом сказанного система (П.30) перепишется так:

(П.32)

Такая сокращенная запись системы линейных уравнений далее является основной.

Заметим, что если число независимых переменных фиксировано, то число всевозможных различных форм, которое можно определить над данным полем , конечно и равно

(П.33)

Так, например, множество всех линейных форм двух независимых переменных над полем GF (2) содержит всего три линейные формы: а над полем GF (3) — уже восемь линейных форм:

Решением системы (П.32) называют совокупность элементов поля , таких, что после подстановки каждое уравнение (П.32) обращается в тождество. Если система уравнений обладает решениями, то она называется совместной. Совместная система называется определенной, если она обладает единственным решением.

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

Однако независимо от этого все формулировки и их запись по-прежнему сохраняют здесь свою силу. Так, например, если в (П.32) число неизвестных равно числу уравнений ( ) то система имеет единственное решение, когда определитель D отличен от нуля, т. е.

(П.34)

где — коэффициент, стоящий при независимой переменной в линейной форме .

Искомые неизвестные , например, могут быть найдены по известной формуле Крамера:

(П.35)

где , к — определитель, полученный из (П.34) заменой -го столбца на столбец, составленный из свободных членов .

При выполнении условия (П.34) линейные формы (П.32) называют линейно независимыми.

Пример. Пусть дана система уравнений .

(П.36)

Допустим сначала, что система (П.36) определена над полем . В этом случае определитель системы (см. табл. (П.2)

Следовательно, система имеет единственное решение. Далее,

Таким образом, согласно (П.35)

Конечно, систему (П.36) можно решить и другим хорошо известным методом. Складывая уравнения (П.36) и учитывая, что

получим

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

или

Следовательно, .

Пусть теперь система (П.36) определена над полем GF (4). Тогда детерминант системы (см. (П.34) и табл.П.3)

Далее,

Следовательно,

Так же как и в предыдущем случае, значения и можно найти и другим способом. Складывая первое уравнение со вторым и учитывая, что и , сразу найдем . Для того чтобы найти , умножим первое уравнение на 2, после чего сложим его со вторым:

и, следовательно, .

Для нас особый интерес представляет случай, когда система (П.32) или, что то же самое, система (П.30) является избыточной . В этой ситуации неизвестные определяются однозначно, если среди линейных форм можно указать по крайней мере одну подсистему линейно независимых форм или, как говорят, если ранг матрицы

(П.37)

составленной из коэффициентов линейных форм (П.31), равен .

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

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

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

В частности, если матрица (П.37) содержит единичную подматрицу порядка , то ее ранг равен .

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