Е.Е. Тыртышников - Матричный анализ и линейная алгебра, страница 8

Äëÿ åå ïîñòðîåíèÿ íàì ïîíàäîáèòñÿ ïîíÿòèå ïîäñòàíîâêè.4.2Ïîäñòàíîâêè è ïåðåñòàíîâêèÎáðàòèìîå îòîáðàæåíèå σ : N → N, ãäå N = {1, 2, . . . , n}, íàçûâàåòñÿ ïîäñòàíîâêîé (èíîãäà òàêæå ïåðåñòàíîâêîé) ñòåïåíè n. Äëÿ îáîçíà÷åíèÿ ïîäñòàíîâêè σ ÷àñòîèñïîëüçóåòñÿ òàáëèöà12...nσ=,σ(1) σ(2) . . . σ(n)â êîòîðîé ÷èñëà σ(1), σ(2), . . . , σ(n) îáðàçóþò ïåðåñòàíîâêó ÷èñåë 1, 2, . . . , n (ýòî ðàâíîñèëüíî îáðàòèìîñòè îòîáðàæåíèÿ σ ).2324Ëåêöèÿ 4Îïðåäåëèì ïðîèçâåäåíèå ïîäñòàíîâîê a è b êàê îòîáðàæåíèå, ïîëó÷àåìîå ïîñëåäîâàòåëüíûì âûïîëíåíèåì (êîìïîçèöèåé) îòîáðàæåíèé b è a:(ab)(i) = a(b(i)),i ∈ N.Ýòî àëãåáðàè÷åñêàÿ îïåðàöèÿ íà ìíîæåñòâå âñåõ ïîäñòàíîâîê ñòåïåíè n, îòíîñèòåëüíîêîòîðîé îíî ÿâëÿåòñÿ ãðóïïîé.  ñàìîì äåëå, àññîöèàòèâíîñòü î÷åâèäíà (ýòèì ñâîéñòâîì âñåãäà îáëàäàåò êîìïîçèöèÿ îòîáðàæåíèé).

Ðîëü åäèíè÷íîãî ýëåìåíòà èãðàåò òîæäåñòâåííîå îòîáðàæåíèå1 2 ... ne=,1 2 ... nà îáðàòíûì ýëåìåíòîì äëÿ σ ÿâëÿåòñÿ îáðàòíîå îòîáðàæåíèå σ −1 .Ãðóïïà ïîäñòàíîâîê ñòåïåíè n íàçûâàåòñÿ ñèììåòðè÷åñêîé ãðóïïîé ñòåïåíè n èîáîçíà÷àåòñÿ Sn . Ýòî îäèí èç âàæíåéøèõ ïðèìåðîâ êîíå÷íûõ ãðóïï (ãðóïï ñ êîíå÷íûì÷èñëîì ýëåìåíòîâ; ïðè ýòîì ÷èñëî ýëåìåíòîâ íàçûâàåòñÿ ïîðÿäêîì ãðóïïû). Íåòðóäíîïðîâåðèòü, ÷òî ïîðÿäîê ãðóïïû Sn ðàâåí n! = 1 · 2 · . . .

