Postać normalna Hermite'a

W algebrze liniowej postać normalna Hermite'a jest odpowiednikiem zredukowanej formy schodkowej dla macierzy nad liczbami całkowitymi Z . Tak jak zredukowana postać schodkowa może być użyta do rozwiązania problemów dotyczących rozwiązania układu liniowego Ax = b , gdzie x jest w R ⁿ , tak postać normalna Hermite'a może rozwiązać problemy dotyczące rozwiązania układu liniowego Ax = b , gdzie tym razem x jest ograniczony tylko do współrzędnych całkowitych. Inne zastosowania postaci normalnej Hermite'a obejmują programowanie całkowitoliczbowe , kryptografię i algebrę abstrakcyjną .

Definicja

Różni autorzy mogą preferować mówienie o postaci normalnej Hermite'a w stylu wierszowym lub kolumnowym. Są zasadniczo takie same aż do transpozycji.

Forma normalna Hermite'a w stylu wiersza

Macierz m na n A z wpisami liczb całkowitych ma (wierszową) postać normalną Hermite'a H , jeśli istnieje kwadratowa jednomodułowa macierz U , gdzie H = UA i H ma następujące ograniczenia:

H jest trójkątem górnym (to znaczy h _ij = 0 dla i > j ), a dowolne rzędy zer znajdują się pod dowolnym innym rzędem.
Współczynnik wiodący (pierwsza niezerowa pozycja od lewej, zwana także osią ) niezerowego wiersza jest zawsze ściśle na prawo od wiodącego współczynnika wiersza powyżej; co więcej, jest pozytywna.
Elementy poniżej osi obrotu są zerowe, a elementy powyżej osi obrotu są nieujemne i ściśle mniejsze od osi obrotu.

Trzeci warunek nie jest standardem wśród autorów, na przykład niektóre źródła wymuszają, aby nie-pivoty były niedodatnie lub nie nakładają na nie ograniczeń znakowych. Jednak te definicje są równoważne przy użyciu innej macierzy jednomodułowej U . Macierz jednomodułowa to kwadratowa odwracalna macierz liczb całkowitych, której wyznacznikiem jest 1 lub −1.

Forma normalna Hermite'a w stylu kolumny

Macierz A m -by- n z wpisami całkowitymi ma (kolumnową) postać normalną Hermite'a H , jeśli istnieje kwadratowa jednomodułowa macierz U , gdzie H = AU i H ma następujące ograniczenia:

H jest dolnym trójkątem, h _ij = 0 dla i < j , a kolumny zerowe znajdują się po prawej stronie.
Współczynnik wiodący (pierwszy niezerowy wpis od góry, zwany także osią obrotu ) kolumny niezerowej jest zawsze dokładnie poniżej współczynnika wiodącego kolumny poprzedzającej; co więcej, jest pozytywna.
Elementy na prawo od czopów są zerowe, a elementy na lewo od czopów są nieujemne i ściśle mniejsze od czopów.

Należy zauważyć, że definicja w stylu wierszowym ma jednomodułową macierz U mnożącą A po lewej stronie (co oznacza, że U działa na wierszach A ), podczas gdy definicja w stylu kolumnowym ma jednomodułowe działanie macierzy na kolumny A . Te dwie definicje postaci normalnych Hermite'a są po prostu wzajemnymi transpozycjami.

Istnienie i niepowtarzalność postaci normalnej Hermite'a

Każda macierz A m -by- n z wpisami całkowitymi ma unikalną macierz m -by- n H taką, że H = UA dla pewnej kwadratowej jednomodułowej macierzy U.

Przykłady

W poniższych przykładach $H$ jest postacią normalną Hermite'a macierzy $A$ , a $U$ jest macierzą jednomodułową taką, że $UA = H$ .

{\ Displaystyle A = {\ początek {pmatrix} 3 i 3 i 1 i 4 \\ 0 i 1 i 0 i 0 \\ 0 i 0 i 19 i 16 \\ 0 i 0 i 0 i 3 \ koniec {pmatrix}} \ qquad H = {\ początek {pmatrix} 3 i 0 i 1 i 1 \\ 0 i 1 i 0 i 0 \\ 0 i 0 i 19 i 1 \\ 0 i 0 i 3 \ koniec { pmatrix}}\qquad U=\left({\begin{tablica}{rrrr}1&-3&0&-1\\0&1&0&0\\0&0&1&-5\\0&0&0&1\end{tablica}}\right)}

