Собственные векторы

Прошлая глава закончилась наблюдением: у линейного преобразования бывают направления, которые оно не поворачивает, а только растягивает. Проверим на матрице $A = \left(\begin{smallmatrix} 2 & 1 \\ 1 & 2 \end{smallmatrix}\right)$. Вектор $(1;\,0)$ она переводит в $(2;\,1)$ — стрелка повернулась. Вектор $(0;\,1)$ уходит в $(1;\,2)$ и тоже поворачивается. А вектор $(1;\,1)$ переходит в $(3;\,3)$: направление прежнее, длина втрое больше. Вектор $(1;\,-1)$ и вовсе остаётся на месте.

Такие направления и будут нашей добычей. Охотиться за ними стоит, потому что в них прячутся ответы на три задачи, между которыми на первый взгляд нет ничего общего. Как найти сотое число Фибоначчи, не вычисляя девяносто девять предыдущих? Как поисковик решает, какая из миллиардов страниц важнее? И что за кривая $5x^2 + 4xy + 2y^2 = 6$ — с тем самым произведением $xy$, разбор которого нам оставила глава о конических сечениях?

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

Следы на сетке

Возьмите матрицу $2 \times 2$ и начните поворачивать вектор $\mathbf v$ единичной длины. Его образ $A\mathbf v$ тоже поворачивается, но со своей скоростью: где-то отстаёт от $\mathbf v$, где-то забегает вперёд. Если в одном положении $A\mathbf v$ отстаёт, а в другом обгоняет, то где-то между ними стрелки обязательно окажутся на одной прямой. Эти положения мы и ловим.

Квадратная матрица — преобразование, которое мы изучаем. Собственный вектор. Он обязан быть ненулевым: нулевой вектор удовлетворяет равенству при любом $\lambda$ и ничего не говорит о матрице. Собственное значение — во сколько раз растягивается вектор. Бывает отрицательным (вектор разворачивается, оставаясь на своей прямой) и нулём (вектор сплющивается в точку). Пример: для $A = \left(\begin{smallmatrix} 2 & 1 \\ 1 & 2 \end{smallmatrix}\right)$ и $\mathbf v = (1;\,1)$ получаем $A\mathbf v = (3;\,3) = 3\mathbf v$, то есть $\lambda = 3$. Для $\mathbf v = (1;\,-1)$ выходит $\lambda = 1$.

Как и в предыдущих главах, векторы пишем жирными буквами, а координаты в тексте — в строчку: $(1;\,-1)$ означает столбец $\left(\begin{smallmatrix} 1 \\ -1 \end{smallmatrix}\right)$.

Если $\mathbf v$ собственный, то собственные и $2\mathbf v$, и $-\mathbf v$, и вообще $c\mathbf v$ при любом $c \ne 0$: $A(c\mathbf v) = c\,A\mathbf v = \lambda\,(c\mathbf v)$. Поэтому охотимся мы за прямыми, а не за отдельными стрелками. Сумма двух собственных векторов с одним и тем же $\lambda$ снова удовлетворяет $A\mathbf v = \lambda\mathbf v$, так что все такие векторы вместе с нулевым образуют подпространство — собственное подпространство. Чаще всего это прямая, но бывает и больше: у гомотетии $\mathbf v \mapsto 2\mathbf v$ собственным оказывается всё пространство.

Вот что даёт охота на знакомых преобразованиях из главы 35:

Рядом с плоскостью в виджете работает сонар. Он показывает площадь параллелограмма на $\mathbf v$ и $A\mathbf v$ со знаком: плюс, если $A\mathbf v$ повёрнут от $\mathbf v$ против часовой стрелки, минус — если по часовой. Там, где кривая пересекает ноль, векторы легли на одну прямую. У поворота кривая целиком выше нуля, и добыча уходит. У сдвига она лишь касается нуля в одной точке.

Почему сонар рисует синусоиду

Для $A = \left(\begin{smallmatrix} a & b \\ c & d \end{smallmatrix}\right)$ и $\mathbf v = (\cos\theta;\,\sin\theta)$ площадь со знаком равна

$$S(\theta) = \det(\mathbf v, A\mathbf v) = \frac{c - b}{2} + \frac{c + b}{2}\cos 2\theta + \frac{d - a}{2}\sin 2\theta.$$

Это синусоида с периодом $180°$, поднятая на $\frac{c - b}{2}$. Подъём — вклад «вращательной» части матрицы, а размах синусоиды равен $\frac12\sqrt{(c + b)^2 + (d - a)^2}$. До нуля она достаёт, когда подъём не больше размаха: $(c - b)^2 \le (c + b)^2 + (d - a)^2$, то есть $(a - d)^2 + 4bc \ge 0$. Слева стоит дискриминант характеристического многочлена из следующего раздела. У симметричной матрицы $b = c$, подъёма нет, и собственных направлений всегда два (или сразу все). К этому мы вернёмся в конце главы.

Сколько собственных направлений у поворота плоскости на $180°$ вокруг начала координат?

Ни одного: это же поворот Два перпендикулярных Все направления Одно

Поворот на $180°$ переводит каждый вектор $\mathbf v$ в $-\mathbf v$, то есть совпадает с матрицей $-E$. Любой ненулевой вектор собственный, $\lambda = -1$: стрелка разворачивается, но остаётся на своей прямой.

Капкан: характеристический многочлен

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

Перепишем определение. Равенство $A\mathbf v = \lambda\mathbf v$ означает то же, что $A\mathbf v - \lambda E\mathbf v = \mathbf 0$, то есть

$$(A - \lambda E)\,\mathbf v = \mathbf 0.$$

Здесь $E$ — единичная матрица (в англоязычных книгах её обозначают $I$); вычесть $\lambda E$ — значит вычесть $\lambda$ из каждого диагонального элемента. Получилась однородная система уравнений, и собственный вектор — её ненулевое решение. Есть ли такое решение, подскажет определитель.

Матрица $n \times n$, собственные значения которой мы ищем. Неизвестное число. Для каждого $\lambda$ получается своя матрица $A - \lambda E$, и нас интересуют те, что сплющивают пространство. Единичная матрица того же размера: $\lambda E$ — это $\lambda$ на диагонали и нули вне её. Пример: для $A = \left(\begin{smallmatrix} 4 & 1 \\ 2 & 3 \end{smallmatrix}\right)$ получаем $\det\left(\begin{smallmatrix} 4 - \lambda & 1 \\ 2 & 3 - \lambda \end{smallmatrix}\right) = (4 - \lambda)(3 - \lambda) - 2 = \lambda^2 - 7\lambda + 10 = 0$, откуда $\lambda_1 = 2$, $\lambda_2 = 5$.

Идея: равенство $A\mathbf v = \lambda\mathbf v$ означает, что матрица $A - \lambda E$ отправляет ненулевой вектор в ноль. Такая матрица сплющивает плоскость в прямую, а определитель показывает, во сколько раз меняется площадь, — значит, он равен нулю. Чертёж сделан для матриц $2 \times 2$; что меняется в $n$ измерениях, скажем в конце.

