main.tex

\documentclass[10pt,a4paper,oneside]{book} % тест4
\usepackage[a4paper,includeheadfoot,top=10mm,bottom=10mm,left=10mm,right=10mm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsmath,amsthm,amssymb,amscd,array}
\usepackage{latexsym}
\usepackage{multicol} % нумерация в нескольких колонках
\usepackage{graphicx} 
%\usepackage{pdfsync}
\usepackage{pgf}
\usepackage{tikz}
\usepackage{tikz-cd}
\usetikzlibrary{arrows,backgrounds,patterns,matrix,shapes,fit,calc,shadows,plotmarks}
\usepackage{hyperref} % гиперссылки
\usepackage{cmap}       % Поддержка поиска русских слов в PDF (pdflatex)
\usepackage{indentfirst}% Красная строка в первом абзаце
\usepackage{misccorr}
\usepackage{arydshln} % штрихованные линии в массивах
\usepackage{mathtools} % выравнивание в матрицах
\usepackage{ccaption}
\usepackage{fancyhdr}
\usepackage{comment}
\usepackage{xcolor}
\hypersetup{
    colorlinks,
    linkcolor={blue!50!black},
    citecolor={blue!50!black},
    urlcolor={red!80!black}
}
% цвета для ссылок

\newtheorem{upr}{Упражнение}
\newtheorem{predl}{Предложение}
\newtheorem{komment}{Комментарий}
\newtheorem{conj}{Гипотеза}
\newtheorem{notation}{Обозначение}


\theoremstyle{definition}
\newtheorem{kit}{Кит}
\newtheorem*{rem}{Замечание}
\newtheorem{zad}{Задача}
\newtheorem*{defn}{Определение}
\newtheorem*{fact}{Факт}
\newtheorem{thm}{Теорема}
\newtheorem*{thmm}{Теорема}
\newtheorem{lem}{Лемма}
\newtheorem{cor}{Следствие}



\renewcommand{\proofname}{Доказательство}
\renewcommand{\mod}{\,\operatorname{mod}\,}
\newcommand{\mf}[1]{\mathfrak{#1}}
\newcommand{\mcal}[1]{\mathcal{#1}}
\newcommand{\mb}[1]{\mathbb{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\tbf}[1]{\textbf{#1}}
\newcommand{\ovl}{\overline}
\newcommand{\Spec}{\operatorname{Spec}}
\newcommand{\K}{\operatorname{K_0}}
\newcommand{\witt}{\operatorname{W}}
\newcommand{\gw}{\operatorname{GW}}
\newcommand{\coh}{\operatorname{H}}
\newcommand{\dist}{\operatorname{dist}}
\newcommand{\cl}{\operatorname{Cl}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand\tgg{\mathop{\rm tg}\nolimits}
\newcommand\ccup{\mathop{\cup}}
\newcommand{\id}{\operatorname{Id}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\chr}{\operatorname{char}}
\newcommand{\rank}{\operatorname{rank}}
\DeclareMathOperator{\Coker}{Coker}
\DeclareMathOperator{\Ker}{Ker}
\newcommand{\im}{\operatorname{Im}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\Tr}{\operatorname{Tr}}
\newcommand{\re}{\operatorname{Re}}
\newcommand{\tr}{\operatorname{Tr}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\Stab}{\operatorname{Stab}}
\newcommand{\orb}{\operatorname{\mathcal O}}
\newcommand{\Fix}{\operatorname{Fix}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\Aut}{\operatorname{Aut}}
\newcommand{\Inn}{\operatorname{Inn}}
\newcommand{\Out}{\operatorname{Out}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\SL}{\operatorname{SL}}
\newcommand{\SO}{\operatorname{SO}}
\newcommand{\Sym}{\operatorname{Sym}}
\newcommand{\Adj}{\operatorname{Adj}}


\newcommand{\di}{\mathop{\,\scalebox{0.85}{\raisebox{-1.2pt}[0.5\height]{\vdots}}\,}}

\newcommand{\ndi}{\mathop{\not\scalebox{0.85}{\raisebox{-1.2pt}[0.5\height]{\vdots}}\,}}
\newcommand{\nequiv}{\not \equiv}
\newcommand{\Nod}{\operatorname{\text{НОД}}}
\newcommand{\Nok}{\operatorname{\text{НОК}}}
\newcommand{\sgn}{\operatorname{sgn}}


\def\llq{\textquotedblleft} 
\def\rrq{\textquotedblright} 
\def\exm{\noindent {\bf Примеры:}}


\def\Cb{\ovl{C}}
\def\ffi{\varphi}
\def\pa{\partial}
\def\V{\bf V}
\def\La{\Lambda}
\def\eps{\varepsilon}
\def\del{\delta}
\def\Del{\Delta}
\def\A{\EuScript{A}}
\def\lan{\left\langle }
\def\ran{\right\rangle}
\def\bar{\begin{array}}
\def\ear{\end{array}}
\def\beq{\begin{equation}}
\def\eeq{\end{equation}}
\def\thrm{\begin{thm}}
\def\ethrm{\end{thm}}
\def\dfn{\begin{defn}}
\def\edfn{\end{defn}}
\def\lm{\begin{lem}}
\def\elm{\end{lem}}
\def\zd{\begin{zad}}
\def\ezd{\end{zad}}
\def\prdl{\begin{predl}}
\def\eprdl{\end{predl}}
\def\crl{\begin{cor}}
\def\ecrl{\end{cor}}
\def\rm{\begin{rem}}
\def\erm{\end{rem}}
\def\fct{\begin{fact}}
\def\efct{\end{fact}}
\def\enm{\begin{enumerate}}
\def\eenm{\end{enumerate}}
\def\pmat{\begin{pmatrix}}
\def\epmat{\end{pmatrix}}

\frenchspacing
\righthyphenmin=2
%\usepackage{floatflt}
\captiondelim{. }





\begin{document}

\title{Актуальный конспект по алгебре, 2 семестр, весна 2018}
\date{}
\author{}
\maketitle
\tableofcontents

\setcounter{chapter}{1}

\chapter{Теория колец: кое-что о многочленах и рядах}

\section{Комплексные числа}
\rm Гомоморфизм из поля всегда инъективен. Следовательно, если есть гомоморфизм из поля $K\to L$, то не умаляя общности (и если этот гомоморфизм нельзя перепутать с каким-нибудь другим гомоморфизмом $K\to L$), то можно считать, что $K\subseteq L$.
\erm

\dfn Если $K\subseteq L$, то будем говорить, что $L$ есть расширение поля $K$, а $K$ -- подполе поля $L$.
\edfn
Покажем, что расширений полей достаточно много.
\thrm[У любого многочлена в каком-то расширении есть все корни] Пусть $f(x)\in K[x]$. Тогда существует расширение $L$ поля $K$, такое, что в $L$ многочлен $f$ раскладывается на линейные множители.  
\ethrm
\proof Индукция по степени $f(x)$. Разложим $f(x)$ на неприводимые множители. Рассмотрим один из этих множителей $p(x)$. Тогда в поле $L=K[x]/p(x)$ у $p(x)$ и, следовательно, у $f(x)$ есть корень $\lambda$. Поделим $g(x)=\frac{f(x)}{x-\lambda}$ в $L[x]$. Получился многочлен меньшей степени, но в $L[x]$. Это нам подходит. Существует $L'$ раcширение $L$, где  $g(x)$ и, следовательно у $f(x)=g(x)(x-\lambda)$ раскладывается на линейные множители.
\endproof

Наше следующее рассмотрение будет примером того, как указанная выше конструкция работает и даёт нетривиальные примеры расширений полей. 

\dfn[Комплексные числа] Поле $\mb R[x]/(x^2 + 1)$ называется полем комплексных чисел. Будем обозначать это расширение полей как $\mb C$.
\edfn

Разберёмся, как устроено умножение в $\mb C$. Прежде всего вспомним, что любой элемент представляется однозначно как класс многочлена вида $a+bx$. Складываются такие представители, как мы помним, покомпонентно. Посмотрим, что происходит при произведении. Рассмотрим два элемента $a+bx$ и $c+dx$. Тогда
$$(a+bx)(c+dx)=ac+(ad+bc)x+bdx^2\equiv ac-bd + (ad+bc)x \mod x^2+1.$$

Так как наша конструкция очень специальная то введём обозначение $i$ для класса элемента $x$. Элемент $i$ по самому определению $\mb C$ удовлетворяет соотношению $i^2=-1$. Благодаря нашему соглашению любой элемент $z$ в $\mb C$ однозначно записывается в виде суммы $z=a+bi$, где $a,b\in \mb R$. Такая форма записи для комплексного числа будет для нас стандартной. В такой форме видно, что любому комплексному числу соответствует точка на плоскости с координатами $(a,b)$. Число $a$ называется вещественной частью числа $z$ и обозначается $a=\re z$, число $b$ --- мнимой частью и обозначается $\im z$. Если говорить на языке пар, то произведению пар $(a,b)$ и $(c,d)$ соответствует пара $(ac-bd,ad+bc)$.
 
\dfn[Комплексное сопряжение] У поля $\mb C$ есть автоморфизм, который задан правилом $z=a+bi \to a-bi=\ovl{z}$. Такой автоморфизм называется комплексным сопряжением.
\edfn

\rm Это действительно автоморфизм. Более того это единственный нетривиальный автоморфизм, который оставляет на месте подполе $\mb R$.

\proof По определению поле $\mb C = \mb R[x]/x^2+1$. Тогда любой гомоморфизм $\mb C \to \mb C$ задается гомоморфизмом $\mb R[x]\to \mb C$. Поэтому нам стоит посмотреть на все гомоморфизмы из $\mb R[x]\to \mb C$ и понять, какие из них пропускаются через фактор по $x^2+1$. Нас интересуют только гомоморфизмы сохраняющие вещественные числа на месте. Они задаются образом элемента $x$. Для того, чтобы гомоморфизм переводящий $x \to \lambda$ пропускался через фактор необходимо, чтобы $\lambda^2+1=0$. Но $\mb C$ -- поле и у квадратного уравнения два корня -- $\pm i$. Если мы $x$ отображаем в $i=\ovl{x}$, то получаем тождественное. Иначе $x\to -i$ и тогда элемент $a+bi$ переходит в $a-bi$.
\endproof
\erm
 
\dfn[Модуль комплексного числа] Рассмотрим комплексное число $z=a+bi\in \mb C$. Тогда модулем комплексного числа $z$ назовём выражение
$$|z|=\sqrt{a^2+b^2}=\sqrt{z\ovl{z}}.$$
\edfn

\lm[Формула для обратного] Пусть $z\in \mb C$, $z\neq 0$. Тогда
$$ z^{-1} =\frac{\ovl{z}}{|z|^2}= \frac{a}{a^2+b^2}-i\frac{b}{a^2+b^2}.$$
\elm

Однако наряду со стандартной формой записи есть и другой способ представления комплексного числа.

\dfn[Тригонометрическая форма записи] Рассмотрим ненулевое комплексное число $z= a+bi\in\mb C$. Поделим число $z$ на его модуль. Число
$\frac{z}{|z|}$ лежит на окружности $|z| = 1$. Точки такой окружности имеют вид $\cos\varphi +i\sin\varphi$ для единственного $0 \leq \varphi < 2\pi$. Обозначим выражение $\cos\varphi+i\sin\varphi$ за $e^{i\varphi}$. Тогда $z=|z|e^{i\varphi}$.
Такая запись называется тригонометрической записью комплексного числа. Угол $\varphi$ обозначают $\arg z$ и называют
аргументом комплексного числа.
\edfn


Почему $e^{i\varphi}$ естественно определить как $\cos\varphi+i\sin \varphi$ ? Основная мотивация для этого есть тождество для рядов  (пока мы не говорим про сходимость, то для формальных степенных рядов).
$$\exp(ix) = \sum_{n=0}^{\infty} \frac{(ix)^n}{n!}=\sum_{n=0}^{\infty} \frac{(-1)^n x^{2n}}{2n!} + i\sum_{n=0}^{\infty} \frac{(-1)^n x^{2n+1}}{(2n+1)!}= \cos(x) + i\sin(x).$$
Возможность подставлять в ряды различные значения вместо формальной переменной вы будете долго обсуждать в рамках курса математического анализа. В частности во все указанные ряды можно будет подставить любое комплексное число. Так же, если для рядов было выполнено некоторое тождество, то оно будет верно и для функций, которые они задают.
Нас на текущий момент гораздо больше  интересует то обстоятельство, что экспонента сумму переводит в произведение. Так как никаких особенных средств матанализа у нас в распоряжении нет, то постараемся показать это свойство в нашем конкретном случае руками, а заодно посмотреть геометрически, что же происходит.


Вопрос: что происходит при домножении на комплексное число $\cos \varphi + i \sin \varphi$? Для понимания ответа необходимо небольшое знание геометрии.
\dfn[Расстояние] Расстоянием между комплексными числами $z_1$ и $z_2$ положим равным $|z_1-z_2 |$.
\edfn

\rm Это просто обычное расстояние на плоскости.
\erm

Отображение плоскости, сохраняющее расстояние называется движением или изометрией плоскости. Множество всех изометрий плоскости образует группу относительно композиции. Верен следующий:
\begin{fact} Поворот вокруг точки на некоторый угол есть изометрия плоскости. Изометрия плоскости, имеющая ровно
одну неподвижную точку является поворотом вокруг этой точки.
\end{fact}

\thrm[Геометрическая интерпретация] Пусть $z\in \mb C$ число по модулю равное единице. Тогда $\mb C \to \mb C$ отображение заданное правилом $ x\to zx$   является поворотом вокруг точки 0 на угол $\arg z$.
\ethrm
\proof Пусть $z\neq 1$ (случай $z=1$ соответствует тождественному отображению). Проверим, что домножение на $z$ имеет ровно одну неподвижную точку 0. Действительно, пусть $z_1z=z_1$. Тогда, если $z_1\neq 0$, то получаем $z=1$. Очевидно, домножение на $z$ сохраняет расстояние $$|zz_1-zz_2|=|z(z_1-z_2)|=|z||(z_1-z_2)|=|(z_1-z_2)|.$$
Получается, что домножение на $|z|$ есть поворот. Как узнать угол? Для этого достаточно посмотреть, куда переходит какая-нибудь точка. Например 1. Единица переходит в $z$, то есть точку под углом $\arg z$ к исходной.
\endproof

\crl Пусть $z_1, z_2\in \mb C$  и $z_1,z_2\neq 0$. Тогда $\arg z_1z_2 = \arg z_1 + \arg z_2$ , $|z_1z_2| = |z_1 ||z_2 |$.
\ecrl

\crl[Формула Муавра] Пусть $z\in \mb C$ имеет тригонометрическую запись $z=re^{i\varphi}$. Тогда
$$z^{n}=r^{n}(\cos \varphi +i\sin \varphi )^{n}=r^{n}(\cos n\varphi +i\sin n\varphi ).$$
Эту формулу можно воспринимать, как выражение для косинусов и синусов кратного угла.
\ecrl

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

\thrm[Извлечение корней] Пусть $z\in \mb C$, $z=re^{i\varphi}$, $r>0$ . Тогда у уравнения $x^n=z$ есть ровно $n$ различных
решений в $\mb C$, которые задаются формулой
$$ x_k =\sqrt[n]{r} e^{i\frac{\varphi + 2\pi k}{n}} ,\,\, k\in \ovl{0,n-1}.$$
\ethrm
\proof
Прямой проверкой можно установить, что указанные $x_k$ являются корнями. Необходимо доказать, что они различные. Рассмотрим частное $x_k$ и $x_l$. Это $e^{i\frac{ 2\pi k- 2\pi l}{n}}$. Так как $\frac{k-l}{n}$ не есть целое число, то их отношение не равно единице.
\endproof

\rm Числа вида $e^{i\frac{2\pi k}{n}}$ являются корнями степени $n$ из единицы. 
\erm

\dfn Пусть $K$ -- поле. Тогда $\xi\in K$ -- корень степени $n$ из единицы  называется первообразным корнем степени $n$ если его порядок в $\mb K^*$ ровно $n$ 
\edfn

\rm Элементы $e^{i\frac{2\pi k}{n}}$, где $(k,n)=1$ являются первообразными корнями из единицы в $\mb C$. 
\erm



Иногда в жизни бывает необходимо посчитать какую-то странную сумму. Часто это невозможно сделать, но иногда компактный ответ можно найти. Приведём пример, как комплексные числа могут помочь в подсчёте сумм.
Рассмотрим сумму $1+ \cos x + \cos 2x + \dots + \cos nx$, где $x > 1$. Вопрос состоит в том, чему она равна в зависимости от $n$. Основной трюк здесь --- заменить непонятные вещественные числа, на их улучшенную комплексную версию. Например, $$\cos x = \frac{e^{ix}+e^{-ix}}{2}, \sin x = \frac{e^{ix}-e^{-ix}}{2i}.$$ 
В данном случае, проще заметить, что $\cos x=\re e^{ix}$. Тогда
$$1 + \cos x+ \dots + \cos nx = \re(1+ e^{ix} + \dots + e^{inx}) = \re \frac{e^{i(n+1)x}-1}{e^{ix}-1}$$
Теперь необходимо привести выражение к виду, не содержащему комплексных чисел.
$$\re \frac{e^{i(n+1)x}-1}{e^{ix}-1} = \re e^{i\tfrac{n+1}{2}x}\cdot e^{-i\tfrac{x}{2}}\frac{\sin \tfrac{n+1}{2}x}{\sin\tfrac{x}{2}}= \frac{\cos \tfrac{nx}{2} \sin \tfrac{n+1}{2}x}{\sin\tfrac{x}{2}}$$


При решении задачи очень часто бывает, что сам факт существования того, о чём идёт речь вообще говоря является не очевидным. Например, далеко не каждая функция имеет на отрезке минимум и следовательно задача поиска минимального значения функции может быть просто не корректна. Поэтому важно заранее знать, что предмет исследования есть. Мы уже поняли, чтобы у каждого многочлена в каком-то поле есть корень. Можно немного поднапрячься и понять, что в некотором поле у многочлена есть все корни (то есть число корней с учётом кратности равно степени многочлена). Однако можно спросить, а бывает ли так, что есть поле, такое что каждый многочлен с коэффициентами из этого поля имеет корень?

Ответ — да, такое поле есть. Первый и основной такой пример --- это поле комплексных чисел.
\dfn[Алгебраическая замкнутость] Поле $K$ называется алгебраически замкнутым, если у любого многочлена  $f(x)\in K[x]$, отличного от константы, есть корень в $K$.
\edfn

\thrm[Основная теорема алгебры] Поле $\mb C$ алгебраически замкнуто.
\ethrm

\lm Пусть $f(x)\in \mb R[x]$ имеет комплексный корень $\lambda \notin \mb R$, тогда $f(x)\di(x-\lambda)(x-\ovl{\lambda})$.
\proof Если $\lambda \notin \mb R$, то $\ovl{\lambda}$ тоже корень $p$. Тогда $p(x)\di(x-\lambda)(x-\ovl{\lambda})$ в $\mb C[x]$. Осталось заметить, что последний многочлен вещественный. Заметим, что так как вычисление остатка от деления $p$ на $(x-\lambda)(x-\ovl{\lambda})$ не зависит от того, над $\mb R$ или над $\mb C$ его считать, то имеет место делимость над $\mb R$.
\endproof
\elm

\crl Любой неприводимый многочлен над $\mb R$ либо линеен, либо является многочленом второй степени с отрицательным дискриминантом.
\proof Рассмотрим неприводимый над $\mb R$ многочлен $p(x)$. У него есть комплексный корень $\lambda$. Если $\lambda \in \mb R$, то $p(x)\di (x-\lambda)$ и по неприводимости $p=x-\lambda$.  Если $\lambda \notin \mb C$, то $p(x)\di (x-\lambda)(x-\ovl{\lambda})$ в $\mb R[x]$. Этот многочлен не имеет вещественных корней и, следовательно, имеет отрицательный дискриминант. Обратно, любой линейный многочлен и квадратичный многочлен с отрицательным дискриминантом неприводимы над $\mb R$.
\endproof
\ecrl

\dfn[Алгебраическое замыкание] Пусть $K$ --- поле. Тогда $L$ --- расширение $K$ называется алгебраическим замыканием $K$, если \\
1) $L$ алгебраически замкнуто.\\
2) Для любого $ \lambda \in L$ существует $0\neq p(x)\in K[x]$, что $p(\lambda)=0$.
\edfn

\thrm У любого поля есть алгебраическое замыкание и оно единственно с точностью до изоморфизма.
\ethrm
\proof[Мы не будем доказывать теорему] Отмечу только, что процесс построения алгебраического замыкания более-менее нагляден. А именно надо взять все неприводимые многочлены в $K[x]$, и шаг за шагом увеличивать расширение, добавляя всё новые корни. Завершив этот процесс можно обнаружить, что добавились новые многочлены, которых раньше не было. Значит надо повторить процедуру ещё раз. И ещё раз ... В общем счётное число раз.

Формализовать такое рассуждение можно с помощью аксиомы выбора. 
\endproof

\zd Классифицируйте, чему может быть изоморфно $\mb R[x]/(x^2 + bx +c)$ в зависимости от $b,c$.
\ezd





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

\begin{thmm}[Основная теорема алгебры] Поле $\mb C$ алгебраически замкнуто.
\proof Пусть $f$ — многочлен степени $n\geq 1$ в $\mb C[x]$. Будем считать, что старший коэффициент $f$ равен единице. Пусть у этого многочлена нет корней. Рассмотрим функцию $|f|\colon \mb C \to \mb R$. Эта функция непрерывна и не принимает значения 0. Так как $f$ --- многочлен степени $n$, то на бесконечности $|f|$ растёт. Разберёмся точнее. Пусть
$c = |f(z_0)| > 0$ в некоторой точке $z_0$. Я утверждаю, что вне некоторого круга радиуса $R$ с центом в 0 функция
$|f|$ принимает значения строго больше чем $c$. Действительно возьмём $R= M \max(2,c)$, где $M$ --- сумма модулей всех коэффициентов многочлена $f$. Двойка здесь играет роль числа строго большего единицы.
Тогда для поиска инфимума $|f|$ достаточно ограничиться кругом радиуса $R$. Но круг радиуса $R$ --- компактное множество и непрерывная функция $|f|$ достигает на нём минимальное значение в точке $x_0$. Пусть $a_0 =f(x_0)$ Разложим
$f$ по степеням $(x-x_0)$. Тогда имеем
$$f(x) = a_0 + a_k (x-x_0)^k + \dots + a_n(x -x_0 )^n.$$
Здесь $a_k$ --- первый ненулевой коэффициент после $a_0$. Такой есть потому что иначе $f$ --- это константа. Теперь наша
задача понять, что мы можем немного сдвинуться от точки $x_0$ , так, чтобы значение $|f|$ уменьшилось. В районе точки
$x_0$ самое большое слагаемое в разложении $f$ это $a_0 + a_k (x-x_0)^k$ и оно практически полностью определяет поведение $f$.
У этого многочлена есть корень. Обозначим его за $y_0$. Будем двигаться из $x_0$ в направлении $y_0$ и смотреть, что происходит.
Рассмотрим $x_{\eps} = x_0 + \eps(y_0 -x_0 ), \,\eps < 1$. Тогда $x_{\eps} -x_0 = \eps(y_0 -x_0 )$. Тогда
$$|f(x_{\eps})| = |(1 - \eps^k)a_0 + \eps^{k+1} a_{k+1} (y_0 -x_0)^{k+1} + \dots+ \eps^n(y_0-x_0 )^n | \leq (1- \eps^k )|f(x_0)| + \eps^{k+1}N,$$
где $N$ — это некоторая константа не зависящая от $\eps$. Например, можно взять $N = \sum_{i=k+1}^n |a_i||y_0 -x_0 |^i$. Для достаточно
маленьких $\eps$ выражение $ -\eps^k |f(x_0)| + \eps^{k+1}N$ отрицательно. Тогда для всех достаточно маленьких $\eps>0$ выполнено неравенство $|f(x_{\eps})| < |f(x_0)|$.
Противоречие с минимальностью $|f(x_0)|$. \endproof
\end{thmm}






\section{Производная}
Со школы вам наверняка известно, что кратность корня многочлена ловится с помощью производной. Попробуем в абстрактном
контексте ввести понятие производной многочлена. Для удобства и по причине наличия общих свойств проделаем все выкладки для степенных рядов затем сосредоточившись на применениях к многочленам.


Прежде чем говорить про производную в нашем контексте, вспомним, что многие вычисления производной основаны на умении вычислять производную композиции. Если для многочленов мы знаем, что такое композиция, то для формальных степенных рядов мы этого ещё не определяли.

\dfn Пусть $f(x)=a_0+ a_1x\dots\in K[[x]]$ и $g(x)= b_1x+b_2x^2+\dots \in xK[[x]]$. Тогда определим 
$$f(g)_n= \sum_{k=0}^n a_k\sum_{j_1+\dots+j_k=n} b_{j_1}\dots b_{j_k}.$$
\edfn

Эта формула получилась, если формально подставить $g$ в $f$. От неё мало проку, кроме факта её существования и того, что если $f(x)$ многочлен, то она совпадает с формулой подстановки, которая, конечно определена. Воспользуемся этим и докажем

\lm Пусть $g\in xK[[x]]$. Тогда отображение $f \to f(g(x))$ является гомоморфизмом колец $K[[x]]\to K[[x]]$.
\elm
\proof Пусть $f_1, f_2 \in K[[x]]$. Хотим показать, что $(f_1f_2)(g)=f_1(g)f_2(g)$. Для этого необходимо проверить равенство коэффициентов в правой и левой части. Проверим для $n$-ого. Пусть $f(x)= a_0+a_1x+\dots+a_nx^n+a_{n+1}x^{n+1}+\dots$. Тогда обозначим многочлен 
$$f_{\leq n}(x)=a_0+\dots+a_nx^n.$$
Тогда заметим, что $n$-ый коэффициент $f_1f_2$ равен $n$-ому коэффициенту $f_{1,\leq n}f_{2,\leq n}$. Так же заметим, что $n$-ый коэффициент в $f(g)$ равен $n$-ому в $f_{\leq n}(g)$. Это означает, что теперь необходимо проверить равенство $n$-ых коэффициентов у $(f_{1,\leq n}f_{2,\leq n})(g)$ и $f_{1,\leq n}(g)f_{2,\leq n}(g)$, но эти два ряда просто равны, потому что подстановка в многочлен --- гомоморфизм. \endproof 

\dfn[Формальная производная] Пусть $R$ --- кольцо. Рассмотрим кольцо формальных степенных рядов $R[[x]]$. Формальной производной назовём отображение
$\frac{d}{dx}\colon R[[x]]\to R[[x]]$, заданное по правилу
$$\frac{d}{dx}(a_0+a_1x+a_2x^2+\dots+a_nx^n+\dots) = a_1+2a_2x+3a_3x^2+\dots+na_nx^{n-1}+\dots.$$
Применение производной к ряду $f$ будем так же обозначать как $f'$.
\edfn



Производная обладает обычными свойствами
\lm[Тождество Лейбница и прочее] Пусть $R$ --- кольцо. Тогда отображение взятия производной обладает свойствами:\\
1) Для любых $f,g\in R[[x]]$ выполнено $(f+g)' = f'+g'$.\\
2) Для любых $f\in R[[x]]$ и $a\in R$ справедливо $(af)' = af'$.\\
3) Для любого $a\in R$ верно  $a'= 0$.\\
4) Для любых $f,g\in R[[x]]$ имеет место $(fg)' = f'g+fg'$.\\
5) Для любых $f\in R[[x]]$ и $n\in \mb N$ верно $ (f^n)' = nf'f^{n-1}$.\\
6) Для любых $f\in R[[x]]$, $g\in xR[[x]]$ верно $f(g(x))' = g'(x)f'(g(x))$.\\
7) Для любого $f\in R[[x]]^*$ верно $(f^{-1})'=-\frac{f'}{f^2}$.
\elm
\proof Свойства 1),2),3) очевидны. Теперь будем доказывать оставшиеся свойства следующим образом: докажем их для многочленов, а потом покажем, что так как равенство для рядов достаточно проверять  покоэффициентно, то ряд можно заменить на свой начальный кусок, который является многочленом.\\
Итак докажем 4). Пусть $f$ и $g$ --- многочлены. Заметим, что правая и левая часть линейны по $f$ и $g$. Таким образом достаточно доказать только для степеней. Распишем $(x^{n+m})'=(n+m)x^{n+m-1}=nx^{n-1}x^{m}+mx^{m-1}x^n=(x^n)'x^m+(x^{m})'x^n$.

