Разделы
Главная Сапромат Моделирование Взаимодействие Методы Инновации Индукция Исследования Факторизация Частоты
Популярное
Как составляется проект слаботочных сетей? Как защитить объект? Слаботочные системы в проекте «Умный дом» Какой дом надежнее: каркасный или брусовой? Как правильно создавать слаботочные системы? Что такое энергоэффективные дома?
Главная »  Факторизация 

Факторизация матриц матрицами Фробениуса

Воронов А.Л., Орлов И.И. (iiorlov@mail.ru)

Институт Солнечно-Земной Физики СО РАН, г. Иркутск

1. Введение.

Большинство прямых методов обращения матриц используют разложение матрицы в произведение легко обращаемых сомножителей [1]. Типичным и достаточно распространенным методом обращения матриц является метод Жордана. В данной работе рассмотрен иной способ факторизации матриц, основанный на использовании матриц Фробениуса.

Введем основные обозначения. Пусть F - матрица фробениусова типа, что соответствует представлению ее в видеF = e2,e3,...,en,f [2], где ek вектор-столбцы

канонического базиса, то есть вектора с координатами (ek)p = ekp = skp. Здесь skp -

символ Кронекера. Считаем, что вектор-столбец f имеет координаты fk . В этом случае

определитель матрицы F равен (-1 )n+1 f1, следовательно, при условии f1 Ф 0 матрица F будет обратимой. Обратная матрица для матрицы F может быть записана в виде

f,e1,e2 ,...,en-1j, где элементы вектор-столбеца f = (f1,f2,...,fn) определяются по формулам

Ju =-fk+1/f1, k = 1,(n-1),Jn = 1/f1. (1)