Пусть $\lambda$ — собственное значение: $A\mathbf v = \lambda\mathbf v$ для некоторого $\mathbf v \ne \mathbf 0$. На чертеже $\mathbf v$ и $A\mathbf v$ лежат на одной прямой. Так как $E\mathbf v = \mathbf v$, правую часть можно записать как $\lambda E\mathbf v$, а по распределительному закону для матриц $A\mathbf v - \lambda E\mathbf v = (A - \lambda E)\mathbf v$. Поэтому $(A - \lambda E)\mathbf v = A\mathbf v - \lambda\mathbf v = \mathbf 0$: матрица $B = A - \lambda E$ переводит ненулевой вектор $\mathbf v$ в ноль. Отсюда $\det B = 0$. Дополним $\mathbf v$ каким-нибудь вектором $\mathbf w$ до базиса плоскости. Любой вектор равен $s\mathbf v + t\mathbf w$, и по линейности $B(s\mathbf v + t\mathbf w) = sB\mathbf v + tB\mathbf w = tB\mathbf w$. Всё, что выдаёт $B$, лежит на одной прямой — прямой вектора $B\mathbf w$, так что единичный квадрат переходит в отрезок нулевой площади. Площадь образа квадрата равна $|\det B|$ (глава 35), значит, $\det B = 0$. На чертеже видно, как столбцы $B\mathbf e_1 = A\mathbf e_1 - \lambda\mathbf e_1$ и $B\mathbf e_2 = A\mathbf e_2 - \lambda\mathbf e_2$ получаются сдвигом концов столбцов $A$ на $\lambda$ вдоль осей и ложатся на одну прямую. Обратно, пусть $\det B = 0$. Тогда параллелограмм на векторах $B\mathbf e_1$ и $B\mathbf e_2$ имеет нулевую площадь, то есть они лежат на одной прямой. Если $B\mathbf e_1 = \mathbf 0$, возьмём $\mathbf v = \mathbf e_1$. Иначе $B\mathbf e_2 = kB\mathbf e_1$ для некоторого числа $k$, и вектор $\mathbf v = (k;\,-1)$ даёт $B\mathbf v = kB\mathbf e_1 - B\mathbf e_2 = \mathbf 0$. В обоих случаях нашёлся $\mathbf v = (v_1;\,v_2) \ne \mathbf 0$, для которого $v_1B\mathbf e_1 + v_2B\mathbf e_2 = B\mathbf v = \mathbf 0$: на чертеже две стрелки возвращаются в начало координат. Прочитав перенос из второго шага в обратную сторону, из $(A - \lambda E)\mathbf v = \mathbf 0$ получаем $A\mathbf v = \lambda\mathbf v$ с $\mathbf v \ne \mathbf 0$, то есть $\lambda$ — собственное значение. В $n$ измерениях рассуждение то же, только вместо площади — объём, а вместо «лежат на одной прямой» — «столбцы линейно зависимы». То, что $\det B = 0$ ровно тогда, когда уравнение $B\mathbf v = \mathbf 0$ имеет ненулевое решение, — теорема из главы 36; для комплексных чисел метод Гаусса работает так же.

У матрицы $n \times n$ характеристический многочлен имеет степень $n$: при раскрытии определителя $\lambda$ из диагональных элементов перемножаются не больше $n$ раз, а старший член равен $(-\lambda)^n$. Поэтому различных собственных значений не больше $n$. Некоторые книги пишут $\det(\lambda E - A)$, чтобы старший коэффициент был единицей; корни от этого не меняются.

Собственные значения найдены — собственные векторы достаются решением однородной системы методом Гаусса из главы 36.

Для матрицы $2 \times 2$ определитель раскрывается в общем виде: $\det(A - \lambda E) = (a - \lambda)(d - \lambda) - bc = \lambda^2 - (a + d)\lambda + (ad - bc)$. Свободный член — определитель $A$, а коэффициент при $\lambda$ — сумма диагональных элементов со знаком минус. Эту сумму называют следом матрицы и обозначают $\operatorname{tr} A$.

След $a + d$. По теореме Виета из главы 10 он равен сумме корней: $\lambda_1 + \lambda_2 = \operatorname{tr} A$. Определитель $ad - bc$ равен произведению корней: $\lambda_1\lambda_2 = \det A$. Пример: у $A = \left(\begin{smallmatrix} 4 & 1 \\ 2 & 3 \end{smallmatrix}\right)$ след $7$ и определитель $10$; корни $2$ и $5$, и действительно $2 + 5 = 7$, $2 \cdot 5 = 10$. Если дискриминант $(\operatorname{tr} A)^2 - 4\det A$ отрицателен, действительных собственных значений нет.

Оба равенства верны и для матриц любого размера.

Отсюда полезный признак: матрица вырождена ровно тогда, когда среди её собственных значений есть ноль. Весь набор собственных значений называют спектром матрицы.

Найдите собственные значения матрицы $\left(\begin{smallmatrix} 1 & 2 \\ 3 & 2 \end{smallmatrix}\right)$.

След $1 + 2 = 3$, определитель $1 \cdot 2 - 2 \cdot 3 = -4$. Уравнение $\lambda^2 - 3\lambda - 4 = 0$ раскладывается как $(\lambda - 4)(\lambda + 1) = 0$, так что $\lambda_1 = 4$, $\lambda_2 = -1$. Проверка: $4 + (-1) = 3$ и $4 \cdot (-1) = -4$.

Трофей: диагональная матрица

Предположим, охота удалась: у матрицы $n \times n$ нашлось $n$ линейно независимых собственных векторов $\mathbf v_1, \dots, \mathbf v_n$ с собственными значениями $\lambda_1, \dots, \lambda_n$. Они образуют базис, и в этом базисе матрица устроена проще некуда. Вектор с координатами $c_1, \dots, c_n$ в новом базисе — это $c_1\mathbf v_1 + \dots + c_n\mathbf v_n$, а матрица превращает его в $\lambda_1c_1\mathbf v_1 + \dots + \lambda_nc_n\mathbf v_n$. Каждая координата умножается на своё число, и ничего не перемешивается.

Запишем это матрицами. Поставим собственные векторы столбцами в матрицу $P$ (в главе 37 такую матрицу называли матрицей перехода), а собственные значения — на диагональ матрицы $D = \operatorname{diag}(\lambda_1, \dots, \lambda_n)$, у которой вне диагонали нули. Тогда

Возврат в исходные координаты: столбцы $P$ — сами собственные векторы. Диагональная матрица из собственных значений: в собственных координатах $A$ просто растягивает $i$-ю ось в $\lambda_i$ раз. Переход в собственные координаты: $P^{-1}\mathbf x$ — координаты вектора $\mathbf x$ в базисе из собственных векторов. Произведение читается справа налево, как композиция преобразований. Пример: $\left(\begin{smallmatrix} 4 & 1 \\ 2 & 3 \end{smallmatrix}\right) = \left(\begin{smallmatrix} 1 & 1 \\ -2 & 1 \end{smallmatrix}\right)\left(\begin{smallmatrix} 2 & 0 \\ 0 & 5 \end{smallmatrix}\right)\cdot\frac13\left(\begin{smallmatrix} 1 & -1 \\ 2 & 1 \end{smallmatrix}\right)$. Столбцы первой матрицы — найденные выше векторы $(1;\,-2)$ и $(1;\,1)$.

Идея: в базисе из собственных векторов матрица растягивает каждую координату отдельно, а $P^{-1}$ и $P$ — всего лишь переход к этому базису и обратно. Чертёж — для $n = 2$, но ни один шаг не пользуется тем, что координат две.

