Выделение эффективно разрешимых классов в задаче подобия матриц над кольцом целых чисел Сидоров Сергей Владимирович

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Сидоров Сергей Владимирович. Выделение эффективно разрешимых классов в задаче подобия матриц над кольцом целых чисел: диссертация ... кандидата физико-математических наук: 01.01.09 / Сидоров Сергей Владимирович;[Место защиты: Нижегородский государственный университет им.Н.И.Лобачевского].- Нижний, 2015.- 121 с.

Содержание к диссертации

Введение

Глава 1. Общие результаты о подобии матриц 20

1.1 Постановка задачи подобия матриц над коммутативным кольцом с единицей 20

1.2 Необходимые условия подобия матриц над Z. Связь подобия матриц над Z и над кольцом вычетов Zm 24

1.3 Редукция матриц, имеющих приводимый характеристический многочлен, к блочному верхне-треугольному виду 30

1.4 Подпространство М в и модуль Лдд 31

1.5 Необходимые условия подобия матрице Фробениуса над кольцом целых чисел 34

Глава 2. Подобие матриц второго порядка над Z и Z[i] 41

2.1 Подобие матриц второго порядка над Z 41

2.1.1 Случай приводимого характеристического многочлена 41

2.1.2 Случай неприводимого характеристического многочлена 45

2.1.3 Трансформирующие матрицы при подобии матриц второго порядка 53

2.1.4 Алгоритм распознавания подобия для 2x2 матриц 56

2.1.5 Классы подобия матриц с характеристическим многочленом Л2 - p2k+l, к 0 58

2.2 Подобие матриц второго порядка, имеющих приводимый харак теристический многочлен, над кольцом Z[i] 67

Глава 3. Подобие матриц третьего порядка над Z 74

3.1 Характеристический многочлен вида (Л — а)3 75

3.2 Характеристический многочлен вида (Л — а) (А — /З)2 78

3.3 Характеристический многочлен вида (Л — а) (А — /3)(А — 7) 83

3.4 Характеристический многочлен вида (Л — а) (Л2 + u\ + v).. 87

Глава 4. Подобие матриц с целочисленным спектром 91

4.1 Свойства трансформирующих матриц 91

4.2 Алгоритм 95

4.3 Треугольный вид матрицы с целочисленным спектром и оценка числа классов 99

Заключение 107

Литература

Необходимые условия подобия матриц над Z. Связь подобия матриц над Z и над кольцом вычетов Zm
Случай приводимого характеристического многочлена
Характеристический многочлен вида (Л — а) (А — /З)2
Треугольный вид матрицы с целочисленным спектром и оценка числа классов

Необходимые условия подобия матриц над Z. Связь подобия матриц над Z и над кольцом вычетов Zm

Н. Appelgate, Н. Onishi в работе [32] рассматривали подобие матриц третьего порядка и описали канонические матрицы классов подобия только для случая, когда матрица имеет единственное собственное число кратности 3. В диссертации полностью разобраны оставшиеся случаи и описаны канонические матрицы, когда все собственные числа целые. В той же работе [32] авторы приводят без доказательства утверждение о канонических матрицах для матриц второго порядка, имеющих приводимый характеристический многочлен. В диссертации это утверждение доказывается.

