Алгебра phys 1 ноябрь–декабрь — различия между версиями

Версия 09:00, 28 ноября 2017

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

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

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

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

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

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

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

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

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

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

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

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

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

• Множества матриц, столбцов и строк: ${\displaystyle \mathrm {Mat} (p,n,R)}$, ${\displaystyle R^{n}\!=\mathrm {Mat} (n,1,R)}$ и ${\displaystyle R_{n}\!=\mathrm {Mat} (1,n,R)}$. Сложение матриц и умножение матриц на скаляры.
• Умножение матриц: ${\displaystyle (b\cdot a)_{k}^{i}=\sum _{j=1}^{p}b_{j}^{i}\,a_{k}^{j}}$. Внешняя ассоциативность умножения. Кольцо ${\displaystyle \mathrm {Mat} (n,R)=\mathrm {Mat} (n,n,R)}$, группа ${\displaystyle \mathrm {GL} (n,R)=\mathrm {Mat} (n,R)^{\times }}$.
• Матрицы специального вида: диагональные, скалярные, верхнетреугольные, нижнетреугольные, треугольные. Блочные и блочно-треугольные матрицы.
• Столбцы, строки, матрицы с нулями и одной единицей: ${\displaystyle (\mathbf e_i)^k=\delta_i^k}$, ${\displaystyle (\mathbf e^j)_l=\delta^j_l}$, ${\displaystyle (\mathbf e_i^j)^k_l=\delta_i^k\,\delta^j_l}$. Утверждение: ${\displaystyle \mathbf e_i\cdot\mathbf e^j=\mathbf e_i^j}$, ${\displaystyle \mathbf e^j\cdot\mathbf e_i=\delta_i^j}$, ${\displaystyle \mathbf e_i^j\cdot\mathbf e_k^l=\delta^j_k\,\mathbf e_i^l}$.
• Строки матрицы ${\displaystyle a}$: ${\displaystyle a^i_\bullet=\mathbf e^i\cdot a}$. Столбцы матрицы ${\displaystyle a}$: ${\displaystyle a^\bullet_j=a\cdot\mathbf e_j}$. Утверждение: ${\displaystyle (b\cdot a)_{\bullet }^{i}=b_{\bullet }^{i}\cdot a=\sum _{j=1}^{p}b_{j}^{i}\,a_{\bullet }^{j}}$, а также ${\displaystyle (b\cdot a)_{k}^{\bullet }=b\cdot a_{k}^{\bullet }=\sum _{j=1}^{p}b_{j}^{\bullet }\,a_{k}^{j}}$.
• Операторы умн.-я на матрицу между ${\displaystyle R^n}$ и ${\displaystyle R^p}$: ${\displaystyle \{\bigl(v\mapsto a\cdot v\bigr)\!\mid a\in\mathrm{Mat}(p,n,R)\}}$ — группа по сложению. Теорема об операторах умножения на матрицу.

  Теорема об операторах умножения на матрицу. Пусть ${\displaystyle R}$ — кольцо и ${\displaystyle n,p\in \mathbb {N} _{0}}$; тогда
  (1) ${\displaystyle \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)}$ — изоморфизм групп по сложению и, если ${\displaystyle n=p}$, то это отобр.-е — изоморфизм колец;
  (2) если ${\displaystyle R}$ — комм. кольцо, то ${\displaystyle \{\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)\}}$
  (то есть множество операторов умножения на матрицу между ${\displaystyle R^n}$ и ${\displaystyle R^p}$ совпадает с множеством линейных операторов между ${\displaystyle R^n}$ и ${\displaystyle R^p}$).

• Транспонир.-е матрицы ${\displaystyle a}$: ${\displaystyle (a^{\mathtt {T}})_{j}^{i}=a_{i}^{j}}$. След квадр. матрицы ${\displaystyle a}$: ${\displaystyle \mathrm{tr}\,a=a^1_1+\ldots+a^n_n}$. Линейность ${\displaystyle {}^\mathtt T}$ и ${\displaystyle \mathrm {tr} }$. Теорема о свойствах транспонирования и следа.

  Теорема о свойствах транспонирования и следа. Пусть ${\displaystyle R}$ — коммутативное кольцо и ${\displaystyle n,p,r\in \mathbb {N} _{0}}$; тогда
  (1) для любых ${\displaystyle a\in \mathrm {Mat} (p,n,R)}$ и ${\displaystyle b\in \mathrm {Mat} (r,p,R)}$ выполнено ${\displaystyle (b\cdot a)^{\mathtt {T}}\!=a^{\mathtt {T}}\!\cdot b^{\mathtt {T}}}$ и, если ${\displaystyle n=r}$, то ${\displaystyle \mathrm {tr} (b\cdot a)=\mathrm {tr} (a\cdot b)}$;
  (2) для любых ${\displaystyle a\in\mathrm{GL}(n,R)}$ выполнено ${\displaystyle (a^{-1})^\mathtt T\!=(a^\mathtt T)^{-1}}$, и для любых ${\displaystyle v,w\in R^n}$ выполнено ${\displaystyle v^\mathtt T\!\cdot w=\mathrm{tr}(v\cdot w^\mathtt T)=v^1w^1+\ldots+v^nw^n}$.

• Симметричные и антисимм. матрицы: ${\displaystyle \mathrm{SMat}(n,R)=\{a\in\mathrm{Mat}(n,R)\mid a^\mathtt T\!=a\}}$, ${\displaystyle \mathrm{AMat}(n,R)=\{a\in\mathrm{Mat}(n,R)\mid a^\mathtt T\!=-a\,\land\,a^1_1=\ldots=a^n_n=0\}}$.

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

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

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

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

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

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

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