Лекция №9 (26. 03. 10) 1 Преобразования и подстановки Определение



Скачать 54.64 Kb.
Дата22.12.2012
Размер54.64 Kb.
ТипЛекция



18.11.12, М.

Лекция № 9 (26.03.10)

6.1.5. Преобразования и подстановки

Определение. Отображение φ, отображающее множество A в себя, называется преобразо­ванием (множества A).

Во множестве всех преобразований данного множества A определена операция умножения (композиции). Она ассоциативна.

Определение. Биективное (или, равносильно, обратимое) преобразование называется под­становкою.

Произведение двух подстановок есть подстановка. Следовательно, на множестве всех под­становок также корректно определена операция умножения (композиции). Тождественное ото­бражение εA является подстановкою. Отображение, обратное к подстановке, всегда существует и также будет подстановкою. Следовательно, множество всех подстановок данного множества обра­зует группу относительно операции композиции отображений. (Группою называется множество объектов произвольной природы, на котором определена ассоциативная операция умножения, су­ществует единица и у каждого элемента есть обратный.)

6.1.6. Табличное обозначение преобразований

Если все элементы данного множества записаны без повторений в виде некоторой последо­вательности (так можно сделать, например, со множеством всех натуральных чисел N, а также с любым конечным множеством), то изобразить данное преобразование можно в виде таблички (матрицы), подобной, например, следующим:

; .

Инъективность отображения при такой форме записи означает, что в нижней строке все элементы различны, а сюръективность означает, что все элементы данного множества в нижней строке таблички присутствуют. Так, из двух вышеприведенных примеров видно, что первое ото­бражение сюръективно, но не инъективно, а второе инъективно, но не сюръективно.

Чаще всего подобное изображение преобразования применяют к конечным множествам. В дальнейшем будем считать, что данное множество A есть множество всех натуральных чисел от 1 до n, расположенное в естественном порядке, а изображать будем только подстановки. Тогда в нижней строке будут находиться те же числа, что и в верхней, но записаны они будут в некоторой перестановке. У тождественной подстановки нижняя строка совпадает с верхней.

Как перемножить две подстановки, записанные в табличном виде? Объясним это на при­мере. Пусть, например, , . Не забудем, что перестановки (как и лю­бые отображения) перемножаются справа налево.
Тогда

.

Если мы перемножим те же подстановки в обратном порядке, то получим другой результат:

.

Таким образом, умножение подстановок, вообще говоря, некоммутативно.

Определение. Неподвижным называется элемент, который данная подстановка переводит в себя (в тот же элемент). Все остальные элементы буду называть перемещаемыми.

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

.

Подстановки можно изображать в виде ориентированного графа.

6.1.7. Свойства подстановок

Если подстановка σ переставляет два элемента i и j, т. е. σ(i) = j, σ(j) = i, ij, а остальные элементы неподвижны, т. е. σ(k) = k при ki, j, то такая подстановка называется транспозициею (элементов i и j). Если вдобавок переставляемые элементы являются соседними, т. е. j = i + 1 или i = j + 1, то такую транспозицию назовём элементарною.

Если для двух элементов нижней строки σ(i) и σ(j) выполняются неравенства i < j, σ(i) > > σ(j), т. е. большее число стоит левее меньшего, то говорят, что эти два элемента нижней строки образуют инверсию. Подстановка называется чётною, если число инверсий в нижней строке её табличной записи чётно, и нечётною в противном случае.

Заметим, что любая транспозиция обратна самой себе: τ−1 = τ (равносильно: τ2 = εA).

Предложение 1. Умножение данной подстановки справа на транспозицию равносильно пе­рестановке соответствующих элементов нижней строки. В частности, умножение данной подста­новки справа на элементарную транспозицию переставляет соседние элементы.

Объясним на примере:

=.

В первом (левом) сомножителе по сравнению с исходной подстановкой (левой частью равенства) переставлены два элемента 5 и 6, а во втором (правом) сомножителе переставлены номера их по­зиций 6 и 2.

Предложение 2. Умножение данной подстановки справа на элементарную транспозицию меняет число инверсий на 1 (уменьшает, если соответствующие элементы образовывали инвер­сию, и увеличивает в противном случае).

Следовательно, умножение данной подстановки справа на элементарную транспозицию меняет чётность подстановки.

Предложение 3. Всякую нетождественную подстановку можно разложить в произведение элементарных транспозиций. При этом число сомножителей можно взять равным числу инверсий.

Доказательство индукцией по числу инверсий.

Если нет инверсий, то это тождественная подстановка. Если есть хотя бы одна инверсия, то не могут выполняться неравенства σ(1) < σ(2) < …  σ(n) (иначе σ = εA), а следовательно, для неко­торого k выполняется σ(k) > σ(k+1) (равенства не может быть в силу инъективности). Переставим эти элементы и получим новую подстановку σ1, а для компенсации умножим справа σ1 на соответ­ствующую элементарную транспозицию τ:

σ = σ1τ.

В подстановке σ1 будет уже на одну инверсию меньше. Если σ1 = ε, то, значит, в подста­новке σ была единственная указанная инверсия, т. е. σ сама является элементарной транспозицией и равенство σ = σ является искомым разложением (из одного сомножителя); в этом случае пред­ложение доказано (база индукции). Если же σ1 ≠ ε, то по предположению индукции σ1 можно раз­ложить в произведение элементарных транспозиций:

