Эрмитова нормальная форма — это аналог ступенчатого вида матрицы для матриц над кольцом целых чисел. В то время, как ступенчатый вид матрицы используется для решения систем линейных уравнений вида для , эрмитова нормальная форма может быть использована для решения линейных систем диофантовых уравнений, в которых подразумевается, что . Эрмитова нормальная форма используется в решении задач целочисленного программирования, криптографии и общей алгебры.
Определение Матрица является эрмитовой нормальной формой целочисленной матрицы если есть унимодулярная матрица такая что и удовлетворяет следующим ограничениям:
является верхне-треугольной, то есть, если и любая строка, целиком состоящая из нулей находится ниже всех остальных. Ведущий элемент любой ненулевой строки всегда положителен и лежит правее ведущего коэффициента строки над ней. Элементы под ведущими равны нулю, а элементы над ведущими неотрицательны и строго меньше ведущего.
Некоторые авторы в третьем условии требуют, чтобы элементы были неположительными или вообще не накладывают на них знаковых ограничений.
Существование и единственность эрмитовой нормальной формы Эрмитова нормальная форма существует и единственна у любой целочисленной матрицы .
Примеры В примерах ниже матрица является эрмитовой нормальной формой матрицы , а соответствующей унимодулярной матрицей является матрица такая что .
Алгоритмы Первые алгоритмы вычисления эрмитовой нормальной формы датируются 1851 годом. При этом первый алгоритм, работающий за строго полиномиальное время был разработан лишь в 1979 году. Один из широко используемых классов алгоритмов для приведения матрицы к эрмитовой нормальной форме основан на модифицированном методе Гаусса. Другим распространённым методом вычисления эрмитовой нормальной формы является LLL-алгоритм.
Применения
Вычисления в решётках Обычно решётки в имеют вид , где . Если рассмотреть матрицу , чьи строки составлены из векторов , то её эрмитова нормальная форма будет задавать некоторый единственным образом определённый базис решётки. Данное наблюдение позволяет быстро проверять, совпадают ли решётки, порождённые строками матриц и , для чего достаточно проверить, что у матриц совпадают их эрмитовы нормальные формы. Аналогичным образом можно проверить, является ли решётка подрешёткой решётки , для чего достаточно рассмотреть матрицу , полученную из объединения строк и . В такой постановке является подрешёткой если и только если совпадают эрмитовы нормальные формы и .
Диофантовы линейные уравнения Система линейных уравнений имеет целочисленное решение если и только если система имеет целочисленное решение, где — эрмитова нормальная форма матрицы .
Реализация Вычисление эрмитовой нормальной формы реализовано во многих системах компьютерной алгебры:
HermiteForm в Maple HermiteDecomposition в Mathematica hermiteForm в MATLAB hermite_form в SageMath
См. также Нормальная форма Смита Нормальная форма Хауэлла Диофантово уравнение
Примечания
Категория:Линейная алгебра Категория:Нормальные формы матриц