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

• Сидоров Сергей Владимирович
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Сидоров Сергей Владимирович

Введение

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

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

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

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

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

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

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

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

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

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

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

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

2.1.5 Классы подобия матриц с характеристическим многочленом Л2 — р2к+1,к >

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

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

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

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

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

3.4 Характеристический многочлен вида (Л — а)(Л2 + иЛ + V) . . 87 Глава 4. Подобие матриц с целочисленным спектром

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

4.2 Алгоритм

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

Заключение

Литература

Приложение А. Таблицы

Список обозначений

В работе используются следующие обозначения: Z — кольцо целых чисел Q — поле рациональных чисел

R пол6 д6иствит6л-ьнidi^ni чис6л C — поле комплексных чисел Z [г] — кольцо целых гауссовых чисел Q[i] — поле рациональных гауссовых чисел Zm — кольцо вычетов по модулю m

Mn — множество столбцов высоты n с M

— множество матриц порядка n с коэффициентами из множества M M[A] — множество многочленов с коэффициентами из множествам K* — группа обратимых элементов кольца K

trA сл6д М 9iT р и JТЕ)Т A (сумма диагональных элементов матрицы) det A — определитель матрицы A a mod m — остаток от деления целого числа a на m

TUl^C Л^сЪ-Я 4tLCTTt> ЧИСЛ^сЪ x

A 0 B — кронекерово произведение матриц A и B

Введение диссертации (часть автореферата) на тему «Выделение эффективно разрешимых классов в задаче подобия матриц над кольцом целых чисел»

Введение

Многие задачи, относящиеся к дискретной математике, в общем случае являются труднорешаемыми, поэтому естественным является стремление выделить такие подзадачи в труднорешаемой задаче, для которых существуют эффективые алгоритмы решения. Зачастую т йк и 6 п одз сь"ч и н 9)3 ы вают эффективно разрешимыми классами для общей В диссбрт^ци и

рассматривается задача подобия целочисленных матриц, которая является

6 с т 6 с т в 6 н н ы iv!

обобщением задачи подобия матриц над полем рациональ-н ых ч и сел. Задача подобия матриц над некоторым полем Е н бпосредствбн н о связана с понятием линейного преобразования некоторого линейного пространства V над пол ем Е. Каждое линейное преобразование характеризуется своей матрицей в некотором базисе. Матрицы одного и того же линейного преобразования связаны соотношением В = X—1ЛХ, где X - некоторая невырожденная матрица, называемая трансформирующей матрицей. Матрица X является матрицей перехода от одного базиса к другому. Говорят, что матрица В подобна матрице Л над пол ем Е. Таким образом, с каждым линейным преобразованием ф пространства V

связан класс [ф] подоб-

Е

чисел Q. Это позволяет ставить вопросы об алгоритмической сложности зэдэл ^ связанных с понятис1\/1

подобия матриц. Естественным образом понятие подобных матриц над полем ^ ^^^^^^^^^^^ ^^ тальцо целых чисел Z. Говорят, что матрица В Е Znхn подобна над кольцом целых чисел матрице Л € znхn, если существует такая матрица X Е Znхn с определителем det X Е { — 1,1}, что В = X—1ЛX. Введенные отношения подобия (как над полем, так и над кольцом Z) являются отношениями эквивалентности, относительно них множество всех квадратных матриц порядка п разбивается на непересекающиеся классы подобия. В связи с этим понятием возникают

д в 6 6 с т 6 с т в 6 н н ы 6 3 9)4•

1) получить алгоритм распознавания подобия матриц над кольцом цел ых ч и сел у

2) среди всех матриц из каждого класса подобия выбрать матрицу простейшего вида (каноническую матрицу).

Задача подобия матриц над кольцом целых чисел имеет давнюю историю исследований. По-видимому, эту задачу впервые начали глубоко изучать G.G. Latimer и С.С. MacDuffee. Еще в 1933 г. они показали (см. [41]), что существует биекция между классами подобия целочисленных матриц, имеющих неприводимый над Z характеристический многочлен, и классами идеалов кольца Z[0], где в — корень характеристического многочлена.

О. Taussky в работе [50] рассматривала свойства трансформирующих матриц при условии, что матрица подобна своей транспонированной мат-

Z

квадратная матрица подобна своей транспонированной).

Д.К. Фаддеев в работе [28] рассматривал целочисленное подобие двух систем матриц и установил, что эта задача сводится к вопросу о том, является ли главным некоторый идеал.

Z

ли F. Grunewald [37] и независимо Р. Саркисян [13]. Алгоритмы, описанные в их работах, являются экспоненциальными и малопригодными с вычислительной точки зрения. Это неудивительно, так как в общем случае не существует полиномиального алгоритма для распознавания подобия матриц над Z. Действительно, даже для матриц второго порядка существуют примеры (см. [23]), показывающие, что размер элементов трансформирующей матрицы субэкспоненциально зависит от размеров элементов исходных матриц. Тем не менее это не исключает существования более эффективных алгоритмов для каких-то классов матриц. Под эффективными алгоритмами будем понимать полиномиальные и квазиполиномиальные (полиномиальные при фиксированной размерности) алгоритмы. В работах Р. Саркисяна

