\input{ca_preamble.tex}

\begin{document}

\lectitle{1}{������� �������� �������������� ���������}
\lecauthor{�.\,��������}
\date{?? �������� 2008}
\maketitle

\tableofcontents

% ���������� ������ %
\section{���������� ������}
���� ������� ���������:
\begin{equation}\label{eq:Ax=b}
		Ax=b
\end{equation}
��� $A \in \ZZ^{n \times n}$, $b \in \ZZ^n$, $\det{A} \neq 0$.
���������� ����� ������� ������ �������. 

\begin{note} 
������� $A \in \ZZ^{n \times n}$ � $\det{A} \neq 0$ 
������� ��� �������� ���������. ��������������� ����� ��� �����
���������������� �� ������ ������������� ������� � �������������� �� ������������ ������� �����������.
\end{note} 

��������, ��� ���� $x$ �������� ��������
������� \Ref{eq:Ax=b}, �� $x \in Q^n$. �������, ����� ������� ������ ������ ������� 
\Ref{eq:Ax=b} --- ��� ����� ������. 

\section{����� ������}

������� ����� ������ ������� �� ���� ������:
\begin{enumerate}
		\item �������������� ����������� �������;
		\item �������� ���.
\end{enumerate}
�� ������ ����� ������������ ���������� �������������� ��� �������� 
����������� ��������:
$$
		A^{(0)}=[a^{(0)}_{ij}]=[A|b],1 \leq i \leq n,1 \leq j \leq n+1,
$$
��� $a^0_{i,n+1}=b_i$. � ���������� ������������������ �������������� 
$$
		A^{(0)} \rightarrow A^{(1)} \rightarrow \dots \rightarrow A^{(n-1)}
$$
���������� ������� $A^{(n-1)}$, ������ $n$ �������� ������� �������� 
����������������� �������. �� ������ ����� �� ������� $A^{(n-1)}$ �������� 
����� ��������� ������� �������� ������� \Ref{eq:Ax=b}. � ������� ������ 
������ �������� ������� $A^{(k)}$ ��������������� ����������� �� ��������:
\begin{equation}\label{eq:ordinary_gauss}
		a^{(k)}_{ij} = a^{(k-1)}_{ij} - \frac{a^{(k-1)}_{ik}}{a^{(k-1)}_{kk}}a^{(k-1)}_{kj},
		k+1 \leq i \leq n, k+1 \leq j \leq n+1
\end{equation}

��������� ������ ������������� ���������� ������� ����� ������ ������
\cite{algorithforcomputeralgebra}.

