Howell formă normală

Forma normală Howell este un analog al matricei de etape pentru matricele peste inelul de resturi modulo . $\mathbb {Z} _{N}$ $N$

Definiție

Să fie o matrice peste . O matrice este sub formă de pas dacă îndeplinește următoarele condiții: $A\in \mathbb {Z} _{N}^{n\times m)$ $\mathbb {Z} _{N}$

Fie numărul de rânduri diferite de zero . Atunci primele rânduri ale matricei sunt diferite de zero, $r$ $A$ $r$
Pentru , fie indexul primului element non-null din șir . Apoi . $1\leq i\leq r$ $j_{i)$ $i$ $j_{1}<j_{2}<\dots <j_{r)$

Orice matrice sub formă de pas poate fi simplificată prin transformări elementare astfel încât să fie îndeplinite următoarele condiții:

Pentru orice , elementul conducător se împarte uniform, $1\leq i\leq r$ $A_{ij_{i)}$ $N$
Pentru orice împlinit . $1\leq k<i\leq r$ $0\leq A_{kj_{i}}<A_{ij_{i}}$

Se spune că o matrice care îndeplinește condițiile de mai sus este în forma de pas redusă .

Fie intervalul liniar al rândurilor matricei . O matrice în formă de trepte reduse este în forma normală a lui Howell dacă este îndeplinită suplimentar următoarea condiție: $S(A)$ $A$

Fie un element al intervalului liniar al șirurilor astfel încât pentru orice . Atunci , unde este o matrice compusă din rânduri de la -a la --a matrice . $v\in S(A)$ $A$ $v_{k}=0$ $1\leq k<j_{i}$ $v\in S(A_{i\dots m})$ $A_{i\dots m)$ $i$ $m$ $A$

Proprietăți

Fie matrice peste . Întinderile de linii ale rândurilor lor se potrivesc dacă și numai dacă formele lor normale Howell se potrivesc. De exemplu, pentru matrice $A,B\in \mathbb {Z} _{N}^{n\times m)$ $\mathbb {Z} _{N}$

A={\begin{bmatrix}4&1&0\\0&0&5\\0&0&0\end{bmatrix}), B={\begin{bmatrix}8&5&5\\0&9&8\\0&0&10\end{bmatrix))

peste , forma lor normală Howell coincide și are forma $\mathbb {Z} _{12}$

H={\begin{bmatrix}4&1&0\\0&3&0\\0&0&1\end{bmatrix}}.

Literatură

Howell J. A. Spans in the module (Z_m) ^ S (engleză) // Linear and Multilinear Algebra - Taylor & Francis , 1986. - Vol. 19, Iss. 1. - P. 67-77. — ISSN 0308-1087 ; 1026-7573 ; 1563-5139 - doi:10.1080/03081088608817705
Storjohann A., Mulders T. Fast Algorithms for Linear Algebra Modulo N (engleză) // Lect. Notă Comput. sci. / G. Goos , J. Hartmanis , J. v. Leeuwen - Berlin , Heidelberg , New York, NY , Londra [etc.] : Springer , 1998. - P. 139-150. — ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-68530-8_12