Теперь заметим, что если $f$ и $g$ ряды, то коэффициенты при $x^n$ справа и слева не зависят от коэффициентов при степенях больше $n+1$ в $f$ и $g$. \\
5) Докажем индукцией по $n$. $(f^n)'=(f\cdot f^{n-1})'=f'f^{n-1}+f(n-1)f'f^{n-2}=nf'f^{n-1}$.\\
6) Прежде всего коэффициент $n$-ой степени справа и слева не меняется если $f$ заменить на $f_{\leq n+1}$. Заменим. Теперь заметим, что обе части линейны по $f$ и поэтому можно проверять только для $f=x^n$. Это пункт 5).\\
7) Рассмотрим тождество $ff^{-1}=1$ и продифференцируем его. Перенеся одно слагаемое направо получим $(f^{-1})'f=-f'f^{-1}$. Осталось поделить на $f$. 
\endproof

Итак, оставим в памяти, что производная определена для любых рядов и перекинемся на многочлены. Кажется сейчас у нас появится первое утверждение, которое зависит от характеристики кольца.

\thrm Если многочлен $f(x) \in K[x]$ делится на $p(x)^l$ то $f'(x) \di p(x)^{l-1}$. Более того, если $p(x)$ неприводим, $\chr K > \deg f$ или $\chr K=0$,а $l$ -- наибольшая степень, что $f(x) \di p(x)$, то $f'(x)\ndi p(x)^{l}$. 
\proof Пусть $f(x)=p(x)^lg(x)$. Тогда $$f'(x)=lp(x)^{l-1}p'(x)g(x)+p(x)^lg'(x)=p(x)^{l-1}(lp'(x)g(x)+p(x)g'(x)) \di p(x)^{l-1}.$$
Пусть теперь $g(x)$ и $p(x)$ взаимно просты, $p(x)$ неприводим, а $\chr K > \deg f$ или $\chr K=0$. Наша задача доказать, что последний сомножитель взаимнопрост с $p(x)$ в указанных условиях. Вопрос сводится к взаимной простоте $lp'(x)$ и $p(x)$. Заметим, что если $lp'(x)$ не 0, то он действительно взаимнопрост с $p(x)$ так как $p(x)$ неприводим. Понятно, что в условиях теоремы $l\neq 0$. Следовательно надо рассмотреть ситуацию, когда $p'(x)=0$. 
\lm Пусть $\chr K=p$, $f(x)\in K[x]$. Тогда $f'(x)=0$ в том и только том случае, когда $f(x)=h(x^p)$.
\elm
\proof
Заметим, что коэффициенты $f'(x)$ имеют вид $c_{i-1}=ia_{i}$. Следовательно, $a_{i}$ может не равняться нулю только тогда, когда $i\di p$. Тогда возьмём $h(x)=\sum_{i=0}^{\deg f/p} a_{ip}x^i$.
\endproof
Таким образом, если предположить, что $p'(x)=0$, то степень $p(x)=h(x^q)$, где $q=\chr K$, должна быть заведомо больше характеристики, что мы исключили по условию. Видно, что в формулировке теоремы можно ещё много уточнить. Сделайте это сами.
\endproof
\ethrm



\noindent {\bf Пример:} Вот пример многочлена, у которого проблемы с кратностью корня у производной: $x^{p}$ в $\mb Z/p$.

Обсудим ещё одно важное свойство производной. Для этого нам потребуется доказать некоторую лемму.

\lm[О разложении по основанию] Пусть $p$ -- многочлен из $K[x]$, $\alpha\in \mb N$, а $h$ многочлен c $\deg h< \alpha \deg p$. Тогда существуют единственный $h_0, \dots, h_{\alpha-1} \in K[x]$, что $\deg h_i< \deg p $ и 
$$h=\sum_{i=0}^{\alpha-1} h_i p^i.$$
\elm
\proof Индукция по $\alpha$. $\alpha=1$ --- тогда $h=h_0$. Теперь $\alpha>1$.  Пусть $h=qp+h_0$. $q$ раскладывается как $\sum_{i=1}^{\alpha-2} q_i p^i$. Ясно, что получили разложение. С другой стороны, очевидно, что в любом разложении $h_0$ это остаток от деления, а $\sum_{i=1}^{\alpha-1} h_ip^{i-1}$ --- это неполное частное.  По индукции мы знаем, что разложение неполного частного по основанию единственно. 
\endproof

Рассмотрим простейший неприводимый многочлен $x-a \in K(x)$. Тогда многочлены в формуле из предыдущей теоремы есть просто элементы поля $K$. Вопрос состоит в том, как найти эти коэффициенты в разложении по степеням $x-a$?

\thrm[Формула Тейлора для многочленов]
Пусть $h$ элемент $K(x)$, $\chr K =0$, и $\deg h=n$. Тогда имеет место формула
 $$h(x)= h(a)+h'(a)(x-a)+\frac{h''(a)}{2}(x-a)^2+
 \dots + \frac{h^{(n)}(a)}{n!}(x-a)^n.$$
\proof По предыдущей теореме у нас есть разложение 
$$h(x)=a_0+a_1(x-a)+\dots+a_n(x-a)^n.$$
Возьмём $k$-ую производную от обеих частей равенства. Получим
$$ h^{(k)}(x)=k!a_k+(k+1)!a_{k+1}(x-a)+\dots+\frac{n!}{k!}a_n(x-a)^{n-k}.$$
Осталось подставить $x=a$.
\endproof
\ethrm


\section{Интерполяция}

Довольно часто требуется решить следующую задачу: пусть $K$ --- некоторое поле. Пусть дан набор различных точек
$x_1,\dots, x_n \in K$ и дан набор значений $a_1,\dots,a_n\in K$. Требуется построить многочлен $f\in K[x]$, такой что $f(x_i)=a_i$.
Прежде всего заметим, что у нас есть некоторая свобода выбора. А именно, рассмотрим многочлен $\phi(x)=(x-x_1)\dots(x-x_n)$. Тогда можно к любому решению интерполяционной задачи прибавить кратное многочлена $\phi(x)$ и снова получить решение интерполяционной задачи. Таким образом можно любое решение заменить на остаток от деления на многочлен $\phi(x)$. В частности, если есть какое-то решение, то есть решение степени строго меньше $n$.

\dfn[Задача интерполяции] Пусть дан набор различных точек $x_1,\dots,x_n\in K$ и дан набор значений
$a_1,\dots, a_n\in K$. Требуется построить многочлен $f\in K[x]$, такой что $f(x_i)=a_i$ и $\deg f < n$.
\edfn

\thrm Задача интерполяции разрешима и притом единственным образом. Более того её решение может быть найдено по формуле
$$f(x)=\sum_{i=1}^n a_i\frac{\prod_{j\neq i}(x-x_j)}{\prod_{j\neq i } (x_i-x_j)}=\sum_{i=1}^n \frac{a_i\phi(x)}{\phi'(x_i)(x-x_i)},$$
где $\phi(x)=(x-x_1)\dots(x-x_n)$.
\ethrm

\proof Заметим, что $\phi'(x_i)=\prod_{j\neq i}(x_i-x_j)$. Теперь очевидно, что указанная формула даёт решение нужной степени. Единственность очевидна из теоремы о многочленах, совпадающих в достаточном числе точек.
\endproof

Последняя формула называется интерполяционной формулой Лагранжа. Так же есть способ Ньютона для решения интерполяционной задачи.
Он позволяет добавлять точки постепенно.


Рассмотрим более общий вариант интерполяционной задачи. А именно попробуем решить задачу следующего вида.
Пусть задан набор точек $x_1,\dots, x_n$ и для каждой точки $x_i$ задан набор чисел $a_{i,0}, a_{i,1},\dots , a_{i,k_i}$ . Интерполяционная задача состоит в следующем: найти $f$ такой, что $j$-тая производная $f^{(j)}(x_i)=a_{i,j}$. Заметим, что решение можно свободно поменять на кратное многочлена
$$\phi(x)=\prod_{i=1}^n (x-x_i)^{k_i} ,$$
следовательно, степень решения $f$ можно ограничить $\deg f < \sum_{i=1}^n k_i$. Такая задача интерполяции называется задачей интерполяции по Эрмиту.



\thrm Пусть $K$ --- поле характеристики 0 (или достаточно большой положительной характеристики). Решение задачи интерполяции по Эрмиту существует и единственно среди многочленов степени меньше $\sum_{i=1}^n k_i$.
\ethrm
\proof Сведём задачу к китайской теореме об остатках. А именно пусть $f(x)$ многочлен. Тогда значения его производных в точке $x_i$ равны $a_{i,j}$ $j\in \ovl{0,k_i-1}$ тогда и только тогда, когда 
$$f(x)\equiv a_{i,0}+a_{i,1}(x-x_i)+a_{i,2}\tfrac{(x-x_i)^2}{2!}+\dots+ a_{i,k_i}\tfrac{(x-x_i)^{k_i-1}}{(k_i-1)!}\,\, (\mod (x-x_i)^{k_i}).$$
Идеалы $(x-x_i)^{k_i}$ взаимно простые.
\endproof

\rm Вообще для  задачи интерполяции по Эрмиту тоже есть формула, но она не сильно хороша (см. Кострикин, Сборник задач по алгебре, стр 93, задача 30.14 ).\erm


Давайте представим себе, что мы хотим перемножить два многочлена. Если действовать по определению, то понадобится $O(n^2)$ операций сложения и умножения. С другой стороны, мы знаем, что оба многочлена и их произведение однозначно определяются своими значениями в точках $x_1,\dots, x_n$ для достаточно большого $n$. Однако перемножить значения гораздо проще! Таким образом, если мы научимся быстро конвертировать многочлен в набор значений в $x_1,\dots, x_n$ и обратно (то есть решать интерполяционную задачу), то мы сможем быстро перемножать многочлены. При этом у нас есть свобода выбора $x_1,\dots, x_n$. 

При произвольном выборе точек $x_i$ сложность задач интерполяции и подстановки $n$ точек есть $O(n^2)$. Однако, оказывается, что в определённых случаях можно подобрать такие $x_i$, что и задача интерполяции и задача о подстановке точек будет иметь сложность $O(n\log n)$. 

\dfn Элемент  $\omega \in R$ называется первообразным корнем  степени $n$ из единицы, если $\omega$ -- корень степени $n$ из $1$-цы и $1-\omega^i$ не делитель нуля при $i\nequiv 0(\mod n)$.
\edfn




Рассмотрим упорядоченную $n$-ку $x=(a_0,\dots,a_{n-1})\in R^n$. Рассмотрим следующий набор $F(x)=(b_0,\dots,b_{n-1})\in R^n$ 
$$b_i=\sum_{j=0}^{n-1} a_j \omega^{ij}.$$

Отображение $x \to F(x)$ из $ R^n \to R^n$ называется дискретным преобразованием Фурье. Где находится связь между этим преобразованием и задачей интерполяции? Давайте посмотрим на строку $(a_0,\dots,a_{n-1})$ как на коэффициенты многочлена $f$ из $R[x]$. Тогда элемент $b_i=f(\omega^i)$.

Оказывается, что обратное отображение обычно есть и имеет очень простой вид: 

\lm Пусть $n\in \mb N$ некоторое натуральное число, а $R$ --- кольцо, такое что $n\in R^*$. Тогда $F^{-1}(b)_i=\frac{1}{n}\sum_{j=0}^{n-1} b_j \omega^{-ij}$
\elm 
\proof Достаточно доказать, что $F^{-1}(F(a))=a$. Подставим.
$$F^{-1}(F(a))_i=\frac{1}{n}\sum_{j=0}^{n-1} \sum_{k=0}^{n-1} a_k \omega^{jk} \omega^{-ij}=\sum_{k=0}^{n-1} a_k \cdot \frac{1}{n}\sum_{j=0}^{n-1} \omega^{j(k-i)}.$$

Заметим, что при $k=i$ коэффициент будет равен $\frac{1}{n}\sum_{j=0}^{n-1} \omega^{0}=1$. Вспомним, что по условию если  $k-i\neq 0$, то  $1-\omega^{k-i}$ не делитель нуля. Тогда заметим, что 
$$\sum_{j=0}^{n-1}\omega^{j(k-i)}=\omega^{k-i}\sum_{j=0}^{n-1} \omega^{(j-1)(k-i)}=\omega^{k-i}\sum_{s=0}^{n-1} \omega^{s(k-i)}=\omega^{k-i}\sum_{j=0}^{n-1} \omega^{j(k-i)}.$$
Так как $1-\omega^{k-i}$ не делитель нуля,то  $\sum_{j=0}^{n-1}\omega^{j(k-i)}=0$.
\endproof

Перейдём теперь к алгоритму быстрого вычисления значений в указанных корнях из 1-цы. Этот алгоритм называется быстрым преобразованием Фурье. 

\thrm Пусть $n=2^k$ и $\omega \in R$ первообразный корень степени $n$ из 1-цы. Тогда дискретное преобразование Фурье можно провести за $O(n\log n)$ операций.
\ethrm
\proof Для начала сделаем замечание: в описанных выше условиях $\omega^{\frac{n}{2}}=-1$. Действительно $0=\omega^n-1=(\omega^{\frac{n}{2}}-1)(\omega^{\frac{n}{2}}+1)$. Осталось заметить, что по условию $(\omega^{\frac{n}{2}}-1)$ не делитель нуля.

Теперь приведём алгоритм дискретного преобразования Фурье. Вспомним, что если дан многочлен $f(x)$, то посчитать его значение в точке $a$ это тоже самое, что посчитать остаток от деления $f$ на $x-a$. Нам нужно посчитать остатки от деления на $x-\omega^i$ по всем $0\leq i\leq n-1$. Заметим, что так как $\omega^{\frac{n}{2}}=-1$, то
$$x^{2^k}-1=(x^{2^{k-1}}-1)(x^{2^{k-1}}+1)=(x^{2^{k-1}}-\omega^0)(x^{2^{k-1}}-\omega^{2^{k-1}}).$$

Более общо $x^{2^i}-\omega^{2j}=(x^{2^{i-1}}-\omega^j)(x^{2^{i-1}}-\omega^{j+\frac{n}{2}})$. В частности, применив указанное соображение $k$ раз получаем  
$$\prod_{i=1}^n(x-\omega^i)=x^n-1.$$

Таким образом, видно, что можно последовательно делить с остатком многочлен $f$ на многочлены $x^{2^{k-i}}-\omega^{j2^{k-i}}$, $0\leq j < 2^i$. То есть на шаге $i$ необходимо будет поделить многочлены степени $2^{i+1}$ на $2^{i}$ многочленов специального вида. Чтобы понять, что это можно легко сделать докажем лемму. 

\lm Пусть многочлен $f(x)=\sum_{i=0}^{n-1} a_ix^i$. Тогда остаток от деления многочлена $f(x)$ на $x^{\frac{n}{2}}-c$ находится по формуле
$$r(x)=\sum_{i=0}^{\frac{n}{2}-1}(a_i+ca_{i+\frac{n}{2}})x^{i}. $$
В частности для вычисления указанного остатка необходимо $\frac{n}{2}$ умножений и $\frac{n}{2}$ сложений
\elm 
\proof Очевидно верна формула
$$f(x)=(x^{\frac{n}{2}}-c)\sum_{i=0}^{\frac{n}{2}} a_{\frac{n}{2}+i}x^i+r(x).$$
\endproof
 Итого в нашем случае необходимо 
$$n+2\frac{n}{2}+4\frac{n}{4}+\dots+2^k\frac{n}{2^k}=nk$$
умножений и сложений  в кольце $R$.
\endproof


\section{Локализация, поле частных и разложение на простейшие дроби}

Наша задача под конец этого раздела понять, как свести некоторые вопросы про общие кольца к вопросам о полях. Однако по пути мы захватим конструкцию, в некотором смысле противоположенную факторизации, которая позволяет <<упростить>> кольцо.

Все мы довольно хорошо знакомы с рациональными числами. Целые числа вкладываются в рациональные. Поэтому
многие вопросы про целые числа можно свести к рациональным. Например, допустим мы знаем, что многочлен
степени $n$ над $\mb Q$ имеет не более чем $n$ корней. Тогда мы автоматически знаем это и для целочисленных многочленов.
Достаточно просто проинтерпретировать их как многочлены с рациональными коэффициентами, а потом сказать, что
если в $\mb Q$ мало корней, то в $\mb Z$ и подавно.
Рациональные числа отличаются от целых тем, что необратимые элементы $\mb Z$ уже обратимы в $\mb Q$. Попробуем понять, можно
ли насильно обратить некоторое множество элементов. Представим себе, что мы насильно обратили два элемента $f$ и
$g$. Тогда мы так же обратили их произведение $fg$. Для простоты рассмотрим ситуацию над областью целостности, хотя разумный ответ есть и в общем случае. Далее в этом разделе $R$ --- область целостности.

\dfn[Мультипликативная система] Пусть $R$ --- область целостности. Мультипликативной системой  в $R$ называется
подмоноид $U$ в моноиде $(R\setminus\{0\},\cdot)$.
\edfn

\exm\\
1) Пусть $f\in R$. Тогда множество $\{1,f,f^2,f^3,\dots\}$ очевидно является мультипликативной системой.\\
2) Пусть $R$ --- область целостности. Тогда $R\setminus \{0\}$ является мультипликативной системой.\\
3) Более общо. Пусть дан простой идеал $p$. Тогда $U=R\setminus p$ есть мультипликативная система.\\

