Спектр матрицы смежностей почти полного орграфа

DOI:

Рассмотрим матрицу A _mn размера N х N , составленную из М нулей и N ² — М единиц. Как матрица смежности, A _mn соответствует орграфу, полученному из полного графа с петлями на N вершинах удалением некоторых М из N ² ребер. Некоторые важные свойства графа связаны со спектром его матрицы смежностей. Так, например, в [4] описана дискретная модель распространения вируса в сети, в которой спектральный радиус матрицы смежностей графа сети оказывается пороговым значением 1 / _т 0 отношения 1 / _т = ⁵ / _v интенсивности 5 исцеления инфецированных узлов и интенсивности v заражения узлов, смежных инфецированным. Положение 1 / т относительно порога 1 / _т 0 определяет (эндемический или эпидемический) характер заражения. Спектральная теория графов и ее приложения подробно рассмотрены в монографии [3].

Что можно сказать о собственных значениях матриц рассматриваемого вида?

Матрицу A _mn можно представить в виде

/1 ••• А amn = Jn - BMN = I .  . ..  . I - bmn ,

1 • • • 1

где J _N — матрица, составленная из N х N единиц, а B _mN имеет единицы в точности на тех М местах, где в A _mN стоят нули.

Спектр ст (J n ) матрицы J _N легко считается: J N = NJ _N , то есть Л ( Л — N ) — аннулирующий и, что легко проверить, минимальный многочлен матрицы J _N , а значит с (J n ) = {0,N} .

При достаточно малых М спектры матриц J _N и A _mN будут «близки». Методом подобных операторов (см.: [1; 2]), позволяющим для возмущений «идеального» объекта, спектральные свойства которого известны, найти элемент рассматриваемой алгебры, изоспектральный возмущенному, но имеющий более удобную для вычислений структуру, в статье доказывается следующая теорема.

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

ci С {^ G R; |r — N| < 4VM},

С2 С | ^ G C; | ^| < 4VM| .

2. Доказательство

Предварительные преобразования

Доказательство состоит в построении уравнения для матрицы, подобной A _mN , но устроеной «проще». Решение возникающего нелинейного уравнения в банаховой алгебре Matr _N C доставляется методом простых итераций (см., например, [1]).

Подобие матриц Л 1 , Л ₂ понимается в смысле существования обратимой матрицы U такой, что Л 1Ы = ^/Л ₂ . Подобные матрицы изоспектральны (их спектры совпадают).

Проведем предварительные преобразования.

/1 ••• 1\

Лемма 1. Матрица единиц Jn = I • '•   • I , подобна матрице

1 ..: 1

	( N	0 ••	• 0\
	0	0 ••	• 0
Л =	• •	•               . •	• •
	• 0	• 0 ••	•            . • 0/

Точнее, существует ортогональная матрица U такая, что J _N = ЫЛЫ ¹

Доказательство. Собственному значению 0 соответствует N — 1 независимый собственный вектор / 1 = (1, —1, 0,..., 0),..., / _N -1 = (0,..., 0,1, —1) , а собственному значению N матрицы J _N соответствует собственный вектор / n = (1,..., 1) . Применив ортогонализацию Грамма — Шмидта, получим ортонормальную систему h 1 ,... ,h _N :

^{h k}    V^ k + 1)

(1, ..., 1, — k, 0, ..., 0) G RN, k = 1,...,N — 1, к раз

hN = (1, ..., 1) G RN,

В качестве матрицы U выберем матрицу, имеющую столбцами векторы h _N , h ₁ ,..., h _{N - 1} :

	{ '	1 G2	1 G • • • V 6
	1	1	1 ——     • • •
	GN	G2	Ge
	1 GN	0	2 --• • • 6
U =	1 GN . .	0 . .	°    ••• .. ..
	. 1 GN	. 0	.. °    •••
	1 GN	0	°    •••
	1 X GN	0	°    •••

_______1_______ _____1_____\ V (N-2)(N -1)  7CW-1)N

V (N-2)(N -1)   ^ N- -1)N

V (N-2)(N -1)   ^ N- -1)N

V (N-2)(N-1)   ^N -1)N .. .. .. 1                    1

