Линейная алгебра. Квадратичные формы

Материалы к курсу “Алгебра” часть II Д.В. Громов 24 мая 2020 г. Оглавление 1 Линейная алгебра 1.1 Линейные (векторные) пространства . . . . . . . . . . . . . . . . . 1.1.1 Линейные пространства и подпространства . . . . . . . . . 1.1.2 Сумма подпространств. . . . . . . . . . . . . . . . . . . . . . Задачи и вопросы . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Конечномерные векторные пространства . . . . . . . . . . . . . . 1.2.1 Линейная оболочка . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Линейная независимость. . . . . . . . . . . . . . . . . . . . 1.2.3 Базис линейного пространства . . . . . . . . . . . . . . . . 1.2.4 Размерность линейного пространства . . . . . . . . . . . . 1.2.5 Канонический базис . . . . . . . . . . . . . . . . . . . . . . . Задачи и вопросы . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Линейные отображения . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Понятие линейного оператора, его свойства . . . . . . . . . 1.3.2 Ядро и образ линейного оператора . . . . . . . . . . . . . . 1.3.3 Изоморфизм векторных пространств. Координатное представление элементов векторных пространств . . . . . 1.3.4 Преобразование базиса . . . . . . . . . . . . . . . . . . . . . 1.3.5 Отношение эквивалентности матриц . . . . . . . . . . . . . *1.3.6 Факторпространство по подмножеству . . . . . . . . . . . . 1.3.7 Матричное представление линейного отображения. Структура и свойства . . . . . . . . . . . . . . . . . . . . . . 1.3.8 Системы линейных алгебраических уравнений с операторной точки зрения . . . . . . . . . . . . . . . . . . Задачи и вопросы . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Геометрия линейных пространств . . . . . . . . . . . . . . . . . . . 1.4.1 Норма вектора . . . . . . . . . . . . . . . . . . . . . . . . . . *1.4.2 Операторная норма . . . . . . . . . . . . . . . . . . . . . . . 1.4.3 Скалярное произведение . . . . . . . . . . . . . . . . . . . . 1.4.4 Ортогональная проекция. Ортогональное дополнение . . . 1.4.5 Ортонормированный базис. Процедура Грама-Шмидта . . 1.4.6 Операторы в пространствах со скалярным произведением 1.4.7 Метод наименьших квадратов . . . . . . . . . . . . . . . . . Задачи и вопросы . . . . . . . . . . . . . . . . . . . . . . . . Проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Собственные числа и векторы . . . . . . . . . . . . . . . . . . . . . 1.5.1 Инвариантные подпространства . . . . . . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 3 5 6 8 8 9 10 12 14 14 16 16 17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 22 24 26 . . . . . . . 26 . . . . . . . . . . . . . . 28 29 31 31 32 34 36 39 43 46 48 49 50 50 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Алгебра – II 1.5.2 1.5.3 Д.В. Громов . . . . . . . . . . . . . . . 51 . . . . . . . . . . . . . . 55 56 59 61 63 67 73 2 Квадратичные формы 2.1 Канонический вид квадратичной формы . . . . . . . . . . . . . . . . . . . . . 2.2 Знакоопределенные квадратичные формы . . . . . . . . . . . . . . . . . . . . . Задачи и вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 74 76 79 3 Приложения линейной алгебры 3.1 Марковские цепи . . . . . . . . . . . . 3.2 Разложения прямоугольных матриц . 3.2.1 QR-разложение . . . . . . . . . 3.2.2 Сингулярное разложение . . . . 3.3 Матричные группы . . . . . . . . . . . 3.4 Приложения . . . . . . . . . . . . . . . 3.4.1 Pseudo-inverse and least squares 3.4.2 Haar wavelet/Haar basis . . . . . 3.4.3 Bernstein polynomials and spline 80 80 88 88 89 92 92 92 92 92 1.5.4 1.5.5 1.5.6 1.5.7 1.5.8 Собственные числа и векторы . . . . . . . . . Кратные собственные числа. Алгебраическая и геометрическая кратность Подобные матрицы . . . . . . . . . . . . . . . Функции от матриц . . . . . . . . . . . . . . . Симметрические и эрмитовы матрицы . . . . Диагонализируемые матрицы . . . . . . . . . Жорданова нормальная форма матрицы . . Задачи и вопросы . . . . . . . . . . . . . . . . Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 2 Глава 1 Линейная алгебра 1.1 Линейные (векторные) пространства 1.1.1 Линейные пространства и подпространства Определение 1.1.1. Линейным пространством над полем F называется множество V вместе с операциями сложения, V × V → V , и умножения на скаляр, F × V → V удовлетворяющих аксиомам, перечисленным в таблице 1.1. Таблица 1.1: Аксиомы линейного пространства Для любых u, v, w ∈ V и любых α, β ∈ F выполняется: Сложение Умножение на скаляр Коммутативность u+v =v+u Ассоциативность (u + v) + w = u + (v + w) Нейтральный элемент u + 0 = u, 0 ∈ V Обратный элемент u + (−u) = 0, −u ∈ V Ассоциативность (αβ)u = α(βu) Дистрибутивность (α + β)u = αu + βu α(u + v) = αu + αv 1 · u = u. Унитарность Для определенности договоримся обозначать элементы векторного пространства (т. е. векторы) полужирными строчными буквами, а линейные (под)пространства – заглавными буквами латинского алфавита. Лемма 1.1.1. Линейное пространство удовлетворяет следующим свойствам: 1. Нейтральный элемент относительно сложения определен единственным образом. 2. Для любого u ∈ V существует единственный противоположный ему вектор (−u) ∈ V , который определяется как (−u) = (−1) · u. 3. Для любого u ∈ V выполняется 0 · u = 0. 3 Алгебра – II Д.В. Громов 4. Для любого α ∈ F выполняется α · 0 = 0. Доказательство. Докажем последние два пункта. Первые свойства доказываются аналогично соответствующим свойствам поля. 3. Запишем v = (1 + 0) · v = v + 0 · v. Прибавляя к обеим частям равенства (−v) получим 0 = 0 · v. 4. Используя п. 3 запишем: α · 0 = α · (0 · v) = (α · 0) · v = 0 · v = 0. Пример 1.1.1. Примеры векторных пространств включают себя как множества “обычных” векторов с элементами из R или C, так и множества, состоящие из более сложных объектов, например пространства матриц или бесконечных последовательностей:             v11 . . . v1m   v1    .. v ∈ F , F ∞ = {(v )∞ |v ∈ F } . F n =  ... vi ∈ F , F n×m =  ... . . .  ij i i=1 i .         vn vn1 . . . vnm Векторным пространством является множество всех функций из S в F , где S – произвольное непустое множество. Это векторное пространство обозначается как F S . Множество полиномов из F [x] степени, не превышающей n, является векторным пространством над F и обозначается PnF (или просто Pn ). Проверьте, что перечисленные множества удовлетворяют свойствам векторных пространств. Линейное подпространство. В линейной алгебре понятие линейного подпространства играет возможно даже большую роль, чем понятие линейного пространства. В то время как линейное пространство представляет собой “весь мир”, линейные подпространства появляются при решении конкретных задач из области линейных (дифференциальных) уравнений, дифференциальной геометрии, случайных процессов и т. д. Определение 1.1.2. Множество W ⊂ V называется линейным подпространством V если W является линейным пространством относительно операций сложения и умножения на скаляр, унаследованных от V . Пример 1.1.2. Очевидно, что W = {0} и W = V являются подпространствами V . Примером подпространства V = R3 является, например, множество     w1  W = w2  ∈ R3 |w1 + w2 − w3 = 0 .   w3 Множество решений однородной системы Ax = 0 с матрицей A размерности n×m является линейным подпространством Rn . Множество всех диагональных матриц размерности n × n с элементами из F является подпространством F n×n , а множество всех бесконечных последовательностей с элементами из F и сходящихся к нулю будет образовывать линейное подпространство F ∞ . Придумайте несколько примеров подмножеств, которые являются (не являются) линейными подпространствами некоторых векторных пространств. Для определения, будет ли некоторое подмножество V его линейным подпространством, можно использовать следующий тест. 4 Алгебра – II Д.В. Громов Лемма 1.1.2. Множество W ⊂ V является линейным подпространством V тогда и только тогда, когда1 1. {0} ∈ W , 2. u + w ∈ W 3. αw ∈ W ∀u, w ∈ W , ∀α ∈ F, w ∈ W . Доказательство. Если W есть векторное подпространство, то перечисленные свойства следуют по определению. Обратно, перечисленные условия гарантируют существование нейтрального элемента и замкнутость W относительно сложения и умножения на скаляр. Коммутативность, ассоциативность и дистрибутивность естественным образом наследуются от V . Наконец, последнее свойство гарантирует существование обратного элемента: (−u) = (−1) · u. В дальнейшем мы будем часто опускать определение линейное, говоря о подпространствах. Кроме того, мы будем полагать, что из контекста всегда понятно, в каком векторном пространстве “живут” наши подпространства и над каким полем они определены. По умолчанию, все подпространства полагаются принадлежащими векторному пространству V над полем F . 1.1.2 Сумма подпространств. Определение 1.1.3. Суммой подпространств U1 , . . . , Un называется множество U1 + · · · + Un = {u1 + · · · + un |ui ∈ Ui }. Определение 1.1.4. Сумма подпространств U1 + . . . + Un называется прямой и обозначается U1 ⊕ . . . ⊕ Un , если каждый элемент u ∈ U1 + · · · + Un может быть однозначно представлен в виде суммы u = u1 + · · · + un , где ui ∈ Ui . Пример 1.1.3. Рассмотрим два подпространства R3 :        u1   0  U = u2  ∈ R3 |u1 , u2 ∈ R и V = v2  ∈ R3 |v2 , v3 ∈ R .     v3 Можно заметить, что U + V = R3 , т. е. сумма U и V совпадает со всем пространством R3 , однако эта сумма не является прямой: U + V 6= U ⊕ V . Это связано с тем, что для любого x ∈ R, выражение x = u2 + v2 не определяет однозначно значения u2 и v2 . Следующие теоремы позволяют точно охарактеризовать подмножества, образующие прямую сумму. Теорема 1.1.3. Сумма U1 + . . . + Un является прямой тогда и только тогда, когда единственный способ записи нулевого вектора 0 в виде суммы 0 = u1 + · · · + un , ui ∈ Ui , заключается в выборе ui = 0 для всех i = 1, . . . , n. 1 Обратите внимание, что первый пункт не является необходимым и может быть опущен без именения смысла результата. Объясните, почему? 5 U1 ⊕ U2 Алгебра – II Д.В. Громов 1. Если U1 + . . . + Un = U1 ⊕ . . . ⊕ Un , то, по определению прямой суммы, нулевой вектор может быть представлен единственным (и тривиальным) образом в виде суммы нулевых элементов Ui . Доказательство. 2. Предположим, что вектор v ∈ U1 + · · · + Un может быть представлен двумя способами в виде суммы векторов из Ui : v = u1 + · · · + un и v = w1 + · · · + wn , где ui , wi ∈ Ui . Вычитая второе выражение из первого получим 0 = (u1 − w1 ) + · · · + (un − wn ). Поскольку, по условию, 0 может быть единственно представлен в виде суммы нулевых векторов, имеем ui − wi = 0, откуда следует, что ui = wi , т. е.оба представления совпадают. Теорема 1.1.4. Сумма двух подпространств U + V является прямой тогда и только тогда, когда U ∩ V = {0}. 1. Положим, что U + V = U ⊕ V . Если v ∈ U ∩ V , то (−v) ∈ U ∩ V . Следовательно мы можем записать 0 = v + (−v). Однако по теореме 1.1.3, нулевой вектор однозначно представляется в виде суммы нулевых векторов. Это значит, что v = 0 и, следовательно, U ∩ V = {0}. Доказательство. 2. Теперь предположим, что U ∩ V = {0}. Пусть нулевой вектор представляется в виде 0 = u + v, где u ∈ U , v ∈ V . По определению векторного сложения, v = (−u) ∈ U . Следовательно, v ∈ U ∩ V = {0}. Аналогично, u = 0. Из теоремы 1.1.3 следует, что U + V – прямая сумма. Задачи и вопросы 1. Будут ли являться линейными подпространствами множество симметрических матриц размера n×n, S n ⊂ Rn×n , и множество косо-симметрических матриц размера n × n, An ⊂ Rn×n ? Если да, то чему равна сумма S n + An ? Будет ли эта сумма прямой? 2. Какие из следующих матриц размерности n×n образуют линейное подпространство Rn×n : a) нижние треугольные матрицы, b) унитарные нижние треугольные, c) вырожденные матрицы, det(B) = 0, d) невырожденные матрицы, det(B) 6= 0, e) ортогональные матрицы, BB> = E, f) диагональные матрицы? 3. Докажите, что множество дважды непрерывно дифференцируемых функций из R в R, удовлетворя2 ющих уравению ddxf2 + f = 0 является линейным подпространством множества функций из R в R. Приведите пример элементов указанного подпространства. 4. Пусть Ue и Uo – множества четных и нечетных функций из R в R. Покажите, что эти множества являются подпространствами. Докажите, что Ue + Uo = Ue ⊕ Uo = RR . 5. Рассмотрим множество полиномов степени k ≤ n из F [x]. Будет ли это множество образовывать подпространство в PnF ? 6. Предложите пример подмножества R2 , которое замкнуто относительно операций сложения и взятия обратного элемента, но не является подпространством. 7. Предложите пример подмножества R2 , которое замкнуто относительно операции умножения на скаляр, но не является подпространством. 8. Пусть U1 и U2 – два подпространства V . Докажите, что U1 ∩ U2 также будет подпространством V . Будет ли являться подпространством объединение U1 ∪ U2 ? 6 Алгебра – II Д.В. Громов 9. Пусть V и W – два векторных пространства. Определим декартово произведение V × W как множество всех упорядоченных пар (v, w), где v ∈ V , w ∈ W . Покажите, что V × W также является векторным пространством если задать операции сложения и умножения на скаляр покомпонентно: (v0 , w0 ) + (v00 , w00 ) = (v0 + v00 , w0 + w00 ), α(v, w) = (αv, αw). Являются ли V и W подпространствами V × W ? Как можно представить V × W в виде прямой суммы двух подпространств? 10. Можно ли разложить R3 в прямую сумму 2,3,4 подпространств? Рассмотрите каждый случай по отдельности. Если да, то предложите примеры, если нет – объясните, почему. x 11∗ . Покажите, что положительный квадрант R2+ = |x, y > 0 будет являться векторным пространy ством над R, если определить операции сложения и умножения на скаляр как α x x x x x x1 = α . + 2 = 1 2 , α y1 y2 y y y2 y1 Приведите пример линейного подпространства R2+ . Покажите как можно представить R2+ в виде прямой суммы своих подпространств. 7 Алгебра – II 1.2 Д.В. Громов Конечномерные векторные пространства 1.2.1 Линейная оболочка Определение 1.2.1. Пусть vi ∈ V , i = 1, . . . , n, есть набор векторов из V . Линейной комбинацией векторов {v1 , . . . , vn } с коэффициентами αi ∈ F называется взвешенная сумма α1 v1 + · · · + αn vn . Множество всех линейных комбинаций векторов {v1 , . . . , vn } называется их линейной оболочкой и обозначается span(v1 , . . . , vn ): span(v1 , . . . , vn ) = {α1 v1 + · · · + αn vn |αi ∈ F, i = 1, . . . , n}. (1.1) Лемма 1.2.1. Линейная оболочка span(v1 , . . . , vn ) является наименьшим подпространством V , содержащим все векторы vi . 1. Для начала покажем, что W = span(v1 , . . . , vn ) действительно является подпространством V . Полагая αi = 0 получаем 0 ∈ W . Кроме того, из (1.1) следует, что W замкнуто относительно операций сложения и умножения на скаляр. Согласно лемме 1.1.2, W является подпространством V . Доказательство. 2. Очевидно, что линейная оболочка span(v1 , . . . , vn ) содержит все векторы vi . В то же время, поскольку каждое подпространство по определению замкнуто относительно сложения и умножения на скаляр, любое подпространство, содержащее векторы {v1 , . . . , vn }, будет также содержать их линейную оболочку. Понятие линейной оболочки может быть обобщено на случай произвольного подмножества линейного пространства V . Определение 1.2.2. Пусть W ⊂ V – некоторое, не обязательно конечное подмножество пространства V . Линейная оболочка span(W ) определяется как пересечение всех подпространств V , содержащих W . Пусть V = span(W ). Мы будем говорить, что подмножество W порождает V или что V натянуто на подмножество W . Определение 1.2.3. Пространство V называется конечномерным если оно совпадает с линейной оболочкой некоторого конечного набора векторов vi ∈ V или, иначе говоря, если V порождается некоторым конечным набором векторов. В противном случае пространство называется бесконечномерным. Исследование конечномерных линейных пространств является предметом линейной алгебры, тогда как бесконечномерные пространства (например, пространство непрерывных функций или пространство бесконечных последовательностей) изучаются в рамках функционального анализа и в данном курсе рассматриваться не будут. Итак, мы будем рассматривать только те линейные пространства, которые могут быть представлены как линейные оболочки некоторого конечного числа своих элементов (векторов). В следующих разделах мы частично ответим на вопрос о том, как выбирать эти векторы и почему один набор векторов может оказаться лучше другого. 8 span(v1 , .., vn ) Алгебра – II 1.2.2 Д.В. Громов Линейная независимость. Определение 1.2.4. Набор векторов {v1 , . . . , vn } называется линейно-независимым если выражение α1 v1 + · · · + αn vn = 0 (1.2) выполняется только при αi = 0 для всех i = 1, . . . , n. В противном случае, т. е. если существует набор коэффициентов αi ∈ F , из которых по меньшей мере один не равен нулю, такой, что выполняется (1.2), то векторы {v1 , . . . , vn } называются линейно-зависимыми. Лемма 1.2.2. Пусть {v1 , . . . , vn } – набор линейно зависимых векторов. Тогда существует такой индекс 1 ≤ k ≤ n, что для вектора vk верно следующее: 1. vk ∈ span(v1 , . . . , vk−1 , vk+1 , . . . , vn ), 2. span(v1 , . . . , vk−1 , vk+1 , . . . , vn ) = span(v1 , . . . , vn ). 1. Поскольку набор {v1 , . . . , vn } является линейно-зависимым, то существуют такие коэффицииенты αi , не все раные нулю, что выполняется (1.2). Выберем в качестве k индекс первого ненулевого коэффициента αk 6= 0 и выразим vk : X αi vi . (1.3) vk = αk Доказательство. i6=k Таким образом, vk может быть представлен в виде линейной комбинации остальных n − 1 векторов. 2. Рассмотрим некоторый вектор u ∈ span(v1 , . . . , vn ). Этот вектор может быть представлен в виде суммы n X u= βi v i . i=1 Подставляя в это выражение vk из (1.3) получаем, что u может быть представлен в виде линейной комбинации векторов из набора {v1 , . . . , vn } \ {vk }, что доказывает вторую часть леммы. Можно сформулировать следующее практически важное следствие из леммы 1.2.2. Следствие 1.2.3. В любом множестве векторов, порождающих пространство V , можно выделить подмножество линейно-независимых векторов, чья линейная оболочка совпадает с V . Доказательство этого результата оставляется в качестве самостоятельного упражнения. Следующая, достаточно техническая лемма окажется очень важной при определении понятия размерности линейного пространства. Лемма 1.2.4. Пусть набор n векторов {v1 , . . . , vn } порождает пространство V , т. е. V = span(v1 , . . . , vn ). Тогда пространство V не может содержать больше n линейнонезависимых векторов. 9 Алгебра – II Д.В. Громов Доказательство. Будем доказывать от противного. А именно, предположим, что V содержит k > n линейно-независимых векторов {u1 , . . . , uk }. Все векторы ui отличны от нулевого вектора2 и принадлежат V . Поскольку V = span(v1 , . . . , vn ), мы можем записать u1 в виде линейной комбинации векторов {v1 , . . . , vn }: u1 = α1 v1 + · · · + αn vn , где по крайней мере один коэффициент αi не равен нулю (в противном случае мы бы получили u1 = 0). Соберем все члены выражения в левой части: u1 − α1 v1 − · · · − αn vn = 0. (1.4) Поскольку равенство выполняется при ненулевых значениях коэффициентов, мы заключаем, что множество векторов {u1 , v1 , . . . , vn } является линейно-зависимым. Поэтому по лемме 1.2.2 мы можем “выбросить” из этого множества один вектор vi (тот, у которого αi 6= 0) и при этом оставшийся набор векторов будет порождать V . Будем повторять ту же процедуру для векторов u2 , u3 , и так далее вплоть до um , m < n. Предположим, что после m-го шага (и, при необходимости, после переобозначения индексов) у нас получился набор {u1 , . . . , um , vm+1 , . . . , vn }. Поскольку, по построению, этот набор порождает V , мы можем представить um+1 в виде линейной комбинации векторов из {u1 , . . . , um , vm+1 , . . . , vn } и записать по аналогии с (1.4): um+1 − β1 u1 − · · · − βm um − βm+1 vm+1 − · · · − βn vn = 0, (1.5) т. е. набор векторов {u1 , . . . , um , um+1 , vm+1 , . . . , vn } является линейно-зависимым. Поскольку um+1 6= 0, в разложении (1.5) есть по крайней мере один ненулевой коэффициент. Предположим, что все коэффициенты при vm+1 , . . . , vn равны нулю. Тогда оказывается, что набор {u1 , . . . , um , um+1 } является линейно-зависимым, что противоречит условию3 . Следовательно существует такой индекс j, m + 1 ≤ j ≤ n, что βj 6= 0. В очередной раз воспользуемся леммой 1.2.2 и “выбросим” из набора {u1 , . . . , um , um+1 , vm+1 , . . . , vn } вектор vj . Следуя той же схеме мы в конце концов замещаем все векторы vi в нашем исходном наборе на векторы ui , i = 1, . . . , n. При этом новый, получившийся после замены набор все так же порождает V : V = span(u1 , . . . , un ). Это значит, что любой из оставшихся векторов uj , j = n + 1, . . . , k может быть представлен в виде линейной комбинации векторов {u1 , . . . , un }. Однако это противоречит тому, что векторы {u1 , . . . , uk } линейно-независимы. 1.2.3 Базис линейного пространства Определение 1.2.5. Базисом линейного пространства V , обозначается B(V ), называется набор линейно-независимых векторов {v1 , . . . , vn } такой, что V = span(v1 , . . . , vn ). Теорема 1.2.5. Набор векторов {v1 , . . . , vn } является базисом V тогда и только тогда, когда любой вектор u ∈ V может быть единственным образом представлен в виде суммы u = α1 v1 + · · · + αn vn . (1.6) 2 См. 3 См. задание 3 в конце раздела. задание 4 в конце раздела. 10 B(V ) Алгебра – II Д.В. Громов В этом случае выражение (1.6) называется разложением u по базису {v1 , . . . , vn }, а коэффициенты αi называются координатами вектора u в базисе {v1 , . . . , vn }. 1. Предположим, что набор {v1 , . . . , vn } является базисом V . По определению, V = span(v1 , . . . , vn ) и следовательно, любой вектор u ∈ V может быть представлен в виде линейной комбинации элементов из {v1 , . . . , vn }. Предположим, что это представление неединственно, т. е. мы можем записать u двумя разными способами: u = α1 v1 + · · · + αn vn , Доказательство. u = β1 v 1 + · · · + βn v n . Вычитая второе уравнение из первого, получим 0 = (α1 − β1 )v1 + · · · + (αn − βn )vn . Это означает, что αi − βi = 0 ∀i = 1, . . . , n поскольку векторы vi линейно-независимы. Таким образом, представление (1.6) существует и единственно. 2. Теперь положим, что любой вектор u ∈ V может быть представлен в виде (1.6). Из этого следует, что V = span(v1 , . . . , vn ). Если бы набор {v1 , . . . , vn } являлся линейнозависимым, то можно было бы выбрать такие коэффициенты αi ∈ F , не все равные нулю, что выполнялось бы выражение (1.2). Однако, по условию, вектор 0 ∈ V может быть единственным образом представлен в виде суммы (1.2) и, очевидно, это представление соответствует αi = 0 ∀i = 1, . . . , n. Таким образом мы приходим к противоречию. Следовательно, векторы {v1 , . . . , vn } являются линейно-независимыми и, по определению, задают базис V . Обратите внимание, что разложение по базису зависит не только от базисных векторов, но и от порядка их расположения. В дальнейшем мы будем часто рассматривать базис как упорядоченный набор векторов и в этом случае будем записывать набор базисных векторов в круглых скобках4 . В том случае, когда это не будет приводить к двусмысленностям, мы будем идентифицировать вектор с его координатами в некотором стандартном (каноническом) базисе5 . Если будет необходимо явно указать, к какому базису относятся координаты, будем писать [v]B . Сформулируем ряд полезных утверждений относительно базиса линейного пространства. Лемма 1.2.6. Верны следующие утверждения: 1. В наборе векторов {v1 , . . . , vn }, порождающих V , можно выделить подмножество, являющееся базисом V . 2. Любое конечномерное линейное пространство обладает базисом. 3. Любой набор линейно-независимых векторов {v1 , . . . , vm }, принадлежащих V , может быть дополнен до базиса V . 4 В математике используется следующее соглашение: множество из n элементов x , . . . , x обозначается n 1 как {x1 , . . . , xn }, а упорядоченный набор тех же элементов (кортеж, англ. tuple) – как (x1 , . . . , xn ). 5 См. раздел 1.2.5 11 [v]B Алгебра – II Д.В. Громов Доказательство. Доказательство приведенных утверждений может быть проведено самостоятельно следуюя следующим указаниям: 1. переформулировка следствия 1.2.3; 2. следует из определения конечномерного линейного пространства и п. 1; 3. следует схеме доказательства леммы 1.2.4 с заменой ui на vi . При необходимости используем результат п. 1. Внимательный читатель может задаться вопросом: а что же будет представлять собой базис пространства, содержащего только один нулевой элемент? Можно легко проверить, что сам нулевой элемент не может быть базисным вектором, так как не выполняется условие линейной независимости: выражение α · 0 = 0 выполняется для любого значения α ∈ F . Итак, базисом {0} является пустое множество, B({0}) = {}. Однако имеет ли смысл этот результат? Необходимо показать, что такой выбор базиса не противоречит теории, т. е. что для пустого множества выполняется определение 1.2.5. Из определения 1.2.2 следует, что span({}) = {0}, так как пустое множество содержится в любом линейном пространстве. Таким образом, линейная оболочка пустого множества совпадает с {0}. Пустое множество также линейно-независимо, так как единственный набор коэффициентов, ассоциированный с пустым множеством сам по себя является пустым. Поэтому утверждение о линейной независимости пустого множества является бессодержательно истиным (англ., vacuous truth), так как следует из ложного утверждения о существовании набора коэффициентов, удовлетворяющих некоторому свойству. 1.2.4 Размерность линейного пространства Можно легко заметить, что выбор базиса не является однозначным. В качестве элементарного примера можно рассмотреть наборы {v1 , . . . , vn } и {λv1 , . . . , λvn }, λ 6= 0. Если один из этих набором является базисом V , то второй также будет базисом V . Однако может ли случиться, что два базиса обладают различным числом элементов? На этот вопрос отвечает следующая важная теорема. Теорема 1.2.7. Пусть V – некоторое конечномерное пространство, а B1 (V ) и B2 (V ) – два базиса V . Тогда B1 (V ) и B2 (V ) содержат одинаковое число элементов (иначе говоря, имеют одинаковую мощность). Доказательство. Предположим, что B1 (V ) = {v1 , . . . , vm }, а B2 (V ) = {u1 , . . . , un }. По определению, каждый из приведенных наборов a) является линейно-независимым, b) порождает V . По лемме 1.2.4, m ≤ n и n ≤ m. Следовательно, n = m. Этот результат открывает нам дорогу для определения ключевого понятия: размерности векторного пространства. Определение 1.2.6. Размерность векторного пространства V , обозначается dim(V ), равна числу элементов (базисных векторов) некоторого произвольного базиса B(V ). Размерность тривиального векторного пространства равна нулю: dim({0}) = 0. Следующий результат указывает (относительно) простой способ определения базиса V . 12 Алгебра – II Д.В. Громов Лемма 1.2.8. Пусть V – линейное пространство такое, что dim(V ) = n. Любой набор из n линейно-независимых векторов, принадлежащих V , будет образовывать базис V . Доказательство. Мы помним, что любой набор линейно-независимых векторов может быть дополнен до базиса. Однако, в нашем случае число линейно-независимых векторов уже равно числу базисных векторов. Следовательно, наш набор и есть базис. Наконец, мы сформулируем результат, позволяющий вычислить размерность линейного пространства, если оно может быть представлено в виде суммы двух подпространств. Теорема 1.2.9 (Грассман6 ). Пусть U и W – два подпространства конечномерного векторного пространства V . Тогда размерность суммы U + W равна dim(U + W ) = dim(U ) + dim(W ) − dim(U ∩ W ). (1.7) Доказательство. Пусть B(U ∩ W ) = {v1 , . . . , vk }. Согласно п. 3 леммы 1.2.6, набор линейно-независимых векторов {v1 , . . . , vk } может быть дополнен до базисов U и W : B(U ) = {v1 , . . . , vk , u1 , . . . , um } и B(W ) = {v1 , . . . , vk , w1 , . . . , wn }. Покажем, что B(U + W ) = {v1 , . . . , vk , u1 , . . . , um , w1 , . . . , wn }. Очевидно, что сумма U + W совпадает с линейной оболочкой span(v1 , . . . , vk , u1 , . . . , um , w1 , . . . , wn ). Осталось доказать, что эта система векторов линейно-независима. Предположим, что это условие не выполняется, т. е. выражение α1 v1 + · · · + αk vk + β1 u1 + · · · + βm um + γ1 w1 + · · · + γn wn = 0 имеет место для некоторых значений коэффициентов, не равных нулю одновременно. Наборы векторов {v1 , . . . , vk }, {u1 , . . . , um } и {w1 , . . . , wn } линейно-независимы. Следовательно ненулевые коэффициенты не могут все находиться в одной группе α, β или γ. Предположим, что среди коэффициентов β1 , . . . , βm есть по крайней мере один ненулевой7 . Тогда мы можем записать β1 u1 + · · · + βm um = −α1 v1 − · · · − αk vk − γ1 w1 − · · · − γn wn , т. е. вектор u = β1 u1 + · · · + βm um ∈ W . Однако верно также u ∈ U и, следовательно, u ∈ U ∩ W . Это значит, что для некоторых, не равных одновременно нулю, значениях α10 , . . . , αk0 выполняется β1 u1 + · · · + βm um = α10 v1 + · · · + αk0 vk , т. е. набор {v1 , . . . , vk , u1 , . . . , um } является линейно-зависимым, что противоречит выбору B(U ). Приходим к противоречию, следовательно набор {v1 , . . . , vk , u1 , . . . , um , w1 , . . . , wn } является линейно-независимым и, тем самым, составляет базис суммы U + W . Считая количество элементов во всех рассмотренных базисах, получаем dim(U ∩ W ) = k, dim(U ) = k + m, dim(W ) = k + n, dim(U + W ) = k + m + n, откуда следует (1.7). 6 Герман Грассман (Hermann Günther Grassmann, 1809 – 1877). Среди своих современников был известен как лингвист и переводчик “Ригведы” с санскрита на немецкий язык, а сейчас больше известен как основатель векторного и тензорного исчисления. 7 Действуем аналогично, если среди γ , . . . , γ есть по крайней мере один ненулевой. n 1 13 dim(V ) Алгебра – II 1.2.5 Д.В. Громов Канонический базис Как уже было сказано выше, базис конечномерного пространства может быть выбран неединственным способом. В связи с этим появляется необходимость определения некоторого “максимально простого” базиса, который мог бы служить в качестве стартовой точки при рассуждении о свойствах некоторого линейного пространства. Такие базисы называются каноническими. Ниже мы рассмотрим примеры канонических базисов наиболее типичных линейных пространств. В пространстве Rn в качестве канонического базиса выбирается упорядоченный набор векторов {e1 , . . . , en }, где ei – это вектор размерности n (т. е. столбец [n × 1]) с единицей на i-й позиции и нулями в остальных позициях (т. н. Евклидов базис):       0  1      0  0 1          .. 0 0 {e1 , . . . , en } =   ,   , . . . ,  . .     .  .    ..  .. 0       1 Немного неожиданно, но оказывается, что в качестве канонического базиса пространства Cn над полем C может быть выбран тот же базис {e1 , . . . , en }. Подумайте, почему? См. задание 9 в конце раздела. Заметим, что как для Rn , так и для Cn , координаты вектора в каноническом базисе могут быть идентифицированы с самим вектором. Каноническим базисом пространства полиномов из F [x] степени, не превышающей n, будет служить набор {1, x, x2 , . . . , xn }. Очевидно, что размерность PnF будет равна n + 1. Соответственно, каждый элемент из PnF может быть представлен в виде набора n + 1 своих коэффициентов. В этом смысле PnF оказывается “похоже” на F n+1 . Скоро мы увидим, что это интуитивное понятие похожести может быть формализовано как изоморфизм двух пространств. Теперь посмотрим на вопрос с другой стороны. Мы помним, что полиномы могут быть интерпретированы не только как элементы кольца, но и как полиномиальные функции. Оказывается, что предложенный выбор базиса согласуется с этой интерпретацией, как следует из решения задачи 7. Наконец, в качестве канонического базиса пространства Rm×n используется набор матриц размерности m × n, у которых только один элемент равен единице, а остальные равны нулю. Можно легко посчитать, что dim(Rm×n ) = mn. Более сложная задача заключается в определении базиса некоторых подпространств Rm×n . См. задание 6 ниже. Задачи и вопросы 1. Пусть v1 , v2 и v3 – линейно-независимые векторы. Будут ли векторы w1 = v1 − v2 , w2 = v2 − v3 , w3 = v3 также линейно-независимыми? Предположим, что векторы v1 , v2 и v3 образуют базис некоторого линейного пространства. Будут ли векторы w1 , w2 и w3 , определенные выше, также образовывать базис? 2. Будет ли множество всех матриц перестановок размера [3 × 3] линейно-независимым? 3. Пусть {v1 , . . . , vn } есть некоторый набор линейно-независимых векторов из V . Докажите, что vi 6= 0 ∀i = 1, . . . , n. 14 Алгебра – II Д.В. Громов 4. Докажите, что если v1 , . . . , vn образуют набор линейно-независимых векторов, то любое подмножество этого набора также будет линейно-независимым. Будет ли это утверждение выполняться для случая набора линейно-зависимых векторов? Докажите или приведите контрпример.     x  3   y ∈R x+y−z =0 . 5. Выберите базис подпространства   z 6. Выберите базис и определите размерность подпространств R3×3 : a) симметрических матриц, b) кососимметрических матриц, с) нижних треугольных матриц. 7. Докажите, что набор функций 1, x, x2 , . . . , xn является линейно-независимым в пространстве всех функций из R в R. 8. Выберите базис для подпространств p(x) ∈ P3R p(1) = 0 , p(x) ∈ P3R p0 (1) = 0 . 9. Рассмотрим C2 как векторное пространство над полем C (обозначим его (C2 , C)) и как векторное пространство над полем R (соответственно, (C2 , R)). Выберите базис и определите размерности (C2 , C) и (C2 , R). 10. Пусть V – конечномерное линейное пространство размерности n. Как можно представить V в виде прямой суммы n подпространств: V = V1 ⊕ · · · ⊕ Vn ? 11. Пусть набор векторов {v1 , . . . , vn } образует базис пространства V . Будет ли набор {v1 + w, . . . , vn + w}, w ∈ V также являться базисом V ? 15 Алгебра – II 1.3 1.3.1 Д.В. Громов Линейные отображения Понятие линейного оператора, его свойства Определение 1.3.1. Отображение T : V → W линейного пространства V над полем F в линейное пространство W над полем8 F называется линейным отображением (оператором), если оно удовлетворяет следующим свойствам для всех v, u ∈ V и α ∈ F : 1. Аддитивность: T (v + u) = T (v) + T (u), 2. Однородность: T (αv) = αT (v). Применительно к линейным отображениям скобки иногда опускаются и вместо T (v) используется запись T v. Множество всех линейных отображений из V в W будем обозначать L(V, W ). На множестве L(V, W ) можно естественным образом ввести операции сложения и умножения на скаляр. Пусть Q, T ∈ L(V, W ), v ∈ V и λ ∈ F . Определим (Q + T )(v) = Qv + T v, (λT )v = λT v. (1.8) Введенные операции аналогичны соответствующим операциям для векторного пространства. Для того, чтобы аналогия была полной, необходимо определить нейтральный элемент относительно сложения в L(V, W ), т. е. нулевой оператор . Это будет отображение, которое любому элементу из V ставит в соответствие нулевой вектор из W : 0v = 0 ∈ W. Утверждение 1.3.1. С введенными операциями, множество L(V, W ) является векторным пространством. Пример 1.3.1. Рассмотрим несколько примеров линейных отображений. Для подпространства полиномов Pn (но не только для него) может быть определен оператор дифференцироd p(x). Можно опревания D ∈ L(Pn , Pn−1 ), который действует обычным образом: Dp(x) = dx делить оператор Tx , который будет отображать Pn−1 в Pn : Tx p(x) = xp(x). Для квадратных матриц можно определить оператор симметризации Σ ∈ L(Rn×n , Sn ): ΣA = 21 (A + A> ). В качестве самостоятельной работы рекомендуется проверить все перечисленные линейные отображения на соответствие свойствам векторного пространства, а также предложить несколько своих примеров линейных операторов. Для линейных операторов можно определить операцию композиции так же, как она определяется для функций. Определение 1.3.2. Пусть V , W и U суть некоторые векторные пространства, а Q ∈ L(V, W ) и T ∈ L(W, U ) – линейные операторы, определенные на этих пространствах. Тогда для всех v ∈ V определим композицию T Q как (T Q)v = T (Qv). 8 В дальнейшем мы будем полагать, что векторные пространства, входящие в одно выражение, всегда определены над одним и тем же полем. 16 L(V, W ) Алгебра – II Д.В. Громов Определение 1.3.3. Оператор Q ∈ L(W, V ) называется обратным к T ∈ L(V, W ) и обозначается T −1 , если (T −1 T )v = v ∀v ∈ V. Иначе говоря, T −1 T = Id, где Id ∈ L(V, V ) отображает каждый вектор из V в себя: Id v = v. Аналогично тому, как мы классифицируем функции, линейные операторы тоже могут быть поделены на инъективные, сюръективные и биективные9 . Определение 1.3.4. Линейный оператор T ∈ L(V, W ) называется • Инъективным если ∀v, u ∈ V : T v = T u ⇒ v = u, • Сюръективным если ∀v ∈ V ∃w ∈ W : T v = w, • Биективным если существует обратный оператор T −1 : W → V . 1.3.2 Ядро и образ линейного оператора С каждым линейным оператором неразрывно связаны два подпространства: его ядро (англ., null space, kernel) и образ (англ., range, image). Определение 1.3.5. Пусть T ∈ L(V, W ) есть линейный оператор, действующий из V в W . Ядром T , обозначается N (T ), называется множество векторов v ∈ V , удовлетворяющих T v = 0. Образ T , обозначается R(T ), состоит из векторов w ∈ W таких, что w = T v для некоторого v ∈ V . N (T ) = {v ∈ V | T v = 0} ⊂ V, R(T ) = {T v ∈ W | v ∈ V } ⊂ W. Для начала мы формально покажем, что ядро и образ линейного оператора действительно являются подпространствами. Лемма 1.3.2. Для T ∈ L(V, W ), N (T ) есть линейное подпространство V , а R(T ) – линейное подпространство W . Доказательство. Для доказательства первого утверждения заметим, что {0} ∈ N (T ). Это следует из следующего рассуждения: T 0 = T (0 + 0) = T 0 + T 0. Прибавляя слева и справа элемент, обратный к T 0, получим T 0 = 0. Закнутость множества N (T ) относительно сложения и умножения на скаляр очевидна. Для R(T ) имеем {0} ∈ R(T ) так как T 0 = 0. Покажем замкнутость R(T ) относительно сложения. Если w1 , w2 ∈ R(T ), то по определению существуют такие v1 , v2 ∈ V , что T v1 = w1 и T v2 = w2 . Тогда v1 + v2 ∈ V и, следовательно, T (v1 + v2 ) = w1 + w2 ∈ R(T ). Доказательство замкнутости относительно умножения на скаляр доказывается аналогично, с использованием свойства однородности линейного оператора. 9 Для того, чтобы не ломать себе язык, мы будем называть биективные отображения взаимно однозначными. 17 N (T ) R(T ) Алгебра – II Д.В. Громов Пример 1.3.2. Рассмотрим линейные операторы из примера 1.3.1. Ядром оператора дифференцирования является множество полиномов нулевой степени, т. е. констант: N (D) = c ∈ F , а образ D совпадает с Pn−1 . Для оператора Tx ∈ L(Pn−1 , Pn ) ядро состоит из нулевого элемента, N (Tx ) = {0}, а образ совпадает с подпространством полиномов размерности, не превышающей n, с нулевым свободным членом (чему будет равна размерность этого подпространства?). Подумайте, что будет являться ядром и образом оператора симметризации Σ, чему равны размерности этих пространств? Оказывается, что анализ ядра и образа линейного оператора позволяет сделать важные выводы о свойствах этого оператора. Лемма 1.3.3. Оператор T ∈ L(V, W ) является инъективным тогда и только тогда, когда N (T ) = {0}. Доказательство. Пусть T – инъективный оператор. Тогда из T v = 0 = T 0 следует v = 0. Наоборот, пусть N (T ) = {0}. Для любых v, u ∈ V таких, что T v = T u имеем T v − T u = T (v − u) = 0, откуда следует v = u. Соответственно, из определения сюръективности следует, что свойство сюръективности оператора T ∈ L(V, W ) эквивалентно R(T ) = W . Теорема 1.3.4. Пусть T ∈ L(V, W ), где V – конечномерное пространство. Тогда выполняется dim(V ) = dim(N (T )) + dim(R(T )). (1.9) Доказательство. Пусть набор линейно-независимых векторов {u1 , . . . , um } образует базис ядра T . Этот набор может быть дополнен до базиса V : B(V ) = {u1 , . . . , um , v1 , . . . , vn }. Соответственно, имеем dim(V ) = m + n и dim(N (T )) = m. Рассмотрим вектор v ∈ span(u1 , . . . , um , v1 , . . . , vn ), т. е. v = α1 u1 + · · · + αm um + · · · + β1 v1 + βn vn и запишем результат действия линейного преобразования T на v: T v = T (α1 u1 + · · · + αm um + β1 v1 + · · · + βn vn ) = = α1 T u1 + · · · + αm T um + β1 T v1 + · · · + βn T vn = (1.10) = β1 T v1 + · · · + βn T vn . По определению, множество {T v ∈ W |v ∈ span(V )} является образом T . Кроме того, из (1.10) следует, что R(T ) = span(T v1 , . . . , T vn ). Осталось показать, что векторы {T v1 , . . . , T vn } линейно-независимы. Предположим, что существуют такие, не равные одновременно нулю, коэффициенты γ1 , . . . , γn , что выполняется γ1 T v1 + · · · + γn T vn = 0. Перепишем это выражение используя свойства однородности и аддитивности линейного оператора: T (γ1 v1 + · · · + γn vn ) = 0. Это значит, что γ1 v1 +· · ·+ γn vn ∈ N (T ), что противоречит выбору базиса B(V ). Приходим к противоречию. Итак, мы показали, что набор векторов {T v1 , . . . , T vn } образует базис R(T ), следовательно, dim(R(T )) = n. Сопоставляя размерности V и соответсвующих подпространств, приходим к (1.9). 18 Алгебра – II Д.В. Громов T ∈ L(V , W ) N (T ) coN (T ) {0} {0} coR(T ) R(T ) V W Рис. 1.1: Четыре основные подпространства, связанные с оператором T . Пространства N (T ) и R(T ) схематически изображены на рис. 1.1. На этом рисунке изображены 4 подпространства, два из которых, coN (T ) и coR(T ), мы рассмотрим позже. Утверждение 1.3.5. Каждое из условий, сформулированных ниже, эквивалентно тому, что линейное отображение T ∈ L(V, W ) биективно: 1. Отображение T сюръективно и инъективно, 2. Размерности V и W совпадают и ядро T равно нулевому подпространству, dim(V ) = dim(W ), N (T ) = {0}, 3. Образ T совпадает с W и ядро T равно нулевому подпространству, R(T ) = W, N (T ) = {0}. Доказательство оставляется в качестве самостоятельного упражнения. Наконец, следующее определение “перебрасывает мостик” от теории линейных операторов к матрицам. Эта связь будет предметом следующего раздела и – в том или ином виде – большей части нашего курса. Определение 1.3.6. Рангом линейного оператора T называется размерность его образа, rank(T ) = dim(R(T )). 1.3.3 Изоморфизм векторных пространств. Координатное представление элементов векторных пространств Изоморфизм векторных пространств. Следующее определение позволит нам в некоторой степени забыть о всем разнообразии (конечномерных) векторных пространств и сосредоточиться на изучении линейных отображений между пространствами типа F n . Определение 1.3.7. Два векторных пространства V и W называются изоморфными, обозначается V ' W , если существует взаимно однозначное линейное отображение T ∈ L(V, W ). Отображение T называется изоморфизмом. 19 rank(T ) Алгебра – II Д.В. Громов Замечание 1.3.1. Для тех, кому интересна математическая систематика заметим, что множество изоморфизмов составляет подмножество гомоморфизмов линейных пространств Hom(V, W ), т. е. всех отображений, сохраняющих структуру линейных пространств10 . А именно, отображение T : V → W векторных пространств V и W является гомоморфизмом если T (αv) = αT v и T (v1 + v2 ) = T v1 + T v2 . Очевидно это есть не что иное, как условия аддитивности и однородности (см. определение 1.3.1). В этом смысле мы можем идентифицировать L(V, W ) = Hom(V, W ). Координатное представление векторов. Каждое векторное пространство V , dim(V ) = n, изоморфно F n . Пусть B(V ) = (v1 , . . . , vn ) есть некоторый упорядоченный набор базисных векторов V . Тогда согласно теореме 1.2.5, любой вектор v ∈ V можно однозначно ассоциировать с вектором своих коэффициентов относительно базиса B(V ), который мы будем обозначать как [v]B(V ) :   α1  .. [v]B(V ) =  . ∈ F n . αn Соответственно, любому вектору из F n может быть однозначно поставлен в соответствие элемент v ∈ V . Такое преобразование называется координатным изоморфизмом относительно базиса B(V ) и обозначается κB(V ) : v 7→ [v]B(V ) . Для полноты картины заметим, что отображение κB(V ) линейно, т. е. для всех v0 , v00 ∈ V и α ∈ F выполняется κB(V ) (v0 + v00 ) = κB(V ) (v0 ) + κB(V ) (v00 ) и κB(V ) (αv0 ) = ακB(V ) (v0 ). Координатное представление линейных операторов. В разделе 1.3.1 мы установили, что множество линейных отображений L(V, W ) является векторным пространством. Поэтому подобно тому, как элемент “обычного” векторного пространства может быть представлен вектором своих координат относительно некоторого базиса, линейный оператор тоже может быть записан в координатной форме. Определение 1.3.8. Пусть T ∈ L(V, W ) и для пространств V и W определены соответствующие базисы: B(V ) = (v1 , . . . , vn ) и B(W ) = (w1 , . . . , wm ). Запишем разложение вектора T vj по базису B(W ) в виде m X T vj = aij wi , aij ∈ F. (1.11) i=1 Матрица A = [aij ], i = 1, . . . , m, j = 1, . . . , n, называется координатным представлением (или координатной матрицей) оператора T относительно базисов B(V ) и B(W ) и обозначается A = M(T ). В координатном представлении (1.11), j-й столбец матрицы A соответствует разложению j-го элемента B(V ) по базису B(W ). Соответственно, число строк матрицы A совпадает с размерностью W , а число столбцов с размерностью V . Покажем, что отображение M : L(V, W ) → F m×n действительно является изоморфизмом. 10 В общем случае понятия гомоморфизма, изоморфизма и т.д. можно обобщить на отображения между однотипными алгебраическими объектами: кольцами, группами и т.д. 20 V ' Fn Алгебра – II Д.В. Громов Теорема 1.3.6. Пусть V и W – два векторных пространства с базисами B(V ) = (v1 , . . . , vn ) и B(W ) = (w1 , . . . , wm ). Тогда отображение M : L(V, W ) → F m×n , определенное выше, является взаимно однозначным, т. е. L(V, W ) и F m×n изоморфны. Доказательство. Легко заметить, что умножение линейного оператора на скаляр и сложение двух линейных операторов соответствует умножению на скаляр и сложению соответствующих координатных матриц. Следовательно, отображение M линейно. Покажем, что оно инъективно и сюръективно. Если T ∈ L(V, W ) и M(T ) = 0 ∈ F m×n11 , то это значит, что T vi = 0 ∈ W для всех vi ∈ B(V ), т. е. T – это нулевой оператор. Следовательно, N (M) = {0} ∈ L(V, W ) и по лемме 1.3.3 отображение M инъективно. Чтобы показать, что M сюръективно, достаточно построить линейный оператор, соответствующий матрице A ∈ F m×n . Это соответствие задается (1.11). Из теоремы 1.3.6 можно заключить, что dim(L(V, W )) = dim(F m×n ) = dim(V ) dim(W ). Лемма 1.3.7. Пусть T и Q суть два линейных оператора, T ∈ L(V, W ), Q ∈ L(W, U ) с координатными матрицами A и B, размерностей [m × n] и [r × m], соответствующими базисам B(V ) = (v1 , . . . , vn ), B(W ) = (w1 , . . . , wm ) и B(U ) = (u1 , . . . , ur ). Тогда координатная матрица композиции двух операторов QT будет равна произведению их координатных матриц: M(QT ) = BA. Доказательство. Принимая во внимание, что по определению композиции двух операторов (QT )v = Q(T v) и используя разложение (1.11), запишем ! ! m r m m r X X X X X akj bik ui . akj wk = akj bik ui = (QT )vj = Q (T (vj )) = Q k=1 k=1 i=1 i=1 k=1 Соответственно, (i, j)-й элемент матрицы M(QT ), т. е. i-й коэффициент разложения vj по базису B(U ), будет иметь вид [M(QT )]ij = m X akj bik = m X bik akj = [BA]ij . k=1 k=1 Следующий результат следует из леммы 1.3.7 если мы предположим, что Q = T −1 . Лемма 1.3.8. Линейный оператор T ∈ L(V, W ) является взаимно однозначным тогда и только тогда, когда его координатная матрица A = M(T ) относительно некоторых базисов B(V ) и B(W ) является обратимой. Соответственно, координатная матрица обратного оператора T −1 относительно тех же базисов будет равна обратной матрице: A−1 = M(T −1 ). Итак, мы можем задать координатное представление для вектора и линейного оператора. Осталось связать эти два представления вместе и описать действие линейного оператора на вектор в координатной форме. 11 Для определенности будем явно указывать, к каким векторным пространствам относятся нулевые элементы. 21 Алгебра – II Д.В. Громов Лемма 1.3.9. Пусть T ∈ L(V, W ) – линейный оператор с координатной матрицей A относительно базисов B(V ) = (v1 , . . . , vn ) и B(W ) = (w1 , . . . , wm ). Для двух векторов v ∈ V и w ∈ W таких, что T v = w, координаты α = [v]B(V ) и β = [w]B(W ) связаны соотношением     β1 α1  ..  .. = A  .  . . βm αn Доказательство. Запишем w = T v и применим (1.11): w= m X βi wi = T v = T (α1 v1 + · · · + αn vn ) = i=1 = m X n X α j T vj = j=1 n X j=1 αj m X aij wi i=1   n X  aij αj  wi . i=1 j=1 Дальнейшее следует из правил умножения матрицы на вектор. Соотношение между линейным оператором и его координатным представлением может быть схематично изображено в виде следующей диаграммы: T V W κB(V ) κB(W ) A Fn 1.3.4 Fm Преобразование базиса Частным случаем линейного преобразования является преобразование базиса. А именно, пусть B1 = (v10 , . . . , vn0 ) и B2 = (v100 , . . . , vn00 ) – два базиса пространства V . Тогда мы можем связать базисные векторы (vi0 ) и (vj00 ) с помощью матрицы преобразования базиса C: vj0 = n X cij vi00 . (1.12) i=1 Для нахождения коэффициентов обратного преобразования dij выразим (vj00 ) через (vi0 ) и используем (1.12): vj00 = n X i=1 dij vi0 = n X i=1 dij n X cki vk00 = n X n X k=1 i=1 k=1 Pn dij cki vk00 = n X jk vk00 , k=1 где jk = i=1 cki dij = [CD]ij . Очевидно, что должно выполняться условие jk = δjk 12 , что эквивалентно CD = E. Таким образом, коэффициенты обратного преобразования находятся как dij = C−1 ij . ( 12 Символ Кронекера δij определяется как δij = 1, 22 i=j i 6= j. Алгебра – II Д.В. Громов Разложим вектор v по базису B1 и используем (1.12): v= n X αj0 vj0 j=1 = n X n X αj0 j=1 cij vi00 n X = i=1   n X  cij αj  vi00 . i=1 j=1 Получаем, что коэффициенты αi0 и αj00 соответствующих разложений связаны как αi00 = n X cij α0 . (1.13) j=1 Обратите внимание, что преобразование коэффициентов при смене базиса, (1.13), направлено в “обратную сторону” по сравнению с тем, как преобразуются базисные векторы, (1.12). Эта особенность привела к тому, что координатные векторы называются контравариантными. Позже мы познакомимся с ковариантными векторами. Понятия ковариантности и контравариантности не будут использоваться в рамках этого курса, но они играют большую роль в тензорном анализе – обобщении линейной алгебры. В дальнейшем мы будем часто “забывать” о базисах и вместо этого “работать в координатах”. Покажем, как этот подход может быть использован при определении матричного представления оператора T при переходе к новым базисным векторам. Пусть T ∈ L(V, W ) и в пространствах V и W определены по два базиса: B1 (V ) = (v10 , . . . , vn0 ), B2 (V ) = (v100 , . . . , vn00 ) 00 ). Координатное представление T в базисах ), B2 (W ) = (w100 , . . . , wm и B1 (W ) = (w10 , . . . , wm B1 (V ) и B1 (W ) записывается в виде матрицы A, а преобразование между базисами B1 (V ) и B2 (V ), соотв., B1 (W ) и B2 (W ) задается матрицами B и C: T vj0 = m X aij wi0 , vj00 = i=1 n X cij vi0 , wj00 = i=1 m X bij wi0 . i=1 Пусть в базисах B1 (V ) и B1 (W ) векторы v ∈ V и w ∈ W представляются своими координатами α0 ∈ F n и β 0 ∈ F m , а в базисах B2 (V ) и B2 (W ) – координатами α00 ∈ F n и β 00 ∈ F m . Теперь с использованием результата леммы 1.3.9 и (1.13) мы можем записать все преобразования в координатном виде: β 0 = Aα0 , α0 = Cα00 , β 0 = Bβ 00 . Теперь задача нахождения координатного представления оператора T в новых базисах B2 (V ) и B2 (W ) сводится к применению стандартных матричных операций: β 0 = Aα0 ⇒ Bβ 00 = ACα00 ⇒ β 00 = B−1 AC α00 . Итак, в новых базисах координатная матрица оператора T имеет вид B−1 AC. Мы будем обозначать это следующим образом: à ∼ B−1 AC. (1.14) Соответствующее преобразование опять может быть схематично изображено в виде следующей диаграммы: V T κB(V ) Fn κB(W ) A C Fn W Fm B à 23 Fm Алгебра – II Д.В. Громов Пример 1.3.3. Предположим, что нам необходимо задать координатное представление 2 оператора T ∈ L(R2 , R2 ),отражающего некоторый произвольный вектор v∈R с (канониα1 x1 2 ческими) координатами ∈ R относительно подпространства U = x2 = kx1 . α2 x2 Стандартный подход заключается в определении образов канонических базисных векторов (e1 , e2 ) под действием преобразования T : (T e1 , T e2 ) и их разложении относительно (e1 , e2 ). Однако можно поступить по другому. Описанное преобразование можно осуществить в 3 шага: 1. Перейти к новому базису (e01 , e02 ), повернув пространство R2 на угол φ = arctg(k). Тем самым мы совмещаем e01 с образующим вектором пространства U , имеющим положительную проекцию на e1 ; 2. Для нового базиса осуществить преобразование T0 (e01 , e02 ) = (e01 , −e02 ); 3. Вернуться к старому базису. В координатном виде, оператор поворота против часовой стрелки на угол φ, Trot (φ), записывается как cos(φ) − sin(φ) M(Trot (φ)) = Rφ = . sin(φ) cos(φ) −1 Легко проверить, что матрица обратного преобразования Trot (φ) = Trot (−φ) записывается > в координатном виде как Rφ . Координатное представление оператора T0 имеет вид 1 M(T0 ) = . 0 −1 Теперь мы имеем все необходимые ингредиенты. Используя — проверить и завершить! 1.3.5 Отношение эквивалентности матриц Выше мы увидели, что преобразование базиса приводит к изменению матричного представления линейного оператора. Однако независимо от базиса, все матричные представления описывают один и тот же оператор, т. е. соответствующие матрицы должны быть в какомто смысле “похожи”. В этом разделе мы дадим формальное опеределение этой похожести, а в следующих разделах рассмотрим ряд полезных следствий. Определение 1.3.9. Матрицы A и à размерности [m × n] называются эквивалентными, обозначается A ∼ Ã, если существуют такие невырожденные матрицы P и Q размерностей [m × m] и [n × n], что à = PAQ. Заметим, что в отличие от (1.14), в определении отсутствует верхний индекс (−1) при матрице P. Это отличие несущественно, так как матрицы P и Q невырождены, поэтому всегда можно переобозначить P = B−1 , соотв. Q = C. Область применения отношений эквивалентности очень широка и выходит далеко за пределы эквивалентности матриц13 . Ниже мы рассмотрим отношение эквивалентности в общем случае и определим некоторые связанные с ним понятия. 13 Например, в теории чисел отношение эквивалентности задается операцией сравнения по модулю: ∀a, b, k ∈ N, a ∼k b если a = b (mod k). На множестве комплексных чисел можно определить отношение эквивалентности различными способами, например, ∀a, b ∈ C, a ∼ b если <(a) = <(b) (для a, b ∈ C \ {0} соотв. |a| = |b| или arg(a) = arg(b)). Подумайте, как будут выглядеть классы эквивалентности для перечисленных случаев? 24 A ∼ à Алгебра – II Д.В. Громов Определение 1.3.10. Отношение эквивалентности – это бинарное отношение, заданное на некотором множестве Σ и удовлетворяющее следующим свойствам для всех a, b, c ∈ Σ: 1. Рефлексивность. a ∼ a. 2. Симметричность. a ∼ b ⇒ b ∼ a. 3. Транзитивность. (a ∼ b & b ∼ c) ⇒ a ∼ c. Отношение эквивалентности разбивает множество Σ на совокупность непересекающихся подмножеств, называемых классами эквивалентности. Определение 1.3.11. Классом эквивалентности [a] ⊂ Σ элемента a ∈ Σ называется множество элементов, эквивалентных a: [a] = {x ∈ Σ | a ∼ x} Докажите, что [a] ∩ [b] 6= ∅ ⇒ [a] = [b], ∀a, b ∈ Σ. Множество всех классов эквивалентности называется фактормножеством и обозначается Σ/ ∼. Следующий результат имеет фундаментальное значение и называется теоремой о каноническом координатном представлении линейного оператора. Теорема 1.3.10. Пусть V и W суть два конечномерных векторных пространства размерностей n и m, и T : V → W – линейное отображение ранга r. Тогда в пространствах V и W могут быть выбраны базисы B(V ) и B(W ) такие, что относительно этих базисов оператор T представляется в координатной форме как Er 0 M(T ) = . 0 0 Доказательство. Аналогично тому, как мы это делали в доказательстве теоремы 1.3.4, выберем базисы пространств V и W как B(V ) = (v1 , . . . , vr , vr+1 , . . . , vn0 ) и B(W ) = (w1 , . . . , wr , wr+1 , . . . , wm ), где векторы (vr+1 , . . . , vn0 ) образуют базис N (T ), а векторы (w1 , . . . , wr ) = (T v1 , . . . , T vr ) – базис образа T . Рассмотрим, как базисные векторы пространства V отображаются под действием T : ∀i = 1, . . . , r T vi = wi , T vj0 = 0, ∀j = r + 1, . . . , n. Переходя к координатной записи, получаем требуемое выражение. Следствие 1.3.11. Пусть A = M(T ), где отображение T имеет ранг r. Тогда существуEr 0 ют такие невырожденные матрицы P и Q, что PAQ = . 0 0 25 Алгебра – II *1.3.6 1.3.7 Д.В. Громов Факторпространство по подмножеству Матричное представление линейного отображения. Структура и свойства Начиная с этого момента мы отвлечемся от абстрактных векторных пространств и сосредоточимся на рассмотрении линейных отображений между “стандартными” векторными пространствами F n в координатной форме, возвращаясь к базисам лишь при необходимости (в основном в доказательствах теорем). Мы будем придерживаться следующих соглашений: вектор-столбцы x, y, . . . обозначают координатную запись элементов векторных пространств относительно некоторых базисов, которые полагаются известными (обычно используются канонические базисы). Число элементов в столбце равняется числу базисных векторов и, соответственно, размерности векторного пространства. Матрицы A, B, . . . обозначают соответствующие линейные отображения в координатной форме. Для краткости мы будем говорить линейный оператор A вместо линейный оператор. заданный своим координатным представлением A и аналогично для векторов. Теперь мы готовы сформулировать некоторые введенные ранее понятия в координатной форме. Линейной комбинации элементов векторного пространства соответствует линейная комбинация координатных векторов; аналогично для координатных векторов определяется свойство линейной зависимости/независимости. Ядро и образ линейного отображения A : Rn → Rm определяются как N (A) = {x ∈ Rn | Ax = 0}, R(A) = span(a×,1 , . . . , a×,n ). Напомним, что span(a×,1 , . . . , a×,n ) обозначает линейную оболочку столбцов матрицы A. Тогда как определение ядра интуитивно понятно, установление связи между приведенным определением образа и ранее данным требует небольших усилий. Этот анализ остается в качестве самостоятельной работы. Две эквивалентные матрицы описывают координатное представление одного и того же линейного оператора относительно разных базисов. Очевидно, что преобразование базиса оставляет неизменными размерности основных подпространств, связанных с линейным отображением. Утверждение 1.3.12. Пусть A и à – два эквивалентных матричных представления оператора T . тогда верно следующее: dim(N (A)) = dim(N (Ã)), rank(A) = dim(R(A)) = dim(R(Ã)) = rank(Ã). (1.15) Сформулируем критерий для определения ранга линейного отображения. Лемма 1.3.13. Ранг линейного оператора A равен числу линейно независимых столбцов матрицы A14 . 14 Такое определение может вызывать некоторую путаницу. “Правильная” формулировка должна звучать так: ранг линейного оператора T : V → W равен числу линейно независимых столбцов в координатном 26 Алгебра – II Д.В. Громов Доказательство. Самостоятельно. Лемма 1.3.14. Для двух линейных операторов A и B согласованных размерностей верно rank(AB) ≤ rank(A). Доказательство. Используя свойство композиции линейных операторов запишем (AB)x = A(Bx) = Ay. Для любого вектора y выполняется Ay ∈ R(A). Это значит, что каждый вектор (AB)x может быть представлен в виде линейной комбинации базисных векторов R(A). Следовательно, размерность образа AB не может превышать размерность образа A. Наконец, используя следствие 1.3.11 и утверждение 1.3.12, мы получаем следующий важный результат. Теорема 1.3.15. Для любого оператора A верно rank(A) = rank(A> ) Доказательство. Если оператор A может быть приведен к канонической форме путем умножения слева и справа на матрицы P и Q, то транспонированный оператор A> может быть приведен к транспонированной канонической форме путем умножения на матрицы P0 = Q> и Q0 = P> : P0 A> Q0 = Q> A> P> = (PAQ)> . Легко проверить, что ранги соответствующих канонических представлений совпадают. Следствие 1.3.16. Пусть A имеет размерность [n × m]. Тогда rank(A) ≤ min{n, m}. Лемма 1.3.17. Для двух операторов A и B таких, что композиция AB определена, выполняется rank(AB) ≤ min {rank(A), rank(B)} . Доказательство. Имеем rank(AB) ≤ rank(A) и rank(AB) = rank(B> A> ) ≤ rank(B> ) = rank(B). Наконец, сформулируем результат, который носит название ранговой факторизации и, как мы убедимся позже, играет большую роль во многих приложениях. Теорема 1.3.18. Любой оператор A размерности [m × n], удовлетворяющий rank(A), может быть представлен в виде композиции двух операторов A = BC размерностей [m × r] и [r × n]. Доказательство. Добавить!!! представлении T , A = M(T ), взятом относительно некоторых произвольных базисов B(V ) и B(W ). Однако мы будем немного злоупотреблять обозначениями и использовать “упрощенные” формулировки, как было оговорено выше. 27 Алгебра – II 1.3.8 Д.В. Громов Системы линейных алгебраических уравнений с операторной точки зрения Решение СЛАУ. Посмотрим, как аппарат линейной алгебры может помочь нам при анализе решений СЛАУ. Вспомним, что неоднородная СЛАУ имеет вид Ax = b. Очевидно, это не что иное, как координатная запись линейного отображения элемента x в b под действием линейного оператора A. Теперь все детали головоломки становятся на свои места ,. Лемма 1.3.19. Линейная система Ax = b (1.16) имеет решение x∗ тогда и только тогда, когда b ∈ R(A). Кроме того, любое решение этой системы имеет вид x = x∗ + z, где z ∈ N (A). Доказательство. Первая часть верна по определению образа линейного оператора. Чтобы показать вторую часть предположим, что x и x∗ – два решения (1.16), т. е. Ax = b = Ax∗ . Тогда A(x − x∗ ) = 0 ⇒ x − x∗ = z ∈ N (A). Сформулируем свойства СЛАУ (1.16) в категориях свойств соответвующего линейного оператора: 1. СЛАУ (1.16) совместна если b ∈ R(A). 2. СЛАУ (1.16) определена если она совместна и N (A) = {0}. Наконец, следующее определение будет играть большую роль в теории линейных дифференциальных уравений, в том числе с частными производными. Определение 1.3.12. Фундаментальной системой решений (ФСР) системы однородных уравнений Ax = 0 называется максимальный набор линейно-независимых решений этой системы. Очевидно, что ФСР совпадает с базисом N (A). Используя ранее введенные понятия мы сможем легко доказать известную теорему Кронекера-Капелли. Надо заметить, что известна она еще и тем, что имеет по меньшей мере пять имен, от теоремы Руше-Капелли до теоремы Фробениуса. Теорема 1.3.20. Система линейных алгебраических уравнений Ax = b является совместной (т. е. имеет по крайней мере одно решение) тогда и только тогда, когда ранг матрицы A равен рангу расширенной матрицы [A | b]: rank A = rank[A | b]. Доказательство. Самостоятельно. Использовать определение образа A. Заметим, что при всей своей привлекательности, практическая ценность теоремы КронекераКапелли невелика. Дело в том, что наиболее эффективным способом определения ранга матрицы является ее сведение с матрице ступенчатого вида по строкам, как мы обсуждали в первой части курса. Но если мы привели расширенную матрицу [A | b] к такому виду, то вопрос существования решений решается очевидным образом и необходимости в вычислении ранга матрицы A нет. 28 Алгебра – II Д.В. Громов Альтернатива Фредгольма. Пример 1.3.4. Рассмотрим линейное дифференциальное уравнение порядка n с вещественными постоянными коэффициентами: x(n) (t) + a1 x(n−1) (t) + · · · + an−1 x0 (t) + an x(t) = f (t). (1.17) Уравенение (1.17) называется однородным если f (t) ≡ 0 и неоднородным в противном случае. Будем полагать, что x(t) и f (t) принадлежат векторному пространству вещественнозначных бесконечно-дифференцируемых функций, определенных на положительной полуоси: C ∞ ([0, ∞), R). Тогда уравнение (1.17) можно представить как n dn−1 d d + a1 n−1 + · · · + an−1 + an x(t) = f (t), Ln x(t) = dtn dt dt где Ln – линейный оператор из C ∞ ([0, ∞), R) в C ∞ ([0, ∞), R). Согласно лемме 1.3.19, решение дифференциального уравнения (1.17) имеет вид x(t) = x∗ (t) + z(t), где z(t) ∈ N (Ln ). Из чего же состоит ядро линейного оператора Ln ? Очевидно, что это должны быть функции из C ∞ ([0, ∞), R), удовлетворяющие однородному уравнению z (n) (t) + a1 z (n−1) (t) + · · · + an−1 zn−1 (t) + an zn (t) ≡ 0. (1.18) Выберем z(t) = eλt . Подставляя эти функции в (1.18) мы получим (λn + a1 λn−1 + · · · + an−1 λn−1 + an )eλt ≡ 0. Это уравнение выполняется в том случае, когда параметры λ выбираются как корни т. н. характеристического полинома λn + a1 λn−1 + · · · + an−1 λn−1 + an = 0 Если все корни характеристического полинома λ1 , . . . , λn различны, то функции eλi t , образуют базис N (Ln ). Тот факт, что любое решение (1.18) может быть представлено в виде линейной комбинации экспонент требует знания некоторых дополнительных фактов о существовании и единственности решений дифференциальных уравнений и не будет тут доказываться. А как обстоит дело с линейной независимостью? Необходимо показать, что уравнение α1 eλ1 t + · · · + αn eλn t ≡ 0 (1.19) выполняется только при α1 = · · · = αn = 0. Вычислим значение (1.19) в n точках t = 0, 1, . . . , n − 1. Получим систему α1 + α2 + ... + αn = 0 α1 p1 .. . + α2 p2 + . . . + αn pn = 0 (1.20) α1 pn−1 + α2 pn−1 + . . . + αn pn−1 = 0, n 1 2 где мы использовали обозначение pi = eλi . Можно легко заметить, что эта система уравнений соответствует умножению матрицы Вандермонда на вектор коэффициентов. Система (1.20) имеет нетривиальное решение в том случае, когда определитель матрицы Вандермонда равен нулю. Мы помним, что это условие выполняется если существуют по крайней мере два коэффициента pi = pj , i 6= j. Однако по условию, λi 6= λj ∀i 6= j и, следовательно, pi 6= pj . Поэтому система (1.20) имеет единственное, тривиальное решение. 29 Алгебра – II Д.В. Громов Задачи и вопросы Ниже V , W и U обозначают конечномерные линейные пространства, Pn – пространство полиномов степени, не превышающей n. 1. Пусть T ∈ L(V, W ) и дан набор векторов {v1 , . . . , vk } такой, что векторы {T v1 , . . . , T vk } линейно независимы. Докажите, что векторы {v1 , . . . , vk } также линейно независимы. 2. Приведите пример функции из R × R в R, для которой выполняется свойство однородности, но не выполняется свойство аддитивности. 3. Приведите пример функции из C в C, для которой выполняется свойство аддитивности, но не выполняется свойство однородности. 4. Пусть V ⊂ U – собственное (т. е. V 6= U ) линейное подпространство U . Для u ∈ U рассмотрите отображение ( u, u ∈ V Tu = 0, u ∈ / V. Будет ли T линейным оператором? 5. Пусть V и U – линейные пространства, причем V ⊂ U , а T : V → V – линейный оператор. Предложите, как можно расширить T на U , т. е. определить оператор S : U → U такой, что Su = T u для всех u ∈ V . 6. Приведите пример линейного отображения T : P5 → P5 такого, что dim(N (T )) = 2. 7. Приведите пример линейного отображения T : V → V такого, что R(T ) = N (T ). Всегда ли возможно найти такое отображение? В качестве примера рассмотрите V = R4 и V = R5 .       x1    . 8. Пусть T : F 5 → F 3 – линейный оператор и N (T ) =  .. ∈ F 5 x1 + x2 = 0, x2 + x3 = 0, x3 + x4 = 0 .     x5 Докажите, что T задает сюръективное отображение. 9. Пусть T ∈ L(V, W ) и S ∈ L(W, U ). Докажите, что dim(N (ST )) ≤ dim(N (S)) + dim(N (T )). Сравните с выражением для dim(R(ST )) = rank(ST ). 10. Пусть T ∈ L(V, F ) и V 3 v ∈ / N (T ). Докажите, что V = N (T ) ⊕ {αv|α ∈ F }. 11. Рассмотрите следующие отображения из P5 в P5 : T1 : p(x) 7→ p0 (x) + 2p(x), T2 : p(x) 7→ xp00 (x) + 1. Запишите координатные представления операторов T1 и T2 относительно канонического базиса P5 . 12. Пусть размерности пространств V и W равны 4 и 5, соответственно, а координатная матрица A оператора T ∈ L(V, W ) содержит k = 17 нулевых элементов. Оцените размерности dim(N (T )) и dim(R(T )). 13. 14. 30 Алгебра – II 1.4 1.4.1 Д.В. Громов Геометрия линейных пространств Норма вектора До сих пор мы рассматривали элементы векторных пространств как объекты, не имеющие длины или положения. Мы не пытались сравнивать различные векторы, определять степень их близости или взаимное расположение. Настало время восполнить этот недочет. Начнем с понятия “длины” вектора. В этом разделе и дальше мы будем рассматривать элементы пространства F n , где F может быть множеством вещественных или комплексных чисел. Конечно, все полученные результаты могут быть распространены на любые векторные пространства, для которых определены соответствующие операции. Так, в качестве примера мы будем иногда рассматривать пространство полиномов. Однако основной наш интерес все-таки будет сосредоточен на пространствах Cn и Rn , для которых мы будем формулировать все результаты. Определение 1.4.1. Нормой называется отображение из векторного пространства F n в R, обозначается k · k : F n → R, удовлетворяющее следующим свойствам (аксиомам нормы) для всех x, y ∈ F n и всех α ∈ F : 1. Свойство точечной отделимости: kxk = 0 ⇒ x = 0. 2. Неравенство треугольника: (субаддитивность) kx + yk ≤ kxk + kyk. 3. Свойство абсолютной однородности: kαxk = |α| · kxk. Заметим, что отображение из векторного пространства в множество вещественных чисел обычно называется функционалом. Лемма 1.4.1. Для нормы выполняется свойство положительной определенности: ( = 0, x = 0 kxk ≥ 0, x 6= 0 Доказательство. Для v = 0 имеем k0k = k0 · 0k = 0 · k0k = 0 (свойство 3). Если x 6= 0, выполняется 0 = kx − xk ≤ kxk + k − xk = kxk + kxk, следовательно, kxk ≥ 0. Ниже мы определим стандартные нормы для F = R и F = C. Обратите внимание: способ вычисления нормы вектора различается для вещественных и комплексных векторных пространств. Дальше мы будем неоднократно сталкиваться с подобными различиями. Определение 1.4.2. Пусть x = [x1 , x2 , . . . , xn ]> ∈ F n . Стандартная (евклидова) норма kxk определяется следующим образом: F = R: kxk = F = C: kxk = p q x21 + x22 + · · · + x2n . |x1 |2 + |x2 |2 + · · · + |xn |2 = 31 √ x1 x̄1 + x2 x̄2 + · · · + xn x̄n . (1.21) (1.22) k·k Алгебра – II Д.В. Громов Проверьте, что приведеные выражения удовлетворяют аксиомам нормы. Подумайте, почему мы не можем использовать (1.21) для вычисления нормы элементов Cn ? Мы будем называть вектор x единичным если kxk = 1. Процедура нормировки (ненулевого) вектора заключается в его делении на норму покомпонентно: y= 1 x. kxk С геометрической точки зрения векторы y и x имеют “одинаковое направление” и отличаются лишь длиной. С помощью нормы можно не только сравнивать два вектора x и y, но и определять степень их близости, вычислив значение kx − yk. Обратите внимание, что по определению kx − yk = ky − xk и kx − yk = 0 только если x = y. ∗ Альтернативные нормы. Очевидно, что норма вектора может быть определена неединственным образом. Во-первых, мы можем “модифицировать” евклидову норму путем назначения каждой компоненте xi вектора x некоторого неотрицательного веса αi > 0: p kxk = α1 |x1 |2 + α2 |x2 |2 + · · · + αn |xn |2 . Использование такой нормы эквивалентно тому, что мы переходим к новому базису, в котором направление базисных векторов остается прежним, а длина изменяется на величину, √ пропорциональную αi . С точки зрения математики такие нормы являются вариантом евклидовой нормы, однако в приложениях они играют большую роль, так как позволяют учесть неоднородную структуру данных, с которыми мы работаем. Однако существуют и другие, принципиально отличные способы определения норм. Рассмотрим два случая. 1. Манхэттенское расстояние, или норма `1 : kxk1 = |x1 | + |x2 | + · · · + |xn | 2. max-норма или равномерная норма: kxk∞ = max {|x1 |, |x2 |, . . . , |xn |} . *1.4.2 Операторная норма В то время, как норма вектора может быть интерпретирована как его “длина”, норма оператора A : F n → F m характеризует степень воздействия этого оператора на векторы из пространства F n . Для того, чтобы “измерить” это воздействие, мы будем использовать векторные нормы, заданные для пространств F n и F m (а в общем случае, когда A действует из V в W , для пространств V и W ). Введенная таким образом норма называется индуцированной нормой оператора A или, иначе говоря, операторной нормой15 . Определение 1.4.3. Пусть A : F n → F m – линейный оператор, а k·k – норма, определенная на соответствующих векторных пространствах16 . Тогда норма оператора A определяется как kAxk (∗) kAk = max = max kAxk. (1.23) x6=0 kxk kxk=1 15 Существуют 16 Обычно и другие способы определения норм операторов, но мы не будем их рассматривать. на пространствах F n и F m берется одна и та же норма, но это не обязательно. 32 Алгебра – II Д.В. Громов Обе формулировки нормы в (1.23) эквивалентны, так как равенство (∗) следует из свойства однородности линейного оператора. Независимо от того, посредством какой векторной нормы была введена операторная норма, она удовлетворяет всем свойствам нормы в смысле определения 1.4.1. Кроме того, выполняется ряд других полезных свойств. Лемма 1.4.2. Пусть на векторном пространстве F n задана некоторая норма k · kx , которая порождает операторную норму k · kx . Сформулируем ряд свойств, которым удовлетворяет операторная норма k · kx . Пусть A и B – два линейных оператора согласованных размерностей, а α ∈ F – скаляр. Тогда выполняется 1. kAkx ≥ 0 и kAkx = 0 ⇔ A = 0, 2. kαAkx = |α| · kAkx , 3. kA + Bkx ≤ kAkx + kBkx , 4. kAxkx ≤ kAkx · kxkx , 5. kABkx ≤ kAkx · kBkx . Доказательство. Свойства 1. – 3. следуют из определения операторной нормы и из свойств векторной нормы. Мы докажем только последние два свойства: x мы опустим максимизацию, то ра4. Если в правой части равенства kAkx = max kAxk x6=0 kxkx венство превратится в неравенство: kAkx ≥ kAxkx , kxkx откуда следует требуемый результат kAkx · kxkx ≥ kAxkx . 5. Последнее доказательство основано на том, что максимум по двум связанным аргументам не превышает максимума по двум независимым аргументам17 . kABkx = max x6=0 kABxkx kAy(x)kx kBxkx kAykx kBxkx = max · ≤ max ·max = kAkx ·kBkx , x6=0 ky(x)kx y6=0 kykx x6=0 kxkx kxkx kxkx где мы определили y(x) = Bx. Нормы, для которых выполняется свойство 5., называются субмультипликативными. Рассмотрим два примера координатного выражения для двух операторных норм, соответствующих векторным нормам k·k1 и k·k∞ . Конечно, наиболее интересный случай представляет собой норма, порожденная обычной евклидовой нормой, так называемая спектральная норма. Однако для ее рассмотрения требуются некоторые факты, с которыми мы пока еще не познакомились, поэтому мы оставим рассмотрение спектральной нормы на потом. 17 Сравните max sin(x) cos(y(x)) при любом выборе y(x), например для y(x) = x и max sin(x) cos(y). x x,y 33 Алгебра – II Д.В. Громов Пусть A : F n → F m . Тогда операторные нормы kAk1 и kAk∞ могут быть выражены через коэффициенты координатного представления A следующим образом: kAk1 = max j kAk∞ = max i 1.4.3 m X i=1 n X |aij |, |aij |. j=1 Скалярное произведение Теперь мы займемся определением взаимного расположения двух векторов. Однако начнем мы немного издалека и сначала определим операцию скалярного произведения. Определение 1.4.4. Скалярное произведение на векторном пространстве F n – это отображение h·, ·i : F n × F n → F , удовлетворяющее следующим свойствам для всех x, y, z ∈ F n и всех α ∈ F : 1. Положительная определенность: ( hx, xi > 0, ∀x ∈ F n \ {0}, h0, 0i = 0. 2. Эрмитовость: hx, yi = hy, xi 3. Линейность по первому аргументу: hαy, xi = αhy, xi hy + z, xi = hy, xi + hz , xi. Из определения 1.4.4 можно вывести ряд дальнейших свойств скалярного произведения. Лемма 1.4.3. Скалярное произведение, определенное выше, удовлетворяет следующим свойствам для всех x, y, z ∈ F n и всех α ∈ F : 1. hx, xi ∈ R, 2. h0, yi = hx, 0i = 0, 3. hx, y + zi = hx, yi + hx, zi, 4. hx, αyi = ᾱhx, yi. Доказательство. Самостоятельно. Обратите внимание, что в скалярном произведении, определенном на Cn , первая и вторая позиции неравноправны. Поэтому скалярное произведение, заданное на комплексном векторном пространстве иногда называют полуторалинейной (англ., sesquilinear) формой18 в отличие от скалярного произведения на Rn , которое называется билинейной формой. 18 В общем случае, форма – это отображение из декартового произведения n векторных пространств F m в F . Заметим, что определитель матрицы [n × n] – это полилинейная форма, заданная на декартовом произведении n векторных пространств. В качестве элементов этих пространств можно рассматривать строки или столбцы матрицы. 34 hx, yi Алгебра – II Д.В. Громов Скалярное произведение может быть введено различными способами. В дальнейшем мы будем использовать стандартное определение евклидова скалярного произведения (опуская слово “евклидово”). Определение 1.4.5. Скалярное произведение двух векторов x, y ∈ F n определяется для F = R: hx, yi = x1 y1 + x2 y2 + . . . + xn yn . (1.24) hx, yi = x1 ȳ1 + x2 ȳ2 + . . . + xn ȳn . (1.25) F = C: Стандартная норма вектора, введенная в (1.21) и (1.22), может быть иначе определена как квадратный корень скалярного произведения этого вектора с самим собой: p kxk = hx, xi. В таких случаях мы будем говорить, что скалярное произведение, заданное в некотором векторном пространстве, порождает в этом пространстве естественную (или стандартную) норму. Понятие скалярного произведения может быть равным образом определено для бесконечномерных пространств. Так, например, на множестве непрерывных функций, определенных на интервале [a, b], f (t), g(t) ∈ C([a, b], F ), скалярное произведение можно определить как Z b hf (t), g(t)i = f (t)ḡ(t)dt. (1.26) a Соответственно, (1.26) порождает в C([a, b], F ) естественную норму: kf (t)k = qR b a |f (t)|2 dt. Скалярное произведение удовлетворяет неравенству Коши-Буняковского-Шварца. Это важное неравенство, которое еще неоднократно встретится вам в различных областях математики. Теорема 1.4.4. Пусть x, y ∈ F n . Тогда верно |hx, yi| ≤ kxk · kyk. (1.27) Доказательство. Для y = 0, неравенство (1.27) тождественно обращается в равенство. Рассмотрим случай y 6= 0 и запишем выражение для квадрата нормы вектора x − αy. Очевидно, что это выражение неотрицательно. Кроме того, мы имеем 0 ≤ kx − αyk2 = hx − αy, x − αyi = = hx, xi + hx, −αyi + h−αy, xi + h−αy, −αyi = = kxk2 − ᾱhx, yi − αhx, yi + αᾱkyk2 . Подставляя в полученное выражение α = hx, yi/kyk2 , получаем 0 ≤ kxk2 − откуда следует (1.27). 35 |hx, yi|2 , kyk2 Алгебра – II Д.В. Громов Для двух векторов из R2 понятие скалярного произведения допускает интуитивную интерпретацию. Посмотрим на векторную диаграмму, изображенную на рисунке справа. Мы можем записать kx − yk2 = kxk2 + kyk2 − 2hx, yi. В то же время, по теореме косинусов мы имеем kx − yk2 = kxk2 + kyk2 − 2kxk·kyk cos φ, т. е. в двумерном вещественном случае скалярное произведение двух векторов равно произведению их длин на косинус угла между ними. Применительно к векторам из Rn , становится менее очевидно, как измерять угол между векторами, поэтому мы введем его через определение. Определение 1.4.6. Угол φ между двумя векторами x, y ∈ Rn определяется как hx, yi , φ ∈ [0, π]. φ = arccos kxk·kyk В Rn угол между двумя векторами x и y равен углу между этими векторами в подпространстве span(x, y). Однако если мы возьмем два вектора из Cn , то окажется, что понятие угла можно ввести различными способами, см. [4]. Ну а если рассмотреть пространство полиномов Pn , то смысл угла между двумя полиномами и вовсе теряется. Поскольку нас интересуют конструкции, общие для различные векторных пространств, мы оставим задачу нахождения углов между векторами для курса евклидовой геометрии и сосредоточимся на рассмотрении одного специального случая. 1.4.4 Ортогональная проекция. Ортогональное дополнение Определение 1.4.7. Два вектора x, y ∈ F n называются ортогональными, обозначается x ⊥ y, если их скалярное произведение равно нулю: hx, yi = 0. Понятие ортогональности является обобщением свойства перпендикулярности двух векторов, известного нам из классической евклидовой геометрии. Заметим, что по свойству 2 леммы 1.4.3, нулевой вектор ортогонален любому вектору x ∈ F n . Аналогично ортогональным векторам, можно ввести понятие параллельных векторов. Определение 1.4.8. Два вектора x, y ∈ F n называются параллельными, обозначается x k y, если y = αx, где α ∈ F . Теорема 1.4.5. Пусть x, y ∈ F n . Тогда вектор x можно представить в виде суммы двух векторов, один из которых будет параллелен y, а второй ортогонален y: x = projy x + orthy x. (1.28) Первый вектор называется ортогональной проекцией x на y и вычисляется по формуле projy x = 36 hx, yi y. kyk2 projy x orthy x Алгебра – II Д.В. Громов Доказательство. Представим x в виде суммы двух векторов u и v таких, что u = αy и v ⊥ y. Запишем 0 = hv, yi = hx − αy, yi = hx, yi − αhy, yi, откуда мы выражаем α. Подставляя найденное выражение в u = αy получаем требуемый результат. Заметим, что ортогональная компонента v находится как orthy x = x − hx, yi y. kyk2 (1.29) Разложение вектора на две ортогональные друг другу компоненты может быть полезно при решении многих задач. Посмотрим, как можно использовать этот подход на примере альтернативного доказательства теоремы Коши-Буняковского-Шварца. Доказательство теоремы 1.4.4. Так же как и в первом доказательстве, предположим, что y 6= 0. Представим x в виде (1.28) и запишем выражение для квадрата нормы kxk2 : hx, yi y kyk2 |hx, yi|2 ≥ , kyk2 kxk2 = 2 + k orthy xk2 (1.30) где равенство (1.30) следует из теоремы Пифагора (см. задание 3). Преобразовывая полученное неравенство получаем (1.27). Задачу нахождения ортогональной проекции вектора на вектор можно обобщить на случай ортогональной проекции вектора на подпространство. Пусть V ⊂ F n и x ∈ F n суть линейное подпространство и вектор, не принадлежащий этому подпространству, x ∈ / V . Подобно тому, как мы делали раньше, вектор x можно представить в виде суммы двух векторов, один из которых принадлежит V , а второй ортогонален со всеми векторами из V : x = projV x + orthV x, причем projV x ∈ V и horthV x, vi = 0 ∀ v ∈ V. В следующем разделе мы вернемся к этому вопросу и изучим в деталях, как строится ортогональная проекция на подпространство. А сейчас остановимся на одном исключительно важном свойстве ортогональной проекции. Предположим, что нам нужно выбрать вектор из V , максимально близкий к вектору x (который, так же как и раньше, не принадлежит V ). Мы помним, что расстояние между двумя векторами может быть естественным образом задано как норма их разности: dist(x, y) = kx − yk. Таким образом, задача может быть поставлена следующим образом: b ∈ V , что неравенство найти такой вектор x kb x − xk ≤ kv − xk выполняется для всех векторов v ∈ V . 37 (1.31) Алгебра – II Д.В. Громов Из курса евклидовой геометрии мы знаем, что (по крайней мере в R3 ) среди всех отрезков, опущенных из точки на плоскость, наименьшей длиной обладает высота, т. е. ортогональная составляющая нашего вектора orthV x = x − projV x. Можно предположить, что решением поставленной задачи должна служить проекция вектора projV x, как подтверждает следующая теорема. Теорема 1.4.6. Пусть V ⊂ F n – линейное подпространство V , а x ∈ F n – некоторый b ∈ V следующие два утверждения эквивавектор, не принадлежащий V . Для вектора x лентны: 1. Неравенство (1.31) выполняется для всех v ∈ V и обращается в равенство только b. для v = x 2. Выполняется (b x − x) ⊥ V . Доказательство. Начнем с [2.] → [1.] Мы имеем (∗) bk2 + kb b) + (b x − xk2 ≥ kb x − xk2 , kv − xk2 = k(v − x x − x)k2 = kv − x b ∈ V , а (b где равенство (∗) следует из теоремы Пифагора, так как v − x x − x) ⊥ V . Взяв квадратный корень из обеих частей неравенства, получаем (1.31). Заметим, что слагаемое bk2 всегда неотрицательно и обращается в ноль только при v = x b. kv − x Теперь докажем [1.] → [2.] Определим функцию ε(t) = k(b x +tv)−xk2 , где t ∈ R, а v – некоторый произольный вектор из V . Поскольку (1.31) выполняется для всех v ∈ V , функция ε(t) имеет минимум в точке t = 0. Раскроем выражение для ε(t), поменяв порядок слагаемых: b − x + tvi = hb b − xi + htv, x b − xi + hb ε(t) = hb x − x + tv, x x − x, x x − x, tvi + htv, tvi = = kb x − xk2 + 2 t <(hb x − x, vi) + t2 kvk2 . Из курса анализа мы знаем, что функция имеет минимум в точке, если ее первая производная в этой точке равна нулю, а вторая производная строго положительна19 . В нашем случае, условие экстремальности первого порядка имеет вид ε0 (t) t=0 = 2 <(hb x − x, vi) = 0, а вторая производная ε00 (t) = 2kvk2 положительно определена везде, за исключением v = 0. Итак, из условия минимизации следует <(hb x −x, vi) = 0. Вектор v выбирается произвольно, поэтому наряду с v мы можем рассмотреть ṽ = iv: x − x, ivi = −ihb x − x, vi + ihb x − x, vi = 2<(hb x − x, ṽi) = 2<(hb x − x, ivi) = hb x − x, ivi + hb = −i hb x − x, vi − hb x − x, vi = −i · 2 i=(hb x − x, vi) = 2=(hb x − x, vi). Итак, из произвольности выбора v следует, что как вещественная, так и мнимая часть скалярного произведения hb x − x, vi должна быть равна нулю. Следовательно, выполняется (b x − x) ⊥ v. Ортогональное дополнение. Включить в следующей версии. 19 Более того, в данном случае мы имеем дело с квадратичной функцией, которая имеет единственный экстремум. 38 Алгебра – II 1.4.5 Д.В. Громов Ортонормированный базис. Процедура Грама-Шмидта В пространствах со скалярным произведением многие операции сильно упрощаются, если в качестве базиса выбрать систему нормированных и взаимно ортогональных векторов. Определение 1.4.9. Набор векторов (e1 , . . . , en ) называется ортонормированным, если 1. Каждый вектор имеет единичную норму, kei k = 1, i = 1, . . . , n; 2. Все векторы попарно ортогональны, hei , ej i = 0, i 6= j. Если набор векторов (e1 , . . . , en ) образует базис пространства F n , этот базис называется ортонормированным. Самым простым примером ортонормированного базиса является канонический евклидов базис. Однако уже в пространстве полиномов Pn cо скалярным произведением, заданным R1 выражением hf, gi = −1 f (t)g(t)dt, канонический базис (1, x, x2 , . . . ) не является ортонормированным. В примере 1.4.1 мы увидим, как с использованием процедуры Грама-Шмидта на основе существующего неортогонального базиса можно построить ортонормированный базис. Сначала сформулируем несколько результатов, демонстрирующих удобство работы с ортонормированными базисами. Лемма 1.4.7. Пусть векторPy ∈ F n представлен в виде линейной комбинации ортонорn мированных векторов, y = i=1 αi ei . Тогда квадрат его нормы равен сумме квадратов абсолютных значений соответствующих коэффициентов (а для Rn – просто сумме квадратов): kyk2 = |α1 |2 + · · · + |αn |2 . (1.32) Доказательство. Раскрыть выражение для kyk2 учитывая, что hei , ej i = 0, i 6= j. Альтернативное доказательство основано на последовательном использовании теоремы Пифагора (см. задание 3). Лемма 1.4.8. Любой набор ортонормированных векторов линейно независим. Доказательство. Рассмотрим набор ортонормированных векторов (e1 , . . . , en ). Если бы эти вектора были линейно зависимыми, то для некоторого набора коэффициентов αi ∈ F , не всех равных нулю, выполнялось бы y = α1 e1 + · · · + αn en = 0. Таким образом норма kyk = k0k = 0 и, следовательно, |α1 |2 + · · · + |αn |2 = 0. Но это значит, что все коэффициенты αi равны нулю. Приходим к противоречию. Лемма 1.4.9. Пусть набор E = (e1 , . . . , en ) задает ортонормированный базис F n . Тогда разложение вектора y ∈ F n по базису E имеет вид y = hy, e1 i e1 + . . . + hy, en i en , а квадрат нормы y равен kyk2 = |hy, e1 i|2 + . . . + |hy, en i|2 . 39 (1.33) Алгебра – II Д.В. Громов Доказательство. Поскольку E является базисом, каждый вектор y может быть однозначно представлен в виде линейной комбинации векторов из E: y = α1 e1 + . . . αn en . (1.34) Вычисляя скалярное произведение левой и правой части (1.34) с ei и принимая во внимание, что базисные векторы ортонормированы, получаем αi = hy, ei i. Выражение для квадрата нормы следует из (1.32). Процедура ортогонализации Грама-Шмидта. Предположим, что нам дан некоторый базис (x1 , x2 , . . . , xn ) пространства F n . Покажем, как на основе этого базиса можно построить ортонормированный базис (e1 , e2 , . . . , en ). Компоненты нового базиса определяются итеративно, с использованием ортонормированных базисных векторов, определенных на предыдущих шагах. 1. В качестве первого элемента нового базиса выбираем нормированный вектор x1 : e1 = x1 . kx1 k 2. Второй элемент выбирается как нормированная ортогональная компонента вектора x2 при проекции на e1 (вспомним выражение (1.29) и учтем, что e1 – единичный вектор): e2 = x2 − hx2 , e1 ie1 kx2 − hx2 , e1 ie1 k 3. Дальше мы берем нормированную ортогональную компоненту проекции вектора x3 на вектора e1 и e2 (т. е. ту “часть” вектора x3 , которая ортогональна как e1 , так и e2 ): e3 = x3 − hx3 , e1 ie1 − hx3 , e2 ie2 kx3 − hx3 , e1 ie1 − hx3 , e2 ie2 k .. . i. Действуя аналогично, приходим к выражению для i-й компоненты нового базиса: ei = xi − hxi , e1 ie1 − · · · − hxi , ei−1 iei−1 kxi − hxi , e1 ie1 − · · · − hxi , ei−1 iei−1 k (1.35) Описанная процедура может быть применена к любому набору линейно независимых векторов, которые не должны обязательно образовывать базис. Достоинство метода Грама-Шмидта заключается в том, что он позволяет конструктивно вычислять новый базис на основе существующего, т. е. он не только говорит, что ортонормированный базис существует, но и позволяет его найти. Это очень важно, так как в математике мы нередко сталкиваемся с ситуациями, когда мы можем доказать, что некоторый объект существует, но не знаем как его найти. В (абстрактной) линейной алгебре таким примером служит базис Гамеля20 : множество элементов пространства V таких, что любой вектор v ∈ V может быть представлен единственным образом в виде линейной комбинации 20 Georg Hamel (1877 – 1954), немецкий математик. Известен своими работами, посвященными основаниям математики и аксиоматизации классической механики. 40 Алгебра – II Д.В. Громов некоторого конечного подмножества базисных векторов. Можно доказать, что существует базис Гамеля, с которым множество вещественных чисел образует векторное пространство над полем рациональных чисел (подумайте об этом!). Однако конструктивно построить этот базис невозможно, так как его существование основано на аксиоме выбора. Однако вернемся к процедуре ортогонализации Грама-Шмидта и формально докажем, что она действительно решает поставленную задачу. Теорема 1.4.10. Пусть (x1 , x2 , . . . , xn ) – набор линейно независимых векторов. Тогда набор векторов (e1 , e2 , . . . , en ), вычисленных итеративно по формуле (1.35), составляет ортонормированную систему и при этом выполняется span(e1 , e2 , . . . , en ) = span(x1 , x2 , . . . , xn ). Доказательство. Проведем доказательство по индукции. Для i = 1 вектор e1 составляет ортонормированную систему и, кроме того, span(e1 ) = span(x1 ). Предположим, что для некоторого 1 < i < n набор (e1 , e2 , . . . , ei−1 ) является ортонормированным и выполняется span(e1 , . . . , ei−1 ) = span(x1 , . . . , xi−1 ). Поскольку векторы (x1 , . . . , xn ) линейно независимые, xi ∈ / span(x1 , . . . , xi−1 ). Также выполняется xi ∈ / span(e1 , . . . , ei−1 ), поскольку линейные оболочки двух наборов совпадают. Таким образом, знаменатель в выражении (1.35) для ei не равен нулю и выражение определено. Пусть j < i. Рассмотрим скалярное произведение hei , ej i. Получаем hei , ej i = xi − hxi , e1 ie1 − · · · − hxi , ei−1 iei−1 , ej kxi − hxi , e1 ie1 − · · · − hxi , ei−1 iei−1 k = = hxi , ej i − hxi , ej ihej , ej i = 0, kxi − hxi , e1 ie1 − · · · − hxi , ei−1 iei−1 k где мы использовали тот факт, что набор (e1 , . . . , ei−1 ) является ортонормированным, следовательно hej , ej i = 1 и hek , ej i = 0 для всех 1 < k 6= j < i. Таким образом, расширенный набор (e1 , . . . , ei−1 , ei ) также является ортонормированным. Осталось показать, что линейные оболочки наборов (x1 , . . . , xi ) и (e1 , . . . , ei ) совпадают. Из выражения (1.35) следует, что xi ∈ span(e1 , . . . , ei ). Следовательно, span(x1 , . . . , xi ) ⊆ span(e1 , . . . , ei ). Однако векторы (x1 , . . . , xi ) и (e1 , . . . , ei ) линейно независимы, одни по условию теоремы, другие согласно лемме 1.4.8. Обе линейные оболочки имеют одинаковую размерность и, следовательно, совпадают. Пример 1.4.1 (Построение ортонормированного базиса для пространства P2 ). Для начала заметим, что любая функция, определенная на конечном интервале [a, b] может преобразована с помощью масштабирования и сдвига в функцию, определенную на интервале [−1, 1], причем это преобразование взаимнооднозначно. Аналогично обстоит дело с функциями. определенными на бесконечном и полубесконечном интервалах. Поэтому определяя скалярное произведение (1.26) на векторном пространстве функций, обычно рассматривают 3 интервала: [−1, 1] (иногда [−π, π]), [0, ∞) и (−∞, ∞). Какой конкретно интервал выбирается, зависит от решаемых задач. Мы рассмотрим вещественное пространство полиномов P2 с каноническим базисом B(P2 ) = (1, x, x2 ). Для определения скалярного произведения мы будем рассматривать полиномы 41 Алгебра – II Д.В. Громов как рациональные функции. Тогда в качестве скалярного произведения можно использовать выражение (1.26), которое мы немного преобразуем: в качестве интервала выберем [−1, 1] и опустим операцию комплексного сопряжения. Теперь наше скалярное произведение выглядит так: Z 1 hp(t), g(t)i = p(t)g(t)dt. −1 Легко проверить, что канонический базис B(P2 ) не является ни нормированным, ни ортогональным. Так, например, Z 1 Z 1 2 x2 dx = 6= 0. 12 dx = 2 6= 1 и h1, x2 i = k1k2 = 3 −1 −1 Используем процедуру ортогонализации Грама-Шмидта для построения ортонормированного базиса пространства P2 . Обозначим этот базис как B⊥ (P2 ) = (p1 , p2 , p3 ). В качестве первого элемента возьмем первый базисный вектор B(P2 ), предварительно пронормировав его: 1 1 =√ . p1 = k1k 2 Второй элемент определяется по формуле p2 = x − hx, p1 ip1 . kx − hx, p1 ip1 k Вычислим скалярное произведение hx, p1 i: 1 hx, p1 i = √ 2 Z 1 xdx = 0. −1 Таким образом, получаем x = p2 = kxk r 3 x. 2 Используя описанную схему, определите третий элемент базиса B⊥ (P2 ) самостоятельно. Проекция на подпространство. Теперь мы вернемся к вопросу вычисления проекции вектора x ∈ F n на подпространство V ⊂ F n . Пусть в пространстве V задан ортонормированный базис B⊥ (V ) = (e1 , . . . , ek ). Тогда мы можем представить вектор x в виде суммы двух компонент, projV x и orthV x, причем первая из них может быть записана как линейная комбинация базисных векторов (e1 , . . . , ek ): projV x = α1 e1 + · · · + αk ek . Компонента orthV x = x − projV x должна удовлетворять условию ортогональности, т. е. должно выполняться horthV , vi = 0 для всех v ∈ V . Легко проверить, что это требование эквивалентно выполнению условий horthV x, ei i = 0 для всех ei ∈ B⊥ (V ). Перепишем эти условия, раскрыв в них выражение для orthV x: hx − α1 e1 − · · · − αk ek , ei i = 0, 42 ei ∈ B⊥ (V ). Алгебра – II Д.В. Громов Учитывая свойство ортонормированности базисных векторов (e1 , . . . , ek ) мы легко получаем выражения для коэффициентов αi : αi = hx, ei i. Итак, мы имеем следующие формулы для определения проекции вектора x на подпространство V и соответствующей ортогональной компоненты: projV x = hx, e1 ie1 + · · · + hx, ek iek и orthV x = x − projV x. (1.36) Легко проверить, что projV αx = α projV x и projV (x0 + x00 ) = projV x0 + projV x00 , а следовательно, projV – это линейный оператор из F n в V . Этот оператор обладает интересным свойством идемпотентности: projV (projV x) = projV x, т. е. будучи применен два раза он дает тот же результат, как и после однократного применения. Докажите! 1.4.6 Операторы в пространствах со скалярным произведением Ниже мы будем рассматривать действие линейных операторов на векторных пространствах, для которых определена операция скалярного произведения. Начнем с того, что дадим определение сопряженного оператора. Определение 1.4.10. Пусть T : F n → F m – линейный оператор между пространствами с заданным на них скалярным произведением h·, ·i. Отображение T ∗ : F m → F n называется сопряженным к T , если оно удовлетворяет hT x, yi = hx, T ∗ yi. (1.37) Во многих учебниках T ∗ полагается линейным оператором по определению. Однако мы для тренировки докажем этот результат. Лемма 1.4.11. Если T ∈ L(F n , F m ) то T ∗ ∈ L(F m , F n ). Доказательство. Пусть y, y0 , y00 ∈ F m , x ∈ F n и α ∈ F . Проверим свойства аддитивности и однородности: 1. Аддитивность: hx, T ∗ (y0 + y00 )i = hT x, y0 + y00 i = hT x, y0 i + hT x, y00 i = hx, T ∗ y0 i + hx, T ∗ y00 i = = hx, T ∗ y0 + T ∗ y00 i. Отсюда следует, что T ∗ (y0 + y00 ) = T ∗ y0 + T ∗ y00 . 2. Однородность: Обоснуйте, почему это так? hx, T ∗ (αy)i = hT x, αyi = ᾱhT x, yi = ᾱhx, T ∗ yi = = hx, αT ∗ yi. Получаем T ∗ (αy) = αT ∗ y, что и требовалось доказать. 43 Алгебра – II Д.В. Громов Лемма 1.4.12. Сопряженный оператор удовлетворяет следующим свойствам: 1. (T + V )∗ = T ∗ + V ∗ , 2. (αT )∗ = ᾱT ∗ , ∗ 3. (T ∗ ) = T, 4. Id∗ = Id, 5. (T V )∗ = V ∗ T ∗ , где T и V – линейные операторы согласованных размерностей, а α ∈ F . Доказательство. Докажем свойства 3. – 5. Остальные доказательства – самостоятельно. При работе с сопряженными операторами и композициями операторов необходимо обращать внимание на то, из какого в какое пространство действует оператор. 3. Пусть T ∈ L(F n , F m ). для x ∈ F n и y ∈ F m имеем hy, (T ∗ )∗ xi = hT ∗ y, xi = hx, T ∗ yi = hT x, yi = hy, T xi. 4. Для x0 , x00 ∈ F n выполняется hx0 , Id∗ x00 i = hId x0 , x00 i = hx0 , x00 i. Обратите внимание, что единичный оператор всегда действует из пространства V в то же самое пространство. В данном случае, Id : F n → F n . 5. Пусть T ∈ L(F n , F m ) и V ∈ L(F m , F k ). Для x ∈ F n , y ∈ F k hx, (V T )∗ yi = hV T x, yi = hT x, V ∗ yi = hx, T ∗ V ∗ yi. Встает естественный вопрос, как же будет выглядеть сопряженный оператор в координатах? Оказывается, что если координатное представление оператора A = M(T ) получено относительно ортонормированных базисов, то координатная запись сопряженного оператора M(T ∗ ) соответствует комплексно-сопряженному транспонированию матрицы A. Сначала дадим определение операции комплексно-сопряженного транспонирования, а затем докажем этот результат. Определение 1.4.11. Для матрицы A ∈ F n×m , элементы комплексно-сопряженной транспонированной матрицы A∗ определяются как [A∗ ]ij = āji , то есть комплексно-сопряженное транспонирование соответствует перестановке строк и столбцов матрицы и поэлементному комплексному сопряжению. 44 Алгебра – II Д.В. Громов В русскоязычной литературе комплексно-сопряженная транспонированная матрица обычно называется эрмитово21 -сопряженной. Заметим, что для F = R эрмитово-сопряженная матрица совпадает с транспонированной матрицей. Если из контекста будет понятно, что мы работаем с вещественными векторными пространствами, то вместо A∗ мы будем писать A> для обозначения координатной матрицы сопряженного оператора. Теорема 1.4.13. Пусть A – координатное представление оператора T ∈ L(F n , F m ) относительно ортонормированных базисов B(F n ) = (e1 , . . . , en ) и B(F m ) = (f1 , . . . , fm ). Тогда координатное представление сопряженного оператора T ∗ ∈ L(F m , F n ) относительно ортонормированных базисов B(F m ) и B(F n ) представляет собой эрмитово-сопряженную матрицу A∗ . Доказательство. Вспомним определение координатного представления оператора: k-й столбец матрицы A представляет собой координаты разложения вектора T ek по базису (f1 , . . . , fm ). Поскольку векторы (f1 , . . . , fm ) составляют ортонормированную систему, мы можем использовать формулу (1.33): T ek = hT ek , f1 if1 + · · · + hT ek , fj ifj + · · · + hT ek , fm ifm . Теперь рассмотрим координатное представление сопряженного оператора T ∗ . Аналогично запишем разложение вектора T ∗ fj по базису (e1 , . . . , en ) T ∗ fj = hT ∗ fj , e1 ie1 + · · · + hT ∗ fj , ek iek + · · · + hT ∗ fj , en ien = = he1 , T ∗ fj ie1 + · · · + hek , T ∗ fj iek + · · · + hen , T ∗ fj ien = = hT e1 , fj ie1 + · · · + hT ek , fj iek + · · · + hT en , fj ien Итак, kj-й элемент координатного представления T ∗ равен hT ek , fj i, то есть комплексносопряженному к jk-тому элементу координатного представления T . Обратите внимание, что вопреки расхожему мнению, полученный результат имеет место только для ортонормированных базисов! В общем случае координатное представление сопряженного оператора будет отличаться от A∗ . Обычно проблем с этим не возникает, так как мы большей частью работаем с ортонормированными базисами и возникает ощущение (которое потом переходит в уверенность), что эрмитово-сопряженная матрица всегда соответствует сопряженному оператору. Однако при работе с реальными задачами, для которых преобразование базиса является нормой, такое заблуждение может привести к ошибкам. В дальнейшем, следуя принятому ранее соглашению, мы не будем делать разницы между сопряженным оператором и эрмитово-сопряженной координатной матрицей этого оператора и будем писать A∗ в том и другом случае, если это не будет приводить к недоразумениям. Более того, мы будем также писать x∗ для обозначения комплексно-сопряженного и транспонированного вектора. Используя введенные обозначения мы будем иногда записывать скалярное произведение двух векторов x и y как hx, yi = x∗ y 21 В честь Шарля Эрмита (Charles Hermite, 1822 – 1901) – выдающегося французского математика 19 века. Среди его результатов можно упомянуть доказательство трансцедентности числа e. Эрмит внес большой вклад в теорию ортогональных многочленов, в том числе названных в его честь многочленов Эрмита. 45 Алгебра – II Д.В. Громов в комплексном случае и hx, yi = x> y в вещественном случае. Конечно, для вещественных пространств все выражения выглядят гораздо проще, так как нам не надо думать о том, какие элементы должны браться комплексно-сопряженными, а какие – нет. К счастью, в большинстве практических задач мы не будем выходить за рамки вещественных пространств. В первой части нашего курса мы обратили внимание на специальный класс симметрических матриц. Эти матрицы тесно связаны с линейными операторами специального вида. Определение 1.4.12. Оператор A называется самосопряженным если A∗ = A (или, в случае F = R, A> = A). Иначе говоря, оператор является самосопряженным если для всех x и y из соответствующих пространств выполняется hAx, yi = hx, Ayi. Для F = C, самосопряженный оператор называется эрмитовым, а для F = R – симметрическим. Самосопряженные операторы и соответствующие матрицы обладают многими полезными свойствами, о которых мы поговорим немного позже. 1.4.7 Метод наименьших квадратов Теперь мы имеем все необходимые ингредиенты для того, чтобы строго сформулировать метод наименьших квадратов (МНК) – один из самых популярных методов прикладной математики. Рассмотрим стандартную формулировку МНК. Пусть дана система линейных алгебраических уравнений Ax = b, где x ∈ F n , b ∈ F m , а матрица A имеет размерности [m × n], причем m > n, то есть система является переопределенной (число уравнений существенно больше числа неизвестных). Обычно такие системы являются несовместными. Почему? Рассмотрим задачу с геометрической точки зрения: необходимо представить вектор b из пространства большой размерности в виде линейной комбинации меньшего числа векторов из того же пространства (векторы эти есть не что иное, как столбцы матрицы A). Очевидно, что в общем случае вектор b не должен принадлежать линейной оболочке, натянутой на столбцы матрицы A. Поэтому мы будем искать приближенное решение xo такое, что результирующий вектор b = Axo максимально приближен к исходному вектору b. Степень близости двух векторов b мы будем измерять как норму их разницы: b − bk = kAxo − bk → min . kb (1.38) b = Axo , а подпространВспомним теорему 1.4.6. Применительно к нашему случаю, x = b, x ство V – это линейная оболочка столбцов матрицы A. Итак, согласно теореме 1.4.6 решение задачи (1.38) должно удовлетворять условию hv, Axo − bi = 0, (1.39) где v ∈ span(a×,1 , . . . , a×,n ). Последнее эквивалентно тому, что v = Ay для некоторого y ∈ F n . Таким образом, мы можем записать условие оптимальности (1.39) hv, Axo − bi = hAy, Axo − bi = hy, A∗ (Axo − b)i = 0. 46 (1.40) Алгебра – II Д.В. Громов В этом выражении A∗ – это матрица сопряженного оператора22 . Поскольку в (1.40) вектор y может быть любым, условие оптимальности может быть записано как A∗ Axo = A∗ b. (1.41) Уравнение (1.41) называется нормальным уравением. Это название связано с тем, что вектор Axo − b нормален, то есть ортогонален всем столбцам матрицы A. В случае вещественных векторных пространств нормальное уравнение (1.41) приобретает вид A> Axo = A> b. (1.42) Рассмотрим уравнение (1.41) более подробно. Заметим, что новая система уравнений содержит столько же уравнений, сколько неизвестных (а именно, n). В этом случае решение может быть определено однозначно если матрица A∗ A невырожденна. Матрица эта обладает рядом интересных свойств. Во-первых, она эрмитово-сопряженная или симметрическая в вещественном случае. Вспоминая свойства (3.) и (5.) леммы 1.4.12 мы можем записать: (A∗ A)∗ = A∗ (A∗ )∗ = A∗ A. Во-вторых, эта матрица невырожденна если ее ранг равен числу столбцов n. Лемма 1.4.14. Пусть матрица A размерности [m×n] имеет ранг n. Тогда матрица A∗ A также имеет ранг n. Доказательство. Пусть вектор y ∈ F ∗ принадлежит ядру матрицы A∗ A, то есть выполняется A∗ Ay = 0. Домножим слева на y∗ : 0 = y∗ 0 = y∗ A∗ Ay = (Ay)∗ Ay = kAyk, то есть Ay = 0. Однако мы помним, что ранг A равен n, а следовательно единственным решением однородной системы Ay = 0 является тривиальное решение y = 0. Таким образом, N (A∗ A) = N (A) = {0}, а ранг A∗ A равен n. Если матрица A имеет полный ранг по столбцам, то матрица A∗ A невырожденна и имеет обратную. Тогда мы можем записать решение (1.41) в виде −1 xo = (A∗ A) A∗ b. (1.43) b Вспомним выражение для аппроксимации b: b = A (A∗ A)−1 A∗ b. b −1 Матрица A (A∗ A) A∗ является координатным представлением оператора проекции на подпространство V = span(a×,1 , . . . , a×,n ). Можно легко убедиться, что этот оператор является идемпотентным: −1 −1 −1 A (A∗ A) A∗ A (A∗ A) A∗ = A (A∗ A) A∗ . 22 Мы не формулировали задачу в терминах линейных операторов и рассматривали только матрицы, но при необходимости (и жертвуя наглядностью) все результаты можно переформулировать в операторном виде. 47 Алгебра – II Д.В. Громов В связи с применением метода наименьших квадратов особый интерес представляют матрицы A специального вида. Если в наша задача такова, что матрицу A можно выбирать произвольно (по крайней мере до какой-то степени), то имеет смысл выбрать ее так, чтобы сократить объем вычислений. Например, предположим, что столбцы матрицы A попарно ортогональны. Тогда мы имеем A∗ A = E. Определение 1.4.13. Матрица A ∈ Cm×n называется унитарной если A∗ A = E. Матрица A ∈ Rm×n называется ортогональной если A> A = E. Задачи и вопросы 1. Докажите правило параллелограмма для евклидовой нормы: kx + yk2 + kx − yk2 = 2(kxk2 + kyk2 ). Нарисуйте соответствующую векторную диаграмму. 2∗ . Покажите, что если в пространстве F n задана норма, удовлетворяющая неравенству параллелограмма, то она может быть использована для определения скалярного произведения двух векторов из F n . Выразите скалярное произведение через норму в случае вещественного и комплексного векторных пространств, F = R и F = C. 3. Докажите теорему Пифагора для F n . А именно, покажите, что для двух ортогональных векторов x, y ∈ F n верно kx + yk2 = kxk2 + kyk2 . 4. Используя теорему Коши-Буняковского-Шварца, докажите, что для любого конечного набора вещественных чисел xi ∈ R, i = 1, . . . , n, квадрат их арифметического среднего не превышает арифметического среднего квадратов, т. е. !2 n n 1X 2 1X xi ≤ x . n i=1 n i=1 i 5. Дайте оценку снизу на произведение суммы n вещественных чисел xi ∈ R, xi > 0, ∀ i = 1, . . . , n, и суммы обратных к ним величин: ! ! n n X X 1 ?≤ xi x i=1 i=1 i 6. Докажите, что если x и y из Rn имеют одинаковые нормы, то векторы x + y и x − y ортогональны. Используя полученный результат покажите, что диагонали ромба в R2 перпендикулярны. 7. Даны x, y ∈ F n . Докажите, что hx, yi = 0 тогда и только тогда, когда kxk ≤ kx + αyk для всех α ∈ F . 8. Пусть hx, yi – скалярное произведение на F n , а S ∈ L(F n , F n ) – инъективное отображение. Докажите, что hx, yiS = hSx, Syi задает скалярное произведение на F n . 9. Пусть f (t) и g(t) – две непрерывно дифференцируемые векторнозначные функции из R в Rn . Найдите d выражение для производной скалярного произведения dt hf (t), g(x)i. Подсказка: 1 [hf (t + h), g(t + h)i − hf (t), g(t)i] = h 1 1 = [hf (t + h), g(t + h)i − hf (t), g(t + h)i] + [hf (t), g(t + h)i − hf (t), g(t)i] . h h 10. Пусть h·, ·ia и h·, ·ib – два скалярных произведения на F n , а k · ka и k · kb – две нормы, порожденные соответствующими скалярными произведениями. Докажите, что существует положительное вещественное число c такое, что для любого x ∈ F n выполняется kxka ≤ ckxkb . 11. Пусть {x1 , . . . , xm } – линейно независимый набор векторов в F n , m ≤ n. Покажите, что существует вектор y ∈ F n такой, что hy, xi i > 0 для всех i = 1, . . . , m. 12. Найти полином p(x) ∈ P3R , удовлетворяющий условиям p(0) = 0 p0 (0) = 1, максимально приближающий полином g(x) = 3x + 2 в смысле нормы, заданной скалярным произведением Z 1 hf (x), g(x)i = f (x)g(x)dx. (1.44) 48 Алгебра – II Д.В. Громов 13. Определим линейный оператор T ∈ L(F n , F n ) как      x1   x2    x1       T (x) = T  . =  .. .  ..  . xn xn−1 Запишите выражение для T ∗ (x). 14. Пусть скалярное произведение в P2R задано формулой (1.44). Определим линейный оператор T ∈ L(P2R , P2R ) как T (a0 x2 + a1 x + a2 ) = a1 x. (a) Покажите, что этот оператор не самосопряженный.   0 0 0 2  (b) Матрица оператора T относительно базиса (1, x, x ) имеет вид 0 1 0. Очевидно, что это 0 0 0 симметрическая матрица, несмотря на то, что T не самосопряженный. Объясните, есть ли тут противоречие? Проекты Проект 1 (Данил Чикилев): Дана функция y = sin(x). Необходимо найти наилучшее в смысле минимизации квадрата нормы разности приближение этой функции полиномами порядка 3,4 и 5. Проанализировать полученные результаты, сравнить результат с разложением в ряд Тейлора. Проект 2 (Егор Сташков и Елена Щетинина): Формулировка и интерпретация непрерывного и дискретного преобразования Фурье с использованием методов линейной алгебры. Проект 3 (один человек): Изучить, как алгебраические методы используются для решения задач из теории графов. См. описание в Project_3.pdf в Dropbox. Проект 4 (один человек): Исследование преобразования Хаара. См. описание в Project_4.pdf в Dropbox. Проект 5 (Даниил Смирнов): Использование методов линейной алгебры для прогнозирования результатов спортивных соревнований. См. описание в Project_5.pdf в Dropbox. Темы, которые не вошли в этот раздел для экономии времени: 1. Линейные функционалы (отображения из векторного пространства в R). 2. Двойственные векторные пространства. 3. Ортогональное дополнение. 4. Оставшиеся 2 фундаментальных подпространства: coN (T ) = N (T > ) и coR(T ) = R(T > ) 49 Алгебра – II 1.5 Д.В. Громов Собственные числа и векторы До сих пор все задачи, которые мы решали так или иначе были связаны с решением систем алгебраических уравнений Ax = b. В этом разделе мы займемся исследованием структуры линейных операторов, действующих из пространства V в то же самое пространство V , то есть операторов из L(V, V ). Для определенности мы опять положим V = F n , но будем помнить, что все изложенные методы могут быть применены к любым векторным пространствам, включая бесконечномерные пространства. Вспомним, что в координатном представлении каждый оператор из L(F n , F n ) записывается в виде квадратной матрицы размерности [n×n]: A ∈ F n×n . Такие матрицы будут составлять предмет нашего изучения в этом разделе. 1.5.1 Инвариантные подпространства Начнем с того, что в очередной раз рассмотрим выражение Ax = y. Оператор A действует на вектор x ∈ F n , преобразуя его в другой вектор y ∈ F n . Пусть x ∈ R2 . Вспомним, какие стандартные преобразования нам известны: масштабирование вектора, его поворот на угол φ, преобразования сдвигов и отражений относительно осей. Запишите примеры матриц, соответствующих всем перечисленным преобразованиям . Эти преобразования могут быть применены не только к векторам, но и к подпространствам. Пусть S ⊂ F n – некоторое линейное подпространство. Определим действие оператора A на подпространство S как AS = {y ∈ F n |y = Ax, x ∈ S}. (1.45) Проверьте, что для любого линейного подпространства S, AS также является линейным подпространством. . Определение 1.5.1. Подпространство S ∈ F n называется инвариантным относительно A или просто A-инвариантным, если выполняется AS ⊆ S. (1.46) Иначе говоря, подпространство S называется A-инвариантным, если Ax ∈ S для любого x ∈ S. Для начала мы познакомимся с некоторыми примерами инвариантных пространств. Лемма 1.5.1. Пусть T ∈ L(F n , F n ) – линейный оператор, а A – его координатная матрица. Следующие подпространства инвариантны относительно A: 1. {0}, 2. F n , 3. R(T ), 4. N (T ). Доказательство. Самостоятельно. Сейчас мы докажем одну теорему, которая будет играть важную роль в задаче анализа управляемости / наблюдаемости линейных систем, с которой вы столкнетесь в курсе “Линейные системы управления”. 50 Алгебра – II Д.В. Громов Теорема 1.5.2. Пусть T ∈ L(F n , F n ) – линейный оператор с координатной матрицей A, а V ⊂ F n – это A-инвариантное подпространство F n размерности k < n. Тогда существует такое преобразование базиса x = Cx0 , что в новом базисе координатное представление à оператора T имеет вид A11 A12 à = C−1 AC = , (1.47) 0 A22 где A11 ∈ F k×k и A22 ∈ F n−k×n−k . Доказательство. Зададим матрицу преобразования следующим образом:  C = v1  ... vk ṽk+1 ... ṽn  , где v1 , . . . , vk – базисные векторы подпространства V , а векторы ṽk+1 , . . . , ṽn выбираются произвольно таким образом, что вся система векторов образует базис F n . Перепишем (1.47), домножая левую и правую части выражения на C:      A11 A12  A v1 . . . vk ṽk+1 . . . ṽn  = v1 . . . vk ṽk+1 . . . ṽn   A21 A22 В выражении слева первые k столбцов Avi , i = 1, . . . , k принадлежат V по свойству Aинвариантности подпространства V . Следовательно, выполняется Avi ∈ span(v1 , . . . , vk ), поэтому A21 = 0. В теореме 1.5.2 мы в первый раз встречаемся со специальным случаем эквивалентности матриц, à ∼ C−1 AC. Этот специальный тип отношения эквивалентности называется отношением подобия. Оно появляется, когда мы рассматриваем преобразование операторов, действующих из одного пространства в то же самое подпространство, под действием преобразования базиса, одинакового для обеих подпространств. Отношению подобия будет посвящен отдельный подраздел 1.5.4. 1.5.2 Собственные числа и векторы Теперь мы вернемся к центральной теме этого раздела. Нас будет интересовать вопрос: имеет ли данный линейный оператор инвариантные подпространства, отличные от перечисленных в лемме 1.5.1? Начнем с того, что рассмотрим инвариантные подпространства размерности 1. Как мы знаем, каждое пространство размерности 1 представляет собой некоторый вектор x ∈ F n и кратные ему: λx, λ ∈ F . Будем обозначать соответствующее подпространство Sx = span(x). Таким образом, подпространство Sx будет A-инвариантным, если для некоторого скаляра λ ∈ F выполняется Ax = λx. Определение 1.5.2. Пусть T ∈ L(F n , F n ) – линейный оператор, а A – его координатная матрица. Число λ ∈ F называется собственным числом, а вектор x ∈ F n \ {0} – собствен- 51 Алгебра – II Д.В. Громов ным вектором23 оператора T , если выполняется Ax = λx. (1.48) Замечание 1.5.1. Обратите внимание, что собственное число оператора может быть равно нулю, в то время как собственный вектор не может быть нулевым. В противном случае A0 = λ0 будет выполняться для всех λ ∈ F . Также заметим, что собственный вектор определен с точностью до ненулевого сомножителя: из Ax = λx следует A(ax) = λ(ax), a ∈ F \ {0}. В дальнейшем мы будем часто говорить о собственных числах и векторах матрицы A. Это так называемый abuse of notation – формулировка, которая не вполне корректна математически, но позволяет существенно упростить изложение. В данном случае мы будем идентифицировать линейный оператор с его матричным представлением относительно некоторого базиса, а элементы векторных пространств с коэффициентами их разложений по этому базису. Теорема 1.5.3. Собственные числа матрицы A удовлетворяют уравнению det(λE − A) = 0. (1.49) Пусть µ – собственное число матрицы A. тогда собственные векторы матрицы A, соответствующие собственному значению µ, принадлежат подпространству N (µE − A). Доказательство. Выражение (1.48) можно переписать как 0 = λx − Ax = (λE − A)x. Это эквивалентно тому, что матрица λE − A имеет нетривиальное ядро, т. е. эта матрица вырождена. Мы помним, что одним из условий вырожденности матрицы является равенство нулю ее определителя. Так мы получаем (1.49). Обратно, если µ – собственное число матрицы A, то любой вектор x ∈ N (µE − A) будет удовлетворять (1.48). Рассмотрим определитель det(λE − A). Используя сигнатурную формулу Лейбница мы можем записать det(λE − A) как полином n-й степени от λ, причем коэффициент при λn будет равен единице. Проверьте! Определение 1.5.3. Полином n-й степени от λ, pA (λ) = det(λE − A) ∈ F [λ] называется характеристическим полиномом матрицы A. Вспоминая результаты из теории полиномов мы приходим к следующему следствию. Следствие 1.5.4. Матрица A ∈ F n×n имеет ровно n собственных значений λ1 , . . . , λn ∈ C с учетом кратностей. Множество всех собственных значений матрицы A называется спектром матрицы A и обозначается Λ(A) = {λ1 , . . . , λn }24 . Остановимся еще ненадолго на собственных числах. В 23 Соответственно, eigenvalue и eigenvector. Первая часть этих терминов происходит от немецкого прилагательного eigen, которое обозначает “свой”, “собственный”. 24 При записи собственных чисел порядок не имеет значения. Однако если мы записываем набор собственных чисел и собственных векторов некоторой матрицы, то порядок их следования должен быть одинаковым. 52 Алгебра – II Д.В. Громов общем случае собственные числа принадлежат комплексному пространству. Теоретически мы можем говорить о собственных числах над полем вещественных чисел R, подобно тому, как мы рассматривали вещественные корни полиномов с вещественными коэффициентами, но применительно к матрицам это не имеет большого смысла. Поэтому, рассматривая уравнение det(λE − A), мы всегда полагаем λ ∈ C! Теперь сформулируем результат, который получит свое развитие в подразделе 1.5.3. Лемма 1.5.5. Матрица A имеет по меньшей мере столько собственных векторов, сколько различных собственных чисел. Доказательство. Вспомним, что согласно теореме 1.5.3, µ является собственным числом A если матрица (µE − A) – вырождена, т. е. имеет нетривиальное ядро. Любой ненулевой b ∈ N (µE − A) будет собственным вектором, т. е. будет удовлетворять элемент этого ядра x Ab x = µb x. Теперь мы вернемся к собственным числам и для начала заметим, что в некоторых случаях собственные числа матрицы могут быть определены без использования характеристического полинома. Лемма 1.5.6. Собственные числа треугольной матрицы совпадают с элементами ее главной диагонали: λi = aii , i = 1, . . . , n. Доказательство. Предположим, что A – верхняя треугольная матрица. Тогда матрица λE − A также будет верхней треугольной матрицей следующего вида:   λ − a11 . . . ∗   .. .. .  . . λ − ann Как мы помним, определитель треугольной матрицы равен произведению ее диагональных элементов, т. е. характеристический полином матрицы A имеет вид pA (λ) = (λ − a11 ) · · · (λ − ann ), откуда следует требуемый результат. Обратите внимание: так же как и в случае полиномов с вещественными коэффициентами, собственные числа вещественной матрицы в общем случае являются комплексными величинами. И точно так же, комплексные собственные числа вещественных матриц “ходят только парами”. Лемма 1.5.7. Если λ и x – собственное число и соответствующий собственный вектор матрицы A ∈ Rn×n , то λ̄ и x̄ также будут собственным числом и собственным вектором A. Доказательство. Мы имеем λx = Ax. Используя операцию комплексного сопряжения получаем λ̄x̄ = λx = Ax = Āx̄ = Ax̄, 53 Алгебра – II Д.В. Громов то есть Ax̄ = λ̄x̄. Поскольку собственные числа матрицы находятся как корни характеристического полинома p(λ), некоторые собственные числа могут соответствовать кратным корням p(λ). На этом месте внимательный читатель может заметить странность: ведь мы говорили, что каждая невырожденная вещественная квадратная матрица может быть преобразована к верхнему треугольному виду. Однако при этом мы нигде не говорили, что элементы на главной диагонали могут быть комплексными! Противоречие? Оказывается, нет. Просто элементарные преобразования, которые мы использовали при LUP - преобразовании, не сохраняют собственные числа. Для примера посчитайте собственные числа матриц 1 0 −1 A1 = и A2 = . 0 −1 1 Наконец мы коротко остановимся еще на одном типе собственных чисел/векторов. Мы помним, что матрицу можно умножать не только на столбец справа, но и на строку слева. Поэтому аналогично обычным (правым) собственным числам и векторам мы можем ввести левые собственные числа и векторы. Определение 1.5.4. Левым собственным числом и вектором матрицы A ∈ F n×n называются скаляр µ ∈ F и вектор y ∈ F n , удовлетворяющие уравнению y> A = µy> (1.50) или, иначе, A> y = µy, т. е. левые собственные числа и векторы матрицы – это то же самое, что обычные (т. е. правые) собственные числа и векторы транспонированной матрицы. Левые и правые собственные числа и векторы – это уже немного чересчур. Однако не все так плохо. Лемма 1.5.8. Множества левых и правых собственных чисел совпадают. Доказательство. Мы помним, что определитель матрицы равен определителю транспонированной матрицы: det(λE − A> ) = det (λE − A> )> = det(λE − A). Следовательно, характеристические полиномы, соответствующие матрице A и транспонированной матрице A> , совпадают, равно как и множества корней этих полиномов. К сожалению, к собственным векторам этот результат не применим. Более того, левые и правые собственные векторы, соответствующие одному и тому же собственному значению, могут сильно различаться. Наконец, последнее замечание по левым собственным векторам. Обратите внимание, что выражение A> y = µy записывается одинаковым образом для вещественных и комплексных матриц (т. е. без эрмитового сопряжения). Это связано с тем, что определение левых и правых собственных чисел и векторов не опирается на использование скалярного произведения. Разобрать позже. Привязка к двойственным пространствам? 54 Алгебра – II 1.5.3 Д.В. Громов Кратные собственные числа. Алгебраическая и геометрическая кратность Интуитивно понятно, что если собственные числа различны, то и соответствующие им собственные векторы тоже должны быть различны. Иначе мы имели бы Ax = λ1 x и Ax = λ2 x для двух различных собственных чисел λ1 6= λ2 . Следующая теорема формализует это наблюдение и усиливает результат леммы 1.5.5. Теорема 1.5.9. Пусть Λ = {λ1 , . . . , λk } – множество попарно различных собственных чисел матрицы A, а V = {v1 , . . . , vk } – соответствующие собственные векторы. Тогда набор собственных векторов V линейно независим. Доказательство. Предположим, что набор V линейно зависим и выберем наименьший индекс l < k такой, что векторы v1 , . . . , vl−1 линейно независимы и vl ∈ span(v1 , . . . , vl−1 ). В таком случае существуют коэффициенты α1 , . . . , αl−1 , для которых выполняется vl = α1 v1 + · · · + αl−1 vl−1 . (1.51) Умножим обе части равенства (1.51) на A и воспользуемся (1.48): λl vl = α1 λ1 v1 + · · · + αl−1 λl−1 vl−1 . (1.52) Домножим (1.51) на λl и вычтем (1.52): 0 = α1 (λl − λ1 )v1 + · · · + αl−1 (λl − λl−1 )vl−1 . (1.53) Однако индекс l был выбран так, что векторы v1 , . . . , vl−1 линейно независимы, то есть коэффициенты при vi , i = 1, . . . , l − 1 должны быть все равны нулю. Поскольку по условию все собственные числа попарно различны, мы имеем αi = 0, i = 1, . . . , l − 1, т. е. vl ∈ / span(v1 , . . . , vl−1 ). Приходим к противоречию. Мы помним, однако, что корни характеристического полинома, а следовательно и собственные числа, могут быть кратными. Рассмотрим две матрицы     2 1 2 2 1 1 A1 = 0 1 −2 и A2 = 0 1 1 . 0 0 2 0 0 2 Очевидно, что в этом случае обе матрицы имеют одно собственное число, равное 1 и два собственных числа, равные 2: λ1 = 1, λ2 = λ3 = 2 (вспоминаем лемму 1.5.6). Собственные числа первой и второй матриц совпадают. Что же происходит с собственными векторами? Запишем выражение для собственных векторов матрицы A1 , соответствующих кратному собственному числу λ2 = λ3 = 2:          1 0 0 2 1 2 0 −1 −2 2 0 1 0 − 0 1 −2 x = 0 1 2 x = 0 . 0 0 1 0 0 2 Получившаяся матрица имеет ранг 1 (одна линейно-независимая строка). По теореме 1.3.4, размерность ядра N (2E − A) равна 2, т. е. мы можем выбрать два линейно-независимых вектора     1 x2 = 0 и x3 =  2 , −1 55 Алгебра – II Д.В. Громов которые мы “припишем” соответствующим собственным числам. Пока все идет хорошо. Попробуем сделать то же самое со второй матрицей. Уравнение для определения собственных векторов имеет вид          1 0 0 2 1 1 0 −1 −1 2 0 1 0 − 0 1 1 x = 0 1 −1 x = 0 . 0 0 1 0 0 2 Однако тут мы сталкиваемся с проблемой. Ранг этой матрицы равен 2, поэтому ядро имеет > размерность 1. Следовательно, единственный собственный вектор – это x2 = 1 0 0 . Мы видим, что ядро матрицы (2 E − A1 ) имеет размерность 2, в то время, как размерность ядра (2 E − A2 ) равна одному. Таким образом, число собственных векторов, соответствующих кратному собственному числу может отличаться от кратности этого собственного числа. Определение 1.5.5. Если характеристический полином матрицы A имеет корень µ кратности k, то соответствующее собственное число называется кратным, причем мы говорим, что его алгебраическая кратность m(µ) равна k. геометрическая кратность g(µ) равна размерности N (µ E − A). Итак, алгебраическая кратность – это обычная кратность корня характеристического многочлена, а геометрическая кратность – это число линейно-независимых собственных векторов, соответствующих собственному числу. Из леммы 1.5.5 следует, что геометрическая кратность не может быть меньше единицы, т. е. любая матрица имеет по крайней мере одну пару (собственное число, собственный вектор)25 . Можно предположить, что геометрическая кратность всегда меньше или равна алгебраической. Действительно, это так. Однако доказательство этого факта мы оставим до того времени, когда познакомимся с преобразованием подобия. Перед тем, как перейти к следующей теме, сделаем еще одно замечание. Раньше мы говорили, что собственный вектор, соответствующий некоторому собственному числу, определен с точностью до умножения на ненулевой скаляр. Теперь мы можем сформулировать этот факт в более общем виде. Утверждение 1.5.10. Пусть µ есть некоторое собственное число матрицы A. Любой элемент ядра N (µE − A) будет являться собственным вектором, соответствующим µ. В частности, если геометрическая кратность g(µ) равна k, то любая линейная комбинация k базисных векторов подпространства N (µE − A) будет являться собственным вектором, соответствующим µ. 1.5.4 Подобные матрицы Теперь настало время определить и изучить в деталях отношение подобия. 25 В английском языке такая пара называется eigenpair. К сожалению, в русском языке аналог этому термину отсутствует. 56 Алгебра – II Д.В. Громов Определение 1.5.6. Две матрицы A и B называются подобными если существует такая невырожденная матрица T, что выполняется B = T−1 AT. (1.54) Матрица T называется матрицей преобразования подобия. Заметим, что выражение (1.54) может быть эквиалентно записано как B = QAQ−1 если мы положим Q = T−1 . Очевидно, что отношение подобия является частным случаем отношения эквивалентности, т. е. оно удовлетворяет свойствам рефлексивности, симметричности и транзитивности. Проверьте! Мы уже коротко обсудили операторную интерпретацию преобразования подобия в конце подраздела 1.5.1, поэтому сейчас не будем на этом останавливаться. Начнем с рассмотрения одного из основных свойств подобных матриц. Теорема 1.5.11. Пусть матрицы A и B подобны. Тогда их характеристические полиномы совпадают. Доказательство. Если матрицы A и B подобны, то по определению существует такая невырожденная матрица T, что B = T−1 AT. Запишем характеристический полином pB (λ): pB (λ) = det(λE − B) = det(λE − T−1 AT) = det(λT−1 T − T−1 AT) = det T−1 [λE − A]T . Вспомним, что для двух квадратных матриц Q и P выполняется det(QP) = det(Q) det(P) и −1 det(Q−1 ) = [det(Q)] . Теперь мы можем закончить вычисления и получить pB (λ) = det T−1 [λE − A]T = det(T−1 ) det(λE − A) det(T) = det(λE − A) = pA (λ). Теорема 1.5.11 имеет ряд полезных следствий, с которыми мы будем знакомиться по мере продвижения в глубь теории. Сейчас мы сформулируем первое следствие. Следствие 1.5.12. Собственные числа двух подобных матриц совпадают. Немного забегая вперед, можно сказать, что подобные матрицы очень похожи (что неудивительно, если мы вспомним о том, чем, собственно, являются подобные матрицы). Наиболее распространенным методом исследования квадратных матриц является нахождение такого преобразования подобия, которое приводит интересующую нас матрицу к некоторому удобному виду. То есть, по сути, мы ищем базис, в котором интересующий нас оператор имеет наиболее подходящую для изучения форму. Для того, чтобы получить следующий результат нам потребуется получше разобраться с характеристическим полиномом. Мы уже увидели, что характеристический полином матрицы над полем F размерности [n × n] – это полином степени n с единичным старшим коэффициентом. Оказывается, что два коэффициента этого полинома несут важную информацию о свойствах матрицы. 57 Алгебра – II Д.В. Громов Лемма 1.5.13. Рассмотрим матрицу A ∈ F n×n с характеристическим полиномом pA (λ) = λn + α1 λn−1 + · · · + αn−1 λ + αn ∈ F [λ]. Коэффициенты полинома p(λ) могут быть охарактеризованы следующим образом: 1. Младший коэффициент, an , равен определителю матрицы A, взятому со знаком минус, если n – нечетное число: αn = (−1)n det(A). (1.55) 2. Второй по порядку коэффициент, a1 , равен следу26 матрицы A, взятому со знаком минус: n X α1 = − trace(A) = − aii . (1.56) i=1 Доказательство. Докажем по пунктам. 1. В уравнении pA (λ) = det(λE − A) положим λ = 0. Получаем pA (0) = αn = det(−A) = (−1)n det(A). 2. Для доказательства второго утверждения нам потребуется вспомнить сигнатурную формулу Лейбница. Если сгруппировать слагаемые в этой формуле по количеству вхождений туда λ, то получим следующее выражение det(λE − A) = n Y (λ − aii ) − (λ − aii )a12 a21 − · · · − {z I n−2 Y (λ − aii )an−1,n an,n−1 + . . . , i=1 i=3 i=1 | n Y }| {z II } где первое слагаемое (I) соответствует перестановке σ = Id, вторая группа слагаемых (II) – единичным транспозициям Id (поэтому знак минус), а дальнейшие слагаемые – двукратным, трекратным и пр. транспозициям Id. Очевидно, что слагаемые второй группы, а уж тем более дальнейшие слагаемые будут соответствовать полиномам от λ степеней, не превышающих n − 2. Нас же интересует коэффициент a1 при λn−1 , поэтому мы будем рассматривать только первое слагаемое (I). Раскрывая произведение n сомножителей (λ−a11 )(λ−a22 ) · · · (λ−ann ) и собирая члены с λn−1 получаем n X aii . α1 = − i=1 Чтобы лучше понять пользу этого результата, вспомним, что по теореме Виета коэффициенты характеристического полинома могут быть выражены через его корни, т. е. характери26 След – это важная характеристика матрицы, чье значение далеко выходит за пределы характеристических полиномов. След широко используется в матричном анализе, статистике, теории бифуркаций и др. областях. Иногда след матрицы A обозначается как Sp(A) от немецкого слова Spur, т. е. след. 58 Алгебра – II Д.В. Громов стические числа. В частности, мы имеем, α1 = − λ1 − · · · − λn .. . αn = (−1)n λ1 λ2 · · · λn . Сопоставляя эти два факта мы получаем следующий полезный результат. Теорема 1.5.14. След матрицы равен сумме ее собственных чисел, а определитель – произведению собственных чисел. Теперь мы можем записать еще одно свойство подобных матриц, которое следует из теоремы 1.5.14. Следствие 1.5.15. След и определитель двух подобных матриц совпадают. Наконец мы докажем последнюю теорему о размерности фундаментальных подпространств подобных матриц. Теорема 1.5.16. Размерности ядра двух подобных матриц равны. Доказательство. Рассмотрим две подобные матрицы A и B, такие что B = T−1 AT. Пусть (x1 , . . . , xk ) – базис N (B). Тогда для любого 1 ≤ i ≤ k выполняется 0 = Bxi = T−1 ATxi . Домножая это равенство слева на T получим ATxi = 0, т. е. векторы Txi принадлежат N (A). Поскольку система векторов (x1 , . . . , xk ) линейнонезависима, а матрица T невырожденная, система (Tx1 , . . . , Txk ) также будет линейнонезависимой. Таким образом, размерность ядра N (B) не меньше k, т. е. N (A) ≤ N (B). Теперь рассмотрим обратное выражение TBT−1 = A. Следуя той же схеме получим N (B) ≤ N (A). Сопоставляя получившиеся неравенства, приходим к требуемому результату. Используя теорему 1.3.4 о размерностях, мы сразу же можем заключить, что две подобные матрицы имеют один и тот же ранг. 1.5.5 Функции от матриц В этом подразделе мы дадим определение функции от матрицы и сформулируем несколько результатов, которые нам потребуются в дальнейшем. 59 Алгебра – II Д.В. Громов Мы знаем, что любая аналитическая27 функция может быть представлена в виде разложения в ряд Тейлора или, в частном случае, в ряд Маклорена. Запишем разложение в ряд Маклорена некоторой функции f (x): f (x) = f (0)x0 + f 0 (0)x1 + 1 00 1 f (0)x2 + f 000 (0)x3 + . . . 2! 3! = α0 x0 + α1 x1 + α2 x2 + α3 x3 + . . . Аргументом функции f (x) является некоторая переменная. Однако с равным успехом мы можем использовать вместо этой переменной некоторую квадратную матрицу: x 7→ A. Для квадратной матрицы определены операции сложения, возведения в неотрицательную целую степень и умножения на скаляр. Поэтому мы можем вычислить значение матричной функции f (A) как сумму бесконечного ряда f (A) = α0 E + α1 A + α2 A2 + α3 A3 + . . . (1.57) Для того, чтобы значение функции f (A) было определено, необходимо, чтобы этот ряд сходился. Одним из простейших примеров матричных функций является матричный полином. Пусть задан полином p(x) ∈ F [x]: p(x) = xn + α1 xn−1 + · · · + αn−1 x + αn . (1.58) Тогда соответствующий матричный полином имеет вид (обратите внимание, что свободный член этого полинома умножается на единичную матрицу): p(A) = An + α1 An−1 + · · · + αn−1 A + αn E. Обратите внимание, что значение p(A) всегда определено, так как мы имеем дело с конечной суммой. Значение матричного полинома от A – это матрица той же размерности, что и A. Поэтому мы с тем же успехом можем вычислять собственные числа и векторы p(A). Теорема 1.5.17. Пусть p(x) – полином вида (1.58), а A – квадратная матрица с собственным числом µ и соответствующим собственным вектором x. Тогда собственное число матрицы p(A), соответствующее x, будет равно p(µ). Доказательство. Домножим p(A) справа на x и используем Ax = µx: p(A)x = An x + α1 An−1 x + · · · + αn−1 Ax + αn x = µAn−1 x + α1 µAn−2 x + · · · + αn−1 µx + αn x .. . = µn x + α1 µn−1 x + · · · + αn−1 µx + αn x = p(µ)x. 27 Если вы еще не проходили аналитические функции, то можете просто считать, что это бесконечно дифференцируемые вещественные функции. В контексте тех задач, которые мы будем решать, это различие не будет играть роли. 60 Алгебра – II Д.В. Громов В качестве элементарного примера применения этой теоремы рассмотрим задачу вычисления собственных чисел матрицы −100 1 A= . −1 −100 Конечно, мы можем записать характеристический полином и найти его корни, но проще будет заметить, что матрица A может быть представлена как полином p(x) = x − 100 от матрицы 0 1 B= . −1 0 Матрица B имеет собственные числа λB = ±i. Следовательно, для матрицы A имеем λA = p(λB ) = ±i − 100. Теперь мы хотим разобраться с тем, как функции от матриц связаны с отношениями подобия. Для начала сформулируем вспомогательную лемму. Лемма 1.5.18. Если матрицы A и B подобны, т. е. B = T−1 AT, то для любого k ∈ N0 выполняется Bk = T−1 Ak T. Доказательство. Запишем выражение для Bk : Bk = (T−1 AT)k = T−1 AT × T−1 AT × · · · × T−1 AT = T−1 Ak T. {z } | k раз Теорема 1.5.19. Пусть матрицы A и B подобны, т. е. существует такая невырожденная матрица преобразования подобия T, что B = T−1 AT. Пусть f (x) есть некоторая аналитическая функция и значение f (B) определено. Тогда f (A) и f (B) подобны: f (B) = T−1 f (A)T. Доказательство. Подставим выражение для B в разложение (1.57) и применим результат леммы 1.5.18. Матричная экспонента! 1.5.6 Симметрические и эрмитовы матрицы В этом разделе мы посмотрим, как преобразование подобия может быть использовано для изучения симметрических или эрмитово-сопряженных матриц. Такие матрицы очень часто возникают в практических приложениях, поэтому им уделяется особое внимание. Перед тем, как мы приступим к изучению свойств эрмитовых матриц, сформулируем один вспомогательный результат. Лемма 1.5.20. Пусть A ∈ F n×n , а S ⊂ F n – A-инвариантное подпространство F n . Тогда S содержит по крайней мере один собственный вектор A. 61 Алгебра – II Д.В. Громов Доказательство. Запишем [n × r] матрицу Q такую, что ее столбцы образуют базис подпространства S. В силу A-инвариантности выполняется AQ ⊆ S, то есть мы можем записать AQ = QP (1.59) для некоторой матрицы P размерности [r × r]. Предположим, что λ и x – это собственное число и соответствующий собственный вектор матрицы P, т. е. Px = λx. Умножая обе части выражения на Q мы получаем QPx = λQx или, после подстановки (1.59), AQx = λQx. Поскольку столбцы матрицы Q линейно независимы (мы помним, что они выбираются как b = Qx является базисные векторы подпространства S), имеем Qx 6= 0 и, следовательно, x собственным вектором A. Кроме того, Qx ∈ S по определению Q. Теперь мы готовы ко встрече с одной из версий так называемой спектральной теоремы. Эта теорема является одной из ключевых на только в линейной алгебре, но и в теории линейных операторов в целом. Мы рассмотрим формулировку спектральной теоремы для матрицы самосопряженного оператора, действующего на конечномерном линейном пространстве, но этот результат может быть расширен в нескольких направлениях. Во-первых, аналогичные результаты могут быть получены для операторов, определенных на бесконечномерных пространствах, во-вторых, этот результат может быть распространен на случай нормальных операторов (и матриц), т. е. таких, для которых выполняется T ∗ T = T T ∗ . Теорема 1.5.21. Пусть матрица A ∈ F n×n удовлетворяет условию A = A∗ , т. е. для любых x, y ∈ F n выполняется hy, Axi = hAy, xi. Тогда верно следующее: 1. Все собственные числа A вещественны. 2. Собственные векторы A формируют ортонормированный базис F n . Доказательство. Рассмотрим утверждения теоремы по порядку. 1. Пусть λ ∈ F есть некоторое собственное число, а x ∈ F n \ {0} – соответствующий собственный вектор матрицы A, т. е. Ax = λx. Тогда мы можем записать λhx, xi = hAx, xi = hx, Axi = hx, λxi = λ̄hx, xi, откуда следует, что λ = λ̄, т. е. λ ∈ R. 2. Из леммы 1.5.5 следует, что существует по крайней мере одна пара (λ1 , x1 ), состоящая из собственного числа и соответствующего собственного вектора, причем вектор x1 может быть выбран так, что kx1 k = 1. Применим доказательство по индукции. Пусть Xk = (x1 , . . . , xk ) – набор ортонормированных собственных векторов эрмитовой матрицы A, а (λ1 , . . . , λk ) – соответствующие собственные числа. Пусть Xk⊥ – линейное подпространство F n28 , натянутое на векторы, ортогональные к векторам из Xk : Xk⊥ = {y ∈ F n |hy, xi = 0, x ∈ Xk }. Покажем, что подпространство Xk⊥ инвариантно относительно A. Для любого y ∈ Xk⊥ и любого xi ∈ Xk выполняется: hxi , Ayi = hAxi , yi = λi hxi , yi = 0, 28 См. задание 1 в конце раздела. 62 Алгебра – II Д.В. Громов следовательно, AXk⊥ ⊆ Xk⊥ . Согласно лемме 1.5.20, подпространство Xk⊥ содержит по меньшей мере один собственный вектор A, который по определению ортогонален всем o n xk+1 векторам из Xk . Обозначим этот вектор xk+1 и определим набор Xk+1 = Xk ∪ kxk+1 k . Новый набор будет ортонормированным. Продолжая индукцию по k получаем требуемый результат. Из доказательства приведенной теоремы можно сделать вывод, что все собственные числа матрицы A имеют одинаковую алгебраическую и геометрическую кратности. Это следует из того, что на каждом шаге мы выбираем по одному собственному вектору и по одному соответствующему ему собственному числу, причем каждый новый собственный вектор линейно-независим с остальными по построению. Таким образом, если спектр матрицы A содержит некоторое собственное число µ кратности q, то оно будет встречаться нам q раз, причем каждый раз мы будем выбирать некоторый новый собственный вектор, линейнонезависимый с остальными. Следовательно, размерность N (µE − A) будет равна q. Теорема 1.5.22. Пусть матрица A ∈ F n×n удовлетворяет условию A = A∗ . Тогда существует такая унитарная (а в случае F = R, ортогональная) матрица преобразования T, что матрица T−1 AT = T∗ AT – диагональная с собственными числами λ1 , . . . , λn на главной диагонали. Доказательство. Пусть X = (x1 , . . . , xn ) – ортонормированная система собственных векторов, а Λ = (λ1 , . . . , λn ) – соответствующие собственные числа. Составим матрицу T так, что ее столбцы будут равны собственным векторам xi , i = 1, . . . , n. Учитывая Axi = λi xi и правило умножения двух матриц “по столбцам”, получим T−1 AT = T−1 T diag(λ1 , . . . , λn ) = diag(λ1 , . . . , λn ). Унитарность (или ортогональность) матрицы T следует из того, что ее столбцы формируют ортонормированную систему. Запишем ij-й элемент произведения T∗ T: ( 1, i = j ∗ ∗ [T T]ij = xi xj = hxi , xj i = 0, i 6= j. Заметим, что преобразование T∗ AT представляет собой еще один подвид преобразования эквивалентности. Мы встретимся с этим преобразованием, когда будем изучать квадратичные формы. Определение 1.5.7. Матрицы A и à называются конгруэнтными если существует такая унитарная (а в случае F = R, ортогональная) матрица преобразования T, что à = T∗ AT (соответственно, à = T> AT). 1.5.7 Диагонализируемые матрицы Матрицы A, рассмотренные выше, представляют собой частный случай диагонализируемых матриц. 63 Алгебра – II Д.В. Громов Определение 1.5.8. Матрица A называется диагонализируемой, если она подобна диагональной матрице. Иначе говоря, матрица A диагонализируема, если существует такая матрица преобразования T, что T−1 AT – диагональная матрица. Более того, теорема 1.5.11 говорит нам, что диагональные элементы этой матрицы равны собственным числам A. К сожалению, в общем случае матрица преобразования T уже не будет унитарной (ортогональной)29 . Сформулируем теорему, объединяющую несколько важных результатов о диагонализируемых матрицах. Теорема 1.5.23. Пусть A ∈ F n×n – некоторая матрица. Следующие утверждения эквивалентны: 1. Матрица A – диагонализируема. 2. Геометрические кратности всех собственных чисел матрицы A совпадают с соответствующими алгебраическими кратностями. 3. Собственные векторы матрицы A образуют базис F n . Доказательство. Для того, чтобы упростить себе жизнь, мы докажем только три импликации. 1. ⇒ 2. Пусть матрица A подобна некоторой диагональной матрице D. Предположим, что матрица A имеет k различных корней (λ1 , . . . , λk ) с соответствующими алгебраическими кратностями m(λi ), i = 1, . . . , k. Рассмотрим собственное число λi и соответствующий полином pi (x) = x − λi . По теореме 1.5.19, матрицы p(A) и p(D) подобны, а следовательно, по теореме 1.5.16, размерности их ядер совпадают, т. е. N (A − λi E) = N (D − λi E). Рассмотрим матрицу D. Её диагональными элементами являются собственные числа матрицы A, причем каждое собственное число появляется число раз, равное его алгебраической кратности. Таким образом, матрица D − λi E будет диагональной, причем ее диагональ будет содержать ровно m(λi ) нулей. Нетрудно заметить, что размерность ядра этой матрицы будет равна m(λi ). Из вышесказанного мы можем заключить, что dim (N (A − λi E)) = g(λi ) = m(λi ). Так мы показали, что геометрические кратности всех собственных чисел равны алгебраическим. 2. ⇒ 3. Если геометрические кратности равны алгебраическим, то для каждого собственного значения λi мы можем выбрать m(λi ) линейно-независимых собственных векторов. Обозначим через Bi базис подпространств N (λi E − A). Будем обозначать собственные векторы двумя индексами: нижний, i = 1, . . . , k, соответствует порядковому номеру собственного числа, а верхний, j = 1, . . . , g(λi ) будет нумеровать векторы в базисе Bi . g(λ ) g(λ ) В результате мы имеем набор n векторов V = x11 , x21 , . . . , x1 1 , . . . , x1k , . . . , xk k . Предположим, что эти векторы линейно зависимы, т. е. существуют такие, не равные одновременно нулю, коэффициенты αij , что выполняется g(λ1 ) g(λ1 ) x1 α1 x1 + α12 x21 + · · · + α1 |1 1 {z ∈B1 } g(λk ) g(λk ) xk + · · · + αk1 x1k + · · · + αk | {z ∈Bk = 0. (1.60) } 29 Очевидное достоинство унитарных / ортогональных матриц заключается в том, что мы получаем обратную матрицу “бесплатно”. 64 Алгебра – II Д.В. Громов Слагаемые в этой линейной комбинации могут быть разбиты на группы. Каждая группа дает собственный вектор, соответствующий λi (вспомним, что линейная комбинация собственных векторов, соответствующих одному и тому же собственному числу, также является собственным вектором). Для наглядности перепишем (1.60) в виде y1 + y2 + · · · + yk = 0, (1.61) где yi ∈ Bi – некоторые собственные векторы, соответствующие собственным числам g(λ ) λi , либо нулевые векторы, если коэффициенты αi1 , . . . , α1 1 все равны нулю. Однако по теореме 1.5.9, собственные векторы, соответствующие различным собственным числам, линейно независимы. Следовательно равенство (1.61) выполняется только тогда, когда все yi = 0, т. е. g(λi ) g(λi ) xi yi = αi1 x1i + αi2 x2i + · · · + αi = 0, ∀i = 1, . . . , k. g(λ ) Однако векторы (x1i , x2i , . . . , xi i ) по определению линейно независимы, как базисные векторы Bi . Приходим к противоречию, поэтому делаем вывод, что векторы V линейно-независимы. 3. ⇒ 1. Используя систему n линейно-независимых векторов запишем матрицу преобразования T аналогично тому, как сделали это в первой части теоремы 1.5.22. Заметьте, что результат не изменится если мы выберем не ортонормированные, а просто линейны независимые векторы. Обратите внимание, что вещественная матрица может быть не диагонализируема над полем R, но диагонализируема над полем C. В качестве примера можно рассмотреть матрицу A2 из задания 2. Теперь рассмотрим небольшой пример, иллюстрирующий использование метод диагонализации. Пример 1.5.1. Предположим, что мы решили завести кроличью ферму и хотим оценить наши шансы на успех. Для этого мы строим математическую модель, описывающую динамику изменения кроличьей популяции. Для начала заметим, что соотношение самцов и самок в популяции практически неизменно, а прирост кроликов определяется числом самок. Поэтому мы будем описывать только динамику числа крольчих. Затем мы заметим, что выживаемость отдельных особей и число потомства зависит от того, к какой возрастной группе относится крольчиха. Поэтому мы разделим всю популяцию крольчих на 3 группы: 1) до года, 2) от года до двух лет и 3) старше двух лет. Обозначим размеры соответствующих популяций в i-том году переменными x1 (i), x2 (i) и x3 (i). Для модели будем использовать следующие предположения о выживаемости: из новорожденных крольчих до одного года доживает 20%, из годовалых крольчих до двух лет доживает 60%, наконец, если крольчихе больше двух лет, то в 30% случаев у нее есть шанс прожить еще один год. Однако это еще не все. Нам необходимо описать динамику прироста крольчих. Предположим, что крольчихи возрастом до одного года не приносят приплод, годовалые крольчиха рожают в среднем двух крольчих в год, а крольчихи возрастом старше двух лет приносят в среднем по одной крольчихе в год. 65 Алгебра – II Д.В. Громов Теперь мы можем формально описать эти наблюдения. Будем описывать популяцию крольчих в (i + 1)-м году как функцию популяции крольчих в i-м году: x1 (i + 1) = 2x2 (i) + x3 (i) x2 (i + 1) = 0.2x1 (i) прирост новорожденных крольчих,, переход из группы x1 в группу x2 , x3 (i + 1) = 0.6x2 (i) + 0.3x3 (i) переход из групп x2 и x3 в группу x3 . > Обозначим общую популяцию в i-м году вектором состояния x(i) = x1 (i) x2 (i) x3 (i) и запишем уравнения динамики популяции в векторно-матричном виде:   2 1 0  x(i) = Ax(i) x(i + 1) = 0.2 0 (1.62) 0 0.6 0.3 Уравнения (1.62) описывают матричную популяционную модель Лесли или, иначе говоря, дискретную популяционную модель с возрастным структурированием. Пусть в начальный момент времени у нас имеется 100 годовалых крольчих (и соответствующее количество кроликов). Попробуем вычислить количество крольчих, которое мы будем иметь через 15 лет. В начальный момент времени наш вектор состояния будет равен > x(0) = 0 100 0 , по прошествии одного года: x(1) = Ax(0), после двух лет: x(2) = Ax(1) = A2 x(0) и так далее. После ряда итераций мы получим число крольчих после 15 лет работы фермы: x(15) = A15 x(0). Для того, чтобы посчитать эту величину, нам понадобится возвести матрицу A в 15 степень! Возведение матрицы в большую степень – это популярная задача с подвохом. Оказывается, что если матрица A – диагонализируемая, то задача решается достаточно просто. В этом случае существует матрица T такая, что T−1 AT = D, где D – диагональная матрица с собственными числами на главной диагонали. Перепишем это уравнение как TDT−1 = A и вспомним лемму 1.5.18, откуда получим A15 = TD15 T−1 . Возвести диагональную матрицу в 15 степень для нас, конечно, не составит большого труда. Рассмотрим матрицу A. Легко заметить, что ее определитель равен нулю, следовательно мы имеем по крайней мере одно нулевое собственное число, λ1 = 0. Два остальных собственных числа связаны соотношением λ2 + λ3 = 0.3. Произведя требуемые вычисления, получаем λ2 = 0.8 и λ3 = −0.5. Найдя соответствующие собственные векторы и произведя вычисления мы получим окончательный результат:     0.0135 0.0542 0.0271 5.4177 A15 = 0.0034 0.0135 0.0068 и x(15) = 1.3514 . 0.0041 0.0163 0.0081 1.6253 Итак, через 15 лет наша популяция сократится больше, чем в 10 раз. Очевидно, что если мы будем продолжать так дальше, то скоро у нас совсем не останется кроликов (если не считать их дробные части). Это значит, что надо либо уточнить параметры модели, либо менять условия содержания кроликов, например, позаботиться о том, чтобы уменьшить смертность маленьких крольчат. Но на этом мы останавливаться не будем, а подумаем о математической стороне дела. Почему популяция кроликов стала стремиться к нулю? Ответ достаточно очевиден: все собственные числа матрицы A меньше единицы по модулю. Поэтому, когда мы возводим 66 Алгебра – II Д.В. Громов диагональную матрицу D в степени высших порядков, ее диагональные элементы, а следовательно и все решение стремятся к нулю. Так мы получили следующий фундаментальный результат из теории линейных дискретных динамических систем: Если в системе x(i+1) = Ax(i) матрица A диагонализируема и все ее собственные числа (в том числе и комплексные) меньше единицы в абсолютном значении, то выполняется lim x(i) = 0. i→∞ Этот результат выполняется и для недиагонализируемых матриц, но мы пока не готовы исследовать этот случай. На этом мы закончим с кроликами и вернемся к матрицам. Как мы убедились, диагонализируемые матрицы представляют собой очень удобный объект для изучения. Что же делать, если матрица недиагонализируема? В этом случае математики пускают в ход “тяжелую артиллерию” – жорданову нормальную форму матрицы. Об этом мы поговорим в следующем разделе. 1.5.8 Жорданова нормальная форма матрицы Перед тем как мы приступим собственно к жордановой форме матрицы, докажем один результат о геометрических и алгебраических кратностях собственых чисел, который был анонсирован в конце подраздела 1.5.3. Теорема 1.5.24. Для любого собственного числа µ матрицы A выполняется 1 ≤ g(µ) ≤ m(µ), (1.63) т. е. геометрическая кратность собственного числа не превышает его алгебраической кратности. Доказательство. При доказательстве мы будем использовать подход, похожий на тот, который был использован в доказательстве теоремы 1.5.2. Пусть µ – собственное число матрицы A, а N (µE − A) – соответствующее нулевое подпространство. Размерность этого подпространства равна геометрической кратности µ. Пусть g(µ) = k. Выберем k векторов (v1 , . . . , vk ), формирующих базис N (µE−A) и запишем матрицу преобразования подобия T в виде   T = v1 ... vk ṽk+1 ... ṽn  , дополняя систему (v1 , . . . , vk ) до базиса F n . Мы имеем µEk A12 −1 à = T AT = . A22 Подумайте, почему в левом верхнем углу появилась матрица µEk ? 67 Алгебра – II Д.В. Громов Характеристический полином матрицы à имеет вид (см. задание 5 в конце раздела) pà = (λ − µ)k det (λE − A22 ) , т. е. собственное число µ имеет алгебраическую кратность, по меньшей мере равную k. Так мы показали вторую часть неравенства (1.63). Первая часть неравенства (1.63) следует из леммы 1.5.5. Следующее определение может показаться несколько дискриминирующим в отношении матричных меньшинств30 . На самом деле определенные ниже дефектные матрицы представляют собой наиболее сложный класс квадратных матриц. Определение 1.5.9. Матрица называется дефектной если геометрическая кратность по меньшей мере одного ее корня меньше алгебраической кратности. Что можно сказать о дефектной матрице? Пока все ответы будет отрицательными: а) число собственных векторов такой матрицы будет меньше ее размерности; б) эта матрица не может быть приведена к диагональному виду с помощью преобразования подобия. Таким образом нам надо решить два вопроса: найти недостающие собственные векторы и определить канонический вид, к которому мы будем приводить такую матрицу. Очевидно, что этот канонический вид должен быть достаточно простым (иначе зачем он?) и максимально приближенным к диагональному виду. Для начала сформулируем следующий полезный факт. Лемма 1.5.25. Геометрические и алгебраические кратности собственных чисел двух подобных матриц равны. Доказательство. Пусть A и B – две подобные матрицы с собственными числами (λ1 , . . . , λk ). Алгебраические кратности собственных чисел λi совпадают, как следует из равенства характеристических полиномов двух подобных матриц. Зафиксируем некоторое собственное число λi и рассмотрим полином pi (x) = x − λi . По теореме 1.5.19, матрицы pi (A) и pi (B) подобны, а по теореме 1.5.16, ядра этих матриц имеют одинаковую размерность. Следовательно, геометрические кратности собственного числа λi совпадают для матриц A и B. Начнем наш поиск с того, что рассмотрим дефектную матрицу вида   3 2 1 A = 0 3 2 . 0 0 3 Эта матрица имеет собственное число µ алгебраической кратности m(µ) = 3. В то же время пространство N (µE − A) имеет размерность, равную 1, т. е. g(µ) = 1. Единственный собственный вектор, соответствующий µ, имеет вид x = [1, 0, 0]> . Давайте подумаем, какой канонический вид B можно выбрать для матрицы A? Для этого используем тот же прием с матричным полиномом, что и в доказательстве леммы 1.5.25. Рассмотрим полином p(x) = x−µ = x−3. Если матрицы p(A) и p(B) подобны, то подобными 30 Матрицы с кратными собственными числами составляют множество нулевой меры в F n×n . 68 Алгебра – II Д.В. Громов будут также их степени, т. е. p(A)k и p(B)k будут подобны для всех полином p(A) и его степени:      0 2 1 0 0 4 p(A) = 0 0 2 , [p(A)]2 = 0 0 0 , [p(A)]3 = 0 0 0 0 0 0 0 k ∈ N. Рассмотрим  0 . Используя reverse engineering, мы заключаем, что подобная матрица B должны иметь вид B = µE + Q, где Q3 = 0, т. е. матрица B должна представлять собой сумму диагональной матрицы с собственным числом µ на диагонали и нильпотентной матрицы31 Q. Простейшая нильпотентная матрица Q, удовлетворяющая условию Q3 = 0 будет иметь вид32   0 1 0 Q = 0 0 1 0 0 0 и, следовательно, в качестве канонической формы  3 B = µE + Q = 0 для матрицы A мы выберем  1 0 3 1 . 0 3 Теперь осталось понять, как выбрать матрицу преобразования T такую, что T−1 AT = B. Запишем матрицу T по столбцам и перепишем это выражение в более удобном виде:      µ 1 0 A x1 x2 x3  = x1 x2 x3   0 µ 1  . 0 0 µ Первый столбец дает нам выражение для собственного числа / вектора: Ax1 = µx1 . Интересное начинается, когда мы переходим ко второму и третьему столбцам: Ax2 = x1 + µx2 Ax3 = x2 + µx3 . Перепишем эти выражения, собрав члены с повторяющимся собственным вектором: (A − µE)x2 = x1 (A − µE)x3 = x2 . (1.64) Домножим первое равенство на (A − µE), а второе на (A − µE)2 и учтем, что x1 = N (A − µE): (A − µE)2 x2 = (A − µE)x1 = 0 (A − µE)3 x3 = (A − µE)2 x2 = 0. Теперь мы можем сформулировать для себя закономерность: первый, «истинный» собственный вектор x1 принадлежит N (A − µE), второй, обобщенный собственный вектор – подпространству N (A − µE)2 и так далее. На практике векторы x2 и x3 находят, решая последовательность неоднородных линейных уравнений (1.64). 31 Напомню, что матрица Q называется нильпотентной если существует такое k ∈ N, что Qk = 0 и Qk−1 6= 0 32 Очевидно, с равным успехом можно было бы выбрать Q> , но как-то так уж сложилось... 69 Алгебра – II Д.В. Громов Доведем наши вычисления до конца и посчитаем векторы x2 и x3 : x2 = [0, 1/2, 0]> , x3 = [0, −1/8, 1/4]> . Можно убедиться, что векторы x1 , x2 и x3 действительно задают преобразования подобия, приводящее матрицу A к каноническому виду:  1  0 1 2 −1  3  1 − 8  0 2 1 4 3  1 1  2 0 1 2 3  3  1 − 8  = 0 1 1 4    1 3 3 Формализуем наши наблюдения. Для этого определим некоторые понятия. Определение 1.5.10. Жордановым блоком размерности ki , соответствующим собственному числу λi , называется матрица Jλi ,ki размерности [ki × ki ] с элементами, равными λi , на главной диагонали и единичными наддиагональными элементами. Определение 1.5.11. Вектор y называется обобщенным собственным вектором матрицы A, соответствующим собственному числу µ если существует такое натуральное число k > 1, что y ∈ N (A − µE)k и y ∈ / N (A − µE)j для всех j < k. Обобщенные собственные векторы, соответствующие собственному числу µ находятся в результате решения последовательности уравнений вида (1.64), которые называются жордановыми цепочками. Каждая жорданова цепочка порождается «истинным» собственным вектором, соответствующим собственному числу µ и продолжается до тех пор, пока некоторая степень матрицы (A − µE) не обращается в нулевую матрицу, т. е. пока для некоторого k > 1 не выполняется (A − µE)k = 0. Обратите внимание: если некоторый собственный вектор µ имет алгебраическую кратность r и геометрическую кратность q, то это означает, что для вычисления обобщенных собственных векторов, соответствующих собственному числу µ, нам потребуется «пройти» q жордановых цепочек, причем общая длина всех этих цепочек будет равна r. Каждая жорданова цепочка порождает свой жорданов блок. Следовательно в описанном случае мы будем иметь q жордановых блоков общей размерностью, равной r, однако размерности отдельных блоков могут быть определены только после выяснения длин всех цепочек. Теорема 1.5.26. Пусть матрица A имеет k собственных векторов (λ1 , . . . , λk ) с геометрическими кратностями g(λi ) = qi . Тогда матрица A подобна матрице, имеющей жорданову нормальную форму, т. е. существует такая невырожденная матрица T, что   Jλ1 ,r11   ..   .     J l1   λ1 ,r1   . −1  , .. T AT =  (1.65)    1 J   λk ,rk     .. .   Jλ ,rlk k 70 k Алгебра – II Д.В. Громов где для каждого i = 1, . . . , k сумма размерностей жордановых блоков, соответствующих числу λi , равна алгебраической кратности этого собственного числа, Pli собственному j r = m(λ ). Каноническая жорданова форма определена с точностью до перестановi j=1 i ки жордановых блоков. Мы не будем доказывать эту теорему. Вместо этого вам предлагается попробовать самим найти матрицу преобразования подобия и записать жорданову нормальную форму матрицы   −1 0 0 0 1 0 . −1 1 0 1 0 1 2  0 A=  1 −1 Порядок действий должен быть следующим: 1. Найти собственные числа матрицы и определить их алгебраические и геометрические кратности. 2. Найти все собственные векторы. Их число должно быть равно сумме геометрических кратностей всех собственных чисел. 3. Для каждого собственного вектора построить жордановы цепочки и вычислить все обобщенные собственные векторы. Длины жордановых цепочек равны размерам соответствующих жордановых блоков. 4. Записать каноническую жорданову форму матрицы A. 5. Сформировать матрицу преобразования подобия T из собственных векторов и обобщенных собственных векторов, записывая их в следующем порядке: собственный вектор, за ним обобщенные собственные векторы, полученные в ходе решения соответствующей жордановой цепочки и в том же порядке; следующий собственный вектор и так далее. 6. Проверить, что преобразование подобия T−1 AT действительно равна канонической жордановой форме, записанной ранее. Теперь, когда мы достаточно хорошо освоились с жордановой нормальной формой, я открою вам большую тайну: жорданову форму матрицы никто не считает. Это связано с тем, что процедура вычисления обобщенных собственных векторов плохо обусловлена. Небольшая ошибка округления, и вот кратные собственные числа «расходятся», появляются «спрятанные» до сих пор собственные векторы и жорданова структура матрицы пропадает. В качестве примера рассмотрите собственные числа и векторы «возмущенного» жорданового блока J̃   1 1 0 J̃ = 0 1 1 0 1 для сколь угодно малых значений ≈ 0. Однако жорданова нормальная форма вовсе не является бесполезной. Исследуя различные свойства матриц мы всегда можем опираться на тот факт, что любая матрица может быть приведена к нормальной жордановой форме некоторым преобразованием подобия. При этом сам вид матрицы преобразования T не играет роли, так как в большинстве случаев мы можем «вынести ее за скобки». 71 Алгебра – II Д.В. Громов Для иллюстрации того, как жорданова форма может быть применена для выяснения свойств матриц, мы рассмотрим фундаментальную теорему Гамильтона-Кэли (Cayley-Hamilton)33 . Теорема 1.5.27. Пусть A – квадратная матрица, а pA (λ) – ее характеристический полином. Тогда верно pA (A) = 0. Иначе говоря, каждая квадратная матрица удовлетворяет своему характеристическому полиному. Доказательство. Пусть AJ – нормальная жоранова форма матрицы A, т. е. существует такая матрица преобразования подобия T, что T−1 AT = AJ . Согласно теореме 1.5.19, матрицы pA (A) и pA (AJ ) подобны. Предположим, что матрица A (и AJ ) имеет k собственных чисел (λ1 , . . . , λk ) с алгебраическими кратностями (m(λ1 ), . . . , m(λk )). Тогда ее характеристический полином pA (λ) будет иметь вид pA (λ) = (λ − λ1 )m(λ1 ) · · · (λ − λk )m(λk ) . Посмотрим, чему будет равен полином pA от матрицы AJ . Для начала заметим, что матрица AJ имеет блочно-диагональный вид (1.65) с жордановыми блоками на главной диагонали. Кроме того, вспомним, что возведение блочно-диагональной матрицы в некоторую степень соответствует возведению в эту степень всех диагональных блоков матрицы. Теперь представим pA (AJ ) в виде произведения k выражений вида (A − λi E)m(λi ) , где i = 1, . . . , k. В выражении (A − λi E), диагональные блоки, соответствующие собственному числу λi , превращаются в нильпотентные матрицы порядка, не превышающего m(λi ). При возведении (A − λi E) в степень m(λi ), все нильпотентные матрицы обнуляются. В результате в каждом выражении (A − λi E)m(λi ) есть нулевой диагональный блок (или диагональные блоки)34 , соответствующие собственному значению λi . При перемножении выражений (A − λi E)m(λi ) соответствующие диагональные блоки перемножаются. Поскольку каждый диагональный блок равен нулю в одном из этих выражений, в результате перемножения получаем нулевую матрицу. Наконец, замечая, что нулевая матрица подобна только нулевой матрице, мы приходим к требуемому результату. Теорема Гамильтона-Кэли имеет много применений, но мы сейчас рассмотрим только одно из них. Предположим, что нам дана некоторая невырожденная матрица A и мы хотим найти обратную к ней. При этом нам известен характеристический полином pA (λ) = λn + · · · + an−1 λ + an . Можем ли мы найти обратную, не вычисляя матрицу алгебраических дополнений? Ответ: «да»! Согласно упомянутой теореме, выполняется равенство pA (A) = An + · · · + an−1 A + an E = 0. Разделим это выражение на −an , перенесем E в правую часть и немного переформулируем выражение слева: 1 n−1 − A + · · · + an−1 E A = E. an Теперь нам не составит труда записать выражение для A−1 : 1 n−1 A−1 = − A + · · · + an−1 E . an 33 По какой-то причине в русском названии этой теоремы фамилии авторов поменяны местами. Видимо упорядочены по старшинству – Гамильтон был старше Кэли. 34 Это зависит от того, сколько жордановых цепочек «привязано» к собственному значению λ . i 72 Алгебра – II Д.В. Громов Это значит, что мы можем найти обратную матрицу как взвешенную сумму степеней матрицы A вплоть до степени (n − 1). Задачи и вопросы 1. Покажите, что множество векторов, ортогональных к некоторому подпространству S ∈ F n , образует векторное подпространство. Это подпространство называется ортогональным дополнением к S и обозначается S ⊥ . 2. Найдите собственные числа, левые и правые собственные векторы следующих матриц: −1 2 1 2 1 1 1 1 A1 = , A2 = , A3 = , A4 = , A5 = 2 −1 −2 1 −1 −2 1 1 1+i 2 0.9 1 1 −2 0 −i A6 = , A7 = , A8 = , A9 = . 1 i 0.1 0 1 i , i 3. Предположим, что некоторая квадратная вещественная матрица размерности [2 × 2] имеет собственные числа λ1,2 = a ± bi. Запишите элементы этой матрицы. Будет ли она однозначно определяться своими собственными значениями? 4∗ . Для верхней треугольной матрицы размерности [3 × 3] найдите собственные векторы, соответствующие собственным числам a11 , a22 и a33 . Рассмотрите случаи, когда (a) все собственые числа различны, (b) есть собственное число кратности 2, и (c) есть собственное число кратности 3. Для случая кратных собственных чисел определите условия, при которых геометрическая кратность собственного числа будет меньше алгебраической. 5. Докажите, что собственные числа блочно-диагональной матрицы совпадают с собственными числами диагональных блоков. Как собственные векторы этой блочно-диагональной матрицы связаны с собственными векторами диагональных блоков? 6∗ . Какими свойствами обладают собственные числа матриц перестановок? Исследуйте для начала матрицы перестановок размерности [3 × 3], попробуйте найти закономерности и обобщить их на случай матрицы размерности [n × n]. 7. Докажите, что левый и правый собственные векторы вещественной матрицы, соответствующие различным собственным числам, ортогональны. Указание: пусть yi и xj – левый и правый собственные векторы матрицы A, соответствующие собственным числам λi и λj . Рассмотрите выражение yi> Axj . 8. Подумайте, что произойдет, если в предыдущем задании мы рассмотрим комплексную матрицу вместо вещественной. Как изменится результат? 9. Определите собственные числа и собственные векторы нулевой матрицы размерности [n × n]. Определите алгебраические и геометрические кратности собственных чисел. Сделайте то же самое для матрицы размерности [n × n], у которой все элементы равны 1. 10. Пусть A – диагонализируемая матрица, т. е. существует такая невырожденная матрица преобразования подобия T, что T−1 AT = D, где D – диагональная матрица. Что мы можем сказать про матрицу, обратную к A, т. е. A−1 ? Будет ли она диагонализируемой? Если да, то как будет выглядеть диагонализирующее преобразование подобия? 11∗ . Пусть A – матрица с попарно различными собственными числами. Докажите, что матрица B коммутирует с A, т. е. выполняется AB = BA тогда и только тогда, когда A и B имеют одинаковый набор собственных векторов. 12. Покажите, что из решения предыдущей задачи следует, что две матрицы с различными собственными числами коммутируют если они одновременно диагонализируемы, т. е. существует матрица преобразования подобия T, диагонализирующая как A так и B. 13. Пусть T−1 AT = B и x – собственный вектор матрицы A, соответствующий собственному числу λ. Чему будет равен собственный вектор B, соответствующий λ? 73 Глава 2 Квадратичные формы 2.1 Канонический вид квадратичной формы В этой главе мы очень коротко познакомимся с квадратичными формами. Обычно квадратичные формы определяют как однородные полиномы второй степени от набора переменных (x1 , . . . , xn ). Однако мы сразу определим квадратичную форму используя векторноматричную нотацию. Для тех, кому интересна полиномиальная интерпретация квадратичных форм, рекомендуется [Утешев, Калинина. Часть-? Глава-?]. Мы будем рассматривать только вещественные квадратичные формы. Комплексные квадратичные формы имеют свою специфику, вдаваться в которую мы не будем. Определение 2.1.1. Квадратичной формой Q(x), x ∈ Rn , называется билинейное отображение Q(·) : Rn × Rn → R, заданное выражением Q(x) = x> Qx. (2.1) Матрица Q ∈ Rn×n называется матрицей квадратичной формы Q(x). Заметим, что любая квадратичная форма представляет собой скаляр. Поэтому для любой матрицы Q и любого вектора x выполняется > x> Qx = x> Qx = x> Q> x. Используя этот факт мы можем симметризовать квадратичную форму Q(x) и записать ее как e e = 1 Q + Q> . Q(x) = x> Qx, где Q 2 e не будут равны, однако все эти матрицы Очевидно, что в общем случае матрицы Q, Q> и Q задают одну и ту же квадратичную форму. Поэтому мы в дальнейшем будем полагать1 матрицу Q симметрической. Посмотрим, что же произойдет, если мы перейдем к другому базису в Rn . Запишем уравнение перехода в виде x = Py и подставим его в (2.1). Тогда выражение для квадратичной 1 Как говорят математики, без потери общности. 74 Алгебра – II Д.В. Громов формы приобретет вид Q(y) = y> P> QPy. (2.2) Мы видим, что при переходе к новому базису матрица Q заменяется на конгруэнтную матрицу U = P> QP. Преобразование конгруэнтности – это частный случай преобразование эквивалентности, однако не частный случай преобразования подобия! Это значит, что свойства преобразования подобия, которые мы изучили выше, не могут быть автоматически перенесены на преобразование конгруэнтности. В качестве упражнения вам рекомендуется изучить, какие свойства матрицы сохраняются при преобразовании конгруэнтности2 . В дальнейшем нас будет интересовать один частный случай, а именно преобразование конгруэнтности симметрической матрицы Q. Мы помним, что любая симметрическая матрица может быть диагонализирована с помощью ортогональной матрицы преобразования P. Это значит, что мы можем найти такую матрицу P, что P−1 = P> и P> QP = D, где D – диагональная матрица с собственными числами на главной диагонали. Мы пойдем немного дальше и поменяем столбцы матрицы P таким образом, что собственные значения на диагонали матрицы D будут упорядочены по знаку: сначала k ≤ n положительных собственных значений, затем r ≤ n − r отрицательных собственных значений и наконец n − k − r нулевых собственных значений3 . Запишем матрицу D в виде произведения трех диагональных матриц:   1   ..   .     1     −1     . .. (2.3) D = D 12   D 21 ,     −1         . .   . где матрица D 21 имеет вид √         D 12 =         λ1  .. . √         .        λk p |λk+1 | .. . p |λk+r | 1 .. . 1 2 Дам подсказку: их гораздо меньше, чем для преобразования подобия. Поэтому преобразование конгруэнтности менее известно среди широкой публики. 3 Мы помним, что все собственные значения симметрической матрицы вещественны. 75 Алгебра – II Д.В. Громов e как произведение P e = D 1 P, где P – это диагонализирующая матриОпределим матрицу P 2 e невырождена (обратите ца, составленная из собственных векторов матрицы Q. Матрица P внимание на последние n − k − r единичных элементов в матрице D 21 ), поэтому она заe уже не будет ортогональной дает преобразование базиса, так же как P. В то же время P матрицей, но для нас это сейчас неважно. Сопоставляя все изложенные выше факты мы можем сформулировать закон инерции Сильвестра. Теорема 2.1.1. Пусть Q ∈ Rn×n есть симметрическая матрица. Тогда существует такая невырожденная матрица P, что матрица Q может быть приведена конгруэнтным преобразованием P> QP к диагональной матрице D, содержащей на главной диагонали исключительно элементы {−1, 0, 1}. При этом число положительных, отрицательных и нулевых элементов определено единственным образом (в отличие от их порядка). Выше мы рассмотрели процедуру построения диагональной матрицы требуемого вида. Единственный открытый вопрос заключается в доказательстве того, что число элементов каждого вида определено однозначно. Мы оставим его на потом... Применительно к квадратичным формам этот результат может быть сформулирован следующим образом. Следствие 2.1.2. Пусть Q(x) = x> Qx есть квадратичная форма. Тогда существует такое преобразование базиса x = Py, что в новых координатах квадратичная форма Q записывается в каноническом виде: 2 2 Q(y) = y12 + · · · + yk2 − yk+1 − · · · − yk+r . Число r отрицательных членов называется индексом инерции данной квадратичной формы, а число k − r, т. е. разность между числом положительных и отрицательных членов называется сигнатурой квадратичной формы. Обсуждение и обобщение на случай эрмитовых матриц см. [5]. 2.2 Знакоопределенные квадратичные формы Начнем с определения. Определение 2.2.1. Квадратичная форма Q(x) называется положительно-определенной (отрицательно-определенной) если Q(x) > 0 (Q(x) < 0) для всех x ∈ Rn \ {0}. Аналогично, квадратная симметрическая матрица Q называется положительно-определенной (отрицательно-определенной), если квадратичная форма Q(x) = x> Qx положительноопределена (отрицательно-определена). Обратите внимание: свойство знакоопределенности определено только для симметрических матриц. Обобщение этого свойства на произвольные квадратные матрицы может привести к ошибочным заключениям. Знакоопределенные (и не только) квадратичные формы играют очень важную роль в теории оптимизации, в дифференциальной (римановой) геометрии, релятивистической физи- 76 Алгебра – II Д.В. Громов ке (метрика пространства-времени4 ) и многих других областях прикладной математики. В связи с этим необходимо определить критерии для выяснения знакоопределенности некоторой матрицы (квадратичной формы). Теорема 2.2.1. Квадратная симметрическая матрица Q ∈ Rn×n является положительноопределенной (отрицательно-определенной) тогда и только тогда, когда все ее собственные числа строго положительны (отрицательны). Доказательство. Используя ортогональное преобразование x = Py квадратичная форма Q(x) = x> Qx может быть приведена к виду Q(y) = y> Dy = n X λi |yi |2 . i=1 Знак этого выражения определяется знаками собственных чисел. Заметим, что в случае нулевых собственных чисел квадратичная форма будет равна нулю для некоторых (каких?) значений x 6= 0, т. е. будет полуопределенной. Лемма 2.2.2. Пусть Q ∈ Rn×n есть симметрическая матрица. Если v> Qv > 0 для всех ненулевых векторов из некоторого k-мерного подпространства V ⊂ Rn , то Q имеет по меньшей мере k положительных собственных чисел (с учетом кратностей). Доказательство. Рассмотрим ортонормированный базис B = (x1 , . . . , xn ) пространства Rn , состоящий из собственных векторов Q вместе с соответствующими собственными числами (λ1 , . . . , λn ). Предположим, что m первых собственных чисел положительны, а остальные отрицательны или равны нулю. Проведем доказательство от обратного и предположим, что m < k. В этом случае (вспоминаем теорему 1.2.9), пересечение подпространства V и линейной оболочки n − m последних векторов базиса B имеет ненулевую размерность, т. е. \ V span(xm+1 , . . . , xn ) 6= {0} и, следовательно, существует такой вектор v0 ∈ V , который может быть записан в виде невырожденной линейной комбинации векторов (xm+1 , . . . , xn ): v0 = αm+1 xm+1 + · · · + αn xn . Вычислим квадратичную форму (v0 )> Qv0 , но для удобства запишем ее в виде скалярного произведения: hv0 , Qv0 i = hv0 , Q (αm+1 xm+1 + · · · + αn xn )i = hv0 , (αm+1 λm+1 xm+1 + · · · + αn λn xn )i = (∗) 2 = αm+1 λm+1 + · · · + αn2 λn , где равенство (∗) следует из условия ортонормированности векторов xi . Поскольку все собственные числа (λm+1 , . . . , λn ) полагаются неположительными, имеем (v0 )> Qv0 ≤ 0, что противоречит условию. Следовательно, m ≥ k, что и требовалось доказать. 4 Правда метрика в пространстве Минковского задается знакопеременной формой, но мы все равно ее здесь упомянем. 77 Алгебра – II Д.В. Громов Квадратичные формы и скалярное произведение∗ . Как вы уже заметили, квадратичную форму можно представить в виде скалярного произведения, т. е. можно записать x> Qx = hx, Qxi. Однако мы можем подойти к задаче с другой стороны и задать скалярное произведение в виде hy, xiQ = y> Qx, где Q есть некоторая квадратная матрица, которая называется структурной матрицей скалярного произведения. Такое скалярное произведение называется косым, так как оно уже не связано с привычным отношением ортогональности двух векторов. Подумайте, каким свойствам должна удовлетворять матрица Q для того, чтобы скалярное произведение h·, ·iQ было хорошо определено? После небольшого лирического отступления мы вернемся к квадратичным формам и докажем результат, который обычно используется для проверки положительной определенности квадратичной формы. Предварительно напомню, что угловым минором порядка k квадратной матрицы Q называется определитель матрицы, полученной вычеркиванием последних n − k столбцов и строк матрицы Q. Обозначим такую угловую подматрицу через Q[1 . . . k]. Теорема 2.2.3 (Критерий Сильвестра). Квадратичная форма Q(x) = x> Qx является положительно определенной тогда и только тогда, когда все угловые миноры строго положительны. Доказательство. Для доказательства необходимости рассмотрим квадратичную форму Q(x) на подпространстве векторов, у которых последние n − k элементов равны нулю, т. е. векторов вида [x1 , . . . , xk , 0, . . . , 0] = [xk , 0n−k ]. Применительно к таким векторам квадратичная форма принимает вид Q([xk , 0n−k ]) = x> k Q[1 . . . k]xk . Такое сужение квадратичной формы будет положительно определенным, следовательно по лемме 2.2.1 все собственные числа матрицы Q[1 . . . k] положительны и по теореме 1.5.14, det (Q[1 . . . k]) > 0. Достаточность докажем по индукции. Для n = 1 результат следует тривиально. Предположим, что достаточность критерия Сильвестра показана для квадратных симметрических матриц размерности [k − 1 × k − 1] и меньше. Если P ∈ Rk×k – симметрическая матрица с положительными угловыми минорами, то по предположению матрица P[1 . . . k − 1] положительно определена. Это значит, что матрица P положительна определена на (k − 1)-мерном подпространстве Rk , состоящем из векторов, у которых последний элемент равен 0. По лемме 2.2.2, матрица P имеет по меньшей мере k − 1 положительное собственное число. В то же время, определитель P положителен по индукционному предположению. Следовательно недостающее собственное число может быть только положительным. Заключаем, что матрица P положительно определена. Продолжая индукцию, получаем требуемый результат. Показанное доказательство достаточности использует упрощенный вариант результата, который известен как теорема Коши о чередовании собственных значений. Приведенные результаты можно развивать дальше в нескольких направлениях. Так, например, развивая лемму 2.2.2, можно показать, что для любой квадратичной формы x> Qx пространство Rn можно представить в виде прямого произведения пространств V + , V − и V 0 , на которых квадратичная форма принимает только положительные, отрицательные или нулевые значения. Эти подпространства инвариантны относительно преобразования базиса, поэтому любая структурная матрица квадратичной формы всегда будет иметь одинаковое число положительных, отрицательных и нулевых собственных чисел, независимо от выбора базиса. 78 Алгебра – II Д.В. Громов Однако мы остановимся и закончим на этом основную часть курса линейной алгебры. Задачи и вопросы 1. Запишите квадратичную форму Q(x1 , x2 ) = x1 x2 в векторно-матричном виде и определите преобразование координат, приводящее эту форму к каноническому виду. 2. 79 Глава 3 Приложения линейной алгебры 3.1 Марковские цепи Для того, чтобы определить понятие марковской цепи, нам потребуется несколько элементарных фактов из теории вероятностей. При этом само понятие вероятности события мы будем полагать интуитивно понятным. Рассмотрим полный набор взаимоисключающих событий Ω = {1, . . . , N }. «Полный» означает, что приведенное множество содержит все возможные события, а «взаимоисключающих» значит, что в каждый отдельный момент времени может осуществиться только одно событие из множества Ω. Обычно мы не знаем точно, какое именно событие произойдет, поэтому мы полагаем (или оцениваем) вероятность осуществления события i ∈ Ω и обозначаем1 ее xi ∈ [0, 1]. Значения на границах интервала соответствуют детерминированным случаям: если xi = 0, то событие точно не произойдет, если xi = 1, то событие достоверно произойдет. Сумма всех вероятностей осуществления событий из множества Ω равна 1: X xi = 1. i∈Ω Интуитивно это можно интерпретировать так, что одно из событий обязательно должно произойти. Предположим, что интересующие нас события могут осуществляться в определенные моменты времени n = 0, 1 . . . Соответственно, вероятность реализации события i ∈ Ω становится функций времени n ∈ N0 и обозначается xi (n) ∈ [0, 1]. Для сокращения записи мы будем использовать векторную нотацию и обозначим через x(n) распределение вероятностей в момент n:   x1 (n)   x(n) =  ...  . xN (n) 1 Обычно вероятность обозначается буквой p, но мы пожертвуем традицией для того, чтобы потом получить уравнения в привычной нам форме. 80 Алгебра – II Д.В. Громов Рис. 3.1: Фрагмент марковской цепи. Сумма элементов вектора x(n) равна 1 для каждого момента времени n. Мы будем называть такой вектор стохастическим. Иначе говоря, вектор x(n) является единичным, но в какой норме? Теперь мы подходим к ключевому предположению, лежащему в основе теории марковских цепей. А именно, предположим, что вероятность осуществления события i ∈ Ω в момент времени n ∈ N зависит исключительно от того, какое событие произошло в момент времени n − 1. При этом зависимость эта также носит вероятностный характер. А именно, мы определяем вероятности переходов pji ∈ [0, 1] следующим образом2 : pji – вероятность того, что событие j реализуется в момент времени n ∈ N, если в момент времени n − 1 осуществилось событие i ∈ Ω. Марковская цепь может быть графически представлена в виде ориентированного взвешенного графа, в котором вершины соответствуют событиям, а ребра описывают связи между событиями, причем вес ребра равен вероятности того, что одно событие повлечет за собой другое (см. рис. 3.1). Вершины этого графа принято называть состояниями марковской цепи. Мы говорим, что xi (n) – это вероятность того, что в момент времени n цепь находится в состоянии i. Обратите внимание: в каждый момент времени марковская цепь может находиться в любом состоянии с некоторой вероятностью. Это отличает цепь Маркова от обычных динамических систем, где состояние системы в каждый момент времени определено однозначно. Для дальнейших выкладок нам потребуется вспомнить основные правила алгебры вероятностей. Известно, что вероятность совместного осуществления двух событий (А и В) равна произведению их вероятностей: pA∨B = pA pB , а вероятность осуществления одного из событий (А или В) равна сумме их вероятностей: pA∧B = pA + pB . Давайте посмотрим, чему равна вероятность того, что в момент n = 1 цепь будет находиться в состоянии i? Рассмотрим все комбинации событий, удовлетворяющие требуемому условию: в момент n = 0 цепь находилась в состоянии 1 и произошел переход 1 → i или в момент n = 0 цепь находилась в состоянии 2 и произошел переход 2 → i или . . . или в момент n = 0 цепь находилась в состоянии N и произошел переход N → i. Запишем это формально, 2 Обратите внимание на «обратный» порядок индексов. Скоро мы увидим, для чего это было сделано. 81 Алгебра – II Д.В. Громов используя приведенные выше правила сложения и умножения вероятностей: xi (n) = pi1 x1 (n − 1) + pi2 x2 (n − 1) + · · · + piN xN (n − 1) = N X pij xj (n − 1). (3.1) j=1 Заметьте, что вероятности переходов pji не зависят от n, поэтому мы можем записать уравнение (3.1) для произвольного момента n ∈ N. Перепишем уравнение (3.1) в векторно-матричном виде: x(n) = Px(n − 1), (3.2) где P = {pij }, i, j = 1, . . . , N , – матрица переходных вероятностей. Теперь мы имеем дело с дискретной динамической системой, подобной той, которую мы рассматривали в примере 1.5.1, только переменные xi (n) соответствуют вероятностям. Начнем с изучения структуры и свойств матрицы P. В j-том столбце этой матрицы стоят вероятности p1j , p2j , . . . , pN j , соответствующие переходам j → 1, j → 2, и так далее до j → N . Очевидно эти события образуют полную систему, т. е. один из переходов должен осуществиться (если цепь осталась в состоянии j, то мы говорим, что произошел переход j → j). Это значит, что для каждого j = 1, . . . , N должно выполняться N X pij = 1. i=1 Определение 3.1.1. Матрица P с неотрицательными компонентами, у которой сумма элементов каждого столбца равна 1, называется стохастической по столбцам. Аналогичным образом определяется матрица, стохастическая по строкам. В дальнейшем мы будем рассматривать только матрицы, стохастические по столбцам. Это связано с тем, что мы записываем распределение вероятностей x в виде столбца. В некоторых областях приложений принято записывать x в виде строки, т. е. вместо Px мы имеем дело с x> P> . Очевидно, что матрица P> будет стохастической по строкам. Легко проверить, что любая стохастическая матрица имеет собственное число, равное 1. Его алгебраическая кратность может отличаться от единицы в зависимости от структуры матрицы. Запишите несколько стохастических матриц с собственным числом 1 различной алгебраической кратности. Однако как же обстаит дело с остальными собственными числами? Оказывается, стохастические матрицы обладают одним очень интересным свойством. Теорема 3.1.1. Для любого собственного числа стохастической матрицы λi выполняется |λi | ≤ 1. Доказательство. Пусть P – стохастическая по столбцам матрица. Будем рассматривать транспонированную матрицу P> и ее собственные числа и векторы (т. е. , фактически, левые собственные числа и векторы матрицы P). Мы помним, что левые и правые собственные числа матрицы совпадают, поэтому такой переход правомочен. Для начала заметим, что P> 1N ×1 = 1N ×1 , т. е. 1 является собственным числом матрицы P> с соответствующим собственным вектором 1N ×1 . 82 Алгебра – II Д.В. Громов Предположим, что существует такое собственное число µ ∈ C матрицы P> , что |µ| > 1. Тогда для некоторого вектора y выполняется P> y = µy. Пусть yi – наибольший по абсолютному значению элемент вектора y. Абсолютное значение |µyi | может быть записано как |µyi | = |p1i y1 + · · · + pN i yN |. (3.3) Оценим правую часть выражения (3.3) с использованием неравенства треугольника и учтем, что компоненты i-й строки матрицы P> вещественны, неотрицательны и суммируются в 1: |µyi | = |p1i y1 + · · · + pN i yN | ≤ |p1i y1 | + · · · + |pN i yN | ≤ p1i |yi | + · · · + pN i |yi | ≤ |yi |. Итак, мы получили |µ||yi | = |µyi | ≤ |yi |, что противоречит нашему предположению о том, что |µ| > 1. Теперь мы вернемся к динамике марковской цепи. Следуя той же логике, что и для дискретной модели кроличьей популяции в примере 1.5.1, можно записать распределение вероятностей состояний марковской цепи в момент времен n как x(n) = Pn x(0). Однако мы помним, что распределение вероятностей всегда должно суммироваться в единицу. Будет ли это условие выполняться для всех x(n)? Следующие результаты дают ответ на этот вопрос. Лемма 3.1.2. Произведение двух стохастических матриц есть стохастическая матрица. Доказательство. Пусть P = {pij } и Q = {qij }, i, j = 1, . . . , N , суть две стохастические по столбцам матрицы. Зафиксируем некоторый индекс j и запишем выражение для суммы элементов j-го столбца произведения PQ: ! N N N N X N N X X X X X qkj = 1. pik qkj = pik qkj = [PQ]ij = i=1 i=1 k=1 k=1 i=1 k=1 Если же P и Q – две матрицы, стохастические по строкам, мы получим аналогичный ре> зультат, рассматривая транспонированнное произведение (PQ) . Лемма 3.1.3. Произведение стохастического вектора и стохастической матрицы дает стохастический вектор. Доказательство леммы аналогично доказательству леммы 3.1.2 и оставлятся в качестве упражнения. Теперь, когда мы немного познакомились с азами марковских цепей, впору рассмотреть несколько примеров. Начнем с валютного рынка, известного под названием Форекс (ForEx). Пример 3.1.1. Предположим, что мы хотим построить модель изменения курса RUB/USD. Для этого мы выделим три состояния курса рубля по отношению к доллару: {курс падает, курс не меняется, курс растет} и обозначим их буквами D, S и A (depreciating, steady and appreciating). Будем считать для определенности, что эти состояния описывают усредненное поведение рынка в определенный интервал времени и определяются один раз в день. После длительного наблюдения за поведением курса мы определили вероятности 83 Алгебра – II Д.В. Громов переходов между различными состояниями3 , которые собраны в матрице переходов (следуя нашему соглашению, столбец обозначает состояние в i-й день, а строка – состояние в (i + 1)-й день): D(i) S(i) A(i) " D(i + 1) 0.3 0.2 0.3 # P = S(i + 1) 0.5 0.6 0.5 A(i + 1) 0.2 0.2 0.2 Посмотрим, как будет изменяться распределение вероятностей x(i) если мы предположим, что в первый день рынок находится в стабильном состоянии, курс не меняется. Тогда x(0) = [0, 1, 0]> . Посчитаем значения x(i), i = 1, . . . ,         0.2 0.24 0.244 0.2444 x(1) = 0.6 , x(2) = 0.56 , x(3) = 0.556 , x(4) = 0.5556 , x(5) ≈ x(4), . . . 0.2 0.20 0.200 0.200 Начиная с пятого дня, распределение вероятностей практически не меняется, а в пределе стремится к некоторому стационарному (или предельному) распределению x̄. Однако что произойдет, если мы начнем наши наблюдения в тот момент, когда рынок находится в другом состоянии? Давайте проведем эксперимент. Посчитаем значения x(i), начиная с другого начального распределения, x(0) = [1, 0, 0]> . Получаем         0.3 0.25 0.245 0.2445 x(1) = 0.5 , x(2) = 0.55 , x(3) = 0.555 , x(4) = 0.5555 , x(5) ≈ x(4), . . . 0.2 0.20 0.200 0.200 Всего за несколько шагов мы практически сошлись к тому же предельному распределению. Но как получается такой результат? Для того, чтобы разобраться с вопросом, посчитаем значения степеней матрицы P:       0.25 0.24 0.25 0.245 0.244 0.245 0.2445 0.2444 0.2445 P2 = 0.55 0.56 0.55 , P3 = 0.555 0.556 0.555 , P4 = 0.5555 0.5556 0.5555 . 0.20 0.20 0.20 0.200 0.200 0.200 0.200 0.200 0.200 За несколько итераций столбцы матрицы Pi практически сравнялись между собой, а в пределе они все устремятся к стационарному распределению x̄. Глядя на степени матрицы P видно, что уже через несколько шагов выбор начального условия совершенно перестает влиять на значение распределения вероятностей: ведь умножая матрицу Pi , i > 5, на произвольный (стохастический) вектор x(0) мы фактически будем складывать одинаковые столбцы с коэффициентами, суммирующимися в 1! Говорят, что марковская цепь «забывает» свои начальные условия. Независимо от того, каково было начальное состояние, через несколько шагов вероятность нахождения в каждом из возможных состояний станет вполне определенной, постоянной величиной. Стоит немного задержаться на понятии стационарного распределения. Отчего оно называется стационарным? Дело в том, что если мы возьмем это распределение в качестве начального, то ничего меняться не будет, то есть будет выполняться условие стационарности: x̄ = Px̄. 3 Например (эмпирическая) вероятность p AD определяется как отношение числа наблюдаемых последовательностей двух состояний DA к общему числу бинарных последовательностей. Очевидно, что если мы наблюдали рынок в течении 1000 дней, то число всех последовательностей будет равно 999. 84 Алгебра – II Д.В. Громов Рис. 3.2: Граф ссылок между Web-страницами. Из этого уравнения нетрудно заметить, что стационарное распределение – это правый собственный вектор, соответствующий единичному собственному значению матрицы P. Само определение стационарного распределения достаточно очевидно, удивительным является то, что при многократном возведении в степень наша стохастическая матрица превращается в матрицу, составленную только из стационарных распределений x̄. Всегда ли это верно? Оказывается нет, но анализ исключений из правил – это достаточно сложная процедура, связанная с разбиением матрицы P на блочную верхнюю треугольную матрицу с 3 блоками и их анализу. Вместо этого, мы рассмотрим один конкретный пример, который используем для введения основных понятий теории марковских цепей. Упражнение 3.1.1. В качестве небольшого упражнения расмотрите матрицу перехода вида a 1−b P= , 1−a b где a и b – две константы, принадлежащие интервалу [0, 1]. Варьируя значения a и b, в том числе полагая их равными граничным значениям, можно получить широкий спектр вариантов поведения марковской цепи, не ограничивающихся тем, что мы видели в примере 3.1.1. Попробуйте классифицировать возможные сценарии развития событий и объяснить для себя, почему они возникают. Перед тем, как мы вернмся к теоретической части, рассмотрим еще один, очень популярный пример: Google PageRank. Пример 3.1.2. Предположим, что у нас есть несколько Web-страниц, которые ссылаются друг на друга, как показано на рис. 3.2. На рисунке изображен ориентированный граф, вершины которого соответствуют Web-страницам, а дуги – ссылкам. Для того, чтобы определить вес страниц, мы предположили, что каждая страница Pi обладает некоторым априорным весом xi . Если страница Pi ссылается на страницу Pj , то она 85 Алгебра – II Д.В. Громов передает ей часть своего веса, доля которого обратно пропорциональна числу исходящих ссылок. Следуя этой логике мы можем компактно записать ления весов страниц:  0 1/4 0 1/3 1/4 1/2  1/3 1/2 0 0 1/2  Qx =  1/3 1/2 0 0  0 1 1/4   0 0 1/4 0 0 0 систему уравнений Qx = x для опреде0     x1 x1 x2  x2  0         1  x3  x3      0  x4  = x4      0 x5   x5  x6     x6 x7 x7 (3.4) Для примера рассмотрим вторую строку: 1 1 1 x2 + x4 + x5 = x1 , 3 4 2 т. е. вес 2-й страницы формируется как взвешенная сумма весов страниц, ссылающихся на нее. Это первая, четвертая и пятая страницы (см. рис. 3.2). А веса определяются как величины, обратные к числу исходящих дуг для соответствующей страницы. Подумайте, будет ли система (3.5) иметь нетривиальное решение? Если да, охарактеризуйте его, если нет, объясните почему. Однако мы не будем останавливаться собственно на уравнениях PageRank. а посмотрим вопрос с другой стороны. Матрица Q практически стохастическая по столбцам. Это значит, что мы можем рассматривать граф на рис. 3.2 как марковскую цепь. А именно, мы будем интерпретировать вершины как состояния цепи, а веса дуг – как вероятности переходов. Однако у нас есть шестой столбец, который выпадает из правила. Дело в том, что у шестой вершины нет ни одной исходящей дуги и поэтому вероятности переходов из состояния P6 не могут быть определены. Для того, чтобы избавиться от этой проблемы, мы добавим к каждому состоянию петлю, т. е. дугу, начальная и конечная вершина которой совпадают. Новый граф изображен на рис. 3.3. Модифицируем матрицу переходов  1/4 1/4  1/4  Q̄ =  1/4  0   0 для нового графа:  0 1/5 0 0 0 1/3 0 1/5 1/3 0 0   1/3 1/2 0 1/3 0 1/2  1/3 0 1/5 0 0 0   0 1/2 1/5 1/3 0 0   0 1/5 0 1 0  0 0 1/2 (3.5) Мы могли бы рассмотреть уравенение x(i + 1) = Qx(i) и исследовать его стационарные решения, но сейчас мы попробуем подойти к вопросу мене формально. Давайте посмотрим на рис. 3.3. Можно заметить, что некоторые вершины в этом графе отличаются от других. Тогда как вершины P1 − P5 достаточно плотно связаны между собой, вершина P6 не имеет исходящих дуг, а вершина P7 – входящих дуг. Это значит, что если мы попадаем в состояние P6 , то уже не можем покинуть его и наоборот, если мы выходим из состояния 86 Алгебра – II Д.В. Громов Рис. 3.3: Граф ссылок между Web-страницами. P7 , то уже никогда туда не вернемся. В теории марковских цепей для таких состояний есть специальные имена: P1 − P5 : возвратные (или рекуррентные) состояния. P6 : поглощающее состояние. P7 : невозвратное (или транзитивное) состояние. Не надо возводить матрицу Q̄ в степени для того, чтобы понять, что с ходом времени распределение вероятностей x(i) будет стремиться к стационарному распределению вида x̄ = [0, 0, 0, 0, 0, 1, 0]> , т. е. система будет находиться в состоянии P6 с вероятностью, асимптотически стремящейся к 1. Однако случится это совсем не скоро. Нам придется сделать примерно 500 шагов для того, чтобы величины xi , i 6= 0 стали достаточно малы. 87 Алгебра – II 3.2 3.2.1 Д.В. Громов Разложения прямоугольных матриц QR-разложение Перед тем, как мы перейдем к теме этого раздела, необходимо познакомиться с так называемым QR-разложением. Мы помним, что решение системы алгебраических уравнений вида Ax = b может быть эффективно осуществлено с помощью LU разложения, в котором матрица A представляется в виде произведения нижней диагональной и верхней диагональной матриц, обозначаемых L и U, соответственно. Тогда система линейных уравнений записывается как LUx = b и решается в два прогона. Альтернативно, мы можем представить матрицу A в другом виде. Пусть A – прямоугольная матрица размерности [m × n], m ≥ n, такая, что rank(A) = n. Это значит, что столбцы матрицы A линейно независимы. Оказывается. что матрицу A можно представить в виде произведения ортогональной матрицы размерности [m × n] и невырожденной верхней треугольной матрицы размерности [n × n], обозначаемых Q и R: A = QR, где Q> Q = En . Заметим, что для случая m = n матрица Q невырождена и ее обратная совпадает с транспонированной матрицей: Q−1 = Q> . Очевидно, что такое представление матрицы A также может упростить решение системы линейных уравенений. Пусть m = n. Тогда, умножая систему уравенний слева и справа на Q> , мы получим новую, эквивалентную систему Rx = Q> b, которую можно решить в один прогон, используя обратную подстановку. Такой подход не приведет к существенному упрощению процесса по сравнением с использованием LU-разложения, но он может быть полезен в других задачах, как мы увидим немного позже. Остановимся коротко на алгоритме получения QR-разложения. Это процесс основан на уже известной нам процедуре ортогонализации Грама-Шмидта. Запишем матрицу A в виде A = [a1 , . . . , an ], где ai – линейно независимые столбцы матрицы A. Перейдем к системе ортонормированных векторов qi , используя процедуру Грама-Шмидта: a1 , ka1 k a2 − ha2 , q1 iq1 , q2 = ka2 − ha2 , q1 iq1 k .. . q1 = qn = an − han , q1 iq1 − · · · − han , qn−1 iqn−1 . kan − han , q1 iq1 − · · · − han , qn−1 iqn−1 k Введем обозначение νi = kai − hai , q1 iq1 − · · · − hai , qi−1 iqi−1 k и выразим векторы ai через qi : a1 = ν1 q1 , a2 = ν2 q2 + ha2 , q1 iq1 , .. . (3.6) an = νn qn + han , q1 iq1 + · · · + han , qn−1 iqn−1 . Записывая уравнения (3.6) в векторно-матричном виде мы получим требуемое разложе- 88 Алгебра – II Д.В. Громов ние: A = a1 ... an = q1 ...  ν1  0 qn  .  .. 3.2.2 ha2 , q1 i . . . ν2 .. .. . . ...  han , q1 i han , q2 i   = QR. ..  . νn Сингулярное разложение Мы увидели, что домножая матрицу A на некоторую ортогональную матрицу Q> мы можем получить верхнюю треугольную матрицу. А можно ли упростить матрицу A еще больше, если домножить ее слева и справа на ортогональные матрицы? Оказывается, да, но в отличие от случая симметрических матриц эти ортогональные матрицы будут различными и – в случае прямоугольной матрицы A – будут иметь разные размерности. Теорема 3.2.1. Пусть дана матрица A ∈ Rm×n . Существуют такие ортогональные матрицы U ∈ Rm×m и V ∈ Rn×n , а также матрица Σ вида    σ1    σ2      [p×(n−p)]   . ..   ,  Σ=    0 σp   0[(m−p)×p] 0[(m−p)×(n−p)] где σ1 ≥ σ2 ≥ · · · ≥ σp > 0 и p = rank(A) ≤ min{m, n}, такие, что U> AV = Σ. Числа σi называются сингулярными числами матрицы A и определены однозначно. Доказательство. Предположим, что m ≥ n. В противном случае мы транспонируем матрицу A и будем работать с транспонированной матрицей, а после преобразований транспонируем результат еще раз. Рассмотрим матрицу M = A> A. Ранг матрицы A> A равен рангу матрицы A. Кроме того, все собственные числа матрицы A> A неотрицательны. Докажите эти утверждения. Это значит, что матрица A> A имеет ровно p неотрицательных и (n − p) нулевых собственных чисел. Запишем ненулевые собственные числа в виде последовательности квадратов некоторых неотрицательных величин: σ12 ≥ σ12 ≥ · · · ≥ σp2 . Поскольку матрица A> A симметрическая, мы можем определить ортонормированный набор собственных векторов v1 , . . . , vn , соответствующих собственным числам σ12 , . . . , σp2 , 0, . . . , 0. Обозначим через V матрицу, столбцами которой являются векторы v1 , . . . , vn . Рассмотрим набор векторов ui = σ1i Avi ∈ Rm , i = 1, . . . , p. Это ортонормированный набор, как следует из ( σj2 > 1, i = j, 1 > > > ui uj = vi A Avj = vi vj = σi σj σi σj 0, i 6= j. Дополним набор u1 , . . . , up (m−p) векторами до ортонормированного базиса Rm и составим из получившихся векторов u1 , . . . , um матрицу U. Очевидно, что это будет ортогональная матрица. Теперь мы можем проверить, что выполняется ( σj2 > σi , i = j ≤ p, 1 > > > ui Avj = vi A Avj = v vj = (3.7) σi σi i 0, в противном случае. 89 Алгебра – II Д.В. Громов Из (3.7) следует, что U> AV = Σ. Последнее утверждение теоремы следует из того, что сингулярные числа находятся как квадратные корни собственных чисел матрицы B = A> A и определяются однозначно для любой матрицы A. Выражение A = UΣV> называется сингулярным разложением (англ., singular value decomposition, SVD), а векторы u и v – левыми и правыми сингулярными векторами матрицы A. Из представления A = UΣV> непосредственно вытекает следующий результат. Следствие 3.2.2. Матрица A ∈ Rm×n такая, что rank(A) = p, может быть представлена в виде p X A= σi ui vi> . (3.8) i=1 Сингулярные числа матрицы A содержат много информации о свойствах матрицы A и могут быть полезны даже для квадратных матриц A4 . Один пример приведен ниже, в лемме 3.2.3. Кроме того, можно упомянуть, что число обусловленности матрицы A, κ(A), определяется как отношение максимального сингулярного числа матрицы A к минимальному. Число обусловленности очень важно в численной математике, т. к. оно показывает, насколько изменится решение СЛАУ вида Ax = b при малой вариации вектора свободных членов b → b + ∆b. Чем больше κ(A), тем более чувствительна система Ax = b к вариации b. Лемма 3.2.3. Если A ∈ Rm×n , то kAk2 = kAT k2 = σ1 , где σ1 – наибольшее сингулярное число матрицы A. Однако вернемся к следствию 3.2.2, а точнее к выражению (3.8). Попробуем аппроксимировать матрицу A урезанной суммой Ãk = k X σi ui vi> , (3.9) i=1 где k < p. Матрица Ãk будет иметь ранг, равный k. Используя результат леммы 3.2.3 мы можем заключить, что kA − Ãk k2 = σk−1 , т.е. спектральная норма разности A − Ãk равна максимальному «откинутому» сингулярному числу. Однако это еще не все. Самый главный результат о Ãk мы сформулируем в виде теоремы. Теорема 3.2.4. Пусть A ∈ Rm×n и матрица Ãk определена согласно (3.9). Тогда неравенство kA − Ãk k2 ≤ kA − Bk2 выполняется для любой матрицы B ∈ Rm×n такой, что rank(B) = k. Иначе говоря, матрица Ãk является наилучшей в смысле спектральной нормы аппроксимацией матрицы A среди всех матриц ранга k. 4 Имется в виду, что у квадратной матрицы можно определить собственные значения, которые очень много сообщают о свойствах матрицы. Для прямоугольных матриц собственных значений нет, поэтому сингулярные числа – это тот единственный источник информации, с которым мы можем работать. 90 Алгебра – II (a) Исходное изображение Д.В. Громов (b) k = 50 (c) k = 30 Рис. 3.4: Огюст Ренуар «Портрет Жанны Самари» Пример 3.2.1. Классический иллюстративный пример использования спектрального раздожения демонстрирует, как SVD помогает компактно хранить изображения с минимальной потерей качества. Предположим, что у нас есть изображение в градациях серого. Это изображение можно представить как массив точек J размерности [m × n], в котором каждый элемент содержит число в интервале от 0 до 255, соответствующее интенсивности соответствующего пиксела5 . Если использовать сингулярное разложение и предположить, что ранг J равен min{m, n} = n, то для однозначного восстановления матрицы J нам потребуется n векторов ui ∈ Rm , n векторов vi ∈ Rn и n сингулярных значений σi ∈ R+ : всего (m + n + 1)n значений. Это больше, чем число элементов в матрице J. Однако мы можем заметить, что сингулярные значения очень сильно различаются между собой. Поэтому имеет смысл оставить лишь k самых старших сингулярных значений и отбросить все остальные. Тогда нам придется хранить всего (m + n + 1)k значений. Если k << n, то выигрыш может быть достаточно существенным. Возьмем для примера известную картину Огюста Ренуара, изображенную на рис. 3.4. Для удобства мы убрали информацию о цвете пикселов и оставили только интенсивность. Эта картина имеет размер [700×532], т.е. для ее хранения нам потребуется 372400 байт. Оставим только k = 50 первых сингулярных значений. Тогда для хранения этого изображения нам потребуется всего (700 + 532 + 1)50 = 61650 байт, т.е. примерно в 6 раз меньше. На рис. 3.4 приведены три версии картины: оригинальное изображение, изображения, полученное с использованием k = 50 и k = 30 сингулярных точек. Разница между ними видна только при достаточно сильном увеличении6 . 5 Или яркости. Специалисты, поправьте меня, если я ошибаюсь. отметить, что отличие будет более заметно, если мы будем рассматривать изображения в оригинальном разрешении. При встраивании изображений в текст осуществляется масштабирование, которое несколько скрадывает изьяны. 6 Надо 91 Алгебра – II 3.3 Матричные группы 3.4 Приложения Д.В. Громов 3.4.1 Pseudo-inverse and least squares 3.4.2 Haar wavelet/Haar basis 3.4.3 Bernstein polynomials and spline interpolation 92 Литература [1] Е. А. Калинина, А. Ю. Утешев Дополнительная литература [4] Scharnhorst, K. Angles in Complex Vector Spaces. Acta Applicandae Mathematicae 69, 95– 103, 2001. Online: arxiv.org/abs/math/9904077 [5] Johnson, C. R., and S. Furtado. A generalization of Sylvester’s law of inertia. Linear Algebra and its Applications 338:1-3, 287–290, 2001. [6] Gilbert G. T. Positive Definite Matrices and Sylvester’s Criterion. American Mathematical Monthly, 98:1, 44–46, 1991. 93