Подстановки, перестановки

Перестановки и транспозиции

Рассмотрим перестановку двух элементов i и j,, в перестановке (i₁,…,i_n) (все остальные элементы, отличные от i, j, остаются на своих местах). Эта процедура называется транспозицией перестановки (i₁,…,i_n).

Лемма 5.2.1.

1. Умножение слева (i j)fподстановки
   

   на цикл (i j) длины 2 приводит к транспозиции элементов i и j в нижней строке (перестановке) (j₁,…,j_n).

2. Умножение справа f(i j) подстановки
   

   на цикл (i j) длины 2 приводит к транспозиции элементов i и j в верхней строке (перестановке) (i₁,…,i_n).

Доказательство.

Лемма 5.2.2 (о списке перестановок). Все n! перестановок из n элементов {1,2,…,n} можно расположить в список, начиная с произвольной перестановки (i₁,i₂,…,i_n), так, что каждая следующая перестановка в этом списке получается из предыдущей с помощью некоторой транспозиции двух элементов.

Доказательство. Проведем индукцию по n. Начало индукции n=2, n!=2, наши списки:

Пусть наше утверждение верно для всех k, k<n. Пользуясь этим, создадим первый блок из различных (n-1)! перестановок с i_1 на первом месте (т. е. перестановок из элементов {i₂,…,i_n}), при этом каждая следующая перестановка получается из предыдущей с помощью транспозиции:

Совершая транспозицию i₁ и i₂ в последней перестановке первого блока и повторяя наше рассуждение, построим второй блок из различных (n-1)! перестановок с i₂ на первом месте (т. е. перестановок элементов {i₁,i₃,…,i_n}), при этом каждая следующая перестановка получается из предыдущей применением транспозиции:

Продолжая этот процесс, получим n блоков из (n-1)! перестановок каждый, всего n! перестановок. Они все различны: в одном блоке по индуктивному предположению, в разных блоках перестановки различаются на первом месте. Таким образом, в этом списке присутствуют все n! перестановок из n элементов, при этом каждая следующая получается из предыдущей с помощью одной транспозиции.

Следствие 5.2.3. От любой перестановки (i₁,…,i_n) можно перейти к любой другой перестановке (j₁,…,j_n) с помощью конечного числа транспозиций.

Доказательство. В списке с началом (i₁,…,i_n) надо найти перестановку (j₁,…,j_n).

Следствие 5.2.4. Каждая подстановка

является произведением конечного числа циклов длины два (называемых также транспозициями). Таким образом, циклы длины два (транспозиции) дают одну из систем образующих группы S_n

.

Доказательство. Составим список перестановок, начинающийся с перестановки (1,2,…,n), в котором каждая l-я перестановка получается из (l-1)-й транспозицией элементов i_l-1 и j_l-1, и найдем в нем нашу перестановку (k₁,…,k_n) из канонической записи подстановки (пусть она занимает (r+1)-е место). Тогда (по лемме об умножении слева на цикл длины два)

т. е. , где .

Замечание 5.2.5. Ясно, что представление подстановки в виде произведения транспозиций возможно разными способами (например, (1 2)=(1 2)³).

Линейные пространства

Вывод свойств линейного пространства из аксиом Пусть K — поле (например, K= R — поле действительных чисел). Многочисленные конкретные примеры линейных пространств, с которыми мы уже столкнулись (линейные пространства строк Kn, столбцов , пространства прямоугольных и квадратных матриц и , пространство многочленов K[x], пространство непрерывных вещественных функций C[0,1] на отрезке [0,1] и т. д.), оправдывают […]

Системы линейных уравнений

В средней школе рассматривались линейные уравнения ax=b и системы линейных уравнений где — действительные числа. В излагаемой теории систем линейных уравнений мы будем совершать с коэффициентами операции сложения и умножения, а также делить (т. е. умножать на обратный элемент) на ненулевой элемент. Таким образом, естественно рассматривать системы линейных уравнений с коэффициентами из произвольного поля K. […]

Решение системы линейных уравнений

Чтобы выяснить имеет ли составленная система решение или нет, а, если имеет решение, то их количество, применяют следующую теорему. Теорема 1. Если ранг матрицы системы равен рангу расширенной матрицы системы, то такая система совместна и имеет хотя бы одно не нулевое решение. Пример. Определить совместность системы Решение. Составим матрицу системы и определим ее ранг (т.е. […]

Системы линейных уравнений

В общем случае линейная система, составленная из К линейных уравнений относительно n неизвестных примет вид: (3.1) где x1, x2, …, xn — неизвестные; a11, a12, …, akn — коэффициенты при неизвестных; b1, b2, …, bk — свободные члены. Определение 1. Решением системы (1) называется совокупность из n чисел (с1, с2, …, сn), которые, будучи подставленными […]

Четность перестановок и подстановок

Будем говорить, что числа i и j в перестановке (…,i,…,j,…) образуют инверсию, если число i расположено левее, чем j, но i>j (в противном случае будем говорить, что числа i и j расположены в правильном порядке). Ясно, что сумма числа всех инверсией и числа всех порядков в любой перестановке из n чисел 1,2,…,n равна . Пример […]

Разложение подстановок в произведение циклов с непересекающимися орбитами

Орбитой цикла (i1 i2 … ir) назовем множество {i1,…,ir} . Если — подстановка символов {1,2,…,n} и , , то рассмотрим последовательность (орбиту элемента a). Из конечности множества {1,2,…,n} следует, что найдутся такие натуральные числа t и s, t<s, что . В группе S_n рассмотрим . Применяя к этому равенству, получим , r=s-t>0. Рассмотрим самое маленькое […]

Подстановки, перестановки

Теорема 5.0.4. Множество S(U) всех биекций с операцией произведения (композиции) отображений gf для , , обладает следующими свойствами: операция произведения ассоциативна (h(gf)=(hg)f для всех ), нейтральным элементом для этой операции является тождественное отображение 1U (1Uf=f=f1U для всех ), для всякой биекции существует обратный элемент — биекция g=f-1 (fg=1U=gf). (Другими словами, S(U) — группа относительно операции […]

Линейные преобразования линейных пространств столбцов, задаваемые (прямоугольной) матрицей

Рассмотрим линейные пространства столбцов над полем K (например, над полем R действительных чисел) Каждая -матрица F=(fij), , задает отображение , для всех где Теорема 7.0.6. Отображение задаваемое прямоугольной -матрицей F=(fij), обладает следующими свойствами: f(X+X’)=f(X)+f(X’) для всех \textup; f(cX)=cf(X) для всех , . Доказательство. Для имеем Применяя отображение f, определяемое прямоугольной матрицей F=(fij), к X+X’ и […]

Вычисление определителей

Определение определителя как суммы n! слагаемых-произведений плохо пригодно для реальных вычислений при больших n. В теоретическом плане важно отметить, что определитель |A| является многочленом от n2 переменных aij, в котором мономы входят с коэффициентами . Отметим лишь одно из следствий этого факта: если aij=aij(x) являются дифференцируемыми функциями от переменной x, то определитель |A| также является […]