и F. Grunewald не исследуется строение классов подобия, их мощностные характеристики, а также канонические представители классов подобия.

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

В работе А. Belm. A.B. Van der Merwe [34] рассматривалось подобие матриц второго порядка. Но там приведена ошибочная формулировка теоремы о канонических матрицах классов подобия, характеристические многочлены матриц которых имеют различные целые корни. Теорема 5.2 в этой работе утверждает, что каждая матрица второго порядка, имеющая характеристический многочлен (ж — a)(x — d), где a,d Е Z, подобна единствен-

a > d. На самом деле условие 0 < b < a — d нужно заменить на следующее:

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

Отметим, что задача распознавания подобия матриц над произвольным полем Е, а также задача построения канонических матриц были реше-

нои матрице вида

, где b > 0 при a = d и 0 < b < a — d при

0 < b < J.

ны еще задолго до того, как начали изучать подобие целочисленных матриц. Если поле алгебраически замкнуто (как, например, поле комплексных чисел С), то каждый класс подобных матриц содержит единственную жордано-ву матрицу, которую и можно выбрать в качестве канонической матрицы (см. [9]). Если поле не является алгебраически замкнутым, то канонической матрицей может служить матрица Фробениуса (в [9] она называется естественной нормальной формой). Критерием подобия двух матриц над полем Е является эквивалентность характеристических матриц Л — ЛЕ и В — ЛЕ над кольцом многочленов Е[Л]. В свою очередь, полиномиальные матрицы эквивалентны только в том случае, когда они имеют одинаковые нормаль-НЫ6 ^ДИЭ)ГОНЭ|ЛЬНЫб формы Смита ( -В ^Л^ Э)Л Ь Н 6 И Т Т Т 6 м НДФС). Зная НДФС характеристических матриц Л — ЛЕ и В — ЛЕ, можно построить единственную

Л В,

рицу. Каждый класс подобия содержит единственную матрицу Фробениуса. Пусть Б (Л) =Ша§(1,..., 1, /1(Л),..., /8(Л)) — НДФС для матриц Л — ЛЕ и В — ЛЕ. Тогда многочлен ^ (Л) делит многочлен /¡+1 (Л) для каждого г = 1,..., в — 1. Каждому многочлену ^(Л) соответствует сопровождающая матрица характеристический многочлен которой есть ^(Л). Тогда блочно-диагональная матрица Е ..., Е3) называется нормальной формой

Фробениуса для матриц Л и В. Далее пусть Б (Л) = Ра(Л)(Л — ЛЕ)QA(Л), Б (Л) = Рв (Л)(В — ЛЕ^в (Л). Тогда В — ЛЕ = Р (Л)—1(Л — ЛЕ ^(Л), где Р(Л) = Рв(Л)—1Ра, Q(Л) = QA(Л)Q—1, Р(ЛЩЛ) = Е. Если записать матрицу Q(Л) в виде многочлeнaQ(Л) = QoЛk+Q1Лk~1+Qk-1Л+Qk и представить его .в видб Q(Л) = Т(Л)(В — ЛЕ) + Q, то В = Q 1ЛQ.

Е

зом обобщить на произвольное коммутативное кольцо К с единицей. Если В = X-1ЛX, где X - обратимая над кольцом К В Л К.

же задачи: задача распознавания подобия и задача описания классов подо-

бия. Интересно, что критерий подобия над полем переносится и на случай коммутативного кольца с единицей. Но неизвестно, как выяснять, эквивалентны ли полиномиальные матрицы в этом случае. Для полиномиальных матриц над произвольным кольцом понятие НДФС не обобщается. Это обстоятельство заставляет либо рассматривать конкретные кольца или кольца специального вида, или же ограничивать класс рассматриваемых матриц. Например, Н. Fitting [36] и В. Прокип [47] изучали свойства подобных матриц над произвольным коммутативным кольцом с единицей. В работах A.A. Нечаева [10], Т.Г. Газаряна [4] и B.J1. Куракина [8] исследуется задача подобия над артиновыми локальными кольцами. Работы В. Прокипа [48], [49] и N. Avni. U. Ünii. A. Prasad, L. Vasers lein [33] посвящены зcL^i^cI/hсз подобия над кольцами главных идеалов. J. Pomfret [46] рассматривал подобие матриц над конечными кольцами.

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

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

Научная новизна. Диссертация посвящена исследованию задачи подобия матриц над кольцами целых чисел и целых гауссовых чисел. В работе: 1) описываются классы матриц, для которых существуют эффективные алгоритмы распознавания подобия; 2) описываются канонические представители классов подобия. Все выносимые на защиту результаты являются новыми. Сформулируем основные результаты.

1. Доказано, что для матриц с целочисленным спектром, жорданова форма которых не содержит клеток одинакового порядка для одного и того же собственного числа, существует квазиполиномиальный алгоритм распознавания подобия.

2. Получена оценка числа классов подобия для матриц с целочисленным спектром, все собственные числа которых различны.

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

