\documentclass[10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1,T2A]{fontenc}
\usepackage[russian]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[version=4]{mhchem}
\usepackage{stmaryrd}
\usepackage{graphicx}
\usepackage[export]{adjustbox}
\graphicspath{ {./images/} }

\title{УДК 512.643 .8 }


\author{Х.Д. Икрамов\\
Московский государственный университет им. М.В. Ломоносова, Ленинские горы, 1, Москва, 119991\\
E-mail: ikramov@cs.msu.su}
\date{}


\begin{document}
\maketitle
\section*{О конгруэнтном выделении жордановых блоков из вырожденной квадратной матрицы}
Икрамов Х.Д. О конгруэнтном выделении жордановых блоков из вырожденной квадратной матрицы // Сиб. журн. вычисл. математики / РАН. Сиб. отд-ние. Новосибирск, 2018. - Т. 21, № 3. - С. 255-258.

Понятие регуляризующего разложения введено Р. Хорном и В. Сергейчуком и означает представление квадратной матрицы прямой суммой жордановых клеток с нулем на главной диагонали и невырожденной матрицы. Это представление достигается конгруэнтными преобразованиями и отличается от жордановой нормальной формы. По причинам, объясняемым в статье, мы предпочитаем говорить вместо регуляризующего о СР-разложении (иначе говоря, сингулярно-регулярном разложении) матрицы. Алгоритмы, вычисляющие это разложение, мы называем СР-алгоритмами. Предлагается рациональный алгоритм, значительно упрощающий СР-алгоритмы Хорна и Сергейчука.

DOI: $10.15372 /$ SJNM20180302


Ключевые слова: конгруэнтное преобразование, жорданова клетка, СР-разложение, рациональный алгоритм.

Ikramov Kh.D. On congruent selection of the Jordan blocks from a singular square matrix // Siberian J. Num. Math. / Sib. Branch of Russ. Acad. of Sci.- Novosibirsk, 2018. - Vol. 21, № 3. - P. 255-258.

The concept of a regularizing decomposition was introduced by R. Horn and V. Sergeichuk. This means the representation of a square matrix by a direct sum of the Jordan blocks with zero on the principal diagonal and a non-singular matrix. Such a representation is attained via congruent transformations and differs from the Jordan normal form. For the reasons explained in this paper, we prefer to speak about the SN-decomposition of a matrix (in other words, singular-non-singular decomposition) rather than the regularizing decomposition. Accordingly, the algorithms providing the former decomposition are called $\mathrm{SN}$-algorithms. We propose a rational algorithm that considerably simplifies the SN-algorithms proposed by Horn and Sergeichuk.

Keywords: congruent transformation, Jordan block, $S N$-decomposition, rational algorithm.

\begin{enumerate}
  \item Пусть $A$ - квадратная $n \times n$-матрица. Для определенности считаем $A$ комплексной матрицей, хотя все сказанное ниже практически без изменений распространяется на матрицы над любым полем (или даже телом) с инволюцией.
\end{enumerate}

Будем различать два типа конгруэнтных преобразований: $T$-конгруэнции, т. е. преобразования вида


\begin{equation*}
A \rightarrow S^{T} A S \tag{1}
\end{equation*}


и *-конгруэнции


\begin{equation*}
A \rightarrow S^{*} A S . \tag{2}
\end{equation*}


В обеих формулах $S$ - произвольная невырожденная матрица. Преобразования вида (1) соответствуют случаю, когда в качестве инволюции в $\mathbf{C}$ принято тождественное отображение $z \rightarrow z$, а преобразования вида (2) - комплексному сопряжению $z \rightarrow \bar{z}$.


%%%%%%%%%%%%%

И в том, и в другом случае матрицу $\boldsymbol{S}$ можно выбрать так, чтобы $A$ приобрела вид


\begin{equation*}
B \oplus J_{n_{1}} \oplus \cdots \oplus J_{n_{p}} . \tag{3}
\end{equation*}


