#import "../conf.typ": *

= Общее решение системы линейных алгебраических уравнений. <NAME>-Капелли.
== Общее решение системы линейных алгебраических уравнений
#definition[
  *Группой* называется множество $G$ с определённой на нём бинарной операцией
  умножения $dot: G times G -> G$, удовлетворяющей следующим условиям:
  - (Ассоциативность)
    #eq[
      $forall a, b, c in G : space (a b) c = a (b c)$
    ]
  - (Существование нейтрального элемента)
    #eq[
      $exists e in G : forall a in G : space a e = e a = a$
    ]
  - (Существование нейтрального элемента)
    #eq[
      $forall a in G : exists a^(-1) in G : space a a^(-1) = a^(-1)a = e$
    ]
]

#definition[
  Группа $(G, dot)$ называется *абелевой*, если умножение в ней коммутативно, то
  есть
  #eq[
    $forall a, b in G : space a b = b a$
  ]
]

#definition[
  *Кольцом* называется множество $R$ с определёнными на нём бинарными операциями
  сложения $+: R times R -> R$ и умножения $dot: R times R -> R$, удовлетворяющая
  следующим условиям:
  - $(R, +)$ -- абелева группа, нейтральный элемент в которой обозначается через $0$.
  - (Ассоциативность умножения)
    #eq[
      $forall a, b, c in R : space (a b) c = a(b c)$
    ]
  - (Дистрибутивность умножения относительно сложения)
    #eq[
      $forall a, b, c in R : space a(b + c) = a b + a c and (a + b)c = a c + b c$
    ]
  - (Существование нейтрального элемента относительно умножения)
    #eq[
      $exists 1 in R : forall a in R : space a 1 = 1 a = a$
    ]
]

#definition[
  Кольцо $(R, +)$ называется *коммутативным*, если умножение в нём коммутативно,
  то есть
  #eq[
    $forall a, b in R : space a b = b a$
  ]
]

#definition[
  Пусть $(R, +, dot)$ -- кольцо.

  Элемент $a in R$ называется *обратимым*, если
  #eq[
    $exists a^(-1) in R : space a a^(-1) = a^(-1)a = 1$
  ]
  *Группой обратимых элементов* кольца $(R, +, dot)$ называется множество $R^*$ его
  обратимых элементов.
]

#definition[
  *Полем* называется такое коммутативное кольцо $(FF, +, dot)$, для которого
  выполнено равенство $FF^* = FF without {0}$.
]

#definition[
  *Линейным пространством*, или *векторным пространством* над полем $FF$ называется
  абелева группа $(V, +)$, на которой определено умножение на элементы поля $dot: FF times V -> V$,
  удовлетворяющее следующим условиям:
  - $forall alpha, beta in FF : forall v in V : space (alpha + beta)v = alpha v + beta v$
  - $forall alpha in FF : forall u,v in V : space alpha(u + v) = alpha u + alpha v$
  - $forall alpha, beta in FF : forall v in V : space (alpha beta)v = alpha(beta v)$
  - $forall v in V : space 1 v = v$
  Элементы поля $FF$ называются *скалярами*, элементы группы $V$ -- *векторами*.
]

#definition[
  Пусть $A = (a_(i j)) in M_(k times n)(FF); b = (b_i) in FF^n$.

  *Системой линейных уравнений* $A x = b$ называется следующая система:
  #eq[
    $cases(
      a_(1 1) x_1 + a_(1 2) x_2 + ... + a_(1 n) x_n = b_1,
      a_(2 1) x_1 + a_(2 2) x_2 + ... + a_(2 n) x_n = b_2,
      ..., a_(k 1) x_1 + a_(k 2) x_2 + ... + a_(k n) x_n = b_k,

    )$
  ]
  Матрица $A$ называется *матрицей системы*, матрица $(A | b)$ -- *расширенной матрицей системы*
]

#definition[
  Система линейных уравнений $A x = b$ называется:
  - *Однородной*, если $b = 0$
  - *Совместной*, если множество её решений непусто
]

#definition[
  *Фундаментальной системой решений* однородной системы $A x = 0$ называется базис
  пространства её решений.

  Матрица, образованная столбцами фундаментальной системы решений, называется
  *фундаментальной матрицей системы* и обозначается через $Phi$.
]

#proposition[
  Множество решений однородной системы $A x = 0$ является линейным пространством.
]

#proof[
  Все требования линейного пространства очевидны.
]

#proposition[
  Пусть $A x = b$ -- совместная система, $x_0 in FF^n$ -- решение системы, $V$ -- пространство
  решений однородной системы $A x = 0$.

  Тогда множество решений системы $A x = b$ имеет вид
  #eq[
    $x_0 + V = {x_0 + v | v in V}$
  ]
]

#proof[
  Пусть $U$ -- множество решений системы $A x = b$.
  - Если $v in V$, то $A(x_0 + v) = A x_0 + A v = b => x_0 + v in U$.
  - Если $u in U$, то $A(u - x_0) = 0 => u - x_0 in V$
  Таким образом, $U = x_0 + V$
]