\begin{example}
\begin{equation}\label{eq:example1}
		\left\{
				\begin{array}{ccc}
							3x_1 + 4x_2 - 2x_3 + x_4 &=& -2 \\
							x_1 - x_2 + 2x_3 + 2x_4 &=& 7 \\
							4x_1 - 3x_2 + 4x_3 - 3x_4 &=& 2 \\
							-x_1 + x_2 + 6x_3 - x_4 &=& 1 
				\end{array}
		\right.
\end{equation}

������������������ �������������� ����������� ������� ��� ������ ������� 
�������� ��������� �������:
$$
		A^{(0)}=
		\left[
				\begin{array}{ccccc}
						3 & 4 & -2 & 1 & -2\\
						1 & -1 & 2 & 2 & 7\\
						4 & -3 & 4 & -3 & 2\\
						-1 & 1 & 6 & -1 & 1
				\end{array}
		\right];
\qquad
		A^{(1)}=
		\left[
				\begin{array}{ccccc}
						3 & 4 						& -2 						& 1 						& -2 \vspace{5pt} \\
						0 & -\frac{7}{3} 	& \frac{8}{3} 	& \frac{5}{3} 	& \frac{23}{3} \vspace{5pt} \\
						0 & -\frac{25}{3} & \frac{20}{3} 	& -\frac{13}{3} & \frac{14}{3} \vspace{5pt} \\
						0 & \frac{7}{3} 	& \frac{16}{3} 	& -\frac{2}{3} 	& \frac{1}{3}
				\end{array}
		\right];
$$ 
$$
		A^{(2)}=
		\left[
				\begin{array}{ccccc}
						3 & 4 						& -2 						& 1 						& -2 \vspace{5pt} \\
						0 & -\frac{7}{3} 	& \frac{8}{3} 	& \frac{5}{3} 	& \frac{23}{3} \vspace{5pt} \\
						0 & 0							& -\frac{20}{7} & -\frac{72}{7} & -\frac{159}{7} \vspace{5pt} \\
						0 & 0						 	& 8						 	& 1						 	& 8
				\end{array}
		\right];
\qquad
		A^{(3)}=
		\left[
				\begin{array}{ccccc}
						3 & 4 						& -2 						& 1 						& -2 \vspace{5pt} \\
						0 & -\frac{7}{3} 	& \frac{8}{3} 	& \frac{5}{3} 	& \frac{23}{3} \vspace{5pt} \\
						0 & 0							& -\frac{20}{7} & -\frac{72}{7} & -\frac{159}{7} \vspace{5pt} \\
						0 & 0						 	& 0						 	& -\frac{139}{5}& -\frac{278}{5}
				\end{array}
		\right].
$$
\end{example}

��� ����� �� �������, �� ������������� ����� ������� ����� ������ ������ ����� 
��������� ������� � �������� ����������. ��� ����, ����� ������ ��� ���������� 
��������� (� ����� �������� ������), ��� �������� � �������������� ��������� 
�������� ��� ���������� ����. ����, ��� ��� ���������� ������� ������� 
\Ref{eq:Ax=b} ����� �������� ������ � �������, ��������, ��������� ������� 
�������. ������, ��-�� ������� ������� �������������� ��������� ($O(n!)$) 
������ ����� ���������� ��� ������� ���� �� ����������. 

�� ����� ���� ����� �������� ����� ������ ����� �������, ����� �� ������������� 
����� �� ��������� ������� �����.

\section{������������� ����������� ������ ������}

��� ��������� ������������� ������� � ������ ������, ����� ��� ���� 
��������������? ���� ��� ��� ���������� �� ������� \Ref{eq:ordinary_gauss}, 
�� �������� ������, ��� �������� �� ���� ������. �������������, ���� ����� 
���, ��� ���������� $k$-� ������� � $i$-��, ��������� $i$-� ������� �� ������� 
$a_{kk}$, �� ������ ������ \Ref{eq:ordinary_gauss} ������� �������:
\begin{equation}\label{eq:fraction_free_gauss}
		a^{(k)}_{ij} = a^{(k-1)}_{kk}a^{(k-1)}_{ij} - a^{(k-1)}_{ik}a^{(k-1)}_{kj},\\
		k+1 \leq i \leq n, k+1 \leq j \leq n+1
\end{equation}
� ������ �������� ��� ��� �������� �������!

%\textbf{������ 2:} 
\begin{example}
���������� ������� \Ref{eq:example1}. �������� ������ ����
������ ������ ��� ������ �������, ��������� ������� 
\Ref{eq:fraction_free_gauss}. ������������������ �������������� 
����� ���������:
$$
		A^{(0)}=
		\left[
				\begin{array}{ccccc}
						3 & 4 & -2 & 1 & -2\\
						1 & -1 & 2 & 2 & 7\\
						4 & -3 & 4 & -3 & 2\\
						-1 & 1 & 6 & -1 & 1
				\end{array}
		\right];
\qquad
		A^{(1)}=
		\left[
				\begin{array}{ccccc}
						3 & 4 	& -2  & 1 	& -2 \\
						0 & -7 	& 8 	& 5 	& 23 \\
						0 & -25 & 20 	& -13 & 14 \\
						0 & 7 	& 16 	& -2 	& 1
				\end{array}
		\right];
$$ 
$$
		A^{(2)}=
		\left[
				\begin{array}{ccccc}
						3 & 4 	& -2   & 1 	 & -2 \\
						0 & -7 	& 8 	 & 5 	 & 23 \\
						0 & 0   & 60 	 & 216 & 477 \\
						0 & 0 	& -168 & -21 & -168
				\end{array}
		\right];
\qquad
		A^{(3)}=
		\left[
				\begin{array}{ccccc}
						3 & 4 	& -2   & 1 	   & -2 \\
						0 & -7 	& 8 	 & 5 	   & 23 \\
						0 & 0   & 60 	 & 216   & 477 \\
						0 & 0 	& 0    & 35028 & 70056
				\end{array}
		\right].
$$
�������� �� ���� ������������� �������� ������ �������������, ���a��, � ������ 
������� ������ ����� ������. �� ����� ����, ���� �������� $a^{(0)}_{ij}$ 
$\delta$-��������� �����, �� �������� $a^{(k)}_{ij}$ ����� ���� 
$2^k\delta$-��������� �������.
\end{example}

����� �������, �� ���������� �� ����� �������� (������ � �������� �������) � 
�������� ������ �������� (���������������� ���� ������, ����������� ��� 
�������� ������������� ������).

\section{����� �������}

������ ��������� ����� (1968 �.), ������� ��������� ������ � �������� ������� �
��������� � ���, ����� �������� ������������� ������ �� ����� ������� ������. 
� ������ ������� ������ ������ \Ref{eq:fraction_free_gauss} ������������ 
��������� ������� (�������, �������� �������, ���� �������� ��� ������� 
\cite{algorithforcomputeralgebra}):
\begin{equation} \label{eq:fraction_free_bareiss}
		\begin{split}
				& a^{(-1)}_{00} = 1 \\
				& a^{(k)}_{ij} = (a^{(k-1)}_{kk}a^{(k-1)}_{ij} - a^{(k-1)}_{ik}a^{(k-1)}_{kj})/a^{(k-2)}_{k-1,k-1},\\
				& k+1 \leq i \leq n, k+1 \leq j \leq n+1
		\end{split}
\end{equation}

%\textbf{������ 3:} 
\begin{example}
������������� ��������� \Ref{eq:fraction_free_bareiss} ���
���������� �������� ����� ������ ������ ��� ������� \Ref{eq:example1}. 
������������������ �������������� ����� ���������:
$$
		A^{(0)}=
		\left[
				\begin{array}{ccccc}
						3 & 4 & -2 & 1 & -2\\
						1 & -1 & 2 & 2 & 7\\
						4 & -3 & 4 & -3 & 2\\
						-1 & 1 & 6 & -1 & 1
				\end{array}
		\right];
\qquad
		A^{(1)}=
		\left[
				\begin{array}{ccccc}
						3 & 4 	& -2 	& 1 	& -2 \\
						0 & -7 	& 8 	& 5 	& 23 \\
						0 & -25 & 20 	& -13 & 14 \\
						0 & 7 	& 16 	& -2 	& 1
				\end{array}
		\right];
$$ 
$$
		A^{(2)}=
		\left[
				\begin{array}{ccccc}
						3 & 4   & -2 	& 1 	& -2 \\
						0 & -7 	& 8 	& 5  	& 23 \\
						0 & 0		& 20  & 72 	& 159 \\
						0 & 0		& -56	& -7	& -56
				\end{array}
		\right];
\qquad
		A^{(3)}=
		\left[
				\begin{array}{ccccc}
						3 & 4   & -2 	& 1 	& -2 \\
						0 & -7 	& 8 	& 5  	& 23 \\
						0 & 0		& 20  & 72 	& 159 \\
						0 & 0		& 0  	& -556& -1112
				\end{array}
		\right].
$$
\end{example}

��� ������������� ������� ������������� (���� � �������� 
\Ref{eq:fraction_free_bareiss} ���� �������� �������), � �������� 
������������� ������ ������ ���������, ��� � ���������� �������. 
�������� �� ���? �����������, ���. ��� ����, ����� ��� ��������, ���������� 
�����. ������, ����� ���� ������ ��������� �����������.

����� 
$
	A
	\left(
			\begin{array}{cccc}
					a_1 & a_2 & \dots & a_p \\
					b_1 & b_2 & \dots & b_p \\
			\end{array}
	\right)
$ ��������� ����� $p$-�� ������� ������� $A$, ��������� �� ��������� ������� 
$A$, ������� �� ����������� ������� � �������� $a_1, a_2, \dots, a_p$ � 
�������� � �������� $b_1, b_2, \dots, b_p$. ����� ������ � ������������ 
����������� ����� 
$
		A
		\left(
				\begin{array}{cccc}
						1 & 2 & \dots & p \\	
						1 & 2 & \dots & p \\
				\end{array}
		\right)
$ 
������������.
\begin{equation}\label{eq:b}
		b_{ik}^{(p)} = 
				A
				\left(
						\begin{array}{ccccc} 
								1 & 2 & \dots & p & i \\	
								1 & 2 & \dots & p & k \\
						\end{array}
				\right)
		\ \ \ (i,k = p+1, \dots, n).
\end{equation}
�������, ������������ �� ���� �������������, ��������� �����
$$
		B^{(p)}=\left\|b_{ik}^{(p)}\right\|_{p+1}^{n}.
$$
��� ������ ������������ ��� �������� ������� $A$ ����������� ��������� ����� 
\cite{gantmahermatrixtheory}

\begin{lemma}[�������������� ��������� ���������� \cite{gantmahermatrixtheory}] 

		$$
				\left|B^{(p)}\right|=
						\left[
								A\left(
										\begin{array}{cccc}
												1 & 2 & \dots & p \\
												1 & 2 & \dots & p \\
										\end{array}
								\right)
						\right]^{n-p-1}
				\left|A\right|
		$$
		��� $1 \leq p \leq n-1$
\end{lemma}

\begin{proof}
		���������� ������� ����� ������ (�.�. ���, � ������� �������� ������������� 
		������ ����������� �� �������� \Ref{eq:ordinary_gauss}). �� $p$-�� ���� 
		�������� ������� $A^{(0)}$ ����� ������������� � �������
		\begin{equation} \label{_matA_k}
				A^{(p)} = 
				\left(
						\begin{array}{ccccccc}
								a_{11} & a_{12} 			& \dots & a_{1p} 					& a_{1,p+1} 				& \dots & a_{1n} \vspace{5pt} \\
								0			 & a_{22}^{(1)} & \dots & a_{2p}^{(1)} 		& a_{2,p+1}^{(1)} 	& \dots & a_{2n}^{(1)} \\
								\hdotsfor{7} \\
								0 		 &  0						& \dots & a_{pp}^{(p-1)} 	& a_{p,p+1}^{(p-1)} & \dots & a_{pn}^{(p-1)} \vspace{5pt} \\
								0 		 &  0						& \dots & 0							 	& a_{p+1,p+1}^{(p)} & \dots & a_{p+1,n}^{(p)} \\
								\hdotsfor{7} \\
								0 		 &  0						& \dots & 0							 	& a_{n,p+1}^{(p)} 	& \dots & a_{n,n}^{(p)} \\
						\end{array}
				\right)
		\end{equation}
		��� �������� �� ������� $A^{(0)}$ � ������� $A^{(p)}$ � ������ ������ ������� 
		$A^{(0)}$, ������� �� $2$-� � ������ $n$-�, ��������������� ������������ 
		�����-�� ���������� ������� (�� ����� ������ $p$), ����������� �� ��������� 
		������������. ������� � ������� $A^{(0)}$ � $A^{(p)}$ ��������� ��� ������ 
		$p$-�� �������, ������������ � ������ $p$ �������, � ����� ��� ������ $p+1$-��
		�������, ������������ � ������� � �������� $1, 2, \dots , p, i (i>p)$:
		{\small
				\begin{equation}\label{eq:minors_eq}
						\left.
								\begin{array}{c}
										A^{(0)}\left(\begin{array}{ccccc} 1 & 2 & \dots & p \\	k_1 & k_2 & \dots & k_p \\\end{array}\right) =
										A^{(p)}\left(\begin{array}{ccccc} 1 & 2 & \dots & p \\	k_1 & k_2 & \dots & k_p \\\end{array}\right) \\
						  			(1 \leq k_1 < k_2 < \dots < k_{p} \leq n). \\
										A^{(0)}\left(\begin{array}{cccccc} 1 & 2 & \dots & p & i\\	k_1 & k_2 & \dots & k_p & k_{p+1} \\\end{array}\right) =
										A^{(p)}\left(\begin{array}{cccccc} 1 & 2 & \dots & p & i\\	k_1 & k_2 & \dots & k_p & k_{p+1} \\\end{array}\right) \\
						 				(1 \leq k_1 < k_2 < \dots < k_{p+1} \leq n).
						  	\end{array}
						\right\}
				\end{equation}
		}
		�� \Ref{_matA_k} � \Ref{eq:minors_eq} �������:
		\begin{equation}\label{eq:A_p_minor}
				A
				\left(
						\begin{array}{ccccc} 
								1 & 2 & \dots & p \\	
								1 & 2 & \dots & p \\
						\end{array}
				\right) =
				a_{11} a_{22}^{(1)} \dots a_{pp}^{(p-1)}
		\end{equation}
		\begin{equation}\label{eq:A_p+1_minor}
				A
				\left(
						\begin{array}{ccccc} 
								1 & 2 & \dots & p & i\\	
								1 & 2 & \dots & p & k\\
						\end{array}
				\right) =
				a_{11} a_{22}^{(1)} \dots a_{pp}^{(p-1)} a_{ik}^{(p)}
		\end{equation}
		���� �������� \Ref{eq:A_p+1_minor} �� \Ref{eq:A_p_minor}, ������� �������:
		\begin{equation}\label{eq:a_ik^p}
				a_{ik}^{(p)} = \frac
				{
						A
						\left(
								\begin{array}{ccccc} 
										1 & 2 & \dots & p & i\\	
										1 & 2 & \dots & p & k\\
								\end{array}
						\right)
				}
				{
						A
						\left(
								\begin{array}{ccccc} 
										1 & 2 & \dots & p \\	
										1 & 2 & \dots & p \\
								\end{array}
						\right)
				} \quad (i,k = p+1, \dots, n).
		\end{equation}
		�� \Ref{eq:minors_eq} � \Ref{eq:A_p_minor} �������:
		\begin{equation}\label{eq:A_n_minor}
				\left|A\right| = 
						A
						\left(
								\begin{array}{cccc} 
										1 & 2 & \dots & n \\
										1 & 2 & \dots & n \\
								\end{array}
						\right) = 
						A
						\left(
								\begin{array}{cccc} 
										1 & 2 & \dots & p \\
										1 & 2 & \dots & p \\
								\end{array}
						\right)
						\left|
								\begin{array}{ccc}
										a_{p+1,p+1}^{(p)} & \dots & a_{p+1,n}^{(p)} \\
										\hdotsfor{3} \\
										a_{n,p+1}^{(p)} 	& \dots & a_{n,n}^{(p)} \\
								\end{array}
						\right|
		\end{equation}
		�������� �������� \Ref{eq:a_ik^p}:
		{
		\footnotesize
				\begin{equation} \label{eq:pre_Silvesters_identity}
						\left|
								\begin{array}{ccc}
										a_{p+1,p+1}^{(p)} & \dots & a_{p+1,n}^{(p)} \\
										\hdotsfor{3} \\
										a_{n,p+1}^{(p)} 	& \dots & a_{n,n}^{(p)} \\
								\end{array}						
						\right| = 
						\frac
						{
								\left|
										\begin{array}{ccc}
												b_{p+1,p+1}^{(p)} & \dots & b_{p+1,n}^{(p)} \\
												\hdotsfor{3} \\
												b_{n,p+1}^{(p)} 	& \dots & b_{n,n}^{(p)} \\
									\end{array}					
								\right|
						}
						{
								\left[
										A
										\left(
												\begin{array}{cccc} 
														1 & 2 & \dots & p \\
														1 & 2 & \dots & p \\
												\end{array}
										\right)
								\right]^{n-p}
						} = 
						\frac{\left|B^{(p)}\right|}
						{
								\left[
										A
										\left(
												\begin{array}{cccc} 
														1 & 2 & \dots & p \\	
														1 & 2 & \dots & p \\
												\end{array}\right)
								\right]^{n-p}
						}.
		\end{equation}
		}
		������� ��������� \Ref{eq:A_n_minor} ����� ���� ���������� ���:
		\begin{equation}\label{eq:Silvesters_identity}
				\left|B^{(p)}\right|=
						\left[
								A\left(
										\begin{array}{cccc}
												1 & 2 & \dots & p \\
												1 & 2 & \dots & p \\
										\end{array}
								\right)
						\right]^{n-p-1}
				\left|A\right|
		\end{equation}		
