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

На правах рукшжСГГ

СИДОРОВ Сергеи Владимирович

ВЫДЕЛЕНИЕ ЭФФЕКТИВНО РАЗРЕШИМЫХ КЛАССОВ В ЗАДАЧЕ ПОДОБИЯ МАТРИЦ НАД КОЛЬЦОМ ЦЕЛЫХ ЧИСЕЛ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

2 3 СЕН 2015

005562.490

Нижний Новгород — 2015

005562490

Работа выполнена в Федеральном государственном автономном образовательном учреждении высшего образования «Нижегородский государственный университет им. Н.И. Лобачевского»

Научный руководитель:

Шевченко Валерий Николаевич доктор физико-математических наук, профессор, ФГАОУ ВО «Нижегородский государственный университет им. Н.И. Лобачевского», профессор

Официальные оппоненты:

Галкин Владимир Михайлович, доктор физико-математических наук, профессор, ФГБОУ ВПО «Нижегородский государственный технический университет им. P.E. Алексеева», заведующий кафедрой

Кочергии Вадим Васильевич, доктор физико-математических наук, профессор, ФГБОУ ВО «Московский государственный университет им. М.В. Ломоносова», профессор

Ведущая организация:

ФГБУН Институт математики и механики им. H.H. Красовского УрО РАН

Защита диссертации состоится ' С&ТЯКря 2015 года вчасов ЗО минут на заседании совета Д212.166.20 по защите докторских и кандидатских диссертаций при Нижегородском государственном университете им. Н.И. Лобачевского по адресу: С03950, г. Нижний Новгород, пр. Гагарина, 23, корп. 2, ауд. 254.

С диссертацией можно ознакомиться в Фундаментальной библиотеке ННГУ им. Н.И. Лобачевского.

Автореферат разослан " 2015 года.

Ученый секретарь

диссертационного совета Х-^^*?-"-—н ß Кротов

Общая характеристика работы

Актуальность темы. Многие задачи, относящиеся к дискретной математике, в общем случае являются труднорешаемыми, поэтому естественным является стремление выделить такие подзадачи в труднорешасмой задаче, для которых существуют эффективые алгоритмы решения. Зачастую такие подзадачи называют эффективно разрешимыми классами для общей задачи. В диссертации рассматривается задача подобия целочисленных матриц. Говорят, что матрица В G Znxn подобна над кольцом целых чисел матрице А € Z"xn, если существует такая матрица X € Z"x" с определителем detX £ {-1,1}, что В = Х-\АХ. Матрица X называется трансформирующей матрицей. Введенное отношение подобия является отношением эквивалентности, относительно него множество всех квадратных матриц порядка тг разбивается на непересекающиеся классы подобия. В связи с этим возникают две задачи:

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

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

В общем случае задачу распознавания подобия матриц над Z решили F. Grunewald [22] и независимо Р. Саркисян [18]. Этих авторов интересовала принципиальная алгоритмическая разрешимость задачи подобия матриц над Z и не интересовала трудоемкость алгоритмов. Алгоритмы, описанные в их работах, являются экспоненциальными и малопригодными с вычислительной точки зрения. Это неудивительно, так как в общем случае не существует полиномиального алгоритма для распознавания подобия матриц над Z. Действительно, даже для матриц второго порядка существуют примеры (см. [12]), показывающие, что размер элементов трансформирующей матрицы субэкспоненциально зависит от размеров элементов исходных матриц. А именно, существует последовательность пар матрицАк, Вк, подобных над Z, для которых log 11Xfc11 = Г2(л/тах{||Л^||, ||ßfc||}), где Хк — минимальная трансформирующая матрица для пары Ак, Вк, а норма матрицы - максимум из абсолютных значений ее элементов. Тем не менее этот факт но исключает существования более эффективных алгоритмов для каких-то классов матриц. В работах Р. Саркисяна и F. Grunewald не исследуется строение классов подобия, их мощностные характеристики, а также канонические представители классов подобия.

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

имеющих неприводимый над Z характеристический многочлен, и классами идеалов кольца Z[0], где в — корень характеристического многочлена.

