LinearAlgebra.tex

\setchapterpreamble[u]{\margintoc}
\chapter{Некоторые понятия линейной алгебры}
\label{chpt:LinAlIntro}
\tikzsetfigurename{LinearAlgebra_}

При изложении ряда алгоритмов будут активно использоваться некоторые понятия и инструменты линейной алгебры, такие как моноид, полукольцо или матрица.
В данном разделе необходимые понятия будут определены и приведены некоторые примеры соответствующих конструкций.
Для более глубокого изучения материала рекомендуются обратиться к соответствующим разделам алгебры.
\marginnote[*6]{
    Неообходимо понимать, что, с одной строны, в данном разделе рассматриваются самые базовые понятия, которые даются практически в любом учебнике алгебры.
    С другой же стороны, определения данных понятий оказываются весьма вариативными и часто вызывают дискуссии.
    Например, интересный анализ тонкостей определения группы можно найти в первом и втором параграфах первого раздела книги Николая Александровича Вавилова \enquote{Конкретная теория групп}~\cite{VavilovGroups}.
    Мы же дадим определения, удобные для дальнейшего изложения материала.
}

\section{Бинарные операции и их свойства}

Введём понятие \emph{бинарной операции} и рассмотрим некоторые её свойства, такие как \emph{коммутативность} и \emph{ассоциативность}.

\begin{definition}[Функция]
    \emph{Функцией} будем называть бинарное отношение на двух множествах $S$ и $T$, такое, что каждому элементу из $S$ сопоставляется ровно один элемент из $T$.
    Запись $f: S \to T$ как раз и обозначает, что функция $f$ сопоставляет элементы из $S$ элементам из $T$.
\end{definition}

\begin{definition}[Домен функции]
    Для функции $f: S \to T$, множество $S$ называется \emph{областью определения функции} или \emph{доменом функции}.
\end{definition}

\begin{definition}[Кодомен функции]
    Для функции $f: S \to T$, множество $T$ называется \emph{областью значений функции} или \emph{кодоменом функции}.
\end{definition}

\begin{definition}[Двухместная функция]
    Функцию, принимающую два аргумента, $f: R \times S \to T$ будем называть \emph{двухместной} или \emph{функцией арности два}.
    Для записи таких функций будем использовать типичную нотацию: $t = f(r, s)$.
\end{definition}

\begin{definition}[Бинарная операция]
    \emph{Бинарная операция}~--- это двухместная функция, от которой дополнительно требуется, чтобы оба аргумента и результат лежали в одном и том же множестве: $f: S \times S \to S$.
    В таком случае говорят, что бинарная операция определена на некотором множестве $S$. Для обозначения произвольной бинарной операции будем использовать символ $\circ$ и пользоваться инфиксной нотацией для записи: $s_3 = s_1 \circ s_2$.
\end{definition}

\begin{definition}[Внешняя бинарная операция]
    \emph{Внешняя бинарная операция}~--- это бинарная операция, у которой аргументы лежат в разных множествах, при этом результат~--- в одном из этих множеств.
    Иными словами $\circ: R \times S \to S$, где $R$ может не совпадать с $S$~--- внешняя бинарная операция.
\end{definition}

Необходимо помнить, что как функции, так и бинарные операции, могут быть частично определёнными (частичные функции, частичные бинарные операции).
Типичным примером частично определённой бинарной операции является деление на целых числах: она не определена, если второй аргумент равен нулю.

Бинарные операции могут обладать некоторыми дополнительными свойствами, такими как \emph{коммутативность} или \emph{ассоциативность}, позволяющими преобразовывать выражения, составленные с использованием этих операций.

\begin{definition}[Коммутативная операция]
    Бинарная операция $\circ : S \times S \to S$ называется \emph{коммутативной}, если для любых  $s_1, s_2 \in S$ верно, что  $s_1 \circ s_2 = s_2 \circ s_1$.
\end{definition}

\begin{example}
    Рассмотрим несколько примеров коммутативных и некоммутативных операций.
    \begin{itemize}
        \item Операция сложения на целых числах является коммутативной: известный ещё со школы перестановочный закон сложения.
        \item Операция умножения на целых числах является коммутативной: известный ещё со школы перестановочный закон умножения.
        \item Операция конкатенации на строках\sidenote{Хотя в языках программирования традиционно строки принято <<складывать>>, использование $\cdot$ позволяет нам естественнвм образом пользоваться математической традицией опускать знак умножения в символьных записях.} $\cdot$ не является коммутативной:
              \["ab" \cdot "c"  = "abc" \neq "cab" = "c" \cdot "ab".\]
        \item Операция умножения матриц (над целыми числами) $\cdot$ не является коммутативной:
              \[\begin{pmatrix}
                      1 & 1 \\
                      0 & 0
                  \end{pmatrix}
                  \cdot
                  \begin{pmatrix}
                      0 & 0 \\
                      1 & 1
                  \end{pmatrix}
                  =
                  \begin{pmatrix}
                      1 & 1 \\
                      0 & 0
                  \end{pmatrix}
                  \neq
                  \begin{pmatrix}
                      0 & 0 \\
                      1 & 1
                  \end{pmatrix}
                  =
                  \begin{pmatrix}
                      0 & 0 \\
                      1 & 1
                  \end{pmatrix}
                  \cdot
                  \begin{pmatrix}
                      1 & 1 \\
                      0 & 0
                  \end{pmatrix}
                  .\]
    \end{itemize}
\end{example}

\begin{definition}[Ассоциативная бинарная операция]
    Бинарная операция $\circ: S \times S \to S$ называется \emph{ассоциативной}, если для любых  $s_1, s_2, s_3 \in S$ верно, что  $(s_1 \circ s_2) \circ s_3 = s_1 \circ (s_2 \circ s_3)$.
    Иными словами, для ассоциативной операции результат вычислений не зависит от порядка применения операций.
\end{definition}