\end{proof}

������ ��������� �����������: 
$$ a_{00}^{(-1)} = 1, [a_{ij}^{(0)}]=A^{(0)}, $$
$$
		a_{ij}^{(k)} = 
		\left|
				\begin{array}{ccccc}
						a_{11} & a_{12} & \dots & a_{1k} & a_{1j} \\
						a_{21} & a_{22} & \dots & a_{2k} & a_{2j} \\
						\hdotsfor{5} \\
						a_{k1} & a_{k2} & \dots & a_{kk} & a_{kj} \\
						a_{i1} & a_{i2} & \dots & a_{ik} & a_{ij} 
				\end{array}
		\right|, k+1 \leq i \leq n, k+1 \leq j \leq n+1,
$$
� �������� ����� � ������� 
$$
		\left(
				\begin{array}{ccccc}
						a_{11} & a_{12} & \dots & a_{1k} & a_{1j} \\
						a_{21} & a_{22} & \dots & a_{2k} & a_{2j} \\
						\hdotsfor{5} \\
						a_{k1} & a_{k2} & \dots & a_{kk} & a_{kj} \\
						a_{i1} & a_{i2} & \dots & a_{ik} & a_{ij} 
				\end{array}		
		\right).
$$
������� ��������� ���������:
\begin{equation}\label{eq:silv_k+1}
		a_{ij}^{(k)}\left[a_{pp}^{(p-1)}\right]^{k-p} = 
		\left|
				\begin{array}{cccc}
						a_{p+1,p+1}^{(p)} & \dots & a_{p+1,k}^{(p)} & a_{p+1,j}^{(p)} \\
						\hdotsfor{4} \\
						a_{k,p+1}^{(p)} & \dots & a_{kk}^{(p)} & a_{kj}^{(p)} \\
						a_{i,p+1}^{(p)} & \dots & a_{ik}^{(p)} & a_{ij}^{(p)}
				\end{array}
		\right|,
