Алгебра phys 1 ноябрь–декабрь

1  Основы алгебры

1.4  Кольца (часть 2)

1.4.1  Делимость в коммутативных кольцах

• Делимость, строгая делимость, ассоциированность в коммутат. кольце $R$: $s\,|\,r\;\Leftrightarrow \;\exists \,t\in R\;{\bigl (}r=s\,t{\bigr )}$; $s\,|\!\!|\!\!|\,r\;\Leftrightarrow \;s\,|\,r\,\land \,\lnot (r\,|\,s)$; $r\overset{\scriptscriptstyle\mid}\sim s\;\Leftrightarrow\;r\,|\,s\,\land\,s\,|\,r$.
• Утверждение: пусть $R$ — обл. цел.-сти, $a,b,r,s\in R$ и $r\neq 0$; тогда $a\,r=b\,r\,\Leftrightarrow\,a=b$, а также $r\overset{\scriptscriptstyle\mid}\sim s\,\Leftrightarrow\,\exists\,t\in R^\times\bigl(r=s\,t\bigr)$. Отн.-е ${\overset {\scriptscriptstyle \mid }{\sim }}$ в $\mathbb {Z}$ и $K[x]$.
• Наибольший относ.-но $|$ общий делитель $r$ и $s$: $\mathrm{gcd}(r,s)$; наименьшее относ.-но $|$ общее кратное $r$ и $s$: $\mathrm{lcm}(r,s)$; $\mathrm {gcd}$ и $\mathrm {lcm}$ опред.-ны с точностью до ${\overset {\scriptscriptstyle \mid }{\sim }}$.
• Нормировка $\mathrm {gcd}$ и $\mathrm {lcm}$ (если они не $0$) в $\mathbb {Z}$ и $K[x]$: $\mathrm{gcd}(a,b)\in\mathbb N$ и $\mathrm{lcm}(a,b)\in\mathbb N$ — в $\mathbb {Z}$, многочлены $\mathrm {gcd} (f,g)$ и $\mathrm {lcm} (f,g)$ нормированы — в $K[x]$.
• Главный идеал — идеал вида $(r)$. Пример неглавн. идеала: $(2)+(x)$ в $\mathbb {Z} [x]$. Область главных идеалов — обл. цел.-сти, в которой все идеалы главные.
• Теорема о делимости и главных идеалах. Пусть $R$ — коммутативное кольцо и $r,s\in R$; тогда
  (1) $s\,|\,r\,\Leftrightarrow \,(r)\subseteq (s)$; $s\,|\!\!|\!\!|\,r\,\Leftrightarrow \,(r)\subset (s)$; $r\overset{\scriptscriptstyle\mid}\sim s\,\Leftrightarrow\,(r)=(s)$; $r\in R^\times\Leftrightarrow\,r\overset{\scriptscriptstyle\mid}\sim1\,\Leftrightarrow\,(r)=R$;
  (2) если идеал $(r)+(s)$ главный, то $(r)+(s)=(\mathrm{gcd}(r,s))$, и, если идеал $(r)\cap(s)$ главный, то $(r)\cap(s)=(\mathrm{lcm}(r,s))$;
  (3) если в кольце $R$ все идеалы главные, то $\mathrm{gcd}(r,s)$ и $\mathrm{lcm}(r,s)$ существуют, а также $(R/(r))^\times\!=\{s+(r)\in R/(r)\mid\mathrm{gcd}(r,s)\overset{\scriptscriptstyle\mid}\sim1\}$.
• Неприводимые и простые эл.-ты: $\mathrm {Irr} (R)=(R\!\setminus \!R^{\times }\!)\setminus \{s\,t\mid s,t\in R\!\setminus \!R^{\times }\!\}$ и $\mathrm {Prime} (R)=\{r\in R\!\setminus \!(R^{\times }\!\cup \{0\})\mid \forall \,s,t\in R\;{\bigl (}r\,|\,s\,t\,\Rightarrow \,r\,|\,s\,\lor \,r\,|\,t{\bigr )}\}$.
• Теорема о неприводимых и простых элементах. Пусть $R$ — коммутативное кольцо; тогда
  (1) если $R$ — область целостности, то $\,\mathrm {Prime} (R)\subseteq \mathrm {Irr} (R)$;
  (2) если $R$ — область главных идеалов, то $\,\mathrm {Irr} (R)=\mathrm {Prime} (R)$;
  (3) для любых $r\in R\!\setminus \!\{0\}$ следующие утверждения эквивалентны: (у1) $r\in \mathrm {Prime} (R)$ и (у2) $R/(r)$ — область целостности;
  (4) если $R$ — область главных идеалов, то для любых $r\in R\!\setminus \!\{0\}$ следующие утверждения эквивалентны: (у1) $r\in \mathrm {Irr} (R)$, (у2) $r\in \mathrm {Prime} (R)$,
  (у3) $R/(r)$ — область целостности и (у4) $R/(r)$ — поле.

1.4.2  Евклидовы кольца и факториальные кольца