\begin{example} Рассмотрим несколько примеров ассоциативных и неассоциативных операций.
    \begin{itemize}
        \item Операция сложения на целых числах является ассоциативной.
        \item Операция умножения на целых числах является ассоциативной.
        \item Операция конкатенации на строках $\cdot$ является ассоциативной:
              \[("a" \cdot "b") \cdot "c"  = "a" \cdot ("b" \cdot "c") = "abc".\]
        \item Операция возведения в степень (над целыми числами) $\hat{\mkern6mu}$ не является ассоциативной:
              \[(2\hat{\mkern6mu}2)\hat{\mkern6mu}3 = 4 \hat{\mkern6mu} 3 = 64 \neq 256 = 2 \hat{\mkern6mu} 8 = 2\hat{\mkern6mu}(2\hat{\mkern6mu}3).\]
    \end{itemize}
\end{example}

\begin{definition}[Дистрибутивная бинарная операция]
    Говорят, что бинарная операция $\otimes: S \times S \to S$ является \emph{дистрибутивной} относительно бинарной операции $\oplus: S \times S \to S$, если
    \begin{enumerate}
        \item Для любых $s_1, s_2, s_3 \in S$, $s_1 \otimes (s_2 \oplus s_3) = (s_1 \otimes s_2) \oplus (s_1 \otimes s_3)$ (дистрибутивность слева).
        \item Для любых $s_1, s_2 ,s_3 \in S$, $(s_2 \oplus s_3) \otimes s_1 = (s_2 \otimes s_1) \oplus (s_3 \otimes s_1)$ (дистрибутивность справа).
    \end{enumerate}
    Если операция $\otimes$ является коммутативной, то дистрибутивность слева и справа равносильны.
\end{definition}

\begin{example}
    Рассмотрим несколько примеров дистрибутивных операций.
    \begin{itemize}
        \item Умножение целых чисел дистрибутивно относительно сложения и вычитания: классический \emph{распределительный закон}, знакомый всем со школы.
        \item Операция деления (допустим, на действительных числах) не коммутативна.
              При этом, она дистрибутивна справа относительно сложения и вычитания, но не дистрибутивна слева%
              \sidenote{
                  Здесь может быть уместно вспомнить правила сложения дробей.
                  Дроби с общим знаминателем складывать проще как раз из-за дистрибутивности справа.}.
              Так, $(a + b) / c = (a / c) + (b / c)$, но $c / (a + b) \neq (c / a) + (c / b)$.
    \end{itemize}
\end{example}

\begin{definition}[Идемпотентная бинарная операция]
    Бинарная операция $\circ: S \times S \to S$ называется \emph{идемпотентной}, если для любого  $s \in S$ верно, что  $s \circ s = s$.
\end{definition}

\begin{example}
    Рассмотрим несколько примеров идемпотентных операций.
    \begin{itemize}
        \item Операция объединения множеств $\cup$ является идемпотентной: для любого множества $S$ верно, что $S \cup S = S$.
        \item Операция сложения на целых числах не является идемпотентной.
        \item Операции \enquote{логическое и} $\land$ и \enquote{логическое или} $\lor$ являются идемпотентными.
        \item Операция \enquote{исключающее или} (\textsf{XOR}) не является идемпотентной.
    \end{itemize}
\end{example}

\begin{definition}[Нейтральный элемент]
    Пусть есть коммутативная бинарная операция $\circ$ на множестве $S$.
    Говорят, что $e \in S$ является \emph{нейтральным элементом} по операции $\circ$, если для любого $s \in S$ верно, что $e \circ s = s \circ e = s$.
    Если бинарная операция не является коммутативной, то можно определить \emph{нейтральный слева} и \emph{нейтральный справа} элементы по аналогии.
\end{definition}

\section{Полугруппа}

\begin{definition}[Полугруппа]
    Множество $S$ с заданной на нём ассоциативной бинарной операцией $\cdot: S \times S \to S$ называется \emph{полугруппой} и обозначается $(S, \cdot)$.
    Если операция $\cdot$ является коммутативной, то говорят о \emph{коммутативной полугруппе}.
\end{definition}

\begin{example}
    Приведём несколько примеров полугрупп.
    \begin{itemize}
        \item Множество положительных целых чисел с операцией сложения является коммутативной полугруппой.
        \item Множество целых чисел с операцией взятия наибольшего из двух ($\max$) является коммутативной полугруппой.
        \item Множество всех строк конечной длины без пустой строки%
              \sidenote{
                  Множество всех строк конечной длины c пустой строкой также является полугруппой.
                  Однако, такая структура является ещё и моноидом, что будет показано далее.}
              над фиксированным алфавитом $\Sigma$ с операцией конкатенации является полугруппой.
              Так как конкатенация на строках не является коммутативной операцией, то и полугруппа не является коммутативной.
    \end{itemize}
\end{example}

\section{Моноид}

\begin{definition}[Моноид]
    \emph{Моноидом} называется полугруппа с нейтральным элементом.
    Если операция является коммутативной, то можно говорить о \emph{коммутативном моноиде}.
\end{definition}

\begin{example}
    Приведём примеры моноидов, построенных на основе полугрупп из предыдущего раздела.
    \begin{itemize}
        \item Неотрицательные целые числа (или же натуральные числа с нулём) с операцией сложения являются моноидом.
              Нейтральный элемент~--- $0$.
        \item Целые числа, дополненные значением $-\infty$ (\enquote{минус бесконечность}) с операцией взятия наибольшего из двух ($\max$) являются моноидом.
              Нейтральный элемент~--- $-\infty$.
        \item Множество всех строк конечной длины с пустой строкой (строка длины 0) над фиксированным алфавитом $\Sigma$ и операцией конкатенации является моноидом.
              Нейтральный элемент~--- пустая строка.
        \item Квадратные неотрицательные матрицы%
              \sidenote{Неотрицательной называется матрица, все элементы которой не меньше нуля.} фиксированного размера с операцией умножения задают моноид.
              Нейтральный элемент~--- единичная матрица.
    \end{itemize}
\end{example}

\section{Группа}

