Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 170
Текст из файла (страница 170)
Избранные темы 4. Верхне-треугольной матрицей (иррег-птапйи!аг шаптх) У называется матрица, у которой все элементы ниже диагонали равны О (и,з = О при 1 ) 7): игг игг ... иг„ О игг .. игп О О ... и„„ Верхне-треугольная матрица является единичной верхне-треугольной матрицей (шп! иррег-!палйп!аг), если все ее диагональные элементы равны 1. 5. Нижне-треугольной матрицей (1о~чег-!палйп!аг шаизх) Ь называется матрица, у которой все элементы выше диагонали равны О (1; = О при г ( 1): 1и О ...
О 1гг 1гг . О Ь= (чг 1чг Нижне-треугольная матрица является единичной нижне-треугольной матрицей (оп!1!очгег-1г!апйп1аг), если все ее диагональные элементы равны 1. 6. Матрица нерестановки (реппигайоп шаптх) Р имеет в каждой строке и столбце ровно по одной единице, а на всех прочих местах располагаются нули. Примером матрицы перестановки может служить матрица О 1 О О О О О О 1 О 1 О О О О Р= О О О О 1 О О 1 О О Такая матрица называется матрицей перестановки, потому что умножение вектора х на матрицу перестановки приводит к перестановке элементов вектора.
7. Симметричная матрица (зупппептс шаптх) А удовлетворяет условию А = = Ат. Например, матрица 1 2 3 2 б 4 3 4 б является симметричной. Глава 28. Работа с матрицами 827 Операции над матрицами А+О=А=О+А. Если Л вЂ” число, а А = (аи) — матрица, то соотношение ЛА = (Ла; ) определяет скалярное произведение (зса1аг пш!бр1е) матрицы на число, которое также выполняется поэлементно.
Частным случаем скалярного произведения является умножение на — 1, которое дает противоположную (пейабче) матр1щу — 1 А = = -А, обладающую тем свойством, что А + ( — А) = О = ( — А) + А. Соответственно, можно определить вычитание матриц (шап1х зпЬ~гаспоп) как сложение с противоположной матрицей: А — В = А + ( — В). Матричное умножение (шаптх пш1пр!1сапоп) определяется следующим образом. Матрицы А и В могут быть перемножены, если они совместимы (сошрапЫе) в том смысле, что число столбцов А равно числу строк В (в общем случае выражение, содержащее матричное произведение АВ, всегда подразумевает совместимость матриц А и В).
Если А = (а; ) — матрица размером т х п, а В = (6; ) — матрица размером и х р, то их произведение С = АВ представляет собой матрицу С = (с; ) размером т х р, элементы которой определяются уравнением с;ь = ~~> а;.6 ь 1=1 (28.3) для ( = 1,2,...,гп и к = 1,2,...,р. Процедура Млтщх Мя.тп'и' из раздела 25.1 реализует матричное умножение квадратных матриц (т = и = р) непосредственно по формуле (28.3). Для умножения матриц размером и х и процедура Млтих Мщ.тички выполняет пз умножений и пз (и — 1) сложений, так что время ее работы равно 9 (пз).
Матрицы обладают многими (но не всеми) алгебраическими свойствами, присущими обычным числам. Единичная матрица является нейтральным элементом Элементами матриц и векторов служат элементы некоторой числовой системы, такие как действительные числа, комплексные числа или, например, целые числа по модулю простого числа. Числовая система определяет, каким образом должны складываться и перемножаться числа. Эти определения можно распространить н на матрицы.
Определим сложение матриц (шап1х айЫоп) следующим образом. Если А = (а; ) и В = (6; ) — матрицы размером т х и, то их суммой является матрица С = (с;.) = А+ В размером т х и, определяемая соотношением су = а, + 6; для г = 1, 2,..., т и у = 1, 2,..., и. Другими словами, сложение матриц выполняется поэлементно.
Нулевая матрица нейтральна по отношению к сложению матриц: Часть ЧП. Избранные темы 828 по отношению к умножению: 1,„А = А1„= А для любой матрицы А размером гп х гг. Умножение на нулевую матрицу дает нулевую матрицу: АО=ОА=О. Умножение матриц ассоциативно: А(ВС) = (АВ)С (28А) для любых совместимых матриц А, В и С. Умножение матриц дистрибутивно относительно сложения: А(В+С) = АВ+АС, (В + С) О = В12 + СВ. (28.5) Для и ) 1 умножение матриц размером и х и не коммутативно.
Например, если А = (о оо~) и В (о оо), то АВ = (ог оо), но ВА = (оо о) Произведения матрицы и вектора иди двух векторов вычисляются путем представления вектора как матрицы размером и х 1 (нли 1 х гг в случае вектора-строки). Таким образом, если А — матрица размером т х и, а х — вектор размером и, то Ах является вектором размера т.
Если х и у — векторы размера и, то произведение и х у=~~ ту; т.е. норма х — это длина вектора в гг-мерном евклидовом пространстве. Обратные матрицы, ранги и детерминанты Матрицей, о0ратной (1пчегзе) к данной матрице А размером и х п, является матрица размером и х тг, обозначаемая как А ' (если таковая существует), такая что А А г = 1в — — А ' А.
Например, представляет собой число (в действительности — матрицу размером 1 х 1), называющееся скалярным произведением (шпег ргодпсг) векторов х и у. Матрица размером п х п Я = ху с элементами аО = ж;у называется тенэорным лроизведением (ошег ргодпсг) этих же векторов. (Евклидова) норма ((еис11деап) попп) ~~х8 вектора к размером и определяется соотношением Глава 28. Работа с матрицами 829 Многие ненулевые квадратные матрицы не имеют обратных матриц. Матрица, для которой не существует обратная матрица, называется необращаемой (поп1пчеи!Ые), или вырожденной (з1пйп!аг). Вот пример ненулевой вырожденной матрицы: (':) Если матрица имеет обратную матрицу, она называется обращаемой (!пчеи1Ые), или невырожденной (попз1пйп!аг). Если обратная матрица существует, то она единственная (см.
упражнение 28.1-3). Если А и  — невырожденные матрицы размером и х и, то (АВ) ' = А 'В '. (28.6) Операция обращения коммутативна с операцией транспонирования: (А-з) = (Ат) ' Векторы хы хз,... х„линейно зависимы (!шеаг!у берепбеп1), если существуют коэффициенты сы сз,..., с„, среди которых есть ненулевые, такие что сзхз + + сзхз+ ° ° + с х„= О. Например, векторы хд = (1 2 3), хз = (2 6 4) и хз = (4 11 9) линейно зависимы, поскольку 2хз + Зхз — 2хз = О. Если векторы не являются линейно зависимыми, они называются линейно независимььни (1!пеаг!у !поерепоеп1).
Например, столбцы единичной матрицы линейно независимы. Столбновым рангом (со1шпп гапк) ненулевой матрицы А размером т х и называется размер наибольшего множества линейно независимых столбцов А. Аналогично, строчным рангом (тою гап1с) ненулевой матрицы А размером т х и называется размер наибольшего множества линейно независимых строк А. Фундаментальным свойством любой матрицы А является равенство ее строчного и столбцового рангов, так что мы можем говорить просто о ранге (гап!с) матрицы. Ранг матрицы размером т х и представляет собой целое число от О до ппп (т, и) включительно (ранг нулевой матрицы равен О, ранг единичной матрицы размером и х и равен и). Другое эквивалентное (и зачастую более полезное) определение ранга ненулевой матрицы А размером т х и — это наименьшее число г такое, что существуют матрицы В и С размером соответственно т х г и т х и такие, что А = ВС.
Квадратная матрица размером и х и имеет полный ранг (йП гапк), если ее ранг равен и. Матрица размером т х и имеет лолный столбцовый ранг (Гп11 со!шпп гав!с), если ее ранг равен и. Фундаментальное свойство рангов приведено в следующей теореме. Часть Ч11. Избранные темы 830 Теорема 28.1. Квадратная матрица имеет полный ранг тогда и только тогда, когда она является невырожденной. И Ненулевой вектор х, такой что Ах = О, называется аннулирующим еектором (пп11 чес1ог) матрицы А.
Приведенная далее теорема (доказательство которой оставлено в качестве упражнения 28.1-9) и ее следствие связывают столбцовый ранг и вырожденность с аннулирующим вектором. Теорема 28.2. Матрица А имеет полный столбцовый ранг тогда и только тогда, когда для нее не существует аннулирующий вектор. Следствие 28.3. Квадратная матрица А является вырожденной тогда и только тогда, когда она имеет аннулирующий вектор. И Минорам (пплог) элемента он (11-минор) матрицы А размером и х и (и > 1) называется матрица А1; 1 размером (и — 1) х (и — 1),получаемая нз А удалением 1-й строки и 7'-го столбца.
Определитель, или детерминант (де1епшпап1) матрицы А размером п х и можно определить рекурсивно при помощи миноров следующим образом: оы при и = 1, де~ (А) = " 1+. ); ( — 1) да131)е~(А1111) прин > 1. 1=1 (28.7) Множитель ( — 1)ь+з деФ (АМ) называется алгебраическим дополнением (со(ас1ог) элемента а;1.
В приведенных ниже теоремах, доказательство которых здесь опущено, описывают фундаментальные свойства определителей. ° Определитель матрицы А умножается на — 1, если обменять местами любые два ее столбца (или строки). Кроме того, для любых квадратных матриц А и В де1 (АВ) = де1 (А) с1еФ (В). И Теорема 28.4 (Свойства определителя). Определитель квадратной матрицы А обладает следующими свойствами. ° Если любая строка или любой столбец А нулевой, то 11е1 (А) = О.
° Если все элементы одного произвольного столбца (или строки) матрицы умножаются на Л, то ее определитель также умножается на Л. ° Определитель матрицы А остается неизменным, если все элементы одной строки (или столбца) прибавить к элементам другой строки (столбца). ° Определитель матрицы А равен определителю транспонированной матрицы 4т Глава 28. Работа с матрицами 831 Теорема 28.5. Квадратная матрица А вырождена тогда и только тогда, когда беФ1А) = О. Ы Положительно определенные матрицы Во многих приложениях важную роль играют положительно определенные матрицы.
Матрица А размером и х и является положительно определенной (роз1сп~е-дейпйе), если хтАх > О для любого ненулевого вектора х размера и. Например, единичная матрица положительно определенная, поскольку для про,т извольного ненулевого вектора х = (х1 хг ...
х„) хт1„х = хгх = ~~> хг > О. Как мы увидим, зачастую встречающиеся в приложениях матрицы положительно определены в силу следующей теоремы. Теорема 28.6. Для произвольной матрицы А с полным столбцовым рангом мат- рица АтА положительно определена. Доказательство. Мы должны показать, что хт 1АтА) х > О для любого ненуле- вого вектора х. Для произвольного вектора х хт (АтА) х = 1Ах) 1Ах) = 8Ах!)г где первое равенство следует из упражнения 28.1-2. Заметим, что 8Ах8 предг ставляет собой просто сумму квадратов элементов вектора Ах. Таким образом, (~Ах8~ > О. Если 8Ах8~ = О, все элементы вектора Ах равны О, те. Ах = = О. Поскольку А — матрица с полным столбцовым рангом, из Ах = О согласно теореме 28.2 следует, что х = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
