Линейная алгебра над конечным полем

Начнем с того, что введем векторные пространства над конечным полем.

Абстрактное векторное пространство можно определить над любым нолем F. Это множество V, на котором заданы следующие операции: сложение Н-: V х V —> V и умножение на «число» FxV V. Свойства этих операций таковы (здесь мы обозначаем элементы поля греческими буквами, а элементы векторного пространства — латинскими, умножение на число обозначаем точкой *, хотя почти всегда в дальнейшем точка будет опускаться):

LI: V — коммутативная группа но сложению;

L2: а • (г>1 4- ъ'2) = а • гц + а • г?2, (o.'i -|- а^)v = ai • v + 0L2 ? v (дистрибутивность);

L3: a • (pv) = (a0)v (композиция умножений на два числа совпадает с умножением на произведение этих чисел);

L4: 1 • V = V.

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

Пример 3.17. Пусть V = Fn множество последовательностей длины п, составленных из элементов поля F. Сложение и умножение на число определим покомпонентно: для а = = (ai,a2,...,aR), ft = (fiu ?2, • • • ,&,), где a* G F, ft G F,

но определению имеем

Легко проверить выполнение всех свойств из определения векторного пространства.

Построенное в этом примере пространство называется п-мерным координатным пространством над полем F.

Аналогично случаю колец (см. выше), из определения векторного пространства сразу следует дистрибутивность относительно вычитания: аv — 0v = (а — 0)v, так как

Отсюда получаем, что 0 • v = 0, так как

и —V = (—1) • v так как

Множество векторов V векторного пространства V назовем порождающим, если каждый вектор пространства является линейной комбинацией векторов из V', т. е. для любого v ? V справедливо равенство вида

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

Множество векторов V называется линейно независимым, если ИЗ J2i=l ai vi = 0’ ГДв аг vi СЛвДуеТ, ЧТО Oii = О для всех г.

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

Легко понять, что базис существует в любом конечномерном векторном пространстве V. Выберем какое-нибудь конечное порождающее множество V'. Среди подмножеств Vкоторые являются порождающими для V, выберем минимальное но включению подмножество В. Это и будет базис. Действительно, если

то В {bj] также порождающее: для любого v ? V имеем Это противоречит минимальности.

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

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

то, вычитая одну из другой, получаем

По определению линейной независимости отсюда следует, что для всех i выполняется равенство о* — Д = 0, т. е. о* = Д. ?

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

Если ввести понятие изоморфизма векторных пространств аналогично изоморфизмам групп и колец (биекция, сохраняющая операции), то можно сказать, что разложение по базису задает изоморфизм между конечномерным пространством V и координатным пространством Fn.

Теорема 3.19. Число элементов в любых двух базисах конечномерного пространства одинаково.

Другими словами, координатные пространства Fn и Fm неизоморфны при п ф т.

По теореме 3.19 число элементов в базисе не зависит от выбора базиса и называется размерностью пространства.

Мы выведем теорему 3.19 из следующей леммы, использующей понятие эквивалентных систем векторов. Две системы векторов у,..., piV и Z,..., zrn в V назовем эквивалентными, если каждый вектор одной из систем выражается в виде линейной комбинации векторов из второй системы. Ясно, что это действительно отношение эквивалентности: подставив в линейную комбинацию вместо векторов одной системы их выражения в виде линейных комбинаций векторов другой системы, можно раскрыть скобки, привести подобные и получить линейную комбинацию векторов второй системы. Отсюда вытекает транзитивность. Симметричность и рефлексивность очевидны из определения.

Лемма 3.20 (лемма о замене). Пусть ух,..., yi — систыш из линейно независилтх векторов и все векторы у, выражаются как линей)те комбинации векторов системы zy..., zm. Тогда существует, эквивалентная системе z,..., zm система, содержащая ух, ?/2? • • • * У) и какие-то т — I векторов из системы z,..., zm.

Следствием этой леммы является неравенство I ^ т. К двум базисам лемму о замене можно применять в две стороны (так как любые векторы выражаются в виде линейной комбинации векторов из базиса, и базисные векторы линейно независимы). Поэтому получаем два неравенства / ^ т, т ^ /, т. е. т = /. Но эго и есть утверждение теоремы.

Значит, осталось доказать лемму о замене.

Доказательство леммы о замене. Будем доказывать индукцией по /.

База индукции: / = 1. Условие леммы означает, что

причем не все коэффициенты равны 0 (поясним на всякий случай: система из одного вектора 0 является по определению

линейно зависимой). Считаем без ограничения общности, что первый коэффициент ац не равен 0. Тогда

Системы 2/1,22> * • •, zm и 21,22,..., zm в силу (3.3) и (3.4) эквивалентны.

Индуктивный переход. Пусть лемма доказана для I < s. Рассмотрим линейно независимую систему 3/1,... 8. Ее подсистема 2/i,..., у8-1 также линейно независима. Поэтом}', перенумеровав векторы в системе Zi,..., zm), можно считать, что системы 2/i,...,ys-i, zs,..., zm и Z,..., zm эквивачеитны. Но тогда

