Журнал вычислительной математики и математической физики, 2020, T. 60, № 10, стр. 1656-1663

1. ВВЕДЕНИЕ

Мы называем комплексные $n \times n$-матрицы $A$ и $B$ конгруэнтными, если

для некоторой невырожденной матрицы $S$. (Другие используемые термины: $A$ и $B$ эрмитово конгруэнтны, или $ * $-конгруэнтны.) Нас интересует возможность проверить наличие или отсутствие конгруэнтности между $A$ и $B$ посредством рационального или почти рационального вычисления. Рациональным мы называем конечный алгоритм, использующий лишь арифметические операции. Если дополнительно допускается вычисление конечного числа квадратичных радикалов, то мы говорим о почти рациональном алгоритме. Сложность задачи о конгруэнтности состоит именно в требовании рациональности алгоритма; в противном случае ее можно было бы решить, сличая (не вычисляемые рационально) канонические формы матриц $A$ и $B$ относительно конгруэнций.

В настоящее время не известен рациональный алгоритм, проверяющий конгруэнтность матриц $A$ и $B$ общего вида. Не известно даже, существует ли вообще такой алгоритм. Однако, если $A$ и $B$ принадлежат тому или иному классу специальных матриц, то рациональная проверка конгруэнтности может оказаться возможной. Пусть, например, $A$ и $B$ – эрмитовы матрицы. Согласно классическому критерию, $A$ и $B$ конгруэнтны тогда и только тогда, когда имеют одинаковые индексы инерции (положительный и отрицательный). Существует несколько рациональных способов вычисления индексов инерции эрмитовой матрицы. Можно, например, построить ее характеристический многочлен и затем, пользуясь теоремой Штурма, определить число его положительных и отрицательных корней.

Другой пример – унитарные матрицы $A$ и $B$. В [1] показано, что конгруэнтность таких $A$ и $B$ равносильна их подобию. Для подобия же унитарных (и, более общо, диагонализуемых) матриц достаточно совпадения их характеристических многочленов. Процедура вычисления характеристического многочлена $n \times n$-матрицы требует лишь $O({{n}^{3}})$ арифметических операций.

Эрмитовы и унитарные матрицы суть подмножества гораздо более широкого класса нормальных матриц. Рационального алгоритма проверки конгруэнтности для произвольных матриц этого класса пока не найдено. В данной статье мы делаем попытку предложить такой алгоритм. Одно ограничение все же остается: мы требуем, чтобы $A$ и $B$ были невырожденными матрицами. Существует несколько простых способов выделения ядра вырожденной матрицы. Однако, если требуется сохранить нормальность, в эти способы нужно ввести возможность извлечения квадратных корней. Хотелось бы избежать этого с тем, чтобы сохранить чисто рациональный характер алгоритма.

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

2. ЮНИТОИДЫ И НОРМАЛЬНЫЕ МАТРИЦЫ

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

является юнитоидом. Действительно, $A$ может быть представлена в виде суммы Первое слагаемое этой суммы есть симметричная матрица $(A + {{A}^{ \top }}){\text{/}}2$, а второе — кососимметричная матрица $(A - {{A}^{{\text{т}}}}){\text{/}}2$. Более того, матрица $(A + {{A}^{{\text{т}}}}){\text{/}}2$ положительно определена, т.е. $A$ есть аккретивная матрица. Известно (см., например, [2]), что все аккретивные матрицы суть юнитоиды.

Пусть $D$ – диагональная форма юнитоида $A$. Выполняя, если требуется, дополнительную конгруэнцию, можно сделать модули ненулевых диагональных элементов ${{d}_{{ii}}}$ равными единице. Эта улучшенная диагональная матрица считается канонической формой $A$ относительно конгруэнций. Она определяется следующими параметрами: рангом $r$ и аргументами ${{\theta }_{1}},\; \ldots ,\;{{\theta }_{r}}$ ненулевых диагональных элементов. Последние называются каноническими углами матрицы $A$. Условимся выбирать их в интервале $( - \pi ,\pi ]$.

