algorithms.tex

\documentclass{article}

\usepackage[T1,T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}

\usepackage[left=2cm,right=2cm, top=2cm,bottom=2cm,bindingoffset=0cm]{geometry}

\usepackage{amsmath,amsthm,amssymb,amsfonts}
\usepackage{mathtext}
\usepackage{mathdots}
\usepackage[all]{xy}
\usepackage[colorlinks=true, urlcolor=blue]{hyperref}  


\newcommand{\tr}{\mathop{\mathrm{tr}}}
\newcommand{\MatrixDim}[3]{\mathop{\mathrm{M}_{#2\,#3}}(#1)}
\newcommand{\Matrix}[2]{\mathop{\mathrm{M}_{#2}}(#1)}
\newcommand{\MatrixR}[1]{\Matrix{\mathbb R}{#1}}
\newcommand{\MatrixC}[1]{\Matrix{\mathbb C}{#1}}
\newcommand{\rk}{\operatorname{rk}}
\newcommand{\diag}{\operatorname{diag}}
\renewcommand{\Im}{\operatorname{Im}}


\renewcommand{\thesubsection}{\arabic{subsection}}

\begin{document}

\section*{Алгоритмы}

\subsection{Выделение базиса из системы векторов}

\paragraph{Дано}

Пусть $v_1,\ldots,v_m\in F^n$ -- вектора и $V = \langle v_1,\ldots,v_m\rangle$ -- их линейная оболочка. 

\paragraph{Задача}

Среди векторов $v_1,\ldots,v_m$ найти базис пространства $V$ и разложить оставшиеся вектора по этому базису.

\paragraph{Алгоритм}

\begin{enumerate}
\item Запишем вектора $v_1,\ldots,v_m$ по столбцам в матрицу $A \in \MatrixDim{F}{n}{m}$. Например, при $n = 3$, $m = 5$
\[
A = 
\begin{pmatrix}
{v_{11}}&{v_{21}}&{v_{31}}&{v_{41}}&{v_{51}}\\
{v_{12}}&{v_{22}}&{v_{32}}&{v_{42}}&{v_{52}}\\
{v_{13}}&{v_{23}}&{v_{33}}&{v_{43}}&{v_{53}}\\
\end{pmatrix}
\]
\item Приведем матрицу $A$ элементарными преобразованиями строк к улучшенному ступенчатому виду. Например
\[
A' = 
\begin{pmatrix}
{1}&{0}&{a_{31}}&{0}&{a_{51}}\\
{0}&{1}&{a_{32}}&{0}&{a_{52}}\\
{0}&{0}&{0}&{1}&{a_{53}}\\
\end{pmatrix}
\]
\item Пусть $k_1,\ldots,k_r$ -- номера главных позиций в матрице $A'$. Тогда вектора $v_{k_1},\ldots,v_{k_r}$ образуют базис $V$. Например, в примере выше это вектора $v_1$, $v_2$ и $v_4$.

\item Пусть $v_i$ -- вектор соответствует неглавной позиции в $A'$. Тогда в $i$-ом столбце $A'$ записаны координаты разложения $v_i$ через найденный базис выше. Например, в примере выше $v_3 = a_{31}v_1 + a_{32}v_2$ и $v_5 = a_{51}v_1 + a_{52}v_2 + a_{53}v_4$.
\end{enumerate}
\paragraph{Пример}
Пусть 
\[
v_1 =
\begin{pmatrix}
{1}\\{3}\\{2}
\end{pmatrix},\,
v_2 =
\begin{pmatrix}
{1}\\{2}\\{1}
\end{pmatrix},\,
v_3 =
\begin{pmatrix}
{5}\\{12}\\{7}
\end{pmatrix},\,
v_4 =
\begin{pmatrix}
{1}\\{1}\\{1}
\end{pmatrix},\,
v_5 =
\begin{pmatrix}
{-1}\\{1}\\{0}
\end{pmatrix}\in F^3
\]
Тогда
\begin{gather*}
\begin{pmatrix}
{1}&{1}&{5}&{1}&{-1}\\
{3}&{2}&{12}&{1}&{1}\\
{2}&{1}&{7}&{1}&{0}\\
\end{pmatrix}\mapsto
\begin{pmatrix}
{1}&{1}&{5}&{1}&{-1}\\
{0}&{0}&{0}&{-1}&{2}\\
{2}&{1}&{7}&{1}&{0}\\
\end{pmatrix}\mapsto
\begin{pmatrix}
{1}&{1}&{5}&{1}&{-1}\\
{0}&{0}&{0}&{-1}&{2}\\
{1}&{0}&{2}&{0}&{1}\\
\end{pmatrix}\mapsto\\\mapsto
\begin{pmatrix}
{1}&{0}&{2}&{0}&{1}\\
{1}&{1}&{5}&{1}&{-1}\\
{0}&{0}&{0}&{1}&{-2}\\
\end{pmatrix}\mapsto
\begin{pmatrix}
{1}&{0}&{2}&{0}&{1}\\
{0}&{1}&{3}&{1}&{-2}\\
{0}&{0}&{0}&{1}&{-2}\\
\end{pmatrix}\mapsto
\begin{pmatrix}
{1}&{0}&{2}&{0}&{1}\\
{0}&{1}&{3}&{0}&{0}\\
{0}&{0}&{0}&{1}&{-2}\\
\end{pmatrix}
\end{gather*}
Тогда $v_1$, $v_2$ и $v_4$ -- базис линейной оболочки. $v_3 = 2v_1 + 3 v_2$ и $v_5 = v_1 - 2 v_4$.

\subsection{Нахождение какого-то базиса линейной оболочки}

\paragraph{Дано} Пусть $v_1,\ldots,v_m\in F^n$ -- вектора и $V = \langle v_1,\ldots,v_m\rangle$ -- их линейная оболочка. 

\paragraph{Задача} Найти какой-нибудь базис подпространства $V$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Уложить все вектора $v_i$ в строки матрицы $A\in \MatrixDim{F}{m}{n}$.

\item Элементарными преобразованиями строк привести матрицу к ступенчатому виду. 

\item Ненулевые строки полученной матрицы будут искомым базисом.
\end{enumerate}

\subsection{Дополнение линейно независимой системы до базиса всего пространства стандартными векторами}

\paragraph{Дано} Пусть $v_1,\ldots,v_m\in F^{n}$ -- линейно независимая система векторов, $V = \langle v_1,\ldots,v_m \rangle$ -- их линейная оболочка и $e_i$ -- стандартные базисные векторы, т.е. на $i$-ом месте стоит $1$, а в остальных $0$.

\paragraph{Задача} Найти такие вектора $e_{k_1},\ldots, e_{k_{n-m}}$, что система $v_1,\ldots,v_m,e_{k_1},\ldots,e_{k_{n-m}}$ является базисом $F^{n}$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Уложить вектора $v_i$ в строки матрицы $A\in\MatrixDim{F}{m}{n}$.

\item Привести матрицу $A$ к ступенчатому виду.

\item Пусть $k_1,\ldots,k_{n-m}$ -- номера неглавных столбцов. Тогда $e_{k_1},\ldots,e_{k_{n-m}}$ -- искомое множество.
\end{enumerate}

\subsection{Найти ФСР однородной СЛУ}

\paragraph{Дано} Система однородных линейных уравнений $Ax = 0$, где $A\in \MatrixDim{F}{m}{n}$ и $x\in F^{n}$.

\paragraph{Задача} Найти ФСР системы $Ax = 0$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Привести матрицу $A$ элементарными преобразованиями строк к улучшенному ступенчатому виду. Например
\[
A' = 
\begin{pmatrix}
{1}&{0}&{a_{31}}&{0}&{a_{51}}\\
{0}&{1}&{a_{32}}&{0}&{a_{52}}\\
{0}&{0}&{0}&{1}&{a_{53}}\\
\end{pmatrix}
\]

\item Пусть $k_1,\ldots,k_r$ -- позиции свободных переменных. Если положить одну из этих переменных равной $1$, а все остальные нулями, то существует единственное решение, которое мы обозначим через $u_i$ (всего $r$ штук). Например, для матрицы $A'$ выше свободные переменные имеют номера $3$ и $5$. Тогда вектора (записанные в строку)
\[
u_1 = 
\begin{pmatrix}
{-a_{31}}&{-a_{32}}&{1}&{0}&{0}
\end{pmatrix},\,
u_2 = 
\begin{pmatrix}
{-a_{51}}&{-a_{52}}&{0}&{-a_{53}}&{1}
\end{pmatrix}
\]
являются ФСР.
\end{enumerate}


\subsection{Задать подпространство базисом, если оно задано матричным уравнением}


\paragraph{Дано} Пусть $A\in\MatrixDim{F}{m}{n}$ и $V\subseteq F^{n}$ задано в виде $V = \{y\in F^{n}\mid A y = 0\}$.

\paragraph{Задача} Найти базис подпространства $V$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Найти ФСР системы $Ay = 0$. Векторы ФСР будут базисом $V$.
\end{enumerate}

\subsection{Задать подпространство матричным уравнением, если оно задано линейной оболочной}

\paragraph{Дано} Пусть $v_1,\ldots,v_k\in F^{n}$ -- набор векторов и $V = \langle v_1,\ldots,v_k \rangle$.

\paragraph{Задача} Для некоторого $m$ найти матрицу $A\in\MatrixDim{F}{m}{n}$ такую, что $V = \{y\in F^{n}\mid Ay = 0\}$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Уложить вектора $v_i$ в строки матрицы $B\in \MatrixDim{F}{k}{n}$.
\item Найти ФСР системы $Bz = 0$.
\item Уложить ФСР в строки матрицы $A\in \MatrixDim{F}{m}{n}$, где $m$ -- количество векторов в ФСР. Матрица $A$ и будет искомой.
\end{enumerate}


\subsection{Найти матрицу замены координат}

\paragraph{Дано} Векторное пространство $V$, $e=(e_1,\ldots,e_n)$ и $f = (f_1,\ldots,f_n)$ -- два базиса пространства $V$. Известна матрица перехода от $e$ к $f$, т.е. $(f_1,\ldots,f_n) = (e_1,\ldots,e_n)A$, где $A\in \Matrix{F}{n}$. Дан вектор $v = x_1e_1+\ldots+x_n e_n$.

\paragraph{Задача} Найти разложение $v$ по  базису $f$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Если $v = e x$, где $x\in F^{n}$, а также $v = f y$, где $y\in F^{n}$, то $y = A^{-1}x$.
\end{enumerate}


\subsection{Найти матрицу линейного отображения при замене базиса}

\paragraph{Дано}

Векторное пространство $V$ с базисами $e=(e_1,\ldots,e_n)$ и $e'=(e'_1,\ldots,e'_n)$, а также векторное пространство $U$ с базисами $f = (f_1,\ldots,f_m)$ и $f' = (f'_1,\ldots,f'_m)$. Известны матрицы перехода $(e'_1,\ldots,e'_n) = (e_1,\ldots,e_n)C$ и $(f'_1,\ldots,f'_m) = (f_1,\ldots,f_m)D$, где $C\in \Matrix{F}{n}$ и $D\in \Matrix{F}{m}$. Дано линейное отображение $\phi\colon V\to U$ заданное в базисах $e$ и $f$ матрицей $A\in\MatrixDim{F}{n}{m}$, т.е. $\phi e = f A$.

\paragraph{Задача}

Найти матрицу отображения $\phi$ в базисах $e'$ и $f'$, то есть такую $A'\in \MatrixDim{F}{n}{m}$, что $\phi e' = f' A'$.

\paragraph{Алгоритм}
\begin{enumerate}
\item $A' = D^{-1} A C$.
\end{enumerate}


\subsection{Определить существует ли линейное отображение заданное на векторах}

\paragraph{Дано} Векторное пространство $V$ над полем $F$ и набор векторов $v_1,\ldots,v_k\in V$, векторное пространство $U$ и набор векторов $u_1,\ldots,u_k\in U$. 

\paragraph{Задача} Определить существует ли линейное отображение $\phi\colon V\to U$ такое, что $\phi(v_i) = u_i$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Среди векторов $v_1,\ldots,v_k$ выделить линейно независимые, а остальные разложить по ним.

\item Пусть на предыдущем этапе базис получился $v_1,\ldots,v_r$, а $v_{r + i} = a_{i1} v_1 + \ldots + a_{ir}v_r$. 

\item Искомое линейное отображение $\phi$ существует тогда и только тогда, когда выполняются равенства $u_{r+i} = a_{i1}u_1 + \ldots + a_{ir}u_r$.\footnote{В частности, если все $v_i$ оказались линейно независимыми, то линейное отображение $\phi$ обязательно существует.}
\end{enumerate}

\subsection{Найти базис образа и ядра линейного отображения}

\paragraph{Дано} $\phi\colon F^{n}\to F^{m}$ задан $x\mapsto Ax$, где $A\in\MatrixDim{F}{m}{n}$.

\paragraph{Задача} Найти базис $\Im \phi\in F^{m}$ и базис $\ker \phi\in F^{n}$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Выделить базис среди столбцов матрицы $A$. В результате получится базис $\Im \phi$.

\item Найти ФСР системы $Ax = 0$. Полученная ФСР будет базисом $\ker \phi$.
\end{enumerate}

\subsection{Найти линейное отображение с заданными ядром и образом}

\paragraph{Дано} Пространства $U\subseteq F^n$ и $W \subseteq F^m$ такие, что $\dim U + \dim W = n$.

\paragraph{Задача} Найти матрицу линейного отображения $\varphi \colon F^n \to F^m$ такого, что $U = \ker \varphi$ и $W = \Im \varphi$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Задать подпространство $W$ с помощью базиса. Пусть $b_1,\ldots,b_k$ -- базис $W$. Определим матрицу $B = (b_1 |\ldots |b_k)$.

\item Задать подпространство $U$ системой с линейно независимыми строками $U = \{y\in F^n \mid A y = 0\}$.

\item В силу условия $\dim U + \dim W = n$ матрица $A$ будет иметь столько же строк, сколько столбцов в матрице $B$. В этом случае искомое линейное отображение задается матрицей $BA$.
\end{enumerate}



\subsection{Найти сумму подпространств заданных линейными оболочками}

\paragraph{Дано} Подпространства $V,U\subseteq F^{n}$ заданные в виде $V = \langle v_1,\ldots,v_m\rangle$, $U = \langle u_1,\ldots,u_k\rangle$, где $v_i,u_j\in F^{n}$.

\paragraph{Задача} Найти базис $V + U$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Надо найти базис линейной оболочки $\langle v_1,\ldots,v_m,u_1,\ldots,u_k\rangle$.
\end{enumerate}

\subsection{Найти пересечение подпространств заданных линейными оболочками}

\paragraph{Дано} Подпространства $V,U\subseteq F^{n}$ заданные в виде $V = \langle v_1,\ldots,v_m\rangle$, $U = \langle u_1,\ldots,u_k\rangle$, где $v_i,u_j\in F^{n}$.

\paragraph{Задача} Найти базис $V\cap U$.\footnote{В это задаче можно задать подпространства системами, потом найти пересечение в виде системы, потом задать результат базисом. Но есть куда более эффективный способ.}

\paragraph{Алгоритм}
\begin{enumerate}
\item Найти ФСР системы $D x = 0$, где $D = (v_1|\ldots|v_m|u_1|\ldots|u_k)$ и $x = \left(\frac{\alpha}{\beta}\right)$, где $\alpha\in F^{m}$, $\beta\in F^{k}$.

\item Пусть $\left(\left.\left.\frac{\alpha_1}{\beta_1}\right|\ldots\right|\frac{\alpha_s}{\beta_s}\right)$ -- ФСР.  Далее есть две опции (из них вторая опция предпочтительнее!):
\begin{itemize}
\item Множество векторов $R = (v_1|\ldots|v_m)(\alpha_1|\ldots|\alpha_s)$ порождает $V\cap U$. Среди $(\alpha_1|\ldots|\alpha_s)$ можно выкинуть те $\alpha_i$, для которых $\beta_i = 0$.\footnote{Если ФСР построен по стандартному базису, то останутся $\alpha_i$ с нулевыми свободными переменными.}

\item Множество векторов $R' = (u_1|\ldots|u_k)(\beta_1|\ldots|\beta_s)$ порождает  $V\cap U$. Причем можно рассматривать только ненулевые $\beta_i$.

\end{itemize}

\item Выделить базис среди столбцов $R$. Это и будет базис $V\cap U$.
\begin{itemize}
\item Если векторы $u_1,\ldots,u_k$ были линейно независимы изначально и $\beta_i,\ldots,\beta_s$ -- все ненулевые сегменты ФСР с прошлого шага, то $(u_1|\ldots|u_k)(\beta_i|\ldots|\beta_s)$ будет базисом $V\cap U$.
\end{itemize}
\end{enumerate}


\subsection{Найти пересечение подпространств заданных матричным уравнением}

\paragraph{Дано}

Подпространства $V,U\subseteq F^{n}$ заданные в виде $V = \{y\in F^{n}\mid Ay = 0\}$, $U = \{y\in F^{n}\mid By = 0\}$, где $A\in \MatrixDim{F}{m}{n}$ и $B\in \MatrixDim{F}{k}{n}$.

\paragraph{Задача}

Задать $V\cap U$ в виде $\{y\in F^{n}\mid D y = 0\}$ для некоторого $D\in\MatrixDim{F}{k}{n}$, где $\rk D = k\leqslant n$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Рассмотреть матрицу $D' = \left(\frac{A}{B}\right)$.

\item Выделить среди строк $D'$ линейно независимую подсистему. Результат и будет искомая $D$.
\end{enumerate}


\subsection{Найти сумму подпространств заданных матричным уравнением}

\paragraph{Дано}

Подпространства $V,U\subseteq F^{n}$ заданные в виде $V = \{y\in F^{n}\mid Ay = 0\}$, $U = \{y\in F^{n}\mid By = 0\}$, где $A\in \MatrixDim{F}{m}{n}$ и $B\in \MatrixDim{F}{k}{n}$.

\paragraph{Задача}

Задать $V+U$ в виде $\{y\in F^{n}\mid Ry = 0\}$ для некоторого $R\in \MatrixDim{F}{k}{n}$, где $\rk R = k \leqslant n$.\footnote{В этой задаче можно задать подпространства базисами, потом найти сумму заданной базисом, потом задать эту сумму системой. Но есть более эффективный метод.}

\paragraph{Алгоритм}
\begin{enumerate}
\item Найти ФСР системы $D x = 0$, где $D = (A^t|B^t)$ и $x = \left(\frac{\alpha}{\beta}\right)$, где $\alpha \in F^{m}$ и $\beta\in F^{k}$.

\item Пусть $\left(\left.\left.\frac{\alpha_1}{\beta_1}\right|\ldots\right|\frac{\alpha_s}{\beta_s}\right)$ -- ФСР. Далее есть две опции:
\begin{itemize}
\item Если определим $S = (\alpha_1|\ldots|\alpha_s)^t A$, то $V+U = \{y\in F^{n}\mid Sy = 0\}$. Здесь достаточно взять только те $\alpha_i$, для которых $\beta_i$ не равны нулю.

\item Если определим $T = (\beta_1|\ldots|\beta_s)^t B$, то $V+U = \{y\in F^{n}\mid Ty = 0\}$. Здесь достаточно взять только ненулевые $\beta_i$.
\end{itemize}

\item Выделить базис среди строк $S$ (или $T$). Это и будет искомая матрица $R$.
\begin{itemize}
\item Если строки $B$ были линейно независимыми и мы выбрали только ненулевые $\beta_i$, то $T$ уже будет искомой, то есть ее строки будут линейно независимыми.
\end{itemize}
\end{enumerate}


\subsection{Найти пересечение подпространств заданных разными способами}

\paragraph{Дано}

Подпространства $V,U\subseteq F^{n}$ заданные в виде $V =\langle v_1,\ldots,v_m\rangle$, $U = \{y\in F^{n}\mid Ay = 0\}$, где $A\in \MatrixDim{F}{k}{n}$.

\paragraph{Задача}

Найти базис $V \cap U$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Определим матрицу $B = (v_1|\ldots|v_m)$ и найдем ФСР для системы $AB x = 0$. Пусть это будет $x_1,\ldots, x_t$.

\item Тогда столбцы матрицы $R = B (x_1|\ldots|x_t)$ порождают $V \cap U$.

\item Отобрать среди столбцов $R$ линейно независимые.
\begin{itemize}
\item Если $v_1,\ldots,v_m$ были линейно независимы (то есть базис $V$), то столбцы $R$ уже будут линейно независимыми.
\end{itemize}
\end{enumerate}

\subsection{Найти пересечение подпространств заданных разными способами}

\paragraph{Дано}

Подпространства $V,U\subseteq F^{n}$ заданные в виде $V =\langle v_1,\ldots,v_m\rangle$, $U = \{y\in F^{n}\mid Ay = 0\}$, где $A\in \MatrixDim{F}{k}{n}$.

\paragraph{Задача}

Задать $V \cap U$ системой линейных уравнений.

\paragraph{Алгоритм}
\begin{enumerate}
\item Задать подпространство $V$ системой в виде $\{x\in F^n \mid Dx = 0\}$.

\item Тогда $V\cap U$ задается объединенной системой $\left(\frac{B}{D}\right)$.
\end{enumerate}


\subsection{Найти сумму подпространств заданных разными способами}

\paragraph{Дано}

Подпространства $V,U\subseteq F^{n}$ заданные в виде $V =\langle v_1,\ldots,v_m\rangle$, $U = \{y\in F^{n}\mid Ay = 0\}$, где $A\in \MatrixDim{F}{k}{n}$.

\paragraph{Задача}

Задать $V + U$ в виде $\{x\in F^n \mid Dx = 0\}$, где $D\in \MatrixDim{F}{t}{n}$ и $t = \rk D$.\footnote{Всегда можно задать $U$ линейной оболочкой, потом задать $V+U$ линейной оболочкой, а потом найти представление системой. Я же покажу тут другой подход.}

\paragraph{Алгоритм}
\begin{enumerate}
\item Определим матрицу $B = (v_1|\ldots|v_m)$ и найдем ФСР для системы $B^tA^t x = 0$. Пусть это будет $x_1,\ldots, x_t$.

\item Тогда матрица $D' = (x_1|\ldots|x_t)^tA$ задает $V + U$ системой.

\item Отобрать среди строк $D'$ линейно независимые и получить $D$.
\begin{itemize}
\item Если строки $A$ были линейно независимы, то строки $D'$ уже будут линейно независимыми.
\end{itemize}
\end{enumerate}


\subsection{Найти сумму подпространств заданных разными способами}

\paragraph{Дано}

Подпространства $V,U\subseteq F^{n}$ заданные в виде $V =\langle v_1,\ldots,v_m\rangle$, $U = \{y\in F^{n}\mid Ay = 0\}$, где $A\in \MatrixDim{F}{k}{n}$.

\paragraph{Задача}

Задать $V + U$ в виде линейной оболочки.

\paragraph{Алгоритм}
\begin{enumerate}
\item Задать подпространство $U$ с помощью линейной оболочки.

\item Объединить линейные оболочки для $V$ и для $U$.
\end{enumerate}



\subsection{Найти матрицу линейного оператора при замене базиса}

\paragraph{Дано} Векторное пространство $V$ над полем $F$, $e=(e_1,\ldots,e_n)$ и $f = (f_1,\ldots,f_n)$ -- два базиса пространства $V$. Известна матрица перехода от $e$ к $f$, т.е. $(f_1,\ldots,f_n) = (e_1,\ldots,e_n)C$, где $C\in \Matrix{F}{n}$. Дано линейное отображение $\phi\colon V\to V$ заданное в базисе $e$ матрицей $A\in\Matrix{F}{n}$, т.е. $\phi e = e A$.

\paragraph{Задача} Найти матрицу отображения $\phi$ в базисе $f$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Пусть $\phi f = f B$, где $B$ -- искомая матрица. Тогда $B = C^{-1} A C$.
\end{enumerate}



\subsection{Найти проекцию вектора на подпространство вдоль другого подпространства}

\paragraph{Дано} $F^{n} = V \oplus U$, где $V$ и $U$ заданы базисами $V = \langle v_1,\ldots,v_m\rangle$, $U = \langle u_1,\ldots,u_k\rangle$. Пусть $z\in F^{n}$ раскладывается $z = v + u$, где $v\in V$ и $u\in U$.

\paragraph{Задача} Найти $v$ и $u$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Решить СЛУ $D x = z$, где $D = (v_1|\ldots|v_m|u_1|\ldots|u_k)$ и $x = \left(\frac{\alpha}{\beta}\right)$, где $\alpha\in F^{m}$ и $\beta\in F^{k}$.

\item Тогда $v = (v_1|\ldots|v_m)\alpha$ и $u = (u_1|\ldots|u_k)\beta$.
\end{enumerate}

\subsection{Найти оператор проекции на подпространство вдоль другого подпространства}

\paragraph{Дано} $F^{n} = V \oplus U$, где $V$ задано базисом $V = \langle v_1,\ldots,v_m\rangle$, $U = \{y\in F^{n}\mid Ay = 0\}$, где $A\in \MatrixDim{F}{k}{n}$ и $\rk A = k \leqslant n$. 

\paragraph{Задача} Найти матрицу отображения $\phi\colon V\to V$ такого, что $\phi(U) = 0$ и $\phi(v) = v$ для любого $v\in V$.\footnote{Заметим, что если $z\in F^{n}$ раскладывается $z = v + u$, где $v\in V$ и $u\in U$, то $\phi(z) = v$.}

\paragraph{Алгоритм}

\begin{enumerate}
\item Положим $B = (v_1|\ldots|v_m)\in \MatrixDim{F}{n}{m}$.

\item Обязательно получится, что $m = k$ и матрица $AB$ невырождена.

\item Искомый $\phi$ имеет матрицу $B(AB)^{-1}A$.

\end{enumerate}


\subsection{Поиск собственных значений и векторов}

\paragraph{Дано} Матрица $A\in\Matrix{F}{n}$.


\paragraph{Задача} Найти все собственные значения $\lambda_i$ для $A$ и для каждого $\lambda_i$ найти базис пространства $V_{\lambda_i} = \{v\in F^{n}\mid A v = \lambda_i v\}$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Посчитать характеристический многочлен $(-1)^n\chi_A(\lambda) = \det(A-\lambda E)$.

\item Найти корни многочлена $\chi_A(\lambda)$. Корни $\{\lambda_1,\ldots,\lambda_k\}$ будут собственным значениями $A$.

\item Для каждого $\lambda_i$ найти ФСР системы $(A-\lambda_i E)x = 0$. Тогда ФСР будет базисом $V_{\lambda_i}$.
\end{enumerate}

Если дополнительно найти с каждым собственным значением $\lambda_i$ его кратность $n_i$ в характеристическом многочлене, то на последнем шаге размер ФСР для $\lambda_i$ оценивается так. Собственных векторов будет не меньше чем $1$ и не больше, чем $n_i$.


\subsection{Поиск корневых подпространств}

\paragraph{Дано} Матрица $A\in\Matrix{F}{n}$.


\paragraph{Задача} Найти все собственные значения $\lambda_i$ для $A$ и для каждого $\lambda_i$ найти базис пространства $V^{\lambda_i} = \{v\in F^{n}\mid \exists n\colon (A - \lambda_i E)^n v = 0\}$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Посчитать характеристический многочлен $(-1)^n\chi_A(\lambda) = \det(A-\lambda E)$.

\item Найти корни многочлена $\chi_A(\lambda)$ с кратностями. Корни $\{\lambda_1,\ldots,\lambda_k\}$ будут собственным значениями $A$. И пусть кратности будут $\{n_1,\ldots, n_k\}$.

\item Для каждого $\lambda_i$ найти ФСР системы $(A-\lambda_i E)^{n_i}x = 0$. Тогда ФСР будет базисом $V^{\lambda_i}$. Обратите внимание, что для каждого $\lambda_i$ должно получиться ровно $n_i$ векторов.
\end{enumerate}


\subsection{Поиск инвариантных подпространств}

\paragraph{Дано} Матрица $A\in\Matrix{F}{n}$.

\paragraph{Задача} Найти все подпространства $U\subseteq F^n$ такие, что $A U \subseteq U$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Для каждого вектора $v\in F^n$ найти главное инвариантное подпространство
\[
[v]_A = \langle v, Av, A^2v, \ldots, A^mv, \ldots\rangle
\]
Обратите внимание, что это <<творческий шаг>> тут нет общего алгоритма,\footnote{Если говорить правду, то алгоритм то есть, но он такой геморройный и требует знаний, которых пока у нас нет, так что да ну его.} тут придется немного догадаться.

\item Описать все инвариантные подпространства, как конечные суммы главных, а именно любое инвариантное $U$ будет иметь вид $[v_1]_A + \ldots +[v_k]_A$, где $v_1,\ldots, v_k$ пробегает все возможные конечные наборы векторов.
\end{enumerate}

\subsection{Поиск инвариантных подпространств для диагонализуемого оператора}

\paragraph{Дано} Матрица $A\in\Matrix{F}{n}$, задающая диагонализуемый оператор.

\paragraph{Задача} Найти все подпространства $U\subseteq F^n$ такие, что $A U \subseteq U$.

\paragraph{Алгоритм}
\begin{enumerate}
\item В начале надо найти все собственные значения и собственные подпространства. Пусть $\lambda_1,\ldots, \lambda_k$ -- все собственные значения с кратностями $n_1,\ldots,n_k$. Тогда $F^n = V_{\lambda_1}\oplus \ldots \oplus V_{\lambda_k}$.

\item Надо выбрать произвольное подпространство $U_i\subseteq V_{\lambda_i}$ (включая нулевое и все $V_{\lambda_i}$ целиком). Тогда $U_1,\ldots, U_k$ будут линейно независимыми и $U = U_1 \oplus \ldots \oplus U_k$ будут все возможные инвариантные подпространства.
\end{enumerate}

\subsection{Проверка на диагонализуемость}

\paragraph{Дано} Матрица $A\in\Matrix{F}{n}$, задающая линейный оператор $\varphi\colon F^n\to F^n$.

\paragraph{Задача} Выяснить существует ли базис, в котором $\varphi$ задается диагональной матрицей и если задается, то какой именно. На матричном языке: существует ли невырожденная матрица $C\in \Matrix{F}{n}$ такая, что $C^{-1}AC$ является диагональной и найти эту диагональную матрицу.

\paragraph{Алгоритм}

\begin{enumerate}
\item Найдем характеристический многочлен $\chi(t)$ для $\varphi$, он же для $A$ по формуле $(-1)^n\chi(t) = \det(A-t E)$.

\item Проверим, раскладывается ли $\chi(t)$ на линейные множители над $F$, то есть представляется ли он в виде $\chi(t) = (t-\lambda_1)^{d_1} \ldots (t-\lambda_k)^{d_k}$. Если не представляется, то $\varphi$ (или что то же самое $A$) не диагонализируется


\item Если $\chi(t) = (t-\lambda_1)^{d_1} \ldots (t-\lambda_k)^{d_k}$. Найдем для каждого $\lambda_i$ базис $V_{\lambda_i}$ как ФСР системы $(A-\lambda_i E)x = 0$. Если для хотя бы одного $i$ количество элементов в ФСР меньше соответствующей кратности корня $d_i$, то $\varphi$ не диагонализируется.

\item Если для каждого $i$ мы получили, что размер ФСР совпадает с кратностью корня, то есть $\dim V_{\lambda_i} = d_i$. То $\varphi$ диагонализируется. В этом случае матрица $C$ состоит из собственных векторов. Если собственные векторы для $\lambda_i$ есть $\{v_{i1},\ldots,v_{id_i}\}$, то $C = (v_{11}|\ldots|v_{1d_1}|v_{21}|\ldots|v_{2d_2}|\ldots |v_{k1}|\ldots|v_{kd_k})$. При этом в новом базисе будет диагональная матрица $C^{-1}AC =\operatorname{Diag}(\lambda_1,\ldots,\lambda_1,\lambda_2,\ldots,\lambda_2,\ldots,\lambda_k,\ldots,\lambda_k)$, где каждое $\lambda_i$ встречается $d_i$ раз.
\end{enumerate}


Заметим, что если поле $F$ алгебраически замкнуто, то первый шаг алгоритма выполнен автоматически, а именно, над алгебраически замкнутым полем любой многочлен разлагается на линейные множители. Потому в этом случае вопрос о диагонализируемости -- это лишь проверка всех равенств $\dim V_{\lambda_i} = d_i$.


\subsection{Определить ЖНФ у оператора}

\paragraph{Дано} Матрица $A\in \Matrix{F}{n}$, где поле $F$ алгебраически замкнуто.

\paragraph{Задача} Определить все собственные значения и размеры клеток в жордановой нормальной форме.

\paragraph{Алгоритм}
\begin{enumerate}
\item Собственные значения совпадают со спектром их ищем, как корни характеристического многочлена $\chi_A(t) = (-1)^n\det(A - t E) = 0$. Получаем набор корней и их кратности $(\lambda_1, n_1),\ldots,(\lambda_k,n_k)$.

\item Для каждого $\lambda_i$ суммарный размер клеток равен $n_i$. Потому надо определить количество клеток для всех $k\in [1, n_i]$. Количество клеток считается по формуле
\[
\text{количество клеток размера $k$ } = \rk (A - \lambda_i E)^{k+1} + \rk(A - \lambda_i E)^{k-1} - 2 \rk(A - \lambda_i E)^k
\]
\end{enumerate}

Обратите внимание, что если вы нашли $m$ клеток размера $k$, а кратность была $n_i$, то на оставшиеся клетки уходит $n_i - mk$ мест. Этим можно пользоваться, чтобы не считать все количества клеток подряд.


\subsection{Определение ЖНФ у матриц $2$ на $2$}

\paragraph{Дано} Матрица $A\in \Matrix{F}{2}$, где поле $F$ алгебраически замкнутое.

\paragraph{Найти} Жорданова форма может быть одной из
\[
\begin{pmatrix}
{\lambda}&{}\\
{}&{\mu}\\
\end{pmatrix}
,\quad
\begin{pmatrix}
{\lambda}&{}\\
{}&{\lambda}\\
\end{pmatrix}
,\quad
\begin{pmatrix}
{\lambda}&{1}\\
{}&{\lambda}\\
\end{pmatrix}
\]
Определить какая форма в нашем случае и определить все числа.

\paragraph{Алгоритм}
Общая идея в том, чтобы подобрать инварианты, которые достаточно рассчитать для выбора из предоставленных вариантов.
\begin{enumerate}
\item Найдем характеристический многочлен $\chi_A(t) =\det(A - t E)$. И посчитаем его корни. Есть два варианта: 
\begin{enumerate}
\item два разных корня $\lambda$ и $\mu$. В этом случае ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{}\\
{}&{\mu}\\
\end{pmatrix}
\]

\item один корень $\lambda$ кратности $2$. В этом случае, если $A = \lambda E$, то ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{}\\
{}&{\lambda}\\
\end{pmatrix}
\]
В противном случае ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}\\
{}&{\lambda}\\
\end{pmatrix}
\]
\end{enumerate}
\end{enumerate}

\subsection{Определить Жорданов базис у матриц $2$ на $2$}

\paragraph{Дано} Матрица $A \in \Matrix{F}{2}$, где поле $F$ алгебраически замкнутое.

\paragraph{Задача} Зная ЖНФ определить жорданов базис $f_1, f_2$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Пусть ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{}\\
{}&{\mu}
\end{pmatrix}
\]
В этом случае оператор диагонализум, а значит базис выбирается из собственных векторов. Есть два способа найти их:
\begin{enumerate}
\item Вектор $f_1$ находим как ненулевое решение системы $(A- \lambda E) x = 0$, а вектор $f_2$ находим как ненулевое решение системы $(A - \mu E) x = 0$.

\item Вектор $f_1$ находим как ненулевой столбец матрицы $A - \mu E$, а вектор $f_2$ находим как ненулевой столбец матрицы $A-\lambda E$.
\end{enumerate}

\item Пусть ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{}\\
{}&{\lambda}
\end{pmatrix}
\]
В этом случае подходит любой базис.

\item Пусть ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}\\
{}&{\lambda}
\end{pmatrix}
\]
В этом случае жорданов базис образует цепочку
\[
\xymatrix@R=15pt@C=15pt{
  {f_2}\ar@{|->}[d]^{A-\lambda E}\\
  {f_1}\ar@{|->}[d]^{A-\lambda E}\\
  {0}
}
\]
В этом случае векторы базиса ищутся так
\begin{enumerate}
\item Выбираем случайный вектор $f_2$. Всегда достаточно выбирать из стандартных базисных векторов.
\item Полагаем $f_1 = (A - \lambda E) f_2$.
\item Если $f_1 = 0$, то вернуться к выбору вектора $f_2$. Если $f_1 \neq 0$, то $f_1, f_2$ -- искомый базис.
\end{enumerate}
\end{enumerate}

\subsection{Определение ЖНФ у матриц $3$ на $3$}

\paragraph{Дано} Матрица $A\in \Matrix{F}{3}$, где поле $F$ алгебраически замкнуто.

\paragraph{Найти} Жорданова форма может быть одной из
\[
\begin{pmatrix}
{\lambda}&{}&{}\\
{}&{\mu}&{}\\
{}&{}&{\gamma}\\
\end{pmatrix}
,\quad
\begin{pmatrix}
{\lambda}&{}&{}\\
{}&{\lambda}&{}\\
{}&{}&{\mu}\\
\end{pmatrix}
,\quad
\begin{pmatrix}
{\lambda}&{1}&{}\\
{}&{\lambda}&{}\\
{}&{}&{\mu}\\
\end{pmatrix}
,\quad
\begin{pmatrix}
{\lambda}&{}&{}\\
{}&{\lambda}&{}\\
{}&{}&{\lambda}\\
\end{pmatrix}
,\quad
\begin{pmatrix}
{\lambda}&{1}&{}\\
{}&{\lambda}&{}\\
{}&{}&{\lambda}\\
\end{pmatrix}
,\quad
\begin{pmatrix}
{\lambda}&{1}&{}\\
{}&{\lambda}&{1}\\
{}&{}&{\lambda}\\
\end{pmatrix}
\]
Определить какая форма в нашем случае и определить все числа.
\paragraph{Алгоритм}
Общая идея в том, чтобы подобрать инварианты, которые достаточно рассчитать для выбора из предоставленных вариантов.
\begin{enumerate}
\item Найдем характеристический многочлен $\chi_A(t) = - \det(A - tE)$ и посчитаем его корни. Возможны следующие варианты:
\begin{itemize}
\item три разных корня $\lambda$, $\mu$, $\gamma$.
\item один корень $\lambda$ кратности $2$, один корень $\mu$ кратности $1$.
\item один корень $\lambda$ кратности $3$.
\end{itemize}
\item Три разных корня. В этом случае ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{}&{}\\
{}&{\mu}&{}\\
{}&{}&{\gamma}\\
\end{pmatrix}
\]

\item Два разных корня, $\lambda$ кратности $2$ и $\mu$ кратности $1$. В этом случае, если $\rk (A - \lambda E) = 1$, то ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{}&{}\\
{}&{\lambda}&{}\\
{}&{}&{\mu}\\
\end{pmatrix}
\]
В противном случае (то есть, если $\rk(A-\lambda E) = 2$) ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}&{}\\
{}&{\lambda}&{}\\
{}&{}&{\mu}\\
\end{pmatrix}
\]

