Ликбез по линейной алгебре

Определение. Функция $f: \mathbb{R}^n \to \mathbb{R}^m$ называется линейной, если для неё выполнено

  1. $ f(x+y) = f(x) + f(y) $
  2. $ f(ax) = a f(x), \; a \in R $

Примеры:

  • $ f(x) = 0 $
  • $ f(x) = x $
  • $ f(x) = 2 x_1 - 2 x_2 - 8 x_3 $ (из $\mathbb{R}^3$ в $\mathbb{R}$)
  • $ f(x) = (x, -x, 0) $ (из $\mathbb{R}$ в $\mathbb{R}^3$)

Линейная алгебра занимается изучением линейных функций. Некоторые полезные свойства:

  • Сумма линейных функций — линейная функция.
  • Сумма коммутативна: $f+g = g+f$).
  • Сумма ассоциативна: $(f+g)+h = f+(g+h)$.
  • Композиция $f(g(x)) = (f \circ g)(x)$ линейных функций — линейная функция.
  • Композция ассоциативна: $(f \circ g) \circ h = f \circ (g \circ h) = f \circ g \circ h$.
  • Композиция в общем случае не коммутативна.
    Пример: $f = (-x_2, x_1)$ — поворот точки на плоскости на прямой угол, $g = (x_1, 0)$ — проекция на $Ox$. Почти для всех точек порядок этих операций важен.

Все свойства можно вывести лишь из этих двух пунктов в определении.

Что такое матрица?

Можно показать, что любую линейную функцию $f: \mathbb{R}^n \to \mathbb{R}^m$ можно представить в таком виде:

$$ f(x) = \begin{pmatrix} a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n \\ a_{21} x_1 + a_{22} x_2 + \ldots + a_{2n} x_n \\ \ldots \\ a_{m1} x_1 + a_{m2} x_2 + \ldots + a_{mn} x_n \\ \end{pmatrix} $$

Матрицы ввели просто как очень компактную запись этих коэффициентов $a_{ij}$.

$$ A = \begin{pmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \\ \end{pmatrix} $$

Каждой линейной функции из $\mathbb{R}^n$ в $\mathbb{R}^m$ соответствует какая-то матрица размера $n \times m$ (первое число это количество строк, второе — столбцов), и наоборот. Элемент на пересечении $i$-го строки и $j$-го столбца будем обозначать $A_{ij}$. Не перепутайте.

Пусть линейной функции $f$ соответствует матрица $A$, а функции $g$ — $B$. Тогда композиции этих функций $h = f \circ g$ будет соответствовать произведение $C$ матриц $A$ и $B$, определяемое так:

$$ C = AB: C_{ij} = \sum_{i=1}^{k} A_{ik} B_{kj} $$

Можете убедиться в этом, расписав, какие коэффициенты получаются, если формулы из $g$ подставить в $f$.

Когда перемножаете руками, удобно думать так: элемент на пересечении $i$-го столбца и $j$-той строки — это скалярное произведение $i$-той строки $A$ и $j$-того столбца $B$. Заметим, что это накладывает ограничение на размерности перемножаемых матриц: если первая матрица имеет размер $n \times k$, то вторая должна иметь размер $k \times m$, то есть «средние» размерности обязательно должны совпадать.

Исходное выражение для $f(x)$ теперь можно компактно записать как $f(x) = Ax$ вместо $m$ уравнений с $n$ слагаемыми в каждом.

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

Из-за такого взаимно однозначного соотношения все ранее упомянутые свойства линейных функций переносятся и на матрицы:

  • Сумма матриц $A$ и $B$ — матрица $C = A+B: C_{ij} = A_{ij} + B_{ij}$.
  • Сумма коммутативна: $A+B = B+A$)
  • Сумма ассоциативна: $(A+B)+C = A+(B+C)$
  • Умножение ассоциативно: $(AB)C = A(BC) = ABC$.
  • Умножение в общем случае не коммутативно.

