АиГ2015-2016 / Лекции / Конспект лекций АиГ_ Реутова ИН_ Часть 1

	i1	i2	...	in		(2.1)
A
	i1	i2	...	in

Подстановка обладает многими различными записями вида (2.1). Любая подстановка А может быть записана в виде:

1		2	...	n
A					(2.2)
	1	2	...	n

Здесь 1 , 2 ,..., n - перестановка чисел 1, 2, 3, …, n.

Очевидно, что общее число подстановок степени n равно n!

Def. Подстановка называется четной (нечетной), если общее число инверсий в перестановках, образованных в верхней и нижней строках четно (нечетно).

Если подстановка записана в виде (2.2), то ее четность определяется четностью перестановки во второй строке, поскольку число инверсий в верхней строке равно нулю.

Def. Транспозицией подстановки называется транспозиция одной из перестановок в верхней или нижней строках (но не в обоих одновременно).

Отсюда следует, что всякая транспозиция меняет четность подстановки на противоположную. Число четных подстановок степени n равно числу нечетных подстановок и равно n! 2 .

Очевидным является следующее утверждение.

Th.2.4 Транспозиция любых столбиков в подстановке не меняет ее четности .

Def. Подстановка	1	2 ...	n	называется тождественной.
	E
	1	2 ...	n

Def. Применение одной подстановки вслед за другой тоже будет подстановкой, которую называют произведением первой из заданных подстановок на другую.

N. Пусть				A	1		2	3		4		и	B	1 2			3	4		. Найти	AB	и BA .
															3	2	4	1
						4	1	2		3
	1	2	3	4	,			1			2	3	4
AB							BA						.
	1	3	2	4					2		1	3	4

Свойства произведения подстановок:

1.Произведение подстановок некоммутативно, т.е. AB BA .

2.Произведение подстановок ассоциативно, т.е. AB C A BC .

3.Произведение любой подстановки на тождественную E , а также произведение тождественной подстановки E на равно A .

11

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

1)Доказательством некоммутативности является приведенный выше пример.

2)Докажем ассоциативность произведения подстановок. Пусть i1 A i2

(подстановка А переводит элемент

i1 в

элемент i2 ),

B

C

i2 i3 ,

i3 i4 .

Тогда,

AB

AB C

С

другой

стороны

BC

и

i1 i3 ,

а i1 i4 .

i2 i4

A BC

i1 i4 .

3)

1

2

...

n

E

1

2 ...

n

, то, перемножая эти

Если A

и

1

2

...

n

1

2 ...

n

подстановки, получаем, что AE EA A .

Def. Обратной

для подстановки А называется такая подстановка A 1 той же

самой степени, что A 1 A AA 1 E .

Очевидно,

что

для

подстановки

1

2

...

n

обратная

A

1

2

...

n

получается переменой строк, т.е.

				...			(2.3)
A 1	1		2			n .
	1	2		...	n

			a11	a12	...	a1n
				a22
	С каждой квадратной матрицей	A	a21		...	a2n	связано
			.	.	.	.
			an1	an2	...	ann

определенное число, называемое ее определителем или детерминантом, которое обозначается det A (или ) и записывается в следующей символьной форме:

		a11	a12	...	a1n
	det A	a21	a22	...	a2n	(2.4)
		.	.	.	.
		an1	an 2	...	ann

Определитель n-го порядка

Def. Определителем n-го порядка называется число, равное алгебраической сумме n! слагаемых, каждое из которых представляет произведение n множителей, взятых по одному и только по одному из каждой строки и

12

каждого столбца. Причем каждое слагаемое входит в сумму со знаком «+», если подстановка, состоящая из индексов множителей четная, и со знаком «–», если эта подстановка нечетная, т.е.:

det A		( 1) a 1 1 a 2 2 ...a n n		(2.5)
1	...	n
1	...	n
или
det A			( 1) a1 1 a2 2 ...an n ,	(2.6)
1	...	n
1	...	n

где – общее число инверсий в обеих строках подстановки.

В частности, определитель		второго	порядка		a11		a12	будет
					a21		a22
содержать два слагаемых:	a11a22 и	a12 a21 . Определим знаки этих слагаемых.
Подстановка из индексов	слагаемого a11a22		имеет вид	1	2		и	является
				1	2

четной. Значит, это слагаемое входит в определитель со знаком «+». Подстановка из индексов, соответствующая слагаемому a12 a21 имеет вид

1		2		и является нечетной. Т.е. второе слагаемое входит в определитель со
	2	1

знаком «–». Таким образом,

	a11	a12	a11a22 a12 a21	(2.7)
	a21	a22

Т.е. определитель второго порядка равен разности произведения элементов главной диагонали и элементов побочной диагонали.

Аналогично, определитель третьего порядка содержит 3!=6 слагаемых и вычисляется по формуле:

a11	a12	a13
a21	a22	a23	a11a22 a33 a12 a23a31 a13a21a32 a13a22 a31 a12 a21a33 a11a23a32 (2.8)
a31	a32	a33

Убедитесь самостоятельно в правильности знаков слагаемых в формуле (2.8). Для запоминания этой формулы используют схему:

Рис. 2.1. Схема вычисления определителя третьего порядка

13

Существует удобный способ вычисления определителя третьего порядка с помощью так называемого правила Саррюса. Допишем справа к определителю первые два столбца, а далее будем перемножать элементы, стоящие на одних диагоналях так, как показано на рисунке 2.2.

	a11	a12	a13	a11	a12
	a21	a22	a23	a21	a22
	a31	a32	a33	a31	a32
–		– –		+	+ +

Рис. 2.2 Правило Саррюса для вычисления определителя третьего порядка

Вычисление определителей более высоких порядков по определению представляется очень громоздким. Уже определитель 4-го порядка будет содержать 4!=24 слагаемых, а определитель 5-го порядка уже 5!=120 слагаемых. Далее мы сформулируем свойства определителей, которые облегчат их вычисление.

ЛЕКЦИЯ 3.

СВОЙСТВА ОПРЕДЕЛИТЕЛЕЙ.

Свойства определителей

Def. Транспонированием матрицы (определителя) называется такое ее преобразование, при котором ее строки становятся столбцами с теми же

норами. Для матрицы А транспонированная матрица обозначается AT .

a11	a12	...	a1n		a11	a21	...	as1
Если A a21	a22	...	a2n	, то	AT a12	a22	...	as 2		(3.1)
.	.	.	.		.	.	.	.
as1	as 2	...	asn		a1n	a2n	...	asn

Теоремы 3.1 – 3.8 выражают свойства определителей n-го порядка.

Th.3.1 Определитель не меняется при транспонировании.

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

Очевидно в результате транспонирования элементы, стоящие в разных строках и столбцах, остаются также в разных строках и столбцах. Пусть в det A входит слагаемое a 1 1 a 2 2 ...a n n , тогда это же слагаемое будет входить

14

и		в		det AT .			В det A	ему будет		соответствовать						подстановка
				...			, а в det AT	- подстановка					...			. Очевидно обе
	1		2			n				1		2			n
	1	2		...	n					1		2	...	n

подстановки имеют одинаковую четность. Значит, det A и det AT состоят из одних и тех же слагаемых, т.е. равны.

Замечание. Теорема 3.1. позволяет сделать вывод о равноправии строк и столбцов в определителе. Поэтому, доказательство остальных свойств будем проводить только для строк.

Th.3.2 Определитель, в котором одна строка (или столбец) состоит из нулей, равен нулю.

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

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

Th.3.3 Если в определителе поменять местами две строки (два столбца), то определитель изменит знак на противоположный.

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

Пусть дан определитель, в котором поменяли местами i-ю и j-ю строки:

	.	.	.	.
	a j1	a j 2 ...		a jn	i ñò ðî êà
	.	.	.	.	(3.2)
	ai1	ai 2 ...		ain	j ñò ðî êà
	.	.	.	.
Пусть a1 1 a2 2 ...ai i ...a j j			...an n	–	произвольное слагаемое исходного

определителя. Ему соответствует подстановка:

1		2	...	i	...	j	...	n	(3.3)
	1	2	...	i	...	j	...	n

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

1		2	...	j	...	i	...	n	(3.4)
	1	2	...	i	...	j	...	n

Подстановки (3.3) и (3.4) имеют различную четность, т.к. получаются друг из друга с помощью одной инверсии в верхней строке. Значит,

15

слагаемые вида a a ...a ...a ...a будут входить в полученный

1 1 2 2 i i j j n n

определитель с противоположным знаком, т.е. определитель поменяет знак.

Th.3.4	Если определитель содержит две равные строки (столбца),
	то он равен нулю..

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

Пусть определитель равен . Поменяем местами две равные строки. С одной стороны, согласно теореме 3.3, его значение станет равным , а с другой стороны не изменится. Имеем , откуда 0 .

Th.3.5 Если все элементы некоторой строки (столбца) определителя умножить на число k, то определитель умножится на k.

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

				a11	a12	...	a1n
				.	.	.	.
		det A		kai1	kai 2	...	kain					( 1) a1 1 ...kai i ...an n
				.	.	.	.		1	...	n
									1	...	n
				an1	an2	...	ann
									a11		a12	...	a1n
									.		.	.	.
k			( 1) a1 1 ...ai i			...an n k			ai1		ai 2	...	ain	.
1		...	n						.		.	.	.
	1
		...	n
									an1	an 2		...	ann

Замечание. Теорема 3.5 позволяет выносить из какой-либо строки (столбца) общий множитель за знак определителя.

	Th.3.6		Если		определитель				содержит две пропорциональные
			строки(столбца), то он равен нулю.
Доказательство.
		.	.	.		.	. . .
	.
	ai1	ai 2	...	ain	Th 3.5	ai1	ai 2	...	ain	Th 3.4
	.	.	.	.	k	.	.	.	.	0.
	kai1	kai 2	...	kain		ai1	ai 2	...	ain
	.	.	.	.		.	. . .

16

Th.3.7 Если все элементы некоторой строки (столбца) определителя представлены в виде суммы двух слагаемых, то определитель равен сумме двух определителей, в первом из которых элементами этой строки (столбца) служат первые слагаемые, а во втором – вторые слагаемые. Все остальные элементы совпадают с элементами исходного определителя.

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

	a11			a12		...	a1n
		.	.			.	.
det A	bi1	ci1	bi 2 ci 2			... bin cin							( 1) a1 1 ...(bi i			ci i )...an n
		.	.			.	.			1	...	n
										1 ...		n
	an1			an2		...	ann
			( 1) a1 1 ...bi i				...an n					n	( 1) a1 1 ...ci i ...an n
	1 ...		n							1	...
	1 ...		n							1	...	n
				a11	a12	...	a1n			a11	a12		...	a1n
				.	.	.	.			.		.	.	.
				bi1	bi 2	...	bin			ci1	ci 2		...	cin	.
				.	.	.	.			.		.	.	.
				an1	an2	...	ann			an1	an 2		...	ann

Th.3.8 Если к какой-нибудь строке (столбцу) определителя прибавить другую строку, умноженную на произвольное число, то определитель не изменится.

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

Прибавим к i-й строке j-ю строку, умноженную на число k. Получим:

.

.

.

.

.

.

.

.

.

.

.

.

ai1 ka j1

ai 2 ka j 2

...

ain ka jn

Th 3.7

ai1

ai 2

...

ain

ka j1

ka j 2

...

ka jn

.

.

.

.

.

.

.

.

.

.

.

.

a j1

a j 2

...

a jn

a j1

a j 2

...

a jn

a j1

a j 2

...

a jn

.

.

.

.

.

.

.

.

.

.

.

.

17

	.	.	.	.		.	.	.	.		.	.	.	.
Th 3.5	ai1	ai 2	...	ain		a j1	a j 2	...	a jn	Th 3.4	ai1	ai 2	...	ain
	.	.	.	.	k	.	.	.	.		.	.	.	.	0
	a j1	a j 2	...	a jn		a j1	a j 2	...	a jn		a j1	a j 2	...	a jn
	.	.	.	.		.	.	.	.		.	.	.	.

	.	.	.	.
	ai1	ai 2	...	ain
	.	.	.	.	.
	a j1	a j 2	...	a jn
	.	.	.	.

Def. Матрица, у которой все элементы, стоящие под (над) главной диагональю равны 0 называют верхней треугольной (нижней треугольной)

матрицей.

a11		a12	...	a1n
	0	a22	...	a2n
.		.	.	.
	0	0	...	ann

Верхняя треугольная матрица

