\newpage

\mysection{Лекция 1 (17.02.05)}

% ***********************************************************************
\subsection{Предварительные сведения}
% ***********************************************************************

Пусть $A = \{ a_1,a_2, \ldots a_n \}$ --- числовое n-элементное множество.

\tdef \ti{Перестановкой} ($\Pi$) назовем упорядоченный набор элементов множества~ $A$.

\txmp
$$
\begin{array}{lcl}
	A	& = & \left(1, 3, 5, 7\right)		\\
	\Pi_1	& = & \left(3, 1, 7, 5\right)		\\
	\Pi_2	& = & \left(5, 7, 1, 3\right) 
\end{array}
$$

\begin{trm}[о числе перестановок]
Число перестановок~ $P_n$ n-эле\-мент\-но\-го множества~ $A$ вычисляется по формуле~ ${P_n=n!}$.
\end{trm}
\tprf Воспользуемся методом математической индукции:

\begin{enumerate}
\item  При $n=1$ утверждение очевидно.
\item  Положим теперь, что при $n=k$ $P_k=k!$. 
\item  Покажем, что для ${n=k+1}$ выполняется тождество $P_{k+1} = (k+1)!$. Действительно,
$$
	P_{k+1} = \underbrace{k! + k! + \dots k!}_{\mbox{$k+1$ раз}} = (k+1)!
$$
\end{enumerate}

\tdef Если в перестановке $\Pi$ $a_i > a_j$ для некоторых $i < j$, то $(a_i,a_j)$ образует \ti{инверсию}.

\txmp В перестановке $\Pi = (3, 2, 1, 5, 4)$ есть следующие инверсии: 
$$
(3, 2); \quad (3, 1); \quad (2, 1); \quad (5, 4)
$$
Следовательно, число инверсий $I(\Pi) = 4$.

\txmp $I(5, 3, 4, 1, 2) = 4 + 2 + 2 = 8$.

\tdef Если число инверсий в перестановке~ $I(\Pi)$ -- четно (нечетно), то перестановка~ $\Pi$ называется четной (нечетной).

\tdef \ti{Транспозицией} назовем перемену местами двух чисел в перестановке.

\begin{trm}[о транспозиции]
\label{trm_transp}
Каждая транспозиция меняет четность пе\-ре\-ста\-новки.
\end{trm}
\tprf Рассмотрим вначале случай \glqq{}соседней\grqq{} транспозиции:
$$
\begin{array}{rclc}
\Pi_1 & = & a_1,\dots,a_i,a_{i+1},\dots,a_n & \\
\Pi_2 & = & a_1,\dots,a_{i+1},a_i,\dots,a_n & .
\end{array}
$$
Очевидно, что если $a_i < a_{i+1}$, то $I(\Pi_2) = I(\Pi_1) + 1$, а в случае, если $a_i > a_{i+1}$ --- $I(\Pi_2) = I(\Pi_1) - 1$.

Теперь рассмотрим случай произвольной транспозиции:
$$
\begin{array}{rclc}
\Pi_1 & = & a_1,\dots,a_i,a_{i+1},\dots,a_{i+m},\dots,a_n & \\
\Pi_2 & = & a_1,\dots,a_{i+m},a_i,\dots,a_{i},\dots,a_n   & .
\end{array}
$$
Нетрудно заметить, что перестановка~ $\Pi_2$ получается из~ $\Pi_1$ с помощью ${2m-1}$ (нечетного числа!) соседних транспозиций, каждая из которых меняет четность исходной перестановки $\Pi_1$. Теорема доказана.

\tdef \ti{Подстановкой}~ ($\Pi_0$) назовем взаимооднозначное отображение числового множества $A$ на себя.
$$
\Pi_0: \quad \varphi = 
\left\lbrace
\begin{array}{cccc}
	a_1,		& a_2, 		& \dots & a_n \\
	\varphi(a_1), 	& \varphi(a_2), & \dots & \varphi(a_n)