Здесь $J_{n_{1}}, \ldots, J_{n_{p}}$ - жордановы клетки порядков соответственно $n_{1}, \ldots, n_{p}$ с нулем на главной диагонали, а $B$ - невырожденная матрица, определяемая с точностью до конгруэнции. Представление (3) названо в [1] регуляризующим разложением матрицы $A$, прямая сумма $J_{n_{1}} \oplus \cdots \oplus J_{n_{p}}$ - сингулярной частъю этого разложения, а о матрице $B$ говорят, что она определяет его регулярную часть. Два последних термина также заимствованы из статьи [1].

Там же, в [1], описаны несколько алгоритмов для вычисления разложения (3). Авторы называют их алгоритмами регуляризации, видимо, по той причине, что после выделения клеток $J_{n_{1}}, \ldots, J_{n_{p}}$ остается невырожденная, т. е. регулярная, матрица $B$. С нашей точки зрения, эти названия - регуляризующее разложение, алгоритм регуляризации - крайне неудачны, поскольку неизбежно напоминают о теории регуляризации А.Н. Тихонова, которую авторы [1] вовсе не имели в виду. Мы будем называть (3) СР-разложением (иначе говоря, сингулярно-регулярным разложением) матрицы $A$, а алгоритмы, вычисляющие это разложение, СР-алгоритмами.

Один из СР-алгоритмов, описанных в [1], использует только унитарные (а в вещественном случае - только ортогональные) преобразования, что рассматривается авторами как важное достоинство, хотя можно усомниться в полезности унитарности при решении некорректной задачи, родственной задаче построения жордановой нормальной формы.

На наш взгляд, излишне сложен и другой СР-алгоритм из [1], основанный на элементарных преобразованиях строк и столбцов матрицы $A$. Цель данной заметки - по возможности упростить СР-процесс, оставаясь в классе неортогональных (неунитарных) преобразований. В рамках систем компьютерной алгебры это дает возможность точной реализации алгоритма, по крайней мере, для матриц с рациональными или гауссовыми рациональными элементами.

\begin{enumerate}
  \setcounter{enumi}{1}
  \item Будем, для определенности, говорить о $T$-конгруэнциях матрицы $A$. Очевидными инвариантами таких преобразований являются ранг $r_{A}$ и дефект $d_{A}$ этой матрицы. Отсюда следует:
\end{enumerate}

\begin{enumerate}
  \item количество $p$ жордановых клеток в СР-разложении (3) равно числу $d_{A}$;

  \item клетки порядка 1 в (3) отвечают векторам, лежащим в пересечении ядер матрицы $A$ и транспонированной матрицы $A^{T}$; число таких клеток равно размерности этого пересечения.

\end{enumerate}

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

\begin{enumerate}
  \setcounter{enumi}{2}
  \item Предположим, что матрица $A$ вырождена и ее ядро $\mathcal{N}_{A}$, возможно, пересекаясь с ядром $\mathcal{N}_{A^{T}}$ матрицы $A^{T}$, не совпадает с ним.
\end{enumerate}
%%%%%%%%%%%%%%%%


Пусть $f$ - произвольный вектор из множества $\mathcal{N}_{A} \backslash \mathcal{N}_{A^{T}}$. От исходного базиса координатных векторов $e_{1}, e_{2}, \ldots, e_{n}$ перейдем к произвольному базису, в котором $f$ является первым вектором. В матрице $\tilde{A}$, полученной в результате этого перехода, первый столбец нулевой. Поскольку $f$ не принадлежит $\mathcal{N}_{A^{T}}$, то в первой строке $\tilde{A}$, напротив, есть\\
ненулевые внедиагональные элементы. Перестановкой столбцов добьемся, чтобы ненулевым был элемент в позиции $(1,2)$. Если это можно сделать разными способами, то, из соображений численной устойчивости, переведем в позицию $(1,2)$ элемент с наибольшим модулем. Чтобы завершить конгруэнтное преобразование, нужно переставить и одноименные строки. Эта перестановка не изменит (нулевой) первый столбец.

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

Первые строка и столбец матрицы приобрели теперь нужный вид. Следующий шаг исключение элементов второго столбца. Первая строка в этом исключении является ведущей, а ее элемент $(1,2)$ - ведущим. Когда исключение заканчивается, этот элемент становится единственным ненулевым элементом второго столбца. Для формального завершения конгруэнции первый столбец, умноженный на надлежащие коэффициенты, следовало бы вычесть из остальных. Так как, однако, этот столбец - нулевой, то соответствующие столбцовые операции можно опустить.

