Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Цуканов Б.И. "Время в психике человека" (Медицина)

Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Яблоков Н.П. "Криминалистика" (Юриспруденция)
Реклама

Матричный анализ - Хорн Р.

Хорн Р. Матричный анализ — М.: Мир, 1989. — 655 c.
ISBN 5-03-001042-4
Скачать (прямая ссылка): matrichniyanaliz1989.djvu
Предыдущая << 1 .. 176 177 178 179 180 181 < 182 > 183 184 185 186 187 188 .. 260 >> Следующая

справедлив для любого цикла, удовлетворяющего условиям
(6.4.21).
Определим теперь множество
К se {р. е? Г (Л); \xm\ — ci*= const для всех т, таких, что
Рт Г out (Р»)} •
Множество К непусто, так как содержит все узлы цикла у'. По-кажем, что в действительности все узлы графа Г (Л) принадлежат /С.
Предположим, что имеется не принадлежащий К узел Ря. Поскольку Г (Л) сильно связен, то для каждого узла из /С найдется хотя бы один ориентированный путь в этот внешний узел Pq. Если из такого рода путей выбрать путь наименьшей длины, то его первая дуга обязательно идет из некоторого узла, принадлежащего К, в некоторый узел Pf% не принадлежащий К. Используя тот же предпорядок на узлах графа Г (Л), что и в доказательстве теоремы 6.4.18, мы можем провести такое же, как там, построение: начать с узла выбрать макси-
мальный узел Р/2 sFout (^/,). выбрать максимальный узел Pj3 е Tout (^/2). и так далее. На каждом шаге множество Г out {Pit) непусто вследствие слабой (и даже сильной) связности Г (Л), и максимальный узел удовлетворяет условию (с) в
(6.4.21) по тем же» что и прежде, причинам.
Если на некотором шаге построения возникнет выбор между максимальными узлами, один из которых принадлежит множеству К, а другой — нет, мы всегда разрешаем его в пользу узла, который не входит в /С. Если же все максимальные узлы данного шага принадлежат /(, мы выбираем произвольный из них и проводим из него кратчайший ориентированный путь к какому-либо узлу не из К; после этого выбор максимальных узлов идет прежним образом. Любой ориентированный путь, проходящий в К, обладает следующим свойством (вытекающим из определения множества К): каждый его узел является максимальным в множестве Tout предыдущего узла (условие (Ь) в
(6.4.21)). Поскольку дополнение к К содержит конечное число узлов, то наше построение рано или поздно натолкнется в первый раз на максимальный узел из дополнения, который уже встречался на одном из предыдущих шагов. Ориентированный путь, связывающий первое и второе появления этого узла, может не быть простым циклом вследствие способа, которым мы вынуждали путь покидать множество К в тех случаях, когда по-
строение приводило к его узлам. Часть пути, попадающая в К, содержит лишь конечное число циклов; отбрасывая их, получим простой ориентированный цикл у"щ удовлетворяющий условиям
(6.4.21) и содержащий по крайней мере один узел не из К.
Так как для цикла у" условия (6.4.21) выполнены, то в доказательстве теоремы 6.4,Ш можно взять у" вместо у'. Рассуждения, изложенные в первой части доказательства, позволяют установить, что — cjt = const для всех Рт е Гout (Pjj.) и всех Р/ е у". Но тогда каждый узел в у" принадлежит К, а это противоречит более раннему утверждению о том, что у" содержит хотя *5ы один узел не из К. Противоречие показывает, что в Г (Л) не может быть узлов, не входящих в К.
Если -у — произвольный нетривиальный .(простой ориентированный) цикл в Г (Л), то он автоматически (поскольку все узлы принадлежат К) удовлетворяет условиям <6.4.21). Мы можем подставить его вместо yf в доказательство теоремы 6.4.18, а затем в вывод равенства (6.4.28). Это и дает желаемый результат: граница каждого множества (6.4.27) проходит через Я. О
6.4.29. Следствие. Пусть А е Мп. Каждое из следующих уело-вий достаточно для того, чтобы матрица А была обратима:
(a) А слабо неразложима и
п ki> п я;
для любого нетривиального цикла у е С(Л);
(b) А неразложима и
П К|> П к
У 1 Pi^V
для любого нетривиального цикла у^С(А), причем хотя бы для одного цикла неравенство должно быть строгим.
Задачи
1. Пусть матрица А=[ац] удовлетворяет условиям Брауэра следствия 6.4.11(b) для обратимости. Показать, что \ait\> R't
для всех i = 1, ..., п, кроме, быть может, одного значения. Таким образом, условия Брауэра лишь немногим слабее условия
(а) теоремы Леви — Деспланка 6.1.10, требующего строгого диагонального преобладания. В какой связи это находится с теоремой 6.1.11?
2. Показать, что обратимость матрицы Л = [^д] можно установить с помощью любого из условий (6.4.11), но ни условие (а) теоремы Леви — Деспланка 6.1.10, ни теорема 6.1.11 для
этой цели неприменимы. Что можно сказать о столбцовом варианте последней теоремы?
3. Показать, что всякая неразложимая матрица ЛеМ„ (п ^ 2) слабо неразложима. Привести пример слабо неразложимой матрицы, не являющейся неразложимой.
4. Доказать следствие 6.4.29. Указание. Использовать те же рассуждения, что обосновывают теоремы 6.1.10 и 6.2.6.
5. Показать, что матрица ЛеМл тогда и только тогда слабо неразложима, когда ее нельзя привести к блочно-треугольной матрице, среди диагональных блоков которой есть блок порядка
1, посредством одновременной перестановки строк и столбцов, ,
Дополнительная литература
Более подробно об областях локализации собственных значений можно прочесть в статье: Brualdi R. Matrices, Eigenvalues, and Directed Graphs. — Lin. Multilin. Alg., 1982, v. 11, p. 143—165. Там же даны многочисленные ссылки на основную литературу по данному вопросу.
Предыдущая << 1 .. 176 177 178 179 180 181 < 182 > 183 184 185 186 187 188 .. 260 >> Следующая