\end{array}
\right\rbrace
$$
Отметим, что число различных подстановок для можества ${A=( a_1, a_2, \dots, a_n)}$ будет~ $n!$.

\txmp Пусть дано множество $A = (1, 2, 3, 4, 5)$. Тогда одной из его подстановок, будет, например, следующая:
$$
\varphi_1 = 
\left\lbrace
\begin{array}{ccccc}
	1, & 2, & 3, & 4, & 5 \\
	5, & 2, & 4, & 3, & 1 
\end{array}
\right\rbrace
$$
%
% !!!! ZYV: каким же образом тут по-нормальному поставить точку??? (точка)
%
\tdef Подстановка~ $\Pi_0$ называется \ti{четной (нечетной)}, если число инверсий во 2-ой строке четно (нечетно).

\begin{trm}
Для некоторого множества $A=( a_1, a_2, \dots, a_n)$ число четных подстановок равно числу нечетных подстановок и, в свою очередь, равно $\frac{n!}{2}$.
\end{trm}

\tprf Справедливость теоремы полностью следует из теоремы~ \ref{trm_transp}.

% ***********************************************************************
\subsection{Матрицы}
% ***********************************************************************

\subsubsection{Общие сведения о матрицах (?)}

\tdef \ti{Матрицей} назовем множество ${m \times n}$ элементов, расположенных в виде таблицы.

\txmp
$$
A = \left( 
\begin{array}{cccc}
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{array}
\right)
$$

\tdef Обозначим за ${{\cal P}_{m \times n}}$ множество матриц размера ${m \times n}$.

\tdef Матрица~ ${m \times n}$ называется \ti{квадратной}, если~ ${m =n}$.

\tdef Для заданной матрицы~ ${A \in {\cal P}_{m \times n}}$, матрица~ ${A^T}$ называется \ti{транспонированной}, если она построена следующим образом:
$$
A^{T} = \left( 
\begin{array}{cccc}
a_{11} 	& a_{21}	& \dots & a_{m1}	\\
a_{12} 	& a_{22}	& \dots & a_{m2}	\\
\vdots	& \vdots	& \ddots& \vdots	\\
a_{1n} 	& a_{2n}	& \dots & a_{mn}	\\
\end{array}
\right)
$$
% ZYV: точка ?

\tdef Квадратная матрица называется \ti{диагональной}, если она имеет вид:
$$
A = \left( 
\begin{array}{cccc}
a_{11} 	& 0		& \dots & 0	\\
0	& a_{22}	& \dots & 0	\\
\vdots	& \vdots	& \ddots& \vdots	\\
0 	& 0		& \dots & a_{nn}	\\
\end{array}
\right)
$$
% ZYV: точка ?

\tdef \ti{Единичную} матрицу~$E$ определим следующим образом:
$$
E = \left( 
\begin{array}{cccc}
1 	& 0		& \dots & 0	\\
0	& 1		& \dots & 0	\\
\vdots	& \vdots	& \ddots& \vdots	\\
0 	& 0		& \dots & 1	\\
\end{array}
\right)
$$
% ZYV: точка ?

\tdef Пусть дана квадратная матрица  ${A \in {\cal P}_{n \times n}}$. \ti{Определителем} такой матрицы назовем число
$$
\det A = \vert A \vert = \sum { \underbrace{ (-1)^{s} a_{1 i_1} a_{2 i_2} \dots a_{n i_n}}_{\mbox{\scriptsize{общий член определителя $A$}}} } = \sum { (-1)^{r} a_{j_1 1} a_{j_2 2} \dots a_{j_n n} } ,
$$
где
$$
\begin{array}{l}
	s = I(i_1, i_2, \dots, i_n)   \\
	r = I(j_1, j_2, \dots, j_n) , \\
\end{array}
$$
при этом, суммирование ведется либо по всем возможным перестановкам~ ${(i_1, i_2, \dots, i_n)}$, либо~ ${(j_1, j_2, \dots, j_n)}$.

