1941 lines
128 KiB
TeX
1941 lines
128 KiB
TeX
|
||
\section{Вычислительная линейная алгебра}
|
||
|
||
\subsection{Системы линейных уравнений и элементарные преобразования}\label{subsection_linear_systems}
|
||
\literature{[F], гл. IV, \S~4, п. 5; [K1], гл. 1, \S~3, пп. 1, 2.}
|
||
|
||
Пусть $R$~--- ассоциативное коммутативное кольцо с единицей. Мы будем
|
||
называть \dfn{системой линейных уравнений}\index{система линейных
|
||
уравнений} (над $R$) набор уравнений
|
||
вида
|
||
$$
|
||
\begin{array}{rcl}
|
||
a_{11}x_1+a_{12}x_2+\dots+a_{1n}x_n &=& b_1\\
|
||
a_{21}x_1+a_{22}x_2+\dots+a_{2n}x_n &=& b_2\\
|
||
\vdots & &\vdots\\
|
||
a_{m1}x_1+a_{m2}x_2+\dots+a_{mn}x_n &=& b_m,
|
||
\end{array}
|
||
$$
|
||
где $a_{ij}$ ($1\leq i\leq m$, $1\leq j\leq n$), $b_i$ ($1\leq i\leq
|
||
m$)~--- элементы $R$, а $x_1,\dots,x_n$~--- неизвестные.
|
||
\dfn{Решением}\index{решение системы линейных уравнений} этой системы линейных уравнений называется набор
|
||
$(c_1,\dots,c_n)$ элементов $R$, при подстановке которого в каждое из
|
||
$m$ уравнений системы получается верное равенство, то есть,
|
||
$\sum_{j=1}^n a_{ij}c_j=b_i$ для всех $i=1,\dots,m$.
|
||
|
||
В первом приближении линейная алгебра изучает свойства множеств
|
||
решений систем линейных уравнений. Наша ближайшая цель~--- указать
|
||
несколько преобразований, которые не меняют множество решений системы,
|
||
но, возможно, упрощают ее вид. Чтобы не писать каждый раз значки $+$ и
|
||
$=$, мы будем пользоваться {\it матричной формой записи} системы.
|
||
\dfn{Матрицей}\index{матрица!системы линейных уравнений} указанной
|
||
системы линейных уравнений называется таблица
|
||
$$
|
||
\begin{pmatrix}
|
||
a_{11} & a_{12} & \dots & a_{1n}\\
|
||
a_{21} & a_{22} & \dots & a_{2n} \\
|
||
\vdots & \vdots & \ddots & \vdots\\
|
||
a_{m1} & a_{m2} & \dots & a_{mn}
|
||
\end{pmatrix}.
|
||
$$
|
||
Заметим, однако, что матрица системы линейных уравнений содержит не
|
||
всю информацию о системе: мы нигде не использовали правые части этих
|
||
уравнений. \dfn{Расширенной матрицей}\index{матрица!расширенная} нашей
|
||
системы линейных уравнений
|
||
называется таблица
|
||
$$
|
||
\left(
|
||
\begin{array}{cccc|c}
|
||
a_{11} & a_{12} & \dots & a_{1n} & b_1\\
|
||
a_{21} & a_{22} & \dots & a_{2n} & b_2\\
|
||
\vdots & \vdots & \ddots & \vdots & \vdots\\
|
||
a_{m1} & a_{m2} & \dots & a_{mn} & b_m
|
||
\end{array}
|
||
\right)
|
||
$$
|
||
Вертикальная черта служит для визуального отделения коэффициентов
|
||
левой части и правой части системы; иногда мы опускаем ее.
|
||
|
||
Заметим, что в матрице линейной системы с $m$ уравнениями и $n$
|
||
неизвестными содержится $m$ строк и $n$ столбцов; на пересечении
|
||
строки с номером $i$ и столбца с номером $j$ стоит элемент $a_{ij}$. В
|
||
расширенной матрице такой системы $m$ строк и $n+1$ столбец.
|
||
|
||
Часто мы будем записывать матрицу так: $(a_{ij})_{\substack{1\leq
|
||
i\leq m\\1\leq j\leq n}}$: в этой матрице $m$ строк, $n$ столбцов,
|
||
и на пересечении $i$-ой строки и $j$-го столбцы стоит элемент
|
||
$a_{ij}$. Если размер матрицы подразумевается известным, мы будем
|
||
сокращать эту запись до $(a_{ij})$.
|
||
|
||
Среди множества преобразований систем линейных уравнений выделяют три
|
||
несложных типа преобразований, играющих важную роль в нахождении
|
||
решений.
|
||
|
||
\begin{enumerate}
|
||
\item Элементарное преобразование первого типа: прибавить к $i$-му
|
||
уравнению $j$-ое уравнение, умноженное на некоторый элемент
|
||
$\lambda\in R$. Иными словами, $i$-ое уравнение
|
||
$$
|
||
a_{i1}x_1+a_{i2}x_2+\dots+a_{in}x_n=b_i
|
||
$$
|
||
заменяется при этом преобразовании на уравнение
|
||
$$
|
||
(a_{i1}+\lambda a_{j1})x_1+(a_{i2}+\lambda a_{j2})x_2+\dots
|
||
+ (a_{in}+\lambda a_{jn})x_n=b_i+\lambda b_j,
|
||
$$
|
||
а все остальные уравнения остаются неизменными.
|
||
\item Элементарное преобразование второго типа: поменять местами
|
||
$i$-ое уравнение и $j$-ое уравнение. Остальные уравнения при этом
|
||
остаются неизменными.
|
||
\item Элементарное преобразование третьего типа: домножить $i$-ое
|
||
уравнение на обратимый элемент кольца $R$. Иными словами, для
|
||
некоторого $\eps\in R^*$ уравнение под номером $i$
|
||
$$
|
||
a_{i1}x_1+a_{i2}x_2+\dots+a_{in}x_n=b_i
|
||
$$
|
||
заменяется на уравнение
|
||
$$
|
||
\eps a_{i1}x_1+\eps a_{i2}x_2+\dots+\eps a_{in}x_n=\eps b_i,
|
||
$$
|
||
а остальные уравнения не меняются.
|
||
\end{enumerate}
|
||
Несложно понять, как указанные преобразования меняют матрицу системы и
|
||
расширенную матрицу системы: элементарное преобразование первого типа
|
||
прибавляет к $i$-ой строке $j$-ую, умноженную на $\lambda\in R$;
|
||
второго типа~--- меняет местами строки с номерами $i$ и $j$; третьего
|
||
типа~--- домножает все элементы $i$-ой строки на $\eps\in R^*$.
|
||
|
||
Мы будем использовать следующие условные обозначения для элементарных
|
||
преобразований: преобразование первого типа, прибавляющее к $i$-ой
|
||
строке $j$-ую, умноженную на $\lambda$, обозначается через
|
||
$T_{ij}(\lambda)$ (здесь $1\leq i,j\leq m$, $i\neq j$, $\lambda\in
|
||
R$); преобразование второго типа, меняющее местами строки с номерами
|
||
$i$ и $j$, обозначается через $S_{ij}$ (здесь $1\leq i,j\leq m$,
|
||
$i\neq j$), а преобразование третьего
|
||
типа, домножающее $i$-ую строку на $\eps$, обозначается через
|
||
$D_i(\eps)$ (здесь $1\leq i\leq m$, $\eps\in R^*$). Через некоторое
|
||
время эти символы превратятся в обозначения совершенно конкретных
|
||
объектов, связанных с соответствующими преобразованиями.
|
||
|
||
Сразу же заметим, что каждое элементарное преобразование {\it
|
||
обратимо}: это означает, что для каждого элементарного
|
||
преобразования найдется другое элементарное преобразование (называемое
|
||
{\it обратным} такое, что
|
||
применение двух этих преобразований подряд (в любом порядке) к системе
|
||
не меняет ее. Действительно, сразу видно, что для преобразования
|
||
третьего типа $D_i(\eps)$ обратным является $D_i(\eps^{-1})$, а для
|
||
преобразования второго типа $S_{ij}$ обратным является оно
|
||
само. Наконец, несложная выкладка показывает, что для преобразования
|
||
первого типа $T_{ij}(\lambda)$ обратным является преобразование
|
||
$T_{ij}(-\lambda)$: последовательное применение этих двух
|
||
преобразований сначала прибавляет к $i$-му уравнению исходной системы
|
||
$j$-ое, умноженное на $\lambda$, а потом прибавляет $j$-ое, умноженное
|
||
на $-\lambda$ (или наоборот), поэтому $i$-ое уравнение в итоге не
|
||
изменяется (а остальные~--- тем более).
|
||
|
||
\begin{lemma}\label{lem_elementary_transformations}
|
||
Элементарные преобразования не меняют множества (всех) решений
|
||
системы.
|
||
\end{lemma}
|
||
\begin{proof}
|
||
По замечанию выше, каждое элементарное преобразование обратимо;
|
||
поэтому достаточно доказать, что множество решений системы не
|
||
уменьшается: если набор $(c_1,\dots,c_n)$ является решением системы,
|
||
то он будет являться и решением системы, полученной из нее
|
||
элементарным преобразованием. Это очевидно для преобразований второго
|
||
и третьего типов, и несложно проверить для преобразований первого
|
||
типа.
|
||
\end{proof}
|
||
|
||
\subsection{Метод Гаусса}
|
||
\literature{[F], гл. IV, \S~4, п. 5; [K1], гл. 1, \S~3, п. 3.}
|
||
|
||
Сейчас мы опишем, как решать произвольную систему линейных
|
||
уравнений {\it над полем}. Основная идея состоит в том, чтобы сначала
|
||
привести систему
|
||
к удобному для решения виду~--- {\it ступенчатому}. Алгоритм
|
||
приведения произвольной системы к ступенчатому виду называется {\it
|
||
методом Гаусса}. Мы дадим строгое определение ступенчатого вида
|
||
после того, как опишем этот алгоритм.
|
||
|
||
Как обычно, нам будет удобно работать не с системой линейных
|
||
уравнений, а с ее [расширенной] матрицей: метод Гаусса состоит в
|
||
последовательном применении к расширенной матрице системы элементарных
|
||
преобразований, после чего матрица становится {\it ступенчатой}, и
|
||
все решения соответствующей системы легко выписать; по
|
||
лемме~\ref{lem_elementary_transformations} полученное множество
|
||
решений будет и множеством решений исходной системы.
|
||
|
||
Итак, пусть $(a_{ij})$~--- матрица над полем $k$ размера $m\times n$.
|
||
Мы будем изучать ее столбцы
|
||
последовательно, слева направо. Возьмем первый столбец. Возможны два
|
||
варианта: либо он состоит из одних нулей, либо в нем найдется
|
||
ненулевой элемент. Если столбец состоит из одних нулей, мы пропускаем
|
||
его и переходим к следующему столбцу, пока не найдем какой-нибудь
|
||
столбец с ненулевым элементом. Пусть, наконец, в столбце с номером
|
||
$j_1$ нашелся ненулевой элемент (если такого столбца нет, то наша
|
||
матрица нулевая, и алгоритм завершен).
|
||
|
||
Для начала поставим этот ненулевой элемент на первое
|
||
место в столбце посредством элементарного преобразования второго
|
||
типа. Теперь мы сделаем все остальные элементы нашего столбца нулевыми
|
||
с помощью элементарных преобразований первого типа. Делается это так:
|
||
теперь мы считаем, что элемент $a_{1,j_1}$ не равен нулю; если
|
||
какой-нибудь элемент $a_{i,j_1}$ первого столбца также не равен нулю, то
|
||
прибавим к $i$-ой строчке первую, умноженную на
|
||
$-a_{i,j_1}/a_{1,j_1}$. Иными словами, проведем элементарное преобразование
|
||
$T_{i,j_1}(-a_{i,j_1}/a_{1,j_1})$. При этом изменится только $i$-ая строчка, и
|
||
ее первый элемент станет равным
|
||
$a_{i,j_1}+a_{1,j_1}\cdot(-a_{i,j_1}/a_{1,j_1})=0$. Проделаем это для всех
|
||
ненулевых элементов первого столбца. Заметим, что здесь мы
|
||
использовали тот факт, что ненулевой элемент $a_{1,j_1}$ обратим, то
|
||
есть, что $k$ является полем.
|
||
|
||
Теперь столбец с номером $j_1$ нашей матрицы содержит единственный
|
||
ненулевой элемент $a_{1,j_1}$ (а все столбцы, стоящие слева от него,
|
||
нулевые).
|
||
Мысленно забудем про первую строчку нашей матрицы и про все столбцы
|
||
вплоть до столбца с номером $j_1$ и повторим нашу операцию: теперь мы
|
||
берем столбец с номером $j_1+1$ и ищем в нем ненулевой элемент, не
|
||
принимая во внимание первую строчку. Если во всех позициях (кроме,
|
||
может быть, первой) этого столбцы стоят нули, мы двигаемся дальше
|
||
вправо, пока не находим, наконец, столбец с номером $j_2$, в котором
|
||
стоит какой-нибудь ненулевой элемент не в первой строчке. Посредством
|
||
элементарного преобразования второго типа можно поставить этот
|
||
ненулевой элемент на второе место, а затем, с помощью элементарных
|
||
преобразований первого типа, добиться того, что все элементы ниже его
|
||
станут нулями. Заметим, что первая строчка в этих преобразованиях уже
|
||
никак не участвует, поэтому про нее и можно забыть. Кроме того, в
|
||
столбцах с номерами $1,\dots,j_1$ стоят нули на тех позициях, которые
|
||
затрагиваются этими преобразованиями, поэтому они не изменяются. Итак,
|
||
в столбце с номером $j_2$ теперь стоит неизвестно что на первой
|
||
позиции, ненулевой элемент $a_{2,j_2}$ на второй позиции, и $0$ на
|
||
остальных позициях. Далее, конечно, мы продолжаем ту же процедуру,
|
||
забывая про первый две строчки и про столбцы с номерами
|
||
$1,\dots,j_2$. Заметим, что мы обязаны двигаться вправо: $1\leq
|
||
j_1<j_2<j_3<\dots$, поэтому этот процесс остановится.
|
||
|
||
Полученная матрица
|
||
$$
|
||
\left(
|
||
\begin{array}{ccccccccccccccccccc}
|
||
0&\dots&0&a_{1,j_1}&*& \dots & * & * & * & \dots &*&*&*&\dots&*&*&*&\dots&*\\
|
||
0 & \dots & 0 & 0 & 0 & \dots & 0 & a_{2,j_2} & * & \dots &*&*&*&\dots&*&*&*&\dots&*\\
|
||
0 & \dots & 0 & 0 & 0 & \dots & 0 & 0 & 0 & \dots & 0 & a_{3,j_3}&*&\dots&*&*&*&\dots&*\\
|
||
\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\
|
||
0&\dots&0&0&0&\dots&0&0&0&\dots&0&0&0&\dots&0&a_{s,j_s}&*&\dots&*\\
|
||
0&\dots&0&0&0&\dots&0&0&0&\dots&0&0&0&\dots&0&0&0&\dots&0\\
|
||
\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\
|
||
0&\dots&0&0&0&\dots&0&0&0&\dots&0&0&0&\dots&0&0&0&\dots&0\\
|
||
\end{array}\right)
|
||
$$
|
||
и называется ступенчатой; теперь мы готовы дать
|
||
формальное определение.
|
||
|
||
\begin{definition}
|
||
Матрица $(a_{ij})_{\substack{1\leq i\leq m\\1\leq j\leq n}}$
|
||
называется \dfn{ступенчатой}\index{матрица!ступенчатая}, если существует некоторая
|
||
последовательность индексов $1\leq j_1<j_2<\dots<j_s\leq n$ такая, что
|
||
\begin{itemize}
|
||
\item $a_{i,j_i}\neq 0$ для любого $i=1,\dots,s$;
|
||
\item $a_{i,j}=0$ при $j<j_i$;
|
||
\item $a_{i,j}=0$ для любого $j$ при $i>s$.
|
||
\end{itemize}
|
||
\end{definition}
|
||
|
||
% 10.12.2014
|
||
|
||
Иными словами, в ступенчатой матрице имеются строки $1,\dots,s$ такие,
|
||
что в строке с номером $i$ первый ненулевой элемент стоит в позиции
|
||
$(i,j_i)$, а все строки с номерами $s+1,\dots,m$~--- нулевые.
|
||
|
||
Ненулевые элементы $a_{1,j_1}, a_{2,j_2},\dots,a_{s,j_s}$ в
|
||
ступенчатой матрице $(a_{ij})$ мы будем
|
||
называть \dfn{ведущими}\index{ведущие элементы}.
|
||
|
||
Что же нам дает применение метода Гаусса к расширенной матрице системы
|
||
линейных уравнений? Напомним, что расширенная матрица системы состоит
|
||
из $m$ строк и $n+1$ столбца, где $m$~--- число уравнений, $n$~---
|
||
число неизвестных. Самый правый столбец расширенной матрицы несет
|
||
особый смысл~--- это правая часть системы. Поэтому сразу рассмотрим
|
||
особый случай: предположим, что ведущий элемент оказался в последнем
|
||
столбце. Очевидно, что это может быть только последний ведущий элемент
|
||
$a_{s,j_s}$. Тогда уравнение с номером $s$ выглядит так:
|
||
$0x_1+\dots+0x_n=a_{s,j_s}$, и $a_{s,j_s}\neq 0$. Очевидно, что это
|
||
уравнение не имеет решений, поэтому и вся система не имеет решений.
|
||
|
||
Теперь можно считать, что $j_s<n+1$, и всем ведущим элементам
|
||
соответствуют переменные $x_{j_1},\dots,x_{j_s}$. {\it Все остальные}
|
||
переменные мы будем называть \dfn{свободными}\index{свободные
|
||
переменные}, а переменные
|
||
$x_{j_1},\dots,x_{j_s}$~--- \dfn{зависимыми}\index{зависимые
|
||
переменные}. Теперь мы утверждаем,
|
||
что множество решений полученной системы выглядит так: свободные
|
||
переменные могут принимать произвольные значения, и, как только они
|
||
заданы, значения зависимых переменных определяются однозначным
|
||
образом.
|
||
|
||
Действительно, предположим, что мы задали произвольные значения
|
||
свободных переменных. Пойдем по уравнениям снизу вверх и начнем
|
||
выражать значения зависимых переменных. Заметим, что уравнения с
|
||
номерами $s+1,\dots,m$ фактически имеют вид $0=0$, поэтому не влияют
|
||
на множество решений системы, и их можно выбросить. Последнее
|
||
уравнение имеет вид $a_{s,j_s}x_{j_s}+\dots=b_s$, и значения всех
|
||
переменных в левой части, кроме $x_{j_s}$, уже заданы. Деля на
|
||
ненулевой элемент $a_{s,j_s}$ и перенося <<многоточие>> в правую
|
||
часть, получаем выражение для зависимой переменной $x_{j_s}$. Теперь
|
||
возьмем предпоследнее уравнение:
|
||
$a_{s-1,j_{s-1}}x_{j_{s-1}}+\dots=b_{s-1}$; мы уже знаем значения всех
|
||
переменных в левой части, кроме $x_{j_{s-1}}$, поэтому аналогичным
|
||
образом получаем выражение для следующей зависимой переменной,
|
||
$x_{j_{s-1}}$. Продолжая этот процесс, мы дойдем и до первой строчки,
|
||
выразив значение $x_{j_1}$.
|
||
|
||
Итак, если заданы значения свободных переменных, то значения свободных
|
||
переменных определяются однозначно. С другой стороны, значения
|
||
свободных переменных могут быть совершенно произвольными, и
|
||
приведенный алгоритм утверждает, что найдется решение с такими
|
||
значениями свободных переменных. Иными словами, мы установили
|
||
взаимно-однозначное соответствие между множеством решений нашей
|
||
системы и множеством произвольных наборов значений независимых
|
||
переменных.
|
||
|
||
\subsection{Операции над матрицами}
|
||
\literature{[F], гл. IV, \S~1; [K1], гл. 3, \S~3, пп. 1--3.}
|
||
|
||
\begin{definition}
|
||
\dfn{Матрицей}\index{матрица} над кольцом $R$ мы будем называть
|
||
прямоугольную
|
||
таблицу, составленную из элементов кольца $R$. Иными словами, задать
|
||
матрицу $A$~--- значит, задать набор элементов $a_{ij}\in R$ для всех
|
||
$i,j$ таких, что $1\leq i\leq m$, $1\leq j\leq n$. Эти элементы
|
||
называются \dfn{коэффициентами}\index{коэффициенты матрицы} матрицы
|
||
$A$ и мы пишем $A=(a_{ij})$.
|
||
При этом мы будем
|
||
изображать такую матрицу в виде таблицы из $m$ строк и $n$ столбцов, в
|
||
которой на пересечении $i$-й строки и $j$-го столбца стоит элемент
|
||
$a_{ij}$. Будем говорить, что $A$ является матрицей $m\times n$;
|
||
множество всех матриц $m\times n$ над кольцом $R$
|
||
обозначается через $M(m,n,R)$. Если
|
||
$m=n$ (число строк совпадает с числом столбцов), матрица называется
|
||
\dfn{квадратной}\index{матрица!квадратная}; мы будем писать $M(n,R)$
|
||
вместо $M(n,n,R)$. При этом $n$ называется
|
||
\dfn{порядком}\index{порядок!квадратной матрицы} квадратной матрицы
|
||
из $M(n,R)$.
|
||
\end{definition}
|
||
|
||
Элемент, стоящий в матрице $A$ на пересечении $i$-й строки и $j$-го
|
||
столбца мы часто будем обозначать через $A_{ij}$; будем говорить, что
|
||
в матрице $A$ элемент $A_{ij}$ \dfn{стоит на позиции
|
||
$(i,j)$}\index{позиция элемента в матрице}.
|
||
|
||
Введем основные операции над матрицами. Если $A=(a_{ij})$,
|
||
$B=(b_{ij})$~--- две матрицы одинакового размера $m\times n$, определим их сумму
|
||
$A+B$ как матрицу, у которой на позиции $(i,j)$ стоит $a_{ij}+b_{ij}$.
|
||
Иными словами, $(A+B)_{ij}=A_{ij}+B_{ij}$ для всех $1\leq i\leq m$,
|
||
$\leq i\leq n$.
|
||
Таким образом, сложение матриц происходит {\it покомпонентно}.
|
||
|
||
Гораздо интереснее выглядит умножение матриц.
|
||
Пусть $A\in M(m,n,R)$, $B\in M(n,p,R)$~--- обратите внимание, что
|
||
число столбцов первой матрицы равно числу строк второй матрицы.
|
||
Тогда их произведением $AB$ называется матрица размера $m\times p$, у
|
||
которой на позиции $(i,k)$ стоит $\sum_{j=1}^nA_{ij}B_{jk}$. Иными
|
||
словами, $(AB)_{ik}=\sum_{j=1}^nA_{ij}B_{jk}$. Обратите внимание, что
|
||
при фиксированных $i$ и $k$ элементы $A_{ij}$ пробегают строку матрицы
|
||
$A$ с номером $i$, а элементы $B_{jk}$ пробегают столбец матрицы $B$ с
|
||
номером $k$. То есть, для того, чтобы получить элемент, стоящий в
|
||
матрице $AB$ на позиции $(i,k)$, нужно взять $i$-ю строку матрицы $A$,
|
||
$k$-й столбец матрицы $B$, и сформировать сумму произведений
|
||
соответствующих элементов этой строки и этого столбца; по условию на
|
||
размер матриц $A$ и $B$ они имеют одинаковую длину.
|
||
|
||
Определим также результат умножения скаляра (элемента кольца $R$) на
|
||
матрицу над $R$: пусть $\lambda\in R$, $A\in M(m,n,R)$. Рассмотрим
|
||
матрицу, в которой на позиции $(i,j)$ стоит $\lambda A_{ij}$; мы будем
|
||
обозначать ее через $\lambda A$. То есть, при умножении матрицы $A$ на
|
||
скаляр $\lambda$ каждый элемент матрицы $A$ умножается на $\lambda$
|
||
(здесь мы предполагаем, что кольцо $R$ коммутативно, поэтому неважно,
|
||
с какой стороны происходит умножение).
|
||
|
||
Наконец, еще одна важная операция~---
|
||
\dfn{транспонирование}\index{транспонирование}\index{матрица!транспонированная}
|
||
матрицы. Пусть $A\in M(m,n,R)$. Определим матрицу $A^T\in M(n,m,R)$
|
||
так: у нее в позиции $(j,i)$ стоит элемент $A_{ij}$. Такая матрица
|
||
называется матрицей, транспонированной к матрице $A$. Неформально
|
||
говоря, это матрица, полученная из матрицы $A$ <<симметрией>>
|
||
относительно главной диагонали. При этом строки с номерами
|
||
$1,2,\dots,m$ матрицы $A$ становятся столбцами с номерами
|
||
$1,2,\dots,m$ матрицы $A^T$; аналогично, столбцы матрицы $A$
|
||
превращаются в строки матрицы $A^T$.
|
||
|
||
Теперь сформулируем свойства введенных операций.
|
||
|
||
\begin{theorem}[Свойства операций над матрицами]\label{thm_matrix_operations_properties}
|
||
Следующие тождества выполняются для любых матриц $A,B,C$ над коммутативным
|
||
кольцом $R$ и для любых $\lambda,\mu\in R$,
|
||
если определены результаты всех входящих в них операций:
|
||
\begin{enumerate}
|
||
\item $A+(B+C)=(A+B)+C$ (ассоциативность сложения);
|
||
\item пусть $0$~--- матрица, все коэффициенты которой нулевые; тогда
|
||
$A+0=0+A=A$ (нейтральный элемент относительно сложения);
|
||
\item для любой матрицы $A$ найдется матрица $-A$ такая, что
|
||
$A+(-A)=(-A)+A=0$ (противоположный элемент);
|
||
\item $A+B=B+A$ (коммутативность сложения).
|
||
\item $(AB)C=A(BC)$ (ассоциативность умножения);
|
||
\item $A(B+C)=AB+AC$ (левая дистрибутивность);
|
||
\item $(B+C)A=BA+CA$ (правая дистрибутивность);
|
||
\item $\lambda(A+B)=\lambda A+\lambda B$ (левая дистрибутивность умножения
|
||
на скаляр);
|
||
\item $(\lambda+\mu)A=\lambda A + \mu A$ (правая дистрибутивность
|
||
умножения на скаляр);
|
||
\item $(\lambda A)B=\lambda (AB)=A(\lambda B)$;
|
||
\item $(\lambda\mu)A=\lambda(\mu A)$;
|
||
\item $(A+B)^T=A^T+B^T$;
|
||
\item\label{property_mult_transpose} $(AB)^T=B^TA^T$.
|
||
\end{enumerate}
|
||
\end{theorem}
|
||
Поясним формулировку <<\dots если определены результаты всех входящих
|
||
в них операций>>: мы можем сложить две матрицы только в том случае,
|
||
если они имеют одинаковый размер, и перемножить две матрицы только в
|
||
том случае, если количество столбцов первой матрицы совпадает с
|
||
количеством строк второй матрицы. Поэтому, скажем, тождество
|
||
$A+(B+C)=(A+B)+C$ выполняется для любых $A,B,C\in M(m,n,R)$, тождество
|
||
$(AB)C=A(BC)$~--- для любых $A\in M(m,n,R)$, $B\in M(n,p,R)$, $C\in
|
||
M(p,q,R)$, тождество $A(B+C)=AB+AC$~--- для любых $A\in M(m,n,R)$ и
|
||
$B,C\in M(n,p,R)$, и так далее.
|
||
|
||
\begin{proof}
|
||
Напоминаем, что через $A_{ij}$ мы обозначаем элемент матрицы $A$,
|
||
стоящий в позиции $(i,j)$. Для того, чтобы проверить равенство двух
|
||
матриц, достаточно проверить, что они имеют одинаковый размер и что
|
||
элементы, стоящие в соответствующих позициях этих матриц,
|
||
равны. Мы займемся именно проверкой поэлементного равенства, оставив
|
||
читателю [тривиальную] проверку равенства размеров.
|
||
\begin{enumerate}
|
||
\item
|
||
$(A+(B+C))_{ij}=A_{ij}+(B+C)_{ij} = A_{ij}+(B_{ij}+C_{ij}) =
|
||
(A_{ij}+B_{ij})+C_{ij} = (A+B)_{ij}+C_{ij}=((A+B)+C)_{ij}$; здесь мы
|
||
воспользовались ассоциативностью сложения в кольце $R$.
|
||
\item $(A+0)_{ij} = A_{ij}+0_{ij} = A_{ij}+0 = A_{ij}=0+A_{ij} =
|
||
0_{ij}+A_{ij} = (0+A)_{ij}$.
|
||
\item Составим матрицу $-A$ из элементов $-A_{ij}$, то есть, положим
|
||
$(-A)_{ij} = -A_{ij}$. Тогда
|
||
$(A+(-A))_{ij}=A_{ij}+(-A)_{ij}=A_{ij}-A_{ij}=0$, откуда $A+(-A)=0$;
|
||
аналогично, $(-A)+A=0$.
|
||
\item $(A+B)_{ij} = A_{ij}+B_{ij} = B_{ij}+A_{ij} = (B+A)_{ij}$,
|
||
поскольку сложение в $R$ коммутативно.
|
||
\item Пусть $A\in M(m,n,R)$, $B\in M(n,p,R)$, $C\in M(p,q,R)$. Тогда
|
||
$$((AB)C)_{il} = \sum_{k=1}^p(AB)_{ik}C_{kl} =
|
||
\sum_{k=1}^p\sum_{j=1}^nA_{ij}B_{jk}C_{kl};$$ с другой стороны,
|
||
$$(A(BC))_{il} = \sum_{j=1}^nA_{ij}(BC)_{jl} =
|
||
\sum_{j=1}^nA_{ij}\sum_{k=1}^pB_{jk}C_{kl} =
|
||
\sum_{j=1}^n\sum_{k=1}^pA_{ij}B_{jk}C_{kl}.$$ Получившиеся суммы
|
||
отличаются только изменением порядка суммирования.
|
||
\item Пусть $A\in M(m,n,R)$, $B\in M(n,p,R)$. Тогда
|
||
$$(A(B+C))_{ik} = \sum_{j=1}^nA_{ij}(B+C)_{jk} =
|
||
\sum_{j=1}^n(A_{ij}B_{jk}+A_{ij}C_{jk})$$ и
|
||
$$(AB+AC)_{ik} = (AB)_{ik}+(AC)_{ik} = \sum_{j=1}^nA_{ij}B_{jk} +
|
||
\sum_{j=1}^nA_{ij}C_{jk} = \sum_{j=1}^n(A_{ij}B_{jk}+A_{ij}C_{jk}).$$
|
||
\item Доказательство совершенно аналогично доказательству предыдущего
|
||
пункта.
|
||
\item $(\lambda(A+B))_{ij} = \lambda(A+B)_{ij} =
|
||
\lambda(A_{ij}+B_{ij}) = \lambda A_{ij}+\lambda B_{ij} =
|
||
(\lambda A)_{ij}+(\lambda B)_{ij}=(\lambda A + \lambda B)_{ij}$.
|
||
\item $((\lambda+\mu)A)_{ij} = (\lambda+\mu)A_{ij} =
|
||
\lambda A_{ij}+\mu A_{ij} = (\lambda A)_{ij} + (\mu A)_{ij} =
|
||
(\lambda A + \mu A)_{ij}$.
|
||
\item Заметим, что $((\lambda A)B)_{ik} = \sum_{j}((\lambda A)_{ij}B_{jk}) =
|
||
\sum_{j}(\lambda A_{ij}B_{jk})$; кроме того,
|
||
$$(A(\lambda B))_{ik} = \sum_j(A_{ij}(\lambda B)_{jk}) =
|
||
\sum_j(A_{ij}\lambda B_{jk}) = \sum_{j}(\lambda A_{ij}B_{jk})$$ и
|
||
$$(\lambda (AB))_{ik} = \lambda (AB)_{ik} = \lambda\sum_j(A_{ij}B_{jk})
|
||
= \sum_j(\lambda A_{ij}B_{jk}).$$
|
||
\item $((\lambda\mu)A)_{ij} = (\lambda\mu)A_{ij} = \lambda\mu A_{ij} =
|
||
\lambda(\mu A_{ij}) = \lambda (\mu A)_{ij} = (\lambda(\mu A))_{ij}$.
|
||
\item $((A+B)^T)_{ij} = (A+B)_{ji} = A_{ji} + B_{ji} = (A^T)_{ij} +
|
||
(B^T)_{ij} = (A^T + B^T)_{ij}$.
|
||
\item $((AB)^T)_{ik} = (AB)_{ki} = \sum_j(A_{kj}B_{ji}) =
|
||
\sum_j((A^T)_{jk}(B^T)_{ij}) = \sum_j((B^T)_{ij}(A^T)_{jk}) = B^TA^T$.
|
||
\end{enumerate}
|
||
\end{proof}
|
||
|
||
\begin{definition}
|
||
Рассмотрим матрицу размера $n\times n$, у которой в позиции $(i,j)$
|
||
стоит $1$, если $i=j$, и $0$, если $i\neq j$. Такая матрица называется
|
||
\dfn{единичной матрицей}\index{матрица!единичная} и обозначается через $E_n$ (и часто мы будем
|
||
обозначать ее просто через $E$, если размер ясен из контекста). Эта
|
||
матрица действительно играет роль нейтрального элемента относительно
|
||
умножения, как показывает следующее утверждение.
|
||
\end{definition}
|
||
|
||
\begin{proposition}\label{prop_identity_matrix}
|
||
Пусть $A\in M(m,n,R)$. Тогда $E_m\cdot A = A\cdot E_n = A$.
|
||
\end{proposition}
|
||
\begin{proof}
|
||
Заметим, что $(E_m\cdot A)_{ik} = \sum_j (E_m)_{ij} A_{jk}$. В
|
||
получившейся сумме матричный элемент $(E_m)_{ij}$ равен $0$ для всех
|
||
$j$, кроме $j=i$. Поэтому от суммы остается одно слагаемое,
|
||
соответствующее случаю $j=i$, и равное $A_{ik}$. Это выполнено для
|
||
всех $i,k$, поэтому $E_m\cdot A = A$. Второе равенство доказывается
|
||
аналогично.
|
||
\end{proof}
|
||
|
||
\begin{remark}\label{rem:matrix_multiplication_properties}
|
||
Заметим, что для квадратных матриц фиксированного размера (то есть,
|
||
для элементов $M(n,R)$) свойства 1--7 из
|
||
теоремы~\ref{thm_matrix_operations_properties} и свойство единичных
|
||
матриц из предложения~\ref{prop_identity_matrix} означают, что эти
|
||
матрицы образуют ассоциативное кольцо с единицей. Это кольцо $M(n,R)$
|
||
называется \dfn{кольцом квадратных матриц}\index{кольцо!квадратных
|
||
матриц} порядка $n$.
|
||
Отметим, что это кольцо не является коммутативным при $n\geq 2$:
|
||
$$
|
||
\begin{pmatrix}0 & 1\\0 & 0\end{pmatrix}\cdot
|
||
\begin{pmatrix}0 & 0\\1 & 0\end{pmatrix} =
|
||
\begin{pmatrix}1 & 0\\0 & 0\end{pmatrix}\neq
|
||
\begin{pmatrix}0 & 0\\0 & 1\end{pmatrix} =
|
||
\begin{pmatrix}0 & 0\\1 & 0\end{pmatrix}\cdot
|
||
\begin{pmatrix}0 & 1\\0 & 0\end{pmatrix}.
|
||
$$
|
||
Напомним, что элемент $a$ произвольного ассоциативного кольца $A$ с
|
||
единицей называется {\it обратимым}, если найдется элемент $b\in A$
|
||
такой, что $ab=ba=1$ в $A$. Такой элемент $b$ обозначается через
|
||
$a^{-1}$ и называется {\it обратным} к $a$. В полном соответствии с
|
||
этим, квадратная матрица $A\in M(n,R)$ называется
|
||
\dfn{обратимой}\index{матрица!обратимая},
|
||
если найдется матрица, обозначаемая через $A^{-1}\in M(n,R)$, такая,
|
||
что $A\cdot A^{-1} = A^{-1}\cdot A = E_n$. При этом, как и в
|
||
произвольном ассоциативном кольце с единицей, для обратимой матрицы
|
||
$A$ выполнено $(A^{-1})^{-1}=A$, а для набора обратимых матриц
|
||
$A_1,\dots,A_s$ выполнено $(A_1\cdot A_2\cdot\dots\cdot A_s)^{-1} =
|
||
A_s^{-1}\cdot\dots\cdot A_2^{-1}\cdot A_1^{-1}$.
|
||
\end{remark}
|
||
|
||
Упомянем еще одно важное свойство, связывающее обратимость и
|
||
транспонирование.
|
||
|
||
\begin{proposition}
|
||
Если матрица $A\in M(n,R)$ обратима, то и матрица $A^T$ обратима,
|
||
причем $(A^T)^{-1} = (A^{-1})^T$.
|
||
\end{proposition}
|
||
\begin{proof}
|
||
Пользуясь свойством~(\ref{property_mult_transpose}) из
|
||
теоремы~\ref{thm_matrix_operations_properties}, получаем
|
||
$A^T\cdot(A^{-1})^T = (A^{-1}\cdot A)^T = (E_n)^T$. Осталось заметить,
|
||
что $(E_n)^T=E_n$, поскольку из определения единичной матрицы легко
|
||
видеть, что $(E_n)_{ij}=(E_n)_{ji}$ для всех $i,j$. Равенство
|
||
$(A^{-1})^T\cdot A^T=E_n$ проверяется аналогично.
|
||
\end{proof}
|
||
|
||
\begin{remark}
|
||
Кольцо матриц $M(n,R)$ не является полем при $n\geq 2$, поскольку в
|
||
нем есть делители нуля. Например, пусть $A=\begin{pmatrix}0 & 1\\0 &
|
||
0\end{pmatrix}\in M(2,R)$; тогда $A\cdot A=\begin{pmatrix}0 & 0\\0 &
|
||
0\end{pmatrix}$. Поэтому матрица $A$ никак не может быть обратимой в
|
||
$M(2,R)$. Нетрудно придумать аналогичный пример в $M(n,R)$ для любого
|
||
$n\geq 2$.
|
||
\end{remark}
|
||
|
||
Удобно конструировать матрицы из маленьких кусочков: обозначим через
|
||
$e_{ij}$ матрицу из $M(m,n,R)$, у которой в позиции $(i,j)$ стоит $1$,
|
||
а во всех остальных позициях стоит $0$. Заметим, что $m$ и $n$ в наше
|
||
обозначение $e_{ij}$ не входят~--- мы подразумеваем, что всегда из
|
||
контекста ясно, какого размера матрицы рассматриваются (если это
|
||
вообще важно).
|
||
Любую матрицу $A=(a_{ij})\in M(m,n,R)$ тогда можно представить в виде
|
||
$A=\sum_{i,j}a_{ij}e_{ij}$. Например, для единичной матрицы имеем
|
||
$E_n=e_{11}+e_{22}+\dots+e_{nn}$.
|
||
Матрицы $e_{ij}$ называются \dfn{матричными единицами}\index{матричная
|
||
единица} (не путать с
|
||
{\it единичными матрицами}!)
|
||
|
||
Как перемножаются матричные единицы? В произведении $e_{ij}\cdot
|
||
e_{kl}$ ненулевые элементы могут стоять только в $i$-ой строчке
|
||
(поскольку все строчки матрицы $e_{ij}$, кроме $i$-ой, нулевые), и
|
||
только в $l$-ом столбце (поскольку все столбцы матрицы $e_{kl}$, кроме
|
||
$l$-го, нулевые). Поэтому произведение $e_{ij}\cdot e_{kl}$ может
|
||
отличаться от нуля только в позиции $e_{il}$. Внимательное
|
||
рассмотрение произведения $i$-ой строчки матрицы $e_{ij}$ на $l$-й
|
||
столбец матрицы $e_{kl}$ показывает, что
|
||
$$e_{ij}\cdot e_{kl}=\begin{cases}e_{il}, &\text{если }j=k;\\ 0,
|
||
&\text{если }j\neq k.\end{cases}$$
|
||
|
||
Наконец, докажем полезный критерий равенства двух матриц.
|
||
\begin{proposition}\label{prop:equal-matrices}
|
||
Пусть $A,B\in M(m,n,R)$. Следующие утверждения равносильны:
|
||
\begin{enumerate}
|
||
\item $A = B$;
|
||
\item $uA = uB$ для всех $u\in M(1,m,R)$;
|
||
\item $Av = Bv$ для всех $v\in M(n,1,R)$;
|
||
\item $uAv = uBv$ для всех $u\in M(1,m,R)$, $v\in M(n,1,R)$.
|
||
\end{enumerate}
|
||
\end{proposition}
|
||
\begin{proof}
|
||
Пусть $A = (a_{ij})$, $B = (b_{ij})$.
|
||
Очевидно, что из первого утверждения следуют остальные.
|
||
Докажем, что $(2)\Rightarrow (1)$.
|
||
Возьмем в качестве $u$ матрицу $e_{1,i}$. Тогда
|
||
$uA = \begin{pmatrix} a_{i1} & a_{i2} & \dots & a_{in} \end{pmatrix}$,
|
||
$uB = \begin{pmatrix} b_{i1} & b_{i2} & \dots & b_{in} \end{pmatrix}$,
|
||
и из их равенства следует равенство $i$-х строчек матриц $A$ и $B$.
|
||
Подставляя $i=1,\dots,m$, получаем, что $A=B$.
|
||
|
||
Совершенно аналогично доказывается, что $(3)\Rightarrow (1)$.
|
||
Наконец, покажем, что $(4)\Rightarrow (1)$.
|
||
Достаточно заметить, что если $u = e_{1,i}$ и $v = e_{j,1}$
|
||
то $uAv = a_{ij}$ и $uBv = b_{ij}$; подставляя всевозможные пары
|
||
$(i,j)$, получаем, что $A = B$.
|
||
\end{proof}
|
||
|
||
% 17.12.2014
|
||
|
||
\subsection{Матрицы элементарных преобразований}
|
||
\literature{[K1], гл. 1, \S~3, п. 6.}
|
||
|
||
В качестве первого применения операций над матрицами мы истолкуем
|
||
элементарные преобразования, введенные в
|
||
разделе~\ref{subsection_linear_systems}, как домножения на матрицы
|
||
определенного вида.
|
||
|
||
Для $i\neq j$ ($1\leq i,j\leq n$) и $\lambda\in R$ определим
|
||
$T_{ij}(\lambda) = E_n + \lambda e_{ij}$. Это матрица, которая
|
||
отличается от единичной матрицы лишь в одной позиции $(i,j)$, в
|
||
которой стоит $\lambda$.
|
||
Напомним, что по этим же данным $i,j,\lambda$ мы определили
|
||
элементарное преобразование первого типа как прибавление к $i$-й
|
||
строке матрицы ее $j$-ой строки, умноженной на $\lambda$. Оказывается,
|
||
проведение этого элементарного преобразования над матрицей $A\in
|
||
M(n,m,R)$ равносильно умножению матрицы $A$ слева на
|
||
$T_{ij}(\lambda)$.
|
||
Действительно, пусть $A=(a_{ij})\in M(n,m,R)$. Посмотрим на матрицу
|
||
$T_{ij}(\lambda)A$. Поскольку матрица $T_{ij}$ отличается от матрицы
|
||
$E_n$ только в $i$-й строке, произведение $T_{ij}(\lambda)A$
|
||
отличается от матрицы $A$ только в $i$-й строке. Значит, нам осталось
|
||
только перемножить $i$-ю строку матрицы $T_{ij}(\lambda)$ на $A$, и
|
||
записать результат в $i$-ю строку результата. В $i$-й строке матрицы
|
||
$T_{ij}(\lambda)$ лишь два элемента отличны от нуля: элемент в позиции
|
||
$i$ равен 1, а элемент в позиции $j$ равен $\lambda$. При умножении на
|
||
$k$-й столбец матрицы $A$, получаем следующее:
|
||
$$
|
||
\left(\begin{matrix}0 & \cdots & 1 & \cdots & \lambda & \cdots & 0\end{matrix}\right)\cdot
|
||
\left(\begin{matrix} a_{1k} \\ \vdots \\ a_{ik} \\ \vdots \\ a_{jk} \\
|
||
\vdots \\ a_{nk}\end{matrix}\right) = a_{ik} + \lambda a_{jk}
|
||
$$
|
||
Это происходит в каждом столбце матрицы $A$; поэтому $i$-я строка
|
||
произведения $T_{ij}(\lambda)$ равна $(\begin{matrix}a_{i1}+\lambda
|
||
a_{j1} & \cdots & a_{in}+\lambda a_{jn}\end{matrix})$, то есть,
|
||
равна сумме $i$-й строки матрицы $A$ и $j$-й строки матрицы $A$,
|
||
умноженной на $\lambda$.
|
||
|
||
Теперь разберемся с элементарными преобразованиями второго
|
||
типа. Для индексов $i\neq j$ рассмотрим матрицу $S_{ij}\in M(n,R)$, которая
|
||
отличается от единичной матрицы $E_n$ перестановкой строк с номерами
|
||
$i$ и $j$. Таким образом, $S_{ij}$ отличается от $E_n$ в четырех
|
||
позициях: в позициях $(i,i)$ и $(j,j)$ стоят $0$ (вместо $1$), а в позициях $(i,j)$
|
||
и $(j,i)$ стоят $1$ (вместо $0$). Иными словами,
|
||
$S_{ij}=E_n-e_{ii}-e_{jj}+e_{ij}+e_{ji}$.
|
||
Покажем, что умножение матрицы $A$ на $S_{ij}$ слева равносильно
|
||
элементарному преобразованию второго типа матрицы $A$~--- перестановке
|
||
$i$-ой и $j$-ой строчки.
|
||
Действительно, произведение $S_{ij}A$ отличается от матрицы $A$ только
|
||
в строчках с номерами $i$ и $j$: $i$-ая строчка равна произведению
|
||
строчки $(\begin{matrix} 0 & \cdots & 0 & 1 & 0 & \cdots &
|
||
0\end{matrix})$ (где $1$ стоит на $j$-м месте) на матрицу $A$, то
|
||
есть, $j$-ой строчке матрицы $A$. Аналогично, $j$-ая строчка
|
||
произведения $S_{ij}A$ равна произведению строчки $(\begin{matrix} 0 &
|
||
\cdot & 0 & 1 & 0 & \cdots & 0\end{matrix})$ (где $1$ стоит на $i$-м
|
||
месте) на матрицу $A$, то есть, $i$-ой строчке матрицы $A$.
|
||
|
||
Наконец, для индекса $i$ и обратимого элемента $\eps\in R^*$
|
||
рассмотрим матрицу $D_i(\eps)\in M(n,R)$, которая отличается от
|
||
единичной матрицы $E_n$ лишь в позиции $(i,i)$, где стоит $\eps$. То
|
||
есть, $D_i(\eps)=E_n+(\eps-1)e_{ii}$. Покажем, что умножение матрицы
|
||
$A$ на $D_i(\eps)$ слева равносильно элементарному преобразованию
|
||
третьего типа матрицы $A$~--- умножению $i$-ой строчки на
|
||
$\eps$. Действительно, матрица $D_i(\eps)\cdot A$ отличается от $A$
|
||
только в $i$-й строчке, и $i$-ая строчка матрицы $D_i(\eps)\cdot A$
|
||
равна произведению $(\begin{pmatrix}0 & \cdots & \eps & \cdots &
|
||
0\end{pmatrix})\cdot A=\eps(\begin{pmatrix}0 & \cdots & 1 & \cdots
|
||
& 0\end{pmatrix})\cdot A$, что равно произведению $\eps$ и $i$-ой
|
||
строчки матрицы $A$.
|
||
|
||
Таким образом, мы истолковали элементарные преобразования над строками
|
||
матрицы как домножения слева на несложные матрицы $T_{ij}(\lambda)$,
|
||
$S_{ij}$ и $D_i(\eps)$:
|
||
\begin{itemize}
|
||
\item умножение на $T_{ij}(\lambda)$ слева соответствует прибавлению к
|
||
$i$-ой строчке $j$-ой строчки, умноженной на $\lambda$;
|
||
\item умножение на $S_{ij}$ слева соответствует перестановке $i$-ой и
|
||
$j$-ой строчек;
|
||
\item умножение на $D_i(\eps)$ слева соответствует умножению $i$-ой
|
||
строчки на $\eps$.
|
||
\end{itemize}
|
||
Применяя транспонирование (с учетом свойства
|
||
$(AB)^T=B^TA^T$), получаем, что элементарные преобразования над {\it
|
||
столбцами} матрицы соответствуют домножения {\it справа} на эти же
|
||
матрицы: действительно, при транспонировании строки матриц
|
||
превращаются в столбцы, и $(T_{ij}(\lambda))^T=T_{ji}(\lambda)$,
|
||
$(S_{ij})^T=S_{ij}$, $(D_i(\eps))^T=D_i(\eps)$. Поэтому
|
||
\begin{itemize}
|
||
\item умножение на $T_{ij}(\lambda)$ справа соответствует прибавлению к
|
||
$j$-ому столбцу $i$-ого столбца, умноженного на $\lambda$;
|
||
\item умножение на $S_{ij}$ справа соответствует перестановке $i$-ого и
|
||
$j$-ого столбцов;
|
||
\item умножение на $D_i(\eps)$ справа соответствует умножению $i$-ого
|
||
столбца на $\eps$.
|
||
\end{itemize}
|
||
Заметим, что обратимость элементарных преобразований соответствует
|
||
тому факту, что любая матрица элементарного преобразования
|
||
обратима. Так, $(T_{ij}(\lambda))^{-1}=T_{ij}(-\lambda),$
|
||
$(S_{ij})^{-1}=S_{ij}$ и $(D_i(\eps))^{-1}=D_i(\eps^{-1}).$ Теперь это
|
||
можно проверить непосредственным матричным перемножением.
|
||
|
||
Теперь мы можем истолковать метод Гаусса как некоторый матричный
|
||
факт. Напомним, что метод Гаусса говорит, что с помощью элементарных
|
||
преобразований строк можно любую матрицу привести к ступенчатому
|
||
виду. В терминах матриц это означает, что для любой матрицы $A\in
|
||
M(m,n,k)$ над полем $k$ найдутся матрицы
|
||
элементарных преобразований $P_1,\dots,P_s\in M(m,k)$ такие, что
|
||
матрица $P_sP_{s-1}\dots P_1A$ является ступенчатой.
|
||
|
||
Проведем после этого некоторые элементарные преобразования над
|
||
{\it столбцами}.
|
||
Посмотрим на первую строчку ступенчатой матрицы $A=(a_{ij})$.
|
||
$$
|
||
\begin{pmatrix}
|
||
0 & \dots & 0 & 1 & * & \dots & * \\
|
||
0 & \dots & 0 & 0 & * & \dots & * \\
|
||
\vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\
|
||
0 & \dots & 0 & 0 & * & \dots & *
|
||
\end{pmatrix}
|
||
$$
|
||
Здесь $1$ стоит в позиции $(1,j_1)$, и $a_{1,j}=0$ при
|
||
$j<j_1$. Для каждого $j>j_1$ прибавим к $j$-му столбцу столбец с
|
||
номером $j_1$, умноженный на $-a_{1,j}$. После этого в позиции $(1,j)$
|
||
окажется $a_{1,j}-a_{1,j}=0$. То есть, после таких прибавлений первая
|
||
строчка нашей матрицы будет иметь только один ненулевой элемент~---
|
||
$1$ в позиции $(1,j_1)$.
|
||
Продолжим эту операцию: посмотрим на вторую строчку нашей
|
||
матрицы. Если она отличается от нулевой, то там стоит $1$ в некоторой
|
||
позиции $(2,j_2)$. Прибавим к $j$-му столбцу столбец с номером $j_2$,
|
||
умноженный на $-a_{2,j}$. При этом первая строчка нашей матрицы уже
|
||
никак не изменится, а во второй останется лишь один ненулевой
|
||
элемент~--- $2$ в позиции $(2,j_2)$. Совершив аналогичное действие для
|
||
всех строк нашей матрицы, мы можем добиться того, что наша матрица
|
||
отличается от нулевой лишь в позициях $(1,j_1), (2,j_2), \dots
|
||
(r,j_r)$, где стоят единицы. После этого перестановкой столбцов можно
|
||
добиться того, что эти единицы будут стоять в позициях $(1,1), (2,2),
|
||
\dots (r,r)$. Полученная матрица называется \dfn{окаймленной
|
||
единичной}\index{матрица!окаймленная единичная} матрицей. Можно изобразить ее в блочной форме следующим
|
||
образом:
|
||
$$
|
||
\left(\begin{matrix}
|
||
E_r & 0\\
|
||
0 & 0
|
||
\end{matrix}\right)
|
||
$$
|
||
(здесь $E_r$~--- единичная матрица размера $r\times r$, а нулевые
|
||
блоки имеют размеры $r\times (n-r)$, $(m-r)\times r$ и $(m-r)\times
|
||
(n-r)$). Конечно, возможно, что $r=0$ и наша матрица нулевая.
|
||
|
||
Сформулируем то, что было сделано, на матричном языке. Как мы знаем,
|
||
элементарные перестановки столбцов соответствуют домножениям нашей
|
||
матрицы на матрицы элементарных преобразований справа. Поэтому на
|
||
самом деле мы только что доказали следующую теорему:
|
||
\begin{theorem}\label{thm_pdq}
|
||
Для любой матрицы $A\in M(m,n,k)$ над полем $k$ найдутся матрицы
|
||
элементарных преобразований $P_1,\dots,P_t,Q_1,\dots,Q_s$ такие, что
|
||
$$
|
||
P_tP_{t-1}\dots P_1AQ_1\dots Q_{s-1}Q_s =
|
||
\begin{pmatrix}
|
||
E_r & 0\\
|
||
0 & 0
|
||
\end{pmatrix}
|
||
$$
|
||
для некоторого $r$.
|
||
\end{theorem}
|
||
|
||
\begin{corollary}\label{cor_pdq}
|
||
Для любой матрицы $A\in M(m,n,k)$ над полем $k$ существуют обратимые
|
||
матрицы $P\in M(m,k)$, $Q\in M(n,k)$ такие, что
|
||
$A=PDQ$, где $D=\begin{pmatrix}E_r&0\\0&0\end{pmatrix}\in
|
||
M(m,n,k)$~--- окаймленная единичная матрица. Более того, матрицы $P$ и
|
||
$Q$ являются произведениями матриц элементарных преобразований.
|
||
\end{corollary}
|
||
\begin{proof}
|
||
По теореме~\ref{thm_pdq} можно записать $P_tP_{t-1}\dots P_1AQ_1\dots
|
||
Q_{s-1}Q_s = \begin{pmatrix}E_r&0\\0&0\end{pmatrix}$.
|
||
Обозначим правую часть через $D$~--- это окаймленная единичная матрица.
|
||
Все матрицы $P_i$,
|
||
$Q_j$ обратимы, поэтому можно последовательно домножить на обратные к
|
||
ним с соответствующих сторон и получить равенство
|
||
$A=P_1^{-1}\dots P_t^{-1}DQ_s^{-1}\dots Q_1^{-1}$. Положим
|
||
теперь $P=P_1^{-1}\dots P_t^{-1}$, $Q=Q_s^{-1}\dots Q_1^{-1}$; матрицы
|
||
$P$ и $Q$ обратимы, поскольку они являются произведениями обратимых
|
||
матриц. Получим $A=PDQ$, что и требовалось.
|
||
\end{proof}
|
||
|
||
Заметим, что набор матриц $P_1,\dots,P_s,Q_1,\dots,Q_t$ из теоремы не
|
||
является однозначно определенным. В то же время (хотя мы этого пока не
|
||
доказали) натуральное число $r$, полученной по матрице $A$, определено
|
||
однозначно: если взять другие матрицы элементарных преобразований,
|
||
после домножения на которые матрица $A$ превратится в окаймленную
|
||
единичную, то размер этой единичной матрицы все равно окажется равным
|
||
$r$. Это число $r$ является важной характеристикой матрицы $A$ и
|
||
называется ее {\it рангом}. Пока что отметим, что для квадратной
|
||
матрицы $A$ обратимость равносильна тому, что окаймленная единичная
|
||
матрица, к которой приводится матрица $A$, на самом деле является
|
||
единичной:
|
||
\begin{corollary}\label{cor_invertible_pdq}
|
||
Пусть квадратная матрица $A\in M(n,k)$ над полем $k$ представлена в
|
||
виде $A=P_sP_{s-1}\dots P_1\left(\begin{matrix}
|
||
E_r & 0\\
|
||
0 & 0\end{matrix}\right)Q_1\dots Q_{t-1}Q_t$, где $P_i,Q_i$~---
|
||
матрицы элементарных преобразований. Тогда обратимость матрицы $A$
|
||
равносильна тому, что $r=n$.
|
||
|
||
Иными словами, матрица $A$ обратима тогда и только тогда, когда ее
|
||
можно представить в виде произведения матриц элементарных
|
||
преобразований.
|
||
\end{corollary}
|
||
\begin{proof}
|
||
Если $r=n$, то в середине разложения $A$ стоит единичная матрица,
|
||
которую можно вычеркнуть, и получится, что $A$ является произведением
|
||
матриц элементарных преобразований. Каждая из матриц элементарных
|
||
преобразований обратима, а произведение обратимых элементов кольца
|
||
обратимо (лемма~\ref{lemma:product_of_invertibles}).
|
||
|
||
Обратно, предположим, что $A$ обратима. Из равенства
|
||
$$A=P_sP_{s-1}\dots P_1\left((\begin{matrix}
|
||
E_r & 0\\
|
||
0 & 0\end{matrix}\right)Q_1\dots Q_{t-1}Q_t$$ получаем, что
|
||
$$P_1^{-1}\dots P_{s-1}^{-1}P_s^{-1}AQ_t^{-1}Q_{t-1}^{-1}\dots
|
||
Q_1^{-1}=\left(\begin{matrix} E_r & 0 \\ 0 &
|
||
0\end{matrix}\right).$$ Опять же, в левой части стоит произведение
|
||
обратимых матриц, поэтому и матрица в правой части должна быть
|
||
обратимой. Но матрица вида $\left(\begin{matrix} E_r & 0 \\
|
||
0 & 0\end{matrix}\right)$ может быть обратимой только при
|
||
$r=n$. Действительно, если $r<n$, то у нее последняя строка равна
|
||
нулю, и в любом произведении этой матрицы на другую последняя строка
|
||
также нулевая; поэтому это произведение не может быть единичной
|
||
матрицей.
|
||
\end{proof}
|
||
|
||
\subsection{Блочные матрицы}
|
||
|
||
При работе с большими матрицами часто удобно разбивать их на
|
||
кусочки поменьше. Мы видели это в теореме~\ref{thm_pdq}:
|
||
окаймленная единичная матрица размера $m\times n$ и ранга $r$
|
||
имеет вид
|
||
$\begin{pmatrix}
|
||
E_r & 0\\ 0 & 0
|
||
\end{pmatrix}$.
|
||
Вообще, пусть $m = m_1 + \dots + m_s$, $n = n_1 + \dots + n_t$~---
|
||
разбиения чисел $m$ и $n$ в сумму $s$ и $t$ слагаемых, соответственно.
|
||
Тогда матрица $A\in M(m,n,R)$ разбивается
|
||
на $st$ матриц с размерами $m_i\times n_j$: мы группируем
|
||
первые $m_1$ строк, следующие $m_2$ строк, и так далее;
|
||
а также первые $n_1$ столбцов, следующие $n_2$, и так далее.
|
||
Обозначим эти блоки через $x_{ij}\in M(m_i,n_j,R)$ для
|
||
$i=1,\dots,s$, $j=1,\dots,t$.
|
||
Матрица с выбранными разбиениями множеств строк и столбцов
|
||
называется \dfn{блочной матрицей}\index{блочная матрица}
|
||
указание разбиений строк и столбцов
|
||
называется \dfn{блочной структурой}\index{блочная структура}.
|
||
Например, в приведенном выше примере окаймленная
|
||
единичная матрица имеет вид
|
||
$\begin{pmatrix}
|
||
E_r & 0\\ 0 & 0
|
||
\end{pmatrix}$.
|
||
в соответствии с разбиениями $m = r + (m-r)$, $n = r + (n-r)$.
|
||
|
||
Пусть теперь $B\in M(m,n,R)$~--- еще одна матрица того же размера,
|
||
что и $A$, и пусть для $B$ выбраны те же разбиения
|
||
$m = m_1 + \dots + m_s$, $n = n_1 + \dots + n_t$; таким образом,
|
||
у матрицы $B$ есть блоки $y_{ij}\in M(m_i,n_j,R)$.
|
||
Посмотрим на сумму $A+B$. Это снова матрица из $M(m,n,R)$.
|
||
Можно и ее разбить на блоки тем же образом и
|
||
получить блоки $z_{ij}\in M(m_i,n_r,R)$.
|
||
Нетрудно понять, что $z_{ij} = x_{ij} + y_{ij}$ для всех $i=1,\dots,s$,
|
||
$j=1,\dots,t$. Иными словами,
|
||
блочные матрицы с одной и той же блочной структурой
|
||
складываются <<поблочно>>.
|
||
|
||
Посмотрим теперь, как перемножаются блочные матрицы.
|
||
Пусть $A\in M(m,n,R)$, $B\in M(n,p,R)$, и пусть выбраны разбиения
|
||
чисел $m,n,p$: $m = m_1 + \dots + m_s$, $n = n_1 + \dots + n_t$,
|
||
$p = p_1 + \dots + p_u$.
|
||
Тогда $A$ является блочной матрицей с блоками, скажем,
|
||
$x_{ij}\in M(m_i,n_j,R)$, а $B$~--- блочной матрицей с блоками
|
||
$y_{jk}\in M(n_j,p_k,R)$.
|
||
Их произведение $AB$ лежит в $M(m,p,R$), и его можно рассмотреть
|
||
как блочную матрицу в соответствии с указанными разбиениями
|
||
чисел $m$ и $p$.
|
||
Блоки матрицы $AB$ обозначим через $z_{ik}\in M(m_i,p_k,R)$.
|
||
Как блок $z_{ik}$ связан с блоками матриц $A$ и $B$?
|
||
Оказывается
|
||
$$
|
||
z_{ik} = x_{i1}y_{1k} + \dots + x_{it}y_{tk}
|
||
= \sum_{j=1}^t x_{ij}y_{jk}.
|
||
$$
|
||
Таким образом, блочные матрицы можно перемножать <<поблочно>>,
|
||
и формула для каждого блока в произведении выглядит точно так же,
|
||
как формула для элемента в произведении матриц.
|
||
Обратите внимание, однако, что теперь в этом произведении
|
||
элементы $x_{ij}$ и $y_{jk}$ являются матрицами, так что
|
||
мы должны следить за порядком, в котором они перемножаются.
|
||
|
||
%%% коллоквиум
|
||
|
||
%%% 2015
|
||
|
||
\subsection{Перестановки}\label{subsect:permutations}
|
||
\literature{[F], гл. IV, \S~2, п. 2.}
|
||
|
||
Нам необходимо на время отвлечься от линейной алгебры, чтобы
|
||
ввести важное понятие {\it группы перестановок}.
|
||
Пусть $X$~--- некоторое
|
||
множество. \dfn{Перестановкой}\index{перестановка} на множестве
|
||
$X$ называется биекция $X\to X$. Заметим, что любая биекция обратима:
|
||
если $\pi\colon X\to X$~--- биекция, то существует и обратное
|
||
отображение $\pi^{-1}\colon X\to X$, также являющееся биекцией, такое,
|
||
что $\pi\circ\pi^{-1}$ и $\pi^{-1}\circ\pi$ тождественны. Напомним
|
||
также, что композиция отображений ассоциативна.
|
||
|
||
\begin{definition}\label{def_group}
|
||
Множество $G$ с бинарной операцией $\circ\colon G\to G$ называется
|
||
\dfn{группой}\index{группа}, если выполняются следующие свойства:
|
||
\begin{itemize}
|
||
\item $a\circ (b\circ c)=(a\circ b)\circ c$ для всех $a,b,c\in G$;
|
||
(\dfn{ассоциативность}\index{ассоциативность!в группе});
|
||
\item существует элемент $e\in G$ (\dfn{единичный
|
||
элемент}\index{единичный элемент!в группе}) такой, что
|
||
для любого $a\in G$
|
||
выполнено $a\circ e=e\circ a=a$;
|
||
\item для любого $a\in G$ найдется элемент $a^{-1}\in G$ (называемый
|
||
\dfn{обратным}\index{обратный элемент!в группе} к $a$) такой, что
|
||
$a\circ a^{-1}=a^{-1}\circ a=e$.
|
||
\end{itemize}
|
||
\end{definition}
|
||
|
||
\begin{definition}\label{def:symmetric_group}
|
||
Множество всех биекций из $X$ в $X$ обозначается через $S(X)$ и
|
||
называется \dfn{группой перестановок}\index{группа!перестановок}
|
||
множества $X$. Тождественное
|
||
отображение $\id_X\colon X\to X$ называется \dfn{тождественной
|
||
перестановкой}\index{тождественная перестановка}.
|
||
\end{definition}
|
||
Как мы заметили выше, $S(X)$ действительно является группой в смысле
|
||
определения~\ref{def_group} относительно операции композиции, которая
|
||
еще называется \dfn{умножением}\index{умножение перестановок} перестановок.
|
||
|
||
Зачастую нам не важна природа элементов множества $X$, а важно лишь их
|
||
количество, особенно если $X$ конечно. Поэтому для каждого
|
||
натурального $n$ можно рассматривать
|
||
группу перестановок какого-нибудь выделенного множества из $n$
|
||
элементов, например, множества $\{1,\dots,n\}$. Эта группа
|
||
обозначается через $S_n$: $S(\{1,\dots,n\})=S_n$.
|
||
Элемент $\pi$ группы $S_n$ можно записывать в виде таблицы из двух
|
||
строк, в первой строке которой стоят числа $1,\dots,n$ (как правило, в
|
||
порядке возрастания), а под каждым
|
||
из них стоит его образ $\pi(1),\dots,\pi(n)$:
|
||
$$
|
||
\pi=\begin{pmatrix} 1 & 2 & \dots & n\\
|
||
\pi(1) & \pi(2) & \dots & \pi(n)\end{pmatrix}.
|
||
$$
|
||
Понятно, что по такой записи однозначно восстанавливается элемент
|
||
$\pi$, и обратно, если есть таблица, в первой строке которой стоят
|
||
числа $1,\dots,n$, а во второй~--- те же самые числа в каком-то
|
||
порядке, то она задает некоторый элемент $S_n$. Такая запись
|
||
называется \dfn{табличной записью}\index{табличная запись
|
||
перестановки} перестановки.
|
||
Например, группа $S_1$ состоит из одного (тождественного) элемента
|
||
$\left(\begin{matrix} 1 \\ 1\end{matrix}\right)$. Группа $S_2$ состоит
|
||
из двух элементов: один из них тождественный,
|
||
$\begin{pmatrix} 1 & 2\\ 1 & 2\end{pmatrix}$,
|
||
а другой переставляет местами $1$ и $2$:
|
||
$\begin{pmatrix} 1 & 2\\ 2 & 1\end{pmatrix}$. Группа $S_3$
|
||
состоит из шести элементов:
|
||
$$
|
||
S_3=\left\{\begin{pmatrix} 1 & 2 & 3\\ 1 & 2 & 3\end{pmatrix},
|
||
\begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2\end{pmatrix},
|
||
\begin{pmatrix} 1 & 2 & 3\\ 2 & 1 & 3\end{pmatrix},
|
||
\begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1\end{pmatrix},
|
||
\begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2\end{pmatrix},
|
||
\begin{pmatrix} 1 & 2 & 3\\ 3 & 2 & 1\end{pmatrix}\right\}.
|
||
$$
|
||
Несложное комбинаторное рассуждение показывает, что количество
|
||
элементов в $S_n$ равно $n!$. Действительно, образом элемента $1$
|
||
может быть любой из $n$ элементов множества $\{1,\dots,n\}$, образом
|
||
элемента $2$~--- любой из оставшихся $n-1$, и так далее; всего
|
||
получаем $n\cdot (n-1)\cdot\dots\cdot 1=n!$ различных вариантов.
|
||
|
||
Табличная запись позволяет визуализировать перемножение перестановок:
|
||
для того, чтобы перемножить перестановки $\pi$ и $\rho$, нужно
|
||
записать друг под другом табличные записи $\pi$ и $\rho$, переставить
|
||
столбцы в таблице $\rho$ так, чтобы в первой строке оказалась {\it
|
||
вторая} строка таблицы $\pi$, и сформировать ответ из первой строки
|
||
верхней таблицы и второй строки нижней таблицы~--- это будет табличной
|
||
записью перестановки $\rho\circ\pi$. Обратите внимание на порядок!
|
||
Напомним, что мы записываем композицию отображений {\it справа
|
||
налево}: запись $\rho\circ\pi$ означает, что мы сначала применяем
|
||
отображение $\pi$, а затем~--- отображение $\rho$.
|
||
Это важно, поскольку при $n\geq 3$ умножение в группе $S_n$
|
||
некоммутативно. Действительно, рассмотрим перестановки
|
||
$\pi=\begin{pmatrix}1 & 2 & 3 \\ 1 & 3 & 2\end{pmatrix}$ и
|
||
$\rho=\begin{pmatrix}1 & 2 & 3 \\ 2 & 3 & 1\end{pmatrix}$.
|
||
Перемножим их по описанному выше способу:
|
||
$$
|
||
\rho\circ\pi\colon
|
||
\begin{matrix}
|
||
\begin{pmatrix}1 & 2 & 3 \\ 1 & 3 & 2\end{pmatrix}
|
||
\\
|
||
\begin{pmatrix}1 & 2 & 3 \\ 2 & 3 & 1\end{pmatrix}
|
||
\end{matrix}
|
||
\to
|
||
\begin{matrix}
|
||
\begin{pmatrix}1 & 2 & 3 \\ 1 & 3 & 2\end{pmatrix}
|
||
\\
|
||
\begin{pmatrix}1 & 3 & 2 \\ 2 & 1 & 3\end{pmatrix}
|
||
\end{matrix}
|
||
\to
|
||
\begin{pmatrix}1 & 2 & 3 \\ 2 & 1 & 3\end{pmatrix}
|
||
$$
|
||
$$
|
||
\pi\circ\rho\colon
|
||
\begin{matrix}
|
||
\begin{pmatrix}1 & 2 & 3 \\ 2 & 3 & 1\end{pmatrix}
|
||
\\
|
||
\begin{pmatrix}1 & 2 & 3 \\ 1 & 3 & 2\end{pmatrix}
|
||
\end{matrix}
|
||
\to
|
||
\begin{matrix}
|
||
\begin{pmatrix}1 & 2 & 3 \\ 2 & 3 & 1\end{pmatrix}
|
||
\\
|
||
\begin{pmatrix}2 & 3 & 1 \\ 3 & 2 & 1\end{pmatrix}
|
||
\end{matrix}
|
||
\to
|
||
\begin{pmatrix}1 & 2 & 3 \\ 3 & 2 & 1\end{pmatrix}
|
||
$$
|
||
Мы получили, что $\rho\circ\pi=\begin{pmatrix}1 & 2 & 3 \\ 2 & 1 &
|
||
3\end{pmatrix}$,
|
||
$\pi\circ\rho=\begin{pmatrix}1 & 2 & 3 \\ 3 & 2 & 1\end{pmatrix}$, и
|
||
видно, что это разные перестановки: $\rho\circ\pi\neq\pi\circ\rho$.
|
||
|
||
% 27.02.2013
|
||
|
||
Сейчас мы покажем, что любая перестановка представляется в виде
|
||
произведения перестановок простейшего вида. Интуитивно ясно, что
|
||
простейшей [нетождественной] перестановкой является та, которая лишь
|
||
меняется местами два элемента, а остальные оставляет на своих местах.
|
||
|
||
\begin{definition}
|
||
Пусть $1\leq i,j\leq n$ и $i\neq j$. Обозначим через $\tau_{ij}$
|
||
следующую перестановку:
|
||
$$
|
||
\begin{cases}
|
||
\tau_{ij}(i)&=j,\\
|
||
\tau_{ij}(j)&=i,\\
|
||
\tau_{ij}(k)&=k\text{ при $k\neq i,j$}.
|
||
\end{cases}
|
||
$$
|
||
Ее табличная запись выглядит так:
|
||
$$
|
||
\begin{pmatrix}
|
||
\dots & i & \dots & j & \dots\\
|
||
\dots & j & \dots & i & \dots.
|
||
\end{pmatrix}
|
||
$$
|
||
(подразумевается, что все столбики с многоточиями отвечают {\it
|
||
неподвижным} элементам).
|
||
Такая перестановка называется \dfn{транспозицией}\index{транспозиция}. Перестановка вида
|
||
$\tau_{i,i+1}$ (при $1\leq i\leq n-1$) называется \dfn{элементарной
|
||
транспозицией}\index{транспозиция!элементарная}.
|
||
\end{definition}
|
||
Очевидно, что любая транспозиция $\tau_{ij}$ совпадает с $\tau_{ji}$ и
|
||
является обратной к себе самой: $\tau_{ij}=\tau_{ji}$,
|
||
$\tau_{ij}\circ\tau_{ij}=\id$.
|
||
Посмотрим, что происходит при умножении перестановки на транспозицию:
|
||
сравним табличные записи перестановок $\pi$ и
|
||
$\pi\circ\tau_{ij}$. Нетрудно видеть, что они различаются только в
|
||
столбцах с номерами $i$ и $j$ (поскольку $\tau_{ij}$ совпадает с
|
||
тождественной в остальных точках). А именно,
|
||
$$
|
||
\pi=\begin{pmatrix}\dots & i & \dots & j & \dots\\
|
||
\dots & \pi(i) & \dots & \pi(j) & \dots\end{pmatrix},\quad
|
||
\pi\circ\tau_{ij}=\begin{pmatrix}\dots & i & \dots & j & \dots\\
|
||
\dots & \pi(j) & \dots & \pi(i) & \dots\end{pmatrix}.
|
||
$$
|
||
Иными словами, домножение на $\tau_{ij}$ справа соответствует
|
||
перестановке $i$-ой и $j$-ой позиций в нижней строке табличной записи
|
||
перестановки.
|
||
|
||
\begin{proposition}\label{prop:product_of_transpositions}
|
||
Любая перестановка является произведением транспозиций.
|
||
\end{proposition}
|
||
\begin{proof}
|
||
Пусть $\pi\in S_n$.
|
||
Начнем с тождественной перестановки $\id$ и покажем, что
|
||
последовательным домножением на транспозиции справа можно получить
|
||
перестановку $\pi$. Сначала добьемся того, чтобы на первом месте в
|
||
нижней строке табличной записи нашей перестановки стояло то, что
|
||
нужно~--- то есть, $\pi(1)$. Для этого нужно переставить местами
|
||
первый столбик с тем, в котором стоит $\pi(1)$ (Конечно, если
|
||
$\pi(1)=1$, ничего переставлять и не нужно). После этого поставим
|
||
на второе место в нижней строке $\pi(2)$: так как $\pi$ является
|
||
перестановкой, то $\pi(1)\neq\pi(2)$, поэтому где-то справа от первого
|
||
столбца есть столбец с $\pi(2)$. Поменяем его со вторым. И так далее:
|
||
на $k$-шаге мы добиваемся того, что первые $k$ чисел в нижней строке
|
||
нашей перестановки выглядели так: $\pi(1),\pi(2),\dots,\pi(k)$. В
|
||
конце концов (дойдя до $k=n$) мы получим перестановку $\pi$ путем
|
||
домножения $\id$ на транспозиции, что и требовалось.
|
||
\end{proof}
|
||
\begin{proposition}\label{prop_odd_number_of_elementary_transpositions}
|
||
Любая транспозиция является произведением нечетного числа элементарных
|
||
транспозиций.
|
||
\end{proposition}
|
||
\begin{proof}
|
||
Неформально задача выглядит так: нам разрешено менять местами любые
|
||
два соседних элемента в строке, а хочется поменять местами два
|
||
элемента, стоящих далеко друг от друга. Как этого добиться? Очень
|
||
просто: сначала «продвинуть» последовательно левый из этих элементов
|
||
направо до второго, поменять их там местами, а потом второй элемент
|
||
«отогнать» обратно на место левого. При этом наши элементы поменяются
|
||
местами, а все остальные элементы останутся на своих местах: любой
|
||
элемент между нашими мы затронем ровно два раза: на пути «туда» и на
|
||
пути «обратно»; сначала он сдвинется на шаг влево, а потом~--- на шаг
|
||
вправо. Ну, а любой элемент, стоящий не между нашими, и подавно
|
||
останется на своем месте. Аккуратный подсчет показывает, что мы
|
||
совершили нечетное число операций.
|
||
|
||
Формально же это рассуждение выражается в виде формулы
|
||
$$
|
||
\tau_{ij}=\tau_{i,i+1}\circ\tau_{i+1,i+2}\circ\dots
|
||
\circ\tau_{j-2,j-1}\circ\tau_{j-1,j}\circ\tau_{j-2,j-1}\circ\dots
|
||
\tau_{i+1,i+2}\circ\tau_{i,i+1}
|
||
$$
|
||
(здесь мы считаем, что $i<j$).
|
||
Это равенство несложно проверить напрямую, и оно представляет
|
||
транспозицию $\tau_{ij}$ в виде произведения $2(j-i)-1$ элементарных
|
||
транспозиций.
|
||
\end{proof}
|
||
|
||
\begin{definition}
|
||
Пусть $\pi\in S_n$. Говорят, что пара индексов $(i,j)$ образует
|
||
\dfn{инверсию}\index{инверсия} для перестановки $\pi$, если $i<j$ и
|
||
$\pi(i)>\pi(j)$. Количество пар индексов от $1$ до $n$, образующих
|
||
инверсию для $\pi$, называется \dfn{числом инверсий}\index{число
|
||
инверсий перестановки} перестановки
|
||
$\pi$ и обозначается через $\inv(\pi)$.
|
||
\end{definition}
|
||
Неформально говоря, число инверсий измеряет «отклонение» перестановки
|
||
от тождественной: если $\pi=\id$, то для $i<j$ всегда выполнено
|
||
$\pi(i)=i<j=\pi(j)$, поэтому $\inv(\id)=0$. Число инверсий~--- это
|
||
количество пар элементов, стоящих в «неправильном» порядке.
|
||
Важнейшей характеристикой перестановки является {\it четность} ее
|
||
числа инверсий, которая называется {\it знаком}:
|
||
\begin{definition}\label{def:permutation_sign}
|
||
Пусть $\pi\in S_n$. Число $(-1)^{\inv(\pi)}$ называется
|
||
\dfn{знаком}\index{знак перестановки}
|
||
перестановки $\pi$ и обозначается через $\sgn(\pi)$. Иными словами,
|
||
$\sgn(\pi)=1$, если $\inv(\pi)$ четно, и $\sgn(\pi)=-1$, если
|
||
$\inv(\pi)$ нечетно. Перестановка называется \dfn{четной}\index{четная
|
||
перестановка}, если
|
||
$\sgn(\pi)=1$, и \dfn{нечетной}\index{нечетная перестановка}, если $\sgn(\pi)=-1$.
|
||
\end{definition}
|
||
\begin{example}
|
||
Единственный элемент в $S_1$ является четной перестановкой.
|
||
Одна из двух перестановок в $S_2$ (тождественная) является четной, а
|
||
другая~--- нечетной. Среди шести перестановок в $S_3$ имеется три
|
||
четных и три нечетных: четными являются $\id$,
|
||
$\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}$ и
|
||
$\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}$, а нечетными~---
|
||
транспозиции $\tau_{12}$, $\tau_{13}$ и $\tau_{23}$.
|
||
\end{example}
|
||
Оказывается, если перестановка представлена в виде произведения
|
||
транспозиций, то четность числа этих транспозиций всегда совпадает с
|
||
четностью перестановки (хотя понятно, что у перестановки может быть
|
||
много различных представлений в виде произведения транспозиций).
|
||
Для доказательства этого нам необходимо посмотреть на то, что
|
||
происходит со знаком при домножении перестановки на
|
||
транспозицию.
|
||
\begin{proposition}\label{prop_transposition_changes_sign}
|
||
Пусть $\pi\in S_n$, $\tau_{ij}\in S_n$~--- транспозиция. Тогда
|
||
$\sgn(\pi)=-\sgn(\pi\circ\tau_{ij})$.
|
||
\end{proposition}
|
||
\begin{proof}
|
||
Посмотрим, как меняется число инверсий перестановки при домножении на
|
||
{\it элементарную транспозицию}. Сравним перестановки
|
||
$$
|
||
\pi=\begin{pmatrix}\dots&i&i+1&\dots\\
|
||
\dots&\pi(i)&\pi(i+1)&\dots\end{pmatrix}\text{ и }
|
||
\pi\circ\tau_{i,i+1}=\begin{pmatrix}\dots&i&i+1&\dots\\
|
||
\dots&\pi(i+1)&\pi(i)&\dots\end{pmatrix}.
|
||
$$
|
||
Заметим, что вне столбцов с номерами $i$ и $i+1$ эти перестановки
|
||
совпадают, поэтому число инверсий для индексов вне множества
|
||
$\{i,i+1\}$, у них одинаковое. Далее, если для некоторого
|
||
$j\notin\{i,i+1\}$ индексы $i$ и $j$ образуют
|
||
инверсию для $\pi$ (например, мы имели $j<i$ и $\pi(j)>\pi(i)$), то
|
||
$i+1$ и $j$ образуют инверсию для $\pi\circ\tau_{i,i+1}$,
|
||
(поскольку
|
||
$(\pi\circ\tau_{i,i+1})(i+1)=\pi(i)<\pi(j)=(\pi\circ\tau_{i,i+1})(j)$
|
||
и $j<i+1$), и наоборот. Аналогично, если $i+1$ и $j$ образуют
|
||
инверсию для $\pi$, то $i$ и $j$ образуют инверсию для
|
||
$\pi\circ\tau_{i,i+1}$, и наоборот. Поэтому среди всех пар индексов,
|
||
кроме пары $(i,j)$, количество инверсий у $\pi$ и
|
||
$\pi\circ\tau_{i,i+q}$ одинаковое. Но если $(i,i+1)$ является
|
||
инверсией для $\pi$, то $(i,i+1)$ не является инверсией для
|
||
$\pi\circ\tau_{i,i+1}$, поскольку значения $\pi$ и
|
||
$\pi\circ\tau_{i,i+1}$ на $i$ и $i+1$ поменялись местами. Обратно,
|
||
если пара $(i,i+1)$ не была инверсией для $\pi$, она станет инверсией
|
||
для $\pi\circ\tau_{i,i+1}$. Значит, число инверсий
|
||
$\pi\circ\tau_{i,i+1}$ отличается от числа инверсий $\tau_{i,i+1}$
|
||
ровно на единицу: $\inv(\pi\circ\tau_{i,i+1})=\inv(\pi)\pm 1$. Поэтому
|
||
эти числа имеют разную четность.
|
||
|
||
Это означает, что при домножении на элементарную транспозицию
|
||
перестановка меняет знак. По
|
||
предложению~\ref{prop_odd_number_of_elementary_transpositions} любую
|
||
транспозицию можно записать как произведение нечетного числа
|
||
элементарных, поэтому при домножении на любую транспозицию
|
||
перестановка меняет знак нечетное число раз~--- то есть, меняет знак.
|
||
\end{proof}
|
||
|
||
\begin{corollary}\label{cor_sign_and_number_of_transpositions}
|
||
Пусть $\pi=\tau_1\circ\dots\circ\tau_s$, где $\tau_1,\dots,\tau_s$~---
|
||
транспозиции. Тогда $\sgn(\pi)=(-1)^s$.
|
||
\end{corollary}
|
||
\begin{proof}
|
||
Запишем $\pi=\id\circ\tau_1\circ\dots\circ\tau_s$ и посмотрим на это
|
||
произведение так: мы начали с тождественной перестановки и $s$ раз
|
||
домножили на транспозиции справа. Тождественная перестановка является
|
||
четной, и при каждом домножении знак меняется на противоположный,
|
||
поэтому итоговый знак равен $(-1)^s$.
|
||
\end{proof}
|
||
|
||
\begin{corollary}\label{cor_odd_and_even}
|
||
При $n\geq 2$ в группе $S_n$ поровну (по $n!/2$) четных и нечетных перестановок.
|
||
\end{corollary}
|
||
\begin{proof}
|
||
Рассмотрим отображение $f\colon S_n\to S_n$, $\pi\mapsto
|
||
\pi\circ\tau_{12}$. Нетрудно видеть, что это биекция (обратным к этому
|
||
отображению является оно само: $(f\circ
|
||
f)(\pi)=f(f(\pi))=(\pi\circ\tau_{12})\circ\tau_{12}=\pi$, поэтому
|
||
$f\circ f=\id_{S_n}$). При этом по
|
||
предложению~\ref{prop_transposition_changes_sign} $f$ переводит четные
|
||
перестановки в нечетные, а нечетные~--- в четные. Поэтому $f$
|
||
устанавливает биекцию между подмножеством четных перестановок и
|
||
подмножеством нечетных перестановок в $S_n$. Всего перестановок $n!$,
|
||
поэтому и четных, и нечетных по $n!/2$.
|
||
\end{proof}
|
||
|
||
Теперь несложно показать, что знак ведет себя мультипликативно:
|
||
|
||
\begin{theorem}\label{thm:permutation_sign_product}
|
||
Пусть $\pi,\rho\in S_n$; тогда
|
||
$\sgn(\pi\circ\rho)=\sgn(\pi)\cdot\sgn(\rho)$.
|
||
\end{theorem}
|
||
\begin{proof}
|
||
Представим $\pi$ и $\rho$ в виде произведения транспозиций:
|
||
$\pi=\sigma_1\circ\dots\circ\sigma_s$,
|
||
$\rho=\tau_1\circ\dots\circ\tau_t$. По
|
||
следствию~\ref{cor_sign_and_number_of_transpositions} имеем
|
||
$\sgn(\pi)=(-1)^s$ и $\sgn(\rho)=(-1)^t$. При этом
|
||
$\pi\circ\rho=\sigma_1\circ\dots\circ\sigma_s\circ\tau_1\circ\dots\circ\tau_t$
|
||
есть произведение $s+t$ транспозиций, поэтому $\sgn(\pi\circ\rho)=(-1)^{s+t}=(-1)^s\cdot(-1)^t=\sgn(\pi)\cdot\sgn(\rho)$.
|
||
\end{proof}
|
||
|
||
\begin{corollary}\label{cor:permutation_sign_inverse}
|
||
Пусть $\pi\in S_n$; тогда $\sgn(\pi^{-1})=\sgn(\pi)$.
|
||
\end{corollary}
|
||
\begin{proof}
|
||
Заметим, что $\pi\circ\pi^{-1}=\id$, поэтому
|
||
$\sgn(\pi)\cdot\sgn(\pi^{-1})=\sgn(\id)=1$.
|
||
\end{proof}
|
||
|
||
\subsection{Определитель}\label{ssect:det}
|
||
\literature{[F], гл. IV, \S~2, пп. 1, 3, 4; [K1], гл. 3, \S~1; [vdW], гл. 4, \S~25.}
|
||
|
||
Теперь все готово, чтобы ввести интересный инвариант квадратной
|
||
матрицы.
|
||
\begin{definition}
|
||
Пусть $A=(a_{ij})\in M(n,k)$~--- квадратная матрица над полем $k$. Ее
|
||
\dfn{определителем}\index{определитель} (или \dfn{детерминантом}\index{детерминант}) называется следующий
|
||
элемент поля $k$:
|
||
$$
|
||
\det(A)=\sum_{\pi\in S_n}\sgn(\pi)\cdot a_{1,\pi(1)}\cdot
|
||
a_{2,\pi(2)}\cdot\dots\cdot a_{n,\pi(n)}=\sum_{\pi\in S_n}\sgn(\pi)\prod_{i=1}^na_{i,\pi(i)}.
|
||
$$
|
||
Мы будем также использовать обозначение $|A|=\det(A)$.
|
||
\end{definition}
|
||
|
||
\begin{examples}
|
||
\begin{itemize}
|
||
\item Определитель матрицы $1\times 1$: в этом случае в сумме из
|
||
определения
|
||
$\det(A)$ всего одно слагаемое, и знак тождественной перестановки
|
||
равен $1$, поэтому
|
||
$\det(\begin{pmatrix}a_{11}\end{pmatrix})=a_{11}$.
|
||
\item Определитель матрицы $2\times 2$: $S_2=\{\id,\tau_{12}\}$,
|
||
причем $\sgn(\id)=1$, $\sgn(\tau_{12})=-1$, поэтому
|
||
$$\left|\begin{matrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{matrix}\right|=a_{11}a_{22}-a_{12}a_{21}.$$
|
||
\item Определитель матрицы $3\times 3$:
|
||
$$
|
||
\left|\begin{matrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\
|
||
a_{31}&a_{32}&a_{33}\end{matrix}\right| = a_{11}a_{22}a_{33} +
|
||
a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} - a_{12}a_{21}a_{33} -
|
||
a_{13}a_{31}a_{22} - a_{11}a_{23}a_{32}.
|
||
$$
|
||
\end{itemize}
|
||
\end{examples}
|
||
|
||
Выясним простейшие свойства определителя.
|
||
\begin{proposition}
|
||
Пусть $A\in M(n,k)$; тогда $\det(A^T)=\det(A)$.
|
||
\end{proposition}
|
||
\begin{proof}
|
||
Посмотрим на формулу для определителя матрицы $A=(a_{ij})$. В
|
||
слагаемом, соответствующем
|
||
перестановке $\pi$, перемножаются элементы вида $a_{i,\pi(i)}$, то
|
||
есть, элементы вида $a_{ij}$ для $j=\pi(i)$. Заметим, что $j=\pi(i)$
|
||
тогда и только тогда, когда $\pi^{-1}(j)=i$. Иными словами, в
|
||
рассматриваемом слагаемом перемножаются элементы вида
|
||
$a_{\pi^{-1}(j),j}$ для всех $j=1,\dots,n$.
|
||
Поэтому мы можем записать
|
||
$$
|
||
\det(A)=\sum_{\pi\in S_n}\sgn(\pi)\prod_{i=1}^n a_{i,\pi(i)}
|
||
=\sum_{\pi\in S_n}\sgn(\pi)\prod_{j=1}^n a_{\pi^{-1}(j),j}
|
||
=\sum_{\pi\in S_n}\sgn(\pi)\prod_{j=1}^n a_{\pi(j),j}.
|
||
$$
|
||
В последнем равенстве мы воспользовались тем фактом, что если $\pi$
|
||
пробегает всю группу $S_n$, то и $\pi^{-1}$ пробегает всю $S_n$; кроме
|
||
того, $\sgn(\pi)=\sgn(\pi^{-1})$, поэтому можно заменить суммирование
|
||
по всем $\pi$ на суммирование по всем $\pi^{-1}$.
|
||
Но последнее выражение совпадает с формулой для $\det(A^T)$: элемент
|
||
матрицы $A$, стоящий в позиции $(\pi(j),j)$~--- это в точности элемент
|
||
матрицы $A^T$, стоящий в позиции $(j,\pi(j))$.
|
||
\end{proof}
|
||
|
||
Следующие свойства определителя касаются его зависимость от различных
|
||
операций над строками.
|
||
Пусть $A=(a_{ij})\in M(n,k)$~--- квадратная
|
||
матрица, $(a'_{i1},a'_{i2},\dots,a'_{in})$~--- некоторая
|
||
строка. Рассмотрим матрицу $A'$, полученную заменой $i$-ой строки
|
||
матрицы $A$ на строку $(a'_{i1},a'_{i2},\dots,a'_{in})$, и матрицу
|
||
$A''$, полученную заменой $i$-ой строки матрицы $A$ на строку
|
||
$(a_{i1}+a'_{i1}, a_{i2}+a'_{i2},\dots, a_{in}+a'_{in})$. Схематично
|
||
мы будем изображать это так:
|
||
$$
|
||
\begin{array}{c}
|
||
A=\begin{pmatrix}\vdots & \vdots & \ddots & \vdots\\
|
||
a_{i1} & a_{i2} & \dots & a_{in}\\
|
||
\vdots & \vdots & \ddots & \vdots\end{pmatrix},
|
||
A'=\begin{pmatrix}\vdots & \vdots & \ddots & \vdots\\
|
||
a'_{i1} & a'_{i2} & \dots & a'_{in}\\
|
||
\vdots & \vdots & \ddots & \vdots\end{pmatrix},\\
|
||
A''=\begin{pmatrix}\vdots & \vdots & \ddots & \vdots\\
|
||
a_{i1}+a'_{i1} & a_{i2}+a'_{i2} & \dots & a_{in}+a'_{in}\\
|
||
\vdots & \vdots & \ddots & \vdots\end{pmatrix}.
|
||
\end{array}
|
||
$$
|
||
Здесь многоточия символизируют тот факт, что все три матрицы $A, A',
|
||
A''$ совпадают за пределами $i$-й строки.
|
||
Оказывается, что определитель ведет себя
|
||
\dfn{аддитивно}\index{аддитивность!определителя} по отношению
|
||
к строкам матрицы: $\det(A'')=\det(A)+\det(A')$. Иными словами, если
|
||
представить какую-нибудь строку матрицы в виде суммы двух строк, то
|
||
определитель исходной матрицы будет равен сумме определителей матриц,
|
||
в которых эта строка заменена на строки-слагаемые.
|
||
Нам будет удобнее записывать это следующим образом: обозначим
|
||
$u=(a_{i1},a_{i2},\dots,a_{in})$,
|
||
$v=(a'_{i1},a'_{i2},\dots,a'_{in})$ (таким образом, $u,v\in
|
||
M(1,n,k)$~--- две строки длины $n$). Тогда
|
||
$$
|
||
\left|\begin{matrix}\vdots \\ u+v \\ \vdots\end{matrix}\right|=
|
||
\left|\begin{matrix}\vdots \\ u \\ \vdots\end{matrix}\right|+
|
||
\left|\begin{matrix}\vdots \\ v \\ \vdots\end{matrix}\right|
|
||
$$
|
||
(здесь $u+v$ обозначает [покомпонентную] сумму строк $u$ и $v$, и
|
||
снова подразумевается, что в остальных позициях эти три матрицы
|
||
совпадают).
|
||
|
||
Посмотрим на формулу для определителя матрицы
|
||
$A''$:
|
||
$$
|
||
\det(A'')=\sum_{\pi\in S_n} \sgn(\pi) a_{1,\pi(1)} \dots
|
||
(a_{i,\pi(i)}+a'_{i,\pi(i)}) \dots a_{n,\pi(n)}
|
||
$$
|
||
(здесь мы воспользовались тем, что в $i$-ой строке матрицы $A''$ стоят
|
||
суммы соответствующих элементов $i$-х строк матриц $A$ и $A'$). Каждое
|
||
слагаемое выписанной суммы в силу дистрибутивности распадается на два
|
||
слагаемых, в одно из которых входит $a_{i,\pi(i)}$, а в другое~---
|
||
$a'_{i,\pi(i)}$:
|
||
\begin{align*}
|
||
\det(A'')&=\sum_{\pi\in S_n}\left(\sgn(\pi) a_{1,\pi(1)} \dots
|
||
a_{i,\pi(i)} \dots a_{n,\pi(n)} + \sgn(\pi)a_{1,\pi(1)} \dots
|
||
a'_{i,\pi(i)}) \dots a_{n,\pi(n)}\right)\\
|
||
&= \sum_{\pi\in S_n}\left(\sgn(\pi) a_{1,\pi(1)} \dots
|
||
a_{i,\pi(i)} \dots a_{n,\pi(n)}\right)
|
||
+ \sum_{\pi\in S_n}\left(\sgn(\pi) a_{1,\pi(1)} \dots
|
||
a'_{i,\pi(i)} \dots a_{n,\pi(n)}\right).
|
||
\end{align*}
|
||
Первое из полученных слагаемых в точности равно $\det(A)$, а второе
|
||
равно $\det(A')$, поэтому $\det(A'')=\det(A)+\det(A')$, что и
|
||
требовалось.
|
||
|
||
Кроме того, если все элементы некоторой строки умножить на $\lambda\in
|
||
k$, то и определитель матрицы умножится на $\lambda$. Точнее,
|
||
рассмотрим матрицу $A=(a_{ij})\in M(n,k)$ и заменим в ней $i$-ю строку
|
||
$(a_{i1},a_{i2},\dots,a_{in})$ на строку $(\lambda a_{i1}, \lambda
|
||
a_{i2}, \dots, \lambda a_{in})$. Обозначим полученную матрицу через
|
||
$A'$. Тогда $\det(A')=\lambda\det(A)$. Действительно, определитель
|
||
матрицы $A'$ равен
|
||
$$
|
||
\det(A') = \sum_{\pi\in S_n}\left(\sgn(\pi) a_{1,\pi(1)} \dots
|
||
(\lambda a_{i,\pi(i)}) \dots a_{n,\pi(n)}\right).
|
||
$$
|
||
В каждом слагаемом полученной суммы присутствует множитель
|
||
$\lambda$. После вынесения его за скобки получаем
|
||
$$
|
||
\det(A') = \lambda\left(\sum_{\pi\in S_n}\sgn(\pi) a_{1,\pi(1)} \dots
|
||
a_{i,\pi(i)} \dots a_{n,\pi(n)}\right) = \lambda\det(A).
|
||
$$
|
||
|
||
% 6.03.2013
|
||
|
||
Доказанные два свойства в совокупности называют \dfn{линейностью}\index{линейность!определителя}
|
||
определителя по строкам. Кроме того, определитель обладает
|
||
\dfn{кососимметричностью}\index{кососимметричность определителя} по
|
||
строкам:
|
||
если две строки матрицы $A=(a_{ij})\in M(n,k)$ совпадают, то ее
|
||
определитель равен
|
||
нулю. То есть, если найдутся такие индексы $i\neq j$, что
|
||
$a_{il}=a_{jl}$ для всех $l=1,\dots,n$, то $\det(A)=0$. Конечно,
|
||
кососимметричность имеет смысл только при $n\geq 2$.
|
||
|
||
Для доказательства кососимметричности заметим сначала, что отображение
|
||
$f\colon S_n\to S_n$, $\pi\mapsto f\circ\tau_{ij}$ является биекцией и
|
||
меняет четность перестановок. Мы уже видели такое отображение в
|
||
доказательстве следствия~\ref{cor_odd_and_even} для частного случая
|
||
$\{i,j\}=\{1,2\}$. Значит, ограничив должным образом отображение $f$,
|
||
мы получаем биекцию между множеством всех четных и множеством всех
|
||
нечетных перестановок. Обозначим множество всех четных перестановок из
|
||
$S_n$ через $A_n$, и для краткости будем писать $\tau$ вместо
|
||
$\tau_{ij}$. Получаем биекцию $A_n\to S_n\setminus A_n$,
|
||
$\pi\mapsto f\circ\tau$, которую мы обозначим также через $f$.
|
||
Теперь вернемся к нашей матрице $A=(a_{ij})\in M(n,k)$, в которой
|
||
$i$-ая строка совпадает с $j$-ой. Запишем определитель матрицы $A$:
|
||
$$
|
||
\det(A)=\sum_{\pi\in S_n}\sgn(\pi)a_{1,\pi(1)}\dots a_{i,\pi(i)}\dots
|
||
a_{j,\pi(j)}\dots a_{n,\pi(n)}.
|
||
$$
|
||
Теперь при помощи биекции $f$ разобьем все слагаемые на пары, поставив
|
||
в одну пару слагаемые, соответствующие перестановкам $\pi\in A_n$ и
|
||
$f(\pi)=\pi\circ\tau\in S_n\setminus A_n$:
|
||
\begin{align*}
|
||
\det(A)=\sum_{\pi\in A_n} & \big(\sgn(\pi)a_{1,\pi(1)}\dots
|
||
a_{i,\pi(i)}\dots a_{n,\pi(n)} +\\
|
||
& \sgn(\pi\circ\tau)a_{1,(\pi\circ\tau)(1)}\dots
|
||
a_{i,(\pi\circ\tau)(i)}\dots a_{j,(\pi\circ\tau)(j)}\dots
|
||
a_{n,(\pi\circ\tau)(n)} \big).\\
|
||
\end{align*}
|
||
Осталось заметить, что $\sgn(\pi\circ\tau)=-\sgn(\pi)$,
|
||
$a_{i,(\pi\circ\tau)(i)}=a_{i,\pi(j)}=a_{j,\pi(j)}$,
|
||
$a_{j,(\pi\circ\tau)(j)}=a_{j,\pi(i)}=a_{i,\pi(i)}$ и
|
||
$a_{k,(\pi\circ\tau)(k)}=a_{k,\pi(k)}$ для всех $k\neq i,j$. Поэтому
|
||
сумма двух слагаемых в каждой паре равна $0$, а с ней и весь
|
||
$\det(A)$.
|
||
|
||
Стало быть, нами доказана следующая теорема.
|
||
\begin{theorem}
|
||
Определитель линейно и кососимметрично зависит от строк матрицы. Иными
|
||
словами,
|
||
$$
|
||
\left|\begin{matrix}\vdots \\ u+v \\ \vdots\end{matrix}\right|=
|
||
\left|\begin{matrix}\vdots \\ u \\ \vdots\end{matrix}\right|+
|
||
\left|\begin{matrix}\vdots \\ v \\ \vdots\end{matrix}\right|,\quad
|
||
\left|\begin{matrix}\vdots \\ \lambda u \\ \vdots\end{matrix}\right|=
|
||
\lambda\left|\begin{matrix}\vdots \\ u \\ \vdots\end{matrix}\right|,\quad
|
||
\left|\begin{matrix}\vdots \\ u \\ \vdots \\ u \\
|
||
\vdots\end{matrix}\right| = 0.
|
||
$$
|
||
Кроме того, определитель линейно и кососимметрично зависит от столбцов
|
||
матрицы.
|
||
\end{theorem}
|
||
\begin{proof}
|
||
Утверждение для строк доказано выше; утверждение для столбцов
|
||
получается транспонированием матрицы.
|
||
\end{proof}
|
||
|
||
Теперь нетрудно понять, как меняется определитель при элементарных
|
||
преобразованиях строк и столбцов.
|
||
\begin{theorem}\label{thm_det_under_elementary}
|
||
Определитель матрицы не меняется при элементарном преобразовании
|
||
(строк или столбцов) первого типа, меняет знак при элементарном
|
||
преобразовании второго типа, и умножается на $\eps$ при элементарном
|
||
преобразовании $D_i(\eps)$ третьего типа. На матричном языке:
|
||
$$
|
||
|T_{ij}(\lambda)A|=|AT_{ij}(\lambda)|=|A|,\quad
|
||
|S_{ij}A|=|AS_{ij}|=-|A|,\quad
|
||
|D_i(\eps)A|=|AD_i(\eps)|=\eps|A|.
|
||
$$
|
||
\end{theorem}
|
||
\begin{proof}
|
||
Как всегда, мы проведем доказательство только для элементарных
|
||
преобразований строк. Рассмотрим элементарное преобразование первого
|
||
типа и воспользуемся линейностью:
|
||
$$
|
||
\left|\begin{matrix}\vdots \\ u+\lambda v \\ \vdots \\ v \\
|
||
\vdots\end{matrix}\right|=
|
||
\left|\begin{matrix}\vdots \\ u \\ \vdots \\ v \\
|
||
\vdots\end{matrix}\right|+
|
||
\lambda\left|\begin{matrix}\vdots \\ v \\ \vdots \\ v \\
|
||
\vdots\end{matrix}\right|.
|
||
$$
|
||
Заметим, что первое слагаемое результата~--- это определитель исходной
|
||
матрицы, а второе слагаемое равно нулю в силу кососимметричности.
|
||
|
||
Посмотрим на элементарные преобразования второго типа. Для любых строк
|
||
$u,v$ длины $n$ выполнено
|
||
$$
|
||
0 = \left|\begin{matrix}\vdots \\ u+v \\ \vdots \\ u+v \\
|
||
\vdots \end{matrix}\right| =
|
||
\left|\begin{matrix}\vdots \\ u \\ \vdots \\ u \\
|
||
\vdots\end{matrix}\right|+
|
||
\left|\begin{matrix}\vdots \\ u \\ \vdots \\ v \\
|
||
\vdots\end{matrix}\right|+
|
||
\left|\begin{matrix}\vdots \\ v \\ \vdots \\ u \\
|
||
\vdots\end{matrix}\right|+
|
||
\left|\begin{matrix}\vdots \\ v \\ \vdots \\ v \\
|
||
\vdots\end{matrix}\right| =
|
||
\left|\begin{matrix}\vdots \\ u \\ \vdots \\ v \\
|
||
\vdots\end{matrix}\right|+
|
||
\left|\begin{matrix}\vdots \\ v \\ \vdots \\ u \\
|
||
\vdots\end{matrix}\right|,
|
||
$$
|
||
откуда
|
||
$$
|
||
\left|\begin{matrix}\vdots \\ u \\ \vdots \\ v \\
|
||
\vdots\end{matrix}\right| = -
|
||
\left|\begin{matrix}\vdots \\ v \\ \vdots \\ u \\
|
||
\vdots\end{matrix}\right|.
|
||
$$
|
||
Это и означает, что элементарное преобразование второго типа меняет
|
||
знак определителя. Наконец, для элементарных преобразований третьего
|
||
типа утверждение теоремы напрямую следует из линейности определителя.
|
||
\end{proof}
|
||
|
||
\subsection{Дальнейшие свойства определителя}
|
||
\literature{[K1], гл. 3, \S~2, п. 2; [vdW], гл. 4, \S~19.}
|
||
|
||
\begin{theorem}[Определитель блочной верхнетреугольной матрицы]\label{thm_det_block_ut}
|
||
Пусть матрица $A\in M(n,k)$ имеет вид
|
||
$A=\begin{pmatrix}B & X\\0 & C\end{pmatrix}$, где
|
||
$B\in M(m,k)$, $C\in M(n-m,k)$, $X\in M(m,n-m,k)$. Тогда $|A|=|B|\cdot
|
||
|C|$.
|
||
\end{theorem}
|
||
\begin{proof}
|
||
Мы знаем, что $\det(A)=\sum_{\pi\in S_n}\sgn(\pi)a_{1,\pi(1)}\dots a_{m,\pi(m)}
|
||
a_{m+1,\pi(m+1)} \dots a_{n,\pi(n)}$.
|
||
По предположению, $a_{ij}=0$, если $i>m$ и $j\leq m$. Поэтому
|
||
некоторые слагаемые в этой сумме равны $0$. Покажем, что ненулевое
|
||
слагаемое не может содержать и множителей из блока $X$, то есть, не
|
||
может включать в себя множитель $a_{ij}$ для $i\leq m$, $j>m$.
|
||
Действительно, посмотрим на некоторое ненулевое слагаемое
|
||
$a_{1,\pi(1)}\dots a_{m,\pi(m)} a_{m+1,\pi(m+1)}\dots a_{n,\pi(n)}$,
|
||
соответствующее перестановке $\pi$.
|
||
Среди чисел $\pi(1),\dots,\pi(n)$ должны встречаться по разу числа
|
||
$1,\dots,m$. Если некоторое число $j\leq m$ равно $\pi(i)$, то
|
||
обязательно должно быть $i\leq m$, поскольку, по предположению,
|
||
$a_{ij}=0$ при $i>m$ и $j\leq m$. Значит, все числа $1,\dots,m$
|
||
встречаются среди чисел $\pi(1),\dots,\pi(m)$. Но тех и других
|
||
поровну, значит, $\pi(i)\leq m$ для любого $i\leq m$. Стало быть,
|
||
$\pi(i)>m$ для любого $i>m$. Мы получили, что наше слагаемое содержит
|
||
лишь множители вида $a_{ij}$, где либо $i,j\leq m$, либо $i,j>m$. В
|
||
частности, матричных элементов из блока $X$ среди них не встречается.
|
||
|
||
Таким образом, на самом деле суммирование в $\det(A)$ производится по
|
||
тем перестановкам $\pi$, которые действуют <<отдельно>> на наборах
|
||
$1,\dots,m$ и $m+1,\dots,n$, не переставляя числа из разных
|
||
наборов. Поэтому каждая такая перестановка однозначно определяет две
|
||
перестановки: на числах $1,\dots,m$ и на числах
|
||
$m+1,\dots,n$. Обозначим первую из них через $\rho$, а вторую сдвинем
|
||
на $m$ влево (чтобы получить перестановку чисел $1,\dots,n-m$, то
|
||
есть, элемент из $S_{n-m}$) и обозначим через $\sigma$. По
|
||
перестановке $\pi$ мы построили пару перестановок $\rho\in S_m$,
|
||
$\sigma\in S_{n-m}$.
|
||
|
||
Посмотрим теперь на произведение $\det(B)\cdot\det(C)$. Это
|
||
$$
|
||
\left(\sum_{\rho\in S_m}\sgn(\rho)a_{1,\rho(1)}\dots a_{m,\rho(m)}\right)\cdot
|
||
\left(\sum_{\sigma\in S_{n-m}}\sgn(\sigma)a_{m+1,m+\sigma(1)}\dots a_{n,m+\sigma(n-m)}\right).
|
||
$$
|
||
При раскрытии скобок в этом произведении получим сумму слагаемых вида
|
||
$$\sgn(\rho)\sgn(\sigma)a_{1,\rho(1)}\dots
|
||
a_{m,\rho(m)}a_{m+1,m+\sigma(1)}\dots a_{n,m+\sigma(n-m)}$$ для всех пар
|
||
перестановок $\rho\in S_m$, $\sigma\in S_{n-m}$. По каждой такой паре
|
||
перестановок построим перестановку $\pi\in S_n$, подействовав
|
||
перестановкой $\rho$ на числах $1,\dots,m$ и перестановкой $\sigma$
|
||
(сдвинутой на $m$ вправо) на числах $m+1,\dots,n$.
|
||
|
||
Теперь видно, что в формулах для $\det(A)$ и $\det(B)\cdot\det(C)$
|
||
происходит суммирование по всем парам перестановок $(\rho,\sigma)\in
|
||
S_m\times S_{n-m}$ слагаемых одинакового вида. Осталось лишь проверить
|
||
совпадение знаков: в первой формуле мы видим $\sgn(\pi)$, а во
|
||
второй~--- произведение $\sgn(\rho)\cdot\sgn(\sigma)$. Но нетрудно
|
||
видеть, что число инверсий в перестановке $\pi$ равно сумме чисел
|
||
инверсий в соответствующих им перестановках $\rho$ и $\sigma$: нет
|
||
никаких инверсий между числами из набора $1,\dots,m$ и числами из
|
||
набора $m+1,\dots,n$.
|
||
\end{proof}
|
||
|
||
\begin{corollary}\label{cor_ut_det}
|
||
Определитель верхнетреугольной матрицы равен произведению ее
|
||
диагональных элементов:
|
||
$$
|
||
\left|
|
||
\begin{pmatrix}
|
||
a_1 & * & * & \dots & *\\
|
||
0 & a_2 & * & \dots & *\\
|
||
0 & 0 & a_3 & \dots & *\\
|
||
\vdots & \vdots & \vdots & \ddots & \vdots\\
|
||
0 & 0 & 0 & \dots & a_n
|
||
\end{pmatrix}
|
||
\right| = a_1a_2\dots a_n.
|
||
$$
|
||
В частности, определитель единичной матрицы $E_n$ равен $1$.
|
||
\end{corollary}
|
||
\begin{proof}
|
||
Это несложно получить из предыдущей теоремы индукцией по размеру
|
||
матрицы. Можно и напрямую заметить, что в сумме из определения
|
||
$\det(A)$ для верхнетреугольной матрицы $A$ лишь одно слагаемое
|
||
отлично от нуля~--- то, которое отвечает тождественной перестановке.
|
||
\end{proof}
|
||
|
||
\begin{proposition}\label{prop_det_zero_row}
|
||
Если в матрице присутствует нулевой столбец или нулевая строка, то ее
|
||
определитель равен нулю.
|
||
\end{proposition}
|
||
\begin{proof}
|
||
Пусть $i$-ая строка матрицы $A$ равна нулю.
|
||
В каждое слагаемое из определения $\det(A)$ входит элемент вида
|
||
$a_{i,\pi(i)}$, равный нулю, поэтому каждое слагаемое равно
|
||
нулю. Доказательство для нулевого столбца получается
|
||
транспонированием.
|
||
\end{proof}
|
||
|
||
\begin{proposition}\label{prop_det_of_elementary}
|
||
Определители матриц элементарных преобразований:
|
||
$|T_{ij}(\lambda)|=1$, $|S_{ij}|=-1$, $|D_i(\eps)|=\eps$.
|
||
Определитель окаймленной единичной матрицы размера $n\times n$:
|
||
$\left|\begin{matrix}E_r & 0 \\ 0 & 0\end{matrix}\right|=\begin{cases}0,
|
||
&\text{если }r<n;\\1, &\text{если }r=n\end{cases}$.
|
||
\end{proposition}
|
||
\begin{proof}
|
||
Матрица элементарных преобразований приводится к единичной одним
|
||
элементарным преобразованием, и мы знаем, как при этом меняется ее
|
||
определитель, поэтому первая часть~--- тривиальное вычисление.
|
||
Окаймленная единичная матрица является верхнетреугольной, поэтому
|
||
вторая часть сразу следует из следствия~\ref{cor_ut_det}.
|
||
\end{proof}
|
||
|
||
\begin{theorem}[Мультипликативность определителя]\label{thm:determinant_product}
|
||
Определитель произведения матриц равен произведению их
|
||
определителей:
|
||
$$\det(AB)=\det(A)\det(B)\quad\text{ для любых }A,B\in M(n,k).$$
|
||
\end{theorem}
|
||
\begin{proof}
|
||
Заметим, что для любой матрицы $C\in M(n,k)$ выполнены равенства
|
||
\begin{align*}
|
||
\det(T_{ij}(\lambda)C) &= \det(T_{ij}(\lambda))\det(C),\\
|
||
\det(S_{ij}C) &= \det(S_{ij})\det(C),\\
|
||
\det(D_i(\eps)C) &= \det(D_i(\eps))\det(C),\\
|
||
\det(\begin{pmatrix}E_r & 0\\0 & 0\end{pmatrix}C) &=
|
||
\det(\begin{pmatrix}E_r & 0\\0 & 0\end{pmatrix})\det(C).
|
||
\end{align*}
|
||
Действительно, первые три равенства следуют из
|
||
теоремы~\ref{thm_det_under_elementary} и
|
||
предложения~\ref{prop_det_of_elementary}. При $r<n$ матрица
|
||
$\begin{pmatrix}E_r & 0\\0 & 0\end{pmatrix}C$ имеет нулевую строку,
|
||
поэтому ее определитель равен нулю
|
||
(предложение~\ref{prop_det_zero_row}), как и произведение
|
||
определителей сомножителей (в силу
|
||
предложения~\ref{prop_det_of_elementary}. При $r=n$ указанная матрица
|
||
является единичной, поэтому результат следует из
|
||
следствия~\ref{cor_ut_det}.
|
||
|
||
По следствию~\ref{cor_pdq} мы можем записать
|
||
$$A=P_t\dots P_1\begin{pmatrix}E_r & 0\\0 & 0\end{pmatrix}Q_1\dots
|
||
Q_s,$$
|
||
где $P_1,\dots,P_t,Q_1,\dots,Q_s$~--- матрицы элементарных
|
||
преобразований. Тогда
|
||
$$\det(AB)=\det(P_t\dots P_1\begin{pmatrix}E_r & 0\\0 &
|
||
0\end{pmatrix}Q_1\dots Q_sB).$$ Применяя замечание из предыдущего
|
||
абзаца несколько раз, получаем, что
|
||
$$\det(AB)=\det(P_t)\dots\det(P_1)\det(\begin{pmatrix}E_r & 0\\0 &
|
||
0\end{pmatrix})\det(Q_1)\dots\det(Q_s)\det(B).$$
|
||
С другой стороны,
|
||
$$\det(A)=\det(P_t\dots P_1\begin{pmatrix}E_r & 0\\0 &
|
||
0\end{pmatrix}Q_1\dots Q_s),$$ и, снова применяя замечание выше,
|
||
получаем
|
||
$$\det(A)=\det(P_t)\dots\det(P_1)\det(\begin{pmatrix}E_r & 0\\0 &
|
||
0\end{pmatrix})\det(Q_1)\dots\det(Q_s).$$ Сопоставляя полученные
|
||
равенства, получаем, что $\det(AB)=\det(A)\det(B)$.
|
||
\end{proof}
|
||
|
||
\subsection{Разложение определителя по строке}
|
||
\literature{[F], гл. IV, \S~2, п. 5; [K1], гл. 3, \S~2.}
|
||
|
||
Посмотрим на матрицу $A\in M(n,k)$. Вычеркнем из нее строку с номером
|
||
$i$ и столбец с номером $j$ для некоторых $1\leq i,j\leq
|
||
n$. Обозначим полученную матрицу через $M_{ij}\in M(n-1,k)$.
|
||
Определитель матрицы $M_{ij}$ (а иногда сама эта матрица) называется
|
||
\dfn{(дополнительным) минором}\index{минор!дополнительный}.
|
||
|
||
Теперь посмотрим на строку с номером $i$ исходной матрицы $A$ и
|
||
воспользуемся линейностью определителя:
|
||
$$
|
||
|A| =
|
||
\left|\begin{matrix}\vdots & \vdots & \ddots & \vdots\\
|
||
a_{i1} & a_{i2} & \dots & a_{in}\\
|
||
\vdots & \vdots & \ddots & \vdots\end{matrix}\right|
|
||
=
|
||
\left|\begin{matrix}\vdots & \vdots & \ddots & \vdots\\
|
||
a_{i1} & 0 & \dots & 0\\
|
||
\vdots & \vdots & \ddots & \vdots\end{matrix}\right| +
|
||
\left|\begin{matrix}\vdots & \vdots & \ddots & \vdots\\
|
||
0 & a_{i2} & \dots & 0\\
|
||
\vdots & \vdots & \ddots & \vdots\end{matrix}\right| + \dots +
|
||
\left|\begin{matrix}\vdots & \vdots & \ddots & \vdots\\
|
||
0 & 0 & \dots & a_{in}\\
|
||
\vdots & \vdots & \ddots & \vdots\end{matrix}\right|.
|
||
$$
|
||
Посчитаем отдельно определитель каждого слагаемого в правой части.
|
||
Слагаемое с номером $j$ имеет вид
|
||
$$
|
||
\left|\begin{matrix}\ddots & \vdots & \vdots & \vdots & \ddots\\
|
||
\dots & 0 & a_{ij} & 0 & \dots\\
|
||
\ddots & \vdots & \vdots & \vdots & \ddots\end{matrix}\right|:
|
||
$$
|
||
все элементы в $i$-ой строчке равны нулю, кроме $a_{ij}$.
|
||
Теперь аккуратно переставим строчки и столбцы так, чтобы элемент
|
||
$a_{ij}$ оказался в левом верхнем углу нашей матрицы; для этого
|
||
нужно сдвинуть по циклу строки с номерами от $1$ до $i$ и столбцы с
|
||
номерами от $1$ до $j$. То есть, сначала поменяем местами строки $i$ и
|
||
$i-1$, затем строки $i-1$ и $i-2$, и так далее, пока не поменяем
|
||
строки $1$ и $2$. Нетрудно видеть, что мы совершили ровно $i-1$
|
||
элементарное преобразоване второго типа. При этом определитель нашей
|
||
матрицы умножился на $(-1)^{i-1}$. После этого сделаем то же самое со
|
||
столбцами, и определитель умножится на $(-1)^{j-1}$. В итоге он
|
||
умножится на $(-1)^{i-1+j-1}=(-1)^{i+j-2}=(-1)^{i+j}$. После таких
|
||
операций наша матрица будет иметь следующий блочный вид:
|
||
$$
|
||
\begin{pmatrix}a_{ij} & 0\\
|
||
* & M_{ij}
|
||
\end{pmatrix}.
|
||
$$
|
||
По теореме~\ref{thm_det_block_ut} (напомним, что определитель не
|
||
меняется при транспонировании) ее определитель равен произведению
|
||
$a_{ij}$ на дополнительный минор $|M_{ij}|$. Значит, $j$-е слагаемое в
|
||
разложении $\det(A)$, с которого мы начали, равно
|
||
$(-1)^{i+j}a_{ij}|M_{ij}|$.
|
||
|
||
Произведение $(-1)^{i+j}|M_{ij}|$ называется
|
||
\dfn{алгебраическим дополнением}\index{алгебраическое дополнение}
|
||
элемента $a_{ij}$ и обозначается
|
||
через $\widetilde{A}_{ij}$.
|
||
Мы получили \dfn{разложение определителя по строке:}\index{разложение
|
||
определителя!по строке}
|
||
$\det(A)=a_{i1}\widetilde{A}_{i1} + a_{i2}\widetilde{A}_{i2} + \dots +
|
||
a_{in}\widetilde{A}_{in}$.
|
||
Транспонируя полученный результат, мы получаем
|
||
\dfn{разложение определителя по столбцу:}\index{разложение
|
||
определителя!по столбцу}
|
||
$\det(A)=a_{1i}\widetilde{A}_{1i} + a_{2i}\widetilde{A}_{2i} + \dots +
|
||
a_{ni}\widetilde{A}_{ni}$.
|
||
|
||
Сформулируем чуть более общий результат.
|
||
|
||
\begin{theorem}[Соотношения ортогональности]\index{соотношения
|
||
ортогональности}
|
||
Пусть $A\in M(n,k)$ и $1\leq i\leq n$. Тогда
|
||
$$
|
||
a_{i1}\widetilde{A}_{j1} + a_{i2}\widetilde{A}_{j2} + \dots +
|
||
a_{in}\widetilde{A}_{jn} =
|
||
\begin{cases}
|
||
\det(A),&\text{если }i=j;\\
|
||
0,&\text{если }i\neq j.
|
||
\end{cases}.
|
||
$$
|
||
\end{theorem}
|
||
\begin{proof}
|
||
При $i=j$ это в точности разложение определителя по строке. Если же
|
||
$i\neq j$, рассмотрим матрицу $A'$, которая совпадает с матрицей $A$
|
||
везде, кроме строчки с номером $j$, а в ее строчке с номером $j$ стоит
|
||
строчка с номером $i$ матрицы $A$. Таким образом, строки матрицы $A'$
|
||
с номерами $i$ и $j$ совпадают, поэтому ее определитель равен нулю. С
|
||
другой стороны, раскладывая этот определитель по строке с номером $j$,
|
||
мы получим в
|
||
точности сумму $a_{i1}\widetilde{A}_{j1} + a_{i2}\widetilde{A}_{j2} + \dots +
|
||
a_{in}\widetilde{A}_{jn}$, поскольку в строке с номером $j$ стоят
|
||
элементы $a_{i1},a_{i2},\dots,a_{in}$, а их дополнения совпадают с
|
||
дополнениями элементов $j$-ой строки матрицы $A$, поскольку
|
||
алгебраические дополнения элементов $j$-ой строки не зависят от того,
|
||
что именно стоит в $j$-ой строке.
|
||
\end{proof}
|
||
Конечно, несложно сформулировать аналогичные соотношения, исходя из
|
||
разложения определителя по столбцу.
|
||
|
||
Эту теорему можно записать в более компактной форме. Для этого
|
||
рассмотрим матрицу
|
||
$\adj(A)$, в которой на позиции $(i,j)$ стоит алгебраическое
|
||
дополнение $\widetilde{A}_{ji}$ (обратите внимание на то, что индексы
|
||
поменялись местами). Она называется
|
||
\dfn{присоединенной}\index{матрица!присоединенная}
|
||
(или \dfn{взаимной}\index{матрица!взаимная}) к матрице
|
||
$A$. Соотношения ортогональности (для
|
||
строк и столбцов) тогда
|
||
переписываются следующим образом.
|
||
\begin{corollary}\label{cor_orthogonality_relations}
|
||
Для матрицы $A\in M(n,k)$ выполнено
|
||
$$
|
||
A\cdot\adj(A)=\det(A)\cdot E = \adj(A)\cdot A
|
||
$$
|
||
\end{corollary}
|
||
Теперь нетрудно доказать критерий обратимости квадратной матрицы.
|
||
\begin{corollary}\label{cor_matrix_invertible_det}
|
||
Матрица $A\in M(n,k)$ обратима тогда и только тогда, когда
|
||
$\det(A)\neq 0$; в этом случае $A^{-1}=(\det(A))^{-1}\adj(A)$.
|
||
\end{corollary}
|
||
\begin{proof}
|
||
Если $A$ обратима, то найдется $A^{-1}$ такая, что $A\cdot A^{-1}=E$;
|
||
тогда $$\det(A)\det(A^{-1})=\det(A\cdot A^{-1})=\det(E)=1$$ в силу
|
||
мультипликативности определителя.
|
||
Обратно, если $\det(A)\neq 0$, то, разделив соотношение
|
||
ортогональности на скаляр $\det(A)$, получаем, что
|
||
$$A\cdot(\det(A))^{-1}\adj(A)=E=(\det(A))^{-1}\adj(A)\cdot A,$$
|
||
что и требовалось.
|
||
\end{proof}
|
||
|
||
% 13.03.2013
|
||
|
||
В частности, для матрицы $2\times 2$ это следствие означает,
|
||
что
|
||
$$
|
||
\begin{pmatrix}a & b\\c & d\end{pmatrix}
|
||
= \frac{1}{ad-bc}\begin{pmatrix}d & -b\\-c & a\end{pmatrix}
|
||
$$
|
||
(если, конечно, $ad-bc\neq 0$).
|
||
|
||
Применим теперь полученные результаты к решению системы линейных
|
||
уравнений с невырожденной матрицей.
|
||
Рассмотрим систему линейных уравнений $AX=B$ с квадратной матрицей
|
||
$A=(a_{ij})\in M(n,k)$, где
|
||
$X=\begin{pmatrix}x_1\\x_2\\\vdots\\x_n\end{pmatrix}$~--- столбец
|
||
неизвестных,
|
||
$B=\begin{pmatrix}b_1\\b_2\\\vdots\\b_n\end{pmatrix}\in M(n,1,k)$~---
|
||
столбец правой части. Напомним, что {\it решить систему}~--- значит,
|
||
найти все столбцы $X\in M(n,1,k)$, для которых выполнено $AX=B$.
|
||
Если матрица $A$ невырождена, то есть, существует обратная матрица
|
||
$A^{-1}$, после домножения обеих частей уравнения на $A^{-1}$ получаем
|
||
$A^{-1}AX=A^{-1}B$, что равносильно равенству $X=A^{-1}B$. Таким
|
||
образом, система уравнений с невырожденной квадратной матрицей всегда
|
||
имеет единственное решение.
|
||
|
||
Более того, для нахождения этого решения нетрудно написать чуть более
|
||
явные формулы, называемые \dfn{формулами Крамера}\index{формулы
|
||
Крамера}.
|
||
Действительно,
|
||
\begin{align*}
|
||
X = A^{-1}B = \frac{1}{\det(A)}\adj(A)B &=
|
||
\frac{1}{\det(A)}
|
||
\begin{pmatrix}
|
||
\widetilde{A}_{11} & \widetilde{A}_{21} & \dots & \widetilde{A}_{n1}\\
|
||
\widetilde{A}_{12} & \widetilde{A}_{22} & \dots & \widetilde{A}_{n2}\\
|
||
\vdots & \vdots & \ddots & \vdots\\
|
||
\widetilde{A}_{1n} & \widetilde{A}_{2n} & \dots & \widetilde{A}_{nn}
|
||
\end{pmatrix}\cdot
|
||
\begin{pmatrix}
|
||
b_1 \\ b_2 \\ \vdots \\ b_n
|
||
\end{pmatrix}\\
|
||
&=
|
||
\frac{1}{\det(A)}
|
||
\begin{pmatrix}
|
||
b_1\widetilde{A}_{11} + b_2\widetilde{A}_{21} + \dots +
|
||
b_n\widetilde{A}_{n1}\\
|
||
b_1\widetilde{A}_{12} + b_2\widetilde{A}_{22} + \dots +
|
||
b_n\widetilde{A}_{n2}\\
|
||
\vdots\\
|
||
b_1\widetilde{A}_{1n} + b_2\widetilde{A}_{2n} + \dots +
|
||
b_n\widetilde{A}_{nn}
|
||
\end{pmatrix}.
|
||
\end{align*}
|
||
Итоговые выражения очень похожи на разложения определителя по строке.
|
||
И действительно, заменим в матрице $A$ столбец под номером $i$ на
|
||
столбец $B$. Обозначим полученную матрицу через~$A'_i$.
|
||
Посчитаем определитель этой матрицы, разложив его по $i$-ому столбцу:
|
||
для этого нужно перемножать элементы ее $i$-го столбца (то есть,
|
||
элементы столбца $B$) на их алгебраические дополнения, которые
|
||
совпадают с соответствующими алгебраическими дополнениями элементов
|
||
матрицы $A$. Мы получим в точности $b_1\widetilde{A}_{1i} +
|
||
b_2\widetilde{A}_{2i} + \dots + b_n\widetilde{A}_{ni}$~--- то, что
|
||
стоит в столбце $X$ на позиции $i$ (с точностью до множителя
|
||
$1/\det(A)$. Сформулируем полученный результат в виде теоремы.
|
||
|
||
\begin{theorem}[Формулы Крамера]
|
||
Пусть $A\in M(n,k)$~--- невырожденная матрица, $B\in M(n,1,k)$~---
|
||
некоторый столбец. Обозначим через $A'_i$ матрицу, полученную
|
||
подстановкой столбца $B$ вместо $i$-го столбца матрицы $A$.
|
||
Тогда решение $X=\begin{pmatrix}x_1\\x_2\\\vdots\\x_n\end{pmatrix}$
|
||
системы линейных уравнений $AX=B$ единственно и задается формулами
|
||
$$
|
||
x_i=\frac{\det(A'_i)}{\det(A)}.
|
||
$$
|
||
\end{theorem}
|
||
|
||
Посмотрим теперь на множество решений произвольной однородной системы
|
||
линейных уравнений $AX=0$ с матрицей $A\in M(m,n,k)$; здесь
|
||
$X=\begin{pmatrix}x_1\\x_2\\\vdots\\x_n\end{pmatrix}$~--- столбец
|
||
неизвестных, а в правой части стоит нулевая матрица $0\in M(m,1,k)$.
|
||
|
||
\begin{proposition}[Свойства решений однородной системы линейных
|
||
уравнений]
|
||
Если $X, X'\in M(n,1,k)$~--- решения системы $AX=0$, то сумма
|
||
$X+X'$ также является решением этой системы.
|
||
Если $X\in M(n,1,k)$~--- решение системы $AX=0$, $\lambda\in k$,
|
||
то $\lambda X\in M(n,1,k)$ также является решением этой системы.
|
||
\end{proposition}
|
||
\begin{proof}
|
||
Если $AX=0$ и $AX'=0$, то $A(X+X')=AX+AX'=0+0=0$ и
|
||
$A(\lambda X)=\lambda(AX)=\lambda\cdot 0=0$.
|
||
\end{proof}
|
||
|
||
Теперь посмотрим на произвольную систему линейных уравнений $AX=B$
|
||
(мы сохраняем предыдущие обозначения; кроме того, $B\in M(m,1,k)$~---
|
||
некоторый столбец правой части).
|
||
\begin{proposition}[Свойства решений неоднородной системы линейных
|
||
уравнений]\label{prop_structure_of_solutions_linear_system}
|
||
Пусть $X_0$~--- некоторое фиксированное решение системы $AX=B$
|
||
Тогда любое решение этой системы
|
||
имеет вид $X = X_0 + Y$, где $Y$~--- некоторое решение соответствующей
|
||
однородной системы $AX=0$. Обратно, для любого решения $Y$ однородной
|
||
системы $AX=0$ сумма $X = X_0+Y$ является решением системы $AX=B$.
|
||
\end{proposition}
|
||
\begin{proof}
|
||
Если $AX_0=B$ и $AY=0$, то $A(X_0+Y)=AX_0+AY=B+0=B$. Обратно, если
|
||
$AX_0=B$ и, кроме того, $AX=B$, то $A(X-X_0)=AX-AX_0=B-B=0$, поэтому
|
||
$X-X_0$ является решением соответствующей однородной системы.
|
||
\end{proof}
|
||
|
||
Поэтому поиск решений произвольной системы линейных уравнений $AX=B$
|
||
сводится к нахождению {\em частного решения} $X_0$ этой системы (если
|
||
оно вообще существует), и к
|
||
нахождению всех решений соответствующей однородной системы $AX=0$.
|
||
В главе~\ref{section_vector_spaces} мы построим общую теорию для
|
||
изучения свойств решений однородных систем, а в главе 7 сформулируем
|
||
в рамках этой теории и вопрос о существовании частного решения
|
||
неоднородной
|
||
системы.
|