Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 31
Текст из файла (страница 31)
Тогда, если М и У вЂ” матрицы р Х д, соответствующие отношениям р и а, то матрица ф пред- ставляющая отношение т, где т ((а, Ь): (а, Ь)сзр или (а, Ь)сва), определяется следующим образом ч„(Ме нлп )з'е)* Ме+Же (логпческое сложение). Следовательно, имеет смысл называть !;з суммой матриц М и У п ппсать ()-М+Д!, подразумевая, что Ч, М и Л имеют один и тот же размер и Д вычисляется по правилу покомвонентного сложения ф, = Ме+ !'з'„, Это — пример использовавпя коммутатнзной диаграммы, изображенной на рис. 6.1, где производится операция на одном множестве с использо- | Ф) Тогда У О 0 Дальше будет видно, что рОа ((а!, Ь!), (а!, Ьз), (а!, 0 0 0 1 0 0 0 Ьз), (аз, Ь!), (аз, Ь!), (аз, Ьз), (ам Ьз)) 197 и, что эквивалентно, 1 1 1 1ОО 11О О1О Более того, если мы возьмем многкество С (с<, сз, сз, см св) и рассмотрим отображение и между В и С, определенное следующим образом: ((Ь<, с<), (Ь<, сь), (Ьт, ст)< (Ьз, с<) (Ьз< св)) то оно может быть представлено в виде матрицы Р, где Очевидно, что отношение и ° р мея<ду А и С корректно определено п, следовательно, будет соответствовать матрице 4 Х 5.
Обозначим зту матрицу через Я. Как ее можно вычислитьг Для этого надо вычислить Яв для всех 1, /, где 1<1~4, 1~1~5. В силу биекции Яв 1 тогда и только тогда, когда (а<, с<)<ип ° р. Однако это так, если только существует некоторое Ь <и В такое, что (ао Ь)ж р и ( Ь, с,) ж и, т. е.
(ае с,)шп р =(а<, Ь<)жр и (Ь<, с,)<ип иля (аь Ьи) жр и (Ьт, с<)<ип, нлп (а„Ьз)<яр и (Ьз, с<)<ил; или же, что эквивалентно, 5<1 ™<1» Р<< + М<2» Рз< + М<3» РЗ< ~л~ вМй» Р<<1 й-1 Матрица Я, вычисленная по такому правилу, называется произведением М и Р и обозначается через М»Р или просто МР. рассмотрим опять естественное (коммутативное) отношение между двумя рассматриваемыми операторами (рис.
6.2). Тогда М»Р <р(<р <(Р)<ф <(М)) ° Замечание. Изменение порядка <р зависят от способа определения матрицы отношения; если (вместо этого) мы определим матрицу отношения следующим 1ЭЗ образом: Мв 1 тогда и только тогда, когда (аь Ьд)ж р, то изменения порядка не будет. Хотя с математической точки зрения было бы бо~д ) один и тот же порядок, зто нарушило бы сложившуюся практику. Соответствующие диаграммы в 8 3 рд„д д . Ю.д! Мер ко ети соглашения естестРас.
8.2 венны для вопросов, изучаемых в атом параграфе, Пример 1.1 (продолжение). Выполним вычисления, соответствующие определенным выше отношениям. По- лучаем 1ОО 1ОО О1О -1ООО1 О 1 О О О О 1 О О О ООО11 О 1 О 1 1 1 О О О 1 1 О О О 1 О 1 О О О Если матрицы М и У имеют одинаковый размер, то их сумма существует и определяется формулой (М+ Я) = Мв+)У„ а если матрицы Р и М согласованы (М имеет размерность р Х д, а Р— размерность о Х г), то умножение матрицы М на Р воэыонсно и определяется следующим образом: ч (МР)О - ~ М„.Рар а=ч Хотя матрицы рассматриваются над (Е„Д д ~/), мы используем символы» п + для того, чтобы иметь возможность обобщения введенных выше операций (см.
8 2). С етого момента обозначения /~ и Ч будут использоваться лишь в тех случаях, когда общие операции пм неадекватны. В заключптельной частя этого параграфа ограничимся рассмотрением матриц, представляемых отношениями на конечном множестве А, где )А! = и. Тогда все матрицы согласованы и их сумма и произведение всегда определены. Из покомпонентного определения сложения сраау следует, что сложение матрпц коммутатпвно и существует 19з нулевая (и ««л)-матрица О: О! О для воет 1я; я. С другой стороны, умяонтепие матриц, вообще говоря, некоммутатпвно, однако существует единица, которая называется единичной (и Х п)цматрицей и определяется следу!ощпм образом: 1: 1е 1, если 3 т, и 1о О, если ! чьу.
Так, если Х вЂ” матрица и «тп н У *Х1, то ч в «!! «ь«Х! 1и ««ХФ 1и+Х!! 1Н и-! в ! (г«««! Так как все 1ю О, ва псключенкем случая р 1, то в сумме все члены, исключая те, где р 1, равны нулю. Кроме того, 1в «, Поэтому Уо Хе, т. е. У Х. Следовательно, Х = Х1. Аналогично 1Х Х; поэтому 1Х ° Х Х1.
1 К сожален!по, обратная по умножению матрица может не существовать; однако если ояа существует, то она единственна, )йслп матрица нвтеет обратную, то она называется обратимой. Пример 1.2. Не существует матрицы Х такой, что '1' '1-' Д о к а з а т е л ь с т в о. Вычисление пропвведения дает [е «„[' Следовательно, какие бы значения компонент матряцы Х не рассматривались, элемент ((, !) произведения никогда не будет равен 1, откуда и следует требуемыи результат. у Таким образом, множество квадратиыл матрцц заданного размера с определеянытш на пем операциями умножения и сложения образует кольцо.
Пспользуя далее связь ментду бипзриымн отношениями на множестве н матрицами пад (2тг /~ф ~«!)ю дадпы следующие определения. Транспоннрованной матрицей М называется матрица М' такая, что Л1!! М;! (поэтому, если М получена из отношения о, то М' может быть получена из отношения о '); транзитивное замьша- 200 ние М+ и реатленеивяое замыкание М» (изоморфны соответствеппо а+ и о*) определяются следующим образом: )1+ ~ Пп Л1» ~~ )1п п=1 п»в где Л1в = 1, Л1' =М и Л1"ы = Л/Л1" (лыс)). (В некоторых случаях зги вамыкаппя нельзя определить корректно (чтобы соответствующие ряды сходплпсь), однако иад (Х„ Д, ~/) определение корректно, поскольку зто— замкнутое полукольцо.) В заключение заметим, что матрицы могут быть частично упорядочены путем позлемектного сравнения, а именно ИйМ тогда п только тогда, когда Л1;~Же для всех 1, /.
Пз данного определепил следует, что М(/У тогда и только тогда, когда М+М У, прп условии что + является операцией »максимум>, подобиой плп. Упразкк ение 6А. т. Пусть А — конечное множество п )А! п, а М— матрица иад (Х„Д, Ч), соответствующая некоторому бинарному отношению иа А, Доказать, что Л1+- Х Л1'. Р г (Следствием этого является тот факт, что вместо полукольца (Хю Д, ~/) мы можем рассматривать булеву алгебру (В, Д ~/, 1) где В = (О, т), Поэтому мы часто будем обозначать множество матриц и Хп через в1(п, В) и называть их булевы,ни матрицами.) 2, Допевать, что если М вЂ” конечная квадратная матрица иад (Х„Д, )/), то Л1» (1+ Л1)+, Указание; см. задачу т. 3, Показать, что если матрица Л1 иад (Хы Д~ )/) такал, что 1~ Л!, то М" < Л1"+' для любого пж г(.
В качестве следствия доказать, что если Ы имеет размер и Х л и р>лг, то М»=(1+М)', М» ЛР' для некоторого д такого, что 2' > пг. 4. Показать, что если существует обратная к Л1 мат. рпцз М ' (т. е. Л1 'Ш МЛ1 ' 1), то ова едивственла. 20т Доказать таьзке, что если У обратима и согласозапа с л/, то (Вй/) -' = М- А- . 5. Доказать, что если А, В и С вЂ” согласованные матрицы такие, что А «В=О=А «С, то отсюда ве следует равенство В = С. // й 2.
Матрицы над другпмп алгебраическими структурамп Ыы уделяем много внимания матрицам вад полукольцами (Х„ Д, ~/) и (В, /~, ~/, 1,) однако ничего не сказали о матрицах, чьп элемепты принадлежат другим структурам. Сначала мы рассмотрим вопрос о том, что надо требовать от структуры (Я, », +) для того, чтобы вгатрицы вад Я обладалп нун'вымп сзойстзамп. Затем обсудим технику вычислений, применяемую в ситуациях, когда операция замыкания корректно определена.
2А. Обобщенные лгатрицы. Пусть (дУ, ®, ®) обозначает мвожество Я(п, (Я, «, +)) матриц яХп вад (Я, «, +) с операциями ® и Ю, определенными в терминах «и +. Можно легко определить матрицы вад произвольным иепустым множеством, одпако вндуцироваииые при этом операции вад матрпцами могут быть некорректными и обладать неестественными свойствамп.
Рассмотрим вначале операцию сложевия. Если й1 и И вЂ” согласованные матрицы вад Я, тогда по определепвю (ма й/) „= м„+/у„. Для получения ® использовалась только одва операция сложения +. Поэтому сложение матриц выполняется просто. Однако для того, чтобы операция ю была коммутативва и ассоциативна, теми же самыми свойствами должно обладать (Ь", +). Отсюда следует, что нулевая матрица л(' существует тогда и только тогда, когда существует двусторонняя э) едивица О по отиогпению к + в Я, Аналогично существовавие аддптизных обратвых елемевтов в я' зависит от существования аддитизных обратвых элемевтов в Я. Поэтому сложение Ю ва М всегда может быть «) Левая я эравая,— Приве«, дед, 202 определено.
Причем, хотя для того, чтобы ( зт, ю) стало коммутативной группой, требуется выполнеапо многих свойств на (Я, +), многое можно получить да!ке тогда, когда операция + не обладает достаточным набором хорошпх свойств. В противоположность атому умножение в зг требует гораздо большего от Я. По аналогии с матрицами пад (Хз, /~, ~) положим (М ® 12 )!! Х '%2 «УА~ А Поскольку суммирование проводится в Я, то для корректного определения умноження в зз необходимо, чтобы результат не зависел от порядка суммирования.
Это будет выполнено, если слолгекие в Я ассоциативно. Не следует ожидать, что умножение в зз будет коммутативно; даже (так как (.21, ®), завпспт от (Я, ») и (Я, +)) для того, чтобы обеспечить ассоциативность в ( л', ® ), требуется больше, чем ассоциативность в (Я, «). Рассзготрпм следующий пример, в котором будут выполнены левая п правая днстрибутивность «над +, ассоциативность в (5, «) и ассоцпативность н коммутативность в (Я, +). Пример 2 !. Пусть И, У и Р— матряцы размерности ! Х 2, 2 Х 3 и 3 Х 1 соответственно. Тогда з ((ЛУ®У)3Р)!1=~~„'(ЛУ®Л!)!!» Р„- Ъ„| ~',311!«У!! 'Р„= ! ! 7 ! ! ! - ((Луы «У„) + (Лу„» У.„)).
Р„+ ((Лу„. У„) + -( (Л! !3» Л 22)) " Ры + ((.!! и» У!з) + (Л! !2» У зз)) " ' 31 ((Лг!!» Уы)» Ры) + ((Л 1~ „Ум) «Ры) + +((Лу„» У,з) «Р„)+ ((Л),2 «У,з). Рз,) + ((Л~„.У„).Р„)+ +((Лайз! ° У„)» Р„)-(Пы (У!! «Р„)) +(Лу„(У„»Ры))+ + (ЛХ„. (У„» Р„))+(ЛУ„. (Д „„«Р,,)Н-(ЛУ„.(й „«Р„))+ + (Л~12 Р 23 Р31)) ( ~1! (! ' 11 11))+ ( ) !! (У12 Р21))+ + (й|„»(У„. Р~))+(Л~„. (У„«Р,,)+ (Луы»(У„«Р„))+ +(Л!»! «(Уз«Р«))=.Ч!»((У»Р11)+(Уз «Рз!)+ +(У!3» Рм)) + Л~12» ((Л и " Ры)+ (Л ы " Р21) +(!' 22 " Рм)) - Х ЛХ„»(Х Уч'«Р,,1 =(ЛУЕ(УОР)1 / У !1 203 Прп провсдеппв выкладок предполагалось, что + ассоциативна, поэтому некоторые скобки былп опущены. г" Пока все это выглядят пе очень оптимистично, поскольку лпшь небольшое число структур может удовлетворять условпнм, накладываемым па (Я, к, +).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
