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

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

Мы получили два эквивалентных определения определителя третьего порядка (формулы (4) и (5)). С помощью (4) определитель 3-го порядка вводится с помощью определителей второго порядка (разложение по столбцу). При этом легко проверяется, что все столбцы равноправны. Аналогично рекуррентным образом можно определить определитель n-го порядка (определитель квадратной матрицы n-го порядка), т. е.

=

= (7)

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

Определение 5. Перестановкой Из N Чисел (или N символов) называется расположение этих чисел (или символов) в любом определённом порядке (без повторений).

Теорема 1. Число перестановок из N Символов равно n!

Доказательство. Составляя перестановку, в качестве первого её элемента можно выбрать точно n символов. Если первый элемент выбран, то в качестве второго элемента можно выбрать любой из оставшихся (n – 1) символов. Следовательно, первые два места можно заполнить n×(n – 1 ) способами. Если два места в перестановке уже заполнены, то на третье место можно поставить любой из оставшихся (n – 2) символов. Следовательно, первые три места можно заполнить n×(n – 1)×(n – 2 ) способами. Продолжая этот процесс, получим, что все n мест в перестановке можно заполнить n×(n – 1)×(n – 2)×…×3×2×1 = n! способами.

Говорят, что числа К и Р образуют в перестановке (…К…р…) Инверсию, если К > Р, Но в перестановке К стоит раньше Р. Перестановка называется Чётной, если она содержит чётное число инверсий. Перестановка называется Нечётной, если она содержит нечётное число инверсий.

Пример. 1) Перестановка (9, 7, 1, 3, 4, 8, 5, 2, 6) чётная. В ней число 9 образует инверсии со всеми стоящими за ней числами, их 8. Число 7 образует новые инверсии со всеми стоящими за ней числами, кроме числа 8, их 6. Число 1 не образует ни одной новой инверсии. Числа 3 и 4 образуют по одной новой инверсии с числом 2. Число 8 образует ещё инверсии с 5, 2 и 6, их 3. Число 5 образует инверсию с числом 2. Итак, получается 8 + 6 + 1 + 1 + 3 + 1 = 20 инверсий.

2) Перестановка ( 2, 1, 3, 5, 4, 6, 9, 8, 7) нечётная. В ней инверсии образуют пары чисел 2 и 1, 5 и 4, 9 и 8, 9 и 7, 8 и 7. Получилось 5 инверсий.

Если в перестановке два символа поменять местами, а все остальные символы оставить на старых местах, то получим новую перестановку. Это преобразование перестановки называется Транспозицией.

Теорема 2. Всякая транспозиция меняет чётность перестановки.

Доказательство. Пусть в перестановке символы К и Р меняются местами. При этом возможны два случая.

1) Символы К и Р В данной перестановке стоят рядом, т. е. (…К, Р …). После транспозиции получится перестановка (….Р, к …). Если К и Р Составляли инверсию в данной перестановке, то после инверсии они уже не будут составлять инверсию и наоборот. Число инверсий, которые К и Р Составляли в данной перестановке с остальными символами, не изменится. Следовательно, число инверсий изменится на 1, т. е. чётность перестановки изменится.

2) Символы К и Р В данной перестановке стоят не рядом, т. е. (….К,…,р…). После транспозиции получится перестановка (…Р,…,к…). Число инверсий, которые К и Р Составляли в данной перестановке с символами, стоящими перед К И после Р, не изменится. Если между К и Р Стоят M символов, то переставить К и Р можно следующим образом: переставить К последовательно с каждым из этих M Символов, затем переставить К и Р, затем в обратном порядке переставить Р с каждым из этих M символов. Получим 2m + 1 транспозиций соседних символов. По доказанному каждая из них меняет чётность перестановки. Итак, чётность перестановки изменилась.

Следствие. При n > 1 число чётных перестановок равно числе нечётных перестановок и равно 0,5×n!.

Определение 6. Подстановкой из N символов ( или Подстановкой N-ой степени) называется любое взаимнооднозначное отображение множества этих символов на себя.

Элементы данного множества будем обозначать 1, 2, …, n. Подстановка А может быть записана так: если число К переходит в число aК, то А = . Если в записи подстановки А Некоторые столбцы поменять местами, то получится то же самое отображение данного множества, т. е. та же подстановка. Например,