Пусть $A\mathbf p_i = d_i\mathbf p_i$ для всех $i$. На чертеже $\mathbf p_1 = \mathbf v_1$, $\mathbf p_2 = \mathbf v_2$, $d_1 = 2$, $d_2 = \frac12$: на векторах базиса матрица действует проще всего — растягивает $\mathbf v_1$ вдвое и сжимает $\mathbf v_2$ вдвое. Косая сетка — координатная сетка этого базиса. Возьмём любой вектор $\mathbf x$ и разложим его по базису: $\mathbf x = c_1\mathbf v_1 + c_2\mathbf v_2$. Это равенство означает $\mathbf x = P\mathbf c$ для столбца $\mathbf c = (c_1;\,c_2)$ (умножить матрицу на столбец — значит сложить её столбцы с этими коэффициентами). Матрица $P$ обратима, поэтому $\mathbf c = P^{-1}\mathbf x$: $P^{-1}$ переводит вектор в его координаты в собственном базисе. По линейности $A\mathbf x = c_1A\mathbf v_1 + c_2A\mathbf v_2 = d_1c_1\mathbf v_1 + d_2c_2\mathbf v_2$. Каждая координата просто умножилась на своё число, и новый столбец координат равен $(d_1c_1;\,d_2c_2) = D\mathbf c = DP^{-1}\mathbf x$. Соберём вектор из новых координат — это снова умножение на $P$: $A\mathbf x = P(DP^{-1}\mathbf x) = (PDP^{-1})\mathbf x$ (умножение матриц ассоциативно). Равенство верно для каждого $\mathbf x$, в частности для $\mathbf e_1, \dots, \mathbf e_n$, а столбцы матрицы — это образы $\mathbf e_i$. Значит, у матриц $A$ и $PDP^{-1}$ одинаковые столбцы: $A = PDP^{-1}$. Обратно, пусть $A = PDP^{-1}$. Умножим обе части справа на $P$: $AP = PD$. Слева $i$-й столбец равен $A\mathbf p_i$, справа — $d_i\mathbf p_i$, потому что умножение на диагональную матрицу справа умножает $i$-й столбец на $d_i$. Значит, $A\mathbf p_i = d_i\mathbf p_i$; столбцы обратимой матрицы ненулевые и линейно независимы, так что $\mathbf p_1, \dots, \mathbf p_n$ — базис из собственных векторов. Весь параллелограмм сетки на $\mathbf v_1$, $\mathbf v_2$ переходит в параллелограмм на $2\mathbf v_1$, $\frac12\mathbf v_2$.

Трофей оправдывает охоту, когда матрицу нужно применить много раз. В произведении $(PDP^{-1})(PDP^{-1})\cdots(PDP^{-1})$ все внутренние пары $P^{-1}P$ сокращаются.

Для нашего примера

$$A^n = \frac13\begin{pmatrix} 2^n + 2\cdot 5^n & 5^n - 2^n \\ 2\cdot 5^n - 2^{n+1} & 5^n + 2^{n+1} \end{pmatrix}.$$

При $n = 1$ получается сама $A$, а при $n = 10$ — матрица $\left(\begin{smallmatrix} 6\,510\,758 & 3\,254\,867 \\ 6\,509\,734 & 3\,255\,891 \end{smallmatrix}\right)$, и перемножать $A$ саму на себя девять раз не пришлось. Видно и другое: при больших $n$ слагаемые с $5^n$ подавляют всё остальное, так что $A^n$ почти пропорциональна матрице $\left(\begin{smallmatrix} 2 & 1 \\ 2 & 1 \end{smallmatrix}\right)$, оба столбца которой смотрят вдоль $(1;\,1)$. К этому наблюдению мы ещё вернёмся.

Найдите левый верхний элемент матрицы $A^5$ для $A = \left(\begin{smallmatrix} 4 & 1 \\ 2 & 3 \end{smallmatrix}\right)$.

По формуле для $A^n$: $\frac{2^5 + 2 \cdot 5^5}{3} = \frac{32 + 6250}{3} = 2094$.

Когда базис из собственных векторов гарантирован? Достаточное условие простое.

Кто уходит от охотника

Охота удаётся не всегда, и неудачи бывают двух видов. Поворот уходит от охотника целиком, а сдвиг оставляет ему меньше добычи, чем нужно для базиса.

Поворот: добыча в комплексной плоскости

У поворота на угол $\varphi$ матрица $\left(\begin{smallmatrix} \cos\varphi & -\sin\varphi \\ \sin\varphi & \cos\varphi \end{smallmatrix}\right)$, след $2\cos\varphi$ и определитель $1$. Уравнение $\lambda^2 - 2\lambda\cos\varphi + 1 = 0$ имеет дискриминант $4\cos^2\varphi - 4 = -4\sin^2\varphi$, отрицательный при любом угле, кроме $0°$ и $180°$. Корни комплексные:

$$\lambda = \cos\varphi \pm i\sin\varphi = e^{\pm i\varphi}.$$

В главе о комплексных числах мы видели, что умножение на $a + bi$ — это поворот с растяжением. Так как $(a + bi)(x + yi) = (ax - by) + (bx + ay)i$, в координатах $(x;\,y)$ оно записывается матрицей $\left(\begin{smallmatrix} a & -b \\ b & a \end{smallmatrix}\right)$, и её собственные значения — $a \pm bi$. Оказывается, так выглядит любая действительная матрица $2 \times 2$ с комплексными собственными значениями, если выбрать подходящий базис.

Пример: у $A = \left(\begin{smallmatrix} 1 & -1 \\ 1 & 1 \end{smallmatrix}\right)$ собственные значения $1 \pm i = \sqrt2\,e^{\pm i\pi/4}$. Значит, $A$ поворачивает на $45°$ и растягивает в $\sqrt2$ раз, и восемь таких шагов дают полный оборот: $A^8 = (\sqrt2)^8E = 16E$. Собственные векторы тоже есть, только комплексные: $A\left(\begin{smallmatrix} 1 \\ -i \end{smallmatrix}\right) = \left(\begin{smallmatrix} 1 + i \\ 1 - i \end{smallmatrix}\right) = (1 + i)\left(\begin{smallmatrix} 1 \\ -i \end{smallmatrix}\right)$.

Над комплексными числами охотник без добычи не остаётся: по основной теореме алгебры у характеристического многочлена всегда есть корень, так что у любой квадратной матрицы найдётся хотя бы одно собственное значение и собственный вектор в $\mathbb C^n$.

Почему у любого вращения шара есть ось

Пусть $A$ — линейное преобразование трёхмерного пространства, которое сохраняет длины векторов и ориентацию ($\det A = 1$). Тогда существует ненулевой вектор $\mathbf n$ с $A\mathbf n = \mathbf n$: преобразование — поворот вокруг оси $\mathbf n$.

Идея: посчитать, какими могут быть собственные значения, и увидеть, что среди них обязательно есть $1$. Характеристический многочлен матрицы $3 \times 3$ имеет степень $3$ и действительные коэффициенты, а у такого многочлена всегда есть действительный корень: при больших $|\lambda|$ он принимает значения разных знаков, а непрерывная функция, меняющая знак, проходит через ноль (теорема о промежуточном значении, глава 25; строгое доказательство — в главе 53). Остальные два корня либо действительные, либо пара сопряжённых $\mu$, $\bar\mu$.

Все собственные значения по модулю равны $1$. Для действительного собственного вектора это прямо следует из $\|A\mathbf v\| = \|\mathbf v\|$ и $A\mathbf v = \lambda\mathbf v$. Для комплексного $\mathbf w = \mathbf u + i\mathbf v$ положим $\|\mathbf w\|^2 = \|\mathbf u\|^2 + \|\mathbf v\|^2$; так как $A\mathbf w = A\mathbf u + iA\mathbf v$ и $A$ сохраняет длины $\mathbf u$ и $\mathbf v$, получаем $\|A\mathbf w\| = \|\mathbf w\|$, а из $A\mathbf w = \mu\mathbf w$ следует $\|A\mathbf w\| = |\mu|\,\|\mathbf w\|$, то есть $|\mu| = 1$.

Произведение трёх собственных значений равно $\det A = 1$ (утверждение о следе и определителе выше). Если есть сопряжённая пара, то $\mu\bar\mu = |\mu|^2 = 1$, и третье, действительное значение тоже равно $1$. Если все три действительные, то это числа $\pm1$ с произведением $1$: либо $1, 1, 1$, либо $1, -1, -1$ — в обоих случаях есть $1$. Собственный вектор $\mathbf n$ с $\lambda = 1$ неподвижен, прямая через него — ось. Так на современном языке доказывается теорема, которую Эйлер получил в 1775 году: любое перемещение твёрдого тела с неподвижной точкой — поворот вокруг некоторой оси.

Сдвиг: добычи меньше, чем нужно