4. Для 2 х 2 матриц с элементами из Z[г], имеющих приводимый характеристический многочлен, описаны канонические матрицы для классов подобия над Z[г].

Теоретическая ценность и практическая значимость. Работа носит теоретический характер. Результаты, полученные в диссертации, могут быть использованы в преподавании курса линейной алгебры и специальных курсов.

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

Диссертация состоит из введения, четырех глав, заключения, приложения и списка литературы.

Глава 1 1 юс вящена общим результатам о подобии матриц над коммутативным кольцом с единицей и, в частности, над кольцом целых чисел. Поскольку от ношен ие подобия матриц является отношением эквивалент-

п х п

щихся классов подобия. Обозначим через Кц(Л) множество целочислен-

ных матриц, подобных матрице А над полем рациональных чисел Q, т. е. Кд(А) = {В Е Znxn I В « А} = {X-1АХ I X Е Znxn,ае1 X = 0}. Аналогично через Кг (А) обозначим множество целочисленных матриц, подобных матрице А над кольцом целых чисел Z, т. е. Кг (А) = {В Е Znxn | В ~ А} = {X-1АХ I X Е Znxn, det X Е {1, — 1}}. Вообще говоря, множества Кц(А) и Кг (А) не равны. Множество Кц(А) является объединением конечного или бесконечного множества классов подобия Кг(А{), где г Е I. Нас интересует как устроено это разбиение.

В разделе 1.1 вводится определение подобия матриц над коммутативным кольцом с единицей и приводится критерий подобия (Теорема 1), который повторяет критерий подобия матриц над полем. Если К является полем, то, как уже было отмечено выше, этот критерий дает алгоритм для распознавания К.

В разделе 1.2 получено несколько необходимых условий подобия матриц над Z. А именно, если А ~ В, то 1)АиВ подобны над полем рациональ-н ых ч и сел. А и В подобны над всеми кольцами вычетов Zm; 3) идеалы, порожденные минорами к-го порядка характеристических матриц А — ХЕ и В — ХЕ, совпадают ^для вссх^ к = 1,... ,п; 4) наибольшие общие ли миноров к-го порядка матриц А и В совпадают для всех к = 1,... ,п. Приведены примеры, показывающие, что эти условия не являются достаточными.

В разделе 1.3 приведена теорема (теорема 5), которая позволяет свести распознавание подобия матриц с приводимым характеристическим многочленом к блочным верхне-треугольным матрицам. Если д,(Х) = р1 (Х)... рДХ) — разложение характеристического многочлена матрицы А на неприводимые множители над полем Q, то А подобна над Z блочной верхне-треугольной матрице В, диагональные блоки Вц которой имеют характеристический многочлен Р{(Х). В частности, если матрица имеет целочисленный спектр, то преобразованием подобия она приводятся к верхне-

треугольному виду. Это непосредственно вытекает из теоремы 5. Но автор

приводит другое доказательство, поскольку оно дает алгоритм приведения

матрицы к треугольному виду преобразованием подобия.

В разделе 1.4 вводятся в рассмотрение подпространство Mab = {X £

gnxn | Ах = XB} и модуль ддв = Mab п Znxn = {X £ Znxn | AX =

XB}. Подобие матриц А и B над Z равносильно существованию в модуле

Ла,в унимодулярной матрицы (т. е. матрицы, определитель которой равен

1 пли -1). Модуль Ла , в имеет размерность, совпадающую с размерностью

t

подпространства MabB, причем dim MabB = n2—rankS < ^ k2, где S =

i=i

E & А — BT 0 E, ki — кратность собствеиного числа ait

А. А B

над Q, то dim Ma , в = dimЛA , в = n. Базис T\,..., Tm модул я Ла , в можно найти за полиномиальное время, решив в целых числах однородную систему

S.

унимодулярная, то А и B подобны. Но проблема в том, что этого может не случиться. В этом случае задача сводится к выяснению разрешимости в

m

целых числах уравнения f (x\,..., xm) = det(^ xiTi) = ±1.

i=i

В разделе 1.5 рассматривается вопрос о подобии матрице Фробениуса F. Если характеристический многочлен матрицы А неприводим, то в явном виде описан базис модуля Ла,^ . Если характеристический многочлен неприводим над полем рациональных чисел и имеет вид d(X) = Xn — d, то получены необходимые условия подобия. К сожалению эти условия не являются достаточными, что показывают приведенные в этом пункте примеры. Тем не менее, найденные условия не являются следствием необходимых условий подобия, полученных в 1.2.

Глава 2 X ЮСВЯЩ6Н cL Z

2.1) и матриц второго порядка над Z[i] (раздел 2.2).

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

Q

ющая характеристический многочлен с1(Х) = (Х — а)2, подобна одной из