Пример: матрица поворота в 2d. $$ \begin{pmatrix} \cos \alpha & -\sin \alpha \\ \sin \alpha & \cos \alpha \\ \end{pmatrix} $$

Пример: матрица проецирования на $Ox$ в 3d. $$ \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{pmatrix} $$

Пример: матрица «свапни $x$ и $y$». $$ \begin{pmatrix} 0 & 1 \\ 1 & 0 \\ \end{pmatrix} $$

Напишем класс, который реализует матричное умножение.

In [ ]:
struct matrix {
    int n, m;
    int t[];
    matrix (int _n, int _m) {
        n = _n, m = _m;
        t = new int(n*m);
        memset(t, 0, sizeof t);
    }
    int[] operator[] (int k) {
        return t[k*m];
    }
}

matrix operator* (matrix a, matrix b) {
    matrix c(a.n, b.m);
    for (int i = 0; i < a.n; i++)
        for (int j = 0; j < b.m; j++)
            for (int k = 0; k < a.m; k++)
                c[i][j] += a[i][k] * b[i][k];
     return c;
}

Динамика

Некоторые динамики можно выразить в терминах матричного умножения.

Расмотрим конкретный пример — Фибоначчи. Ну а чем не динамика?

$$ \begin{pmatrix} f_{n+1} \\ f_{n+2} \\ \end{pmatrix} = \begin{pmatrix} 0+f_{n+1} \\ f_{n}+f_{n+1} \\ \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \\ \end{pmatrix} \begin{pmatrix} f_{n} \\ f_{n+1} \\ \end{pmatrix} $$

Обозначим за $A$ эту матрицу перехода. Чтобы посчитать $n$-е число Фибоначчи, нужно применить $n$ раз эту матрицу к вектору $(f_0, f_1) = (0, 1)$.

Вспомним, что умножение коммутативно. Значит, мы можем применить бинарное возведение в степень к матрицам:

$$ A^8 = A^{2^{2^{2}}} = ((AA)(AA))((AA)(AA)) $$

Это будет работать за $O(n^3 \log n)$. Мы делаем $O(n^3)$ операций для одного умножения, а всего их нужно сделать $O(\log n)$. Кстати, наука знает и более быстрые способы перемножить матрицы, но на контестах они не нужны.

In [ ]:
matrix binpow (matrix a, int p) {
    matrix b(n, n);
    for (int i = 0; i < n; i++)
        b[i][i] = 1;
    while (p) {
        if (p&1) b = b*a;
        a = a*a;
        p >>= 1;
    }
    return b;
}

Единичной называется матрица, у которой единицы стоят на главной диагонали. Обозначение: $I$.

