Алгебраические структуры 5 2015

Лектор: Евгений Евгеньевич Горячко.

Преподаватель практики у подгруппы №1: Евгений Евгеньевич Горячко.

Список подгруппы №1 на практике: Иван Абрамов, Евгений Акимов, Роман Васильев, Марк Геллер, Сергей Голованов,
Андрей Крутиков, Рауф Курбанов, Антон Мордберг, Кирилл Пилюгин, Дмитрий Саввинов, Андрей Серебро, Алексей Степанов,
Ильнур Шугаепов, Наталья Ялышева, а также Иван Дмитриевский и Ирина Щукина.

Преподаватель практики у подгруппы №2: Софья Сергеевна Афанасьева.

Список подгруппы №2 на практике: Дмитрий Байдин, Виталий Бибаев, Фёдор Бочаров, Артём Бутомов, Святослав Власов,
Шамиль Гарифуллин, Егор Горбунов, Эдгар Жаворонков, Никита Иванов, Сергей Козлов, Татьяна Кузина, Михаил Митрофанов,
Семён Поляков, Владислав Саенко, Леонид Сташевский, Константин Чаркин.

Файл с домашним заданием на 11-е ноября.

Таблица успеваемости студентов.

Все основные материалы курса имеются на следующих страницах: http://mit.spbau.ru/courses/algstructures и
http://mit.spbau.ru/courses/algstructures_se (а также http://mit.spbau.ru/courses/algstructures_cs для группы CS).

1.1.1  Пространства матриц, столбцов, строк

• Пространство матриц $\mathrm {Mat} (p,n,K)$. Пространство столбцов: $K^{p}=\mathrm {Mat} (p,1,K)$. Пространство строк: ${}^{n}\!K=\mathrm {Mat} (1,n,K)$.
• Матричные единицы. Стандартный базис пространства $\mathrm {Mat} (p,n,K)$: $\{e_{i}^{j}\mid i\in \{1,\ldots ,p\},\,j\in \{1,\ldots ,n\}\}$.
• Стандартный базис пространства $K^{p}$: $\{e_{i}\mid i\in \{1,\ldots ,p\}\}$. Стандартный базис пространства ${}^{n}\!K$: $\{e^{j}\mid j\in \{1,\ldots ,n\}\}$.
• Умножение матриц: $(b\cdot a)_{k}^{i}=\sum _{j=1}^{p}b_{j}^{i}\,a_{k}^{j}$. Внешняя ассоциативность умножения матриц. Кольцо $\mathrm {Mat} (n,K)$. Группа $\mathrm {GL} (n,K)$.
• Выделение строк матрицы: $a^{i}=e^{i}\cdot a$. Выделение столбцов матрицы: $a_{j}=a\cdot e_{j}$. Утверждение: $(b\cdot a)^{i}=b^{i}\cdot a$ и $(b\cdot a)_{k}=b\cdot a_{k}$.
• След матрицы: $\mathrm {tr} \,a=\sum _{i=1}^{n}a_{i}^{i}$. Утверждение: пусть $a\in \mathrm {Mat} (p,n,K)$ и $b\in \mathrm {Mat} (n,p,K)$; тогда $\mathrm {tr} (b\cdot a)=\mathrm {tr} (a\cdot b)$.
• Транспонирование матрицы: $(a^{\mathtt {T}})_{j}^{i}=a_{i}^{j}$. Утверждение: пусть $a\in \mathrm {Mat} (p,n,K)$ и $b\in \mathrm {Mat} (r,p,K)$; тогда $(b\cdot a)^{\mathtt {T}}=a^{\mathtt {T}}\cdot b^{\mathtt {T}}$.

1.2.2  Ранг линейного оператора

