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

Версия 10:00, 9 января 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),\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/(r))^{\times }\!=\{s+(r)\in R/(r)\mid (r)+(s)=R\}}$ и, если в кольце ${\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 \mathrm {Irr} (\mathbb {C} [x])=\{a\,x+b\mid a,b\in \mathbb {C} ,\,a\neq 0\}}$ и ${\displaystyle \mathrm {Irr} (\mathbb {R} [x])=\{a\,x+b\mid a,b\in \mathbb {R} ,\,a\neq 0\}\cup \{a\,x^{2}+b\,x+c\mid a,b,c\in \mathbb {R} ,\,b^{2}-4a\,c<0\}}$.
• Теорема о неприводимых и простых элементах. Пусть ${\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 \nu \colon R\to N}$, где ${\displaystyle N\subseteq \mathbb {N} _{0}\cup \{-\infty \}}$ и ${\displaystyle \forall \,r\in R\!\setminus \!\{0\},\,s\in R\;{\Bigl (}\exists \,q,t\in R\;{\bigl (}s=q\,r+t\,\land \,\nu (t)<\nu (r){\bigr )}\,\land \,{\bigl (}s\,|\,r\,\Rightarrow \,\nu (s)\leq \nu (r){\bigr )}{\Bigr )}}$.
• Евклидово кольцо — область целостности с евклидовой нормой. Примеры: ${\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})}}$; ${\displaystyle rs\;{\overset {\scriptscriptstyle \mid }{\sim }}\;p_{1}^{d_{1}+e_{1}}\!\cdot \ldots \cdot p_{k}^{d_{k}+e_{k}}\!\;{\overset {\scriptscriptstyle \mid }{\sim }}\;\mathrm {gcd} (r,s)\cdot \mathrm {lcm} (r,s)}$.

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

• Алгоритм Евклида в евклидовом кольце: ${\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\,\Rightarrow \,r_{n}\;{\overset {\scriptscriptstyle \mid }{\sim }}\;\mathrm {gcd} (r,s)}$.
• Соотношение Безу для элементов ${\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))^{\times }}$.
• Расширенный алгоритм Евклида в евкл. кольце: ${\displaystyle u_{n+1}=0}$ и ${\displaystyle v_{n+1}=1}$; на ${\displaystyle i}$-м шаге ${\displaystyle u_{i}=v_{i+1}-q_{i}u_{i+1}}$ и ${\displaystyle v_{i}=u_{i+1}}$; тогда ${\displaystyle u_{1}r_{1}+v_{1}r_{0}\;{\overset {\scriptscriptstyle \mid }{\sim }}\;\mathrm {gcd} (r,s)}$.
• Китайская теорема об остатках для евклидовых колец. Пусть ${\displaystyle R}$ — евклидово кольцо, ${\displaystyle k\in \mathbb {N} _{0}}$, ${\displaystyle r_{1},\ldots ,r_{k}\in R}$ и ${\displaystyle r_{1},\ldots ,r_{k}}$ попарно взаимно
  просты (то есть ${\displaystyle \forall \,i,j\in \{1,\ldots ,k\}\;{\bigl (}i\neq j\,\Rightarrow \,\mathrm {gcd} (r_{i},r_{j})\;{\overset {\scriptscriptstyle \mid }{\sim }}\;1{\bigr )}}$); обозначим через ${\displaystyle r}$ элемент ${\displaystyle r_{1}\cdot \ldots \cdot r_{k}}$ кольца ${\displaystyle R}$; тогда отображение
  ${\displaystyle {\biggl (}\!{\begin{aligned}R/(r)&\to R/(r_{1})\times \ldots \times R/(r_{k})\\s+(r)&\mapsto (s+(r_{1}),\ldots ,s+(r_{k}))\end{aligned}}\!{\biggr )}}$ определено корректно и является изоморфизмом колец.