\begin{definition}[Группа]
    Непустое%
    \sidenote{Требование непустоты здесь, как и далее, в определениях полукольца и кольца~--- дискуссионный вопрос.}
    множество $G$ с заданной на нём бинарной операцией $\circ: {G} \times {G} \to {G}$ называется \emph{группой} $(G ,\circ)$, если выполнены следующие аксиомы:
    \begin{enumerate}
        \item ассоциативность: для любых $a, b, c \in G$ выполнено $(a \circ b) \circ c = a \circ (b \circ c)$;
        \item наличие нейтрального элемента $e$: для любого $a \in G$ выполнено $e \circ a = a \circ e = a$;
        \item наличие обратного элемента: для любого $a \in G$ существует $a^{-1} \in G$, такой что $a \circ a^{-1} = a^{-1} \circ a = e$.
    \end{enumerate}
    Иными словами, группа~--- это моноид с дополнительным требованием наличия обратных элементов.
\end{definition}

\begin{definition}[Абелева группа]
    Если операция $\circ$ коммутативна, то говорят, что группа \emph{абелева}.
\end{definition}

\begin{example}
    Рассмотрим несколько примеров групп.
    \begin{itemize}
        \item Целые числа $\BbbZ$ с операцией сложения $+$ являются группой.
              Получается дополнением моноида из предыдущего раздела обратными по сложению элементами.
        \item Целые числа $\BbbZ$ без нуля%
              \sidenote{
                  При наличии нуля возникают трудности с нейтральным элементом.
                  Логично считать $1$ нейтральным по умножению, однако $0 \cdot 1 = 0$, а не 1, как того требует определение.}
              с операцией умножения $\cdot$ не являются группой, так как нет обратных по умножению.
              Действительно, возьмём $a = 3$, тогда должен существовать $a^{-1} \in \BbbZ$, такой что $3 \cdot a^{-1} = 1$.
              Видим, что $a^{-1} = 1/3$, но $1/3 \notin \BbbZ$.
        \item Множество обратимых%
              \sidenote{
                  Квадратная матрица $M$ называется обратимой, если существует матрица $N$, называемая обратной, такая что $M \cdot N = N \cdot M = I$, где $I$~--- единичная матрица.
                  К сожалению, не все матрицы являются обратимыми, потому, чтобы сконструировать группу, нам приходится требовать обратимость явно.}
              матриц с операцией матричного умножения задают группу.
    \end{itemize}
\end{example}

\section{Полукольцо}

\begin{definition}[Полукольцо]
    Непустое множество $R$ с двумя бинарными операциями $\oplus: R \times R \to R$ (часто называют сложением) и $\otimes: R \times R \to R$ (часто называют умножением) называется \emph{полукольцом}, если выполнены следующие условия.
    \begin{enumerate}
        \item $(R, \oplus)$~--- это коммутативный моноид, нейтральный элемент которого~--- $\Bbbzero$. Для любых $a, b, c \in R$:
              \begin{itemize}
                  \item $(a \oplus b) \oplus c = a \oplus (b \oplus c)$
                  \item $\Bbbzero \oplus a = a \oplus \Bbbzero = a$
                  \item $a \oplus b = b \oplus a$
              \end{itemize}
        \item $(R, \otimes)$~--- это моноид, нейтральный элемент которого~--- $\Bbbzero$. Для любых $a, b, c \in R$:
              \begin{itemize}
                  \item $(a \otimes b) \otimes c = a \otimes (b \otimes c)$
                  \item $\Bbbzero \otimes a = a \otimes \Bbbzero = a$
              \end{itemize}
        \item $\otimes$ дистрибутивно слева и справа относительно $\oplus$:
              \begin{itemize}
                  \item $a \otimes (b \oplus c) = (a \otimes b) \oplus (a \otimes c)$
                  \item $(a \oplus b) \otimes c = (a \otimes c) \oplus (b \otimes c)$
              \end{itemize}
        \item $\Bbbzero$ является \emph{аннигилятором} по умножению:
              \begin{itemize}
                  \item для любых $a \in R$ выполнено $\Bbbzero \otimes a = a \otimes \Bbbzero = \Bbbzero$
              \end{itemize}
    \end{enumerate}
    Если операция $\otimes$ коммутативна, то говорят о \emph{коммутативном полукольце}.
    Если операция $\oplus$ идемпотентна, то говорят об \emph{идемпотентном полукольце}.
\end{definition}

\begin{example}
    \label{exmpl:semiring}
    Рассмотрим пример полукольца, а заодно покажем, что левая и правая дистрибутивность могут существовать независимо для некоммутативного умножения%
    \sidenote{
        Хороший пример того, почему левую и правую дистрибутивность в случае некоммутативного умножения нужно проверять независимо (правда, для колец), приведён Николаем Александровичем Вавиловым в книге \enquote{Конкретная теория колец} на странице 6~\cite{VavilovRings}.}%
    .

    В качестве $R$ возьмём множество множеств строк конечной длины над некоторым алфавитом $\Sigma$.
    В качестве сложения возьмём теоретико-множественное объединение: $\oplus \equiv \cup$.
    Нейтральный элемент по сложению~--- это пустое множество ($\varnothing$).
    В качестве умножения возьмём конкатенацию множеств ($\otimes \equiv \odot$) и определим её следующим образом:
    \[S_1 \odot S_2 = \left\{ w_1 \cdot w_2 \mid w_1 \in S_1, w_2 \in S_2\right\},\]
    где $\cdot$~--- конкатенация строк.
    Нейтральным элементом по умножению будет являться множество из пустой строки: $\{\varepsilon\}$, где $\varepsilon$~--- обозначение для пустой строки.

    Проверим, что $(R, \cup, \odot)$ действительно полукольцо по нашему определению.
    \begin{enumerate}
        \item $(R, \cup)$~--- действительно коммутативный моноид с нейтральным элементом $\varnothing$.
              Для любых $a, b, c \in R$ по свойствам теоретико-множественного объединения верно:
              \begin{itemize}
                  \item $(a \cup b) \cup c = a \cup (b \cup c)$
                  \item $\varnothing \cup a = a \cup \varnothing = a$
                  \item $a \cup b = b \cup a$.
              \end{itemize}
        \item $(R, \odot)$~--- действительно моноид с нейтральным элементом $\{\varepsilon\}$.
              Для любых $a, b, c \in R$:
              \begin{itemize}
                  \item $(a \odot b) \odot c = a \odot (b \odot c)$ по определению $\odot$
                  \item $\{\varepsilon\} \odot a = \{\varepsilon \cdot w \mid w \in a \} = \{w \mid w \in a \} = a \odot \{\varepsilon\} = a$
              \end{itemize}
              Вообще говоря, сконструированный нами моноид не является коммутативным: легко проверить, например, что существуют непустые $a, b \in R$, $a \neq b$, $a \neq \{\varepsilon\}$, $b \neq \{\varepsilon\}$, такие что $a \cdot b \neq b \cdot a$ по причине некоммутативности конкатенации строк.
        \item $\odot$ дистрибутивно слева и справа относительно $\cup$:
              \begin{itemize}
                  \item Сначала проверим дистрибутивность слева.
                        \begin{align*}
                            a \odot (b \cup c) & = \{ w_1 \cdot w_2 \mid  w_1 \in a, w_2 \in b \cup c\}                                                \\
                                               & = \{ w_1 \cdot w_2 \mid  w_1 \in a, w_2 \in b \} \cup  \{ w_1 \cdot w_2 \mid  w_1 \in a, w_2 \in c \} \\
                                               & =  (a \odot b) \cup (a \odot c)
                        \end{align*}
                  \item Аналогично, $(a \cup b) \odot c = (a \odot c) \cup (b \odot c)$
              \end{itemize}
              При этом, в общем случае, $a \odot (b \cup c) \neq (b \cup c) \odot a$ из-за некоммутативности операции $\odot$.
              Действительно,
              \begin{gather*}
                  \{"a"\} \odot (\{"b"\} \cup \{"c"\}) = \{"a"\} \odot \{"b","c" \} = \{"ab","ac" \} \\
                  (\{"b"\} \cup \{"c"\}) \odot \{"a"\} =  \{"b", "c"\} \odot \{"a"\} = \{"ba","ca"\} \\
                  \{"ab","ac"\} \neq \{"ba","ca"\}
              \end{gather*}
        \item $\varnothing$ является \emph{аннигилятором} по умножению: для любого $a \in R$ верно, что
              $\varnothing \odot a =  \{ w_1 \cdot w_2 \mid w_1 \in \varnothing, w_2 \in a \} =  \{ w_1 \cdot w_2 \mid w_1 \in a, w_2 \in \varnothing \} = a \odot \varnothing = \varnothing$
    \end{enumerate}