В работе A. Behn, А.В. Van der Merwe [34] рассматривалось подобие матриц второго порядка. Но там приведена ошибочная формулировка теоремы о канонических матрицах классов подобия, характеристические многочлены матриц которых имеют различные целые корни. Теорема 5.2 в этой работе утверждает, что каждая матрица второго порядка, имеющая характеристический многочлен (х — а){х — d), где a,d Є Z, подобна единствен ( а Ь \ ной матрице вида , где Ъ 0 при a = dnO b a — d при

Кроме того, в диссертации рассмотрен достаточно широкий класс матриц порядка п, для которого получен квазиполиномиальный алгоритм распознавания подобия, а также приведена оценка числа классов подобия. Помимо этого, мы рассматриваем задачу подобия матриц второго порядка над кольцом целых гауссовых чисел Z[i]. Найдены канонические матрицы и число классов подобия в случае, когда характеристический многочлен приводим над Z[i].

Отметим, что задача распознавания подобия матриц над произвольным полем F, а также задача построения канонических матриц были реше ны еще задолго до того, как начали изучать подобие целочисленных матриц. Если поле алгебраически замкнуто (как, например, поле комплексных чисел С), то каждый класс подобных матриц содержит единственную жордано-ву матрицу, которую и можно выбрать в качестве канонической матрицы (см. [9]). Если поле не является алгебраически замкнутым, то канонической матрицей может служить матрица Фробениуса (в [9] она называется естественной нормальной формой). Критерием подобия двух матриц над полем F является эквивалентность характеристических матриц А — ХЕ и В — ХЕ над кольцом многочленов F[A]. В свою очередь, полиномиальные матрицы эквивалентны только в том случае, когда они имеют одинаковые нормальные диагональные формы Смита (в дальнейшем НДФС). Зная НДФС характеристических матриц А — ХЕ и В — ХЕ, можно построить единственную матрицу Фробениуса для матриц А и В, & также трансформирующую матрицу. Каждый класс подобия содержит единственную матрицу Фробениуса. Пусть D(X) =diag(l,..., 1, /і (Л),..., Л (Л)) - НДФС для матриц А - ХЕ и В — ХЕ. Тогда многочлен fi(X) делит многочлен fi+i(X) для каждого і = 1,..., s — 1. Каждому многочлену fi(X) соответствует сопровождающая матрица F{, характеристический многочлен которой есть /«(Л). Тогда блочно-диагональная матрица F =diag(i7i,..., Fs) называется нормальной формой Фробениуса для матриц А и В. Далее пусть D(X) = РА(Х)(А — XE)QA(X), D(X) = Рв{Х){В - XE)QB{X). Тогда В - ХЕ = P(A)"1 - \E)Q{\), где Р(А) = РВ(Х)-1РА, Q(X) = QA(X)QZ\ P(X)Q(X) = Е. Если записать матрицу Q{X) в виде многочлена Q{X) = QQX +Q\X l+Qk-\X+Qk и представить его в виде Q{X) = Т{Х){В - ХЕ) + Q, то В = Q lAQ.

Понятие подобных матриц над полем F можно естественным образом обобщить на произвольное коммутативное кольцо К с единицей. Если В = Х 1АХ} где X - обратимая над кольцом К матрица, то говорят, что матрица В подобна матрице А над кольцом К. При этом возникают те же задачи: задача распознавания подобия и задача описания классов подо бия. Интересно, что критерий подобия над полем переносится и на случай коммутативного кольца с единицей. Но неизвестно, как выяснять, эквивалентны ли полиномиальные матрицы в этом случае. Для полиномиальных матриц над произвольным кольцом понятие НДФС не обобщается. Это обстоятельство заставляет либо рассматривать конкретные кольца или кольца специального вида, или же ограничивать класс рассматриваемых матриц. Например, Н. Fitting [36] и В. Прокип [47] изучали свойства подобных матриц над произвольным коммутативным кольцом с единицей. В работах А.А. Нечаева [10], Т.Г. Газаряна [4] и В.Л. Куракина [8] исследуется задача подобия над артиновыми локальными кольцами. Работы В. Прокипа [48], [49] и N. Avni, U. Onn, A. Prasad, L. Vaserstein [33] посвящены задаче подобия над кольцами главных идеалов. J. Pomfret [46] рассматривал подобие матриц над конечными кольцами.

Цель работы заключается в выделении эффективно разрешимых классов в задаче подобия матриц над кольцом целых чисел, описании классов подобия и построении канонических матриц этих классов.

Методы исследований. В работе использованы методы дискретной математики, теории чисел и алгебры, особенно, линейной.

Научная новизна. Диссертация посвящена исследованию задачи подобия матриц над кольцами целых чисел и целых гауссовых чисел. В работе: 1) описываются классы матриц, для которых существуют эффективные алгоритмы распознавания подобия; 2) описываются канонические представители классов подобия. Все выносимые на защиту результаты являются новыми. Сформулируем основные результаты. 1. Доказано, что для матриц с целочисленным спектром, жорданова форма которых не содержит клеток одинакового порядка для одного и того же собственного числа, существует квазиполиномиальный алгоритм распознавания подобия. 2. Получена оценка числа классов подобия для матриц с целочисленным спектром, все собственные числа которых различны. 3. Описаны канонические матрицы для классов подобия матриц второго и третьего порядков, все собственные числа которых целые, и доказано существование полиномиального алгоритма. 4. Для 2x2 матриц с элементами из Z[i], имеющих приводимый характеристический многочлен, описаны канонические матрицы для классов подобия над Z[i]. Теоретическая ценность и практическая значимость. Работа носит теоретический характер. Результаты, полученные в диссертации, могут быть использованы в преподавании курса линейной алгебры и специальных курсов.

