Теорема Перрона – Фробениуса

В теории матриц теорема Перрона -Фробениуса , доказанная Оскаром Перроном ( 1907 ) и Георгом Фробениусом ( 1912 ), утверждает, что действительная квадратная матрица с положительными элементами имеет уникальное собственное значение наибольшей величины и что собственное значение действительно. Соответствующий собственный вектор может быть выбран так, чтобы иметь строго положительные компоненты, а также утверждает аналогичное утверждение для определенных классов неотрицательных матриц . Эта теорема имеет важные приложения к теории вероятностей ( эргодичность ) цепей Маркова ; к теории динамических систем ( подсдвигам конечного типа ); в экономику ( теорема Окисио , Условие Хокинса-Саймона ); демографии ( модель возрастного распределения населения Лесли ); в социальные сети ( процесс обучения DeGroot ); в поисковые системы Интернета ( PageRank ); и даже к рейтингу американского футбола команды. Первым, кто обсудил порядок расположения игроков в турнирах с использованием собственных векторов Перрона-Фробениуса, является Эдмунд Ландау .

Заявление

Пусть положительные и неотрицательные соответственно описывают матрицы с исключительно положительными действительными числами в качестве элементов и матрицы с исключительно неотрицательными действительными числами в качестве элементов. Собственные значения действительной квадратной матрицы A представляют собой комплексные числа , составляющие спектр матрицы. Экспоненциальная скорость роста матричных степеней A ^к при k → ∞ контролируется собственным значением A с наибольшим абсолютным значением ( модулем ). Теорема Перрона-Фробениуса описывает свойства главного собственного значения и соответствующих собственных векторов, когда A является неотрицательной действительной квадратной матрицей. Первые результаты были получены Оскаром Перроном ( 1907 ) и касались положительных матриц. Позднее Георг Фробениус ( 1912 ) нашел их распространение на некоторые классы неотрицательных матриц.

Положительные матрицы

Позволять $A=(a_{ij})$ быть $n\times n$ положительная матрица: $a_{ij}>0$ для $1\leq i,j\leq n$. Тогда справедливы следующие утверждения.

