А.А. Михалёв, А.В. Михалёв - Начала алгебры часть 1, страница 14

ЕЕ Х ОД1- I ,./У, ТО о:-'IJ.+.1=12: П'ij(Лn"j) = Л 2:j=12: аij(Й] +1I.j)j=14)"2:Ui;(U,j=1Oij"';.1=1= Л· о = о,)=1n3)'i, 1 ,;; .; ,;; П.:2:'щ(rtj +/i.j) = 2:а;.;й.! + 2:а"jбj =0+0= о,.1=12)Е Х,Е Х ОЮ I 'Доказательство. Для любого1)'1/,-"11..;)=2:Оi';Йj +L.i=1)=1= LOij'Uj )=10ijll.j= О + Ь ; = Ь;,Lаi';Пj = Ь ;j=1-Ь; = о.о4.2.109Связь решенийСледствие1)4.2.2.Множество решений однородной системы Ход"является ли­нейным пространством (подпространством линейного простран­ства К''').2)Если 'и Е Х (любое частное решение совместной неоднороднойсистемы), тоХт.е.=Х од н +'и,= {" +u 1" ЕХодн},множество решений неоднородной системы Х являетсясдвигом под пространства решений однородной системы Ходн налюбое частное решение 'и, Е Х.Доказательство. Если а Е Хаю"т.

е. Х однЕслии Е Х, ТО в силу3) а+и ЕХ,+ и. с;; Х.v Е Х, то v= СИтаким образом, Х с;; ХОдНИтак, Х = Х однЗамечание- и)+ и.+ ",при этом в силу4) v -" Е Х одн ,+ и,4.2.3.ОПозже мы покажем, что для любого линейногоподпространства И линейного пространства строк К" над полем Ксуществует однородная система линейных уравнений, для которойХ одн= И, таким образом, любое подпространство в К" может бытьзадано как пространство решений однородной системы.Глава5Подстановки, перестановкиТеоремаМножество 8(U) всех биекций5.0.4..1:и-->исоперациейпроизведения(композиции)отображений9/дляU.L и!!. И, /,9 Е 8(U), обладает следующими свойствами:1) операция произведения ассоциативна (ll,(9Л = (h.g)f для всех.1,.'1,11 Е 8(и)).2)3)нснзргяьньн«элементом для этой операции является тожде­flu (lu.1 =для ВСЯ/ШЙ бнекннни -+ и СУЕцествует обратный элемент­бнекннп .'1=.г' иу(Другими с.повами,ння отппражений;S(U) S(U) -I:=lи= Ли для всехfственное отображение.1: U~Uгруппа относительно операции пронэьеле­подгруппа мононле т(и):множестваUмножества8 = 8( {l, 2,."{1, 2, ..

') -n}рическои группой).изn))})1.6.4S(U)и леммыС;; т(и).)1.8.4Очасто называются подстанов­КЙМИ. Наиболее важный для нас случайс.пучае группуS(U)),= g.f).Доказотельство следует из теоремыБискцииЕU = {l, 2~.п. }, в этомназывают группой подстаковокэлементов (иногда называемой сим,мет­IIIЗапись подстановак. Перестановки5.1.Запись подстановок. Перестановки5.1.Если/Е8" -повстановка. то рассмотрим её каноническую за-nиеь(А1) f~2)Внижней1(',')) .(/(1),1(2),. ,1(n)), поскольку / - бискция,i, 1 =:;; 1, ::;;; 'n, при этом только ПО одно­му разу.

Такие строчки элементов (;], . . ,;,,), 1"; ;j ,,; n, где каж­ДЫЙ элемент i j , 1 =:;; ·ij =:;; Т/" встречается один и только один раз,называются перестановками элементов 1) 2; ... ; n.встречаютсястрочкевсе элементыЛеммаравно5.1.1. Число всех перестановокn! = 1 . 2 . .. . n.('ilJ'.') i n ) из п. элементовДоказательство. Для';.[ имеем 11, возможностей. При выбран­;[ для ;2 имеем (11, - 1) возможность. Таким образом, числоразличных перестановок равно n· (n - 1).. ·2·1 = n!.DномЛемма{1, 2, ...

, n}5.1.2.Числоравно n! (т. е.Доказательство. Дляразличных18,,1= т,.').f8"Еподстановакмножестварассмотрим каноническую запись2/(2)Таким образом, различных подстановок столько же, сколько различ­ных пересгановок п. элементов, т. е.Во/Емногих8",случаяхудобноО·n!.рассматриватьзаписиподстановкирасполагая в верхней строчке произвольную перестановку(;[, i2, ... , "п):;'2I(2)"п[(;,,)Каждый столбец этой таблицы имеет вид).1125_ГлаваПример1)ПодстаНОВКИ,лерестансеки5.1.3.Лля тождественной подстановки вl' =.Для биекцииJ: {1, 2}имеем82(1 2) (2 1).1=22{1, 2}, J(I)-+1=2, J(2)J=(~ ~) = (~ ~).J=('i2) Если1, имеемЕ 8n ,in )l)1=)nтоЗ) Так как(0"7)('i)=0"(7(i)),то;)(~ ~ ~) с ~(~ ~ ~).=в частности,...... n) (12ла4) Обозначим через (i[ i 2...'ln=.712)2оцикл длины э: в группе подстано­i.,.)во" 8 п : подсгановку, переводящую ik в 'ik+l для 1':;k: ,:; л - 1,'i'J' в 'i.[, и оставляющую все элементы из {1)2,._.~n}, отличныеот i 1 , · · .

.ч. на месте. Тогда в 8з имеем шесть подетанавок:е.=(1 :3) =(12:3) =(1 2 :,)(~ ~ 3) .С ~ 3) .1 23 '(1 2) =(~ ~1'(23) =С ~1'(132) =(~ ~5.2.113Переетанавки и транепозиuии3При этом вдля"n ;;, 3=(12)(1 3)следовательно,группаимеем(1 3 2)l'(1 2 3)=(1 3)(1 2),33 и любая группа 3"приn ;;, 3неком­мутагивны. Так как 31 = {Р} И 32 = {е,(12)}-коммутативныегруппы, то получаем, что группако тогда, когда5.2.n=1илиnSn.коммутативна тогда и толь­= 2.Перестановки и транспозиции.; и j, i l' j, в переста­i n ) (все остальные элементы, отличные от ь, ), оста­Рассмотрим перестановку двух элементовновке (ч , ...1ются на своих местах). Эта процедура называется транспозициейперестаковки (ч,Лемма... ,i n).5.2.1.1) Умножение слева и л.!" лодстаяовкнна цикл«j)Г> C~длины2приводит К транспозиции элемензовв нижней строке (перестановке) (уl,i иj...

,jn).2) Умножение справа I(i j) подстановкина цикл(;Л длины2приводнт К транспозиции элементов·i нв верхней строке (перестановке)«1, ... ,i,,).Доказательство.1)(j...) С:=i.~.jA·С1:11';',='1.)1 =}-i.~:j<»'1)I= УАin)=}n.in.111)j114ГлаваПодстановки. лересгачовхи5.2)'i-il( .1]j,=;'is =jin ).1.,j, ..JnС!.1]Леммаn5.2.2элементовjj(...;= 1,..,..jу,Tз»(о списке перестановок). Все{1,2,... , 'n}можно респопожнлъс произвольной перестановки(;1, i 2, · · · , ;п,),);п)= 'iDJnn!перестановак извСПИСОК,начинаятак, что каждая следую­щая пересгеноеке в этом списке получается из предыдущей с помо­щью некоюрой транспозиции двух элементов.Доказательство.11. =2, n!= 2,Проведём индукцию по 'п.

Начало индукциинаши списки:(1,2) .(2,1) ,(2,1)(1,2)'k, k < 'п. Пользуясь(n - 1)! перестановак СПусть наше утверждение верно для всехэтим,создадим первый блок из различных;1напервом месте (Т. е. перестановак из элементов {i2, ... з 'ln.}) , при этомкаждая следующая перестановка получается из предыдущей с помо­щью транспозиции:01, 'i2,(n~1)!Совершая транспозицию{:(-11, .. " i2, . .. ).i, и ;'2 в последней перестановке первогоблока и повторяя наше рассуждение, построим второй блок из раз­личных(n -1)!элементовперестановок с{i 1 : iз; ... i n.} ) ,1i2на первом месте (т.

е. перестановонпри этом каждая следующая перестановкаполучается из предыдущей применением транспозиции:(;2, ... ).(n-1)!{.'(1'2, .. ,iз,·· .).5.2,115Пересэгноекя и транспозицииПродолжая этот процесс, получимкаждый, всего71,'nблоков изперестановок(n - 1)!перестановок. Они все различны: в одном блоке поиндуктивному предположению,в разных блоках перестановки разли­чаются на первом месте. Таким образом, в этом списке присутствуютвсеn' перестановокиз71,элементов, при этом каждая следующая по­лучается из предыдущей с помощью одной транспозиции.Следствие5.2.3.От любой перестановкирейти к любой другой переетановке (j11'"jjn)(-;], ...

, i n )Оможно пе­с помощью конечногочисла транспозиций.Доказательство, В списке с началомрестановку и],··(i 11 · · · i n )1надо найти пе-., jn).ОСледствие 5.2.4. Каждая подстановка=является лронгееленнем т77' ... 71конечного числа циклов Т;, дли­ны два (называемых также транспозициями). Таким образом, циклыдлины два (транспозиции) дают одну из систем образующих груп­пыSn.Доказательство. Составим список перестановок, начинающийсяс перестановкилучается из(1,2.. ,n),в котором каждая l-я перестановка по­l)-й транспозицией элементов(1 -в нём нашу перестановку(kl"", kn )становки 7 (пусть она занимает (Т'-[,_] и j,_],И найдёмиз канонической записи под­+ l)-еместо). Тогда (по лемме обумножении слева на цикл длины два)22(i, j,.).т.

е. 7= Т, .. . 7].Замечаниегде Т,.5.2.5.71,)n= (i,. j.,.) , . "=(1т[= (i l'.7.) -_k]kТ.пjl),Ясно, что представление подсгановки 7= Тl . . Т/, В виде произведения транспозицийсобами (например, (1 2) = (1 2)3)о=ВОЗМОЖНО разными СПО~116Глава5Поястноекн, лерестановхиРазложение подстановок5.3.впроизведение цикловс непересекающимисяорбитамиОрбитой циклаЕсли аt~(J. (ЕSn -«{;[ , , ,i,},n} и и Еi,,) назовём множество[i 2подстановкасимволов{1: 2.М,n, то рассмотрим послсдовательиосгъ(орбиту элемента а), Из конечности множества{1, 2"", n} следует,что найдутся такие натуральные числа I и<8,I8.что (Г'о. = (ГВо.,В группе ВN рассмотрим 0'-1, Применяя (0-1)' К этому равенству,получим= ОЭ-"(а),Q,т=s - t > О, Рассмотрим самое маленькоетакое натуральное число т (со свойством а =при этом все(1"(0.),'" элементов {Il, (1 ((J), "" (1,-1(/I,)} различны), Итак, получили цикл(а (1(а) ,,' (1,'-1 (0.)) длины т. Выбирая элемент /) вне этого цикла(если ',.

< n), получаем цикл (/) (1(/))0 з- '-1(/))) длины т", при этоморбиты этих циклов не первсекаются. Продолжим этот процесс, За­метим, что циклы с непересекающимися орбитами пересгановочны.Единственность этого разложения следует из инвариантности опре­деления орбиты, Итак, получаем следующее утверждение,Теорема5.3.1.Каждая попстноекэ т Е В,. разлагается (и притомединственным образом) в ПРО113ведение инклов с непеьесекеклининсяорбитами (поэтому эти циклы переетановочны друг с другом),Замечание1)В5.3.2.практическихчислоЬзадачахвыбиратькак{n, 0(/1,),., .. (1'-1(u)},2)КакудобноУпражнениечисло,со.не=1,затемвошедшеевИ т, д'правило, циклы длиныопускают в записиначинатьнаименьшее1(Т, е,неподвижные элементы)циклового разложенияподстановки.5.3.3.1) Пусть о, т Е Sn' Подстановка тат- ! называется попстанов­кой,сопряжённой с подстановкой а(спомощьюподстанов­ки т), Проверьте.

что отношение сопряжённости является ОТ-5.3.Il7Разложение в произведение цикловношением эквивалентности. Соответствующее разбиение мно­жестваSnна классы эквивалентных подстановок называетсяразбиением на классы сопряжённых элементов.2) Доказать, что подстановки "У, а Е Sn сопряжены тогда и голь­ко тогда, когда"'/и а имеют одинаковое цикловое разложение(т. е. одинаковое число ЦИКЛОВ каждой длины в своих разложе­ниях в произведение циклов с непересекающимисяорбитами).Указания.а) T(CTICT2)t-1 = (TCTIt-1) (T CT2 t - 1).б) Если а=Пример=01, ... , i,.) -ЦИКJIдлиныт,ТОтстт- 1(T(i 1), ...

, Т(!с)).5.3.4.Пустьб = (~ ~4 5 6 7 8 9 10)2 4 7 5 3 6 10 '{ст=(; ~ ~4 5 6 7 8 9 10)10 2 4 9 7 3 8 .Требуется найти (бст)100Сначала находим_(1 2 3 4 5 6 7 8дет = 4 9 7 10 8 2 6 59 10)1 3 = (5 8)(1 4 10 3 762 9)(разложение в произведение циклов с непересекающимися орбита­ми). ПоэтомуТак как100=(58)2 и (1 4 10 3 7629)8 - тождественные подстановки.12·8 + 4, то(бст)IОО = (1 4 10 3 7 6 2 9)4 =1= ( 7210394 56 56471118ГлаваЗадача5.3.5.тов для групп 8 э .ЗадачаНайти разбиение на классы сопряженных элемен­84, 85.5.3.6.Группа1)Подстановки, перестановки5.порождается транспозициями8"(1 2), (1 :3),... (1(т. с. любой элемент группып)является произведением этих8"транспоаиций) .Указание. Еслиi, j'f1.то(; j) = (1 п(1 Л(1 п·2)Группа8 n , n ;;: :3,порождается транспозицией(1 2)и циклом(12 ... п).5.4.Чётность перестановок и подстановокi и j в перестановке (...