\item Один корень $\lambda$ кратности $3$. Если $A = \lambda E$, то ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{}&{}\\
{}&{\lambda}&{}\\
{}&{}&{\lambda}\\
\end{pmatrix}
\]
Если $\rk(A-\lambda E) = 1$, то ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}&{}\\
{}&{\lambda}&{}\\
{}&{}&{\lambda}\\
\end{pmatrix}
\]
В противном случае (то есть $\rk(A - \lambda E) = 2$) ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}&{}\\
{}&{\lambda}&{1}\\
{}&{}&{\lambda}\\
\end{pmatrix}
\]
\end{enumerate}

\subsection{Определить Жорданов базис у матриц $3$ на $3$}

\paragraph{Дано} Матрица $A \in \Matrix{F}{3}$, где поле $F$ алгебраически замкнуто.

\paragraph{Задача} Зная ЖНФ определить жорданов базис $f_1, f_2, f_3$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Пусть ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{}&{}\\
{}&{\mu}&{}\\
{}&{}&{\gamma}\\
\end{pmatrix}
\]
В этом случае оператор диагонализуем, а значит базис выбирается из собственных векторов. Базис можно найти следующим образом. Вектор $f_1$ -- ненулевое решение системы $(A - \lambda E) x = 0$, вектор $f_2 $ -- ненулевое решение системы $(A - \mu E) x = 0$, вектор $f_3$ -- ненулевое решение системы $(A - \gamma E) x = 0$.

