Алгебра. Доказательства.

В процессе составления использовались материалы Аруновой Анастасии

Модуль 1

1. Какие три условия достаточно наложить на функцию от столбцов матрицы, чтобы она обязательно была детерминантом? Ответ обоснуйте для матриц второго порядка.

Утверждение. На функцию от столбцов матрицы достаточно наложить следующие три условия, чтобы она обязательно была детерминантом:

1. Линейность.

2. Кососимметричность ($f(x, y) = -f(y, x)$)

   $\det A = 0$, если есть 2 одинаковых столбца

3. $f({E_n}) = 1$.

Доказательство.

Докажем при $n = 2$. Разложим столбцы:

Определим, чему равна функция от матрицы:

2. Сформулировать и доказать критерий линейной зависимости.

Утверждение. $a_1, ..., a_s$ - линейно зависимы $\Leftrightarrow$ хотя бы один из $a_1, ..., a_s$ линейно выражаются через другие.

Доказательство.

1. Необходимость

Дано: $a_1, ..., a_s$ - линейно зависимы

Доказать: найдутся выражаемые через другие.

По определению:

Пусть $\alpha_1 \neq 0$. Тогда:

2. Достаточность

Дано: один линейно выражается через другие

Доказать: они линейно зависимы

Пусть $a_1 = \beta_2 a_2 + ... + \beta_s a_s$. Тогда $\underbrace{1 \cdot a_1 - \beta_2 a_2 - ... - \beta_s a_s}_{\text{нетривиальная лин. комб.}} = 0 \Rightarrow$ по определению они л. з.

3. Сформулируйте и докажите теорему о базисном миноре.

Теорема. (о базисном миноре)

1. Базисные строки (столбцы), соответствующие любому базисному минору $M$ матрицы $A$ л. н. з.

2. Строки (столбцы) матрицы $A$, не входящие в $M$ являются линейной комбинацией базисных строк.

Доказательство.

1. предположим, что они линейно-зависимы $\Rightarrow$ по критерию линейной зависимости хотя бы один из них является линейной композицией остальных $\Rightarrow$ базисный минор равен нулю $\Rightarrow$ получаем противоречие с определением базисного минора

2. Без ограничения общности можем считать, что базисный минор $M$ расположен в левом верхнем углу матрицы

Здесь $Rg A = r$. Возьмем строку $A_k$, где $k > r$, и покажем, что $\exists \lambda_1, ..., \lambda_r \in \R: A_k = \lambda_1 A_1 + ... + \lambda_r A_r$ - базисные строки.

Составим определитель $\Delta = \begin{vmatrix} a_{11} & \dots & a_{1\ r} & a_{1\ j}\\ \vdots & & \vdots & \vdots \\ a_{r\ 1} & \dots & a_{r\ r} & a_{r\ j} \\ a_{k\ 1} & \dots & a_{k\ r} & a_{k\ j} \end{vmatrix}$, полученный добавлением к $M$ $k$-ой строки и $j$-ого столбца (выбранного произвольно, $j \in [1; n]$). Покажем, что $\Delta = 0$. Если $j \leq r$, то в $\Delta$ есть 2 одинаковых столбца $\Rightarrow \Delta = 0$. Если $j > r$, то $\Delta$ - минор матрицы $A$ порядка $r + 1 \Rightarrow \Delta = 0$ по определению ранга.

Теперь разложим по $j$-ому столбцу: $a_{1\ j}B_1 + ... + a_{r\ j} B_r + a_{k\ j} B_{k} = 0$, где $B_1, ..., B_k$ - алгебраические дополнения соответствующих элементо в $\Delta$. Причем $B_k = \pm M \neq 0 \Rightarrow \\ \Rightarrow a_{kj} = -\frac{B_1}{B_k} a_{1j} - ... - \frac{B_r}{B_k} a_{rj}$, где $j = \overline{1, n}$. Тогда $A_k$ - линейная комбинация строк $A_1, ..., A_r$.

4. Сформулируйте и докажите теорему о ранге матрицы (теорема о базисном миноре предполагается известной).