Сдвиг $\left(\begin{smallmatrix} 1 & 1 \\ 0 & 1 \end{smallmatrix}\right)$ ведёт себя иначе. Его характеристический многочлен $(1 - \lambda)^2$ имеет двойной корень $\lambda = 1$, но система $(A - E)\mathbf v = \mathbf 0$, то есть $\left(\begin{smallmatrix} 0 & 1 \\ 0 & 0 \end{smallmatrix}\right)\mathbf v = \mathbf 0$, оставляет только векторы с $y = 0$ — одну прямую. Корень посчитан дважды, а направление одно. Базиса из собственных векторов нет, и матрица не диагонализуема.

Здесь расходятся два понятия кратности. Алгебраическая кратность собственного значения — сколько раз оно встречается среди корней характеристического многочлена. Геометрическая кратность — размерность его собственного подпространства. У сдвига алгебраическая кратность $2$, а геометрическая $1$. Больше, чем алгебраическая, геометрическая кратность не бывает.

Если взять коэффициенты матрицы наугад, кратные корни почти наверняка не встретятся, так что недиагонализуемые матрицы — исключение. Зато встречаются они как раз там, где поведение системы меняется, например на границе между колебаниями и плавным затуханием (об этом — в примечании ниже).

У матриц $\left(\begin{smallmatrix} 3 & 0 \\ 0 & 3 \end{smallmatrix}\right)$ и $\left(\begin{smallmatrix} 3 & 1 \\ 0 & 3 \end{smallmatrix}\right)$ один и тот же характеристический многочлен $(\lambda - 3)^2$. Какая из них диагонализуема?

Обе: многочлен одинаковый Только первая Только вторая Ни одна: корень двойной

Первая уже диагональна, собственное у неё всё пространство. У второй система $(A - 3E)\mathbf v = \mathbf 0$ даёт одну прямую, как у сдвига. Характеристический многочлен не определяет матрицу, а двойной корень ещё не приговор.

Кролики Фибоначчи

Числа Фибоначчи $0, 1, 1, 2, 3, 5, 8, 13, \dots$, восходящие к задаче о кроликах из «Книги абака» (1202), подчиняются правилу $F_{n+1} = F_n + F_{n-1}$ (глава 13). Чтобы получить следующее число, нужно помнить два последних. Сложим их в вектор, и шаг последовательности станет умножением на матрицу:

$$\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix}.$$

Обозначим эту матрицу $M$. Начав с $(F_1;\,F_0) = (1;\,0)$ и умножив $n$ раз, получим $(F_{n+1};\,F_n) = M^n(1;\,0)$ (при $n = 0$ это верно, если считать $M^0 = E$). Попутно выходит красивая формула для самих степеней.

Охотимся. След $M$ равен $1$, определитель $-1$, характеристическое уравнение $\lambda^2 - \lambda - 1 = 0$. Его корни — золотое сечение и его «двойник»:

$$\varphi = \frac{1 + \sqrt5}{2} \approx 1{,}618, \qquad \psi = \frac{1 - \sqrt5}{2} \approx -0{,}618.$$

Собственные векторы — $(\varphi;\,1)$ и $(\psi;\,1)$. Разложив по ним стартовый вектор, получаем знаменитую формулу.

Идея: разложить стартовый вектор по двум собственным направлениям. Дальше каждое умножение на $M$ просто растягивает обе части — каждую в своё число раз.

По лемме вектор $(F_{n+1};\,F_n)$ получается из $(1;\,0)$ умножением на $M$ $n$ раз. На чертеже эти векторы для $n = 0, 1, 2, 3, 4$: $(1;\,0)$, $(1;\,1)$, $(2;\,1)$, $(3;\,2)$, $(5;\,3)$. Они всё сильнее прижимаются к одной прямой. У $M$ два собственных направления: $(\varphi;\,1)$ с $\lambda = \varphi$ и $(\psi;\,1)$ с $\lambda = \psi$. Проверим первое: $M(\varphi;\,1) = (\varphi + 1;\,\varphi)$, и это $\varphi\,(\varphi;\,1)$, потому что $\varphi^2 = \varphi + 1$ — так $\varphi$ определено, как корень уравнения $\lambda^2 - \lambda - 1 = 0$. Для $\psi$, второго корня, проверка та же. Разложим стартовый вектор: $(1;\,0) = \frac{1}{\sqrt5}(\varphi;\,1) - \frac{1}{\sqrt5}(\psi;\,1)$. Проверка: первая координата равна $\frac{\varphi - \psi}{\sqrt5} = \frac{\sqrt5}{\sqrt5} = 1$, вторая $\frac{1 - 1}{\sqrt5} = 0$. Умножение на $M$ линейно, поэтому части можно умножать по отдельности. Собственный вектор при этом только растягивается: из $M\mathbf v = \lambda\mathbf v$ следует $M^2\mathbf v = \lambda M\mathbf v = \lambda^2\mathbf v$ и так далее, $M^n\mathbf v = \lambda^n\mathbf v$. Значит, $(F_{n+1};\,F_n) = \frac{\varphi^n}{\sqrt5}(\varphi;\,1) - \frac{\psi^n}{\sqrt5}(\psi;\,1)$. На чертеже первая часть растёт вдоль своей прямой в $\varphi \approx 1{,}618$ раза за шаг, а вторая, умножаясь на $\psi \approx -0{,}618$, тает и каждый раз перескакивает на другую сторону. Сравним вторые координаты: $F_n = \frac{\varphi^n}{\sqrt5} \cdot 1 - \frac{\psi^n}{\sqrt5} \cdot 1 = \frac{\varphi^n - \psi^n}{\sqrt5}$. На чертеже это высоты точек: $0, 1, 1, 2, 3$.

Растущая составляющая: собственное значение $\varphi \approx 1{,}618$ в степени $n$. Угасающая составляющая: $|\psi| \approx 0{,}618 < 1$, поэтому $\psi^n \to 0$, меняя знак на каждом шаге. Нормировка, пришедшая из разложения стартового вектора: $\sqrt5 = \varphi - \psi$. Пример: $\varphi^{10} \approx 122{,}9919$ и $\psi^{10} \approx 0{,}0081$, поэтому $F_{10} \approx \frac{122{,}9919 - 0{,}0081}{2{,}2361} \approx 55{,}000$. Так как $|\psi^n| / \sqrt5 < \frac12$ при любом $n$, число $F_n$ — это $\frac{\varphi^n}{\sqrt5}$, округлённое до ближайшего целого: $\frac{\varphi^{10}}{\sqrt5} \approx 55{,}004$.

Сотое число Фибоначчи больше не нужно добывать девяноста девятью сложениями: $F_{100}$ — ближайшее целое к $\varphi^{100}/\sqrt5$, то есть $354\,224\,848\,179\,261\,915\,075$. Правда, чтобы округление было честным, $\varphi^{100}$ придётся вычислить с точностью больше двадцати знаков. Формулу называют по имени Жака Бине, опубликовавшего её в 1843 году, хотя Абрахам де Муавр и Даниил Бернулли знали её больше чем за сто лет до него.

Матричный взгляд даёт и неожиданные тождества.

Это тождество нашёл Джованни Доменико Кассини в 1680 году. На нём держится старый фокус: квадрат $8 \times 8$ разрезают на четыре части и складывают из них прямоугольник $5 \times 13$, и площадь будто бы вырастает с $64$ до $65$. Лишняя клетка размазана по узкой, почти незаметной щели вдоль диагонали прямоугольника: $5 \cdot 13 - 8^2 = 1$.

Числа Люка $2, 1, 3, 4, 7, 11, \dots$ подчиняются тому же правилу, но начинаются с $L_0 = 2$, $L_1 = 1$. Их стартовый вектор раскладывается по собственным векторам ещё проще, и $L_n = \varphi^n + \psi^n$. Найдите $L_{10}$.