\item Пусть ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{}&{}\\
{}&{\lambda}&{}\\
{}&{}&{\mu}\\
\end{pmatrix}
\]
В этом случае оператор диагонализуем, а значит базис выбирается из собственных векторов. Базис можно найти одним из двух способов ниже:
\begin{enumerate}
\item Вектор $f_3$ берется как решение системы $(A - \mu E) x = 0$, векторы $f_1, f_2$ берутся как ФСР системы $(A - \lambda E) x = 0$.

\item Вектор $f_3$ берется как ненулевой столбец матрицы $A - \lambda E$, векторы $f_1, f_2$ берутся, как линейно независимые столбцы матрицы $A - \mu  E$.
\end{enumerate}

\item Пусть ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{}&{}\\
{}&{\lambda}&{}\\
{}&{}&{\lambda}\\
\end{pmatrix}
\]
В этом случае в качестве жорданова базиса годится любой базис.

\item Пусть ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}&{}\\
{}&{\lambda}&{}\\
{}&{}&{\mu}\\
\end{pmatrix}
\]
В этом случае вектор $f_3$ находится как решение системы $(A - \mu E) x = 0$. Векторы $f_1, f_2$ можно найти одним из следующих способов:
\begin{enumerate}
\item Найдем ФСР системы $(A - \lambda E)^2 x = 0$, пусть это будет $x_1, x_2$. Тогда в качестве $f_2$ берем один из векторов $x_i$, а $f_1 = (A - \lambda E) f_2$. В итоге выбираем такое $x_i$ в качестве $f_2$, чтобы $f_1$ был не ноль.

