Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 282
Текст из файла (страница 282)
Если векторы не являются линейно зависимыми, они называются лнненно незавнснмымн (1шеаг!у (пберепбепг). Например, столбцы единичной матрицы линейно независимы. Столбцовым рангам (со!штш гапк) ненулевой матрицы А размером т х и называется размер наибольшего множества линейно независимых столбцов А. Аналогично строчным рангам (толч гап)с) ненулевой матрицы А размером т х и называется размер наибольшего множества линейно независимых строк А. Фундаментальным свойством любой матрицы А является равенство ее строчного и столбцового рангов, так что мы можем говорить просто о ранге (шпк) матрицы.
Ранг матрицы размером т х и представляет собой целое число от нуля до ш)п(т, и) включительно (ранг нулевой матрицы равен нулю, ранг единичной матрицы размером и х и равен и). Другое эквивалентное (и зачастую более полезное) определение ранга ненулевой матрицы А размером т х и — это наименьшее число т, такое, что существуют матрицы В и С размером соответственно ги х г и т х и, такие, что А =ВС. !276 Часть !777!. Припожении математические основы Квадратная матрица размером и х и имеет полный ранг (бзП гапк), если ее ранг равен и. Матрица размером т х и имеет ноиный столбцовый ранг (й1! со1шпп гапк), если ее ранг равен и.
Фундаментальное свойство рангов приведено в следующей теореме. Теорема Г. ! Квадратная матрица имеет полный ранг тогда и толью тогда, коща она является невырожденной. Ненулевой вектор х, такой, что Ах = О, называется аннулирующим веитораи (пц11 чес1ог) матрицы А. Приведенная далее теорема (доказательство которой оставлено в качестве упр. Г.2.7) и ее следствие связывают столбцовый ранг и вырожденность с аннулирующим вектором. Теорема Г.2 Матрица А имеет полный столбцовый ранг тогда и только тогда, когда для нее не существует аннулирующего вектора. Следствие ГЗ Квадратная матрица А является вырожденной тогда и только тогда, когда она имеет аннулирующий вектор. у'-минором матрицы А размером и х и (и > 1) называется матрица А1в1 размером (п — 1) х (и — 1), получаемая из А удалением в'-й строки и 7-го столбца.
Опредеаитель, или детерминант (бе1епп(пап!), матрицы А размером и х п можно определить рекурсивно с помощью миноров следующим образом: если и = 1 аы с1е1(А) = ( — 1)'+)а!! с)ес(А1!11), если и > 1 . Множитель ( — 1)иь! с1еь(А1!71) называется алгебраическим дополнением (со!асгог) элемента а; . В приведенных ниже теоремах, доказательство которых здесь опущено, описываются фундаментальные свойства определителей. Теорема Г4 (Свойства определителя) Определитель квадратной матрицы А обладает следующими свойствами. Если любая строка или любой столбец А нулевой, то бе1(А) = О. Если все элементы одного произвольного столбца (или строки) матрицы умножаются на Л, то ее определитель также умножается на Л.
Определитель матрицы А остается неизменным„если все элементы одной строки (или столбца) прибавить к элементам другой строки (столбца). Приложение Г. Матрицы !277 ° Определитель матрицы А равен определителю транспонированной матрицы 4т Определитель матрицы А умножается на — 1, если обменять местами любые два ее столбца (или строки). Кроме того, для любых квадратных матриц А и В справедливо соотношение с(ес(АВ) = с(ес(А) с)ес(В).
Теорема Г.5 Матрица А размером п х и выролсдена тогда и только тогда, когда с1ег(А) = О. ° Положительно определенные матрицы Во многих приложениях важную роль играют положительно определенные матрицы. Матрица А размером п х п является положительно определенной (роз(6це-бебшйе), если х "Ах > О для любого ненулевого вектора х размером п. Например, единичная матрица положительно определенная, поскольку для произвольного ненулевого векторах = ( х1 хз .х„ )т х 1„х=х х т т п з с=1 > О. Матрицы, возникающие в различных приложениях, зачастую оказываются положительно определенными в силу следующей теоремы. Теорема Г.б Для произвольной матрицы А с полным столбцовым рангом матрица АтА поло- жительно определена. хт(АтА)х = (Ах)т(Ах) = ()Ах8~ .
(согласно упр. Г.1.2) Заметим, что 8Ах)( представляет собой просто сумму квадратов элементов вектора Ах. Таким образом, ()Ах(! > О. Если )(Ах8 = О, все элементы вектора Ах равны нулю, т.е. Ах = О. Поскольку матрица А имеет полный столбцовый ранг, из Ах = О согласно теореме Г.2 следует, что х = О. Следовательно, матрица АтА положительно определенная. Другие свойства положительно определенных матриц рассматриваются в разделе 28.3.
Доказательство. Необходимо показать, что хт(АтА)х > О для любого ненулевого вектора х. Для произвольного вектора х 127а части ггд. Прилоакения: математические основы Упражнении Г21 Докажите единственность обратной матрицы, т.е. что если В и С обратны к А, то В = С. Г.2.2 Докажите, что определители нижне- и верхнетреугольной матриц равны произведению их диагональных элементов.
Докажите, что матрица, обратная к ннжнетреугольной матрице (если таковая существует), также является нижнегреугольной. Г2.3 Докажите, что если Р является матрицей перестановок, то матрица Р обратима, обратной к ней является матрица Рт и Р г представляет собой матрицу перестановок. Г2.4 Пусть А и  — матрицы размером п х и, такие, что АВ = Х. Докажите, что если А' получена из А путем прибавления к строке ( строки 5, то обратную к А' матрицу В' можно получить, вычтя в матрице В столбец ( из столбца 7'.
Г.2,5 Пусть А — невырожденная матрица размером и х п с юмплексными элементами. Покажите, что все элементы матрицы А ' вещественны тогда и толью тогда, когда вещественны все элементы матрицы А. Г2.6 Покажите, что если А — невырожденная симметричная матрица размером и х и, то матрица А ' симметрична. Покажите, что если  — произвольная матрица размером тл х п, то матрица размером ти х гл, полученная в результате умножения ВАВт, симметрична. Г2. 7 Докажите теорему Г.2, т.е, покажите, что матрица А имеет полный столбцовый ранг тогда и только тогда, когда из Ах = О следует х = О. (Указание: запишите условие линейной зависимости одного столбца от остальных в виде матричновекторного уравнения.) Г.2.3 Докажите, что для любых совместимых матриц А и В гапй(АВ) ( ппп(гапй(А), гап(с(В)), причем равенство достигается, если либо А, либо  — невырожденная квадратная матрица.
(Указание; воспользуйтесь альтернативным определением ранга матрицы.) П79 Приложение Г. матрицы Задачи Г2. Матрица Вандермонда Докажите, что для заданных чисел хо, хы..., х„г определитель матрицы Вандернонда (Чапдеппопде шапзх) 1 хо хо хо 1 х х х" з У(хо,хы...,х„1) = 1 х„ 1 х„ 1 х„ равен г)ес(У(хо,хы...,х„з)) = П (хь — х ) . 0<1<а<в-1 (Указание: умножьте столбец г на — хо и прибавьте к столбцу 1+ 1 для 1 = п — 1, и — 2,..., 1, а затем примените индукцию.) Г2.
Перестановки, определенные матрично-векторным умножением над паяем Се (2) Один из классов перестановок целых чисел из множества Я„= (О, 1,2,..., 2" — 1) определяется матричным умножением над полем Се (2), Для каждого целого числа х из Я„мы рассматриваем его двоичное представление как и-битовый вектор хо х1 хз хв — 1 где х = 2,". о~ х,2'. Если А представляет собой матрицу размером и х н, в которой каждый элемент равен либо нулю, либо единице, то можно определить отображение-перестановку каждого значения х из Я„на число, двоичное представление которого является матрично-векторным произведением Ах. Все арифметические действия при этом выполняются над полем Се (2): все значения равны либо нулю, либо единице, при этом применимы все правила сложения и умножения, за единственным исключением: 1 + 1 = О.
Арифметику над полем СР(2) можно рассматривать как обычную целочисленную арифметику, с тем отличием, что при этом рассматривается только один младший бит. В качестве примера для множества Яз = (О, 1, 2, 3) матрица А=( ) !280 Часть ПП, Прилажениаг математические основы определяет следующую перестановку ггл. 'ггл(О) = О, яд(1) = 3, ггл(2) = 2, хе(3) = 1. Чтобы понять, почему гге(3) = 1, заметим, что (при работе в СТ(2)) (3) 1 О =Ю что представляет собой двоичное представление единицы.
В оставшейся части данной задачи мы работаем над полем Сг (2), и все элементы матриц и векторов являются либо нулем, либо единицей. Определим ранг 0-1-матрицы (матрицы, в которой каждый элемент является либо нулем, либо единицей) над полем СР(2) так же, как и для обычной матрицы, только при этом все арифметические действия, определяющие линейную независимость, выполняются над СГ(2). Определим диапозон (гапке) О-1-матрицы А размером и х и как гс(А) = (у; у = Ах для некоторого х е Я„), так что К(А) представляет собой множество чисел из Я„, которые можно полу- чить умножением каждого значения х нз Я„на А.
а Докажите, что если г — ранг матрицы А, то ~Е(А) ~ = 2'. Заключите отсюда, что А определяет перестановку Я„только тогда, когда А имеет полный ранг. Для заданной матрицы А размером и х и и заданного значения у Е гс(А) определим прообраз (ргеппайе) у как Р(А, у) = (х: Ах = у), так что Р(А, у) представляет собой множество значений из Я„, которые отобра- жаются на у при умножении на А. б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
