ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 2, с. 185-188
УДК 519.61
О СПОСОБАХ ХАРАКТЕРИЗАЦИИ (T + Я)-МАТРИЦ И (T + ^-ЦИРКУЛЯНТОВ1
© 2015 г. Х. Д. Икрамов, В. Н. Чугунов
(119992 Москва, Ленинские горы, МГУ, ВМК; 119991 Москва, Ин-т вычисл. матем. РАН) e-mail: ikramov@cs.msu.su; chugunov.vadim@gmail.com Поступила в редакцию 08.05.2014 г.
Пусть задана (n х п)-матрица A. Как выяснить, является ли она (T + Н)-матрицей? Если да, то не будет ли A даже (T + Н)-циркулянтом? Как найти циркулянтные слагаемые ее (T + ^-разложения? На эти вопросы даны алгоритмические ответы. Библ. 3.
Ключевые слова: тёплицевы матрицы, ганкелевы матрицы, (T + Н)-матрицы, циркулянты, ганкелевы циркулянты, (T + Н)-циркулянты.
DOI: 10.7868/S0044466915020106
1. В пространстве Mn(C) комплексных (n х п)-матриц выделим линейные подпространства 2Гn и Жп, состоящие, соответственно, из тёплицевых и ганкелевых матриц. Сумму этих подпространств будем обозначать символом 2ГЖп. Матрицу A е 2ГЖп принято называть (T + Н)-матри-цей (соответствующий английский термин — Toeplitz-plus-Hankel matrix). Условимся записывать матрицу T е 2Гn в виде
(
T =
а матрицу H е Жп в виде
¿0 ti t2 • tn - 2 tn -
t-1 ¿0 t1 - tn - 3 tn -
t-2 t-i t0 • tn - 4 tn -
t-n + 2 t-n + 3 t- -n + 4 • t0 t1
t-n + 1 t-n + 2 t- -n + 3 - t-1 t0
hn - 1 hn - 2 hn - 3 •■ h1 h
hn - 2 hn - 3 hn -4 •■ h0 h-
hn - 3 hn - 4 hn -5 •■ h-1 h-
h1 h0 h_ 1 •■ h-n + 3 h-n
h0 h-1 h_ 2 •• h-n + 2 h-n
(1)
H =
г + 2 г+ 1 ^
Тёплицева матрица (1) называется (тёплицевым) циркулянтом, если
и = К -I, 1 = 1, 2, ..., п - 1. Будем называть матрицу (2) ганкелевым циркулянтом, если
= Ьп-1, ' = 1, 2, ..., п - 1.
(2)
1) Работа второго автора выполнена при поддержке Российского науч. фонда (14-11-00806).
Матрицу, представимую в виде суммы тёплицева и ганкелева циркулянтов, будем называть (Т + Н)-циркулянтом.
В этом сообщении мы рассматриваем такие вопросы: пусть задана (п х п)-матрица А. Как выяснить, является ли она (Т + Н)-матрицей? Если да, то не будет ли А даже (Т + Н)-циркулянтом? Первый из этих вопросов обсуждается в разд. 2, а второй — в разд. 3.
2. Пусть (п х п)-матрица А удовлетворяет условию
а -1, у + а +1, у = а, у -1 + а,, у + ^ (3)
где индексная пара (I, у) такова, что
1 < /, У < п. (4)
Учитывая расположение участников равенства (3) в матрице А, мы называем его правилом ромба относительно элемента ау.
В [1] получена следующая характеризация (Т + Н)-матриц.
Теорема 1. Матрица А е Мп(С) тогда и только тогда является (Т + Н)-матрицей, когда для всякой индексной пары (/, у), удовлетворяющей ограничениям (4), выполнено правило ромба.
Проверка этого критерия для конкретной матрицы А требует не более 2(п — 1)2 операций сложения и (п — 1)2 сравнений. Проверка может закончиться значительно раньше, если для какой-то позиции правило ромба не выполнено и, следовательно, А не является (Т + Н)-матрицей.
Недостаток описания (Т + Н)-матриц, предоставляемого теоремой 1, состоит в следующем: даже если заданная матрица А оказалась (Т + Н)-матрицей, мы не можем указать слагаемые Т и Н в ее представлении
А = Т + Н, Т е Н е Жп. (5)
Всякое представление этого вида будем называть (Т + Н)-разложением матрицы А. Оно всегда не единственно в силу того, что подпространства 2Гп и Жп имеют нетривиальное пересечение. Опишем его.
Если В е 2Гп п Жп, то все элементы Ьу с четной суммой индексов должны быть одинаковы, и то же верно для элементов с нечетной суммой I + у. Матрицы, удовлетворяющие этим условиям, образуют двумерное подпространство, базисом которого можно считать две специальные матрицы: матрицу /п, все элементы которой равны единице, и "шахматную" матрицу Кп, для которой
(К)у= (-1 -у, I,у = 1, 2.....п.
Пусть А е ^Жп. Полученное выше описание подпространства 2Гп п Жп означает, что в представлении (5) оба слагаемых определены с точностью до линейной комбинации вида
а ]п + р Кп.
Укажем один из возможных способов вычисления всех возможных (Т + Н)-разложений заданной (Т + Н)-матрицы А. В качестве свободных параметров этих разложений возьмем коэффициенты и 1Х.
Приравняв в (5) элементы главной диагонали и элементы в позициях (к, к + 1), где 1 < к < п, выразим неизвестные Ну через параметры
кп -1 = а11 - ¿0, кп - 3 = а22 - к-п + 1 = апп - ¿0, (6)
кп - 2 = а12 - ^ кп - 4 = а23 - ¿1, •■■ , к-п + 2 = ап -1, п - ¿1. (7)
Теперь приравняем элементы первой строки и первого столбца:
¿2 = а13 - кп - 3 = а13 - а22 + ^ ¿3 = а14 - кп - 4 = а14 - а23 + ¿1,
¿4 = а15 - кп -5 = а15 - азз + ¿0,
¿-1 = а21 - кп - 2 = а21 - а 12 + ¿1, ¿-2 = аз1 - кп -3 = аз1 - а22 + ¿о, ¿-3 = а41 - кп - 4 = а41 - а23 + ¿1,
О СПОСОБАХ ХАРАКТЕРИЗАЦИИ (Т + Н)-МАТРИЦ
187
Задавая значения свободным переменным ^ и получаем конкретное (Т + Н)-разложение. Наиболее простым выбором является
?о = 11 = 0.
В этом случае весь процесс сводится к 2п — 1 присваиваниям и 2п — 3 вычитаниям.
3. Переходя к обсуждению (Т + Н)-циркулянтов, отметим, что эти матрицы могут рассматриваться как элементы некоторой алгебры. Согласно [2] (см. также [3]), такой алгеброй является централизатор матрицы
(
Z =
0 1 1 0 1 10
1
V 1
1 0 у
Напомним, что централизатором квадратной матрицы ^ называется алгебра матриц, перестановочных с Z.
Таким образом, выяснение, является ли (Т + Н)-циркулянтом заданная матрица А, может сводиться к проверке перестановочности
А2 = ^А. (8)
Эта проверка есть не что иное, как циклически применяемое правило ромба. Действительно, для позиций (I, у), удовлетворяющих ограничениям (4), приравнивание элементов в равенстве (8) приводит к соотношению (3). Тем самым "внутренние" условия перестановочности равносильны проверке для А свойства быть (Т + Н)-матрицей. Дополнительные ("граничные") условия перестановочности относятся к границе матрицы А, т.е. к ее первой и последней строке и первому и последнему столбцу. Например, для позиции (1, п) уравнение (8) дает
Это то же правило ромба, записанное для матрицы, первый столбец которой "подклеен справа" к последнему столбцу, а последняя строка "подклеена сверху" к первой строке.
В целом проверка равенства (8) для конкретной матрицы А требует не более 2п2 операций сложения и п2 сравнений. Проверка может закончиться значительно раньше, если для какой-то позиции правило ромба не выполнено и, следовательно, А не является (Т + Н)-циркулянтом.
Описанный способ страдает тем же недостатком, что и первый алгоритм из предыдущего пункта: даже если заданная матрица А оказалась (Т + Н)-циркулянтом, мы не можем указать тёп-лицев циркулянт Т и ганкелев циркулянт Н в ее представлении (5). Обсудим, как для этого случая следует модифицировать второй алгоритм из п. 2.
Если п = 2к, то, по существу, никаких изменений не требуется. Обе матрицы 1п и Кп являются одновременно тёплицевыми и ганкелевыми циркулянтами. Поэтому для заданной матрицы А годится любое (Т + Н)-разложение: если А есть (Т + Н)-циркулянт, то компонента Т произвольного разложения обязательно будет циркулянтом, а компонента Н — ганкелевым циркулянтом. Алгоритм из предыдущего пункта, проводимый со свободными параметрами ^ и 1Х, дает все множество (Т + Н)-разложений. Если же достаточно иметь одно разложение, то простейшим выбором остается ^ = = 0.
Ситуация меняется для п = 2к + 1. Шахматная матрица Кп теперь не является ни тёплицевым, ни ганкелевым циркулянтом. Например, в матрице
К, =
( \
1 -1 1 -1 1 -1
1 -11 у
1, п - 1 + а11 — а2п + апп.
а
элементы в позициях (1, 3) и (2, 1) не равны, так же как не равны элементы в позициях (1, 1) и (3, 2). Таким образом, пересечение подпространств, составленных из тёплицевых и ганкелевых циркулянтов, имеет размерность 1, а не 2. Это значит, что даже если матрица A есть (T + Н)-цир-кулянт, слагаемые ее (T + Н)-разложения отнюдь не обязаны быть циркулянтами. Они будут циркулянтами лишь при определенном соотношении между параметрами t0 и t1.
Найти нужное соотношение можно так: согласно одному из равенств (7), имеем
h1 = ak, k + 1 - t\.
С другой стороны (см. (6)),
h-n + 1 = ann — t0 .
Если компонента H в (T + Н)-разложении является ганкелевым циркулянтом, то должно быть
h-n +1 = hi,
что приводит к искомому соотношению между t0 и t1:
t1 - t0 = ak, k + 1 - ann.
Выбрав какое-либо значение для t0 (например, t0 = 0), получим однозначно определенное значение для t1. Теперь обсуждаемый алгоритм дает требуемое (T + Н)-разложение при условии, что заданная матрица A действительно является (T + Н)-циркулянтом.
СПИСОК ЛИТЕРАТУРЫ
1. Икрамов Х.Д., Чугунов В.Н., Абдикалыков А.К. О локальных условиях, характеризующих множество (T + Н)-матриц // Докл. АН. 2014. Т. 457. № 1. С. 17-18.
2. Bozzo E. Algebras of higher dimension for displacement decompositions and computations with Toeplitz plus Hankel matrices // Linear Algebra Appl. 1995. V. 230. P. 127-150.
3. Икрамов Х.Д., Савельева Н.В. О некоторых квазидиагонализуемых семействах матриц // Ж. вычисл. матем. и матем. физ. 1998. Т. 38. № 7. С. 1075-1084.
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.