Дадим теперь следующее определение
\dfn[Локализация] Пусть $U$ --- мультипликативная система в $R$. Определим кольцо $R[U^{-1}]$ как
фактор множества дробей (формально --- пар)
$$ R[U^{-1}]=\{ \tfrac{a}{u}\,|\, a\in R, \, u\in U\}/\sim$$
профакторизованное по отношению эквивалентности $\sim$, заданного правилом
$$ \tfrac{a}{u}\sim \tfrac{b}{v}, \text{ если } av=bu.$$
Операции сложения и умножения введём подобно рациональным числам:
$$ \tfrac{a}{u}+\tfrac{b}{v}=\tfrac{av+bu}{uv} \text{ и } \tfrac{a}{u}\cdot\tfrac{b}{v}=\tfrac{ab}{uv}.$$
\edfn




\thrm[Конструкция работает] Пусть $U$ --- мультипликативная система в $R$. Тогда все операции на множестве $R[U^{-1}]$ корректно определены и вместе с ними $R[U^{-1}]$ становится кольцом.
\ethrm
\proof
Прежде всего необходимо проверить, что указанное отношение действительно есть отношение эквивалентности. Проверим транзитивность. Пусть $av=bu$ и $bw=cv$. Тогда $avbw=cvbu$. Сократим на $vb$. 

Теперь перейдём к корректности операций. Рассмотрим сумму. Пусть $\tfrac{a}{u}\sim \tfrac{a'}{u'}$, а  $\tfrac{b}{v}=\tfrac{b'}{v'}$. Тогда сумма 
$$\tfrac{a'v'+b'u'}{u'v'}\sim \tfrac{uva'v'+uvb'u'}{uvu'v'}= \tfrac{au'vv'+bv'u'u}{uvu'v'}\sim \tfrac{av+bu}{uv}.$$
Произведение --- ещё проще. 

Докажем ассоциативность сложения. Пусть даны дроби $\tfrac{a}{u}$, $\tfrac{b}{v}$, $\tfrac{c}{w}$. Приведём их к общему знаменателю. Тогда ассоциативность следует из ассоциативности для кольца $R$. Остальные свойства --- так же. 
\endproof



\thrm[Область целостности вкладывается в свою локализацию] Пусть $U$ мультипликативная система в области целостности $R$. Отображение $i\colon R\to R[U^{-1}]$ заданное по правилу $a\to \tfrac{a}{1}$ является инъективным гомоморфизмом колец.
\ethrm
\proof Исходя из формул для локализации видно, что это гомоморфизм. Докажем инъективность. Пусть дробь $\tfrac{a}{1}\sim \tfrac{0}{r}$. Тогда $ra=0$. Так как $r\neq 0$, то $a=0$. чтд.
\endproof

%\rm Если $R$ область целостности $U\subseteq R\setminus \{0\}$, то в определении отношения эквивалентности условие $\exists s\in U sav=abu$  можно заменить просто на $av=bu$.
%\erm

%\lm[Область целостности вкладывается в свою локализацию] Пусть $R$ --- область целостности, $U$ --- 
%мультипликативная система в $R$, которая не содержит $0$. Тогда $i\colon R \to R[U^{-1}]$ является мономорфизмом.
%\elm

%\lm[Описание идеалов] Пусть $U$ --- мультипликативная система в $R$. Тогда имеет место взаимно-однозначное
%соответствие 
%$$\{I \leq R\, | \,\forall u\in U, \text{ $u$ не является делителем нуля в } R/I\} \cong \{I \leq R[U^{-1}]\}.$$
%\elm

\thrm[Универсальное свойство] Пусть $R,S$ кольца и $U$ --- мультипликативная система в $R$. Тогда для любого гомоморфизма $\psi \colon R\to S$, такого что $\forall u\in U \,\,\psi(u)$ обратим, существует единственный гомоморфизм $\phi\colon R[U^{-1} ] \to S$ такой, что треугольник коммутативен:
\begin{center}
\begin{tikzpicture}
\node (A) at (0, 0) {$R$};
\node (B) at (2.5, 0) {$S$};
\node (C) at (0, -1) {$R[U^{-1}]$};
\path[->,font=\scriptsize,>=angle 60]
(A) edge node[above]{$\psi$} (B)
(A) edge node[right]{$i$} (C);
\path[dashed,->,font=\scriptsize,>=angle 60]
(C) edge node[below]{$\exists !\, \phi$} (B);
\end{tikzpicture}
\end{center}
\ethrm
\proof
Как всегда начнём с единственности. Вместо дроби $\tfrac{a}{1}$ буду писать просто $a$. Рассмотрим дробь $\tfrac{a}{u}=au^{-1}$. Тогда $\phi(au^{-1})=\phi(a)\phi(u)^{-1}=\psi(a)\psi(u)^{-1}$. Значит вариантов нет.

Теперь надо показать, что отображение, заданное правилом
$$\phi(\tfrac{a}{u})=\psi(a)\psi(u)^{-1}$$
корректно задано и является гомоморфизмом. Проверка прямолинейна.
\endproof

\dfn[Поле частных] Пусть $R$ --- область целостности. Возьмём $U=R\setminus \{0\}$. Тогда кольцо $R[U^{-1}]$ является полем. Обозначим это поле $Q(R)$. Будем называть его полем частных $R$.
\edfn

Например $\mb Q$ --- поле частных $\mb Z$.

\lm Пусть $U$ --- мультипликативная система в области целостности $R$. Тогда $R[U^{-1}]$ вкладывается в $Q(R)$.
\elm
\proof
Из $R[U^{-1}]\to Q(R)$ есть единственный гомоморфизм по универсальному свойству. Пусть он переводит дробь $\frac{f}{g}$ в $0$. Тогда он переводит $f\in R$ в ноль. Тогда  $f=0$ по теореме о вложении. Получили инъективность.
\endproof

\dfn[Локализация в простом идеале] Пусть $R$  --- область целостности, $p$ --- простой идеал. Определим кольцо $R_p= R[U^{-1}]$, где $U=R\setminus p$.
\edfn

Например, множество всех рациональных чисел, знаменатель которых не делится на $p$, обозначается $\mb Z_{(p)}$ --- является локализацией кольца $\mb Z$ в идеале $(p)$. Из кольца $\mb Z_{(p)}$ всегда есть отображение в $\mb Z/p$ по универсальному свойству. Как это может пригодиться?

Рассмотрим задачу: дана сумма $1+\frac{1}{2}+\dots+\frac{1}{p-1}$, где $p>2$ простое. Покажите, что числитель этой дроби делится на $p$. Заметим, что указанная сумма есть элемент $\mb Z_{(p)}$ . Отправим эту сумму в $\mb Z/p$. Тогда это будет сумма всех обратных элементов, то есть просто сумма всех элементов кроме 0. Она равна $\frac{p(p-1)}{2}$, то есть $0$ в $\mb Z/p$. Но тогда числитель исходной дроби переходит в ноль, то есть делится на $p$.



Конструкция поля частных бывает полезна в теоретических построениях. Например, когда мы применяем приём <<замены коэффициентов>>.

\thrm У многочлена $f$ в области целостности не более чем $\deg f$ различных корней с учётом кратности. \ethrm 
\proof Пусть корни $f$ в $R$ это $x_0,\dots,x_k$ и их кратности это $\alpha_0,\dots,\alpha_k$. Вложим кольцо $R[x]$ в $Q(R)[x]$. Очевидно, что если $f\di (x-x_i)^{\alpha_i}$ над $R$, то $f\di (x-x_i)^{\alpha_i}$ над $Q(R)$. Но тогда $f\di \prod (x-x_i)^{\alpha_i}$ в $Q(R)[x]$. Тогда $  \sum \alpha_i \leq \deg f $, а степень очевидно не меняется.
\endproof



\dfn[Поле рациональных функций] Пусть $K$ --- поле. Тогда $Q(K[x])$ называется полем рациональных функций. Обозначается оно как $K(x)$.
\edfn

\dfn Пусть $R$ область целостности и $0\neq f\in R$. Пусть $U=\{1,f,f^2,\dots\}$. Тогда $R[U^{-1}]$ обозначается $R[f^{-1}]$ и
называется локализацией $R$ по элементу  $f$.
\edfn

\dfn[Многочлены Лорана] Пусть $K$ --- поле. Тогда $K[x][x^{-1}]$ называется кольцом многочленов Лорана. Обозначается как $K[x,x^{-1}]$.
\edfn

\dfn[Ряды Лорана] Пусть $K$ --- поле. Тогда $Q(K[[x]])=K[[x]][x^{-1}]$ называется полем рядов Лорана. Обозначается как $K((x))$.
\edfn

\rm Поле $K(x)$ естественным образом вкладывается в $K((x))$ по универсальному свойству.
\erm

Поговорим о специальных свойствах поля $K(x)$. Это поле в целом напоминает поле рациональных чисел, так как является полем частных евклидового кольца.

\lm Пусть $\frac{f}{g} \in K[x]$. Тогда существуют  единственные с точностью до константы многочлены  $h,r$, что $\Nod(h,r)=1$ и $\frac{f}{g}=\frac{h}{r}$. Такие дроби называются несократимыми.
\elm
\proof Возьмём какие-то $f,g$ и рассмотрим $d=\Nod(f,g)$. Тогда $h=\frac{f}{d}$, а $r=\frac{g}{d}$ подходят. Пусть есть две пары $h,r$ и $h',r'$ подходящие по условию. Тогда $hr'=h'r$. Так как $h$ и $r$ взаимно просты выполнено $h\di h'$. Симметрично $h'\di h$. Тогда $h=ch'$, где $c\in K$. Тогда $r=cr'$.
\endproof

\dfn Дробь $\frac{f}{g} \in K(x)$ называется правильной, если $\deg f< \deg g$. 
\edfn

\lm Любая дробь $\frac{h}{g}\neq 0$ единственным образом представляется в виде суммы многочлена $f(x)\in K[x]$ и правильной дроби $\frac{h_1}{g_1}$, где $\frac{h_1}{g_1}$ несократимая дробь и старший коэффициент $g_1$ равен 1. При этом, если $\frac{h}{g}$ несократима, то можно считать, что $g_1=cg$ для некоторого $c\in K$
\proof Покажем существование. Сделаем дробь $\frac{h}{g}$ несократимой и старший коэффициент $g$ равным 1 поделив верх и низ на старший коэффициент. Поделим с остатком $h(x)=q(x)g(x)+h_1(x)$, где $\deg h_1(x)<\deg g(x)$. Тогда 
$$\frac{h(x)}{g(x)} =\frac{q(x)g(x)+h_1(x)}{g(x)} =q(x)+\frac{h_1(x)}{g(x)}.$$
Покажем единственность. Пусть 
$$f_1(x)+\frac{h_1}{g_1}=f_2(x)+\frac{h_2}{g_2}.$$
Имеем равенство многочленов. 
$$(f_1(x)-f_2(x))g_1(x)g_2(x)=g_1(x)h_2(x)-h_1(x)g_2(x).$$
Если $f_1\neq f_2$, то степень многочленов справа строго меньше степени многочлена слева. Таким образом $f_1=f_2$, а $\frac{h_1}{g_1}=\frac{h_2}{g_2}$. По единственности несократимой записи $h_1=h_2$ и $g_1=g_2$.
\endproof
\elm

\rm Сумма двух правильных дробей -- снова правильная дробь.
\erm

\dfn[Простейшие дроби] Пусть $K$ --- поле, $p\in K[x]$ --- неприводимый многочлен со страшим коэффициентом единица. Тогда дробь
$$\frac{f(x)}{p(x)^{k}} \text{ называется простейшей, если $f \neq 0$ и $\deg f < \deg p$}. $$
\edfn



\thrm[О разложении на простейшие] Пусть $K$ ---  поле. Тогда для любой несократимой дроби $0
\neq \frac{f}{g} \in K(x)$ существуют единственные многочлен $h\in K[x]$, неприводимые многочлены $p_1, \dots, p_n$ со старшим коэффициентом 1, натуральные числа $\alpha_1,\dots, \alpha_n$ и многочлены $h_{ij}$, где $i\in \ovl{1,n}$, и $j\in \ovl{0,\alpha_i}$, что дроби
$$ \frac{r_{ij}}{p_i^{j}} \text{ --- простейшие и } \frac{f}{g}=h+\sum_{i,j} \frac{r_{ij}}{p_i^{j}}.$$
При этом, если  $r_{i\alpha_i}$ не ноль и старший коэффициент $g$  равен 1, то $g=\prod p_i^{\alpha_i}$.
\ethrm

\proof Докажем существование разложения. Если $g(x)=p(x)^{\alpha}$, то разложение можно получить следующим способом -- надо представить дробь $\frac{f(x)}{g(x)}= h(x)+\frac{r(x)}{g(x)}$ в виде многочлена и правильной дроби, а затем разложить по основанию $p(x)$ числитель  $r(x)=\sum_{j=1}^{\alpha} r_{j}p(x)^{\alpha-j} $, где $\deg r_i < \deg p(x)$. Теперь получаем, что 

$$\frac{f(x)}{g(x)}= h(x)+\sum \frac{r_j(x)}{p^j(x)}$$

Это отличная база для индукции по степени многочлена в знаменателе (или по числу различных неприводимых делителей знаменателя). Допустим, что многочлен $g(x)$ раскладывается на взаимно простые множители $g=g_1g_2$, где $\Nod(g_1,g_2)=1$. Представим $a(x)g_1+b(x)g_2=1$. Тогда, конечно, $f(x)=f(x)a(x)g_1+f(x)b(x)g_2$. Подставляя в дробь, получим

$$\frac{f(x)}{g(x)}=  \frac{f(x)a(x)}{g_2(x)}+\frac{f(x)b(x)}{g_1(x)}.$$
Знаменатели явно уменьшились в степени.\\
Покажем единственность. Возьмём $g$ таким, что его старший коэффициент равен 1. Итак пусть
$$\frac{f}{g}=h+\sum_{i,j} \frac{r_{ij}}{p_i^{j}},$$
где $r_{i\alpha_i}$ не ноль (можно так считать, выкинув нулевые слагаемые с большей степенью $p_i$ в знаменателе).

Прежде всего заметим, что $$\sum_{i,j} \frac{r_{ij}}{p_i^{j}}$$ 
правильная дробь. Тогда $h$ определяется однозначно из единственности представления дроби в виде суммы многочлена и правильной дроби. Заменяя $f$ на $f-gh$ можем считать, что дробь $\frac{f}{g}$ правильная. Теперь  покажем, что  $g=\prod p_i^{\alpha_i}$. Введём обозначение $$r_i= \sum r_{ij} p_i^{\alpha_i-j}.$$
Приведя правильную дробь справа ($h$ больше нет) к общему знаменателю получим дробь $$\frac{\sum_{i} r_{i}\prod_{k\neq i} p_k^{\alpha_{k}}}{\prod p_i^{\alpha_{i}}}.$$
Покажем, что эта дробь несократима. Выберем некоторый элемент $p_l$ и покажем, что числитель не делится на $p_l$. Слагаемые вида $$r_{i} \prod_{k\neq i} p_k^{\alpha_{k}}$$ делятся на $p_l$, если $l \neq i$. С другой стороны, $r_l$ не делится на $p_l$, так как $r_{l\alpha_l}$ не делится (потому что он не ноль и степени меньше $\deg p_l$). Тогда и вся сумма не делится на $p_l$. 
Теперь $\prod p_i^{\alpha_i}=g$ из единственности несократимой записи  дроби, а $$f=\sum_{i} r_{i}\prod_{k\neq i} p_k^{\alpha_{k}}.$$ 
Тогда 
$$f\equiv r_{i}\prod_{k\neq i} p_k^{\alpha_{k}} \mod p_i^{\alpha_i},$$
откуда, пользуясь обратимостью $\prod_{k\neq i} p_k^{\alpha_{k}} $ по модулю $p_i^{\alpha_i}$, получаем

$$r_i \equiv f \left(\prod_{k\neq i} p_k^{\alpha_k}\right)^{-1} \!\! \!\! \!\! \mod p_i^{\alpha_i}.$$ Из этого соотношения $r_i$ определяется однозначно, так как его степень меньше $\deg p_i^{\alpha_i}$. Чтобы восстановить $r_{ij}$ надо $r_i$ разложить по основанию $p_i$. Такое разложение единственно по лемме.
\endproof

\zd Какой аналог у последней теоремы в рациональных числах?
\ezd

Рассмотрим теперь конкретные поля $\mb C$. Так как поле $\mb C$ алгебраически замкнуто, то все неприводимые многочлены над $\mb C$ имеют степень 1. Это заметно упрощает жизнь, так как в числителе простейшей дроби могут стоять только константы. 

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

Рассмотрим рациональную функцию $\frac{1}{x^{n}-1}$. Я хочу найти её разложение на простейшие над $\mb C$. Корни  многочлена $x^{n}-1$ нам известны --- это $x_l=e^{\tfrac{2i \pi l}{n}}$, $l\in \ovl{0,n-1}$, они без кратностей. Многочлен $g(x)=1$ восстанавливается по своим значениям в точках  $e^{\tfrac{2i \pi l}{n}}$ по формуле Лагранжа
$$1=\sum_{l=0}^{n-1} \frac{ \prod_{i\neq l} (x-x_i)}{nx_l^{n-1}}.$$
Тогда 
$$\frac{1}{x^{n}-1}=\frac{\sum_{l=0}^{n-1} \frac{ x_l\cdot \prod_{i\neq l} (x-x_i)}{n}}{x^{n}-1}= \sum_{l=0}^{n-1} \frac{x_l}{n(x-x_l)}.$$



\section{Степенные ряды как производящие функции}


\dfn[Линейное рекуррентное соотношение] Будем говорить, что последовательность $x_n$ удовлетворяет линейному рекуррентному соотношению $k$-го порядка, если существуют числа $a_0,\dots,a_{k}$, что $a_k,a_0\neq 0$ и 
$$a_k x_{n+k}+a_{k-1}x_{n+k-1}+\dots+a_0x_n=0$$
\edfn


\rm Вообще говоря, ничто не мешает считать, что начальные коэффициенты $a_0,\dots,a_s=0$. Просто это означает, что до номера $k+s$ последовательность может быть любой, а после $k+s$ начинает удовлетворять соотношению с коэффициентами $a_{s+1},\dots,a_k$.
\erm

\dfn[Производящая функция] Пусть дана последовательность $a_n$, $n\geq 0$. Производящей функцией для последовательности $a_n$ назовём формальный степенной ряд $f(x)=\sum_{i=0}^{\infty} a_ix^i$.
\edfn



\thrm Ряд из $K[[x]]$ является рядом некоторой правильной дроби $\frac{f(x)}{g(x)}$, тогда и только тогда, когда его коэффициенты  удовлетворяют линейному рекуррентному соотношению. Более того, порядок наименьшего линейного рекуррентного соотношения, которому удовлетворяют коэффициенты, равен степени знаменателя в несократимой дроби.
\ethrm

\proof
Заметим, что, ряд Лорана  несократимой дроби $\frac{f}{g}$ лежит в $K[[x]]$ тогда и только тогда, когда $g(x)\ndi x$. Если $g(x)\ndi x$, то $g(x)$ обратима в $K[[x]]$, откуда и вся дробь лежит в $K[[x]]$. Обратно, если $g \di x$, и $\frac{f}{g}$ лежит в $K[[x]]$, то $f\ndi x$ и тогда $f$   обратимо в $K[[x]]$ откуда $g(x)^{-1} \in K[[x]]$, что не возможно, потому что свободный член $g$ равен 0.

Пусть $q(x)$ есть ряд правильной несократимой дроби $\frac{f(x)}{g(x)}$. Тогда $q(x)$ удовлетворяет соотношению $g(x)q(x)=f(x)$. Мы уже один раз выписывали соотношение на коэффициенты $g(x)$, когда $f(x)$ был равен 1. Поступим аналогично. Пусть $g(x)=b_nx^n+\dots +b_0$, $f(x)=a_mx^m+\dots +a_0$, а $q(x)=c_0+c_1x+\dots$. Тогда имеем уравнения на коэффициенты $q(x)$

$$ \sum_{j=0}^{n} b_j c_{i-j} =a_i .$$
Выражение справа равно 0 при $i>m$. Выражение слева при $i\geq n$ всегда имеет $n$ слагаемых. Функция $g(x)$ не может делиться на $x$ так как иначе мы не получили бы элемент из $K[[x]]$ или дробь была бы сократима. Тогда $b_0\neq 0$. Таким образом, при $i\geq n$ получаем рекуррентное соотношение на $c_j$

$$ b_0 c_{j+n}+b_1 c_{j+n-1}+\dots + b_n c_j=0.$$
Обратно, пусть $c_j$ удовлетворяют рекуррентному соотношению 
$$ b_0 c_{j+n}+b_1 c_{j+n-1}+\dots + b_n c_j=0, \text{ где } b_0,b_n \neq 0.$$

Тогда возьмём в качестве $g(x)= b_n x^n+\dots+b_0$. Как теперь найти $f(x)$? Вспомним условие на коэффициенты и положим 
$$a_i= \sum_{j=0}^{n} b_{j} c_{i-j}, \text{ где } i\in \ovl{0,n}.$$
Это и есть коэффициенты $f(x)$. Допустим дробь $\frac{f}{g}$ сократима. Тогда по уже доказанному она удовлетворяет соотношению меньшего $\deg g$ порядка.
\endproof

Рассмотрим простейший пример. Какая рациональная функция соответствует последовательности удовлетворяющей соотношению $z_{n+1}=\lambda z_n$, $z_0=1$? Эта последовательность имеет вид $z_n=\lambda^n$. Ей соответствует ряд $$1+ \lambda x+\dots + \lambda^nx^n+\dots .$$  
Это ряд для функции 
$$\frac{1}{1-\lambda x}.$$
Значит функции 
$$\frac{1}{x-\lambda}=\frac{-1}{\lambda}\frac{1}{1-\frac{x}{\lambda}}$$
соответствует последовательность $z_n=-{\frac{1}{\lambda}^{n+1}}$, то есть некоторая геометрическая прогрессия. 