V (N-2)(N-1)   ^ (N-1)N 2-N           1

V (N-2)(N-1)   ^ (N-1)N °           / 1-N V (N -1)N/

Таким образом, исходная матрица A _mn подобна матрице А—В , где В = U ¹ B _MN U . Далее ортогональность матрицы U будет играть важную роль.

Расщепление матрицы и результат хи

Матрицы из Matr _N C будем записывать в блочном виде X —

■ 11

^X 21

^X 12

^X 22

, где

— число, X ₁₂ — строка, X ₂₁ — столбец, X ₂₂ — квадратный блок размерности N — 1 .

Такие блочные матрицы сами образуют алгебру, изоморфную исходной, и их можно естественным образом умножать на элементы пространства C х C ^{N -1} , изоморфного C ^N :

■ 11

^X 21

^X 12

^X 22

) (У = (

ХцХ1 + X12X2 X21X1 + X2 2Х2

)■ ■ - К)

G C х C ^{N -1} .

В дальнейших выкладках изоморфные объекты понимаются взаимозаменяемыми.

Следуя общей схеме метода подобных операторов [2], будем искать более «простую» матрицу, подобную А — В , в виде А — JX с матрицей преобразования подобия Е + rX , где Е G Matr _N C — единичная матрица, J, Г : Matr _N C ^ Matr _N C — линейные операторы, действующие на алгебре Matr _N C, подбираемые в ходе решения, причем J — проектор ( J ² = J ), «упрощающий» возмущение JX , а Г при всех X G Matr _N C удовлетворяет уравнению ArX — (rX)А = X — JX.

Лемма 2. Операторы J и Г следует задать формулами

JX = (Т А^) ,

rX =

°

N  —X21

^X 12 О

,

для X —

■ 11

^X 21

^X 12

^X 22

)

G MatrNC.

Следствие 1. Спектр блочно-диагональной матрицы Л — JX = объединение спектров ее диагональных блоков:

( ^{N —} Жц

V 0

^Х 22

)

есть

о (Л — jX) = {X — Хц} U с (Х ₂ 2).

Доказательство. Пусть Г действует по формуле ГХ =

Г 11 (Х)

Г 21 (Х )