Нормальная матрица $A$ приводима к диагональному виду посредством унитарного подобия, являющегося заодно (унитарной) конгруэнцией. Диагональные элементы полученной диагональной формы суть собственные значения ${{\lambda }_{1}},\; \ldots ,\;{{\lambda }_{n}}$ матрицы $A$. По предположению, все они отличны от нуля. Таким образом, канонические углы нормальной матрицы – это аргументы ее собственных значений.

Из сказанного следует, что для проверки конгруэнтности (невырожденных) нормальных матриц $A$ и $B$ достаточно сравнить их канонические углы. При этом вычислять сами углы нет необходимости, нужно лишь убедиться в их совпадении или различии. Можно, например, использовать то обстоятельство, что числа ${{e}^{{iarg{{\lambda }_{j}}}}}$, $1 \leqslant j \leqslant n$, суть собственные значения унитарной матрицы ${{U}_{A}}$ из полярного разложения матрицы $A$:

Поэтому конгруэнтность матриц $A$ и $B$ равносильна подобию унитарных матриц ${{U}_{A}}$ и ${{U}_{B}}$ из их полярных разложений.

Дефект этого рассуждения состоит в том, что полярное разложение нормальной матрицы в общем случае нельзя вычислить даже в радикалах [3], не говоря уже о рациональном процессе. Конечно, вместо самой матрицы ${{U}_{A}}$ достаточно было бы найти ее характеристический многочлен. Однако не известен рациональный алгоритм вычисления этого многочлена непосредственно по матрице $A$, и сама возможность такого (рационального) вычисления сомнительна.

В отличие от ${{U}_{A}}$, матрицу $U_{A}^{2}$ вычислить несложно. Напомним, что сомножители полярного разложения (2) нормальной матрицы $A$ перестановочны. Отсюда выводим

Рационально вычисляемая матрица ${{A}^{{ - * }}}A$ называется коквадратом матрицы $A$.

Поскольку для конгруэнтных матриц $A$ и $B$ унитарные матрицы ${{U}_{A}}$ и ${{U}_{B}}$ подобны, то должны быть подобны и коквадраты $U_{A}^{2}$ и $U_{B}^{2}$. К сожалению, обратное неверно: из подобия коквадратов не следует конгруэнтности $A$ и $B$. Пусть, например, $A$ и $B$ – (невырожденные) эрмитовы матрицы. Тогда

Однако $A$ и $B$ не будут конгруэнтны, если их индексы инерции различны.

Итак, подобие коквадратов – необходимое, хотя и не достаточное условие конгруэнтности $A$ и $B$. Поскольку оно проверяется рациональным и несложным способом, исследование конгруэнтности разумно начинать с него.

Если, несмотря на подобие коквадратов, $A$ и $B$ не конгруэнтны, это свидетельствует о наличии у них канонических углов ${{\theta }_{A}}$ и ${{\theta }_{B}}$, отличающихся друг от друга на $\pi $. Соответствующие собственные значения ${{\lambda }_{A}} = {{r}_{A}}{{e}^{{i{{\theta }_{A}}}}}$ и ${{\lambda }_{B}} = {{r}_{B}}{{e}^{{i{{\theta }_{B}}}}}$ порождают одно и то же собственное значение коквадрата ${{e}^{{i2{{\theta }_{A}}}}} = {{e}^{{i2{{\theta }_{B}}}}}$.

Наш алгоритм для проверки конгруэнтности опирается на два простых следствия из интерпретации чисел $arg{{\lambda }_{i}}$ как канонических углов нормальной матрицы.

Следствие 1. Пусть нормальные матрицы $A$ и $B$ имеют разное число собственных значений в некотором секторе комплексной плоскости. Тогда $A$ и $B$ не могут быть конгруэнтны.

Следствие 2. Рассмотрим пару симметричных секторов

и Если для нормальных матриц $A$ и $B$ разность количеств собственных значений в этих двух секторах различна, то $A$ и $B$ не могут быть конгруэнтны.