· n.Íàçâàíèå ñèììåòðè÷åñêîé ãðóïïû íàâåÿíî îïðåäåëåíèåì òàê íàçûâàåìûõ ñèììåòðè÷åñêèõ ôóíêöèé: òàê íàçûâàåòñÿ ôóíêöèÿ F (x1 , . . . , xn ), åñëè îíà èíâàðèàíòíà îòíîñèòåëüíî ëþáûõ ïîäñòàíîâîê ñâîèõ àðãóìåíòîâ:F (x1 , . . . , xn ) = F (xσ(1) , . . . , xσ(n) ) ∀ σ ∈ Sn .Ïðèìåð ñèììåòðè÷åñêîé ôóíêöèè (îïðåäåëÿåìîé ÷èñëîâûì ïàðàìåòðîì k ):Fk (x1 , . . .

, xn ) =nXxki .i=1Çàäà÷à.Äàíû äâå ñèñòåìû ÷èñåëëþáîé ïîäñòàíîâêèσ ∈ Snx1 ≤ x2 ≤ ... ≤ xnnX|xi − yi | ≤i=14.3èy1 ≤ y2 ≤ ... ≤ yn .Äîêàçàòü, ÷òî äëÿâûïîëíÿåòñÿ íåðàâåíñòâînX|xi − yσ(i) |.i=1Öèêëû è òðàíñïîçèöèèÏîäñòàíîâêà a ∈ Sn íàçûâàåòñÿ öèêëîì äëèíû k , åñëè èìååòñÿ k ïîïàðíî ðàçëè÷íûõíîìåðîâ i1 , . . . , ik ∈ N òàêèõ, ÷òî(1) a(i1 ) = i2 , a(i2 ) = i3 , . . . , a(ik−1 ) = ik , a(ik ) = i1 ,(2) a(i) = i∀ i ∈ N \ {i1 , i2 , . . . , ik }.Äëÿ îáîçíà÷åíèÿ öèêëà a óäîáíî èñïîëüçîâàòü çàïèñüa = (i1 , .

. . , ik ).Öèêë äëèíû 2 íàçûâàåòñÿ òàêæå òðàíñïîçèöèåé.Öèêëû a = (i1 , . . . , ik ) è b = (j1 , . . . , jm ) íàçûâàþòñÿ íåçàâèñèìûìè, åñëè{i1 , . . . , ik } ∩ {j1 , . . . , jm } = ∅.Å. Å. Òûðòûøíèêîâ25(1) Ëþáûå íåçàâèñèìûå öèêëû a è b êîììóòèðóþò: ab = ba.(2) Ëþáàÿ ïîäñòàíîâêà σ ∈ Sn ïðåäñòàâèìà â âèäå ïðîèçâåäåíèÿ íåçàâèñèìûõ öèêëîâîäíîçíà÷íî ñ òî÷íîñòüþ äî ïîðÿäêà ñîìíîæèòåëåé.(3) Ëþáîé öèêë äëèíû k ïðåäñòàâèì â âèäå ïðîèçâåäåíèÿ k − 1 òðàíñïîçèöèé.(4) Ëþáàÿ ïîäñòàíîâêà ïðåäñòàâèìà â âèäå ïðîèçâåäåíèÿ òðàíñïîçèöèé.Óòâåðæäåíèå (1) ïðîâåðÿåòñÿ íåïîñðåäñòâåííî: â ñëó÷àå íåçàâèñèìûõ öèêëîâ a =(i1 , .

. . , ik ) è b = (j1 , . . . , jm ) íàõîäèì(ab)(i) = (ba)(i) = a(i) ïðè i ∈ {i1 , . . . , ik },(ab)(i) = (ba)(i) = b(i) ïðè i ∈ {j1 , . . . , jm },(ab)(i) = (ba)(i) = i ïðè i ∈/ {i1 , . . . , ik } ∪ {j1 , . . . , jm }.×òîáû äîêàçàòü (2), âîçüìåì ïðîèçâîëüíûé íîìåð j è ðàññìîòðèì ïîñëåäîâàòåëüíîñòü íîìåðîâ j, σ(j), σ 2 (j), . . . .

Èìååòñÿ òîëüêî n ðàçëè÷íûõ çíà÷åíèé ïîýòîìó äëÿêàêèõ-òî k < l äîëæíî áûòü σ k (j) = σ l (j), îòêóäà ïîëó÷àåì σ l−k (j) = j . Ïóñòü k íàèìåíüøèé íîìåð òàêîé, ÷òî σ k (j) = j . Òîãäà ïîëó÷àåì öèêëa = (j, σ(j), σ 2 (j), . . . , σ k−1 (j)),äëÿ êîòîðîãîσ(i) = a(i) ïðè i ∈ {j, σ(j), σ 2 (j), . . . , σ k−1 (j)}.ßñíî, ÷òî ïîäñòàíîâêà σ1 = σa−1 îñòàâëÿåò íà ìåñòå èíäåêñûi ∈ {j, σ(j), σ 2 (j), . . .

, σ k−1 (j)}.Äàëåå, âîçüìåì j1 ∈/ {j, σ(j), σ 2 (j), . . . , σ k−1 (j)} è àíàëîãè÷íûì îáðàçîì ïîñòðîèì öèêëb, âûïîëíÿþùèé ïðåîáðàçîâàíèÿ âèäàj1 → σ1 (j1 ) → σ12 (j1 ) → . . . .(Çàìåòèì, ÷òî σ1l (j1 ) = σ l (j1 ) äëÿ âñåõ l.) Ïðîäîëæàÿ ïîäîáíûå ïîñòðîåíèÿ, ìû íåèçáåæíî ïðèäåì ê òîæäåñòâåííîé ïîäñòàíîâêåσ a−1 b−1 . . . c−1 = e,îòêóäàσ = c . .

