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

(2)

2

получаем, что 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.