3. ТЁПЛИЦЕВО РАЗЛОЖЕНИЕ

Напомним, что тёплицевым (или эрмитовым) разложением квадратной комплексной матрицы $A$ называется ее представление в виде

Эрмитовы матрицы $B$ и $C$ в этом разложении однозначно определены:

Тёплицево разложение нормальной матрицы $A$ характеризуется следующим свойством.

Предложение 1. Квадратная матрица $A$ нормальна, если и только если матрицы $B$ и $C$ в ее тёплицевом разложении перестановочны:

Выполним унитарное подобие, приводящее $A$ к диагональному виду:

Числа ${{\lambda }_{j}} = {{\beta }_{j}} + i{{\gamma }_{j}}$, $j = 1,\;2,\; \ldots ,\;n$, суть собственные значения матрицы $A$. Матрица $U$ приводит к диагональному виду и каждую из матриц $B$ и $C$: Отсюда выводим

Предложение 2. Собственные значения матрицы $B(C)$ суть вещественные (мнимые) части собственных значений нормальной матрицы $A$.

В свою очередь, из предложений 1 и 2 вытекает

Предложение 3. Собственными значениями эрмитовой матрицы $\xi B + \eta C$ $(\xi ,\eta \in {\mathbf{R}})$ являются вещественные числа $\xi {{\beta }_{j}} + \eta {{\gamma }_{j}}$, ($j = 1,\;2,\; \ldots ,\;n$).

Количества положительных, отрицательных и нулевых собственных значений эрмитовой матрицы $H$ (т.е. индексы инерции этой матрицы) будем обозначать символами ${{n}_{ + }}(H)$, ${{n}_{ - }}(H)$ и ${{n}_{0}}(H)$.

Применяя предложение 2 к разложению (3) нормальной матрицы $A$, немедленно получаем:

Теорема 1. Индексы ${{n}_{ + }}(B)$ и ${{n}_{ - }}(B)$ указывают число собственных значений матрицы $A$, находящихся соответственно в полуплоскостях $\operatorname{Re} z > 0$ и $\operatorname{Re} z < 0$. Если вместо открытых полуплоскостей говорить о замкнутых полуплоскостях $\operatorname{Re} z \geqslant 0$ и $\operatorname{Re} z \leqslant 0$, то к числам ${{n}_{ + }}(B)$ и ${{n}_{ - }}(B)$ нужно добавить нулевой индекс ${{n}_{0}}(B)$. Тот же смысл по отношению к полуплоскостям $\operatorname{Im} z > 0$, $\operatorname{Im} z \geqslant 0$, $\operatorname{Im} z < 0$ и $\operatorname{Im} z \leqslant 0$ имеют числа ${{n}_{ + }}(C)$, ${{n}_{ + }}(C) + {{n}_{0}}(C)$, ${{n}_{ - }}(C)$ и ${{n}_{ - }}(C) + {{n}_{0}}(C)$.

Подставим в теорему 1 вместо $A$ матрицу ${{e}^{{ - i\alpha }}}A$. Тёплицево разложение этой матрицы имеет вид

Теперь в силу предложения 3 получаем теорему:

Теорема 2. Числа ${{n}_{ + }}({{C}_{\alpha }})$ и ${{n}_{ - }}({{C}_{\alpha }})$ указывают количества собственных значений матрицы $A$, лежащих соответственно выше и ниже прямой с уравнением $y = (\operatorname{tg} \alpha )x$ на декартовой плоскости $Oxy$.

Следствие 3. Рассмотрим пару симметричных секторов, ограниченных прямыми $y = ({\text{tg}}\alpha )x$ и $y = (\operatorname{tg} \beta )x$, $\beta - \alpha < \tfrac{\pi }{2}$. Предположим, что на граничных прямых нет собственных значений А. Разность между числом собственных значений матрицы $A$, попадающих в эти два сектора, равна ${{n}_{ + }}({{C}_{\alpha }}) - {{n}_{ + }}({{C}_{\beta }})$.

