Одновременное сжатие

Дана матрица размера $n\times n$. Задает ли она сжатие пространства $\mathbb{R}^n$? Это легко проверить: евклидова норма матрицы должна быть меньше единицы. Но в большинстве приложений вопрос ставится по-другому: существует ли норма в $\mathbb{R}^n$, в которой данная матрица задает сжатие? Ответ дает теорема Ляпунова: спектральный радиус матрицы (наибольший модуль собственных значений) должен быть меньше единицы. Причем, искомую норму всегда можно взять эллипсоидальной, т.е. с единичным шаром в виде эллипсоида. Задача резко усложняется, если дана не одна матрица, а несколько. Являются ли они сжатиями в какой-то (одной на всех!) норме в $\mathbb{R}^n$? Теорема Ляпунова в этом случае не работает, и спектральные радиусы данных матриц не помогут. Задача в такой постановке появилась в 1960 г. в работе Рота и Стрэнга при исследовании нормированных алгебр. Независимо Фюрстенберг и Кестен (1960) сформулировали вероятностный аналог той же задачи, что привело к появлению показателя Ляпунова. Одновременное сжатие нашло множество приложений: в математической физике, в теории приближений, в теории всплесков, в комбинаторике, в теории формальных языков, и т.д. Однако даже для неотрицательных матриц распознавание одновременного сжатия и построение соответствующей нормы является NP-сложной задачей. А для произвольных матриц она и вовсе алгоритмически неразрешима (Блондель, Цициклис, 2000). Тем не менее, геометрические соображения позволяют построить весьма эффективные методы. Как такое оказалось возможным – мы обсудим на лекции, а заодно и сформулируем ряд открытых проблем.