А что соответствует ${\frac{1}{(1-\lambda x)^k}}$, где $k\geq 2$? Вспомним про производную. Заметим, что $$\frac{d^{k-1}}{dx^{k-1}}\frac{1}{1-\lambda x}=\frac{\lambda^{k-1} (k-1)!}{(1-\lambda x)^k}.$$
Переписывая получаем
$$\frac{1}{(1-\lambda x)^k}= \frac{1}{\lambda^{k-1} (k-1)!}\frac{d^{k-1}}{dx^{k-1}}\frac{1}{1-\lambda x}=  \sum_{n=0}^{\infty} C_{n+k-1}^{k-1} \lambda^{n}x^{n}.$$

\crl Пусть последовательность комплексных чисел $z_n$ удовлетворяет соотношению $a_k z_{n+k}+a_{k-1}z_{n+k-1}+\dots+a_0z_n=0$. Пусть многочлен $p(x)=a_k x^k+\dots +a_0$ имеет корни $\lambda_1$ кратности $k_1$, $\ldots$, $\lambda_l$ кратности $k_l$. Тогда последовательность $z_n$ имеет вид 
$$ p_1(n)\lambda_1^n+\dots+p_l(n)\lambda_l^n,$$
где $p_i$ многочлен степени не выше $k_i$.
\proof
Рассмотрим многочлен $g(x)=a_0x^k+\dots+a_k$. Заметим, что $$g(x)=x^k p\left(\frac{1}{x}\right)= x^k\prod\left(\frac{1}{x}-\lambda_i\right)^{k_i}= \prod (1-\lambda_ix)^{k_i}.$$
Последовательность $z_n$ имеет производящую функцию вида
$$\frac{h(x)}{g(x)}.$$
Разложим её на простейшие над $\mb C$. Получим 
$$\frac{h(x)}{g(x)}=\sum_{i=1}^l \sum_{0\leq j < k_i} \frac{b_{ij}}{(1-\lambda_ix)^j}.$$
Каждое слагаемое является производящей функцией для последовательности вида $p_{ij}(n)\lambda_i^n$, $\deg p_i < k_i$. Осталось просуммировать при одинаковом $i$.
\endproof
\ecrl

\dfn Многочлен $a_kx^k+\dots +a_0$ называется характеристическим многочленом линейной рекуррентной последовательности.
\edfn

Рассмотрим пример: пусть $f_n$ --- последовательность чисел Фибоначчи. Она удовлетворяет рекуррентному соотношению $f_{n+2}-f_{n+1}-f_n=0.$ Такой последовательности соответствует многочлен $g(x)=-x^2-x+1$ и $f(x)=x$. Рассмотрим дробь $F(x)=\frac{x}{-x^2-x+1}$  и разложим её в сумму простейших. Корни знаменателя это $\lambda_1=\frac{-1+\sqrt{5}}{2}$ и $\lambda_2=\frac{-1-\sqrt{5}}{2}$. Получим 
$$F(x)= -\left(\frac{\lambda_1}{\sqrt{5}(x-\lambda_1)}-\frac{\lambda_2}{\sqrt{5}(x-\lambda_2)}\right).$$
Представим каждое слагаемое в виде ряда и получим формулу 
$$f_n= \frac{1}{\sqrt{5}}(\ffi^{n-1}-\ovl{\ffi}^{n-1}),$$
где $\ffi=\frac{1+\sqrt{5}}{2}$, а $\ovl{\ffi}=\frac{1-\sqrt{5}}{2}$

Пусть последовательность $a_{n+2}=4a_{n+1}-4a_n$ начинается с $a_1=2$, $a_0=0$. Найдём общую формулу. Рассмотрим дробь $$A(x)=\frac{2x}{4x^2-4x+1}=\frac{2x}{(2x-1)^2}.$$ 
Как найти разложение в ряд? Заметим, что $$\frac{2}{(2x-1)^2}= \frac{d}{dx}\frac{-1}{2x-1}.$$
Вспомним, как считается производная для рядов. Тогда
$$A(x)=\sum_{n=0} (n+1) 2^{n+1} x^{n+1}=\sum_{n=0} n2^nx^n.$$

 


Заметим, что если $z_n$ --- комплексная последовательность, удовлетворяющая линейному рекуррентному соотношению, то её производящая функция $f(x)=\frac{h(x)}{g(x)}$ имеет конечный набор комплексных точек, в которых она не определена. Более того, мы даже знаем эти комплексные точки --- это корни $g(x)$, то есть обратные к корням характеристического многочлена. Общая философия, которая за этим стоит такая --- поведение последовательности определяется  <<особыми точками>> её производящей функции, то есть точками на комплексной плоскости, куда эта  функция не может быть продолжена, например, её полюсами.

\chapter{Линейная алгебра}

\setcounter{zad}{0}
\setcounter{lem}{0}
\setcounter{thm}{0}
%\setcounter{defn}{0}
\setcounter{cor}{0}

\section{Системы линейных уравнений и метод Гаусса}

\dfn Пусть $R$ -- кольцо. Тогда системой $m$ линейных уравнений от $n$ неизвестных называется набор условий

$$\begin{cases}
a_{11}x_1+\dots + a_{1n}x_n=b_1\\
\vdots \\
a_{m1}x_1+\dots+a_{mn}x_n=b_m
\end{cases},$$
где $a_{ij}, b_i \in R$.
\edfn

 Совершенно понятно, что система линейных уравнений определяется однозначно числами $a_{ij}$ и $b_i$. Эти числа удобно организовывать в матрицы.

\dfn Матрица размера $m\times n$ над кольцом $R$ -- это набор чисел проиндексированных двумя индексами $a_{ij}$ $i\in \ovl{1,m}$, $j\in \ovl{1,n}$. Множество всех матриц размера $m\times n$ над кольцом $R$ обозначается как $M_{m\times n}(R)$. Обычно матрицы я буду обозначать заглавными буквами, например $A$. Тот факт, что матрица $A$ имеет размер $m\times n$ будем записывать как $A\in M_{m\times n}(R)$.
\edfn

\dfn Матрица системы линейных уравнений называется матрица $A\in M_{m\times n}$, заполненная коэффициентами этой системы -- то есть числами $a_{ij}$. Матрица размера $m\times (n+1)$ содержащая дополнительно столбец $b_1,\dots, b_m$ называется расширенной матрицей системы. Мы будем отчёркивать столбец $b$, чтобы выделить его особую роль и будем обозначать расширенную матрицу системы как $(A|b)$.
\edfn

\dfn Пусть $A$ -- матрица $M_{m\times n}(K)$ составленная из элементов $a_{ij}$, а $x \in K^n$ -- столбец с компонентами $x_j$. Определим произведение матрицы $A$ на столбец $x$, как элемент $Ax \in K^m$, заданный по правилу
$$(Ax)_i=\sum_{j=1}^n a_{ij}x_j.$$ 
 \edfn
 
Таким образом матрица $A \in M_{m\times n}(K)$ задаёт отображение $K^n \to K^m$. А систему уравнений с матрицей $A$ и столбцом $b$ можно переписать как 
$$Ax=b.$$

От каждой системы нас прежде всего интересует множество её решений. Поэтому логично ввести определение:

\dfn Две системы линейных уравнений называются эквивалентными, если множества их решений совпадают.
\edfn

Как для данной системы линейных уравнений можно построить эквивалентную? Прежде всего заметим, что если есть два уравнения, то по ним можно построить много новых, а именно, пусть имеют $\lambda$ и $\mu$ из $R$. Тогда сложив два уравнения с коэффициентами $\lambda$ и $\mu$ получаем третье
$$\begin{cases}
a_1x_1+\dots+a_nx_n=c\\
b_1x_1+\dots+b_nx_n=d
\end{cases} \Rightarrow (\lambda a_1+\mu b_1)x_1+ \dots +(\lambda a_n+ \mu b_n)x_n= \lambda c+\mu d.$$
Понятно, что если набор $(x_1,\dots,x_n)$ -- решение первых двух, то и нового тоже.

Получать новые уравнения мы научились, остался вопрос про эквивалентные системы. Введём определение элементарных преобразований.

\dfn Пусть дана система уравнений
 $$\begin{cases}
a_{11}x_1+\dots + a_{1n}x_n=b_1\\
\vdots \\
a_{m1}x_1+\dots+a_{mn}x_n=b_m
\end{cases},$$
Элементарным преобразованием первого типа над этой системой линейных уравнений называется следующая операция. Рассмотрим уравнения с номерами $i$ и $j$, где $i\neq j$ и элемент $\lambda \in K$. Тогда прибавим  $i$-ое уравнение к $j$-ому с коэффициентом $\lambda$ и поместим результат на место $j$-го уравнения.
\edfn

\rm Очевидно, что решение новой системы содержит решения старой. Однако верно и наоборот, так как старая система получается из новой аналогичным прибавлением $i$-ого уравнения к $j$-ому, но с коэффициентом $-\lambda$.
\erm 

\dfn Элементарным преобразованием второго типа называется преобразование меняющее местами $i$-ое и $j$-ое уравнения местами. Элементарным преобразованием третьего типа называется преобразование, домножающие $i$-ое уравнение на коэффициент $\lambda \in R^*$.
\edfn

\rm Элементарное преобразование третьего типа приводит к эквивалентной системе так как есть обратное преобразование -- домножение на $\lambda^{-1}$. Для преобразования второго типа эквивалентность тривиальна.
\erm

Нам будет удобно вместо системы линейных уравнений работать с её упрощённой записью -- матрицей этой системы. Поэтому логично перевести понятия элементарных преобразований на язык матриц. 

\dfn Элементарным преобразованием строк первого типа над матрицей $A$ называется прибавление к $j$-ой строчке матрицы $A$ её $i$ строки с некоторым коэффициентом $\lambda$. Элементарным преобразованием второго типа называется перестановка $i$-ой и $j$-ой строк в матрице $A$. Преобразованием третьего типа называется домножение $i$-ой строчки на обратимый элемент $\lambda \in R^*$.
\edfn

Нас в основном пока будет интересовать случай $R=K$ -- поле. Обсудим метод Гаусса решения систем линейных уравнений. Он заключается в том, чтобы с помощью элементарных преобразований перевести систему уравнений к эквивалентной системе, так, чтобы вид последней был как можно более простым. Сформулируем это.

\dfn Будем говорить, что матрица $A$ имеет ступенчатый вид, если каждая новая строчка начинается с большего количества нулей, чем предыдущая. Говоря строго, для $i$-ой строки номер столбца в котором стоит первый ненулевой элемент строки строго больше, чем аналогичный  номер у $i-1$ строки, если только строка не целиком состоит из нулей.  
\edfn

Утверждение, которое стоит за методом Гаусса можно сформулировать следующим образом:

\thrm Любую матрицу над полем $K$ можно перевести элементарными преобразованиями к ступенчатому виду. Более того, можно считать, что для каждой строки первый её ненулевой элемент равен 1 и в столбце над ним стоят нули.
\ethrm
Предъявим индукционный алгоритм для получения ступенчатого вида:\\
{\bf Случай 1:} Элемент $a_{11}\neq 0$. Тогда прибавим ко всем остальным строкам первую с коэффициентами $-\frac{a_{i1}}{a_{11}}$. Получится матрица у которой в перво столбце стоят нули, кроме первой позиции. Вычеркнем первый столбик и первую строчку и продолжим по индукции.\\
{\bf Случай 2:} Элемент $a_{11}=0$, но в $i$-ой строчке стоит ненулевой элемент. Поменяем строку с номером $i$ с первой строкой и продолжим, как в случае 1.\\
{\bf Случай 3:} Весь первый столбец нулевой. Тогда вычеркнем первый столбец и продолжим по индукции.


Указанные преобразования очевидно приводят матрицу к ступенчатому виду. Способ добиться нулей над первыми не нулевыми элементами называется обратным ходом метода Гаусса. 


Прежде всего заработаем единицы в первых ненулевых элементах строк $a_i$ поделив на $a_i^{-1}$.

Затем посмотрим на последнюю ненулевую строку -- скажем строку $k$, первый  столбец с ненулевым элементом в которой имеет номер $j_k$, и прибавим её ко всем строкам выше с коэффициентом $-a_{lj_k}$ для $l$-ой строки. После чего перейдём к следующей строке.\\



\noindent {\bf Метод Гаусса}
Приступим к решению системы линейных уравнений. Приведём расширенную матрицу системы к ступенчатому виду. Рассмотрим последнюю ненулевую строчку. Если её ненулевой элемент находится в самом последнем отчёркнутом столбце, то решений нет, потому, что эта строчка соответствует уравнению $0x_1+\dots+0x_n=b_1\neq 0$, которое, как ни крути, решений не имеет. 

Если же такого не происходит, то разделим переменные на два класса -- те, в чьём столбце есть первый ненулевой элемент какой-то строки и те, в чьём столбце такого элемента нет -- обозначим последние за $x_{i_1},\dots,x_{i_n}$. Тогда выбрав любые значения для $x_{i_1},\dots,x_{i_n}$ из оставшихся уравнений мы однозначно восстановим значения всех остальных переменных. Более того, значения остальных переменных представляются в виде значений многочленов первой степени от  $x_{i_1},\dots,x_{i_n}$. Так выглядит стандартное описание всех решений линейного уравнения, которое выдаёт метод Гаусса. 

\rm Метод Гаусса подразумевает работу со строчками в определённой порядке, в частности, перестановка строк делается только в экстренных случаях. Но, в принципе, никто не запрещает для удобства переставлять строчки и прибавлять их друг к другу в произвольном порядке -- лишь бы вид системы в конце позволял проанализировать множество решений.
\erm

\exm\\
Допустим мы хотим наладить некоторую поисковую систему. Что это значит? Поисковая система индексирует страницы в сети и, то какая страница на какую ссылается. Иными словами, поисковая система видит ориентированный граф $G$, вершины которого -- это страницы в сети, а рёбра проводятся, если один сайт ссылается на другой. 

Что же дожна сделать поисковая система? Ей неплохо было назначить каждому сайту его важность. То есть необходима функция из множества вершин графа в вещественные числа  $W\colon G \to \mb R$. Важность сайта зависит от того, насколько много на него ссылаются. Это приводит  к следующей системе уравнений:
$$w_i=\sum_{j\to i} \frac{1}{d_j^{out}}w_j,$$
где $d_j^{out}$ исходящая степень вершины $j$. 

Приведу другой пример, в котором систему линейных уравнений можно увидеть не сразу. Точнее, рассмотрим набор целых чисел $a=-5250$, $b=-140$, $c=-1050$, $d=-1470$. Вопрос: можно ли найти такие $k_1,k_2,k_3,k_4$ не все чётные, что 
$a^{k_1}b^{k_2}c^{k_3}d^{k_4}$ есть квадрат целого числа? Вообще-то это довольно сложная задача. Но числа которые я здесь взял немного специальные. Я знаю их разложение на множители: 
$$a=2\cdot 3\cdot 5^3\cdot 7, \,\,b=-2^2\cdot 5\cdot 7, \,\, c=-2\cdot 3\cdot 5^2 \cdot 7,\,\, d=-2\cdot 3\cdot 5\cdot 7^2.$$

Целое число является квадратом, тогда и только тогда, когда оно положительно и любое простое входит в него в чётной степени. Получаем, что $a^{k_1}b^{k_2}c^{k_3}d^{k_4}$ есть квадрат, тогда и только тогда, когда 
$$\begin{cases} k_2+k_3+k_4=0 \mod 2,\\
k_1+2k_2+k_3+k_4=0 \mod 2,\\
k_1+k_3+k_4=0 \mod 2,\\
3k_1+k_2+2k_3+k_4=0 \mod 2,\\
k_1+k_2+k_3+2k_4=0 \mod 2,\\
\end{cases}.$$
Похоже, что это система уравнений над $\mb Z/2$. Сразу видно, что на $k_i$ можно смотреть по модулю 2. Составим матрицу системы. 

$$A=\pmat 0&0&1&1\\
1&0&1&1\\ 1&0&1&1 \\
1&1&0 &1 \\
1&1&1&0 \epmat.$$

Начнём применять элементарные преобразования. Замечу, что столбец $b$ нулевой и его можно опустить.
$$\pmat
0&0&1&1\\
1&0&1&1\\
1&0&1&1 \\
1&1&0&1 \\
1&1&1&0 \epmat \stackrel{\substack{(3)+(2), (4)+(2),\\ (5)+(2), (2) \to (1),\\ (2) \to (4), (3) \to (5)}}{\sim} 
\pmat
1&0&1&1\\
0&1&0&1\\
0&1&1&0 \\
0&0&1&1\\
0&0&0&0 \epmat \stackrel{\substack{(3)+(2), (4)+(3)}}{\sim} \pmat
1&0&1&1\\
0&1&0&1\\
0&0&1&1 \\
0&0&0&0\\
0&0&0&0 \epmat 
\stackrel{\substack{(1)+(3)}}{\sim} \pmat
1&0&0&0\\
0&1&0&1\\
0&0&1&1 \\
0&0&0&0\\
0&0&0&0 \epmat 
.$$
Ответ да можно. Возьмём $k_4=1$, тогда $k_2,k_3=1$, $k_1=0$.

Подобная задача возникает при поиске разложения числа $n$ на множители. Точнее, нетривиальное решение сравнения $x^2=y^2(\mod n)$ (то есть $x\neq \pm y (\mod n)$) даёт разложение числа $n$. Для получения такого разложения можно взять набор не очень больших простых $b_1,\dots,b_k$ и считать  $x \to x^2$ для случайного $x$. Если $k$ большое, то с высокой вероятностью $z=x^2 (\mod n)$ есть произведение $b_1^{\alpha_1}\dots b_k^{\alpha_k}$. Оставим только такие $z_i$. Подберём $d=\prod z_i^{\eps_i}$, чтобы $d=y^2$ в $\mb Z$. Тогда  $y^2=d=\prod {x_i^{\eps_i}}^2 (\mod n)$. Вопрос, почему это эффективный алгоритм относится к разделу аналитической теории чисел и пока вне нашей досягаемости.
 
Казалось бы, мы научились решать произвольную систему линейных уравнений -- что же ещё можно спросить? Я поставлю несколько вопросов, на которые отвечу в дальнейшем. Вот первый и основной из них:\\
1) Предположим, что две системы эквивалентны, например, потому что получились одна из другой перестановкой строк. Верно ли, что ответ для общего решения ответ в методе Гаусса будет содержать одинаковое число независимых параметров? А что будет, если одна система из другой получается заменой переменных?\\
2) В методе Гаусса видно, что решающую роль играет матрица системы. Вопрос: как по матрице системы определить, для каких $b$ система будет разрешима?\\
3) Мы интуитивно догадываемся, что обычно решение системы из $n$ уравнений и $m$ неизвестных описывается $m-n$ параметрами (если это число не отрицательно, конечно). Однако это не всегда так. Вопрос -- найти критерии, когда это выполнено, а когда нет. Это очень полезно, например, в задаче про поисковик. Ведь в этой задаче $n$ уравнений на $n$ неизвестных, но она, очевидно, имеет нулевое решение. Хочется верить, что оно не единственное.




\section{Векторные пространства}

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

\dfn[Векторное пространство]
Векторным пространством над полем $K$ называется множество $V$ вместе с отображениями $+\colon V\times V \to V$ и $\cdot \colon K \times V \to V$, удовлетворяющее свойствам:\\
1) $V, +$ является абелевой группой\\
2) $\forall v \in V$ верно, что $1\cdot v=v$\\
3) $\forall v \in V$, $\forall \lambda, \mu \in K$ верно, что $(\lambda+\mu)\cdot v= \lambda\cdot v + \mu \cdot v$.\\
4) $\forall u,v \in V$, $\forall \lambda \in K$ верно, что $\lambda\cdot(u+v)= \lambda\cdot u + \lambda \cdot v$.\\
5) $\forall v \in V$ $\forall \lambda, \mu \in K$ верно, что $(\lambda\mu)\cdot v= \lambda\cdot(\mu \cdot v)$.
\edfn
 
\dfn Пусть $R$ -- кольцо. Тогда модулем (левым) над $R$ называется множество $M$ вместе с отображениями $+\colon M\times M \to M$ и $\cdot \colon R \times M \to M$, удовлетворяющее свойствам 1)-5) из определения векторного пространства
\edfn

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

\exm\\
0) Само поле $K$ вместе со сложением и умножением.\\
1) Пространство столбцов $K^n$. Умножение и сложение покомпонентное.\\
2) Обобщая. Пространство матриц $M_{m\times n}(K)$.\\
3) Пусть $X$ -- множество. Рассмотрим множество всех функций  из $K$ в $X$ , то есть $K^X$. Это векторное пространство над полем $K$ с поточечным сложением и умножением.\\
4) Рассмотрим множество непрерывных вещественнозначных функций на отрезке $[0,1]$. Это векторное пространство над $\mb R$.\\
5) Рассмотрим множество последовательностей над полем $K$, удовлетворяющих заданному линейному рекуррентному соотношению $a_k x_{n+k}+\dots+a_0x_n=0$. Это векторное пространство над $K$.\\
6) Рассмотрим множества всех многочленов $K[x_1,\dots,x_n]$, всех рациональных функций $K(x_1,\dots, x_n)$, рядов $K[[x_1,\dots,x_n]]$. Это векторные пространства относительно естественного сложения и умножения на элементы $K$.\\
7) Пусть $A$ -- абелева группа, такая, что любой ей элемент имеет порядок $p$, для фиксированного простого числа $p$. Тогда на $A$ существует и единственна структура векторного пространства над $\mb Z/p$.\\
8) Пусть $L$ -- расширение поля $K$. Тогда $L$ является векторным пространством над $K$. В частности $\mb C$ вектроное пространство над $\mb R$ и над $\mb Q$. Аналогично $\mb R$ -- векторное пространство над $\mb Q$.\\
9) Рассмотрим фактор $K[x_1,\dots,x_n]/I$ -- это векторное пространство над полем $K$.\\

Отметим простейшие свойства элементов векторных пространств.
\lm Пусть $V$ -- векторное пространство над полем $K$. Тогда выполнено:\\
1) $\forall v  \in V$ выполнено, что $0\cdot v =0$.\\
2) Если для некоторых $\lambda \in K$ и $v \in V$ верно равенство $\lambda v =0$, то либо $\lambda=0$, либо $v=0$.\\
3) $\forall v  \in V$ выполнено, что $(-1)\cdot v=-v$.\\
\elm






\dfn[Подпространство] Пусть $V$ -- векторное пространство над полем $K$. Подмножество $U\subseteq V$ называется подпространством $V$, если\\
1) $U$ -- подгруппа $V$.\\
2) $\forall \lambda \in K$, $\forall u \in U$ верно, что $\lambda u \in U$.\\
По другому говоря,  операции на $V$ можно сузить на $U$, с тем, чтобы $U$ стало векторным пространством относительно этих операций.
\edfn

