Вычисление собственных значений нормальных матриц специальной структуры и смежные вопросы теории матриц Абдикалыков Абдикожа Кожанасиридинович

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

Введение

Глава 1. Постановка задачи 11

1.1. Алгоритмы решения спектральной задачи для специальных матриц 11

1.2. Тёплицевы и ганкелевы матрицы 14

1.3. Предпосылки постановки теоретической задачи 22

Глава 2. Эффективные спектральные алгоритмы для некоторых специальных классов матриц 25

2.1. Спектральные алгоритмы для нормальных тёплицевых матриц 26

2.2. Спектральные алгоритмы для нормальных ганкелевых матриц 33

2.3. Спектральные алгоритмы для некоторых классов (T+H)-матриц 73

Глава 3. Унитарные автоморфизмы 89

3.1. Группа UAut90

3.2. Группа UAut 96

3.3. Группа UAut 108

3.4. Группа UAut119

3.5. Связь между группами унитарных автоморфизмов 126

3.6. Группа UAut 135

Заключение 172

Список литературы

• Тёплицевы и ганкелевы матрицы
• Предпосылки постановки теоретической задачи
• Спектральные алгоритмы для нормальных ганкелевых матриц
• Группа UAut

Введение к работе

Актуальность работы

Задачи на собственные значения являются одним из важнейших разделов вычислительной линейной алгебры. В данной работе исследуется задача нахождения всех собственных значений матрицы, называемая в дальнейшем для краткости спектральной задачей. В численной практике решения спектральной задачи для матриц не слишком высокого порядка наибольшей популярностью пользуется QR-алгоритм. В частности, в широко известной среде инженерных вычислений Matlab этот метод реализован стандартной функцией eig. Для эрмитовых (или, в вещественном случае, симметричных) матриц существует значительно более эффективная модификация QR-алгоритма, что привело к вопросу построения алгоритма такой же или сопоставимой эффективности для всего класса нормальных матриц. Кажется вполне естественным, что такой алгоритм должен существовать, поскольку нормальные матрицы обладают тем же набором хороших свойств, что и вещественные симметричные и комплексные эрмитовы матрицы, за исключением вещественности собственных значений, которая не играет особой роли.

Однако, несмотря на многие усилия, удовлетворительные результаты были до сих пор получены только для некоторых частных случаев. Например, в статье Calvetti D., Reichel L., Хи Н. (Linear Algebra Appl. 2015. Vol. 476. P. 197-232) предлагается метод решения спектральной задачи для унитарных матриц. Что касается нормальных матриц общего вида, то для них всё ещё не найдено метода, сравнимого по эффективности с симметричным QR-алгоритмом.

Таким образом, задача построения эффективного алгоритма решения спектральной задачи для всего класса нормальных матриц оказалась весьма сложной. Поэтому в диссертации рассматривается менее амбициозная задача, а именно разработка приёмов ускорения спектральных алгоритмов для нормальных матриц специальных типов, таких как тёплицевы, ганкелевы матрицы, а также некоторые типы матриц, представимых в виде суммы тёплицева и ганкелева слагаемых (так называемые (T+H)-матрицы).

Отметим, что, подобно QR-алгоритму, все предлагаемые в диссертации методы подразумевают хранение в памяти вычислительной машины всей матрицы в явном виде, требуя таким образом порядка п² ячеек памяти, где п — порядок матрицы, спектр которой мы ищем. Таким образом, данная задача рассматривается относительно матриц

умеренного порядка. Единственным исключением могут быть (T+H)-циркулянты и подобные им подмножества (T+H)-матриц, рассматриваемые в 3 главы 2: для них были выведены явные формулы вычисления спектра, которые затрагивают элементы только первой строки или только первого столбца. Мы называем (T+H)-циркулянтами матрицы, представимые в виде суммы (тёплицевого) циркулянта и ганкелевого циркулянта. Циркулянтами, в свою очередь, называются матрицы вида

т =

и

t

а ганкелевыми циркулянтами — матрицы вида

"П-1

h n-2 h n-2

ih h,2 h1 h0

h 1 h 0 h n-1

Н =

h3 h,2 h1

110 '<"n-1 '<"n-2

Мотивация теоретической части работы была почерпнута из статьи Wilkes D.M., Morgera S.D., Noor F., Hayes M.H. (IEEE Trans. Signal Processing. 1991. Vol. 39. № 9. P. 2146–2148). Основным результатом данной публикации являлось следующее утверждение: каждое из отображений