Апробация работы. Результаты диссертации докладывались на Международных семинарах «Дискретная математика и ее приложения» (Москва, 2010, 2012), на Международной конференции «Проблемы теоретической кибернетики» (Пенза, 2005; Казань, 2008; Нижний Новгород, 2011; Казань, 2014), на школс-ссминарс «Синтез и сложность управляющих систем» (Нижний Новгород, 2003; Санкт-Петербург, 2006), на Международной конференции «Дискретные модели в теории управляющих систем» (Москва, 2009), на Молодежной научной школе по дискретной математике и ее приложениям (Москва, 2007, 2011, 2013), на заседаниях Нижегородского семинара по дискретной математике.

Случай приводимого характеристического многочлена

Ясно, что СІІЇЇІЛДВ = СІІЇЇІМДВ = ті1—ranks . Другими словами, размерность модуля Лдв равна геометрической кратности собственного числа О матрицы S. Пусть характеристический многочлен матриц А и В имеет следующее разложение на множители над полем комплексных чисел d(X) = (А — X\)kl (А — Xt)kt. Тогда /І = ХІ — Xj - все собственные числа матрицы S, и характеристический многочлен матрицы S равен

Итак, в общем случае, задача о распознавании подобия матриц сводится к решению некоторого дпофантова уравнения. Как решать это уравнение в общем случае, неизвестно. Но если п = 2, то det(iriTi + Х2Т2) = fdetTi + xiX2(det(t\,t2) +det( i,4)) + 2detT2 - бинарная квадратичная форма. Таким образом, задача о подобии матриц второго порядка сводится к классическому вопросу теории чисел - представлению целого числа (в нашем случае ±1) бинарной квадратичной формой (см., например, [3], [7], [44]).

Необходимые условия подобия матрице Фробениуса над кольцом целых чисел Здесь получены некоторые необходимые условия подобия над кольцом целых чисел целочисленной матрицы А матрице Фробениуса F.

Таким образом, любая рациональная трансформирующая матрица может быть получена следующим образом: первый столбец Х\ берется любым, отличным от нулевого; остальные вычисляются последовательно по формулам хк = Axk-i — fk-1%1, к = 2,..., п.

Если Х\ = (ХЦ, ..., жпі)т, то X = ХцТ\ + ... + хп\Тп. Очевидно, что система матриц Т\,..., Тп линейно независима, поэтому образуют базис подпространства MA,F- Далее очевидно, что Ті,..., Тп образуют базис модуля Лд_р. Лемма доказана. Нас интересует вопрос, подобна ли матрица А матрице Фробениуса F над кольцом целых чисел. Другими словами, существует ли матрица X Є A,F с условием detX = ±1. Так как Ахп = fn%i, то для подобия над Z необходимо выполнение сравнения Ахп = 0 (mod fn). Тогда Х\ = 4-Ахп, Xk = Axk-i — fk-1%1, к = 2,..., n — 1. Будем говорить, In что матрица X = (х\}... ,хп), полученная таким образом, соответствует вектору хп.