( а 0 I ( а 1 I

жордановых матриц Я0(а) = или Я1(а) = . Таким об-

0 а 0 а

разом, существуют два класса подобных над ^ ^^^иц: Кц(Я0(а)) = {А Е Z2x2 | А и Яо(а)}, Кц(Яо(а)) = {А Е Z2x2 | А и ЯДа)}, т. е. М(д,(Х)) = Кц(Я0(а))иКц(Я1(а)). Очевидно, чтоКд(Я0(а)) = Кг(Я0(а)) = {Я0(а)}. Доказано, что класс Кц(Я1(а)) разбивается на счетное число подклассов Кг(Яу(а)) = {А Е Z2x2 | А ~ Яу(а)}, каждый из которых характеризуется

( а ] I

канонической матрицей Яу (а) = , где ] > 1.

0а

Далее рассматривается случай характеристического многочлена вида (Х — а)(Х — в). Можно считать, что а < в. Над пол ем Q каждая матрица, имеющая такой характебистический многочлен, подобна жордановой матч ( а 0 I

рпцеЯ0(а,в)= . Таким образом, имеем один класс подобных над

0 в 2 2

^ ^отрнц Кц(Я0(а, в)) = {А Е Z2x2 | А и Я0(а,в)}. Доказано, что класс Кц(Я0(а, в)) разбивается на конечное число подклассов Кг(Яу(а, б)) =

а ]

{А Е Z2x2 | А ~ Яу (а, в)}

, и матрица вида Яу (а, в) = I I, гДе

0в

0 < j <

в—а

является канонической. Таким образом, в этом случае число

2

классов подобия конечно и равно

в—а

2 + 1. Также в этом пункте приведен пример, показывающий, что необходимые условия подобия, полученные в разделе 1.2, не являются достаточными даже для матриц второго порядка.

В подразделе 2.1.2 рассмотрен случай неприводимого характеристического многочлена. В этом случае dim Лдв = 2 и теорема 14 устанавливает явный вид базисных матриц T1 и T2 модул я Лдв. Задача распознавания подобия сводится к выяснению разрешимости в целых числах уравнения f (x,y) = det(xTi + yT2) = ax2 + bxy + cy2 = ±1. Ho f (x,y) - бинарная квадратичная форма, а задача о представлении целого числа такой формой является классической задачей теории чисел, которую рассмат-

j^pïBcLjt еице К.Ф. Гаусс. Доказано, что число классов подобия 2 х 2 матриц с неприводимым характеристическим многочленом конечно. Достаточно рассматривать характеристические многочлены вида d\(X) = Л2 — d и d2(A) = Л2 — Л — d. Если матрица A имеет неприводимый характеристиче-

2 l a b |

ский многочлен di (Л) = Л2 — d, то A подобна матрице R =1 I , где

\с —ai

a > 0, \b\ > a + 1, \c\ > a + 1, причем при d > 0 имеет место неравенство

a

\/2d—1—1 2

а при d < 0 неравенство a < Щу1 . Если матрица A имеет

неприводимый характеристический многочлeнd2(Л) = Л2—Л—d, то A подоб

| a + 1 b

на матрице R = | | , где a > 0, \b\ > a + 1, \c\ > a + 1, причем

ca

л/ёЩ+Г—3 4

, a при d < 0 неравенство

при d > 0 имеет место неравенство а < а < Щ — 1. Поскольку во всех случаях количество возможных значений диа-

а

для Ь и с. Следовательно, число классов подобия конечно.

В подр^здблб 2.1.3 показано, как устроено множество трансформирующих матриц для матриц, имеющих неприводимый характеристический многочлен. Пусть О = Ь2 — 4ас - дискриминант квадратичной формы /(х, у) = det(жTl + уТ2) = ах2 + Ьху + су2. Если О > 0, то форма /(х,у) является положительно или отрицательно определенной. В этом случае уравнение /(х,у) = ±1 либо не имеет решений в целых числах, либо имеет лишь конечное число решений. В первом случае матрицы не подобны, а во втором п одобн ы и для них существует только конечное число трансформирующих матриц. Если О > 0, то форма /(х,у) является неопределенной и в случае разрешимости в целых числах уравнение /(х,у) = ±1 имеет конечное число бесконечных серий решений (х,1П,у{,п), г = 1,... п € Ъ. Обозначим че-

I х' — Ьу' —2су' \ I х" — 2у'' —су'' \

рез = I , ^2 = , где (х',у')

\ 2ау' х' + Ьу' I \ ау" х" +1у" I

— минимальное положительное решение уравнения Пелля х2 — Оу2 = ±1

(в случае нечетного &), и (х'',у") — минимальное положительное решение уравнения Пелля х2 — ^ у2 = ±1 (в случае четного Ъ). Тогда в случае нечет/ X г п 1 / ^^ ^ 0 ■

ного Ъ получаем I I = ОМ ' I , п Е Z, а в случае четного Ъ

\ Уг,п X \ У«,0 )

I х2,п

получаем = ^П , п Е Z, г = 1,..., N. При этом (хг,0,уг,0)

\ Уг,п ) \ У2,0 )

— некоторые начальные решения в каждой из N серий. Следовательно,

все трансформирующие матрицы имеют вид Бг,п = хгпТ1 + уг,пТ2, п Е Z,

г = 1,... N.

В подразделе 2.1.4 приведен алгоритм распознавания подобия матриц второго порядка, который полиномиален в случае приводимого характеристического многочлена и неполиномиален в противном случае.