\exm\\ 
1) Рассмотрим множество столбцов из $K^n$, у которых первая координата равно 0. Это подпространство в пространстве столбцов.\\
2) Рассмотрим множество многочленов, которые делятся на данный многочлен $p(x)K[x]$. Это подпространство в $K[x]$. \\
3) Рассмотрим множество непрерывных на отрезке $[0,1]$ функций, принимающих значение $0$  в точках $0, \frac{1}{2}, 1$. Это подпространство в $C[0,1]$.\\
4) Рассмотрим множество многочленов степени не выше $n$ от одной переменной $$K[x_1,\dots, x_k]_{\leq n}=\{ f \in K[x_1,\dots, x_k]\,|\, \deg f\leq n\}.$$ Это подпространство в  $K[x_1,\dots,x_n]$.\\
5) Рассмотрим множество правильных дробей $\frac{f}{g}\in K(x)$. Это подпространство в $K(x)$.\\
6) Множество решений уравнения $Ax=0$, где матрица $A \in M_{m \times n}(K)$ образует подпространство в $K^n$.\\




Как и в жизни элементы пространства обычно не интересны сами по себе, а только во взаимоотношении с окружающей их действительностью.

\dfn(Линейная комбинация) Линейной комбинацией векторов $v_1,\dots, v_n$ с коэффициентами $\lambda_1, \dots, \lambda_n$, называется элемент $v\in V$ 
$$v=\lambda_1 v_1 +\dots + \lambda_n v_n.$$
Если хотя бы один из элементов $\lambda_1,\dots, \lambda_n $ не равен 0, то говорят, что линейная комбинация нетривиальна.
\edfn

\lm Рассмотрим набор $v_1,\dots,v_n \in V$. Пусть $w_1=\mu_{11}v_1+\dots+\mu_{1n}v_n$, $\dots$, $w_m= \mu_{m1}v_1+\dots+\mu_{mn}v_n$. Рассмотрим набор $\lambda_1,\dots, \lambda_m$. Тогда вектор $w=\sum \lambda_i w_i$ является линейной комбинацией набора $v_i$. 
\elm


\dfn[Линейная зависимость] Набор векторов $v_1,\dots,v_n$ называется линейно зависимым, если 0 является нетривиальной линейной комбинацией $v_1,\dots, v_n$, то есть существуют  $\lambda_1, \dots, \lambda_n \in K$ не все равные 0, что
$$0=\lambda_1v_1+\dots+\lambda_n v_n.$$
\edfn

\dfn[Линейная независимость] Набор векторов $v_1,\dots,v_n$ называется линейно независимым, если он не является линейно зависимым, то есть если $\lambda_1, \dots, \lambda_n \in K$ такие, что $$0=\lambda_1v_1+\dots+\lambda_n v_n, \text{ то $\lambda_1=\dots=\lambda_n=0$}.$$ 
\edfn



\rm Будем говорить, что набор линейно независим, если независим каждый его конечный поднабор. 
\erm

\exm \\
0) Набор из одного нуля линейно зависим.\\
1) Пусть $v_1$ и $v_2$ два вектора из $V$. Они линейно зависимы тогда и только тогда, когда они пропорциональны.\\
2) Рассмотрим пространство $K^n$ и набор столбцов 
$$e_1=\pmat 1\\0\\ \vdots\\ 0\epmat,\, \dots, e_n=\pmat 0\\ 0 \\ \vdots \\ 1 \epmat.$$
Это линейно независимая система векторов. \\
3) Аналогично в пространстве матриц $M_{m \times n}(K)$ имеется набор матриц $e_{ij}$ вида
$$ e_{ij}= 
\bordermatrix{
 & &j&& \cr
 &0&\cdots&\cdots&0\cr
 &\vdots&\ddots && \vdots\cr
i&\vdots& 1 & \ddots& \vdots\cr
 &0&\cdots& \cdots&0
}
$$\\
4) Все мономы $x^{\alpha}$ в кольце  $K[x_1,\dots,x_n]$ линейно независимы\\
5) Набор  $\frac{1}{x-\lambda}$ линейно независим.\\
6) Любой поднабор линейно независимого набора линейно независим.\\


\thrm[О линейной зависимости линейных комбинаций.] Пусть $u_1,\dots,u_m$ и $v_1,\dots,v_n$ два набора векторов. При этом все вектора $u_i$ являются линейными комбинациями $v_j$, то есть $u_i=\sum_{j=1}^n \lambda_{ij}v_j$. Тогда, если $m>n$, то $u_i$ обязательно линейно зависимы. 
\ethrm
\proof Индукция по $n$. $n=1$. Все вектора $u_i$ кратны $v_1$ и пропорциональны друг другу.

Будем поступать как в методе Гаусса. Запишем $u_i$ в виде 
$u_i=\sum_{j=1}^n \lambda_{ij}v_j$. Если для некоторого индекса $j$ все $\lambda_{ij}=0$, то можно воспользоваться предположением индукции.

Рассмотрим вектор $u_i$, что $\lambda_{in}\neq 0$. Тогда перейдём к набору $$u_s'=u_s - \frac{\lambda_{sn}}{\lambda_{in}}u_i= \sum_{j=1}^{n-1} \mu_{sj} v_j, \,\,\,\, s\neq i.$$
Это набор из $m-1$ элемента, которые суть линейные комбинации $v_1,\dots,v_{n-1}$. Этот набор линейно зависим по индукционному предположению, то есть существуют $\nu_{s}$ не все равные нулю, что
$$0=\sum \nu_s u_{s}'= -\left(\sum\nu_s\frac{\lambda_{sn}}{\lambda_{in}}\right)u_i +\sum \nu_s u_s.$$
Заметим, что не все коэффициенты при $u_s$ равны нулю. Таким образом мы получили нетривиальную линейную зависимость.
\endproof




\dfn Пусть $X$ подмножество векторного пространства $V$. Тогда подпространство, порожденное $X$ -- это наименьшее подпространство, содержащее $X$. Обозначается оно $\lan X \ran$. Это подпространство так же называют линейной оболочкой $X$.
\edfn

 
\lm Пусть $X\subseteq V$. Тогда линейная оболочка $\lan X \ran$ существует и описывается как множество всех линейных комбинаций элементов из $X$.
$$\lan X \ran = \{ v\in V\,|\, \exists x_1, \dots,x_n \in X, \text{ и } \lambda_1,\dots,\lambda_n \in K, \text{ что } v=\lambda_1x_1+\dots+\lambda_nx_n\}$$
\proof Аналогично лемме про идеалы.
\endproof
\elm

\dfn Будем говорить, что набор $v_{\alpha} \in V$ $\alpha \in I$ является порождающим для $V$, если $\lan \{v_{\alpha}\}_{\alpha \in I}\ran= V$. Иными словами, для любого $v \in V$ существуют $v_{\alpha_1},\dots,v_{\alpha_n}$  и $\lambda_1,\dots,\lambda_n$, что $v=\sum \lambda_i v_{\alpha_i} $.
\edfn

\dfn[Базис] Набор векторов $v_{\alpha}$, $\alpha \in I$ называется базисом пространства $V$, если он является порождающей и линейно независимой системой векторов в $V$. \edfn

\exm\\
1) Набор векторов $e_i \in K^n$ является базисом. Этот базис называют стандартным.\\
2) Набор $e_{ij}$ является базисом $M_{m\times n}(K)$.\\
3) Мономы $x^{\alpha}$ являются базисом $K[x_1,\dots,x_n]$.\\
4) Элементы $1,x, \dots, x^n, \dots$ и $\frac{1}{(x-\lambda)^n}$ по всем $\lambda \in \mb C$ являются базисом в $\mb C(x)$.\\
5) $1,i$ -- базис $\mb C$ над $\mb R$.






\lm[Переформулировки] Пусть $e_1,\dots,e_n$ -- набор элементов пространства $V$.
Тогда следующие свойства эквивалентны: \\
1) $e_1,\dots,e_n$ -- базис $V$.\\
2) $e_1,\dots,e_n$ -- минимальный по включению среди порождающих $V$ наборов векторов.\\
3) Для любого $v\in V$ существуют единственные $\lambda_1,\dots,\lambda_n \in K$, что $v=\lambda_1e_1+\dots+\lambda_ne_n$. Такие элементы $\lambda_1,\dots,\lambda_n$ называются координатами вектора $v$ в базисе $e$.
4) $e_1,\dots,e_n$ -- максимальный по включению набор среди линейно независимых наборов векторов из $V$.
\proof 1)  в 2). Пусть набор не минимален. Тогда выкинем векторок. Например, $v_1$. Но тогда $v_1=\sum_{i\geq 2}\lambda_i v_i$. Это даёт нетривиальную линейную зависимость.

2) в 3). Существование разложения следует из порождаемости. Пусть $\sum \lambda_i v_i =\sum \mu_i v_i$. Тогда либо все $\mu_i=\lambda_i$, либо, скажем, $\mu_1-\lambda_1 \neq 0$. Тогда  $v_1=\frac{1}{\mu_1-\lambda_1}\sum_{i\geq 2} (\mu_i-\lambda_i) v_i$. Тогда из системы можно выкинуть $v_1$ и всё равно будет порождающая система.

3) в 4). Единственность разложения для 0 означает линейную независимость. Покажем максимальность. Пусть система не максимальна. Тогда к ней можно добавить вектор $v\neq 0$ и она останется независимой. Но такого не может быть, так как $v=\sum \lambda_i v_i$, что очевидно даёт линейную зависимость.

4) в 1). Пусть система не порождает $V$. Тогда добавим к ней вектор $v \in V\setminus \lan v_i \ran$. Если система зависима, то есть $\lambda v+ \sum \lambda_i v_i=0$, то либо $\lambda=0$ и тогда получаем, что $v_i$ зависимы, что не так, либо $v=-\lambda^{-1} \sum \lambda_i v_i$, что противоречит определению $v$. Таким образом, система $v,v_1,\dots, v_n$ независима, что противоречит максимальности. 
\endproof
\elm

\dfn Пространство называется конечно порождённым, если существует конечная порождающая система $e_1,\dots,e_n$ для $V$.
\edfn

\thrm[Теорема о дополнении до базиса] Пусть $V$ -- конечно порождённое векторное пространство. Тогда любой набор линейно независимых векторов $(u_{\alpha})_{\alpha \in I}$ можно дополнить до базиса при помощи элементов заданного конечного порождающего множества $v_1,\dots,v_n$.
\proof Будем добавлять элементы из порождающего множества к линейно независимой системе до тех пор, пока полученный набор будет оставаться линейно независимым.
Индукция по числу элементов из порождающего множества не лежащих в линейной оболочке $\lan u_{\alpha}\ran$. База. Если все элементы задействованы, то
$$ V=\lan v_1,\dots,v_n \ran \subseteq \lan u_{\alpha}\ran \subseteq V.$$
Следовательно, система $u_{\alpha}$ является порождающей, и  является базисом. 

Рассмотрим порождающий набор $v_1,\dots,v_n$. Пусть элемент $v_i$ не лежит в $\lan u_{\alpha}\ran$. Рассмотрим новую систему $\{ u_{\alpha}\}\cup \{v_i\}$. Эта система линейно независима и, очевидно, в её линейной оболочке лежит больше векторов из порождающей системы. Тогда её можно дополнить до базиса.
\endproof
\ethrm

\crl В любом конечно порождённом пространстве есть конечный базис.
\proof Пустое множество линейно независимо. Дополним его до базиса при помощи конечной порождающей системы.
\endproof
\ecrl


\thrm[Теорема о равномощности базисов] Пусть $V$ -- конечно порождённое пространство. Тогда любые два базиса $V$ конечны и равномощны.
\proof Можно считать, что один базис $e_1,\dots,e_n$ конечен. Рассмотрим другой базис $f_{\alpha}$. Тогда по теореме о линейной зависимости линейных комбинаций число независимых элементов в $f_{\alpha}$ не более $n$. Пусть их $m\leq n$. Тогда заметим, что $e_j$ выражаются через $f_i$. Тогда $n\leq m$.
\endproof
\ethrm

\crl Размер любого базиса не больше размера любой порождающей системы и не меньше размера любой независимой системы векторов.
\ecrl

\rm Верны бесконечномерные версии этих теорем. А именно, любую линейно независимую систему можно дополнить до базиса при помощи элементов любой порождающей системы. Любое пространство имеет базис и два разных базиса одного и того же пространства равномощны.
\erm

\dfn[Размерность] Пусть $V$ -- векторное пространство. Размерностью $V$ называется мощность какого-нибудь базиса $V$.
\edfn

\dfn Пространство $V$ называется конечномерным, если в нём есть конечный базис. В противном случае пространство $V$ называется бесконечномерным. Класс конечномерных пространств совпадает с классом конечно порождённых пространств.
\edfn

\thrm Любое подпространство $U$ конечномерного пространства $V$ конечномерно и $\dim U \leq \dim V$ и равенство достигается только в случае $U=V$.
\ethrm
\proof Пусть в пространстве $U$ нет конечного базиса. Тогда рассмотрим линейно независимую систему $u_1,\dots,u_m$ в $U$ самого большого размера. Такая есть, так как линейно независимая система в $U$ лежит в $V$ и, следовательно, ограничена размерностью $V$. Если $\lan u_1,\dots,u_m \ran =U$, то теорема доказана. Иначе рассмотрим вектор $u_{m+1}\in U$, что $u_{m+1}\notin \lan u_1,\dots,u_m \ran$. Новая система $u_1,\dots,u_m,u_{m+1}$ линейно независима и больше предыдущей. Противоречие. Значит в $U$ есть конечный базис. Этот базис есть линейно независимая система внутри $V$ и, как мы уже отмечали, имеет размер меньший, чем у базиса $V$ и равный, только при $U=V$ (иначе можно нетривиально дополнить). 
\endproof

\lm Пусть размерность $V$ равна $n$, а $f_1,\dots, f_n \in V$ набор векторов с одним из условий:\\
1)  $f_1,\dots, f_n$ -- линейно независимая система\\
2) $f_1,\dots, f_n$ -- порождает $V$.\\
Тогда $f_1,\dots, f_n$ -- базис $V$.
\elm




\exm\\
1) Размерность пространства $M_{m\times n}(K)$ равна $mn$. Базисом является $e_{ij}$. Такой базис называется стандартным\\
2) Размерность пространства $K[x]_{\leq n}=n+1$. Базис $1,x,\dots,x^n$.\\
3) Размерность $\mb C$ над $\mb R$ равна 2.\\
4) Размерность $K[x]/p(x)=\deg p(x)$.\\

Как определить по системе векторов $v_1,\dots,v_k$ из $V$, что она линейно независима? Пусть заранее известен $e_1,\dots,e_n$ базис $V$. Разложим  $v_j=\sum a_{ij} e_i$. Тогда сумма $0=\sum \lambda_j v_j=\sum \sum \lambda_j a_{ij} e_i$ обнуляется тогда и только тогда, когда $\lambda_i$ решение системы уравнений $A\lambda =0$. Итого, вектора линейно независимы тогда и только тогда, когда у этой системы нет нетривиальных решений и зависимы иначе.

Как определить, что система порождающая? Для этого необходимо и достаточно получить любой базисный элемент $e_i$, то есть добиться существования линейной комбинации $\sum \lambda_iv_i - e_j =0$ по всем $j$. Это эквивалентно тому что система уравнений с расширенной матрицей $(A|e_i)$ имеет решение (в последнем случае $e_i$ -- это столбец из стандартного базиса).

Приведём пример использования понятия линейной зависимости. Пусть $\alpha \in \mb R$ корень многочлена с рациональными коэффициентами $x^3-x-1=0$. Вопрос, а верно ли, что $\beta=\alpha^2$ тоже удовлетворяет какому-то уравнению с рациональными коэффициентами (такие числа называют алгебраическими), и, если да, то какому.  

Для этого рассмотрим пространство $V= \lan 1,\alpha, \alpha^2, \dots, \ran$. Заметим, что это пространство порождено $1,\alpha,\alpha^2$. Покажем, что это его базис. Для этого заметим, что многочлен $x^3-x-1$ неприводим над  $\mb Q$ и если бы была нетривиальная линейная зависимость $a_2 \alpha^2+ a_1 \alpha+ a_0=0$, то $x^3-x-1$ имел бы общий делитель с многочленом $a_2 x^2+ a_1 x+ a_0$, что противоречит неприводимости. 

Теперь заметим, что элементы $1, \beta, \beta^2, \beta^3$ лежат в $V$ и, следовательно линейно зависимы. Тогда нулевая линейная комбинация $b_3 \beta^3+b_2 \beta^2+b_1 \beta + b_0=0$ даёт желаемое уравнение. Найдём её. Для этого заметим, что $\beta^2=\alpha(\alpha+1)$, а $\beta^3=(\alpha+1)^2$. Строим матрицу 
$$A =\pmat 
1&0&0&1\\
0&0&1&2\\
0&1&1&1
\epmat
.$$
Заменяем матрицу на эквивалентную
$$\pmat 
1&0&0&1\\
0&1&0&-1\\
0&0&1&2
\epmat$$
и находим решение $-1,1,-2,1$. Итого $\beta$ удовлетворяет уравнению 
$$\beta^3-2\beta^2+\beta-1.$$

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

\dfn[Линейное отображение] Пусть $U,V$ -- два векторных пространства над полем $K$. Отображение $L\colon U \to V$ называется линейным, если\\
1) $\forall a,b \in U$ верно, что $L(a+b)=L(a)+L(b)$.\\
2) $\forall a \in U$, $\lambda \in K$ верно, что $L(\lambda a)=\lambda L(a)$.
\edfn

\dfn Линейное отображение называется моно-, эпи-, изоморфизмом, если оно инъективно, сюръективно, биективно. Линейное отображение $V \to V$ называется эндоморфизмом пространства $V$, а обратимый эндоморфизм $V$ -- автоморфизмом $V$.
\edfn

\exm\\
0) Рассмотрим пространство $K^n$ и набор элементов $a_1,\dots,a_n$. Определим отображение $K^n \to K$ по правилу $$x \to (a_1,\dots, a_n) \cdot x= \sum a_ix_i.$$
Это отображение линейно.\\
1) Пусть задана матрица $A \in M_{m\times n}(K)$. Тогда отображение $K^n \to K^m$, заданное как $x \to Ax$ линейно.\\
2) Пусть задан многочлен $p(x) \in K[x]$. Тогда отображение $K[x] \to K[x]$ $f(x)\to p(x)f(x)$ линейно.\\
3) Пусть $\lambda \in K$. Тогда отображение $f(x) \to f(\lambda)$ линейно.\\
4) Пусть $p(x) \in K[x]$ -- многочлен. Тогда отображение $K[x] \to K[x]$, заданное как  $f(x)\to f(p(x))$ линейно.\\
5) Отображение взятия производной $f \to f'$ линейно во всех пространствах, где оно определено (например, как отображение из $K[x] \to K[x]$).\\
6) Отображение сопряжения $\ovl{\cdot} \colon \mb C \to \mb C$ линейно над $\mb R$, но не линейно над $\mb C$.\\
7) Пусть $g(x,y)$ непрерывная функция из $[0,1]^2 \to \mb R$. Тогда отображение $f(x) \to \int_{0}^1 f(y)g(x,y)dy$ линейно  как отображение $C([0,1])\to C([0,1])$ .\\




Итак, благодаря примерам, мы поняли, что отображение $K^n \to K^m$, заданное с помощью матрицы $A$ это частный случай линейного отображения. Таким образом, решение системы линейных уравнений можно понимать как нахождение прообраза элемента при линейном отображении. В дальнейшем мы увидим, что общий случай можно свести  и разными способами к указанному частному случаю. Но прежде посмотрим, на общие качественные свойства линейных отображений.



\lm[Базовые свойства]
0) Пусть $V$ -- векторное пространство, а $\lambda \in K$. Тогда отображение $x \to \lambda x$ является линейным отображением. \\
1) Пусть $L_1$ и $L_2$ -- два линейных отображения $V \to W$. Тогда $L_1+L_2$ -- их поточечная сумма -- тоже линейное отображение.\\
2) Пусть $\mu \in K$ и $L\colon V \to W$ -- линейное отображение. Тогда $\mu L$ -- тоже линейное отображение.\\
3) Пусть $L_1\colon V_1\to V_2$, а $L_2\colon V_2 \to V_3$. Тогда $L_1\circ L_2$ -- линейное отображение $V_1 \to V_3$.\\
4) Пусть $L\colon V \to W$ линейное отображение. Тогда обратное к нему линейно.\\
5) Для композиции линейных отображений выполнена дистрибутивность. А именно, если $L_1,L_2 \colon V \to W$, а $L_3 \colon W \to U$, а $\lambda_1, \lambda_2 \in K$, то 
$$(\lambda_1 L_1+ \lambda_2 L_2 ) \circ L_3 = \lambda_1 (L_1 \circ L_3)+ \lambda_2 (L_2 \circ L_3).$$\\
6) Так же, если $L_1 \colon V \to W$, а $L_2,L_3 \colon W \to U$, и $\lambda_1, \lambda_2 \in K$, то 
$$ L_1 \circ (\lambda_1 L_2+ \lambda_2 L_3 ) = \lambda_1 (L_1 \circ L_2)+ \lambda_2 (L_1 \circ L_3).$$
7) Пусть $L\colon V \to W$. Тогда $\Ker L$ и $\im L$   -- это подпространства $V$ и $W$ соответственно. 
\elm
\proof 
\endproof

\crl Множество всех отображений $\Hom(U,V)$ является векторным пространством.
\proof Необходимо дополнительно проверить, что сложение ассоциативно, коммутативно, любой элемент имеет противоположенный и что умножение на скаляр ассоциативно. Эти свойства верны потому что они верны в $V$.  
\endproof
\ecrl






Основная теорема, которая говорит про устройство линейных отображений, следующая:
\begin{thm}
Пусть $V_1$, $V_2$ --- векторные пространства над полем $K$. Пусть $e_1,\dots,e_n$ - базис $V_1$, а $f_1,\dots,f_n$ --- набор каких-то векторов из $V_2$. Тогда существует единственное отображение $L\colon V_1 \to V_2$, что $L(e_i)=f_i$. Пусть вектор $v\in V_1$ раскладывается по базису $v=\sum \lambda_i e_i$, то $L(v)=\sum \lambda_i f_i$.
\proof Очевидно, что отображение должно быть задано такой формулой и это показывает единственность. 
Осталось показать, что оно линейно. Действительно, если два вектора $v=\sum \lambda_i e_i$ и $u=\sum \mu_i e_i$, то $u+v= \sum (\lambda_i +\mu_i) e_i$ есть разложение для суммы. Осталось посчитать $L(u+v)$ и раскрыть скобки. 
\endproof
\end{thm}

