Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 281
Текст из файла (страница 281)
Обычно размер единичного вектора ясен из контекста. Иулееая матрица (лего шапзх) — это матрица, все элементы которой равны нулю. Такая матрица часто записывается просто как О, поскольку неоднозначность между числом 0 и нулевой матрицей легко разрешается с помощью контекста. Если размер нулевой матрицы не указан, то он также выводится из контекста.
Квадратные матрицы Часто приходится иметь дело с квадратными (а<риге) матрицами размером и х и. Некоторые из квадратных матриц представляют особый интерес. 1. Диагональная матрица (б)адопа! шапзх) обладает тем свойством, что сч. = 0 при 1 ~ з1 Поскольку все недиагональные элементы такой матрицы равны нулю, диагональную матрицу можно определить путем перечисления ее элементов вдоль диагонали: аг1 0 ... 0 0 азз... 0 Йай(аы,азз,...,аоо) = 0 0 ...са 2.
Единичная матрица (к$епбгу шагпх) 1„размером и х и представляет собой диагональную матрицу, все диагональные элементы которой равны единице: 1„= йаб(1, 1,...,1) 10...0 01...0 1271 Принижение Г. Матрицы Если используется обозначение 1 без индекса, размер единичной матрицы определяется из контекста. Заметим, что 1-м столбцом единичной матрицы является единичный вектор е,. 3.
Элементы трехдиогоиольиой матрицы (Пийайопа! ша1пх) Т обладают тем свойством, что если !1 — Я ) 1, то 10 — — О. ненулевые элементы такой матрицы располагаются на главной диагонали, непосредственно над ней (21,1+1 для ! = 1, 2,..., и — 1) и непосредственно под ней (11+1; для 1 = 1, 2,..., и — 1): гп 812 0 О ... 0 0 0 !21 !22 823 0 ... О 0 0 0 гзз гзз гз4 . 0 0 0 0 0 0 0 ...Гп — 2,п — ззп — 2,п — 1 0 0 0 0 0 .
° Фп-1,п-з Сп-1,п-1 Сп-1,п 0 О О О ... 0 Фп„1 Гпп 4. Верхиетреугольиой мширицей (пррег-Пзапйц)аг ша1пх) У называется матрица, все элементы которой ниже диагонали равны нулю (иг = 0 прн 1 ) 1): иы иы ... ига О п22 ... п2п У= 0 0 ... опп Верхнетреугольная матрица является единичной верхнетреугольиой матрицей (опй пррег-нзалйо)аг), если все ее диагональные элементы равны единице. 5. Нижиетроугольиой могирицей ()озчег-Пзапйо!аг шанзх) Ь называется матрица, все элементы которой выше диагонали равны нулю (!11 = 0 при 1 < 2): !пО...О !21 !22 ...
0 Ь= (п1 !п2 !пп Нижнетреугольная матрица является единичной иижиетреугольиой мигирицей (цшг )оъ ег-пзалйо!аг), если все ее диагональные элементы равны единице. б, Матрица иересгиинооии (репппгайоп пза1пх) Р имеет в кзждой строке и столбце ровно по одной единице, а на всех прочих местах располагаются !с72 Часть еШ. Приеоскеииеь моьисиотические основы нули. Примером матрицы перестановки может слуясить матрица 01000 00010 Р= 10000 00001 00100 Такая матрица называется матрицей перестановки, потому что умножение векторахх на матрицу перестановки приводит к перестановке элементов вектора, В упр.
Г.!А рассматриваются дополнительные свойства матриц перестановок. 7. Симметричная матрица (яупппепзс шаптх) А удовлетворяет условию А = Ат. Например, матрица (26ч) является симметричной. Основные матричные операции Элементами матриц и векторов служат элементы некоторой числовой системы, такие как действительные числа, комплексные числа илн, например, целые числа по модулю простого числа. Числовая система определяет, каким образом должны складываться и перемножаться числа. Эти определения можно распространить и на матрицы. Мы определяем сложение матриц (шантх асЫ11юп) следующим образом. Если А = (о; ) и В = (бч ) — матрицы размером т х п, то нх суммой является матрица С = (с;ч) = А + В размером т х п, определяемая соотношениями с;Ч вЂ” — об+ бб 1 = 1, 2,..., гп и 7' = 1, 2,..., п.
Другими словами, сложение матриц выполняется позлементно. Нулевая матрица является единичным элементом по отношению к сложению матриц: А+ 0 = А = О+ А Если Л вЂ” число, а А = (а, ) — матрица, то соотношение ЛА = (Лоб) определяет скалярное нранзведение (зса1аг пш1йр!е) матрицы на число, которое также выполняется поэлементно. Частным случаем скалярного произведения является умножение на — 1, которое дает противоположную (пейайче) матрицу — 1 А = — А, обладающую тем свойством, что (ч-й элемент — А равен — а; . Таким образом, А + ( — А) = 0 = ( — А) + А . Понятие противоположной матрицы используется при определении вычитания матриц (шаптх зп(ягас11оп): А — В = А + ( — В).
!273 Приложение П Матрицы Матричное умноженне (шаитх пщйбр!кайоп) определяется следующим образом. Матрицы А и В могут быль перемножены, если они соамеснлнмы (сотрайЫе) в том смысле, что число столбцов А равно числу строк В (в общем случае выражение, содержащее матричное произведение АВ, всегда подразумевает совместимость матриц А и В).
Если А = (о; ) — матрица размером т х и, а В = (6; ) — матрица размером и х р, то их произведение С = АВ представляет собой матрицу С = (с, ) размером т х р, элементы которой определяются уравнением с," = ~ а,.ьбь а=1 (Г.2) 1 А=А1„=А для любой матрицы А размером т х и. Умножение на нулевую матрицу дает нулевую матрицу: АО=О. Умножение матриц ассоциативно: А(ВС) = (АВ)С для любых совместимых матриц А, В и С.
Умножение матриц дистрибутивно относительно сложения; А(В+С) = АЗ+ АС, (В + С)Р = ВР+ СР . Для и > 1 умножение матриц размером п х п не коммутативно. Например, если А (о1) и В (оо), то АВ=( ) ВА=( ) . Произведения матрицы и вектора или двух векторов вычисляются путем представления вектора как матрицы размером п х 1 (или 1 хи в случае вектора-строки). для г = 1,2,..., т и 2 = 1, 2,...,р, Процедура БОЦлкн-МАтк!Х-М[л.т1Р1.у из раздела 4.2 реализует матричное умножение квадратных матриц непосредственно по формуле (Г2).
Для умножения матриц размером и х и процедура Б017АКВМлтк1х-М1лтпчу выполняет и умножений и пз(п — 1) сложений, так что время ее работы равно тз(пз). Матрицы обладают многими (но не всеми) алгебраическими свойствами, присущими обычным числам. Единичная матрица является единичным элементом по отношению к умножению: 1274 Часть ггП. Приеонеение: матеыатичеение основы Таким образом, если А — матрица размером т х и, а х — вектор размером и, то Ах является вектором размером т.
Если х и у — векторы размером и, то произведение Т %'ч х У = ~ хеУ1 1=1 представляет собой число (в действительности — матрицу размером 1 х 1), называемое скалярным лроизаеделием (1ппег ргое(нег) векторов х и у. Матрица .'о = хут размером и х п с элементами 21 = х,у называется тензорным произведением (ошег ргос$псг) этих же векторов. (Евклидова) норма ((еос11деап) попп) ))х)! вектора х размером и определяется соотношением (,2 + 2 + + х2)172 (хтх)172 Таким образом, норма х — это длина вектора в п-мерном евклидовом простран- стве. Упражнении Г.1.1 Покажите, что если А и В являются симметричными матрицами размером п х и, то то же справедливо и в отношении матриц А + В и А — В.
Г.1.2 Докажите, что (АВ)т = ВтАт и что АтА всегда является симметричной матрицей. Г.1.3 Докажите, что произведение двух нижнетреугольных матриц является нижнетре- угольной матрицей. Г.1.4 Докажите, что если Р представляет собой матрицу перестановки размером и х п, а А является матрицей размером и х п, то матричное произведение РА представляет собой матрицу А с перестааленными строками, а матричное произведение АР представляет собой матрицу А с переставленными строками. Докажите, что произведение двух матриц перестановки является матрицей перестановки. Г.2.
Осцоввыс свойства матриц В этом разделе будут определены некоторые основные свойства матриц: обратимость, линейная зависимость и независимость, ранги и детерминанты. Мы также изучим класс положительно определенных матриц. Приложение П Матрицы !775 Обратные матрицы, ранги и детерминанты Матрицей, обратной ((пчегзе) к данной матрице А размером и х и, является матрица размером и х и, обозначаемая как А г (если таковая существует), такая, что АА л = 1„= А ~ А, например 10 1 — 1 Многие ненулевые квадратные матрицы размером и х и не имеют обратных матриц. Матрица, для которой не существует обратная матрица, называется необращаемой (попшчег6Ые) или вмрожденной (з(пйп!аг). Вот пример ненулевой вырожденной матрицы: (1о) Если матрица имеет обратную матрицу, она называется обращаемой (шчеп(Ые) или невмрожденной (попа(пйп)аг).
Если обратная матрица существует, то она единственная (см. упр. Г.2.1). Если А и  — невырожденные матрицы размером и х и, то (ВА) ' = А 'В ' Операция обращения коммутативна с операцией транспонирования: (А-г)т (,4т)-1 Векторы хы хз,..., х„линейно зависимы (1шеаг1у йерепбепг), если существуют коэффициенты сы сз,..., с, среди которых не все нулевые, такие, что елхл + сзхз+ + с„х„= О. Например, векторы-строки хл = ( 1 2 3 ), хз = ( 2 64 ) и хз = ( 4 П 9 ) линейно зависимы, поскольку 2хг + Зхз — 2хз = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