== Теорема Кронекера-Капелли
#definition[
  Системы $A x = b$ и $A' x = b'$ называются *эквивалентными*, если множества их
  решений совпадают.
]

#definition[
  *Элементарными преобразованиями* строк матрицы $A in M_(n times k)(FF)$ называются
  следующие операции:
  - Прибавление к $i$-й строке $j$-й строки, умноженной на скаляр $alpha in FF; quad i, j in overline("1,n"); i != j$
  - Умножение $i$-й строки на скаляр $lambda in FF^*; i = overline("1, n")$
  - Перестановка $i$-й и $j$-й строк местами; $i, j in overline("1, n"); i != j$
]

#definition[
  *Элементарными матрицами* порядка $n in NN$ называются матрицы, умножение слева
  на которые приводит к осуществлению соответствующего элементарного
  преобразования строк над матрицей с $n$ строками:
  - $D_(i j)(alpha) := E + alpha E_(i, j); quad i,j in overline("1,n"); i != j$
  - $T_i(lambda) := E + (lambda - 1)E_(i i); quad i in overline("1,n")$
  - $P_(i j) := E - (E_(i i) + E_(j j)) + (E_(i j) + E_(j i))$
]

#definition[
  Матрица $A in M_n (FF)$ называется *обратимой*, если существует матрица $A^(-1) in M_n (FF)$ такая,
  что $A A^(-1) = A^(-1) A = E$.
]

#proposition[
  Элементарные матрицы любого порядка $n$ обратимы
]

#proof[
  Предъявим обратные матрицы в явном виде:
  - $(D_(i j)(alpha))^(-1) = D_(j i) (-alpha)$
  - $(T_i (lambda))^(-1) = T_i (lambda^(-1))$
  - $(P_(i j))^(-1) = P_(i j)$
]

#proposition[
  Элементарные преобразования строк расширенной матрицы переводят её в
  эквивалентную.
]

#definition[
  *Главным элементом* строки называется её первый ненулевой элемент.
]

#definition[
  Матрица $A in M_(n times k)(FF)$ имеет *ступенчатый вид*, если номера главных
  элементов её строк строго возрастают.

  При этом если в матрице есть нулевые строки, то они расположены внизу матрицы.
]

#theorem(
  "Метод Гаусса",
)[
  Любую матрицу $A in M_(n times k)(FF)$ элементарными преобразованиями можно
  привести к ступенчатому виду
]

#proof[
  Предъявим алгоритм:
  + Если $A = 0$, то она уже имеет ступенчатый вид, завершаем процедуру.
  + Пусть $j in overline("1, k")$ -- наименьший номер ненулевого столбца. Переставим
    строки так, чтобы $a_(1 j)$ стал ненулевым.
  + Для всех $i in overline("2, n")$ к $i$-й строке прибавим первую, умноженную на $-a_(i j)(a_(1 j))^(-1)$.
    Тогда все элементы $a_(2 j), ..., a_(n j)$ станут нулевыми
  + Пусть матрица была приведена к виду $A'$. Если она ступенчатая, то
    останавливаемся. Если она не ступенчатая, то начинаем заново для подматрицы $B$ расположенной
    на пересечении строк с номерами $overline("2,n")$ и столбцом с номерами $(overline("j+1,k"))$.
    Дальнейшие преобразования не изменят элементов за пределами этой подматрицы.
]

#definition[
  Пусть $V$ -- конечномерное линейное пространство, $X subset V$.

  *Рангом* системы $X$ называется наибольший размер линейно независимой подсистемы
  в $X$.

  Обозначение -- $"rk" X$.
]

#definition[
  Пусть $A in M_(n times k)(FF)$
  - *Строчным рангом* матрицы $A$ называется ранг $"rk"_r A$ системы её строк.
  - *Столбцовым рангом* матрицы $A$ называется ранг $"rk"_c A$ системы её столбцов.
]

#theorem[
  Для любой матрицы $A in M_(n times k)(FF)$ выполнено следующее равенство:
  #eq[
    $"rk"_r A = "rk"_c A$
  ]
]

#definition[
  *Рангом матрицы* $A in M_(n times k)(FF)$ называется её строчный или столбцовый
  ранг.

  Обозначение -- $"rk" A$.
]

#proposition[
  Пусть $A in M_(n times k)(FF); B in M_(k times M) (FF)$, причём столбцы матрицы $A$ линейно
  независимы. Тогда
  #eq[
    $"rk" A B = "rk" B$
  ]
]

#note[
  В том числе, элементарные преобразования не меняют ранг матрицы.
]

#proposition[
  Ранг ступенчатой матрицы $A in M_(n times k)(FF)$ равен числу ступеней.
]

#theorem("Кронекера-Капелли")[
  #eq[
    $"Система" A x = b "совместна" <=> "rk" A = "rk" (A | b)$
  ]
]

#proof[
  Приведём расширенную матрицу системы $(A | b)$ к упрощённому виду $(A' | b')$.

  Тогда система совместна $<=>$ в $(A' | b')$ нет ступеньки, начинающейся в
  столбце $b' <=>$ у $A'$ и $(A' | b')$ одно и то же число ступенек $<=>$ $"rk" A = "rk" (A | b)$.
]