Следствие. (Теорема о ранге матрицы)

Ранг матрицы равен максимальному числу ее линейно независымых строк и равен максимальному числу линейно независимых столбцов.

Доказательство.

Докажем только для строк. Для столбцов - аналогично.

Пусть $Rg A = r$, а максимальное количество линейно независимых строк равно $k$. Покажем, что $k = r$.

1. Так как в $A$ есть $r$ линейно независимых строк (то есть $Rg A = r$, это базисные строки некоторой базисной матрицы) $\Rightarrow k \geq r$

2. Покажем, что $k \leq r$ Вычеркнем в $A$ все строки кроме $k$ л.н.з. строк. Получим матрицу $A_1$. В ней $k$ строк, при $Rg A_1 = k$, так как если бы $Rg A_1$ был $< k$, то среди ее $k$ строк только часть была бы базисной и по 2-ой части теоремы о базисном миноре нашлась бы строка, являющаяся линейной комбинацией базисных, но тогда по критерию линейной зависимости все строки в $A_1$ - л/з. Противоречие. Тогда БМ матрицы $A_1$ имеет порядок $k$ и является не равным нулю минором матрицы $A$ (исходной) $\Rightarrow k \leq r$ - максимальный порядом ненулевого минора в $A \Rightarrow k = r$

5. Сформулировать и доказать следствие теоремы о базисном миноре для квадратных матриц (критерий невырожденности).

Следствие. Рассмотрим квадратную матрицу $A \in M_n(\R)$. Следующие три условия эквивалентны:

1. $\det A \neq 0$

2. $Rg\ A = n$

3. все строки $A$ линейно независимы

Доказательство.

1. $1 \Rightarrow 2$ Пусть $\det A \neq 0 \Rightarrow$ в $A$ есть минор порядка $n$, он $\neq 0 \Rightarrow$ по определению $Rg\ A = n$.

2. $2 \Rightarrow 3$ Пусть $Rg\ A = n \Rightarrow$ все строки базисные $\Rightarrow$ по первому пункту теоремы о базисном миноре (строки базисного минора л. н. з.) они все л. н. з.

3. $3 \Rightarrow 1$ Пусть строки $A$ л. н. з. Предположим противное: $\det A = 0 \Rightarrow Rg\ A < n \Rightarrow$ по второму пункту теоремы о базисном миноре (строки, не входящие в базисный минор являются лин. комб. базисных) по крайней мере одна из строк является линейной комбинацией остальных $\Rightarrow$ по критерию л. з. все строки л. з. - $\perp$

Модуль 2

1. Сформулируйте теорему Кронекера-Капелли и докажите её.

Теорема. (теорема Кронекера-Капелли)

СЛАУ $A x = b$ - совместна $\Leftrightarrow Rg\ A = Rg(A | b)$

Доказательство.

Необходимость

Дано: СЛАУ совместна, доказать $Rg\ A = Rg(A | b)$

По условию $\exists x^0 = \begin{pmatrix} x^0_1 \\ \vdots \\ x^0_n \end{pmatrix}$, такое что $A x^0 = b$. Или в векторной форме: $x_1^0 A_1 + ... + x^0_n A_n = b$, где $A = \begin{pmatrix} A_1 & \dots & A_n \end{pmatrix}$ (то есть столбец $b$ является линейной комбинацией столбцов $A_1, ..., A_n$).

Пусть $Rn\ A = r \Rightarrow \exists$ базисный минор $M$ порядка $r$ в матрице $A$. Предположим, что он расположен в левом верхнем углу матрицы $A$. Столбцы $A_1, ..., A_r$ - базисные, а $A_{r + 1}, ..., A_n$ их линейная комбинация по теореме о базисном миноре.

