Dump more hwsHEADmaster

5 files changed, 510 insertions, 0 deletions

diff --git a/alg/alg-5.tex b/alg/alg-5.tex
new file mode 100644
index 0000000..4832df7
--- /dev/null
+++ b/alg/alg-5.tex
@@ -0,0 +1,90 @@
+\documentclass[11pt]{article}
+\usepackage{../intro}
+
+\lhead{\color{gray} \small \textit{Шарафатдинов Камиль 192}}
+\rhead{\color{gray} \small \textit{алг-5}}
+\title{Алгебра 5}
+
+% -- Here bet  dragons --
+\begin{document}
+\maketitle
+\drawcat{30pt}
+\clearpage
+
+\dmquestion{1}
+
+    Такое действие - просто умножение на три разных ненулевых коэффициента координат данного вектора. Поэтому орбита какого-то вектора - все векторы, у которых в тех же местах стоят ненулевые координаты (получается, всего $8$ орбит).
+
+    По тем же соображениям, стабилизатор элемента $(x_1, x_2, x_3)$ -- матрицы вида $\mathrm{diag}(a_1, a_2, a_3) \in \mathrm{GL}_n(\mathbb{R})$ со следующим условием: если $x_i \neq 0$, то $a_i = 1$.
+
+    Простая проверка показывает, что любая такая матрица лежит в стабилизаторе;
+    любая другая не оставляет вектор на месте,
+    потому что не оставляет соответствующую координату на месте.
+
+\dmquestion{2}
+
+    Ядро неэффективности такого действия - это такие $g$, что
+    \[
+        \forall h \in G : ghg^{-1} = h
+    \]
+
+    Умножая на $g$ справа получаем
+    \[
+        \forall h \in G : gh = hg
+    \]
+
+    а это в точности определение элемента из центра. \qed
+
+\dmquestion{3}
+
+    Упорядочим $G = \mathbb{Z} \oplus \mathbb{Z}$ лексикографически.
+    Тогда посмотрим на действие $G$ на себя левыми сдвигами
+    и для каждого элемента найдем соответствующую перестановку:
+
+    \begin{align*}
+        &(0, 0): \begin{bmatrix}
+            (0, 0) \mapsto (0, 0)\\
+            (0, 1) \mapsto (0, 1)\\
+            (1, 0) \mapsto (1, 0)\\
+            (1, 1) \mapsto (1, 1)\\
+        \end{bmatrix} = \mathrm{id}\\
+        &(0, 1): \begin{bmatrix}
+            (0, 0) \mapsto (0, 1)\\
+            (0, 1) \mapsto (0, 0)\\
+            (1, 0) \mapsto (1, 1)\\
+            (1, 1) \mapsto (1, 0)\\
+        \end{bmatrix} = (1\ 2)(3\ 4)\\
+        &(1, 0): \begin{bmatrix}
+            (0, 0) \mapsto (1, 0)\\
+            (0, 1) \mapsto (1, 1)\\
+            (1, 0) \mapsto (0, 0)\\
+            (1, 1) \mapsto (0, 1)\\
+        \end{bmatrix} = (1\ 3)(2\ 4)\\
+        &(1, 1): \begin{bmatrix}
+            (0, 0) \mapsto (1, 1)\\
+            (0, 1) \mapsto (1, 0)\\
+            (1, 0) \mapsto (0, 1)\\
+            (1, 1) \mapsto (0, 0)\\
+        \end{bmatrix} = (1\ 4)(2\ 3)\\
+    \end{align*}
+
+    Это и есть подгруппа $S_n$, изоморфная $G$
+
+\dmquestion{4}
+
+    Пусть $\tau = (1\ 2\ 3\ \ldots\ n)$.
+    Тогда нам надо найти все такие $\sigma \in S_n$, что 
+    \[
+        \sigma \tau \sigma^{-1} = \tau  \Leftrightarrow \sigma \tau = \tau \sigma
+    \]
+    
+    Понятно, что $\tau$ коммутирует со всеми своими степенями.
+
+    Пусть единица при $\sigma$ переходит в $k$.
+    Тогда, чтобы не терять коммутативность, $2$ переходит в $k + 1$.
+    Чтобы теперь не противоречить коммутативности нового перехода для $2$,
+    $3$ должна переходить в $k + 2$ и так далее$^\dagger$. Тогда каждый элемент переходит на $k$ позиций вправо, а это и есть $k$-ая степень $\tau$. \qed
+
+    $^\dagger$ $k + 1, k + 2$ берутся по модулю $n$, с прибавлением единички, если надо, чтобы не выходить из $[1..n]$
+
+\end{document}
diff --git a/alg/alg-6.tex b/alg/alg-6.tex
new file mode 100644
index 0000000..03cdbca
--- /dev/null
+++ b/alg/alg-6.tex
@@ -0,0 +1,117 @@
+\documentclass[11pt]{article}
+\usepackage{../intro}
+
+\lhead{\color{gray} \small \textit{Шарафатдинов Камиль 192}}
+\rhead{\color{gray} \small \textit{алг-6}}
+\title{Алгебра 6}
+
+% -- Here bet  dragons --
+\begin{document}
+\maketitle
+\drawcat{30pt}
+\clearpage
+
+\dmquestion{1.1}
+
+    Из линейной алгебры мы знаем кучу эквивалентных условий для обратимости матрицы, например, что её определитель не равен нулю.
+
+\dmquestion{1.2}
+    
+    $A$ делитель нуля $\Leftrightarrow$ $A$ необратима
+
+    \begin{itemize}
+        \item[$\Rightarrow$] Факт с лекции: для любого кольца делитель нуля необратим
+        \item[$\Leftarrow$] Пусть $A$ необратима,
+        тогда у системы $Ax = 0$ есть ненулевое решение $(x_1, x_2)$.
+        Но тогда 
+        \[
+            A \begin{bmatrix} x_1 & 0\\ x_2 & 0\end{bmatrix} = 0
+        \]
+
+        Обе матрицы ненулевые, а значит $A$ - делитель нуля.
+    \end{itemize}
+
+\dmquestion{1.3}
+
+    Рассмотрим оператор, задаваемый матрицей $A \in M_{2\times2}(\mathbb{C})$ и посчитаем его характеристический многочлен:
+    \[
+        \chi(x) = x^2 + ax + b
+    \]
+
+    У него над полем $\mathbb{C}$ два корня:
+    \[
+        x_1, x_2 = \frac{-b \pm \sqrt{b^2 - 4c}}{2}
+    \]
+    откуда следует, что мнимые части отличаются только знаком.
+    Значит, либо оба корня ненулевые и не действительные, либо оба действительные.
+
+    Докажем, что они оба действительные: предположим противное, они оба комплексные. Тогда над полем $\mathbb{C}$ ЖНФ оператора имеет вид \[
+        \begin{bmatrix}
+            x_1 & 0\\
+            0 & x_2
+        \end{bmatrix}
+    \]
+    ранг которой равен $2$, но тогда и ранг $A$ равен $2$, значит она обратима,
+    а значит не может быть нильпотентом.
+
+    Тогда оба корня действительные и, по аналогичным соображениям,
+    один из них равен $0$.
+    
+    Получается, что $A = CJC^{-1}$, где $J$ - ее Жорданова форма, имеющая вид
+    \[
+        \begin{bmatrix}
+            t & 0\\
+            0 & 0
+        \end{bmatrix}
+        \text{ или }
+        \begin{bmatrix}
+            0 & 1\\
+            0 & 0
+        \end{bmatrix}
+        \text{ или }
+        \begin{bmatrix}
+            0 & 0\\
+            0 & 0
+        \end{bmatrix}
+    \]
+
+    Ну и понятно, что $A = CJC^{-1}$ - нильпотент для любой обратимой $C$:
+    \[
+        A^2 = (CJC^{-1})^2 = CJC^{-1}CJC^{-1} = CJJC^{-1} = 0
+    \]
+
+\dmquestion{2}
+
+    Докажем такой факт: $p \in I \Rightarrow \gcd(p, n) \in I$.
+
+    Мы хотим: $\exists x \suchthat px = \gcd(p, n)$ или в целых числах:
+    $px - yn = \gcd(p, n)$. Но это обычное диофантово уравнение относительно $x$ и $y$,
+    и оно имеет решения $(x_0 + mn, y_0 + mp), m \in \mathbb{Z}$.
+
+    $x$ из решений отличаются на $n$, поэтому найдется $0 \leqslant x < n$, для которого
+    выполняется $px = \gcd(p, n) (\mathrm{mod}\  n)$, а значит, $\gcd(p, n) \in I$.
+
+    Тогда видно, что любой идеал натянут на какие-то делители $n$.
+
+    \medskip
+
+    Идеал, порожденный каким-то делитель $d$ -- все остатки, делящиеся на $d$:
+    \begin{itemize}[leftmargin=1in,rightmargin=1in]
+        \item[1] все, что мы можем получить, умножая $d$ на другие элементы - только остатки, делящиеся на $d$.
+        \item[2] любой остаток, делящийся на $d$ мы можем получить, просто умножив его на первые несколько остатков ($0d, 1d, 2d, \ldots$)
+    \end{itemize}
+
+\dmquestion{3}
+    
+    Пусть $f = (x - 1), \ g = (x - 2)$. Тогда $I = (\{f, g\})$ - идеал. 
+
+    $f$ (и $g$) единственным образом раскладывается в произведение
+    двух элементов кольца: $1(x - 1)$ (и $1(x - 2)$).
+
+    $f$ и $g$ могут быть порождены только $1$,
+    поскольку это единственный их общий множитель.
+    Так как $(1) = \mathbb{Z}[x] \neq I$,
+    то $I$ не порожден $1$, а значит не порожден никаким элементом кольца. \qed
+
+
+\end{document}
diff --git a/alg/alg-7.tex b/alg/alg-7.tex
new file mode 100644
index 0000000..f28cbc5
--- /dev/null
+++ b/alg/alg-7.tex
@@ -0,0 +1,209 @@
+\documentclass[11pt]{article}
+\usepackage{../intro}
+
+\lhead{\color{gray} \small \textit{Шарафатдинов Камиль 192}}
+\rhead{\color{gray} \small \textit{алг-6}}
+\title{Алгебра 6}
+
+% -- Here bet  dragons --
+\begin{document}
+\maketitle
+\drawcat{30pt}
+\clearpage
+
+\dmquestion{1}
+
+    Достаточно показать, что многочлен остается на месте для всех транспозиций вида $(i, i + 1)$, тогда он остается на месте для любой перестановки.
+
+    % (x_1 + x_2 - x_3 - x_4)(x_1 - x_2 + x_3 - x_4)(x_1 - x_2 - x_3 + x_4)
+    \begin{itemize}[leftmargin=0.7in]
+        \item[$(x_1, x_2)$:]
+        \begin{tabular}{|c}
+        \(
+            (x_1 + x_2 - x_3 - x_4)(x_2 - x_1 + x_3 - x_4)(x_2 - x_1 - x_3 + x_4)
+        \)\\
+
+        последние две скобки поменялись местами и поменяли знак
+        \end{tabular}
+
+        \item[$(x_2, x_3)$:]
+        \begin{tabular}{|c}
+        \(
+            (x_1 + x_3 - x_2 - x_4)(x_1 - x_3 + x_2 - x_4)(x_1 - x_3 - x_2 + x_4)
+        \)\\
+
+        первые две скобки поменялись местами
+        \end{tabular}
+
+        \item[$(x_3, x_4)$:]
+        \begin{tabular}{|c}
+        \(
+            (x_1 + x_2 - x_4 - x_3)(x_1 - x_2 + x_4 - x_3)(x_1 - x_2 - x_4 + x_3)
+        \)\\
+
+        последние две скобки поменялись местами
+        \end{tabular}
+
+    \end{itemize}
+
+    Значит, многочлен симметрический.
+    \vspace*{20pt}
+
+    Так так многочлен однородный, то мы можем сразу выписать все мономы, которые входят в разложение (возможно, с нулевыми коэффициентами)
+
+    $L(f) = x_1^3$, поэтому на итерациях алгоритма могут получиться
+    три разных старших члена: $x_1^3, \ x_1^2 x_2, \ x_1 x_2 x_3$.
+    Для каждого из них мономы: $\sigma_1^3, \ \sigma_1\sigma_2, \ \sigma_3$.
+    Причем первый из них точно входит с коэффициентом $1$.
+
+    Теперь, методом неопределенных коэффициентов узнаем коэффициенты остальных мономов:
+    \[
+        f = \sigma_1^3 + A\sigma_1\sigma_2 + B\sigma_3
+    \]
+    \[
+        A = -4, \qquad B = 8
+    \]
+
+    Получаем:
+    \[
+        f = \sigma_1^3 - 3\sigma_1\sigma_2 + 8\sigma_3
+    \]
+
+\dmquestion{2}
+
+    Пусть $x_1, x_2, x_3$ -- корни многочлена
+    $3\br{ x^3 + \frac{2}{3}x^2 - \frac{1}{3} }$
+
+    Тогда нас просят посчитать
+    \[
+        \frac{1}{x_1} + 
+        \frac{1}{x_2} + 
+        \frac{1}{x_3} =
+        \frac{x_1x_2 + x_1x_3 + x_2x_3}{x_1x_2x_3} = \frac{\sigma_2}{\sigma_3}
+    \]
+
+    По теореме Виета
+    \begin{align*}
+        \sigma_2 = 0\\
+        \sigma_3 = \frac{1}{3}
+    \end{align*}
+
+    Значит, то, что нам нужно равно $0$.
+
+\clearpage
+
+\dmquestion{3}
+
+    Наш многочлен:
+    \[
+        f = x^4 + x - 1
+    \]
+
+    Пусть нужный многочлен имеет вид
+    \[
+        g = x^4 - \alpha_1 x^3 + \alpha_2 x^2 - \alpha_3 x + \alpha_4
+    \]
+
+    а $x_1, x_2, x_3, x_4$ -- корни нашего многочлена
+
+    Тогда от нас хотят, чтобы:
+    \begin{align*}
+        \alpha_4 &= (x_1 x_2 x_3 x_4)^3 =\\
+            &= \sigma_4^3
+            = -1\\[12pt]
+        \alpha_3 &= (x_1 x_2 x_3)^3 + (x_1 x_2 x_4)^3 +
+                    (x_1 x_3 x_4)^3 + (x_2 x_3 x_4)^3 =\\
+            &= 3 \sigma_4^2 \sigma_1 - 3 \sigma_4 \sigma_3 \sigma_2 + \sigma_3^3
+            = -1\\[12pt]
+        \alpha_2 &= (x_1 x_2)^3 + (x_1 x_3)^3 + (x_1 x_4)^3 +
+                    (x_2 x_3)^3 + (x_2 x_4)^3 + (x_3 x_4)^3\\
+            &= 3\sigma_4\sigma_1^2 - 3\sigma_4\sigma_2 -
+               3\sigma_1\sigma_3\sigma_2 + 3\sigma_3^2 +
+               \sigma_2^3
+            = 3\\[12pt]
+        \alpha_1 &= x_1^3 + x_2^3 + x_3^3 + x_4^3 =\\
+            &= 3\sigma_3 + \sigma_1^3 - 3\sigma_1\sigma_2
+            = -3
+    \end{align*}
+
+    Итого, нужный нам многочлен:
+    \[
+        g = x^4 + 3x^3 + 3x^2 + x - 1
+    \]
+
+\dmquestion{4}
+    
+    \newcommand{\almostD}{\ensuremath{\mathrm{D}_\text{почти}}}
+
+    {\color{lightgray}
+        Здесь было рассуждение про почти дискриминант
+        \[
+            \almostD = (x_1 - x_2)(x_2 - x_3)(x_1 - x_3)
+        \]
+
+        который тоже равен нулю, если есть кратный корень,
+        но он оказался не симметрическим и пришлось считать обычный :(
+    }
+
+    %У честного дискриминанта 6 степень и считать его чото не хочется :(
+
+    %Понятно, что \almostD \ равен нулю тогда же, когда и
+    %$\mathrm{D}_\text{честный}$, а именно, когда есть кратный корень.
+
+    %Как в 1 задаче разложим \almostD \ в элементарные:
+    %\[
+    %    \almostD = \sigma_1 \sigma_2 + \sigma_3
+    %\]
+
+    \[
+        f = x^3 - 3x + \lambda
+    \]
+
+    \[
+        \sigma_1 = 0, \ \ \sigma_2 = -3, \ \ \sigma_3 = -\lambda
+    \]
+
+    \[
+        \mathrm{D}(f) = - 27 \sigma_3^2 - 4 \sigma_3 \sigma_1^3 +
+        18 \sigma_3 \sigma_1 \sigma_2 + \sigma_1^2 \sigma_2^2 -
+        4 \sigma_2^3 = -27 \sigma_3^2 - 4 \cdot (-27)
+    \]
+
+    Мы хотим, чтобы дискриминант был равен $0$, значит $-\lambda = \sigma_3 = \pm 2$
+
+\dmquestion{5}
+
+    Докажем по индукции, что $\mathbb{N}^k$ с лексикографическим порядком
+    -- фундированное, из этого сразу будет следовать утверждение задачи.
+
+    База: $\mathbb{N}$ -- очевидно
+
+    Теперь пусть $\mathbb{N}^{k - 1}$ -- фундированное, а $\mathbb{N}^{k}$ -- нет.
+
+    Рассмотрим тогда бесконечно убывающую цепь в $\mathbb{N}^{k}$. Назовем ее $C$. $C_i$ тогда -- строчка из натуральных чисел -- `цифр'.
+
+    Теперь посмотрим на те переходы от $C_i$ к $C_{i + 1}$,
+    когда меняются первые $k - 1$ цифр.
+    Дальше есть два варианта: таких переходов:
+    \begin{itemize}
+    \item[1.] \textit{бесконечное число}
+    \par
+        Тогда при каждом таком переходе явно не увеличивается подслово из первых
+        $k - 1$ цифр, но все-таки, по построению, изменяется. Значит, уменьшается.
+        Тогда, забыв про последнюю цифру,
+        мы получим бесконечно убывающую цепь в $\mathbb{N}^{k - 1}$.
+    \item[2.] \textit{конечное число}
+        Это означает, что начиная с какого-то момента
+        уменьшается только последняя цифра.
+        А так как $\mathbb{N}$ тоже фундированное,
+        то цепь $C$ когда-то закончится.
+    \end{itemize}
+
+    В любом случае приходим к противоречию, значит, $\mathbb{N}^k$ - фундированное. \qed
+
+    \vspace*{30pt}
+
+    Утверждение задачи -- переформулировка фундированности $\mathbb{N}^n$:
+    моном однозначно определяется степенями переменных.
+
+\end{document}
diff --git a/alg/alg-8.pdf b/alg/alg-8.pdf
new file mode 100644
index 0000000..42a1841
--- /dev/null
+++ b/alg/alg-8.pdf
diff --git a/alg/alg-8.tex b/alg/alg-8.tex
new file mode 100644
index 0000000..0f757eb
--- /dev/null
+++ b/alg/alg-8.tex
@@ -0,0 +1,94 @@
+\documentclass[11pt]{article}
+\usepackage{../intro}
+
+\lhead{\color{gray} \small \textit{Шарафатдинов Камиль 192}}
+\rhead{\color{gray} \small \textit{алг-8}}
+\title{Алгебра 8}
+
+% -- Here bet  dragons --
+\begin{document}
+\maketitle
+%\drawcat{30pt}
+\clearpage
+
+\dmquestion{1}
+
+    \[
+        f = x^5 + x^3 + x, \quad g = x^4 + x + 1
+    \]
+
+    \begin{align*}
+        (f, g) = (x^5 + x^3 + x, \quad x^4 + x + 1) =\\
+        (x^3 - x^2, \quad x^4 + x + 1) =\\
+        (x^3 - x^2, \quad x^2 + x + 1) =\\
+        (-2x^2 - x, \quad x^2 + x + 1) =\\
+        (- x, \quad x^2 + x + 1) =\\
+        (x, \quad x^2 + x + 1) = 1\\
+    \end{align*}
+
+\dmquestion{2}
+
+    Так как $[\mathbb{Q}(\sqrt[3]{2}) : \mathbb{Q}] = 3$, то мы можем записать так:
+    \[
+        \frac{1 - \sqrt[3]{3}}{1 + \sqrt[3]{3} - \sqrt[3]{9}} = a + b\sqrt[3]{3} + c\sqrt[3]{9}
+    \]
+
+    и умножить на знаменатель обе части ($\alpha = \sqrt[3]{3}$:
+    \[
+        1 - \alpha = (a + b\alpha + c\alpha^2)(1 + \alpha - \alpha^2) =
+        a - b + c + \alpha(a + b - c) + \alpha^2(b + c - a)
+    \]
+
+    Получаем СЛУ
+    \[
+        \left[\begin{array}{@{}ccc|c@{}}
+            1 & -1 & 1 & 1 \\
+            1 & 1 & -1 & -1 \\
+            -1 & 1 & 1 & 0 \\
+        \end{array}\right]
+    \]
+
+    Решаем, получаем
+    \begin{align*}
+        a &= 0\\
+        b &= -\frac{1}{2}\\
+        c &= \frac{1}{2}\\
+    \end{align*}
+
+    \[
+        \frac{1 - \sqrt[3]{3}}{1 + \sqrt[3]{3} - \sqrt[3]{9}} = -\frac{\sqrt[3]{3}}{2} + \frac{\sqrt[3]{9}}{2}
+    \]
+
+\dmquestion{3}
+
+    Аналогично семинарской задаче:
+    \[
+        \mathbb{Q}(\sqrt3 + \sqrt5) = \mathbb{Q}(\sqrt3)(\sqrt{5})
+    \]
+
+    Степень расширения равна $2 \cdot 2 = 4$.
+
+    Поэтому по теореме с лекции минимальный многочлен степени $4$.
+
+    \begin{align*}
+        x = \sqrt3 + \sqrt5\\
+        x^2 = 8 + 2\sqrt{15}\\
+        (x^2 - 8)^2 = 60\\
+        x^4 - 16x^2 + 4 = 0
+    \end{align*}
+
+    У нас есть зануляющий многочлен нужной степени, значит, это то, что нам нужно.
+\dmquestion{4}
+
+    \begin{align*}
+        x^4 + x^2 + 1 =
+        (x^2)^2 + x^2 + 1 \\
+        \text{корни: } x^2 =
+        \frac{-1 \pm \sqrt{-3}}{2} =
+        -\sqrt[3]{-1}; \sqrt[3]{-1}^2\\
+        x = \left\{ \pm \sqrt[3]{-1}; \pm \sqrt[3]{-1}^2 \right\}
+    \end{align*}
+
+    Теперь видно, что присоединение $\sqrt[3]{-1}$ дает все корни, а степень такого расширения равна $3$.
+
+\end{document}