О. Taussky в работе [26] рассматривала свойства трансформирующих матриц при условии, что матрица подобна своей транспонированной матрице (в отличие от поля рациональных чисел, над кольцом Z не любая квадратная матрица подобна своей транспонированной).

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

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

В работе А. Behn, A.B. Van der Merwe [21] рассматривалось подобие матриц второго порядка. Но там приведена ошибочная формулировка теоремы о канонических матрицах классов подобия, характеристические многочлены матриц которых имеют различные целые корни. Теорема 5.2 в этой работе утверждает, что каждая матрица второго порядка, имеющая характеристический многочлен (х — а)(х — d), где a, d 6 Z, подобна единственной матрице вида ^ ^ с£ ) ' ^ — ® ПРН a = d и 0<b<a — d при

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

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

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

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

Научная новизна. Диссертация посвящена исследованию задачи по-

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

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

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

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

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

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

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

Публикации. По теме диссертации автором опубликовано 15 работ (115], из них 4 - в изданиях, рекомендованных ВАК [1-4]. Работы [1], [5], [15] выполнены совместно с В.Н. Шевченко. В [1] и [15] В.Н. Шевченко принадлежит постановка задачи и формулировка необходимых условии подобия матриц над Ъ, а автору принадлежат доказательства. В работе [5] В.Н.

Шевченко принадлежит постановка задачи, а автору принадлежат формулировки теорем и доказательства.

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения, списка литературы и приложения. Общий объем диссертации составляет 121 страницу. Библиография содержит 50 наименований.

Содержание работы

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

Глава 1 посвящена общим результатам о подобии матриц над коммутативным кольцом с единицей и, в частности, над кольцом целых чисел. Поскольку отношение подобия матриц является отношением эквивалентности, то множество п х п матриц является объединением непересекающихся классов подобия. Обозначим через /^(Л) множество целочисленных матриц, подобных матрице Л над полем рациональных чисел С^, т. с. КЯ(А) = {В е Ъпхп I Б « Л} = {Х^АХ I X е Ъпхп,АеЬХ ^ 0}. Аналогично через К%(А) обозначим множество целочисленных матриц, подобных матрице А над кольцом целых чисел Z, т. е. К^{А) = {В £ 2,пхп \ В ~ А} = {Х~гАХ | X € Хпхп,(1еЬХ € {1,-1}}. Вообще говоря, множества Ка{А) и Кх{А) не равны. Множество Кц(А) является объединением конечного или бесконечного множества классов подобия Къ(А{), где г € /. Нас интересует, как устроено это разбиение.

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

Теорема 1. Для того, чтобы матрицы, Л,£? £ кпх" были подобны, над кольцом К., необходимо и достаточно, чтобы их характеристические матрицы были эквивалентны.

Если К является полем, то этот критерий даст известный алгоритм для распознавания подобия матриц над К.

В разделе 1.2 получено несколько необходимых условий подобия матриц над Z. Обозначим через 1к{А — ХЕ) - идеал в кольце Z[A], порожденный минорами к-го порядка характеристической матрицы А—ХЕ, а через Ак(А) - наибольший общий делитель миноров к-го порядка матрицы А. Теорема 2. Если А~В, то

1) /(Л)«/(5) для любого многочлена /(А) е Z[A]

2) А~тВ над кольцом Zm для всех т > 2

3) 1к{А - ХЕ) = 1к{В - ХЕ) для всех к = 1,...,п

4) Ак(А) = Ак(В) для всех к = 1,..., п.

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

Теорема 5.(см., например, [25]) Если характеристический многочлен ¿(X) матрицы А е ЪпУ-п раскладывается на неприводимые множители следующим образом с1(А) = рх(Л) - ... • р.,(Л) , то существуют матрицы Ау, 1 < г < 3 < в такие, что А подобна блочной верхие-треугольиой матрице

