Спектр матриці. Спектр матриці "спектр матриці" у книгах

DOI: https://doi.org/10.15688/mpcm.jvolsu.2017.4.2

УДК 517.984.3: 519.177 ББК 22.161

СПЕКТР МАТРИЦІ ЗМІЖНОСТЕЙ Майже ПОВНОГО ОРГРАФУ

Сергій Вікторович Козлуков

Воронезький державний університет [email protected]

вул. Університетська, 1, 394000 м. Воронеж, російська Федерація

Анотація. За допомогою методу подібних операторів вивчаються спектральні властивості матриць суміжностей графів, близьких до орієнтованих повних (графів). Наведено оцінки власних значень таких матриць.

Ключові слова: метод подібних операторів, спектр графа, локалізація спектру, нормальна форма жорданова, нелінійні рівняння, що стискають відображення.

1. Введення та основний результат

Розглянемо матрицю Ами розміру N х N, складену з М нулів та Ы2 - М одиниць. Як матриця суміжності Амм відповідає орграфу, отриманому з повного графа з петлями на N вершинах видаленням деяких М з М2 ребер. Деякі важливі властивості графа пов'язані із спектром його матриці суміжностей. Так, наприклад, описана дискретна модель поширення вірусу в мережі, в якій спектральний радіус матриці суміжностей графа мережі виявляється пороговим значенням 1/Т0 відношення 1/т = 5/у інтенсивності Ь лікування заражених вузлів і інтенсивності V зараження вузлів, суміжних зараженим. Положення 1/т щодо порога 1/Т0 визначає (ендемічний чи епідемічний) характер зараження. Спектральна теорія графів та її застосування докладно розглянуті в монографії.

Що можна сказати про власні значення матриць аналізованого виду?

Матрицю АМм можна подати у вигляді

де - матриця, складена з N х N одиниць, а має одиниці в точності

на тих місцях, де в Амм стоять нулі.

Спектр а) матриці легко вважається: ^ = , тобто Л(Л - N) - анулюючий і, що легко перевірити, мінімальний багаточлен матриці, а значить

а (^) = (0,М).

За досить малих М спектри матриць і Амм будуть «близькі». Методом подібних операторів (див.: ), що дозволяє для обурень «ідеального» об'єкта, спектральні властивості якого відомі, знайти елемент алгебри, що розглядається, ізоспектральний обуреному, але має більш зручну для обчислень структуру, в статті доводиться наступна теорема.

Теорема 1. Нехай М< М2, тогда спектр матрицы Амм можно представить в виде объединения а (Амм) = а! и а2 непересекающихся одноэлементного множества а! = = {Л!} и множества а2, удовлетворяющих условиям:

ai С (це R; | ц - N |< 4VМ Ü2 С |ц е C; |ц| < 4у/М

2. Доказ

Попередні перетворення

Доказ полягає у побудові рівняння для матриці, подібної до Амм, але влаштованої «простіше». Рішення нелінійного рівняння в банаховій алгебрі С доставляється методом простих ітерацій (див., наприклад, ). Подібність матриць Л!, Л2 розуміється в сенсі існування оборотної матриці і такої, що ЛЩ = ЫЛ2. Подібні матриці ізоспектральні (їхні спектри збігаються). Проведемо попередні перетворення.

Лемма 1. Матриця одиниць

Подібна до матриці

Точніше, існує ортогональна матриця і така, що = ЫЛИ-!.

Доведення. Власному значенню 0 відповідає N – 1 незалежний власний вектор /! = (1, -1, 0, ..., 0), ..., -! = (0,..., 0,1, -1), а власного значення N матриці відповідає власний вектор = (1,..., 1). Застосувавши ортогоналізацію Грама - Шмідта, отримаємо ортонормальну систему Н]_,..., :

= (1, ..., 1) е, Як матриця і виберемо матрицю, що має стовпцями вектори, к1,

2)(М -1 1) ■1)М

2)(М -1 1) у/(" -1 ■1)М

^(М -2 -2)(М -М 1) ■1)М

Таким чином, вихідна матриця Лмм подібна матриці А-Б, де Б Далі ортогональність матриці і відіграватиме важливу роль.

Розщеплення матриці та результат

Матриці з Ма^^С записуватимемо в блоковому вигляді X

