Файл: ALGYeBRA_I_GYeOMYeTRIYa.doc

Пример.

= ·

§8. Перестановки.

Определение. Пусть A={a₁, a₂,…, a_n} – произвольное множество. Перестановкой множества A называется любой порядок расположения элементов этого множества.

Общее количество перестановок множества, состоящего из n элементов, обозначим P_n.

Теорема 1.1. P_n=n!=1·2·3·…·n (n! читается так: «эн факториал»).

Доказательство. По индукции. Пусть множество A состоит из одного элемента: A={a}. Очевидно, что существует только одна перестановка этого множества равенство P₁=1! верно.

Пусть теперь мы знаем, чтоP_n1=(n1)!, а множество A состоит из n элементов. Для того, чтобы создать перестановку, необходимо сначала выбрать тот элемент, который будет первым. Сделать это можно n различными способами. После этого у нас остаётся n1 элемент, и расположить их сзади первого элемента можно (n1)! способами согласно предположению индукции. Таким образом, общее количество способов расположения равно n·(n1)!= n!.

Каждой перестановке (a_i1, a_i2,…, a_in ) элементов множества A={a₁, a₂,…, a_n} однозначно соответствует перестановка (i₁, i₂,…, i_n) их номеров. Поэтому в дальнейшем будем говорить только про перестановки множества {1, 2,…, n} натуральных чисел.

Определение. Пусть (p₁, p₂,…, p_n) – произвольная перестановка. Говорим, что пара (p_i, p_j) образует инверсию, если i<j, но p_i>p_j (то есть бóльшее число стоит раньше).

Общее количество инверсий в перестановке (p₁, p₂,…, p_n) обозначим I(p₁, p₂,…, p_n). Если это число чётно (нечётно), то перестановка называется чётной (нечётной).

Пример. I(4, 2, 1, 5, 3)=5, т.к. в данной перестановке мы имеем следующие инверсии: (4, 2), (4, 1), (4, 3), (2, 1), (5, 3).

Предложение 3. Если в перестановке поменять местами два числа, то её чётность изменится.

Доказательство. Предположим сначала, что меняются местами два соседних числа p_i и p_i+1. Если p_i<p_i+1, Тогда у нас сохранятся все инверсии, в которых участвует только одно из этих чисел. Если p_i<p_i+1, то у нас появится одна новая инверсия (p_i+1, p_i), а если p_i>p_i+1, то у нас исчезнет одна инверсия (p_i, p_i+1). В любом случае общее количество инверсий изменится на 1, а значит, чётность перестановки изменится.

Предположим теперь, что меняются местами произвольные числа p_i и p_i+к. Между ними находится k1 чисел

p_i+1,…, p_i+к1. (1.10)

Мы сначала будем перемещатьp_i назад поочерёдно меняя его с каждым из чисел (1.10), пока оно не окажется перед p_i+к. Теперь p_i и p_i+к стали соседними. Мы меняем их местами, и затем, перемещаем p_i+к вперёд, меняя поочерёдно с каждым из элементов (1.10) в обратном порядке. В итоге мы поменяем p_i и p_i+к местами и совершим нечётное количество 2(k1) +1 перестановок соседних элементов. Каждая из таких перестановок меняла чётность. В итоге чётность нашей перестановки изменится.

§9. Формула полного разложения определителя по элементам матрицы.