4. ПИФАГОРОВЫ ТРОЙКИ

Поставив задачу построения рационального алгоритма, мы должны считать элементы матриц $A$ и $B$ рациональными или гауссовыми рациональными числами. В этом случае алгоритм может быть выполнен точно, если использовать возможность безошибочных вычислений, предоставляемую системами компьютерной алгебры. Поскольку предполагается многократное применение следствия 3, аргументы $\alpha $ и $\beta $ в нем нужно выбирать так, чтобы коэффициенты соответствующих прямых были рациональными числами. Для такого выбора мы прибегнем к пифагоровым тройкам.

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

где $m$ и $n$ – взаимно простые числа разной четности. Тройке $(p,q,r)$ можно сопоставить прямую или, иначе, Если положить $n = 2$, то для больших $m$. При $m = n + 1$ имеем для больших $n$.

5. АЛГОРИТМ

Наш алгоритм основан на простых соображениях. Он начинается с построения коквадратов ${{A}^{{ - * }}}A$ и ${{B}^{{ - * }}}B$ и проверки их подобия. (В разд. 6 мы изменяем символ матрицы $B$, чтобы не путать ее с первой матрицей в теплицевом разложении $A$.) Если коквадраты не подобны, то $A$ и $B$ не конгруэнтны. На этом работа алгоритма закончена.

Пусть оказалось, что коквадраты подобны. В этом случае плоскость $Oxy$ разбивается на большое число пар симметричных секторов прямыми, проходящими через начало координат. Если растворы этих секторов достаточно малы, а в спектрах матриц $A$ и $B$ нет патологически близких (в смысле хордального расстояния) точек, то в каждой паре секторов будет находиться не более одного (возможно, кратного) собственного значения каждой из матриц. Если собственные значения действительно присутствуют, но расположены в разных секторах, то $A$ и $B$ не могут быть конгруэнтны. Обнаруживается такая ситуация с помощью следствия 3.

Предположим, что ни в одной паре секторов нашего разбиения описанной ситуации не обнаружено. В этом случае можно с высокой вероятностью считать, что $A$ и $B$ имеют одни и те же канонические углы и, следовательно, конгруэнтны. Конечно, эта вероятность не равна единице, поэтому наш алгоритм в заголовке статьи назван эвристическим.

Разбиение плоскости происходит следующим образом. Выберем большие целые числа $M$ и $N$. Проведем в первом и третьем квадрантах два семейства прямых

(таким образом, $M$ нечетно) и (По поводу обозначений ${{\varphi }_{m}}$ и ${{\psi }_{n}}$ см. разд. 4.) Симметричные семейства прямых $y = ( - \operatorname{tg} {{\phi }_{m}})x$ и $y = ( - \operatorname{tg} {{\psi }_{n}})$ проводим во втором и четвертом квадрантах. Эти прямые определяют разбиение плоскости $Oxy$ на пары симметричных секторов. Возможно проведение дополнительных лучей внутри секторов и симметричных лучей в трех остальных квадрантах.

6. ЧИСЛЕННЫЕ РЕЗУЛЬТАТЫ

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

Как известно, циркулянты фиксированного порядка $n$ образуют коммутативную алгебру, диагонализуемую посредством одного и того же унитарного подобия, задаваемого матрицей дискретного преобразования Фурье. Тем самым все циркулянты являются нормальными матрицами.

Обозначим через ${{a}_{0}},{{a}_{1}},\; \ldots ,\;{{a}_{{n - 1}}}$ элементы первой строки $n \times n$-циркулянта $A$. Рассмотрим многочлен

Числа $f(\varepsilon _{0}^{j})$, $j = 0,\;1,\; \ldots ,\;n - 1$, суть собственные значения матрицы $A$. Здесь есть первообразный корень $n$-й степени из единицы. В частности, при $j = 0$, т.е. когда $\lambda $ в формуле (6) равно единице, получаем собственное значение

Обозначим через $J$ матрицу порядка $n$, все элементы которой равны единице. Эта матрица также является циркулянтом. Ее ранг равен 1, а единственное ненулевое собственное значение равно $n$. Положим

