Теорема Перрона-Фробениуса: спектральный радиус и собственный вектор

Теорема Перрона-Фробениуса - главный спектральный результат для неотрицательных матриц. Она утверждает, что у любой такой матрицы есть «привилегированное» собственное число - спектральный радиус $\rho(A)$ - которому отвечает собственный вектор с неотрицательными координатами. На этом одном факте держатся стационарные распределения цепей Маркова, алгоритм PageRank, модель Лесли в демографии и асимптотика любой динамической системы вида $x_{k+1} = A x_k$ с $A \geq 0$. Оскар Перрон доказал теорему в 1907 году для строго положительных матриц, Георг Фробениус в 1912 году распространил её на неотрицательные неприводимые случаи. С тех пор формулировка не меняется - меняется только пул приложений.

Постановка: неотрицательные матрицы

Матрица $A = (a_{ij}) \in \mathbb{R}^{n \times n}$ называется неотрицательной ($A \geq 0$), если $a_{ij} \geq 0$ для всех $i, j$. Положительная ($A > 0$) - если все $a_{ij} > 0$ строго. Это разные классы, и теорема о них формулируется по-разному. Спектральный радиус определяется как

$$\rho(A) = \max\{ |\lambda| : \lambda \in \sigma(A) \}$$

где $\sigma(A)$ - спектр (множество собственных чисел). Для произвольной матрицы $\rho(A)$ - просто число; ключевой вклад Перрона и Фробениуса в том, что для $A \geq 0$ это само собственное число, причём с особыми свойствами.

Классическая формулировка

Теорема (Перрон, 1907; Фробениус, 1912). Пусть $A \geq 0$ - неотрицательная квадратная матрица. Тогда:

1. $\rho(A)$ - собственное число матрицы $A$;
2. существует собственный вектор $v \geq 0$, $v \neq 0$, такой что $A v = \rho(A)\, v$;
3. если $A$ неприводима, то $\rho(A) > 0$, оно простое (алгебраическая кратность 1), а соответствующий собственный вектор строго положителен ($v > 0$) и единственен с точностью до положительного множителя;
4. если $A$ примитивна, то $\rho(A)$ строго доминирует: $|\lambda| < \rho(A)$ для любого другого собственного числа $\lambda$.

Свойство (4) - то, ради чего теорему вообще применяют в динамике: оно гарантирует, что итерации $A^k x_0$ сходятся к направлению вектора $v$, и сходимость экспоненциальная со скоростью, определяемой вторым по модулю собственным числом.

Подставь свою матрицу ниже - соберём её, проверим неприводимость и примитивность, найдём $\rho(A)$ и положительный собственный вектор пошагово в чате.

Неприводимость и примитивность

Эти два свойства легко перепутать, а в формулировке они отвечают за разные пункты.

Неприводимость. Матрица $A$ называется неприводимой, если её ассоциированный ориентированный граф $G(A)$ (вершины - индексы, ребро $i \to j$ ставится при $a_{ij} > 0$) сильно связен: из любой вершины можно дойти до любой по рёбрам. Эквивалентное определение - не существует перестановочной матрицы $P$, приводящей $A$ к блочно-треугольному виду

$$P^T A P = \begin{pmatrix} B & C \\ 0 & D \end{pmatrix}$$

Примитивность. Матрица $A \geq 0$ примитивна, если она неприводима и существует $k \geq 1$, для которого $A^k > 0$ (все элементы строго положительны). Эквивалентно: $A$ неприводима и апериодична - наибольший общий делитель длин циклов графа $G(A)$ равен 1.

Различие важно. Перестановочная матрица $P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ неприводима, но не примитивна: её собственные числа $\pm 1$ имеют одинаковый модуль, никакая степень не даст строго положительной матрицы. Поэтому пункт (4) - про доминирование - для неё не выполняется.

Доказательство-эскиз через неподвижную точку

Самый прозрачный путь - топологический. Рассмотрим симплекс

$$\Delta = \left\{ x \in \mathbb{R}^n : x_i \geq 0,\ \sum_i x_i = 1 \right\}$$

Это компакт, гомеоморфный шару. Определим отображение

$$T(x) = \frac{A x}{\sum_i (A x)_i}$$

(нормализация суммы координат к единице). Если $A x \neq 0$ для всех $x \in \Delta$ - а это так при $A \geq 0$ без нулевых столбцов и при сохранении положительности симплекса - то $T : \Delta \to \Delta$ непрерывно. По теореме Брауэра о неподвижной точке существует $v \in \Delta$ с $T(v) = v$, то есть $A v = \lambda v$ при $\lambda = \sum (A v)_i \geq 0$. Это $\lambda$ оказывается равным $\rho(A)$.

Для общего неотрицательного случая (с нулевыми столбцами) используется теорема Шаудера о неподвижной точке в более тонкой версии или аппроксимация $A + \varepsilon J$, где $J$ - матрица из единиц, с переходом $\varepsilon \to 0$. Все строгие версии можно найти у Гантмахера в «Теории матриц».

Простоту собственного числа в неприводимом случае доказывают отдельно - обычно через анализ присоединённого оператора и характеристический полином.

Стационарные распределения цепей Маркова

Цепь Маркова с конечным числом состояний задаётся стохастической матрицей $P$: $P \geq 0$ и $\sum_j p_{ij} = 1$ для каждой строки. Стационарное распределение - это вектор-строка $\pi \geq 0$ с $\sum \pi_i = 1$ и $\pi P = \pi$, то есть левый собственный вектор матрицы $P$ для собственного числа 1.