{ Ап Аи ■ ■ ■ Аъ \ О Аоу ■■■ А2в А'= . ; . .

О О ... Авв/

и характеристический многочлен матрицы А^. равен рь(Л), к = 1,..., в.

Следствие 0. Если характеристический многочлен матрицы А е 2пхп раскладывается на линейные миоэ/сители над Ъ, то А подобна над кольцом целых чисел некоторой верхие-треугольиой матрице, на диагонали которой стоят ее собственные числа.

Это следствие непосредственно вытекает из приведенной теоремы. Но в диссертации автор приводит другое доказательство, поскольку оно даст эффективный алгоритм приведения матрицы к треугольному виду преобразованием подобия.

В разделе 1.4 вводятся в рассмотрение подпространство Ма.в = {X £ су*» I АХ = хв} и модуль ЛАВ = Ма.в П Ъп*п = {X е г"х» | АХ = ХВ}. Подобие матриц А и В над Ъ равносильно существованию в модуле Аа.в унимодулярной матрицы (т. с. матрицы, определитель которой равен 1 или -1). Модуль Ал.в имеет размерность, совпадающую с размерностью подпространства Ма.в, причем сШпЛ/д.в = п2-гапк5 <

/—1

где Б = Е®А-ВТ®Е, к, — алгебраическая кратность собственного числа а,- матрицы А. Если характеристический многочлен матриц А и В нсприводим над <3, то ¿\тМА.в = ¿ппЛд.в = п. Базис ТЬ...,ТШ модуля Аа.в можно найти за полиномиальное время, решив в целых числах однородную систему линейных уравнений АХ — ХВ = 0 (при некотором выбранном порядке неизвестных элементов матрицы X матрицей этой системы линейных уравнений является матрица 5). Если среди базисных матриц нашлась унимодулярная, то А и В подобны. В противном случае задача сводится к выяснению разрешимости в целых числах уравнения

т

/(хь...,хш) =ск* (£>¿7}) = ±1-

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

ном виде описан базис модуля Если характеристический многочлен

нсприводим над полем рациональных чисел и имеет вид ¿(Х) = Хп — ¿, то получены необходимые условия подобия. Эти условия не являются достаточными, что показывают приведенные в этом разделе примеры. Найденные необходимые условия новые и не являются следствием необходимых условий подобия, полученных в разделе 1.2.

Результаты первой главы опубликованы в [1], [10].

Глава 2 посвящена подобию матриц второго порядка над Z (раздел 2.1) и матриц второго порядка над ЪЩ (раздел 2.2).

В подразделе 2.1.1 рассмотрен случай приводимого характеристического многочлена. Над полем рациональных чисел С^ любая матрица, имеющая характеристический многочлен с1(А) = (Л — а)2, подобна одной из

разом, существуют два класса подобных над матриц: Кя(11о(а)) = {А £

7?*2 | А « Я0(а)}, Кд(До(а)) = {А £ г2х2 | А « Лх(а)}. Очевидно, что ^д(ДоН) = КъШ")) = {До(«)}-

Теорема 9. Если д(Х) = (А — а)2, где а £ 2, то

1) А ~ В тогда и только тогда, когда 1\{А — \Е) = 1\{В — ХЕ)

2) Кс}(Е0(а)) = К2(Ло(а)) = {Яо(а)},

Кя№(«)) = и #г(Д»)> где Кг^а)) = {А € \ А ~ Я»}, а

- каноническая матрица.

Далее рассматривается случай характеристического многочлена вида (Л — сс)(А — /3). Можно считать, что а < р. Над полем С} каждая матрица, имеющая такой характеристический многочлен, подобна жордановой мат-

над С* матриц /Гд(ДЬ(а,/3)) = {А £ г2х2 | А « Яо(а,0)}.

Теорема 10. Если е?(А) = (Л - а)(Л - /3), а, /3 е 2. /3 > а, то

Таким образом, имеем один класс подобных

/Сд(До(а,/3)) = У где

КгШ= 6 22x2 I л ~

•2x2

ЯДа,/3) — каноническая матрица.

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

В подразделе 2.1.2 рассмотрен случай неприводимого характеристического многочлена. В этом случае сШпЛл.в = 2 и следующая теорема устанавливает явный вид базисных матриц 7\ и Т2 модуля Аа.в-

