埃爾米特形式
埃爾米特形式
埃爾米特形式(Hermite Normal form)複流形上的一種特殊雙線性形式。
在線性代數中，埃爾米特形式是整數Z上矩陣的簡化階梯形式的一個類似形式。就像簡化的階梯形式可以用來解決關於線性系統的解的問題Ax = b其中x在Rn中，埃爾米特形式可以解決關於線性系統Ax = b的解的問題，其中這個時間x僅限於具有整數坐標。埃爾米特形式的其他應用包括整數規劃、密碼學，和抽象代數。
如果存在平方單模矩陣 U，其中 H = UA且 H具有以下限制，則具有整數項的 m× n矩陣 A具有（行）埃爾米特形式（HNF） H：
1.i> j
2.非零行的前導係數（從左邊開始的第一個非零輸入，也稱為樞軸）始終嚴格地位於其上一行的前導係數的右側。
3.樞軸下方的元素為零，樞軸上方的元素非負，嚴格小於樞軸。
第三個條件在作者之間不是標準的，例如有些來源強迫非樞軸是非正的或者對它們沒有任何的標誌限制。然而，這些定義是通過使用不同的單模矩陣等效 U。甲幺模矩陣是一個正方形可逆整數矩陣，其行列式是1或-1。
如果有一個正方形的單模矩陣 U，其中 H = AU和 H有以下限制，那麼具有整數項的m×n矩陣 A具有（列）Hermite範式（HNF） H：
1.i
2.非零列的前導係數（從頂部開始的第一個非零的入口，也稱為支點）始終嚴格低於之前列的前導係數。
3.樞軸右側的元素為零，樞軸左側的元素非負，嚴格小於樞軸。
請注意，行樣式定義具有在左邊乘以 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是三角形的。
目錄