$b = x_1^0 A_1 + ... + x_r^0 A_r + x^0_{r + 1} (\lambda_{1\ r + 1} A_1 + ... + \lambda_{r\ r + 1} A_r) + ... + x_n^0 (\lambda_{1\ n} A_1 + ... + \lambda_{r\ n} A_r) = \\ = (x_1^0 + \lambda_{1\ r + 1}\ x^0_{r + 1} + ... + \lambda_{1\ n} x^0_n) A_1 + (x_r^0 + \lambda_{r\ r+ 1} x^0_{r + 1} + ... + \lambda_{r\ n} x_n^0) A_r \Rightarrow M$ - базисный минор и в расширенной матрице $(A | b)$

1. он $\neq 0$

2. все окаймляющие его миноры равно нулю, так как в них один из столбцов является линейной комбинацией $A_1, .., A_r$

Достаточность

Дано: $Rg\ A = Rg(A|b) = r$

Доказать: СЛАУ совместна

Пусть $Rg\ A = r$. Пусть $M$ - базисный минор $A$, предположим $M$ в верхнем углу матрицы $A$. Тогда $M$ - является базисным минором и в расширенной матрице $(A|b)$, так как $Rg\ A = Rg(A|b) = r$ и $M \neq 0$ порядка $r$.

$\Rightarrow$ по теореме о базисном миноре столбец $b$ является линейной комбинацией столбцов $A_1, ..., A_r$ (базисных).

$b = \lambda_1 A_1 + ... + \lambda_r A_r \Rightarrow$ столбец $x^0 = \begin{pmatrix} \lambda_1 \\ \vdots \\ \lambda_r \\ 0 \\ \vdots \\ 0 \end{pmatrix}$ - решение СЛАУ $Ax = b$, так как справедлива векторная форма записи.

$\lambda_1 A_1 + ... + \lambda_r A_r + 0 \cdot A_{r + 1} + ... + 0 \cdot A_n = b \Leftrightarrow A x^0 = b$

2. Дайте определение фундаментальной системы решений (ФСР) однородной системы линейных уравнений. Докажите теорему о существовании ФСР.

Определение. (ФСР)

Любые $n - r$ (где $r = Rg\ A$) линейно независимых столбцов, является решениями однородной СЛАУ $Ax = 0$ называют фундаментальной системой решений ОСЛАУ.

Теорема. (о существовании ФСР)

Рассмотрим ОСЛАУ $Ax = 0$, у нее $\exists k = n - r$ линейно независимых решений, где $n$ - число неизвестных, а $r = Rg\ A$

Доказательство.

Предположим: базисный минор $M$ в верхнем левом углу матрицы $A$. Тогда строки $A_1, ..., A_r$ - базисные, а $A_{r + 1}, ..., A_n$ - их линейная комбинация по теореме о базисном миноре.

$\begin{cases} A_{r + 1} = \lambda_1 A_1 + ... + \lambda_r A_r \\ \dots \\ A_m = \mu_1 A_1 + ... + \mu_r A_r \end{cases}$

Сделаем $A_{r + 1} \rightarrow A_{r + 1} - \lambda_1 A_1 - ... - \lambda_r A_r$, ..., $A_m \rightarrow A_m - \mu_1 A_1 - ... - \mu_r A_r$

Получим матрицу, в которой после $m - r$ строк нулевые. Заметим, что элементы преобразования строк матрицы $A$ соостветственно эквивалентны элементарным преобразованиям уравнений исходной СЛАУ $Ax = 0 \Rightarrow Ax = 0$ эквивалентна $$\begin{cases}a_{11} x_1 + ... + a_{1\ r} x_r + a_{1\ r+ 1} x_{r + 1} + ... + a_{1\ n} x_n = 0 \\ \vdots \\ a_{r\ 1} x_1 + ... + a_{r\ r} x_r + a_{r\ r+1} x_{r + 1} + ... + a_{r\ n} x_n = 0 \end{cases}$$

Будем назыввать переменные, отвечающие базисным столбцам главными, а остальные - свободными.

$x_1, ..., x_r$ - главные (соответствуют БМ), их число $r = Rg\ A \\ x_{r + 1}, ..., x_n$ - свободные ($n - r$)