Теперь рассмотрим частный случай, когда характеристический многочлен имеет вид d(X) = Xа — d, d 7 0. При этом столбцы трансформирующей матрицы имеют вид хи = А х\, к = 2,..., п. Первый и последний столбцы связаны условием Ахп = dx\. Множество решений сравнения Ахп = 0 (mod d) образует подгруппу Г в аддитивной группе Z , если рассматривать столбцы хп по модулю d. Если d — простое число, то Г - циклическая группа порядка d.

Лемма 3 Пусть характеристический многочлен матрицы А равен d(X) = Xа — d} d 7 0. Рассмотрим две целочисленные матрицы X = (х\,Х2,,жп), Y = (уі,2/2, іУп)і столбцы которых удовлетворяют условиям, Xk = Ak lx\, yk = Ak lyi, к = 2,... ,n, Axn = dx\, Ayn = dy\. Если xn = yn (mod d), mo detX = det У (mod d).

Один из определителей очевидно есть det Y. Оставшиеся 2П — 1 определителей делятся на два типа: 1) первый столбец определителя первого типа равен у\ (их ровно 2n_1 — 1); 2) первый столбец определителя второго типа равен At (их ровно 2n_1). Докажем, что все эти определители делятся на d. Отсюда и будет следовать утверждение леммы.

Определители второго типа делятся на d, так как каждый из них равен произведению det Л = (—l)n+1 i и некоторого другого определителя. Теперь рассмотрим произвольный определитель detT первого типа. Пусть его столбцы с номерами к\, &2, , ка равны соответственно АкЧ, АкЧ,..., АкЧ, причем 2 кх к2 ... ks п. Остальные столбцы имеют вид Агу\. Таким образом, detT = det(yi,... ,АкЧ,... ,Akst,...). Умножив detT на (detA)n kl, получаем (det A)n kl det T = det(An-klyu ..., АЧ,..., Ап+к кЧ,...). Так как det A = (—l)n+ld, то левая часть последнего равенства делится na,dn kl. Определитель из правой части делится на dn kl+l, так как все его столбцы, номера которых больше или равны к\, делятся на d. Следовательно, detT делится на d. Лемма доказана.