Теорема 14. Пусть А = ^ ^ ^ ^, В = ^ ^ ^ ^ и их характеристический многочлен с1{\) неприводим над р. Тогда базис модуля Аа.в образуют матрицы

~ 1 f аю 0 \ т_1/ Т-У

Т1 = гДЬц-ап ""А + ЧГ + Ь

где 6i = НОД(а12,Ъ12,Ьп ~ «и), ¿2 = НОД{а12, Ь21, Ъ22 ~ «и), А = НОДС-f, а 7 удовлетворяет сравнению =

(mod А).

Задача распознавания подобия сводится к выяснению разрешимости в целых числах уравнения f(x,y) = det(xTi +уТ2) = ах2+Ъху+су2 = ±1. Но f(x,y) - бинарная квадратичная форма, а задача о представлении целого числа такой формой является классической задачей теории чисел, которую рассматривал еще К.Ф. Гаусс. Доказано, что число классов подобия 2x2 матрице неприводимым характеристическим многочленом конечно. Достаточно рассматривать характеристические многочлены видаЙ!(А) = А2 — d и d2(А) = А2 - А - d. Если матрица А имеет неприводимый характеристический многочлен di{\) = А2 - d, то А подобна матрице R = ^ " -а ) ' где а > О, |Ь| > а + 1, |с| > а + 1, причем при d > 0 имеет место неравенство а < , а при d < 0 неравенство а < [^J • Если матрица А имеет неприводимый характеристический многочлен d2(X) = A2 — A — d, то А подобна матрице R = ^ ° ^ 1 Д ^ , где а > 0, \b\ > а + 1, |с| > а + 1,

причем при d > 0 имеет место неравенство а < vM+i-qj, а при d < О неравенство а < |с/| - 1. Поскольку во всех случаях количество возможных значений диагонального элемента а ограничено, то существует конечное число вариантов для Ь и с. Следовательно, число классов подобия конечно.

В подразделе 2.1.3 показано, как устроено множество трансформирующих матриц для матриц, имеющих неприводимый характеристический

многочлен. Пусть Б = Ь2 — 4ас - дискриминант квадратичной формы /(х,у) = det(:EГl+2Д2) = ах2 + Ьху + су2. Если И > О, то форма /(х, у) является положительно или отрицательно определенной. В этом случае уравнение /(х, у) = ±1 либо не имеет решений в целых числах, либо имеет лишь конечное число решений. В первом случае матрицы не подобны, а во втором подобны и для них существует только конечное число трансформирующих матриц. Если И > 0, то форма /(х, у) является неопределенной и в случае разрешимости в целых числах уравнение /(х, у) = ±1 имеет конечное число бесконечных серий решений (хг-.п, т/г,„), г = 1,..., ЛГ, п € Z. Обозначим

( х' - Ъу' -2су' \ _ ( х" - \у" -су" \ , , ,, через = ^ 2ау/ х, + ¡у, а/ х„ +\у„ ) , где у')

— минимальное положительное решение уравнения Пелля х2 — Еу2 = ±1 (в случае нечетного Ь), и (х",у") — минимальное положительное решение уравнения Пелля х2 — ^у2 = ±1 (в случае четного Ь). Тогда в случае

нечетного Ь получаем ( Х''п ) = <3? ( Х' а ) , п £ Z, а в случае четного Ь \ Уг.п ) \ УиО /

получаем ( Х'м ) = <3<> ( "Ег ° ) > п е г = 1,..., N. При этом у1д) \ Уг.п ) \ У'ь.О )

— некоторые начальные решения в каждой из N серий. Следовательно, все трансформирующие матрицы имеют вид ¿'¿.п = + у; пТг, п £ Z, г = 1,...,ЛГ.

В подразделе 2.1.4 приведен алгоритм распознавания подобия матриц второго порядка. Алгоритм. Вход: А, В £ г2х2.

Выход: Трансформирующая матрица 5, если А ~ В. Шаг 1. Находим характеристические многочлены ¿л(А) = det(Л—\Е), ^д(А) = det(^? — АЕ). Если ¿а(А) ф ¿в(А), то А и В не подобны. Если <1а(А) = ¿в(А), то переходим на Шаг 2.

Шаг 2. Пусть А) - характеристический многочлен матриц А и В. Если <1(А) приводим над Z, т.е. имеет вид ¿(А) = (А — а)(А — /3), а,/3 £ Z, то переходим на Шаг 3, в противном случае, на Шаг 4.