\item В качестве вектора $f_2$ перебираем столбцы матрицы $A - \mu E$ до тех пор, пока $f_1 = (A - \lambda E) f_2$ не станет ненулевым. Как только $f_1$ будет не ноль, векторы $f_1, f_2$ -- искомые.
\end{enumerate}

\item Пусть ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}&{}\\
{}&{\lambda}&{}\\
{}&{}&{\lambda}\\
\end{pmatrix}
\]
В этом случае жорданов базис имеет конфигурацию
\[
\xymatrix@R=15pt@C=40pt{
  {f_2}\ar@{|->}[d]^{A-\lambda E}&{}\\
  {f_1}\ar@{|->}[d]^{A-\lambda E}&{f_3}\ar@{|->}[d]^{A-\lambda E}\\
  {0}&{0}
}
\]
В этом случае базис ищем по следующему алгоритму
\begin{enumerate}
\item Вектор $f_2$ выбираем случайно из всего пространства $F^3$. Всегда достаточно выбирать из стандартных базисных векторов.

\item Вектор $f_1 = (A - \lambda E) f_2$. Если $f_1 = 0$, то возвращаемся к шагу выбора вектора $f_2$.

\item В случае когда $f_1\neq 0$ это будет вектор из $\ker (A - \lambda E)$, надо дополнить его до базиса ядра. Это можно сделать так: находим ФСР для системы $(A - \lambda E) x = 0$ и дополняем $f_1$ любым вектором из ФСР, который не пропорционален $f_1$, это и будет $f_3$.
\end{enumerate}