\end{equation}
��� $1 \leq p \leq k-1.$ ������ �����, ��� ������ ����� \Ref{eq:silv_k+1}
������� �� ��������� $\left[a_{pp}^{(p-1)}\right]^{k-p}$. ���� � 
\Ref{eq:silv_k+1} �������� $p=k-1$, �� �������:
\begin{equation}\label{eq:silv_p_=_k-1}
	  a_{ij}^{(k)} = \frac{1}{\left[a_{k-1,k-1}^{(k-2)}\right]}
		\left|
				\begin{array}{cc}
						a_{kk}^{(k-1)} & a_{k,j}^{(k-1)} \\
						a_{i,k}^{(k-1)} & a_{ij}^{(k-1)}
				\end{array}
		\right|,
\end{equation}
��� � �������� ��������� � \Ref{eq:fraction_free_bareiss}.\\

������ \cite{bareissmultistep} �������, ��� \Ref{eq:silv_k+1} ����� ���� 
������������ ��� ���������� $k-p$ ���������� �� ���. �������� ��������� ������ 
��� $p=k-2$:
\begin{equation}\label{eq:silv_p_=_k-2}
	  a_{ij}^{(k)} = \frac{1}{\left[a_{k-2,k-2}^{(k-3)}\right]^2}
		\left|
				\begin{array}{ccc}
						a_{k-1,k-1}^{(k-2)} & a_{k-1,k}^{(k-2)} & a_{k-1,j}^{(k-2)} \vspace{5pt} \\
						a_{k,k-1}^{(k-2)} & a_{k,k}^{(k-2)} & a_{k,j}^{(k-2)} \vspace{5pt} \\
						a_{i,k-1}^{(k-2)} & a_{i,k}^{(k-2)} & a_{i,j}^{(k-2)}
				\end{array}
		\right|