\crl Если $L$ переводит некоторый базис $V$ в базис $W$, то $L$ обратимо. Обратно, если линейное отображение $L \colon V \to W$ является изоморфизмом, то $L$ переводит любой базис $V$ в базис $W$. 
\proof 
Пусть $e_1,\dots,e_n$ -- базис $V$ и $L(e_1),\dots,L(e_n)$ -- базис $W$. Тогда есть единственное линейное отображение $T \colon W \to V$, которое переводит $L(e_i)$ в $e_i$. Заметим, что композиция $U\circ L$ переводит $e_i \to e_i$. Тогда по единственности такая композиция тождественна. Аналогично композиция в другом порядке тождественна. Тогда $T$ -- обратное отображение к $L$.
 В другую сторону. Пусть $e_1,\dots,e_n$ -- базис $V$. Покажем, что $L(e_1),\dots,L(e_n)$ -- базис $W$.  Пусть есть линейная зависимость  $$0=\lambda_1 L(e_1)+\dots+\lambda_n L(e_n).$$
Тогда 
$$0=L^{-1}(0)=L^{-1}(L(\lambda_1 e_1+\dots+\lambda_n e_n))=\lambda_1 e_1+\dots+\lambda_n e_n.$$
Тогда все $\lambda_i$ равны 0. Покажем, что $L(e_i)$ порождают $W$. Рассмотрим вектор $w\in W$. Тогда $$w=L(v)=L\left(\sum \lambda_i e_i\right)=\sum \lambda_i L(e_i).$$
\endproof
\ecrl

Это позволяет нам установить следующее 

\crl Два конечномерных пространства $V$ и $W$ изоморфны тогда и только тогда, когда $\dim V=\dim W$. В частности $V\cong K^{\dim V}$. Более того, задание базиса равносильно заданию изоморфизма $V\to K^{\dim V}$.
\proof
Рассмотрим в качестве $W$ пространство $K^n$ и стандартный базис $e_1,\dots,e_n$. Тогда базису $f_1,\dots,f_n$ в $V$ соответствует линейное отображение переводящее $f_i \to e_i$. Это отображение берёт вектор $v \in V$, раскладывает его как $v=\sum_{i=1}^n \lambda_i f_i$ и переводит его в столбец координат $\lambda_i$. Обратно, если есть изоморфизм $L\colon V \to K^n$, то можно рассмотреть обратное отображение $L^{-1}$. Тогда $L^{-1}(e_i)$ -- это базис $V$.
\endproof
\ecrl

\dfn
Изоморфизм между пространством $V$ и пространством $K^n$ называется линейной системой координат на пространстве $V$. Мы знаем что любая линейная система координат происходит из некоторого базиса. Отображение, сопоставляющее вектору $v$ его $i$-ую координату, называется $i$-ой координатной функцией.
\edfn

Сделаем отступление про модули над кольцом. Мы видели, что все векторные пространства изоморфны пространствам столбцов. Изоморфизм строится благодаря наличию базиса. 
Сейчас я приведу примеры модулей и мы увидим, что модули могут иметь самый разнообразный облик. Итак 


\exm\\
1) Пусть $R$ -- кольцо. Тогда множество $R^n$ является модулем над $R$ вместе с покоординатным сложением и умножением (и даже в разумном смысле имеет базис). Такой модуль называется свободным модулем ранга $n$\\
2) Пусть $M$ -- абелева группа. Тогда на $M$ существует единственная структура $\mb Z$ модуля.\\
3) Пусть $I$ идеал кольца $R$. Тогда можно ограничить умножение на элементы из $R$ со всего $R$ до  $I$ -- это и задаёт структуру модуля на $I$ (быть идеалом это то же, что быть подмодулем в $R$ при естественном определении этого слова). 

Верно ли что каждый модуль изоморфен модулю вида $R^n$? Пусть $R=\mb Z$. Тогда модуль $\mb Z/p$ точно не изоморфен $\mb Z$, потому что он конечен. Но можно заметить, что любой идеал $I \leq \mb Z$ изоморфен $\mb Z$. Действительно, $I$ имеет вид $n\mb Z$. Изоморфизм осуществляется умножением на $n$. 

Может быть так происходит всегда? Ответ -- нет. Покажем, что идеал $(x,y) \leq K[x,y]$ имеет не менее двух порождающих его элементов, но при этом между любыми из этих элементов есть нетривиальная зависимость. 

Прежде всего найдём зависимость, потому что это легче. Пусть есть два элемента из $I=(x,y)$ -- скажем, $f,g$. Тогда $0=fg+(-f)g$. Просто они лежат внутри кольца $R$, какой хотите идеал берите.
Пусть теперь $(x,y)= (g)$. Тогда степень $g$ обязана быть равной 1, чтобы получить в качестве кратного элемент $x$. Пусть $g= \alpha x+ \beta y$, $\alpha, \beta \in K$. Но тогда единственные многочлены степени $1$ кратные $g$ это $\lambda g$, $\lambda \in K$. Это одномерное пространство в $\lan x, y\ran $ -- двумерном над $K$. Итого, все элементы не получить. Такие дела.  \\



Вернёмся к векторным пространствам. {\color{red} Внимание!} Далее я всегда буду предполагать, что все пространства конечномерны. Можно ли как-то попроще разобраться с нашими модельными примерами конечномерных пространств --  пространствами $K^n$?

\crl
Все линейные отображения $L\colon K^n \to K^m$ имеют вид $L(x)=Ax$, где $A$ --- матрица $m\times n$
\proof Если задано линейное отображение $L$, то по нему определяется матрица $A$ составленная из столбцов $L(e_i)$, где $e_i$ -- это стандартный базис $K^n$. Тогда отображения $x \to L(x)$ и $x \to Ax$ оба переводят $e_i \to L(e_i)$, то есть совпадают на базисе и, значит, совпадают везде.
\endproof
\ecrl


\dfn Пусть $U \leq V$. Рассмотрим факторгруппу $V/U$. Введём на ней структуру векторного пространства по следующему правилу $\lambda \cdot \ovl{v}=\ovl{\lambda v}$.
\edfn

Можно заметить, что верна теорема
\thrm[Об изоморфизме] Пусть $V$ и $W$ два векторных пространства, а $L\colon V \to W$ -- линейное отображение. Тогда $V/\Ker L \cong \Im L$.
\ethrm

\dfn Рангом линейного отображения $L\colon V \to W$ называется размерность его образа $\rank L= \dim \im L$. Рангом матрицы $A\in M_{m\times n}(K)$ называется ранг соответствующего ей линейного отображения $K^n \to K^m$. Иными словами ранг матрицы это размерность пространства, порождённого столбцами этой матрицы.
\edfn


\begin{thm}
Пусть $L\colon V \to W$ --- линейное отображение между конечномерными пространствами. Тогда 
$$\dim V= \dim \Ker L +  \dim \im L= \dim \Ker L +\rank L.$$
\end{thm}
\proof Выберем $e_1,\dots, e_k$ -- базис $\Ker L$ и дополним его элементами $e_{k+1},\dots,e_n$ до базиса всего $V$. Я утверждаю, что $L(e_{k+1},\dots,L(e_n))$ являются базисом образа. Действительно, образ $L$ порождён $L(e_1),\dots, L(e_n)$, но первые $k$ элементов этого набора нули. Поэтому их можно исключить, что означает, что $L(e_{k+1}), \dots, L(e_n)$ порождают образ $L$. 

Пусть сумма $\sum_{i=k+1}^n \lambda_i L(e_i)=0$. Тогда элемент $\sum_{i=k+1}^n \lambda_i e_i $ лежит в ядре $L$. Отсюда получаем, что имеет место равенство $$\sum_{i=k+1}^n L(e_i) = \sum_{i=1}^k \mu_i e_i$$
которое приводит к нулевой линейной комбинации всех $e_i$. Но $e_i$ -- базис $V$ и поэтому все коэффициенты, в частности, $\lambda_i$ равны нулю. 

Итого, размерность ядра равна $k$, размерность образа равна $n-k$, что в сумме и даёт $n$.
\endproof

\crl Пусть $U \leq V$. Тогда $\dim V/U= \dim V - \dim U$.
\ecrl

\dfn Коразмерностью пространства $U \leq V$ называется число $\dim V/U$. 
\edfn

\crl Для любого подпространства $U \leq K^n$ коразмерности $d$ существует линейное отображение $L\colon K^n \to K^d$, такое, что $U=\Ker L$. Иными словами, такое подпространство задаётся $d$ уравнениями. 
\ecrl
\proof Рассмотрим цепочку линейных отображений $K^n \to K^n/U \stackrel{\sim}{\longrightarrow} K^d$.
\endproof 

\crl[Принцип Дирихле для линейных отображений] Пусть $V$ и $W$ два пространства размерности $n$ и $L \colon V \to W$ -- линейное отображение между ними. Тогда $L$ -- сюръективно тогда и только тогда, когда $L$ -- инъективно.
\ecrl




\section{Линейные уравнения и качественное описание их решений}
Итак, основную задачу линейной алгебры можно обозначить следующим образом: пусть $L\colon V \to W$ -- линейное отображение. Требуется для конкретного $y\in V$ описать множество решений уравнения $Lx=y$ и, с другой стороны, описать все $y\in W$, для которых есть решение есть.

Попробуем качественно ответить на эти вопросы. Прежде всего множество $y$, для которых уравнение $Lx=y$ разрешимо есть, как мы знаем, подпространство $W$. Его базис можно найти следующим образом -- взять базис $V$ -- $e_1,\dots,e_n$, рассмотреть порождающий набор для образа $L(e_1),\dots,L(e_n)$ и выбрать из него базис образа. 

Задача описания прообраза для элемента $0\in W$ по определению есть задача описания ядра $L$, которую мы разберём чуть позже. Пусть дан некоторый $y\in \im L$. Тогда все решения уравнения $Lx=y$ образуют класс $x_0+\Ker L$.



\dfn Аффинным подпространством векторного пространства $V$ называется подмножество вида $U+v_0$, где $U$ -- линейное подпространство $V$, а $v_0\in V$, или, что тоже самое -- смежный класс относительно некоторого линейного подпространства.
\edfn

\lm Пусть $W$ -- аффинное подпространство $V$. Тогда существует единственное подпространство $U$, что $W=U+v_0$. Вектор $v_0$ однозначно определён с точностью до  элементов из $U$.
\elm
\proof Рассмотрим множество $U'=\{w-v\,|\, w,v \in W\}$. Очевидно оно однозначно определяется множеством $W$. Пусть $W=U+v_0$. Необходимо показать, что $U=U'$. Прежде всего включение $U'\subseteq U$ получается исходя из того, что $x-v_0-y+v_0=x-y \in U$. В другую сторону. Пусть $x\in U$. Тогда $x=(x+v_0)-v_0\in U'$. Так как $W$ -- это смежный класс по $U$, то в качестве $v_0$ можно взять любой элемент из $W$. Но все они отличаются на элемент из $U$ по определению.
\endproof

\dfn Пусть $W=U+v_0$ аффинное подпространство $V$. Тогда определим $\dim W=\dim U$.
\edfn

Сформулируем полученное в виде теоремы.

\thrm Пусть $L\colon V \to W$ -- линейное отображение и $\dim V= n$, а $\dim W=m$. Тогда множество решений  $Lx=y$ либо пусто, либо образует аффинное подпространство вида $x_0+ \Ker L$ размерности $$\dim \Ker L = n - \rank L\geq n -m.$$
\ethrm

 Рассмотрим модельный случай, а именно, когда $L$ -- это некоторое отображение $K^n \to K^m$, которое, как мы знаем, задаётся некоторой матрицей $A \in M_{m\times n}(K)$. Тогда задача описать все решения уравнения $Ax=y$ равносильна решению системы линейных уравнений, которую  мы уже умеем решать методом Гаусса.

Прежде всего ответим на вопрос: верно ли, что число параметров в методе Гаусса равно размерности соответствующего аффинного подпространства? 

\thrm Пусть дана система линейных уравнений $Ax=b$ c непустым множеством решений $W$. Тогда число параметров, задающих общее решение системы после использования метода Гаусса, равно размерности соответствующего пространства решений.
\ethrm
\proof Пусть переменные в методе Гаусса $x_{i_1}, \dots,x_{i_s}$ -- любые, а остальные выражаются через них следующим образом
$$x_{i}=t_i+ \sum c_{ij} x_{i_j}, \text{ при всех $i \notin \{i_1,\dots, i_k\}$}.$$ 
Тогда набор $x_{i_1}=\dots=x_{i_k}=0, \,\, x_i=t_i, \text{ при всех $i \notin \{i_1,\dots, i_s\}$}$ является решением системы. Обозначим этот столбец за $v_0$. Вычитая  $v_0$ произвольного решения системы $x$ мы должны получить произвольный элемент ядра. С другой стороны, координаты $x-v_0$ определяются по $x_{i_1}, \dots,x_{i_s}$  по формуле
$$x_{i}=\sum c_{ij} x_{i_j}, \text{ при всех $i \notin \{i_1,\dots, i_s\}$}.$$
 Заметим, что тогда мы получили взаимооднозначное линейное отображение $K^s \to \Ker A$, то есть изоморфизм. Следовательно, $\dim \Ker A = s$, что и есть число параметров.
\endproof


 

Как же найти частное решение $x_0$ системы $Ax=y$? Для этого надо решить систему методом Гаусса и подставить конкретные значения для свободных переменных. Проще всего подставить нули, что мы и сделали при доказательстве теоремы про число параметров. Как теперь описать ядро? Метод Гаусса даёт параметрическое описание ядра. Нас же может интересовать базис ядра. Заметим, что подобное параметрическое описание даёт  изоморфизм $K^s \to \Ker A$. При изоморфизме базис переходит в базис, следовательно взяв стандартный базис $K^s$ в качестве его образов получим базис ядра. Разберём пример:

Пусть $$A=\pmat
1 & 2 & -1 & 2\\
0& 1& 0 & 1\\
1& 0 & -1 & 0\epmat, \,\,b= \pmat -1\\ -1\\ 1 \epmat.$$
Решаем систему
$$\pmat
1 & 2 & -1 & 2 & -1\\
0& 1& 0 & 1 & -1\\
1& 0 & -1 & 0 & 1\epmat \sim
\pmat 1& 0 & -1 & 0 & 1 \\
0& 1& 0 & 1 & -1\\
0 & 2 & 0 & 2 & -2
\epmat \sim \pmat 1& 0 & -1 & 0 & 1 \\
0& 1& 0 & 1 & -1\\
0 & 0 & 0& 0 & 0
\epmat.$$
Параметра два -- это $x_3,x_4$. Берём $x_3=x_4=0$. Тогда $x_2=-1$, $x_1=1$. Итого $$v_0=\pmat 1\\ -1\\0 \\ 0 \epmat.$$ 
Ищем базис ядра. Для этого переходим к системе 
$$\pmat 
1& 0 & -1 & 0 & 0 \\
0& 1& 0 & 1 & 0\\
0 & 0 & 0& 0 & 0
\epmat.$$
Подставляем стандартные вектора из $K^2$. Берём $x_3=1$, $x_4=0$. Тогда $x_2=0,x_1=1$. Берём $x_3=0$, $x_4=1$. Тогда $x_1=0,x_2=-1$. Итого базис состоит из двух векторов 
$$v_1=\pmat 1\\0\\1\\0 \epmat, \, v_2=\pmat 0 \\ -1 \\ 0 \\ 1 \epmat.$$
Общее решение описывается как 
$$\pmat 1\\ -1\\0 \\ 0 \epmat+ \lan \pmat 1\\0\\1\\0 \epmat, \pmat 0 \\ -1 \\ 0 \\ 1 \epmat \ran.$$

\section*{Дополнительно: больше слов про аффинность и немного другое доказательство про число параметров в методе Гаусса}

\dfn Пусть $U$ и $V$ векторные пространства. Тогда отображение $T\colon U \to V$ называется аффинным, если существует линейное отображение  $L$ и вектор $v_0 \in V$, что $T(x)=L(x)+v_0$.  
\edfn

\rm Отображение $L$ и вектор $v_0$
определены однозначно Прежде всего $v_0=T(0)$. Далее $L(x)=T(x)-v_0$. Говорят, что отображение $L$ -- это дифференциал $T$ и обозначают $L=dT$. Это имеет прямое отношение к дифференциалу из математического анализа.
Если $T \colon U \to V$ аффинное с дифференциалом $L$, то $\im T$ аффинное и $\dim \im T= \dim \im L$, так как $T(U)=L(U)+v_0$. 
\erm


\begin{thmm} Пусть $T \colon U \to V$ инъективное аффинное отображение. Тогда $\dim U = \dim \im T$. 
\end{thmm}
\proof Если отображение $T$ инъективно, то и его дифференциал инъективен ( иначе бы $T$ склеивало те же точки, что и $L$). Тогда $\dim U = \dim L(U)= \dim T(U)$.
\endproof

\crl Пусть дана система линейных уравнений $Ax=b$ и множество её решений $W$ не пусто. Тогда число параметров задающих общее решение системы после использования метода Гаусса равно размерности $W$. 
\proof Пусть переменные в методе Гаусса $x_{i_1}, \dots,x_{i_s}$ -- любые, а остальные выражаются через них следующим образом
$$x_{i}=t_i+ \sum c_{ij} x_{i_j}, \text{ при всех $i \notin \{i_1,\dots, i_k\}$}.$$ 
Это задаёт аффинное взаимооднозначное соответствие между $K^s \to W$. Тогда $s=\dim W$.
\endproof
\ecrl







\section{Матрица линейного отображения}
Итак, у нас есть модельная задача: пусть $A \colon K^n \to K^m$ линейное отображение и элемент $y \in K^m$. Необходимо описать прообраз элемента $y$, то есть решить систему линейных уравнений $Ax=y$. Про эту задачу мы понимаем всё.
Наша текущая задача -- научиться сводить общую задачу к модельной. Однако тут возникает нюанс -- это можно сделать разными способами. Точнее:

\dfn
Пусть $V_1$, $V_2$ - векторные пространства над полем $K$ с базисами $e_1,\dots, e_n$ и $f_1,\dots, f_m$ соответственно. Пусть $L\colon V_1\to V_2$ - линейное отображение. Рассмотрим диаграмму:

\begin{center}
\begin{tikzpicture}
\node (A) at (1, 1) {$V_1$};
\node (B) at (0, 0) {$K^n$};
\node (C) at (3, 1) {$V_2$};
\node (D) at (4, 0) {$K^m$};
\path[->,font=\scriptsize,>=angle 60]
(A) edge node[above]{$L$} (C)
(A) edge node[above,rotate=45]{$\sim$} (B)
(C) edge node[above,rotate=-45]{$\sim$} (D);
\path[->,font=\scriptsize,>=angle 45]
(B) [bend left] edge node[below]{$A$}  (D);
\end{tikzpicture}
\end{center}

Сквозная композиция $f \circ L \circ e^{-1}$ задаёт линейное отображение из $K^n\to K^m$, то есть матрицу $A$. Матрица $A$ называется матрицей линейного отображения $L$ в базисах $e_1,\dots, e_n$ и $f_1,\dots, f_m$. 

Это даёт следующий рецепт для вычисления матрицы $A$ -- $i$-ый столбец матрицы $A$ состоит из координат $L(e_i)$ в базисе $f_1,\dots, f_m$.
\edfn


\exm \\
0) Пусть $V$ векторное пространство с базисом $e_1,\dots,e_n$. Тогда матрица тождественного отображения $\id \colon V \to V$ из базиса $e$ в базис $e$ есть единичная матрица 
$$E_{n}=\pmat 
1&&\\
&\ddots& \\
& &1
\epmat.$$
1) Рассмотрим произвольный базис $V$ $v_1,\dots,v_n$. Тогда  матрица отображения $V\to V$, заданного как  $x \to \lambda x$  из этого базиса  в себя равна
$$ \lambda E_n=\pmat \lambda & & \\
 & \ddots &\\
&  & \lambda
\epmat.$$
2) Рассмотрим пространство $V=K[x]_{\leq 3} $, где $\chr K \neq 2,3$ и отображение $L\colon V \to K^3$, заданное как $f \to (f(-1),f(0),f(2))$. Его матрица в стандартных базисах имеет вид 
$$\bordermatrix{
    &1& x&x^2&x^3\cr
e_1\, &1&-1&1  &-1 \cr
e_2\, &1& 0&0  &0  \cr
e_3\, &1& 2&4  &8  
}.$$
Найдём ядро этого отображения. Для этого сначала решим однородную систему
$$\pmat 1&-1&1  &-1 \\
1& 0&0  &0  \\
1& 2&4  &8
\epmat \sim 
\pmat 1& 0&0  &0  \\
0&-1&1  &-1 \\
0& 2&4  &8 \epmat  \sim 
\pmat 1& 0&0  &0  \\
0&-1&1  &-1 \\
0& 0&6  &6 \epmat$$
Размерность ядра матрицы единица. Оно порождено вектором $\pmat 0\\ -2\\-1\\1\epmat $, которому соответствует многочлен $$x^3-x^2-2x=x(x+1)(x-2).$$ Что, в общем, и ожидалось исходя из наших знаний про многочлены.\\
3) Рассмотрим линейное отображение из пространства $K[x]_{\leq n} \to K[x]_{\leq n}$ заданное по правилу $f(x) \to f(x+1)$. Найдём его матрицу. Рассмотрим базис $1,\dots, x^n$ справа и слева. Получим матрицу $a_{i,j}=C_{j-1}^{i-1}$
$$
\pmat
1& 1& \dots & 1  & 1 \\
& 1  & \dots & C_{n-1}^{n-2}& C_{n}^{n-1}\\ 
 &  & \ddots &\vdots &\vdots \\
& &  & 1  & C_{n}^{1} \\
 &  & &  &1
\epmat
$$
4) А ещё для того же отображения можно выбрать базисы $1,x,\dots,x^n$ и $1,x+1,\dots,(x+1)^n$. Получится матрица 
$$E_{n+1}=\pmat 
1&&\\
&\ddots& \\
& &1
\epmat.$$
Видно, что матрица линейного отображения очень чувствительна к замене базиса.

\lm Пусть $L_1,L_2\colon U \to V$ и $e$ -- базис $U$, а $f$ -- базис $V$. Тогда матрица $L_1+L_2$ в базисах $e$ и $f$ есть сумма матриц $L_1$ и $L_2$. Аналогично про домножение на скаляр. 
\elm
\proof Пусть $L_1 e_j= \sum A_{ij}f_i$, а $L_2=\sum B_{ij}f_i$. Тогда $L_1(e_j)+L_2(e_j)=\sum (A_{ij}+B{ij})f_i$, что и доказывает требуемое.
\endproof