Из стохастичности следует $\rho(P) = 1$: вектор-столбец из единиц всегда правый собственный для собственного числа 1, а норма строки не превосходит 1. Теорема Перрона-Фробениуса гарантирует существование $\pi$. Если цепь неприводима - $\pi$ единственно. Если ещё и апериодична (то есть $P$ примитивна) - для любого начального распределения $\mu_0$ итерации $\mu_k = \mu_0 P^k$ сходятся к $\pi$. Это и есть теорема об эргодичности.

PageRank и веб-граф

Алгоритм Сергея Брина и Ларри Пейджа сводится к собственному вектору для $\rho = 1$ матрицы

$$M = d\, A^T D^{-1} + \frac{1-d}{n}\, J$$

где $A$ - матрица смежности веб-графа, $D$ - диагональная матрица из исходящих степеней, $d \approx 0{,}85$ - коэффициент демпфирования, $J$ - матрица из единиц. Слагаемое $(1-d)/n \cdot J$ делает $M$ строго положительной - а значит примитивной, и пункт (4) теоремы гарантирует сходимость степенного метода $x_{k+1} = M x_k$ к единственному положительному собственному вектору. Без демпфирования (при $d = 1$) матрица могла бы оказаться приводимой - застрявшие в «висячих» страницах потоки нарушали бы единственность.

Скорость сходимости определяется отношением $|\lambda_2|/\rho(M)$, где $\lambda_2$ - второе по модулю собственное число. Для типичного веб-графа это отношение около 0,85 - отсюда «магическое» значение $d$.

Модель Лесли в демографии

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

$$L = \begin{pmatrix} f_1 & f_2 & \cdots & f_n \\ s_1 & 0 & \cdots & 0 \\ 0 & s_2 & \cdots & 0 \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & 0 \end{pmatrix}$$

где $f_i \geq 0$ - плодовитость возрастной группы $i$, $s_i \in (0, 1]$ - вероятность дожития до следующей группы. Матрица неотрицательна; неприводима, если есть хотя бы две ненулевые $f_i$ с взаимно простыми индексами (иначе циклы имеют общий делитель и матрица периодическая, а не примитивная).

Спектральный радиус $\rho(L)$ интерпретируется как асимптотическая скорость роста популяции - при $\rho > 1$ популяция растёт экспоненциально, при $\rho < 1$ вымирает, при $\rho = 1$ стабильна. Соответствующий положительный собственный вектор $v$ - асимптотическое возрастное распределение, к которому популяция сходится независимо от начального состава. Это уравнение Эйлера-Лотки в матричной форме.

Частые ошибки

• Путают «неотрицательный» и «положительный». Теорема Перрона (1907) для $A > 0$ - это частный случай; Фробениус расширил её на $A \geq 0$. Свойство «собственный вектор строго положителен» требует именно неприводимости - для просто неотрицательной матрицы вектор может быть с нулями.
• Применяют пункт (4) без проверки примитивности. Перестановочная матрица $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ имеет $\rho = 1$ и второе собственное число $-1$ того же модуля. Итерации не сходятся к одному направлению - осциллируют. Доминирование $\rho(A)$ требует апериодичности.
• Считают $\rho(A)$ простой через определитель. Простота собственного числа - это его алгебраическая кратность как корня характеристического полинома. Через определитель не проверить; стандартный приём - проверить, что $\det(A - \rho(A) I) = 0$, но $\det'(A - \rho I) \neq 0$ при $\rho = \rho(A)$.
• Забывают проверить неприводимость через граф. В задачах с большой $n$ глазом не видно, а блочно-треугольный вид может скрываться за перестановкой строк/столбцов. Проверка через сильную связность графа смежности - обязательный этап.

FAQ

Чем теорема Перрона отличается от теоремы Фробениуса? Перрон (1907) доказал утверждение для строго положительных матриц $A > 0$: $\rho(A)$ - простое собственное число, единственное по модулю, собственный вектор строго положителен. Фробениус (1912) ослабил гипотезу до $A \geq 0$ - но взамен добавил условия неприводимости (для единственности и положительности вектора) и примитивности (для доминирования). В современной литературе их объединяют под одним именем - теорема Перрона-Фробениуса.

Зачем нужны левые собственные векторы - раз есть правые? Правый собственный вектор $v$ ($Av = \rho v$) описывает асимптотическое направление итераций, левый $w^T$ ($w^T A = \rho w^T$) - проекцию начального вектора на это направление. В цепях Маркова стационарное распределение - это именно левый собственный вектор стохастической матрицы. Оба существуют по теореме, единственны при неприводимости и связаны нормализацией $w^T v = 1$.

Можно ли применять теорему к матрицам с отрицательными элементами? Напрямую - нет. Но если матрица $B$ имеет неотрицательную структуру по модулю ($|B|_{ij} = |b_{ij}|$), то $\rho(B) \leq \rho(|B|)$ - это уже следствие, не сама теорема. Для знакопеременных матриц используют обобщения вроде теоремы Виландта или подходы через положительные обратные.

Коротко

Теорема Перрона-Фробениуса даёт неотрицательной матрице $A$ привилегированное собственное число $\rho(A)$ с неотрицательным собственным вектором. Для неприводимой матрицы $\rho(A)$ простое и вектор строго положителен. Для примитивной - $\rho(A)$ строго доминирует по модулю, что гарантирует сходимость степенного метода. Эти три уровня - неотрицательность, неприводимость, примитивность - определяют, какой из выводов вы вправе делать. Стационарные распределения цепей Маркова, PageRank, асимптотика модели Лесли - всё это один и тот же спектральный результат под разными вывесками.