• Евклидова норма — такая функция $\nu\,\colon R\to\mathbb N_0\cup\{-\infty\}$, что относ.-но $\nu$ можно делить с остатком на ненул. эл.-ты и $\nu$ не убывает относ.-но $|$ на $R\!\setminus\!\{0\}$.
• Евклидово кольцо — область целостности с евклидовой нормой. Примеры: $\mathbb {Z}$ ($\nu (a)=|a|$); $K[x]$ ($\nu (f)=\deg f$); $\mathbb {Z} [\mathrm {i} ]$, $\mathbb {Z} [{\sqrt {2}}\,\mathrm {i} ]$, $\mathbb {Z} [\mathrm {e} ^{{\frac {2\pi }{3}}\mathrm {i} }]$ ($\nu (a)=|a|^{2}$).
• Теорема о евклидовых кольцах. Пусть $R$ — евклидово кольцо с евклидовой нормой $\nu$; тогда
  (1) для любых $r\in R\!\setminus \!\{0\}$ и $s\in R$ выполнено $s\,|\!\!|\!\!|\,r\,\Rightarrow \,\nu (s)<\nu (r)$;
  (2) в $R$ невозможна бесконечная строгая делимость (то есть в $R$ не существует такой бесконечной послед.-сти $r_{1},r_{2},\ldots$, что $\forall\,i\in\mathbb N\;\bigl(r_{i+1}\,|\!\!|\!\!|\,r_i\bigr)$);
  (3) если $I\trianglelefteq R$, то для любых $r\in I\!\setminus \!\{0\}$ выполнено $I=(r)\,\Leftrightarrow \,\nu (r)=\min\{\nu (s)\mid s\in I\!\setminus \!\{0\}\}$;
  (4) $R$ — область главных идеалов (в частности, кольца $\,\mathbb {Z}$ и $K[x]$, где $K$ — поле, являются областями главных идеалов).
• Факториальное кольцо — обл. цел.-сти с единств. (с точностью до ${\overset {\scriptscriptstyle \mid }{\sim }}$ и перестановок) разложением любого эл.-та ($\neq 0$) в произв.-е неприводимых эл.-тов.
• Примеры: $\mathbb {Z}$ — факториальное кольцо (это основная теорема арифметики); если кольцо $R$ факториально, то и $R[x]$ факториально (без доказательства).
• Теорема о факториальности евклидовых колец.
  (1) Пусть $R$ — область целостности, в $R$ невозможна бесконечная строгая делимость и $\,\mathrm {Irr} (R)=\mathrm {Prime} (R)$; тогда $R$ — факториальное кольцо.
  (2) Евклидовы кольца являются факториальными кольцами (в частности, кольца $\,\mathbb {Z}$ и $K[x]$, где $K$ — поле, являются факториальными кольцами).
• Теорема о факториальных кольцах. Пусть $R$ — факториальное кольцо и $r,s\in R\!\setminus \!\{0\}$; разложим $r$ и $s$ в произведение неприводимых элементов:
  $r\overset{\scriptscriptstyle\mid}\sim p_1^{d_1}\!\cdot\ldots\cdot p_k^{d_k}$ и $s\overset{\scriptscriptstyle\mid}\sim p_1^{e_1}\!\cdot\ldots\cdot p_k^{e_k}$, где $k\in \mathbb {N} _{0}$, $p_{1},\ldots ,p_{k}\in \mathrm {Irr} (R)$, $p_{1},\ldots ,p_{k}$ попарно неассоциированы и $d_{1},\ldots ,d_{k},e_{1},\ldots ,e_{k}\in \mathbb {N} _{0}$; тогда
  (1) $s\,|\,r\;\Leftrightarrow \;\forall \,i\in \{1,\ldots ,k\}\;{\bigl (}e_{i}\leq d_{i}{\bigr )}$ и $r\overset{\scriptscriptstyle\mid}\sim s\;\Leftrightarrow\;\forall\,i\in\{1,\ldots,k\}\;\bigl(d_i=e_i\bigr)$;
  (2) $\mathrm{gcd}(r,s)\overset{\scriptscriptstyle\mid}\sim p_1^{\min(d_1,e_1)}\!\cdot\ldots\cdot p_k^{\min(d_k,e_k)}$ и $\,\mathrm{lcm}(r,s)\overset{\scriptscriptstyle\mid}\sim p_1^{\max(d_1,e_1)}\!\cdot\ldots\cdot p_k^{\max(d_k,e_k)}$.

1.4.3  Алгоритм Евклида, китайская теорема об остатках, функция Эйлера

• Соотношение Безу для эл.-тов $r$ и $s$ евклидова кольца: $u\,r+v\,s\overset{\scriptscriptstyle\mid}\sim\mathrm{gcd}(r,s)$, где $u$ и $v$ — коэффициенты Безу. Нахождение $(s+(r))^{-1}$ в кольце $R/(r)$.
• Алгоритм Евклида в евклидовом кольце: $r_{0}=s$ и $r_{1}=r$; на $i$-м шаге $r_{i-1}=q_{i}r_{i}+r_{i+1}$ и $\nu (r_{i+1})<\nu (r_{i})$; тогда, если $r_{n+1}=0$, то $r_n\overset{\scriptscriptstyle\mid}\sim\mathrm{gcd}(r,s)$.
• Расширенный алгоритм Евклида в евклидовом кольце: $r_n=-q_{n-1}r_{n-1}+r_{n-2}$; на $i$-м шаге $r_n=u_ir_i+v_ir_{i-1}$; тогда $r_n=u_1r+v_1s\overset{\scriptscriptstyle\mid}\sim\mathrm{gcd}(r,s)$.
• Китайская теорема об остатках для целых чисел. Пусть $k\in \mathbb {N} _{0}$, $n_{1},\ldots ,n_{k}\in \mathbb {N}$ и $n_{1},\ldots ,n_{k}$ попарно взаимно просты (то есть $\forall\,i,j\in\{1,\ldots,k\}$
  $\bigl(i\ne j\,\Rightarrow\,\mathrm{gcd}(n_i,n_j)=1\bigr)$); тогда отображение $\biggl(\!\begin{align}\mathbb Z/(n_1\cdot\ldots\cdot n_k)&\to\mathbb Z/n_1\times\ldots\times\mathbb Z/n_k\\a&\mapsto(a\;\mathrm{mod}\;n_1,\ldots,a\;\mathrm{mod}\;n_k)\end{align}\!\biggr)$ — изоморфизм колец.