$$ \begin{vmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{vmatrix} $$

В плане умножения она действительно ведет себя как единица: $AI = A = IA$. В коде она используется вместо единицы.

В общем случае, линейная рекуррента $f_n = a_1 f_{n-1} + a_2 f_{n-2} + \ldots + a_k f_{n-k}$ имеет такую матрицу перехода:

\begin{pmatrix} 0 & 1 & 0 & \ldots & 0 \\ 0 & 0 & 1 & \ldots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & 1 \\ a_k & a_{k-1} & a_{k-2} & \ldots & a_1 \\ \end{pmatrix}

Матрица смежности

У перемножения матриц смежности есть комбинаторный смысл — количество способов попасть из вершины $a$ в вершину $b$ за определенное количество переходов. Иными словами, (G^n)_{ab} будет равно количеству способов попасть из $a$ в $b$, используя ровно $n$ переходов.

Когда нам нужна только информация, можно ли дойти из $a$ в $b$ (количество способов не важно), то решение можно ускорить (см. Битсет).

Обобщения

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

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

Определитель

Определителем кадратной матрицы $A$ называется такое выражение:

$$ \det A = |A| = \ldots $$

Где $\epsilon$ — чётность числа инверсий в перестановке ($-1$ или $+1$). То есть, чтобы его посчитать «в лоб», нужно перебрать все перестановки элементов, взять соответствующие элементы со столбцов и добавить в сумму с нужным знаком. Например:

$$ \begin{vmatrix} a & b \\ c & d \\ \end{vmatrix} = ad - bc $$

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

В двумерном случае его значение равно ориентированной площади (проверьте — сравните с формулой для векторного произведения). Для трехмерного — объему, в общем случае это какой-то «гипер-объем». Доказывать это утверждение мы не будем.

Базис

Базисом множества называется набор векторов, через который можно выразить все вектора этого множества и только их.

Базисы есть не только в линейной алгебре. Например, $\{1, x, x^2\}$ является базисом всех квадратных трёхчленов. Или $\{\neg, \land, \lor\}$ является базисом всех логических выражений (то есть всё можно выразить через И, ИЛИ и НЕ). В произвольном языке программирования можно выделить какой-то набор команд, через который можно будет написать всё что угодно, и он тоже в этом смысле будет базисом.

Метод Крамера и easy пересечение прямых

Пусть нам надо пересечь две прямые.

$$ \begin{cases} a_1 x + b_1 y + c_1 = 0 a_2 x + b_2 y + c_2 = 0 \end{cases} $$

Это то же самое, что найти такие коэффициенты $x$ и $y$, что

$$ x \vec{a} + y \vec{b} = -\vec{c} $$

Площадь параллелограмма, натянутого на $\vec{a}$ и $\vec{b}$, равна векторному произведению, или детерминанту.

По сути, нам нужно выразить $c$ в другом базисе. Давайте спроецируем её на $a$.

Аналогично, напрягите воображение и спроецируйте эту точку в $n$-мерном пространстве. Это уже сложно, да?

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

Очень часто у матриц есть собственные вектора -- те, которые не меняют направление.

$ Av = k v $, где $k \neq 0$.

$ Av - kv = (A-kI)v = 0 $. Это означает

Вообще, собственные вектора в линейной алгебре имеют почти такое же значение, как простые числа в арифметике.

Системы уравнений и метод Гаусса

Иногда встречаются задачи, требующие решения системы линейных уравнений. Очень большая часть из них на самом деле над полем $\mathbb{Z}_2$ — то есть все числа по модулю 2. К примеру: есть $n$ переключателей лампочек, каждый активированный переключатель меняет состояние (включает или выключает) какого-то подмножества из $n$ лампочек. Известно состояние всех лампочек, нужно восстановить состояние переключаетелей.

Нас по сути просят решить следующую систему:

$$ \begin{cases} a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n \equiv b_1 \pmod 2\\ a_{21} x_1 + a_{22} x_2 + \ldots + a_{2n} x_n \equiv b_2 \pmod 2\\ \ldots \\ a_{n1} x_1 + a_{n2} x_2 + \ldots + a_{nn} x_n \equiv b_n \pmod 2 \end{cases} $$

Здесь $x$ — состояния переключателей, $b$ — состояния лампочек, $A$ — информация о том, влияет ли переключатель на лампочку.

Метод Крамера неоптимален — там $O(n^4)$ операций.

В таком случае можно значительно ускорить и упростить обычный метод Гаусса:

In [ ]:
t gauss (matrix a) {
    for (int i = 0; i < n; i++) {
        int nonzero = i;
        for (int j = i+1; j < n; j++)
            if (a[j][i])
                nonzero = j;
        swap(a[nonzero], a[i]);
        for (int j = 0; j < n; j++)
            if (j != i && a[j][i])
                a[j] ^= a[i];
    }
    t x;
    for (int i = 0; i < n; i++)
        x[i] = a[i][n] ^ a[i][i];
    return x;
}

Код находит вектор $x$ из уравнения $Ax = b$ при условии, что решение существует и единственно. Для простоты кода, предполагается, что вектор $b$ приписан справа к матрице $A$.

Часто эту систему нужно решить по модулю 2. Тогда код значительно упрощается и ускоряется (опять же, см. Битсет).