причем хотя бы один из коэффициентов Д отличен от нуля (иначе из (3.5) получалась бы линейная зависимость между векторами системы i/i,... ,ув). Можно без ограничения общности предположить, что Д Ф 0. Тогда

Системы 2/1» • • • » У в—1> • • • » и У»• • •»2/$» -^s+i»• • •»в силу (3.5) и (3.6) эквивалентны. Значит, эквивачЧентны и системы

У»• • • ч Vs > ^«+1»• • • » И Z,. . . , П

Пример 3.21. Многочлены степени не выше d с коэффициентами из поля F образуют линейное пространство над полем F размерности d + 1. Очевидно, что многочлены 1, гг, гг2, , xd образуют базис в этом пространстве. Но можно указать и другие интересные базисы для пространства многочленов. В частности, если в поле F больше d элементов, то для любого набора ао, ...,ad из различных элементов поля существуют такие многочлены /о, • • •, fd, что /г(a*) = 1 и fi(dj) = 0 при г ф j. Многочлены /о,... образуют базис. Действительно, многочлен / = Eto ai/i = 0 принимает в каждой точке а.{ значение а*. Поэтому линейная зависимость между такими многочленами t*o/o + tti/i H-----1- (*dfd = 0 означает, что все а*

равны 0.

Выпишем явно выражения для многочленов /,;1

Коэффициенты разложения многочлена / по этому базису равны значениям многочлена в точках а само

разложение но этому базису называется интерполяционной формулой Лагранжа:

Как следствие, получаем, что многочлен степени d над полем F однозначно определяется своими значениями, если |F| > d. В частности, над любым бесконечным полем кольцо функций, представимых многочленами, изоморфно кольцу многочленов над этим полем, определенному как в разделе 2.2.

Замечание 3.22. Можно доказать и обратное: если в поле не более d элементов, то некоторый многочлен степени не выше d тождественно равен 0, см. ниже следствие 3.36.

Применим теперь линейную алгебру к изучению конечных полей.

Лемма 3.23. Поле характеристики р является, векторным пространством над полем GF(p).

Операция сложения в поле дает операцию сложения в векторном пространстве. Как уже показано, поле F характеристики р содержит подполе кратных 1, изоморфное GF(p). Это позволяет определить умножение элементов F («векторов») на элементы GF(p) («числа») как умножение в иоле F. Аксиомы векторного пространства выполняются в силу свойств арифметических операций в поле.

Следствие 3.24. В конечном поле рп элементов, рпростое, п — натуральное.

Теперь рассмотрим поле GF(pn), построенное как кольцо вычетов по модулю некоторого неприводимого многочлена f(x) степени п над GF(p). Мы описали элементы этого поля с помощью многочленов степени п — 1 с коэффициентами из GF(p): элемент {ao + aiaM-----fan_i#n-1} ноля GF(pn) соответствует тому классу вычетов, в который входят многочлены, дающие при делении на f(x) остаток ао + оцяЧ-----ban_i#n_1.

Теорема 3.25. Элементы {1}, {#}, ..., {#п_1} образуют базис GF(pn).

В частности, GF(pn) — векторное пространство размерности п над полем GF(p).

Доказательство. Любой остаток представим в виде линейной комбинации указанных векторов:

И обратно, пусть

Это означает, что многочлен bo+bx-------bn-ixn~l делится на

многочлен 71-й степени f(x). Поскольку при умножении ненулевых многочленов их степени складываются, это возможно лишь при Ьо + Ьх + • • • + Ьпп~1 = 0. Значит, система {1}, {т}, .... {.тп_1} линейно независима. ?

Замечание 3.26. Разумеется, построение ноля с помощью вычетов но модулю некоторого неприводимого многочлена и аналоги доказанных в этом разделе теорем справедливы не только в случае конечных полей. Например, возьмем поле действительных чисел и неприводимый над R многочлен х2 + 1. Построим поле IR/(#2 + 1), оно является векторным пространством над Ш. Элементы {1}, {.т} образуют базис этого пространства. Значит, каждый элемент можно представить в виде а{1} 4- 6{&[1]}. Легко проверить, что полученное поле изоморфно полю комплексных чисел С, один из возможных изоморфизмов задается соответствием 1 [1]-? 1, {#} i.

Лемма 3.27. Если поле GF(pn) содержит поле GF(pk), то к делит п.

Доказательство. Аналогично доказательству леммы 3.23. Если F[ С F2, то элементы F^ можно умножать на элементы из Fi, а также складывать. Поэтому F2 является векторным пространством над полем F размерности d. Значит, в нем Fid элементов. Таким образом рп = (pk)d, что и означает делимость п на к. ?

Замечание 3.28. Справедливо и обращение леммы 3.27. Оно следует из единственности ноля GF(pn) (см. ниже раздел 3.8) и существования неприводимого многочлена степени к над любым конечным полем (см. второе доказательство теоремы 3.16 на с. 161).

  • [1] у нормированного многочлена старший коэффициент равен 1. Всякий многочлен можно нормировать, умножив его на обратный к старшему коэффициенту, при этом множество корней не изменяется.
  • [2] у нормированного многочлена старший коэффициент равен 1. Всякий многочлен можно нормировать, умножив его на обратный к старшему коэффициенту, при этом множество корней не изменяется.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >