АГ ПЗ 1-35 (полный вариант). Практическое занятие 1 Решето Эратосфена

• Название: Практическое занятие 1 Решето Эратосфена
• Анкор: АГ ПЗ 1-35 (полный вариант).pdf
• Дата: 23.02.2018
• Размер: 2.3 Mb.
• Имя файла: АГ ПЗ 1-35 (полный вариант).pdf
• Тип: Занятие; #15834
• страница: 37 из 44

Практическое занятие 29
Определители
Теорминимум: перестановки конечного множества, их количество, инверсии, чет- ность перестановки, транспозиция и ее свойства, определитель, член определителя и его знак. Правило знаков.
п.1 Теория
п.1.1 Перестановки
Определение. Перестановкой множества из n элементов называется любой упорядоченный набор из всех элементов этого множества, сре- ди которых нет одинаковых.
Под множеством из n элементов мы будем понимать множество
M {1, 2, ..., n}

Пример.
Упорядоченные наборы:
(1, 2, 3, 4, 5), (5, 2, 1, 4, 3), (2, 5, 4, 1, 3) являются перестановками множества M, а наборы
(3, 2, 1, 5), (3, 2, 1, 4, 3), (3, 2, 6, 4, 5) не являются перестановками множества М.
Определение.__Перестановка_(1,_2,_...,_n)_называется_первоначальной_перестановкой_множества_из_n_элементов._Теорема.'>Определение.
Перестановка (1, 2, ..., n) называется первоначальной перестановкой множества из n элементов.
Теорема.
(О количестве перестановок.) Существует ровно n! переста- новок множества из n элементов.
Определение.
Говорят, что пара чисел (i, j) образуют в перестановке инверсию, если i j
 , но число i находится в перестановке левее числа j.
Пример.
В перестановке (2, 5, 4, 1, 3) инверсию образуют пары чисел
(2, 1), (5, 4), (5, 1), (5, 3), (4, 1) и (4, 3).
Произвольную перестановку из n элементов обозначают:
1 2
n
( i , i , ..., i ) .
Здесь каждое число перестановки обозначают буквой с нижним ин- дексом. Индекс показывает, в каком месте перестановки стоит данное число. Например, число
3
i стоит в перестановке третьим по счету.
Головизин В.В. ПЗ по курсу «Алгебра и геометрия», ПЗ 29, УдГУ, Ижевск – 2011, с.13 2
Число (количество) всех инверсий в перестановке
1 2
n
( i , i , ..., i ) мы бу- дем обозначать
1 2
n
( i , i , ... , i )

Так, например, (2, 5, 4,1, 3) 6

 .
Теорема.'>Пример.'>Определение.
Перестановка называется четной, если число ее инвер- сий четно, и нечетной в противном случае.
Пример.
Так как (2, 5, 4,1, 3) 6

 , а (2, 5, 4, 3,1) 7

 , то перестановка
(2, 5, 4, 1, 3) четная, а (2, 5, 4, 3, 1) – нечетная.
Определение.
Транспозицией называется действие, заключающееся в том, что в перестановке два каких-либо числа меняют местами друг с другом.
Обозначение:
(i j)
(... i ... j...)
(... j... i ...)

Пример.
(15)
(1, 2, 3, 4, 5)
(5, 2, 3, 4, 1)

Теорема.
(О транспозиции соседних элементов перестановки.) Любая транспозиция соседних элементов перестановки меняет четность пе- рестановки на противоположную.
Теорема.
(О транспозиции произвольных элементов перестановки.)
Любая транспозиция любых двух элементов перестановки меняет четность перестановки на противоположную.
Теорема.
(О первоначальной перестановке.) Любую перестановку можно получить из начальной перестановки последовательным вы- полнением конечного числа транспозиций, причем это количество транспозиций есть число четное, если данная перестановка четна, и нечетное в противном случае.
Пример.
(1 2)
(2 5)
(3 4)
(2, 5, 4,1, 3)
(1, 5, 4, 2, 3)
(1, 2, 4, 5, 3)



(3 4)
(4 5)
(1, 2, 3, 5, 4)
(1, 2, 3, 4, 5)



