* Данный текст распознан в автоматическом режиме, поэтому может содержать ошибки

26 ВЕКТОРНЫЕ ПРОСТРАНСТВА И ЛИНЕЙНЫЕ ПРЕОБРАЗОВАНИЯ позволяет для доказательства нашего утверждения в общем случае использовать индукцию по числу элементов в перестановке. Предположим, что утверждение уже доказано для перестановок из л — 1 элементов. Пусть даны две любые перестановки из п элементов (конечно, одних и тех же!) (h> i , ... , i ) 2 n и (j u / , ... , J ). 2 n Требуется рядом транспозиций вторую из них перевести в пер­ вую. Прежде всего находим среди элементов j y' , . . . ,,y" элемент Пусть это будет j . Е с л и Д ^ / j , то производил! во второй переста­ новке транспозицию элементов j и у,. Получаем перестановку u s rt k k (Jk* j\> ••• i Jk-t* /1» jk+i> — ) • Если сравнить её с первой из данных перестановок, то мы увидим, что её элементы, начиная со второго, образуют некоторую переста­ новку элементов г , г , . . . , i . Так как число этих элементов равно п—1, то согласно сделанному предположению можно рядом транс­ позиций превратить эту перестановку в / , г , , г , а это и нужно. Исключённый из рассмотрения случай j =j\ ещё проще, так как в нём не требуется подготовительной транспозиции. Вторым важным для нас фактом является то, что при транс­ позиции двух элементов перестановки её чётность меняется на противоположную. В самом деле, если транспозиция производится н а д с о с е д ­ н и м и элементами перестановки, — это очевидно, так как может появиться или исчезнуть лишь одна инверсия между переставляемыми элементами: расположение этих элементов относительно других элементов перестановки и других элементов между собою не изме­ няется. В общем случае, когда транспонируемые элементы лежат не рядом, перемена мест указанных элементов может быть получена транспозициями соседних элементов следующим образом: сначала меняем местами первый из данных элементов со следующим за ним, затем во вновь полученной перестановке снова меняем местами первый из данных элементов со следующим за ним и т. д. до тех пор, пока первый из данных элементов не займёт места второго из данных. После этого второй из данных элементов переставляем с предшествующими элементами несколько раз до тех пор, пока он не займёт первоначального места первого из данных элементов. Легко усмотреть, что если между данными элементами находилось т элементов перестановки, то для «перенесения» первого элемента на место второго потребуется т -\-1 транспозиция соседних эле­ ментов, а для того, чтобы после этого перенести второй элемент на место первого, нужно т транспозиций соседних элементов. Всего для выполнения нужной нам транспозиции потребовалось 2т -J-1 транспозиций соседних элементов. А так как при каждой такой транспоа 3 n 2 3 л k