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

Версия 00:00, 2 октября 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 \mathrm {gcd} }$ и ${\displaystyle \mathrm {lcm} }$ в коммут. кольце ${\displaystyle R}$: ${\displaystyle t\;{\overset {\scriptscriptstyle \mid }{\sim }}\;\mathrm {gcd} (r,s)\;\Leftrightarrow \;\forall \,t'\in R\;{\bigl (}t'\,|\,r\,\land \,t'\,|\,s\,\Leftrightarrow \,t'\,|\,t{\bigr )}}$ и ${\displaystyle t\;{\overset {\scriptscriptstyle \mid }{\sim }}\;\mathrm {lcm} (r,s)\;\Leftrightarrow \;\forall \,t'\in R\;{\bigl (}r\,|\,t'\,\land \,s\,|\,t'\,\Leftrightarrow \,t\,|\,t'{\bigr )}}$.
• Нормировка ${\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 \mathbb {Z} }$ и ${\displaystyle K[x]}$ все идеалы главные. Пример неглавного идеала: идеал ${\displaystyle (2)+(x)}$ в ${\displaystyle \mathbb {Z} [x]}$.
• Теорема о делимости и главных идеалах. Пусть ${\displaystyle R}$ — коммутативное кольцо и ${\displaystyle r,s,t\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 }{\sim }}\;1\,\Leftrightarrow \,(r)=R}$;
  (2) если ${\displaystyle R}$ — область целостности, то ${\displaystyle r\neq 0\;\Rightarrow \;\forall \,a,b\in R\;{\bigl (}a\,r=b\,r\,\Rightarrow \,a=b{\bigr )}}$, а также ${\displaystyle r\;{\overset {\scriptscriptstyle \mid }{\sim }}\;s\;\Leftrightarrow \;\exists \,\varepsilon \in R^{\times }{\bigl (}r=\varepsilon \,s{\bigr )}}$;
  (3) ${\displaystyle t\;{\overset {\scriptscriptstyle \mid }{\sim }}\;\mathrm {lcm} (r,s)\,\Leftrightarrow \,(t)=(r)\cap (s)}$ и, если идеал ${\displaystyle (r)+(s)}$ главный, то ${\displaystyle t\;{\overset {\scriptscriptstyle \mid }{\sim }}\;\mathrm {gcd} (r,s)\,\Leftrightarrow \,(t)=(r)+(s)}$;
  (4) если в кольце ${\displaystyle R}$ все идеалы главные, то ${\displaystyle (R/(r))^{\times }\!=\{s+(r)\in R/(r)\mid \mathrm {gcd} (r,s)\;{\overset {\scriptscriptstyle \mid }{\sim }}\;1\}}$.
• Неприводимые и простые эл.-ты: ${\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)\subseteq \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 R}$ — такая функция ${\displaystyle \nu \,\colon R\to N}$ (${\displaystyle N\subseteq \mathbb {N} _{0}\cup \{-\infty \}}$), что относ.-но ${\displaystyle \nu }$ можно делить с остатком и ${\displaystyle \nu }$ не убывает относ.-но делимости.
• Евклидово кольцо — область целостности с евклидовой нормой. Примеры: ${\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_{1},r_{2},\ldots }$ элементов кольца ${\displaystyle R}$, что для любых ${\displaystyle i\in \mathbb {N} }$ выполнено ${\displaystyle r_{i+1}\,|\!\!|\!\!|\,r_{i}}$;
  (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 \,\mathrm {Irr} (R)=\mathrm {Prime} (R)}$.