Головизин В.В. ПЗ по курсу «Алгебра и геометрия», ПЗ 29, УдГУ, Ижевск – 2011, с.13 3
Здесь, перестановка (2, 5, 4, 1, 3) приведена к начальной за
4 транспозиции и она четная, так как (2, 5, 4,1, 3) 6

 .
Замечание.
Понятно, что любую перестановку можно привести к на- чальной и обратно с помощью тех же самых транспозиций, выпол- ненных в обратном порядке.
Теорема.
(О количестве четных и нечетных перестановок.) Количест- во четных перестановок множества из n элементов равно количеству нечетных и равно n!
2
п.1.2 Определитель n-го порядка
Пусть дана квадратная матрица n-го порядка над полем  :
11 12 1n
21 22 2n m1
m2
mn a
a
... a a
a
... a
A
a a
... a













Определение.
Произведение n элементов матрицы А, взятых в точно- сти по одному из каждой строки и каждого столбца называется чле- ном определителя матрицы А.
Обозначение:
1 2
n
1i
2i n i a
a
... a

 
Здесь первый индекс обозначает номер строки, из которой взят элемент, второй индекс k
i , который в свою очередь имеет нижний ин- декс k 1, 2, ..., n

, обозначает номер столбца, из которой взят элемент, и набор вторых индексов образует перестановку
1 2
n
{ i , i , ... , i } множе- ства из n элементов: M {1, 2, ..., n}

Так как число всех перестановок множества M {1, 2, ..., n}

равно n!, то существует ровно n! членов определителя. Каждый член опре- делителя снабдим знаком плюс или минус, в зависимости от четности или нечетности перестановки вторых индексов. Это можно сделать с помощью множителя
1 2
n
(i , i ,...,i )
( 1)


, который равен 1, если перестановка
Головизин В.В. ПЗ по курсу «Алгебра и геометрия», ПЗ 29, УдГУ, Ижевск – 2011, с.13 4
1 2
n
( i , i , ... , i ) четная и тогда число инверсий
1 2
n
(i , i , ... , i )

есть четное число и равен –1, если перестановка
1 2
n
( i , i , ... , i ) нечетная и тогда число инверсий
1 2
n
(i , i , ... , i )

есть нечетное число.
Определение.
Определителем (детерминантом) n-го порядка или оп- ределителем (детерминантом) квадратной матрицы n-го порядка на- зывают алгебраическую сумму всех членов определителя данной мат- рицы, взятых со своими знаками.
Обозначение:
11 12 1n
21 22 2n n1
n 2
nn a
a
... a a
a
... a det A
a a
... a


1 2
n
1 2
n
1 2
n
( j , j ,..., j )
1 j
2 j n j
( j , j ,..., j )
( 1)
a a
... a




 

, (1) где суммирование ведется по всем перестановкам столбцов.
Пример.
Вычислим определитель 3 – го порядка:
11 12 13 21 22 23 31 32 33
a a
a a
a a
a a
a
Выпишем все члены определителя, их ровно 6 штук. Для этого, вы- пишем сначала все перестановки множества из 3 элементов:
(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) и определим их четность:
(1, 2, 3) 0, (1, 3, 2) 1, (2, 1, 3) 1, (2, 3, 1) 2







 ,
(3, 1, 2) 2, (3, 2, 1) 3



 .
Теперь выписываем члены определителя, причем первые индексы
(номера строк) образуют начальную перестановку, а вторые индексы
(номера столбцов) образуют перестановку, одну из 6 приведенных выше.
11 22 33 11 23 32 12 21 33
a a
a , a a
a , a a
a






12 23 31 13 21 32 13 22 31
a a
a , a a
a , a a
a







Головизин В.В. ПЗ по курсу «Алгебра и геометрия», ПЗ 29, УдГУ, Ижевск – 2011, с.13 5
Теперь мы можем записать определитель, как алгебраическую сумму всех членов определителей, взятых со знаком плюс, если вторые ин- дексы сомножителей, входящих в член определителя, образуют чет- ную перестановку, и со знаком минус в противном случае:
11 12 13 21 22 23 11 22 33 12 23 31 13 21 32 31 32 33
a a
a a
a a
a a
a a
a a
a a
a a
a a










13 22 31 11 23 32 12 21 33
a a
a a
a a
a a
a