• Китайская теорема об остатках для многочленов. Пусть $K$ — поле, $k\in \mathbb {N} _{0}$, $f_{1},\ldots ,f_{k}\in K[x]\!\setminus \!\{0\}$ и $f_{1},\ldots ,f_{k}$ попарно взаимно просты (то есть
  $\forall \,i,j\in \{1,\ldots ,k\}\;{\bigl (}i\neq j\,\Rightarrow \,\mathrm {gcd} (f_{i},f_{j})=1{\bigr )}$); тогда отображение $\biggl(\!\begin{align}K[x]/(f_1\cdot\ldots\cdot f_k)&\to K[x]/f_1\times\ldots\times K[x]/f_k\\a&\mapsto(a\;\mathrm{mod}\,f_1,\ldots,a\;\mathrm{mod}\,f_k)\end{align}\!\biggr)$ — изоморфизм колец.
• Функция Эйлера от $n$: $\phi (n)=|\{a\in \mathbb {Z} /n\mid \mathrm {gcd} (a,n)=1\}|$. Пример: если $p\in \mathbb {P}$ и $d\in \mathbb {N}$, то $\phi (p^{d})=p^{d-1}(p-1)$. Утверждение: $\phi(n)=|(\mathbb Z/n)^\times\!|$.
• Теорема о свойствах функции Эйлера.
  (1) Пусть $n\in \mathbb {N}$, $a\in \mathbb {Z}$ и $\mathrm {gcd} (a,n)=1$; тогда $a^{\phi (n)}\!\equiv 1\;(\mathrm {mod} \;n)$ (это теорема Эйлера).
  (2) Пусть $m,n\in \mathbb {N}$ и $\mathrm {gcd} (m,n)=1$; тогда $\phi (mn)=\phi (m)\,\phi (n)$.
  (3) Пусть $n\in \mathbb {N}$; разложим $n$ в произведение простых чисел: $n=p_{1}^{d_{1}}\!\cdot \ldots \cdot p_{k}^{d_{k}}$, где $k\in \mathbb {N} _{0}$, $p_{1},\ldots ,p_{k}\in \mathbb {P}$, $p_{1},\ldots ,p_{k}$ попарно различны и
  $d_{1},\ldots ,d_{k}\in \mathbb {N}$; тогда $\phi (n)=p_{1}^{d_{1}-1}(p_{1}-1)\cdot \ldots \cdot p_{k}^{d_{k}-1}(p_{k}-1)=n\,{\Bigl (}1-{\frac {1}{p_{1}}}{\Bigr )}\cdot \ldots \cdot {\Bigl (}1-{\frac {1}{p_{k}}}{\Bigr )}$.

1.4.4  Производная многочлена, интерполяция, рациональные дроби

• Производная многочлена: $(f_nx^n+\ldots+f_0)'\!=nf_nx^{n-1}+\ldots+f_1$. Правило Лейбница. Пусть $R$ — кольцо и $f,g\in R[x]$; тогда $(fg)'\!=f'g+f\,g'$.
• Корень $r$ кратности $k$ многочлена $f$: $(x-r)^k\,|\,f\,\land\,\lnot\bigl((x-r)^{k+1}\,|\,f\bigr)$ ($\Leftrightarrow\;\exists\,g\in R[x]\;\bigl(f=(x-r)^kg\,\land\,g(r)\ne0\bigr)$). Теорема о кратных корнях.

  Теорема о кратных корнях. Пусть $R$ — коммутативное кольцо, $f\in R[x]$, $r\in R$ и $k\in \mathbb {N}$; тогда
  (1) если $r$ — корень кратности не меньше $k$ многочлена $f$, то $r$ — корень кратности не меньше $k-1$ многочлена $f'$;
  (2) если $R$ — область целостности, $\mathrm {char} \,R$ не делит $k$ и $r$ — корень кратности $k$ многочлена $f$, то $r$ — корень кратности $k-1$ многочлена $f'$;
  (3) $r$ — кратный корень многочлена $f$ (то есть корень кратности не меньше $2$), если и только если $r$ — корень многочленов $f$ и $f'$.

• Теорема об интерполяции. Пусть $K$ — поле, $n\in \mathbb {N} _{0}$, $c_{1},\ldots ,c_{n},e_{1},\ldots ,e_{n}\in K$ и $c_{1},\ldots ,c_{n}$ попарно различны; тогда существует единственный
  такой многочлен $f\in K[x]$, что $\forall\,i\in\{1,\ldots,n\}\;\bigl(f(c_i)=e_i\bigr)$ и $\deg f<n$, и этот многочлен можно найти по следующим формулам:
  (1) $f=\sum _{i=1}^{n}e_{i}l_{i}$, где $\forall \,i\in \{1,\ldots ,n\}\;{\biggl (}l_{i}={\frac {(x-c_{1})\cdot \ldots \cdot (x-c_{i-1})\cdot (x-c_{i+1})\cdot \ldots \cdot (x-c_{n})}{(c_{i}-c_{1})\cdot \ldots \cdot (c_{i}-c_{i-1})\cdot (c_{i}-c_{i+1})\cdot \ldots \cdot (c_{i}-c_{n})}}{\biggr )}$ (это интерполяционная формула Лагранжа);
  (2) $f=f_{n}$, где $f_{0}=0$ и $\forall \,i\in \{1,\ldots ,n\}\;{\biggl (}f_{i}=f_{i-1}+{\bigl (}e_{i}-f_{i-1}(c_{i}){\bigr )}{\frac {(x-c_{1})\cdot \ldots \cdot (x-c_{i-1})}{(c_{i}-c_{1})\cdot \ldots \cdot (c_{i}-c_{i-1})}}{\biggr )}$ (это интерполяционная формула Ньютона).