Так как Г - циклическая группа с порождающим элементом у, то все ее элементы имеют вид ку для некоторого целого к. Соответствующие им матрицы имеют вид kY. Поэтому из равенства &еі{кУ) = kn det Y и Теоремы 7 следует доказываемое утверждение. Теорема доказана. имеет вид 8&2 = ±1 (mod 17) и эквивалентно сравнению к2 = ±2 (mod 17), имеющее решение к = ±6 (mod 17). Тем не менее, А и F не подобны над кольцом целых чисел, так как у их характеристических матриц не равны идеалы, порожденные минорами первого порядка (см. подобия является разрешимость сравнения —ЗА;3 = ±1 (mod 7), которое эквивалентно следующему: А;3 = ±2 (mod 7). Это сравнение не имеет решений, так как куб любого целого числа сравним по модулю 7 либо с 1, либо с —1. Таким образом, матрица А не подобна F.

Характеристический многочлен вида (Л — а) (А — /З)2

Если уравнение д(х,у) = ±1 имеет решение (ж,у), то уравнение f(x,y) = ±1 также имеет решение (х,ру), так как f(x,py) = д(х,у). Следовательно, из подобия матриц В , В" вытекает подобие матриц А , Л". Теперь обратно. Если разрешимо уравнение f(x,y) = ±1, то по Лемме 6 оно имеет решение вида (х,ру). Таким образом, (х,у) является решением уравнения д(х,у) = ±1. Тем самым доказано, что из подобия матриц А , А" следует подобие матриц В , В". Лемма доказана.

Определение 5 Обозначим через N(d) число классов подобия матриц, имеющих характеристический многочлен d(X) = X2 — d. Теорема 16 Если р - простое число, N(p) = t и минимальное положительное решение уравнения Пелля х2 — ру2 = ±1 ме делится на р, то

Сначала докажем, что матрицы Ak+i t+j представляют различные классы подобия, т.е. не подобны при разных і и j. Проведем индукцию по ft. При ft = 0 утверждение превращается в одно из условий теоремы. Предположение индукции: матрицы Ak t+j не подобны при различных і и j. Следовательно, матрицы Ak+ijt+j = pAk t+j, і = 0,..., ft — 1 также не подобны. Далее, матрицы 4fc,(A;-i)t+j не подобны при разных j по предположению индукции, значит, по Лемме 7 матрицы Ak+i kt+j также не подобны при разных j. Осталось доказать, что матрицы Ak+i t+j с различными і не подобны. Это следует из того, что НОД элементов матрицы Ak+i,it+j равен pk %HOJ\{(ij, bj, Cj). При разных значениях і эти величины различны, что противоречит одному из необходимых условий подобия. Теперь перейдем к доказательству того, что любая матрица, имеющая характеристический многочлен Л2 — р2 +1, к О, подобна матрице Ak-\-\7it+j для некоторых і и j. Снова применим индукцию по к. Случай к = 0 очевиден. Предположение индукции: каждая матрица, имеющая характеристический многочлен Л2 —р, подобна одной из матриц имеет характеристический многочлен А —р . Следователь-d -а! ) но, по предположению индукции А подобна одной из матриц вида Ak t+j-Так как d = с не делится на р, а элементы матриц Ak t+j при і = 0,..., к — 2

Здесь будем рассматривать 2x2 матрицы с коэффициентами из Z[i]. Обозначим через Кцщ(А) множество матриц, подобных матрице А над полем рациональных гауссовых чисел Q[i], а через Кхщ(А) множество матриц, подобных матрице А над кольцом Z[i]. В этом разделе символ будет обозначать подобие над полем Q[i], а символ будет обозначать подобие над кольцом Z[i]. Как и в случае целочисленного подобия, для подобия матриц над Z[i] необходимо подобие их над полем Q[i].

Легко проверить, что введенное отношение /-эквивалентности является отношением эквивалентности на множестве элементов кольца Z[г]. Таким образом, имеет место следующее утверждение. кольцом Z[i] тогда и только тогда когда г и г" являются эквива лентными относительно идеала I = (/3 — а), порожденного элементом, /3 — а.

Пусть [5 — а = т + пі. Не уменьшая общности, можно считать, что п 0, а если п = 0, то т 0. Из определения / - эквивалентности следует, что класс эквивалентности Ка, содержащий элемент а Є Z[i], является объединением четырех смежных классов а + I, —а + /, га + /, — га + /. Следовательно, в качестве представителя класса эквивалентности можно взять элемент из некоторого смежного класса. Известно, что представителем любого смежного класса фактор-кольца кольца Z[i] по идеалу / = (т + пі) является некоторая точка квадрата с вершинами 0, т + пі —п + ті (т — п) + (т + п)і (см. рис. 2.1). Этот квадрат обозначим через К(т,п).

Но не все точки квадрата К(т, п) принадлежат разным классам эквивалентности. Действительно, легко показать, что для любого а Є Z[i] точки а, 2р — а, p + i(p — а), р — i(p — а), где р = їїк !1 + iniY1 — центр рассматриваемого квадрата, эквивалентны относительно идеала I. Заметим, что эти точки также образуют квадрат с центром в точке р. Кроме того, если точка а принадлежит исходному квадрату К(т, п), то полученный новый квадрат находится внутри исходного. Верно и обратное: если точки образуют вершины квадрата с центром р, то они / - эквивалентны. Следовательно, представитель любого класса эквивалентности находится в квадрате К( , ) (на рисунке это квадрат ОМ\РМ ). Заметим, что точки на сторонах ОМ\ и М\Р эквивалентны точкам, симметричным относительно диагонали ОР: на сторонах ОМ и М Р соответственно.

Определение 7 Обозначим через К(т + in) множество целочисленных точек, лежащих внутри квадрата К(т}п) и на двух его смежных сторонах, содержащих вершины 0, т + пі, (т — п) + (т + п)і. Из приведенных выше рассуждений вытекает следующая лемма. Лемма 8 Элементы из К(Щ + Щ) образуют множество представителей всех классов эквивалентности относительно идеала I = (т + пі)} причем различные элементы из К( + Щ) не являются I-эквивалентными.

