!!§!! Вспомогательная страница к разделу ((:algebra2:dets ОПРЕДЕЛИТЕЛЬ))
== Приемы вычисления определителей, зависящих от параметров ==
Довольно часто на практике возникает необходимость вычислять определители, элементы которых зависят от параметров. ((algebra2:dets#метод_приведения_к_треугольному_виду_метод_гаусса Метод Гаусса)) оказывается не слишком приспособленным для такой задачи.
!!П!! **Пример.** Вычислить
$$
\left|
\begin{array}{cccc}
{\color{Red} \alpha } +1 &{\color{Red} \alpha } ^2+1 &{\color{Red} \alpha } ^2-1 & {\color{Red} \alpha } \\
{\color{Red} \alpha } ^2+{\color{Red} \alpha } +1 & {\color{Red} \alpha } ^2- {\color{Red} \alpha } +1 & {\color{Red} \alpha } ^2 & 1 \\
2\,{\color{Red} \alpha } +1 &{\color{Red} \alpha } ^2+2 & {\color{Red} \alpha } & {\color{Red} \alpha } ^2-1 \\
2\,{\color{Red} \alpha } & 2\, {\color{Red} \alpha } ^2+2\,{\color{Red} \alpha } +1 & {\color{Red} \alpha } ^2-{\color{Red} \alpha } -1 & {\color{Red} \alpha } +1
\end{array}
\right| \ .
$$
**Решение.** Разложение по ((:algebra2:det4x4 общей формуле)) даст величину этого определителя в виде ((:polynomial полинома)) от
$ {\color{Red} \alpha } $. С другой стороны, если для его вычисления мы попытаемся применить
((algebra2:dets#метод_приведения_к_треугольному_виду_метод_гаусса метод Гаусса)), то на первом же шаге элементы преобразованного определителя окажутся дробно--рациональными
функциями от параметра $ {\color{Red} \alpha } $. Понятно, что после приведения определителя
к треугольному виду и
перемножения стоящих на диагонали дробей мы, в конце концов, получим тот же
ответ полиномиального вида, но сам
факт, что для его получения потребовалось "выйти за пределы" множества
полиномиальных функций не свидетельствует в пользу метода
Гаусса...
♦
Универсальных методов вычисления подобных определителей
(отличных, естественно, от ((algebra2:dets#определение определения))) __не существует__. Успех во многом будет зависеть от искусства
вычислителя. Здесь мы покажем несколько полезных приемов, которые __иногда__ помогают.
===Выделение линейных множителей====
Этот прием основан на свойстве ((:algebra2:dets#определение полиномиальности определителя)) как функции его элементов. Если элементы зависят --- также полиномиально --- от одного параметра, то можно попытаться определить ((:polynomial#основная_теорема_высшей_алгебры линейные множители)) "полинома из ответа": иногда из особенностей определителя очевидно при каких значениях параметра этот определитель обращается в нуль.
!!П!! **Пример.** Вычислить определитель
$$\left|\begin{array}{ccccc}
1&1&1&\dots&1\\
1&2-x&1&\dots&1\\
1&1&3-x&\dots&1\\
\vdots& & &\ddots&\vdots\\
1&1&1&\dots&n+1-x
\end{array}\right|.$$
**Решение.** Ответом в этой задаче должен быть полином по $ x_{} $. Обозначим его $ F(x)_{} $ и попробуем догадаться какие корни он может иметь. Обратим внимание на структуру определителя. Если положить $ x=1_{} $, то вторая строка будет одинаковой с первой, на основании ((:algebra2:dets#элементарные_свойства_определителя свойства))
3
определителя, при этом значении $ x_{} $ будем иметь $ F(1)=0 $. Аналогично убеждаемся, что $ F(2)=0, \dots, F(n)=0 $. Итак, на основании ((:polynomial#корни теоремы Безу)), имеем:
$$ F(x) \equiv F_1(x) (x-1)\times \dots \times (x-n) \ , $$
где через $ F_1(x) $ обозначен полином, являющийся частным от деления $ F(x)_{} $ на произведение линейных множителей. Оценим степень полинома $ F(x)_{} $. Очевидно, что при разложении определителя по общей формуле из ((algebra2:dets#определение определения)), каждое слагаемое представляет произведение элементов определителя и будет полиномом по $ x_{} $. В каждом слагаемом максимально возможная степень может быть достигнута если каждый элемент в произведении будет иметь максимально возможную степень --- в нашем случае равную $ 1_{} $. Отсюда с неизбежностью следует, что самым
"большим" по степени может быть только ((algebra2:dets#элементарные_свойства_определителя главный член)) определителя, т.е. произведение элементов его главной диагонали:
$$
F(x) \equiv 1\cdot (2-x)\times \dots \times (n+1-x) + \dots \ ,
$$
где многоточия скрывают все оставшиеся слагаемые полного разложения определителя и имеют степени меньшие степени выделенного слагаемого. Выделяем из этого слагаемого степень $ x_{} $:
$$
F(x) \equiv (-1)^n x^n + \dots \ .
$$
Мы получили оценку степени $ F(x)_{} $ вместе с выражением для его старшего коэффициента.
**Ответ.** $ (-1)^{n} (x-1)\times \dots \times (x-n) $.
!!П!! **Пример.** Вычислить определитель
$$D=\left|\begin{array}{cccc}
0&x&y&z\\
x&0&y&z\\
y&z&0&x\\
z&y&x&0
\end{array}\right|.$$
**Решение.** Если к первому столбцу прибавить остальные, то обнаружится, что определитель делится на $ x+y+z $; если к первому столбцу прибавить второй и вычесть третий и четвертый, то выделится множитель $ y+z-x $; если к первому столбцу прибавить третий и вычесть второй и четвертый, то выделится множитель $ x-y+z $; наконец, если к первому столбцу прибавить четвертый и вычесть второй и третий, то выделится множитель $ x+y-z $. Считая $ x,y,z $ независимыми переменными, заключаем, что все эти четыре множителя попарно взаимно просты, и значит, определитель --- как полином от $ x,y,z $ --- делится на их произведение $ (x+y+z)(y+z-x)(x-y+z)(x+y-z) $.
Это произведение содержит член $ z^4 $ с коэффициентом $ (-1) $, а сам определитель содержит тот же член с коэффициентом $ +1 $. Следовательно,
$$
D=-(x+y+z)(y+z-x)(x-y+z)(x+y-z)
=x^4+y^4+z^4-2x^2y^2-2x^2z^2-2y^2z^2 \ . $$
♦
=== Метод рекуррентных соотношений==
Для понимания материалов этого пункта рекомендуется ознакомиться с разделом ((:recurr "Разностное уравнение и рекуррентная последовательность"))
.
Основная идея метода заключается в том, что некоторые определители можно свести к вычислению определителей, имеющих аналогичный вид, но меньший порядок. Если удается установить вид этой зависимости в виде явной формулы, то эта формула --- последовательным ее применением --- позволит нам "спуститься" к определителям малых порядков.
!!П!! **Пример.** Вычислить определитель
$$D_n=\left|\begin{array}{ccccc}
a_1&x&x&\dots&x\\
x&a_2&x&\dots&x\\
x&x&a_3&\dots&x\\
\vdots&&&\ddots&\vdots\\
x&x&x&\dots&a_n
\end{array}\right|.$$
**Решение.** Представив элемент в правом нижнем углу в виде $ a_n=x+(a_n-x) $, можем определитель $ D_n $ разбить на сумму двух определителей:
$$D_n=\left|\begin{array}{ccccc}
a_1&x&x&\dots&x\\
x&a_2&x&\dots&x\\
x&x&a_3&\dots&x\\
\vdots&&&\ddots&\vdots\\
x&x&x&\dots&x
\end{array}\right|+\left|\begin{array}{ccccc}
a_1&x&x&\dots&0\\
x&a_2&x&\dots&0\\
x&x&a_3&\dots&0\\
\vdots&&&\ddots&\vdots\\
x&x&x&\dots&a_n-x
\end{array}\right|.$$
В первом определителе последний столбец вычтем из остальных, а второй определитель разложим по последнему столбцу:
$$D_n=x(a_1-x)(a_2-x)\times\dots\times(a_{n-1}-x)+(a_n-x)D_{n-1}\ .$$
Это и есть рекуррентное соотношение. Подставляя в него аналогичное выражение для
$ D_{n-1} $, найдем
$$\begin{array}{l}
D_n=x(a_1-x)(a_2-x)\times\dots\times(a_{n-1}-x)+\\
+x(a_1-x)(a_2-x)\times\dots\times(a_{n-2}-x)(a_n-x)+D_{n-2}(a_{n-1}-x)(a_n-x).
\end{array}$$
Повторяя то же рассуждение $ n-1 $ раз и замечая, что $ D_1=a_1=x+(a_1-x) $, найдем
$$\begin{array}{l}
D_n=x(a_1-x)(a_2-x)\dots(a_{n-1}-x)+x(a_1-x)\times\dots\times(a_{n-2}-x)(a_n-x)+\dots+\\
+x(a_2-x)\times\dots\times(a_n-x)+(a_1-x)(a_2-x)\times\dots\times(a_n-x)=\\
\displaystyle
=x(a_1-x)(a_2-x)\times\dots\times(a_n-x)\left( \frac{1}{x}+\frac{1}{a_1-x}+\dots+\frac{1}{a_n-x}\right).
\end{array}$$
♦
!!?!! Вычислить определитель
$$\left|\begin{array}{ccccc}
a_1b_1&a_1b_2&a_1b_3&\dots&a_1b_n\\
a_1b_2&a_2b_2&a_2b_3&\dots&a_2b_n\\
a_1b_3&a_2b_3&a_3b_3&\dots&a_3b_n\\
\vdots&&&&\vdots\\
a_1b_n&a_2b_n&a_3b_n&\dots&a_nb_n
\end{array}\right|.$$
**Ответ.** $ \displaystyle a_1b_n\prod_{j=1}^{n-1}(a_{j+1}b_j-a_jb_{j+1}) $ .
!!П!! **Пример.** Вычислить определитель
$$D_n=\left|\begin{array}{ccccc}
a_1&x&x&\dots&x\\
y&a_2&x&\dots&x\\
y&y&a_3&\dots&x\\
\vdots&&&\ddots&\vdots\\
y&y&y&\dots&a_n
\end{array}\right|.$$
**Решение** начинается тем же приемом, что и в предыдущем примере:
$$ D_n= \left|\begin{array}{ccccc}
a_1&x&x&\dots&x\\
y&a_2&x&\dots&x\\
y&y&a_3&\dots&x\\
\vdots&&&\ddots&\vdots\\
y&y&y&\dots&x
\end{array}\right|+(a_n-x)D_{n-1}=x(a_1-y)(a_2-y)\times \dots \times (a_{n-1}-y)+(a_n-x)D_{n-1} \ .
$$
Можно было бы идти по проторенному пути и "разделывать" определитель $ D_{n-1} $ с использованием уже полученной формулы. Имеется, однако, более эффективный прием. Заметим, что начальный определитель симметричен относительно вхождения параметров $ x_{} $ и $ y_{} $, и эта симметрия должна проявляться в окончательном ответе. Следовательно, наряду с полученным выражением, будет справедливо и следующее:
$$
D_n=y(a_1-x)(a_2-x)\times \dots \times (a_{n-1}-x)+(a_n-y)D_{n-1} \ ,
$$
произведенное перестановкой параметров $ x \leftrightarrow y $. В результате мы получаем систему уравнений для определения двух неизвестных величин $ D_{n} $ и $ D_{n-1} $. Решаем эту систему относительно $ D_n $ (например, по ((:algebra2/linearsystems/cramert формулам Крамера))):
$$ D_n = \frac{\displaystyle y\prod_{k=1}^n(a_k-x)-x\prod_{k=1}^n(a_k-y)}{y-x} \ . $$
♦
Прием, позволивший решить последний пример, можно отнести к случаю "удачно заметил" (свойство симметрии) --- но, повторюсь, универсального способа вычисления определителей, зависящих от параметров, не существует.
В примере следующего пункта метод рекуррентных соотношений комбинируется с методом ((#выделение_линейных_множителей выделения линейных множителей)).
====Определитель Вандермонда==
!!§!! Подробнее о матрице, определителе Вандермонда и их применении
☞
((:algebra2:vander ЗДЕСЬ)).
!!П!! **Пример.** Вычислить определитель Вандермонда
$$
V(x_1,\dots,x_n)=
\left|\begin{array}{ccccc}
1 &x_1&x_1^2&\ldots&x_1^{n-1}\\
1 &x_2&x_2^2&\ldots&x_2^{n-1}\\
\vdots& &&& \vdots\\
1 &x_n&x_n^2&\ldots&x_n^{n-1}
\end{array}\right|_{n\times n}
$$
**Решение.** Поясним идею для случая $ n=4 $. Выражение для $ V(x_1,x_2,x_3,x_4) $ --- если его формально разложить ((:algebra2:det4x4 по общей формуле)) --- будет ((:polynomial#полином_нескольких_переменных полиномом)) относительно своих переменных. Рассмотрим его как полином от переменной $ x_4 $, которую --- для удобства --- временно переобозначим через $ x $:
$$
\tilde V(x)=\left|\begin{array}{llll}
1 &x_1&x_1^2&x_1^3\\
1 &x_2&x_2^2&x_2^3\\
1 &x_3&x_3^2&x_3^3\\
1 &x&x^2&x^3\\
\end{array}\right| \ ;
$$
оставшиеся переменные будем считать параметрами.
Если подставить в этот определитель $ x=x_1 $, то определитель обратится в нуль (как имеющий одинаковые строки см. свойство
3
☞
((algebra2:dets#элементарные_свойства_определителя ЗДЕСЬ))). Аналогичные рассуждения верны для $ x=x_2 $ и $ x=x_3 $. Таким образом, полином $ \tilde V(x) $ имеет корни $ x_1,x_2,x_3 $,
а его степень --- если разложить по последней строке --- не превышает $ 3 $. Следовательно, этот полином должен иметь следующее ((:polynomial#основная_теорема_высшей_алгебры разложение на линейные множители)):
$$
\tilde V(x) \equiv A(x-x_1)(x-x_2)(x-x_3) \ ;
$$
при этом константа $ A $ зависит только от $ x_1, x_2,x_3 $. Выражение для нее можно найти, если сообразить, что она является ((:polynomial#общая_информация старшим коэффициентом)) полинома $ \tilde V(x) $, т.е. коэффициентом при степени $ x^3 $. Этот коэффициент можно "извлечь" из исходного определителя --- это ((algebra2:dets#миноры_и_алгебраические_дополнения алгебраическое дополнение)) элемента определителя, стоящего в правом нижнем углу, т.е.
$$
\left|\begin{array}{lll}
1 &x_1&x_1^2\\
1 &x_2&x_2^2\\
1 &x_3&x_3^2
\end{array}\right| \ .
$$
Но этот определитель --- тот же определитель Вандермонда, только порядка меньшего исходного. Возвращая переменной $ x $ ее исходное значение, получаем рекуррентное соотношение:
$$ V(x_1,x_2,x_3,x_4)\equiv V(x_1,x_2,x_3) (x_4-x_1)(x_4-x_2)(x_4-x_3) \ . $$
Раскладываем определитель в правой части по той же схеме:
$$ V(x_1,x_2,x_3) \equiv \left|\begin{array}{ll}
1 &x_1\\
1 &x_2
\end{array}\right| (x_3-x_1)(x_3-x_2) \equiv (x_3-x_1)(x_3-x_2)(x_2-x_1) \ .
$$
Таким образом,
$$
V(x_1,x_2,x_3,x_4)=
$$
$$
=(x_2-x_1)(x_3-x_1)(x_3-x_2)(x_4-x_1)(x_4-x_2)(x_4-x_3) \ .
$$
А в общем случае получаем ответ
$$ V(x_1,\dots,x_n)= \prod_{1\le j < k \le n} (x_k-x_j)\ . $$
♦
====Определитель трёхдиагональной матрицы==
Более сложный пример применения метода дает задача вычисления определителя ((:algebra2#ленточная трехдиагональной матрицы)), представленного в следующем виде (**определитель Якоби**):
$$
{\mathfrak J}_n =
\left|\begin{array}{ccccccc}
a_1 &b_1&0&0& \dots & 0 & 0\\
-c_2 &a_2&b_2&0& \dots & 0 & 0\\
0 &-c_3&a_3&b_3& \dots & 0 & 0\\
\vdots &&& &\ddots&& \vdots \\
0 &0&0&0& \dots & a_{n-1} & b_{n-1}\\
0 &0&0&0& \dots & -c_n & a_{n}
\end{array}\right|_{n\times n} \ .
$$
Формальное вычисление этого определителя (в соответствии с ((algebra2:dets#определение определением))) даст
((:polynomial#полином_нескольких_переменных полином)) по $ a_1,\dots,a_n,b_1,\dots,b_{n-1},c_2,\dots,c_n $, линейный
по каждой из этих переменных. Если разложить $ {\mathfrak J}_n $ по последней строке, то
получим:
$$
\begin{matrix}
{\mathfrak J}_n&=&a_n{\mathfrak J}_{n-1}+b_{n-1}c_n{\mathfrak J}_{n-2}
=a_n(a_{n-1}{\mathfrak J}_{n-2}+b_{n-2}c_{n-1}{\mathfrak J}_{n-3})+
b_{n-1}c_n{\mathfrak J}_{n-2}= \\
&=&(a_na_{n-1}+b_{n-1}c_n){\mathfrak J}_{n-2}+a_nb_{n-2}c_{n-1}{\mathfrak J}_{n-3}=
\dots
\end{matrix}
$$
!!П!! **Пример.**
$ {\mathfrak J}_2=a_1a_2+b_1c_2 $ ,
$ {\mathfrak J}_3=a_1a_2a_3+a_1b_2c_3+b_1c_2a_3 $,
$$
{\mathfrak J}_5=a_1a_2a_3a_4a_5+b_1c_2a_3a_4a_5+a_1b_2c_3a_4a_5+a_1a_2b_3c_4a_5
+a_1a_2a_3b_4c_5+b_1c_2b_3c_4a_5+b_1c_2a_3b_4c_5+a_1b_2c_3b_4c_5 \ .
$$
!!Т!! **Теорема.** Значение $ {\mathfrak J}_n $ равно сумме главного члена $ a_1a_2\times \dots \times a_{n} $ и всевозможных произведений, получающихся из него заменой одной или нескольких пар соседних множителей $ a_ja_{j+1} $ на $ b_jc_{j+1} $.
Частный случай определителя Якоби --- ((:algebra2:dets#континуант континуант)):
$$
Q_n(x_1,x_2,\dots,x_{n})
=
\left|\begin{array}{ccccccc}
x_1 &1&0&0& \dots & 0 & 0\\
-1 &x_2&1&0& \dots & 0 & 0\\
0 &-1&x_3&1& \dots & 0 & 0\\
\vdots &&& &\ddots&&\vdots \\
0 &0&0&0& \dots & x_{n-1} & 1\\
0 &0&0&0& \dots & -1 & x_{n}
\end{array}\right|_{n\times n}
$$
!!Т!! **Теорема.** //Континуант равен сумме произведения// $ x_1\cdot x_2 \times \dots \times x_n $ //и всевозможных произведений, получающихся из него вычеркиванием пар соседних множителей// (//и добавлением// $ 1 $ //в случае четного// $ n $).
!!П!! **Пример.**
$$
\begin{array}{lcl}
Q_2(x_1,x_2)&=&x_1x_2+1 \ , \\
Q_3(x_1,x_2,x_3)&=& x_1x_2x_3+x_3+x_1 \ , \\
Q_6(x_1,x_2,x_3,x_4,x_5,x_6)&=&x_1x_2x_3x_4x_5x_6+\\
&&+x_3x_4x_5x_6
+x_1x_4x_5x_6+ x_1x_2x_5x_6+ x_1x_2x_3x_6+x_1x_2x_3x_4+ \\
&&+x_5x_6+x_1x_6+x_1x_2+x_1x_4+x_3x_4+x_3x_6+1 .
\end{array}
$$
Исследуем еще один частный случай определителя Якоби --- при одинаковых элементах на диагоналях
$$a_1=\dots=a_n = a, \ b_1=\dots=b_{n-1} = b, \
c_2=\dots=c_n = c \ ; $$
таким образом:
$$
{\mathfrak J}_n=
\left|\begin{array}{ccccccc}
a &b&0&0& \dots & 0 & 0\\
c &a&b&0& \dots & 0 & 0\\
0 &c&a&b& \dots & 0 & 0\\
\vdots &&& &\ddots&& \vdots \\
0 &0&0&0& \dots & a & b\\
0 &0&0&0& \dots & c & a
\end{array}\right|_{n\times n}
\ .
$$
В этом случае уравнение, связывающее определители трех последовательных порядков, принимает вид:
$$ {\mathfrak J}_n=a{\mathfrak J}_{n-1}-bc{\mathfrak J}_{n-2} \ .$$
Оно может быть решено применением ((:recurr#идея_решения общего приема решения линейного разностного уравнения)).
!!П!! **Пример.** Вычислить
$$
\left|\begin{array}{cccccc}
2 &2&0& \dots & 0 & 0\\
1 & 2 &2& \dots & 0 & 0\\
0 &1&2& \dots & 0 & 0\\
\vdots && \ddots &\ddots&& \vdots\\
0 &0&0& \dots & 2 & 2\\
0 &0&0& \dots & 1 & 2
\end{array}\right|_{n\times n} \ .
$$
**Решение.** Разностное уравнение имеет вид
$ {\mathfrak J}_n=2{\mathfrak J}_{n-1}-2{\mathfrak J}_{n-2} $.
Cтроим соответствующее ему характеристическое уравнение и находим его корни: $ \lambda_{1,2}=1 \pm \mathbf i $. Поскольку они различны, решение разностного уравнения ищем в виде
$$ C_1 (1+\mathbf i )^n+C_2 (1-\mathbf i)^n \ .$$
Для определения констант $ C_1 $ и $ C_2 $
вычислим определители первого и второго порядков: $ {\mathfrak J}_1=2,{\mathfrak J}_2=2 $.
$$
\left\{
\begin{array}{llll}
2&=&C_1(1+\mathbf i)&+C_2(1+\mathbf i), \\
2&=&C_1(1+\mathbf i)^2&+C_2(1+\mathbf i)^2
\end{array}
\right. \quad \Rightarrow \quad C_1=\frac{1-\mathbf i}{2},\ C_2=\frac{1+\mathbf i}{2}
$$
**Ответ.**
$ {\mathfrak J}_n=(1+\mathbf i)^{n-1}+(1-\mathbf i)^{n-1} $.
Хотя исходный определитель имеет явно вещественное значение, ответ, тем не менее, получился __мнимым__. Объяснение этого "парадокса"
☞
((:recurr#идея_решения ЗДЕСЬ)).
====Ганкелевы полиномы==
**Ганкелева матрица** порядка $ k_{} $ --- это квадратная матрица вида
$$
\left(\begin{array}{llllll}
\color{Brown}c_0 & \color{Blue}c_1 & \color{Green}c_2 & \color{Violet}c_3 & \dots & c_{k-1} \\
\color{Blue}c_1 & \color{Green}c_2 & \color{Violet}c_3 & c_4 & \dots & c_k \\
\color{Green}c_2 & \color{Violet}c_3 & c_4 & &\dots & c_{k+1} \\
\color{Violet}c_3 & c_4 & & & & \\
\vdots & & & \ddots & \vdots \\
c_{k-1} & c_{k} & c_{k+1} & &\dots & c_{2k-2}
\end{array}
\right)_{k\times k}= \left[ c_{j+k}\right]_{j,k=0}^{k-1} \ .
$$
Элементы числовой последовательности
$$ \{c\}= c_0,c_1,\dots, c_{2k-2},\dots $$
называются **образующими ганкелевой матрицы**.
Определитель ганкелевой матрицы порядка $ k $ будем обозначать $ H_{k} $.
Если в ганкелевой матрице порядка $ k+1 $ заменить последнюю строку на $ \left[ 1,x,x^2,\dots,x^{k} \right] $, то определитель полученной матрицы
$$
\mathcal H_k(x) =
\left|
\begin{array}{lllll}
c_0 & c_1 & c_2 & \ldots & c_{k} \\
c_1 & c_2 & c_3 &\ldots & c_{k+1} \\
\vdots & & & \ddots& \vdots \\
c_{k-1} & c_{k} & c_{k+1} & \ldots & c_{2k-1} \\
1 & x & x^2 & \ldots & x^{k}
\end{array} \right|_{(k+1) \times (k+1)}
$$
будет полиномом по $ x_{} $; он называется **ганкелевым полиномом k-го порядка** (**порожденным последовательностью** $ \{c\} $). Его каноническое представление имеет коэффициентами числовые определители $ k_{} $-го порядка:
$$
\mathcal H_k(x)\equiv x^{k}
\left|
\begin{array}{lllll}
c_0 & c_1 & \ldots & c_{k-2} & c_{k-1} \\
c_1 & c_2 & \ldots & c_{k-1} & c_{k} \\
\vdots & & \ddots& & \vdots \\
c_{k-1} & c_{k} & \ldots & c_{2k-3} & c_{2k-2}
\end{array} \right|- x^{k-1}
\left|
\begin{array}{lllll}
c_0 & c_1 & \ldots & c_{k-2} & c_{k} \\
c_1 & c_2 & \ldots & c_{k-1} & c_{k+1} \\
\vdots & & \ddots& & \vdots \\
c_{k-1} & c_{k} & \ldots & c_{2k-3} & c_{2k-1}
\end{array} \right|+
$$
$$
+ \dots
+(-1)^k
\left|
\begin{array}{lllll}
c_1 & c_2 & \ldots & c_{k-1} & c_{k} \\
c_2 & c_3 & \ldots & c_{k} & c_{k+1} \\
\vdots & & \ddots& & \vdots \\
c_{k} & c_{k+1} & \ldots & c_{2k-2} & c_{2k-1}
\end{array} \right| \ .
$$
Коэффициенты будем обозначать $ h_{kj} $; таким образом
$$
\mathcal H_k(x)\equiv h_{k0} x^k +h_{k1} x^{k-1} +\dots + h_{kk} \quad \mbox{ при } \quad h_{k0}= H_k \ ;
$$
Коэффициент $ h_{k0} $ может обращаться в нуль, так что степень ганкелевого полинома $ k_{} $-го порядка может оказаться меньшей $ k_{} $.
!!Т!! **Теорема [Якоби, Йоахимшталь].**[[Йоахимшталь Фердинанд (Joachimsthal Ferdinand, 1818-1861) --- немецкий математик, ученик Якоби. Биография
☞
((http://www-history.mcs.st-andrews.ac.uk/history/Biographies/Joachimsthal.html ЗДЕСЬ)).]] //Любые три ганкелевых полинома// $ \mathcal H_{k-2}(x), \mathcal H_{k-1}(x), \mathcal H_{k}(x) $
//связаны тождеством//
$$
H_k^2\mathcal H_{k-2}(x) + \left(H_kh_{k-1,1}-H_{k-1}h_{k1}-H_kH_{k-1}x\right)\mathcal H_{k-1}(x) + H_{k-1}^2 \mathcal H_{k}(x) \equiv 0 \, .
$$
Это тождество позволяет организовать вычисление ганкелевого полинома, рекурсивное по порядку этого полинома:
$ \mathcal H_{k}(x) $ вычисляется через ранее вычисленные $ \mathcal H_{k-1}(x) $ и $ \mathcal H_{k-2}(x) $. Подробнее
☞
((:algebra2/hankel/jjidentity ЗДЕСЬ)).
=== Представление определителя в виде суммы определителей ===
!!П!! **Пример.** Вычислить определитель
$$D_n=\left|\begin{array}{cccc}
a_1+b_1&a_1+b_2&\dots&a_1+b_n\\
a_2+b_1&a_2+b_2&\dots&a_2+b_n\\
\dots&&&\dots\\
a_n+b_1&a_n+b_2&\dots&a_n+b_n
\end{array}\right|.$$
**Решение.** Определитель раскладывается по первой строке на два определителя, каждый из них по второй строке снова раскладывается на два определителя и т.д. Дойдя до последней строки, получим $ 2^n $ определителей.
Если при каждом разложении за первые слагаемые принимать числа $ a_i $, а за вторые --- числа $ b_j $, то строки полученных определителей будут либо вида $ (a_i,a_i,\dots,a_i) $, либо вида $ (b_1,b_2,\dots,b_n) $. Две строки первого типа пропорциональны, а второго типа равны. При $ n>2 $ в каждый получившийся определитель попадут по крайней мере две строки одного типа, и он обратится в нуль. Таким образом,
$$D_n=0 \ npu \ n>2,\ D_1=a_1+b_1,\quad D_2=\left|\begin{array}{cc}
a_1&a_1\\
b_1&b_2
\end{array}\right|+\left|\begin{array}{cc}
b_1&b_2\\
a_2&a_2
\end{array}\right|=(a_1-a_2)(b_2-b_1).$$
♦
!!?!! Вычислить определитель методом представления его в виде суммы определителей
$$\left|\begin{array}{ccccc}
x_1&a_1b_2&a_1b_3&\dots&a_1b_n\\
a_2b_1&x_2&a_2b_3&\dots&a_2b_n\\
a_3b_1&a_3b_2&x_3&\dots&a_3b_n\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
a_nb_1&a_nb_2&a_nb_3&\dots&x_n
\end{array}\right|.$$
**Ответ.** $$(x_1-a_1b_1)(x_2-a_2b_2)\times \dots \times (x_n-a_nb_n)
\times
$$
$$
\times \left(1+\frac{a_1b_1}{x_1-a_1b_1}+\frac{a_2b_2}{x_2-a_2b_2}+\dots+\frac{a_nb_n}{x_n-a_nb_n}\right) \ .$$
=== Увеличение порядка определителя ==
!!П!! **Пример.** Вычислить определитель
$$
\det \left[ s_{j+k}x-s_{j+k+1} \right]_{j,k=0}^{n-1} = \left| \begin{array}{llll}
s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} \\
s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} \\
\dots & & & \dots \\
s_{n-1}x-s_{n} & s_{n}x-s_{n+1} & \dots & s_{2n-2}x-s_{2n-1}
\end{array} \right|_{n\times n}
$$
при заданных числовых значениях $ s_0,s_1,\dots,s_{2n-1} $.
**Решение.** Здесь каждый элемент определителя зависит от переменной $ x $. Как уже отмечалось в ((#приемы_вычисления_определителей_зависящих_от_параметров начале раздела)), применение метода Гаусса к вычислению такого определителя неэффективно. Сформируем новый определитель порядка $ n+1 $, дополнив исходный одной строкой и одним столбцом:
$$
\left| \begin{array}{llllc}
s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 0 \\
s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 0 \\
\dots & & & \dots & \dots \\
s_{n-1}x-s_{n } & s_{n}x-s_{n+1} & \dots & s_{2n-2}x-s_{2n-1}& 0 \\
s_n & s_{n+1} & \dots & s_{2n-1}& 1
\end{array} \right|_{(n+1)\times (n+1)} \ .
$$
Разложение нового определителя по последнему столбцу приведет к исходному определителю. С другой стороны, выполним элементарные преобразования нового определителя: прибавим последнюю строку к предпоследней:
$$
\left| \begin{array}{llllc}
s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 0 \\
s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 0 \\
\dots & & & \dots & \dots \\
s_{n-1}x & s_{n}x & \dots & s_{2n-2}x& 1 \\
s_n & s_{n+1} & \dots & s_{2n-1}& 1
\end{array} \right|_{(n+1)\times (n+1)} \ ;
$$
вынесем общий множитель:
$$
x\left| \begin{array}{llllc}
s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 0 \\
s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 0 \\
\dots & & & \dots & \dots \\
s_{n-1} & s_{n} & \dots & s_{2n-2}& 1/x \\
s_n & s_{n+1} & \dots & s_{2n-1}& 1
\end{array} \right|_{(n+1)\times (n+1)} \ ;
$$
предпоследнюю строку прибавим к предыдущей:
$$
x\left| \begin{array}{llllc}
s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 0 \\
s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 0 \\
\dots & & & \dots & \dots \\
s_{n-2}x & s_{n-1}x & \dots & s_{2n-3}x& 1/x \\
s_{n-1} & s_{n} & \dots & s_{2n-2}& 1/x \\
s_n & s_{n+1} & \dots & s_{2n-1}& 1
\end{array} \right|_{(n+1)\times (n+1)} \ ;
$$
и снова вынесем общий множитель:
$$
x^2\left| \begin{array}{lllll}
s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 0 \\
s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 0 \\
\dots & & & \dots & \dots \\
s_{n-2} & s_{n-1} & \dots & s_{2n-3}& 1/x^2 \\
s_{n-1} & s_{n} & \dots & s_{2n-2}& 1/x \\
s_n & s_{n+1} & \dots & s_{2n-1}& 1
\end{array} \right|_{(n+1)\times (n+1)} \ .
$$
Продолжим процесс по аналогии, в конце концов получим
$$
x^n\left| \begin{array}{lllll}
s_0x-s_1&s_1x-s_2&\dots& s_{n-1}x-s_{n} & 1/x^n \\
s_1x-s_2&s_2x-s_3&\dots& s_{n}x-s_{n+1} & 1/x^{n-1} \\
\dots & & & \dots & \dots \\
s_{n-2}x & s_{n-1}x & \dots & s_{2n-3}x& 1/x^2 \\
s_{n-1} & s_{n} & \dots & s_{2n-2}& 1/x \\
s_n & s_{n+1} & \dots & s_{2n-1}& 1
\end{array} \right|_{(n+1)\times (n+1)} \ ,
$$
и внесем множитель в последний столбец:
$$
\left| \begin{array}{lllll}
s_0&s_1&\dots&s_{n-1}&1 \\
s_1&s_2&\dots&s_n& x \\
\vdots & && \vdots & \vdots \\
s_{n}&s_{n+1}&\dots&s_{2n-1}&x^{n}
\end{array} \right|_{(n+1)\times (n+1)} \ .
$$
Получившийся определитель имеет порядок больший исходного. Тем не менее, выражения его элементов стали проще с той точки зрения, что переменная оказалась "выметена на край" определителя. Если разложить теперь определитель по последнему столбцу, то коэффициентами при степенях $ x $ становятся __числовые__ определители, для вычисления которых уже можно применять метод Гаусса.
♦
Разобранный прием, на первый взгляд, кажется не вполне естественным; он практически не упоминается в литературе. Тем не менее, он неявно используется в двух методах вычисления ((:algebra2:charpoly#методы_вычисления_характеристического_полинома характеристического полинома матрицы)).
=== Интерполяция ==
Для понимания материалов настоящего раздела рекомендуется ознакомиться с разделом ((:interpolation "ИНТЕРПОЛЯЦИЯ")).
.
Впервые о методе прочитал в ((#источники [1])). В литературе кое-где упоминается --- в основном, в связи с вычислением ((:algebra2:charpoly характеристического полинома матрицы)).
Можно считать излагаемый ниже метод обобщением приведенного выше метода ((#выделение_линейных_множителей выделения линейных множителей)): если матрица имеет полиномиальную зависимость от параметра (параметров), то угадать корни ее определителя --- также полинома от этого параметра --- удается не всегда, а вот его значения при конкретных величинах параметра (параметров) всегда можно вычислить.
Попробуем решить пример, с которого ((#приемы_вычисления_определителей_зависящих_от_параметров начинается настоящий раздел)).
!!П!! **Пример.** Вычислить
$$ \det A(\alpha)=
\left|
\begin{array}{cccc}
\alpha+1 &\alpha^2+1 &\alpha^2-1 &\alpha \\
\alpha^2+\alpha+1 & \alpha^2-\alpha+1 & \alpha^2 & 1 \\
2\,\alpha+1 &\alpha^2+2 & \alpha & \alpha^2-1 \\
2\,\alpha & 2\, \alpha^2+2\,\alpha+1 & \alpha^2-\alpha-1 & \alpha+1
\end{array}
\right| \ .
$$
**Решение.** Поскольку каждый элемент определителя является ((:polynomial полиномом)), то, на основании ((algebra2:dets#определение определения определителя как суммы произведений его элементов)), величина определителя также должна быть полиномом по $ \alpha_{} $. Обозначим этот полином через $ F(\alpha) $. Таким образом, задача сводится к вычислению степени $ \deg F $ этого полинома и его коэффициентов. Для решения первой задачи формируем новый определитель, путем вытаскивания из элементов исходного определителя их старших мономов:
$$
\left|
\begin{array}{cccc}
\alpha &\alpha^2 &\alpha^2 &\alpha \\
\alpha^2 & \alpha^2 & \alpha^2 & 1 \\
2\,\alpha &\alpha^2 & \alpha & \alpha^2 \\
2\,\alpha & 2\, \alpha^2 & \alpha^2 & \alpha
\end{array}
\right| \ .
$$
Если этот определитель не равен нулю тождественно по $ \alpha_{} $, то его старший моном совпадает со старшим мономом $ F(\alpha) $. Новый определитель также зависит от $ \alpha_{} $, но характер этой зависимости становится менее сложным, чем у исходного, и для его вычисления можно использовать различные упрощающие соображения. Например, можно вынести
общие множители элементов первого, второго и третьего столбцов (см. свойство
4
☞
((:algebra2:dets#элементарные_свойства_определителя ЗДЕСЬ)) )
$$
=\alpha\cdot \alpha^2 \cdot \alpha
\left|
\begin{array}{cccc}
1 &1 & \alpha &\alpha \\
\alpha & 1 & \alpha & 1 \\
2 &1 & 1 & \alpha^2 \\
2 & 2 & \alpha & \alpha
\end{array}
\right| =
$$
Далее, вычитаем из последней строки первую, умноженную на $ 2_{} $:
$$
=\alpha^4
\left|
\begin{array}{cccc}
1 &1 & \alpha &\alpha \\
\alpha & 1 & \alpha & 1 \\
2 &1 & 1 & \alpha^2 \\
0 & 0 & -\alpha & -\alpha
\end{array}
\right| =-\alpha^5
\left|
\begin{array}{cccc}
1 &1 & \alpha &\alpha \\
\alpha & 1 & \alpha & 1 \\
2 &1 & 1 & \alpha^2 \\
0 & 0 & 1 & 1
\end{array}
\right|
$$
Теперь вычтем из четвертого столбца третий:
$$
=-\alpha^5
\left|
\begin{array}{cccc}
1 &1 & \alpha & 0 \\
\alpha & 1 & \alpha & 1-\alpha \\
2 &1 & 1 & \alpha^2 -1 \\
0 & 0 & 1 & 0
\end{array}
\right|
$$
и разложим определитель по последней строке:
$$
= \alpha^5
\left|
\begin{array}{ccc}
1 &1 & 0 \\
\alpha & 1 & 1-\alpha \\
2 &1 & \alpha^2 -1 \\
\end{array}
\right| \ .
$$
Поскольку нас интересует только лишь старший моном этого определителя, в элементах последнего столбца оставляем старшие мономы:
$$
\alpha^5
\left|
\begin{array}{ccc}
1 &1 & 0 \\
\alpha & 1 & -\alpha \\
2 &1 & \alpha^2
\end{array}
\right| =
\alpha^6
\left|
\begin{array}{ccc}
1 &1 & 0 \\
\alpha & 1 & -1 \\
2 &1 & \alpha
\end{array}
\right| \ .
$$
Этот определитель можно вычислить "вручную" (при этом, повторюсь, нас интересуют только лишь максимальные по степени $ \alpha_{} $ члены его разложения), получаем: $ - \alpha^8 $.
Итак, неизвестный полином $ F(\alpha) $ имеет степень $ 8_{} $. Для его определения у нас имеется представление этого полинома в форме определителя. При этом считается, что __числовые определители__ мы вычислять ((algebra2:dets#метод_приведения_к_треугольному_виду_(метод_Гаусса) умеем)). Будем искать полином $ F(\alpha) $ как решение ((:interpolation задачи интерполяции)). Зададим произвольные __числовые__ значения для $ \alpha_{} $ --- в количестве $ 9_{} $ штук (по числу коэффициентов полинома, требующих определения), вычислим соответствующие числовые определители, составим интерполяционную таблицу:
$$
\begin{array}{c|cccc}
\alpha & \alpha_1 & \alpha_2 & \dots & \alpha_9 \\ \hline
F & \det A (\alpha_1) &\det A (\alpha_2) & \dots & \det A (\alpha_9)
\end{array}
$$
и вычислим $ F(\alpha) $ по одному из методов вычисления ((:interpolation интерполяционного полинома)).
На виду лежат два соображения:
1.
имеет смысл в качестве чисел $ \alpha_j $ выбирать возможно минимальные по модулю;
2.
поскольку мы уже знаем величину одного из коэффициентов, имеет смысл выбрать --- из двух стандартных представлений интерполяционного полинома --- ((:interpolation#интерполяционный_полином_в_форме_ньютона форму Ньютона)) (последнее вычисление делать не придется, можно сократить число узлов интерполяции). Для настоящего примера:
$$
\begin{array}{c|rrrccccc}
\alpha & 0 & 1 & -1 & 2 & -2 & 3 & -3 & 4 \\ \hline
F & -4 & -4 & 24 &-222 & 734 & -9616 & 4388 & -98176
\end{array}
$$
**Ответ.** $ -\alpha^8-3\,\alpha^7+3\,\alpha^6-\alpha^5+23\,\alpha^4-7\,\alpha^3-11\,\alpha^2-3\,\alpha-4 $.
При решении примера настоящего пункта мы столкнулись со следующей задачей. Составим матрицу степеней полиномов, содержащихся в матрице $ A_{} $:
$$
B=\left(
\begin{array}{cccc}
1 &2 &2 &1 \\
2 &2 &2 & 0 \\
1 &2 &1 & 2 \\
1 & 2 & 2 & 1
\end{array}
\right) \ .
$$
Требуется выбрать по одному элементу из каждой строки и каждого столбца этой матрицы, так, чтобы получившаяся сумма стала максимальной:
$$
b_{1j_1}+b_{2j_2}+b_{3j_3}+b_{4j_4} \quad \mbox{ при различных } \quad \{ j_1,j_2,j_3,j_4\} \subset \{ 1,2,3,4 \} .
$$
Иными словами, после выбора какого-то кандидата в сумму, из матрицы вычеркиваются строка и столбец его содержащие, и дальнейший выбор осуществляется в оставшейся подматрице. Задача оказывается нетривиальной уже хотя бы потому, что "жадная стратегия" выбора --- когда на каждом шаге выбирается максимальный из оставшихся элементов --- не приводит к правильному ответу:
$$
B=\left(
\begin{array}{cc}
4 &3 \\
3 &1
\end{array}
\right) \quad \Rightarrow \quad 4+1 < 3 + 3 \ .
$$
Оказывается эта задача является примером известной в теории оптимизации **задачи о назначениях**[[assignment problem]].
**Задача.** Имеется $ n_{} $ работ, которые надо поручить $ n_{} $ работникам. Каждый работник может быть назначен только на одну работу, и каждая работа может быть поручена только одному работнику. Прибыль от труда работника под номером $ j_{} $ при выполнении работы под номером $ k_{} $ известна и равна $ b_{jk} $. Как распределить работы между работниками так, чтобы прибыль стала максимальной?
==Разные определители, встречающиеся в ресурсе==
===Определитель Коши==
$$\det \left[\frac{1}{a_j+b_k} \right]_{j,k=1}^n=
\left|\begin{array}{cccc}
\frac{1}{a_1+b_1} &\frac{1}{a_1+b_2}&\ldots&\frac{1}{a_1+b_n}\\
& & & \\
\frac{1}{a_2+b_1} &\frac{1}{a_2+b_2}&\ldots&\frac{1}{a_2+b_n}\\
& & & \\
\ldots & & & \ldots\\
\frac{1}{a_n+b_1} &\frac{1}{a_n+b_2}&\ldots&\frac{1}{a_n+b_n}
\end{array}\right|_{n\times n}\ .
$$
Рассматривается
☞
((:algebra2:dets:special_cases:vspom1 ЗДЕСЬ)).
===Определитель расстояний==
или определитель матрицы расстояний
$$
\det \left[ |P_jP_k|^2 \right]_{j,k=1}^m =\left|
\begin{array}{cccc}
0 & |P_1P_2|^2 & \dots & |P_1P_m|^2 \\
|P_1P_2|^2 & 0 & \dots & |P_2P_m|^2 \\
\vdots & & \ddots & \vdots \\
|P_1P_m|^2 & |P_2P_m|^2 & \dots & 0
\end{array}
\right| \quad npu \quad \{P_1,\dots,P_m\} \subset \mathbb R^n
$$
Рассматривается
☞
((:dets:geometry:ptolemy#матрица_расстояний ЗДЕСЬ)).
===Определители безымянные, но полезные==
$$
\left|\begin{array}{llllllll}
1 & \cos x_1 & \sin x_1 & \cos \, 2\, x_1 & \sin \, 2\, x_1 & \dots & \cos \, n\, x_1 & \sin \, n\, x_1 \\
1 & \cos x_2 & \sin x_2 & \cos \, 2\, x_2 & \sin \, 2\, x_2 & \dots & \cos \, n\, x_2 & \sin \, n\, x_2
\\
\dots & & & & & & & \dots \\
1 & \cos x_{2n+1} & \sin x_{2n+1} & \cos \, 2\, x_{2n+1} & \sin \, 2\, x_{2n+1} & \dots & \cos \, n\, x_{2n+1} & \sin \, n\, x_{2n+1}
\end{array}
\right| =
$$
$$
= 2^{2n^2} \prod_{0\le k < j \le 2n} \sin \frac{x_k-x_j}{2} \ .
$$
Рассматривается
☞
((:interpolation:dft#тригонометрическая_интерполяция1 ЗДЕСЬ)).
==Задачи==
☞
((:algebra2:dets:special_cases:problems ЗДЕСЬ)).
==Источники==
[1]. **Микеладзе Ш.Е.** //Решение численных уравнений.// Тбилиси.Мецниереба. 1965