Выразим главные переменные через свободные в $$\begin{cases}a_{11} x_1 + ... + a_{1\ r} x_r = - a_{1\ r+ 1} x_{r + 1} - ... - a_{1\ n} x_n \\ \vdots \\ a_{r\ 1} x_1 + ... + a_{r\ r} x_r = - a_{r\ r+1} x_{r + 1} - ... - a_{r\ n} x_n\end{cases}$$

Присвоим свободным переменным следующие наборы значений.

Для каждого набора решений СЛАУ относительно $(x_1, ..., x_r)$ она всегда имеет решения, так как это СЛАУ с квадратной невырожденной матрицей (ее $\det M \neq 0$) (т. е., например, решения можно найти по формулам Крамера)

Получим следующие решения:

Столбцы $\begin{pmatrix}\phi_{1\ 1} \\ \vdots \\ \phi_{1\ r} \\ 1 \\ 0 \\ \vdots \\ 0\end{pmatrix}, \begin{pmatrix}\phi_{2\ 1} \\ \vdots \\ \phi_{2\ r} \\ 0 \\ 1 \\ \vdots \\ 0\end{pmatrix}, ..., \begin{pmatrix}\phi_{k\ 1} \\ \vdots \\ \phi_{k\ r} \\ 0 \\ 0 \\ \vdots \\ 1\end{pmatrix}$ являются решениями СЛАУ $\Rightarrow$ являются решениями исходной СЛАУ.

3. Сформулируйте и докажите критерий существования ненулевых решений однородной квадратной СЛАУ (как следствие теоремы о существовании ФСР).

Следствие. (критерий существования ненулевого решения однородной квадратной СЛАУ)

Пусть $A$ - квадратная матрица, тогда ОСЛАУ $Ax = 0$ имеет ненулевое решение $\Leftrightarrow \det A = 0$

Доказательство.

Необходимость

Дано: $Ax = 0$

Доказать: $\det A = 0$

Предположим: пусть $\det A \neq 0 \Rightarrow$ по формулам Крамера СЛАУ имеет единственное решение, но всегда есть нулевое решение $\Rightarrow$ других нет $\Rightarrow$ противоречие.

Достаточность

Дано: $\det A = 0$

Доказать: $\exists$ решения $x \neq 0$

Пусть $\det A = 0 \Rightarrow Rg A < n$. Пусть $Rg A = r$. По теореме о существования ФСР $\exists n - r > 0$ л. н. з. решений. Это и есть ненулевое решение (так как нулевой вектор линейно зависим).

4. Докажите теорему о структуре общего решения однородной системы линейных алгебраических уравнений, то есть о том, что произвольное решение однородной СЛАУ может быть представлено в виде линейной комбинации элементов ФСР.

Теорема.

Пусть $\phi_1, ..., \phi_k$ - ФСР ОСЛАУ $Ax = 0$. ($k = n - r$, где $r = Rg\ A, n -$ число неизвестных). Тогда любое решение этой ОСЛАУ можно представить в виде $x = c_1 \phi_1 + ... + c_k \phi_k$, где $c_1, ..., c_k$ - некоторые числа.

Доказательства.

Пусть $x^o = (x_1^0 \dots x^0_n)$ - произвольное решение ОСЛАУ $Ax = 0$. Покажем, что оно линейно выражается через ФСР. Предположим, что БМ матрицы $A$ расположен в левом верхнем углу. Тогда исходная СЛАУ эквивалентна системе: $${\color{green}\textcircled{1}} \begin{cases} a_{1\ 1} x_1 + ... + a_{1\ r} x_r = -a_{1\ r} x_{r+1} - ... - a_{1\ n} x_n \\ \dots \\ a_{r\ 1} + ... + a_{r\ r} x_r = - a_{r\ r + 1} x_{r + 1} - ... - a_{r\ r + 1} x_{r + 1} \end{cases}$$

Решим ${\color{green}\textcircled{1}}$ относительно главных переменных (методы Гаусса или Крамера)

Составим матрицу $\mathcal{D}$

Покажем, что $Rg\ \mathcal{D} = k$.