Осталось найти количество классов эквивалентности относительно идеала I = (т + пі). Обозначим число этих классов через N(1). Для вычисления N(1) нам понадобится следующая лемма (см., например, [12]). Лемма 9 (Формула Пика, Pick G., 1899)

Если внутри многоугольника с вершинами в точках с целыми координатами лежит s, а на границе — р целочисленных точек, то площадь многоугольника равна s + — 1. Лемма 10 Пусть I = (т + пі) — идеал, порожденный элементом т + ni. Тогда верны утверждения 1) Если т = 0 (mod 2), п = 0 (mod 2), то N(1) = ± + 2. 2) Если m + n = l (mod 2), то N(I) = m2+f+\ 3) Если т = 1 (mod 2), п = 1 (mod 2), то N(I) = m2+f+\ ДОКАЗАТЕЛЬСТВО основывается на формуле Пика. Согласно Лемме 8 число классов N(1) равно мощности множества К(Щ + Щ). В силу симметрии внутри каждого из квадратов ОМхРМ М1АМ2Р, М2ВМ3Р, МЪСМАР находится одинаковое количество целочисленных точек (обозначим его через s). Через р\ обозначим количество целочисленных точек, лежащих на каждой из сторон М\Р} М2Р} М%Р} М Р} не считая вершин. Через р2 обозначим количество целочисленных точек, лежащих на каждой из сторон ОМи МіА, АМ2, М2В, БМз, М3С\ СМА, МАО, не считая вершин. Рассмотрим три возможных варианта 1)т = 0 (mod 2), п = 0 (mod 2)

Треугольный вид матрицы с целочисленным спектром и оценка числа классов

Если внутри многоугольника с вершинами в точках с целыми координатами лежит s, а на границе — р целочисленных точек, то площадь многоугольника равна s + — 1.

Лемма 10 Пусть I = (т + пі) — идеал, порожденный элементом т + ni. Тогда верны утверждения 1) Если т = 0 (mod 2), п = 0 (mod 2), то N(1) = ± + 2. 2) Если m + n = l (mod 2), то N(I) = m2+f+\ Если т = 1 (mod 2), п = 1 (mod 2), то N(I) = m2+f+\ ДОКАЗАТЕЛЬСТВО основывается на формуле Пика. Согласно Лемме 8 число классов N(1) равно мощности множества К(Щ + Щ). В силу симметрии внутри каждого из квадратов ОМхРМ М1АМ2Р, М2ВМ3Р, МЪСМАР находится одинаковое количество целочисленных точек (обозначим его через s). Через р\ обозначим количество целочисленных точек, лежащих на каждой из сторон М\Р} М2Р} М%Р} М Р} не считая вершин. Через р2 обозначим количество целочисленных точек, лежащих на каждой из сторон ОМи МіА, АМ2, М2В, БМз, М3С\ СМА, МАО, не считая вершин. Рассмотрим три возможных варианта 1)т = 0 (mod 2), п = 0 (mod 2)