х11 – число, Х12 – рядок, Х21 – стовпець, Х22 – квадратний блок розмірності N – 1. Такі блокові матриці самі утворюють алгебру, ізоморфну вихідної, і їх можна природним чином множити на елементи простору С х См-1, ізоморфного См:

/ ХцХ1 + Х12 ^ 2 \ \ X21X1 + Х22Х2)

У подальших викладках ізоморфні об'єкти розуміються як взаємозамінні.

Наслідуючи загальну схему методу подібних операторів , шукатимемо більш «просту» матрицю, подібну до Л - Б, у вигляді Л - ЗХ з матрицею перетворення подібності Е + ГХ, де Е е С - одинична матриця, З, Г: С ^ С - лінією -

ні оператори, що діють на алгебрі Ма^^С, що підбираються в ході рішення, причому З - проектор (З2 = З), що «спрощує» обурення ЗХ, а Г при всіх X е С

задовольняє рівняння ЛГХ – (ГХ)Л = X – ЗХ. Лемма 2. Оператори З і Р слід задати формулами

(Хц 0 \ ^0 Х22),

Наслідок 1. Спектр блочно-діагональної матриці Л - JX = ^^ 0Хп х) є

об'єднання спектрів її діагональних блоків:

a(A - JX) = (N - хп] U a(X22).

Доведення. Нехай Р діє за формулою ГХ = (г11(^) г12 (v)), тоді

\Г21(^) Г 22))

ЛГХ - (ГХ)Л = (-N ЫХ)

та рівняння для ГХ зводиться до

- - «= - (-гі%) 0 .

нальних блоків Хц і Х22, тому покладемо

Отже, J може обнулити в X ~ (^З1 ^12) е MatrNC все, крім двох діаго-

Г Л N V-^21 0) ■

Тепер випишемо рівняння подібності матриць Л-В та Л-JX:

(Л - В) (Е + ГХ) = (Е + ГХ) (Л - JX), X е MatrNC. (1)

Лемма 3. Рівняння (1) еквівалентне рівнянню

X = ВГХ + В-(ГХ)(3(В(Е + ГХ))), X е MatrNC. (2)

Доведення. Розкриваючи дужки, рівняння (1) можна перетворити на вигляд

X = ВГХ + В - (ГХ) JX. (3)

Нехай X виконано (3). Тоді, враховуючи рівність J((ГХ)JX) = 0, отримаємо рівність

JX = ЛВ + J (ВГХ) = 3 (В (Е + ГХ)). (4)

Підставляючи цей вираз назад (3), отримаємо (2). Аналогічно, застосовуючи до обох частин рівності (2) оператор J та враховуючи, що J((ГХ)3(В(Е + ГХ))) = 0, отримаємо (3).

Вираз у правій частині рівняння (2) позначимо як

Ф(Х) = ВГХ + В-(ГХ)(3(В(Е + ГХ))).

Тепер покажемо, що за певних умов нелінійне відображення Ф: Іа^мС ^ Іа^мС має інваріантним безліччю деяку кулю П С Іа^мС з центром в нулі (тобто Ф(П) С П), на якому воно є стискальним.

Нехай в Іа^мС обрано якусь субмультиплікативну норму || ■ || (тобто норма, що задовольняє нерівності ||^Л2|< ||Д1||||Д2|| при всех А\, Л2 € € Matr мС). Нам нужно найти такой радиус г >0, що з ||Х||, ||У ||< г выполнялись бы неравенства ||Ф(Х)|| < г и ||Ф(Х) - Ф(У)|| < дЦХ - У||, д € (0,1). Обозначим в = ||В||, у = 8ПР||Х || = ! ||ГХ ||. Лемма 4. Пусть ув < 4, тогда шар

П = (X € Іа^мС; | | Х | |< Го} ,

0 <Г° =-^-< 4в,

задовольняє умову Ф(П) З П. Доказ. Очевидна нерівність

||Ф(Х)||< вУ2|Х||2 + 2ву|Х|| + в. Значит, если г удовлетворяет неравенству

ву2г2 + (2ву - 1)г + в< 0, (5)

