close

Вход

Забыли?

вход по аккаунту

?

О подобии матриц второго порядка над кольцом целых чисел.

код для вставкиСкачать
2006
ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ
МАТЕМАТИКА
Є 4 (527)
УДК 512.643
В.Н. ШЕВЧЕНКО, С.В. СИДОРОВ
О ПОДОБИИ МАТРИЦ ВТОРОГО ПОРЯДКА
НАД КОЛЬЦОМ ЦЕЛЫХ ЧИСЕЛ
Из линейной алгебры известно (напр., [1], с. 101), что с линейным преобразованием линейного пространства V над полем F связан класс ['] подобных между собой матриц. А именно,
этот класс состоит из всех матриц преобразования ' в различных базисах пространства V . Если
A; B 2 ['], то существует невырожденная матрица S с элементами из F такая, что AS = SB .
Подобие матриц A и B над полем рациональных чисел будем обозначать A B . Для проверки
подобия над полем Q имеется алгоритм (напр., [1], с. 154{157) приведения характеристической
матрицы A ; E к нормальной диагональной форме Смита и построения по ней единственной канонической матрицы F (в [1], с. 181, она называется естественной нормальной формой матрицы
A).
Перенесем понятие подобия на кольцо Z целых чисел. Сильно возросшие трудности заставили ограничиться двумерным случаем, в котором будет получен алгоритм проверки подобия
двух матриц A и B над Z и, если их характеристический многочлен приводим над Q, описаны
классы подобных матриц.
nn подобна матрице A 2 Znn над
Определение 1. Будем говорить, что матрица B 2 Z
n
n
кольцом Z, если существует S 2 Z такая, что AS = SB и det S 2 f;1; 1g, и обозначать это
AB . При этом матрицу S будем называть Z-трансформирующей A в B матрицей.
Очевидно, введенное отношение есть отношение эквивалентности.
Следовательно, множество Znn разбивается на классы эквивалентности Kj , j 2J . Таким
образом, можно записать
nn = [ K :
Z
j
j 2J
Целочисленную матрицу A можно рассматривать как матрицу над кольцом вычетов Z=m,
если положить A = (resm aij ), где m | натуральное число, а resm x | остаток от деления x на
m. Обозначим через (Z=m) множество делителей единицы в Z=m.
nn подобна матрице A 2 Znn над
Определение 2. Будем говорить, что матрица B 2 Z
n
n
кольцом Z=m, если существует S 2 Z такая, что AS SB (mod m) и det S 2 (Z=m) , и
обозначать это Am B .
Задача заключается в том, чтобы определить, являются ли две данные целочисленные матрицы A и B подобными, и если являются, то найти трансформирующую матрицу.
Над полем Q критерием подобия матриц является равенство наибольших общих делителей (НОД) миноров k-го порядка их характеристических матриц. Обобщением понятия НОД
на кольцо Z[] является идеал, порожденный минорами k-го порядка характеристической матрицы. Так как Q[] | кольцо главных идеалов, а Z[] таковым не является, то это первое
усложнение при переходе к Z.
Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (код проекта Є 05-01-00552-a).
57
Обозначим через Ik (A ; E ) идеал в кольце Z[], порожденный минорами k-го порядка
характеристической матрицы A ; E , а через k (A) | НОД (рассматриваемый над кольцом
целых чисел Z) миноров k-го порядка матрицы A.
Теорема 1. Если
AB , то
1) AB ,
2) Am B над кольцом Z=m для всех m 2,
3) Ik (A ; E ) = Ik (B ; E ) для всех k = 1; : : : ; n,
4) k (A) = k (B ), k = 1; : : : ; n.
nn такая, что det T 2 f;1; 1g
Доказательство. Так как AB , то существует матрица T 2 Z
и AT = TB .
1) Очевидно, T удовлетворяет условиям подобия над полем Q.
2) Очевидно, AT TB (mod m) и det T 2 (Z=m) , т. е. Am B .
3) (A ; E )T = T (B ; E ), откуда A ; E = T (B ; E )T ;1 . Из формулы Бине{Коши (напр.,
[2], с. 19) следует, что любой минор k-го порядка матрицы A ; E принадлежит Ik (B ; E ).
Следовательно, Ik (A ; E ) Ik (B ; E ). Аналогично доказывается обратное включение.
4) Доказательство проводится аналогично предыдущему пункту теоремы.
Заметим, что условие 1) является следствием условия 3).
Теорема 2. Пусть
Тогда
что
A mk B .
Доказательство.
A; B 2
nn ,
Z
Am B
и
Ak B ,
где
m
и
k
| взаимно простые числа.
Существуют матрицы T = (tij ) 2 (Z=m)nn , S = (sij ) 2 (Z=k)nn такие,
AT TB (mod m); AS SB (mod k)
и det T 2 (Z=m) , det S 2 (Z=k) . Равенства (1) можно переписать следующим образом:
n
X
j =1
aij tjl n
X
j =1
tij ajl (mod m);
Согласно китайской теореме об остатках
n
X
j =1
aij sjl n
X
j =1
sij ajl (mod k); i; l = 1; : : : ; n:
=m Z=k = Z=mk:
Z
(1)
(2)
(3)
Построим матрицу Q = (qij ), элементы которой удовлетворяют условиям
resm qij = tij ; resk qij = sij :
(4)
Эта матрица строится однозначно в силу изоморфизма (3). Из (1), (2) и (4) вытекает, что
AQ AT (mod m); AQ AS (mod k); QB TB (mod m); QB SB (mod k):
Следовательно, AQ QB (mod m) и AQ QB (mod k), откуда AQ QB (mod mk) в силу
взаимной простоты m и k.
Осталось доказать, что det Q 2 (Z=mk ) . Действительно, resm (det Q) = resm (det T ) 2 (Z=m) ,
resk (det Q) = resk (det S ) 2 (Z=k) . Отсюда видно, что det Q 2 (Z=mk ) .
Следствие 1. Если Ami B , где i = 1; : : : ; s, НОД(mi ; mj ) = 1 для всех i 6= j , то Aq B , где
q = m1 : : : ms .
k
Следствие 2. Если Aq B , где q = p для любых простых p и натуральных k , то Am B ,
для любого натурального m 2.
nn и существует матрица S 2 Znn , у которой det S =
Следствие 3. Пусть A; B 2 Z
k
k
s
1
p1 ps и AS = SB . Если Aq B над Z=q, где q = pi k , i = 1; : : : ; s, для любого натурального k, то Am B над Z=m для всех m 2.
58
Доказательство. Логически возможны два варианта.
1) НОД(m; det S ) = 1. Тогда AS SB (mod m). Покажем, что det S 2 (Z=m) . Действительно,
det S = p1 k1 ps ks r (mod m), причем НОД(m; r) = 1, т. к. в противном случае имели бы
противоречие с взаимной простотой m и det S .
2) НОД(m; det S ) = d 6= 1. Таким образом, m = db и НОД(b; det S ) = 1. Тогда A d B по
следствию 1 и A b B согласно предыдущему случаю. Следовательно, в силу взаимной простоты
d и b и теоремы 2 получаем Am B .
nn и существуют матрицы Si 2 Znn такие, что ASi = Si B ,
Следствие 4. Пусть A; B 2 Z
det Si 6= 0, i = 1; : : : ; l. Если НОД(det S1 ; : : : ; det Sl ) = 1, то Am B для всех m 2.
Пусть матрицы A и B имеют один и тот же характеристический многочлен d(), который
неприводим
над Q. Введем несколько обозначений: MA;B = fS 2 Qnn j AS = SB g и A;B =
T nn
MA;B Z . Очевидно, MA;B | подпространство в Qnn, а A;B | подмодуль в Znn. В этом
случае верно
2
n;1 S ) = L(S; SB; SB 2 ; : : : ; SB n;1 ), где
Утверждение ([2], с. 193). MA;B = L(S; AS; A S; : : : ; A
S 2 MA;B , det S 6=0, а буквой L обозначили множество всех линейных комбинаций матриц,
стоящих в скобках.
Не уменьшая общности, можно считать, что S | целочисленная матрица. Пусть T1 ; : : : ; Tn
| базис модуля A;B . Тогда очевидна
Лемма 1. Для того чтобы A B , необходимо и достаточно, чтобы уравнение det(x1 T1 +
+xnTn) = 1 имело решение в целых x1 ; : : : ; xn .
Если tij есть j -й столбец матрицы Ti , то
f (x1; : : : ; xn ) = det
n
X
i=1
xi Ti =
n
X
i1 =1
n
X
in =1
xi1 xin det(ti11 ; : : : ; tinn ):
Нужно выяснить, имеет ли уравнение f (x1 ; : : : ; xn ) = 1 решение в целых числах. Как решать
это уравнение в общем случае, неизвестно. Но если n = 2, то det(x1 T1 + x2 T2 ) = x21 det T1 +
x1 x2 (det(t11 ; t22 )+det(t21; t12 ))+ x22 det T2 | бинарная квадратичная форма, т. е. в этом случае задача
о подобии сводится к классическому вопросу теории чисел | представлению целого числа (здесь
1) квадратичной формой (напр., [3], с. 286; [4], с. 310). Поэтому для более детального изучения
перейдем к матрицам второго порядка. Из третьего необходимого условия подобия вытекает
(при k = n), что если AB , то характеристические многочлены матриц совпадают. Будем это
предполагать, не оговаривая специально.
1. Случай приводимого характеристического многочлена
Пусть 2Z | корень многочлена d() и x = (x1 ; x2 )T | собственный вектор, соответствующий . Не уменьшая общности, можно считать, что x 2 Z2 и НОД(x1 ; x2 ) = 1. Тогда существуют
целые числа y1 ; y2 такие, что det ( xx12 yy12 ) = det(x; y) = 1. Векторы x и y образуют базис в Q2.
Разложим Ay по этому базису: Ay = c1 x + c2y. В пространстве Q2 определим линейное преобразование ' с матрицей A, т. е. [']e = A в стандартном базисе e. Тогда в базисе x, y
C = ['](x;y) = 0 cc1 :
(5)
2
Таким образом, C = T ;1 AT , где T = (x; y). Следовательно, A C и tr A = tr C , det A =
det C (где tr A | след матрицы, т. е. сумма элементов главной диагонали, det A | определитель
матрицы). Возможны два варианта:
1 . d() имеет один двукратный корень,
2 . d() имеет два различных корня.
59
1 . Имеем d() = ( ; )2 = 2 ; 2 + 2 , т. е. tr A = 2 и det A = 2 . Над полем рациональных
чисел Q имеем два класса Y1 () и Y2 () подобных матриц с каноническими матрицами R0 () =
( 0 0 ) и R1 () = ( 0 1 ) соответственно, т. е. Y1 () = fA 2 Z22 j A R0 ()g, Y2 () = fA 2 Z22 j
A R1 ()g. Посмотрим, что изменится над Z. В силу вышесказанного c2 = . Таким образом,
выражение (5) принимает вид C = ['](x;y) = ( 0 c1 ). Теперь заметим, что можно считать c1 0,
т. к. в противном случае, взяв T = ( ;01 01 ), получим T ;1 CT = ( 0 ;c1 ). Из теоремы 1 следует,
что матрицы Rk1 () = ( 0 k1 ) и Rk2 () = ( 0 k2 ), где k1 ; k2 0, не подобны, если k1 6= k2 , т. к.
I1 (R1 ; E ) 6= I1(R2 ; E ).
Матрицы Rk1 () и Rk2 () представляют разные классы эквивалентности и однозначно характеризуют класс, которому принадлежат. Поэтому матрица вида Rk () = ( 0 k ), где k 0,
является канонической. Таким образом, класс Y2 () разбивается на счетное число подклассов
Kj () = fA 2 Z22 j A Rj ()g, каждый из которых характеризуется канонической матрицей
Rj () = ( 0 j ), где j 1. Тем самым доказана
2
Теорема 3. Если d() = ( ; ) , где 2 Z, то
1) A B тогда и только тогда, когда I1 (A ; E ) = I1 (B ; E ),
2) Y1 () = K0 (), Y2 () = j[1 Kj (), где Kj () = fA 2 Z22 j A Rj ()g, а Rj () = ( 0 j ),
j 0, | каноническая матрица.
2 . Если корни простые, то d() = ( ; )( ; ), т. е. tr A = + и det A = . Не уменьшая общности, можно считать, что > . Над полем Q имеем один класс Y; 3 (; ) = fA 2
22 j A R (; )g подобных матриц с канонической матрицей R (; ) = 0 . Найдется
Z
0
0
0
собственный вектор x = (x1 ; x2 )T 2 Z2 с НОД(x1 ; x2 ) = 1, соответствующий , т. е. Ax = x.
Найдем y = (y1 ; y2 )T 2 Z2c такой, что det(x; y) = 1. В данном случае c2 = . Тогда (5) примет вид C = ['](x;y) = ( 0 1 ). Во-первых, можно считать, что 0 c1 < ; . Действительно,
c1 = q( ; ) + r, где 0 r < ; . Тогда T ;1 CT = ( 0 r ) =Rr (; ), если
T = ( 10 ;q1 ). Во-вторых,
можно считать, что 0 c1 [ ;2 ], т. к. S ;1 Rr (; )S = 0 (;);r , где S = 01 ;;11 . Теперь
убедимся в том, что матрицы Rk1 (; ) = 0 k1 и Rk2 (; ) = 0 k2 не подобны, если k1 6= k2 и
;t t 12
0 k1 ; k2 [ ;2 ]. Предположим, что найдется
унимодулярная
матрица
T
=
такая, что
t11
21 t22
t
t
11 k2 t11 +t12
11 +k1 t21 t12 +k1 t22
Rk1 (; )T = TRk2 (; ). Тогда Rk1 (; )T = t21
= t21 k2 t21 +t22 = TRk2 (; ).
t22
Отсюда видим, что t21 = 0 и ( ; )t12 = k1 t22 ; k2 t11 , значит, t11 t22 = 1 и ( ; )t12 = k1 k2 .
Но тогда t12 не может быть целым в силу ограничений на k1 ; k2 . Таким образом, над кольцом Z
класс Y3 (; ) разделилсяна конечное
число подклассов Kj (; ) = fA 2 Z22 j A Rj (; )g , и
j
матрица вида Rj (; ) = 0 , где 0 j [ ;2 ], является канонической. Из вышеизложенного
следует
[ ; ]
2
d() = ( ; )( ; ), ; 2 Z, > , то Y3 (; ) = j[=0
Kj (; ), где
Kj (; ) = fA 2 Z22 j A Rj (; )g, а Rj (; ) = 0 j , 0 j [ ;2 ], | каноническая
Теорема 4. Если
матрица.
Теорема 4 позволяет строить примеры, показывающие, что условия, сформулированные в
теореме 1, не являются достаточными для подобия двух матриц.
11
12
Пример 1. Рассмотрим A = ( 0 6 ) и B = ( 0 6 ). Выполнение первого, третьего и четвертого
условий очевидно, причем AT = TB , где T = ( 10 02 ). Для проверки второго условия в силу
следствия 3 достаточно показать, что A m B , где m = 2k , k | натуральное число. Для этого
в качестве трансформирующей матрицы можно взять S = ( 10 17 ). Но по теореме 4 A и B |
канонические матрицы из разных классов эквивалентности, т. е. они не подобны.
Пусть A = ( aa1121 aa1222 ), B = bb1121 bb1222 . Следовательно, t = a11 + a22 = b11 + b22 , s = det A = det B ,
а характеристический многочлен имеет вид d() = 2 ; t + s. Очевидно, если 2 Z, то A и B
60
подобны над Z тогда и только тогда, когда A ; E и B ; E подобны над Z. Если в качестве взять [ 2t ], то возможны два случая.
1) t | четное число. Тогда след матриц A ; E и B ; E будет равен 0, а характеристический
многочлен запишется в виде
d() = 2 ; d;
(6)
где d = 2 ; det A. В этом случае
A ; E = aa ;a1a ; B ; E = bb ;b1b :
(7)
2
2
2) t | нечетное число. Тогда след матриц A ; E и B ; E будет равен 1, а характеристи-
ческий многочлен
d() = 2 ; ; d;
где d = 2 + ; det A. В этом случае
1 b1 :
A ; E = a a+2 1 ;a1a ; B ; E = b +
b2 ;b
Итак, исходную задачу свели к задаче о подобии матриц вида (7) или (9).
(8)
(9)
2. Случай неприводимого характеристического многочлена
Итак, предполагаем, что характеристический многочлен (имеющий вид (6) или (8)) неприводим над полем Q (отсюда, в частности, следует, что A и B невырождены). ;
b Рассмотрим сначала случай, когда d() = 2 ; ; d. В этом случае A = a+1
c ;a подобна
над полем рациональных чисел матрице Фробениуса F = ( d1 10 ), где d = a2 + a + bc, b 6= 0 и
c 6= 0. Это следует из того, что НОД миноров любого порядка их характеристических матриц
одинаковы (действительно, НОД миноров первого порядка равен 1, а второго | d()). Выясним,
1 ; b 0
останется ли этот факт верным над Z. Базисом модуля A;F являются
матрицы ( a+1
c 0 ) и ;a 1 .
yb x
2
Таким образом, A;F состоит из матриц вида S = x(acx+1)+
;ay y , x; y 2 Z, а det S = ;cx +
(2a + 1)xy + by2 . Получили бинарную квадратичную форму. Заметим, что ее дискриминант
совпадает с дискриминантом исходного характеристического многочлена. Выясним, разрешимо
ли в целых числах уравнение
; cx2 + (2a + 1)xy + by2 = 1:
(10)
Домножив (10) на 4b, получим равносильное (10) уравнение
(2by + (2a + 1)x)2 ; Dy2 = 4b;
(11)
где D = 1 + 4d. Для того чтобы уравнение (11) имело решение в целых x и y (а, соответственно,
и для подобия матриц A и F ), необходимо, чтобы для любого простого p, являющегося делителем D, хотя бы одно из чисел 4b было полным квадратом в поле вычетов Z=p. Тем самым
получили пятое необходимое условие подобия при p 1 (mod 4), т. к. в противном случае (если
p ;1 (mod 4)) либо 4b, либо ;4b является полным квадратом в Z=p. Заметим, что в силу
равноправия b и c аналогичное необходимое условие формулируется ;и для c.
Теперь перейдем к случаю, когда d() = 2 ; d. При этом A = ac ;ba подобна над полем
2
01
Q матрице Фробениуса F = ( d 0 ), где d = a + bc, b 6= 0 и c 6= 0. Здесь базисом модуля A;F
; b 0
ax+by x , x; y 2 Z, а
являются матрицы ( ac 10 ) и ;a 1 , т. е. любая матрица из A;F имеет вид S = cx
;ay y
det S = ;cx2 +2axy + by2 . Аналогично предыдущему случаю имеем уравнение ;cx2 +2axy + by2 =
1, эквивалентное
(by + ax)2 ; dy2 = b:
(12)
61
Чтобы (12) имело решение в целых числах, получаем аналогичное предыдущему случаю необходимое условие (хотя бы одно из чисел b и хотя бы одно из чисел c должны быть полными
квадратами в поле вычетов Z=p для любого простого p, являющегося делителем d).
Пятое необходимое условие не следует из первых четырех, что показывает
A = ( 05 20 ), F = ( 100 10 ), d = 10; AF , т. к. AS = SF , где S = ( 20 01 ). Для проверки
второго необходимого условия в силу следствия 3 достаточно убедиться, что Am F для m = 2k .
Здесь в качестве трансформирующей можно взять матрицу T = ( 05 10 ). Но пятое необходимое
условие нарушается, т. к. ни одно из чисел 2 не является квадратом в поле вычетов Z=5.
Следовательно, A и F не подобны над Z.
Пример 2.
Это еще один пример, показывающий, что необходимые условия подобия, сформулированные
в теореме 1, не являются достаточными. Но и все пять необходимых условий в совокупности не
являются достаточными. Это мы продемонстрируем на следующем примере (который получен
на основе примера из ([4], с. 314).
Рассмотрим A = ( 410 20 ), F = ( 820 10 ), d = 82. Нетрудно проверить выполнение
необходимых условий из теоремы 1. Справедливость пятого условия следует из того, что оба
числа 2 являются квадратами в поле вычетов Z=41, а именно, 112 ;2 (mod 41) и 172 2 (mod 41). Но, несмотря на это, квадратичная форма 2y2 ; 41x2 не представляет ни одно из
чисел 1, т. е. A и F не подобны над Z.
Пример 3.
Теорема 5. Если
d() неприводим над Q, то множество матриц с характеристическим
d() распадается на конечное число классов эквивалентности.
;a b 2
Доказательство. 1) Пусть d > 0. Рассмотрим случай, когда d() = ; d. Тогда A = c ;a ,
;
a 0, a2 + bc = d > 0. Докажем, что существует такое r 0, что A cr1 ;b1r , где
b1 r + 1; c1 r + 1:
(13)
Не уменьшая общности,
можно считать, что b > 0 или c > 0. Действительно, если b < 0, то
;
A B , где B = ;ac ;;ab , т. к. AE1 = E1B , а E1 = ( 10 ;01 ) (аналогично, если c < 0).
Заметим, что если j b j a + 1 и j c j a + 1, то bc > 0, т. к. в противном случае имели
бы a2 > ;bc (a + 1)2 , что неверно. С учетом предыдущего замечания в этом случае можно
считать, что b > 0 и c > 0.
многочленом
Возможны три варианта.
1. Если 0 < b a;, то, разделив
a; на b с остатком, получим a = q1 b + r1 , где 0 r1 < b. Тогда
AT = TB1 , где T = ;1q1 01 , а B1 = rc11 ;br1 .
2. Если 0 < c a, то, разделив; a на c с остатком, получим a = q2 c + r2 , где 0 r2 < c. Тогда
AS = SB2 , где S = ( 10 q12 ), а B2 = rc2 ;br22 .
3. Если b a + 1 и c a + 1, то условия (13) выполнены, что и требовалось.
После выполнения действий в первом или во втором вариантах для новой матрицы (B1 или
B2 ) снова будет справедлив один из трех вариантов. Но с каждым шагом элемент a на главной
диагонали будет уменьшаться и в силу его неотрицательности в конце
концов придем к третьему
p
варианту. Тогда d = a2 + bc a2 + (a + 1)2 , откуда следует a [ 2d;2 1;1 ].
Аналогично pрассматривается случай, когда d() = 2 ; ; d. При этом ограничение на a
;3
имеет вид a [ 8d+1
4 ].
2) Пусть d < 0. Здесь можно применить те же действия,
которые проводились в предыдущем
;
случае, и добиться того, чтобы для матрицы A = ac ;ba , a 0, a2 + bc = d < 0, имели место
неравенства b a + 1, c a + 1. В этом случае ;d =j d j= ;bc ; a2 (a + 1)2 ; a2 = 2a + 1,
1
2
2
2 2
откуда a [ jdj;
2 ]. Если же d() = ; ; d, то j d j= ;bc ; a ; a (a + 1) ; a ; a = a + 1,
откуда a j d j ;1.
62
Пусть S1 и S2 | базис A;B , тогда произвольную матрицу из A;B можно представить в
виде xS1 + yS2 для некоторых x и y из Z . Наша задача состоит в том, чтобы определить,
существует ли в A;B матрица с определителем 1 или ;1. Пусть S 2 A;B , тогда det S = f (x; y) =
det(xS1 + yS2 ) = x2 det S1 + xy(det(s11 ; s22 ) + det(s21 ; s12 )) + y2 det S2 , где s11 , s12 | столбцы матрицы
S1 , а s21, s22 | столбцы матрицы S2.
a11 a12
b11 b12 и их характеристический многочлен
Теорема 6. Пусть A = ( a21 a22 ), B =
b21 b22
1 ; a12 0 и
d() неприводим
над Q. Тогда базис модуля A;B образуют матрицы T1 =
1 b11 ;a11 b12
a12 a12
1
2
1
T2 = b21 + b11;a11 b22;a11 + b12 , где 1 =НОД(a12 ; b12 ; b11 ; a11 ), 2 =НОД(a12; b21 ; b22 ; a11),
2
1
2
1
=НОД( a121 ; a122 ), а удовлетворяет сравнению b121 a11;2b22 (mod ).
Доказательство. Так как d() неприводим, то a12 6= 0. Прежние обозначения при n = 2
имеют вид MA;B = fS; 2 Q22 j AS = SB
g и aA;B= MA;B \ Z22 . В качестве базиса MA;B можно
; 0
a
0
12
взять матрицы S1 = b11 ;a11 b12 , S2 = b21 b22 ;12a11 .
Обозначим 1 =НОД(a12 ; b12 ; b11 ; a11 ), 2 =НОД(a12 ; b21 ; b22 ; a11 ). Следовательно, S1 и S2
можно сократить на 1 и 2 соответственно. Получим матрицы S10 , S20 . Их можно представить
в виде четырехмерных
векторов s1 = ( a121 0 b11;1a11 b121 )T , s2 = ( 0 a122 b212 b22;2a11 )T , образующих
a12
T
b11 ;a11
b12
матрицу G = 01 a012 b211 b22;1a11 . Очевидно, подпространство L в Q4 , базис которого обра2
2
2
зуют s1 ; s2 , изоморфно MA;B . Нам нужно найти базис модуля L \ Z4 . НОД элементов матрицы
G равен 1, а НОД миноров второго порядка равен
= НОД a12 a12 ; a12 b21 ; a12 (b22 ; a11 ) ; a12 b12 ; a12 (b11 ; a11 ) ; a12 a21 =
1 2 1 2
1 2
1 2
1 2
1 2
a
a
b
b
;
a
a
b
b
;
a
a
a
a
12
12
21
22
11
12
12
11
11
21
12
12
= НОД НОД ; ; ; НОД ; ; = НОД ; :
1
2 2
2
2
1
1
1
1 2
x
Рассмотрим систему сравнений G ( y ) 0 (mod ), которая эквивалентна одному сравнению
b12 x + b22 ; a11 y 0 (mod ):
1
2
Множество решений данного сравнения является аддитивной циклической группой. Пусть
(; ) | ее порождающий элемент, тогда s1 +s2 0 (mod ), причем НОД(; ) =НОД(; )=1,
т. к. в противном случае хотя бы один из векторов s1 ; s2 можно было бы сократить на некоторый множитель. Следовательно, в качестве порождающего можно взять вектор (; 1), где удовлетворяет сравнению b121 a11;2b22 (mod ). Таким образом, базис модуля L \ Z4 образуют
векторы s1 и s3 = 1 (s1 + s2 ) = 1 ( a121 a122 b212 + b11;1a11 b22;2a11 + b121 )T . Значит,
базис модуля
A;B
a12
a12 ;
0
0
0
a
0
образуют матрицы T1 = S1 = 11 b11 ;12a11 b12 и T2 = 1 (S1 + S2 ) = 1 b21 + b111 ;a11 b22;a112+ b12 .
2
1
2
1
Пусть верны условия предыдущей теоремы. Тогда квадратичная форма f (x; y)
имеет вид f (x; y) = x2 a1212b12 +xy(2 a1212b12 + a12 (b1222;b11 ) )+y2 ( a1212 b122 2 + a12(1b222 ;2b11 ) ; a1222 b212 ) и Dd = (1 ; 2 )2 ,
где d | дискриминант d(), D | дискриминант f (x; y), (1 ; 2 ) | НОД 1 и 2 .
Следствие 5.
3. Алгоритм определения подобия
Даны две матрицы A; B 2 Z22
1. Находим tr A и tr B . Если tr A 6= tr B , то A и B не подобны. Если tr A = tr B , то переходим
к п. 2.
2. Находим det A и det B . Если det A 6= det B , то A и B не подобны. Если det A = det B , то
переходим к п. 3.
63
3. Пусть d() = 2 ;a+b | характеристический многочлен матриц A и B , где a = tr A = tr B ,
b = det A = det B . Если d() приводим над Z, т. е. имеет вид d() = ( ; )( ; ), ; 2 Z, то
переходим к п. 4, в противном случае к п. 5.
4. Находим векторы xA ; xB 2 Z2 | собственные векторы матриц A и B , соответствующие
, такие, что НОД(xA1 ; xA2 ) = 1, НОД(xB1 ; xB2 ) = 1. Находим такие векторы yA; yB 2 Z2 , что
det(xA ; yA ) = 1, det(xB ; yB ) = 1. Далее раскладываем вектор AyA по базису xA ; yA , а вектор ByB
по базису xB ; yB . Получаем AyA = c1 xA + yA , ByB = c2 xB + yB . Обозначим S1 = (xA ; yA ); S2 =
(xB ; yB ). Если = , то переходим к п. 4.1, иначе к п. 4.2.
4.1. Если c1 = c2 , то AB и AS = SB , где S = S1 S2;1 . Если c1 = ;c2 , то AB и AS = SB , где
S = S1 T ;1 S2;1 , T = ( ;01 01 ). Если jc1 j 6= jc2 j, то A и B не подобны.
4.2. Считаем, что > . Делим с остатком c1 и c2 на ; . Получаем c1 = q1 ( ; ) + r1 ,
c2 = q2( ; )+ r2 . Если r1 = r2 , то AB и AS = SB , где S = S1 T1 T2;1 S; 2;1 , T1 = ( 10 q11 ), T2 = ( 10 q12 ).
Если r1 = ; ; r2, то AB и AS = SB , где S = S1 T1 QT2;1 S2;1 , Q = 10 ;;11 . В противном случае
A и B не подобны.
5. Находим квадратичную форму f (x; y), фигурирующую в следствии 5, и ее дискриминант
D. Если D < 0, то переходим к п. 5.1, если D > 0, то к п. 5.2.
5.1. f (x; y) | положительно определенная форма. Для выяснения вопроса о представимости
целого числа этой формой применяется алгоритм приведения Гаусса (напр., [3], с.293{294).
5.2. f (x; y) | неопределенная форма. В этом случае можно применить алгоритм из [5].
Трудоемкость алгоритма. На вход алгоритма подаются две целочисленные матрицы A и B .
Будем считать, что элементы этих матриц ограничены по модулю константой C . Пусть n = log C
| длина представления числа C . Очевидно, алгоритм, приведенный выше, является полиномиальным относительно n, если d() приводим. Алгоритм приведения Гаусса также является полиномиальным. Алгоритм
pD из [5] не полиномиален, т. к. он использует разложение квадратичной
P
+
0
иррациональности
Q0 в цепную дробь, которая является периодической с длиной периода
p
l = O( D log D). Вопрос о существовании полиномиального решающего алгоритма в случае,
если f (x; y) | неопределенная форма, остается открытым.
Часть результатов, представленная в данной статье, была анонсирована в ([6], с. 112).
Литература
1.
2.
3.
4.
5.
Мальцев А.И. Основы линейной алгебры. { М.{Л.: Гостехиздат, 1948. { 424 с.
Гантмахер Ф.Р. Теория матриц. { М.: Наука, 1988. { 552 с.
Бухштаб А.А. Теория чисел. { М.: Просвещение, 1966. { 384 с.
Касселс Дж. Рациональные квадратичные формы. { М.: Мир, 1982. { 440 с.
Matthews K. The diophantine equation ax2 + bxy + cy2 = N , D = b2 ; 4ac > 0 // J. Theor.
Nombres Bordeaux. { 2002. { V. 14. { P. 257{270.
6. Шевченко В.Н., Сидоров С.В. О подобии матриц второго порядка над кольцом целых чисел //
Материалы XIV Международн. школы-семинара \Синтез и сложность управляющих систем"
(Нижний Новгород, 27 октября { 1 ноября 2003 г.) / Под ред. О.Б. Лупанова. { Н. Новгород:
Изд-во. Нижегородск. гос. пед. ун-та, 2003. { 131 с.
Нижегородский государственный
Поступила
30.09.2004
университет
64
Документ
Категория
Без категории
Просмотров
13
Размер файла
202 Кб
Теги
кольцо, над, матрица, подобия, чисел, порядке, второго, целым
1/--страниц
Пожаловаться на содержимое документа