A i—)- Q*AQi

і = 1,2, 3,

где

Q1 = —=(I_n + iP_n), Q2 = —j=(I_n — iPn),
v 2 V2

4?3 = ^_((1 + ^г)1п + (1 ^— 1)Pn)-

2 переводит множество эрмитовых тёплицевых матриц в множество вещественных (T+H)-матриц. Здесь Р_п — так называемая перъединичная матрица, содержащая единицы на побочной диагонали и нули вне неё. Как видим, эти преобразования переводят одно подмножество комплексных (T+H)-матриц порядка п (эрмитовы тёплицевы матрицы) в другое (вещественные (T+H)-матрицы) путём унитарного

подобия, причём, как можно показать, эти подобия овеществляют любую центроэрмитову матрицу. Поскольку переход к вещественной арифметике позволяет быстрее проводить машинные вычисления, возникает логичный вопрос: какие ещё унитарные подобия могут облегчить решение спектральной задачи для тёплицевых, ганкелевых или (T+H)-матриц? В связи с этим вопросом исследуются группы унитарных автоморфизмов UAut(T_ra), XJAut(H_n), UAut(TH_n), где

и Є 1)Ат{1_п) -<=> у А Є 1_п и AU Є 1_п,

U Є UAut(n„j Ф> у А Є Н_п и AU Є h_n,

U є UAut(ТН_п) Ф> \/А є ТН_п U* AU є ТН_п.

Здесь Т_п, Н_п, ТН_п — множества тёплицевых, ганкелевых и (T+H)-матриц порядка п соответственно, U — унитарная матрица. Первые две группы (UAut(T_ra) и UAut(H_n)) были описаны Х.Д. Икрамовым. В диссертации анализ структуры этих групп, во многом отличающийся от рассуждений Х.Д. Икрамова, дан с целью упростить понимание значительно более сложного анализа группы UAut(ТН_п). Как выяснилось, матрицы Q_i, і = 1,2,3, входят в UAut(T_ff_ra), то есть, осуществляют автоморфизм пространства (T+H)-матриц. В диссертации дано исчерпывающее описание группы UAut(T_ff_ra). Кроме того, в диссертации приведён анализ групп автоморфизмов, действующих в пространствах тёплицевых и ганкелевых матриц посредством конгруэнции:

U Є UAut_c(T_ra) Ф> \/А єТ_п U AU є Т_п,

U є UAut_c(_ff_ra) Ф> \/А є Н_п U AU є Н_п.

Поскольку унитарные конгруэнции являются частным случаем псевдоподобий (А \—> U~¹AU), то такие автоморфизмы могут быть использованы для упрощения процедуры нахождения псевдоспектра.

Цель работы

Целями данной работы являются построение эффективных спектральных алгоритмов для нормальных матриц специального вида, а также получение описаний групп унитарных автоморфизмов множеств тёплицевых, ганкелевых и (T+H)-матриц, осуществляемых путём подобий и конгруэнций.

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

простой структуры. Аналогично, унитарные автоморфизмы, действующие посредством конгруэнций, могут быть использованы при вычислении псевдособственных значений, определяемых так же, как в статье George A., Ikramov Kh.D., Matushkina E.V., Tang W.-P. (SIAM J. Matrix Anal. Appl. 1995. Vol. 16. № 4. P. 1107–1126).

Новые научные результаты, выносимые на защиту

1. Получены эффективные алгоритмы решения спектральной задачи для
нормальных тёплицевых, нормальных ганкелевых матриц и некоторых алгебр,
состоящих из (T+H)-матриц.

1. Получено описание групп унитарных автоморфизмов, действующих посредством конгруэнций в пространствах тёплицевых и ганкелевых матриц.

2. Дано объяснение связи между полученными группами.

4. Получено описание группы унитарных автоморфизмов пространства (T+H)-
матриц, осуществляемых путём подобия.

Научная новизна работы, основные идеи

Классификация нормальных тёплицевых и нормальных ганкелевых матриц была получена не так давно, поэтому алгоритмы для таких матриц, использующие особенности их структуры, действительно новы. Для повышения эффективности алгоритмов использовались такие идеи, как переход к вещественному случаю, разбиение задачи порядка n на две или более задач меньшего порядка, использование быстрого дискретного преобразования Фурье, диагонализация (или приведение к квазидиагональному виду с малыми порядками диагональных блоков) матриц из специальных алгебр (T+H)-матриц. Исследования автоморфизмов матриц специальной структуры, в особенности (T+H)-матриц, впервые привязываются к спектральной задаче. Также впервые были получены описания группы автоморфизмов (T+H)-матриц, осуществляемых с помощью унитарных подобий.

Практическая значимость работы

Разработаны методы для нахождения собственных значений нормальных ганкелевых, нормальных тёплицевых и некоторых классов (T+H)-матриц. Все алгоритмы реализованы в виде функций Matlab. Они успешно используют специальную структуру матриц и существенно превосходят по скорости стандартные спектральные алгоритмы.

Личный вклад автора

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

Соответствие диссертации паспорту научной специальности

Содержание и результаты работы соответствуют паспорту специальности 01.01.07, а именно соответствуют областям исследований:

1. Создание алгоритмов численного решения задач алгебры, типичных для приложений математики к различным областям науки и техники.

2. Разработка теории численных методов, анализ и обоснование алгоритмов, вопросы повышения их эффективности.

3. Особенности численных методов и связанных с ними программных комплексов,
отражающие рост производительности современных ЭВМ и способствующие
повышению эффективности вычислений.

Апробация работы

Основные результаты диссертации докладывались на следующих семинарах и конференциях:

научный семинар кафедры вычислительных методов факультета ВМК МГУ под руководством профессора А. В. Гулина;

семинар “Матричные методы и вычисления”; научный руководитель — чл.-корр. РАН Е. Е. Тыртышников; Институт вычислительной математики РАН;

международная конференция “Matrix Methods in Mathematics and Applications”, Москва, август 2015 г.

Публикации

По теме диссертации опубликовано 10 научных работ, из них 8 в следующих журналах из списка ВАК: Вестник Московского университета, серия 15, Вычислительная математика и кибернетика; Журнал вычислительной математики и математической физики; Записки научных семинаров ПОМИ; Доклады РАН; Сибирский журнал вычислительной математики.

Структура и объем работы

Тёплицевы и ганкелевы матрицы

Очевидно, что для любой тёплицевой матрицы Т матрица Н = ТР будет являться ганкелевой, так как Н будет состоять из тех же столбцов, что и Т, но переставленных в обратном порядке. То же самое можно сказать и про пары циркулянт — ганкелев циркулянт, косой циркулянт — ганкелев косой циркулянт, 0-циркулянт — ганкелев 0-циркулянт. Связанные таким соотношением матрицы Т и Н мы будем называть ассоциированными.

К слову, матрица РТ будет также являться ганкелевой, так как домножение на перъединичную матрицу слева располагает в обратном порядке строки исходной матрицы. Если же домножать на Р и справа, и слева, то матрица отразится и горизонтально, и вертикально, что приведёт к отражению всех элементов матрицы относительно центра. Это позволяет определить центросимметричные матрицы простым равенством: А — центросимметричная матрица, если А = РАР. При замене знака на противоположный получаем определение косоцентросимметричной матрицы: — косоцентросимметричная матрица, если

Нетрудно видеть, что как тёплицевы, так и ганкелевы матрицы порядка образуют линейные подпространства в , где — множество всех комплексных матриц порядка . Назовём их и соответственно. Таким образом, можно ввести подпространство матриц, представимых в виде суммы тёплицевой и ганкелевой матриц. Это множество называется множеством (T+H)-матриц и будет обозначаться в дальнейшем . Необходимо заметить, что и не образуют прямой суммы, так как их пересечение имеет ненулевую размерность. Из этого следует, что обе компоненты в разложении (T+H)-матрицы на тёплицево и ганкелево слагаемое определяются неоднозначно.

В свою очередь, циркулянты и ганкелевы циркулянты образуют линейные подпространства размерности в и соответственно. Аналогично понятию (T+H)-матрицы вводятся понятия (T+H)-циркулянта и косого (T+H)-циркулянта.

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

Существуют критерии нормальности для тёплицевых и ганкелевых матриц, выведенные Х.Д. Икрамовым и В.Н. Чугуновым в [37] и [38] соответственно.

Теорема 1.1. Тёплицева матрица является нормальной тогда и только тогда, когда принадлежит одному из следующих классов: Класс 1.1. — матрица вида + , где , C, — эрмитова тёплицева матрица. Класс 1.2. представляет собой -циркулянт для некоторого числа C, = 1.

Перед формулировкой классификации нормальных ганкелевых матриц необходимо ввести понятие -преобразования. Пусть — некоторая вещественная невырожденная матрица второго порядка, 1 и 2 — вещественная и мнимая части алгебраического разложения комплексной матрицы . Тогда под действием -преобразования матрица заменяется матрицей = (111+212)+(121+222).

Теорема 1.2. Ганкелева матрица является нормальной тогда и только тогда, когда принадлежит одному из следующих классов: Класс 2.1. Вещественные ганкелевы матрицы и произвольные их комплексные кратные. Класс 2.2. Матрицы вида + 1, , C, где 1 — произвольная вещественная центросимметричная ганкелева матрица. Класс 2.3. Блочно-диагональные матрицы вида аН\ 0 (ЗЩ, а, /З Є С; где Н\ — верхнетреугольная вещественная ганкелева матрица порядка к (0 к п), а Н2 — нижнетреуголъная вещественная ганкелева матрица порядка I = п — к. При этом мы называем Н\ и Н2 соответственно верхнетреугольной и нижнетреуголъной ганкелевыми матрицами, если {H{\ij = 0 при і + j к + \ и {H2}ij = О при і + j I + 1.

Класс 2.4- Матрицы вида аН\ + /ЗН , а, /З Є С; где Ні — невырожденная вещественная верхнетреугольная (или нижнетреуголъная) ганкелева матрица.

Класс 2.5. Ганкелевы матрицы, для которых ассоциированные тёплицевы матрицы получаются V-преобразованием множества унитарных ф-циркулянтов (\ф\ = 1,ф ф ±1) и их скалярных кратных.

Класс 2.6. Ганкелевы матрицы, для которых ассоциированные тёплицевы матрицы получаются V-преобразованием матриц вида Т = Т\ + ІТ2, полученных одним из следующих способов: а) Ті — произвольный вещественный невырожденный -циркулянт, Т2 — произвольное вещественное кратное матрицы Т{ ; б) Т\ и Tj — вещественные -циркулянты, удовлетворяющие условию TiTj = О.

Предпосылки постановки теоретической задачи

Получаем ту же ситуацию, что и для класса 2.6а: матрицы Hi и Н2 обязаны иметь одинаковый набор собственных векторов. Однако есть одно существенное различие: если в случае класса 2.6а мы получили некоторый собственный вектор матрицы Н\, то он гарантированно будет собственным вектором и для і . Для класса 2.6б такой гарантии нет. Поэтому предлагаются следующие два немного различающихся алгоритма.

Класс 2.6а. Сначала с помощью стандартной функции eig находятся собственные значения Xj вещественной матрицы Н\. Для каждого j вычисляем величину 6 Xj где 5 — коэффициент в равенстве Н\іІ2 = 51п. Нетрудно проверить, что fij — собственное значение i 2, отвечающее тому же собственному вектору, что и собственное значение Xj матрицы Н\.

Класс 2.6б. С помощью стандартной функции eig находятся собственные значения матриц Н\ и В. . Обозначим их А - и //соответственно. Сконструируем перестановки Xj и fij этих двух множеств так, чтобы выполнялись равенства Xjfij = 0 для любого j. Этого можно добиться как сортировкой массивов А и // в противоположных порядках, так и простым перебором обоих массивов методом двух указателей.

Конечная часть снова общая для двух классов. После нахождения Xj и \ij мы можем выписать спектр Н. Он будет состоять из чисел (vnXj + V21 flj) + i{v\2Xj + V22 j) В результате, чтобы решить исходную задачу для Н, необходимо найти собственно матрицы Hi и Н2 и коэффициенты матрицы У, осуществляющей нужное -преобразование.

Для этого перейдём к ассоциированным тёплицевым матрицам. Заметим, что в любом случае Ті — вещественный -циркулянт, Т2 — вещественный _-циркулянт, поскольку для любого -циркулянта А обратная матрица А 1 (если существует) также является -циркулянтом, а транспонированная матрица Ат является _1-циркулянтом. Таким образом, обе матрицы Т\ и Т2 можно представить в виде линейной комбинации -циркулянта и _1-циркулянта для некоторого вещественного . Понятно, что благодаря условию \V\ Ф 0 можно говорить об обратном -преобразовании и, значит, можно и наоборот матрицы Т\ и Т2 представить в виде линейной комбинации Т\ и Ті. Попробуем это использовать для нахождения .

Пусть а,(3 — такие вещественные числа, что аТ\ + /ЗТ2 — -циркулянт. Введём такие обозначения: pj — транспонированная первая строка матрицы Tj без первого элемента, qj — записанный в обратном порядке первый столбец матрицы Tj без первого элемента, j = 1,2. Тогда, пользуясь собственно определением -циркулянта, данное условие можно переписать следующим образом: (1Ц\ + /3 2 = (сфі + (Зр2) Преобразуя, получаем a(qi — pi) + (3(q2 — 2) = О, то есть задача сводится к тому, чтобы найти такое , что векторы q\ — pi и Я.2 — ,Р2 линейно зависимы. При таком должны быть линейно зависимы все пары двумерных векторов [qij — q,P\j-, qik о,Р\к) и j — 2j, 2k — 2k) ,, = l,2,...,. Получаем такие уравнения:

Надо заметить, что коэффиценты при 2 и есть не что иное, как миноры А?к и А ,, определённые в [38]; там же доказывается, что равенство А к = ACL обязано выполняться для всех нормальных ганкелевых матриц. Следовательно, все полученные уравнения с не равным нулю старшим коэффициентом имеют одни и те же два взаимно обратных корня, причём оба нам будут подходить. Так мы находим .

Теперь уже можно находить начальные матрицы і и 2. Разберём основной случай, когда і не является ни -циркулянтом, ни _1-циркулянтом. Тогда ц 0, 2і 7 0, и, не ограничивая общности, можно считать, что і = і + і. Здесь матрица заменяется на матрицу «21 а матрицы T\ и T i — на V\\T\ и V21T2 соответственно с сохранением всех полученных соотношений.

Внедиагональные элементы Т\ и Т2 находятся посредством решения п — 1 систем из двух линейных уравнений от двух переменных. Если обозначить первые строки матриц Ті и Т2 как

Здесь было использовано только то, что Ті — -циркулянт, а Т2 — _1-циркулянт. Для нахождения же диагональных элементов t 0 и о надо использовать тот факт, что все внедиагональные элементы матрицы Т{Г равны нулю, так как TiTj = 61п для некоторого вещественного д, причём 6 ф 0 соответствует классу 2.6а, 5 = 0 — классу 2.6б. Кроме того, сумма t 0+tQ равна диагональному элементу матрицы Ті. Снова получается система из двух линейных уравнений. Таким образом, найдены искомые матрицы Ті и Ті. Чтобы найти оставшиеся коэффициенты v\i и 22 (мы положили г п = г 2і = 1), нужно решить уравнение

Спектральные алгоритмы для нормальных ганкелевых матриц

Данная глава содержит решение задачи описания групп унитарных автоморфизмов UAut(), UAut(), UAut(), UAut() и UAut(), определение которых дано в (1.7). Фактически каждый параграф данной главы состоит из формулировки теоремы, описывающей состав соответствующего множества, и последующего доказательства.

Группам автоморфизмов UAut() и UAut(), осуществляемых путём подобий, посвящены 1 и 2, основанные на статьях [46, 47] Х. Д. Икрамова. Автоморфизмы, осуществляемые путём конгруэнций, исследуются в 3 и 4, содержание которых построено на основе совместных статей [7, 8] автора с Икрамовым Х. Д. и Чугуновым В. Н. В 5 предлагается объяснение схожести структур двух пар полученных множеств. В последнем 6 содержится решение задачи об унитарных автоморфизмах пространства (T+H)-матриц, осуществляемых путём подобия. В основу этого параграфа легли статьи [9, 10] автора и совместная статья [11] автора с Икрамовым Х. Д. и Чугуновым В. Н.

По определению унитарная матрица U Є Мп принадлежит множеству UAut(Tn) в том и только том случае, если У А Є Тп U AU Є Тп. Докажем теорему, описывающую состав множества UAut(Tn). Теорема 3.1. Все матрицы U Є UAut(Tn) представимы в одном из следующих двух видов: а) U = а diag (1, є, є2,..., sn l); б) U = аРп diag (1, є, є2,..., en l). В обоих случаях а и є — комплексные числа, равные по модулю единице. Доказательство Докажем эту теорему методом индукции по п. Пусть п = 2. Тогда для включения U Є UAut(Tn) необходимо и достаточно, чтобы подобие с трансформирующей матрицей U сохраняло тёплицеву структуру трёх матриц, составляющих базис Ті: 0 11 /1 о\ т /00 4=1 I , 2= I =1 \о о/ \о l/ \l о

Учитывая очевидные равенства U l2U = /2, U ATU = (U AU) , можем утверждать, что достаточно того, чтобы тёплицевой была матрица В = U AU. Таким образом, должно выполняться равенство Ъц = &22, или, что то же самое, равенство

Однако матрица U унитарна, следовательно, её строки (равно как и столбцы), если рассматривать их как комплексные векторы, должны образовывать ортогональный базис пространства С2 в смысле стандартного скалярного произведения. В частности, первая строка должна быть ортогональна второй: и\\Щ\ + М12Й22 = 0. (3.2) Из (3.1) и (3.2) следует, что WllM2l = U\2ll22 = 0. (3.3) Если гі2і = 0, то ІІЦ = 1 ввиду унитарности матрицы U, а значит, и iii2 = 0, ІІ22І = 1. В итоге получаем нужное представление U = (т diag (1, є), где (7 = МЦ, = Щї/Щі. При ІІ2І ф 0 видим из (3.3), что Щ\ = 0, it2i = 1, а значит, и м22 = 0, ІІІ2І = 1. В этом случае U = (тР2 diag (1, є), где (т = ІІ2І, є = U\2/u2\. Базис индукции доказан. Перейдём к шагу индукции. Предположим, что теорема доказана для всех порядков, меньших, чем п 3. Обозначим первую и последнюю строки матрицы U Є UAut(Tn) как (скі,..., ап) и (/Зі,..., (Зп). Подобно случаю п = 2 положим А = Е\п, то есть, А — тёплицева матрица, единственный ненулевой элемент которой находится в позиции (1,п) и равен единице. Матрица В = U AU по-прежнему обязана быть тёплицевой. При этом нетрудно видеть, что

Пусть сначала 1 = 0, тогда обязательно 1 = 0. Следовательно, первый столбец матрицы является нулевым, и является строго верхнетреугольной матрицей ввиду своей тёплицевости. Нетрудно убедиться, что если 2 = . . . = к-1 =0, k ф 0, то ранг матрицы окажется равным + 1 — . При этом rg = rg = 1, поскольку подобные матрицы имеют одинаковые ранги. Тем самым, п — единственный ненулевой элемент в последней строке матрицы . Но тогда \п\ = 1 и все внедиагональные элементы последнего столбца также равны нулю.

Выходит, что в матрице отличен от нуля только элемент, находящийся в позиции (1,). Тогда из равенств п = п = 0, 2, получаем 2 = . . . = VJ = 0. Поэтому і = 1 и это единственный ненулевой элемент в первом столбце матрицы . В итоге имеет вид = \i 0 n-2 пп, где n-2 — унитарная матрица порядка — 2. Перейдём ко второму случаю \ = 0. Если предположить, что і = 0, то матрица будет строго верхнетреугольной и строго нижнетреугольной одновременно, то есть, нулевой, что невозможно, так как rg = 1. Поэтому і ф 0.

Рассуждая аналогично тому, как это делалось выше, выводим, что на границе матрицы находятся только два ненулевых элемента ап и /Зі. Здесь и далее под границей матрицы подразумевается совокупность элементов первой и последней строк и первого и последнего столбцов. Поэтому матрица U представима в виде U = Рп (ип\ 0 Un-2 0 It In), где Un-2 — также унитарная матрица порядка п — 2.

Выясним, как должна выглядеть матрица Un-2. Не ограничивая общности, разберём только первый случай, поскольку домножение на перъединичную матрицу не выводит матрицу из рассматриваемой группы автоморфизмов: если U AU Є Тп, то и (UPn) A(UPn) = Pn(U AU)Pn Є Тп, так как при отражении своих элементов относительно центра тёплицева матрица просто транспонируется и остаётся тёплицевой. Соответственно, для второго случая достаточно домножить полученный ответ Un-2 на Рп-2 слева. Итак, U = Щ\ 0 Un-2 0 ипп Є UAut(Tn).

Пусть А — произвольная матрица из Тп, В = U AU. Введём матрицы Ап_2 и Вп_2 — центральные главные подматрицы порядка п — 2 для А и В соответственно. Нетрудно убедиться, что Вп_2 = U _2An_2Un-2, где Ап_2 может принимать любое значение из Тп_2. Таким образом, Un-2 Є UAut(Tn_2). При этом, по предположению индукции, матрица Un-2 должна иметь один из двух видов, указанных в условии теоремы

Группа UAut

Ясно, что равенства (3.60) суть необходимые условия для включения U Є \J Aut(ТНп). Однако Это верно, так как можно показать, что эти же равенства являются достаточными условиями. Понятно, что U Є XJA\it(THn) тогда и только тогда, когда U XU Є ТНп для всех матриц X, относящихся хотя бы к одному из следующих четырёх классов: 1) X = Е\р + і?2,р-і + + Epi, р = 1,... ,п; 2) X = Епр + En_\iP+\ + ... + Ерп, р = 1,..., п; 3) X = Е\р + Е2,р+1 + ... + Еп_р \іП, р = 1,..., п; 4) X = Епр + En_hp_i + ... + En_p+hh р = 1,..., п.любую (T+H)-матрицу можно представить в виде линейной комбинации указанных матриц, причём первые два матричные множества соответствуют ганкелевым компонентам (T+H)-матриц, а два последних множества — их тёплицевым компонентам. (Кроме того, стоит отметить, что данная система избыточна, то есть не является базисом ТНп, так как dim ТНп = 4п — 4, в то время как в четырёх выписанных классах содержится 4п матриц.) Нетрудно видеть, что для матрицы X первого класса матрица РпХ попадает в четвёртый класс, матрица ХРп — в третий, а матрица РпХРп — во второй. При этом выполнение (3.60) соответствует включению U XU Є ТНп для всех матриц X из первого класса. Ввиду центросимметричности матрицы U (или её косоцентросимметричности) имеем U (APn)U = ±U AU Рп, U (PnA)U = ±РП U AU. Следовательно, (3.60) является необходимым и достаточным условием для включения U Є UAut(Ti/n), поскольку умножение на перъединичную матрицу слева или справа не выводит матрицу из множества ТНп.

Запись (3.60) можно упростить. Пусть S — трёхдиагональная тёплицева матрица с нулём на главной диагонали и единицами на двух соседних диагоналях, а R — (вещественная) нижнетреугольная тёплицева матрица с первым столбцом (гі,Г2? irn)T. Для таких R и S левая часть соотношения (3.60) равна элементу матрицы US, стоящему в позиции (j,k), а правая — элементу матрицы RU в той же позиции. Таким образом, это соотношение допускает следующую эквивалентную формулировку:

Унитарная матрица U, для которой \u\2\2, + міз2 + ііі;П-і2 0, тогда и только тогда принадлежит множеству XJA\it(THn), когда существует такая нижнетреугольная вещественная тёплицева матрица R, что матрицы RU и US совпадают всюду, кроме, быть может, первого и последнего столбцов. Другими словами, {RU}jk = {US}jk для j = 1,... ,п и к = 2,..., п — 1.

Полученное утверждение можно улучшить. Все столбцы матрицы RU — US, кроме первого и последнего, нулевые; следовательно, то же самое можно сказать про матрицу Е = U (RU — US) = U RU — 5. Однако E Є ТНП: так как R и 5 — тёплицевы, а, следовательно, являются и (Т+Н)-матрицами. Снова воспользовавшись правилом ромба, получаем, что Е = ацЕц + ы\пЕ\п + OLniEni + (ХппЕпп для каких-то комплексных «и, аы, anh апп. Тем самым, в матрице Е ненулевыми могут быть только угловые элементы. Например, {Е}2і = {Е}і2 + {і?}з2 — {Е}23 = 0.

Итак, U RU = S + Е. Поэтому (S + Е) = S + Е = (U RU) = U RTU, откуда выводим U (R + RT)U = 2S + Е + Е и U (R — RT)U = Е — Е . Заметим, что матрица R + RT — центросимметрична; значит, центросимметрична и матрица 25 + Е + Е . Это верно, так как матрицы U и U одновременно центросимметричны или косоцентросимметричны. Те же соображения применимы и к матрице R — RT: она косоцентросимметрична; значит, косоцентросимметрична и матрица Е — Е . Получаем следующие равенства: «11 + «И = Сїпп + Unni «In + Unl = OLni + «In, an — скп = —{pLnn — ann), ain — ani = —{ani — a in). Решения данной системы имеют вид an = ск, апп = а: ain = р: c ni = Q: гДе p,q ЄШ. Следовательно, лемма 3.4 доказана. Доказательство теоремы для п 3