헤르미트 정상형

선형 대수학에서 헤르미트 정규 형태는 정수 Z에 걸친 행렬에 대한 축소된 에슐론 형태의 아날로그다. 축소된 에슐론 형태를 사용하여 x가 R에ⁿ 있는 선형계 Ax=b에 대한 해법에 관한 문제를 해결할 수 있듯이, 헤르미테 정상 형태는 이 시간 x가 정수 좌표만을 갖는 것으로 제한되는 선형계 Ax=b에 대한 해법에 관한 문제를 해결할 수 있다. Hermite 정상 형태의 다른 응용 프로그램으로는 정수 프로그래밍,^[1] 암호학,^[2] 추상 대수학 등이 있다.^[3]

정의

다양한 작가들은 행 스타일이나 칼럼 스타일 중 하나로 헤르미트의 정상적인 형태에 대해 이야기하는 것을 선호할 수 있다. 그들은 본질적으로 전이될 때까지 동일하다.

행형 헤르미트 보통형

정수 입력의 m by n 행렬 A는 H=UA와 H가 다음과 같은 제한을 갖는 정사각형 단변형 행렬 U가 있는 경우 Hermite 정규 형태 H를 가진다.^[4][5][6]

1. H는 상위 삼각형(즉, i의 경우 h_ij = 0 > j)이며, 0의 모든 행은 다른 행 아래에 위치한다.
2. 0이 아닌 행의 선행 계수(왼쪽에서 첫 번째 0이 아닌 입력, 피벗이라고도 함)는 항상 그 위 행의 선행 계수의 우측에 엄격하게 위치하며, 더욱이 양수적이다.
3. 피벗 아래의 원소는 0이고 피벗 위의 원소는 음이 아니며 피벗보다 엄격히 작다.

세 번째 조건은 저자들 사이에서 표준이 아니다. 예를 들어, 일부 출처에서는 비-피봇을 비양성으로^[7][8] 강제하거나 표지판 제한을 두지 않는다.^[9] 그러나 이러한 정의는 다른 단변성 행렬 U를 사용함으로써 동등하다. 단변성 행렬은 결정인자가 1 또는 -1인 정사각형 반전성 정수 행렬이다.

기둥 스타일 헤르미트 정규 형태

정수 입력의 m by n 행렬 A는 H=AU와 H가 다음과 같은 제한을 갖는 정사각형 단변형 행렬 U가 있는 경우 Hermite 정규 형태 H를 가진다.^[8][10]

1. H는 하위 삼각형이고, h_ij = i < j의 경우 0이며, 0의 어떤 열도 우측에 위치한다.
2. 0이 아닌 열의 선행 계수(위로부터 첫 번째 0이 아닌 입력, 피벗이라고도 함)는 항상 그 이전의 열 선행 계수보다 엄격히 아래에 있다. 더욱이 양수다.
3. 피벗 우측의 원소는 0이고 피벗 좌측의 원소는 음이 아니며 피벗보다 엄격히 작다.

행 형식 정의에는 왼쪽에 A를 곱한 단모형 행렬 U가 있는 반면(U는 A의 행에 작용한다는 의미) 열 형식 정의에는 A의 열에 대한 단모형 행렬 동작이 있다. 헤르미트의 정상적인 형태에 대한 두 가지 정의는 단순히 서로에 대한 전이일 뿐이다.

헤르미테 정상 형태의 존재와 고유성

정수 항목이 있는 매 m by n 매트릭스 A는 일부 정사각형 단변형 매트릭스 U에 대한 H=UA와 같은 n 매트릭스 H를 갖는 고유한 m을 가진다.^[5][11][12]

예

아래 예에서 H는 매트릭스 A의 헤르미테 정상형이며 U는 UA=H와 같은 단모형 매트릭스다.

${\displaystyle A={\begin{pmatrix}3&, 3&, 1&, 4\\0&, 1&, 0&, 0\\0&, 0&, 19&, 16\\0&, 0&, 0&, 3\end{pmatrix}}\qquad H={\begin{pmatrix}3&, 0&, 1&, 1\\0&, 1&, 0&, 0\\0&, 0&, 19&, 1\\0&, 0&, 0&, 3\end{pmatrix}}\qquad U=\left({\begin{배열}{rrrr}1&, -3&, 0&, -1\\0&, 1&, 0&, 0\\0&, 0&, 1&.-5\\0&, 0&, 0&, 1\end{배열}}\right)}$

${\displaystyle A=\left({\begin{array}{rrrr}2&3&6&2\\5&6&1&6\\8&3&1&1\end{array}}\right)\qquad H=\left({\begin{array}{rrrr}1&0&50&-11\\0&3&28&-2\\0&0&61&-13\end{array}}\right)\qquad U=\left({\begin{array}{rrr}9&-5&1\\5&-2&0\\11&-6&1\end{array}}\right)}$

