Ранг матрицы: информационная размерность и фундаментальная теорема

Строчный и столбцовый ранг: чудо совпадения

С матрицей неразрывно связаны два линейных подпространства: пространство строк (натянутое на векторы-строки) и пространство столбцов (натянутое на векторы-столбцы). Строчным рангом называется максимальное количество линейно независимых строк матрицы, а столбцовым рангом — максимальное количество линейно независимых столбцов. На первый взгляд, это совершенно разные геометрические объекты, особенно для прямоугольных матриц (например, размера 10 на 1000). Однако Фундаментальная теорема линейной алгебры утверждает поистине магический факт: для любой матрицы над любым полем строчный ранг всегда в точности равен столбцовому рангу. Это число и называется просто рангом матрицы (rank A).

Теорема о базисном миноре

Как алгоритмически найти ранг? В теоретической алгебре используется понятие минора — определителя квадратной подматрицы, полученной вычеркиванием некоторых строк и столбцов. Теорема о базисном миноре гласит, что ранг матрицы равен максимальному порядку (размеру) отличного от нуля минора этой матрицы. Строки и столбцы, на пересечении которых стоит этот ненулевой минор, называются базисными. Они образуют линейно независимую подсистему, а все остальные строки и столбцы матрицы гарантированно выражаются через них в виде линейных комбинаций. Хотя этот метод красив аналитически, на практике вычисление всех возможных миноров для больших матриц требует астрономического времени, поэтому компьютеры его не используют.

Вычисление ранга методом Гаусса и SVD

На практике самым быстрым ручным способом нахождения ранга является приведение матрицы к ступенчатому виду с помощью элементарных преобразований строк (прямой ход метода Гаусса). Поскольку элементарные преобразования не меняют линейных зависимостей, ранг ступенчатой матрицы в точности равен количеству ее ненулевых строк. Для вычислительных машин, подверженных ошибкам округления, определение того, является ли число «настоящим» нулем или просто погрешностью процессора, представляет проблему. Поэтому в профессиональном программировании (в библиотеках BLAS и LAPACK) ранг вычисляется исключительно через Сингулярное разложение (SVD). Ранг матрицы строго равен количеству ее ненулевых (или превышающих машинный эпсилон) сингулярных чисел.

Ранговая факторизация и сжатие данных

Понимание ранга открывает путь к мощным алгоритмам сжатия данных. Если огромная матрица A размера m на n имеет небольшой ранг r (где r значительно меньше и m, и n), ее можно факторизовать (разложить) в произведение двух маленьких матриц: A = C * F, где матрица C имеет размер m на r, а матрица F — размер r на n. Вместо хранения m*n чисел, нам достаточно хранить r*(m+n) чисел. Это свойство, известное как низкоранговая аппроксимация, лежит в основе алгоритмов обработки изображений, рекомендательных систем (предсказание оценок пользователей фильмам) и методов латентно-семантического анализа в обработке естественного языка, где огромные разреженные матрицы текстов заменяются плотными матрицами малого ранга.