Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 28
Текст из файла (страница 28)
Информация в компьютере обычно хранится в виде матриц. ОПРЕДЕЛЕНИЕ 4.31. Для положительных целых чисел т и и матрицей пг х гг, или массивом гтг х тг, называется функция А: (1,2,...,т) х (1,2,...,п) — Р, где Р— это, как правило, множество действительных, комплексных, рациональных или целых чисел. Элементы Р называются скаллрами. Таким образом, для каждого г, 1 < г < т, и каждого т', 1 < г < п, имеется элемент А(г, г) из Р, который находится в 1-ой строке и в гьом столбце соответствующей прямоугольной таблицы, Образ А(г, г) элемента (г, г) области определения сокращенно обозначается через А, . Таким образом, и х пг матрица А изображается прямоугольной таблицей, где образы (г, г) Е (1, 2,..., т) х (1,2,..., и) при отображении А могут быть перечислены следующим образом: А~~ Агг А~з Аг Аш Агг Агз Аг Апп Ап,г Аыз Атп где первая строка таблицы состоит из А~ для г = 1 до и, вторая строка состоит из Аг для г = 1 до и и т.д.
При этом говорят, что А содержит т строк и и столбцов и является матрицей размера т х п. Иногда зайисывают сокращенно А = [А, ] или даже А = (а;Д. Значение А, называется компонентой, или элементом матрицы А. Матрица размера 1 х т называется матрицей-строкой, а матрица размера п х 1 называется матрицей-столбцом. Если в матрице число строк и число столбцов совпадает, она называется квадратной матрицей. Если А— матрица-строка, индекс строки обычно опускают и пишут 168 ГЛА8А 4. Функции и магприцы [2 1 71 Например, А = ~ 4 О 6 ~ — это матрица 2 х 3, а В = — 2 5 7 — 3 9 О 25 2 9 представляет собой квадратную матрицу 3х3. По определению, Аьз = 7, Агг — — 4, [7 1[ В1г = 5 и Взг = 25.
Матрица С = ~ 3 9 ~ есть квадратная матрица 2 х 2 ОПРЕДЕЛЕНИЕ 4.32. Говорят, что две матрицы А = [А1 [ и В = [В,у[ размера т х и равны, если равны их соответствующие элементы; т.е. А = В тогда н только тогда, когда А„= В„для всех 1, 1 < 1 < т, и всех г, 1 < 1 < и. Например Аы А1г А1з А21 Агг Агз Азг Азг Азз В11 Вгг В1з В21 В22 В23 В31 В32 Взз тогда и только тогда, когда А„= В„для 1 < 1, г < 3.
Заметим, что это определение равенства матриц является всего лишь переформулировкой условия равенства двух функций А и В: А((1', 1)) = В((1, г)) для всех (1, 2). В данном разделе некоторые определения и теоремы будут сформулированы только для матриц 2 х 2 и 3 х 3; более общая их формулировка будет дана в последующих главах. Для упрощения выкладок, а также для удобства и определенности, большинство теорем будет доказано только для матриц 2 х 2 и 3 х 3. ОПРЕДЕЛЕНИЕ 4.33. Если 11 — скаляр, а А = [А, ] — матрица т х и, то 11А есть матрица Р = [Р„[ размера т х п, где Р„= 11А11, т.е. каждая компонента Р есть произведение соответствующей компоненты А на Ы. Произведение числа 0 и матрицы А называется умножением матрицы на скаллр.
ПРИМЕР 4.34. Пусть А = [А; [ = 6 О -2 (7)(6) 1 — 3 51 6 Π— 2~, т да (7)( — 3) (7)(5) ~ [ 7 — 21 35 ~ (7)(О) (7)( — 2) ~ ~ 42 Π— 14 ~' РАзйеЛ4.3. матрицы 169 ПРИМЕР 4.36. Пусть А = Тогда ОПРЕДЕЛЕНИЕ 4,37. Произведение двух матриц определяется следующим образом: а) Пусть У вЂ” матрица-строка или матрица-столбец с и элементами, и Иг— матрица-строка или матрица-столбец с и элементами: У1 12 или У=[Уз 12 ' 1п] или Иг = [ И'"1 Игг Игп ], Тогда скалярным лроизведением, или внутренним нроизведением У и Иг называется число У1)Уг+У2Игг+. +У„И'„, которое обозначается через УаИг.
б) Пусть Аы Агз Агг .. Азр А2г А2р А Ашг Атр есть матрица ги х р, а Вгг ' ' ' Вгп Вгг Вгг ' ' ' В2п есть матрица р х и. А+В= [ Игг И2 ру = ( — 1) + 3 3+ 11 2+( — 5) 7+4 4+8 ( — 5) +2 170 ГЛЯВА 4. Функции и матрицы ПРИМЕР 4.38. Пусть — 2 4 0 8 3 — 1 — 2 1 0 5 7 0 А=[АО) = 6 0 2 и В=[ВО) = [ — 2 Си=[1 — 3 5] ° = (1)(-2) + (-3)(3) + (5)(0) = -11; Сгз=[6 0 — 21 ° = (6)(0) + (0)(-2) + (-2)(7) = -14 . Продолжая вычисления в том же духе, получаем АВ= 6 0 — 2 -11 32 41 5 3 — 1 — 2 1 -12 14 -14 48 П Доказательство следующей теоремы можно найти в любой книге по линейной алгебре. ТЕОРЕМА 4.39. Для любых матриц А, В и С размера и х п и действительных чисел г и а справедливы следующие утверждения: а) А+ В = В+ А (свойство коммутативности сложения); б) А + (В + С) = (А + В) + С (свойство ассоциативности сложения); в) А.
(В. С) = (А. В) . С (свойство ассоциативности умножения); г) А . (В + С) = (А В) + (А С) (свойство дистрибутивности матриц); д) А. (гВ + зС) = г(А В) + а(А. С) (свойство линейности матриц ). Вычислим матричное произведение С = [С, ] = АВ следующим образом. Матрица А имеет размер 2 х 3, а матрица  — размер 3 х 4, так что произведение АВ = С определено и будет представлять собой матрицу размера 2 х 4. Сы есть скалярное произведение первой строки матрицы А и первого столбца матрицы В, а Сзз — скалярное произведение второй строки матрицы А и третьего столбца матрицы В. Таким образом, РЯЗДЕЛ 43.
Матрицы 171 ОПРЕДЕЛЕНИЕ 4.40. Пусть А — матрица п х т. Ее транснонировинной матрицей называется матрица А' размера т х п такая, что А';, = А,;, где А, — элемент 1-ой строки и г-го столбца матрицы А. Если А — матрица п х п и А, = А, для всех 1 < г,г < п, то матрица А называется симметричной. Иными словами, матрица А симметрична тогда и только тогда, когда А = А'. ПРИМЕР 4.41. Пусть А =~ б ). Тогда А' — матрица размера 3 х 2, (1 — 3 51 полученная из А заменой строк на столбцы: А'= б О 2 ТЕОРЕМА 4.42. Пусть А и  — матрицы, произведение которых определено.
Тогда (АВ)' = В'А'. Доказательство этой теоремы мы предоставляем читателю. ПРИМЕР 4.44. Пусть А = (аыаг,аз) и В = (ЬыЬг). Пусть  — отношение ((а1 Ь1), (аг, Ь|), (аг, Ьг), (аз, Ьг)). Тогда матричное представление имеет вид ПРИМЕР 4.45. Наименьшее рефлексивное отношение на А = (амаг,аз) есть отношение ((аы аг),(аг,аг),(аз,аз)). Матричное представление этого отношения имеет вид Наибольшее отношение на А есть А х А. Его матричное представление имеет вид ИИ о 1. 172 ГЛАВА 4. Функцоо о матрацы ОПРЕДЕЛЕНИЕ 4.46.
Определим булевы операции и и л на множестве (О, Ц следуюшим образом: О 1 Булевой матрицей называется матрица, каждый элемент которой есть О или 1. Пусть А и  — булевы матрицы размера т х и, а С вЂ” булева матрица размера и х р. Тогда а) У = А и В определяется соотношением 1У,, = А, ~~ Внп где 1 < 1 < т, 1 < з < и; б) 1 = АлВ определяется соотношением Ц=А,,лВО, где1<г<т,1<з<п; в) П = А ОС определяется соотношением В„= (Ам д В„) ~(А„д Взу) ~ . 'о' (А;„д В„.), где 1< 1 < т, 1 < у < р. ПРИМЕР 447.
Пусть А = (ам аз,аз), В = ((ам аз),(ам аз),(аз,а~),(аз,аз), (аз,оз)) и В = ((оз о~),(оыаз),(аз,аз),(аз,аз),(аз,аз),(аз,аз)). Матричными представлениями отношений В и Я, соответственно, являются Тогда О 1 1 1 .[ д О 1 и О О О 1 О 1 РАЗДЕЛ 4.3. Матрицы 173 ТЕОРЕМА 4.48. Пусть Л и Я вЂ” отношения на конечном множестве А = (ам аз, ...,а„) и им соответствуют матричные представления М и Ж. а) Если Л рефлексивно, то Мн = 1 для 1 < 1 < и. б) Если Л симметрично, то МО = М,; для 1 < 1, з < и; поэтому М = М', и М вЂ” симметричная матрица.
в) ПУсть Мшз = М О М. Если Л тРанзитивно, то, как только М аз = 1, мы имеем М,ь = 1 для 1 < 1, Й < и. г) М~~ АГ является матричным представлением ЛОВ. д) МААг является матричным представлением ЛйЯ. ДОКАЗАТЕЛЬСТВО. а) Поскольку отношение Л рефлексивно, то (а,, а;) е Л для всех 1 < 1 < и. Поэтому М„= 1 для всех 1 < г < и. б) Если М, = 1, то (а„а ) Е Л, а поскольку Л симметрично, то (а,, а;) Е Л, так что М, = 1. Обратно, если М, = 1, то (а,,а,) Е Л, а поскольку Л симметрично, то (ам а ) Е Л, так что М, = 1. В силу того, что М, = 1 тогда и только тогда, когда М,; = 1, М = М', М вЂ” симметричная матрица. в) Допустим, что М,ьз = 1. Поскольку Мсьз = (А 1лАгь) ч (А,злАзь)ч ° ° ° ч (А,„ЛА„ь), то существует такое ги, что (А, АА ь) = 1.
Поэтому А, = 1 и А ь = 1. По определению матричного представления (а„а„,) е Л и (а, йь) е Л. Поскольку Л транзитивно, то (а„аь) Е Л и М,ь = 1. Оставшуюся часть доказательства предоставляем читателю. Далее, имеем 1 1 0 0 0 0 1 0 1 1 0 0 001 О 1 1 0 0 и Я = ((ам с1), (й1, сз), (й1, сз), (йз, с|), (аз сз)). Следующее утверждение является следствием теорем 4.48, 4.49 и 2.37. ТЕОРЕМА 4.51.
Пусть А — матричное представление отношения Л. а) Рефлексивное замыкание Л имеет матричное представление А о 1. б) Симметричное замыкание Л имеет матричное представление А 0 А'. в) Если А — конечное множество, содержащее и элементов, тогда транзитивное замыкание Л имеет матричное представление А о Ащз с1 Ашз с1 . и Аш". Доказательство следующей теоремы мы также предоставляем читателю. ТЕОРЕМА 4.49.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