. ba.Ïî ïîñòðîåíèþ öèêëû a, b, . . . , c íåçàâèñèìû.Óòâåðæäåíèå (3) äîêàçûâàåòñÿ ïðîâåðêîé, íàïðèìåð, ñëåäóþùåãî ðàâåíñòâà:(i1 , . . . , ik ) = (i1 , i2 )(i2 . i3 ) . . . (ik−1 , ik ).Óòâåðæäåíèå (4) î÷åâèäíî âûòåêàåò èç (2) è (3).Çàäà÷à.Äîêàæèòå, ÷òî âñå ìíîæåñòâî ïîäñòàíîâîê ñòåïåíèn ìîæíî óïîðÿäî÷èòü òàêèì îáðàçîì,÷òî êàæäàÿ ñëåäóþùàÿ ïîäñòàíîâêà áóäåò ïîëó÷àòüñÿ èç ïðåäûäóùåé ïóòåì óìíîæåíèÿ ñïðàâà íàíåêîòîðóþ òðàíñïîçèöèþ.264.4Ëåêöèÿ 4×åòíîñòü ïîäñòàíîâêèÏîäñòàíîâêà ìîæåò áûòü ðàçëîæåíà â ïðîèçâåäåíèå òðàíñïîçèöèé ìíîãèìè ðàçíûìèñïîñîáàìè. Íàïðèìåð,1 2 3 4 5 6 7=7 5 3 1 2 4 6(1, 7) (7, 6) (6, 4) (2, 5) = (1, 7) (7, 6) (6, 4) (7, 2) (7, 5) (7, 2).Îäíàêî, ÷èñëî òðàíñïîçèöèé â ëþáîì ðàçëîæåíèè îäíîé è òîé æå ïîäñòàíîâêè îáëàäàåòñëåäóþùèì âàæíûì ñâîéñòâîì.Ëåììà î ÷èñëå òðàíñïîçèöèé.

×åòíîñòü ÷èñëà òðàíñïîçèöèé íå çàâèñèò îò ñïîñîáà ïðåäñòàâëåíèÿ ïîäñòàíîâêè â âèäå ïðîèçâåäåíèÿ òðàíñïîçèöèé.Äîêàçàòåëüñòâî. Äëÿ çàäàííîé ïîäñòàíîâêè σ ∈ Snσ=12...nσ(1) σ(2) . . . σ(n)íàçîâåì èíâåðñèåé ïàðó (i, j), åñëè i < j , íî σ(i) > σ(j). Ïóñòü δ(σ) îáùåå ÷èñëîèíâåðñèé äëÿ σ . Äîêàæåì, ÷òî äëÿ ëþáîé òðàíñïîçèöèè τ ðàçíîñòü δ(στ ) − δ(σ) áóäåòíå÷åòíûì ÷èñëîì. Ïóñòü τ = (i, j), i < j . Òîãäà1...i−1ii+1...j−1jj+1...nστ =.σ(1) .

. . σ(i − 1) σ(j) σ(i + 1) . . . σ(j − 1) σ(i) σ(j + 1) . . . σ(n)Ïðåäïîëîæèì, ÷òî ïîäñòàíîâêà σ èìååò k èíâåðñèé ñðåäè ïàð âèäà(i, l),ãäå l ∈ {i + 1, i + 2, . . . , j − 1},(∗)ãäå l ∈ {i + 1, i + 2, . . . , j − 1},(∗∗)m èíâåðñèé ñðåäè ïàð âèäà(l, j),è åùå s èíâåðñèé ñðåäè ëþáûõ äðóãèõ ïàð. Òîãäà στ áóäåò èìåòü j − i − 1 − k èíâåðñèéñðåäè ïàð âèäà (∗) è j − i − 1 − m èíâåðñèé ñðåäè ïàð âèäà (∗∗).