\crl Пусть пространства $U$ и $V$ имеют размерности $n$ и $m$. Допустим выбраны базисы $e_1,\dots,e_m$ и $f_1,\dots,f_m$ пространств $U$ и $V$ соответственно. Тогда сопоставление линейному отображению $L \in \Hom(U,V)$ его матрицы в указанных базисах есть изоморфизм 
$$\Hom(U,V) \stackrel{\sim}{\longrightarrow} M_{m\times n}(K).$$
\ecrl





Пусть есть две матрицы $A\in M_{n\times m}(K)$ и $B\in M_{m\times l}(K)$. Какая матрица соответствует композиции линейных отображений, построенных по $A$ и $B$?

\dfn
Определим произведение $C=A\cdot B$ следующим образом: 
$$C_{ij}= \sum_{1\leq k\leq m} A_{ik} B_{kj}$$
Иными словами надо взять $i$-ую строку $A$, $j$-ый столбец $B$, и их перемножить.
\edfn

\rm Можно смотреть на произведение матриц немного по другому. Точнее, $j$-ый столбец $AB$ получается как произведения $j$-го столбца $B$ на матрицу $A$. Это тоже самое, что взять линейную комбинацию столбцов матрицы $A$ с коэффициентами из $j$-го столбца матрицы $B$. Аналогично $i$-ая строка $AB$ это линейная комбинация строк $B$ с коэффициентами из $i$-ой строки $A$. Произведение матриц ассоциативно, так как ассоциативна композиция линейных отображений.
\erm

\thrm Пусть $U$, $V$, $W$ пространства с базисами $e_1,\dots,e_n$, $f_1,\dots,f_m$, $g_1,\dots,g_l$. Пусть $L\colon U \to V$ и $T\colon V \to W$ два линейных отображения. Пусть $A$ и $B$ матрицы $T$ и $L$ в парах базисов $v$,$w$  и $u$, $v$. Тогда матрица $T \circ L$ в базисах $u$, $w$ равна произведению $AB$.
\proof По определению это свойство верно, если речь  идёт о композиции линейных отображений между $K^n$ в стандартных базисах. Матрица композиции $T \circ L$ по определению соответствует линейному отображению 
$$g\circ T \circ L \circ e^{-1}=(g \circ T \circ f^{-1}) \circ (f \circ L \circ e^{-1})=AB.$$
\endproof
\ethrm

Какая матрица соответствует изоморфизму? Та, которая осуществляет изоморфизм пространств $K^n$ и $K^m$.



\dfn Матрица $A \in M_{m\times n}$ называется обратимой, если существует $B \in M_{n\times m}$, что $AB=E_m$, $BA=E_n$.  Матрица $B$ называется обратной к $A$ и обозначается $A^{-1}$.
\edfn



\crl Если матрица $A \in M_{n\times m}$ обратима, то $n=m$. Обратная матрица единственна.
\proof Обратимая матрица осуществляет изоморфизм пространства $K^n$ и $K^m$.  Но если пространства изоморфны, то их размерности равны, то есть $n=m$.
\endproof
\ecrl

\crl Квадратная $A\in M_n(K)$ обратима тогда и только тогда, когда $\rank A =n$. Обратимые матрицы так же называются невырожденными. 
\proof Следует из принципа Дирихле для линейных отображений.
\endproof
\ecrl

\dfn Пусть $V$ -- пространство. Определим полную линейную группу $\GL(V)$ как множество всех изоморфизмов из $V\to V$ относительно композиции. Если $V=K^n$, то для $\GL(K^n)$ имеется специальное обозначение: $\GL_n(K)$. Элементы из $\GL_n(K)$ -- это обратимые матрицы.
\edfn

\exm\\
0) Обратная к единичной матрице -- это единичная матрица.\\
1) Очевидно отображение $L \colon f(x) \to f(x+1)$ на пространстве $K[x]_{\leq n}$ имеет обратное $U \colon f(x)\to f(x-1)$. Матрица первого отображения -- $A$ нам известна. Матрица второго находится аналогично и равна
$$
B=\pmat
1& -1& \dots & (-1)^{n-1}  & (-1)^n \\
& 1  & \dots & (-1)^{n-2}C_{n-1}^{n-2}& (-1)^{n-1}C_{n}^{n-1}\\ 
 &  & \ddots &\vdots &\vdots \\
& &  & 1  & -C_{n}^{1} \\
 &  & &  &1
\epmat
$$
Тогда $A\cdot B=E_{n+1}$. Что же это значит? Посмотрим, что даёт это очевидное равенство. Перемножим последний столбец матрицы $B$ и первую строчку $A$. Получим
$$0=\sum_{i=0}^{n}(-1)^{i}C_{n}^{i}.$$
Посмотрим, что получится, если взять вторую строчку $A$ при $n \geq 2$
$$0=\sum_{i=0}^{n}(-1)^{i}iC_{n}^{i}.$$
Вообще тождества, происходящие из очевидных равенств с многочленами -- очень широкая степь.\\

Настала пора ответить на следующий вопрос: что происходит с матрицей линейного отображения, если мы заменим базисы пространств?



\dfn Рассмотрим пространство $V$ размерности $n$ и два базиса $e_1,\dots,e_n$ -- старый и $f_1,\dots,f_n$ -- новый. Имеем связанную с ними диаграмму.
\begin{center}
\begin{tikzpicture}
\node (A) at (1, 1) {$V$};
\node (B) at (0, 0) {$K^n$};
\node (C) at (-1, 1) {$K^n$};
\path[->,font=\scriptsize,>=angle 60]
(A) edge node[above left]{$f$} (B)
(A) edge node[above]{$e$} (C);
\path[->,font=\scriptsize,>=angle 45]
(C) [bend left] edge node[below left]{$\color{red} {C_e^f}$}  (B);
\end{tikzpicture}
\end{center}
Здесь $e$ и $f$ обозначают координатные отображения  для соответствующих базисов. Так как $u$ обратимо, то можно определить отображение $C_{e}^f=f\circ e^{-1}$. Матрица соответствующая $C_{e}^f$ называется матрицей замены из базиса $e$ в базис $f$. 
\edfn


Это отображение устроено следующим образом: оно берёт столбец $x$ и сопоставляет ему вектор $v=\sum x_i e_i$, у которого ровно такие координаты, а затем считает его координаты в новом базисе. То есть матрица $C$ -- это способ пересчитать координаты вектора из старого базиса в новый. Точнее

\rm Если есть вектор $v$ и его координаты в базисе $e_1,\dots,e_n$ это столбец $x$, а координаты в базисе $f_1,\dots,f_n$ -- это столбец $y$, то верно соотношение 
$$y=Cx.$$
\erm

Как найти матрицу $C$? Для этого рассмотрим вектор $i$-ый вектор из стандартного базиса $K^n$ и посмотрим, что с ним происходит. Он переходит в вектор $e_i$, а теперь нужно разложить $$e_i= \sum_{j=1}^n C_{ji} f_j.$$
Тогда коэффициенты $C_{ji}$ и будут составлять $i$-ый столбец матрицы $C$, что и объясняет выбранную для них индексацию. 
Это соотношение удобно записать в такой форме
$$(e_1,\dots,e_n)=(f_1,\dots,f_n)\cdot C$$
или
$$\pmat e_1 \\ \vdots\\ e_n \epmat =C^{\top} \pmat f_1 \\ \vdots \\ f_n \epmat $$

\dfn Пусть $C\in M_{m \times n}(K)$. Тогда транспонированной к $C$ называется матрица $C^{\top} \in M_{n \times m}(K)$ с элементами $C^{\top}_{ij}=C_{ji}$.
\edfn


\rm Имеют место следующие соотношения $C_f^e= (C_e^f)^{-1}$ и $C_f^gC_e^f= C_e^g$. Действительно $C_f^e=e\circ f^{-1}= (f\circ e^{-1})^{-1}= (C_f^e)^{-1}$. Далее $C_f^gC_e^f= g \circ f^{-1} \circ f \circ e^{-1}= g \circ e^{-1}= C_e^g$.
В частности, матрица замены базиса всегда обратима. Любая обратимая матрица есть матрица замены из заданного базиса в какой-то.
\erm



Теперь можно разобраться с ситуацией про замену базиса. Пусть даны пространства $V$, $W$ и линейное отображение $L\colon V\to W$. Рассмотрим в пространстве $V$ два базиса $e_1,\dots, e_n$ (старый) и $e_1',\dots, e_n'$ (новый). Аналогично в $W$ --- $f_1,\dots, f_m$ (старый) и $f_1',\dots, f_m'$ (новый). Нарисуем диаграмму


\begin{center}
\begin{tikzpicture}
\node (A) at (1, 1) {$V$};
\node (B) at (0, 0) {$K^n$};
\node (C) at (3, 1) {$W$};
\node (D) at (4, 0) {$K^m$};
\node (E) at (-1, 1) {$K^n$};
\node (F) at (5, 1) {$K^m$};
\path[->,font=\scriptsize,>=angle 60]
(A) edge node[above]{$\color{red} L$} (C)
(A) edge node[above left]{ $e'$} (B)
(C) edge node[above right]{$f'$} (D)
(A) edge node[above]{ $e$} (E)
(C) edge node[above]{ $f$} (F);
\path[->,font=\scriptsize,>=angle 45]
(B) [bend left] edge node[below]{$\color{red} {A'}$}  (D)
(E) [bend left] edge node[above]{$\color{red}{A}$ } (F)
(E) [bend left] edge node[below left]{$\color{red}{C}$ } (B)
(F) [bend right] edge node[below right]{$\color{red}{D}$}  (D);
\end{tikzpicture}
\end{center}

\thrm
В указанных предположениях матрицу $A'$ линейного отображения $L$ в базисах $e'$ и $f'$ можно выразить через матрицу $A$ и матрицы замены $C$ и $D$ следующим образом
$$A'=DAC^{-1}.$$
\ethrm 
\proof $$A'=f'\circ L\circ {e'}^{-1}= f'\circ f^{-1} \circ f\circ L\circ e^{-1}\circ e\circ{e'}^{-1}= D A C^{-1}$$
\endproof




\section{Свойства ранга}

Наша ближайшая задача -- классифицировать все линейные отображения. Для этого мы посмотрим на их численную характреистику -- ранг. Ранг линейного отображения отвечает за его обратимость и за размерность множества решений уравнения $Lx=y$. Исследуем свойства ранга.

\lm Пусть $S \colon V \to W$, $T \colon W \to U$, тогда $$\rank T \circ S \leq \min(\rank T, \rank S).$$
\proof Для начала покажем, что если есть $L\colon V_1 \to V_2$ и $V' \leq V_1$, то $\dim L(V') \leq \dim V'$. Действительно $$\dim V'= \dim \im L|_{V'} + \dim \Ker L|_{V'} \geq \dim L(V').$$
Теперь $\im T \circ S \subseteq  \im T$, поэтому $\rank T \circ S \leq \rank T$. 
Далее $\rank T \circ S= \dim \im T \circ S = \dim T (S(V)) \leq \dim S(V)= \rank S.$ Что и требовалось.
\endproof
\elm

\lm Пусть $S, T \colon V \to W$ -- два линейных отображения. Тогда $$\rank (T + S) \leq \rank T + \rank S.$$
\elm
\proof Для начала покажем, что, если $V_1,V_2 \leq V$, то $\dim V_1 +V_2 \leq \dim V_1 + \dim V_2$. Действительно, если $e_1,\dots, e_k$ базис  $V_1$, и $f_1,\dots, f_l$ базис $V_2$, то $e_1,\dots, e_k, f_1, \dots, f_l$ порождает $V_1+V_2$. Осталось заметить, что размер базиса меньше размера любой порождающей системы.
Теперь заметим, что $\im (S+T) \leq \im S + \im T$. Тогда $\rank (S+T) \leq \dim (\im S + \im T) \leq \rank S + \rank T$. 
\endproof

\lm[Ранг не меняется при подкрутке на изоморфизмы] Пусть $L \colon U_1 \to V_1$ -- линейное отображение, а $G \colon U_1 \to U_2 $ и $H \colon V_1 \to V_2$ изоморфизмы. Тогда $\rank (H \circ L \circ G^{-1}) = \rank L$.
\elm
\proof Для начала покажем, что, если некоторое линейное отображение $T\colon V \to W$ обратимо, то  $\dim T(U)= \dim U$ для любого $U \leq V$. Действительно, если $T$ обратимо, то оно инъективно и его сужение на $U$ тоже инъективно. Тогда $\dim U = \dim T(U) + \dim \ker T|_U= \dim T(U)$.
Заметим, что если $G$ обратимо, то  $G^{-1}$ тоже и, следовательно, сюръективно. Тогда $G^{-1}(X)=U$.  Теперь $\rank L= \dim L(U)= \dim H(L(U))= \dim H(L(G^{-1}(X))= \rank H \circ L \circ G^{-1}$.
\endproof

\thrm Пусть $U_1, U_2$ и $V_1,V_2$ векторные пространства над полем $K$, причём  $\dim U_1=\dim U_2$ и $\dim V_1 =\dim V_2$. Пусть $L \colon U_1\to V_1$ и $T \colon U_2 \to V_2$ -- линейные отображения. Тогда условие $\rank L=\rank T$ равносильно существованию изоморфизмов 
$$G \colon U_1 \to U_2 \text{ и }  H \colon V_1 \to V_2, \text{ что }  H \circ L \circ G^{-1}=T$$
\ethrm
\proof Для того, чтобы построить $H$ и $G$ нужно выбрать подходящие базисы пространств. Рассмотрим базис $e_1,\dots, e_k$ пространства $\Ker T$ и дополним его элементами $e_{k+1},\dots, e_n$ до базиса $U_1$. Так как $\dim \Ker L = \dim \Ker T$ (благодаря равенству рангов), то аналогично можно построить базис $f_1,\dots, f_k$ ядра $\Ker T$ и дополнить его $f_{k+1},\dots, f_n$ до базиса $U_2$. 

Построим линейное отображение $G\colon U_1 \to U_2$ по правилу $G(e_i)=f_i$. Это обратимое линейное отображение.

Теперь заметим, что образы $L(e_{k+1}), \dots, L(e_n)$ являются базисом $\im L$ и, аналогично, $T(f_{k+1}), \dots, T(f_n)$  являются базисом $\im T$. Тогда дополним их элементами $g_1,\dots,g_l$ и $ g_1',\dots, g_l'$ до базисов $V_1$ и $V_2$. Тогда  зададим $H(L(e_i))=T(f_i)$ и $H(g_i)=g_i'$. 

Проверим теперь, что $H \circ L \circ G^{-1}=T$. Рассмотрим базисный элемент $f_i$. Тогда $G^{-1}(f_i)=e_i$. Далее, если $i<k$, то  $H(L(G^{-1}(f_i)))= H(L(e_i))=0=T(f_i)$. В оставшемся случае $H(L(G^{-1}(f_i)))= H(L(e_i))=T(f_i)$ по выбору $H$.
\endproof


Напомню, что ранг матрицы -- это ранг соответствующего линейного отображения. Иными словами, это размерность пространства, порождённого столбцами матрицы.

\crl Для любой матрицы $A \in M_{m \times n}$ ранга $r$ существуют обратимые матрицы $C$ и $D$, что $CAD^{-1}$ имеет вид 
$$\pmat E_r& 0\\
0&0\\
\epmat.$$
\ecrl


Однако, в методе Гаусса удобно смотреть на строчки, чем на столбцы. Это замечание приводит нас к определению строчного ранга.

\dfn Пусть $A\in M_{m\times n}(K)$. Определим $\rank_{row}$ -- cтрочный ранг матрицы $A$ как размерность пространства, порождённого её строками.
\edfn

\rm Очевидно равенство $\rank_{row} A= \rank A^{\top}$.
\erm

Поэтому исследуем свойства операции транспонирования матрицы.

\lm Пусть $A,B$ -- матрицы. Тогда\\
0) ${A^{\top}}^{\top}=A$.\\
1) $(A+\lambda B)^{\top}= A^{\top}+\lambda B^{\top}$.\\
2) $(AB)^{\top}=B^{\top}A^{\top}$.\\
3) $(A^{\top})^{-1}= (A^{-1})^{\top}$.
\elm
\proof Покажем второй пункт. Имеем
$$(AB)^{\top}_{ij}= (AB)_{ji}=\sum_k A_{jk}B_{ki}=\sum_k B^{\top}_{ik}A^{\top}_{kj}=(B^{\top}A^{\top})_{ij}.$$
Теперь покажем пункт 3. Пусть $AA^{-1}=E_n$. Тогда $E_n=E_n^{\top}=(AA^{-1})^{\top}= (A^{-1})^{\top}A^{\top}$. Аналогично из равенства $A^{-1}A=E_n$ следует $E_n=A^{\top}(A^{-1})^{\top}$, что завершает доказательство. 
\endproof

\rm Заметим, что, вообще говоря, проверять второе условие не обязательно. Действительно, предположим, что $BA=E_n$, где $A,B$ квадратные матрицы размера $n$. Покажем, что тогда $B=A^{-1}$. Заметим, что матрица $A$ имеет нулевое ядро так как в противном случае матрица $E_n$ имела бы нетривиальное ядро. Тогда матрица $A$ обратима по принципу Дирихле, потому что обратимо соответствующее линейное отображение. Тогда $B=BAA^{-1}=E_nA^{-1}=A^{-1}$.
\erm

\thrm Пусть $A\in M_{m \times n}(K)$. Тогда ранг по строчкам и ранг по столбцам совпадают.  
\ethrm
\proof Представим матрицу $A$ в виде произведения 
$$A=C \pmat E_r & 0\\
0 & 0 \epmat D,$$
где $C \in \GL_m(K)$, а $D \in \GL_n(K)$, а $r$ -- ранг матрицы. Тогда 
$$A^{\top}=D^{\top} \pmat E_r & 0\\
0 & 0 \epmat C^{\top}.$$
Так как ранг не меняется при домножении на обратимые матрицы, то $\rank A^{\top} = \rank \pmat E_r & 0\\
0 & 0 \epmat = r = \rank A$. 
\endproof

Есть и другое определение -- минорный ранг.

\dfn Пусть $A \in M_{m\times n}(K)$ и  даны два множества индексов $I=\{i_1< \dots< i_k\}\subseteq \ovl{1,m}$, $J=\{j_1< \dots < j_l\}\subseteq \ovl{1,n}$. Подматрицей $A_{I,J} \in M_{k\times l}$ определим так, чтобы ${A_{I,J}}_{s,t}=a_{i_s,j_t}$.   
\edfn

\dfn[Минорный ранг] Пусть $A \in M_{m\times n}(K)$. Минорный ранг матрицы $A$ -- это наибольшее такое $k$, что существует невырожденная квадратная подматрица $A_{I,J}$ размера $k$ внутри $A$. 
\edfn

\thrm Ранг матрицы равен её минорному рангу.
\ethrm
\proof Пусть $A$ -- матрица ранга $r$. Тогда в матрице $A$ есть $r$ линейно независимых столбцов $v_1,\dots,v_r$. Составим из них матрицу $A'$. Ранг $A'$ равен $r$. Теперь, так как строчный и столбцовый ранги совпадают, то в $A'$ есть $r$ линейно независимых строк. Они дают крадратную невырожденную подматрицу в $A'$ и следовательно в $A$.  
\endproof


\begin{comment}
\rm Пусть есть матрица составленная из столбцов $v_1,\dots,v_n$. Что значит, что её минорный ранг равен $k$? По определению это значит, что можно выбрать $k$ столбцов и $k$ стандартных базисных векторов $e_{i_1},\dots,e_{i_k}$ так, чтобы проекция на подпространство $U=\lan e_{i_1},\dots,e_{i_k}\ran$ дала базис этого пространства. Таким образом любое подпространство размерности $k$ изоморфно проецируется на некоторое координатное подпространство размерности $k$.
\erm
\end{comment}

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

Для этого покажем, что элементарное преобразование можно реализовать домножив исходную матрицу на некоторую обратимую матрицу. Точнее, рассмотрим матрицу
$$ E_{ij}(\lambda)=E_n +\lambda e_{ij}= 
\bordermatrix{
 & &j&& \cr
 &1&\cdots&\cdots&0\cr
 &\vdots&\ddots && \vdots\cr
i&\vdots& \lambda & \ddots& \vdots\cr
 &0&\cdots& \cdots&1
}.
$$\\
Домножение на матрицу $E_{ij}(\lambda)$ приводит к тому, что матрица
$$A'=E_{ij}(\lambda)A.$$
получается из матрицы $A$ прибавлением $j$-ой строки к $i$-ой с коэффициентом $\lambda$. 
Действительно, домножение матрицы $A$ на матрицу $e_{ij}$ выделяет из матрицы $A$ $j$-ую строку и записывает её на позицию $i$.

\dfn Матрица $E_{ij}(\lambda)$ называется матрицей элементарного преобразований первого типа.
\edfn



Что соответствует замене местами двух строк матрицы $A$? Для этого надо поставить $i$-ую строчку в позицию $j$ и наоборот, а остальные строки оставить на месте. Итого имеем матрицу
$$T_{(ij)}=\,\bordermatrix{
 & & &j& & i& \cr
 &1& & & & & &0\cr
 & &\ddots & & & & \cr
j\,& && 0 & & 1 & &\cr
\,& &&  & &  & &\cr
i\,& && 1 & &0 & &\cr
 & & & & & & \ddots& \cr
 &0& & & & & &1
}=E_n- e_{ii}-e_{jj}+e_{ij}+e_{ji}.
$$


\dfn Матрица $T_{(ij)}$ называется матрицей элементарного преобразований второго типа или матрицей транспозиции.
\edfn

А что вообще происходит при перестановке строк? Каждой перестановке $\sigma \in S_n$ однозначно соответствует матрица $T_{\sigma}$ заданная правилом 
$$(T_{\sigma})_{ij}= \begin{cases}
1, \text{ если $\sigma(j)=i$}\\
0, \text{ иначе }
\end{cases}.$$


\dfn Матрица $T_{\sigma}$ называется матрицей перестановки $\sigma$.
\edfn


\rm Заметим, что произведение $T_{\sigma} T_{\tau}=T_{\sigma\tau}$. Это даёт гомоморфизм из группы перестановок в группу $\GL_n(K)$. Любая матрица, у которой в каждом столбце ровно один единичный элемент, а все остальные 0 является матрицей перестановки. Можно написать аналогичное условие для строк. 
\erm

Наконец, преобразованию третьего типа соответствует матрица
$$ D_{i}(\lambda)= 
\bordermatrix{
 & &&i&& \cr
 &1&&&&0\cr
 &&\ddots &&& \cr
i&&  & \lambda && \cr
&&  &  &\ddots& \cr
 &0&& &&1
}.
$$

\dfn Матрица $D_{i}(\lambda)$, $\lambda \in K^*$ называется матрицей элементарного преобразований третьего типа.
\edfn

\rm Заметим, что $E_{ij}^{-1}(\lambda)= E_{ij}(-\lambda)$ и $D_i(\lambda)= D_i(\lambda^{-1})$, а $T_{ij}^{-1}=T_{ij}$.
\erm

Прежде чем пойти дальше сформулируем давно напрашивающиеся определения про преобразования столбцов, которые нам пригодятся в дальнейшем. 

\dfn Определим элементарные преобразования столбцов матрицы $A\in M_{n \times m}(K)$ следующим образом:\\
1) Преобразование первого типа соответствует домножению
$$A \to A E_{ij}(\lambda),$$
которое приводит к тому, что $i$-ый столбец прибавляется к $j$-ому с коэффициентом $\lambda$.\\
2) Преобразование столбцов второго типа -- это перестановка $i$-го  и $j$-го столбца местами, что соответствует домножению на $T_{(ij)}$ 
$$A \to A T_{(ij)}.$$
3) Преобразование третьего типа -- это домножение на $D_i(\lambda)$ -- умножение $i$-го столбца на $\lambda \in K^*$.
\edfn

