1611141246-ab877e3369ab95682ab65d15168ec168 (824984), страница 7
Текст из файла (страница 7)
е. рав/и1изnси,м,вОЛО8 равно,2 n ..в самом деле, упорядочим, на основании доказанного ранее, всеперестановкцnизсимволовтак,чтокаждаяполучаетсядущей одной транспозицией. Соседние перестановкипротивоположныечетности,т.е.перестановкиизпредыбудутиметьрасположенытак,что четные и нечетные чередуются. Наше утверждение вытекаеттеперь из очевидного замечания, что при n ~ 2 число n! четно.Определим теперь одно новое понятие, а именно понятие nодстановlCи n-й степени. Запишем одну под другой две перестановкииз (L символов, беря полученныепридвестрокив скобки; например,n=5:3 5 1 4 2)( 52341•в этом примере 1) под числом 3 стоитчисло 2 и т.
д. Мы скажем, что числопереходит в2,число1переходит в3,(4)число 5, под чцслом 5переходит в 5, число 53число4переходит в4(илиостается на .месте) и, наконец, число 2 переходит в 1. Такимобразом, две перестановки, записанные друг под другом в виде (4),определяют некоторое взаимно одн,озн,ачное отображен,ие множества из первых пяти натуральных чисел на себя, т. е. отображе-1)Внешне он напоминает матрицу из двух строк исовсем иной смысл.5столбцов, но имеет§ 3]ПЕРЕСТАНОВКИИние, которое каждому из натуральных чиселв31ПОДСТАНОВКИ1, 2, 3, 4, 5ставитсоответствие одно из этих же натуральных чисел, причемразнымчислам ставятся в соответствие различные же числа.
При этом, таккакчисел всего пять,т.е.конечное множество,пЯти чисел будет соответствовать одномуаименночислу,котороеЯсно, что топервыхмощипяти(4),ввзаимнонегоизк а ж Д о ечиселиз этих1, 2, 3, 4, 5,«переходит».однозначное отображение множества изнатуральныхчисел,котороемыполучилиприпоможно было бы получить, записывая одну под другой инекоторые другие пары перестановок из пяти символов. Эти записи(4)получаются изпутем нескольких транспозиций столбиков; таковы,например,(15243)(25143)( 21534)13254' 32145' 12345 •(5)Во всех этих записях 3 переходит в 5, 5 в 2, и Т.
д.Аналогичным путем две перестановки из n символов, записанныеодна под другой,определяют некоторое взаимно однозначное отображение множества первыхnнатуральных чисел насебя. Всякоевзаимно однозначное отображение А множества первыхnнатуральных чисел на себя называется nодстанов!(ой n-й степени, причем,очевидно, всякая под станов ка А может быть записана при помощидвух перестановок,подписанныходнаподдругой(6)через (Zi здесь обозначается то число, в которое при подстановке А=переходит число Ё, i1, 2, о о .
, n.Подстановка А обладает многими различными записями вида (6).Так, (4) и (5) являются различными записями одной и той же подстановки 5-й степени.От одной записи подстановки А к другой можно перейти припомощи нескольких транспозиций столбиков. При этом можно получить такую запись вида (6), в верхней (или нижней) строке которойстоит любая наперед заданная перестановка из n символов. В частности, всякая подстановка n-й степени А может быть записанаввидеА-т. е. стакой(1 2 о(Хl (Х2•••••n )(Х n(7)'натуральным расположением чисел в верхней строке.записиразличныеподстановкиотличаются другПриот другаперестановками, стоящими в нижней строке, и поэтому число nодстаново!( n-й степени равно числу nерестаново!( uзт.
е. равноn!nсuмволов,32СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ.[гл.ОПРЕДЕЛИТЕЛИ1Примером подстановки n-Й степени служит тождествен,ная подстановкаЕ=при которой наСледует(11 22 ..•.•, n),nместе остаются все СИМВОЛЫ.заметить, чтоверхняяи нижняя строки в записи (6)подстановки А играют разные роли и, переставив их, мы, вообщеговоря, получаем другую подстаНО!JКУ. Так, подстановки 4-й степени( 2 1 4 З) и ( 24 31 41 32)4 3 1 2различны: при первой число 2 переходит в 4, при второй-в 3.Возьмем произвольную запись (6) некоторой подстановки n-й степени А.
Перестановки, составляющие верхнюю и нижнюю строкиэтойзаписи,могут иметьилиодинаковые,или противоположныечетности. Переход к любой другой записи подстановкиосуществить,какМЫзнаем,путемпоследовательногоАможновыполнениянескольких транспозиций в верхней строке и соответствующих имтранспозиций в нижней строке. Однако, совершая одну транспозициювверхней строке записиствующих элементоввнижней(6)иодну тран-спозицию соответстроке,МЫодновременно меняемчетности обеих перестановок и поэтому сохраняем совпадение илипротивоположно.сть этих четностеЙ.
Отсюда следует, что либо привсех записях nодстановки А четности верхн.еЙ и н,ижн,ей строксовпадают, либо же при всех записях он,и nротивоположн,ы.В первом случае подстановка А будет называться четной, во втора'\! - nettemHoU. В частности, тождественная 110дстановка будетчетной.Если подстановка А записана в виде (7), т. е. в верхней строкестоит четная перестановка 1, 2, ... , n, то четность подстановки Абудет определяться четностью перестановки CX 1 , СХ 2 , ••• , СХ п , стоящейв нижней стреке. Отсюда следует, что число четных nодстановокI/-Йcmellenuравно числу нечетных, т. е.
равно12"nl.Определению четности подстан'ОВОК можно дать следующую несколько измененную форму. Если в записи(6) четности обеих строксовпадают, то число инверсий или в обеих строках четное, или в обеихнечетное, т. е. общее число инверсий в двух строках записи (6)будет четным; если же четности строк записи (6) ПРОТИВОПОЛОЖНЫ,то общее чцсло инверсий в этих двух строках нечетно. Таким образом, nодстановка А будет четн,ой, если общее число ин,версийв двух строках любой ее записи чеmн.о, инечетнои - в nротивоnоЛожно-мслучае.§ 3]ПЕРЕСТАНОВКИИ33ПОДСТАНОВКИПри м е р. Пусть дана подстановка пятой степени( 3 1 4 5 2)25431 •в ее верхней строке 4 инверсии, в нижней 7 инверсиli.
Общее числоинверсий в двух строках есть 11, и поэтому подстановка нечетиа.Перепишем эту подстановку в виде( 1 2 3 4 5)51243 .Число инверсий в верхней строке есть О, в нижней 5, т. е. общее числоснова нечетно. Мы видим, что при раЗНblХ записях подстановки сохраняетсячетность общего числа инверсий, но не само это число.Мы хотим указать теперь другие формы определения четностиподстановок, эквивалентные приведенным выше 1). Для этой целиопределим у.мн.ожен.uе noacmaHOBOfC, представляющее и само посебе очень большой интерес. I10дстановка n-й степени есть, как мызнаем, взаимно однозначное отображение множества чисел 1, 2, ... , nна себя. Результат последовательного выполнения двух взаимнооднозначных отображений множества 1, 2, ...
, n на себя сновабудет, очевидно,некоторымвзаимноэтого множества на себя, т. е.однозначнымотображениемпоследовательное выполнение двухподстановок n-Й степени приводит к некоторой вполне определеннойтретьей подстановке n-й степени, называемой nРQuзведен.uе.м первойиз заданных подстановок на вторую. Так, если даныподстановкичетвертой степени1 23 4)1 2 3 4)(А=,3142'В= ( 1 342•то1234)АВ= ( 4 1 23 •Действительно, припри В символходит в4,Можно3подстановкепереходит в4,Асимволпоэтому1припереходитв3,АВ Символ1перенои т.
д.пере множитьлишьподстановкиу .мн.ожен.uе nодстан.овоfC n-й стеnен.и приn~одинаковойстепени.3 flefCoMMymamUBflo_Действительно, для рассмотренных выше подстановок А и В произведение ВА имеет вид1 2 3 4)ВА= ( 3421•т. е. подстановка ВА отлична от подстановки АВ. Такие ПР1iмерыможно подобрать для всех n при n ~ 3, хотя для некоторых парподстановок закон1)этоткоммутативности случайно можетОни потребуются нам лишь в главематериалможноопустить.14,выполняться.и поэтому при первом чтении34[г.'!.СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ.
ОПРЕДЕЛИТЕЛИ1у.множение nодстановок ассоциативно, т. е. можно говоритьо произведении любого конечного числа подстановокn-й степени,взятых (ввиду некоммутативности) в определенном порядке. В самомделе, пусть даны подстановки А, В и С и пусть символ i 1 , 1 ~ i 1 о;::;;;; n,переходит при подстановке А в символ i z , i 2 при подстановке Впереходит в символ i з , а последний при подстановке С-В симВОЛ i4 • Тогда при подстановке АВ символ i 1 переходит в i з , приподстановке ВС символ i 2 переходит в i 4 , а поэтому как при (АВ) С,так и при А (ВС) символ i 1 будет переходить в символ i 4 •Очевидно, что произведение любой nодстановки А на тождественную nодстановку Е, а также произведение Е на А,равно А:АЕ=ЕА=А.Назовем, наконец, обратной для подстановки А такую подстановку А -1 той же степени, чтоAA-l=А-lА=Е.Легко видеть, что обратной для подстановкислужит подстановкаА-l= (СХ 1 а 21 2...
аn )•.. n,получающаяся из А пере меной мест верхней И нижней строк.Рассмотримтеперьподстановкиспециальноговида, получающиеся из тождественной подстановки Е при помощи одной транспозиции,нечетны:производимойонивназываютсяеенижнейстроке.трансnозиция.мииТакиеимеютподстановкивид.. , j ... )( '"... j '" i .,.(8)где многоточиями заменены символы, остающиеся на месте.вимсяобозначатьэтутранспозиции символовтранспозицию символомi, jУслои, л. Применениек нижней строке записи(7)lIРОИЗВОЛЬной подстановки А равносильно умножению подстановки А справана подстановкуизnсимволов(8),т.
е. наможно(i,Л. МЫ знаем, что все перестановкиполучитьизоднойизних,напримернз 1, 2, ... , n, последова тельным выполнением транспозиций; поэтомувсякая подстановка может быть получена из тождественной подстановки путем последовательного выполнения нескольких транспозицийвнижнейстроке,т. е.путемпоследовательногоумножениянаподстановки вида (8). Можно утверждать, следовательно (опускаямножитель Е), что всякая nодстановка nредстави.м.а в виде nроизведения транспозиций.§ 3]ПЕРЕСТАНОВКИи35ПОДСТАНОВКИВсякую подстановку можно многими разными способами разложить в произведение транспозиций.
Всегда можно, например, добавитьдваодинаковыхмножителяj) (l, ;1,вида и,которые даютв произведении подстановку Е, т. е. взаимно уничтожаются. Укажемменее тривиальный при мер:(; ; ~ ~ ~) = (12) (15) (34) = (14) (24) (45) (34) (13).Новый способ определения четности подстановки основан на следующей теореме:При всех разложен,иflХ nодстановки в произведениетран,сnо·зиций четн,ость числа этих тран,сnозuций будет одн,а ита же,причем она совпадает с четн,осmью саАЕОй nодстан,овки.Так, подстановка в рассмотренном выше примере будет нечетной,как можно проверитьи подсчетомчисла инверсий.Эта теорема будет доказана, если мы покажем, что nроизведен,иелюбых kтран,сnозiщий естьсовпадает с четн,осmьючислаnодстан,овка, четн,ость которойПри k = 1 это верно, так какk.транспозиция есть нечетная подстановка. Пусть наше утверждениеk- 1уже доказано для случаямножителей.
Тогда его справедливость для k множителей BbITeJ{aeT из того, что числа k - 1 и kимеют противоположные четности, а умножение подстановки (в данном случае-про изведения первыхk- 1множителей) на транспозицию равносильно выполнению этой транспозицииподстановки,т.е.меняетеевнижней строкечетность.Удобным способом записи подстановок, позволяющим легко находитьих четность, является разложение 8 циклы. Всякая подстановка n-й стеПЕНИможет некоторые из символов 1, 2, ... ,оставлять на месте, другие жедействительно перемещать. Циклической подстановкой или циклО},f назыnваетсятакаяподстановка,чтоприповторенииеедостаточное число развсякий из действительно перемещаемых ею символов может быть переведенв любой другой из этих символов.
Такова, например, подстановка восьмойстепени( 1 2 3 4 5 67 8)1 864 5 273 •она действительно перемещает символы 2, З, 6 и 8, причем переводит символ 2 в 8, символ 8 в 3, символ 3 в 6, а символ 6 снова в 2.К числу циклов принадлежат все транспозиции. По аналогии с употребленной выше сокращенной записью транспозиций, для циклов употребляетсяследующая запись: действительно переставляемые символы записываютсяв круглых скобках друг за другом в том порядке, в каком они друг в другапереходят при повторении подстановки; начинается запись с любого из действительно перемещаемых символов, а последний символ сqитается переходящим в первый. Так, для указанного выше примера эта запись имеет вид(2 8 3 6).Число символов, действительноцикла.перемещаемыхциклом, называется длиной36СИСТЕМЫ ЛИНЕАныхУРАВНЕНИЙ.[ГЛ.ОПРЕДЕЛИТЕЛИ1Два цикла n-й степени называются незавUСUItIЫМU, если они не имеютобщих действительно переставляеМLlХ символов.
Понятно, что при перемножении независимых циклов порядок ыножителей не влияет на результат.Всякаяnодстановкаможетбытьединственны."способомразложенав nроизведенuе попарно незавuсимых циклов. Доказательство этого утверждения не представляет затруднений, и мы его опускаем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