В подразделе 2.1.5 приведены канонические матрицы классов подобия с характеристическим многочленом вида X2 — р2к+1, р - простое число, к > 0. Обозначим число классов подобия матриц, имеющих характеристический многочлен X2 — р2к+1 через N(р). Доказано, что если минимальное положительное решение уравнения Пелля х2 — ру2 = ±1 не делится нар, то

I а. Ъ■ I

N(р2к+1) = (к + 1) • N(р). Пусть А1■ = I I = 1,... ^ — предста-

\ ^ —а )

вители классов подобия для к = 0, причем можно считать, что ^ не делится р.

г(к + 1) класса подобия можно взять

I рк а рк+% \

матрицы Ак+1,= I I , г = 0,..., к; ] = 1,... ,ъ.

\ рк—г^ —рка^ )

В разделе 2.2 рассматривается задача подобия над кольцом целых гауссовых чисел Z [г] матриц второго порядка, имеющих приводимый характеристический многочлен. Описаны канонические матрицы классов подобия. Доказано, что число классов подобия конечно, если собственные числа различные. Глава 3

1 юс вящен сЬ

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

В разделе 3.1 рассмотрен случай характеристического многочлена вида (Л — а)3. Над полем Q матрица, имеющая такой характеристический многочлен, подобна одной из жордановых матриц

Л(а) =

а00

V

, Л(а) =

/

а00

V

0 а 1 0 0 а

/

, М.а) =

( л Л

а 1 0

\

0 а 1 0 0 а

0а0 0 0 а

Тогда доказано, что

1. Кд(^(а)) = Кх(Ь(а)) = {А € Ъ3х3|А - ^(а)} = Ша)},

2. Кр(^>(а)) = К К2(ЯаМ), Кх(ЯаШ = {А € Ъ3х3|А - Яа(d)}

/

Яа (d) =

а00

V

, d > 1

0 а d 0 0 аК

3. Кд(^(а)) = К Кх(Яа(а, Ь,г)) Кх(Яа(а,Ь,г)) = {А € Ъ3х3|А Яа (а, Ь, г)},

Яа (а, Ь, г) =

( \

ааг

\

0 а Ь 0 0 а

/

а,Ь > 10 < г<НОД(а,Ь).

В разделе 3.2 рассмотрен случай характеристического многочлена вида (Л—а)(Л—в)2. Матрица, имеыщая такой характеристический многочлен,

подобна над ^ табо Л (а, в) =

Тогда доказано, что

а00 0 в 0 ^ 0 0 в )

либо -12(а, в) =

а00 0 в 1 ^00 в )

1. Кд№(а,в)) = и ЫЯа в М), ЫЯа, в (d)) = {А € Ъ3х3|А - Яа, в

Яа,в (d) =

( А Л

а d 0

0 в 0

d = ^и ^ ^ ^^^^^^^^^ный делитель ^ — а| (не

V 0 0 в )

равный ^ — а|)

2. Кц(^(а,в)) = [}Къ(Яав(а1,а2,а3)) Къ(Яав(а1,а2,а3)) Ъ3х3|А - Яа в (а1,а2,а3)},

= {А €

Яа, в (а1,а2, а3) =

( \

а а1 а2

0 в аз

{ 0 0 в )

а1, а2, а3

I) а1 = 0, 0 < а2 < а1\, аз > 1. 11а) если \в — а\ - нечетное, то

1 < а1 < [1в——а1 \, 0 < а2 < й, а3 > 1, где й =НОД(\в — а\,а1)

11Ъ) если \в — а\ - четное, то

1)1 < а1 < в2г — 10 < а2 <й,аз > 1.

2) а1 =

_ \в—а\

2

аз > 1

если в — а > 0, то —|_\ < а2 < [|\, если в — а < 0, то —|_|\ < а2 < [\,

где г - остаток от деления аз на а1.

В разделе 3.3 рассмотрен случай характеристического многочлена вида (X — а)(А — в)(А — 7). Можно считать, что а < в < 1. Над полем ^ ^отрица, имеющая такой характеристический многочлен, подобна

J (а,в,1 ) =

а00 0в0

. Тогда доказано, что

V 0 0 7 / К^(3 (а, в, 7)) = и къ(Яа в л (а1,а2,аз)),

Кх(Яа,в,1 (а1, а2, аз)) = {А Е Z3x3\A - Яа,вл(аь а2, аз)}

Яа,в,7(аЬ а2) аз) =

( \

а а1 а2

0 в аз

\ 0 0 7 у

а1, а2, аз

I) а1 = 0 0 < а2 < 0 < аз < \

11а) если 7 — в ~

1 < а1 < [\, 0 < а2 <1 — а, 0 < аз < [— \ 11Ъ) если 7 — в ~

ЧбТНОб^ то

1) 1 < а1 < [—0 < а2 <1 — а, 0 < а3 < — 1

2) 1 < а1 < —II1 ] < а2 < а3 = •

В разделе 3.4 рассмотрен случай характеристического многочлена вида (Л — а)(Л2 + иЛ + -и), где Л2 + иЛ + V неприводимый многочлен. Над