{\ Displaystyle A = {\ rozpocząć {pmatrix} 2 i 3 i 6 i 2 \\ 5 i 6 i 1 i 6 \\ 8 i 3 i 1 i 1 \ koniec {pmatrix}} \ qquad H = \ lewo ({\ rozpocząć {tablica} {rrrr} 1 i 0 i 50 i -11 \\ 0 i 3 i 28 i -2 \\ 0&0&61&-13\end{tablica}}\right)\qquad U=\left({\begin{array}{rrr}9&-5&1\\5&-2&0\\11&-6&1\end{array}}\right) }

Jeśli $A$ ma tylko jeden wiersz, to $H = A$ lub $H = - A$ , w zależności od tego, czy pojedynczy wiersz $A$ ma dodatni, czy ujemny współczynnik wiodący.

Algorytmy

Istnieje wiele algorytmów obliczania postaci normalnej Hermite'a, których początki sięgają 1851 r. Dopiero w 1979 r. Po raz pierwszy opracowano algorytm obliczania postaci normalnej Hermite'a, który działał w silnie wielomianowym czasie ; to znaczy liczba kroków do obliczenia postaci normalnej Hermite'a jest ograniczona powyżej wielomianem w wymiarach macierzy wejściowej, a przestrzeń wykorzystywana przez algorytm (liczby pośrednie) jest ograniczona wielomianem w rozmiarze kodowania binarnego liczby w macierzy wejściowej. Jedna klasa algorytmów opiera się na eliminacji Gaussa , ponieważ wielokrotnie używane są specjalne macierze elementarne. The LLL może być również użyty do wydajnego obliczenia postaci normalnej Hermite'a.

Aplikacje

Obliczenia kratowe

Typowa krata w R ⁿ ma postać ${\ textstyle L = \ lewo \ {\ lewo. \ suma _ {i = 1} ^ {n} \ alfa _ {i} \ mathbf {a} _ {i} \; \ prawo \ vert \;\alpha _{i}\in {\textbf {Z}}\right\}}$ gdzie a i _są w R ⁿ . Jeśli kolumnami macierzy A są a _i , krata może być powiązana z kolumnami macierzy, i mówi się, że A jest bazą L . Ponieważ postać normalna Hermite'a jest wyjątkowa, można jej użyć do odpowiedzi na wiele pytań dotyczących opisów dwóch sieci. W dalszej części $A. Ponieważ$ znajduje się w kolumnach macierzy A , należy użyć postaci normalnej Hermite'a w stylu kolumnowym Biorąc pod uwagę dwie podstawy sieci, A i A' , problem równoważności polega na zdecydowaniu, ${\ Displaystyle L_ {A} = L_ {A'}.} Można to zrobić, sprawdzając, czy postać normalna$ A i A' Hermite'a w stylu kolumnowym jest taka sama aż do dodania zerowych kolumn. Ta strategia jest również przydatna do decydowania, czy krata jest podzbiorem ( ${\ Displaystyle L_ {A} \ subseteq L_ {A'}}$ wtedy i tylko wtedy, gdy ${\ Displaystyle L_ {[A \ mid A']} = L_ {A'}} )$ , decydując, czy wektor v jest w sieci ( ${\ displaystyle v \ in L_ {A}}$ wtedy i tylko ${\ Displaystyle L_ {[v \ mid A]} = L_ {A}})$ = dla innych obliczeń.

Rozwiązania całkowitoliczbowe układów liniowych

Układ liniowy $Ax = b$ ma rozwiązanie całkowitoliczbowe $x$ wtedy i tylko wtedy, gdy układ $Hy = b$ ma rozwiązanie całkowitoliczbowe $y$ , gdzie $y = U -1 x$ , a $H$ jest kolumnową postacią normalną Hermite'a $A$ . Sprawdzenie, czy $Hy = b$ ma rozwiązanie całkowitoliczbowe, jest łatwiejsze niż $Ax = b$ , ponieważ macierz $H$ jest trójkątna.

Implementacje

Wiele pakietów oprogramowania matematycznego może obliczyć postać normalną Hermite'a:

Przez dowolną domenę Dedekind

Postać normalną Hermite'a można zdefiniować, gdy zastąpimy Z dowolną domeną Dedekinda . (na przykład dowolna domena główna-idealna ). Na przykład w $danym$ sterowania może być rozważenie postaci normalnej Hermite'a dla wielomianów polem F .

Zobacz też