Линейная
алгебра

Оболочка, независимость, базис

Опр. 1. \mathrm{span}(v_1,\dots,v_k) — множество всех линейных комбинаций. Набор независим, если нулевая комбинация только тривиальная; базис — независимый набор, оболочка которого есть всё пространство; его размер — размерность. Щёлкните стрелку — вектор входит в набор или выходит из него; щёлкните поле — переместится w.

Многочлены — тоже векторы

Задачи 6—7. Многочлен степени \le 2 — это вектор коэффициентов в базисе (x^2, x, 1). Вопрос «выражается ли x^2+2x+3 через данный набор» — это вопрос о совместности СЛУ, столбцы которой суть данные многочлены.

Три элементарных преобразования

Опр. 2. Над строками разрешены три операции: перестановка двух строк, умножение строки на ненулевой скаляр, прибавление к строке другой строки с коэффициентом. Каждая из них есть умножение слева на элементарную матрицу E — единичную, к которой применили ту же операцию.

Алгоритм: ступенчатый и улучшенный вид

Метод Гаусса по шагам

Задача 5. Элементарные преобразования строк не меняют множество решений. На каждом шаге видно, из какой строки, с каким коэффициентом и во что вычитают: дуга подписана коэффициентом, под каждым новым числом — его арифметика.

Сколько решений и почему

Та же система в другом поле

Задача 8. Метод Гаусса использует только четыре арифметических действия, поэтому работает над любым полем. Ниже — система из плана по модулю 5; переключение поля меняет ответ, но не алгоритм.

Обратная матрица: [A | E] → [E | A⁻¹]

Задачи 9—11. Приписываем к A единичную матрицу и приводим левую половину к E. Те же элементарные преобразования превращают E в A^{-1}: их произведение и есть обратная матрица. Стоимость — O(n^3).

Определитель: определение

Опр. 5. \det A = \sum_{\sigma\in S_n}\mathrm{sgn}(\sigma) \prod_{i} a_{i\sigma(i)}: из каждой строки и каждого столбца берётся ровно один элемент, знак — чётность перестановки. Ниже все 3! = 6 слагаемых.

Определитель элементарных матриц

Определитель мультипликативен: \det(EA) = \det E \cdot \det A. Поэтому достаточно знать определитель каждой из трёх элементарных матриц — и становится ясно, как каждая операция метода Гаусса меняет ответ.

Определитель за O(n³)

Задачи 12—15. Приводим матрицу к ступенчатому виду, не нормируя строки: определитель равен произведению ведущих элементов, умноженному на (-1) в степени числа перестановок строк.

Пространство \mathbb{Z}_2^n

Задачи 16—17. Над \mathbb{Z}_2 сложение — это xor, а линейная комбинация — xor подмножества. Поэтому «сколько различных чисел получается как xor подмножеств» — вопрос о размере линейной оболочки. Щёлкните вершину куба, чтобы проверить принадлежность.

xor-базис: вставка числа

Базис хранится в массиве по ведущему разряду. Новое число гасит старшими базисными векторами свои занятые разряды; если что-то осталось — оно встаёт на свой свободный разряд, иначе число линейно зависимо. Одна вставка — O(\log C).

Максимальный xor

Задачи 18—19. Идём от старшего разряда: базисный вектор берётся, если увеличивает ответ. Приведённый базис (обратный ход) делает проверку излишней и снижает стоимость запроса до O(\log n).

k-е число и счёт до x

Задача 20. В приведённом базисе значение строго возрастает по номеру: разряд номера отвечает за независимый ведущий бит. Отсюда — и k-е по возрастанию, и количество представимых чисел \le x.

Критерий совершенного паросочетания

Задача 21. Теорема (Татт). Пусть T_{ij} = x_{ij}, T_{ji} = -x_{ij} для каждого ребра и 0 иначе. В графе есть совершенное паросочетание тогда и только тогда, когда \det T \not\equiv 0 как многочлен.

Число остовных деревьев

Задача 22. Теорема (Кирхгоф). Пусть L = D - A — матрица Кирхгофа. Тогда для любой вершины i число остовных деревьев равно \det L_{\hat i\hat i} — минору порядка n-1. Щёлкните ребро — оно появится или исчезнет; щёлкните вершину — вычеркнется другая строка.

Почему это верно: L = B·Bᵀ

Ориентируем каждое ребро произвольно и построим матрицу инцидентности B: +1 у начала, -1 у конца. Тогда BB^{T} = L, и минор раскрывается формулой Коши—Бине.

Одна процедура — семь задач