在线性代数中,埃尔米特形式是整数Z上矩阵的简化阶梯形式的一个类似形式。就像简化的阶梯形式可以用来解决关于线性系统的解的问题其中x在中,埃尔米特形式可以解决关于线性系统的解的问题,其中这个时间x仅限于具有整数坐标。埃尔米特形式的其他应用包括整数规划、密码学,和抽象代数。定义行埃尔米特形式
如果存在平方单模矩阵
U
,其中 且H
具有以下限制,则具有整数项的 矩阵A
具有(行)埃尔米特形式(HNF)H
:1.
,
2.非零行的前导系数(从左边开始的第一个非零输入,也称为枢轴)始终严格地位于其上一行的前导系数的右侧。
3.枢轴下方的元素为零,枢轴上方的元素非负,严格小于枢轴。
第三个条件在作者之间不是标准的,例如有些来源强迫非枢轴是非正的或者对它们没有任何的标志限制。然而,这些定义是通过使用不同的单模矩阵等效
U
。甲幺模矩阵是一个正方形可逆整数矩阵,其行列式是1或-1。列埃尔米特形式如果有一个正方形的单模矩阵
U
,其中 和H
有以下限制,那么具有整数项的矩阵A
具有(列)Hermite范式(HNF)H
:1.
,
2.非零列的前导系数(从顶部开始的第一个非零的入口,也称为支点)始终严格低于之前列的前导系数。
3.枢轴右侧的元素为零,枢轴左侧的元素非负,严格小于枢轴。
请注意,行样式定义具有在左边乘以
A
的单模矩阵U
(意味着U
在A
的行上作用),而列样式定义在A
的列上具有单模矩阵行为。Hermite范式的两个定义只是彼此的转置。Hermite范式的存在性和唯一性每个具有整数项的 矩阵
A
具有唯一的矩阵H
(HNF),使得对于某个平方单模矩阵U
。示例在下面的例子中,
H
是矩阵的埃尔米特正常形式A
,和U
是单模矩阵,使 。如果A只有一行,则或,取决于A的单行是否具有正的或负的超前系数。算法
有许多算法计算可追溯到1851年的Hermite标准形式。直到1979年,才开始计算在强多项式时间运行的Hermite标准形式的算法;也就是说,计算Hermite范数的步数由输入矩阵的维数中的多项式来界定,算法所使用的空间(中间数)由二进制编码中的多项式输入矩阵中数字的大小。一类算法是基于高斯消元的,因为特殊的基本矩阵被重复使用。所述的LLL算法也可以用来有效地计算Hermite范式。
应用程序格子计算典型的晶格中 具有形式 其中 是。如果矩阵
A
的列是,则格可以与矩阵的列相关联,并且A
被认为是L
的基础。由于Hermite范式是唯一的,所以可以用来回答关于两个格点描述的许多问题。接下来,表示由A的列生成的格。因为基础在矩阵A
的列中,所以必须使用列式Hermite范式。给定一个格点A
和A'的
两个基础,等价问题是决定是否 这可以通过检查A
和A'
的列式Hermite标准形式是否 相同直到添加零列来完成。这个策略对于决定格是否是一个子集也是有用的当且仅当),判断一个向量v是否在一个格中(当且仅当 )和其他计算。整数解线性系统线性系统
的
具有整数解X
当且仅当所述系统 具有整数溶液y
其中 和H
是列式的隐士正常形式H
。检查是否具有整数解比容易,因为矩阵H
是三角形的。