\item Пусть ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}&{}\\
{}&{\lambda}&{1}\\
{}&{}&{\lambda}\\
\end{pmatrix}
\]
В этом случае жорданов базис имеет конфигурацию
\[
\xymatrix@R=15pt@C=40pt{
  {f_3}\ar@{|->}[d]^{A-\lambda E}\\
  {f_2}\ar@{|->}[d]^{A-\lambda E}\\
  {f_1}\ar@{|->}[d]^{A-\lambda E}\\
  {0}
}
\]
В этом случае базис ищется по следующему алгоритму
\begin{enumerate}
\item Случайно выбираем $f_3$ из $F^3$. Всегда достаточно выбирать из стандартных базисных векторов.

\item Положим $f_2 = (A - \lambda E) f_3$ и $f_1 = (A - \lambda E) f_2$.

\item Если вектор $f_1$ равен нулю, то возвращаемся к шагу выбора $f_3$ иначе получили нужный базис.
\end{enumerate}

\end{enumerate}

\subsection{Определение ЖНФ у матриц $4$ на $4$ с одним собственным значением}

\paragraph{Дано} Матрица $A\in \Matrix{F}{4}$ с единственным собственным значением $\lambda\in F$, где поле $F$ алгебраически замкнуто.

\paragraph{Найти} Жорданова форма может быть одной из
\[
\begin{pmatrix}
{\lambda}&{}&{}&{}\\
{}&{\lambda}&{}&{}\\
{}&{}&{\lambda}&{}\\
{}&{}&{}&{\lambda}\\
\end{pmatrix}
,\quad
\begin{pmatrix}
{\lambda}&{1}&{}&{}\\
{}&{\lambda}&{}&{}\\
{}&{}&{\lambda}&{}\\
{}&{}&{}&{\lambda}\\
\end{pmatrix}
,\quad
\begin{pmatrix}
{\lambda}&{1}&{}&{}\\
{}&{\lambda}&{}&{}\\
{}&{}&{\lambda}&{1}\\
{}&{}&{}&{\lambda}\\
\end{pmatrix}
,\quad
\begin{pmatrix}
{\lambda}&{1}&{}&{}\\
{}&{\lambda}&{1}&{}\\
{}&{}&{\lambda}&{}\\
{}&{}&{}&{\lambda}\\
\end{pmatrix}
,\quad
\begin{pmatrix}
{\lambda}&{1}&{}&{}\\
{}&{\lambda}&{1}&{}\\
{}&{}&{\lambda}&{1}\\
{}&{}&{}&{\lambda}\\
\end{pmatrix}
\]
Определить какая форма в нашем случае и определить собственное значение.

\paragraph{Алгоритм}
Общая идея в том, чтобы подобрать инварианты, которые достаточно рассчитать для выбора из предоставленных вариантов.
\begin{enumerate}
\item Найдем характеристический многочлен $\chi_A(t) = \det(A - t E)$. Нам нужно найти его единственный корень. Так как многочлен имеет вид $(t-\lambda)^4$, то можно найти его $3$-ю производную и решить $\chi_A(t)^{(3)} = 0$ для нахождения корня. Это работает, если $2\neq 0$ и $3\neq 0$ в поле $F$.\footnote{Действительно, третья производная от  $(t-\lambda)^4$ будет $4! (t - \lambda)$. Если $2$ и $3$ обратимы в $F$, то можно сократить на $4!$.}${}^{,\,}$\footnote{Можно воспользоваться любым другим приемлемым способом по поиску корня многочлена.}

\item Если $A = \lambda E$, то ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{}&{}&{}\\
{}&{\lambda}&{}&{}\\
{}&{}&{\lambda}&{}\\
{}&{}&{}&{\lambda}\\
\end{pmatrix}
\]

\item Если $\rk(A-\lambda E) = 1$, то ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}&{}&{}\\
{}&{\lambda}&{}&{}\\
{}&{}&{\lambda}&{}\\
{}&{}&{}&{\lambda}\\
\end{pmatrix}
\]

\item Если $\rk (A - \lambda E) = 3$, то ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}&{}&{}\\
{}&{\lambda}&{1}&{}\\
{}&{}&{\lambda}&{1}\\
{}&{}&{}&{\lambda}\\
\end{pmatrix}
\]

\item Если $\rk(A - \lambda E) = 2$, то надо посмотреть на $(A - \lambda E)^2$. Если $(A - \lambda E)^2 = 0$, то ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}&{}&{}\\
{}&{\lambda}&{}&{}\\
{}&{}&{\lambda}&{1}\\
{}&{}&{}&{\lambda}\\
\end{pmatrix}
\]
иначе (если $(A - \lambda E)^2 \neq 0$) ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}&{}&{}\\
{}&{\lambda}&{1}&{}\\
{}&{}&{\lambda}&{}\\
{}&{}&{}&{\lambda}\\
\end{pmatrix}
\]
\end{enumerate}