Сложением: $2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123$. По формуле: $\varphi^{10} + \psi^{10} \approx 122{,}9919 + 0{,}0081 = 123$. Заодно видно, почему $\varphi^{10}$ так близко к целому числу: от $L_{10}$ его отделяет крошечное $\psi^{10}$.

Охота без капкана: степенной метод

Посмотрите на отношения соседних чисел Фибоначчи: $\frac21 = 2$, $\frac32 = 1{,}5$, $\frac53 \approx 1{,}667$, $\frac85 = 1{,}6$, $\frac{13}{8} = 1{,}625$, $\frac{21}{13} \approx 1{,}615$, $\frac{34}{21} \approx 1{,}619$. Они сходятся к $\varphi$, и формула Бине объясняет почему. В векторе $M^n(1;\,0)$ составляющая вдоль $(\psi;\,1)$ по сравнению с главной убывает как $(\psi/\varphi)^n \approx (-0{,}382)^n$, и вектор всё точнее ложится на прямую $(\varphi;\,1)$.

Это наблюдение работает для любой диагонализуемой матрицы, у которой одно собственное значение по модулю строго больше остальных. Разложим начальный вектор по собственным: $\mathbf x = c_1\mathbf v_1 + c_2\mathbf v_2 + \dots$, где $|\lambda_1| > |\lambda_2| \ge \dots$. После $k$ умножений

Общий множитель: вектор растёт или убывает, но направление от этого не зависит. На практике после каждого шага вектор делят на его длину, чтобы числа не переполнились. Ошибка: доля второго собственного вектора за шаг умножается на $\lambda_2/\lambda_1$. Нужно, чтобы $|\lambda_1| > |\lambda_2|$ и $c_1 \ne 0$ — начальный вектор должен иметь хоть какую-то составляющую вдоль $\mathbf v_1$. Пример: у матрицы Фибоначчи $|\psi/\varphi| \approx 0{,}382$, и за десять шагов ошибка уменьшается примерно в $1/0{,}382^{10} \approx 15\,000$ раз.

Так получается степенной метод: берём почти любой вектор, умножаем на $A$ снова и снова, нормируя после каждого шага, и его направление сходится к собственному вектору с наибольшим по модулю собственным значением. Само $\lambda_1$ получаем в конце как $\langle \mathbf x, A\mathbf x\rangle$ для единичного $\mathbf x$. Метод описали Рихард фон Мизес и Хильда Поллачек-Гейрингер в 1929 году. Ему не нужны ни определители, ни многочлены — только умножение матрицы на вектор, поэтому он годится и для матриц с миллиардами строк.

Идея: в собственных координатах умножение на $A^k$ умножает $c_i$ на $\lambda_i^k$, и по сравнению с первой все остальные части тают как $|\lambda_i/\lambda_1|^k$. На чертеже $n = 2$, $\lambda_1 = 2$, $\lambda_2 = 1$, так что отношение частей каждый шаг уменьшается вдвое.

Разложим $\mathbf x$ по собственному базису: $\mathbf x = c_1\mathbf v_1 + \dots + c_n\mathbf v_n$; на чертеже части $c_1\mathbf v_1$ и $c_2\mathbf v_2$ — стороны параллелограмма. Число $\lambda_1$ действительное: невещественные собственные значения действительной матрицы идут сопряжёнными парами $\mu$, $\bar\mu$ с одинаковым модулем, а $|\lambda_1|$ строго больше модулей всех остальных. Умножение на $A$ умножает каждую часть на её собственное значение: $A\mathbf x = \lambda_1c_1\mathbf v_1 + \dots + \lambda_nc_n\mathbf v_n$. После $k$ шагов $A^k\mathbf x = \lambda_1^k\,(c_1\mathbf v_1 + \mathbf r_k)$, где $\mathbf r_k = \sum_{i \ge 2} c_i\,(\lambda_i/\lambda_1)^k\,\mathbf v_i$. Нормировка $\mathbf x_k = A^k\mathbf x/\|A^k\mathbf x\|$ меняет длину, но не направление; на чертеже нормированные векторы лежат на окружности. Остаток мал: по неравенству треугольника $\|\mathbf r_k\| \le \sum_{i \ge 2}|c_i|\,|\lambda_i/\lambda_1|^k\,\|\mathbf v_i\| \le K\,|\lambda_2/\lambda_1|^k$, где $K = \sum_{i \ge 2}|c_i|\,\|\mathbf v_i\|$, потому что $|\lambda_i| \le |\lambda_2|$ при $i \ge 2$. На чертеже отношение частей $|c_2/c_1|\,(1/2)^k$ каждый шаг уменьшается вдвое, и точки на окружности ползут к прямой $\mathbf v_1$. Переведём это в расстояние между направлениями. Для любых ненулевых $\mathbf y$, $\mathbf z$ верно $\bigl\|\frac{\mathbf y}{\|\mathbf y\|} - \frac{\mathbf z}{\|\mathbf z\|}\bigr\| \le \frac{2\|\mathbf y - \mathbf z\|}{\|\mathbf z\|}$: разность равна $\frac{\mathbf y - \mathbf z}{\|\mathbf z\|} + \mathbf y\bigl(\frac{1}{\|\mathbf y\|} - \frac{1}{\|\mathbf z\|}\bigr)$, и второе слагаемое по длине равно $\frac{|\|\mathbf z\| - \|\mathbf y\||}{\|\mathbf z\|} \le \frac{\|\mathbf y - \mathbf z\|}{\|\mathbf z\|}$. Возьмём $\mathbf y = c_1\mathbf v_1 + \mathbf r_k$ и $\mathbf z = c_1\mathbf v_1$: вектор $\mathbf x_k$ отличается от $\mathbf y/\|\mathbf y\|$ разве что знаком (множитель $\lambda_1^k$ может быть отрицательным), так что расстояние от $\mathbf x_k$ до $\pm\mathbf v_1/\|\mathbf v_1\|$ не больше $\frac{2\|\mathbf r_k\|}{|c_1|\,\|\mathbf v_1\|} \le \frac{2K}{|c_1|\,\|\mathbf v_1\|}\,|\lambda_2/\lambda_1|^k$. Здесь и нужно $c_1 \ne 0$: поставьте $\mathbf x$ на прямую $\mathbf v_2$ — первая часть исчезнет, и сходиться будет не к чему. Выходит, $\mathbf x_k$ сколь угодно близко подходит к $\pm\mathbf u$, где $\mathbf u = \mathbf v_1/\|\mathbf v_1\|$. Для единичного собственного вектора $\langle \mathbf u, A\mathbf u\rangle = \lambda_1\langle \mathbf u, \mathbf u\rangle = \lambda_1$ (и для $-\mathbf u$ тоже), а скалярное произведение $\langle \mathbf x, A\mathbf x\rangle$ непрерывно зависит от $\mathbf x$, поэтому $\langle \mathbf x_k, A\mathbf x_k\rangle \to \lambda_1$.

Где метод ломается, видно по тем же двум случаям, что и раньше. Если два главных собственных значения равны по модулю, как $1$ и $-1$ у отражения, ни одно направление не побеждает. Если они комплексные, веер вращается вечно. А если $|\lambda_2/\lambda_1|$ близко к единице, метод формально работает, но очень медленно.

Самокаты расползаются по городу

Компания сдаёт в аренду $600$ самокатов. Город для неё делится на две зоны: центр и окраины. Статистика за сезон такая: из самокатов, начавших день в центре, $90$ % заканчивают его в центре, а $10$ % уезжают на окраины. Из стоявших на окраинах к вечеру половина оказывается в центре, половина остаётся на месте. Где окажутся самокаты через неделю, если после ночного фестиваля все $600$ собрались на окраинах?

Запишем доли самокатов в центре и на окраинах вектором $\mathbf p = (p_1;\,p_2)$. Один день — умножение на матрицу:

$$\mathbf p_{k+1} = P\,\mathbf p_k, \qquad P = \begin{pmatrix} 0{,}9 & 0{,}5 \\ 0{,}1 & 0{,}5 \end{pmatrix}.$$