• Ранг линейного оператора: $\mathrm {rk} (a)=\dim \mathrm {Im} \,a$. Ранг матрицы (ранг по столбцам): $\mathrm {rk} (a)=\dim \,\langle a_{1},\ldots ,a_{n}\rangle$. Утверждение: $\mathrm {rk} (a)=\mathrm {rk} (a_{e}^{h})$.
• Утверждение: $\mathrm {rk} (a)\leq \min(\dim V,\dim Y)$. Утверждение: $a\in \mathrm {Inj} (V,Y)\,\Leftrightarrow \,\mathrm {rk} (a)=\dim V$ и $a\in \mathrm {Surj} (V,Y)\,\Leftrightarrow \,\mathrm {rk} (a)=\dim Y$.
• Теорема о свойствах ранга. Пусть $K$ — поле, $n,p\in \mathbb {N} _{0}$ и $a\in \mathrm {Mat} (p,n,K)$; тогда
  (1) для любых матриц $g\in \mathrm {GL} (p,K)$ и $g'\in \mathrm {GL} (n,K)$ выполнено $\mathrm {rk} (g\cdot a\cdot g')=\mathrm {rk} (a)$;
  (2) существуют такие матрицы $g\in \mathrm {GL} (p,K)$ и $g'\in \mathrm {GL} (n,K)$, что $g\cdot a\cdot g'=e_{1}^{1}+e_{2}^{2}+\ldots +e_{\mathrm {rk} (a)}^{\mathrm {rk} (a)}$;
  (3) $\mathrm {rk} (a^{\mathtt {T}})=\dim \,\langle a^{1},\ldots ,a^{p}\rangle$ и $\,\mathrm {rk} (a)=\mathrm {rk} (a^{\mathtt {T}})$ (то есть ранг по столбцам равен рангу по строкам).

1.4.2  Полилинейные отображения и формы объема

• Пространства полилинейных отображений $\mathrm {Multi} (V_{1},\ldots ,V_{k};Y)$ и $\mathrm {Multi} ^{k}(V;Y)$ и полилинейных форм $\mathrm {Multi} (V_{1},\ldots ,V_{k})$ и $\mathrm {Multi} ^{k}V$.
• Пространство симметричных полилинейных форм $\mathrm {SMulti} ^{k}V$. Пространство антисимметричных полилинейных форм $\mathrm {AMulti} ^{k}V$.
• Лемма об антисимметричных формах. Пусть $K$ — поле, $V$ — векторное пространство над полем $K$, $k\in \mathbb {N} _{0}$ и $\omega \in \mathrm {Multi} ^{k}V$; тогда
  следующие условия эквивалентны (если $\mathrm {char} \,K=2$, то исключаются импликации (2)$\;\Rightarrow \,$(1) и (3)$\;\Rightarrow \,$(1)):
  (1) $\omega \in \mathrm {AMulti} ^{k}V$;
  (2) для любых $v_{1},\ldots ,v_{k}\in V$ и таких $u\in \mathrm {S} _{k}$, что $u$ — транспозиция, выполнено $\omega (v_{u(1)},\ldots ,v_{u(k)})=-\omega (v_{1},\ldots ,v_{k})$;
  (3) для любых $v_{1},\ldots ,v_{k}\in V$ и $u\in \mathrm {S} _{k}$ выполнено $\omega (v_{u(1)},\ldots ,v_{u(k)})=\mathrm {sgn} (u)\,\omega (v_{1},\ldots ,v_{k})$.
• Пространство форм объема $\mathrm {AMulti} ^{n}V$ ($n=\dim V$). Форма объема, связанная с базисом: $\mathrm {vol} ^{e}(v_{1},\ldots ,v_{n})=\sum _{u\in \mathrm {S} _{n}}\mathrm {sgn} (u)\,(v_{1}^{e})^{u(1)}\!\ldots (v_{n}^{e})^{u(n)}$.
• Теорема о формах объема. Пусть $K$ — поле, $V$ — векторное пространство над $K$, $\dim V<\infty$; обозначим через $n$ число $\dim V$; тогда
  (1) для любых $e\in \mathrm {OB} (V)$ и $\omega \in \mathrm {AMulti} ^{n}V$ выполнено $\omega =\omega (e_{1},\ldots ,e_{n})\,\mathrm {vol} ^{e}$;
  (2) для любых $e\in \mathrm {OB} (V)$ множество $\{\mathrm {vol} ^{e}\}$ — базис пространства $\,\mathrm {AMulti} ^{n}V$;
  (3) для любых $v_{1},\ldots ,v_{n}\in V$ и $\omega \in \mathrm {AMulti} ^{n}V\setminus \{0\}$ выполнено $(v_{1},\ldots ,v_{n})\in \mathrm {OB} (V)\,\Leftrightarrow \,\omega (v_{1},\ldots ,v_{n})\neq 0$.