\end{example}

\section{Кольцо}

\begin{definition}[Кольцо]
    Непустое множество $R$ с двумя бинарными операциями $\oplus: R \times R \to R$ (сложение) и $\otimes: R \times R \to R$ (умножение) называется \emph{кольцом}, если выполнены следующие условия.
    \begin{enumerate}
        \item $(R, \oplus)$~--- это абелева группа, нейтральный элемент которой~--- $\Bbbzero$.
              Для любых $a, b, c \in R$:
              \begin{itemize}
                  \item $(a \oplus b) \oplus c = a \oplus (b \oplus c)$
                  \item $\Bbbzero \oplus a = a \oplus \Bbbzero = a$
                  \item $a \oplus b = b \oplus a$
                  \item для любого $a \in R$ существует $-a \in  R$, такой что $a + (-a) = \Bbbzero$.
              \end{itemize}
              В последнем пункте кроется отличие от полукольца.
              \item $(R, \otimes)$~--- это моноид, нейтральный элемент которого~--- 1.
              Для любых $a, b, c \in R$:
              \begin{itemize}
                  \item $(a \otimes b) \otimes c = a \otimes (b \otimes c)$
                  \item $1 \otimes a = a \otimes 1 = a$
              \end{itemize}
        \item $\otimes$ дистрибутивно слева и справа относительно $\oplus$:
              \begin{itemize}
                  \item $a \otimes (b \oplus c) = (a \otimes b) \oplus (a \otimes c)$
                  \item $(a \oplus b) \otimes c = (a \otimes c) \oplus (b \otimes c)$
              \end{itemize}
    \end{enumerate}
\end{definition}

Заметим, что мультипликативное свойство $\Bbbzero$ (быть аннигилятором по умножению) не указыватеся явно, так как может быть выведено из остальных утверждений.
Действительно,
\begin{enumerate}
    \item $a \otimes \Bbbzero = a \otimes (\Bbbzero \oplus \Bbbzero)$, так как $\Bbbzero$~--- нейтральный по сложению, то $\Bbbzero \oplus \Bbbzero = \Bbbzero$
    \item Воспользуемся дистрибутивностью: $a \otimes (\Bbbzero \oplus \Bbbzero) = a \otimes \Bbbzero \oplus a \otimes \Bbbzero$.
          В итоге: $a \otimes \Bbbzero = a \otimes \Bbbzero \oplus a \otimes \Bbbzero$
    \item Так как у нас есть группа по сложению, то для любого $a$ существует обратный элемент $a^{-1}$, $a \oplus a^{-1} = \Bbbzero$.
          Прибавим $a^{-1} \otimes \Bbbzero$ к левой и правой части равенства%
          \sidenote{Обычно данное действие воспринимается как очевидное, но, строго говоря, оно требует аккуратного введения структур с равенством и соответствующих аксиом.}%
          , полученного на предыдущем шаге:
          \[a \otimes \Bbbzero \oplus a^{-1} \otimes \Bbbzero = a \otimes \Bbbzero \oplus a \otimes \Bbbzero \oplus a^{-1} \otimes \Bbbzero.\]
    \item Воспользуемся дистрибутивностью и ассоциативностью.
          \begin{align*}
              (a \oplus a^{-1}) \otimes \Bbbzero & = a \otimes \Bbbzero \oplus (a  \oplus a^{-1}) \otimes \Bbbzero \\
              \Bbbzero \otimes \Bbbzero          & = a \otimes \Bbbzero \oplus \Bbbzero \otimes \Bbbzero           \\
              \Bbbzero                           & = a \otimes \Bbbzero
          \end{align*}
    \item Аналогично можно доказать, что $\Bbbzero = \Bbbzero \otimes a$.
\end{enumerate}

%\section{Поле}

\section{Матрицы и вектора}

К определению матрицы мы подойдём структурно, так как в дальнейшем будем сопоставлять эту структуру с объектами различной природы, а значит определение матрицы через какой-либо из этих объектов (например через квадратичные формы) будет менее удобным.