Шаг 3. Находим векторы хА,х° £ Z2 - собственные векторы матриц А и В, соответствующие а, такие, что НОД(х^,х^) = 1, ИОД(хв ,хв) = 1. Находим такие векторы уА,ув 6 Z2, что det(.rл, г/"4) = l,det(хв,ув) = 1. Далее раскладываем вектор Аул по базису хА,ул, а вектор Вув по базису хв,ув. Получаем Аул = с\хА + /ЗуА, Вув = сохв + /3ув. Обозначим = (хл,уА),32 = (хв,ув). Если а = /3, то переходим на Шаг 4.1, иначе на Шаг 4.2.

Шаг 3.1 Если С\ = С2-, то Л.^ В и АБ = БВ, где 5 = З^"1. Если

С1 = -с2, ТО Л~В и /15 = 5В, [-до 5 = ^Т"^"1, Т = ^ ^ ^ ). Если

17^|с2[, то Л и В не подобны.

Шаг 3.2 Считаем, что ¡3 > а. Делим с остатком с\ и с2 на /3 — а. Получаем с\ = д{(/3 — а) + г\, с2 = ц2ЦЗ — а) + г2.

Если т*1 = г2, то Л~В и Л5 = 5В, где 5 = адТ,-1^1, 7\ = ^ * ^ Г - ( 1 ^

V 0 1 ,

Если п = /3 - а- г2, то Л~Б и Л5 = где 5 = ЗДОД-^1, (5 = ^ ^ | В противном случае Л и В не подобны.

Шаг 4. Находим М\,Мо — базис модуля А^.в, квадратичную форму ¡(х,у) = det(a;Л/l + уМ2) п ее дискриминант И. Если О < 0, то переходим на Шаг 4.1, если О > 0, то на Шаг 4.2.

Шаг 4.1 О < 0, поэтому /(х,у) — положительно определенная или отрицательно определенная форма. Для выяснения вопроса о представимости целого числа этой формой можно применить алгоритм приведения Гаусса (см., например, [16]).

Шаг 4.2 Б > 0, поэтому }{х,у) — неопределенная форма. В этом случае можно применить алгоритм из [24].

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

Алгоритм из [24] не полиномиален, т.к. он использует разложение некоторой квадратичной иррациональности в цепную дробь, которая является периодической с длиной периода / = 0(^/D\ogD).

В подразделе 2.1.5 приведены канонические матрицы классов подобия с характеристическим многочленом вида А2— р2к+1, р - простое число, к > 0. Обозначим число классов подобия матриц, имеющих характеристический многочлен А2 — р2к+1 через ЛГ(р).

Теорема 16. Если р - простое число, ЛТ(р) = £ и минимальное положительное решение уравнения Псллях2 —ру2 = ±1 не делится на р, то

дг(р2/с+1) = + ^ Пусть Ли- = ( ^ Л,- ) = ''' ~ пРедставители классов подобия для к = 0, причем можно считать, что с^ не делится на р. Тогда в качестве представителей (к + 1)£ классов подобия

моэ/сно взять матрицы Ак+\.ц+] = I к 3 ) > ^ = 0, ■ • •, к\] =

\ Р с] Р а] /

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

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

Теорема 17. Пусть А е Z[г]2х2 и det(AЕ - А) = (А - а)2. Тогда А

( OL T*i

подобна над Z[i] единственной матрице вида I g а ) , где г = 0 или

г = u + iv 6 Z[i], причем и > 0,v > 0.

Теорема 18. Пусть А е Z[г]2х2 и det(A£ —Л) = (А-а)(А-/3), а ^ /3, причем М0Э1СН0 считать, что f3 — a = m + in, где п > 0, а если п = 0, то т > 0. Тогда

1. Л подобна над Z[i] единственной матрице вида ( q ^ J , где. к

прииадлеэюит миоэ/сеству целочисленных точек квадрата с вершинами

0. + i)^, лео/еащих внутри пего и на смеоюных сторонах, содержащих точку -.

2. число классов подобия N(a, /3) определяется следующим образом:

если т = 0 (mod 2), п = 0 (mod 2), то N{a, /3) = + 2. если т + п = 1 (mod 2), mo ЛГ(а, (3) = "'2+f+3. если m s 1 (mod 2), n = 1 (mod 2), wo N(aJ3) = ™2+f+°. Результаты второй главы опубликованы в [1], [2], [11]. Глава 3 посвящена подобию целочисленных матриц третьего порядка. В разделе 3.1 рассмотрен случай характеристического многочлена вида (А — а)3. Над нолем Q матрица, имеющая такой характеристический многочлен, подобна одной из жордановых матриц

(а 0 0\ (а 0 0\ /а 1 0\

Jj(a)= 0 а 0 ,J2(a)= 0 а 1 , J3(a) = 0 а 1 . У 0 0 а у \ 0 0 a J \ 0 0 a J

Теорема 19. Пусть d(А) = (А - a)3, a е Z. Тогда

1. KQ(Ma)) = Kz(Ma)) = {Ае г3х3|Л ~ Ма)} = {Л(а)},

2. KQ(J2(a)) = U^z(Ra(d)), I<z(Ra(d)) = {Л e г3х3|Л ~ Ra(d)},

I a 0 0 \ Ra(d) = 0 a d , d> 1 V 0 0 а У

3. KQ(J3(a)) = UKz{Ra{a,b,r)), I<z(Ra(a,b,r)) = {Л € г3х3|Л ~ Ra(a,b,r)},

(a a r \

0 a b \,а,Ь>1,0<г<НОД{а,Ъ).

0 0 a J

В разделе 3.2 рассмотрен случай характеристического многочлена вида (А —а)(А —/З)2. Над полем Q матрица, имеющая такой характеристический

многочлен, подобна одной из жордановых матриц

fa 0 0 \ /а 0 0 \

Ма,0) = 0/3 0 I ,J2(a,/3) =00 1 . V 0 0 /3 / \ 0 0 /3 /

Теорема 20. Пусть d(А) = (Л - а)(А - /3)2,а,,5 € Z. ТогЛг

1. KQ(Ji(aJ3)) = U I<z(R».e(d)) = {A G Z3x3|A ~ i?«.3(d)},

/ а d 0 \

3(d) = I 0 /3 0 1. d = О шш d - положительный делитель |/3 — а|

V 0 0 /3 /

()<е равный |/3 — а|)

2. I<Q(J2{a,/3)) = и^До.зСаьаг.аз)), ^2(Да.3(аь а2, а3)) = {Л е

г3х3|Л ~ Яа.з(аьа2,а3)},

/о ai а2 \

i?Q■ ?(ai, а2,а3) = I 0 /3 аз ). где ai.a2, аз удовлетворяют условиям

V о о

7) oi =0, 0 < а2 < L^J. «з > 1.

Па) если |/3 — а\ нечетное, то

1 < ai < L^J, 0 < а2 < d, а3 > 1, где d =Н0Д{\/3 - а|, ai) lib) если |/3 — а| - четное, то

1) 1 < aj < - 1, 0 < а2 < d, а3 > 1.

2) а, = 1^1, ¡з > 1,

если /3 - а > 0, то < а2 <

если 13 - а <0, то -¡jjj < а2 <

г - остаток от деления а3 на а\.

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

/ а 0 0 \ матрице J(a,f3,~') = 0/3 0 .

V о 07/

Теорема 21. Пусть d{А) = (A-a)(A-/3)(A-7),a,/3,7 G Z,a < /3 < 7. Тогда KQ(J(a, (3,-/)) =\jKz{R0.g.1{a\,a2,a3)),

Kz(Ra,3.-y{ai,a2,a3)) = {Л e г3х3|Л ~ Д„..з,7(аь «2, аз)},

/ a ai a2 \

V 0 0 7 )

где ai.a2,a3 удовлетворяют условиям

I) а 1 = 0; 0 < а2 < L^J, 0 < а3 < L^J

Ла) cc/iu 7 — ¡3 - нечетное, то

1 < «1 < L^J» О < а2 < 7 - а, 0 < а3 < [^J

IIb) если 7 — ß - четное, то

1) 1 < oi < L^J> 0 < a2 < 7 - а, 0 < а3 < — 1

2) 1 < <ц < -Ifl < «2 < а3 =

Доказательства теорем 19, 20, 21 о канонических матрицах предоставляют полиномиальный алгоритм распознавания подобия.

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

В разделе 3.4 рассмотрен случай характеристического многочлена вида (X — a)(X2 + u\ + v), где A2+uA + v неприводимый многочлен. Над полем Q матрица А, имеющая такой характеристический многочлен, подобна мат' а 0 0

рице Фробсниуса F = 0 -u —v |. Над кольцом Z матрица А подобна

0

блочной матрице В = ^ д ^ ^, где аТ € 7?, А' € г2х2, причем характеристический многочлен матрицы А' равен х(-М = А2 + ыА + 1>. В Теореме 23 содержится критерий подобия таких матриц, который предоставляет алгоритм распознавания подобия. Доказано, что класс Кц{Е) разбивается на конечное число классов подобия матриц над Z.

Результаты третьей главы опубликованы в [3].

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

Теорема 24. Пусть А и В две п х п матрицы с целочисленным спектром, подобные над полем С}. Если жорданова форма обеих матриц не содержит клеток одинакового порядка для одного и того же собствеино-

т

го числа, то определитель /(у\,... ,ут) = произвольной мат-

¿=1

рицы из Аа.в является произведением линейных функций с целыми коэффициентами относительно переменных у\,..., ут.

Алгоритм.

Вход: Две матрицы А, В € гпх", имеющие целочисленный спектр и жорданова форма которых не содержит клеток одинакового порядка для одного и того же собственного числа.

Выход: Трансформирующая матрица Т, если А ~ В.

Шаг 1. Найти жорданову форму 3 матриц А и В и трансформирующие

матрицы Sa, Sb• Пусть tt порядок ¿-ort клетки, г = 1,... ,р, где р — число клеток.

Шаг 2. Вычислить матрицы Hj = SAGjSß1, j = 1,... , m, образующие базис Ма.в, где Gj — диагональная матрица, диагональ которой заполнена нулями и единицами, причем единицы расположены на местах с номерами

j-i з OTl + E и ДО J2 ti> 3 = • ■ • --Р-i ¿=i

Шаг 3. Найти Т\,..., Тш -- базис модуля Аа.в-

Шаг 4. Разложить матрицы Т; но базису Hj, j = l,...,m. Получим

m

Тг = Е ßjiHj, ßjt e Q. j=i

Шаг 5. Найти HOK знаменателей рациональных чисел ßji,i = 1 ,...,ш, которое обозначим через Д/. Затем найдем величины = НОД {ßjAj, г = 1 ,...,m}, 7ii = j = 1,..., m, а =

dctJ»^)'1''' (а~Ур- Для подобия матриц Л и В необходима и достаточна разрешимость в целых числах уравнения f(yi,...,y,n) =

m m

УПиУ' '' ■ (S УП1»У" = Если |a| ^ 1, то Л и В не подобны. В

! = 1 1 = 1

противном случае нужно выяснить, совместна ли в целых числах хотя бы одна из следующих 2Р систем линейных уравнений

Г m

| YL vnji = ±1> 3 =

Если все они несовместны в целых числах, то Л и В не подобны над Z, в противном случае пусть ?/?,..., - одно из решений. При этом А и В

m

подобны над Z, а матрица Т = yfTJ является трансформирующей.

! = 1

Все шаги данного алгоритма, кроме Шага 5, можно выполнить за полиномиальное время от п и размера максимального из коэффициентов матриц Л и В. На Шаге 5 приходится в худшем случае решать 2Р систем линейных уравнений (на самом деле, можно ограничиться рассмотрением 2/,_1 систем). Поэтому приведенный алгоритм является квазиполиномиальным.

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

В разделе 4.3 рассмотрен случай, когда геометрическая кратность каждого собственного числа матрицы Л равна 1. Основными результатами этого раздела являются следующая теорема и следствие из нее.

Теорема 28. Пусть матрица А S Znxn имеет характеристический

многочлен d(А) = (А — ai) • • • (Л — a„), где аь а2,.. -, ап е Z и Qi < а2 < ... < а„. Тогда А подобна некоторой верхие-треуголъиой матрице Т = (tij), у которой

tu = а,-, г = 1,... ,п

О < ff, f+i <

Qfi+i — а«

г = 1,..., п — 1

О < ti4+k < ai+k -a-t, i = 1,.. ■ , n - 1, fc = 2,..., n - i.

Следствие 11. Число классов подобия матриц, имеющих характеристический многочлен d{X) = (А — »1) • • ■ (А — а„), где а\ < а2 < ... < ап, конечно и не превосходит величины

п-1

П(

г=1

+ D

j-i> 2

аг).

Результаты четвертой главы опубликованы в [4].

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

В приложении приведены таблицы канонических матриц классов подобия над Ъ матриц второго порядка, имеющих неприводимые характеристические многочлены вида X2 — d м X2 — X — d для 1 < d < 101.

Работы автора по теме диссертации

Статьи в журналах, рекомендованных ВАК

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

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

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

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

Другие публикации

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

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

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

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

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

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

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

- К.: Отечество, 2008. - С. 106.

[10] Сидоров C.B. О необходимых условиях подобия матрице Фробе-ниуса над кольцом целых чисел //Материалы 8-й Международной конференции «Дискретные модели в теории управляющих систем», (Москва, 6-9 апреля 2009 г.), 2009. - С. 159-162.

[11] Сидоров C.B. О канонических представителях классов подобия матриц второго порядка над кольцом целых чисел //Материалы X Международного семинара «Дискретная математика и се приложения», (Москва, 1-6 февраля 2010 г.) / Под редакцией О. М. Касим-Заде. — М.: Изд-во механико-математического факультета МГУ, 2010. - С. 272-274.

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

- С. 32-35.

[13] Сидоров С.В. О подобии матрицы второго порядка и транспонированной к ней матрицы над кольцом целых чисел// Материалы XI-i'O Международного семинара «Дискретная математика и ее приложения», (Москва, 18-23 июня 2012), 2012. С. 270-272.

[14] Сидоров С.В. О подобии блочно-диагоиальных матриц над кольцом целых чисел // Материалы XVII Международной конференции «Проблемы теоретической кибернетики» (Казань, 10-20 июня 2014) / Под редакцией Ю. И. Журавлева. -- Казань: Отечество, 2014. - С. 264266.

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

Цитированная литература

[1G] Бухштаб А.А. Теория чисел. - М.: Просвещение, 196С.-384с.

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

[18] Саркисян Р.А. Проблема сопряэ/сенности для наборов целочисленных матриц Ц Мат. заметки. - 1979. - Т.25, вып.6. - С. 811-824.

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

[20] Appclgate Н., Onishi Н. The similarity problem for 3x3 inteyer matrices // Linear algebra and its applications. - 1982. - №42. - P. 159-147.

[21] Bchn A., Van der Merwe A. B. An algorithm version of the theorem by Latimer and MacDuffee for 2x2 inteyral matrices // Linear algebra and its applications. - 2002. - Vol.340. - P. 1-14.

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

[23] Latimer C.G., MacDuffee C.C. A correspondence between classes of ideals and classes of matrices // Annals Math. 1933. - Vol. 34. - P. 313-31G.

[24] Matthews K. The diophantine equation ax2 + bxy + cy1 = N,D = b2 -4ac > 0 /7 J. Theor. Nombrcs Bordeaux. 2002. - №14. - P. 257-270.

[25] Newman M. Integral matrices. - New York and London: Academic Press, 1972.

[2G] Taussky O. On the similarity transformation between an inteyral matrix with irreducible characteristic polynomial and its transpose /7 Math. Aimalcn - 19GG. - Vol. 166. - P. 60-63.