\subsection{Определить Жорданов базис у матриц $4$ на $4$ с единственным собственным значением}

\paragraph{Дано} Матрица $A \in \Matrix{F}{4}$ с единственным собственным значением $\lambda$, где поле $F$ алгебраически замкнутое.

\paragraph{Задача} Зная ЖНФ определить жорданов базис $f_1, f_2, f_3, f_4$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Пусть ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{}&{}&{}\\
{}&{\lambda}&{}&{}\\
{}&{}&{\lambda}&{}\\
{}&{}&{}&{\lambda}\\
\end{pmatrix}
\]
В этом случае любой базис годится в качестве жорданова.

\item Пусть ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}&{}&{}\\
{}&{\lambda}&{}&{}\\
{}&{}&{\lambda}&{}\\
{}&{}&{}&{\lambda}\\
\end{pmatrix}
\]
В этом случае конфигурация жорданова базиса будет следующая
\[
\xymatrix@R=15pt@C=40pt{
  {f_2}\ar@{|->}[d]^{A-\lambda E}&{}&{}\\
  {f_1}\ar@{|->}[d]^{A-\lambda E}&{f_3}\ar@{|->}[d]^{A-\lambda E}&{f_4}\ar@{|->}[d]^{A-\lambda E}\\
  {0}&{0}&{0}
}
\]
В этом случае базис находится по следующему алгоритму
\begin{enumerate}
\item Вектор $f_2$ выбираем случайно из $F^4$. Всегда достаточно выбирать из стандартных базисных векторов.

\item Положим $f_1 = (A - \lambda E) f_2$. Если вектор $f_1 = 0$, то вернемся к шагу выбора вектора $f_2$.

\item Вектор $f_1$ будет лежать в $\ker(A - \lambda E)$ теперь его надо дополнить до базиса ядра двумя векторами. Это можно сделать так: находим ФСР системы $(A - \lambda E)x = 0$ и из трех векторов выберем два $f_3, f_4$, которые будут линейно независимы с $f_1$.
\end{enumerate}

\item Пусть ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}&{}&{}\\
{}&{\lambda}&{1}&{}\\
{}&{}&{\lambda}&{}\\
{}&{}&{}&{\lambda}\\
\end{pmatrix}
\]
В этом случае конфигурация жорданова базиса будет следующая
\[
\xymatrix@R=15pt@C=40pt{
  {f_3}\ar@{|->}[d]^{A-\lambda E}&{}\\
  {f_2}\ar@{|->}[d]^{A-\lambda E}&{}\\
  {f_1}\ar@{|->}[d]^{A-\lambda E}&{f_4}\ar@{|->}[d]^{A-\lambda E}\\
  {0}&{0}
}
\]
В этом случае базис находится по следующему алгоритму
\begin{enumerate}
\item Вектор $f_3$ выбираем случайно в $F^4$. Всегда достаточно выбирать из стандартных базисных векторов.

\item Положим $f_2 = (A - \lambda E) f_3$ и $f_1 = (A - \lambda E) f_2$. Если $f_1 = 0$, то вернуться к шагу выбора вектора $f_3$.

\item Вектор $f_1$ лежит в $\ker (A - \lambda E)$, его надо дополнить одним вектором $f_4$ до базиса ядра. Это можно сделать следующим образом. Найдем ФСР системы $(A - \lambda E)x = 0$ и дополним вектор $f_1$ одним вектором из ФСР, чтобы полученная пара была линейно независима.
\end{enumerate}

\item Пусть ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}&{}&{}\\
{}&{\lambda}&{1}&{}\\
{}&{}&{\lambda}&{1}\\
{}&{}&{}&{\lambda}\\
\end{pmatrix}
\]
В этом случае конфигурация жорданова базиса будет следующая
\[
\xymatrix@R=15pt@C=40pt{
  {f_4}\ar@{|->}[d]^{A-\lambda E}\\
  {f_3}\ar@{|->}[d]^{A-\lambda E}\\
  {f_2}\ar@{|->}[d]^{A-\lambda E}\\
  {f_1}\ar@{|->}[d]^{A-\lambda E}\\
  {0}
}
\]
В этом случае базис находится по следующему алгоритму
\begin{enumerate}
\item Вектор $f_4$ выбираем случайно из $F^4$. Всегда достаточно выбирать из стандартных базисных векторов.

\item Положим $f_3 = (A - \lambda E) f_4$, $f_2 = (A - \lambda E) f_3$, $f_1 = (A - \lambda E) f_2$. Если $f_1 = 0$, то вернуться к шагу перевыбора $f_4$ иначе получился искомый базис.
\end{enumerate}

\item Пусть ЖНФ имеет вид
\[
\begin{pmatrix}
{\lambda}&{1}&{}&{}\\
{}&{\lambda}&{}&{}\\
{}&{}&{\lambda}&{1}\\
{}&{}&{}&{\lambda}\\
\end{pmatrix}
\]
В этом случае конфигурация жорданова базиса будет следующая
\[
\xymatrix@R=15pt@C=40pt{
  {f_2}\ar@{|->}[d]^{A-\lambda E}&{f_4}\ar@{|->}[d]^{A-\lambda E}\\
  {f_1}\ar@{|->}[d]^{A-\lambda E}&{f_3}\ar@{|->}[d]^{A-\lambda E}\\
  {0}&{0}
}
\]
В этом случае базис можно найти по следующему алгоритму.
\begin{enumerate}
\item Выбираем вектор $f_2$ случайно в $F^4$. Всегда достаточно выбирать из стандартных базисных векторов.

\item Положим $f_1 = (A - \lambda E) f_2$. Если $f_1 = 0$, то вернуться к шагу выбора $f_2$.

\item Выбираем вектор $f_4$ случайно в $F^4$. Всегда достаточно выбирать из стандартных базисных векторов.

\item Положим $f_3 = (A - \lambda E) f_4$. Если векторы $f_1,  f_3$ линейно зависимы, вернуться к шагу выбора $f_4$. Иначе получили искомый базис.

\end{enumerate}
\end{enumerate}


\subsection{Найти матрицу билинейной формы при замене базиса}

\paragraph{Дано}
Векторные пространства $V$ и $U$ над полем $F$. Пусть $e=(e_1,\ldots,e_n)$ и $e'=(e'_1,\ldots,e'_n)$ -- базисы пространства $V$, а $f = (f_1,\ldots,f_m)$ и $f' = (f'_1,\ldots,f'_m)$ -- базисы пространства $U$. Кроме того, известны матрицы перехода от $e$ к $e'$ и от $f$ к $f'$, т.е. $(e'_1,\ldots,e'_n) = (e_1,\ldots,e_n)C$ и $(f'_1,\ldots,f'_m) = (f_1,\ldots,f_m)D$, где $C\in \Matrix{F}{n}$ и $D\in \Matrix{F}{m}$ две обратимые матрицы. Дана билинейная форма $\beta\colon V\times U\to F$ заданная в базисах $e$ и $f$ матрицей $B\in\MatrixDim{F}{n}{m}$, т.е. $b_{ij} = \beta(e_i, f_j)$.

\paragraph{Задача} Найти матрицу билинейной формы $\beta$ в базисах $e'$ и $f'$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Пусть в базисах $e'$ и $f'$ мы имеем $\beta (x, y) = x^t B' y$, где $B'$ -- искомая матрица. Тогда $B' = C^t B D$.
\end{enumerate}


\subsection{Найти правое ортогональное дополнение к подпространству}

\paragraph{Дано} Дана билинейная форма $\beta\colon F^n\times F^m \to F$ по правилу $\beta(x,y) = x^t B y$, где $B\in\MatrixDim{F}{n}{m}$ и подпространство $V\subseteq F^n$, заданное образующими $V = \langle v_1,\ldots,v_k\rangle$.

\paragraph{Задача} Найти $V^\bot = \{y\in F^m \mid \beta(V, y) = 0\}$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Составить вектора $v_i$ в столбцы матрицы $D = (v_1|\ldots|v_k) \in \MatrixDim{F}{n}{k}$.

\item Найти ФСР СЛУ $D^tB y = 0$. Данная ФСР дает базис $V^\bot$.
\end{enumerate}

\subsection{Найти левое ортогональное дополнение к подпространству}


\paragraph{Дано} Дана билинейная форма $\beta\colon F^n\times F^m \to F$ по правилу $\beta(x,y) = x^t B y$, где $B\in\MatrixDim{F}{n}{m}$ и подпространство $V\subseteq F^m$, заданное образующими $V = \langle v_1,\ldots,v_k\rangle$.

\paragraph{Задача} Найти ${}^\bot V = \{x\in F^n \mid \beta(x, V) = 0\}$.


\paragraph{Алгоритм}
\begin{enumerate}
\item Составить вектора $v_i$ в столбцы матрицы $D \in \MatrixDim{F}{n}{k}$.

\item Найти ФСР СЛУ $D^tB^t x = 0$. Данная ФСР дает базис ${}^\bot V$.
\end{enumerate}

\subsection{Симметричный Гаусс}

\paragraph{Дано} Симметричная билинейная форма $\beta\colon F^n\times F^n \to F$ по правилу $(x,y)\mapsto x^t B y$, где $B\in \operatorname{M}_n(F)$ -- симметричная матрица и при этом $2\neq 0$  в поле $F$.

\paragraph{Задача} Диагоналзовать $\beta$, то есть найти матрицу перехода к новому базису $C$ такую, чтобы $B' = C^t B C$ была диагональная, и посчитать саму матрицу $B'$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Чтобы найти матрицу $B'$ будем приводить ее к диагональному виду симметричными элементарными преобразованиями, то есть допускаются следующие преобразования:
\begin{itemize}
\item Прибавить $i$-ю строку умноженную на $\lambda$ к $j$-ой строке и сразу же прибавление $i$-го столбца умноженного на $\lambda$ к $j$-ому столбцу.
\item Поменять местами $i$-ю и $j$-ю строку и тут же поменять местами $i$-ый и $j$-ый столбец.
\item Умножить $i$-ю строку на ненулевое $\lambda$ и тут же умножить $i$-ый столбец на то же самое $\lambda$.
\end{itemize}
Получившаяся диагональная матрица будет искомая $B'$.