^Г 12 ( ^Х 3 тогда

Г 22 (X) , тогда

лгх — (гх )Л = (     ⁰ , . ^NГ 12 ^(X>) ,

\— N Г21(Х)      0    / и уравнение для ГХ сводится к

X — JX = N (   ⁰.     ^{Г 12} < ^Х > ) .

^{— Г} 21 ^(Х )     ⁰   /

Значит, J может обнулить в X ~ ( ^Х 1¹    12 ) € Matr _v C все, кроме двух диаго-

^Х 21 ^Х 22

нальных блоков Х 11 и Х ₂₂ , поэтому положим

JX=("d1 vJ - гх = — ( 0

N —Х21   0.

Теперь выпишем уравнение подобия матриц Л — В и Л — J X :

(Л — В)(Е + ГХ) = (Е + ГХ)(Л — JX), X € MatrvC.

Лемма 3. Уравнение (1) эквивалентно уравнению

X = ВГХ + В— (ГХ)(З(В(Е + ГХ))), X € MatrvC.

Доказательство. Раскрывая скобки, уравнение (1) можно преобразовать к виду

X = ВГХ + В— (ГХ )JX.

Пусть для X выполнено (3). Тогда, учитывая равенство J ((ГХ)JX) = 0, получим равенство

JX = ЗВ + J (ВГХ)= J(В(Е + ГХ)).

Подставляя это выражение обратно в (3), получим (2). Аналогично, применяя к обеим частям равенства (2) оператор J и учитывая, что J ((ГХ)З(В(Е + ГХ))) = 0 , получим (3).

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

Ф(Х) = ВГХ + В — (ГХ)(J(S(E + ГХ))).

Теперь покажем, что при определенных условиях возникшее нелинейное отображение Ф : Matr _v C ^ Matr _v C имеет инвариантным множеством некоторый шар Q С Matr _v C с центром в нуле (то есть Ф(^) С Q ), на котором оно является сжимающим.

Пусть в Matr _v C выбрана какая-нибудь субмультипликативная норма || • || (то есть норма, удовлетворяющая неравенству ||Л 1 Л 2 | < ЦЛ^ЦЛ^ при всех Л 1 , Л 2 G G Matr _v C). Нам нужно найти такой радиус г > 0 , что при |Х|, ||У|| <  г выполнялись бы неравенства ||Ф(Х)| <  г и ||Ф(Х) — Ф(У)| <  qWX — У| , q G (0,1) . Обозначим ^в = НИ Y = sup _HX,= ^{| ГХ} \ .

Лемма 4. Пусть Ye <  4 , тогда шар

П = {X G MatrvC; |Х|| < го} ,

1    — 2ув - V1 -ЬЛ 0 < го = -------------- < 4в,

2у2в удовлетворяет условию Ф(^) С Q.

Доказательство. Очевидно неравенство

|Ф(Х)| < вУ2|Х|2 + 2ву|Х| + в.

Значит, если г удовлетворяет неравенству

ву2г2 + (2ву — 1)г + в < 0,

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

го =

1 — 2ув — V1 — 4ув 2^23

Учитывая ув <  4 , имеем г ₀ < 4 в .

Аналогичным образом устанавливается следующая лемма.

Лемма 5. Пусть ув <  | , тогда Ф — сжимающее отображение:

|Ф(Х) — Ф(У)|< q^X — У|, Х,У G П,

q = (1 + 2уго)ув < (1 + 8ув)ув < 4.

Доказательство.

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

< 3y|x - у | + 3Y2HX - у ||х + у |<

< 3YHX - У| + 2^2|Х - У|.

Здесь использовано равенство

(ГХ)J(ВГX) - (ГУ)J(ВГУ) = 2 [Г(Х - У) J(ВГ(X + У)) + Г(Х + У) J(ВГ(X - У))].

Отсюда и из теоремы Банаха о неподвижной точке следует лемма.

Лемма 6. В шаре

Q = {Х G MatrvC;  |Х|| < Го} существует и притом единственное решение Х° уравнения (2), являющееся пределом последовательности {Ф^(0); к G N}, где Ф^ = Ф о ф^-1 — композиция.

Следствие 2. Матрица А - В подобна блочно-диагональной матрице А - JX ° :

А-вД^ 0x°°

-

Х °2

) •

при этом выполняются условия:

а(А-В) = {X -^11} U а(-Х°2),

x°° G R, |x°°| < Го < 4в,

а (-Х°2) С {^ G C; |x| < Го < 4в}.

Доказательство. Матрица А - В подобна блочно-диагональной А - JX ° , поэтому их спектры совпадают. Спектр матрицы А - JX ° есть объединение спектров ее диагональных блоков. Ввиду субмультипликативности нормы имеют место неравенства

sPr(X°) =  max |Л| < ||Х°|| < Го.

.V а \ ° )

Кроме того, собственное значение х °1 является вещественным, как предел сходящейся вещественной последовательности.

Вернемся, наконец, к непосредственному доказательству основной теоремы.

Доказательство теоремы 1. Для доказательства осталось лишь выбрать подходящую субмультипликативную норму. Заметим, что матрица U, приводящая Jv к диагональному виду, является ортогональной, поэтому умножение на U или U-° есть изометрия.

Следовательно, |В| = ^ B mn | Рассмотрим в пространстве Matr _v C норму Фробениуса

H^l p , определенную

формулой ||^Х ||р = У ^.Ц ^lx ij |

2 , Х = (x ij ) G Matr _v C. Она субмуль

типликативна. При этом B _MV состоит из М единиц, поэтому

в = ЦВ |р = |Bmv|p = VM.

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

Y = n ^SU P

^N IMp = 1

( 0

-^ 21

-^12 0

)

F

N'

Если VM <  N , то выполняются условия леммы, причем г₀<  4 VM . Это значит, что o (A _M n ) = ^ 1 U С 2 , где a = { А 1 } С R , | A i - N | < 4VM , ^ 2 С { ^ G C ; | ^ | <  4VM } , а 1 П а ₂ = 0 . Теорема доказана.