Замечание.
Формула (1) определяет отображение из множества всех квадратных матриц n-го порядка над полем  в поле  . Это отобра- жение называется определителем или детерминантом и обозначается n
det : M ( )


 .
Теорема.
(Правило знаков.)
1 1 2 2
n n m
i j i j i j n!
det A
( 1) a a
... a



 

, где
1 2
n
1 2
n m
( i , i , ... , i )
( j , j , ..., j )
 
 
и суммирование происходит по всем членам определителя.
п.2 Список задач
Список №1
1. Выяснить, образует ли перестановку данный упорядоченный набор чисел.
2. Найти все перестановки множества из двух, трех и четырех элемен- тов.
3. Выписать все пары чисел, образующих инверсию в данной переста- новке.
4. Вычислить количество инверсий в перестановке и определить её четность.
5. Выполнить заданную транспозицию в перестановке.
6. С помощью транспозиций привести данную перестановку к началь- ной перестановке и определить её четность.
7. Выяснить, является ли данное произведение членом определителя.
8. Определить знак данного члена определителя.
9. Вычислить определитель пользуясь его определением.
Головизин В.В. ПЗ по курсу «Алгебра и геометрия», ПЗ 29, УдГУ, Ижевск – 2011, с.13 6
Список №2
Задачи списка №1, содержащие произвольное количество чисел и за- дачи на доказательство.
п.3 Примеры
Пример 1.
Какие из следующих упорядоченных наборов чисел обра- зуют перестановку множества {1,2,3,4,5,6}: а) (2, 1, 3, 5, 4, 1, 6); б) (2, 3, 5, 4, 6); в) (2, 3, 5, 4, 1, 6)?
Решение. В наборе а) число 1 встречается два раза, а в наборе б) число
1 отсутствует, поэтому эти наборы чисел не являются перестановками множества {1,2,3,4,5,6}. В наборе в) все числа данного множества встречаются в точности по одному разу без повторений и пропусков, и поэтому этот набор чисел является перестановкой данного множества.
Ответ: в)
Пример 2
. Выписать все пары чисел, образующих инверсию в пере- становке (1, 3, 2, 5, 4, 6).
Ответ: (3, 2), (5, 4).
Пример 3.
Определить четность перестановки
(1, 3, 2, 5, 4, 6).
Решение. Число пар, образующих инверсию в данной перестановке равно двум (смотрите предыдущий пример):
(1,3,2,5,4,6) 2

 .
Ответ: четная.
Пример 4.
Выполнить транспозицию (15) в перестановке (1, 3, 2, 5, 4,
6).
Решение.
(15)
(1,3,2,5,4,6)
(5,3,2,1,4,6)

Ответ: (5, 3, 2, 1, 4, 6).
Пример 5.
Привести перестановку (2, 4, 6, 1, 3, 5) к первоначальному виду с помощью транспозиций и определить её четность.
Решение.
(12)
(24)
(36)
(2,4,6,1,3,5)
(1,4,6,2,3,5)
(1,2,6,4,3,5)



(36)
(56)
(1,2,3,4,6,5)
(1,2,3,4,5,6)


. Для приведения перестановки к пер- воначальному виду нам понадобилось 4 транспозиции. Следователь-

Головизин В.В. ПЗ по курсу «Алгебра и геометрия», ПЗ 29, УдГУ, Ижевск – 2011, с.13 7 но, перестановка (2, 4, 6, 1, 3, 5) является четной.
Ответ: четная.
Пример 6.
Найти знак члена определителя 5-го порядка: а)
12 24 33 41 53
a a a a a ; б)
12 24 31 43 55
a a a a a ; в)
31 24 53 15 42
a a a a a .
Решение. а) Первые индексы расположены по возрастанию, выписы- ваем последовательность вторых индексов:
(2, 4, 3, 1, 3).
Эта последовательность не образует перестановку множества {1, 2, 3,
4, 5}, так как число 3 встречается в ней два раза. б) Так как первые индексы образуют первоначальную перестановку, то выписываем последовательность вторых индексов:
(2, 4, 1, 3, 5).
Эта последовательность чисел образует перестановку множества {1, 2,
3, 4, 5}. Найдем её четность. Выпишем все пары чисел, которые обра- зуют в этой перестановке инверсию:
(2, 1), (4, 1), (4, 3).
Количество пар образующих инверсию нечетное число, следователь- но, перестановка вторых индексов является нечетной, а сам член оп- ределителя имеет знак «минус». в) Выписываем последовательности первых и вторых индексов:
(3, 2, 5, 1, 4), (1, 4, 3, 5, 2).
Обе последовательности образуют перестановку множества {1, 2, 3, 4,
5}, поэтому данное произведение является членом определителя 5-го порядка. Вычислить знак этого члена можно двумя способами.
1-й способ. Находим четность каждой перестановки. Приведем каж- дую перестановку к первоначальному виду с помощью транспозиций:
(13)
(35)
(45)
(3,2,5,1,4)
(1,2,5,3,4)
(1,2,3,5,4)
(1,2,3,4,5)