• Поле частных: $\mathrm {Q} (R)={\bigl (}R\times (R\!\setminus \!\{0\}){\bigr )}/{\sim }$, где $(r,s)\sim ({\breve {r}},{\breve {s}})\,\Leftrightarrow \,r{\breve {s}}={\breve {r}}s$ и $[(r,s)]_\sim\!+[(t,u)]_\sim\!=[(ru+st,su)]_\sim$, $[(r,s)]_\sim[(t,u)]_\sim\!=[(rt,su)]_\sim$.
• Теорема о поле частных. Отождествл.-е $r$ и $[(r,1)]_\sim$. Примеры: $\mathrm {Q} (\mathbb {Z} )\cong \mathbb {Q}$, $K(x)=\mathrm {Q} (K[x])={\Bigl \{}{\frac {f}{g}}\!\mid f,g\in K[x],\,g\neq 0{\Bigr \}}$ — поле рацион.-х дробей.

  Теорема о поле частных. Пусть $R$ — область целостности; тогда отображение $\biggl(\!\begin{align}R&\to\mathrm Q(R)\\r&\mapsto[(r,1)]_\sim\end{align}\!\biggr)$ — инъективный гомоморфизм колец, а также
  для любых $r\in R$ и $s\in R\!\setminus \!\{0\}$ выполнено $[(r,s)]_\sim\!=\frac{[(r,1)]_\sim}{[(s,1)]_\sim}$ (и, значит, $\mathrm Q(R)=\Bigl\{\frac{[(r,1)]_\sim}{[(s,1)]_\sim}\!\mid r,s\in R,\,s\ne0\Bigr\}$).

• Несократимая запись: ${\frac {f}{g}}$ ($\mathrm {gcd} (f,g)=1$, $g$ нормир.). Приведение к несократ. записи. Правильная дробь: ${\frac {f}{g}}$ ($\deg f<\deg g$). Выделение правил. дроби.
• Примарная дробь: ${\frac {f}{h^{d}}}$ ($h\in \mathrm {Irr} (K[x])$, $h$ нормир., $d\in \mathbb {N}$, $\deg f<\deg h^{d}$). Простейшая дробь: ${\frac {f}{h^{d}}}$ ($h\in \mathrm {Irr} (K[x])$, $h$ нормир., $d\in \mathbb {N}$, $\deg f<\deg h$).
• Метод неопределенных коэффиц.-тов для разложения правильной дроби в сумму простейших дробей (док.-во корректности см. в п. 3 в § 4 главы 5 в [3]).

1.4.5  Матрицы, столбцы, строки

• Множества матриц, столбцов и строк: $\mathrm {Mat} (p,n,R)$, $R^{n}\!=\mathrm {Mat} (n,1,R)$ и $R_{n}\!=\mathrm {Mat} (1,n,R)$. Сложение матриц и умножение матриц на скаляры.
• Умножение матриц: $(b\cdot a)_{k}^{i}=\sum _{j=1}^{p}b_{j}^{i}\,a_{k}^{j}$. Внешняя ассоциативность умножения. Кольцо $\mathrm {Mat} (n,R)=\mathrm {Mat} (n,n,R)$, группа $\mathrm {GL} (n,R)=\mathrm {Mat} (n,R)^{\times }$.
• Матрицы специального вида: диагональные, скалярные, верхнетреугольные, нижнетреугольные, треугольные. Блочные и блочно-треугольные матрицы.
• Матрицы, столбцы, строки с одной единицей: $({\underline {e}}_{i}^{j})_{l}^{k}=\delta _{i}^{k}\delta _{l}^{j}$, $({\underline {e}}_{i})^{k}=\delta _{i}^{k}$, $({\underline {e}}^{j})_{l}=\delta _{l}^{j}$. Утверждение: ${\underline {e}}_{i}^{j}\cdot {\underline {e}}_{k}^{l}=\delta _{k}^{j}{\underline {e}}_{i}^{l}$, ${\underline {e}}_{i}\cdot {\underline {e}}^{j}={\underline {e}}_{i}^{j}$, ${\underline {e}}^{j}\cdot {\underline {e}}_{i}=\delta _{i}^{j}$.
• Строки матрицы $a$: $a_{\bullet }^{i}={\underline {e}}^{i}\cdot a$. Столбцы матрицы $a$: $a_{j}^{\bullet }=a\cdot {\underline {e}}_{j}$. Утверждение: $(b\cdot a)_{\bullet }^{i}=b_{\bullet }^{i}\cdot a=\sum _{j=1}^{p}b_{j}^{i}\,a_{\bullet }^{j}$, а также $(b\cdot a)_{k}^{\bullet }=b\cdot a_{k}^{\bullet }=\sum _{j=1}^{p}b_{j}^{\bullet }\,a_{k}^{j}$.
• Транспонирование матрицы $a$: $(a^{\mathtt {T}})_{j}^{i}=a_{i}^{j}$. След квадратной матрицы $a$: $\mathrm {tr} \,a=\sum _{i=1}^{n}a_{i}^{i}$. Теорема о транспонировании, следе и произведении матриц.

  Теорема о транспонировании, следе и произведении матриц. Пусть $R$ — коммутативное кольцо, $n,p,r\in \mathbb {N} _{0}$, $a\in \mathrm {Mat} (p,n,R)$ и $b\in \mathrm {Mat} (r,p,R)$;
  тогда $(b\cdot a)^{\mathtt {T}}\!=a^{\mathtt {T}}\!\cdot b^{\mathtt {T}}$, а также, если $n=r$, то $\mathrm {tr} (b\cdot a)=\mathrm {tr} (a\cdot b)$.