1.4.3  Определитель линейного оператора

• Определитель линейного оператора: $\omega (a(v_{1}),\ldots ,a(v_{n}))=\det a\cdot \omega (v_{1},\ldots ,v_{n})$, где $\omega \in \mathrm {AMulti} ^{n}V\setminus \{0\}$. Корректность определения.
• Теорема о главных свойствах определителя. Пусть $K$ — поле, $V$ — векторное пространство над полем $K$ и $\dim V<\infty$; тогда
  (1) $\mathrm {GL} (V)=\{a\in \mathrm {End} (V)\mid \det a\neq 0\}$ (напоминание: $\mathrm {GL} (V)=\mathrm {End} (V)^{\times }$);
  (2) для любых $a,b\in \mathrm {End} (V)$ выполнено $\det(a\circ b)=\det a\cdot \det b$
  (и, значит, отображение ${\biggl (}\!{\begin{aligned}\mathrm {GL} (V)&\to K^{\times }\\a&\mapsto \det a\end{aligned}}\!{\biggr )}$ определено корректно и является гомоморфизмом групп).
• Определитель матрицы: $\det a=\sum _{u\in \mathrm {S} _{n}}\mathrm {sgn} (u)\,a_{1}^{u(1)}\!\ldots a_{n}^{u(n)}$. Утверждение: пусть $e\in \mathrm {OB} (V)$; тогда $\mathrm {vol} ^{e}(v_{1},\ldots ,v_{n})=\det \!{\bigl (}v_{1}^{e}\;\ldots \;v_{n}^{e}{\bigr )}$.
• Лемма об определителе оператора и определителе матрицы. Пусть $K$ — поле, $V$ — векторное пространство над полем $K$, $\dim V<\infty$,
  $a\in \mathrm {End} (V)$ и $e\in \mathrm {OB} (V)$; тогда, обозначая через $n$ число $\dim V$, имеем $\det a=\mathrm {vol} ^{e}(a(e_{1}),\ldots ,a(e_{n}))=\det a_{e}^{e}$.
• Утверждение: $\det a=\det a^{\mathtt {T}}$ и определитель блочно-треугольной матрицы равен произведению определителей диагональных блоков.
• Специальные линейные группы: $\mathrm {SL} (V)=\{a\in \mathrm {GL} (V)\mid \det a=1\}\trianglelefteq \mathrm {GL} (V)$ и $\mathrm {SL} (n,K)=\{a\in \mathrm {GL} (n,K)\mid \det a=1\}\trianglelefteq \mathrm {GL} (n,K)$.

1.5  Линейные операторы (часть 2)

1.5.1  Многочлены от операторов

• Многочлен от оператора: $f(a)=\sum _{k=0}^{\deg f}f_{k}a^{k}$. Эвалюация ${\biggl (}\!{\begin{aligned}\mathrm {eval} _{a}\colon K[x]&\to \mathrm {End} (V)\\f&\mapsto f(a)\end{aligned}}\!{\biggr )}$ — гомоморфизм колец и векторных пространств.
• Кольцо, порожденное оператором: $K[a]=\{f(a)\mid f\in K[x]\}=\mathrm {Im} \,\mathrm {eval} _{a}$ — коммутативное подкольцо и подпространство в $\mathrm {End} (V)$.
• Минимальный многочлен оператора: $\mu _{a}(a)=0$, $\mu _{a}$ приведен, $\deg \mu _{a}=\min\{\deg f\mid f\in K[x]\setminus \{0\}\;\land \;f(a)=0\}$; $(\mu _{a})=\mathrm {Ker} \,\mathrm {eval} _{a}\trianglelefteq K[x]$.
• Утверждение: пусть $a\in \mathrm {End} (V)$ и $f\in K[x]$; тогда $a{\bigl (}\mathrm {Ker} \,f(a){\bigr )}\leq \mathrm {Ker} \,f(a)$ и, если $g\in K[x]$ и $f$ делит $g$, то $\,\mathrm {Ker} \,f(a)\leq \mathrm {Ker} \,g(a)$.
• Теорема о разложении в прямую сумму ядер. Пусть $K$ — поле, $V$ — векторное пространство над полем $K$, $a\in \mathrm {End} (V)$,
  $f,g\in K[x]$ и $\gcd(f,g)=1$; тогда $\,\mathrm {Ker} \,(fg)(a)=\mathrm {Ker} \,f(a)\oplus \mathrm {Ker} \,g(a)$.