Êðîìå òîãî, ñðåäèëþáûõ äðóãèõ ïàð ïîäñòàíîâêà στ áóäåò èìåòü s + 1 èíâåðñèþ, åñëè ïàðà (i, j) íå áûëàèíâåðñèåé, è s − 1 â ïðîòèâíîì ñëó÷àå. Òàêèì îáðàçîì,δ(σ) = k + m + s,δ(στ ) = (i − j − 1 − k) + (i − j − 1 − m) + s ± 1.Îòñþäàδ(στ ) − δ(σ) = 2(i − j − 1 − k − m) ± 1.2Ñëåäñòâèå. ×åòíîñòü ÷èñëà òðàíñïîçèöèé â ðàçëîæåíèè ïîäñòàíîâêè ñîâïàäàåò ñ÷åòíîñòüþ åå ÷èñëà èíâåðñèé.Îïðåäåëåíèå. Ïîäñòàíîâêà íàçûâàåòñÿ ÷åòíîé, åñëè îíà ÿâëÿåòñÿ ïðîèçâåäåíèåì÷åòíîãî ÷èñëà òðàíñïîçèöèé, è íå÷åòíîé â ïðîòèâíîì ñëó÷àå.Çàìå÷àíèå. Ðàññìîòðèì ôóíêöèþ∆(x1 , . . . , xn ) =Y(xj − xi ).i<jÅ.

Å. Òûðòûøíèêîâ27Òîãäà äëÿ ëþáîé ïîäñòàíîâêè σ ∈ Sn èìååò ìåñòî îäíî èç äâóõ:ëèáî∆(x1 , . . . , xn ) = ∆(xσ(1) , . . . , xσ(n) )∆(x1 , . . . , xn ) = −∆(xσ(1) , . . . , xσ(n) ).×åòíûå ïîäñòàíîâêè è òîëüêî îíè çíàê ñîõðàíÿþò (ïåðâûé ñëó÷àé), íå÷åòíûå è òîëüêîîíè çíàê ìåíÿþò (âòîðîé ñëó÷àé).Ìíîæåñòâî âñåõ ÷åòíûõ ïîäñòàíîâîê â Sn îáðàçóåò ïîäãðóïïó (äîêàæèòå!), êîòîðàÿíàçûâàåòñÿ çíàêîïåðåìåííîé ãðóïïîé ñòåïåíè n è îáîçíà÷àåòñÿ An .Çàäà÷à.Äîêàæèòå, ÷òî ëþáóþ ÷åòíóþ ïîäñòàíîâêó ñòåïåíèn ≥ 3ìîæíî ïðåäñòàâèòü â âèäåïðîèçâåäåíèÿ öèêëîâ äëèíû 3.4.5Åäèíñòâåííîñòü èíäèêàòîðà ëèíåéíîé çàâèñèìîñòèÂåðíåìñÿ ê ïîñòðîåíèþ èíäèêàòîðà ëèíåéíîé çàâèñèìîñòè ôóíêöèè f (a1 , .

. . , an ) îòâåêòîðîâa11a12a1n a21  a22  a2n a1 =  . . .  , a2 =  . . .  , . . . , an =  . . .  ,an1an2annóäîâëåòâîðÿþùåé òðåáîâàíèÿì (A), (B), (C). Ëåãêî âèäåòü, ÷òîa1 =nXai1 1 ei1 ,a2 =i1 =1nXi2 =1ai1 2 ei2 ,... ,an =nXain n ein ,in =1ãäå e1 , e2 , . . . , en ñòîëáöû åäèíè÷íîé ìàòðèöû ðàçìåðîâ n × n.Åñëè èñêîìàÿ ôóíêöèÿ f ñóùåñòâóåò, òî ñâîéñòâî (A) ëèíåéíîñòè ïî êàæäîìó àðãóìåíòó ïðèâîäèò ê âûðàæåíèþf (a1 , . . . , an ) =nXi1 =1...nXai1 1 ai2 2 .