A의 단일 행에 양수 또는 음수 선행 계수가 있는지 여부에 따라 A의 행이 하나만 있는 경우 H = A 또는 H = -A 중 하나가 된다.

알고리즘

1851년으로 거슬러 올라가는 헤르미트의 정상 형태를 계산하는 알고리즘은 많다. 그것은 1979년 때 강하게 다항 시간에 운행되는 에르 미트 정규형 산정을 위한 알고리즘 처음 개발된 때까지[13]그것은 에르 미트 정상적인 형태를 계산할 수를 above 입력 매트릭스의차원의 다항식. 그리고 공간은 이 알고리즘(중간 숫자)에 의해 사용된 a을 경계로 하고 있고 있지 않았습니다실내 변기입력 매트릭스에 있는 숫자의 이진 인코딩 크기의 리노미럴. 특수 초등 행렬이 반복적으로 사용된다는 점에서 한 등급의 알고리즘은 가우스 제거에 기초한다.^[11][14][15] LLL 알고리즘은 Hermite 정규 형태를 효율적으로 계산하는 데도 사용될 수 있다.^[16][17]

적용들

격자 계산

R의ⁿ 일반적인 격자는 $L{\displaystyle }$= {${\displaystyle \sum \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{i}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle {\alpha }_{}}$ i ${\displaystyle \alpha {}_{}{}_{}}$ i α ${\displaystyle i_{}}$ α ${\displaystyle i\mathbb{}{}_{}\}}$ Z$$} {\$displaystyle L$=\left$\{\\\\\왼쪽$) 형식을 가지고 있다$.$$\sum _$${i=1}^{n}\알파 _{i}a_{i}\;\right\vert \\\nalpha$ __i${i}\$inⁿ $\mathb {Z}\right\}}}}.$ 행렬 A의 열이 a일 경우_i 격자는 행렬의 열과 연관될 수 있으며, A는 L의 기초가 된다고 한다. 헤르미테 정상 형태가 독특하기 때문에 두 개의 격자 설명에 대한 많은 질문에 답하는 데 사용할 수 있다. 다음에 대한 L ${\displaystyle A_{}}$ ${\$는 A의 열에 의해 생성된 격자를 나타낸다. 기본은 행렬 A의 열에 있기 때문에 기둥형 헤르미트 정규 형태를 사용해야 한다. 격자 A와 A'에 대한 두 가지 기준을 고려할 때 동등성 문제는 $L{\displaystyle {}_{}}$ ${\displaystyle A_{}}$= L ${\displaystyle {A{}^{}\prime .}_{}}$ ${\displaystyle L_{A}=$의 여부를 결정하는 것이다.$L_{A'}.}$ 이것은$$ 컬럼형 헤르미트 정규 형태인 A와 A'가 0기둥을 추가할 때까지 동일한지 확인하면 된다. 이 전략은 또한${\displaystyle {}_{}}L{\displaystyle {}_{}}$ [ ${\displaystyle {A{}^{}}_{}}$ A${\displaystyle {{}^{}]}_{}}$ ${\displaystyle {}_{}}$ = ${\displaystyle {}_{}}$ ${\displaystyle {A{}^{}}_{}}$${\displaystyle {{\prime }^{}}_{}}$ ${\$ $L_{A}\subseteq$ $L_$${A'}}}$인 경우에만 래티스가 서브셋인지 결정하는 데 유용하다$.$$A\mid A']}=L_{A'}}$), deciding if a vector v is in a lattice (${\displaystyle v\in L_{A}}$ if and only if ${\displaystyle L_{[v\mid A]}=L_{A}}$), and for other calculations.^[18]

선형 시스템에 대한 정수 솔루션

선형 시스템 Ax=b는 Hy=b 시스템이 정수 솔루션 y를 갖는 경우에만 정수 솔루션 x를 가지며, 여기서 y=Ux와⁻¹ H는 칼럼 스타일의 Hermite 정규 형태 A이다. H 행렬이 삼각형이기 때문에 Hy=b에 정수용액이 있는지 확인하는 것이 Ax=b보다 쉽다.^{[11]: 55}

구현

많은 수학 소프트웨어 패키지는 Hermite 정규 형태를 계산할 수 있다.

• 단풍나무와 헤르미트폼
• 헤르미테 데 콤포메이션이 있는 마티카
• HermiteForm이 있는 MATLAB
• NTL(HNF 포함)
• PARI/GP(mathnf 포함)
• SageMath with Hermite_form

참고 항목

• 헤르미테 반지
• 스미스 보통형
• 디오판틴 방정식

참조