то ||Ф(Х)||< г при всех ||Х|| < г. Если ув < то дискриминант А = 1 - 4ув соответствующего уравнения положителен и его корни вещественны. Из знаков коэффициентов возникшего многочлена видно, что оба корня положительны. Следовательно, наименьший положительный г, удовлетворяющий неравенству (5), есть наименьший корень соответствующего уравнения:

1 - 2ув - V! - 4ув

Враховуючи ув< 4, имеем г° < 4в.

Аналогічно встановлюється наступна лема. Лемма 5. Нехай ув< тогда Ф - сжимающее отображение:

||Ф(Х) - Ф(У)||< дЦХ - У||, Х,У € П,

д = (1 + 2уг °) ув< (1 + 8ув)ув < 4.

Доведення.

||Ф(Х) - Ф(У)|| = ||БГ(Х - У) + (ГХ)(ВДХ + Б) - (ГУ)(БДУ + Б)\\<

< ву\\Х - У|| + ву2||Х -У||||Х + У|| < < ву|Х - У|| + 2гсву2||Х - У||.

Тут використано рівність

(ГХ)З(БГХ) - (ГУ)З(БДУ) = 1 [Г(Х - У)З(БГ(Х + У)) + Г(Х + У)З(БГ(Х - У))]

Звідси і з теореми Банаха про нерухому точку випливає лема. Лемма 6. У кулі

П = (X е Ма ^ С; | | Х | |< Гд}

існує і притому єдине рішення Х° рівняння (2), що є межею послідовності (Фк (0); до е М), де Фк = Ф про Фк-1 - композиція. Наслідок 2. Матриця Л - Б подібна до блочно-діагональної матриці Л - ЗХ

при цьому виконуються умови:

а (Л -Б) = (X - ж?1)і а (-Х2 ° 2),

х°п е М, |ж?1|< Го < 4в, а (-^2°2) С (ц е С; |ж| < го < 4р}.

Доведення. Матриця Л - Б подібна до блочно-діагональної Л - ЗХ °, тому їх спектри збігаються. Спектр матриці Л - ЗХ є об'єднання спектрів її діагональних блоків. Зважаючи на субмультиплікативності норми мають місце нерівності

зрг(Х°) = тах |А|< ||Х°|| < гд.

Крім того, власне значення х^ є речовим, як межа речової послідовності, що збігається.

Повернімося, нарешті, до безпосереднього підтвердження основний теореми.

Доказ теореми 1. Для доказу залишилося лише вибрати відповідну субмультиплікативну норму. Зауважимо, що матриця І, що призводить до діагонального вигляду, є ортогональною, тому множення на ТА або І-1 є ізометрією. Отже, ||Б|| = ЦВ ми | |. Розглянемо у просторі З норму Фробеніуса

||-||^, визначену формулою ||Х= ^^^х^^, X = (х^) е Ма^^уС. Вона є субмультиплікативною. При цьому Вми складається з М одиниць, тому

ß = \\в \\F = \\Bmn \\f =

Зауважимо також очевидну рівність

(0 Xi2\ V-^21 0)

Якщо у/М< , то выполняются условия леммы, причем г° < 4\/~М. Это значит,

що а(Амм) = а! та а2, де а! = (Л С М, |ЛХ - N| !}< 4v/M, а2 С {ц € С; |ц| < 4v/M}, а! П а2 = 0. Теорема доказана.

СПИСОК ЛІТЕРАТУРИ

1. Баскаков, А. Г. Гармонічний аналіз лінійних операторів/А. Г. Баскаков. - Воронеж: Вид-во Воронеж. держ. ун-ту, 1987. – 165 с.

2. Баскаков, А. Г. Розщеплення обуреного диференціального оператора з необмеженими операторними коефіцієнтами / А. Г. Баскаков // Фундаментальна та прикладна математика. – 2002. – Т. 8, № 1. – C. 1-16.

3. Cvetkovic, D. M. Spectra of Graphs: Theory and Applications (3rd revision) / D. M. Cvetkovic, M. Doob, H. Sachs. - N. Y.: Wiley, 1998. - 368 p.

4. Епідемічне розповсюдження в реальних мережах: an eigenvalue viewpoint / Y. Wang, D. Chakrabarti, C. Wang, C. Faloutsos // 22nd International Symposium on Reliable Distributed Systems, Oct. 2003. Proceedings. – 2003. – P. 25-34.