. . ain n f (ei1 , ei2 , . . . , ein ).in =1Ñîãëàñíî òðåáîâàíèþ (B), f = 0 íà ëþáîé ëèíåéíî çàâèñèìîé ñèñòåìå âåêòîðîâ.Î÷åâèäíî, ñèñòåìà âåêòîðîâ ei1 , ei2 , . . . , ein áóäåò ëèíåéíî çàâèñèìîé â òîì è òîëüêî òîìñëó÷àå, êîãäà ñðåäè ýòèõ âåêòîðîâ åñòü ðàâíûå (åñëè âñå ýòè âåêòîðû ïîïàðíî ðàçëè÷íû,òî îíè îáðàçóþò ïåðåñòàíîâêó ñòîëáöîâ åäèíè÷íîé ìàòðèöû). Ñëåäîâàòåëüíî, èñêëþ÷àÿèç ñóììèðîâàíèÿ çàâåäîìûå íóëè, íàõîäèìXf (a1 , . . . , an ) =aσ(1)1 aσ(2)2 . . . aσ(n)n f (eσ(1)i , eσ(2) , .

. . , eσ(n) ).σ∈SnÄàëåå, èç òðåáîâàíèé (A) è (B) âûòåêàåò, ÷òî f äîëæíà ìåíÿòü çíàê ïðè ïåðåñòàíîâêåëþáûõ äâóõ àðãóìåíòîâ. Äîêàæåì ýòî, íàïðèìåð, äëÿ ïåðâîãî è âòîðîãî àðãóìåíòîâ.Ó÷òåì, ÷òî f = 0 â ñëó÷àå ðàâíûõ àðãóìåíòîâ è âîñïîëüçóåìñÿ ëèíåéíîñòüþ ïî êàæäîìóàðãóìåíòó:0 = f (a1 + a2 , a1 + a2 , a3 , .

. . , an ) =f (a1 , a1 , a3 , . . . , an ) + f (a1 , a2 , a3 , . . . , an ) + f (a2 , a1 , a3 , . . . , an ) + f (a2 , a2 , a3 , . . . , an ).28Ëåêöèÿ 4Ïåðâîå è ÷åòâåðòîå ñëàãàåìûå èìåþò ñîâïàäàþùèå âåêòîðû è ïîýòîìó ðàâíû íóëþ.Îòñþäàf (a1 , a2 , a3 , . . . , an ) = −f (a2 , a1 , a3 , . . . , an ).Ñëåäîâàòåëüíî, åñëè ïîäñòàíîâêà σ ÿâëÿåòñÿ òðàíñïîçèöèåé, òîf (eσ(1) , eσ(2) , . . . , eσ(n) ) = −f (e1 , e2 , .

. . , en ) = −1. îáùåì ñëó÷àå ïîäñòàíîâêó σ ìîæíî ðàçëîæèòü â ïðîèçâåäåíèå òðàíñïîçèöèé.Ïóñòü δ(σ) åñòü ÷èñëî òðàíñïîçèöèé â êàêîì-ëèáî èç ðàçëîæåíèé. Òîãäàf (eσ(1) , eσ(2) , . . . , eσ(n) ) = (−1)δ(σ) .Ïî ëåììå î ÷èñëå òðàíñïîçèöèé, ÷åòíîñòü ÷èñëà δ(σ) íå çàâèñèò îò êîíêðåòíîãî ðàçëîæåíèÿ â ïðîèçâåäåíèå òðàíñïîçèöèé, ïîýòîìó âåëè÷èíà (−1)δ(σ) çàâèñèò òîëüêî îò σ .Íàçîâåì åå çíàêîì ïîäñòàíîâêè è îáîçíà÷èì ÷åðåç sgn(σ). Îêîí÷àòåëüíî,Xf (a1 , . . . , an ) =sgn(σ) aσ(1)1 aσ(2)2 .