В столбце $j$ записано, куда за день разъезжаются самокаты из зоны $j$; сумма каждого столбца равна $1$, потому что самокаты не пропадают. Ожидаемое число самокатов в центре день за днём: $0$, $300$, $420$, $468$, $487{,}2$, $494{,}9$ — и дальше оно подбирается к $500$. Недостача до $500$ составляет $500$, $200$, $80$, $32$, $12{,}8$ и каждый день уменьшается ровно в $2{,}5$ раза.

Это степенной метод в чистом виде. Первое собственное значение $P$ равно $1$ (почему — ниже), след равен $1{,}4$, значит, второе собственное значение $1{,}4 - 1 = 0{,}4$ — тот самый множитель, на который каждый день умножается недостача. А предел — собственный вектор с $\lambda = 1$. Уравнение $P\boldsymbol\pi = \boldsymbol\pi$ сводится к балансу потоков $0{,}1\,\pi_1 = 0{,}5\,\pi_2$: сколько самокатов уезжает из центра, столько же приезжает. Вместе с условием $\pi_1 + \pi_2 = 1$ получаем $\boldsymbol\pi = (5/6;\,1/6)$: $500$ самокатов в центре и $100$ на окраинах, с какого бы распределения мы ни начали.

Как у самокатов, сходимость к равновесию обеспечена, если все вероятности переходов положительны. Чтобы это доказать, будем измерять расстояние между распределениями суммой модулей разностей координат: $\|\mathbf y\|_1 = |y_1| + \dots + |y_n|$. Главное — одна лемма.

Идея: множество всех распределений матрица $P$ отображает внутрь себя, и при каждом применении всё сжимается хотя бы в $1/q$ раз. Вложенные друг в друга образы стягиваются в одну точку — она и есть $\boldsymbol\pi$. Чертёж — для трёх состояний.

Распределение на трёх состояниях — тройка $(p_1;\,p_2;\,p_3)$ с $p_i \ge 0$ и суммой $1$. Нарисуем его точкой $p_1\mathbf e_1 + p_2\mathbf e_2 + p_3\mathbf e_3$ треугольника с вершинами $\mathbf e_1, \mathbf e_2, \mathbf e_3$ — это центр масс грузов $p_1, p_2, p_3$, положенных в вершины. Вершина $\mathbf e_j$ означает, что цепь наверняка в состоянии $j$. $P\mathbf e_j$ — это $j$-й столбец $P$, тоже распределение; его координаты не меньше $\varepsilon$, поэтому точка лежит строго внутри треугольника. Матрица линейна: $P(p_1\mathbf e_1 + p_2\mathbf e_2 + p_3\mathbf e_3) = p_1P\mathbf e_1 + p_2P\mathbf e_2 + p_3P\mathbf e_3$ — центры масс переходят в центры масс с теми же грузами. Поэтому весь треугольник переходит в треугольник с вершинами в столбцах $P$. Применим $P$ снова: $P^2(\Delta) = P(P(\Delta)) \subset P(\Delta)$, и так далее — треугольники вложены друг в друга. К тому же они сжимаются: разность двух распределений имеет сумму координат $0$, и по лемме расстояние между образами не больше $q$ от расстояния между прообразами. Вначале любые два распределения отстоят друг от друга не больше чем на $2$ (сумма модулей разности не больше $1 + 1$), поэтому любые две точки $P^k(\Delta)$ — не больше чем на $2q^k$. Возьмём любое распределение $\mathbf p$ и последовательность $\mathbf p_k = P^k\mathbf p$. Соседние члены близки: $\|\mathbf p_{k+1} - \mathbf p_k\|_1 = \|P^k(P\mathbf p - \mathbf p)\|_1 \le 2q^k$, а ряд $2 + 2q + 2q^2 + \dots$ сходится. Значит, каждая координата $\mathbf p_k$ — частичная сумма абсолютно сходящегося ряда и имеет предел (глава 30). Предел $\boldsymbol\pi$ — снова распределение (неотрицательность и сумма $1$ сохраняются в пределе), а переходя к пределу в равенстве $\mathbf p_{k+1} = P\mathbf p_k$, получаем $\boldsymbol\pi = P\boldsymbol\pi$. В эту точку и стягиваются треугольники. Единственность и положительность. Если $P\boldsymbol\pi' = \boldsymbol\pi'$ для другого распределения, то $\|\boldsymbol\pi - \boldsymbol\pi'\|_1 = \|P(\boldsymbol\pi - \boldsymbol\pi')\|_1 \le q\,\|\boldsymbol\pi - \boldsymbol\pi'\|_1$, а при $q < 1$ это возможно только если $\boldsymbol\pi' = \boldsymbol\pi$. Каждая координата $\pi_i = \sum_j p_{ij}\pi_j \ge \varepsilon\sum_j \pi_j = \varepsilon$: точка $\boldsymbol\pi$ лежит во внутреннем треугольнике, где все координаты не меньше $\varepsilon$. Наконец, для любого начального $\mathbf p$: $\|P^k\mathbf p - \boldsymbol\pi\|_1 = \|P^k(\mathbf p - \boldsymbol\pi)\|_1 \le q^k\,\|\mathbf p - \boldsymbol\pi\|_1 \le 2q^k$ — точка $\mathbf p$ шаг за шагом входит в $\boldsymbol\pi$. Для $n$ состояний рассуждение то же, только вместо треугольника — многогранник распределений в $n$-мерном пространстве.

Для самокатов наименьший элемент $P$ равен $0{,}1$, состояний два, и теорема гарантирует множитель $q = 1 - 2 \cdot 0{,}1 = 0{,}8$ за день. На деле недостача сокращалась быстрее, в $0{,}4$ раза, — это второе собственное значение. Лемма даёт оценку, пригодную для любой положительной матрицы сразу, а точную скорость задаёт $|\lambda_2|$.

В книгах по теории вероятностей и в главе 50 матрицу переходов обычно пишут транспонированной, так что в единицу складываются строки, а распределение записывают строкой: $\boldsymbol\pi P = \boldsymbol\pi$. Это та же задача о собственном векторе, только умножение идёт слева. Андрей Марков начал изучать такие цепи в 1906 году, а как он проверял их на тексте «Евгения Онегина», расскажет та глава.

Другая компания работает в двух районах, $A$ и $B$. За день $30$ % самокатов из $A$ уезжают в $B$, а $20$ % самокатов из $B$ — в $A$. Какая доля всех самокатов окажется в районе $A$ через много дней? Ответ дайте обыкновенной или десятичной дробью.

Матрица переходов $P = \left(\begin{smallmatrix} 0{,}7 & 0{,}2 \\ 0{,}3 & 0{,}8 \end{smallmatrix}\right)$. Баланс потоков: $0{,}3\,\pi_A = 0{,}2\,\pi_B$, то есть $\pi_B = 1{,}5\,\pi_A$. Вместе с $\pi_A + \pi_B = 1$ получаем $\pi_A = 0{,}4$. Второе собственное значение равно $\operatorname{tr}P - 1 = 0{,}5$, так что отклонение от равновесия каждый день уменьшается вдвое.

Набить руку на собственных значениях, векторах и цепях Маркова можно в тренажёре. А разобрать по шагам свою матрицу поможет решатель.

Как Google расставил страницы по местам

В 1998 году аспиранты Стэнфорда Сергей Брин и Ларри Пейдж опубликовали статью «Анатомия крупномасштабной гипертекстовой поисковой машины», а осенью того же года основали Google. Одной из главных идей статьи был PageRank — способ оценить важность страницы по ссылкам на неё. Страница важна, если на неё ссылаются важные страницы. Определение похоже на порочный круг, но на самом деле это уравнение на собственный вектор.