А = = .

Запись подстановки А = будем называть стандартной. Всякую подстановку можно записать в стандартном виде. Верхнюю и нижнюю строки подстановки можно рассматривать как перестановки. Подстановка А называется чётной, если её верхняя и нижняя строки есть перестановки одинаковой чётности, т. е. общее число инверсий в них – чётное. В противном случае А Называется Нечётной. Так как перестановка столбцов равносильна транспозиции как в верхней так и в нижней строке, то при перестановке столбцов чётность подстановки не изменится, поэтому чётность подстановки можно вычислять по её стандартному виду и в этом случае она совпадает с чётностью нижней строки.

Подстановка Е = называется Тождественной Или Единичной.

Произведением двух подстановок одного и того же порядка называется результат последовательного выполнения тех отображений, которые задают эти подстановки. Например, если А = , В = , то

А×В = . Действительно, первая подстановка переводит 1 в 5, вторая переводит 5 в 4, следовательно, окончательно 1 перейдёт в 4. Аналогично, , , следовательно, ; , , следовательно, ; , , следовательно, ; , , следовательно, ; , , следовательно, .

Аналогично получаем, что В×А = . Отсюда следует, что умножение подстановок не подчиняется коммутативному закону. Но можно проверить, что (А×В)×С = А×(В×С) для любых подстановок А, В, С Одного и того же порядка. Очевидно, А×Е = Е×А для любой подстановки А, Если А и Е Одного порядка. Для подстановок А = и В = очевидно А×В = В×А = Е. Следовательно, А-1 = В, т. е. каждая подстановка имеет обратную.

Источник

Перестановки и подстановки. Методы вычисления определителей n-го порядка

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

Методы вычисления определителей n-го порядка.

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

Так как каждый элемент определяется своим номером, то будем говорить, что дано n натуральных чисел.

Число различных перестановок из n чисел равно n!

Если в некоторой перестановке из n чисел число i стоит раньше j, но i > j, т. е. большее число стоит раньше меньшего, то говорят, что пара i, j составляет инверсию.

Пример 1. Определить число инверсий в перестановке (1, 5, 4, 3, 2)

Числа 5 и 4, 5 и 3, 5 и 2, 4 и 3, 4 и 2, 3 и 2 образуют инверсии. Общее число инверсий в данной перестановке равно 6.

Перестановка называется чётной, если общее число инверсий в ней чётное, в противном случае она называется нечётной. В рассмотренном выше примере дана чётная перестановка.

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

От любой перестановки из n чисел можно перейти к любой другой перестановке из этих чисел с помощью нескольких транспозиций.

Всякая транспозиция меняет чётность перестановки.

При n ≥ 2 число чётных и нечётных перестановок из n чисел одинаково и равно .

Пусть М – упорядоченное множество из n элементов. Всякое биективное преобразование множества М называется подстановкой n-й степени.

Подстановки записывают так: , где ik , и все ik различны.

Подстановка называется чётной, если обе её строки (перестановки) имеют одинаковые чётности, т. е. либо обе чётные, либо обе нечётные. В противном случае подстановка называется нечётной.

При n ≥ 2 число чётных и нечётных подстановок n-й степени одинаково и равно .

Определителем квадратной матрицы А второго порядка А= называется число, равное =а11а22–а12а21.

Определитель матрицы называют также детерминантом. Для определителя матрицы А используют следующие обозначения: det A, ΔA.

Определителем квадратной матрицы А= третьего порядка называют число, равное │А│=а11а22а33+а12а23а31+а21а13а32‑а13а22а31‑а21а12а33‑а32а23а11

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

«+» «—»

Пример 2. Вычислить определитель 3-го порядка по правилу треугольника

.

Пусть А – матрица n-го порядка с комплексными элементами:

А=

Рассмотрим всевозможные произведения элементов матрицы А, взятых по одному из каждой строки и каждого столбца: (1). Эти произведения будем называть членами определителя . По каждому члену (1) составим подстановку (2).

Определителем n-го порядка, или определителем квадратной матрицы А=(aij) при n>1, называется алгебраическая сумма всевозможных произведений вида (1), причём произведение (1) берётся со знаком «+», если соответствующая ему подстановка (2) чётная, и со знаком «‑», если подстановка нечётная.

