PA_full (1127144), страница 5
Текст из файла (страница 5)
множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать45 / 432Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полем46 / 432Векторное пространство: определениеОпределениеАбстрактным векторным пространством над полем = {↵, . .
.}называется двухосновная алгебраическая система V = h V, ; +, · i, гдеV = {0, v, . . .} � произвольное множество,++ � бинарная операция сложения над V : V ⇥ V ! V ,· � бинарная операция умножения элемента (�числа�) из·элемент (�вектор�) из V : ⇥ V ! V ,наПрикладная алгебраПоля ГалуаЛинейная алгебра над конечным полем46 / 432Векторное пространство: определениеОпределениеАбстрактным векторным пространством над полем = {↵, . . .}называется двухосновная алгебраическая система V = h V, ; +, · i, гдеV = {0, v, . . .} � произвольное множество,++ � бинарная операция сложения над V : V ⇥ V ! V ,· � бинарная операция умножения элемента (�числа�) из·элемент (�вектор�) из V : ⇥ V ! V ,причём операции + и · удовлетворяют следующим аксиомам:наL1: V � коммутативная группа по сложению, 0 � еёнейтральный элемент.L2: ↵ · (v1 + v2 ) = ↵ · v1 + ↵ · v2 , (↵1 + ↵2 ) · v = ↵1 · v + ↵2 · v,(дистрибутивность · относительно +),L3: ↵ · ( · v) = (↵ ) · v (композиция умножений на дваэлемента поля совпадает с умножением их произведение,�ассоциативность� операций умножения поля и ·),L4: 1 · v = v (унитальность).Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полем47 / 432Координатное пространствоПримерПусть V = n � множество последовательностей длины n,составленных из элементов поля .Сложение и умножение на число определяются покомпонентно.Получившаяся структура � векторное пространство.Его называют n-мерным координатным пространством над полем .Дистрибутивность относительно вычитания: ↵ · v(↵)·v+· v = (↵· v = (↵) · v:+ )·v = ↵·v.Отсюда получаем, что 0 · v = 0, так как 0 · v = (1v = ( 1) · v так какv + ( 1) · v = 1 · v + ( 1) · v = (11) · v = v1) · v = 0 · v = 0 .v=0иПрикладная алгебраПоля ГалуаЛинейная алгебра над конечным полем48 / 432Применение линейной алгебры к изучению конечных полейЛеммаПоле характеристики p > 0 есть векторное пространство надp.Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полем48 / 432Применение линейной алгебры к изучению конечных полейЛеммаПоле характеристики p > 0 есть векторное пространство надДоказательствосложение � наследуется операция сложения в поле ;умножение � посколькуp 1z }| {⇠p = F = { 0, 1, 1 + 1, .
. . , 1 + . . . + 1 } ✓ ,то при умножении �числа� из поля p можнозаменять на соответствующие элементы из поля F ;аксиомы векторного пространства � выполняются в силусвойств арифметических операций в поле .p.Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полем48 / 432Применение линейной алгебры к изучению конечных полейЛеммаПоле характеристики p > 0 есть векторное пространство надДоказательствосложение � наследуется операция сложения в поле ;умножение � посколькуp 1z }| {⇠p = F = { 0, 1, 1 + 1, .
. . , 1 + . . . + 1 } ✓ ,то при умножении �числа� из поля p можнозаменять на соответствующие элементы из поля F ;аксиомы векторного пространства � выполняются в силусвойств арифметических операций в поле .СледствиеКонечное поле (как векторное пространство) состоит из pnэлементов, p � простое, n � натуральное.p.Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полем49 / 432Поля Галуа как кольца вычетов или векторные пространстваПолеnpесть конечная АС с элементами-многочленамиM =a0 + a1 x + .
. . + an1xn 1⇢p [x],которую можно рассматривать какфакторкольцо вычетов по модулю некоторогонеприводимого многочлена f (x) степени n над полем⌦↵n ⇠p [x]/(f (x)); +p , ·pp =или какn-мерное координатное пространство над полем⌦↵n ⇠p = M, p ; +p , ·p .p:p:Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемБазис в50 / 432npТеоремаЭлементы 1, x, . . .
, xn1образуют базисn.pПрикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемБазис в50 / 432npТеоремаЭлементы 1, x, . . . , xn1образуют базисn.pДоказательствоЛюбой элемент np представим в виде линейнойкомбинации указанных векторов:a0 + a1 x + . . . + an1xn 1= a0 1 + a1 x + . . . + an1xn 1.Обратно, пусть g(x) = b0 1 + b1 x + . . .
+ bn 1 xn 1 = 0.Это означает, что многочлен g(x) степени n 1 делится нанекоторый многочлен n-й степени, что возможнолишь приnob0 = b1 = . . . = bn 1 = 0, т.е. система 1, x, . . . , xn 1линейно независима.Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемРасширение поляЗамечаниеПостроение поля с помощью вычетов по модулю некоторогонеприводимого многочлена и аналоги доказанных теоремсправедливы не только в случае конечных полей.51 / 432Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемРасширение поляЗамечаниеПостроение поля с помощью вычетов по модулю некоторогонеприводимого многочлена и аналоги доказанных теоремсправедливы не только в случае конечных полей.Например:12345рассмотрим поле действительных чисел и кольцомногочленов [x] над ним;в [x] возьмём неприводимый многочлен x2 + 1;построим поле F как факторкольцо: F = [x]/(x2 + 1);F также и векторное пространство над ; его базис � 1, xи каждый его элемент z 2 F можно представить в видеz = a1 + bx, a, b 2 ;Поле F изоморфно полю комплексных чисел= a + ib | a, b 2 , i2 = 1 : изоморфизм задаётсясоответствием 1 7! 1, x 7! i.51 / 432Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемПодполя52 / 432npЛеммаЕсли полеnpсодержит подполеk,pто k | n.Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемПодполя52 / 432npЛеммаЕсли полеnpсодержит подполеk,pто k | n.ДоказательствоЕсли поле 1 содержится в поле 1 ⇢ 2 , то элементы 2можно умножать на элементы из 1 , а результаты складывать.Поэтому поле 2 является векторным пространством над полемd1 некоторой размерности d � значит, в нём | 1 | элементов.Для нашего случая: pn = (pk )d , что и означает k | n.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды53 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств54 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать55 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМинимальный многочленРассмотрим поле np , а в нём � какой-нибудь элемент ибудем интересоваться многочленами, для которых этот элементявляется корнем.ОпределениеМногочлен m(x) называется минимальной функцией (илиминимальным многочленом, м.м.) для , если m(x) �нормированный многочлен минимальной степени, для которогоявляется корнем.Другими словами, должны выполняться три свойства:123m( ) = 0;8f (x) 2 p [x] : (deg f (x) < deg m(x) ) f ( ) 6= 0);коэффициент при старшей степени в m(x) равен 1.56 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМинимальные многочлены: пример построенияРассмотрим np = p [x]/(a(x)), гдеa(x) = a0 + a1 x + .
. . + an xn � неприводимый многочлен.Тогда для элемента x 2 np многочлен an 1 a(x) �минимальный.57 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем57 / 432Минимальные многочлены: пример построенияРассмотрим np = p [x]/(a(x)), гдеa(x) = a0 + a1 x + .
. . + an xn � неприводимый многочлен.Тогда для элемента x 2 np многочлен an 1 a(x) �минимальный.1a0 1 + a1 x + . . . + an xn = a0 + a1 x + . . . + an xn ⌘p 0,т.е. x � корень a(x), но тогда x � корень и an 1 a(x).2Пусть существует многочлен b0 + b1 x + . . . + bnкоторогоb0 1+b1 x+. . .+bn1xn 1= b0 1+b1 x+. . .+bn1x1xn 1,n 1для= 0.Это равенство задает линейную зависимость междуклассами 1, x, . . . , xn 1 , которые образуют базис полякак векторного пространства над p .Поэтому b0 = b1 = . . .
= bn 1 = 0.npПрикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленовУтверждениеМинимальные многочлены неприводимы.58 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем58 / 432Свойства минимальных многочленовУтверждениеМинимальные многочлены неприводимы.ДоказательствоПусть m(x) � м.м. и m(x) = m1 (x)m2 (x).Тогдаm1 ( ) = 0m( ) = 0 ),m2 ( ) = 0но deg m1 < deg m и deg m2 < deg m икорнем ни m1 (x), ни m2 (x).не может бытьПрикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленов...УтверждениеПусть в некотором поле Галуа m(x) � м.м.
для элемента , аf (x) � многочлен такой, что f ( ) = 0.Тогда f (x) делится на m(x).59 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем59 / 432Свойства минимальных многочленов...УтверждениеПусть в некотором поле Галуа m(x) � м.м. для элемента , аf (x) � многочлен такой, что f ( ) = 0.Тогда f (x) делится на m(x).ДоказательствоРазделим f (x) на m(x) с остатком:f (x) = u(x)m(x) + v(x) ,deg v < deg m .Подставляя в это равенство , получаем0 = f ( ) = u( ) m( ) +v( ) = v( ) ,| {z }=0т.е.� корень v(x), что противоречит минимальности m(x).Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленов...СледствиеДля каждогоесть ровно один м.м.60 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленов...СледствиеДля каждогоесть ровно один м.м.ДоказательствоПусть минимальных многочленов два.Они взаимно делят друг друга, а значит, различаются наобратимый множитель-константу.Поскольку минимальный многочлен нормирован, эта константаравна 1, т.е.
многочлены совпадают.60 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем61 / 432Свойства минимальных многочленов...УтверждениеДля каждого элементане превосходит n.поляnpсуществует м.м. и его степеньПрикладная алгебраПоля ГалуаКорни многочленов над конечным полем61 / 432Свойства минимальных многочленов...УтверждениеДля каждого элементане превосходит n.поляnpсуществует м.м. и его степеньДоказательствоРассмотрим следующие элементы поля p : 1, , 2 , . . . , n �их n + 1 штука, а размерность np как векторного пространстваравна n ) эти элементы линейно зависимы, т.е. существуюттакие не все равные 0 коэффициенты c0 , . . . , cn , чтоc0 + c1 + . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
