Одной из самых ресурсоемких операций в вычислительной линейной алгебре является обращение больших матриц (вычислительная сложность O(n^3)). В задачах онлайн-машинного обучения, фильтрации сигналов в реальном времени и системной идентификации данные часто поступают последовательно (по одному вектору). При получении новой порции данных матрица системы немного изменяется, и нам требуется найти ее новую обратную матрицу. Пересчитывать обратную матрицу с нуля каждый миллисекунду для систем с тысячами переменных — физически невозможно. На помощь приходит потрясающий математический инструмент — Формула Шермана-Моррисона и ее матричное обобщение, Тождество Вудбери (Woodbury matrix identity), которые позволяют вычислять обновления за сотые доли секунды.

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

Среди всех разреженных матриц линейной алгебры существует класс с абсолютно исключительной и элегантной структурой — трехдиагональные матрицы. У этих матриц ненулевые элементы располагаются исключительно на главной диагонали и на двух соседних побочных диагоналях (чуть выше и чуть ниже главной), образуя узкую ленту. Вне этой ленты стоят строгие нули. Трехдиагональные матрицы возникают повсеместно: при численном решении дифференциальных уравнений методом конечных разностей (например, уравнения теплопроводности для одномерного стержня), в квантовой механике (одномерные решетки) и в алгоритмах Ланцоша. Изучение их алгебраических свойств раскрывает удивительную связь между матрицами и классической теорией ортогональных многочленов (полиномов).

Определитель матрицы известен каждому студенту, изучающему линейную алгебру. Его формула представляет собой сумму всевозможных произведений n элементов матрицы, взятых по одному из каждой строки и каждого столбца, где перед каждым произведением ставится знак плюс или минус в зависимости от четности перестановки. Но что произойдет, если мы уберем из этой формулы все минусы и просто сложим все эти произведения со знаком плюс? Мы получим алгебраическую функцию, которая называется Перманентом матрицы (Permanent). На первый взгляд, перманент выглядит как более простая и естественная версия определителя, однако за обманчивой простотой скрывается одна из величайших вычислительных проблем тысячелетия, стоящая на стыке линейной алгебры, комбинаторики и квантовой механики.