Определитель | это... Что такое Определитель? (original) (raw)

Определи́тель (или детермина́нт) — одно из основных понятий линейной алгебры. Определитель матрицы является многочленом от элементов квадратной матрицы (то есть такой, у которой количество строк и столбцов равно). В общем случае матрица может быть определена над любым коммутативным кольцом, в этом случае определитель будет элементом того же кольца.

Определитель матрицы А обозначается как: det(A), |А| или Δ(A).

Содержание

1 Определение через разложение по первой строке
2 Определение через перестановки
3 Альтернативные методы вычисления
4 Свойства определителей
5 Алгоритмическая реализация
6 Специальные виды определителей
7 См. также
8 Примечания
9 Литература

Определение через разложение по первой строке

Схема расчета определителя матрицы $2 \times 2$ .

Для матрицы первого порядка детерминантом является сам единственный элемент этой матрицы:

$\Delta=\begin{vmatrix} a_{11}\end{vmatrix} = a_{11}$

Для матрицы $2 \times 2$ детерминант определяется как

$\Delta=\begin{vmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{vmatrix}=a_{11}a_{22}-a_{12}a_{21}$

Для матрицы $n \times n$ определитель задаётся рекурсивно:

$\Delta=\sum_{j=1}^n (-1)^{1+j} a_{1j}\bar M_j^1$ , где $\bar M_j^1$ — дополнительный минор к элементу $a_{1j}$ . Эта формула называется разложением по строке.

В частности, формула вычисления определителя матрицы $3 \times 3$ такова:

$\Delta = \begin{vmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{vmatrix} = a_{11}\begin{vmatrix} a_{22} & a_{23} \\ a_{32} & a_{33} \end{vmatrix}-a_{12}\begin{vmatrix} a_{21} & a_{23} \\ a_{31} & a_{33} \end{vmatrix}+a_{13}\begin{vmatrix} a_{21} & a_{22} \\ a_{31} & a_{32} \end{vmatrix} =$

$= a_{11}a_{22}a_{33} - a_{11}a_{23}a_{32} - a_{12}a_{21}a_{33}+ a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} - a_{13}a_{22}a_{31}$

Легко доказать, что при транспонировании определитель матрицы не изменяется (иными словами, аналогичное разложение по первому столбцу также справедливо, то есть даёт такой же результат, как и разложение по первой строке):

$\Delta=\sum_{i=1}^n (-1)^{i+1} a_{i1}\bar M_1^i$

Доказательство

Пусть $\tilde{\Delta}= \sum_{i=1}^n (-1)^{i+1} a_{i1}\bar M_1^i$ .

Докажем, что $\tilde{\Delta}=\Delta$ по индукции. Видно, что для матрицы $2 \times 2$ это верно:

$\tilde{\Delta_2}=\sum_{i=1}^n (-1)^{i+1} a_{i1}\bar M_1^i=a_{11}a_{22}-a_{21}a_{12}=\Delta_2$

Предполжим, что для матрицы порядка n−1 $\tilde\Delta_{n-1}=\Delta_{n-1}$ — верно.

$\tilde{\Delta_n}=\sum_{i=1}^n (-1)^{i+1} a_{i1}\bar M_1^i=a_{11}\bar M_1^1+\sum_{i=2}^n (-1)^{i+1} a_{i1}\bar M_1^i=a_{11}\bar M_1^1+\sum_{i=2}^n (-1)^{i+1} a_{i1}\sum_{j=2}^n(-1)^j a_{1j}\bar M_{1j}^{i1}=$

$=a_{11}\bar M_1^1+\sum_{i=2}^n\sum_{j=2}^n (-1)^{i+j+1} a_{i1}a_{1j}\bar M_{1j}^{i1}$

${\Delta_n}=\sum_{j=1}^n (-1)^{1+j} a_{1j}\bar M_j^1=a_{11}\bar M_1^1+\sum_{j=2}^n (-1)^{1+j} a_{1j}\bar M_j^1=a_{11}\bar M_1^1+\sum_{j=2}^n (-1)^{1+j} a_{1j}\sum_{i=2}^n(-1)^i a_{i1}\bar M_{j1}^{1i}=$

$=a_{11}\bar M_1^1+\sum_{j=2}^n\sum_{i=2}^n (-1)^{i+j+1} a_{1j}a_{i1}\bar M_{j1}^{1i}=\tilde{\Delta_n}$ ■

Также справедливо и аналогичное разложение по любой строке (столбцу):

$\Delta=\sum_{j=1}^n (-1)^{i+j} a_{ij}\bar M_j^i$

Доказательство

Пусть $\tilde{\Delta}= \sum_{j=1}^n (-1)^{i+j} a_{ij}\bar M_j^i$ .

Докажем, что $\tilde{\Delta}=\Delta$ по индукции. Видно, что для матрицы $2 \times 2$ это верно:

$\tilde{\Delta_2}=\sum_{j=1}^n (-1)^{i+j} a_{ij}\bar M_j^i=-a_{21}a_{12}+a_{22}a_{11}=\Delta_2$

Предположим, что для матрицы порядка n−1 $\tilde\Delta_{n-1}=\Delta_{n-1}$ — верно.

$\tilde{\Delta_n}=\sum_{j=1}^n (-1)^{i+j} a_{ij}\bar M_j^i=\sum_{j=1}^n (-1)^{i+j} a_{ij}\left(\sum_{k<j}(-1)^{1+k}a_{1k}\bar M_{jk}^{i1}+\sum_{k>j}(-1)^k a_{1k}\bar M_{jk}^{i1}\right)$

Соберём коэффициенты при $\bar M_{j_0k_0}^{i\,\,1}$ :

$j_0>k_0\colon\; (-1)^{i+j_0}a_{ij_0}(-1)^{1+k_0}a_{1k_0}+(-1)^{i+k_0}a_{ik_0}(-1)^{j_0}a_{1j_0}=(-1)^{i+j_0+k_0+1}(a_{ij_0}a_{1k_0}-a_{ik_0}a_{1j_0})=$

$=(-1)^{i+j_0+k_0+1}M_{j_0k_0}^{1\,\,i}$

$j_0<k_0\colon\; (-1)^{i+j_0}a_{ij_0}(-1)^{k_0}a_{1k_0}+(-1)^{i+k_0}a_{ik_0}(-1)^{j_0+1}a_{1j_0}=(-1)^{i+j_0+k_0+1}(a_{ik_0}a_{1j_0}-a_{ij_0}a_{1k_0})=$

$=(-1)^{i+j_0+k_0+1}M_{j_0k_0}^{1\,\,i}$

$\tilde{\Delta_n}=\sum_{j\ne k}(-1)^{i+j+k+1}M_{jk}^{1i}\bar M_{jk}^{1i}$

$\Delta=\sum_{j=1}^n (-1)^{1+j} a_{1j}\bar M_j^1=\sum_{j=1}^n (-1)^{1+j} a_{1j}\left(\sum_{k<j}(-1)^{i+k-1}a_{ik}\bar M_{jk}^{1i}+\sum_{k>j}(-1)^{i+k-2}a_{ik}\bar M_{jk}^{1i}\right)$

Соберём коэффициенты при $\bar M_{j_0k_0}^{i\,\,1}$ :

$j_0>k_0\colon\; (-1)^{1+j_0}a_{1j_0}(-1)^{i+k_0-1}a_{ik_0}+(-1)^{1+k_0}a_{1k_0}(-1)^{i+j_0-2}a_{ij_0} =(-1)^{j_0+i+k_0}(a_{1j_0}a_{ik_0}-a_{1k_0}a_{ij_0})=$

$=(-1)^{i+j_0+k_0+1}M_{j_0k_0}^{1\,\,i}$

$j_0<k_0\colon\; (-1)^{1+j_0}a_{1j_0}(-1)^{i+k_0-2}a_{ik_0}+(-1)^{1+k_0}a_{1k_0}(-1)^{i+j_0-1}a_{ij_0}= (-1)^{k_0+i+j_0}(a_{1k_0}a_{ij_0}-a_{1j_0}a_{ik_0})=$

$=(-1)^{i+j_0+k_0+1}M_{j_0k_0}^{1\,\,i}$

${\Delta_n}=\sum_{j\ne k}(-1)^{i+j+k+1}M_{jk}^{1i}\bar M_{jk}^{1i}=\tilde{\Delta_n}$ ■

Обобщением вышеуказанных формул является разложение детерминанта по Лапласу (Теорема Лапласа), дающее возможность вычислять определитель по любым k строкам (столбцам):

$\Delta=\sum_{1\leqslant j_1<\ldots<j_k\leqslant n} (-1)^{i_1+...+i_k+j_1+...+j_k} M_{j_1...j_k}^{i_1...i_k} \bar M_{j_1...j_k}^{i_1...i_k}$

Определение через перестановки

Для матрицы $n \times n$ справедлива формула:

$\Delta=\sum_{\alpha_1, \alpha_2, \ldots, \alpha_n} (-1)^{N(\alpha_1, \alpha_2, \ldots, \alpha_n)} \cdot a_{\alpha_11} \cdots a_{\alpha_nn}$ ,

где $\alpha_1, \alpha_2, ..., \alpha_n$ — перестановка чисел от 1 до , $N(\alpha_1, \alpha_2, ..., \alpha_n)$ — число инверсий в перестановке, суммирование идёт по всем возможным перестановкам порядка . Таким образом, в определитель войдёт слагаемых, которые также называют «членами определителя». Важно заметить, что во многих курсах линейной алгебры это определение даётся как основное.

Альтернативные методы вычисления

Метод конденсации Доджсона, основанный на рекурсивной формуле:

$\det(M) = \frac{\det(M_1^1)\det(M_k^k) - \det(M_1^k) \det(M_k^1)}{\det(M_{1,k}^{1,k})},$ где $M_1^1,M_k^k,M_1^k,M_k^1,M_{1,k}^{1,k}$ матрицы, получающиеся из исходной вычёркиванием соответствующих строк и столбцов.

Свойства определителей

Алгоритмическая реализация

Прямые методы вычисления определителя могут быть основаны непосредственно на его определении, как суммы по перестановкам, или на разложении Лапласа по определителям меньшего порядка. Однако такие методы очень неэффективны, так как требуют О(n!) операций для вычисления определителя -го порядка.
Один из более быстрых методов заключается в простой модификации метода Гаусса. Следуя методу Гаусса, произвольную матрицу можно привести к ступенчатому виду (Верхнетреугольная матрица), используя лишь две следующие операции над матрицей — перестановку двух строк и добавление к одной из строк матрицы другой строки, умноженной на произвольное число. Из свойств определителя следует, что вторая операция не изменяет определителя матрицы, а первая лишь меняет его знак на противоположный. Определитель матрицы, приведённой к ступенчатому виду, равен произведению элементов на её диагонали, так как она является треугольной, поэтому определитель исходной матрицы равен:
$\! \det A = (-1)^s \cdot \det A_{\mbox{ref}},$

где — число перестановок строк, выполненных алгоритмом, а $A_{\mbox{ref}}$ — ступенчатая форма матрицы , полученная в результате работы алгоритма. Сложность этого метода, как и метода Гаусса, составляет O(n^3) .

Определитель можно вычислить, зная LU-разложение матрицы. Если , где и — треугольные матрицы, то $\det A = (\det L)(\det U)$ . Определитель треугольной матрицы равен просто произведению её диагональных элементов.
Если доступен алгоритм, выполняющий умножение двух матриц порядка за время , где $M(n) \geqslant n^a$ , для некоторого , то определитель матрицы порядка может быть вычислен за время .[1] В частности это означает, что, используя для умножения матриц алгоритм Копперсмита — Винограда, определитель можно вычислить за время $O(n^{2.376})$ .

Специальные виды определителей

См. также

Примечания

↑ J. R. Bunch and J.E. Hopcroft. Triangular factorization and inversion by fast matrix multiplication, Mathematics of Computation, 28 (1974) 231—236.

Литература

В. А. Ильин, Э. Г. Позняк Линейная алгебра, М.: Наука — Физматлит, 1999.
Беклемишев Д. В. Курс аналитической геометрии и линейной алгебры. М.: Физматлит, 2000.