Теорема 1.2. detA = (;\s\do10(I(j1(1)^I(j₁^{, j}₂^{,…, j}_n⁾aj1; 1aj2; 2… ajn;n.

Поясним, что здесь записано. Мы выбираем в матрице n элементов, так чтобы из каждой строки и каждого столбца был выбран ровно один элемент. Мы расположим эти элементы в порядке возрастания номеров строк и составим их произведение. Тогда номера столбцов образуют перестановку I(j₁, j₂,…, j_n). Если эта перестановка нечётная, то мы добавляем к произведению знак минус. Затем мы все такие произведения складываем. Число слагаемых равно числу различных перестановок (j₁, j₂,…, j_n) нижних индексов, т.е. равно n!.

Например, множество индексов {1, 2, 3} имеет 6 перестановок:

(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1),

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

= a1;1a1;2a1;3+ a2;1a3;2a1;3+ a3;1a1;2a2;3a1;1a3;2a2;3a2;1a1;2a3;3a3;1a2;2a1;3.

Эту формулу можно запомнить виде схемы

§10. Системы линейных уравнений. Правило Крамера.

Определение. Система из m линейных уравнений с n неизвестными (СЛУ) имеет вид:

(1.11)

Числа a_ij называются коэффициентами системы, а числа b¹, b²,…, b^m – свободными членами. Коэффициенты системы образуют матрицу A, а свободные члены – столбец B:

A= , B =

Символы x¹, x²,…, xⁿ называются неизвестными. Матрица

A^*=

Называется расширенной матрицей СЛУ (8).

Определение. Решением системы линейных уравнений (1.11) (частным решением) называется любой набор чисел (¹, ²,…, ⁿ), при подстановке которых вместо неизвестных x¹, x²,…, xⁿ все уравнения системы превращаются в верные равенства. Система называется совместной, если она имеет хотя бы одно решение и несовместной, если она не имеет решений.

Например, следующая система несовместна:

СЛУ может иметь более, чем одно решение. Тогда она имеет бесконечное количество решений. Например, все решения системы

можно записать в виде (12, ),R (т.е.  выступает здесь в качестве параметра: вместо  мы можем подставить любое число, и получится частное решение). Такая запись называется общим решением системы.

Пусть теперь число уравнений в СЛУ равно числу неизвестных: m=n. Тогда матрица A является квадратной. Обозначим =detA, а _i – определитель матрицы, которая получается из A заменой i-го столбца на столбец свободных членов B. Например,

₁= .

Теорема 1.3. (Правило Крамера). Если 0, то СЛУ (1.11) (при m=n) имеет, и притом единственное решение. Это решение можно найти по формулам

x¹ = , x² = , …, xⁿ = .

Обратите внимание, что данная теорема состоит из двух утверждений. Первое предложение о существовании и единственности решения имеет самостоятельное большое значение.

Пример 3. Найти решение системы уравнений

Решение.

== –2, ₁= = 6, ₂= = – 4.

x₁ = = = –3, x₂ = = = 2.

Ответ: (–3, 2).

§11. Ранг матрицы.

Определение. Рангом системы строк (системы столбцов) матрицы A называется максимальное количество её линейно независимых строк (столбцов). Т.е. говорим, что ранг системы строк матрицы A равен r₁, если в матрице существует r₁ линейно независимых строк, а любые r₁+1 строк линейно зависимы; говорим, что ранг системы столбцов матрицы A равен r₂, если в матрице существует r₂ линейно независимых столбцов, а любые r₂+1 столбцов линейно зависимы.

Определение. Рангом матрицы A называется максимальная размерность её ненулевого минора. Т.е. говорим, что ранг матрицы A равен r, если в ней существует ненулевой минор порядка r, а любой минор порядка r+1 равен нулю (или таких миноров вообще нет).

Ранг матрицы обозначаем rankA или rkA. Если L – ненулевой минор порядка r, то он называется базисным минором. В матрице может быть несколько базисных миноров. Строки и столбцы, в которых расположен базисный минор будем называть базисными.

Пример 3. В следующей матрице первая и вторая строки пропорциональны, а третья строка им не пропорциональна.

A= .

Поэтому в матрице есть 2 линейно независимые сроки, а 3 строки линейно зависимы. Значит ранг системы строк матрицы A равен 2.

Минор

L12;23 = 0,

а любой минор порядка три должен включать в себя часть первой и часть второй сроки. Поэтому любой минор порядка 3 равен нулю. Значит, L12;23 – базисный минор и rankA=2. Также базисными будут миноры L13;23 , L14;23 , L34;23 , L24;23 .

Перебирать все миноры в поисках базисного – это очень трудоёмкая задача. Поэтому можно использовать метод окаймляющих миноров. Если мы нашли ненулевой минор L порядка k, то мы затем перебираем не все миноры порядка k+1, а только те, которые содержат в себе минор L (их будем называть окаймляющими). Если все окаймляющие миноры окажутся равными нулю, то и все миноры порядка k+1 тоже будут равны нулю, и мы сделаем вывод, что rankA=k. Если среди окаймляющих миноров мы найдём ненулевой минор L, то переходим к минорам порядка k+2, которые содержат в себе L, и т.д.

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

Назовём элементарными преобразованиями матрицы следующие преобразования.

1. Вычёркивание срок и столбцов, которые состоят только из нулей.

2. Перестановка строк или столбцов.

3. Умножение строки или столбца на число не равное нулю.

4. Прибавление к одной строке (столбцу) матрицы другой строки (столбца), домноженной на некоторое число.

Предложение 4. Элементарные преобразования не изменяют ранга матрицы.

Шаг 1. Вычеркнем все строки и столбцы, состоящие только из нулей.

Шаг 2. В первом столбце матрицы выберем ненулевой элемент и строку, в которой он находится, поставим на первое место.

Шаг 3. Разделим первую строку на a1;1. К каждой i-ой строке матрицы прибавим первую строку, домноженную на число a1; i. В результате мы получим матрицу вида