\txmp Рассмотрим случай $n=2$. Пусть
$$
A = \left( 
	\begin{array}{cc}
		a_{11} 	& a_{12} \\
		a_{21} 	& a_{22} \\
	\end{array}
\right) ,
$$
% ZYV: точка - запятая?
тогда $\det A = a_{11} a_{22} - a_{12} a_{21} $. Для $n=3$, 
$$
A = \left( 
	\begin{array}{ccc}
		a_{11} 	& a_{12} & a_{13} \\
		a_{21} 	& a_{22} & a_{23} \\
		a_{31} 	& a_{32} & a_{33} \\
	\end{array}
\right)
, \quad \mbox{и, соответственно, }
$$
$$
\det A = a_{11} a_{22} a_{33}  +  a_{12} a_{23} a_{31}  +  a_{13} a_{21} a_{32}  -  a_{11} a_{23} a_{32}  -  a_{12} a_{21} a_{33}  -  a_{13} a_{22} a_{31} 
.
$$

\subsubsection{Свойства определителей матриц}

\begin{enumerate}

\item \label{matr_trsp} ${\det A = \det A^{T}}$, т.е. свойства матриц, справедливые для строк $A$ остаются верными и для столбцов.

\item \label{matr_nul} Если матрица~ $A$ содержит строку, состоящую из нулей, то~ ${\det A = 0}$.

\item \label{matr_swap} Если матрица~ $B$ получена из~ $A$ перестановкой двух строк, то~ ${\det B = - \det A}$.

\item Если в матрице~ $A$ есть две одинаковых строки, то~ ${\det A = 0}$.

\item \label{matr_lin} Определитель обладает свойством линейности, т.е.
$$
\begin{array}{l}
\left \vert 
	\begin{array}{ccc}
	a_{11} & \dots & a_{1n}  \\
	\vdots & \cdots & \vdots  \\
	\alpha b_{k1} + \beta c_{k1} & \dots & \alpha b_{kn} + \beta c_{kn} \\
	\vdots & \cdots & \vdots \\
	a_{n1} & \dots  & a_{nn} \\
	\end{array}
\right \vert 
= \\
\smallskip \\
\qquad {} = 
\alpha 
\left \vert 
	\begin{array}{ccc}
	a_{11} & \dots & a_{1n}  \\
	\vdots & \cdots & \vdots  \\
	b_{k1} & \dots &  b_{kn} \\
	\vdots & \cdots & \vdots \\
	a_{n1} & \dots  & a_{nn} \\
	\end{array}
\right \vert 
+
\beta
\left \vert 
	\begin{array}{ccc}
	a_{11} & \dots & a_{1n}  \\
	\vdots & \cdots & \vdots  \\
	c_{k1} & \dots &  c_{kn} \\
	\vdots & \cdots & \vdots \\
	a_{n1} & \dots  & a_{nn} \\
	\end{array}
\right \vert 
\\
\end{array}
$$

\item \label{matr_lin_comb} Если в матрице~ $A$ какая-либо строка является линейной комбинацией других строк, то~ $\det A = 0$.

\item $\det A$ не изменится, если в матрице~ $A$ к какой-либо строке прибавить линейную комбинацию других строк.

\end{enumerate}

\tprf Свойства~\ref{matr_trsp} и~\ref{matr_nul} с очевидностью следуют из данных  определений.
\begin{enumerate}
\addtocounter{enumi}{2} % начинаем с 3-го пункта доказывать