\end{equation}
��� ���� ������������ ��������� �������:
\begin{eqnarray}
		&&a_{00}^{(-1)} = 1, \left[a_{ij}^{(0)}\right]=A^{(0)},\label{eq:bareiss_k-2_1}\\
		&&c_{0}^{(k-2)} = (a^{(k-2)}_{k-1,k-1}a^{(k-2)}_{kk} - a^{(k-2)}_{k-1,k}a^{(k-2)}_{k,k-1})/a^{(k-3)}_{k-2,k-2},\label{eq:bareiss_k-2_2}\\
		&&c_{i1}^{(k-2)} = (a^{(k-2)}_{k-1,k}a^{(k-2)}_{i,k-1} - a^{(k-2)}_{k-1,k-1}a^{(k-2)}_{i,k})/a^{(k-3)}_{k-2,k-2},\label{eq:bareiss_k-2_3}\\
		&&c_{i2}^{(k-2)} = (a^{(k-2)}_{k,k-1}a^{(k-2)}_{ik} - a^{(k-2)}_{kk}a^{(k-2)}_{i,k-1})/a^{(k-3)}_{k-2,k-2},\label{eq:bareiss_k-2_4}\\
		&&a_{ij}^{(k)} = (c^{(k-2)}_{0}a^{(k-2)}_{ij} + c^{(k-2)}_{i1}a^{(k-2)}_{kj} + c^{(k-2)}_{i2}a^{(k-2)}_{k-1,j})/a^{(k-3)}_{k-2,k-2},\label{eq:bareiss_k-2_5}