• Симметрич. и антисимм. матрицы: $\mathrm{SMat}(n,R)=\{a\in\mathrm{Mat}(n,R)\mid a^\mathtt T\!=a\}$ и $\mathrm{AMat}(n,R)=\{a\in\mathrm{Mat}(n,R)\mid a^\mathtt T\!=-a\,\land\,a^1_1=\ldots=a^n_n=0\}$.
• Операторы умн.-я на матрицу между $R^n$ и $R^p$: $\{\bigl(v\mapsto a\cdot v\bigr)\!\mid a\in\mathrm{Mat}(p,n,R)\}$ — группа по сложению. Теорема об операторах умножения на матрицу.

  Теорема об операторах умножения на матрицу. Пусть $R$ — кольцо и $n,p\in \mathbb {N} _{0}$; тогда
  (1) $\biggl(\!\begin{align}\mathrm{Mat}(p,n,R)&\to\{\bigl(v\mapsto a\cdot v\bigr)\!\mid a\in\mathrm{Mat}(p,n,R)\}\\a&\mapsto\bigl(v\mapsto a\cdot v\bigr)\end{align}\!\biggr)$ — изоморфизм групп по сложению и, если $n=p$, то это отобр.-е — изоморфизм колец;
  (2) если $R$ — комм. к.-цо, то $\{\bigl(v\mapsto a\cdot v\bigr)\!\mid a\in\mathrm{Mat}(p,n,R)\}=\{a\in\mathrm{Map}(R^n,R^p)\mid\forall\,v,v'\in R^n,\,c,c'\in R\;\bigl(a(c\,v+c'v')=c\,a(v)+c'a(v')\bigr)\}$.

1.5  Группы (часть 2)

1.5.1  Симметрические группы

• Транспозиции: $(i\;\,j)$ ($i,j\in \{1,\ldots ,n\}$, $i<j$). Фундаментальные транспозиции: $(i\;\,i+1)$ ($i\in \{1,\ldots ,n-1\}$). Число циклов в перестановке $u$: $\kappa (u)$.
• Множество инверсий последовательности $(f_1,\ldots,f_n)$: $\mathrm {inv} (f_{1},\ldots ,f_{n})=\{(i,j)\in \{1,\ldots ,n\}^{2}\!\mid i<j\;\land \,f_{i}>f_{j}\}$. Лемма о количестве инверсий.

  Лемма о количестве инверсий. Пусть $n\in \mathbb {N} \!\setminus \!\{1\}$, $f_{1},\ldots ,f_{n}\in \mathbb {R}$, $l=|\mathrm {inv} (f_{1},\ldots ,f_{n})|$ и $i\in \{1,\ldots ,n-1\}$; тогда
  (1) $(f_{1},\ldots ,f_{n})\circ (i\;\,i+1)=(f_{1},\ldots ,f_{i-1},f_{i+1},f_{i},f_{i+2},\ldots ,f_{n})$;
  (2) если $f_{i}>f_{i+1}$, то $|\mathrm {inv} ((f_{1},\ldots ,f_{n})\circ (i\;\,i+1))|=l-1$, и, если $f_{i}<f_{i+1}$, то $|\mathrm {inv} ((f_{1},\ldots ,f_{n})\circ (i\;\,i+1))|=l+1$.

