埃尔米特

时间:2023-06-04 20:55:09编辑:奇事君
简介

在线性代数中,埃尔米特形式是整数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

是三角形的。

上一篇:藤黄微球菌

下一篇:自燃物品