\item Если при этом надо восстановить матрицу $C$, то рассматриваем $(B|E)$ и делаем симметричные элементарные преобразования над ней в том смысле, что преобразования над строками выполняются над всей матрицей, а преобразования над столбцами только над часть, где лежит $B$. Тогда матрица приведется к виду $(B'|C^t)$.
\end{enumerate}

\subsection{Метод Якоби}

\paragraph{Дано} Симметричная билинейная форма $\beta\colon V\times V \to F$, базис $e_1,\ldots,e_n$ пространства $V$, такой, что $\det \beta|_{\langle e_1,\ldots,e_k\rangle}\neq 0$.

\paragraph{Задача} Найти базис $e_1',\ldots,e_n'$ такой, что $e_i' - e_i\in \langle e_1,\ldots,e_{i-1}\rangle = \langle e_1',\ldots,e_{i-1}'\rangle$ такой, что $\beta(e_i',e_j') = 0$ при $i \neq j$.


\paragraph{Алгоритм}
\begin{enumerate}
\item В начале положим $e_1' = e_1$.

\item Пусть мы нашли вектора $e_1',\ldots,e_{i - 1}'$.  Тогда положим вектор $e_i' $ в виде\footnote{В силу условия $\det \beta|_{\langle e_1,\ldots,e_k\rangle}\neq 0$ выражения вида $\beta(e_k',e_k')$ будут всегда отличны от нуля.}
\[
e_i' = e_i - \frac{\beta(e_i, e_1')}{\beta(e_1',e_1')} e_1' - \ldots - \frac{\beta(e_i, e_{i-1}')}{\beta(e_{i-1}', e_{i-1}')}e_{i-1}'
\]
\end{enumerate}

\subsection{Алгоритм диагонализации на основе метода Якоби}

\paragraph{Дано} Симметрическая матрица $B\in \operatorname{M}_n(F)$.

\paragraph{Задача} Проверить, что все ее угловые подматрицы $B_k$ невырождены и если это так, то найти их значения, а также найти верхнетреугольную матрицу с единицами на диагонали $C\in \operatorname{M}_n(F)$ и диагональную матрицу $D\in\operatorname{M}_n(F)$ такие, что $B = C^t D C$.

\paragraph{Алгоритм}
\begin{enumerate}
\item Начнем приводить матрицу $B$ к верхнетреугольному виду элементарными преобразованиями первого типа, когда нам разрешено прибавлять строку с коэффициентом только к более низкой строке. Возможны два исхода:
\begin{itemize}
\item На каком-то этапе получили, что на диагонали на $k$-ом месте стоит $0$, а под диагональю есть ненулевой элемент. Это значит, что $\Delta_k = 0$. Условие на матрицу не выполнено.

\item Мы привели матрицу $B$ к верхнетреугольной матрице $U$. Переходим к следующему шагу.
\end{itemize}

\item Восстановим все необходимые данные по матрице $U$ следующим образом:
\begin{enumerate}
\item $D$ -- диагональ матрицы $U$.

\item $C =  D^{-1}U$.

\item $\Delta_k$ -- произведение первых $k$ элементов диагонали матрицы $D$.
\end{enumerate}

\end{enumerate}


\subsection{Алгоритм диагонализации унитарного оператора}

\paragraph{Дано} Унитарная матрица $A\in \Matrix{\mathbb C}{n}$.

\paragraph{Задача} Найти разложение вида $A = U D U^*$, где $U = (u_1|\ldots|u_n)\in \Matrix{\mathbb C}{n}$ -- унитарная матрица и $D\in \Matrix{\mathbb C}{n}$ -- диагональная матрица с числами равными по модулю $1$.

\paragraph{Алгоритм} 
\begin{enumerate}
\item Найти характеристический многочлен $\chi_A(t)$. Пусть $\lambda_1,\ldots, \lambda_k$ -- его корни с кратностями $n_1,\ldots,n_k$.\footnote{Должно получиться, что $|\lambda_i| = 1$ для всех $i$.}

\item Для каждого $\lambda_i$ найдем ортонормированный базис собственного подпространства:
\begin{enumerate}
\item найдем базисные собственные векторы, решив систему $(A - \lambda_iE)x = 0$ в $\mathbb C^n$.

\item К полученным векторам применить применим алгоритм Грама-Шмидта используя стандартное скалярное произведение $(x, y) = \bar x^t y$.

\item Нормируем каждый вектор, поделив на его длину.
\end{enumerate}

\item Тогда матрица $D$ будет $\diag(\lambda_1,\ldots,\lambda_1,\lambda_2,\ldots,\lambda_2,\ldots,\lambda_k,\ldots,\lambda_k)$, где каждое $\lambda_i$ встречается $n_i$ раз.

\item Матрица $U$ будет составлена из базисных векторов собственных подпространств. Сначала идут $n_1$ векторов для $\lambda_1$, потом $n_2$ для $\lambda_2$ и т.д.
\end{enumerate}

\subsection{Алгоритм приведения произвольного ортогонального оператора к каноническому виду}

\paragraph{Дано} Ортогональная матрица $A\in \Matrix{\mathbb R}{n}$.

\paragraph{Задача} Найти разложение $A = U D U^t$, где $U = (u_1|\ldots|u_n)\in \Matrix{\mathbb R}{n}$ -- ортогональная матрица и $D$ -- блочно диагональная матрица, где на диагонали стоят:
\[
1,\quad -1,\quad
\begin{pmatrix}
{\cos \alpha}&{-\sin\alpha}\\
{\sin \alpha}&{\cos \alpha}
\end{pmatrix}
\]

\paragraph{Алгоритм}
\begin{enumerate}
\item Найти характеристический многочлен $\chi_A(t)$. Пусть кратность корня $1$ равна $n_1$, кратность корня $-1$ равна $n_{-1}$. Остальные комплексные корни имеют вид $\lambda_1,\ldots,\lambda_k$ и $\bar\lambda_1,\ldots,\bar\lambda_k$, при этом кратности их будут $m_1,\ldots,m_k$ (и у сопряженных такие же).\footnote{Таким образом имеем $n = n_1 + n_{-1} + 2 m_1 + \ldots + 2 m_k$.}

\item Надо найти ортонормированные базисы для блоков.
\begin{enumerate}
\item Блоки $1$ и $-1$. Опишем процесс для $1$.
\begin{enumerate}
\item Найдем базисные собственные векторы, решив систему $(A- E)x = 0$.
\item Применим Грама-Шмидта для стандартного скалярного произведения $(x, y) = x^ty$ к базису собственных векторов.
\item Нормируем базисные векторы, поделив на их длину.
\end{enumerate}

\item Блоки размера $2$.
\begin{enumerate}
\item За каждый такой блок отвечает пара комплексно сопряженных корней. Возьмем $\lambda_i = \cos \alpha_i + i \sin\alpha_i$.

\item Найдем комплексные базисные собственные векторы для $\bar \lambda_i$,\footnote{Причина почему я беру именно $\bar\lambda_i$ связана с тем, где я хочу получить минус в блоке.} решив систему $(A - \bar\lambda_iE)x = 0$.

\item Применим к базисным векторам Грама-Шмидта для стандартного скалярного произведения $(x, y) = \bar x^ty$.

\item Пусть получилась последовательность $w_1,\ldots,w_{m_i}$. Каждый их этих векторов имеет вид $w_s = u_s + i v_s$, при этом мы знаем, что $|u_s| = |v_s|$ и $u_s\perp v_s$.

\item Заменим каждый $w_i$ на пару векторов $u_i/|u_i|, v_i/|v_i|$. Тогда набор этих пар будет ортонормированным базисом отвечающим набору блоков вида\footnote{Если бы мы решали систему для $\lambda_i$, то минус был бы в левом нижнем углу.}
\[
\begin{pmatrix}
{\cos \alpha_i}&{-\sin\alpha_i}\\
{\sin \alpha_i}&{\cos \alpha_i}
\end{pmatrix}
\]
\end{enumerate}
\end{enumerate}
\item Теперь в качестве матрицы $D$ выберем матрицу такую, что она блочно диагональная. В начале идут $1$ в количестве $n_1$, потом $-1$ в количестве $n_{-1}$. Потом идут блоки $2$ на $2$ вида
\[
\begin{pmatrix}
{\cos \alpha_i}&{-\sin\alpha_i}\\
{\sin \alpha_i}&{\cos \alpha_i}
\end{pmatrix}
\]
которые повторяются $m_i$ раз.

\item В качестве $U$ надо выбрать матрицу из построенных базисных векторов. Сначала $n_1$ векторов для $1$, потом $n_{-1}$ векторов для $-1$. А потом векторы соответствующие блокам $2$ на $2$. Сначала $2m_1$ пар полученных из $\lambda_1$, потом $2m_2$ пар полученных из $\lambda_2$ и т.д.
\end{enumerate}

\subsection{Алгоритм приведения ортогонального оператора $\mathbb R^3$ к каноническому виду}

\paragraph{Дано} Ортогональная матрица $A\in\Matrix{\mathbb R}{3}$.

\paragraph{Задача} Найти разложение $A = U D U^t$, где $U=(u_1|u_2|u_3)\in\Matrix{\mathbb R}{3}$ -- ортогональная матрица и $D$ одна из следующих матриц\footnote{Прямая натянутая на вектор $u_1$ называется осью для $A$.}
\[
(I)\quad D =
\begin{pmatrix}
{1}&{}&{}\\
{}&{\cos \alpha}&{-\sin\alpha}\\
{}&{\sin\alpha}&{\cos\alpha}\\
\end{pmatrix}
\quad\text{или}\quad
(II)\quad D =
\begin{pmatrix}
{-1}&{}&{}\\
{}&{\cos \alpha}&{-\sin\alpha}\\
{}&{\sin\alpha}&{\cos\alpha}\\
\end{pmatrix}
\]

