Конспект лекций по алгебре. Системы линейных уравнений. Основные понятия
 Скачать 0.68 Mb.
|
|
§18. Квадратные матрицы. Единичная матрица Рассмотрим множество матриц типа n×n , т. е. матриц, у которых количе- ство строк совпадает с количеством столбцов. Такие матрицы называются квад- ратными, а число n — порядком матрицы. Нетрудно видеть, что любые две квадратные матрицы порядка n можно умножать и что их произведением будет являться квадратная матрица того же порядка n. На протяжении всего параграфа будут рассматриваться только квадратные матрицы фиксированного порядка. Коль скоро на множестве квадратных матриц задана операция умножения, можно поставить задачу о нахождении специальной матрицы, обладающей свойством единицы. Определение. Квадратная матрица E называется единичной, если для вся- кой матрицы A того же порядка справедливы равенства A E= E A= A. Элементы единичной матрицы порядка n обозначим через δ i j . Для вычисле- ния δ i j воспользуемся формулой (15). Если A=(a i j ) , то равенство A E= A в развёрнутой форме примет вид ∑ k =1 n a i k δ k j = a i j (16) Подчеркнём, что последнее соотношение представляет собой на самом деле систему n 2 равенств, так как оба индекса i и j независимо друг от друга прини- мают значения от 1 до n. Зафиксируем какие-нибудь значения индексов i=i 0 и j= j 0 Матричное ра- 5 Некоторые закоренелые формалисты утверждают, что при такой постановке вопроса луч- ше говорить не о современной, а формальной математике. 37 венство A E= A должно выполняться для любой матрицы A, в частности, для матрицы, у которой все элементы, кроме одного, расположенного на позиции ( i 0 j 0 ) , равны нулю. Допустим, что a i 0 j 0 = 1. Для такой матрицы все уравне- ния системы (16), у которых i≠i 0 , будут иметь вид 0=0 . Если же i=i 0 , то уравнения системы (16) примут вид δ j 0 j = a i 0 j , так как в левой части (16) все слагаемые с k ≠ j 0 заведомо равны нулю и a i 0 j 0 = 1. Следовательно δ j 0 j = 0 в случае j≠ j 0 и δ j 0 j = 1 в случае j= j 0 Таким образом, все недиагональные элементы единичной матрицы равны нулю, а диагональные — единице. Например, единичная матрица порядка 4 имеет вид E= ( 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ) Замечание 1. Символ δ i j = { 0 , i≠ j , 1 , i= j довольно часто используется в сокра- щённых записях сумм. Символ δ i j называется дельта-символом Кронекера. Замечание 2. Понятие единичной матрицы можно ввести иным способом. Можно рассмотреть оператор I :ℝ n →ℝ n , I ( x)=x и заметить, что для любого оператора A:ℝ n →ℝ n справедливо равенство A I = I A= A. Остаётся только заметить (а читателю проверить), что во всяком базисе пространства ℝ n эле- менты линейного оператора I равны δ i j §19. Обратимые матрицы. Понятие обратной матрицы Здесь, как и в предыдущем параграфе, рассматриваются только квадратные матрицы фиксированного порядка. Единичная матрица обозначается через E . Определение. Матрица A порядка n называется обратимой, если существу- ет такая матрица B , что справедливы равенства A B=B A= E . Если матрица A обратима, то матрица B из предыдущего определения на- зывается матрицей, обратной к A. Обратная к A матрица обычно обознача- ется символом A − 1 Метод вычисления обратной матрицы поясним на примере. Пример. Найдём матрицу, обратную к A= ( 2 3 1 2 ) . Положим 38 A − 1 = ( x 11 x 12 x 21 x 22 ) Числа x i j нужно подобрать таким образом, чтобы выполнялось двойное матричное равенство A A − 1 = A − 1 A=E . Рассмотрим отдельно соотношение A − 1 A= E , которое эквивалентно системе четырёх линейных уравнений с четырьмя неизвестными x i j : { 2 x 11 + 3 x 21 = 1 , x 11 + 2 x 21 = 0 , 2 x 12 + 3 x 22 = 0, x 12 + 2 x 22 = 1 . Решая эту систему, например, методом Гаусса, находим, что A − 1 = ( 2 − 3 − 1 2 ) Замечание. В рассмотренном примере мы использовали только одно из ра- венств, определяющих A − 1 , а именно A A − 1 = E . Можно доказать, что во всех случаях из справедливости равенства A B=E вытекает справедливость равен- ства B A=E . §20. Перестановки из n элементов Рассмотрим множество X ={1, 2,…, n}. Перестановкой из n элементов на- зывается любое биективное отображение σ : X → X . Множество всех переста- новок из n элементов будем обозначать через S n Имеется два основных способа записи перестановок. Один из них заключает- ся в том, что перестановку σ задают с помощью матрицы из двух строк. В первой строке перечисляются элементы X , а во второй — их образы: σ= ( 1 2 … n σ( 1) σ(2) … σ(n) ) Задача. Сколько элементов содержит множество S n ? Второй способ задания называется представлением перестановки в виде произведения 6 независимых циклов. Если для всякого i∈ X имеет место равен- ство σ( i)=i , то такая перестановка называется единичной и она записывается в виде σ=(1). Для любой другой перестановки обязательно найдётся i , для 6 Слово «произведение» пока нужно понимать формально. 39 которого σ( i)≠i . В этом случае представление σ в виде произведения неза- висимых циклов начинается так: σ=( i σ(i) σ 2 ( i)…) …, где σ k — k-я итерация отображения σ . Выписанная строчка (цикл) состоит из конечного числа попарно различных элементов множества X . (Почему?) Цикл ( i σ(i) σ 2 ( i)…) полностью определяет перестановку, если в выписан- ной строчке встречаются все элементы множества X . Если же имеется эле- мент j∈ X , такой что σ( j)≠ j и j не входит в построенный цикл, то для этого элемента строим аналогичный цикл из итераций и приписываем его к пер- вому. Так поступаем до тех пор, пока не будут исчерпаны все элементы множе- ства X . При таком способе задания перестановки договариваются не включать в за- пись неподвижные элементы перестановки, т. е. те элементы множества X , для которых σ(i)=i . Таким образом, циклы любой перестановки (кроме еди- ничной) содержат не менее двух элементов. Из алгоритма разложения перестановки на циклы видно, что различные цик- лы не имеют общих элементов. Такие циклы называют независимыми. Пример 1. Перестановка σ= ( 1 2 3 4 5 4 5 1 2 3 ) представляется единствен- ным циклом σ=(1 4 25 3), так как σ(1)=4 , σ(2)=5, σ(5)=3, σ(3)=1. Пример 2. Для перестановки τ= ( 1 2 3 4 5 6 7 3 2 4 1 6 5 7 ) τ( 1)=3 , τ(3)=4, τ( 4)=1 , поэтому цикл (13 4) не исчерпывает всех элементов τ и построе- ние циклов нужно продолжить: τ ( 5)=6 , τ(6)=5. Поскольку элементы 2 и 7 яв- ляются неподвижными для τ , то τ=(13 4)(5 6). Пример 3. Пусть перестановка из S 7 задана в виде произведения независи- мых циклов σ=(16)(2 5)(34). Тогда её можно записать в виде матрицы σ= ( 1 2 3 4 5 6 7 6 5 4 3 2 1 7 ) Определение. Перестановка состоящая из одного двухэлементного цикла на- зывается транспозицией. В примере 3 каждый независимый цикл является транспозицией. 40 §21. Умножение перестановок Из курса математического анализа читателю должно быть известно, что композиция биекций сама является биекцией. Поэтому для любых двух пере- становок σ , τ∈S n композиция τ σ также является перестановкой из S n Перестановка τ σ называется произведением 7 σ и τ (в указанном порядке). Определённая операция умножения перестановок является ассоциативной операцией (почему?), но, в общем случае, не коммутативной. Пример 1. Для двух перестановок σ=(214), τ=(13)∈S 4 произведение τ σ=( 1 4 23), но σ τ=(13 4 2). Ясно, что τ σ≠σ τ , поскольку, например, τ σ( 2)=3, σ τ(2)=1. Из того же курса математического анализа известно, что всякое биективное отображение обратимо, причём обратное отображение само является биектив- ным. Применительно ко множеству S n этот факт означает, что для всякой перестановки σ найдётся перестановка τ , такая что оба произведения τ σ и σ τ являются единичными перестановками. Как обычно перестановка, обрат- ная к σ , обозначается через σ − 1 Очевидно также, что если единичную перестановку обозначить через ε , то для всякой перестановки σ справедливы равенства σ ε=ε σ=σ . Итак, операция умножения перестановок обладает следующими свойствами. 1. ∀ σ , τ ,ρ∈S n (σ τ)ρ=σ (τρ); 2. ∃ε∈S n | ∀ σ∈S n σ ε=ε σ=σ ; 3. ∀ σ ∃(σ − 1 ) |σ σ − 1 =σ − 1 σ=ε Теорема 1. Всякая перестановка может быть представлена в виде произведе- ния транспозиций. Доказательство. Достаточно рассмотреть случай, когда перестановка представлена одним цик- лом, т. е. когда σ=(i 1 i 2 … i k ) . В целях наглядности будем считать, что k =5. Доказательство теоремы завершает проверка соотношения ( i 1 i 2 i 3 i 4 i 5 )=( i 1 i 2 )( i 2 i 3 )( i 3 i 4 )( i 4 i 5 ) □ Пример 2. (13 4)(5 6)=(13)(3 4)(56). Представление перестановки в виде произведения транспозиций не единственно. Например, в S n , n⩾3, является верным равенство ( 12 3)=(1 2)(2 3)=(13)(2 3)(13)(2 3). Т. е. перестановка ( 12 3) представлена в виде произведения транспозиций дву- 7 Введённая операция позволяет рассматривать произведение независимых циклов из § 20 в буквальном смысле, т. е. как результат умножения. 41 мя различными способами. Однако имеет место Теорема 2. Если заданы два представления перестановки в виде произведе- ния s и r транпозиций, то числа s и r имеют одинаковую чётность. В примере 2 числа s и r равны 2 и 4. Прежде чем доказывать теорему 2, введём понятие инверсии. Определение 1. Упорядоченная пара различных целых чисел (i j) образует инверсию, если i> j . Числа ( i j) образуют правильную пару, если i< j . Пусть перестановка σ∈S n задана в виде таблицы σ= ( i 1 i 2 … i n σ( i 1 ) σ ( i 2 ) … σ ( i n ) ) Обозначим через I (σ) количество упорядоченных пар в обеих строках, обра- зующих инверсию. Пример 2. Если σ= ( 3 2 4 1 6 5 6 5 3 4 2 1 ) , то в верхней строке инверсию об- разуют пары (31),(2 1),(41),(32),(6 5), а в нижней — (61),(51),(31),(41), ( 2 1),(6 2),(5 2),(3 2),(4 2),(6 3),(53),(6 4),(5 4),(65). Значит I (σ)=19. Лемма 1. Для любой перестановки σ ∈ S n I (σ⋅(i i+1))= I (σ)±1. Доказательство. Если σ= ( … i i+1 … … σ( i) σ(i+1) … ) , то σ⋅(i i+1)= ( … i i+1 … … σ ( i+1) σ(i) … ) Ясно, что если пара (σ(i) σ(i+1)) образует инверсию, то (σ(i+1) σ(i)) — правильная пара и наоборот. Кроме того, порядок других пар в каждой переста- новке σ и σ⋅(i i+1) одинаковый. Поэтому I (σ⋅(i i+1))=I (σ)±1. □ Определение 2. Перестановка σ называется чётной, если I (σ) чётно, и нечётной, если I (σ) нечётно. Задача 1. Проверьте, что перестановка (i i+1) является нечётной. Задача 2. Проверьте справедливость равенства ( i i+3)=(i i+1)(i+1 i+2)(i+2 i+3)(i+1 i+2)(i i+1). Равенство из задачи 2 означает, что транспозиция (i i+3) может быть пред- ставлена в виде произведения пяти транспозиций соседних элементов. Задача 3. Запишите транспозицию (i i+ p) в виде произведения 2 p−1 транспозиций соседних элементов. Ук а з а н и е . Проанализируйте соотношение из задачи 2 и попытайтесь выяс- нить его происхождение. Поэкспериментируйте с перекладыванием монеток, ручек или др. подручных материалов. Лемма 2. Всякая транспозиция является нечётной перестановкой. Доказательство вытекает из результатов задач 1, 3 и леммы 1. □ 42 Задача 4. Произведение чётного числа транспозиций является чётной пере- становкой, а произведение нечётного числа транспозиций — нечётной переста- новкой. Доказательство теоремы 2. Пусть перестановка σ представлена в виде произведения s транспозиций, каждая из которых согласно лемме 2 является нечётной перестановкой. Допу- стим, что σ является чётной перестановкой. Из задачи 4 следует, что это воз- можно только при чётном s. Аналогично, если перестановка σ — нечётная, то число s может быть только нечётным. □ Задача 5. Произведение двух чётных (двух нечётных) перестановок является чётной перестановкой. Произведение чётной и нечётной перестановки есть перестановка нечётная. Задача 6. При n⩾2 во множестве S n чётных перестановок столько же, сколько нечётных. §22. Определители n-го порядка Определение 1. Знаком перестановки σ называют число sgn σ=(−1) I (σ ) Рассмотрим квадратную матрицупорядка n A= ( a 11 a 12 ... a 1 n a 21 a 22 ... a 2 n a n 1 a n 2 ... a n n ) Определение 2. Определителем матрицы A называется число det A= ∑ σ ∈ S n sgn σ a 1σ (1) a 2 σ (2) … a n σ (n) (17) Таким образом, определитель матрицы порядка n есть сумма n ! слагае- мых, каждое из которых является произведением n элементов матрицы, взя- тых из каждой строки и каждого столбца по одному и только одному разу; если множители упорядочить по возрастанию номеров строк, то слагаемое берётся со знаком + , если перестановка номеров столбцов четная и со знаком − в противном случае. Свойство 1. Для любой матрицы n-го порядка det A t = det A. Доказательство. По определению, i-я строка матрицы A t состоит из элементов i-го столбца 43 матрицы A. Поэтому det A t = ∑ σ∈ S n sgn σ a σ ( 1)1 a σ ( 2) 2 … a σ ( n)n . Заметим, что если перестановка σ пробегает всё множество S n , то обратная перестановка σ − 1 также пробегает всё множество S n . Следовательно замена σ на σ − 1 в сум- ме, определяющей число det A t , лишь изменит порядок слагаемых, что конеч- но не изменит значения самой суммы: det A t = ∑ σ∈ S n sgn σ − 1 a σ − 1 ( 1)1 a σ − 1 ( 2)2 … a σ − 1 ( n) n Теперь в каждом слагаемом sgn σ − 1 a σ − 1 ( 1) 1 a σ − 1 ( 2) 2 … a σ − 1 ( n)n изменим порядок множителей таким образом, чтобы номера строк (первые индексы у элемен- тов a i j матрицы A) располагались в возрастающем порядке. Нетрудно ви- деть 8 , что после такой перестановки произведение перепишется в виде sgn σ − 1 a 1 σ(1) a 2 σ( 2) … a n σ (n) И поскольку sgn σ − 1 = sgn σ , det A t = ∑ σ∈ S n sgn σ a 1 σ (1) a 2 σ (2) … a n σ (n) = det A. □ Свойство 2. При умножении любой строки определителя на число, определи- тель умножается на это число. Свойство 3. Если в определителе поменять местами строки, то определитель изменит знак. Доказательство. Будем для определённости считать, что переставляются 1-я и 2-я строки. Обозначая матрицу с переставленными строками через A 1 2 , запишем равен- ства det A 1 2 = ∑ σ ∈ S n sgn σ a 2σ ( 1) a 1σ (2) … a n σ ( n) = ∑ σ ∈ S n sgnσ a 1 σ (2) a 2 σ (1) … a n σ (n) Перестановку τ номеров столбцов в последней сумме можно представить в виде произведения σ⋅(12) (см. доказательство леммы 1 в §21). Из результатов предыдущего параграфа следует, что sgn τ=−sgn σ . Для завершения доказа- тельства нужно заметить, что если σ пробегает всё множество S n , то τ так- же пробегает всё множество S n : det A 1 2 =− ∑ τ∈ S n sgn τ a 1 τ(1) a 2 τ(2) … a n τ( n) =− det A. □ 8 Это не стандартная фраза, оправдывающая отсутствие обоснования. Формулируемое да- лее утверждение на самом деле очевидно. 44 Свойство 4. Определитель, элементы некоторой строки которого представле- ны в виде суммы двух слагаемых, равен сумме двух определителей, каждый из которых получается из исходного заменой одноимённой строки строкой первых и вторых слагаемых соответственно. Свойство 5. Определитель с нулевой строкой равен нулю. Свойство 6. Определитель с одинаковыми строками равен нулю. Доказательство. Если в матрице A поменять местами две одинаковые строки, то её опреде- литель не изменится. С другой стороны, согласно свойству 3, определитель матрицы A изменит знак. Поэтому det A=−det A, т. е. det A=0. □ Из свойств 2, 4 и 6 вытекает Свойство 7. Определитель не изменится, если к элементам некоторой строки определителя прибавить соответственные элементы другой строки, умножен- ные на одно и то же число. Свойство 8. Определитель равен нулю тогда и только тогда, когда его строки линейно зависимы. Доказательство. Если в матрице A система строк является линейно зависимой, то равен- ство det A=0 вытекает из свойств 2, 4 и 6. Доказательство обратного утверждения, т. е. что из равенства det A=0 сле- дует линейная зависимость строк матрицы можно провести следующим об- разом. Согласно свойствам 2, 3 и 7 элементарные преобразования строк матри- цы не меняют абсолютной величины её определителя. Напомним, что всякую матрицу с помощью элементарных преобразований можно привести к ступенча- тому виду и что при элементарных преобразованиях ранг матрицы не меняется не меняется. Приведём матрицу A порядка n к ступенчатому виду. Если строки матрицы линейно независимы, т. е. если rank A=n, то преобразованная матрица будет иметь строго треугольную форму (см. §12). Определитель такой матрицы равен произведению её диагональных элементов, а значит отличен от нуля, что проти- воречит исходному равенству det A=0. □ |