Пусть у страницы $j$ есть $L_j$ исходящих ссылок. Она делит свою важность $r_j$ поровну между страницами, на которые ссылается, и каждая получает $r_j/L_j$. Важность страницы — сумма всего, что ей досталось:

$$r_i = \sum_{j \to i} \frac{r_j}{L_j}, \qquad \text{то есть} \qquad \mathbf r = M\mathbf r,$$

где в столбце $j$ матрицы $M$ стоят числа $1/L_j$ напротив страниц, на которые ведёт $j$, и нули в остальных местах. Столбцы $M$ в сумме дают $1$, так что перед нами матрица переходов цепи Маркова, а $\mathbf r$ — её стационарное распределение. У него есть наглядный смысл: это доля времени, которую проводит на каждой странице случайный пользователь, бесконечно щёлкающий по случайным ссылкам.

С настоящим интернетом так просто не выходит. Есть страницы без исходящих ссылок, и случайный пользователь на них застревает. Есть группы страниц, которые ссылаются только друг на друга: как ловушка, они со временем забирают себе всю важность. А если сеть распадается на несвязанные куски, стационарных распределений становится много. Брин и Пейдж починили всё одним приёмом: пользователь с вероятностью $d$ щёлкает по случайной ссылке, а с вероятностью $1 - d$ устаёт и открывает случайную страницу из всех $N$. В статье сказано, что обычно берут $d = 0{,}85$. Со страницы без ссылок будем считать, что пользователь всегда уходит на случайную, — так обычно и делают.

Вероятность пойти по ссылке, обычно $0{,}85$. Матрица ссылок: столбец $j$ делит единицу поровну между страницами, на которые ссылается $j$. Доля, которую каждая из $N$ страниц получает от «телепортации»; $\mathbf 1$ — вектор из единиц. Поскольку $r_1 + \dots + r_N = 1$, уравнение можно записать как $\mathbf r = G\mathbf r$ с матрицей $G = dM + \frac{1 - d}{N}J$, где $J$ — матрица из одних единиц. Пример: для трёх страниц выше при $d = 0{,}85$ получается $\mathbf r = \frac{1}{1769}(686;\ 380;\ 703) \approx (0{,}388;\ 0{,}215;\ 0{,}397)$. Теперь $C$ чуть впереди $A$: часть важности, которую $C$ отдавал $A$, растекается по всем страницам.

Почему у этого уравнения есть решение, причём единственное? Ответ у нас уже в руках. Матрица $G$ — матрица переходов: столбцы $M$ в сумме дают $1$ (со страницы без ссылок пользователь уходит на любую из $N$ с вероятностью $1/N$), столбцы $\frac1N J$ — тоже, а $d + (1 - d) = 1$. При этом все элементы $G$ не меньше $\varepsilon = \frac{1 - d}{N}$. По теореме о стационарном распределении положительной цепи с $n = N$ получаем $q = 1 - N\varepsilon = d$: рейтинг существует, он единственный, каждая страница получает вес не меньше $\frac{1 - d}{N}$, а степенной метод сходится, и ошибка после $k$ шагов не больше $2d^k$. При $d = 0{,}85$ после $50$ итераций это $2 \cdot 0{,}85^{50} \approx 6 \cdot 10^{-4}$. А умножить $G$ на вектор можно за один проход по списку ссылок, даже когда страниц миллиарды.

Наша теорема о положительных цепях — частный случай общего результата о матрицах с положительными элементами.

Идеальная добыча: симметричные матрицы

Вернёмся к кривой $5x^2 + 4xy + 2y^2 = 6$. Её левая часть — квадратичная форма, однородный многочлен второй степени от координат. Любую такую форму можно записать через симметричную матрицу:

$$5x^2 + 4xy + 2y^2 = \begin{pmatrix} x & y \end{pmatrix}\begin{pmatrix} 5 & 2 \\ 2 & 2 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix} = \langle \mathbf x, S\mathbf x\rangle.$$

Коэффициент при $xy$ делится поровну между двумя клетками вне диагонали: $4xy = 2xy + 2yx$. Матрицу, которая не меняется при транспонировании ($S^{\mathsf T} = S$), называют симметричной. С такими матрицами охота удаётся всегда.

Начнём с плоскости, где всё видно на чертеже. Для симметричной матрицы $S$ удобно рассматривать функцию $Q(\mathbf x) = \langle \mathbf x, S\mathbf x\rangle$ на единичной окружности: как мы увидим, её наибольшее и наименьшее значения и есть собственные значения.

Идея: найти на единичной окружности точку, где форма $Q$ максимальна, и заметить, что там её градиент направлен вдоль радиуса. А это и значит, что $S\mathbf u \parallel \mathbf u$.

Запишем единичные векторы как $\mathbf u(\theta) = (\cos\theta;\,\sin\theta)$ и рассмотрим функцию $f(\theta) = Q(\mathbf u(\theta)) = a\cos^2\theta + 2b\sin\theta\cos\theta + c\sin^2\theta$. Она непрерывна на отрезке $[0;\,2\pi]$ и потому принимает там наибольшее значение (теорема Вейерштрасса, глава 53). Точку максимума обозначим $\mathbf u_1 = \mathbf u(\theta_1)$. На чертеже кольцо темнее там, где $Q$ больше. Геометрически в этой точке линия уровня $Q = f(\theta_1)$ касается окружности: вся окружность лежит в области $Q \le f(\theta_1)$, а в точке $\mathbf u_1$ её граница окружности касается. Проверим это вычислением. Функция $f$ периодическая, поэтому точку максимума можно считать внутренней точкой отрезка (сдвинем отрезок длины $2\pi$ так, чтобы $\theta_1$ оказалась в его середине), а во внутренней точке максимума производная равна нулю (глава 27). По правилу дифференцирования произведения $f' = \langle \mathbf u', S\mathbf u\rangle + \langle \mathbf u, S\mathbf u'\rangle$. Для симметричной $S$ второе слагаемое равно первому: $\langle \mathbf u, S\mathbf u'\rangle = \mathbf u^{\mathsf T}S\mathbf u' = (S\mathbf u)^{\mathsf T}\mathbf u' = \langle S\mathbf u, \mathbf u'\rangle$, потому что $S^{\mathsf T} = S$. Значит, $f'(\theta) = 2\langle \mathbf u'(\theta), S\mathbf u(\theta)\rangle$, и в точке максимума $S\mathbf u_1$ перпендикулярен вектору $\mathbf u'(\theta_1) = (-\sin\theta_1;\,\cos\theta_1)$. На плоскости этому вектору перпендикулярны только кратные $\mathbf u_1$, поэтому $S\mathbf u_1 = \lambda_1\mathbf u_1$ для некоторого действительного $\lambda_1$. Это и видно на чертеже: градиент $2S\mathbf u_1$ направлен вдоль радиуса. Умножив равенство скалярно на $\mathbf u_1$, находим $\lambda_1 = \langle \mathbf u_1, S\mathbf u_1\rangle = \max Q$. Возьмём единичный вектор $\mathbf u_2 = (-\sin\theta_1;\,\cos\theta_1)$, перпендикулярный $\mathbf u_1$. Снова по симметрии $\langle S\mathbf u_2, \mathbf u_1\rangle = \langle \mathbf u_2, S\mathbf u_1\rangle = \lambda_1\langle \mathbf u_2, \mathbf u_1\rangle = 0$. Значит, $S\mathbf u_2$ перпендикулярен $\mathbf u_1$, то есть кратен $\mathbf u_2$: $S\mathbf u_2 = \lambda_2\mathbf u_2$ с действительным $\lambda_2 = \langle \mathbf u_2, S\mathbf u_2\rangle$. Любой единичный вектор записывается как $\mathbf x = \cos\alpha\,\mathbf u_1 + \sin\alpha\,\mathbf u_2$, и тогда $Q(\mathbf x) = \lambda_1\cos^2\alpha + \lambda_2\sin^2\alpha$ (смешанные слагаемые пропали, потому что $\mathbf u_1 \perp \mathbf u_2$). Это число между $\lambda_2$ и $\lambda_1$, поэтому $\lambda_2 = \min Q$: внутренняя линия уровня $Q = \lambda_2$ касается окружности в точках $\pm\mathbf u_2$. Мы получили два перпендикулярных единичных собственных вектора с действительными собственными значениями.