\item Пусть определены матрицы $A$ и $B$:
$$
A = \left (
	\begin{array}{cccc}
	a_{11} & a_{12} & \dots & a_{1n} \\
	\vdots & \cdots & \cdots & \vdots \\
	a_{k1} & a_{k2} & \dots & a_{kn} \\
	\vdots & \cdots & \cdots & \vdots \\
	a_{l1} & a_{l2} & \dots & a_{ln} \\
	\vdots & \cdots & \ddots & \vdots \\
	a_{n1} & a_{n2} & \dots & a_{nn} \\
	\end{array}
\right )
, \qquad
B = \left (
	\begin{array}{cccc}
	a_{11} & a_{12} & \dots & a_{1n} \\
	\vdots & \cdots & \cdots & \vdots \\
	a_{l1} & a_{l2} & \dots & a_{ln} \\
	\vdots & \cdots & \cdots & \vdots \\
	a_{k1} & a_{k2} & \dots & a_{kn} \\
	\vdots & \cdots & \ddots & \vdots \\
	a_{n1} & a_{n2} & \dots & a_{nn} \\
	\end{array}
\right )
.
$$
% ZYV: точка?
Тогда
$$
\begin{array}{l}
\det A = \sum{\mathstrut (-1)^s a_{1 {i_{1}}} \dots a_{k {i_{k}}} \dots a_{l {i_{l}}} \dots a_{n {i_{n}}}} = \\
\phantom{\det A} =  \sum{\mathstrut -(-1)^s a_{1 {i_{1}}} \dots a_{l {i_{l}}} \dots a_{k {i_{k}}} \dots a_{n {i_{n}}}} = - \det B ,\\
\end{array}
$$
и т. к., по доказанной теореме, 
${I(i_{1},\dots,i_{k},\dots,i_{l},\dots,i_{n})}$ 
четно, если
${I(i_{1},\dots,i_{l},\dots,i_{k},\dots,i_{n})}$
нечетно и, соответственно, наоборот.

\item Непосредственно воспользуемся свойством \ref{matr_swap}, т.е. поменяем местами те самые две одинаковых строки. Но тогда, т.к. получившаяся в результате перестановки строк матрица $B = A$,
$$
	\det B = - \det A = \det A \Rightarrow  
	2 \det A = 0 \Rightarrow \det A = 0 
.
$$

\item Воспользуемся определением определителя матрицы:
$$
\begin{array}{l}
	\sum { \mathstrut (-1)^{s} a_{1 i_{1}} \dots (\alpha b_{k i_{k}} + \beta c_{k i_{k}}) \dots a_{n i_{n}} } =\\
	\qquad = \alpha \sum { \mathstrut (-1)^{s} a_{1 i_{1}} \dots b_{k i_{k}} \dots a_{n i_{n}} } + \beta \sum { \mathstrut (-1)^{s} a_{1 i_{1}} \dots c_{k i_{k}} \dots a_{n i_{n}} } . \\
\end{array}
$$

\item Следует из свойства ~ \ref{matr_lin}.
\item Следует из свойства ~ \ref{matr_lin_comb}.
\end{enumerate}

\tdef Пусть ${A \in {\cal P}_{n \times n}}$. \ti{Минором} элемента $a_{ij}$ -- $M_{ij}$ назовем определитель матрицы, полученной из $A$ вычеркиванием {$i$-ой строки} и {$j$-го столбца}.

\tdef \ti{Алгебраическим дополнением} к элементу $a_{ij}$ назовем ${A_{ij} = (-1)^{i+j} M_{ij}}$.

\txmp Найдем минор и алгебраическое дополнение для элемента $a_{12}$ для заданной матрицы $A$.
% ***********************************************
% ZYV: это перечеркивание строк/столбцов матрицы
\begin{picture}(0,0)
	\put(16.5,-6.7){\line(1,0){24}}
	\put(27.8,-17){\line(0,1){12}}
\end{picture}
% ***********************************************
$$
A = \left( 
	\begin{array}{ccc}
		a_{11} 	& a_{12} & a_{13} \\
		a_{21} 	& a_{22} & a_{23} \\
		a_{31} 	& a_{32} & a_{33} \\
	\end{array}
\right)
$$
$$
M_{12} = \left \vert
	\begin{array}{cc}
		a_{21}	& a_{23}  \\
		a_{31}	& a_{33}  \\
	\end{array}
\right \vert
; \quad A_{12} = (-1)^{(1+2)} M_{12} = - M_{12} .
$$