полем ^ ^^^ица А, имеющая такой характеристический многочлен, по/ п п \

добна матрице Фробениуса Г =

А подобна блочной матрице В =

а 0

0 —и

0 1

а а

0 А'

Ъ

а — 0 /

где ат € Ъ2, А' € Ъ2х2, при-

чем характеристический многочлен матрицы А' равен Л2+иЛ+V. В Теореме 23 содержится критерий подобия таких матриц, который одновременно является и алгоритмом распознавания подобия. Доказано, что класс Кц (Г)

Ъ.

Глава 4 посвящен сЬ подобию матриц с целочисленным спектром, жор-данова форма которых не содержит клеток одинакового порядка для одного и того же собственного числа. В разделе 4.1 показано, что определитель произвольной матрицы из подпространства М7 77, где , — жорданова матрица, равен произведению диагональных элементов. В разделе 4.2 показано, что

т

определитель /(у1,...,ут) = det(^уТ%) произвольной матрицы из Ад в

¿=1

является произведением линейных функций с целыми коэффициентами относительно переменных у1,... ,ут. Это обстоятельство дает квазиполиномиальный алгоритм для распознавания подобия. Алгоритм заключается в решении в целых числах некоторых систем линейных уравнений. В разделе 4.3 рассмотрен случай, когда геометрическая кратность каждого собствен-

А равна 1. уменьшая общности мож^но считать,

А

любая трансформирующая матрица является верхне-треугольной. Следовательно, ее диагональные элементы могут принимать лишь два значения:

1 —1. 1,

то показано, что число классов подобия конечно и не превосходит величи-

п—1

ны П ([+ 1) ^ (а^ — аг), где а1,... ,ап — все собственные числа г=1 у-г>2

А.

В заключении приведены основные результаты диссертации и возмож-ныв направления дальнеитттих исслед^овании.

В приложении приведены канонические матрицы классов подобия над Z, соответствующих неприводимым характеристическим многочленам вида А2 — й и А2 — А — й (1 < й < 101).

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

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

Из линейной алгебры хорошо известно (см., например, [9]), что с линейным преобразованием линейного пространства V над полем а1 связан класс |ф| подобных между собой матриц. А именно, этот класс состоит из всех матриц преобразования ф в различных базисах пространства V. Если А, В Е [ф] , то существует невырожденная матрица Б с элементами из Е такая, что В = Б—1АБ. Понятие подобных матриц над полем естественным образом обобщается на произвольное коммутативное кольцо К с единицей. Определение 1 Будем говорить, что матрица В Е Кпхп подобна матрице А Е Кпхп над кольцом К, если существует матрица Б Е Кпхп такая, что АБ = БВ и det Б Е К*. При этом матрицу Б будем называть К-трансформирующей А в В матрицей.

К

АВ

Для коммутативного кольца с единицей условие det Б Е К* равносильно существованию обратной матрицы Б—1, поэтому в этом случае равенство АБ = Б В равносильно В = Б—1АБ. Для кольца целых чисел предыдущее 011 рбдблбниб прбвр0)1Ц0)бтся в с л бду Ю Щ66 •

Определение 2 Будем говорить, что матрица В Е Znxn подобна матрице А Е %пхп над кольц ом Z, если существует ма трица Б Е Znxn такая, что АБ = БВ и det Б Е { — 1,1}.

Определение 3 Целочисленная квадратная матрица называется унимо-дулярной, если ее определитель равен 1 или —1.

Утверждение 1 Отношение подобия матриц над коммутативным кольцом с единицей есть отношение эквивалентности.

Доказательство.

А так как

АЕ = ЕА, где Е — единичная матрица (det Е =1 € К*).

В А, то сущвстВув'1' об-

ратимая над К матрица 5 ТйКйЯ^ что А5 = 5В. Следовательно, матрица 5 имеет обратную и det 5—1 € К*. Домножив равенство А5 = 5В слева и справа на 5—1, имеем В5—1 = 5 —1А, т. е. матрица А подобна матрице В. 3) Транзитивность. Пусть матрица С подобна матрице В, а матрица В подобна матрице А. Тогда найдутся обратимые над К матрицы 51 и 52 такие, что А51 = 51В, В52 = 52С. Верна следующая цепочка равенств: А(5152) = (А51)52 = (51В)52 = 51(В52) = 51(52С) = (5152)С. Поскольку det(S1S2) = det 51 det 52 € К*, то С подобна матрице А. Утверждение доказано.

Поскольку от ношен И^З подобия матриц над коммутативным кольцом с единицей есть отношение эквивалентности, то множество матриц Кпхп разбивается на классы эквивалентности К^ ] €•], где • — некоторое множество индексов, конечное или бесконечное. Таким образом, можно записать

Кпхп = у К3, з €7

где Кз — класс подобных матриц.

В связи с введенным понятием подобия матриц возникают две естественные з^д^чи.

Р1 : выяснить, являются ли две данные матрицы подобными, и если являются, найти хотя бы одну трансформирующую матрицу; 2:

матрицу специального вида — каноническую матрицу).