• Проектор (идемпотент): $a^{2}=a\,\Leftrightarrow \,V=\mathrm {Ker} \,(\mathrm {id} _{V}-a)\oplus \mathrm {Ker} \,a$. Нильпотентный оператор: $\exists \,m\in \mathbb {N} _{0}\;{\bigl (}a^{m}=0{\bigr )}\,\Leftrightarrow \,\exists \,m\in \mathbb {N} _{0}\;{\bigl (}\mu _{a}=x^{m}{\bigr )}$.

1.5.2  Спектр оператора и характеристический многочлен оператора

• Спектр оператора: $\mathrm {Spec} (a)=\{c\in K\mid (a-c\cdot \mathrm {id} _{V})\notin \mathrm {GL} (V)\}$; если $\dim V<\infty$, то $\mathrm {Spec} (a)=\{c\in K\mid \mathrm {Ker} \,(a-c\cdot \mathrm {id} _{V})\neq \{0\}\}$.
• Характеристический многочлен матрицы: $\chi _{a}=\det(x\cdot \mathrm {id} _{n}-a)$. Характеристический многочлен оператора: $\chi _{a}=\chi _{a_{e}^{e}}$. Корректность определения.
• Утверждение: $\chi _{a}=x^{n}-\mathrm {tr} \,a\cdot x^{n-1}+\ldots +(-1)^{n}\det a$. Утверждение: $\mathrm {Spec} (a)=\{c\in K\mid \chi _{a}(c)=0\}$ (и, значит, $|\mathrm {Spec} (a)|\leq \dim V$).
• Теорема Гамильтона–Кэли. Пусть $K$ — поле, $V$ — векторное пространство над полем $K$, $\dim V<\infty$ и $a\in \mathrm {End} (V)$; тогда $\chi _{a}(a)=0$.
• Две кратности: $\alpha (a,c)$ — кратность $c$ как корня многочлена $\chi _{a}$ (алгебраическая кратность) и $\beta (a,c)$ — кратность $c$ как корня многочлена $\mu _{a}$.
• Лемма о минимальном и характеристическом многочленах. Пусть $K$ — поле, $V$ — вект. пр. над $K$, $\dim V<\infty$, $a\in \mathrm {End} (V)$; тогда
  (1) многочлен $\mu _{a}$ делит многочлен $\chi _{a}$ (и, значит, $\forall \,c\in K\;{\bigl (}\beta (a,c)\leq \alpha (a,c){\bigr )}$);
  (2) $\mathrm {Spec} (a)=\{c\in K\mid \mu _{a}(c)=0\}$;
  (3) если $a$ — нильпотентный оператор, то $\chi _{a}=x^{\dim V}$.

1.5.3  Собственные и корневые подпространства оператора