1. $Rg\ \mathcal{D} \geq k$, так как $\phi_1, ..., \phi_k$ - л.н.з. (по определению ФСР), а $Rg\ \mathcal{D} =$ максимальному л.н.з. столбцов (по т. о ранге матрицы)

2. Покажем, что $Rg\ \mathcal{D} \leq k$ Столбцы матрицы $\mathcal{D}: x_o, \phi_1, ..., \phi_k$ - решения СЛАУ $Ax = 0$. Из ${\color{green}\textcircled{2}}$ получим, что

То есть первая строка матрицы $\mathcal{D}$ является линейной комбинацией строк $\mathcal{D}_{r + 1}, ..., \mathcal{D}_n$

Таким образом, при помощи простейших операций:

То есть $Rg\ \mathcal{D} = Rg\ \mathcal{D}^{\text{'}} \leq k$

Мы доказали, что $\mathcal{D} = k \Rightarrow$ так как столбцы $\Phi_1, ..., \Phi_k$ - базисные (так как они л.н.з.) $\Rightarrow$ по теореме о БМ $x^0$ - их линейная комбинация, то есть

5. Сформулируйте теорему о структуре общего решения неоднородной системы линейных алгебраических уравнений и докажите её (теорема о структуре общего решения однородной системы линейных алгебраических уравнений предполагается известной).

Теорема.

Пусть известно частное решение $\widetilde{x}$ СЛАУ $Ax = b$. Тогда любое решение этой СЛАУ может быть представлено в виде: $$x = \widetilde{x} + c_1 \Phi_1 + ... + c_k \Phi_k$$

где $c_1, ..., c_k$ - некоторые постоянные, а $\Phi_1, ..., \Phi_k$ - ФРС соответствующей однородной системы $Ax = 0$.

Доказательство.

Пусть $x^0$ - произвольное решение СЛАУ $Ax = b \Rightarrow x^0 - \widetilde{x}$ - решение СЛАУ $Ax = 0$ (по свойствам решений СЛАУ).

К $x^0 - \widetilde{x}$ применим теорему о структуре общего решения ОСЛАУ: $$x^0 - \widetilde{x} = c_1 \Phi_1 + ... + c_k \Phi_k \Rightarrow x^0 = \widetilde{x} + c_1 \Phi_1 + ... + c_k \Phi_k$$

6. Докажите теорему о том, что любое линейное уравнение на координаты точки в трехмерном пространстве задает плоскость и что любая плоскость определяется линейным уравнением.

Теорема.

1. Любая плоскость в пространстве определяется уравнением $Ax + By + Cz + D = 0$, в котором $A, B, C, D$ - некоторые числа.

2. Любое уравнение $Ax + By + Cz + D = 0$, где $A^2 + B^2 + C^2 > 0$, определяет в пространстве плоскость.

Доказательство.

1. Рассмотрим плоскость $\pi$. пусть точка $M_0(x_0, y_0, z_0)$ ей принадлежит. Рассмотрим $\overrightarrow{n} \perp \pi$. Пусть $\overrightarrow{n} = (A, B, C)$. $$M(x, y, z) \in \pi \Leftrightarrow (\overrightarrow{n}, \overrightarrow{M_0 M}) = 0 \Leftrightarrow A(x_0 - x) + B(y_0 - y) + C(z_0 - z) = 0$$ Т.е. $Ax + By + Cz + D = 0$ , где $D = -Ax_0 -By_0 - Cz_0$. Таким образом, координаты точки $M$ удовлетворяют уравнению $Ax + By + Cz + D = 0$

2. Рассмотрим уравнение $Ax + By + Cz + D = 0$, где $A^2 + B^2 + C^2 > 0$. Оно имеет хотя бы одно рашение (например, если $A \neq 0$, то $x_0 = - \frac{D}{A}, y_0 = z_0 = 0$). Обозначим за $M_0$ точку $(x_0, y_0, z_0)$. Пусть точка $M(x, y, z)$ удовлетворяет уравнению $Ax + By + Cz + D = 0$. Вычтем из него равенство $Ax_0 + By_0 + Cz_0 + D = 0$: $$A(x_0 - x) + B(y_0 - y) + C(z_0 - z) = 0 \Leftrightarrow (\overrightarrow{n}, \overrightarrow{M_0 M}) = 0\text{, где } \overrightarrow{n} = (A, B, C)$$ $(\overrightarrow{n}, \overrightarrow{M_0 M}) = 0 \Leftrightarrow \overrightarrow{n} \perp \overrightarrow{M_0 M} \Leftrightarrow$ точка $M$ лежит в плоскости, проходящей через $M_0$ и перпендикулярной вектору $\overrightarrow{n} \Rightarrow$ уравнение $Ax + By + Cz + D = 0$ определяет плоскость.

Модуль 3

1. Сформулируйте и докажите утверждение о связи порядка элемента, порождающего циклическую группу, с порядком группы.

Утверждение.

Пусть $G$ – группа и $g \in G$. Тогда $|\langle g \rangle|$ = $ord(g)$

Доказательство.

Заметим, что если $\forall{k, s \in \N}\ g^k = g^s \Rightarrow g^{k−s} = e$ (т.к. $\exists g^{−1}$), то $ord\ g \leq k−s \Rightarrow$ если $g$ имеет бесконечный порядок, то все элементы $g^n, n \in \Z$ различны $\Rightarrow \langle g \rangle$ содержит бесконечного много элементов $\Rightarrow$ в бесконечном случае доказано.

Если же $ord(g) = m$, то из минимальности $m \in \N \Rightarrow e = g^0, g = g^n, ..., g^{m−1}$ попарно различны. Покажем, что $\langle g \rangle = \{e, g, g^2, ..., g^{m−1}\}$. Т.к. $\forall{n \in \Z}$ представимо в виде $n = qm + r$, где $0 \leq r < m$, $g^n = g^{qm+r} =(g^m)^q \cdot g^r = e^q \cdot g^r = g^r \Rightarrow \langle g \rangle = \{e, g, ..., g^{m−1}\}$ и $|\langle g \rangle| = m = ord(g)$.

2. Сформулируйте и докажите утверждение о том, какими могут быть подгруппы

группы целых чисел по сложению.

Утверждение.

Любая подгруппа в $(Z, +)$ имеет вид $kZ$ (числа, кратные $k$) для $k \in \N \cup \{0\}$.

Доказательство.

$kZ$ является подгруппой. Докажем, что других нет.

Если $H = \{0\}$ ($H$ – подгруппа, $0$ – нейтральный элемент), то положим, что $k = 0$. Иначе $k = min(H \cap \N)$ ($\neq \varnothing$, т.к. $H \neq \{0\}$). Тогда $kZ \subseteq H$.

Рассмотрим $a \in H$ и $a = qk+r, 0 \leq r < k$. Тогда $r= \underbrace{a}_{\in H} − \underbrace{qk}_{\in H} \in H \Rightarrow r = 0$ (так как $r < k = min(H \cap N)$). Получаем, что $a = qk \Rightarrow H \subseteq kZ$.

Доказана принадлежность в обе стороны: $kZ \subseteq H$ и $H \subseteq kZ$. Значит, $kZ = H$.

3. Сформулируйте и докажите теорему Лагранжа (включая две леммы).

Лемма.

Левые смежные классы $G$ по подгруппе $H$ либо не пересекаются, либо совпадают:

Доказательство.

Докажем, что если классы пересекаются, то они совпадают. Если $g_1H \cap g_2H \neq \varnothing$, то $\exists{h_1, h_2 \in H}: g_1 \cdot h_1 = g_2 \cdot h_2 \Rightarrow g_1 = g_2 \cdot \underbrace{h_2 \cdot h_1^{-1}}_{\in H} \Rightarrow g_1 H = g_2 \underbrace{h_2 h_1^{-1} H}_{\text{лежит в } H} \subseteq g_2 H \Rightarrow g_1 H \subseteq g_2 H$. Аналогично есть обратное включение.