1. Баскаков А.Г. Гармонійський аналіз лінійних операторів. Voronezh, Voronezh State University Publ., 1987. 165 p.

2. Баскаков А.Г. Розщеплення возмущенного диференціального оператора з неограніченними операторними коефіціентами. Fundamentalna i prikladna matematika, 2002, vol. 8, no. 1, pp. 1-16.

3. Cvetkovic D.M., Doob M., Sachs H. Spectra of Graphs: Theory and Applications (3rd revision). N. Y., Wiley, 1998. 368 p.

4. Wang Y., Chakrabarti D., Wang C., Faloutsos C. Epidemic Spreading в Real Networks: Eigenvalue Viewpoint. 22nd International Symposium on Reliable Distributed Systems, Oct. 2003. Proceedings, 2003, pp. 25-34.

ON SPECTRUM OF AN ADJACENCIES MATRIX OF ALMOST-COMPLETE GRAPH

Sergey Victorovich Kozlukov

Voronezh State University [email protected]

Університетська St., 1, 394000 Воронеж, Російська Федерація

Abstract. Let AMn be a N x N matrix складається з N2 - M unities and M zeroes. Сприйняли як амортизацію matrix, AMn corresponds to a complete digraph with loops on N vertices with some M out of N2 edges removed. Some

Важливі властивості графа визначаються його спектром. Для прикладу Wang et al. proposed a discrete-time model viral propagation in a network. У цьому modelі virus will die out or linger on depending on what the ratio of curing and infection rates is below or above the treshold value. As Wang та ін. має казати, що третій рівень є спектровим radius of adjacencies matrix of network graph, i.e. максимальне повне значення його бойових цінностей. Більше сприятливе опис spectral graph theory і його застосування є веденим Cvetkovic et al. .

Цей матеріал analyzes spectral properties of such matrices. Matrix AMN може бути представлений у формі AMn = Jn - BMN, де Jn є N x N matrix які всі написи є один і BMN є unities exactly at the M places де AMN є zeroes. Спектр JN може бути легко сформульований: JN = NJ, so Л(Л - N) є мінімальним annihilating polynomial of JN і основою спектра Jn є a(JN) = (0,N).

Для малого дружби M eigenvalues of AMN буде "close" to those of JN. У цьому методі подібних операторів використовується, які дозволяють в разі відсутності певного objective (будь-які особливості є визначними) для пізнання елемента в алгебра під наглядом подібного до того, щоб розірвати один може бути "симплер" структури. Via this method the following theorem is proven:

Theorem. Let M< N2, then the spectrum of AMN can be represented as a disjoint union a (AMN) = a1 U a2 of a singletone a1 = {Л1} and the set a2, satisfying the following conditions:

CTi (ц e R; | ц - N |< iVM a2 С |ц e C; |ц| < А^М}.

Key words: метод подібних операторів, граф spectra, eigenvalues localization, Jordan normal form, nonlinear equations, contraction theory.

Сукупність її власних значень.Див. також Характеристичний багаточленматриці.

