игляд де Х і Z -квадратние матриці. В іншому випадку матриця А називається неразложимой.
Спектральні властивості нерозкладних невід'ємних матриць описуються наступною теоремою Фробеніуса.
Теорема 1.3. Нерозкладна неотрицательная матриця А завжди має позитивне власне значення r, яке є простим коренем характеристичного рівняння. Модулі всіх інших власних значень не перевищують числа r. «Максимальному» власному значенню r відповідає власний позитивний вектор. Крім того, якщо А має h власних значень, по модулю рівних r, то ці числа всі різні між собою і є корінням рівняння і взагалі весь спектр [] матриці А, що розглядається як система точок в комплексній? -плоскості, Відображається на себе при повороті цій площині на кут 2?/h. Якщо h gt; 1, то перестановкою рядків з такою ж перестановкою стовпців можна матрицю А привести до наступного «циклічного» увазі:
(1.1)
уздовж головної діагоналі тут стоять квадратні блоки.
При h gt; 1 матриця А називається імпрімітівной; число h - її індекс імпрімітівності. В іншому випадку матриця А примітивна.
Згідно з теоремою 1.3 спектр мультиграфом (мультіорграфа) G лежить в колі, де r - найбільше дійсне власне значення. Це власне значення називається індексом графа G. Алгебраїчна кратність індексу може бути більше 1. У цьому випадку існує відповідний даному індексом ненегативний власний вектор.
Нерозкладним матриці суміжності графа пов'язана з властивістю зв'язності. Матриця суміжності сильно зв'язкового мультіорграфа неразложима: мультіорграф, матриця суміжності якого неразложима, сильно зв'язний. У неорієнтованих мультиграфом властивість сильної зв'язності зводиться просто до зв'язності.
Згідно з теоремою 1.3. індекс сильно зв'язкового мультіорграфа є простим власним значенням матриці суміжності, якому відповідає позитивний власний вектор.
Як показує наступна теорема, у разі симетричної матриці суміжності справедливо також зворотне твердження.
Теорема 1.4. Якщо «мaксімaльное» власне значення r неотрицательной матриці А є простим і йому відповідають позитивні власні вектори матриць А і АТ, то А - нерозкладна матриця.
Теорема 1.5. «Максимальному» власному значенню r неотрицательной матриці А відповідає позитивний власний вектор матриці А і позитивний власний вектор матриці АТ тоді і тільки тоді, коли матриця А може бути представлена ??перестановкою рядків і такий же перестановкою стовпців в квазідіагональном вигляді А=diag (А1, ..., As). де A1, ... Аs - нерозкладних матриці, у кожної з яких r «максимальне» власне значення.
Наведемо ще кілька теорем з теорії матриць, що характеризують спектральні властивості графів.
Теорема 1.6. «Максимальне» власне значення r будь головною подматріци (порядок якої менше n) неотрицательной матриці А (порядку n) не перевищує «максимального» власного значення r матриці А. Якщо А - нерозкладна матриця, то нерівність r lt; r справедливо завжди. Якщо А - разложимой матриця, то по крайней мepe для однієї головної подматріци r '= r.
Теорема 1.7. При збільшенні будь-якого елементу неотрицательной матриці А «максимальне» власне значення не зменшується. Воно строго зростає, якщо А - нерозкладна матриця.
Теореми 1.6 і 1.7 стверджують, що індекс будь-якого подграфа зв'язкового (сильно зв'язкового) мультиграфом (мультіорграфа) G менше індексу графа G.
Теорема 1.8 Всі власні значення ермітової матриці є дійсними числами.
Комплексна матриця А=() називається ермітової, якщо Ат =, тобто =.
Теорема 1.10. Нехай А - ермітова матриця з власними значеннями і В - одна з її головних підматриць з власними значеннями? 1, ...,? M .Тогда справедливі нерівності? N-m + 1 ?? i ?? i (i=1, ... , m).
Це - відомі нерівності Коші, а саме твердження відоме як теорема про сплетінні.
Теорема 1.11 Нехай А - дійсна симетрична матриця з власними значеннями за умови що задано розбиття множини {l, 2, ..., n} =, розглянемо відповідну блокову матрицю А=(Аij), у якої блок має розміри ni nj. Якщо еij - сума значень елементів матриці Аij і В=(eij/ni), т. Е. Eij/ni - середня сума значень елементів рядка матриці А, то спектр матриці В міститься в відрізку [? N,? 1].
Якщо припустити, що в кожному блоці Aij (див. теорему 1.11) всі суми значень елементів рядків однакові, можна отримати навіть більш сильне твердження.
Теорема 1.12. Нехай А - блокова матриця з розбиттям на блоки згідно умовам теореми 1.11. Нехай, далі, для всіх рядків блоку А ij сума bij значень елементів рядка однакова і В=(bij). Тоді спектр матриці В міститься в спектрі матриці А.
Квадратні матриці А і В називаються подібними, якщо існує невироджена квадратна матриця Х, перетворююча А в В, т. е. така, що X - 1AX=В. Кожна симетрична матриця і кожна матриця, всі власні значення якої різні, подібні діагональної матриці. Якщо А є матрицею суміжності мультигр...