\paragraph{Алгоритм}
\begin{enumerate}
\item Ищем матрицу $U$. Начинаем с поиска образующего оси. Решаем систему $(A - E)x = 0$. Возможны следующие случаи:
\begin{enumerate}
\item ФСР пустое.

Это значит, что у нас случай (II) и ось надо искать из уравнения $(A+E)x = 0$. Приведем матрицу $A+E$ к улучшенному ступенчатому виду $(v_1|v_2)^t$. Тогда ее ФСР будет из одного вектора, нормируем его и обозначим за $u_1$ -- это образующий оси. Векторы $v_1, v_2$ образуют базис $\langle u_1\rangle^\bot$. Ортогонализуем и нормируем векторы $v_1,v_2$. Полученные векторы будут $u_2$ и $u_3$.

\item ФСР из одного вектора $u$. Нормируем его и обозначим через $u_1$.

Это значит, что у нас случай (I) и вектор $u_1$ -- образующий оси. Когда мы решали $(A-E)x = 0$ мы привели матрицу $A-E$ к улучшенному ступенчатому виду $(v_1|v_2)^t$. Тогда $v_1,v_2$ -- базис  $\langle u_1\rangle^\bot$. Ортогонализуем $v_1,v_2$ и потом нормируем. Полученные векторы будут $u_2$ и $u_3$.

\item ФСР из двух векторов $v_1$ и $v_2$.

Это значит, что у нас случай (II). Пусть $v$ -- любая ненулевая строка матрицы $A-E$, тогда нормируем $v$ и обозначим получившийся вектор $u_1$ -- это будет образующий оси. Ортогонализуем и нормируем векторы $v_1$ и $v_2$. Полученные векторы будут $u_2$ и $u_3$.

\item ФСР из трех векторов. 

Это значит, что у нас случай (I). Такое возможно только если $A = E$. В этом случае $U= E$, $\alpha = 0$. 
\end{enumerate}

\item Теперь найдем $\cos \alpha$. Возможны два случая.
\begin{enumerate}
\item Случай (I). Тогда $\tr A = 1 + 2 \cos \alpha$.
\item Случай (II). Тогда $\tr A = -1 + 2 \cos \alpha$.
\end{enumerate}

\item Теперь найдем $\sin \alpha$. Для этого заметим, что $(Au_2, u_3) = \sin \alpha$.

\end{enumerate}

\subsection{Алгоритм разложения симметрических матриц}


\paragraph{Дано} Матрица $A\in\Matrix{\mathbb R}{n}$ такая, что $A^t = A$.

\paragraph{Задача} Найти разложение $A = C \Lambda C^t$, где $C\in\Matrix{\mathbb R}{n}$ -- ортогональная матрица, $\Lambda\in\Matrix{\mathbb R}{n}$ -- диагональная матрица.

\paragraph{Алгоритм}
\begin{enumerate}
\item Найти собственные значения матрицы $A$. 
\begin{enumerate}
\item Составить характеристический многочлен $\chi(\lambda) = \det(A-\lambda E)$.
\item Найти корни $\chi(\lambda)$ с учетом кратностей: $\{(\lambda_1, n_1),\ldots,(\lambda_k, n_k)\}$, где $\lambda_i$ -- корни, $n_i$ -- кратности.
\end{enumerate}

\item Для каждого $\lambda_i$ найти ортонормированный базис в пространстве собственных векторов отвечающему $\lambda_i$.
\begin{enumerate}
\item Найти ФСР системы $(A-\lambda_i E)x = 0$. Пусть это будет $v^i_1,\ldots,v^i_{n_i}$. Обратите внимание, что их количество будет в точности равно кратности $n_i$.

\item Ортогонализовать $v^i_1,\ldots,v^i_{n_i}$ методом Грама-Шмидта. Обратите внимание, после ортогонализации останется ровно $n_i$ векторов.

\item Сделать каждый вектор длинны один: $v^i_j\mapsto \frac{v^i_j}{|v^i_j|}$.
\end{enumerate}

\item Матрица $\Lambda$ будет диагональной с числами $\lambda_1,\ldots,\lambda_1,\lambda_2,\ldots,\lambda_2,\ldots,\lambda_k,\ldots,\lambda_k$ на диагонали, где каждое $\lambda_i$ повторяется $n_i$ раз. Обратите внимание, всего получится $n$ чисел.

\item Матрица $C$ будет составлена из столбцов $v^1_1,\ldots,v^1_{n_1}, v^2_1,\ldots,v^2_{n_2},\ldots,v^k_1,\ldots,v^k_{n_k}$. Обратите внимание, порядок собственных векторов соответствует порядку собственных значений в матрице $\Lambda$.
\end{enumerate}


\subsection{Алгоритм нахождения сингулярного разложения}

\paragraph{Дано} Матрица $A \in \MatrixDim{\mathbb R}{m}{n}$.\footnote{Этот алгоритм рекомендуется применять при $m\leqslant n$, в противном случае, применить его к матрице $A^t$, а потом транспонировать полученное разложение.}

\paragraph{Задача} Найти разложение $A = U \Lambda V^t$, где $U\in\Matrix{\mathbb R}{m}$ ортогональная, $V\in\Matrix{\mathbb R}{n}$ ортогональная, $\Lambda \in\MatrixDim{\mathbb R}{m}{n}$ содержит на диагонали элементы $\sigma_1\geqslant\ldots\geqslant \sigma_s>0$, а все остальные нули.

\paragraph{Алгоритм}
\begin{enumerate}
\item Составим матрицу $S = A A^t\in\Matrix{\mathbb R}{m}$. Тогда $S = U \Lambda\Lambda^t U^t$. 

\item Так как $S^t = S$. То с помощью алгоритма для симметрических матриц найдем ее разложение $S = C D C^t$. Причем, обязательно получится, что диагональная матрица $D=\diag(\lambda_1,\ldots,\lambda_m)$ состоит из неотрицательных элементов.

\item Тогда $U = C$, а $\Lambda\Lambda^t = D$. То есть $\sigma_i^2 = \lambda_i$. Так как $\sigma_i \geqslant 0$, то они находятся как $\sigma_i = \sqrt{ \lambda_i}$.

\item Теперь надо найти $V$ из условия $A = U\Lambda V^t$.\footnote{Обратите внимание $\Lambda$ не обязательно квадратная и тем более не обязательно обратимая.} Пусть $\sigma_1\geqslant \ldots \geqslant \sigma_s > 0$. Положим $U=(u_1|\ldots|u_m)$ и $V = (v_1|\ldots|v_n)$. Тогда $A^t U = V\Lambda^t $, то есть $v_i = \frac{1}{\sigma_i}A^t u_i$ при $1\leqslant i\leqslant s$.

\item Теперь найдем оставшиеся $v_{s+1},\ldots,v_n$. Для этого дополним $v_1,\ldots,v_s$ до базиса $\mathbb R^{n}$ и ортонормируем полученное семейство.\footnote{Можно заметить, что $v_{s+1},\ldots,v_n$ будут базисом ядра $A$, потому можно найти ФСР для $\{y\in\mathbb R^{n}\mid Ay = 0\}$ и ортонормировать его.}

\end{enumerate}


\subsection{Алгоритм нахождения компактного сингулярного разложения}

\paragraph{Дано} Матрица $A \in \MatrixDim{\mathbb R}{m}{n}$.\footnote{Этот алгоритм рекомендуется применять при $m\leqslant n$, в противном случае, применить его к матрице $A^t$, а потом транспонировать полученное разложение.}

\paragraph{Задача} Найти разложение $A = U \Sigma V^t$, где $U\in\MatrixDim{\mathbb R}{m}{s}$, $V\in\MatrixDim{\mathbb R}{n}{s}$ -- матрицы с ортонормированными столбцами, $\Sigma \in\Matrix{\mathbb R}{s}$ -- диагональная матрица с элементами $\sigma_1\geqslant\ldots\geqslant \sigma_s>0$ на диагонали.

\paragraph{Алгоритм}
\begin{enumerate}
\item Составим матрицу $S = A A^t\in\Matrix{\mathbb R}{m}$. Тогда $S = U \Sigma^2 U^t$. 

\item Так как $S^t = S$. То с помощью алгоритма для симметрических матриц найдем ее разложение $S = C D C^t$.\footnote{Здесь $D$ будет диагональной матрицей, а $C$ ортогональной.} Причем, обязательно получится, что диагональная матрица $D=\diag(\lambda_1,\ldots,\lambda_m)$ состоит из неотрицательных элементов и мы можем выбрать порядок так, чтобы $\lambda_1 \geqslant \lambda_2\geqslant\ldots \geqslant \lambda_m\geqslant 0$.

\item Пусть $C = (C_1|\ldots|C_m)$, тогда положим $U = (C_1|\ldots|C_s)\in\MatrixDim{\mathbb R}{m}{s}$. А матрица $\Sigma\in \Matrix{\mathbb R}{s}$ будет диагональной с числами $\sigma_i = \sqrt{\lambda_i}$ на диагонали, то есть $\Sigma = \diag(\sigma_1,\ldots,\sigma_s)$.

\item Теперь надо найти $V$ из условия $A = U\Sigma V^t$.\footnote{Обратите внимание, что $\Sigma$ квадратная и обратимая матрица.} Положим $U=(u_1|\ldots|u_s)$ и $V = (v_1|\ldots|v_s)$. Тогда $A^t U \Sigma^{-t} = V$, то есть $v_i = \frac{1}{\sigma_i}A^t u_i$ при $1\leqslant i\leqslant s$.

\end{enumerate}



\end{document}