Для проверки подобия над полем Е известен алгоритм (см., например, [9]) приведения характеристической матрицы А — ЛЕ к нормальной диагональной форме Смита и построения по ней единственной канониче-

ской матрицы Г (в [9] она называется естественной нормальной формой А

Е[А] является евклидовым и, следовательно, кольцом главных идеалов. Так как кольцо К [А] не является кольцом главных идеалов (а, следовательно,

Список литературы диссертационного исследования кандидат наук Сидоров Сергей Владимирович, 2015 год

Литература

1. Астафьев H.H. Двойственные системы однородных линейных уравнений // Тр. Ин-та математики и механики УрО РАН. -2013. - Т. 19, №2,- С. 48-53.

2. Боревич З.И., Шафаревич И.Р. Теория чисел. - М.: Наука, 1985.

3. Бухштаб A.A. Теория чисел. - М.: Просвещение, 1966.

4. Газарян Т. Г. Свойства матриц над коммутативным кольцом, связанные с отношением подобия // Дискретная математика. - 1994. -т. б, вып. 3. С. 143-153.

5. Газарян Т. Г. Подобие инволютивных матриц над локальным кольцом характеристики 2к // Дискретная математика. - 1995. - т. 7, вып. 4 - С. 145-156.

6. Гантмахер Ф.Р. Теория матриц. - 5-е изд. - М.: ФИЗМАТЛИТ, 2004.

7. Касселс Дж. Рациональные квадратичные формы. Пер. с англ. - М.: Мир, 1982.

8. Куракин В. Л. Инварианты подобия матриц над коммутативным артиновым цепным кольцом// Матем. заметки. - 2006. - том 80, вып. 3. - С. 403-412.

9. Мальцев А.И. Основы линейной алгебры. - ОГИЗ, 1948.

10. Нечаев А. А. О подобии матриц над коммутативным локальным артиновым кольцом // Тр. семинара им. И.Г. Петровского. - 1983. -№9.-С. 81-101.

11. Петров Е. Е. О классах сопряженных элементов группы SLn(2,Z/pxZ), p = 2 ¡I Известия ВУЗ. Математика - 1980. -№8. - С. 85-88.

12. Прасолов В.В. Задачи по планиметрии— М.: МЦНМО, 2006.

13. Саркисян P.A. Проблема сопряженности для наборов целочисленных матриц // Мат. заметки. - 1979. - Т.25, вып.6. - С. 811-824.

14. Сидоров С. В., Шевченко В. Н. О подобии матриц второго порядка над кольцом целых гауссовых чисел // Тезисы докладов XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 23-28 мая 2005 г.)/ Под ред. О. Б. Лупанова. - М.: Изд-во механико-математического факультета МГУ. - 2005. - С. 190.

15. Сидоров C.B. О подобии матриц третьего порядка над кольцом целых чисел // Материалы XVI Международной школы-семинара «Синтез и сложность управляющих систем» (Санкт-Петербург, 26-30 июня

2006 г.) / Под редакцией О. Б. Лупанова. - М.: Изд-во механико-математического факультета МГУ. - 2006. - С. 159.

16. Сидоров C.B. О строении классов подобия матриц второго и третьего порядков над Zf /Материалы VI Молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 апреля

2007 г.). Часть II. / Под редакцией А. В. Чашкина. - 2007. - С.52

17. Сидоров C.B. О числе обратимых матриц над кольцом вычетов // Материалы IX Международного семинара «Дискретная математика и ее приложения» (Москва, 18-23 июня 2007 г.) / Под редакцией О. М. Касим-Заде. М.: Изд-во механико-математического факультета МГУ. - 2007. - С.477.

18. Сидоров C.B. О подобии матриц второго порядка над кольцом целых гауссовых чисел, имеющих приводимый характеристический многочлен // Вестник Нижегородского университета им. Н.И. Лобачевского. - 2008. - №4. - С. 122-126.

19. Сидоров C.B. Об одном частном случае подобия матриц над кольцом целых чисел // Материалы XV Международной конференции «Проблемы теоретической кибернетики», (К азань, 2-7 июня 2008 г.). - С. 106.

20. Сидоров C.B. О необходимых условиях подобия матрице Фробениуса над кольцом целых чисел // Материалы 8-й Международной конфе-

ренции «Дискретные модели в теории управляющих систем», (Москва, 6-9 апреля 2009 г.)

21. Сидоров C.B. О подобии матриц третьего порядка над кольцом целых чисел, имеющих приводимый характеристический многочлен // Вестник Нижегородского университета им. Н.И. Лобачевского. - 2009.

ЛН. - С. 119-127.

22. Сидоров C.B. О подобии матриц с целочисленным спектром над кольцом целых чисел // Известия высших учебных заведений. Математика. - 2011. - №3. - С. 86-94.

23. Сидоров C.B. О размере элементов трансформирующих матриц при подобии матриц над кольцом целых чисел // Материалы VIII Молодежной научной школы по дискретной математике и ее приложениям (Москва, 24-29 октября 2011)

