Нормальная форма Хауэлла
Нормальная форма Хауэлла — аналог ступенчатого вида матрицы для матриц над кольцом Z N {displaystyle mathbb {Z} _{N}} остатков по модулю N {displaystyle N} .
Определение
Пусть A ∈ Z N n × m {displaystyle Ain mathbb {Z} _{N}^{n imes m}} — матрица над Z N {displaystyle mathbb {Z} _{N}} . Матрица находится в ступенчатом виде если она удовлетворяет следующим условиям:
- Пусть r {displaystyle r} — число ненулевых строк A {displaystyle A} . Тогда первые r {displaystyle r} строк матрицы ненулевые,
- Для 1 ≤ i ≤ r {displaystyle 1leq ileq r} , пусть j i {displaystyle j_{i}} — индекс первого ненулевого элемента в строке i {displaystyle i} . Тогда j 1 < j 2 < ⋯ < j r {displaystyle j_{1}<j_{2}<dots <j_{r}} .
Любую находящуюся в ступенчатом виде матрицу можно упростить элементарными преобразованиями таким образом, чтобы были выполнены следующие условия:
- Для любого 1 ≤ i ≤ r {displaystyle 1leq ileq r} , ведущий элемент A i j i {displaystyle A_{ij_{i}}} делит N {displaystyle N} нацело,
- Для любых 1 ≤ k < i ≤ r {displaystyle 1leq k<ileq r} выполнено 0 ≤ A k j i < A i j i {displaystyle 0leq A_{kj_{i}}<A_{ij_{i}}} .
Про матрицу, удовлетворяющую условиям выше говорят, что она находится в приведённом ступенчатом виде.
Пусть S ( A ) {displaystyle S(A)} — линейная оболочка строк матрицы A {displaystyle A} . Матрица в приведённой ступенчатом виде находится в нормальной форме Хауэлла, если дополнительно выполнено следующее условие:
- Пусть v ∈ S ( A ) {displaystyle vin S(A)} — элемент линейной оболочки строк A {displaystyle A} , такой что v k = 0 {displaystyle v_{k}=0} для любого 1 ≤ k < j i {displaystyle 1leq k<j_{i}} . Тогда v ∈ S ( A i … m ) {displaystyle vin S(A_{idots m})} , где A i … m {displaystyle A_{idots m}} — матрица составленная из строк с i {displaystyle i} -й по m {displaystyle m} -ю матрицы A {displaystyle A} .
Свойства
Пусть A , B ∈ Z N n × m {displaystyle A,Bin mathbb {Z} _{N}^{n imes m}} — матрицы над Z N {displaystyle mathbb {Z} _{N}} . Линейные оболочки их строк совпадают если и только если совпадают их нормальные формы Хауэлла. Например, для матриц
A = [ 4 1 0 0 0 5 0 0 0 ] , B = [ 8 5 5 0 9 8 0 0 10 ] {displaystyle A={egin{bmatrix}4&1&0 &0&5 &0&0end{bmatrix}},B={egin{bmatrix}8&5&5 &9&8 &0&10end{bmatrix}}}над Z 12 {displaystyle mathbb {Z} _{12}} , их нормальная форма Хауэлла совпадает и имеет вид
H = [ 4 1 0 0 3 0 0 0 1 ] . {displaystyle H={egin{bmatrix}4&1&0 &3&0 &0&1end{bmatrix}}.}