σ1 = τ1τ2…τs,

причем s равно числу инверсий в подстановке σ1.

Имеем:

σ = σ1τ = τ1τ2…τsτ.

Мы разложили подстановку σ в произведение s + 1 элементарной транспозиции, но в ней ровно столько же инверсий. Предложение доказано.

Предложение 4. Всякую транспозицию можно разложить в произведение нечётного числа элементарных транспозиций. Следовательно, всякая транспозиция нечётна.

Доказательство. Пусть дана какая-то транспозиция τ:

.

Рассмотрим пример, который покажет, как доказывать предложение в общем случае. До­пустим, необходимо переставить элементы 2 и 6. Проследим, как будет изменяться положение элементов в нижней строке:



Итого: 2k + 1 элементарная транспозиция. Таким образом, мы разложили транспозицию элементов 2 и 6 в произведение нечётного числа элементарных транспозиций.

Предложение 5. Умножение справа на транспозицию меняет чётность подстановки.

Доказательство. Умножение справа на транспозицию равносильно умножению справа на произведение нечётного числа элементарных транспозиций (предложение 4). Умножение справа на одну элементарную транспозицию меняет число инверсий на единицу. В общей сложности число инверсий изменится на нечётное число, что означает изменение чётности подстановки.

Предложение 6. При любом разложении подстановки в произведение транспозиций число сомножителей имеет ту же чётность, что и сама данная подстановка.

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

σ = τ1τ2…τs = τ1τ2…τs.

Если число сомножителей s чётно, то по предложению 5 чётное число раз переменится чёт­ность подстановки , т. е. подстановка σ чётна. Аналогично для нечётного s.

Предложение 7. Произведение двух подстановок одной чётности чётно. Произведение двух подстановок разной чётности нечётно.

Доказательство. Разложим обе подстановки произвольным образом в произведение транс­позиций. Допустим,

σ1 = τ1τ2…τs – чётная подстановка;

σ2 = – нечётная подстановка.

Из предложения 6 следует, что s чётно, а t нечётно.

σ1σ2 = τ1τ2…τs. s + t нечётно, следовательно, по предложению 6 подстановка σ1σ2 не­чётна. Аналогично в других случаях.

Предложение 8. Обратная подстановка имеет ту же чётность, что и данная.

Доказательство. Пусть σ – данная подстановка, σ−1 – обратная к σ. Рассмотрим произведе­ние:

σσ−1 = ε. (1)

Необходимо доказать, что σ и σ−1 имеют одну и ту же чётность. Допустим, σ и σ−1 имеют разную чётность, тогда левая часть равенства (1) нечётна по предложению 7, а правая – чётна, чего не может быть.


Похожие:

Лекция №9 (26. 03. 10) 1 Преобразования и подстановки Определение iconЦель вступительного экзамена
Отображения между множествами, преобразования и подстановки. Прямые произведения множеств. Бинарные отношения и некоторые их виды....
Лекция №9 (26. 03. 10) 1 Преобразования и подстановки Определение iconЭкзаменационные вопросы определение левой и правой систем координат. Определение радиус-вектора
Двумерные преобразования: операции переноса (трансляции), масштабирование, вращение
Лекция №9 (26. 03. 10) 1 Преобразования и подстановки Определение iconПреобразования в 2D пространстве Преобразования используются в разных целях
С аналитической точки зрения преобразования это пересчет значений координат. Двухмерные и трехмерные преобразования отличаются по...
Лекция №9 (26. 03. 10) 1 Преобразования и подстановки Определение iconМетоды и средства проектирования систем компьютерной алгебры как компоненты в моделях активного обучения программированию
В качестве базовых средств обсуждаются языковые составляющие ска, базовые преобразования и действия переобозначений. Основной упор...
Лекция №9 (26. 03. 10) 1 Преобразования и подстановки Определение iconРеферат на тему «Геометрические преобразования»
Геометрические преобразования являются достаточно поздним разделом математики. Первые геометрические преобразования стали рассматриваться...
Лекция №9 (26. 03. 10) 1 Преобразования и подстановки Определение iconЛекция 22. Числовые ряды. 22 Основные определения. Определение
Определение. Сумма членов бесконечной числовой последовательности называется числовым рядом
Лекция №9 (26. 03. 10) 1 Преобразования и подстановки Определение iconЛекция №4 (22. 09. 09) Определение
Определение. Координатами точки m (абсциссой, ординатой и аппликатой) на­зываются соответствующие координаты вектора (где o − начало...
Лекция №9 (26. 03. 10) 1 Преобразования и подстановки Определение iconО свойстве простой подстановки для суперинтуиционистских и модальных логик В. И. Хомич
Настоящее сообщение посвящено изучению введенного в работах [1,2] свойства простой подстановки, касающегося суперинтуиционистских...
Лекция №9 (26. 03. 10) 1 Преобразования и подстановки Определение iconЛекция 12. Первообразная и неопределённый интеграл. 12 Первообразная функция. Определение
Определение: Функция F(x) называется первообразной функцией функции f(x) на отрезке [a, b], если в любой точке этого отрезка верно...
Лекция №9 (26. 03. 10) 1 Преобразования и подстановки Определение iconЛекция Матрицы. Основные определения и типы матриц. Определение Матрицей А
...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org