Действие матрицы F справа на некоторую матрицу A = a1,a2,...,a[, где ak вектор-столбцы, сводится к сдвигу вектор-столбцов матрицы A влево на одну позицию и образованию нового ( n -го) столбца по правилу

AF = \\a2,a3,...,an,an\\, an =S akfk. (2)

Здесь ak = (a1k,a2k,...,ank) - вектор-столбцы, а A = lai1. Легко проверить, что имеет место равенство

detF1F2...Fm = (-1)m(n+1> П f1(k), Fk =\e2,e3,...,en,f(k)\. (3)

и, как следствие из него

detF1F2...Fn =П f((k). (4)

2. Условия представимости матриц в виде произведения Фробениусовых матриц.



Здесь

1,2,.

., m

1,2,...,n - m

, A12

m + 1,m + 2,..., n { 1, 2, ...,n - mj

1, 2, ...,m

n - m + 1,n - m + 2,..., n j

f m +1, m + 2, ...,n n - m + 1,n - m + 2,..., n

В формулах (6) индексы в верхнем ряду указывают на номера строк исходной матрицы, использованные при образовании соответствующего блока, а нижние индексы - на номера столбцов. Обозначим также через Dm определитель матрицы A12 размера m х m

detA12 = Dm = D\

12 m

1, 2, ...,m

n - m + 1,n - m + 2,...,

Так как при умножении матрицы на фробениусову справа столбцы исходной матрицы смещаются влево на одну позицию, то матрица A21 будет единичной матрицей размером (n - m) х (n - m), а прямоугольная матрица A11 будет нулевой. Поэтому, в силу теоремы Лапласа о вычислении определителей через миноры и алгебраические дополнения к ним [3], имеем

detA = (-1)m(n-m)Dm = (-1)m(n+1)П f((k), и Dm =Ц f(k>. (8)

k=1 k=1

При последовательном перемножении матриц фробениусового типа квадратная матрица, стоящая в правом верхнем углу, смещается влево и увеличивается в размерах на единицу. Тем самым показано, что все определители Dk главных миноров матрицы A = F1F2 ...Fn отличны от нуля.

Известно, что все матрицы с не нулевыми определителями Dk образуют множество регулярных матриц Greg [4]. Такие матрицы могут быть представлены в виде произведения верхней и нижней треугольных матриц [5]. Кроме того, множество Greg

Покажем, что для матриц фробениусова типа имеет место следующая теорема. Теорема 1. Пусть матрица A представима в виде произведения n фробениусовых матриц. Тогда все определители главных миноров матрицы A ненулевые. Обратно, если все определители главных миноров матрицы A не нулевые, то матрица A представима в виде произведения n матриц Фробениуса.

Доказательство. Пусть A = F1F2...Fm. Введем следующие обозначения, представив матрицу A в блочной форме,

(A A \

к A21 A22 j



всюду плотно в множестве не особых матриц G . Так как матрицы фробениусового типа F характеризуется n параметрами, то множество таких матриц (f1 0 ) будет системой образующих для множества Greg и, следовательно, по непрерывности для множества

G всех обратимых матриц.

Докажем теперь обратное утверждение, заключающееся в том, что любая регулярная A матрица (размером n х n) представима в виде произведения n матриц Фробениуса. Для этого будем искать такую обратную матрицу к матрице фробениусового типа F- (не особую), действие которой на матрицу A справа приводит к смещению всех столбцов вправо на одну позицию, а в качестве первого столбца для новой матрицы A1 дает столбец en - один из векторов канонического базиса. В этом случае, если

обозначить первый столбец F- через , то задача сводится к уравнению AF1-1 = A1, где

A = \\d1,a2,...,dn\\, A1 = \\en,a1,a1 ,...,an \ (9)

В силу специальной структуры преобразующей матрицы уравнение для вектора f(1) примет вид Af(1) = en . Заметим, что матрица A1 не особая, так как ее определитель, по теореме Лапласа, определяется формулой

detA1 = ( 1)n+1Dn 1, (10)

где Dn-1 определитель минора исходной матрицы A . Отсюда получаем, что

detF-1 = ( 1)n+1Dn 1 /Dn = ( 1)n1~fi1). (11)

Далее, действуя по индукции, рассматриваем уравнение A1 F2 1 = A2 , где матрица A2 выбрана в виде

A2 = \\en 1>en>a1>a2>-,an 2\[ (12)

В этом случае задача также сводится к системе линейных уравнений вида A1 f(2) = en 1 . Так как матрица A1 не особая, то эта система линейных уравнений имеет единственное решение.

Определитель A2 , в соответствии с теоремой Лапласа, равен

detA2 = ( 1)2(n+1)Dn 2, (13)

откуда получаем, что

detF;1 = ( 1)n+1Dn 2/Dn 1 = ( 1)n1~fi2K (14)

Предположим теперь, используя индукцию, что на m -ом шаге определитель матрицы Am равен



detAm = (-1)m(n-1>Dn-, (15)

где величины Dk - определители главных миноров исходной матрицы A . Матрица Am имеет вид

Am = \en+1-m ,en+2-m> >en ,а1 ,a2 >an-m\

Рассмотрим следующий шаг индукции, определяя матрицу Am+1 в виде произведения AmF~m +1 = Am+1, где матрица Am+1 ищется в следующей форме

Am+1 = \en-m>en+1-m> >en>a1>a2> >an-m-1

Эта матрица содержит все известные элементы, а искомой величиной является первый столбец обратной фробениусовой матрицы F ~г. Как и ранее задача сводится к системе линейных уравнений вида Amf(m+1) = en-m . Так как det Am = Dm Ф 0, то система имеет единственное решение.

Для определителя матрицы Am+1, как и ранее, используя теорему Лапласа, имеем

det Am+1 = (-1)(m+1)(n+1}Dn-m-1 (18)

Соответственно, для обратной фробениусовой матрицы получаем

detF-J, = (-1)n+1Dn-m-1 /Dn-m = (-1)n+1f<tm+1) (19)

Тем самым доказано, что после ( n -1 )-го шага мы получим матрицу

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

Следствие. Так как любая обратимая матрица A, не обязательно регулярна, то с помощью матрицы перестановки столбцов T она может быть преобразована к регулярной матрице по формуле AT = Areg, то Areg = AT . Следовательно, любая не особая матрица

может быть представлена в виде произведения n фробениусовых матриц и матрицы перестановки столбцов или строк.

3. Алгоритм решения систем линейных уравнений.

Рассмотрим алгоритм решения системы линейных уравнений Ax = g, основанный

на использовании представления обратимой матрицы A = a1,a2, ,an в виде

произведения n фробениусовых матриц и матриц перестановки столбцов. На первом шаге, с помощью матрицы перестановки двух столбцов T1 , преобразуем матрицу A так, чтобы первый элемент первого столбца новой матрицы был отличен от нуля. Тогда



матрицу F1 = e2,e3,...,en,f( , в которой вектор f = a1, вычисляем матрицу

A1 = F~1A1, имеющую вид A1 = en,a<21>,a<31>,...,a(n1) . Исходная же система уравнений

заменяется следующей F~1A1x1 = A1x1 = F1 g = g1. Заметим, что матрица A1 обратима.

На втором шаге, действуя аналогично первому шагу, в случае необходимости, осуществляем перестановку пары столбцов A1 таким образом, чтобы первый элемент второго столбца стал отличным от нуля. Это возможно в силу обратимости матрицы A1. Тогда система уравнений примет вид (A1T2)T2x1 = A2T2x = A2x2 = g1. Преобразуя

матрицу A2 по формуле A2 = F21A2, где F2 = \\e2,e3,..., en,f(2>\\, а f<2> = a

получаем, что A2 = jen 1,en,a(32> ,...,a(n2)j.

В результате, после конечного числа шагов, решение исходной системы линейных уравнений описывается формулой Tn 1Tn 2...T1x = F1Fn ,1...F~1 g. Очевидно, что наряду с получением решения системы линейных уравнений, одновременно получается набор матриц Fk 1, имеющих фробениусов вид, произведение которых определяет обратную

матрицу по формуле A = T1T2...Tn 1Fn 1 FI .1...F~1. Кроме этого, приведенная выше

процедура дает также величины определителей главных миноров исходной матрицы, так как последние выражаются через произведения первых элементов определяющих вектор-столбцов матриц Фробениуса. Оценка числа операций, необходимых для построения решения системы линейных уравнений по предложенному алгоритму однотипных операций, дает величину порядка n3 n2 / 2. Алгоритм Гаусса для решения системы линейных уравнений имеет тот же порядок по числу операций [5].

4. Представление обратимой матрицы в виде произведения матриц Фробениуса. В этом разделе рассмотрен общий случай представимости произвольной не особой матрицы в виде произведения фробениусовых матриц. Имеет место теорема.

Теорема 2. Произвольная обратимая матрица представима в виде не более чем (2n 1) фробениусовых матриц. Существуют обратимые матрицы, не представимые в виде произведения ( 2n 2 ) фробениусовых матриц.

Доказательство. Рассмотрим сначала второе утверждение, предположив справедливым первое утверждение теоремы. Пусть первый столбец матрицы A имеет нули в первых ( n 1 ) строках. Очевидно, что существуют не особые матрицы с этим свойством. Такой

система уравнений примет вид (AT1 )T1x = A1T1x = A1x1 = g . Здесь матрица T1 является либо единичной, либо задает нетривиальную перестановку двух столбцов. Далее, вводя



матрицей будет, например, антидиагональная матрица, состоящая из единиц вдоль второй диагонали. Предположим, что такая антидиагональная матрица представляется в виде произведения (2n - 2) фробениусовых матриц, то есть A = F1F2. F2n-2. Тогда первый

столбец матрицы A совпадает с (n-1)-м столбцом произведения F1F2. Fn. Это имеет

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

Поскольку, согласно теореме 1, все определители главных миноров матрицы F1F2.Fn не нулевые, то и определитель главного минора, размером (n -1) х (n -1) не

равен нулю. В то же время, согласно предположению, первые (n -1) компонент 1 -го столбца матрицы F1F2. Fn нулевые , откуда определитель главного минора размером (n -1) х (n -1) равен нулю и мы пришли к противоречию. Тем самым антидиагональная матрица представляется точно в виде (2n -1) фробениусовых матриц.

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

произведение не особых фробениусовых матриц F1F2. Fn-1, что матрица AF71 F71 F~- 1 будет регулярной. Тогда нужное утверждение будет следовать из теоремы 1.

При умножении произвольной матрицы на матрицу вида F1-1 справа элементы первого столбца получаются умножением строк исходной матрицы на первый столбец матрицы F1-1 , а остальные столбцы исходной матрицы сдвигаются вправо на одну позицию. Покажем, что можно так выбрать матрицу F1-1 , чтобы для элементов первого столбца матрицы A1 = AF71 были выполнены равенства a(/k = xk1, где x1 - некоторое не нулевое число. Пусть a(11> - первый столбец матрицы A1 и - первый столбец матрицы F1-1 . Тогда f1-1 = A-1a1(1) и для обратимости матрицы F1 нам нужно добиться, чтобы n -ая компонента вектора f1-1 была ненулевой. Эта компонента фактически является скалярным произведением n-й строки матрицы A- на вектор a(11>. Поскольку

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

Рассматривая теперь матрицу A1 = AF1-1 в качестве исходной, можно будет перейти к матрице A2 = AF71F21 по только что описанному алгоритму, выбирая x2 Ф x1.



В результате этой операции у матрицы A2 первые два столбца будут иметь вид a1( ,2k) = x2k , a2(2,k) = x1k . Продолжая такие построения, после ( n 1 )-го шага, получаем матрицу An 1 = AF1F1 ...Fn 11, обладающую тем свойством, что ее первые из (n 1) столбцов совпадают с первыми ( n 1 ) столбцами матрицы Вандермонда относительно чисел xn 1,xn 2,...,x1. При этом считаем, что все числа xn 1,xn 2,...,x1 отличны друг от друга.

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

регулярной и тем самым, в соответствии с теоремой 1 представимой в виде произведения n матриц фробениусова типа. Таким образом, теорема 2 доказана. Литература

1. Математическая энциклопедия. Т. 3. М.: Советская энциклопедия, 1982. 1184 с..

2. Глазман И.М., Любич Ю.И. Конечномерный линейный анализ. М.:Наука, 1969. 476 с..

3. Фаддеев Д.К. Лекции по линейной алгебре. М.:Наука, 1984. 416 с..

4. Желобенко Д.П. Компактные группы Ли и их представления. М.:Наука, 1970. 664 с..

5. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1988, 548 с..