\section{Линейные отображения}

\subsection{Первые определения}

\literature{[F], гл. XII, \S~4, п. 1.; [K2], гл. 2, \S~1, п. 1; [KM],
  ч. 1, \S~3, пп. 1, 2; [vdW], гл. IV, \S~23.}

\begin{definition}
Пусть $V$, $W$~--- векторные пространства над полем $k$.
Отображение $T\colon V\to W$ называется \dfn{линейным},
если
\begin{itemize}
\item $T(u+v)=T(u) + T(v)$;
\item $T(va) = T(v)a$ для всех $a\in k$, $v\in V$.
\end{itemize}
Иногда вместо $T(v)$ мы будем писать $Tv$.
Множество всех линейных отображений из $V$ в $W$ мы будем
обозначать через $\Hom(V,W)$.
Линейное отображение часто называется
\dfn{гомоморфизмом}\index{гомоморфизм!векторных пространств} векторных
пространств; оно называется
\dfn{эндоморфизмом}\index{эндоморфизм!векторных пространств}, если $U=V$.
\end{definition}

\begin{example}
Обозначим через $0$ отображение, которое любой вектор $v\in V$
переводит в $0\in W$; то есть, $0(v)=0$ для всех $v\in V$.
Нетрудно видеть, что оно линейно, то есть,
$0\in\Hom(V,W)$. Обратите внимание, что мы используем тот же
символ $0$, что и для обозначения нулевого элемента поля $k$
и нулевых элементов в векторных пространствах $V$ и $W$.
\end{example}
\begin{example}
Для каждого векторного пространства $V$ можно рассмотреть
тождественное отображение $\id_V\colon V\to V$.
Нетрудно проверить, что он линейно; таким образом,
$\id_V\in\Hom(V,W)$.
\end{example}
\begin{example}\label{example:linear-derivative}
Для пространства многочленов $k[x]$ можно рассмотреть отображение
{\em дифференцирования} $T\colon k[x]\to k[x]$, сопоставляющее каждому
многочлену $f\in k[x]$ его производную $f'$. Это отображение линейно,
поскольку $(f+g)' = f' + g'$ и $(fa)' = f'a$ для всех
$f,g\in k[x]$ и $a\in k$ (см.
предложение~\ref{prop:derivative-properties}).
\end{example}
\begin{example}\label{example:linear-timesx}
Отображение $k[x]\to k[x]$, умножающее каждый многочлен на $x$,
является линейным.
\end{example}
\begin{example}
Снова рассмотрим пространство многочленов $k[x]$, и пусть
$c\in k$~--- фиксированный элемент основного поля.
Рассмотрим отображение $\ev_c\colon k[x]\to k$, сопоставляющее
каждому многочлену $f\in k[x]$ его значение в точке $c$.
Иными словами, $\ev_c(f) = f(c)$.
Это отображение линейно (см. предложение~\ref{prop:evaluation-properties});
оно называется \dfn{эвалюацией в точке $c$}.
\end{example}
\begin{example}
Пусть $k=\mb R$; рассмотрим отображение $T\colon \mb R[x]\to\mb R$,
сопоставляющее многочлену $f\in\mb R[x]$ значение интеграла
$$
T(f) = \int_0^1 f(x)\;dx.
$$
Из простейших свойств определенного интеграла следует, что
отображение $T$ линейно.
\end{example}
\begin{example}
Рассмотрим пространство бесконечных последовательностей ${}^\infty k$.
Отображение $T\colon {}^\infty k\to {}^\infty k$, сопоставляющее
последовательности $(x_1,x_2,\dots)$ последовательность
$(x_2,x_3,\dots)$ ({\em сдвиг влево}) является линейным.
\end{example}

Пусть $T\colon V\to W$~--- линейное отображение, и пусть
$v_1,\dots,v_n$~--- базис пространства $V$.
Если $v\in V$, то можно записать $v = v_1a_1 + \dots + v_na_n$
для некоторых $a_1,\dots,a_n\in k$. Тогда
из определения линейности следует, что
$T(v) = T(v_1)a_1 + \dots + T(v_n)a_n$.
Это означает, что значение $T$ на любом векторе $v$ полностью
определяется своими значениями на базисе. Обратно, можно задать
значения $T(v_1),\dots, T(v_n)\in W$ {\em произвольным} образом,
и по этим данным однозначно восстанавливается единственное
линейное отображение из $V$ в $W$.
\begin{theorem}[Универсальное свойство базиса]\label{thm:universal-basis-property}
Пусть $V,W$~--- конечномерные векторные пространства,
$v_1,\dots,v_n$~--- базис $V$, и пусть заданы произвольные
векторы $w_1,\dots,w_n\in W$.
Существует единственное линейное отображение $T\colon V\to W$
такое, что $T(v_i) = w_i$ для всех $i=1,\dots,n$.
\end{theorem}
\begin{proof}
Возьмем вектор $v\in V$ и разложим его базису $v_1,\dots,v_n$:
$v = v_1a_1 + \dots + v_na_n$.
Если $T(v_i) = w_i$ для $i=1,\dots,n$, то
\begin{align*}
T(v) &= T(v_1a_1+\dots+v_na_n) \\
&= T(v_1)a_1+\dots+T(v_n)a_n \\
&= w_1a_1 + \dots + w_na_n.
\end{align*}
Таким образом, значение $T$ на $v$ однозначно определено
(поскольку коэффициенты $a_1,\dots,a_n$ однозначно определяются
вектором $v$, см. теорему~\ref{thm:basis-equiv}).
Это рассуждение работает для произвольного вектора $v\in V$,
поэтому линейное отображение $T$, удовлетворяющее условиям
$T(v_i) = w_i$, единственно.

Обратно, если нам дан базис $\{v_i\}$ в $V$ и
векторы $\{w_i\}$, то для произвольного вектора
$v = v_1a_1 + \dots + v_na_n$ положим
$T(v) = w_1a_1 + \dots + w_na_n$ (это выражение определено
однозначно по теореме~\ref{thm:basis-equiv}).
Мы получили отображение $T\colon V\to W$; осталось доказать, что
оно линейно. Действительно, пусть $u,v\in V$,
причем $v = v_1a_1+\dots+v_na_n$ и $u=v_1b_1+\dots+v_nb_n$.
Тогда по нашему определению
$T(v) = w_1a_1 + \dots + w_na_n$,
$T(u) = w_1b_1 + \dots + w_nb_n$.
Сложение выражений для $u$ и $v$ показывает, что
$u+v = v_1(a_1+b_1) + \dots + v_n(a_n+b_n)$, и по определению
$T$ тогда $T(u+v) = w_1(a_1+b_1) + \dots + w_n(a_n+b_n)$.
Нетрудно видеть теперь, что $T(u+v) = T(u) + T(v)$.
Если, кроме того, $a\in k$,
то $va = v_1a_1a + \dots + v_na_na$, и потому
$T(va) = w_1a_1a + \dots + w_na_na$. Легко проверить,
что $T(va) = T(v)a$.
\end{proof}

\subsection{Операции над линейными отображениями}\label{subsect:hom_space}

\literature{[F], гл. XII, \S~4, пп. 4--6; [K2], гл. 2, \S~1, п. 1;
  \S~2, пп. 1--2; [KM], ч. 1, \S~3; [vdW], гл. IV, \S~23.}


Пусть $V,W$~--- векторные пространства над $k$. Оказывается,
множество $\Hom(V,W)$ всех линейных отображений из $V$ в $W$
естественным образом снабжается структурой векторного
пространства над $k$.
Чтобы продемонстрировать это, мы должны определить на нем
две операции: сложение и умножение на скаляр.
Пусть $S,T\colon V\to W$~--- линейные отображения.
Определим новое отображение $S+T\colon V\to W$
формулой $(S+T)(v) = S(v) + T(v)$ для всех $v\in V$.
Нетрудно проверить, что отображение $S+T$ линейно.
Поэтому для $S,T\in\Hom(V,W)$ мы построили их сумму
$S+T\in\Hom(V,W)$.
Если же $S\colon V\to W$~--- линейное отображение, и $a\in k$,
можно определить отображение $Sa\colon V\to W$ формулой
$(Sa)(v) = S(v)a$. Это отображение также линейно, то есть,
$Sa\in\Hom(V,W)$.

Теперь можно проверить, что введенные операции действительно
превращают $\Hom(V,W)$ в векторное пространство.
Роль нулевого элемента в нем играет нулевое отображение
$0\colon\Hom(V,W)$. Для примера проверим одно условие из
определения векторного пространства:
пусть $S,T\in\Hom(V,W)$, $a\in k$.
Тогда для всех $v\in V$ выполнены равенства
\begin{align*}
((S+T)a)(v) &= ((S+T)(v))\cdot a \\
&= (S(v)+T(v))a \\
&= (S(v)a) + (T(v)a) \\
&= (Sa)(v) + (Ta)(v) \\
&= (Sa+Ta)(v)
\end{align*}
Поэтому отображения $(S+T)a$, $Sa+Ta$ из $V$ в $W$ совпадают.

% 23.03.2015

Более того, некоторые линейные отображения можно <<перемножать>>.
Пусть $U,V,W$~--- векторные пространства над $k$.
Возьмем линейные отображения $T\in\Hom(U,V)$ и
$S\in\Hom(V,W)$. Тогда имеет смысл рассматривать их композицию
$S\circ T\colon U\to W$. Оказывается, отображение $S\circ T$
также является линейным. Действительно, напомним, что
$(S\circ T)(u) = S(T(u))$ для всех $u\in U$ по определению
композиции.
Поэтому
\begin{align*}
(S\circ T)(u_1+u_2) &= S(T(u_1+u_2)) \\
&= S(T(u_1)+T(u_2)) \\
&= S(T(u_1))+S(T(u_2)) \\
&= (S\circ T)(u_1) + (S\circ T)(u_2)
\end{align*}
для всех $u_1,u_2\in U$. Если же $u\in U$, $a\in k$, то
$$
(S\circ T)(ua) = S(T(ua)) = S(T(u)a) = S(T(u))a
= (S\circ T)(u)a.
$$
Значит, $S\circ T\in\Hom(U,W)$.
Вместо $S\circ T$ мы будем часто писать $ST$ и воспринимать
$ST$ как {\em произведение} линейных отображений $S$ и $T$.

Заметим, что композиция линейных отображений автоматически
ассоциативна (по теореме~\ref{thm_composition_associative}),
то есть, $R(ST) = (RS)T$ для трех линейных отображений таких,
что указанные композиции имеют смысл.
Тождественные отображения линейны и играют роль нейтральных
элементов: $T\id_V = \id_W T$ для $T\in\Hom(V,W)$.
Наконец, несложно проверить (упражнение!), что
умножение и сложение линейных отображений обладают свойством
дистрибутивности: если $T,T_1,T_2\in\Hom(U,V)$
и $S,S_1,S_2\in\Hom(V,W)$
то $(S_1+S_2)T = S_1T + S_2T$ и $S(T_1+T_2) = ST_1 + ST_2$.