• Китайская теорема об остатках для целых чисел и многочленов.
  (1) Пусть ${\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\}\;{\bigl (}i\neq j\,\Rightarrow \,\mathrm {gcd} (n_{i},n_{j})=1{\bigr )}}$); обозначим через ${\displaystyle n}$
  число ${\displaystyle n_{1}\cdot \ldots \cdot n_{k}}$; тогда отображение ${\displaystyle {\biggl (}\!{\begin{aligned}\mathbb {Z} /n&\to \mathbb {Z} /n_{1}\times \ldots \times \mathbb {Z} /n_{k}\\a&\mapsto (a{\bmod {n}}_{1},\ldots ,a{\bmod {n}}_{k})\end{aligned}}\!{\biggr )}}$ — изоморфизм колец.
  (2) Пусть ${\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 f}$ многочлен ${\displaystyle f_{1}\cdot \ldots \cdot f_{k}}$; тогда отображение ${\displaystyle {\biggl (}\!{\begin{aligned}K[x]/f&\to K[x]/f_{1}\times \ldots \times K[x]/f_{k}\\a&\mapsto (a{\bmod {f}}_{1},\ldots ,a{\bmod {f}}_{k})\end{aligned}}\!{\biggr )}}$ — изоморфизм колец.
• Функция Эйлера: ${\displaystyle \phi (n)=|\{a\in \mathbb {Z} /n\mid \mathrm {gcd} (a,n)=1\}|=|(\mathbb {Z} /n)^{\times }\!|}$. Пример: если ${\displaystyle p\in \mathbb {P} }$, то ${\displaystyle \phi (p)=p-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)}$.

  Следствие из теоремы Эйлера. Пусть ${\displaystyle n\in \mathbb {N} }$, ${\displaystyle a\in \mathbb {Z} }$, ${\displaystyle \mathrm {gcd} (a,n)=1}$ и ${\displaystyle t\in \mathbb {Z} }$; тогда ${\displaystyle a^{t}\equiv a^{t{\bmod {\phi }}(n)}\;(\mathrm {mod} \;n)}$.

• Теорема о функции Эйлера.
  (1) Пусть ${\displaystyle p\in \mathbb {P} }$ и ${\displaystyle d\in \mathbb {N} }$; тогда ${\displaystyle \phi (p^{d})=p^{d-1}(p-1)}$.
  (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} }$, ${\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 \deg f<n}$ и для любых ${\displaystyle i\in \{1,\ldots ,n\}}$ выполнено ${\displaystyle f(c_{i})=e_{i}}$, и этот многочлен можно найти следующими способами:
  (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}$ — область целостности; тогда
  (1) отображение ${\displaystyle {\biggl (}\!{\begin{aligned}R&\to \mathrm {Q} (R)\\r&\mapsto \mathrm {cl} _{\sim }\!(r,1)\end{aligned}}\!{\biggr )}}$ — инъективный гомоморфизм колец;
  (2) для любых ${\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 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) Отображение ${\displaystyle {\biggl (}\!{\begin{aligned}\mathbb {C} &\to \mathrm {Mat} (2,\mathbb {R} )\,\\\alpha +\beta \,\mathrm {i} &\mapsto \!{\Bigl (}{\begin{smallmatrix}\alpha &-\beta \\\beta &\alpha \end{smallmatrix}}{\Bigr )}\end{aligned}}\!{\biggr )}}$ — инъективный гомоморфизм колец (и, значит, ${\displaystyle \mathbb {C} \cong {\bigl \{}{\Bigl (}{\begin{smallmatrix}\alpha &-\beta \\\beta &\alpha \end{smallmatrix}}{\Bigr )}\!\mid \alpha ,\beta \in \mathbb {R} {\bigr \}}}$).
  (2) Отображение ${\displaystyle {\biggl (}\!{\begin{aligned}\mathbb {H} &\to \mathrm {Mat} (2,\mathbb {C} )\\\alpha +\beta \,\mathrm {i} +\gamma \,\mathrm {j} +\delta \,\mathrm {k} &\mapsto \!{\Bigl (}{\begin{smallmatrix}\alpha +\beta \,\mathrm {i} &\gamma +\delta \,\mathrm {i} \\-\gamma +\delta \,\mathrm {i} &\alpha -\beta \,\mathrm {i} \end{smallmatrix}}{\Bigr )}\end{aligned}}\!{\biggr )}}$ — инъективный гомоморфизм колец (и, значит, ${\displaystyle \mathbb {H} \cong {\bigl \{}{\Bigl (}{\begin{smallmatrix}c&d\\-{\overline {d}}&{\overline {c}}\end{smallmatrix}}{\Bigr )}\!\mid c,d\in \mathbb {C} {\bigr \}}}$).

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 \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 f_{1},\ldots ,f_{n}}$ не попарно различны.
• Знак перестановки ${\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}$, то это сюръективный гомоморфизм групп;
  (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 i_{1},\ldots ,i_{m}}$ попарно различны, выполнено ${\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}}}$) равны.