Пусть $\hat{A}$ - матрица, полученная по завершении исключения во втором столбце. Если в ее второй строке имеются ненулевые элементы, то мы повторяем для этой строки те же действия, какие ранее были проделаны для первой строки матрицы $A$, т. е. перестановкой столбцов переводим ненулевой элемент (или даже элемент с максимальным модулем) в позицию $(2,3)$, проводим исключение остальных ненулевых элементов этой строки, а затем исключаем элементы $(3,3),(4,3), \ldots,(n, 3)$ третьего столбца. Каждое из этих действий дополняется до конгруэнции соответствующими операциями со строками или столбцами. При этом сохраняются все нулевые элементы первых двух столбцов.

Если в третьей строке полученной матрицы присутствуют ненулевые элементы, то описанный процесс продолжается уже известным образом. Может случиться, что так мы дойдем до последней строки. Тогда итоговым результатом будет матрица вида

\begin{center}
\includegraphics[max width=\textwidth]{2024_02_27_07dc12870868d64e82bcg-3}
\end{center}

конгруэнтная исходной матрице $A$. Дополнительной конгруэнцией с диагональной трансформирующей матрицей можно превратить (4) в жорданову клетку $J_{n}$. В данном случае эта клетка будет единственным слагаемым СР-разложения (3).

Если абстрагироваться от этого крайнего случая, то процесс выделения жордановой клетки закончится на каком-то более раннем шаге. Предположим, что после $k-1$ шагов описанного выше процесса, где $k \leq n-2$, обнаружилось, что все элементы $k$-й строки равны нулю. Это означает, что текущая матрица имеет вид прямой суммы

$$
G_{k} \oplus A_{n-k},
$$

где

$$
G_{k}=\left(\begin{array}{cccccc}
0 & \alpha_{1} & & & & \\
& 0 & \alpha_{2} & & & \\
& & \cdots & \cdots & \cdots & \\
& & & & 0 & \alpha_{k-1} \\
& & & & & 0
\end{array}\right)
$$

а $A_{n-k}$ - матрица порядка $n-k$. Диагональной конгруэнцией превратим $G_{k}$ в жорданову клетку $J_{k}$, которая будет одним из слагаемых искомого СР-разложения.

Если матрица $A_{n-k}$ невырождена, то она будет слагаемым $B$ этого разложения, а само разложение будет суммой двух слагаемых. В противном случае к $A_{n-k}$ нужно применить изложенный выше процесс выделения жордановых клеток.

\begin{enumerate}
  \setcounter{enumi}{3}
  \item Авторы статьи [1] рассматривают СР-разложение (3) как первый этап в процессе построения канонической формы матрицы $A$ относительно конгруэнций. Следующий этап состоит в упрощении вида невырожденной матрицы $B$. В случае *-конгруэнций этот этап имеет определенные сложности, которые мы рассмотрим в отдельной публикации.

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

\end{enumerate}


\begin{equation*}
r_{k}=\operatorname{rank} A^{k}, \quad k=1,2, \ldots, \quad r_{0}=n \tag{5}
\end{equation*}


Последовательность $\left\{r_{k}\right\}$ нужно вычислять до момента ее стабилизации, т. е. до индекса $k_{0}$, когда впервые выполнится равенство

$$
r_{k_{0}}=r_{k_{0}+1}
$$

Алгоритм вычисления СР-разложения, описанный в пункте 3 настоящей статьи, также является рациональным. Однако остается открытым вопрос о том, как интерпретировать параметры $p, n_{1}, n_{2}, \ldots, n_{p}$ разложения (3) в терминах величин, определяемых непосредственно по матрице $A$ (ср. с (5)).

\section*{Литература}
\begin{enumerate}
  \item Horn R.A., Sergeichuk V.V. A regularization algorithm for matrices of bilinear and sesquilinear forms // Linear Algebra Appl. - 2006.- Vol. 412, iss. 2-3.-P. 380-395.
\end{enumerate}

Поступила в редакцию 10 августа 2017 г., в окончательном варианте 7 ноября 2017 г.


\end{document}