В этом случае вершины квадрата if (у, ) являются целочисленными, поэтому можно непосредственно применить формулу Пика. Внутри квадрата if (тг, ) находится s, а на границе 2pi + 2р2 + 4 целочисленных точек. Число классов подобия N (а, /3) = \М\ определяется следующим образом: если т = 0 (mod 2), п = 0 (mod 2), mo АГ(а, /3) = " + 2 если m + п = 1 (mod 2); mo 7V(a, /3) если т = 1 (mod 2), п = 1 (mod 2), то 7V(a,/3) - та2+п2+6 Резюмируя приведенные результаты, отметим, что в случае кратного собственного числа количество классов подобия счетно, а в случае разных собственных чисел конечно.

В заключение приведем один интересный факт. Очевидно, что если матрицы подобны над Z, то они подобны и над Z[i]. Оказывается, что об ( « Л ратное неверно. Примером могут служить матрицы А = , В =

Каждый из вышеперечисленных классов матриц, подобных над Q, вообще говоря, не является классом подобных над Z матриц. Поэтому возникает задача о классификации матриц по отношению подобия над Z или о разбиении каждого из этих классов на подклассы матриц, подобных над

Если a\ = 0, то из этих равенств видно, что и Ъ\ = 0. Если же а\ Ф" 0, то из первого равенства следует, что Ъ\ делится на а\, так как а\ -делитель 1/3 — а\. С другой стороны, домножив первое выражение Has4, второе на —из и сложив получим ± 2i±&iS4 = (/3 —a) ( 1-- 2 3), откуда а\ делится на &i, так как Ъ\ - делитель /3 — а\: значит, а\ = Ъ\. Таким образом, матрицы вида Ra (d) подобны только в том случае, когда они совпадают. 2) А и В имеют вид Ііа/з(аі,а2,аз), «з = &з 0.

Как проверять первое условие Утверждения б, мы рассмотрели в Главе 2. Выясним, как проверить второе условие. Пусть Т\ и Т - базис А ,в = {S Є Z2x2\A S = SB }. Тогда любую матрицу из АА представить в виде хТ\ + уТ для некоторых х и у из Z. Для подобия нужно, чтобы существовали целые х и у такие, что f(x,y) = det(irTi + yT i) = о!х1 + Ь ху + с у2 = ±1. Пусть D = Ь 2 — А.а!с — дискриминант квадратичной формы f(x,y). Возможны два случая: 1) f(x,y) - знакоопределенная квадратичная форма (если D 0); 2) f(x,y) неопределенная квадратичная форма (если D 0). В первом случае уравнение f(x,y) = ±1 имеет конечное число решений, следовательно, число матриц, трансформирующих А в В : конечно. Поэтому проверку второго условия Утверждения б можно осуществить перебором. Во втором же случае это уравнение либо не имеет решений, либо имеет счетное множество решений. В разделе 2.1.3 было показано, что любая матрица, трансформирующая А в В имеет вид

Нужно проверить, существует ли такое п, что и = (aSj n ± Ь)(В — аЕ) 1 Є Z2. Это условие равносильно системе сравнений (aSi n ± Ь){В — аЕ) = 0 (mod А), где А = det(,B/ — аЕ)\, (В — аЕ) — присоединенная матрица для В — аЕ. Заметим, что достаточно рассматривать 0 п А2. Действительно, множество матриц {Qn\n Є Z} по модулю А образует циклическую группу, содержащую не более А2 элементов, так как любая степень матрицы Q представима в виде pQ + qE для некоторых целых р, q. Рассмотрев представление (3.18) по модулю А, имеем не более A2N различных матриц. В итоге условие 2) Утверждения б можно проверить за конечное число шагов. Таким образом, имеет место следующая теорема. Теорема 23 Матрицы вида (3.16) подобны над Z тогда и только тогда, когда выполняются условия: 1) А и В подобны над Z;