- Дворядні комплексні ермітові матриці Введені В. Паулі для описусобств. механіч. моменту імагн. моменту електрона...
Фізична енциклопедія
- Число r, таке, що визначник принаймні однієї rx r -матриці, отриманої з даної матриці видаленням нек-рих рядків і стовпців, відмінний від нуля, а визначники всіх матриць розмірності ...
Фізична енциклопедія
- дворядні комплексні постійні ермітові матриці коефіцієнтів. Введені Ст Паулі, для опису спинового механіч. моменту та магнітного моменту електрона...
Математична енциклопедія
- квадратні матриці Аі Водного порядку, пов'язані співвідношенням = S-1AS, де S - яка-небудь невироджена матриця того ж порядку. П. м. мають один і той же ранг, один п той же визначник, один і той же характеристич.
Математична енциклопедія
- Прогресивні матриці Равена - батарея тестів, розроблена англійським психологом Дж. Равеном в 1938 р. для діагностики рівня інтелекту - , заснована на роботі наочного мислення - за аналогією.
Психологічний словник
- Die radius - .Радіус зовнішнього краю глибоковитяжної матриці, над якою поміщається тонколистовий матеріал.
Словник металургійних термінів
- англ. progressive matrices, Raven; ньому. Progressionsrnatrix von Raven...
Енциклопедія соціології
- сума діагональних елементів матриці.
- алгоритм, який застосовується при чисельному знаходженні зворотної матриці. Як і в задачі вирішення лінійних систем, методи чисельного звернення поділяються на прямі та ітераційні...
Математична енциклопедія
- див. Мутація зсуву рамки "...
Великий медичний словник
- "...Електронна діафрагма - елемент конструкції ПЗЗ-матриці, що забезпечує автоматичне регулювання витримки в залежності від рівня освітленості.
Офіційна термінологія
- "...Електронний затвор - елемент конструкції ПЗЗ-матриці, що забезпечує можливість зміни часу накопичення електричного заряду.
Офіційна термінологія
- Квадратні матриці А і В порядку n, пов'язані співвідношенням В = Р-1АР, де Р - яка-небудь неособлива матриця того ж порядку...
Велика Радянська Енциклопедія
- найвищий з порядків відмінних від нуля мінорів цієї матриці.
Великий енциклопедичний словник
- упо/ри-ма/триці, упо/рів-ма/триць, од. упо/р-ма/триця, упо/ра-матрі/ци,...
Добре. Окремо. Через дефіс. Словник-довідник
- ...
Орфографічний словник-довідник

"СПЕКТР МАТРИЦІ" у книгах

Достойне життя для людей першої матриці: Матриці Блаженства та Спокою

автора Ангелайт

Достойне життя для людей першої матриці: Матриці Блаженства і Спокою Перша матриця – Матриця Блаженства та Спокою – сповнена своїх переваг, якими ми користуємося у повсякденному житті, навіть не замислюючись про те, як у нас це виходить. Одного разу, коли моя машина була в

Достойне життя для людей другої матриці: Матриці Терпіння та Нагромадження

З книги Формула гідного життя. Як побудувати свій добробут за допомогою Матриць Життя автора Ангелайт

Достойне життя для людей другої матриці: Матриці Терпіння та Накопичення Друга матриця – Матриця Терпіння та Накопичення – надає нам свої можливості для гідного життя. На перший погляд здається, що життя у другій матриці складніше та важче, ніж у всіх

Достойне життя для людей третьої матриці: Матриці Боротьби та Втілення

З книги Формула гідного життя. Як побудувати свій добробут за допомогою Матриць Життя автора Ангелайт

Третя матриця – Матриця Боротьби та Втілення – сповнена своїх переваг, особливо щодо досягнення бажаного рівня життя. Адже саме енергія третьої матриці дозволяє нам прагнути до

Достойне життя для людей четвертої матриці: Матриці Успіху та Перемоги

З книги Формула гідного життя. Як побудувати свій добробут за допомогою Матриць Життя автора Ангелайт

Четверта матриця – Матриця Успіху та Перемоги – дуже приваблива для багатьох людей завдяки своїм особливим достоїнствам. Найбільш привабливі переможне досягнення успіху та вміння його

автора Ангелайт

Ознаки першої матриці – Матриці Блаженства та Спокою

Ознаки другої матриці - Матриці Терпіння та Накопичення

З книги Карматерапія. Лікування минулих життів автора Ангелайт

Ознаки другої матриці – Матриці Терпіння та Накопичення Настала черга докладніше розібратися з ознаками другої матриці. Нагадаю, що ми досліджуємо з вами пари "проробленості-непроробленості" матриць, які я відзначив у таблиці трохи раніше. Це нам потрібно для того,

Ознаки третьої матриці – Матриці Боротьби та Втілення

З книги Карматерапія. Лікування минулих життів автора Ангелайт

Ознаки третьої матриці – Матриці Боротьби та

З книги Карматерапія. Лікування минулих життів автора Ангелайт

Ознаки четвертої матриці – Матриці Успіху та Перемоги

Програми першої матриці – Матриці Блаженства та Спокою

автора Ангелайт

Програми першої матриці – Матриці Блаженства та Спокою Визначаючи програми першої матриці, нам потрібно обов'язково згадати властиві їй властивості, її ознаки. Незважаючи на те, що всі люди різні, ці ознаки властиві всім нам певною мірою. Тобто всі ми добрі,