• Обобщенные собственные подпространства: $V_{j}(a,c)=\mathrm {Ker} \,(a-c\cdot \mathrm {id} _{V})^{j}\leq V$. Корневые подпространства: $V(a,c)=\bigcup _{j=0}^{\infty }V_{j}(a,c)\leq V$.
• Цепь $a$-инвариантных подпространств: $\{0\}<V_{1}(a,c)<\ldots <V_{p-1}(a,c)<V_{p}(a,c)=V_{p+1}(a,c)=\ldots$; вывод: $V(a,c)=V_{p}(a,c)$.
• Обобщенные геометрические кратности: $\gamma _{j}(a,c)=\dim V_{j}(a,c)-\dim V_{j-1}(a,c)$ и $\gamma (a,c)=\gamma _{1}(a,c)$. Утверждение: $\gamma (a,c)\leq \alpha (a,c)$.
• Лемма об обобщенных собственных подпространствах. Пусть $K$ — поле, $V$ — векторное пространство над полем $K$, $\dim V<\infty$,
  $a\in \mathrm {End} (V)$ и $c\in \mathrm {Spec} (a)$; обозначим через $\beta$ число $\beta (a,c)$; тогда
  (1) для любых $j\in \mathbb {N} _{0}$ выполнено $\beta \leq j\,\Leftrightarrow \,V_{\beta }(a,c)=V_{j}(a,c)$;
  (2) $V_{\beta -1}(a,c)<V_{\beta }(a,c)=V_{\beta +1}(a,c)$ и $V(a,c)=V_{\beta }(a,c)=V_{\alpha (a,c)}(a,c)$.
• Теорема о диагонализуемых операторах. Пусть $K$ — поле, $V$ — векторное пространство над полем $K$, $\dim V<\infty$ и $a\in \mathrm {End} (V)$;
  тогда следующие условия эквивалентны:
  (1) существует такой упорядоченный базис $e\in \mathrm {OB} (V)$, что $a_{e}^{e}$ — диагональная матрица;
  (2) $\mu _{a}=\!\!\!\prod _{c\in \mathrm {Spec} (a)}\!\!\!(x-c)$;
  (3) $V=\!\!\!\bigoplus _{c\in \mathrm {Spec} (a)}\!\!\!V_{1}(a,c)$ (это разложение пространства $V$ в прямую сумму собственных подпространств оператора $a$).
• Теорема о разложении в прямую сумму корневых подпространств. Пусть $K$ — поле, $V$ — векторное пространство над полем $K$,
  $\dim V<\infty$, $a\in \mathrm {End} (V)$ и многочлен $\chi _{a}$ раскладывается в произведение многочленов степени $1$ в кольце $K[x]$ (если $K=\mathbb {C}$,
  то это условие выполнено для любого оператора $a$ в силу алгебраической замкнутости поля $\mathbb {C}$); тогда
  (1) $V=\!\!\!\bigoplus _{c\in \mathrm {Spec} (a)}\!\!\!V(a,c)$ (это разложение пространства $V$ в прямую сумму корневых подпространств оператора $a$);
  (2) для любых $c\in \mathrm {Spec} (a)$, обозначая через $\mathrm {nil} (a,c)$ оператор $(a-c\cdot \mathrm {id} _{V})|_{V(a,c)\to V(a,c)}$, имеем следующие факты:
  $\mathrm {nil} (a,c)$ — нильпотентный оператор, $\mu _{\mathrm {nil} (a,c)}=x^{\beta (a,c)}$ и $\chi _{\mathrm {nil} (a,c)}=x^{\alpha (a,c)}$ (и, значит, $\dim V(a,c)=\alpha (a,c)$).

1.6  Линейные операторы (часть 3)

1.6.1  Относительные базисы

• Независимое подмножество в $V$ относительно $U$: $\sum _{c\in C}f(c)\,c\in U\,\Rightarrow \,f=0$. Порождающее подмножество в $V$ относительно $U$: $U+\langle D\rangle =V$.
• Базис в $V$ относительно $U$: одновременно независимое и порождающее подмножество в $V$ относительно $U$. Три леммы без доказательств.

  Лемма 1 об относительных базисах. Пусть $K$ — поле, $V$ — вект. пр. над $K$, $U\leq V$, $E\subseteq V$; тогда следующие условия эквивалентны:
  (1) $E$ — базис в $V$ относительно $U$;
  (2) для любого базиса $A$ в $U$ выполнено $A\cap E=\varnothing$ и $A\cup E$ — базис в $V$;
  (3) существует такой базис $A$ в $U$, что $A\cap E=\varnothing$ и $A\cup E$ — базис в $V$.
  Лемма 2 об относительных базисах. Пусть $K$ — поле, $V$ — вект. пр. над $K$, $U\leq V$, $C$ — независимое подмножество в $V$ относительно $U$;
  тогда существует базис в $V$ относительно $U$, содержащий $C$.
  Лемма 3 об относительных базисах. Пусть $K$ — поле, $V$ — вект. пр. над $K$, $T\leq U\leq V$, $E$ — базис в $V$ относительно $U$, $F$ — базис в $U$
  относительно $T$; тогда $E\cup F$ — базис в $V$ относительно $T$.