a11	0	...	0
a21	a22	...	0
.	.	.	.
an1	an2	...	ann

Нижняя треугольная матрица

Th.3.9	Определитель				верхней			треугольной		матрицы равен
	произведению элементов главной диагонали.
Доказательство.
		a11		a12	...	a1n
Докажем, что			0	a22	...	a2n	a a	22	...a .	(3.5)
			.	. .		.	11		nn
			0	0	...	ann
Очевидно, что			произведение				a11a22 ...ann будет			одним из слагаемых

определителя, взятым со знаком «+», т.к. соответствующая ему подстановка

1	2	...	n	– четная.
1	2	...	n
	Пусть a1 1 a2 2 ...an n – произвольное слагаемое определителя, не равное 0.
Тогда		1 1 ,		2 2 , ..., n n	(поскольку элементы, у которых i i ,

18

расположены	ниже главной диагонали, т.е.	равны 0). Но
1 2 ... n	1 2 ... n . Значит, 1 1, 2 2, ..., n	n . Таким образом,
определитель содержит лишь одно ненулевое слагаемое a1 1 a2 2 ...an n .

Следствие. Определитель нижней треугольной матрицы равен произведению элементов главной диагонали, т.е.

	a11	0	...	0
	a21	a22	...	0	a11a22	...ann .	(3.6)
	.	.	.	.
	an1	an2	...	ann

ЛЕКЦИЯ 4.

МИНОРЫ И АЛГЕБРАИЧЕСКИЕ ДОПОЛНЕНИЯ. ВЫЧИСЛЕНИЕ ОПРЕДЕЛИТЕЛЕЙ. ПРАВИЛО КРАМЕРА.

Миноры и алгебраические дополнения

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

Def. Если вычеркнуть строки и столбцы, на пересечении которых находится минор М, то оставшиеся элементы образуют матрицу порядка n-k, определитель которой называется дополнительным минором к минору М и обозначается M .

В частности, дополнительный минор к элементу aij обозначается Mij .
Def. Пусть минор k-го порядка расположен в строках с номерами i1 , i2 , ..., ik				и
в столбцах с номерами			j1 , j2 , ..., jk . Обозначим
		sM	i1 i2 ... ik j1 j2 ... jk
Алгебраическим дополнением для минора М называют число ( 1)sM M .
В частности, алгебраическое дополнение к элементу aij обозначается				Aij
и A ( 1)i j M	ij	.
ij

19

	1	2	1	0	3
	3	2	1	1	1
N. Пусть дан определитель	0	0	2	3	1	.
	4	2	1	1	0
	3	1	1	1	1

M		0	3		– минор	2-го		порядка, M			1	1	3		– дополнительный
											3	1	1
		2	1								3	1	1
						1	1	3
минор к M ,					( 1)3 4 2 4	3	1	1	– алгебраическое дополнение для M .
						3	1	1

Смысл алгебраического дополнения становится ясен из следующей леммы.

Lemma Произведение любого минора определителя на его алгебраическое дополнение есть сумма, слагаемые которого являются некоторыми членами определителя

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

1) Рассмотрим сначала случай, когда выбранный минор k-го порядка расположен в верхнем левом углу определителя.

	a11		...	a1k		a1k 1	...	a1n
	.		M	.		.	.	.
	ak1		...	akk		ak k 1	...	akn
	ak								1n
		11	...	ak 12		ak 1k 1	...	ak
	.		.	.		.	M	.
	an1		...	ank		an k 1	...	ann
Произвольный член минора М имеет вид ( 1)l a									a		...a	, где l – число
								1 1	2 2			k k

инверсий в перестановке 1 , 2 ,..., k . Произвольный член его дополнительного минора M имеет вид ( 1)t ak 1 k 1 ak 2 k 2 ...an n , где t – число

инверсий в перестановке k 1 , k 2 ,..., n .

Члены алгебраического дополнения будут получены из членов минора

M умножением

на

( 1)sM

( 1)1 ...k 1 ...k

( 1)2(1 ...k ) 1 ,

т.е. будут

равны

членам дополнительного минора.

Произведение

членов

M

и

M

имеют

вид

( 1)l t a

a

2

...a

k

a

k 1

a

k 2

...a

n

.

1

2

k

k 1

k 2

n

1

20