Договоримся, что \emph{алгебраическая структура}~--- это собирательное название для объектов вида \enquote{множество с набором операций} (например, кольцо, моноид, группа и т.д.), а соответствующее множество будем назвать \emph{носителем} этой структуры.

\begin{definition}[Матрица]
    Предположим, что у нас есть некоторая алгебраическая структура с носителем $S$. Тогда \emph{матрицей} будем называть прямоугольный массив размера $n \times m$, $n > 0$, $m > 0$, заполненный элементами из $S$.

    Говорят, что $n$~--- это высота матрицы или количество строк в ней, а $m$~--- ширина матрицы или количество столбцов.
\end{definition}

При доступе к элементам матрицы используются их индексы.
При этом нумерация ведётся с левого верхнего угла, первым указывается строка, вторым~--- столбец.
В нашей работе мы будем использовать \enquote{программистскую} традицию и нумеровать строки и столбцы с нуля%
\sidenote{
    В противоположность \enquote{математической} традиции нумеровать строки и столбцы с единицы.
    Стоит, правда, отметить, что в некоторых языках программирования (например, Fortran или COBOL) жива \enquote{математическая} традиция.}%
.

\begin{example}
    Пусть есть моноид $(S, \cdot)$, где $S$~--- множество строк конечной длины над алфавитом $\{a, b, c\}$.
    Тогда можно построить, например, следующую матрицу $2 \times 3$.
    \[
        M_{2 \times 3} =
        \begin{pmatrix}
            "a"  & "ba"  & "cb" \\
            "ac" & "bab" & "b"
        \end{pmatrix}
    \]
    Для доступа к элементу матрицы будем использовать такую запись: $M_{2 \times 3}[1, 1] = "bab"$.
\end{example}

К определению вектора мы также подойдём структурно.
\begin{definition}[Вектор]
    \emph{Вектором} будем называть матрицу, хотя бы один из размеров которой равен единице.
    Если единице равна высота матрицы, то это \emph{вектор-строка}, если же единице равна ширина матрицы, то это \emph{вектор-столбец}.
\end{definition}

Операции над матрицами можно условно разделить на две группы:
\begin{itemize}
    \item \emph{структурные}~--- не зависящие от алгебраической структуры, над которой строилась матрица, и работающие только с её структурой;
    \item \emph{алгебраические}~--- определение таковых опирается на свойства алгебраической структуры, над которой построена матрица.
\end{itemize}

Примерами структурных операций является \emph{транспонирование}, \emph{взятие подматрицы} и \emph{взятие элемента по индексу}.

\begin{example}
    Транспонирование матрицы.
    \[
        \begin{pmatrix}
            "a"  & "ba"  & "cb" \\
            "ac" & "bab" & "b"
        \end{pmatrix}^\top =
        \begin{pmatrix}
            "a"  & "ac"  \\
            "ba" & "bab" \\
            "cd" & "b"
        \end{pmatrix}
    \]
\end{example}

\begin{definition}[Транспонирование матрицы]
    Пусть дана матрица $M_{n \times m}$.
    Тогда результат её \emph{транспонирования}, это такая матрица $M'_{m \times n}$, что $M'[i,j] = M[j,i]$ для всех $i \in [0 \rng m - 1]$ и $j \in [0 \rng n - 1]$.

    Операцию транспонирования принято обозначать как $M^\top$.
\end{definition}

\begin{definition}[Прямая сумма матриц]
    Пусть даны матрицы $M_{n_1 \times m_1}$ и $N_{n_2 \times m_2}$.
    Тогда \emph{прямой суммой} этих матриц называется матрица $L_{(n_1 + n_2) \times (m_1 + m_2)}$ вида
    \[
        L =
        \begin{pmatrix}
            M & 0 \\
            0 & N
        \end{pmatrix}
    \]
    Где 0 обозначает нулевой блок. Прямая сумма обозначается $L = M \oplus N$.
\end{definition}

\begin{definition}[Взятие подматрицы]
    Пусть дана матрица $M_{n\times m}$.
    Тогда $M_{n \times m}[i_0 \rng i_1, j_0 \rng j_1]$~--- это такая $M'_{(i_1 - i_0 + 1) \times (j_1 - j_0 + 1)}$, что $M'[i, j] = M[i_0 + i, j_0 + j]$ для всех $i \in [0 \rng i_1 - i_0 + 1]$ и $j \in [0 \rng j_1 - j_0 + 1]$.
\end{definition}

\begin{example}
    Взятие подматрицы.
    \begin{multline*}
        \begin{pmatrix}
            "a"  & "ba"  & "cb" \\
            "ac" & "bab" & "b"
        \end{pmatrix} [0 \rng 1, 1 \rng 2] =
        \begin{pmatrix}
            "ba"  & "cb" \\
            "bab" & "b"
        \end{pmatrix}
    \end{multline*}
\end{example}

\begin{definition}[Взятие элемента по индексу]
    \emph{Взятие элемента по индексу}~--- это частный случай взятия подматрицы, когда начало и конец \enquote{среза} совпадают: $M[i, j] = M[i \rng i, j \rng j]$.
\end{definition}

\begin{example}
    Взятие элемента по индексу.
    \[
        \begin{pmatrix}
            "a"  & "ba"  & "cb" \\
            "ac" & "bab" & "b"
        \end{pmatrix}[0, 1] = "ba"
    \]
\end{example}

Из алгебраических операций над матрицами нас в дальнейшем будут интересовать \emph{поэлементные операции}, \emph{скалярные операции}, \emph{матричное умножение}, \emph{произведение Кронекера}.

\begin{definition}[Поэлементные операции]
    Пусть $G = (S, \circ)$~--- полугруппа%
    \sidenote{Здесь, как и в дальнейшем, требование к структуре быть полугруппой не обязательно.
        Оно лишь позволяет нам получить ассоциативность соответствующих операций над матрицами, что может оказаться полезным при дальнейшей работе.}%
    , $M_{n \times m}$, $N_{n \times m}$~--- две матрицы одинакового размера над этой полугруппой.
    Тогда $\mathrm{ewise}(M, N, \circ) = P_{n \times m}$, такая, что $P[i, j] = M[i, j] \circ N[i, j]$.
\end{definition}