Минором Мij элемента aij определителя называется определитель, полученный из исходного вычёркиванием i-й строки и j—го столбца.

1. Определитель не изменяется при замене всех строк соответствующими столбцами (определитель не изменится при транспонировании).

2. При перестановке двух строк (столбцов) определитель меняет знак.

3. Определитель с двумя одинаковыми (пропорциональными) строками (столбцами) равен нулю.

4. Общий для всех элементов строки (столбца) множитель можно вынести за знак определителя.

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

6. Если все элементы некоторой строки (столбца) определителя равны нулю, то он равен нулю.

7. Определитель равен сумме произведений элементов любой строки (столбца) на их алгебраические дополнения (свойство разложения определителя по строке (столбцу)).

Рассмотрим некоторые способы вычисления определителей порядка n.

1. Если в определителе n-го порядка хотя одна строка (или столбец) состоят из нулей, то определитель равен нулю.

2. Пусть в определителе n-го порядка какая-то строка содержит отличные от нуля элементы. Вычисление определителя n-го порядка можно свести в этом случае к вычислению определителя порядка n-1. Действительно, используя свойства определителя, можно все элементы какой-либо строки, кроме одного, сделать нулями, а затем разложить определитель по указанной строке. Например, переставим строки и столбцы определителя так, чтобы на месте а11 стоял отличный от нуля элемент.

.

Тогда первый столбец умножаем на и прибавляем ко второму, далее первый столбец, умноженный на , прибавляем к третьему и т. д. Получаем определитель вида

Заметим, что переставлять строки (или столбцы) не обязательно. Можно нули получать в любой строке (или столбце) определителя.

Общего метода вычисления определителей порядка n не существует, если не считать вычисление определителя заданного порядка непосредственно по определению. К определителю того или иного специального вида применяются различные методы вычисления, приводящие к более простым определителям.

3. Приведем к треугольному виду. Пользуясь свойствами определителя, приводим его к так называемому треугольному виду, когда все элементы, стоящие по одну сторону от главной диагонали равны нулю. Полученный определитель треугольного вида равен произведению элементов, стоящих на главной диагонали. Если удобнее получить нули по одну сторону от побочной диагонали, то он будет равен произведению элементов побочной диагонали, взятому со знаком . Действительно, произведение а1n, а2n-1, …, an1 является членом определителя и его знак определяет (-1)s, где s – число инверсий в перестановке (n, n-1, n-2,…, 2, 1). Следовательно, s=n-1+n-2+…+1=.

Пример 3. Вычислить определитель разложением по строке

.

Разложим данный определитель по первой строке:

Пример 4. Вычислить определитель четвёртого порядка

.

1-й способ (вычисление определителя путём сведения его к треугольному виду):

Приведём определитель к треугольному виду, умножив первую строку последовательно на (‑1), 1, (‑2) и сложив соответственно со второй, третьей и четвёртой строками.

.

2-й способ (вычисление определителя путём разложения его по строке):

Вычислим этот определитель разложением по строке, предварительно преобразовав его так, чтобы в какой-то его строке все элементы кроме одного обратились в ноль. Для этого прибавим первую строку определителя к третьей. Затем умножим третий столбец на (‑5) и сложим с четвёртым столбцом. Преобразованный определитель раскладываем по третьей строке. Минор третьего порядка приводим к треугольному виду относительно главной диагонали.

.

Пример 5. Вычислить определитель n-ого порядка

Вычтем из первой строки вторую, из второй – третью и т. д., наконец, из предпоследней последнюю (последняя строка остается без изменений).

Элементы последней строки представим в виде сумм двух слагаемых 0+1, 0+1, …, 0+1, (n-1)+1. Применив свойство (аддитивности), будем иметь

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

=(n–1)n+(n–1)n + nn-1.

4. Вычисление определителя с помощью теоремы Лапласа. Если в определителе выделить k строк (или столбцов) (1£k£n-1), то определитель равен сумме произведений всех миноров k-ого порядка, расположенных в выделенных k строках (или столбцах), на их алгебраические дополнения.

Пример 6. Вычислить определитель

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

ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ №2

«ВЫЧИСЛЕНИЕ ОПРЕДЕЛИТЕЛЕЙ N-ГО ПОРЯДКА»

.

.

.

Источник