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