Конечно, произведение линейных отображений некоммутативно:
равенство $ST=TS$ не обязано выполняться, даже если обе его
части имеют смысл. Например, если $T\in\Hom(k[x],k[x])$~---
отображение дифференцирования многочленов
(см. пример~\ref{example:linear-derivative}),
а $S\in\Hom(k[x],k[x])$~--- умножение на $x$
(см. пример~\ref{example:linear-timesx}),
то $((ST)(f))(x) = xf'(x)$,
а $((TS)(f))(x) = (xf(x))' = xf'(x) + f(x)$.
Таким образом, $ST-TS = \id_{k[x]}$.

\subsection{Ядро и образ}

\literature{[F], гл. XII, \S~4, п. 1; [K2], гл. 2, \S~1, пп. 1, 3;
  [KM], ч. 1, \S~3.}

\begin{definition}
Пусть $T\in\Hom(V,W)$~--- линейное отображение. Его
\dfn{ядром} называется множество векторов, переходящих
в $0$ под действием $T$:
$$
\Ker(T) = \{v\in V\mid T(v) = 0\}.
$$
\end{definition}

\begin{example}
Если $T\in\Hom(k[x],k[x])$~--- дифференцирование
(см. пример~\ref{example:linear-derivative}), то
$\Ker(T) = \{f\in k[x] \mid f'=0\}$. Если поле $k$
имеет характеристику $0$, то $\Ker(T)$ состоит только из
констант, то есть, $\Ker(T) = k\subseteq k[x]$~--- одномерное
подпространство в $k[x]$. Если же
$\cchar k = p$, то существуют и неконстантные многочлены
$f\in k[x]$
такие, что $f'=0$. Например, таков многочлен $x^p$,
а потому и любой многочлен от $x^p$: действительно,
обозначим $g(x) = x^p$, тогда
$(f(g(x)))' = f'(g(x))\cdot g'(x) = 0$.
Можно показать (упражнение!),
что $\Ker(T)$ в этом случае в точности состоит
из многочленов от $x^p$, то есть, от многочленов вида
$\sum_{j=0}^n a_j x^{jp}$. Таким образом,
$\Ker(T) = k[x^p]$ в этом случае бесконечномерно.
\end{example}
\begin{example}
Пусть $T\in\Hom(k[x],k[x])$~--- умножение на $x$
(см. пример~\ref{example:linear-timesx}).
Тогда $\Ker(T) = 0$.
\end{example}

\begin{proposition}\label{prop:kernel-is-subspace}
Если $T\in\Hom(V,W)$, то $\Ker(T)$ является подпространством
в $V$.
\end{proposition}
\begin{proof}
Заметим, что $T(0) = T(0+0) = T(0)+T(0)$, откуда
$T(0)=0$. Значит, $0\in\Ker(T)$.
Если $u,v\in\Ker(T)$, то по определению $T(u)=T(v)=0$.
Тогда и $T(u+v) = T(u)+T(v) = 0+0=0$, то есть, $u+v\in\Ker(T)$.
Наконец, если $u\in\Ker(T)$ и $a\in k$, то
$T(u)=0$ и $T(ua)=T(u)a=0\cdot a = 0$, откуда $ua\in\Ker(T)$.
Вышесказанное означает, что $\Ker(T)\leq V$.
\end{proof}
\begin{proposition}\label{prop:injective-iff-kernel-trivial}
Пусть $T\in\Hom(V,W)$. Отображение $T$ инъективно тогда и только
тогда, когда $\Ker(T) = 0$.
\end{proposition}
\begin{proof}
Предположим, что $T$ инъективно. Множество $\Ker(T)$ состоит из
тех векторов $v$, для которых $T(v) = 0$. Мы знаем, что
$T(0)=0$ и из инъективности следует, что других таких векторов
нет; поэтому $\Ker(T) = \{0\}$.

Обратно, предположим, что $\Ker(T)=0$. Для проверки инъективности
возьмем $v_1,v_2\in V$ такие, что $T(v_1)=T(v_2)$ и покажем,
что $v_1=v_2$. Действительно, тогда $T(v_1-v_2) =
T(v_1)-T(v_2) = 0$, и потому $v_1-v_2\in\Ker(T) = \{0\}$,
откуда $v_1-v_2=0$, что и требовалось.
\end{proof}

\begin{definition}
Пусть $T\in\Hom(V,W)$. Его \dfn{образом} называется его
образ как обычного отображения, то есть, множество
$$
\Img(T) = \{T(v)\mid v\in V\}.
$$
\end{definition}

\begin{proposition}\label{prop:image-is-subspace}
Если $T\in\Hom(V,W)$, то $\Img(T)$ является подпространством
в $W$.
\end{proposition}
\begin{proof}
Из равенства $T(0)=0$ следует, что $0\in\Img(T)$.
Если $w_1,w_2\in\Img(T)$, то найдутся $v_1,v_2\in V$ такие, что
$T(v_1)=w_1$ и $T(v_2)=w_2$. Но тогда
$T(v_1+v_2) = T(v_1) + T(v_2) = w_1 + w_2$, и потому
$w_1 + w_2 \in \Img(T)$.
Если $w\in\Img(T)$, то $T(v)=w$ для некоторого $v\in V$.
Пусть $a\in k$; тогда $T(va) = T(v)a = wa$, и потому
$wa\in\Img(T)$. По определению тогда $\Img(T)\leq W$.
\end{proof}

\begin{theorem}[О гомоморфизме]\label{thm:homomorphism-linear}
Пусть $V$~--- конечномерное пространство, $T\in\Hom(V,W)$~---
линейное отображение. Тогда $\Img(T)$ является конечномерным
подпространством в $W$ и, кроме того,
$$
\dim(V) = \dim(\Ker(T)) + \dim(\Img(T)).
$$
\end{theorem}
\begin{proof}
Пусть $u_1,\dots,u_m$~--- базис $\Ker(T)$. Этот линейно
независимый набор векторов можно продолжить до базиса
$(u_1,\dots,u_m,v_1,\dots,v_n)$ всего пространства $V$
по теореме~\ref{thm:li-contained-in-a-basis}.
Таким образом, $\dim(\Ker(T)) = m$ и $\dim(V) = m+n$;
нам остается лишь доказать, что $\dim(\Img(T)) = n$.
Для этого рассмотрим векторы $T(v_1),\dots,T(v_n)$ и покажем,
что они образуют базис подпространства $\Img(T)$. Очевидно,
что они лежат в $\Img(T)$, и потому
$\la T(v_1),\dots,T(v_n)\ra\subseteq\Img(T)$. Обратно, если
$w\in\Img(T)$, то $w=T(v)$ для некоторого $v\in V$.
Разложим $v$ по нашем базису пространства $V$:
$$
v = u_1a_1+\dots+u_ma_m + v_1b_1+\dots+v_nb_n
$$
и применим к этому разложению отображение $T$:
$$
w = T(v) = T(u_1a_1+\dots+u_ma_m + v_1b_1 + \dots + v_nb_n)
= T(v_1)b_1 + \dots + T(v_n)b_n.
$$
Поэтому $w\in \la T(v_1),\dots,T(v_n)\ra$.
Осталось показать, что векторы $T(v_1),\dots,T(v_n)$
линейно независимы. Пусть
$T(v_1)c_1 + \dots + T(v_n)c_n = 0$~--- некоторая линейная комбинация.
Тогда $0=T(v_1c_1+\dots+v_nc_n)$. Это означает, что
вектор $v_1c_1+\dots+v_nc_n$ лежит в $\Ker(T)$.
Мы знаем базис $\Ker(T)$,потому
$v_1c_1+\dots+v_nc_n = u_1d_1 + \dots +u_md_m$ для некоторых
$d_i\in k$. Но набор векторов $u_1,\dots,u_m,v_1,\dots,v_n$
лниейно независим. Значит, все коэффициенты $c_i,d_j$ равны
нулю, и исходная линейная комбинация векторов
$T(v_1),\dots,T(v_n)$ тривиальна.
\end{proof}

Приведем пару полезных следствий этой теоремы; оказывается,
уже тривиальные соображения неотрицательности размерности
имеют серьезные последствия.

\begin{corollary}
Пусть $V,W$~--- векторные пространства над $k$, и
$\dim V < \dim W$. Не существует сюръективных линейных
отображений $V\to W$.
\end{corollary}
\begin{proof}
Предположим, что линейное отображение
$T\colon V\to W$ сюръективно. Тогда
$\Img(T) = W$, и по теореме~\ref{thm:homomorphism-linear}
$\dim(V) = \dim(\Ker(T)) + \dim(\Img(T))
= \dim(\Ker(T)) + \dim(W)$.
Но $\dim(\Ker(T))\geq 0$, и поэтому
$\dim(V) \geq \dim(W)$~--- противоречие с условием.
\end{proof}

\begin{corollary}\label{cor:no-injective-maps}
Пусть $V,W$~--- векторные пространства над $k$,
и $\dim V > \dim W$. Не существует инъективных линейных
отображений $V\to W$.
\end{corollary}
\begin{proof}
Предположим, что линейное отображение $T\colon V\to W$ инъективно.
По предложению~\ref{prop:injective-iff-kernel-trivial}
ядро $T$ тривиально. По теореме~\ref{thm:homomorphism-linear}
$\dim(V) = \dim(\Ker(T)) + \dim(\Img(T)) = \dim(\Img(T))
\leq \dim(W)$ (последнее неравенство выполнено
по предложению~\ref{prop:dimension_is_monotonic})~---
противоречие с условием.
\end{proof}

\subsection{Матрица линейного отображения}
\literature{[F], гл. XII, \S~4, пп. 1--3; [K2], гл. 2, \S~1, п. 2;
  \S~2, п. 3; [KM], ч. 1, \S~4; [vdW], гл. IV, \S~23.}

Пусть $V,W$~--- два конечномерных пространства,
и пусть $\mc B = (v_1,\dots,v_n)$~--- упорядоченный базис $V$,
а $\mc B' = (w_1,\dots,w_m)$~--- упорядоченный базис $W$.
Универсальное свойства базиса
(теорема~\ref{thm:universal-basis-property}) означает, что
для задания линейного отображение $T\colon V\to W$
достаточно задать векторы $T(v_1),\dots,T(v_n)\in W$.
Каждый вектор $T(v_j)$, в свою очередь, можно разложить
по базису $\mc B'$. Задание $T(v_j)$, таким образом, равносильно
заданию коэффициентов в этом разложении.
Мы получили, что линейное отображение $T\colon V\to W$
в итоге задается конечным набором скаляров~--- при условии, что
в пространствах $V$ и $W$ выбраны базисы.
Этот набор скаляров удобно записывать в виде матрицы.

\begin{definition}\label{dfn:matrix-of-linear-map}
Пусть $T\colon V\to W$~--- линейное отображение между
конечномерными пространствами, и пусть выбраны
упорядоченные базисы
$\mc B = (v_1,\dots,v_n)$ в $V$
и $\mc B' = (w_1,\dots,w_m)$ в $W$.
Разложим каждый вектор $T(v_j)$ по базису $\mc B'$
и запишем
$$
T(v_j) = w_1a_{1j} + w_2a_{2j} + \dots + w_ma_{mj}.
$$
Набор коэффициентов $(a_{ij})_{\substack{1\leq i\leq m \\
1\leq j\leq n}}$ мы воспринимаем как матрицу
размера $m\times n$; она называется
\dfn{матрицей линейного отображения $T$ в базисах $\mc B$,
$\mc B'$} и обозначается через $[T]_{\mc B,\mc B'}$.
\end{definition}

Как мы увидим ниже (см. теорему~\ref{thm:hom-isomorphic-to-m}),
линейное отображение полностью определяется
своей матрицей (в выбранных базисах). Известные нам операции
над линейными отображениями (сложение, умножение на скаляр,
композиция) при этом превращаются в известные
нам операции над матрицами (сложение, умножение на скаляр,
произведение). Ниже мы введем понятие координат вектора,
и тогда рассуждения с абстрактными векторными пространствами
и линейными отображениями можно будет сводить к конкретным
матричным вычислениям. Иными словами, матрицы полезны, когда
вам нужно <<засучить рукава>> и вычислить что-нибудь конкретное.
В то же время, всегда нужно помнить, что для перехода к матрицам
нужно зафиксировать базисы в рассматриваемых пространствах,
что может привести к утрате симметрии и некоторой неуклюжести.

Пусть $T,S\colon V\to W$~--- линейные отображения, и
в пространствах $V,W$ выбраны базисы, как в
определении~\ref{dfn:matrix-of-linear-map}.
Покажем, что матрица суммы $T+S$ этих отображений
является суммой матрицы отображения $T$ и матрицы отображения $S$.
Иными словами, $[T+S]_{\mc B,\mc B'} = [T]_{\mc B,\mc B'}
+ [S]_{\mc B,\mc B'}$.
Пусть $[T]_{\mc B,\mc B'} = (a_{ij})$, 
$[S]_{\mc B,\mc B'} = (b_{ij})$.
По определению это означает, что
$T(v_j) = \sum_{i=1}^m w_ia_{ij}$,
$S(v_j) = \sum_{i=1}^m w_ib_{ij}$.
Но тогда $(T+S)(v_j) = T(v_j) + S(v_j)
= \sum_{i=1}^m w_i(a_{ij}+b_{ij})$.
Значит, в разложении вектора $(T+S)(v_j)$ по базису $\mc B'$
коэффициент при $w_i$ равен $a_{ij}+b_{ij}$.
Это означает, что в матрице $[T+S]_{\mc B,\mc B'}$
в позиции $(i,j)$ стоит $a_{ij} + b_{ij}$.
Но это и есть определение суммы матриц $[T]_{\mc B,\mc B'}$
и $[S]_{\mc B,\mc B'}$.

Совершенно аналогичное рассуждение показывает, что
$[Ta]_{\mc B,\mc B'} = [T]_{\mc B,\mc B'}\cdot a$ для
любого скаляра $a\in k$.
Доказанные факты можно сформулировать следующим образом.
\begin{theorem}\label{thm:taking-matrix-is-linear}
Пусть $V,W$~--- конечномерные векторные пространства над полем $k$,
и $\mc B,\mc B'$~--- базисы в $V,W$ соответственно.
Обозначим $n=\dim(V)$, $m=\dim(W)$.
Отображение $\ph\colon \Hom(V,W) \to M(m,n,k)$, сопоставляющее
линейному отображению $T\in\Hom(V,W)$ его матрицу
$[T]_{\mc B,\mc B'}$ в базисах $\mc B,\mc B'$, является линейным.
\end{theorem}
\begin{proof}
Для проверки линейности $\ph$ по определению нужно показать,
что $[T+S]_{\mc B,\mc B'} = [T]_{\mc B,\mc B'} + [S]_{\mc B,\mc B'}$
и $[Ta]_{\mc B,\mc B'} = [T]_{\mc B,\mc B'}a$ для всех
$T,S\in\Hom(V,W)$, $a\in k$, что и было доказано выше.
\end{proof}

Гораздо интереснее посмотреть, что
происходит при композиции линейных отображений.
\begin{theorem}\label{thm:composition-is-multiplication}
Пусть $U,V,W$~--- три векторных пространства с базисами
$\mc B = (u_1,\dots,u_l)$,
$\mc B' = (v_1,\dots,v_m)$,
$\mc B'' = (w_1,\dots,w_n)$, соответственно,
и пусть $S\colon U\to V$, $T\colon V\to W$~--- линейные отображения.
Тогда
$[T\circ S]_{\mc B,\mc B''} = [T]_{\mc B',\mc B''}\cdot
[S]_{\mc B,\mc B'}$.
\end{theorem}
Читатель может проверить, что написанное выражение имеет смысл:
в правой части стоят матрицы таких размеров, что их можно
перемножить, и в результате получается матрица того же размера,
что и в левой части.

Доказательство этого факта нужно воспринимать как
(слегка запоздалое) объяснение определения умножения матриц.
В самом деле, единственная причина, по которой умножение
матриц выглядит так, как оно выглядит~--- это взаимно
однозначное соответствие между матрицами и линейными отображениями,
которое превращает композицию линейных отображений
в умножение матриц. Каждый, кто задумается, что происходит
при композиции линейных отображений (подстановке одних линейных
выражений в другие), неизбежно обязан открыть умножение матриц.

Итак, пусть $[T]_{\mc B',\mc B''} = (a_{ij}) \in M(n,m,k)$,
$[S]_{\mc B,\mc B'} = (b_{ij}) \in M(m,l,k)$.
Как найти матрицу отображения $T\circ S$?
По определению мы должны разложить каждый вектор
вида $(T\circ S)(u_p)$ по базису $w_1,\dots,w_n$.
Заметим, что  $(T\circ S)(u_p) = T(S(u_p))$,
а $S(u_p)$ мы умеем раскладывать по базису пространства $V$.
А именно,
$$
S(u_p) = \sum_{j=1}^m v_jb_{jp}.
$$
Получаем, что
\begin{align*}
(T\circ S)(u_p) &= T\left(\sum_{j=1}^m v_jb_{jp}\right)\\
&= \sum_{j=1}^m T(v_j)b_{jp},
\end{align*}
где в последнем равенстве мы воспользовались линейностью
отображения $T$. Теперь можно подставить в полученное
выражение разложение для каждого вектора вида
$T(v_j) = \sum_{i=1}^n w_i a_{ij}$.
После несложных преобразований сумм получаем
\begin{align*}
(T\circ S)(u_p) &=  \sum_{j=1}^m T(v_j)b_{ji} \\
&= \sum_{j=1}^m \sum_{i=1}^n w_i a_{ij} b_{jp} \\
&= \sum_{i=1}^n w_i\left( \sum_{j=1}^m a_{ij}b_{jp}\right).
\end{align*}
Коэффициент при $w_i$ в полученном разложении и равен
коэффициенту, стоящему в позиции $(i,p)$ матрицы
$[T\circ S]_{\mc B,\mc B''}$.
Он оказался равен $\sum_{j=1}^m a_{ij}b_{jp}$,
и потому матрица $[T\circ S]_{\mc B,\mc B''}$ равна
произведению матриц
$[T]_{\mc B',\mc B''}\cdot [S]_{\mc B,\mc B'}$.

Мы узнали, как понятие матрицы линейного отображение
ведет себя при сложении отображений, умножении на скаляры,
композиции. Есть еще одна операция над линейными
отображениями, самая простая: мы можем в линейное
отображение $T\colon V\to W$ подставить вектор из
$V$ и получить вектор из $W$.
Отображению $T$ мы сопоставили матрицу; сейчас мы сопоставим
векторам из $V$ и $W$ некоторые столбцы (матрицы ширину $1$)
таким образом, что вычисление результата действия
линейного отображения на векторе сведется к умножению
матрицы на столбец.

А именно, пусть $\mc B = (v_1,\dots,v_n)$~--- базис
векторного пространства $V$.
Любой вектор $v\in V$ можно разложить по этому базису,
то есть, записать его в виде линейной комбинации
элементов $\mc B$:
$$
v = v_1a_1+\dots+v_na_n,\quad a_i\in k.
$$
Запишем полученные скаляры $a_1,\dots,a_n$
в столбец. Полученный элемент пространства
$k^n$ называется \dfn{столбцом координат}
(или \dfn{координатным столбцом})
\dfn{вектора $v$ в базисе $\mc B$} и обозначается так:
$$
[v]_{\mc B} = \begin{pmatrix} a_1 \\ \vdots \\ a_n\end{pmatrix}.
$$
Коэффициенты $a_1,\dots,a_n$ называются
\dfn{координатами вектора $v$ в базисе $\mc B$}.
Обратите внимание на сходство этой записи с обозначением
для матрицы линейного оператора в выбранных базисах.

Таким образом, как только мы выбрали базис $\mc B$
в пространстве $V$, каждому вектору из $V$
сопоставляется столбец $[v]_{\mc B}\in k^n$.
Более того, указанное сопоставление хорошо согласовано
с операциями в пространстве $V$: если сложить два вектора,
то соответствующие им координатные столбцы сложатся,
а если вектор умножить на скаляр, то его координатный столбец
умножится на этот же скаляр.
Есть более короткий способ выразить указанные свойства:
сопоставление вектору $v\in V$ его координатного столбца
{\em линейно}. Сформулируем это в виде теоремы.
\begin{theorem}\label{thm:taking-coordinates-is-linear-map}
Пусть $V$~--- конечномерное векторное пространство над
полем $k$; $\mc B = \{v_1,\dots,v_n\}$~--- его базис.
Отображение
\begin{align*}
V & \to k^n,\\
v & \mapsto [v]_{\mc B}
\end{align*}
линейно.
\end{theorem}
\begin{proof}
Фактически, нам нужно показать, что если $v,v'\in V$,
$a\in k$, то
$[v+v']_{\mc B} = [v]_{\mc B} + [v']_{\mc B}$
и $[va]_{\mc B} = [v]_{\mc B} \cdot a$.
Пусть
$$
[v]_{\mc B} = \begin{pmatrix}a_1\\\vdots\\a_n\end{pmatrix},
\quad
[v']_{\mc B} = \begin{pmatrix}b_1\\\vdots\\b_n\end{pmatrix}.
$$
По определению это означает, что
\begin{align*}
v &= v_1a_1 + \dots + v_na_n,\\
v' &= v_1b_1 + \dots + v_nb_n.
\end{align*}
Сложим эти два равенства:
$$
v+v' = v_1(a_1+b_1) + \dots + v_m(a_n+b_n).
$$
Но тогда
$$
[v+v']_{\mc B} = \begin{pmatrix} a_1+b_1 \\
\vdots \\ a_n + b_n \end{pmatrix}
= \begin{pmatrix}a_1\\\vdots\\a_n\end{pmatrix} +
\begin{pmatrix}b_1\\\vdots\\b_n\end{pmatrix}
= [v]_{\mc B} + [v']_{\mc B},
$$
что и требовалось. Доказательство для умножения на скаляр
совершенно аналогично и оставляется читателю в качестве
упражнения.
\end{proof}

Теперь мы готовы сделать последний шаг в установлении
соответствия между действиями с векторными пространствами
с одной стороны, и вычислениями с матрицами с другой стороны.

\begin{theorem}\label{thm:matrix-multiplied-by-vector}
Пусть $T\colon V\to W$~--- линейное отображение между
конечномерными пространствами $V$ и $W$, и пусть
$\mc B = (v_1,\dots,v_n)$~--- базис $V$, а
$\mc B' = (w_1,\dots,v_m)$~--- базис $W$.
Тогда
$$
[Tv]_{\mc B'} = [T]_{\mc B,\mc B'}\cdot [v]_{\mc B}
$$
для любого вектора $v\in V$.
\end{theorem}
\begin{proof}
Пусть $v = v_1c_1 + \dots + v_nc_n$, то есть,
$$
[v]_{\mc B} = \begin{pmatrix} c_1 \\ \vdots \\ c_n
\end{pmatrix},
$$
и пусть
$[T]_{\mc B,\mc B'} = (a_{ij})$~--- матрица отображения $T$.
Тогда
$$
T(v) = T(\sum_{j=1}^n v_j c_j) = \sum_{j=1}^n T(v_j)c_j
= \sum_{j=1}^n \left( \sum_{i=1}^m w_ia_{ij}\right) c_j
= \sum_{i=1}^m w_i \left( \sum_{j=1}^n a_{ij}c_j \right).
$$
Значит, $i$-я координата вектора $T(v)$ в базисе $\mc B'$
равна $\sum_{j=1}^n a_{ij}c_j$.
Но это и означает, что столбец $[T(v)]_{\mc B'}$ равен
произведению матрицы $(a_{ij}) = [T]_{\mc B,\mc B'}$
на столбец $[v]_{\mc B}$.
\end{proof}

\subsection{Изоморфизм}

\begin{definition}
Линейное отображение $T\colon V\to W$ называется \dfn{обратимым}, если
существует линейное отображение $S\colon W\to V$ такое, что $S\circ T = \id_V$
и $T\circ S = \id_W$. Такое $S$ называется \dfn{обратным} к $T$.
\end{definition}

\begin{proposition}\label{prop:invertible-linear-iff-iso}
Линейное отображение $T\colon V\to W$ обратимо тогда и только тогда, когда
оно биективно.
\end{proposition}
\begin{proof}
Если $T$ обратимо, то обратное к нему является обратным отображением
в теоретико-множественном смысле (определение~\ref{dfn:inverse-map}),
и потому биективно по теореме~\ref{thm:sur-inj-reformulations}.

Если же отображение $T$ биективно, то
(снова по теореме~\ref{thm:sur-inj-reformulations}) существует отображение
множеств $S\colon W\to V$ такое, что $S\circ T = \id_V$ и $T\circ S = \id_W$.
Можно и явно построить это $S$: для каждого $w\in W$ заметим,
что (по определению биективности) существует единственное $v\in V$
такое, что $T(v) = w$; тогда положим $S(w) = v$.
Осталось проверить, что это отображение линейно. Действительно,
возьмем $w_1,w_2\in W$ и пусть $S(w_1) = v_1$, $S(w_2) = v_2$.
Это означает, что $T(v_1)=w_1$, $T(v_2)=w_2$.
Но тогда $T(v_1+v_2) = w_1+w_2$, и потому $S(w_1+w_2) = v_1+v_2 = S(w_1)+S(w_2)$.
Кроме того, если $w\in W$ и $a\in k$, пусть $S(w) = v$.
Это означает, что $T(v) = w$, откуда $T(va) = wa$, и, стало быть,
$S(wa) = va = S(w)a$.
\end{proof}

\begin{definition}
Обратимое линейное отображение иногда называется \dfn{изоморфизмом}. Если между
пространствами $V$ и $W$ существует изоморфизм $T\colon V\to W$,
они называются \dfn{изоморфными}. Обозначение: $V\isom W$.
\end{definition}

\begin{theorem}\label{thm:isomorphic-iff-equidimensional}
Два конечномерных векторных пространства над $k$ изоморфны тогда и только тогда,
когда их размерности равны.
\end{theorem}
\begin{proof}
Пусть $V\isom W$, то есть, существует обратимое линейное отображение $T\colon V\to W$.
По предложению~\ref{prop:invertible-linear-iff-iso} $T$ биективно. В частности,
$T$ инъективно, и потому $\Ker(T)=0$ (теорема~\ref{prop:injective-iff-kernel-trivial});
кроме того, $T$ сюръективно, и потому $\Img(T)=W$.
Воспользуемся теоремой о гомоморфизме~\ref{thm:homomorphism-linear}:
$$
\dim\Ker(T) + \dim\Img(T) = \dim(V).
$$
В нашем случае $\dim\Ker(T)=0$ и $\dim\Img(T)=\dim W$; поэтому $\dim V = \dim W$, что и
требовалось.

Обратно, пусть $\dim V = \dim W = n$. Выберем базис $v_1,\dots,v_n$ в $V$
и базис $w_1,\dots,w_n$ в $W$. По теореме~\ref{thm:universal-basis-property} для задания
линейного отображения $T\colon V\to W$ достаточно задать $T(v_i)$ для всех $i$.
Положим $T(v_i)=w_i$ и покажем, что полученное отображение $T$ является изоморфизмом.
Для этого (по предложению~\ref{prop:invertible-linear-iff-iso}) достаточно проверить,
что оно инъективно и сюръективно.

Для инъективности
(по предложению~\ref{prop:injective-iff-kernel-trivial}) нужно показать, что $\Ker(T)=0$.
Возьмем $v\in\Ker(T)$. Разложим $v$ по базису пространства $V$:
$v = v_1a_1 + \dots + v_na_n$. Тогда
$0 = T(v) = T(v_1)a_1+\dots+T(v_n)a_n = w_1a_1+\dots+w_na_n$.
Но элементы $w_1,\dots,w_n\in W$ образуют базис, и потому линейно независимы. Их
линейная комбинация оказалась равна нулю~--- поэтому все ее коэффициенты равны
нулю: $a_1=\dots=a_n=0$. Но тогда и $v = 0$.

Осталось проверить, что $T$ сюръективно. Но любой вектор $W$ есть линейная комбинация
векторов $w_1,\dots,w_n$, поэтому является образом соответствующей линейной комбинации
векторов $v_1,\dots,v_n$.
\end{proof}

\begin{corollary}
Любое конечномерное векторное пространство $V$ изоморфно пространству
$k^n$, где $n=\dim(V)$.
Более того, если $\mc B$~--- некоторый базис пространства $V$,
то отображение $\ph\colon v\mapsto [v]_{\mc B}$ устанавливает изоморфизм между
$V$ и $k^n$.
\end{corollary}
\begin{proof}
Пусть $\dim(V)=n$; тогда $\dim(k^n)=n=\dim(V)$, и
по теореме~\ref{thm:isomorphic-iff-equidimensional} пространства $V$ и $k^n$
изоморфны.

Для доказательства второго утверждения обозначим элементы базиса $\mc B$
через $v_1,\dots,v_n$.
Мы уже знаем, что отображение $v\mapsto [v]_{\mc B}$ линейно
(теорема~\ref{thm:taking-coordinates-is-linear-map}); проверим, что это
изоморфизм. Для этого нужно проверить, что его ядро тривиально, а образ
совпадает с $k^n$. Возьмем $v\in\Ker(\ph)$; это означает, что столбец
координат вектора $v$ нулевой. Но тогда по определению координат
$v=v_10+\dots+v_n0 = 0$. Значит, $\Ker(\ph)=0$. Пусть теперь
$w\in k^n$~--- некоторый столбец, состоящий из скаляров
$a_1,\dots,a_n$. Рассмотрим вектор $v = v_1a_1 + \dots + v_na_n\in V$.
Легко видеть, что $[v]_{\mc B} = w$, что доказывает сюръективность
отображения $\ph$.
\end{proof}

Таким образом, любое конечномерное пространство изоморфно пространству столбцов.
Подчеркнем, что этот изоморфизм зависит от выбора базиса (в таком случае говорят,
что этот изоморфизм {\em не является каноническим}): в разных базисах один
и тот же вектор, как правило, имеет разные наборы координат.

\begin{theorem}\label{thm:hom-isomorphic-to-m}
Пусть $V,W$~--- конечномерные векторные пространства над полем $k$.
Пространство $\Hom(V,W)$ линейных отображений из $V$ в $W$ изоморфно
векторному пространству $M(m,n,k)$ матриц размера $m\times n$ над $k$,
где $m=\dim W$, $n=\dim V$.
Более того, если $\mc B,\mc B'$~--- базисы в $V,W$ соответственно, то
отображение $\ph\colon T\mapsto [T]_{\mc B,\mc B'}$ устанавливает
изоморфизм между $\Hom(V,W)$ и $M(m,n,k)$.
\end{theorem}
\begin{proof}
Мы сразу докажем второе утверждение.
Обозначим элементы $\mc B$ через $v_1,\dots,v_n$,
а элементы $\mc B'$ через $w_1,\dots,w_m$.
По теореме~\ref{thm:taking-matrix-is-linear}
отображение $\ph$ линейно. Проверим, что его ядро тривиально, а образ
совпадает с $M(m,n,k)$. Пусть $T\in\Ker(\ph)$. Это значит, что у линейного
отображения $T$ матрица нулевая. По определению матрицы это значит,
что все координаты вектора $T(v_j)$ в базисе $\mc B'$ равны нулю,
а потому $T(v_j)=0$ для всех $j$. Но мы знаем одно такое линейное отображение:
это $0\in\Hom(V,W)$. По единственности в универсальном свойстве
базиса (теорема~\ref{thm:universal-basis-property}) $T=0$.
Наконец, пусть $A=(a_{ij})\in M(m,n,k)$~--- некоторая матрица. Мы утверждаем, что существует
линейное отображение $T\colon U\to V$, матрица которого в базисах $\mc B,\mc B'$
совпадает с $A$. Действительно, положим
$T(v_j) = w_1a_1+\dots+w_ma_m$. По теореме~\ref{thm:universal-basis-property}
это однозначно определяет линейное отображение $T$, и очевидно, что
$[T]_{\mc B,\mc B'} = A$.
\end{proof}

\begin{corollary}\label{cor:dim-of-hom-space}
Если пространства $V,W$ конечномерны, то $\dim\Hom(V,W) = \dim V\cdot\dim W$.
\end{corollary}
\begin{proof}
Очевидно, что размерность пространства матриц $M(m,n,k)$ равна $mn$; осталось
применить теорему~\ref{thm:hom-isomorphic-to-m}
и теорему~\ref{thm:isomorphic-iff-equidimensional}.
\end{proof}

Важный частный случай понятия линейного отображения~--- {\em линейный оператор}.
\begin{definition}
Линейное отображение $T\colon V\to V$ называется \dfn{линейным оператором}
на пространстве $V$, или \dfn{эндоморфизмом} пространства $V$.
\end{definition}

\begin{proposition}\label{prop:operators-bij-inj-surj}
Пусть $T\colon V\to V$~--- линейный оператор на конечномерном пространстве $V$.
Следующие утверждения равносильны.
\begin{enumerate}
\item Отображение $T$ биективно.
\item Отображение $T$ инъективно.
\item Отображение $T$ сюръективно.
\end{enumerate}
\end{proposition}
\begin{proof}
Очевидно, что из (1) следуют (2) и (3). Покажем, что из (2) следует (1).
Если $T$ инъективно, то $\Ker T=0$ (предложение~\ref{prop:injective-iff-kernel-trivial}).
По теореме о гомоморфизме (теорема~\ref{thm:homomorphism-linear})
$\dim\Ker T + \dim\Img T = \dim V$. Первое слагаемое равно нулю, поэтому
$\dim\Img T = \dim V$. В то же время, $\Img T$~--- подпространство в $V$,
и по предложению~\ref{prop:dimension_is_monotonic} из совпадения размерностей
следует, что $\Img T = V$, что означает сюръективность, а потому и биективность
отображения $T$.

Осталось показать, что из (3) следует (1). Снова воспользуемся теоремой о гомоморфизме:
$\dim\Ker T + \dim\Img T = \dim V$. Теперь по предположению $\Img T = \dim V$, и,
стало быть, $\dim\Ker T=0$. Значит, подпространство $\Ker T$ тривиально, и потому
$T$ инъективно и, следовательно, биективно.
\end{proof}

\begin{theorem}
Пусть $V$~--- векторное пространство. Множество $\Hom(V,V)$ всех линейных операторов
на $V$ образует ассоциативное кольцо с единицей относительно сложения и композиции.
\end{theorem}
\begin{proof}
Мы уже знаем, что сложение линейных отображений ассоциативно, коммутативно, обладает
нейтральным элементом $0$ и обратными элементами. Кроме того, композиция (которая играет
роль умножения) ассоциативна и обладает нейтральным элементом $\id_V$. Осталось проверить
левую и правую дистрибутивность. Ограничимся проверкой одной из них.
Пусть $S,T,U\in\Hom(V,V)$. Для каждого $v\in V$ выполнено
$$
(S\circ (T+U))(v) = S((T+U)(v)) = S(T(v)+U(v)) = S(T(v)) + S(U(v))
= (S\circ T)(v) + (S\circ U)(v) = (S\circ T + S\circ U)(v),
$$
а потому отображения $S\circ (T+U)$ и $S\circ T + S\circ U$ совпадают.
\end{proof}
Отметим, что в конечномерном случае кольцо операторов на $V$ {\em изоморфно} кольцу
квадратных матриц порядка $n = \dim V$
(см. замечание~\ref{rem:matrix_multiplication_properties}). Поясним, что означает
слово <<изоморфизм>> в этом контексте (пока мы обсуждали только изоморфизм
векторных пространств, но не колец).
Пусть $\mc B$~--- базис пространства $V$, и $\dim V = n$.
Из теоремы~\ref{thm:hom-isomorphic-to-m} следует, что
отображение $T\mapsto [T]_{\mc B}$ является биекцией между $\Hom(V,V)$
и $M(n,n,k)$, переводящей сложение в сложение. Кроме того,
по теореме~\ref{thm:composition-is-multiplication} она переводит
композицию операторов в умножение. Наконец, тождественный оператор
переходит при этом отображении в единичную матрицу. Мы получили биекцию
между кольцами, которая сохраняет все операции
(включая <<взятие единичного элемента>>). Такая биекция и называется
<<изоморфизмом колец>>; ее существование означает, что указанные кольца
<<ведут себя одинаково>>.

\subsection{Ранг матрицы}
\literature{[F], гл. IV, \S~3, пп. 4--6; [K1], гл. 2,
  \S~2, п. 1--2; [vdW], гл. IV, \S\S~22, 23.}

Первым приложением теории векторных пространств для нас станет
определение ранга матрицы, которые мы неформально обсуждали после
доказательства теоремы~\ref{thm_pdq}. Напомним, что любую матрицу
$A\in M(m,n,k)$ можно представить в виде
$A=P\left(\begin{matrix}
E_r & 0\\
0 & 0\end{matrix}\right)Q$, где $P,Q$~--- некоторые обратимые
матрицы. Мы покажем, что на самом деле натуральное число $r$ не
зависит от выбора такого представления, и поэтому имеет право
называться {\it рангом} матрицы $A$.
Для этого мы введем еще несколько понятий ранга, и покажем, что все
они совпадают друг с другом.

\begin{definition}
Пусть $A=(a_{ij})\in M(m,n,k)$. Линейная оболочка столбцов матрицы $A$
называется \dfn{пространством столбцов матрицы $A$}\index{векторное
  пространство!столбцов матрицы}; по определению
оно является подпространством в $k^m$. Иными словами, это пространство
$$\la\begin{pmatrix}a_{11}\\a_{21}\\\vdots\\a_{m1}\end{pmatrix},
\dots,
\begin{pmatrix}a_{1n}\\a_{2n}\\\vdots\\a_{mn}\end{pmatrix}\ra\leq
k^m.$$
Линейная оболочка строк матрицы $A$ называется \dfn{пространством
  строк матрицы $A$}\index{векторное пространство!строк матрицы}; по
определению оно является подпространством в
${}^nk$. Иными словами, это пространство
$$\la\begin{pmatrix}a_{11}&a_{12}&\dots&a_{1n}\end{pmatrix},\dots,
\begin{pmatrix}a_{m1}&a_{m2}&\dots&a_{mn}\end{pmatrix}\ra\leq {}^nk.$$
\end{definition}
Таким образом, пространство столбцов состоит из всевозможных линейных
комбинаций столбцов матрицы $A$; аналогично и со строками.
\begin{definition}
\dfn{Столбцовым рангом}\index{ранг матрицы!столбцовый} матрицы $A$ называется размерность ее
пространства столбцов; \dfn{строчным рангом}\index{ранг
  матрицы!строчный} $A$ называется
размерность ее пространства строк.
\end{definition}
Очевидно, что столбцовый ранг матрицы $A\in M(m,n,k)$ не превосходит
$n$, а ее строчный ранг не превосходит $m$.
Для определения следующего понятия~--- {\em тензорного ранга}~---
необходимо сначала определить матрицы ранга $1$.
\begin{definition}
Матрица $A\in M(m,n,k)$ называется \dfn{матрицей ранга
  $1$}\index{матрица!ранга $1$}, если
$A\neq 0$ и $A$ можно представить в виде $A=uv$, где $u\in k^m$, $v\in
{}^nk$. \dfn{Тензорным рангом}\index{ранг матрицы!тензорный} матрицы $A$ называется наименьшее
натуральное число $r$ такое, что $A$ можно представить в виде суммы
$r$ матриц ранга $1$. Иными словами, тензорный ранг $A$~--- это
наименьшее $r$, при котором существуют столбцы $u_1,\dots,u_r\in k^m$
и строки $v_1,\dots v_r\in {}^nk$ такие, что $A=u_1v_1+\dots+u_rv_r$.
\end{definition}

Заметим, что тензорный ранг матрицы $A\in M(m,n,k)$ определен: он не
превосходит $mn$. Действительно, несложно представить матрицу
$A=(a_{ij})$ в виде суммы $mn$ матриц ранга $1$: мы видели, что
$A=\sum_{i,j}a_{ij}e_{ij}$, а матрица $a_{ij}e_{ij}$ имеет ранг $1$:
$$
a_{ij}e_{ij} = \begin{pmatrix}0 \\ \vdots \\ 0 \\ a_{ij} \\ 0 \\
  \vdots \\ 0\end{pmatrix}\cdot\begin{pmatrix}0 & \dots & 0 & 1 & 0 &
  \dots & 0\end{pmatrix}.
$$
Здесь в столбце высоты $m$ элемент $a_{ij}$ стоит в позиции $i$, и в
строке длины $n$ элемент $1$ стоит в позиции $j$.

\begin{theorem}
Тензорный ранг матрицы не изменяется при домножении ее слева или
справа на обратимую матрицу. В частности, тензорный ранг матрицы
сохраняется при элементарных преобразованиях ее строк и столбцов.
\end{theorem}
\begin{proof}
Пусть $A\in M(m,n,k)$~--- матрица тензорного ранга $r$. Тогда мы можем
записать $A=u_1v_1+\dots+u_rv_r$ для некоторых столбцов
$u_1,\dots,u_r\in k^m$ и строк $v_1,\dots,v_r\in {}^nk$.
Если матрица $B\in M(m,k)$ обратима, то
$BA=B(u_1v_1+\dots+u_rv_r)=(Bu_1)v_1+\dots+(Bu_r)v_r$~--- сумма $r$
матриц ранга $1$, поэтому тензорный ранг $BA$ не превосходит $r$. С
другой стороны, если тензорный ранг $BA$ меньше $r$, то можно записать
$BA=u'_1v'_1+\dots+u'_pv'_p$ для $p<r$ и после домножения на $B^{-1}$
слева мы получили бы, что $A$ является суммой $p$ матриц ранга $1$~---
противоречие. Доказательство для домножения на обратимую матрицу
справа совершенно аналогично.
\end{proof}

\begin{theorem}\label{thm_ranks}
Тензорный ранг матрицы равен ее строчному рангу и столбцовому рангу.
\end{theorem}
\begin{proof}
Пусть размерность пространства строк матрицы $A\in M(m,n,k)$ равна
$d$. Это значит, что каждая строка матрицы $A$ является некоторой
линейной комбинацией строк $v_1,\dots,v_d\in {}^nk$.
Запишем эту линейную комбинацию:
$a_{i*} = \lambda_{i1}v_1+\dots+\lambda_{id}v_d$.
Заметим, что $A=e_1a_{1*}+e_2a_{2*}+\dots+e_ma_{m*}$, где
$e_i=\begin{pmatrix}0\\\vdots\\0\\1\\0\\\vdots\\0\end{pmatrix}$~---
стандартный базисный столбец в $k^m$.
Таким образом,
$$
A=e_1(\lambda_{11}v_1+\dots+\lambda_{1d}v_d) + \dots +
e_m(\lambda_{21}v_1+\dots+\lambda_{md}v_d).
$$
Раскрывая скобки, получаем, что $A=u_1v_1+\dots+u_dv_d$ для некоторых
столбцов $u_1,\dots,u_d\in k^m$.
Поэтому тензорный ранг $A$ не превосходит $d$.

Обратно, если $r$~--- тензорный ранг матрицы $A$, то
$u_1v_1+\dots+u_rv_r$, поэтому каждая строка матрицы $A$ является
линейной комбинацией строк $v_1,\dots,v_r$. Это означает, что
$v_1,\dots,v_r$~--- система образующих пространства строк матрицы
$A$. В силу следствия~\ref{thm:independent-set-smaller-than-generating}
получаем, что $d\leq r$.

Доказательство для столбцового ранга совершенно аналогично (или можно
заметить, что тензорный ранг не меняется при транспонировании).
\end{proof}

\begin{definition}
Общее значение тензорного, строчного и столбцового рангов матрицы $A$
называется ее \dfn{рангом}\index{ранг} и обозначается через $\rk(A)$.
\end{definition}

Теперь мы можем связать понятие тензорного ранга с понятием ранга,
введенным после доказательства следствия~\ref{cor_pdq}.
\begin{corollary}\label{cor_pdq_and_rank}
Пусть матрица $A\in M(m,n,k)$ представлена в виде $A=PDQ$, где $P\in
M(m,k)$, $Q\in M(n,k)$~--- обратимые матрицы, а
$D=\begin{pmatrix}E_r&0\\0&0\end{pmatrix}$~--- окаймленная единичная
матрица. Тогда $r$ равно тензорному рангу матрицы $A$.
\end{corollary}
\begin{proof}
По теореме~\ref{thm_ranks} тензорный ранг матрицы $A$ равен тензорному
рангу матрицы $\begin{pmatrix}E_r&0\\0&0\end{pmatrix}$; с другой
стороны, очевидно, что строчный ранг этой матрицы равен $r$.
\end{proof}

\begin{corollary}\label{cor_invertibility_rank}
Матрица $A\in M(n,k)$ обратима тогда и только тогда, когда ее ранг
равен $n$.
\end{corollary}
\begin{proof}
Простая комбинация следствия~\ref{cor_invertible_pdq} и
следствия~\ref{cor_pdq_and_rank}.
\end{proof}

\begin{theorem}[Кронекера--Капелли]
Система линейных уравнений имеет решение
(\dfn{совместна}\index{система линейных уравнений!совместная}) тогда и
только тогда, когда ранг матрицы этой системы равен рангу ее
расширенной матрицы. Если, кроме того, этот ранг равен количеству
неизвестных, то система имеет единственное решение.
\end{theorem}
\begin{proof}
Рассмотрим систему линейных уравнений $AX=B$.
Пусть $u_1,\dots,u_n$~--- столбцы матрицы $A$.
Система $AX=B$ имеет решение тогда и только тогда, когда существуют
$x_1,\dots,x_n\in k$ такие, что $u_1x_1+\dots+u_nx_n=B$. Это, в свою
очередь равносильно тому, что $B$ лежит в линейной оболочке векторов
$u_1,\dots,u_n$, то есть, тому, что $\la u_1,\dots,u_n\ra =
\la u_1,\dots,u_n,B\ra$. Это равенство и означает совпадение
[столбцовых] рангов матриц $A$ и $(A|B)$.

Если же ранг равен количеству неизвестных $n$, то пространство $\la
u_1,\dots,u_n\ra$ имеет размерность $n$. При этом $\la
u_1,\dots,u_n\ra$~--- его система образующих, и из нее можно выбрать
базис, в котором должно быть $n$ элементов. Значит, $u_1,\dots,u_n$
образуют базис пространства столбцов матрицы $A$. Поэтому вектор $B$
имеет единственное представление в виде $B=u_1x_1+\dots+u_nx_n$, что и
означает единственность решения системы.
\end{proof}


% 05.04.2015

\subsection{Фактор-пространство}

\literature{[F], гл. XII, \S~2, п. 5; [K2], гл. 1, \S~2, п. 6; [KM],
  ч. 1, \S~6.}

\begin{definition}\label{def:quotient_space}
Пусть $V$~--- векторное пространство над полем $k$, $U\leq V$. Будем
говорить, что элементы $v_1,v_2\in V$ \dfn{сравнимы по модулю
  $U$}\index{сравнение по модулю!подпространства},
если $v_1-v_2\in U$. Обозначения: $v_1\sim_U v_2$, $v_1\sim v_2$ (если
понятно, по модулю какого подпространства рассматривается сравнение).
\end{definition}

Пользуясь определением подпространства,
несложно проверить, что сравнение по модулю подпространства $U\leq V$
является отношением эквивалентности на $V$. Действительно, это отношение
рефлексивно: $v\sim v$, поскольку $v-v=0\in U$. Оно симметрично: если
$v_1\sim v_2$, то $v_1-v_2\in U$; тогда и $v_2-v_1=(v_1-v_2)\cdot
(-1)\in U$. Наконец, если $v_1\sim v_2$ и $v_2\sim v_3$, то
$v_1-v_2\in U$ и $v_2-v_3\in U$; отсюда
$v_1-v_3=(v_1-v_2)+(v_2-v_3)\in U$, поэтому $v_1\sim v_3$.

Раз мы получили отношение эквивалентности, то по
теореме~\ref{thm_quotient_set} сразу получаем разбиение на классы
эквивалентности. Мы будем обозначать класс эквивалентности элемента
$v\in V$ по отношению $\sim_U$ через $\overline{v}$ или через
$v+U$. Последнее обозначение имеет также следующий смысл: для любых
подмножеств $S,T\subseteq V$ можно определить их сумму $S+T=\{s+t\mid
s\in S, t\in T\}$ и результат умножения на скаляр $\lambda\in k$:
$S\lambda=\{s\lambda\mid s\in S\}$. В этих обозначениях класс
эквивалентности $v+U$~--- это в точности $\{v\}+U=\{v+u\mid u\in U\}$.

Фактор-множество множества $V$ по отношению эквивалентности $\sim_U$
мы будем обозначать через $V/U$. Наша ближайшая цель~--- ввести на нем
структуру векторного пространства.
Для этого необходимо определить сумму классов и результат умножения
класса на скаляр из $k$. Это, как и в случае построения кольца
классов вычетов (см. п.~\ref{subsect_residues}), осуществляется с
помощью операций над представителями классов: чтобы сложить два
элемента фактор-пространства, посмотрим, в каком классе лежит сумма
двух [любых] представителей этих элементов; чтобы умножить элемент на
скаляр, умножим любой его представитель на этот скаляр и посмотрим на
класс результата.
Точнее, положим $(v_1+U)+(v_2+U)=(v_1+v_2)+U$ и
$(v+U)a=va+U$ для любых $v,v_1,v_2\in V$ и $a\in k$.
В других обозначениях,
$\overline{v_1}+\overline{v_2} = \overline{v_1+v_2}$ и
$\overline{v}\cdot a = \overline{v\cdot a}$.
Как всегда, необходимо проверить {\em корректность} данного
определения, то есть, тот факт, что результат операций не зависит от
выбора представителей. Это делается совершенно прямолинейно, поэтому
мы оставляем проверку читателю в качестве упражнения.
Наконец, проверим, что полученные операции превращают $V/U$ в
векторное пространство над $k$.
\begin{proposition}\label{prop:quotient_space}
Пусть $V$~--- векторное пространство над полем $k$, $U\leq
V$. Фактор-множество $V/U$ вместе с введенными выше операциями
является векторным пространством над $k$.
\end{proposition}
\begin{proof}
Все проверки тривиальны; приведем выкладки с минимальными
комментариями.
\begin{enumerate}
\item $(\ol{v_1}+\ol{v_2})+\ol{v_3} = \ol{v_1+v_2}+\ol{v_3} =
\ol{(v_1+v_2)+v_3} = \ol{v_1+(v_2+v_3)} = \ol{v_1}+\ol{v_2+v_3} =
\ol{v_1}+(\ol{v_2}+\ol{v_3})$.
\item $\ol{v}+\ol{0}=\ol{v+0}=\ol{v}$, поэтому $\ol{0}\in V/U$ играет
  роль нейтрального элемента по сложению.
\item $\ol{v}+\ol{-v}=\ol{v+(-v)}=\ol{0}$, поэтому $\ol{-v}$~---
  обратный по сложению к $\ol{v}$.
\item $\ol{v_1}+\ol{v_2}=\ol{v_1+v_2}=\ol{v_2+v_1}=\ol{v_2}+\ol{v_1}$.
\item $(\ol{v_1}+\ol{v_2})\cdot a = \ol{v_1+v_2}\cdot a = 
\ol{(v_1+v_2)\cdot a} = \ol{v_1 a+v_2 a} =
\ol{v_1 a} + \ol{v_2 a} = \ol{v_1}\cdot a +
\ol{v_2}\cdot a$.
\item $\ol{v}(a+b) = \ol{v(a+b)} = \ol{va+vb}
  = \ol{va} + \ol{vb} = \ol{v}\cdot a + \ol{v}\cdot b$.
\item $\ol{v}(ab) = \ol{v(ab)} = \ol{(va)b} =
  \ol{va}\cdot b = (\ol{v}\cdot a)\cdot b$.
\item $\ol{v}\cdot 1 = \ol{v\cdot 1} = \ol{v}$.
\end{enumerate}
\end{proof}

С каждым отношением эквивалентности связана каноническая проекция
исходного множества на фактор-множество. В нашем случае она является
отображением $V\to V/U$, сопоставляющим вектору $v\in V$ его класс
$\ol{v}=v+U$. Нетрудно видеть, что это отображение является линейным:
действительно, $\ol{v_1+v_2}=\ol{v_1}+\ol{v_2}$ и
$\ol{v\lambda}=(\ol{v})\lambda$ просто по определению операций в фактор-пространстве.

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

%\literature{[F], гл. XII, \S~4, п. 1; [K2], гл. 2, \S~1, пп. 1, 3;
%  [KM], ч. 1, \S~3.}

\begin{theorem}[Теорема о гомоморфизме]\label{thm_homomorphism}
Пусть $\ph\colon U\to V$~--- линейное отображение. Тогда
$U/\Ker(\ph)\isom\Img(\ph)$.
\end{theorem}
\begin{proof}
Построим отображение $f\colon U/\Ker(\ph)\to\Img(\ph)$:
отправим класс $u+\Ker(\ph)$ в $\ph(u)\in\Img(\ph)$.
Проверим, что $f$ корректно определено, то есть, не зависит от выбора
представителя класса из $U/\Ker(\ph)$. Действительно, если
$u+\Ker(\ph)=u'+\Ker(\ph)$, то $u'-u\in\Ker(\ph)$, откуда
$0=\ph(u'-u)=\ph(u')-\ph(u)$. Значит, $\ph(u')=\ph(u)$, что и
требовалось.

Отображение $f$ является линейным. Действительно, если $u_1,u_2\in U$,
то $f(\ol{u_1})=\ph(u_1)$ и $f(\ol{u_2})=\ph(u_2)$, поэтому
$f(\ol{u_1})+f(\ol{u_2}) = \ph(u_1)+\ph(u_2)$. С другой стороны,
$f(\ol{u_1}+\ol{u_2}) = f(\ol{u_1+u_2}) = \ph(u_1+u_2) =
\ph(u_1)+\ph(u_2)$~--- то же самое. Наконец, если $u\in U$ и
$a\in k$, то $f(\ol{u})a=\ph(u)a$ и
$f(\ol{u}\cdot a) = f(\ol{u a}) = \ph(ua) =
\ph(u)a$.

Проверим, что $f$ биективно. Заметим, что из $\ph(u)=0$ следует, что
$u\in\Ker(\ph)$, то есть, что $\ol{u}=\ol{0}\in U/\Ker(\ph)$; поэтому
$f$ инъективно. С другой стороны, для каждого $v\in\Img(\ph)$
существует $u\in U$ такое, что $v=\ph(u)$. Тогда $f(\ol{u})=\ph(u)=v$,
поэтому $f$ сюръективно.
\end{proof}

\subsection{Относительный базис}

\literature{[F], гл. XII, \S~2, пп. 4--6; [K2], гл. 1, \S~2, пп. 4, 5.}

Пусть $V$~--- векторное пространство над полем $k$, $U\leq V$.

\begin{definition}
Набор векторов $v_1,\dots,v_n\in V$ называется \dfn{линейно независимым над
  $U$}\index{линейная независимость!над подпространством}, если
из $v_1a_1+\dots+v_na_n\in U$ следует, что
$a_1=\dots=a_n=0$.
Набор векторов $v_1,\dots,v_n\in V$ называется \dfn{порождающей системой
  над $U$}\index{порождающая система!над подпространством} (или
\dfn{системой образующих $V$ над $U$}\index{система образующих!над
  подпространством}), если любой вектор из $V$ можно представить в виде
$v_1a_1+\dots+v_na_n+u$ для некоторых
$a_1,\dots,a_n\in k$ и $u\in U$.
Наконец, набор $v_1,\dots,v_n\in V$ называется \dfn{относительным
  базисом $V$ над $U$}\index{базис!относительный}, если он линейно независим
над $U$ и является порождающей системой над $U$.
Нетрудно видеть, что это равносильно тому, что любой вектор $V$
представляется в виде $v_1a_1+\dots+v_na_n+u$ для
некоторого $u\in U$ {\em единственным образом}.
\end{definition}

\begin{theorem}\label{thm_relative_basis}
Следующие условия равносильны:
\begin{enumerate}
\item $v_1,\dots,v_n$~--- относительный базис $V$ над $U$;
\item $v_1+U,\dots,v_n+U$~--- базис фактор-пространства $V/U$;
\item $v_1,\dots,v_n$ вместе с некоторым базисом пространства $U$ в
  совокупности образуют базис пространства $V$;
\item $v_1,\dots,v_n$~--- базис некоторого дополнения $U$ в $V$.
\end{enumerate}
\end{theorem}
\begin{proof}
\begin{itemize}
\item[$1\Rightarrow 2$] Пусть $v_1,\dots,v_n$~--- относительный базис
  $V$ над $U$. Проверим, что система $v_1+U,\dots,v_n+U$ линейно
  независима. Действительно, если
  $(v_1+U)a_1+\dots+(v_n+U)a_n=0\in V/U$,
   то $(v_1a_1+\dots+v_na_n)+U=0\in V/U$.
  Это означает, что $v_1a_1+\dots+v_na_n\in U$, откуда по
  определению линейной независимости над $U$ следует
  $a_1=\dots=a_n=0$.
  Кроме того, любой вектор $v\in V$ можно представить в виде
  $v = v_1a_1+\dots+v_na_n+u$ для некоторых
  $a_1,\dots,a_n\in k$ и $u\in U$. Тогда
  $\ol{v}=\ol{v_1}a_1 + \dots + \ol{v_n}a_n$, поскольку
  $\ol{u}=0$. Значит, $\ol{v_1},\dots,\ol{v_n}$~--- система образующих
  $V/U$.
\item[$2\Rightarrow 3$] Пусть $v_1+U,\dots,v_n+U$~--- базис $V/U$,
  $u_1,\dots,u_k$~--- некоторый базис $U$. Тогда для любого вектора
  $v\in V$ класс $v+U\in V/U$ можно представить в виде
  $v+U=(v_1+U)a_1 + \dots + (v_n+U)a_n = (v_1a_1 +
  \dots + v_na_n) + U$. Поэтому $v\sim_U v_1a_1 + \dots +
  v_na_n$ и $v-(v_1a_1+\dots+v_na_n) = u\in
  U$. Разложим вектор $u$ по базису $u_1,\dots,u_k$:
  $u = u_1b_1 + \dots + u_kb_k$. Получаем, что
  $v = v_1a_1 + \dots + v_na_n + u_1b_1 + \dots +
  u_kb_k$.
  Это доказывает, что $v_1,\dots,v_n,u_1,\dots,u_k$~--- базис $V$.
  Наконец, если $v_1a_1 + \dots + v_na_n + u_1b_1 +
  \dots + u_kb_k = 0$, то $v_1a_1 + \dots + v_na_n =
  -u_1b_1 - \dots - u_kb_k\in U$, поэтому
  $\ol{v_1a_1 + \dots + v_na_n} = \ol{0}$, и в силу
  линейной независимости $\ol{v_1},\dots,\ol{v_n}$ в $V/U$ из этого
  следует, что $a_1 = \dots = a_n = 0$.
\item[$3\Rightarrow 4$] Пусть $u_1,\dots,u_k$~--- базис $U$ такой, что
  $v_1,\dots,v_n,u_1,\dots,u_k$~--- базис $V$. Тогда
  $\la v_1,\dots,v_n\ra + \la u_1,\dots,u_k\ra = V$, откуда
  $\la v_1,\dots,v_n\ra$~--- дополнение к $U$ в $V$.
\item[$4\Rightarrow 1$] Пусть $\la v_1,\dots,v_n\ra=U'$; по
  предположению, $V=U\oplus U'$. Если $v = v_1a_1 + \dots +
  v_na_n\in U$, то $v\in U\cap U'$, откуда $v=0$, и в силу
  линейной независимости векторов $v_1,\dots,v_n$, получаем $a_1 = \dots =
  a_n = 0$.
  Наконец, любой вектор $v\in V$ можно представить в виде $v=u+u'$ для
  некоторых $u\in U$, $u'\in U'$. Запишем $u' = v_1a_1 + \dots +
  v_na_n$; получаем, что $v = v_1a_1 + \dots +
  v_na_n + u$.
\end{itemize}
\end{proof}

\begin{corollary}
Пусть $U\leq V$~--- векторные пространства. Тогда
$\dim(V/U)=\dim(V)-\dim(U)$.
\end{corollary}
\begin{proof}
Выберем базис $u_1,\dots,u_k$ в $U$ и базис $\ol{v_1},\dots,\ol{v_n}$
в $V/U$. По части~3 теоремы~\ref{thm_relative_basis} набор
$u_1,\dots,u_k,v_1,\dots,v_n$ является базисом в $V$, состоящим из
$k+n$ элементов.
\end{proof}

% 13.04.2015

\subsection{Матрица перехода}

\literature{[F], гл. XII, \S~1, п. 4; [K2], гл. I, \S~2, п. 3; [KM],
  ч. 1, \S~4, п. 7.}

Напомним, что выбор базиса $\mc B$ в конечномерном пространстве $V$,
$\dim(V)=n$, задает
изоморфизм между $V$ и пространством столбцов $k^n$: у каждого
вектора $v$ появляется координатный столбец $[v]_{\mc B}$, состоящий
из $n$ координат вектора $v$ в базисе $\mc B$.

Пусть теперь $\mc B'$~--- еще один базис пространства $V$. Возникает
естественный вопрос: как связаны между собой координаты вектора $v$ в
базисах $\mc B$ и $\mc B'$? Ответ на этот вопрос формулируется с
помощью {\em матрицы перехода} между базисами.

\begin{definition}\label{def:change_of_basis_matrix}
Пусть $\mc B=\{u_1,\dots,u_n\}$, $\mc B'=\{v_1,\dots,v_n\}$~--- базисы
конечномерного пространства $V$. В частности, векторы $v_j$ можно
разложить по базису $\mc B$:
$$
v_j=\sum_{i=1}^n u_ic_{ij}.
$$
Матрица $C=(c_{ij})_{i,j=1}^n$, составленная из коэффициентов этих
разложений, называется~\dfn{матрицей перехода}\index{матрица!перехода}
от базиса $\mc B$ к
базису $\mc B'$ и обозначается через $(\mc B\rsa\mc B')$. Иными
словами, матрица $(\mc B\rsa\mc B')$ составлена из координатных
столбцов векторов $v_1,\dots,v_n$ в базисе $\mc B$:
$$
(\mc B\rsa\mc B')=\begin{pmatrix}[v_1]_{\mc B} & [v_2]_{\mc B} & \dots
  & [v_n]_{\mc B}\end{pmatrix}.
$$
В этой ситуации $\mc B$ называется \dfn{старым базисом}, $\mc B'$~---
\dfn{новым базисом}, а $(\mc B\rsa\mc B')$~--- \dfn{матрицей перехода
  от старого базиса к новому}.
\end{definition}

Символически мы можем записать
$$
\begin{pmatrix}v_1 & v_2 & \dots & v_n\end{pmatrix} =
\begin{pmatrix}u_1 & u_2 & \dots & u_n\end{pmatrix}\cdot
(\mc B\rsa\mc B').
$$
В такой записи слева стоит строчка, составленная из {\em векторов}
пространства $V$, а справа~--- произведение такой строчки на матрицу
над $k$. Переменожая строчку векторов на столбцы матрицы над $k$ мы
будем получать линейные комбинации этих векторов, поэтому в правой
части после перемножения окажется строчка, состоящая из $n$
линейных комбинаций векторов $u_1,\dots,u_n$. Равенство теперь означает,
что вектор $v_j$ равен $j$-й из этих линейных комбинаций.


\begin{proposition}[Свойства матрицы перехода]
Пусть $\mc B=\{u_1,\dots,u_n\}$, $\mc B'=\{v_1,\dots,v_n\}$,
$\mc B''=\{w_1,\dots,w_n\}$~--- базисы конечномерного пространства
$V$. Тогда
\begin{enumerate}
\item $(\mc B\rsa\mc B)=E$;
\item $(\mc B\rsa\mc B'')=(\mc B\rsa\mc B')\cdot (\mc B'\rsa\mc B'')$;
\item матрица $(\mc B\rsa\mc B')$ обратима и
$(\mc B\rsa\mc B')^{-1}=(\mc B'\rsa\mc B)$.
\end{enumerate}
\end{proposition}
\begin{proof}
\begin{enumerate}
\item Очевидно: столбец координат вектора $u_i$ в базисе
  $\{u_1,\dots,u_n\}$ равен $e_i$, то есть, равен $i$-му столбцу
  единичной матрицы.
\item Мы знаем, что $$(w_1,\dots,w_n)=(u_1,\dots,u_n)(\mc B\rsa\mc
  B'').$$
С другой стороны, $(w_1,\dots,w_n) = (v_1,\dots,v_n)(\mc B'\rsa\mc B'')
= (u_1,\dots,u_n)(\mc B\rsa\mc B')(\mc B'\rsa\mc B'')$.
Поэтому
$$
(u_1,\dots,u_n)(\mc B\rsa\mc B'') = (u_1,\dots,u_n)(\mc B\rsa\mc
B')(\mc B'\rsa\mc B'').
$$
Поскольку $(u_1,\dots,u_n)$ является базисом, из равенства линейных
комбинаций векторов $u_1,\dots,u_n$ следует равенство всех их
коэффициентов, поэтому
$$
(\mc B\rsa\mc B'') = (\mc B\rsa\mc B')(\mc B'\rsa\mc B''),
$$
что и требовалось.
\item Из первых двух пунктов следует, что $(\mc B\rsa\mc B')\cdot(\mc
  B'\rsa\mc B) = (\mc B\rsa\mc B) = E$; аналогично, $(\mc B'\rsa\mc
  B)\cdot(\mc B\rsa\mc B') = (\mc B'\rsa\mc B') = E$.
\end{enumerate}
\end{proof}

Теперь мы можем связать координаты одного и того же вектора в разных
базисах.

\begin{theorem}\label{thm:change_of_coordinates}
Пусть $V$~--- конечномерное векторное пространство, $\mc B$, $\mc
B'$~--- базисы $V$. Тогда для любого вектора $v\in V$ выполнено
$$
[v]_{\mc B'} = (\mc B'\rsa\mc B)\cdot [v]_{\mc B}.
$$
\end{theorem}
\begin{remark}\label{rem:contravariant_change}
Это означает, что координаты вектора в базисе преобразуются
{\em контравариантно} при замене базиса: координаты в новом базисе
получаются из координат в старом базисе домножением на матрицу
перехода {\em из нового базиса в старый}.
\end{remark}
\begin{proof}
Пусть $\mc B=\{u_1,\dots,u_n\}$, $\mc B'=\{v_1,\dots,v_n\}$.
Запишем $[v]_{\mc B} =
\begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n\end{pmatrix}$ и
$[v]_{\mc B'} = 
\begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_n\end{pmatrix}$.
По определению это означает,
что $v = u_1x_1+\dots+u_nx_n = v_1y_1+\dots+v_2y_2$,
то есть,
$$v=\begin{pmatrix}u_1 & \dots & u_n\end{pmatrix}
\begin{pmatrix}x_1 \\ \vdots \\ x_n\end{pmatrix} = 
\begin{pmatrix}v_1 & \dots & v_n\end{pmatrix}
\begin{pmatrix}y_1 \\ \vdots \\ y_n\end{pmatrix}.$$
По определению матрицы перехода имеем
$\begin{pmatrix}v_1 & \dots & v_n\end{pmatrix}
=\begin{pmatrix}u_1 & \dots & u_n\end{pmatrix}
\cdot (\mc B\rsa\mc B')$.
Подставляя это в полученное равенство, получаем
$$
v=\begin{pmatrix}u_1 & \dots & u_n\end{pmatrix}
\begin{pmatrix}x_1 \\ \vdots \\ x_n\end{pmatrix} = 
=\begin{pmatrix}u_1 & \dots & u_n\end{pmatrix}
(\mc B\rsa\mc B')
\begin{pmatrix}y_1 \\ \vdots \\ y_n\end{pmatrix}
$$
Но $(u_1,\dots,u_n)$ является базисом, поэтому из равенства линейных
комбинаций этих векторов следует равенство их коэффициентов.
Значит,
$$
\begin{pmatrix}x_1 \\ \vdots \\ x_n\end{pmatrix} = 
(\mc B\rsa\mc B')
\begin{pmatrix}y_1 \\ \vdots \\ y_n\end{pmatrix},
$$
что и требовалось доказать.
\end{proof}


% \subsection{Матрица линейного отображения}\label{subsect:matrix_of_a_linear_map}

%\literature{[F], гл. XII, \S~4, пп. 1--3; [K2], гл. 2, \S~1, п. 2;
%  \S~2, п. 3; [KM], ч. 1, \S~4; [vdW], гл. IV, \S~23.}

Еще один естественный вопрос~--- что происходит с матрицей отображения
при замене базисов в пространствах?
Пусть в пространстве $U$ заданы базисы $\mc B$ и $\mc C$, а в
пространстве $V$~--- базисы $\mc B'$ и $\mc C'$. У каждого линейного
отображения $\ph\colon U\to V$ имеется матрица $[\ph]_{\mc B,\mc B'}$
в базисах $\mc B,\mc B'$ и матрица $[\ph]_{\mc C,\mc C'}$ в базисах
$\mc C,\mc C'$.

\begin{theorem}\label{thm_matrix_under_change_of_bases}
Пусть $U,V$~--- векторные пространства над полем $k$,
$\ph\colon U\to V$~--- линейное отображение,
 $\mc B$, $\mc
C$~--- базисы в $U$, $\mc B'$, $\mc C'$~--- базисы в $V$. Тогда
$$
[\ph]_{\mc C,\mc C'} = (\mc B'\rsa\mc C')^{-1}[\ph]_{\mc B,\mc B'}(\mc
B\rsa\mc C)
$$
\end{theorem}
\begin{proof}
Пусть $u\in U$; тогда
$[\ph(u)]_{\mc B'} = [\ph]_{\mc B,\mc B'}\cdot[u]_{\mc B}$
и $[\ph(u)]_{\mc C'} = [\ph]_{\mc C,\mc C'}\cdot[u]_{\mc C}$.
Кроме того, $[u]_{\mc B} = (\mc B\rsa \mc C)[u]_{\mc C}$ и
$[\ph(u)]_{\mc C'} = (\mc C'\rsa \mc B')[\ph(u)]_{\mc B'}$.
Поэтому
\begin{align*}
[\ph]_{\mc C,\mc C'}\cdot [u]_{\mc C} &= 
[\ph(u)]_{\mc C'} = (\mc C'\rsa\mc B')[\ph(u)]_{\mc B'} \\
&= (\mc C'\rsa\mc B')[\ph]_{\mc B,\mc B'}\cdot[u]_{\mc B} \\
&= (\mc C'\rsa\mc B')[\ph]_{\mc B,\mc B'}\cdot(\mc B\rsa\mc C)[u]_{\mc
  C}
\end{align*}
для всех векторов $u\in U$.
По предложению~\ref{prop:equal-matrices} из этого следует
нужное равенство матриц.
\end{proof}

Итак, при замене базисов в пространствах $U$ и $V$ матрица отображения
$\ph\colon U\to V$ домножается справа на матрицу замены базиса в $U$ и
слева~--- на обратную матрицу замены базиса в $V$. Это можно
использовать следующим образом: для фиксированного отображения $\ph$
попробуем подобрать базисы в $U$ и $V$ так, чтобы матрица $\ph$ в этих
базисах выглядела наиболее простым образом.

\begin{theorem}[Каноническая форма матрицы линейного отображения]\label{thm_homomorphism_canonical}
Пусть $\ph\colon U\to V$~--- гомоморфизм векторных пространств. Тогда
найдутся базис $\mc B$ в $U$ и базис $\mc B'$ в $V$ такие, что матрица
$[\ph]_{\mc B,\mc B'}$ является окаймленной единичной:
$[\ph]_{\mc B,\mc B'} = \begin{pmatrix}E_r & 0\\0&0\end{pmatrix}$.
При этом $r=\dim(\Img(\ph))$.
\end{theorem}
\begin{proof}
По теореме о гомоморфизме (\ref{thm_homomorphism}) имеется изоморфизм
$\tld\ph\colon U/\Ker(\ph)\isom\Img(\ph)$.
Выберем какой-нибудь базис в $\Ker(\ph)$ и базис в $U/\Ker(\ph)$; по
теореме~\ref{thm_relative_basis} мы получим базис в $U$; пусть это
$e_1,\dots,e_n$,
причем $e_1,\dots,e_r$~--- относительный базис $U$ над $\Ker(\ph)$, а
$e_{r+1},\dots,e_n$~--- базис $\Ker(\ph)$.
Базису $\ol{e_1},\dots,\ol{e_r}$ в $U/\Ker(\ph)$ в силу
изоморфизма $\tld\ph$ соответствует базис $f_1,\dots,f_r$ в
$\Img(\ph)$; при этом $\ph(e_i)=f_i$ для $i=1,\dots,r$, и видно, что
$r=\dim(\Img(\ph))$.
Наконец, поскольку $\Img(\ph)\leq V$, можно дополнить систему
$f_1,\dots,f_r$ до базиса $V$ векторами $f_{r+1},\dots,f_m$.
Поскольку $\ph(e_i)=f_i$ для $i=1,\dots,r$ и $\ph(e_i)=0$ для $i\geq
r+1$, матрица $\ph$ в базисах $(e_1,\dots,e_n)$, $(f_1,\dots,f_m)$
имеет нужный вид.
\end{proof}

Фактически мы получили еще одно доказательство
следствия~\ref{cor_pdq}.
\begin{remark}\label{rem_rank_homomorphism}
Размерность образа отображения $\ph$ называется
\dfn{рангом}\index{ранг!линейного отображения} $\ph$; по
теореме~\ref{thm_homomorphism_canonical} ранг линейного отображения
равен рангу его матрицы (в любой паре базисов, поскольку при
домножении на обратимые матрицы ранг не меняется).
\end{remark}

\begin{remark}\label{rem:rank-is-dim-im}
Приведем еще одну характеризацию ранга: {\em размерность образа
линейного отображения равна рангу его матрицы}. Действительно,
по теореме~\ref{thm_homomorphism_canonical} можно выбрать базис так,
что матрица нашего отображения станет окаймленной единичной.
Для окаймленной единичной матрицы ранга $r$ очевидно, что образ
соответствующего линейного отображения имеет размерность $r$~---
этот образ есть просто линейная оболочка первых $r$ базисных векторов.
Осталось вспомнить, что при замене базиса происходит домножение
матрицы линейного отображения на обратимые матрицы слева и справа,
что, как мы знаем, не меняет ранга матрицы. 
\end{remark}

\begin{proposition}
Размерность пространства решений однородной системы линейных уравнений
равна числу неизвестных минус ранг матрицы этой системы.
\end{proposition}
\begin{proof}
Пусть речь идет о системе $AX=0$, где $A\in M(m,n,k)$, и $X\in k^n$~---
столбец неизвестных. Рассмотрим линейный оператор
$T\colon k^n\to k^m$, $X\mapsto AX$. Нетрудно понять, что его матрица
относительно стандартных базисов $k^n$, $k^m$ равна $A$.
Пространство решений системы $AX=0$~--- это в точности ядро оператора
$T$. Ранг матрицы $A$, как мы заметили выше~--- это размерность
образа оператора $T$. Число неизвестных здесь равно $n$.
Осталось применить теорему о гомоморфизме~\ref{thm:homomorphism-linear}.
\end{proof}

\begin{corollary}
Пусть $A\in M(m,n,k)$.
Однородная линейная система уравнений $AX=0$ имеет нетривиальное (то
есть, ненулевое) решение тогда и только тогда, когда $\rk(A)<n$. В
частности, если $m<n$, то эта система всегда имеет нетривиальное
решение; если же $m=n$, то она имеет нетривиальное решение тогда и
только тогда, когда матрица $A$ необратима.
\end{corollary}
\begin{proof}
Нетривиальное решение системы $AX=0$ существует тогда и только тогда,
когда размерность пространства решение строго больше $0$, что по
предыдущей теореме равносильно неравенству $\rk(A)<n$. Если $m<n$, то
ранг матрицы $A$, будучи равен строчному рангу, не превосходит $m$:
$\rk(A)\leq m<n$, поэтому нетривиальное решение имеется. Если же
$m=n$, то неравенство $\rk(A)<n$ по
следствию~\ref{cor_invertibility_rank} равносильно необратимости $A$.
\end{proof}

Докажем еще раз теорему Кронекера--Капелли.
\begin{theorem}[Кронекера--Капелли]\label{thm_kronecker_kapelli_2}
Система линейных уравнений $AX=B$ имеет решение тогда и только тогда,
когда ранг матрицы $A$ равен рангу расширенной матрицы $(A|B)$. При
этом решение единственно тогда и только тогда, когда, дополнительно,
этот ранг равен числу неизвестных $n$.
\end{theorem}
\begin{proof}
Рассмотрим соответствующее линейное отображение $T\colon k^n\to
k^m$, $X\mapsto AX$.
Образ $T$~--- это подпространство, порожденное векторами
$T(e_1),\dots,T(e_n)$, то есть, пространство столбцов матрицы
$A$. Значит, $B$ лежит в $\Img(T)$ тогда и только тогда, когда
столбец $B$ является линейной комбинацией столбцов матрицы $A$. По
предложению~\ref{prop_structure_of_solutions_linear_system} имеется
биекция между множеством решений системы
$AX=B$ и множеством решений однородной системы $AX=0$; это множество
состоит из одной точки тогда и только тогда, когда $\Ker(T)=0$, то
есть, когда $\rk(A)=\dim(\Img(T))=n$.
\end{proof}