• Теорема об относительно независимых подмножествах. Пусть $K$ — поле, $V$ — векторное пространство над полем $K$, $a\in \mathrm {End} (V)$,
  $j\in \mathbb {N} \setminus \{1\}$; обозначим через $V_{j-2}$, $V_{j-1}$ и $V_{j}$ пространства $\,\mathrm {Ker} \,a^{j-2}$, $\mathrm {Ker} \,a^{j-1}$ и $\,\mathrm {Ker} \,a^{j}$ соответственно; пусть $C$ — независимое
  подмножество в $V_{j}$ относительно $V_{j-1}$; тогда $a|_{C\to a(C)}$ — биекция и $a(C)$ — независимое подмножество в $V_{j-1}$ относительно $V_{j-2}$.

1.6.2  Жорданова нормальная форма оператора

• Жордановы клетки: $\mathrm {J} _{n}(0)=e_{1}^{2}+e_{2}^{3}+\ldots +e_{n-1}^{n}$ и $\mathrm {J} _{n}(c)=c\cdot \mathrm {id} _{n}+\mathrm {J} _{n}(0)$. Прямая сумма матриц: $a\oplus b\oplus \ldots =\!{\Biggl (}{\begin{smallmatrix}a&0&0\\0&b&0\\0&0&\ddots \end{smallmatrix}}{\Biggr )}$.
• Диаграммы Юнга. Жорданов блок: $\mathrm {J} _{\Delta }(c)=\mathrm {J} _{n_{1}}(c)\oplus \ldots \oplus \mathrm {J} _{n_{r}}(c)$, где числа $n_{1},\ldots ,n_{r}$ суть длины строк диаграммы Юнга $\Delta$.
• Диаграмма Юнга $\Delta (a,c)$: высоты столбцов диаграммы $\Delta (a,c)$ суть обобщенные геометрические кратности $\gamma _{1}(a,c),\ldots ,\gamma _{\beta (a,c)}(a,c)$.
• Теорема о жордановой нормальной форме нильпотентного оператора. Пусть $K$ — поле, $V$ — векторное пространство над $K$, $\dim V<\infty$,
  $a\in \mathrm {End} (V)$, $a$ — нильпотентный оператор; тогда существует такой упорядоченный базис $e\in \mathrm {OB} (V)$, что $a_{e}^{e}=\mathrm {J} _{\Delta (a,0)}(0)$.
• Теорема о жордановой нормальной форме. Пусть $K$ — поле, $V$ — векторное пространство над полем $K$, $\dim V<\infty$, $a\in \mathrm {End} (V)$
  и многочлен $\chi _{a}$ раскладывается в произведение многочленов степени $1$ в кольце $K[x]$ (если $K=\mathbb {C}$, то это условие выполнено для
  любого оператора $a$ в силу алгебраической замкнутости поля $\mathbb {C}$); тогда существует такой упорядоченный базис $e\in \mathrm {OB} (V)$, что
  $a_{e}^{e}=\!\!\!\bigoplus _{c\in \mathrm {Spec} (a)}\!\!\!\mathrm {J} _{\Delta (a,c)}(c)$ (то есть матрица $a_{e}^{e}$ раскладывается в прямую сумму жордановых блоков).
• Экспонента оператора: $\mathrm {e} ^{a}=\sum _{k=0}^{\infty }{\frac {1}{k!}}\,a^{k}$. Вычисление степеней и экспоненты оператора при помощи теоремы о жордановой нормальной форме.