\thrm
Элементарные преобразования строк и столбцов не меняют ранг матрицы.

\ethrm
\proof Преобразования строк и столбцов соответствуют домножениям на обратимые матрицы и поэтому не меняют ранг.  
\endproof

Приведём пример использования свойства ранга. Для этого посмотрим на пример с поисковой системой. Пусть $G$ граф на $n$ вершинах. Тогда рассмотрим квадратную матрицу $P(G)$ размера $n$
$$P(G)_{ij}= \begin{cases} \frac{1}{d_j^{out}}, \text{ если есть ребро $j \to i$} \\
0, \text{ иначе }
\end{cases}.$$
Эта матрицу еще называется матрицей случайного блуждания на графе $G$. Смысл состоит в том, что она моделирует следующую ситуацию -- если мы с вероятностями $w_1,\dots,w_n$ находимся в вершинах графа и на следующем шаге хотим из $j$-ой вершины перейти в $i$-ую по ребру графа, при этом проход по каждому ребру равновероятен, то после такого действия новый набор вероятностей будет иметь вид $P(G)w$. Матрица $P$ обладает тем свойством, что сумма элементов в каждом столбце равна 1. 

Теперь систему для нахождения <<важностей>> вершин графа можно переписать в виде $E_n w= P(G)w$ или 
$$(E_n - P(G))w=0.$$
Нам хочется показать, что у этой системы есть нетривиальное решение, то есть, что ранг матрицы $E_n- P(G)$ строго меньше $n$. Для этого можно показать, что ранг 
$$E_n - P(G)^{\top}$$
меньше $n$, а это легко сделать -- достаточно заметить, что матрица $E_n - P(G)^{\top}$  имеет столбец $(1,1,\dots, 1)^{\top}$ в своём ядре. Заметьте -- это не помогает найти решение исходной системы, а лишь доказывает его существование.






\section{Прямая сумма и фактор}

\dfn[Прямая сумма и прямое произведение] Рассмотрим набор векторных пространств $U_{\alpha}$ над полем $K$,  где элементы $\alpha$ пробегают множество индексов $I$. Определим прямую сумму пространств из семейства $U_{\alpha}$, как множество
$$\prod_{\alpha \in I} U_{\alpha}$$
вместе с операциями $$(u_{\alpha})_{\alpha\in I}+ (v_{\alpha})_{\alpha\in I}=(u_{\alpha}+v_{\alpha})_{\alpha\in I},\,\,\, \lambda \cdot (u_{\alpha})_{\alpha\in I}= (\lambda \cdot u_{\alpha})_{\alpha\in I}.$$
То есть операции покомпонентные. Определим прямую сумму набора $U_{\alpha}$ как подпространство в $\prod_{\alpha \in I} U_{\alpha}$, заданное следующими условиями
$$\bigoplus_{\alpha \in I } U_{\alpha}=\left\{ (u_{\alpha})_{\alpha \in I} \,|\, \text{ все, кроме конечного числа компонент $u_{\alpha}$ равны 0}\right\}.$$
\edfn

\rm Прямая сумма конечного числа пространств совпадает с прямым произведением. Обычно мы будем использовать значок прямой суммы $U_1\oplus \dots \oplus U_n$.
\erm


\rm $\dim U_1\oplus \dots \oplus U_n= \sum \dim U_i$.
\erm

Применим это нехитрое соображение.


\lm[Формула Грассмана] Пусть $U$ и $V$ подпространства некоторого $W$ тогда имеет место соотношение
$$\dim U +\dim V = \dim U\cap V + \dim (U+V).$$

\proof Рассмотрим последовательность отображений
$$U\cap V \stackrel{v\to (v,-v)}{\longrightarrow} U\oplus V \stackrel{(u,v)\to u+v}{\longrightarrow} W$$
Заметим, что образ отображения $L$ из $U\oplus V \to W$ это в точности $U+V$. Когда пара элементов $(u,v)$ лежит в ядре $L$? Когда $u=-v$. То есть лежит в образе $U \cap V$. Так как отображение из $U\cap V$ инъективно, то $U\cap V \cong \Ker L$. Тогда $\dim U\cap V = \dim \Ker L $. Осталось применить соотношение про связь размерности ядра и образа
$$\dim U+ \dim V = \dim U\oplus V= \dim(U+V)+\dim U\cap V.$$
\endproof
\elm

\dfn Пусть $W$ -- векторное пространство, а $U_1,\dots,U_n$ -- его подпространства. Будем говорить, что пространство $W$ раскладывается в прямую сумму $U_i$, если отображение $U_1\oplus \dots \oplus U_n \to W$ заданное по правилу $(u_1,\dots,u_n) \to u_1 +\dots+u_n$ является изоморфизмом.
\edfn

\thrm
Пусть $W$ -- векторное пространство, а $U_i$ его подпространства. Тогда следующие условия эквивалентны\\
1) $W$ раскладывается в прямую сумму $U_i$ \\
2) $\forall w \in W$, существуют единственные $u_i \in U_i$  $w=u_1+\dots+u_n$\\
3) $U_i\cap \bigoplus_{j\neq i} U_j= \{0\}$ и $\dim U_1 +\dots+ \dim U_n =\dim W$\\
\ethrm

Сделаем ещё несколько уточнений для случая двух подпространств:

\lm Пространство $W$ раскладывается в прямую сумму $U$   и $V$ тогда и только тогда, когда существует оператор $L \colon W \to W$, что $L^2=L$ и $U=\im L$, а $V=\Ker L$. Более того, такой оператор единственен.
\elm

\dfn Оператор, удовлетворяющий тождеству $L^2=L$ называется проектором.
 Любой проектор однозначно определяет пару $U$ и $V$. Проектор, соответствующий такой паре подпространств, называется проекцией на $U$ вдоль $V$.
\edfn

\rm Для любого подпространства $U \leq W$ существует пространство $V$, что $W=U\oplus V$.

  Пусть $U,V\leq W$ подпространства и верно, что $W=U\oplus V$. Рассмотрим каноническую проекцию $\pi \colon W \to W/U$. Тогда $\pi|_{V} \colon V \to W/U$ является изоморфизмом. 
\erm 

Последним замечанием станет следующие: пусть $L\colon V \to W$ -- линейное отображение, а пространства $V$ и $W$ разложены в прямую сумму $V=U_1\oplus U_2 $ и $W=U_1'\oplus U_2'$. Рассмотрим базисы  $U_1, U_2$ и $U_1', U_2'$. Тогда матрица $L$ в этих базисах имеет вид 
$$ \pmat A& B \\
C & D
\epmat,
$$
где матрица $A$ -- это матрица $pr_{U_1'}\circ L|_{U_1}$, $B=pr_{U_2'}\circ L |_{U_1}$ и т.д. Такую запись матрицы $L$ будем называть блочной. Если $C=0$, то матрица называется блочной верхнетреугольной. Если и $C=0$ и $B=0$, то матрица называется блочно диагональной.


\dfn[Пространство натянутое на множество]
Пусть $X$ множество. Рассмотрим множество функций $\lan X \ran = \{ f\colon X \to K\,|\, \text{ $f=0$ всюду, кроме кромне конечного числа точек} \}$. 
\edfn

Это множество, очевидно является подпространством в пространстве всех функций. Более того, с каждой точкой $x\in X$ можно связать функцию $$\delta_x(y)=\begin{cases} 1, \text{ если  $x=y$} \\
0, \text{ иначе }
\end{cases}$$
Набор таких функций образует базис $\lan X \ran$. Вместо сложного обозначения $\delta_x$, если не возникает противоречий, можно просто говорить про точку $x$. Тогда все элементы $\lan X \ran $ можно записать в виде $\lambda_1 x_1+\dots +\lambda_n x_n$. Про такое выражение говорят, что это формальная линейная комбинация элементов из $X$. Такой подход позволяет посмотреть на некоторые задачи, как на задачи из линейной алгебры, что в некоторых ситуациях приносит пользу, так как для задачи из линейной алгебры обычно имеют решение. Вот например:

Рассмотрим граф $G$ с множеством вершин $V$ и множеством рёбер $E$. 

Пусть на множестве рёбер задана ориентация. Определим отображение $\lan E \ran \to \lan V \ran$ заданное на базисе следующим образом: 

$$\text{ ребро $e$ идущее из вершины $u$ в вершину $v$ переходит в $v-u$}.$$

Матрица этого отображения имеет специальное название.

\dfn Определим матрицу инцидентности $B(G)$ размера $n\times m$, $n$ -- число вершин, а $m$ число рёбер $G$, так, что 
$$b_{ij}=\begin{cases} 1, \text{ если ребро $j$ входит в вершину $i$}\\
-1, \text{ если ребро $j$ исходит из вершины $i$}\\
0, \text{ иначе }
\end{cases}.$$
\edfn

Рассмотрим для простоты $K=\mb Z/2$. Тогда ориентация не нужна, так как никакого знака нет. Более того -- теперь любому элементу из $\lan E \ran $ однозначно соответствует подграф -- если коэффициент 1, то ребро есть, если 0, то нет. Посчитаем теперь некоторую характеристику матрицы $B$ 

\lm Размерность ядра матрицы инцидентности  равна $m-n+c$, где $m$ -- количество рёбер, $n$ -- количество вершин.
\elm
\proof Посчитаем коразмерность образа матрицы $B$ -- для этого мы придумаем уравнения на образ. Рассмотрим множество компонент связности  $C = \{ K_1,\dots,K_c\}$ графа $G$.

Построим отображение $\ffi \colon \lan V \ran \to \lan C \ran$ заданное по правилу $v \to K_i$ , если $v\in K_i$. Это отображение сюръективно. Я утверждаю, что $\Ker \ffi$ -- это в точности $\Im B$.

Формальная сумма $\sum a_v v$ лежит в ядре $\ffi$ тогда и только тогда, когда для любой компоненты связности $\sum_{v\in K_i} a_v=0$. Очевидно образ $B$ удовлетворяет этим  уравнениям (достаточно посмотреть на образ ребра).

Покажем, что любой элемнт $x= \sum_{v \in V} a_v v \in \lan V \ran$ с таким свойством лежит в $\Im B$. Покажем это индукцией по числу вершин с ненулевым $a_v$. Действительно, в компоненте связности $K_i$ не может быть одной вершины $v$, что $a_v\neq 0$ так как сумма весов в её компоненте связности была бы не нулевая.
Пусть есть хотя бы две вершины $u$ и $w$ в одной компоненте связности с $a_{u},a_{w}\neq 0$. Проведём путь $e_1\dots e_k$ из вершины $u \to w$. Тогда посмотрим на сумму $a_{u}(\sum e_i)$. Имеем $$B(a_{u}(\sum e_i))= a_{u}w - a_u u.$$
Заметим, что $a_{u}w - a_uu +x$ имеет по крайней мере на одну нулевую координату больше (обнулился коэффициент в вершине $u$ и, возможно, в $w$, остальные --) и, следовательно, по индукционному предположению лежит в $\Im B$. Но тогда и $x \in \Im B$ так как от этой суммы он отличается на $B(a_{u}(\sum e_i))$.

Теперь $\dim \Ker B = m - \dim \Im B= m - (n-c)= m-n +c$.
\endproof

\dfn Граф называется эйлеровым, если множество его рёбер можно представить в виде дизъюнктного объединения циклов. Это эквивалентно тому, что степень каждой вершины чётна.
\edfn

\crl Граф $G$ содержит $2^{m-n+c}$ эйлеровых подграфов (считая пустой).
\proof Элемент $x \in \lan E \ran $ лежит в $\Ker B$ (над $\mb Z/2$) тогда и только тогда, когда сумма в каждой вершине равна нулю, то есть когда в соответствующем подграфе степень любой вершины чётна.
\endproof
\ecrl


\section{Определитель}

Есть ли какая-нибудь численная характеристика, которая позволяет сказать, что матрица $A\in M_n(K)$ обратима? Напомню, что обратимость матрицы $A$ равносильна линейной независимости её столбцов. Если посмотреть на картинку над $\mb R$, то видно, что вектора линейно независимы тогда и только тогда, когда объём параллелепипеда на них натянутого отличен от нуля.

\dfn Пусть $V$ -- векторное пространство размерности $n$ над $\mb R$, тогда для набора  $v_1,\dots,v_n \in V$ определим параллелепипед 
$$D(v_1,\dots,v_n)=\{\sum_{i=1}^n \lambda_i v_i\,|\, \text{ где } \lambda_i\in [0,1]\}.$$
\edfn

Обозначим для краткости $\Vol(v_1,\dots,v_n)= \Vol (D(v_1,\dots,v_n))$. Более того, работая с набором векторов из пространство $K^n$ я буду отождетвлять его с матрицей $M_n(K)$. 
Попробуем понять есть ли возможность как-то аксиоматизировать понятие объёма параллелепипеда, так, чтобы оно работало над произвольным полем и для произвольного пространства. А заодно узнаем как его посчитать.

Отображение $\Vol \colon M_n(K) \to K$ типа объёма естественно удовлетворяет следующим свойствам...\\
0) Объём единичного кубика это $\Vol(E)=1$.\\
1) При растяжении одного вектора объём меняется пропорционально $\Vol(\dots,\lambda v,\dots)=|\lambda|\Vol(\dots,v,\dots)$.\\
2) Исходя из принципа Кавальери $\Vol(\dots,v,\dots,u,\dots)=\Vol(\dots,v,\dots,u+\lambda v,\dots)$.\\
3) Если в наборе есть два одинаковых вектора, то $\Vol(\dots,v, \dots, v,\dots)=0$.\\

Для общего пространства $V$ условие типа 0) не имеет смысла, так как нет возможности выбрать какой-то канонический базис в $V$.

Безусловно, модуль числа в свойстве 2) нет возможности определить над произвольным полем. Да и вообще ни о какой положительности, как для объёма, речи нет. Вместо свойства 1) хочется потребовать\\
1') $\omega(\dots,\lambda v,\dots)=\lambda \det(\dots,v,\dots)$.\\

Заметим, что если мы находимся над $\mb R$ и  выполнены свойства 0), 1'), 2), то для отображения $|\omega|$ выполнены свойства 0),1),2). Однако, с алгебраической точки зрения свойство 2) не самое удобное. Вместо него мы рассмотрим свойство\\
2') $\omega(\dots,u+v,\dots)=\omega(\dots,u,\dots)+\omega(\dots,v,\dots)$.


\begin{defn}
Отображение $\omega \colon  V^l\to K $ называется полилинейным, если для любого $1\leq i\leq l$ 
$$\omega(v_1,\dots,v_i+\lambda u_i,\dots, v_l)= \omega(v_1,\dots,v_i,\dots, v_l)+\lambda\omega(v_1,\dots,u_i,\dots, v_l).$$
\end{defn}

\lm Для полилинейного отображения $\omega \colon V^l \to K $ выполнено, что, если $e_1,\dots,e_n$ базис $V$, то 
$$\omega(v_1,\dots,v_l)=\sum \omega(e_{i_1},\dots,e_{i_l}) \prod_{j=1}^l a_{i_j,j}$$
где $a_{i,j}$ -- это $i$-ая координата $v_j$.\\
\elm

\begin{defn}
Полилинейное отображение $\mu \colon V^l\to K $ называется антисимметричным или кососимметрическим, если 
$$\omega(v_1,\dots,v,\dots,v,\dots, v_l)=0.$$ и симметричным, если
$$\omega(v_1,\dots,v_i,\dots,v_j,\dots, v_l)=\omega(v_1,\dots,v_j,\dots,v_i,\dots, v_l)$$
\end{defn}



Теперь надо разобраться с естественностью рассматриваемых понятий и как-то отметить их свойства.
\lm Пусть $V$ пространство размерности $n$. Для кососимметрического полилинейного отображения $\mu \colon V^l \to K $ выполнено, что \\
1) $\omega(\dots,u,\dots,v,\dots)= -\omega(\dots,v,\dots,u,\dots)$.\\
2) Для любой перестановки $\sigma \in S_l$ выполнено, что $\omega(v_{\sigma(1)},\dots,v_{\sigma(l)})= \sgn(\sigma) \omega(v_1,\dots,v_n)$.\\
3)  $\omega(\dots,v,\dots,u,\dots)=\omega(\dots,v,\dots,u+\lambda v,\dots)$.\\
4) В случае, если $\chr K \neq 2$, то из  свойства 1) следует кососимметричность.\\
5) Пусть $l=n$. Для набора векторов $v_1,\dots,v_n$ и базиса $e_1,\dots,e_n$ выполнено, что 
$$\mu(v_1,\dots,v_n)=\omega(e_1,\dots,e_n)\sum_{\sigma \in S_n} \sgn(\sigma)\prod_{j=1}^n a_{\sigma(j),j}=\omega(e_1,\dots,e_n)\sum_{\sigma \in S_n} \sgn(\sigma)\prod_{i=1}^n a_{i,\sigma(i)},$$
где $a_{i,j}$ -- это $i$-ая координата $j$-ого вектора.
\elm







\begin{defn}
Пусть $n=\dim V$. Антисимметричная форма $\omega \colon V^n \to K $ называется формой объёма на $V$. Если такая форма не равна 0, то будем говорить, что она невырождена. 
\end{defn}



До этого момента мы говорили про объекты которых, возможно, просто не существует. Настала пора предъявить для них конструкцию и в  доказать её единственность.

\dfn  Определителем $\det$ называется отображение $\det \colon M_n(K) \to K$, такое, что $$\det(A)=\sum_{\sigma \in S_n} \sgn(\sigma)\prod_{1\leq i\leq n} a_{i\sigma(i)}.$$
\edfn

\dfn Пусть $e_1,\dots,e_n$ базис пространства $V$. Определим отображение $\Vol_e \colon V^n \to K$, такое, что 
$$\Vol_e(v_1,\dots,v_n)=\det(e(v_1),\dots, e(v_n)),$$ 
где $e\colon V \to K^n$ -- отображение сопоставления координат.
\edfn

\begin{thm} Следующие свойства верны:\\
1) Определитель является формой объёма на $K^n$, такой, что $\det E=1$.\\
2) Если $V$ -- пространство размерности $n$, то любая форма объёма на $V$ имеет вид $$\omega=\omega(e_1,\dots,e_n)\Vol_e.$$
В частности, если есть два базиса $e$ и $f$, то $\Vol_{f}=\det(C^f_{e}) \Vol_{e}$.\\
3) Пространство форм объёма одномерно.\\
4) Для любой формы объёма $\omega(v_1,\dots,v_n)=0$ тогда и только тогда, когда $v_1,\dots,v_n$ линейно независимы.
\proof
\endproof
\end{thm}



С вычислительной точки зрения формула для определителя бесполезна -- в ней $n!$ слагаемых. Но она даёт некоторые важные следствия. Например, то, что определитель есть однородный многочлен степени $n$ с целыми коэффициентами от элементов матрицы (следовательно, понятие определителя можно ввести над любым коммутативным кольцом по этой формуле).

Выпишем несколько свойств определителей:

\lm Верны следующие свойства:\\
0) $\det(A)=\det(A^{T})$.\\
1) Определитель не меняется при элементарных преобразованиях первого типа для строк и столбцов. При смене строк местами меняется знак определителя. При домножении строки на $\lambda$, определитель меняется на $\lambda$.\\
2) $\det(AB)=\det(A)\det(B)$.\\
3) $\det \left(\begin{matrix}A & B\\
0 & C \\
\end{matrix}\right)= \det(A)\det(C)$.\\
4) Определитель верхнетреугольной или нижнетреугольной матрицы равен произведению диагональных элементов.\\
5) $\det \colon \GL(V) \to K^*$
является гомоморфизмом групп.
\elm

\dfn Минором порядка $k$ матрицы $A_{m\times n}(K)$ называется определитель некоторой квадратной подматрицы $M_{I,J}=\det A_{I,J}$, где $|I|=|J|=k$. Алгебраическим дополнением элемента $a_{ij}$ называется $A^{i,j}=(-1)^{i+j} M_{\ovl{i},\ovl{j}}$.
\edfn

\lm При разложении по $j$-ому столбцу имеет место формула  $$\det(A)=\sum_{i=1}^n a_{ij} A^{ij}.$$
\elm
Это свойство называется разложением  определителя матрицы по строке или столбцу.

\dfn Пусть $L\colon V \to V$ -- линейный оператор. Тогда определим $\det L=\det A$, где $A$ -- матрица оператора в каком-то базисе.
\edfn

\rm Линейный оператор обратим тогда и только тогда, когда $\det L \neq 0$.
\erm




Понятие определителя выросло из понятия объёма и немного его переросло. А именно, для набора элементов из пространства $\mb R^n$ можно посчитать не только объём, но ещё и некоторый знак. О смысле этого знака и пойдёт сейчас речь. 

\dfn  Будем говорить, что два базиса пространства $V$ над $\mb R$ одинаково ориентированы, если матрица перехода между ними имеет положительный определитель.
\edfn

\rm Отношение одинаковой ориентированности есть отношение эквивалентности.
\erm

\dfn Выбор одного из классов эквивалентности базисов называется заданием ориентации.
\edfn

\dfn Пусть $V$ -- векторное пространство над $\mb R$. Будем говорить, что линейный оператор $L\colon V \to V$ сохраняет ориентацию, если $\det L >0$ и не сохраняет, если $\det L<0$.
\edfn




\end{document}