,
(24)
(45)
(1,4,3,5,2)
(1,2,3,5,4)
(1,2,3,4,5)


Перестановка первых индексов нечетная, вторых индексов – четная, т.е. (3,2,5,1,4)

– нечетное число, а (1,4,3,5,2)

– четное, и знак чле- на определителя
31 24 53 15 42
a a a a a равен:
(3,2,5,1,4)
(1,4,3,5,2)
( 1)
1



  .
2-й способ. Переставим сомножители в данном члене определителя таким образом, чтобы первые индексы образовали первоначальную перестановку:
Головизин В.В. ПЗ по курсу «Алгебра и геометрия», ПЗ 29, УдГУ, Ижевск – 2011, с.13 8
15 24 31 42 53
a a a a a .
Выписываем получившуюся перестановку вторых индексов:
(5, 4, 1, 2, 3), и определяем её четность:
(15)
(24)
(35)
(5,4,1,2,3)
(1,4,5,2,3)
(1,2,5,4,3)
(1,2,3,4,5)



Перестановка нечетная и знак члена определителя равен
(5,4,1,2,3)
( 1)
1


  .
Ответ: а) произведение не является членом определителя; б) знак ми- нус; в) знак минус.
Пример 7.
Вычислить определитель
11 12 21 22 33 34 43 44
a a
0 0
a a
0 0
0 0 a a
0 0 a a
Решение. Выпишем все ненулевые члены определителя. Если в член определителя сомножителем входит нулевой элемент определителя, то такой член определителя равен нулю. Поэтому из каждой строки мы можем выбрать лишь два элемента определителя. Из первой стро- ки выбираем элемент
11
a . Тогда из второй строки мы без вариантов должны выбрать элемент
22
a , который стоит во втором столбце, так как элемент
21
a стоит в первом столбце, из которого элемент уже вы- бран. Далее, из третьей строки мы можем выбрать либо элемент
33
a , либо
34
a . Если мы выбираем элемент
33
a , то из 4-й строки мы должны без вариантов выбрать элемент
44
a . Если же в третьей строке мы вы- бираем элемент
34
a , то из 4-й строки мы должны без вариантов вы- брать элемент
43
a . Таким образом, мы получаем всего 4 члена опре- делителя:
11 22 33 44 11 22 34 43
a a a a , a a a a ,
12 21 33 44 12 21 34 43
a a a a , a a a a .
Легко находим, что первый и четвертый члены имеют знак плюс, а второй и третий – знак минус. Получаем:

Головизин В.В. ПЗ по курсу «Алгебра и геометрия», ПЗ 29, УдГУ, Ижевск – 2011, с.13 9
11 12 21 22 11 22 33 44 11 22 34 43 33 34 43 44
a a
0 0
a a
0 0
a a a a a a a a
0 0 a a
0 0 a a



12 21 33 44 12 21 34 43
a a a a a a a a



11 22 33 44 34 43 12 21 33 44 34 43
a a (a a a a ) a a (a a a a )





33 34 11 12 11 22 12 21 33 44 34 43 43 44 21 22
a a
a a
(a a a a )(a a a a )
a a
a a





Ответ:
11 12 21 22 33 34 11 12 33 34 43 44 21 22 43 44
a a
0 0
a a
0 0
a a
a a
0 0 a a
a a
a a
0 0 a a