\end{eqnarray}
��� $k+1 \leq i \leq n, k+1 \leq j \leq n+1$;
\begin{eqnarray}
		&&a_{kk}^{(k-1)} = c_{0}^{(k-2)},\label{eq:bareiss_k-2_6}\\
		&&a_{kl}^{(k-1)} = a_{kl}^{(k)} = (a_{k-1,k-1}^{(k-2)}a_{kl}^{(k-2)} - a_{k-1,l}^{(k-2)}a_{k,k-1}^{(k-2)})/a^{(k-3)}_{k-2,k-2},\label{eq:bareiss_k-2_7}
\end{eqnarray}
��� $k+1 \leq l \leq n+1$,
������� ����������� ��� $k = 2,4, \dots, 2\left\lfloor \frac{n-1}{2} \right\rfloor$.\\
� ������, ����� $n$ ������, ��������� ��� ����������� �� �������� 
\Ref{eq:fraction_free_bareiss}.

%\textbf{������ 4:}
\begin{example}
�������� ������ ���� ������ ������ ��� �������
\Ref{eq:example1}, ��������� ������� 
\Ref{eq:bareiss_k-2_1}--\Ref{eq:bareiss_k-2_7}. ������������������ 
�������������� ����� ���������:
$$
		A^{(0)}=
		\left[
				\begin{array}{ccccc}
						3 & 4 & -2 & 1 & -2\\
						1 & -1 & 2 & 2 & 7\\
						4 & -3 & 4 & -3 & 2\\
						-1 & 1 & 6 & -1 & 1
				\end{array}
		\right];
