Собственные значения и собственные векторы

Растяните резиновый лист за края. Почти каждая нарисованная на нём стрелка поворачивается, но некоторые особые стрелки только удлиняются или укорачиваются, сохраняя направление. Для матрицы такие особые направления — её собственные векторы, а коэффициенты растяжения — собственные значения. Они описывают собственные частоты колебаний моста, предельное поведение цепи Маркова и идею первого рейтинга Google. Немецкое eigen в международном термине означает «собственный».

Определение и геометрический смысл

Геометрически A не поворачивает v, а лишь растягивает его в λ раз. При λ > 1 вектор удлиняется, при 0 < λ < 1 укорачивается, при λ < 0 ещё и меняет направление на противоположное, а λ = 0 означает, что A «сжимает» v в нулевой вектор. Любой ненулевой вектор, пропорциональный собственному, тоже собственный: A(cv) = cAv = λ(cv). Поэтому на самом деле мы ищем собственные направления.

Характеристическое уравнение

Как найти собственные значения без угадывания? Перепишем Av = λv в виде Av − λIv = 0, то есть (A − λI)v = 0. Эта однородная система имеет ненулевое решение v тогда и только тогда, когда матрица A − λI вырождена, то есть её определитель равен нулю.

Диагонализация

Пусть у матрицы A размера n × n есть n линейно независимых собственных векторов v₁, …, vₙ. Запишем их столбцами матрицы P, а собственные значения — на диагональ D. Равенства Avᵢ = λᵢvᵢ вместе означают AP = PD, откуда A = PDP⁻¹. Это всегда возможно, если все n собственных значений различны, а вещественная симметричная матрица всегда диагонализуется с перпендикулярными собственными векторами.

Применения: цепи Маркова, PageRank, PCA

Цепь Маркова описывает систему, которая переходит из состояния в состояние с постоянными вероятностями. Пусть два кафе у студенческого городка, A и B, делят между собой студентов: каждую неделю 80% посетителей A остаются верны ему, а 20% уходят в B; из B 30% переходят в A, а 70% остаются. Записав доли столбцом xₖ = [aₖ; bₖ], получим xₖ₊₁ = Txₖ, где сумма каждого столбца T равна 1.

PageRank. Исходная идея Google рассматривает интернет как гигантскую цепь Маркова: случайный пользователь переходит по ссылкам, а важность страницы — её доля в стационарном распределении, то есть собственный вектор «матрицы Google» для λ = 1. При миллиардах страниц его находят степенным методом: берут любой вектор и снова и снова умножают его на матрицу. PCA (метод главных компонент). Ковариационная матрица данных симметрична; её собственный вектор с наибольшим собственным значением указывает направление, в котором данные разбросаны сильнее всего. Оставив лишь несколько таких главных компонент, данные сжимают, например в распознавании лиц.

import numpy as np

A = np.array([[4, 1], [2, 3]])
values, vectors = np.linalg.eig(A)
print(values)
print(np.linalg.matrix_power(A, 10))

T = np.array([[0.8, 0.3], [0.2, 0.7]])
x = np.array([0.5, 0.5])
for week in range(30):
    x = T @ x
print(np.round(x, 4))

[5. 2.]
[[6510758 3254867]
 [6509734 3255891]]
[0.6 0.4]