24. Сидоров C.B. О подобии матрицы второго порядка и транспонированной к ней матрицы над кольцом целых чисел // Материалы Х1-го Международного семинара «Дискретная математика и ее приложения», (Москва, 18-23 июня 2012)

25. Сидоров C.B. О подобии блочно-диагональных матриц над кольцом целых чисел // Материалы XVII Международной конференции «Проблемы теоретической кибернетики». - (К азань, 16-20 июня 2014)

26. Хинчин А.Я. Цепные дроби. - М.: Наука, 1978.

27. Шевченко В.Н., Сидоров C.B. О подобии матриц второго порядка над кольцом целых чисел // Материалы XIV Международной школы-семинара «Синтез и сложность управляющих систем» (Нижний Новгород, 27 октября - 1 ноября 2003г) Под ред. О. Б. Лупанова. - Н. Новгород: Изд. Ниж. гос. пед. университета. - 2003. - С. 131.

28. Фаддеев Д. К. Об эквивалентности систем целочисленных матриц // Изв. АН СССР. Сер. матем. - 1966. - Т.ЗО, вып.2. - С. 449-454.

29. Шевченко В. Н., Сидоров С. В. О подобии матриц второго порядка над кольцом целых чисел// Известия высших учебных заведений. Математика. - 2006. - №4. - С. 57-64.

30. Шевченко В. Н. Качественные вопросы целочисленного программирования М.: Наука, 1995.

31. Ankeny N. С. , Artin Е. , Chowla S. The Class-Number of Real Quadratic Number Fields, The Annals of Mathematics, Second Series. - 1952. - Vol. 56, №3, P. 479-493.

32. Appelgate H., Onishi H. The similarity problem for 3 x 3 integer matrices // Linear algebra and its applications. - 1982. - №42. - P. 159-147.

3 x 3

matrices over a local principal ideal ring // Comm. Algebra. - 2009. -Vol.37, №8. - P. 2601-2615.

34. Behn A., Van der Merwe A. B. An algorithm version of the theorem by Latimer and MacDuffee for 2 x 2 integral matrices // Linear algebra and its applications. - 2002. - Vol.346. - P. 1-14.

35. Farahat H. K. The multiplicative groups of a ring //Math. Zeitsch. -1965. - Vol.87. - P. 378-384.

36. Fitting H. Die Determinantenideale eines Modulus // Jahresber. Deutch. Math.-Verein. - 1936. - Vol.46. - P. 195-228.

37. Grunewald F. Solution of the conjugacy problem in certain arithmetic groups, in Word Problems II, (ed Adian, Boone, Higman). North-Holland, Amsterdam. - 1980. - P. 101-139.

38. Grunewald F. J., Iyudu N. K. The conjugacy problem for two-by-two matrices over polynomial rings // Journal of mathematical sciences. -1982. - Vol. 142, №4. - P. 2233-2247.

39. Khachay M., Pobery M., Khachay D. Integer Partition Problem: Theoretical Approach to Improving Accuracy of Classifier Ensembles // Intern. J. Artificial Intelligence. - 2015. - Vol.13, №1. - P. 135-146.

40. Lagarias J. C. On the Computational Complexity of Determining the Solvability or Unsolvability of the Equation X2 — DY2 = — 1 // Transactions of the American Mathematical Society. - 1980. - Vol. 260, №2. - P. 485-508.

41. Latimer C.G., MacDuffee C.C. A correspondence between classes of ideals and classes of matrices // Annals Math. - 1933. - Vol. 34. - P. 313-316.

42. Lenstra H.W., Jr. Algorithms in algebraic number theory, Bull. Amer. Math. Soc. - 1992. - Vol. 26. - P. 211-244.

43. Matthews K. The diophantine equation x2 — Dy2 = N, D > 1, in integers II Expositiones Mathematicae. - 2000. - Vol. 18. - P. 323-331.

44. Matthews K. The diophantine equation ax2 + bxy + cy2 = N,D = b2 — 4ac > OH J. Theor. Nombres Bordeaux. - 2002. - Vol. 14. - P. 257-270.

45. Newman M. Integral matrices. - New York and London: Academic Press, 1972.

46. Pomfret J. Similarity of matrices over finite rings // Proceedings of the AMS. - 1973. - vol. 307, №2. P. 421-422.

47. Prokip V. On similarity of matrices over commutative rings // Linear algebra and its applications. - 2005. - Vol. 399. - P. 225-233.

48. Prokip V. Diagonalizability of matrices over principal ideal domain // Ukrainian Mathematical Journal. - 2012. - vol. 64, №2. - P. 316-323.

49. Prokip V. Diagonalization of matrices over a principal ideal domain with minimal polynomial m(A) = (A — a)(X — [3), a = ft // Ukr. Mat. Visn. -2010. - Vol. 7, №2. - P. 212-219.

50. Taussky O. On the similarity transformation between an integral matrix with irreducible characteristic polynomial and its transpose // Math. Annalen - 1966. - Vol. 166. - P. 60-63.

Приложение А. Таблицы

Здесь приведены канонические матрицы для классов подобия матриц второго порядка, имеющих неприводимый характеристический многочлен Л2 — йиА2 — Л — для 1 < d < 101.