\begin{example}
    Пусть $G$~--- полугруппа строк с конкатенацией $\cdot$,
    \[M =
        \begin{pmatrix}
            "a"  & "ba"  & "cb" \\
            "ac" & "bab" & "b"
        \end{pmatrix},
        \qquad
        N =
        \begin{pmatrix}
            "c" & "aa"  & "b"  \\
            "a" & "bac" & "bb"
        \end{pmatrix}.
    \]
    Тогда
    \[
        \mathrm{ewise}(M, N, \cdot) =
        \begin{pmatrix}
            "ac"  & "baaa"   & "cbb" \\
            "aca" & "babbac" & "bbb"
        \end{pmatrix}.
    \]
\end{example}

\begin{definition}[Скалярная операция]
    Пусть $G = (S, \circ)$~--- полугруппа, $M_{n \times m}$~--- матрица над этой полугруппой, $x \in S$.
    Тогда $ M \circ x = P_{n \times m}$, такая, что $P[i, j] = M[i, j] \circ x$, а $x \circ M = P_{n \times m}$, такая, что $P[i, j] = x \circ M[i, j]$.
\end{definition}

\begin{example}
    Пусть $G$~--- полугруппа строк с конкатенацией $\cdot$, $x = "c"$,
    \[
        M =
        \begin{pmatrix}
            "a"  & "ba"  & "cb" \\
            "ac" & "bab" & "b"
        \end{pmatrix}.
    \]
    Тогда
    \begin{gather*}
        M \cdot x =
        \begin{pmatrix}
            "ac"  & "bac"  & "cbc" \\
            "acc" & "babc" & "bc"
        \end{pmatrix},\\
        x \cdot M =
        \begin{pmatrix}
            "ca"  & "cba"  & "ccb" \\
            "cac" & "cbab" & "cb"
        \end{pmatrix}.
    \end{gather*}
\end{example}

\begin{definition}[Матричное умножение]
    \label{def:MxM}
    Пусть $G = (S, \oplus, \otimes)$~--- полукольцо, $M_{n \times m}$, $N_{m\times k}$~--- две матрицы над этим полукольцом.
    Тогда $M \cdot N = P_{n \times k}$, такая, что $P[i, j] = \bigoplus_{l \in [0 \rng m - 1]} M[i, l] \otimes N[l, j]$.
\end{definition}

\begin{example}
    Пусть $G$~--- полукольцо из примера~\ref{exmpl:semiring},
    \[
        M =
        \begin{pmatrix}
            \{"a"\} & \{"a"\} \\
            \{"b"\} & \{"b"\}
        \end{pmatrix},
        \qquad
        N =
        \begin{pmatrix}
            \{"c"\} \\
            \{"d"\}
        \end{pmatrix}.
    \]
    Тогда
    \[
        M \cdot N =
        \begin{pmatrix}
            \{"a" \cdot "c"\} \cup \{"a" \cdot "d"\} \\
            \{"b" \cdot "c"\} \cup \{"b" \cdot "d"\}
        \end{pmatrix}=
        \begin{pmatrix}
            \{"ac" \ ,  "ad"\} \\
            \{"bc" \ , "bd"\}
        \end{pmatrix}.
    \]
\end{example}