\qquad		
		A^{(2)}=
		\left[
				\begin{array}{ccccc}
						3 & 4 	& -2 		& 1 	& -2 \\
						0 & -7 	& 8 		& 5 	& 23 \\
						0 & 0   & 20 		& 72 	& 159 \\
						0 & 0 	& -56 	& -7 	& -56
				\end{array}
		\right];
$$ 
$$
		A^{(3)}=
		\left[
				\begin{array}{ccccc}
						3 & 4   & -2 	& 1 	& -2 \\
						0 & -7 	& 8 	& 5  	& 23 \\
						0 & 0		& 20  & 72 	& 159 \\
						0 & 0		& 0  	& -556& -1112
				\end{array}
		\right].
$$
\end{example}

������ ������������� ������������� ������������ � ����������� ������� \cite{bareisscompsolution}
����������, ��� ��������� ��������������� ������� �� $50\%$.

\subsection*{��������}

\begin{algorithmic}[1]
\REQUIRE $A \in \ZZ^{n \times n}$, $b \in \ZZ^n$, $\det{A} \neq 0$;
\ENSURE ����������� �������, ��������������� �� �������� 
				\Ref{eq:fraction_free_bareiss};
\STATE $d := 1$; \COMMENT{�������������}\\
\FOR{$k=1,\dots,n$}
		\IF{$a_{kk}=0$}
				\STATE $i = k+1$;
				\WHILE{$(i \leq n) \& (a_{ik} = 0)$}
						\STATE $i = i+1$;
				\ENDWHILE
				\IF{$i \leq n$}
						\STATE ����������� $i$-� � $k$-� �������;
				\ELSE
						\STATE �������������;
				\ENDIF
		\ENDIF
		\FOR{$i=k+1,\dots,n$}
				\FOR{$j=k+1,\dots,n$}
						\STATE $a_{ij} = \frac{1}{d}(a_{ij}a_{kk} - a_{kj}a_{ik})$;
				\ENDFOR
				\STATE $b_{i} = \frac{1}{d}(b_{i}a_{kk} - b_{k}a_{ik})$;
				\STATE $a_{ik} = 0$;
				\STATE $a_{ii} = a_{kk}$;
				\STATE $i = i+1$;
		\ENDFOR
		\STATE $d = a_{kk}$;
\ENDFOR
\end{algorithmic}

\section{����������}

���� �������� ������� ������� � �������� ������ �����������, ���������� � 
������ ������ ������� ������ �������� ���������. ������ ������ ������ 
������������� � ���������� ����� ����� (��������, ������� ���������, 
������������� ������� �������� �������� �� ���������� ����������).
������������� � ������� �������� ����� � \cite{algorithforcomputeralgebra}.

\begin{thebibliography}{9} % ������������
\bibitem{algorithforcomputeralgebra}
		{\it Geddes~K.O., Czapor~S.R., Labahn~G.}  Algorithms for Computer Algebra, 1992.
\bibitem{gantmahermatrixtheory}
		{\it ���������~�.�.} ������ ������, 1967.
\bibitem{bareissmultistep}
		{\it Bareiss~E.H.} `Sylvester's Identity and Multistep Integer-Preserving Gaussian
		Elimination // Math. Comp., 1968, 22 (103), P.\,565--578.
\bibitem{bareisscompsolution}
		{\it Bareiss~E.H.} Computational Solutions of Matrix Problems Over an Integral
		Domain // J. Inst. Maths Applcs, 1972, 10, P.\,68--104.
		
\end{thebibliography}
\end{document}