• Теорема о сортировке пузырьком. Пусть $n\in \mathbb {N} _{0}$, $f_{1},\ldots ,f_{n}\in \mathbb {R}$ и $l=|\mathrm {inv} (f_{1},\ldots ,f_{n})|$; обозначим через ${\hat {f_{1}}},\ldots ,{\hat {f_{n}}}$ числа $f_{1},\ldots ,f_{n}$,
  упорядоченные по неубыванию (то есть $\mathrm {inv} ({\hat {f_{1}}},\ldots ,{\hat {f_{n}}})=\varnothing$); тогда
  (1) существуют такие фундаментальные транспозиции $u_{1},\ldots ,u_{l}\in \mathrm {S} _{n}$, что $(f_{1},\ldots ,f_{n})\circ u_{1}\circ \ldots \circ u_{l}=({\hat {f_{1}}},\ldots ,{\hat {f_{n}}})$;
  (2) для любых $l'\!\in \mathbb {N} _{0}$ из существования таких фундаментальных транспозиций $u_{1},\ldots ,u_{l'}\!\in \mathrm {S} _{n}$, что $(f_{1},\ldots ,f_{n})\circ u_{1}\circ \ldots \circ u_{l'}=({\hat {f_{1}}},\ldots ,{\hat {f_{n}}})$,
  следует, что $l\leq l'$, а также в том случае, когда числа $f_{1},\ldots ,f_{n}$ попарно различны, что $l\equiv l'\;(\mathrm {mod} \;2)$.
• Знак последовательности $(f_1,\ldots,f_n)$: $\mathrm {sgn} (f_{1},\ldots ,f_{n})=(-1)^{|\mathrm {inv} (f_{1},\ldots ,f_{n})|}$, если числа $f_{1},\ldots ,f_{n}$ попарно различны; иначе $\mathrm {sgn} (f_{1},\ldots ,f_{n})=0$.
• Знак перестановки $u$: $\mathrm {sgn} (u)=\mathrm {sgn} (u(1),\ldots ,u(n))$. Теорема о свойствах знака. Знакопеременная группа: $\mathrm {A} _{n}=\{u\in \mathrm {S} _{n}\!\mid \mathrm {sgn} (u)=1\}\trianglelefteq \mathrm {S} _{n}$.

  Теорема о свойствах знака. Пусть $n\in \mathbb {N} _{0}$; тогда
  (1) отображение ${\biggl (}\!{\begin{aligned}\mathrm {S} _{n}\!&\to \{1,-1\}\\u&\mapsto \mathrm {sgn} (u)\end{aligned}}\!{\biggr )}$ — гомоморфизм групп и, если $n\geq 2$, то это отображение — сюръекция и $|\{u\in\mathrm S_n\!\mid\mathrm{sgn}(u)=1\}|=\frac{n!}2$;
  (2) для любых таких $i,j\in \{1,\ldots ,n\}$, что $i<j$, выполнено $|\mathrm {inv} ((i\;\,j))|=2(j-i)-1$ и $\mathrm {sgn} ((i\;\,j))=-1$;
  (3) для любых $m\in \{1,\ldots ,n\}$ и попарно различных чисел $i_{1},\ldots ,i_{m}\in \{1,\ldots ,n\}$ выполнено $\mathrm {sgn} ((i_{1}\;\ldots \;i_{m}))=(-1)^{m-1}$;
  (4) для любых $u\in \mathrm {S} _{n}$ выполнено $\mathrm {sgn} (u)=(-1)^{n-\kappa (u)}$.

• Теорема о классах сопряженности в симметрических группах. Пусть $n\in \mathbb {N} _{0}$ и $s,{\breve {s}}\in \mathrm {S} _{n}$; тогда перестановки $s$ и ${\breve {s}}$ сопряжены, если и только если
  (неупорядоченные) наборы длин циклов перестановок $s$ и ${\breve {s}}$ (то есть цикловые типы перестановок $s$ и ${\breve {s}}$) равны.
• Задание группы $\mathrm S_n$ коксетеровскими образующими и соотношениями (без доказат.-ва). Примеры: $\mathrm S_3\cong\langle d_1,d_2\!\mid d_1^2,d_2^2,(d_1d_2)^3\rangle$, задание группы $\mathrm S_4$.

1.5.2  Группы матриц

• Определитель квадр. матрицы $a$ над коммут. кольцом: $\det a=\sum_{u\in\mathrm S_n}\mathrm{sgn}(u)\,a^{u(1)}_1\!\cdot\ldots\cdot a^{u(n)}_n\!$. Определитель и расстановки ладей на шахматной доске.
• Примеры: $\det \!{\Bigl (}{\begin{smallmatrix}\alpha &\beta \\\gamma &\delta \end{smallmatrix}}{\Bigr )}\!=\alpha \delta -\beta \gamma$, $\det \!{\biggl (}{\begin{smallmatrix}\alpha &\beta &\gamma \\\delta &\varepsilon &\zeta \\\eta &\theta &\iota \end{smallmatrix}}{\biggr )}\!=\alpha \varepsilon \iota +\beta \zeta \eta +\gamma \delta \theta -\gamma \varepsilon \eta -\beta \delta \iota -\alpha \zeta \theta$. Определитель и объем. Теорема о свойствах определителя.

  Теорема о свойствах определителя. Пусть $R$ — коммутативное кольцо и $n\in \mathbb {N} _{0}$; тогда
  (1) для любых $i\in \{1,\ldots ,n\}$, $v_{1},\ldots ,v_{i-1},v,v',v_{i+1},\ldots ,v_{n}\in R^{n}$ и $c,c'\in R$ выполнено
  $\det \!{\bigl (}v_{1}\;\ldots \;v_{i-1}\;\,c\,v+c'v'\;\,v_{i+1}\;\ldots \;v_{n}{\bigr )}=c\,\det \!{\bigl (}v_{1}\;\ldots \;v_{i-1}\;\,v\;\,v_{i+1}\;\ldots \;v_{n}{\bigr )}+c'\det \!{\bigl (}v_{1}\;\ldots \;v_{i-1}\;\,v'\;\,v_{i+1}\;\ldots \;v_{n}{\bigr )}$;
  (2) для любых таких $v_{1},\ldots ,v_{n}\in R^{n}$, что $v_{1},\ldots ,v_{n}$ не попарно различны, выполнено $\det \!{\bigl (}v_{1}\;\ldots \;v_{n}{\bigr )}=0$;
  (3) для любых $a\in \mathrm {Mat} (n,R)$ выполнено $\det a^\mathtt T\!=\det a$;
  (4) для любых $n',n''\!\in \mathbb {N} _{0}$, $a'\in \mathrm {Mat} (n',R)$, $a''\in \mathrm {Mat} (n'',R)$ и $b\in \mathrm {Mat} (n',n'',R)$ выполнено $\det \!{\Bigl (}{\begin{smallmatrix}a'&b\\0&a''\!\end{smallmatrix}}{\Bigr )}\!=\det a'\!\cdot \det a''$.

• Анонс: пусть $K$ — поле; тогда $\mathrm {GL} (n,K)=\{a\in \mathrm {Mat} (n,K)\mid \det a\neq 0\}$ и отобр. ${\biggl (}\!{\begin{aligned}\mathrm {Mat} (n,K)&\to K\\a&\mapsto \det a\end{aligned}}\!{\biggr )}$ — гомоморфизм моноидов по умножению.
• Специальная линейн. группа: $\mathrm {SL} (n,K)=\{a\in \mathrm {Mat} (n,K)\mid \det a=1\}\trianglelefteq \mathrm {GL} (n,K)$. Утверждение: $\forall\,a,b\in\mathrm{Mat}(n,K)\;\bigl(b\cdot a=\mathrm{id}_n\Rightarrow\,b=a^{-1}\bigr)$.
• Ортогональная группа: $\mathrm {O} (n)=\{a\in \mathrm {Mat} (n,\mathbb {R} )\mid a^{\mathtt {T}}\!\cdot a=\mathrm {id} _{n}\}\leq \mathrm {GL} (n,\mathbb {R} )$. Специальная ортогон. группа: $\mathrm {SO} (n)=\mathrm {SL} (n,\mathbb {R} )\cap \mathrm {O} (n)\trianglelefteq \mathrm {O} (n)$.
• Унитарная группа: $\mathrm {U} (n)=\{a\in \mathrm {Mat} (n,\mathbb {C} )\mid {\overline {a}}^{\mathtt {T}}\!\cdot a=\mathrm {id} _{n}\}\leq \mathrm {GL} (n,\mathbb {C} )$. Специальная унитарная группа: $\mathrm {SU} (n)=\mathrm {SL} (n,\mathbb {C} )\cap \mathrm {U} (n)\trianglelefteq \mathrm {U} (n)$.
• Изометрии в $\mathbb {R} ^{n}$: $\mathrm{Isom}(\mathbb R^n)=\{\bigl(v\mapsto a\cdot v+z\bigr)\!\mid a\in\mathrm O(n),\,z\in\mathbb R^n\}$ (док.-во только $\supseteq$). Теорема о комплексных числах и вещественных матрицах.

  Теорема о комплексных числах и вещественных матрицах. Отображение $\Biggl(\!\begin{align}\mathbb C&\to\bigl\{\Bigl(\begin{smallmatrix}\alpha&-\beta\\\beta&\alpha\end{smallmatrix}\Bigr)\!\mid\alpha,\beta\in\mathbb R\bigr\}\\\alpha+\beta\,\mathrm i&\mapsto\!\Bigl(\begin{smallmatrix}\alpha&-\beta\\\beta&\alpha\end{smallmatrix}\Bigr)\end{align}\!\Biggr)$ — изоморфизм колец, а также
  $\mathrm{SO}(2)=\bigl\{\Bigl(\begin{smallmatrix}\cos\varphi&-\sin\varphi\\\sin\varphi&\cos\varphi\end{smallmatrix}\Bigr)\!\mid\varphi\in[0;2\pi)\bigr\}$ и отображение $\biggl(\!\begin{align}\mathrm S^1\!&\to\mathrm{SO}(2)\\\cos\varphi+\sin\varphi\;\mathrm i&\mapsto\!\Bigl(\begin{smallmatrix}\cos\varphi&-\sin\varphi\\\sin\varphi&\cos\varphi\end{smallmatrix}\Bigr)\end{align}\!\biggr)$ — изоморфизм групп.

• Аффинная линейная группа: $\mathrm{AGL}(n,K)=\bigl\{\Bigl(\begin{smallmatrix}a&z\\0&1\end{smallmatrix}\Bigr)\!\mid a\in\mathrm{GL}(n,K),\,z\in K^n\bigr\}\le\mathrm{GL}(n+1,K)$. Геометрический смысл: $\Bigl(\begin{smallmatrix}a&z\\0&1\end{smallmatrix}\Bigr)\!\cdot\!\Bigl(\begin{smallmatrix}v\\1\end{smallmatrix}\Bigr)=\Bigl(\begin{smallmatrix}a\cdot v\,+\,z\\1\end{smallmatrix}\Bigr)$.

1.5.3  Действия групп на множествах

• Действие $\pi$ группы $G$ на мн.-ве $X$ — гомоморфизм моноидов ${\biggl (}\!{\begin{aligned}G&\to \mathrm {Map} (X)\\g&\mapsto \pi _{g}\end{aligned}}\!{\biggr )}$. Утверждение: $\forall\,g\in G\;\bigl(\pi_g\!\in\mathrm{Bij}(X)\bigr)$. Обозначение: $g\,x=\pi _{g}(x)$.
• Примеры: группа $\mathrm {Bij} (X)$ действует на $X$, группы матриц действуют на $K^{n}$, группа $G$ действует на $G/H$ сдвигами (где $H\leq G$) и на $G$ сопряжениями.
• Динамическая система с дискретным$\,/\,$непрерывным временем (каскад$\,/\,$поток) — множество с действием группы $\mathbb {Z} ^{+}$$/\,$группы $\mathbb {R} ^{+}$. Теорема Кэли.

  Теорема Кэли. Пусть $G$ — группа; тогда
  (1) для любых $g\in G$, обозначая через $\mathrm {lm} _{g}$ отображение ${\biggl (}\!{\begin{aligned}G&\to G\\x&\mapsto g\,x\end{aligned}}\!{\biggr )}$, имеем следующий факт: $\mathrm {lm} _{g}$ — биекция (то есть $\mathrm{lm}_g\!\in\mathrm{Bij}(G)$);
  (2) отображение $\biggl(\!\begin{align}G&\to\mathrm{Bij}(G)\\g&\mapsto\mathrm{lm}_g\end{align}\!\biggr)$ — инъективный гомоморфизм групп.

• $G$-Множество — множество с действием группы $G$. Гомоморфизмы $G$-множеств: $\mathrm {Hom} (X,Y)=\{f\in \mathrm {Map} (X,Y)\mid \forall \,g\in G\;{\bigl (}f(g\,x)=g\,f(x){\bigr )}\}$.
• Орбита точки $x$: $Gx$ ($Gx=[x]_\sim$, где $\,\forall\,x,\breve x\in X\;\bigl(x\sim\breve x\,\Leftrightarrow\,\exists\,g\in G\;\bigl(\breve x=g\,x\bigr)\!\bigr)$). Разбиение $G$-множества $X$ на орбиты: $X/G=\{Gx\mid x\in X\}$.
• Транзитивное действие (однородное $G$-мн.-во): $|X/G|=1$. Стабилизатор: $\mathrm {St} _{G}(x)=\{g\in G\mid g\,x=x\}\leq G$. Точное действие: $\bigcap _{x\in X}\mathrm {St} _{G}(x)=\{1\}$.
• Свободное действие (свободное $G$-мн.-во): $\forall \,x\in X\;{\bigl (}\mathrm {St} _{G}(x)=\{1\}{\bigr )}$. Торсор над $G$ — однородн. свободн. $G$-мн.-во ($\forall \,x,y\in X\;\exists !\,g\in G\;{\bigl (}g\,x=y{\bigr )}$).
• Теорема о классах смежности по стабилизатору. Неподвижные точки: $\mathrm {Fix} _{X}(g)=\{x\in X\mid g\,x=x\}$. Лемма Бернсайда. Пример: ${\frac {1}{n!}}\sum _{u\in \mathrm {S} _{n}}|\mathrm {Fix} (u)|=1$.

  Теорема о классах смежности по стабилизатору. Пусть $G$ — группа, $X$ — $G$-множество и $x\in X$; тогда
  (1) отображение ${\biggl (}\!{\begin{aligned}G/\,\mathrm {St} _{G}(x)&\to X\\g\,\mathrm {St} _{G}(x)&\mapsto g\,x\end{aligned}}\!{\biggr )}$ определено корректно, является инъективным гомоморфизмом $G$-множеств и его образ есть $Gx$;
  (2) если $|G|<\infty$, то $|Gx|\,|\mathrm {St} _{G}(x)|=|G|$.

  Лемма Бернсайда. Пусть $G$ — группа, $X$ — $G$-множество и $|G|<\infty$; тогда $|X/G|={\frac {1}{|G|}}\sum _{g\in G}|\mathrm {Fix} _{X}(g)|$.

1.5.4  Автоморфизмы, коммутант, полупрямое произведение групп

• Группа автоморфизмов: $\mathrm {Aut} (G)$. Пример: $\mathrm {Aut} ((\mathbb {Z} /n)^{+})\cong (\mathbb {Z} /n)^{\times }$. Группа внутренних автоморф.-в: $\mathrm {Inn} (G)=\{{\bigl (}x\mapsto g\,x\,g^{-1}{\bigr )}\!\mid g\in G\}\leq \mathrm {Aut} (G)$.
• Центр: $\mathrm {Z} (G)=\{g\in G\mid \forall \,x\in G\;{\bigl (}g\,x=x\,g{\bigr )}\}$. Теорема о внутренних автоморфизмах. Группа внешних автоморф.-в: $\mathrm {Out} (G)=\mathrm {Aut} (G)/\,\mathrm {Inn} (G)$.

  Теорема о внутренних автоморфизмах. Пусть $G$ — группа; тогда отображение ${\biggl (}\!{\begin{aligned}G&\to \mathrm {Aut} (G)\\g&\mapsto {\bigl (}x\mapsto g\,x\,g^{-1}{\bigr )}\!\end{aligned}}\!{\biggr )}$ — гомоморфизм групп, его ядро есть $\,\mathrm {Z} (G)$,
  его образ есть $\,\mathrm {Inn} (G)$ (и, значит, $G/\,\mathrm {Z} (G)\cong \mathrm {Inn} (G)$) и, кроме того, $\mathrm {Inn} (G)\trianglelefteq \mathrm {Aut} (G)$.

• Коммутатор элементов группы (мультипликативный коммутатор): $[g_{1},g_{2}]=g_{1}\,g_{2}\,g_{1}^{-1}g_{2}^{-1}$. Коммутант группы $G$: $[G,G]=\bigl\langle\{[g_1,g_2]\mid g_1,g_2\in G\}\bigr\rangle$.
• Утверждение: $[G,G]\trianglelefteq G$. Теорема о коммутанте. Пример: $[\mathrm {S} _{n},\mathrm {S} _{n}]=\mathrm {A} _{n}$ (док.-во только включения $\subseteq$). Абелианизация группы $G$: $G^{\mathtt {ab}}\!=G/[G,G]$.

  Теорема о коммутанте. Пусть $G$ — группа и $H\trianglelefteq G$; тогда группа $G/H$ абелева, если и только если $[G,G]\subseteq H$ (и, значит, $G/[G,G]$ абелева).

• Простая группа: $|\{H\subseteq G\mid H\trianglelefteq G\}|=2$. Примеры: группы $\mathrm {A} _{n}$ ($n\ge5$) и $\mathrm {SL} (2,K)/\{\mathrm {id} _{2},-\mathrm {id} _{2}\}$ ($K$ — поле, $|K|\ge4$) простые (без доказательства).
• Полупрямое произвед.-е $F\;{\underset {\pi }{\leftthreetimes }}\,H$ относ.-но действия $\pi$ ($\pi \in \mathrm {Hom} (H,\mathrm {Aut} (F))$): $F\times H$ с бинарной операцией $(f_{1},h_{1})\,(f_{2},h_{2})=(f_{1}\,\pi _{h_{1}}\!(f_{2}),h_{1}\,h_{2})$.
• Утверждение: ${\biggl (}\!{\begin{aligned}F\;{\underset {\pi }{\leftthreetimes }}\,H&\to H\\(f,h)&\mapsto h\end{aligned}}\!{\biggr )}$ — гомоморфизм групп. Пример: $\mathrm {AGL} (n,K)\cong (K^{n})^{+}\,{\underset {\pi }{\leftthreetimes }}\,\mathrm {GL} (n,K)$, где $\,\forall\,a\in\mathrm{GL}(n,K),\,z\in K^n\,\bigl(\pi_a(z)=a\cdot z\bigr)$.
• Теорема о полупрямом произведении. Пусть $G$ — группа и $F,H\leq G$; обозначим через $\mathrm {mult}$ отображение ${\biggl (}\!{\begin{aligned}F\times H&\to G\\(f,h)&\mapsto f\,h\end{aligned}}\!{\biggr )}$; тогда
  (1) $\exists \,\pi \in \mathrm {Hom} (H,\mathrm {Aut} (F))\;{\bigl (}\mathrm {mult} \in \mathrm {Hom} (F\;{\underset {\pi }{\leftthreetimes }}\,H,G){\bigr )}\Leftrightarrow \,\forall \,h\in H\;{\bigl (}h\,F\,h^{-1}\!\subseteq F{\bigr )}$, $\mathrm {mult} ^{-1}(1)=\{(g,g^{-1})\mid g\in F\cap H\}$ и $\,\mathrm {Im} \,\mathrm {mult} =FH$;
  (2) $\exists \,\pi \in \mathrm {Hom} (H,\mathrm {Aut} (F))\;{\bigl (}\mathrm {mult} \in \mathrm {Iso} (F\;{\underset {\pi }{\leftthreetimes }}\,H,G){\bigr )}\Leftrightarrow \,F\cap H=\{1\}\,\land \,G=FH\,\land \,\forall \,h\in H\;{\bigl (}h\,F\,h^{-1}\!\subseteq F{\bigr )}$;
  (3) если $|G|<\infty$, то в пункте (2) условие "$G=FH\!$" можно заменить на условие "$\,|G|=|F|\,|H|$".