п.4 Задачи
Задачи для аудиторного решения 29
1. Определить число инверсий в перестановках: а) (2, 3, 5, 4, 1); б) (1, 9, 6, 3, 2, 5, 4, 7, 8); в) (6, 3, 1, 2, 5, 4); г) (7, 5, 6, 4, 1, 3, 2); д) (1, 3, 5, …, 2n 1
 , 2, 4, 6, 8, …, 2n); е) (n, n 1, n 2, ..., 3, 2,1)


2. Сколько инверсий образует число 1, стоящее на k
-м месте переста- новки?
3. Сколько инверсий образует наибольшее число перестановки, стоя- щее на k
-м месте?
4. Перейти от перестановки 7, 5, 3, 9, 1, 6, 2, 8, 4 к начальной переста- новке 1, 2, 3, 4, 5, 6, 7, 8 за наименьшее число транспозиций.
5. Выяснить, какие из следующих произведений входят в определите- ли соответствующих порядков и с какими знаками: а)
43 21 35 12 54
a a a a a ; б)
61 23 45 36 12 54
a a a a a a ; в)
27 36 51 74 25 43 62
a a a a a a a ; г)
33 16 72 27 55 61 44
a a a a a a a ; д)
12 23 34
n 1,n n,1
a a a ... a a

6. Выбрать числа m и k так, чтобы произведение
62 m5 33 k 4 46 21
a a a a a a входило в определитель 6-го порядка со знаком минус.
Головизин В.В. ПЗ по курсу «Алгебра и геометрия», ПЗ 29, УдГУ, Ижевск – 2011, с.13 10 7. Пользуясь только определением определителя выпишите все члены определителя 2-го и 3-го порядков.
8. Пользуясь определением вычислить определитель
0 0 0 1 0 0 2 2 0 3 3 3 4 4 4 4 9. С каким знаком входит в определитель произведение элементов: а) главной диагонали; б) побочной диагонали?
10. Пользуясь только определением определителя вычислите опреде- литель: а) диагональной матрицы; б) треугольной матрицы; в) матрицы, у которой все элементы выше побочной диагонали равны нулю.
11. Пользуясь только определением определителя выпишите все чле- ны определителя 4-го порядка, которые входят в определитель со знаком плюс.
12. Найти члены определителя 4-го порядка, содержащие элемент
32
a и входящие в определитель со знаком плюс.
Задачи повышенного уровня сложности 29
1. Докажите, что при транспозиции соседних элементов перестановки число инверсий изменяется на 1.
2. Докажите, что при транспозиции любых элементов перестановки число инверсий изменяется на нечетное число.
3. В какой перестановке множества чисел {1, 2, …, n} число инверсий наибольшее и чему оно равно?
4. Докажите, что любую транспозицию можно выполнить с помощью смежных транспозиций.
5. Найти сумму инверсий во всех перестановках множества из четы- рех элементов.
6. Докажите, что от любой перестановки, содержащей k инверсий можно перейти к начальной перестановке с помощью k смежных транспозиций.
7. Известно, что число инверсий в перестановке
1 2
n
(a , a ,..., a ) равно k.
Сколько инверсий в перестановке n
n 1 1
(a , a ,..., a )

?

Головизин В.В. ПЗ по курсу «Алгебра и геометрия», ПЗ 29, УдГУ, Ижевск – 2011, с.13 11 8. Вычислите определитель, пользуясь его определением: а)
11 12 13 14 21 22 23 24 33 34 43 44
a a
a a
a a
a a
0 0
a a
0 0
a a
; б)
13 14 23 24 31 32 33 34 41 42 43 44 0
0
a a
0 0
a a
a a
a a
a a
a a
Домашнее задание 29.
1. Выбрать числа m и k так, чтобы произведение
47 63 1m 55 7k 24 31
a a a a a a a входило в определитель 7-го порядка со знаком плюс.
2. Пользуясь определением вычислить определители: а)
2 1 0 3 1 2 0 4 2 3 0 5 3 4 0 6



; б)
1 0 0 2 3 0 0 4 0 5 6 0 0 7 8 0
; в)
1 1
0 0
0 3
2 4
0 0
6 5
0 0
0 8




3. Выпишите все члены определителя x 1 2 3
x x 1 2 1 2 x 3
x 1 2 x
, содержащие в качестве сомножителей
4
x и
3
x .