Нормальная форма Хауэлла (Ukjbgl,ugx skjbg }grzllg)

Нормальная форма Хауэлла — аналог ступенчатого вида матрицы для матриц над кольцом $\mathbb {Z} _{N}$ остатков по модулю $N$.

Определение

Пусть $A\in \mathbb {Z} _{N}^{n\times m}$ — матрица над $\mathbb {Z} _{N}$. Матрица находится в ступенчатом виде если она удовлетворяет следующим условиям:

• Пусть $r$ — число ненулевых строк $A$. Тогда первые $r$ строк матрицы ненулевые,
• Для $1\leq i\leq r$, пусть $j_{i}$ — индекс первого ненулевого элемента в строке $i$. Тогда $j_{1}<j_{2}<\dots <j_{r}$.

Любую находящуюся в ступенчатом виде матрицу можно упростить элементарными преобразованиями таким образом, чтобы были выполнены следующие условия:

• Для любого $1\leq i\leq r$, ведущий элемент $A_{ij_{i}}$ делит $N$ нацело,
• Для любых $1\leq k<i\leq r$ выполнено $0\leq A_{kj_{i}}<A_{ij_{i}}$.

Про матрицу, удовлетворяющую условиям выше говорят, что она находится в приведённом ступенчатом виде.

Пусть $S(A)$ — линейная оболочка строк матрицы $A$. Матрица в приведённой ступенчатом виде находится в нормальной форме Хауэлла, если дополнительно выполнено следующее условие:

• Пусть $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$.

Свойства

Пусть $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}}$

над $\mathbb {Z} _{12}$, их нормальная форма Хауэлла совпадает и имеет вид

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

Литература

• Howell J. A. Spans in the module (Z_m)^S (англ.) // 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 (англ.) // Lecture notes in computer science / G. Goos, J. Hartmanis, J. v. Leeuwen — Berlin, Heidelberg, New York City, London: Springer, 1998. — P. 139—150. — 12 p. — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-68530-8_12