Ю.И. Журавлёв, Ю.А. Флёров, М.Н. Вялый - Дискретный анализ. Основы высшей алгебры (1127101), страница 24
Текст из файла (страница 24)
Другими словами их можно сформулироватьтак: любое поле содержит pn элементов, где p — простое, идля каждого простого p и натурального n есть ровно одно(с точностью до изоморфизма) поле GF (pn ).138Глава 3.Конечные поля или поля ГалуаДоказательства этих теорем приводятся ниже. Сейчас заметим только, что нам потребуется строить поля расширениемне только простого поля вычетов GF (p), но и произвольного конечного поля. Конструкция такого расширения дословносовпадает с приводимой выше конструкцией расширения поляGF (p).3.4. Линейная алгебра над конечнымполемНачнем с того, что введем векторные пространства надконечным полем.Абстрактное векторное пространство можно определитьнад любым полем F . Это множество V , на котором заданыследующие операции: сложение + : V ×V → V и умножение на«число» F ×V → V .
Свойства этих операций таковы (здесь мыобозначаем элементы поля греческими буквами, а элементывекторного пространства — латинскими, умножение на числообозначаем точкой ·, хотя почти всегда в дальнейшем точкабудет опускаться):L1: V — коммутативная группа по сложению;L2: α · (v1 + v2 ) = α · v1 + α · v2 , (α1 + α2 ) · v = α1 · v + α2 · v(дистрибутивность);L3: α · (β · v) = (αβ) · v (композиция умножений на два числасовпадает с умножением на произведение этих чисел);L4: 1 · v = v.Нулевой вектор (единичный элемент в группе сложениявекторного пространства) будем обозначать 0.Пример 3.17.
Пусть V = F n — множество последовательностей длины n, составленных из элементов поля F . Сложениеи умножение на число определим покомпонентно: для α̃ == (α1 , α2 , . . . , αn ), β̃ = (β1 , β2 , . . . , βn ), где αi ∈ F , βi ∈ F ,3.4.Линейная алгебра над конечным полем139по определению имеемα̃ + β̃ = (α1 + β1 , α2 + β2 , . . . , αn + βn ),α · α̃ = (αα1 , αα2 , .
. . , ααn ).Легко проверить выполнение всех свойств из определения векторного пространства.Построенное в этом примере пространство называетсяn-мерным координатным пространством над полем F .Аналогично случаю колец (см. выше), из определения векторного пространства сразу следует дистрибутивность относительно вычитания: α · v − β · v = (α − β) · v, так как(α − β) · v + β · v = (α − β + β) · v = α · v.Отсюда получаем, что 0 · v = 0, так как0 · v = (1 − 1) · v = v − v = 0,и −v = (−1) · v так какv + (−1) · v = 1 · v + (−1) · v = (1 − 1) · v = 0 · v = 0.Множество векторов V ′ векторного пространства V назовем порождающим, если каждый вектор пространства является линейной комбинацией векторов из V ′ , т.
е. для любогоv ∈ V справедливо равенство видаv=mXi=1αi vi ,αi ∈ F, vi ∈ V ′ .Пространство V называется конечномерным, если в немсуществует конечное порождающее множество.Множествовекторов V ′ называется линейно независимым,Pkесли из i=1 αi vi = 0, где αi ∈ F , vi ∈ V , следует, что αi = 0для всех i.Совокупность векторов V ′ называется базисом, если онаодновременно является и порождающим, и линейно независимым множеством.Легко понять, что базис существует в любом конечномерном векторном пространстве V .
Выберем какое-нибудь конечное порождающее множество V ′ . Среди подмножеств V ′ , которые являются порождающими для V , выберем минимальное140Глава 3.Конечные поля или поля Галуапо включению подмножество B. Это и будет базис. Действительно, еслиkXαi bi = 0,i=1αi ∈ F, αj 6= 0, vi ∈ B,то B \ {bj } также порождающее: для любого v ∈ V имеемmXXXβjβj Xαi bi =βi − αibi .v=βi b i =βi b i −αjαji=1i6=ji6=ji6=jЭто противоречит минимальности.Утверждение 3.18.
Каждый элемент конечномерного векторного пространства однозначно представляется в виде линейной комбинации элементов базиса.Доказательство. Действительно, если есть два представления в виде линейной комбинации векторов из базисаv=nXi=1αi vi =nXβi vi ,i=1то, вычитая одну из другой, получаемnnnXXXX0= v−v =αi vi −βi vi =(αi v − βi v) =(αi − βi )v.i=1i=1i=1i=1По определению линейной независимости отсюда следует, чтодля всех i выполняется равенство αi − βi = 0, т. е. αi = βi . Таким образом, каждому элементу векторного пространства с конечным базисом однозначно соответствует набор коэффициентов разложения по этому базисуv ↔ (α1 , .
. . , αn ).Если ввести понятие изоморфизма векторных пространстваналогично изоморфизмам групп и колец (биекция, сохраняющая операции), то можно сказать, что разложение по базисузадает изоморфизм между конечномерным пространством Vи координатным пространством F n .Теорема 3.19.
Число элементов в любых двух базисах конечномерного пространства одинаково.3.4.Линейная алгебра над конечным полем141Другими словами, координатные пространства F n и F mнеизоморфны при n 6= m.По теореме 3.19 число элементов в базисе не зависит отвыбора базиса и называется размерностью пространства.Мы выведем теорему 3.19 из следующей леммы, использующей понятие эквивалентных систем векторов. Две системывекторов y1 , . . . , yl ∈ V и z1 , .
. . , zm ∈ V назовем эквивалентными, если каждый вектор одной из систем выражается ввиде линейной комбинации векторов из второй системы. Ясно,что это действительно отношение эквивалентности: подставив в линейную комбинацию вместо векторов одной системыих выражения в виде линейных комбинаций векторов другойсистемы, можно раскрыть скобки, привести подобные и получить линейную комбинацию векторов второй системы.
Отсюдавытекает транзитивность. Симметричность и рефлексивностьочевидны из определения.Лемма 3.20 (лемма о замене). Пусть y1 , . . . , yl — системаиз линейно независимых векторов и все векторы yi выражаются как линейные комбинации векторов системы z1 , . . . , zm .Тогда существует эквивалентная системе z1 , .
. . , zm система, содержащая y1 , y2 , . . . , yl и какие-то m − l векторов изсистемы z1 , . . . , zm .Следствием этой леммы является неравенство l 6 m.К двум базисам лемму о замене можно применять в две стороны (так как любые векторы выражаются в виде линейнойкомбинации векторов из базиса, и базисные векторы линейнонезависимы). Поэтому получаем два неравенства l 6 m, m 6 l,т. е. m = l. Но это и есть утверждение теоремы.Значит, осталось доказать лемму о замене.Доказательство леммы о замене. Будем доказывать индукцией по l.База индукции: l = 1.
Условие леммы означает, чтоy1 =mXαi zi ,(3.3)i=1причем не все коэффициенты равны 0 (поясним на всякийслучай: система из одного вектора 0 является по определению142Глава 3.Конечные поля или поля Галуалинейно зависимой). Считаем без ограничения общности, чтопервый коэффициент α1 не равен 0. Тогда−α1 z1 = −y1 +mXαi vi ,т. е. z1 = α−11 y1 +i=2mX(−α−11 αi )zi .i=2(3.4)Системы y1 , z2 , . . . , zm и z1 , z2 , . . . , zm в силу (3.3) и (3.4)эквивалентны.Индуктивный переход. Пусть лемма доказана для l < s.Рассмотрим линейно независимую систему y1 , .
. . , ys . Ее подсистема y1 , . . . , ys−1 также линейно независима. Поэтому, перенумеровав векторы в системе z1 , . . . , zm ), можно считать, чтосистемы y1 , . . . , ys−1 , zs , . . . , zm и z1 , . . . , zm эквивалентны. Нотогдаs−1mXXys =αi yi +βi z i ,(3.5)i=1i=sпричем хотя бы один из коэффициентов βi отличен от нуля(иначе из (3.5) получалась бы линейная зависимость междувекторами системы y1 , .
. . , ys ). Можно без ограничения общности предположить, что βs 6= 0. Тогдаzs = βs−1 ys +s−1Xi=1(−βs−1 αi )yi +mX(−βs−1 βi )zi .(3.6)i=s+1Системы y1 , . . . , ys−1 , zs , . . . , zm и y1 , . . . , ys , zs+1 , . . . , zm в силу (3.5) и (3.6) эквивалентны. Значит, эквивалентны и системыy1 , . . . , ys , zs+1 , .
. . , zm и z1 , . . . , zm .Пример 3.21. Многочлены степени не выше d с коэффициентами из поля F образуют линейное пространство над полемF размерности d + 1. Очевидно, что многочлены 1, x, x2 , . . . ,xd образуют базис в этом пространстве. Но можно указатьи другие интересные базисы для пространства многочленов.В частности, если в поле F больше d элементов, то для любогонабора a0 , . . . , ad из различных элементов поля существуюттакие многочлены f0 , .
. . , fd , что fi (ai ) = 1 и fi (aj ) = 0 приi 6= j. МногочленыPd f0 , . . . , fd образуют базис. Действительно,многочлен f =i=0 αi fi = 0 принимает в каждой точке aiзначение αi . Поэтому линейная зависимость между такими3.4.Линейная алгебра над конечным полем143многочленами α0 f0 + α1 f1 + · · · + αd fd = 0 означает, что все αiравны 0.Выпишем явно выражения для многочленов fi :(x − a1 )(x − a2 ) . . .
(x − ad ),(a0 − a1 )(a0 − a2 ) . . . (a0 − ad )(x − a0 )(x − a2 ) . . . (x − ad )f1 =,(a1 − a0 )(a1 − a2 ) . . . (a1 − ad )...,f0 =fd =(x − a0 )(x − a1 ) . . . (x − ad−1 )(ad − a0 )(ad − a1 ) . . . (ad − ad−1 )Коэффициенты разложения многочлена f по этому базису равны значениям многочлена в точках a0 , . . . , ad , а саморазложение по этому базису называется интерполяционнойформулой Лагранжа:f=dXf (ai )fi .(3.7)i=0Как следствие, получаем, что многочлен степени d над полем F однозначно определяется своими значениями, если|F | > d.
В частности, над любым бесконечным полем кольцо функций, представимых многочленами, изоморфно кольцумногочленов над этим полем, определенному как в разделе 2.2.Замечание 3.22. Можно доказать и обратное: если в поле неболее d элементов, то некоторый многочлен степени не вышеd тождественно равен 0, см. ниже следствие 3.36.Применим теперь линейную алгебру к изучению конечныхполей.Лемма 3.23. Поле характеристики p является векторнымпространством над полем GF (p).Операция сложения в поле дает операцию сложения в векторном пространстве. Как уже показано, поле F характеристики p содержит подполе кратных 1, изоморфное GF (p).
Этопозволяет определить умножение элементов F («векторов»)144Глава 3.Конечные поля или поля Галуана элементы GF (p) («числа») как умножение в поле F . Аксиомы векторного пространства выполняются в силу свойстварифметических операций в поле.Следствие 3.24. В конечном поле pn элементов, p — простое, n — натуральное.Теперь рассмотрим поле GF (pn ), построенное как кольцо вычетов по модулю некоторого неприводимого многочленаf (x) степени n над GF (p). Мы описали элементы этого поляс помощью многочленов степени n − 1 с коэффициентами изGF (p): элемент {a0 + a1 x + · · · + an−1 xn−1 } поля GF (pn ) соответствует тому классу вычетов, в который входят многочлены,дающие при делении на f (x) остаток a0 + a1 x + · · · + an−1 xn−1 .Теорема 3.25.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