1. Существует положительное действительное число r , называемое корнем Перрона или собственным значением Перрона-Фробениуса (также называемое ведущим собственным значением , главным собственным значением или доминирующим собственным значением ), такое, что r является собственным значением A и любым другим собственным значением λ (возможно, комплексным ) в абсолютное значение строго меньше r , | λ | < р . Таким образом, спектральный радиус $\rho (A)$ равен р . Если матричные коэффициенты являются алгебраическими, это означает, что собственное значение является числом Перрона .
2. простое: r является простым корнем характеристического многочлена A Собственное значение Перрона- Фробениуса . Следовательно, собственное пространство, связанное с r , одномерно. (То же самое верно и для левого собственного пространства, т. е. собственного пространства для A ^Т , транспонирование A .)
3. Существует собственный вектор v = ( v ₁ ,..., v _n ) ^Т A таким с собственным значением r , что все компоненты v положительны: A v = rv , vi _> 0 для 1 ≤ i ≤ n . (Соответственно существует положительный левый собственный вектор w : w ^Т А = ш ^Т r, w _i > 0.) Он известен в литературе во многих вариациях как вектор Перрона , собственный вектор Перрона , собственный вектор Перрона-Фробениуса , ведущий собственный вектор , главный собственный вектор или доминирующий собственный вектор .
4. Других положительных (тем более неотрицательных) собственных векторов, кроме положительных кратных v (соответственно левых собственных векторов, кроме ww'w ), нет, т. е. все остальные собственные векторы должны иметь хотя бы одну отрицательную или невещественную компоненту.
5. $\lim _{k\rightarrow \infty }A^{k}/r^{k}=vw^{T}$, где левый и правый собственные векторы A нормированы так, что w ^Т v = 1. Более того, матрица vw ^Т — проекция на собственное пространство, соответствующее r . Эта проекция называется проекцией Перрона .
6. Коллатца Формула – Виланда : для всех неотрицательных ненулевых векторов x пусть f ( x ) будет минимальным значением [ Ax ] _i / x _i, взятым для всех тех i, таких что x _i ≠ 0. Тогда f является действительным значная функция, максимум которой по всем неотрицательным ненулевым векторам x является собственным значением Перрона – Фробениуса.
7. Формула Коллатца-Виландта «Мин-макс» принимает форму, аналогичную приведенной выше: для всех строго положительных векторов x пусть g ( x ) будет максимальным значением [ Ax ] _i / x _{i ,} взятым по i . Тогда g — вещественная функция, минимум которой по всем строго положительным векторам x является собственным значением Перрона – Фробениуса.
8. Биркгофа – Варги Формула : пусть x и y — строго положительные векторы. Затем, $$r=\sup _{x>0}\inf _{y>0}{\frac {y^{\top }Ax}{y^{\top }x}}=\inf _{x>0}\sup _{y>0}{\frac {y^{\top }Ax}{y^{\top }x}}=\inf _{x>0}\sup _{y>0}\sum _{i,j=1}^{n}y_{i}a_{ij}x_{j}/\sum _{i=1}^{n}y_{i}x_{i}.$$
9. Донскера – Варадана – Фридланда Формула : Пусть p — вектор вероятности, а x — строго положительный вектор. Затем, $$r=\sup _{p}\inf _{x>0}\sum _{i=1}^{n}p_{i}[Ax]_{i}/x_{i}.$$
10. Фидлера Формула : $$r=\sup _{z>0}\ \inf _{x>0,\ y>0,\ x\circ y=z}{\frac {y^{\top }Ax}{y^{\top }x}}=\sup _{z>0}\ \inf _{x>0,\ y>0,\ x\circ y=z}\sum _{i,j=1}^{n}y_{i}a_{ij}x_{j}/\sum _{i=1}^{n}y_{i}x_{i}.$$
11. Собственное значение Перрона – Фробениуса удовлетворяет неравенствам $$\min _{i}\sum _{j}a_{ij}\leq r\leq \max _{i}\sum _{j}a_{ij}.$$

Все эти свойства распространяются за пределы строго положительных матриц на примитивные матрицы (см. Ниже). Факты 1–7 можно найти у Мейера. глава 8 утверждает 8.2.11–15, стр. 667 и упражнения 8.2.5,7,9, стр. 668–669.

Левый и правый собственные векторы w и v иногда нормируются так, что сумма их компонент равна 1; в этом случае их иногда называют стохастическими собственными векторами . Часто они нормируются так, что сумма правого собственного вектора v равна единице, а $w^{T}v=1$.

Неотрицательные матрицы

Существует расширение матриц с неотрицательными элементами. Поскольку любую неотрицательную матрицу можно получить как предел положительных матриц, получается существование собственного вектора с неотрицательными компонентами; соответствующее собственное значение будет неотрицательным и больше или равно по абсолютной величине всем остальным собственным значениям. Однако для примера $A=\left({\begin{smallmatrix}0&1\\1&0\end{smallmatrix}}\right)$максимальное собственное значение r = 1 имеет то же абсолютное значение, что и другое собственное значение −1; в то время как для $A=\left({\begin{smallmatrix}0&1\\0&0\end{smallmatrix}}\right)$максимальное собственное значение равно r = 0, что не является простым корнем характеристического многочлена, а соответствующий собственный вектор (1, 0) не является строго положительным.

Однако Фробениус обнаружил специальный подкласс неотрицательных матриц — неприводимые матрицы, — для которых возможно нетривиальное обобщение. Для такой матрицы, хотя собственные значения, достигающие максимального абсолютного значения, могут быть неединственными, их структура находится под контролем: они имеют вид $\omega r$, где $r$ является действительным строго положительным собственным значением, и $\omega$ пробегает комплексные корни h'-й степени из 1 для некоторого положительного целого числа h, называемого периодом матрицы. Собственный вектор, соответствующий $r$ имеет строго положительные компоненты (в отличие от общего случая неотрицательных матриц, где компоненты только неотрицательны). Кроме того, все такие собственные значения являются простыми корнями характеристического многочлена. Дополнительные свойства описаны ниже.

Классификация матриц

Пусть A — квадратная n × n над полем F. матрица размера Матрица A неприводима , если любое из следующих эквивалентных свойств держит.

Определение 1: A не имеет нетривиальных инвариантных координатных подпространств. Здесь нетривиальное координатное подпространство означает линейное подпространство , натянутое на любое собственное подмножество стандартных базисных векторов F ^н . Более явно, для любого линейного подпространства, натянутого на стандартные базисные векторы e _{i 1} , ..., e _{i k} , 0 < k < n, его образ под действием A не содержится в том же подпространстве.

Определение 2: A не может быть сопряжено в блочную верхнетреугольную форму с помощью матрицы перестановок P :

$PAP^{-1}\neq {\begin{pmatrix}E&F\\O&G\end{pmatrix}},$

где E и G — нетривиальные (т.е. размера больше нуля) квадратные матрицы.

Определение 3: можно сопоставить Матрице A некоторый ориентированный граф G _A . Она имеет n вершин, помеченных 1,..., n существует ребро от вершины i до вершины j именно тогда, когда a _ij ≠ 0. Тогда матрица A неприводима тогда и только тогда, когда связанный с ней граф GA _{, и} связен сильно .

Если F — поле действительных или комплексных чисел, то мы также имеем следующее условие.

4: Групповое представление Определение $(\mathbb {R} ,+)$ на $\mathbb {R} ^{n}$ или $(\mathbb {C} ,+)$ на $\mathbb {C} ^{n}$ данный $t\mapsto \exp(tA)$ не имеет нетривиальных инвариантных координатных подпространств. (Для сравнения: это было бы неприводимое представление , если бы вообще не существовало нетривиальных инвариантных подпространств, не только с учетом координатных подпространств.)

Матрица является приводимой , если она не является неприводимой.

Действительная матрица A является примитивной , если она неотрицательна и ее m -я степень положительна для некоторого натурального числа m (т. е. все элементы матрицы A ^м положительны).

Пусть А вещественно и неотрицательно. Зафиксируйте индекс i и определите период индекса i как наибольший общий делитель всех натуральных чисел m таких, что ( A ^м ) _ii > 0. Когда A неприводим, период каждого индекса одинаков и называется периодом A . Фактически, когда A неприводим, период можно определить как наибольший общий делитель длин замкнутых направленных путей в G _A (см. Кухни стр. 16). Этот период еще называют индексом импримитивности (Мейер стр. 674) или порядок цикличности. Если период равен 1, A является апериодическим . Можно доказать, что примитивные матрицы — это то же самое, что и неприводимые апериодические неотрицательные матрицы.

Все утверждения теоремы Перрона–Фробениуса для положительных матриц остаются верными и для примитивных матриц. Те же утверждения справедливы и для неотрицательной неприводимой матрицы, за исключением того, что она может иметь несколько собственных значений, абсолютное значение которых равно ее спектральному радиусу, поэтому утверждения необходимо соответствующим образом изменить. Фактически число таких собственных значений равно периоду.

Результаты для неотрицательных матриц были впервые получены Фробениусом в 1912 году.

Теорема Перрона–Фробениуса для неприводимых неотрицательных матриц.

Позволять $A$ быть неприводимым неотрицательным $N\times N$ матрица с периодом $h$ и спектральный радиус $\rho (A)=r$. Тогда справедливы следующие утверждения.

• Число $r\in \mathbb {R} ^{+}$ - положительное действительное число и собственное значение матрицы $A$. Оно называется собственным значением Перрона-Фробениуса .
• Собственное значение Перрона – Фробениуса. $r$ это просто . Как правое, так и левое собственное пространство, связанное с $r$ являются одномерными.
• $A$ имеет как правый, так и левый собственные векторы соответственно $\mathbf {v}$ и $\mathbf {w}$, с собственным значением $r$ и все компоненты которого положительны. Более того, это единственные собственные векторы, все компоненты которых положительны, - это те, которые связаны с собственным значением. $r$.
• Матрица $A$ имеет точно $h$ (где $h$ — период ) комплексные собственные значения с абсолютным значением $r$. Каждый из них представляет собой простой корень характеристического многочлена и является произведением $r$ с $h$корень единства .
• Позволять $\omega =2\pi /h$. Тогда матрица $A$ похоже ​ на $e^{i\omega }A$, следовательно, спектр $A$ инвариантен относительно умножения на $e^{i\omega }$ (т.е. к поворотам комплексной плоскости на угол $\omega$).
• Если $h>1$ тогда существует матрица перестановок $P$ такой, что

$PAP^{-1}={\begin{pmatrix}O&A_{1}&O&O&\ldots &O\\O&O&A_{2}&O&\ldots &O\\\vdots &\vdots &\vdots &\vdots &&\vdots \\O&O&O&O&\ldots &A_{h-1}\\A_{h}&O&O&O&\ldots &O\end{pmatrix}},$

где $O$ обозначает нулевую матрицу, а блоки вдоль главной диагонали являются квадратными матрицами.

• Коллатца Формула – Виланда : для всех неотрицательных ненулевых векторов $\mathbf {x}$ позволять $f(\mathbf {x} )$ быть минимальным значением $[A\mathbf {x} ]_{i}/x_{i}$ взял на себя все эти $i$ такой, что $x_{i}\neq 0$. Затем $f$ – вещественная функция, максимум которой является собственным значением Перрона – Фробениуса.

• Собственное значение Перрона – Фробениуса удовлетворяет неравенствам

$\min _{i}\sum _{j}a_{ij}\leq r\leq \max _{i}\sum _{j}a_{ij}.$

Пример $A=\left({\begin{smallmatrix}0&0&1\\0&0&1\\1&1&0\end{smallmatrix}}\right)$ показывает, что (квадратные) нулевые матрицы по диагонали могут иметь разные размеры, блоки A _j не обязательно должны быть квадратными, а h не обязательно делить n .

Дополнительные свойства

Пусть A — неприводимая неотрицательная матрица, тогда:

1. (Я+ А ) ^{п -1} является положительной матрицей. (Мейер претензия 8.3.5п. 672 ). Для неотрицательного A это также достаточное условие.
2. Теорема Виланда. Если | B |< A , тогда ρ ( B )≤ ρ ( A ). Если имеет место равенство (т.е. если µ=ρ(A)e ^iφ является собственным значением для B ), то B = e ^iφ ПАПА ⁻¹ для некоторой диагональной унитарной матрицы D (т.е. диагональные элементы D равны e ^{я _л} , недиагональные равны нулю).
3. Если некоторая мощность А ^д приводима, то она полностью приводима, т. е. для некоторой матрицы перестановок P верно, что: $PA^{q}P^{-1}={\begin{pmatrix}A_{1}&O&O&\dots &O\\O&A_{2}&O&\dots &O\\\vdots &\vdots &\vdots &&\vdots \\O&O&O&\dots &A_{d}\\\end{pmatrix}}$, где A _i — неприводимые матрицы, имеющие одинаковое максимальное собственное значение. Число этих матриц d является наибольшим общим делителем q и h , где — период A. h
4. Если c ( x ) = x ^н + _{ск 1} х ^{например ₁} + _{ск 2} х ^{нк ₂} + ... + c _{k s} x ^{с _нк} является характеристическим полиномом A , в котором перечислены только ненулевые члены, то период A равен наибольшему общему делителю k ₁ , k ₂ , ... , k _s .
5. Чезаро В среднем : $\lim _{k\rightarrow \infty }1/k\sum _{i=0,...,k}A^{i}/r^{i}=(vw^{T}),$ где левый и правый собственные векторы A нормированы так, что w ^Т v = 1. Более того, матрица vw ^Т — спектральная проекция, соответствующая r , проекция Перрона.
6. Пусть r будет собственным значением Перрона – Фробениуса, тогда присоединенная матрица для ( r - A ) положительна.
7. Если A имеет хотя бы один ненулевой диагональный элемент, то A примитивен.
8. Если 0 ⩽ A < B , то r _A ⩽ r _B. Более того, если B неприводима, то неравенство строгое: r _A < r _B .

Матрица A является примитивной, если она неотрицательна и A ^м положительна для некоторого m и, следовательно, A ^к положителен для всех k ≥ m . Чтобы проверить примитивность, нужно оценить, насколько большим может быть минимальное такое m в зависимости от размера A :

• Если A — неотрицательная примитивная матрица размера n , то A ^{н 2 − 2n + 2} является положительным. Более того, это наилучший результат, поскольку для приведенной ниже матрицы M степень M ^к не является положительным для любого k < n ² − 2 n + 2, так как ( M ^{н 2 − 2 н +1} ) _1,1 = 0.

$M=\left({\begin{smallmatrix}0&1&0&0&\cdots &0\\0&0&1&0&\cdots &0\\0&0&0&1&\cdots &0\\\vdots &\vdots &\vdots &\vdots &&\vdots \\0&0&0&0&\cdots &1\\1&1&0&0&\cdots &0\end{smallmatrix}}\right)$

Приложения

По теме неотрицательных матриц написано множество книг, и теория Перрона-Фробениуса неизменно занимает центральное место. Следующие примеры, приведенные ниже, лишь поверхностно касаются обширной области его применения.

Неотрицательные матрицы

Теорема Перрона-Фробениуса не применима напрямую к неотрицательным матрицам. Тем не менее, любая приводимая квадратная матрица A может быть записана в верхнетреугольной блочной форме (известной как нормальная форма приводимой матрицы ).

ПАП ⁻¹ = $\left({\begin{smallmatrix}B_{1}&*&*&\cdots &*\\0&B_{2}&*&\cdots &*\\\vdots &\vdots &\vdots &&\vdots \\0&0&0&\cdots &*\\0&0&0&\cdots &B_{h}\end{smallmatrix}}\right)$

где P — матрица перестановок, а каждая B _i — квадратная матрица, которая либо неприводима, либо равна нулю. если А Теперь , неотрицательен, то и каждый блок PAP тоже ⁻¹ , более того, спектр A представляет собой просто объединение спектров Б _я .

Обратимость A также можно изучить. Обратный вариант ПАП ⁻¹ (если он существует) должен иметь диагональные блоки вида B _i ⁻¹ так что если есть B _i не является обратимым, то и PAP не является обратимым. ⁻¹ или А. ​ Обратно, пусть D будет блочно-диагональной матрицей, соответствующей PAP. ⁻¹ другими словами ПАП ⁻¹ с звездочки обнулены. Если каждый B _i обратим, то обратимы также D и D. ⁻¹ ( ПАП ⁻¹ ) равен тождество плюс нильпотентная матрица. Но такая матрица всегда обратима (если N ^к = 0 обратное число 1 − N равно 1 + Н + Н ² + ... + Н ^{к -1} ) так что ПАП ⁻¹ и A оба обратимы.

Следовательно, многие спектральные свойства A можно вывести, применив теорему к неприводимому B _i . Например, корень Перрона является максимумом ρ( B _i ). Хотя собственные векторы с неотрицательными компонентами все равно будут, это вполне возможно. что ни один из них не будет положительным.

Стохастические матрицы

строка (столбец) Стохастическая матрица — это квадратная матрица, каждая строка (столбец) которой состоит из неотрицательных действительных чисел, сумма которых равна единице. Теорему нельзя применить непосредственно к таким матрицам, поскольку они не обязательно должны быть неприводимыми.

Если A является стохастическим по строкам, то вектор-столбец с каждой записью 1 является собственным вектором, соответствующим собственному значению 1, которое также является ρ( A ) согласно замечанию выше. Возможно, это не единственное собственное значение единичного круга: и связанное с ним собственное пространство может быть многомерным. Если A стохастическая по строкам и неприводимая, то проекция Перрона также стохастическая по строкам и все ее строки равны.

Алгебраическая теория графов

Теорема имеет особое применение в алгебраической теории графов . «Основной граф» неотрицательной n -квадратной матрицы - это граф с вершинами с номерами 1,..., n и дугой ij тогда и только тогда, когда A _ij ≠ 0. Если основной граф такой матрицы сильно связен, то матрица неприводима, и, следовательно, теорема применима. В частности, матрица смежности неприводима сильно связного графа .

Конечные цепи Маркова

Теорема имеет естественную интерпретацию в теории конечных цепей Маркова (где она является теоретико-матричным эквивалентом сходимости неприводимой конечной цепи Маркова к ее стационарному распределению, сформулированному в терминах матрицы перехода цепи; см., например, например, статья о подсдвиге конечного типа ).

Компактные операторы

Основная статья: теорема Крейна – Рутмана

В более общем смысле его можно распространить на случай неотрицательных компактных операторов , которые во многом напоминают конечномерные матрицы. Они обычно изучаются в физике под названием операторов переноса или иногда операторов Рюэля-Перрона-Фробениуса (в честь Дэвида Рюэля ). В этом случае главное собственное значение соответствует термодинамическому равновесию динамической системы , а меньшие собственные значения — режимам распада системы, не находящейся в равновесии. Таким образом, теория предлагает способ обнаружить стрелу времени в том, что в противном случае могло бы показаться обратимыми, детерминированными динамическими процессами, если рассматривать их с точки зрения топологии множества точек .

Методы доказательства

Общей нитью во многих доказательствах является теорема Брауэра о неподвижной точке . Другой популярный метод — метод Виландта (1950). Он использовал описанную выше формулу Коллатца -Виланда, чтобы расширить и уточнить работу Фробениуса. Другое доказательство основано на спектральной теории. откуда заимствована часть аргументов.

Корень Перрона - это строго максимальное собственное значение для положительных (и примитивных) матриц.

Если A - положительная (или, в более общем смысле, примитивная) матрица, то существует действительное положительное собственное значение r (собственное значение Перрона – Фробениуса или корень Перрона), которое по абсолютной величине строго больше, чем все другие собственные значения, следовательно, r - это спектральный радиус А. ​

Это утверждение не справедливо для общих неотрицательных неприводимых матриц, которые имеют h собственных значений с тем же абсолютным собственным значением, что и r , где h - период A .

Доказательство положительных матриц

Пусть A — положительная матрица, предположим, что ее спектральный радиус ρ( A ) = 1 (в противном случае рассмотрим A/ρ(A) ). Следовательно, на единичной окружности существует собственное значение λ, а все остальные собственные значения по абсолютной величине меньше или равны 1. Предположим, что еще одно собственное значение λ ≠ 1 также попадает на единичную окружность. Тогда существует целое положительное число m такое, что A ^м — положительная матрица, а действительная часть λ ^м является отрицательным. Пусть ε — половина наименьшего диагонального элемента A ^м и положим T = A ^м − εI , что является еще одной положительной матрицей. Более того, если Ax = λx , то A ^м х = λ ^м x, таким образом, λ ^м − ε — собственное значение T . Из-за выбора m эта точка лежит вне единичного круга, следовательно, ρ ( T ) > 1. С другой стороны, все элементы в T положительны и меньше или равны элементам в A. ^м поэтому по формуле Гельфанда ρ ( T ) ≤ ρ ( A ^м ) ≤ ρ ( А ) ^м = 1. Это противоречие означает, что λ=1 и на единичной окружности не может быть других собственных значений.

Совершенно те же рассуждения можно применить и к случаю примитивных матриц; нам достаточно упомянуть следующую простую лемму, проясняющую свойства примитивных матриц.

Лемма

Учитывая неотрицательное значение A , предположим, что существует m такое, что A ^м положительно, то A ^{м +1} , А ^{м +2} , А ^{м +3} ,... все положительные.

А ^{м +1} = АА ^м , поэтому он может иметь нулевой элемент только в том случае, если какая-то строка A полностью равна нулю, но в этом случае та же строка A ^м будет нулевым.

Применяя те же рассуждения, что и выше для примитивных матриц, докажите основное утверждение.

Степенной метод и положительная собственная пара

Для положительной (или, в более общем смысле, неприводимой неотрицательной) матрицы A доминирующий собственный вектор веществен и строго положителен (для неотрицательной A соответственно неотрицательен).

Это можно установить с помощью степенного метода , который утверждает, что для достаточно общей (в смысле ниже) матрицы A последовательность векторов b _{k +1} = Ab _k / | Аб _к | сходится к собственному вектору с максимальным собственным значением . (Начальный вектор b ₀ может быть выбран произвольно, за исключением некоторого множества нулевой меры). Начиная с неотрицательного вектора b _0, создается последовательность неотрицательных векторов b _k . Следовательно, предельный вектор также неотрицательен. По степенному методу этот предельный вектор является доминирующим собственным вектором для A , что доказывает утверждение. Соответствующее собственное значение неотрицательно.

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

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

Лемма: если задана положительная (или, в более общем случае, неприводимая неотрицательная) матрица A и v как любой неотрицательный собственный вектор для A , то она обязательно строго положительна, и соответствующее собственное значение также строго положительно.

Доказательство. Одно из определений неприводимости неотрицательных матриц состоит в том, что для всех индексов i,j существует m такое, что ( A ^м ) _ij строго положителен. Учитывая неотрицательный собственный вектор v и что хотя бы один из его компонентов говорит, что j -th строго положителен, соответствующее собственное значение действительно строго положительно, если n такое, что ( A ^н ) _ii >0, следовательно: r ^н v _и = И ^н v _и ≥ ( А ^н ) _ii v _я >0. Следовательно, r строго положительно. Собственный вектор является строгой положительностью. Тогда дано m такое, что ( A ^м ) _ij >0, следовательно: r ^м v _j = ( А ^м v ) _j ≥ ( А ^м ) _ij v _i >0, следовательно v _j строго положителен, т. е. собственный вектор строго положителен.

Кратность один

В этом разделе доказывается, что собственное значение Перрона – Фробениуса является простым корнем характеристического многочлена матрицы. Следовательно, собственное пространство, связанное с собственным значением Перрона – Фробениуса r, является одномерным. Аргументы здесь близки к аргументам Мейера.

Дан строго положительный собственный вектор v, соответствующий r , и другой собственный вектор w с тем же собственным значением. (Векторы v и w могут быть выбраны вещественными, поскольку A и r оба вещественны, поэтому нулевое пространство Ar имеет основу, состоящую из вещественных векторов.) Предполагая, что хотя бы один из компонентов w положителен (в противном случае умножьте w на −1). Если задан максимально возможный α такой, что u=v-αw неотрицательен, то один из компонентов u равен нулю, в противном случае α не является максимальным. Вектор u является собственным вектором. Он неотрицательен, следовательно, по лемме, описанной в предыдущем разделе, из неотрицательности следует строгая положительность для любого собственного вектора. С другой стороны, как указано выше, по крайней мере один компонент u равен нулю. Противоречие означает, что w не существует.

Случай: не существует жордановых ячеек, соответствующих собственному значению Перрона – Фробениуса r и всем другим собственным значениям, имеющим то же абсолютное значение.

Если есть жорданова ячейка, то норма бесконечности (А/р) ^к _∞ стремится к бесконечности при k → ∞ , но это противоречит существованию положительного собственного вектора.

Учитывая r = 1 или A/r . Полагая v строго положительным собственным вектором Перрона–Фробениуса, поэтому Av=v , тогда:

$\|v\|_{\infty }=\|A^{k}v\|_{\infty }\geq \|A^{k}\|_{\infty }\min _{i}(v_{i}),~~\Rightarrow ~~\|A^{k}\|_{\infty }\leq \|v\|/\min _{i}(v_{i})$ Итак, А ^к _∞ ограничено для всех k . Это дает еще одно доказательство того, что не существует собственных значений, которые имели бы большее абсолютное значение, чем значение Перрона – Фробениуса. Это также противоречит существованию жордановой ячейки для любого собственного значения, имеющего модуль, равный 1 (в частности, для числа Перрона–Фробениуса), поскольку из существования жордановой ячейки следует, что A ^к _∞ неограничен. Для матрицы два на два:

$J^{k}={\begin{pmatrix}\lambda &1\\0&\lambda \end{pmatrix}}^{k}={\begin{pmatrix}\lambda ^{k}&k\lambda ^{k-1}\\0&\lambda ^{k}\end{pmatrix}},$

следовательно, Дж ^к _∞ = | к + λ | (для | λ | = 1), поэтому он стремится к бесконечности, когда k это делает. Поскольку Дж ^к = С ⁻¹ А ^к С , затем А ^к ≥ Дж ^к / ( С ⁻¹ C ), поэтому оно также стремится к бесконечности. Полученное противоречие означает, что для соответствующих собственных значений не существует жордановых клеток.

Объединение двух приведенных выше утверждений показывает, что собственное значение Перрона – Фробениуса r является простым корнем характеристического многочлена. В случае непримитивных матриц существуют другие собственные значения, имеющие то же абсолютное значение, что и r . То же утверждение справедливо и для них, но требует дополнительной работы.

Никаких других неотрицательных собственных векторов.

Учитывая положительную (или, в более общем случае, неприводимую неотрицательную матрицу) A собственный вектор Перрона-Фробениуса является единственным (с точностью до умножения на константу) неотрицательным собственным вектором для A .

Другие собственные векторы должны содержать отрицательные или комплексные компоненты, поскольку собственные векторы для разных собственных значений в некотором смысле ортогональны, но два положительных собственных вектора не могут быть ортогональными, поэтому они должны соответствовать одному и тому же собственному значению, но собственное пространство для Перрона – Фробениуса одномерно.

Предполагая, что существует собственная пара ( λ , y ) для A , такая что вектор y положителен, и задано ( r , x ), где x – левый собственный вектор Перрона – Фробениуса для A (т.е. собственный вектор для A ^Т ), затем прием ^Т у = ( х ^Т А ) у = х ^Т ( Is ) = λx ^Т у , также х ^Т y > 0, поэтому имеем: r = λ . Поскольку собственное пространство для собственного значения Перрона – Фробениуса r одномерно, неотрицательный собственный вектор y кратен вектору Перрона – Фробениуса.

Формула Коллатца – Виланда

Учитывая положительную (или, в более общем смысле, неприводимую неотрицательную матрицу) A , можно определить функция f на множестве всех неотрицательных ненулевых векторов x таких, что f(x) — минимальное значение [ Ax ] _i / x _i, взятое по всем таким i , что x _i ≠ 0. Тогда f является вещественная функция, максимум которой является собственным значением Перрона – Фробениуса r .

Для доказательства мы обозначим максимум f значением R . Для доказательства требуется показать R = r . Подставляя собственный вектор Перрона-Фробениуса v в f , мы получаем f(v) = r и заключаем, что r ≤ R. Для противоположного неравенства рассмотрим произвольный неотрицательный вектор x и положим ξ=f(x) . Определение f дает 0 ⩽ ξx ⩽ Ax (покомпонентно). Теперь мы используем положительный правый собственный вектор w для A для собственного значения Перрона-Фробениуса r , тогда ξ w ^Т х = ш ^Т ξx ≤ w ^Т (Ax) = (w ^Т А)x = rw ^Т х . Следовательно, f(x) = ξ ≤ r , откуда следует р ≤ р .

Проекция Перрона как предел: A ^к / р ^к

Пусть A — положительная (или, в более общем смысле, примитивная) матрица, и пусть r — ее собственное значение Перрона–Фробениуса.

1. Существует предел A ^к /р ^к для k → ∞ его через P. обозначим
2. P — оператор проектирования : P ² = P , который коммутирует с A : AP = PA .
3. Образ P одномерен и натянут на собственный вектор Перрона–Фробениуса v (соответственно для P ^Т — собственным вектором Перрона–Фробениуса w для A ^Т ).
4. P = vw ^Т , где v,w нормированы так, что w ^Т v = 1.
5. Следовательно, P — положительный оператор.

Следовательно, P является спектральной проекцией для собственного значения Перрона – Фробениуса r и называется проекцией Перрона. Приведенное выше утверждение неверно для общих неотрицательных неприводимых матриц.

На самом деле приведенные выше утверждения (кроме утверждения 5) справедливы для любой матрицы M такой, что существует собственное значение r , которое строго больше других собственных значений по абсолютной величине и является простым корнем характеристического многочлена . (Эти требования справедливы для примитивных матриц, как указано выше).

Учитывая, что M диагонализуема, M сопряжена диагональной матрице с собственными значениями r ₁ , ... , r _n на диагонали (обозначим r ₁ = r ). Матрица М ^к / р ^к будет сопряжено (1, ( r ₂ / r ) ^к , ... , ( р _н / р ) ^к ), который стремится к (1,0,0,...,0) при k → ∞ , поэтому предел существует. Тот же метод работает для общего M (без предположения, что M диагонализуемо).

Свойства проекции и коммутативности являются элементарными следствиями определения: MM ^к / р ^к = М ^к / р ^к М ; П ² = Лим М ^{22 тыс.} / р ^{22 тыс.} = П. ​Третий факт также элементарен: M ( Pu ) = M lim M ^к / р ^к u = клей rM ^{к +1} / р ^{к +1} u , поэтому переход к пределу дает M ( Pu ) = r ( Pu ), поэтому образ P лежит в r -собственном пространстве для M , которое по предположениям является одномерным.

Обозначая через v , r -собственный вектор для M (через w для M ^Т ). Столбцы P кратны v , потому что изображение P охватывается им. Соответственно, строки w . Таким образом, P принимает форму (avw ^Т ) , для некоторых a . Следовательно, его след равен (aw ^Т в) . След проектора равен размеру его изображения. Ранее было доказано, что оно не более чем одномерно. Из определения видно, что P действует тождественно на r -собственный вектор M . Так что это одномерно. Итак, выбрав ( w ^Т v ) = 1, следует P = vw ^Т .

Неравенства для собственного значения Перрона – Фробениуса

Для любой неотрицательной матрицы A ее собственное значение Перрона – Фробениуса r удовлетворяет неравенству:

$r\;\leq \;\max _{i}\sum _{j}a_{ij}.$

Это не характерно для неотрицательных матриц: для любой матрицы A с собственным значением $\scriptstyle \lambda$ это правда что $\scriptstyle |\lambda |\;\leq \;\max _{i}\sum _{j}|a_{ij}|$. Это является непосредственным следствием Теорема Гершгорина об окружности . Однако другое доказательство более прямое:

Любая матричная индуцированная норма удовлетворяет неравенству $\scriptstyle \|A\|\geq |\lambda |$ для любого собственного значения $\scriptstyle \lambda$ потому что, если $\scriptstyle x$ - соответствующий собственный вектор, $\scriptstyle \|A\|\geq |Ax|/|x|=|\lambda x|/|x|=|\lambda |$. Норма бесконечности матрицы — это максимум сумм строк: $\scriptstyle \left\|A\right\|_{\infty }=\max \limits _{1\leq i\leq m}\sum _{j=1}^{n}|a_{ij}|.$ Следовательно, искомое неравенство в точности равно $\scriptstyle \|A\|_{\infty }\geq |\lambda |$ применяется к неотрицательной матрице A .

Другое неравенство:

$\min _{i}\sum _{j}a_{ij}\;\leq \;r.$

Этот факт характерен для неотрицательных матриц; для общих матриц нет ничего подобного. Учитывая, что A положителен (а не просто неотрицательен), тогда существует положительный собственный вектор w такой, что Aw = rw и наименьший компонент w (скажем, w _i ) равен 1. Тогда r = ( Aw ) _i ≥ сумма числа в строке i из A . Таким образом, минимальная сумма строк дает нижнюю оценку r , и это наблюдение можно распространить на все неотрицательные матрицы по непрерывности.

Другой способ доказать это — использовать формулу Коллатца -Виланда. Берем вектор x = (1, 1, ..., 1) и сразу получаем неравенство.

Дальнейшие доказательства

Проекция Перрона

Доказательство теперь продолжается с использованием спектрального разложения . Хитрость здесь заключается в том, чтобы отделить корень Перрона от других собственных значений. Спектральная проекция, связанная с корнем Перрона, называется проекцией Перрона и обладает следующим свойством:

Проекция Перрона неприводимой неотрицательной квадратной матрицы является положительной матрицей.

Выводы Перрона, а также (1)–(5) теоремы являются следствиями этого результата. Ключевым моментом является то, что положительная проекция всегда имеет ранг один. Это означает, что если A — неприводимая неотрицательная квадратная матрица, то алгебраическая и геометрическая кратности ее перроновского корня равны единице. Также, если P — его проекция Перрона, то AP = PA = ρ( A ) P , поэтому каждый столбец P является положительным правым собственным вектором A , а каждая строка — положительным левым собственным вектором. Более того, если Ax = λ x , то PAx = λ Px = ρ( A ) Px , что означает Px = 0, если λ ≠ ρ( A ). Таким образом, единственными положительными собственными векторами являются те, которые связаны с ρ( A ). Если A — примитивная матрица с ρ( A ) = 1, то ее можно разложить как P ⊕ (1 − P ) A так, что A ^н знак равно п + (1 - п ) А ^н . По мере увеличения n второй из этих членов уменьшается до нуля, оставляя P как предел A. ^н при n → ∞.

Степенной метод — удобный способ вычисления проекции Перрона примитивной матрицы. Если v и w — положительные векторы-строки и столбцы, которые он генерирует, то проекция Перрона — это просто wv / vw . Спектральные проекции не блокируются аккуратно, как в жордановой форме. Здесь они накладываются друг на друга, и каждый из них обычно имеет сложные записи, охватывающие все четыре угла квадратной матрицы. Тем не менее они сохраняют взаимную ортогональность, что облегчает декомпозицию.

Периферическая проекция

Анализ, когда A неприводим и неотрицательен, в целом аналогичен. Проекция Перрона по-прежнему положительна, но теперь могут существовать другие собственные значения модуля ρ( A ), которые сводят на нет использование степенного метода и предотвращают затухание степеней (1 − P ) A , как в примитивном случае, когда ρ( A ) = 1 Итак, мы рассматриваем периферийную проекцию , которая является спектральной проекцией A, соответствующей всем собственным значениям, имеющим модуль ρ ( A ). Затем можно показать, что периферийная проекция неприводимой неотрицательной квадратной матрицы является неотрицательной матрицей с положительной диагональю.

Цикличность

Предположим дополнительно, что ρ( A ) = 1 и A имеет h собственных значений на единичной окружности. Если P — периферийная проекция, то матрица R = AP = PA неотрицательна и неприводима, R ^час = P , а циклическая группа P , R , R ² , ...., Р ^{час -1} представляет гармоники A . Спектральная проекция A на собственное значение λ на единичную окружность задается формулой $\scriptstyle h^{-1}\sum _{1}^{h}\lambda ^{-k}R^{k}$. Все эти проекции (включая проекцию Перрона) имеют одну и ту же положительную диагональ, более того, выбирая любую из них и затем беря модуль каждой записи, неизменно получаем проекцию Перрона. Для установления циклических свойств (6)–(8) все еще требуется некоторая серьезная работа, но по сути это всего лишь вопрос поворота ручки. Спектральное разложение A задается формулой A = R ⊕ (1 − P ) A , поэтому разница между A ^н и Р ^н это А ^н − Р ^н знак равно (1 - п ) А ^н представляющие переходные процессы A ^н которые в конечном итоге сводятся к нулю. P можно вычислить как предел A ^нет при n → ∞.

Контрпримеры

Матрицы L = $\left({\begin{smallmatrix}1&0&0\\1&0&0\\1&1&1\end{smallmatrix}}\right)$, Р = $\left({\begin{smallmatrix}1&0&0\\1&0&0\\\!\!\!-1&1&1\end{smallmatrix}}\right)$, Т = $\left({\begin{smallmatrix}0&1&1\\1&0&1\\1&1&0\end{smallmatrix}}\right)$, М = $\left({\begin{smallmatrix}0&1&0&0&0\\1&0&0&0&0\\0&0&0&1&0\\0&0&0&0&1\\0&0&1&0&0\end{smallmatrix}}\right)$ приведите простые примеры того, что может пойти не так, если не будут выполнены необходимые условия. Легко видеть, что проекции Перрона и периферийные проекции матрицы L равны P , поэтому, когда исходная матрица приводима, проекции могут потерять неотрицательность и нет возможности выразить их как пределы ее степеней. Матрица T является примером примитивной матрицы с нулевой диагональю. Если диагональ неприводимой неотрицательной квадратной матрицы не равна нулю, то матрица должна быть примитивной, но этот пример демонстрирует, что обратное неверно. M — пример матрицы с несколькими отсутствующими спектральными зубцами. Если ω = e ^iπ/3 тогда ω ⁶ = 1, а собственные значения M равны {1,ω ² , ой ³ =-1, ох ⁴ } с собственным пространством размерности 2 для +1, поэтому ω и ω ⁵ оба отсутствуют. Точнее, поскольку M является блочно-диагональной циклической системой, то собственные значения равны {1,-1} для первого блока, а {1,ω ² , ой ⁴ } для нижнего

Терминология

Проблема, вызывающая путаницу, заключается в отсутствии стандартизации определений. Например, некоторые авторы используют термины «строго положительный» и «положительный» для обозначения > 0 и ≥ 0 соответственно. В этой статье положительное означает > 0, а неотрицательное означает ≥ 0. Еще одна проблемная область касается разложимости и сводимости : неприводимый — это перегруженный термин. Во избежание сомнений ненулевую неотрицательную квадратную матрицу A такую, что 1 + A является примитивной, иногда называют связной . Тогда неприводимые неотрицательные квадратные матрицы и связные матрицы являются синонимами.

Неотрицательный собственный вектор часто нормируют так, чтобы сумма его компонент была равна единице; в этом случае собственный вектор является вектором распределения вероятностей и иногда называется стохастическим собственным вектором .

Собственное значение Перрона-Фробениуса и доминирующее собственное значение являются альтернативными названиями корня Перрона. Спектральные проекции также известны как спектральные проекторы и спектральные идемпотенты . Период иногда называют индексом примитивности или порядком цикличности .

См. также

• Теорема Мин-Макса - Вариационная характеризация собственных значений компактных эрмитовых операторов в гильбертовых пространствах
• Z-матрица (математика) - квадратная матрица, недиагональные элементы которой неположительны.
• М-матрица
• P-матрица - комплексная квадратная матрица, у которой каждый главный минор положителен.
• Матрица Гурвица - алгебраический матричный элемент для анализа многочлена по его коэффициентам.
• Матрица Мецлера ( Квазиположительная матрица )
• Позитивный оператор - самосопряженный (или эрмитовый) элемент A C*-алгебры A называется положительным, если его спектр σ (A) состоит из неотрицательных действительных чисел. Страницы, отображающие описания викиданных в качестве запасного варианта.
• Теорема Крейна-Рутмана - обобщение теоремы Перрона-Фробениуса на банаховые пространства.

Ссылки

• Перрон, Оскар (1907), «К теории матриц» , Mathematical Annals , 64 (2): 248–263, doi : 10.1007/BF01449896 , hdl : 10338.dmlcz/104432 , S2CID   123460172
• Фробениус, Георг (май 1912 г.), «О матрицах из неотрицательных элементов», труды Королевской прусской академии наук : 456–477.
• Фробениус, Георг (1908), «О матрицах положительных элементов, 1», Труды Королевской прусской академии наук : 471–476.
• Фробениус, Георг (1909), «О матрицах положительных элементов, 2», Труды Королевской прусской академии наук : 514–518.
• Гантмахер, Феликс (2000) [1959], Теория матриц, Том 2 , AMS Chelsea Publishing, ISBN  978-0-8218-2664-5 (Издание 1959 года имело другое название: «Приложения теории матриц». Также в двух изданиях разная нумерация глав.)
• Лэнгвилл, Эми; Мейер, Карл (2006), рейтинг страницы Google и выше , Princeton University Press, doi : 10.1007/s10791-008-9063-y , ISBN  978-0-691-12202-1 , S2CID   7646929
• Кинер, Джеймс (1993), «Теорема Перрона-Фробениуса и рейтинг футбольных команд», SIAM Review , 35 (1): 80–93, doi : 10.1137/1035004 , JSTOR   2132526
• Мейер, Карл (2000), Матричный анализ и прикладная линейная алгебра (PDF) , SIAM, ISBN  978-0-89871-454-8 , заархивировано из оригинала (PDF) 7 марта 2010 г.
• Минк, Хенрик (1988), Неотрицательные матрицы , John Wiley&Sons, Нью-Йорк, ISBN  0-471-83966-3
• Романовский В. (1933), «О нулях стокастических матриц», Bulletin de la Société Mathématique de France , 61 : 213–219, doi : 10.24033/bsmf.1206
• Коллатц, Лотар (1942), «Заключительная теорема для характеристических чисел матриц», Mathematical Journal , 48 (1): 221–226, doi : 10.1007/BF01180013 , S2CID   120958677
• Виландт, Хельмут (1950), «Неразложимые неотрицательные матрицы», Mathematical Journal , 52 (1): 642–648, doi : 10.1007/BF02230720 , hdl : 10338.dmlcz/100322 , S2CID   122189604

Дальнейшее чтение

• Авраам Берман, Роберт Дж. Племмонс , Неотрицательные матрицы в математических науках , 1994, SIAM. ISBN   0-89871-321-8 .
• Крис Годсил и Гордон Ройл , Алгебраическая теория графов , Springer, 2001.
• А. Грэм, Неотрицательные матрицы и применимые темы линейной алгебры , John Wiley&Sons, Нью-Йорк, 1987.
• Р. А. Хорн и Ч. Р. Джонсон, Матричный анализ , издательство Кембриджского университета, 1990 г.
• Бас Лемменс и Роджер Нуссбаум, Нелинейная теория Перрона-Фробениуса , Cambridge Tracts in Mathematics 189, Cambridge Univ. Пресс, 2012.
• С.П. Мейн и Р.Л. Твиди, Марковские цепи и стохастическая устойчивость. Лондон: Springer-Verlag, 1993. ISBN   0-387-19832-6 (2-е издание, Cambridge University Press, 2009 г.)
• Сенета, Э. Неотрицательные матрицы и цепи Маркова . 2-я ред. изд., 1981, XVI, 288 стр., Серия Springer в мягкой обложке по статистике. (Первоначально опубликовано Allen & Unwin Ltd., Лондон, 1973 г.) ISBN   978-0-387-29765-1
• Супруненко, Д.А. (2001) [1994], «Теорема Перрона–Фробениуса» , Энциклопедия математики , EMS Press (Утверждение о том, что A _j имеет порядок n / h в конце утверждения теоремы, неверно.)
• Варга, Ричард С. (2002), Матричный итеративный анализ (2-е изд.), Springer-Verlag .