Все, кроме одного, собственные значения матрицы $F$ те же, что у $A$. Единственное отличающееся собственное число равно $f(1) + n\mu $ (см. (7)). При это собственное число приобретает значение $ - f(1)$. Коквадраты матриц $A$ и $F$ имеют одинаковый спектр и, следовательно, подобны. В то же время $A$ и $F$ не конгруэнтны, поскольку имеют пару канонических углов, различающихся знаком. Описанным способом мы генерировали пары неконгруэнтных нормальных матриц, имеющих подобные коквадраты.

Предположим теперь, что число $n$ нечетно, и определим диагональную матрицу

Подобие преобразует циркулянт $A$ в косой циркулянт $G$, также являющийся нормальной матрицей. Это простой способ генерирования пар конгруэнтных нормальных матриц.

Наконец, если мы хотим повернуть спектр матрицы $A$ и/или изменить модули ее собственных значений, достаточно умножить $A$ на гауссово число $\alpha + i\beta $, где $\alpha ,\beta \in {\mathbf{Z}}$.

Рассмотрим теперь два примера работы нашего алгоритма. Все вычисления проводились в рациональной арифметике системы Maple.

Пример 1. Пусть ${v}$ – строчный вектор

а ${{A}_{1}}$ – циркулянт, для которого $v$ является первой строкой. Положим $A = (1 - 3i){{A}_{1}}$: Сумма элементов в первой строке матрицы ${{A}_{1}}$ равна $f(1) = \tfrac{3}{2}$. Обозначим через ${{F}_{1}}$ матрицу ${{A}_{1}} + \mu J$, где, согласно (8), $\mu = - \tfrac{3}{5}$. Положим $F = (1 - 3i){{F}_{1}}$: Приведем спектры матриц $A$ и $F$: Таким образом, четыре собственных значения обеих матриц совпадают; вместе с тем имеется пара собственных значений, различающихся знаком.

Работа нашего алгоритма начинается с проверки подобия коквадратов, выполняемой Maple-процедурой IsSimilar. Эта процедура реализует рациональный процесс приведения матриц к их формам Смита и сличения обеих форм.

В данном случае коквадраты матриц $A$ и $F$ подобны, поэтому алгоритм переходит к построению семейства прямых (4). Значение $M$ равно 43. Для каждой пары симметричных секторов, определяемых этими прямыми, разность между числом собственных значений матриц $A$ и $F$, попадающих в два сектора, находится с помощью следствия 3. Участвующие в этом следствии индексы инерции вычисляются Maple-функцией Sturm, применяемой к характеристическим многочленам эрмитовых матриц из соответствующих тёплицевых разложений.

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

На этот раз обнаруживается различие в положении собственных значений матриц $A$ и $F$, принадлежащих секторам с граничными линиями $y = - \tfrac{{165}}{{52}}x$ и $y = - \tfrac{{117}}{{44}}x$. Эти секторы показаны на фиг. 2. На основании следствия 2 алгоритм делает вывод о том, что $A$ и $F$ не конгруэнтны, и прекращает работу.

Пример 2. Пусть ${v}$ – строчный вектор

а ${{A}_{1}}$ – циркулянт, для которого ${v}$ является первой строкой. Положим $A = (1 - 4i){{A}_{1}}$:

Пусть $G$ – косой циркулянт, полученный из $A$ изменением знаков у элементов ${{a}_{{ij}}}$ с нечетной суммой индексов $i + j$. Матрицы $A$ и $G$ диагонально конгруэнтны.

Для этого примера мы использовали оба семейства (4) и (5), а также два симметричных семейства прямых. Значение $M$ по-прежнему равно 43, тогда как для N (см. (5)) взято значение 20. Ни одной пары симметричных секторов с различным расположением собственных чисел матриц $A$ и $G$ не было обнаружено. Поэтому алгоритм прекращает работу с диагностикой “$A$ и $G$ конгруэнтны.”