Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 32
Текст из файла (страница 32)
Заметам такн;е, что для существоваппл едипвчвоп матрицы требуется, чтосы: а) О ьх-О=хе О для всех вша, где Π— аддптивная едпппца в Я (напомвим, что это условие пе является акспомой поля); б) Я должно пметь двустороннюю мультпплпкатпвную единпцу. Тем не менее можно проверить, что если (Я, э, +)— кольцо плв лоле, тогда все вышеукааэнпые условия выполнены п ( гт, ®, Я) — кольцо. Понятия упорядочения и замыкания матряц над более узкими структурами, тэкпми как упорядоченные поля п т.
п., становятся слишком сложнымв п поэтому обсуждаться не будут. Как уже отмечалось в упражкеипи бЛ, мы можем рассматривать .Ж(л,(Хю Д, ~)) как гг" (и, В). Аналогично мы можем обобщить вычпслепия на другие родствевные алгебраические структуры, однако требуется тщательность, чтобы сформулировать услонкя на то, какую систему попользовать. Например, оа Хз эх Хз путем обычного включеппя Х, <= Х, (А ~= В обозпачает тождествевпое отображение па А, где А ы В) следует, что А ы Я(п, Хз) = А а Л(п, Хз), Пусть теперь дана матрица пэ О и 1.
Спрашивается, оппределена опа па (О, П илк же па (О, 1, 2)г Это веобходимо акать для перехода к построеяшо арифметики. Конечно (как будет показано в $ 3), все это вависнт от того, чтб мы пытаемся вычислять. Апалогпчиые проблемы возвикают с любыми включениями, особенно эг'(и, В), .Х(, Х,), М (., Х), Л(л, Х.) ..гу(л, 'О) в .эу(, К). ' 2.2. Алгоритм Уоршолла. В этом разделе мы опишем быстрый способ вызволения (транзптввпого влв рефлекспвпого) замыкания квадратных матриц пад (Хэ, /~, ~/). Этот способ — один пз внрпаптов метода Уоршолла; представпм его в виде программы. Если М вЂ” матрица размерности я Х и над (Х„ /~, ~/), то ее можно преобразовать в М+ следующим образом: 1ог / (гош 1 (о и до 1ог $ Ьош 1 1о я бо Н 1»ьг апй М„! 1'оеп 1ог й Угош ! Со и до М» -М»ЧМв.
Чтобы вычислить М», мы можем прибавить 1 плп в вачале, или в конце, используя соотпошекие М -(М+7) -М.+У, Пример 2.2. Пусть О 1 1 О О О О О О 1 О О О О О О 0 О О О 1 1 О тогда, используя алгоритм, заменим О ва ! в следующих элементах: (1, 4), (1, 5), (3, 4), (3, 5), (5, 2), (5, 5), (2, 2,), (2, 3), (3, 3). Получим матрицу О 1 1 1 1 о о ! О О О О О О 1 1 1 1 Мы не будет! доказывать, что программа выполняет нужные действвя, однако отметим, что смысл программы состоит в том, что если !ч'! и Мо $, то (1, ))»во' для некоторого р < л, где а — отпошевие, порожденвое М.
Поэтому замеппм 1-ю строку ва дизъювкцию 1-й и /-й строк, чтобы указать, что все, что относится к 1, также отвоситсяик!. Очевидно, что при 1 1 выяолвевие этого шага не дает никакого выигрыша. Основная сложность проверки правильности программы — убедиться в том, что ничего не пропущено.
Читатель сможет доказать это самостоятельно, прочитав гл. 7. Метод Уоршолла дает аначительный выигрыш по сравнению с прямым пспользовавием определения замыкавпя; он может быть еще улучшен, однако это требует использования более сложных структур данных, и поэтому мы ве будем больше этим завиматься. Этот метод можно многими путями приспособить для получевия различных оценок, сязанных с матрицами (отпошенпямв), простейшим из которых является понятие воз «расстояния» между злементамв мнон«ества, свнзапнымв о»ношением о. 1'асстояпне между двумя точками х в у (й(х, у)) равно наименьшему и такому, что и ю й( и р ю х о" (х).
Если М вЂ” матрица, соответствугощая а, то, заменяя циклы следующим образом, получим требуемый результат: Л Мат'-О 1Ьеп 1ог Й 1гонт 1 1о п ао 11М„,ФО апй (М„О ог Ма > Ма + Ма) 1Ьев Ма - Ме+ Ма. Здесь используется арифметика над Е (а не над 7»). Пример 2.3. Прямепенпе описанной выше процедуры к матрице пз предыдущего примера дает О 1 1 2 2 О 3 2 1 1 О 1 3 2 2 О О О О О О 2 1 1 3 У и р а ж н е н и е 6.2.
1. Определение. Говорят, что две (и Хи)-матрицы Х и У над полем Р подобна» над Р, если существует обратимая матрица Р над Р такая, что Х Р 'УР. г" Показать, что отношение, пядуцпруемое подобием на .6'(и, Р), является отношением эквивалентности и что матрица 1 подобна только себе. 2. Показать, что если А, В ю.аг" (и, Р) для некоторого и ю г( и некоторого полн Р, тогда (А + В)г А«,1. Вг (АВ)г В*А« 3. 0 н р еде лен ив. Сгохасгической з«атрицей называется действительная матрица над ((х: О < х ~ 1), «, +) такая, что сумма элементов в каждой строке равна 1. г Показать, что мнон'ество 3 Х 3 стохастпческпх матриц не замкнуто по отношению к слоягенпю, но замкнуто по отношению к у»гноженпю.
Установить, какпе свойства поля (К) при атом попользовалась. 3 3. Матрицы и векторные пространства Результаты 3 2 показывают, как мон но применять матрицы для проверки выполнения отношений между конечнымп множествами соответсгвующнх размеров. Цель 2ОО етого параграфа — показа гь, кзк поп ~льзовзть матрпцгл иад полом (И,, +) (далее просто, И) д;ш зол>, ггобы выполнять некоторые преобразования, в шсгиосги липеиные преобразования в векторном пространство У над И. В замечании из 3 4 гл. 5 было усгановлг оо, что если Тш ш Епй(У) — множество лггггсйгггзх преобгразовггггий У, то ((х, Тх):хшТ)с= УХУ является бинарным отношением пад У.
Ыы ищем результат применения линейного ареобразования на У в ай(п, К), где л = йгш(У). Возможны два обобигения. Первое — рассмотрение произвольных полей, второе — линейные преобразовании между вскторпызш простравствами произвольных размерностей, которые могут бьгть определены аналогичным образом в аг(л, гп, й). Так как ати обобщщшя нам не потребуются, то в дальнейшем рассматривать их не будем. ЗЛ. Матричные представления линейных преобразований.
Операции слонгеиия и умножения матриц в гг'(л, И) неявно были определены в з 2. Если Л ш.гг'(гг, й) имеет элементы Ле и 7 ~ И, определим 7,! ш.я (и, К) как матрацу с злементами ХЛо. Эту операцшо называют узгпожениега лгатрггг7ьг на слаляр. Поскольку Х(п, й) играет цептральиуго роль в оставшейся части атой главьг, то полезно перечислить все его свойства относительно определенны.г выше операций. Единичную ьгатрггггу в Ж(л, Й) будем обозначать через 1 прп всех л гн Х. Предлонгение. гг'(гг, К) являегсл лилейлой алгеброй.
Х Ыы не даем доказательства етого факта. Рекомендуем вначале проверить выполнение аксиом линейной алгебры для Я(2, И), после чего будет видно, как монгно построить доказательство в общем случае. Надо показать, что: а) М(п, Й) является векторным пространством; б) гг'(л, К) — кольцо; в) умпожеппо матрицы на скаляр обладает следующим свойством: )г(АВ)=(ХЛ)В=А(7.В) для всех 7. ы й, А, В гн я'(л, К).
Полезно иметь специальное обозначение для подмножества обратимых матриц из гя'(п, К). Обоаначим ато подмножество через СТ,(п, й) = (А гн.Х!(л, И): Л ' существует). Каждое СГ (и, И), пыжа, опргдгляет группу по узггщже- 207 нию. Эти группы называют полными линейными груллалси. Пусть >т — векторное пространство размерности л вад К н ТсиЕпй(Р). Если В (е>...„е.) — базис в (т, то очевидно, что Те, ю '>т для всех с, 1 н с < л. Следовательно, должны существовать Се ю К (1 < С, С ~ л) такие, что Те> сие> + Сг~ег + ...
+ с«,е„, Те„с,„е> + сз„ез +... + С„„е„. Пусть Ат — матрица вида '» сгс " '1« Ат м >с ''' з« с с ... с «1 «3 ° '' «« с с „,с тогда ее называют матрицей преобразования Т в базисе В. Для данного В матрица А, единственна; таким образом, мы можем определить отображение ср«; Епс(((т) - Вс (л, К) следующим образом: ср'(Т) А„ Так как А, можно вычислить, то ее можно использовать для нахождения 'Г. Предложение. Пусть Тж Епй(>т) соответствует матрица А, в базисе В ° (е>, ..., е ). Тогда, если хж т'- вектор хен 2', Х,ес, то Тх = лл (»ес ен '>т, гдв « Доказательство, Пусть х Х Хсе>. Тогда 1-1 « Тх ~о~ 1>Тес ~ Х>~~' с,е. 1-1 ЛОВ Следовательно, в данком базисе липейпоо преобразование Т можно выполнить с помощью произведения АтХ, где Ат имеет размерность и Х и, а Л вЂ” вектор (матрица размерности и Х 1) соответствующий х ж 1'.
На самом деле гюжпо установить гораздо болли>е. Ног>ге мы установим важные свойства >р'. Предл он>ение. Отобразвение >рг: Епб(1>)- -т.>г (и, В) является изоз>орфизмолг линейной алгебры с обычными операциями е Еш1(У) и .г>(п, В) на й, причел> ау>ге»ие >рг на группу Лис(1>) ~ Еп>1(т) является группой изоморфизм>ов на С> (и, И). Д о к а з а т е л ь с т а о, Отметим основные моменты.
Чтобы избе кать болыиого количества ипдоксов, ограничимся случаем и — 2. В общем случае доказательство аналогично. Изот>орфизгг линейкой алгебры следует пз следующих утверждений; а) >рг бпектпвпо; б) >р'(1;) =1; в) >рг(БТ) = >р'(Б)ц" (Т) для всех Я, Тгн Еп>1(г); г) >р" (ХЯ+ рТ) = й>р'ф)+ р>р'(Т) для всех 5, Т >н ы Еш1 (1') и ), р ее й. Докажем некоторые из втих утверждений; остальные оставим в качестве упражнений. Пусть (е>, ег1 — базис в 1>. а) Чтобы доказать, что ч>' инъсктивно, необходимо показать, что р Д=р (Т) б-т.
Если Яе> гме>+ гг,ег, Те> 1»е, +!г>ег, то >р (о) >р (Т) ~ г>> 1п, гм сю. Понтону 5е> — Тео Лналогичпо Бег Тег, Следовательно, Я и Т совпадают на базисных элементах с> и ег, Однако для всех х ж т' выполняется соотношение х = йе> + рог, Й д, ктв, Г, Бгез 209 такпм образом, Ьх Ыс~ + рбез = йте, + ртез = Т(Рс~ + роз) = 1х, т.е. Я=Т, Доказательство сюръективности оставляем в качество упражнения. б) 1;х х для всех х ю У; следовательно, 1,е1 = е~ + Оез, 1,ез = Ое1 + ез, и о) , в(1„) 1 — ~о 13 в) Пусть вд " ",в(т) тогда Те~ 1пе, + гмег, Ьте1 = гпЯе~ + ГмЯез = 6и(гие~ + змсз)+ гм (гме, + змез) (Гпзь1+ тмз~г) е1 + (гази + Гм газ) сз Аналогично отез (г1ззы + 8зз81з) е1+ (1!28з!+ 1мз22) ез.
Следовательио, р'рт)- р (я) р'(т), что и требовалось доказать. г) Утвер>кдеиие доказывается апалогичио утверждению в). Чтобы показать, что сужение уз на Аа1(г') является группой изоморфизмов, используем свойства б)-г). Пусть Т ~ Аиг(Р); тогда 1=,р (1,)- р (тт- ) = р (т) р (т- ), следовательно, Т ~в Акт (У) :- гр'(Т) ~и СЬ (и, К), р (т)- - р (т- ), 1 Этот результат играет существенную роль, так как имеет много важиых следствий. Выведем некоторые из иих.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