В любой размерности рассуждение то же, только окружность становится сферой, а переход к перпендикулярному направлению — индукцией.

Идея: собственный вектор даёт максимум формы на сфере, а перпендикулярное ему подпространство матрица $S$ не выпускает наружу — и там можно повторить то же самое.

Индукция по $n$; при $n = 1$ доказывать нечего. Пусть $n \ge 2$. Функция $Q(\mathbf x) = \langle \mathbf x, S\mathbf x\rangle$ непрерывна на единичной сфере $\{\mathbf x : \|\mathbf x\| = 1\}$ — замкнутом ограниченном множестве, поэтому достигает на ней наибольшего значения в некоторой точке $\mathbf u_1$ (теорема Вейерштрасса для функций нескольких переменных, глава 53). $\mathbf u_1$ — собственный вектор. Возьмём любой единичный $\mathbf w \perp \mathbf u_1$. Окружность $\cos\theta\,\mathbf u_1 + \sin\theta\,\mathbf w$ лежит на сфере, и на ней $Q$ максимальна при $\theta = 0$. Та же выкладка, что на плоскости, даёт $\langle \mathbf w, S\mathbf u_1\rangle = 0$. Вектор $S\mathbf u_1$ перпендикулярен всем векторам, перпендикулярным $\mathbf u_1$, значит, он кратен $\mathbf u_1$: разложим $S\mathbf u_1 = \alpha\mathbf u_1 + \mathbf w_0$ с $\mathbf w_0 \perp \mathbf u_1$, тогда $0 = \langle \mathbf w_0, S\mathbf u_1\rangle = \|\mathbf w_0\|^2$, то есть $\mathbf w_0 = \mathbf 0$. Поэтому $S\mathbf u_1 = \lambda_1\mathbf u_1$, причём $\lambda_1 = \langle \mathbf u_1, S\mathbf u_1\rangle$ — действительное число. Подпространство $W = \{\mathbf w : \langle \mathbf w, \mathbf u_1\rangle = 0\}$ имеет размерность $n - 1$, и $S$ переводит его в себя: если $\mathbf w \perp \mathbf u_1$, то $\langle S\mathbf w, \mathbf u_1\rangle = \langle \mathbf w, S\mathbf u_1\rangle = \lambda_1\langle \mathbf w, \mathbf u_1\rangle = 0$. Выберем в $W$ ортонормированный базис $\mathbf w_1, \dots, \mathbf w_{n-1}$ (его строит процесс Грама — Шмидта из главы 39). В этом базисе преобразование $S$ на $W$ записывается матрицей с элементами $\langle \mathbf w_i, S\mathbf w_j\rangle$, и она снова симметрична: $\langle \mathbf w_i, S\mathbf w_j\rangle = \langle S\mathbf w_i, \mathbf w_j\rangle$. По предположению индукции в $W$ есть ортонормированный базис $\mathbf u_2, \dots, \mathbf u_n$ из собственных векторов с действительными собственными значениями. Векторы $\mathbf u_1, \dots, \mathbf u_n$ единичные и попарно перпендикулярные, то есть образуют ортонормированный базис $\mathbb R^n$ из собственных векторов. По критерию диагонализации $S = UDU^{-1}$, а для матрицы $U$ с ортонормированными столбцами $U^{\mathsf T}U = E$ (элементы произведения — скалярные произведения столбцов), так что $U^{-1} = U^{\mathsf T}$. Характеристический многочлен $S$ равен $(\lambda_1 - \lambda)\cdots(\lambda_n - \lambda)$ с действительными $\lambda_i$, поэтому никаких других, в том числе комплексных, собственных значений у $S$ нет.

Матрицы с ортонормированными столбцами называют ортогональными; подробнее о них — в главе 39. Для $2 \times 2$ действительность собственных значений видна и без всяких максимумов: дискриминант характеристического многочлена $S = \left(\begin{smallmatrix} a & b \\ b & c \end{smallmatrix}\right)$ равен $(a + c)^2 - 4(ac - b^2) = (a - c)^2 + 4b^2 \ge 0$.

В нашем примере след $7$, определитель $6$, собственные значения $6$ и $1$, а собственные векторы $(2;\,1)$ и $(1;\,-2)$ перпендикулярны, как и обещано: $2 \cdot 1 + 1 \cdot (-2) = 0$. Проведём новые оси $X$ и $Y$ вдоль единичных векторов $\frac{1}{\sqrt5}(2;\,1)$ и $\frac{1}{\sqrt5}(1;\,-2)$. В этих координатах матрица диагональна, произведение $XY$ исчезает, и форма становится суммой квадратов.

Первое собственное значение; $X$ — координата вдоль его единичного собственного вектора. Второе собственное значение; $Y$ — координата вдоль перпендикулярного направления. Смешанного слагаемого нет, потому что в собственных координатах $S$ диагональна. Пример: $5x^2 + 4xy + 2y^2 = 6$ превращается в $6X^2 + Y^2 = 6$, то есть $X^2 + \frac{Y^2}{6} = 1$. Это эллипс с полуосями $1$ вдоль $(2;\,1)$ и $\sqrt6 \approx 2{,}449$ вдоль $(1;\,-2)$. Его длинная ось наклонена к оси $Ox$ под углом $\operatorname{arctg}2 \approx 63{,}4°$, а площадь равна $\pi\sqrt6 \approx 7{,}70$.

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

У нашей кривой $\det S = 5 \cdot 2 - 2^2 = 6 > 0$ и след $7 > 0$, так что оба собственных значения положительны — эллипс, как мы и нашли.

Картинка из доказательства работает и как инструмент поиска осей. Нормаль к кривой $\langle \mathbf x, S\mathbf x\rangle = 6$ в точке $\mathbf x$ направлена по градиенту, а градиент квадратичной формы равен $2S\mathbf x$ (глава 32). Концы осей — это точки, где радиус-вектор перпендикулярен кривой, то есть направлен по нормали: $S\mathbf x \parallel \mathbf x$, снова уравнение на собственный вектор. У эллипса в этих точках длина радиуса наибольшая и наименьшая.

Главные оси встречаются всюду, где есть симметричная матрица. У твёрдого тела это оси инерции: у любого тела, будь то книга или космическая станция, есть три взаимно перпендикулярные оси, вокруг которых оно может вращаться, не виляя. Это собственные векторы симметричной матрицы, которую называют тензором инерции. Вращение вокруг осей с наибольшим и наименьшим моментом инерции устойчиво, а вокруг средней — нет. Подбросьте книгу, перетянутую резинкой, закрутив её по очереди вокруг каждой из трёх осей: в одном из трёх случаев она начнёт кувыркаться. В 1985 году космонавт Владимир Джанибеков заметил на станции «Салют-7», что гайка-барашек, закрученная в невесомости, через равные промежутки времени переворачивается. С тех пор это называют эффектом Джанибекова.

Куда дальше

Возьмите облако точек — например, рост и вес тысячи человек — и попробуйте провести через него прямую, которая описывает его лучше всего. Точки на прямой не лежат: система «все точки на одной прямой» несовместна, и ни одно решение не подходит точно. Какое приближение считать лучшим? Ответ снова приведёт к симметричной матрице и её собственным векторам. А у прямоугольной матрицы собственных векторов нет вовсе: она переводит векторы из одного пространства в другое, и $A\mathbf v$ с $\mathbf v$ даже нельзя сравнить. Что их заменяет и как с этим сжимают фотографии, расскажет глава 39.