\begin{definition}[Произведение Кронекера]
    Пусть $G = (S, \circ)$~--- полугруппа, $M_{m \times n}$ и $N_{p \times q}$~--- две матрицы над этой полугруппой.
    Тогда \emph{произведение Кронекера} или \emph{тензорное произведение} матриц $M$ и $N$~--- это блочная матрица $K$ размера $mp \times nq$, вычисляемая следующим образом:
    \begin{multline*}
        K = M \otimes N =
        \begin{pmatrix}
            (M[0,0] \circ N  & \cdots & M[0,n-1] \circ N   \\
            \vdots           & \ddots & \vdots             \\
            M[m-1,0] \circ N & \cdots & M[m-1,n-1] \circ N
        \end{pmatrix}
    \end{multline*}
\end{definition}

\begin{remark}
    \label{note:KronIsNotCommutative}
    Произведение Кронекера не является коммутативным\sidenote{Показать это можно по определению: найти пример, для которого $M \otimes N \neq N \otimes M$.}.
    При этом всегда существуют две матрицы перестановок $P$ и $Q$ такие, что $A \otimes B = P(B \otimes A)Q$.
\end{remark}

\begingroup
\newcommand{\examplemtrx}
{
    \begin{pmatrix}
        5  & 6  & 7  & 8  \\
        9  & 10 & 11 & 12 \\
        13 & 14 & 15 & 16
    \end{pmatrix}
}

\begin{example}
    Возьмём в качестве полугруппы целые числа с умножением.
    \[
        M=
        \begin{pmatrix}
            1 & 2 \\
            3 & 4
        \end{pmatrix},
        \qquad
        N=\examplemtrx
    \]
    Тогда
    \begin{align*}
        M \otimes N & =
        \begin{pmatrix}
            1 & 2 \\
            3 & 4
        \end{pmatrix}
        \otimes
        \examplemtrx =                  \\
                    & =
        \begin{pNiceArray}[margin]{c|c}
            1 \examplemtrx & 2 \examplemtrx \\
            \midrule
            3 \examplemtrx & 4 \examplemtrx
        \end{pNiceArray} = \\
                    & =
        \begin{pNiceArray}[margin]{cccc|cccc}
            5  & 6  & 7  & 8  & 10 & 12 & 14 & 16 \\
            9  & 10 & 11 & 12 & 18 & 20 & 22 & 24 \\
            13 & 14 & 15 & 16 & 26 & 28 & 30 & 32 \\
            \midrule
            15 & 18 & 21 & 24 & 20 & 24 & 28 & 32 \\
            27 & 30 & 33 & 36 & 36 & 40 & 44 & 48 \\
            39 & 42 & 45 & 48 & 52 & 56 & 60 & 64
        \end{pNiceArray}
    \end{align*}
\end{example}
\endgroup

%% FIXME: Исправить раздел
% \section{Теоретическая сложность умножения матриц}

% В рамках такого раздела теории сложности, как мелкозернистая сложность (fine-grained complexity) задача умножения двух матриц оказалась достаточно важной, так как через вычислительную сложность этой задачи можно оценить сложность большого класса различных задач.
% С примерами таких задач можно ознакомиться в работе~\sidecite{Williams:2010:SEP:1917827.1918339}. Поэтому рассмотрим алгоритмы нахождения произведения двух матриц более подробно.
% Далее для простоты мы будем предполагать, что перемножаются две квадратные матрицы одинакового размера $n \times n$.

% Для начала построим наивный алгоритм, сконструированный на основе определения произведения матриц.
% Такой алгоритм представлен на листинге~\ref{algo:MxM}.
% \marginnote{TODO: Оформление алгоритмов точно надо обсудить, потому что я в этом мало понимаю.}
% Его работу можно описать следующим образом: для каждой строки в первой матрице и для каждого столбца в второй матрице найти сумму произведений соответствующих элементов.
% Данная сумма будет значением соответствующей ячейки результирующей матрицы.

% \begin{algorithm}{Наивное умножение матриц}{MxM}
%     \begin{pseudo}[]
%         \kw{function} \pr{MatrixMult}(M_1, M_2, G = (S, \oplus, \otimes)) \\+
%         $M_3 = $ пустая матрица размера $n \times n$ \\
%         \kw{for} $i \in [0 \rng n - 1]$ \\+
%         \kw{for} $j \in [0 \rng n - 1]$ \\+
%         \kw{for} $k \in [0 \rng n - 1]$ \\+
%         $M_3[i, j] = M_3[i, j] \oplus (M_1[i, k] \otimes M_2[k, j])$ \\---
%         \kw{return} $M_3$
%     \end{pseudo}
% \end{algorithm}

% Сложность наивного произведения двух матриц составляет $O(n^3)$ из-за тройного вложенного цикла, где каждый уровень вложенности привносит $n$ итераций.
% Но можно ли улучшить этот алгоритм?
% Первый положительный ответ был опубликовал Ф. Штрассен в 1969 году~\sidecite{Strassen1969}.
% Сложность предложенного им алгоритма~--- $O(n^{\log_2 7}) \approx O(n^{2.81})$.
% Основная идея~--- рекурсивное разбиение исходных матриц на блоки и вычисление их произведения с помощью только 7 умножений, а не 8.

% Рассмотрим алгоритм Штрассена более подробно.
% Пусть $A$ и $B$~--- две квадратные матрицы размера $2^n \times 2^n$ над кольцом $R=(S, \oplus, \otimes)$.
% Если размер умножаемых матриц не является натуральной степенью двойки, то дополняем исходные матрицы дополнительными нулевыми строками и столбцами.
% Наша задача найти матрицу $C = A \cdot B$.

% Разделим матрицы $A, B$ и $C$ на четыре равные по размеру блока.
% \[
%     A =
%     \begin{pmatrix}
%         A_{1,1} & A_{1,2} \\
%         A_{2,1} & A_{2,2}
%     \end{pmatrix},
%     \quad
%     B =
%     \begin{pmatrix}
%         B_{1,1} & B_{1,2} \\
%         B_{2,1} & B_{2,2}
%     \end{pmatrix},
%     \quad
%     C =
%     \begin{pmatrix}
%         C_{1,1} & C_{1,2} \\
%         C_{2,1} & C_{2,2}
%     \end{pmatrix}
% \]

% По определению произведения матриц выполняются следующие равенства.
% \marginnote{TODO: Вообще можно попробовать раскидать на 2 столбца}
% \begin{align*}
%     C_{1, 1} & = A_{1, 1} \cdot B_{1, 1} + A_{1, 2} \cdot B_{2, 1} \\
%     C_{1, 2} & = A_{1, 1} \cdot B_{1, 2} + A_{1, 2} \cdot B_{2, 2} \\
%     C_{2, 1} & = A_{2, 1} \cdot B_{1, 1} + A_{2, 2} \cdot B_{2, 1} \\
%     C_{2, 2} & = A_{2, 1} \cdot B_{1, 2} + A_{2, 2} \cdot B_{2, 2}
% \end{align*}

% Данная процедура не даёт нам ничего нового с точки зрения вычислительной сложности.
% Но мы можем двинуться дальше и определить следующие элементы.
% \begin{align*}
%     P_1 & \equiv (A_{1, 1} + A_{2, 2}) \cdot (B_{1, 1} + B_{2, 2}) \\
%     P_2 & \equiv (A_{2, 1} + A_{2, 2}) \cdot B_{1, 1}              \\
%     P_3 & \equiv A_{1, 1} \cdot (B_{1, 2} - B_{2, 2})              \\
%     P_4 & \equiv A_{2, 2} \cdot (B_{2, 1} - B_{1, 1})              \\
%     P_5 & \equiv (A_{1, 1} + A_{1, 2}) \cdot B_{2, 2}              \\
%     P_6 & \equiv (A_{2, 1} - A_{1, 1}) \cdot (B_{1, 1} + B_{1, 2}) \\
%     P_7 & \equiv (A_{1, 2} - A_{2, 2}) \cdot (B_{2, 1} + B_{2, 2})
% \end{align*}

% Используя эти элементы мы можем выразить блоки результирующей матрицы следующим образом.
% \begin{align*}
%     C_{1, 1} & = P_1 + P_4 - P_5 + P_7 \\
%     C_{1, 2} & = P_3 + P_5             \\
%     C_{2, 1} & = P_2 + P_4             \\
%     C_{2, 2} & = P_1 - P_2 + P_3 + P_6
% \end{align*}

% При таком способе вычисления мы получаем на одно умножение подматриц меньше, чем при наивном подходе.
% Это и приводит, в конечном итоге, к улучшению сложности всего алгоритма, который основывается на рекурсивном повторении проделанной выше процедуры.

% \marginnote{TODO: здесь \textbackslash{}sidecite не влезает}
% Впоследствии сложность постепенно понижалась в ряде работ, таких как~\cite{Pan1978,BiniCapoRoma1979,Schonhage1981,CoppWino1982,CoppWino1990}.
% Было введено специальное обозначение для показателя степени в данной оценке: $\omega$.
% То есть сложность умножения матриц~--- это $O(n^\omega)$, и задача сводится к уменьшению значения $\omega$.
% В настоящее время работа над уменьшением показателя степени продолжается и сейчас уже предложены решения с $\omega < 2.373$%
% \sidenote{
%     В данной области достаточно регулярно появляются новые результаты, дающие сравнительно небольшие, в терминах абсолютных величин, изменения.
%     Так, в 2021 была представлена работа, улучшающая значение $\omega$ в пятом знаке после запятой~\cite{alman2020refined}.
%     Несмотря на кажущуюся несерьёзность результата, подобные работы имеют большое теоретическое значение, так как улучшают наше понимание исходной задачи и её свойств.}%
% .

% Всё тем же Ф. Штрассеном ещё в 1969 году была выдвинута гипотеза о том, что для достаточно больших $n$ существует алгоритм, который для любого сколь угодно маленького наперёд заданного $\varepsilon$ перемножает матрицы за $O(n^{2+\varepsilon})$.
% На текущий момент ни доказательства, ни опровержения этой гипотезы не предъявлено.

% Важной особенностью указанного выше направления улучшения алгоритмов является то, что оно допускает использования (и даже основывается на использовании) более богатых алгебраических структур, чем требуется для определения умножения двух матриц.
% Так, уже алгоритм Штрасеена использует операцию вычитания, что приводит к необходимости иметь обратные элементы по сложению, а значит определять матрицы над кольцом.
% Хотя для исходного определения (\ref{def:MxM}) достаточно более бедной структуры.
% При этом, часто, структуры, возникающие в прикладных задачах кольцами не являются.
% \marginnote{TODO: Не кажется ли что текста на полях слишком много и его можно прямо в главу вписать?}
% Примерами могут служить тропическое (или $\{min, +\}$) полукольцо, играющее ключевую роль в тропической математике, или булево ($\{\lor, \land\}$) полукольцо, возникающее, например, при работе с отношениями%
% \sidenote{
%     Вообще говоря, в некоторых прикладных задачах возникают структуры, не являющиеся даже полукольцом.
%     Предположим, что есть три различных множества $S_1$, $S_2$ и $S_3$ и две двухместные функции $f: S_1 \times S_2 \to S_3$ и $g: S_3 \times S_3 \to S_3$.
%     Этого достаточно, чтобы определить произведение двух матриц $M_1$ и $M_2$, построенных из элементов множеств $S_1$ и $S_2$ соответственно.
%     Результирующая матрица будет состоять из элементов $S_3$.
%     Как видно, функции не являются бинарными операциями в смысле нашего определения.
%     Несмотря на кажущуюся экзотичность, подобные структуры возникают на практике при работе с графами и учитываются, например, в стандарте GraphBLAS (\url{https://graphblas.github.io/}), где, кстати, называются полукольцами, что выглядит не вполне корректно.}%
% .
% Значит, описанные выше решения не применимы и вопрос о существовании алгоритма с менее чем кубической сложностью снова актуален.

% В попытках ответить на этот вопрос появились так называемые комбинаторные алгоритмы умножения матриц%
% \sidenote{
%     В противовес описанным выше, не являющимся комбинаторными.
%     Стоит отметить, что строгое определение комбинаторных алгоритмов отсутствует, хотя этот термин и получил широкое употребление.
%     В частности, Н.~Бансал (Nikhil Bansal) и Р.~Уильямс (Ryan Williams) в работе~\cite{5438580} дают определение комбинаторного алгоритма, но тут же замечают следующее: \enquote{We would like to give a definition of \enquote{combinatorial algorithm}, but this appears elusive. Although the term has been used in many of the cited references, nothing in the literature resembles a definition. For the purposes of this paper, let us think of a \enquote{combinatorial algorithm} simply as one that does not call an oracle for ring matrix multiplication.}.
%     Ещё один вариант определения и его обсуждение можно найти в~\cite{das2018lower}.}%
% .
% Классический результат в данной области~--- это алгоритм четырёх русских, предложенный  В. Л. Арлазаровым, Е. А. Диницем, М. А. Кронродом и И. А. Фараджевым в 1970 году~\cite{ArlDinKro70}, позволяющий перемножить матрицы над конечным полукольцом за $O(n^3/\log n)$.
% Лучшим результатом%
% \sidenote{
% В работе~\cite{das2018lower} предложен алгоритм со сложностью $\Omega(n^{7/3}/2^{O(\sqrt{\log n})})$, однако авторы утверждают, что сами не уверены в комбинаторности предложенного решения.
% По-видимому, полученные результаты ещё должны быть проверены сообществом.}
% в настоящее время является алгоритм со сложностью%
% \sidenote{Нотация $\hat{O}$ скрывает $poly(\log\log)$ коэффициенты.} $\hat{O}(n^3/\log^4 n)$~\cite{10.1007/978-3-662-47672-7_89}.

% Как видим, особенности алгебраических структур накладывают серьёзные ограничения на возможности конструирования алгоритмов.
% Отметим, что, хотя, в указанных случаях и предлагаются решения лучшие, чем наивное кубическое, они обладают принципиально разной асимптотической сложностью.
% В первом случае сложность оценивается полиномом, степень которого меньше третьей.
% Такие решения принято называть \emph{истинно субкубическими} (truly subcubic).
% В то время как в случае комбинаторных алгоритмов степень полинома остается прежней, третьей, хотя сложность и уменьшается на логарифмический фактор.
% Такие решения принято называть \emph{слегка субкубическими} (mildly subcubic).
% Естественный вопрос о существовании истинно субкубического алгоритма перемножения матриц над полукольцами (или же комбинаторного перемножения матриц) всё ещё не решён%
% \sidenote{Один из кандидатов~--- работа~\cite{das2018lower}, однако на текущий момент предложенное в ней решение  требует проверки.}.

% %Заметим, что скалярная операция~--- это частный случай произвеления Кронекера: достаточно превратить элемент носителя полугруппы в матрицу размера $1\times 1$.

% %\section{Вопросы и задачи}
% %\begin{enumerate}
% %	\item Привидите примеры некоммутативных операций.
% %	\item Привидите примеры ситуаций, когда наличие у бинарных операций каких-либо дополнитльных свойств (ассоциативности, коммутативности), позволяет строить более эффективные алгоритмы, чем в общем случае.
% %\end{enumerate}