• Факториальное кольцо — область целостности с ${\displaystyle {\overset {\scriptscriptstyle \mid }{\sim }}}$-единственным разложением любого ненулевого элемента в произведение неприводимых элементов.
• Примеры: ${\displaystyle \mathbb {Z} }$ — факториальное кольцо (это основная теорема арифметики); если кольцо ${\displaystyle R}$ факториально, то и ${\displaystyle R[x]}$ факториально (без доказательства).
• Теорема о факториальности евклидовых колец.
  (1) Пусть ${\displaystyle R}$ — такая область целостности, что не существует такой бесконечной последовательности ${\displaystyle r_{1},r_{2},\ldots }$ элементов кольца ${\displaystyle R}$, что
  для любых ${\displaystyle i\in \mathbb {N} }$ выполнено ${\displaystyle r_{i+1}\,|\!\!|\!\!|\,r_{i}}$, и, кроме того, ${\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\bmod n_1,\ldots,a\bmod 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\bmod f_1,\ldots,a\bmod 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 {\biggl (}\!{\begin{aligned}'\,\colon R[x]&\to R[x]\\f_{n}x^{n}+\ldots +f_{0}&\mapsto nf_{n}x^{n-1}+\ldots +f_{1}\end{aligned}}\!{\biggr )}}$. Лемма о свойствах формальной производной.

  Лемма о свойствах формальной производной. Пусть ${\displaystyle R}$ — кольцо; тогда для любых ${\displaystyle f,g\in R[x]}$ и ${\displaystyle r\in R}$ выполнено ${\displaystyle (f+g)'=f'\!+g'}$ (и, значит,
  отображение ${\displaystyle \,'}$ — эндоморфизм группы ${\displaystyle R[x]^{+}}$) и ${\displaystyle (rf)'=rf'}$, а также ${\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 )}\;\Leftrightarrow \;\exists \,g\in R[x]\;{\bigl (}f=(x-r)^{k}g\,\land \,g(r)\neq 0{\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 \mathrm {cl} _{\sim }\!(r,s)+\mathrm {cl} _{\sim }\!(t,u)=\mathrm {cl} _{\sim }\!(ru+st,su)}$, ${\displaystyle \mathrm {cl} _{\sim }\!(r,s)\,\mathrm {cl} _{\sim }\!(t,u)=\mathrm {cl} _{\sim }\!(rt,su)}$.
• Лемма о поле частных. Отождествление ${\displaystyle r}$ и ${\displaystyle \mathrm {cl} _{\sim }\!(r,1)}$. Примеры: ${\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{aligned}R&\to \mathrm {Q} (R)\\r&\mapsto \mathrm {cl} _{\sim }\!(r,1)\end{aligned}}\!{\biggr )}}$ — инъективный гомоморфизм колец, а также
  для любых ${\displaystyle r\in R}$ и ${\displaystyle s\in R\!\setminus \!\{0\}}$ выполнено ${\displaystyle \mathrm {cl} _{\sim }\!(r,s)={\frac {\mathrm {cl} _{\sim }\!(r,1)}{\mathrm {cl} _{\sim }\!(s,1)}}}$ (и, значит, ${\displaystyle \mathrm {Q} (R)={\Bigl \{}{\frac {\mathrm {cl} _{\sim }\!(r,1)}{\mathrm {cl} _{\sim }\!(s,1)}}\!\mid r,s\in R,\,s\neq 0{\Bigr \}}}$).

• Несократимая запись: ${\displaystyle {\frac {f}{g}}}$ (${\displaystyle \mathrm {gcd} (f,g)=1}$, ${\displaystyle g}$ нормирован). Правильные дроби: ${\displaystyle {\frac {f}{g}}}$ (${\displaystyle \deg f<\deg g}$). Лемма о несократимой записи и правильных дробях.

  Лемма о несократимой записи и правильных дробях. Пусть ${\displaystyle K}$ — поле и ${\displaystyle z\in K(x)}$; тогда
  (1) существуют единственные такие многочлены ${\displaystyle f,g\in K[x]}$, что ${\displaystyle z={\frac {f}{g}}}$, ${\displaystyle \mathrm {gcd} (f,g)=1}$ и многочлен ${\displaystyle g}$ нормирован;
  (2) существуют единственные такие многочлен ${\displaystyle q\in K[x]}$ и правильная дробь ${\displaystyle {\tilde {z}}\in K(x)}$, что ${\displaystyle z=q+{\tilde {z}}}$.

• Примарные и простейшие дроби: ${\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 ({\underline {e}}_{i}^{j})_{l}^{k}=\delta _{i}^{k}\delta _{l}^{j}}$, ${\displaystyle ({\underline {e}}_{i})^{k}=\delta _{i}^{k}}$, ${\displaystyle ({\underline {e}}^{j})_{l}=\delta _{l}^{j}}$. Утверждение: ${\displaystyle {\underline {e}}_{i}^{j}\cdot {\underline {e}}_{k}^{l}=\delta _{k}^{j}{\underline {e}}_{i}^{l}}$, ${\displaystyle {\underline {e}}_{i}\cdot {\underline {e}}^{j}={\underline {e}}_{i}^{j}}$, ${\displaystyle {\underline {e}}^{j}\cdot {\underline {e}}_{i}=\delta _{i}^{j}}$.
• Строки матрицы ${\displaystyle a}$: ${\displaystyle a_{\bullet }^{i}={\underline {e}}^{i}\cdot a}$. Столбцы матрицы ${\displaystyle a}$: ${\displaystyle a_{j}^{\bullet }=a\cdot {\underline {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 a}$: ${\displaystyle (a^{\mathtt {T}})_{j}^{i}=a_{i}^{j}}$. Утверждение: пусть ${\displaystyle R}$ — коммут. кольцо, ${\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 \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\}}$.
• След квадр. матрицы ${\displaystyle a}$: ${\displaystyle \mathrm {tr} \,a=\sum _{i=1}^{n}a_{i}^{i}}$. Утверждение: пусть ${\displaystyle R}$ — коммут. кольцо, ${\displaystyle a\in \mathrm {Mat} (p,n,R)}$ и ${\displaystyle b\in \mathrm {Mat} (n,p,R)}$; тогда ${\displaystyle \mathrm {tr} (b\cdot a)=\mathrm {tr} (a\cdot b)}$.

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} \!\setminus \!\{1\}}$, ${\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 \mathrm {sgn} (f_{1},\ldots ,f_{n})=(-1)^{|\mathrm {inv} (f_{1},\ldots ,f_{n})|}}$, если числа ${\displaystyle f_{1},\ldots ,f_{n}}$ попарно различны; иначе ${\displaystyle \mathrm {sgn} (f_{1},\ldots ,f_{n})=0}$.
• Знак перестановки ${\displaystyle u}$: ${\displaystyle \mathrm {sgn} (u)=\mathrm {sgn} (u(1),\ldots ,u(n))}$. Теорема о свойствах знака. Знакопеременная группа: ${\displaystyle \mathrm {A} _{n}=\{u\in \mathrm {S} _{n}\!\mid \mathrm {sgn} (u)=1\}\trianglelefteq \mathrm {S} _{n}}$.

  Теорема о свойствах знака. Пусть ${\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}$, то это отображение — сюръекция и ${\displaystyle |\{u\in\mathrm S_n\!\mid\mathrm{sgn}(u)=1\}|=\frac{n!}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 n\in \mathbb {N} _{0}}$; тогда ${\displaystyle \,\mathrm S_n\cong\langle d_1,\ldots,d_{n-1}\!\mid d_1^2,\ldots,d_{n-1}^2,}$
  ${\displaystyle (d_1d_2)^3,(d_2d_3)^3,\ldots,(d_{n-2}d_{n-1})^3,(d_1d_3)^2,(d_1d_4)^2,\ldots,(d_1d_{n-1})^2,(d_2d_4)^2,(d_2d_5)^2,\ldots,(d_2d_{n-1})^2,\ldots,(d_{n-3}d_{n-1})^2\rangle}$.