Умножение матриц

Математическая операция в линейной алгебре

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

В математике , в частности в линейной алгебре , умножение матриц — это бинарная операция , которая производит матрицу из двух матриц. Для умножения матриц количество столбцов в первой матрице должно быть равно количеству строк во второй матрице. Результирующая матрица, известная как произведение матриц , имеет количество строк первой и количество столбцов второй матрицы. Произведение матриц A и B обозначается как AB . ^[1]

Матричное умножение было впервые описано французским математиком Жаком Филиппом Мари Бине в 1812 году ^[2] для представления композиции линейных отображений , представленных матрицами. Таким образом, матричное умножение является основным инструментом линейной алгебры и, как таковое, имеет многочисленные приложения во многих областях математики, а также в прикладной математике , статистике , физике , экономике и инженерии . ^{[3] [4]} Вычисление матричных произведений является центральной операцией во всех вычислительных приложениях линейной алгебры.

Обозначение

В этой статье будут использоваться следующие условные обозначения: матрицы обозначаются заглавными буквами жирным шрифтом, например A ; векторы — строчными буквами жирным шрифтом, например a ; записи векторов и матриц обозначаются курсивом (это числа из поля), например A и a . Индексная нотация часто является самым понятным способом выражения определений и используется в качестве стандарта в литературе. Запись в строке i , столбце j матрицы A обозначается как ( A ) _ij , A _ij или a _ij . Напротив, один нижний индекс, например A ₁ , A ₂ , используется для выбора матрицы (не записи матрицы) из набора матриц.

Определения

Матрица умноженная на матрицу

Если A — матрица размером m × n , а B — матрица размером n × p , то матричное произведение C = AB (обозначается без знаков умножения или точек) определяется как матрица размером m × p ^{[5] [6] [7] [8]} такая, что для i = 1, ..., m и j = 1, ..., p . $${\displaystyle \mathbf {A} ={\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\\\end{pmatrix}},\quad \mathbf {B} ={\begin{pmatrix}b_{11}&b_{12}&\cdots &b_{1p}\\b_{21}&b_{22}&\cdots &b_{2p}\\\vdots &\vdots &\ddots &\vdots \\b_{n1}&b_{n2}&\cdots &b_{np}\\\end{pmatrix}}}$$ $${\displaystyle \mathbf {C} ={\begin{pmatrix}c_{11}&c_{12}&\cdots &c_{1p}\\c_{21}&c_{22}&\cdots &c_{2p}\\\vdots &\vdots &\ddots &\vdots \\c_{m1}&c_{m2}&\cdots &c_{mp}\\\end{pmatrix}}}$$ $${\displaystyle c_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots +a_{in}b_{nj}=\sum _{k=1}^{n}a_{ik}b_{kj},}$$

То есть, запись ⁠ ⁠ ${\displaystyle c_{ij}}$ произведения получается путем умножения почленно записей i- й строки A и j -го столбца B и суммирования этих n произведений . Другими словами, ⁠ ⁠ ${\displaystyle c_{ij}}$ является скалярным произведением i -й строки A и j - го столбца B.

Следовательно, AB можно также записать как $${\displaystyle \mathbf {C} ={\begin{pmatrix}a_{11}b_{11}+\cdots +a_{1n}b_{n1}&a_{11}b_{12}+\cdots +a_{1n}b_{n2}&\cdots &a_{11}b_{1p}+\cdots +a_{1n}b_{np}\\a_{21}b_{11}+\cdots +a_{2n}b_{n1}&a_{21}b_{12}+\cdots +a_{2n}b_{n2}&\cdots &a_{21}b_{1p}+\cdots +a_{2n}b_{np}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}b_{11}+\cdots +a_{mn}b_{n1}&a_{m1}b_{12}+\cdots +a_{mn}b_{n2}&\cdots &a_{m1}b_{1p}+\cdots +a_{mn}b_{np}\\\end{pmatrix}}}$$

Таким образом, произведение AB определено тогда и только тогда, когда число столбцов в A равно числу строк в B , ^[1] в данном случае n .

В большинстве сценариев записи являются числами, но они могут быть любыми видами математических объектов , для которых определены сложение и умножение, которые являются ассоциативными , и такими, что сложение является коммутативным , а умножение является дистрибутивным относительно сложения. В частности, записи могут быть самими матрицами (см. блочная матрица ).

Матрица умноженная на вектор

Вектор длины можно рассматривать как вектор-столбец , соответствующий матрице , элементы которой задаются следующим образом: Если это матрица, то произведение матрицы на вектор, обозначенное как , представляет собой вектор, который, рассматриваемый как вектор-столбец, равен матрице В индексной нотации это равносильно: ${\displaystyle \mathbf {x} }$ ${\displaystyle n}$ ${\displaystyle n\times 1}$ ${\displaystyle \mathbf {X} }$ ${\displaystyle \mathbf {X} _{i1}=\mathbf {x} _{i}.}$ ${\displaystyle \mathbf {A} }$ ${\displaystyle m\times n}$ ${\displaystyle \mathbf {Ax} }$ ${\displaystyle \mathbf {y} }$ ${\displaystyle m\times 1}$ ${\displaystyle \mathbf {AX} .}$

${\displaystyle y_{i}=\sum _{j=1}^{n}a_{ij}x_{j}.}$

Один из способов взглянуть на это состоит в том, что изменения от «простого» вектора к вектору-столбцу и обратно предполагаются и остаются неявными.

Вектор умножить на матрицу

Аналогично вектор длины можно рассматривать как вектор-строку , соответствующий матрице. Чтобы было ясно, что подразумевается вектор-строка, в этом контексте принято представлять его как транспонированный вектор-столбец; таким образом, можно увидеть такие обозначения, как Тождество выполняется. В индексной нотации, если это матрица, то это равносильно: ${\displaystyle \mathbf {x} }$ ${\displaystyle n}$ ${\displaystyle 1\times n}$ ${\displaystyle \mathbf {x} ^{\mathrm {T} }\mathbf {A} .}$ ${\displaystyle \mathbf {x} ^{\mathrm {T} }\mathbf {A} =(\mathbf {A} ^{\mathrm {T} }\mathbf {x} )^{\mathrm {T} }}$ ${\displaystyle \mathbf {A} }$ ${\displaystyle n\times p}$ ${\displaystyle \mathbf {x} ^{\mathrm {T} }\mathbf {A} =\mathbf {y} ^{\mathrm {T} }}$ ${\displaystyle y_{k}=\sum _{j=1}^{n}x_{j}a_{jk}.}$

Вектор умножить на вектор

Скалярное произведение двух векторов одинаковой длины равно одному элементу матрицы , полученной в результате умножения этих векторов как вектора строки и столбца, то есть: (или что приводит к той же матрице). ${\displaystyle \mathbf {a} \cdot \mathbf {b} }$ ${\displaystyle \mathbf {a} }$ ${\displaystyle \mathbf {b} }$ ${\displaystyle 1\times 1}$ ${\displaystyle \mathbf {a} ^{\mathrm {T} }\mathbf {b} }$ ${\displaystyle \mathbf {b} ^{\mathrm {T} }\mathbf {a} ,}$ ${\displaystyle 1\times 1}$

Иллюстрация

Рисунок справа схематически иллюстрирует произведение двух матриц A и B , показывая , как каждое пересечение в матрице произведения соответствует строке A и столбцу B. $${\displaystyle {\overset {4\times 2{\text{ matrix}}}{\begin{bmatrix}a_{11}&a_{12}\\\cdot &\cdot \\a_{31}&a_{32}\\\cdot &\cdot \\\end{bmatrix}}}{\overset {2\times 3{\text{ matrix}}}{\begin{bmatrix}\cdot &b_{12}&b_{13}\\\cdot &b_{22}&b_{23}\\\end{bmatrix}}}={\overset {4\times 3{\text{ matrix}}}{\begin{bmatrix}\cdot &c_{12}&\cdot \\\cdot &\cdot &\cdot \\\cdot &\cdot &c_{33}\\\cdot &\cdot &\cdot \\\end{bmatrix}}}}$$

Значения на пересечениях, отмеченные кружками на рисунке справа, следующие: $${\displaystyle {\begin{aligned}c_{12}&=a_{11}b_{12}+a_{12}b_{22}\\c_{33}&=a_{31}b_{13}+a_{32}b_{23}.\end{aligned}}}$$

Фундаментальные приложения

Исторически матричное умножение было введено для облегчения и прояснения вычислений в линейной алгебре . Эта тесная связь между матричным умножением и линейной алгеброй остается фундаментальной во всей математике, а также в физике , химии , инженерии и информатике .

Линейные карты

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

Линейное отображение A из векторного пространства размерности n в векторное пространство размерности m отображает вектор-столбец

${\displaystyle \mathbf {x} ={\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{pmatrix}}}$

на вектор-столбец

${\displaystyle \mathbf {y} =A(\mathbf {x} )={\begin{pmatrix}a_{11}x_{1}+\cdots +a_{1n}x_{n}\\a_{21}x_{1}+\cdots +a_{2n}x_{n}\\\vdots \\a_{m1}x_{1}+\cdots +a_{mn}x_{n}\end{pmatrix}}.}$

Таким образом, линейное отображение A определяется матрицей

${\displaystyle \mathbf {A} ={\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\\\end{pmatrix}},}$

и отображает вектор-столбец в матричное произведение ${\displaystyle \mathbf {x} }$

${\displaystyle \mathbf {y} =\mathbf {Ax} .}$

Если B — это другое линейное отображение из предыдущего векторного пространства размерности m в векторное пространство размерности p , оно представляется матрицей ⁠ ⁠ Прямое ${\displaystyle p\times m}$ вычисление показывает, что матрица составного отображения ⁠ ⁠ является произведением матриц Общая формула ⁠ ⁠ ), определяющая композицию функций, приведена здесь как частный случай ассоциативности произведения матриц (см. § Ассоциативность ниже): ${\displaystyle \mathbf {B} .}$ ${\displaystyle B\circ A}$ ${\displaystyle \mathbf {BA} .}$ ${\displaystyle (B\circ A)(\mathbf {x} )=B(A(\mathbf {x} ))}$

${\displaystyle (\mathbf {BA} )\mathbf {x} =\mathbf {B} (\mathbf {Ax} )=\mathbf {BAx} .}$

Геометрические вращения

Используя декартову систему координат в евклидовой плоскости, поворот на угол вокруг начала координат представляет собой линейную карту. Точнее, где исходная точка и ее изображение записываются как векторы-столбцы. ${\displaystyle \alpha }$ $${\displaystyle {\begin{bmatrix}x'\\y'\end{bmatrix}}={\begin{bmatrix}\cos \alpha &-\sin \alpha \\\sin \alpha &\cos \alpha \end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}},}$$ ${\displaystyle (x,y)}$ ${\displaystyle (x',y')}$

Композиция вращения на и на затем соответствует матричному произведению , где для второго равенства используются соответствующие тригонометрические тождества . То есть композиция соответствует вращению на угол , как и ожидалось. ${\displaystyle \alpha }$ ${\displaystyle \beta }$ $${\displaystyle {\begin{bmatrix}\cos \beta &-\sin \beta \\\sin \beta &\cos \beta \end{bmatrix}}{\begin{bmatrix}\cos \alpha &-\sin \alpha \\\sin \alpha &\cos \alpha \end{bmatrix}}={\begin{bmatrix}\cos \beta \cos \alpha -\sin \beta \sin \alpha &-\cos \beta \sin \alpha -\sin \beta \cos \alpha \\\sin \beta \cos \alpha +\cos \beta \sin \alpha &-\sin \beta \sin \alpha +\cos \beta \cos \alpha \end{bmatrix}}={\begin{bmatrix}\cos(\alpha +\beta )&-\sin(\alpha +\beta )\\\sin(\alpha +\beta )&\cos(\alpha +\beta )\end{bmatrix}},}$$ ${\displaystyle \alpha +\beta }$

Распределение ресурсов в экономике

Расчет нижней левой записи соответствует рассмотрению всех путей (выделенных) от базового товара до конечного продукта в графе производственного потока. ${\displaystyle \mathbf {AB} }$ ${\displaystyle b_{4}}$ ${\displaystyle f_{1}}$

В качестве примера, вымышленная фабрика использует 4 вида основных товаров , для производства 3 видов промежуточных товаров , которые в свою очередь используются для производства 3 видов конечных продуктов , Матрицы ${\displaystyle b_{1},b_{2},b_{3},b_{4}}$ ${\displaystyle m_{1},m_{2},m_{3}}$ ${\displaystyle f_{1},f_{2},f_{3}}$

${\displaystyle \mathbf {A} ={\begin{pmatrix}1&0&1\\2&1&1\\0&1&1\\1&1&2\\\end{pmatrix}}}$   и   ${\displaystyle \mathbf {B} ={\begin{pmatrix}1&2&1\\2&3&1\\4&2&2\\\end{pmatrix}}}$

укажите количество основных товаров, необходимых для данного количества промежуточных товаров, и количество промежуточных товаров, необходимых для данного количества конечных продуктов, соответственно. Например, для производства одной единицы промежуточного товара , одной единицы основного товара , двух единиц , ни одной единицы и одной единицы , что соответствует первому столбцу . ${\displaystyle m_{1}}$ ${\displaystyle b_{1}}$ ${\displaystyle b_{2}}$ ${\displaystyle b_{3}}$ ${\displaystyle b_{4}}$ ${\displaystyle \mathbf {A} }$

Используя умножение матриц, вычислите

${\displaystyle \mathbf {AB} ={\begin{pmatrix}5&4&3\\8&9&5\\\ 6&5&3\\11&9&6\\\end{pmatrix}};}$

эта матрица напрямую предоставляет количество основных товаров, необходимых для заданного количества конечных товаров. Например, нижняя левая запись вычисляется как , отражая, что единиц требуется для производства одной единицы . Действительно, одна единица требуется для , одна для каждого из двух , и для каждой из четырех единиц, которые входят в единицу, см. рисунок. ${\displaystyle \mathbf {AB} }$ ${\displaystyle 1\cdot 1+1\cdot 2+2\cdot 4=11}$ ${\displaystyle 11}$ ${\displaystyle b_{4}}$ ${\displaystyle f_{1}}$ ${\displaystyle b_{4}}$ ${\displaystyle m_{1}}$ ${\displaystyle m_{2}}$ ${\displaystyle 2}$ ${\displaystyle m_{3}}$ ${\displaystyle f_{1}}$

Для того чтобы произвести, например, 100 единиц конечного продукта , 80 единиц и 60 единиц , необходимое количество основных товаров можно рассчитать следующим образом: ${\displaystyle f_{1}}$ ${\displaystyle f_{2}}$ ${\displaystyle f_{3}}$

${\displaystyle (\mathbf {AB} ){\begin{pmatrix}100\\80\\60\\\end{pmatrix}}={\begin{pmatrix}1000\\1820\\1180\\2180\end{pmatrix}},}$

то есть, необходимы единицы , единицы , единицы , единицы . Аналогично, матрица продукта может быть использована для вычисления необходимого количества базовых товаров для других данных о количестве конечного товара. ^[9] ${\displaystyle 1000}$ ${\displaystyle b_{1}}$ ${\displaystyle 1820}$ ${\displaystyle b_{2}}$ ${\displaystyle 1180}$ ${\displaystyle b_{3}}$ ${\displaystyle 2180}$ ${\displaystyle b_{4}}$ ${\displaystyle \mathbf {AB} }$

Система линейных уравнений

Общая форма системы линейных уравнений имеет вид

${\displaystyle {\begin{matrix}a_{11}x_{1}+\cdots +a_{1n}x_{n}=b_{1},\\a_{21}x_{1}+\cdots +a_{2n}x_{n}=b_{2},\\\vdots \\a_{m1}x_{1}+\cdots +a_{mn}x_{n}=b_{m}.\end{matrix}}}$

Используя те же обозначения, что и выше, такая система эквивалентна уравнению с одной матрицей

${\displaystyle \mathbf {Ax} =\mathbf {b} .}$

Скалярное произведение, билинейная форма и полуторалинейная форма

Скалярное произведение двух векторов-столбцов является уникальной записью матричного произведения.

${\displaystyle \mathbf {x} ^{\mathsf {T}}\mathbf {y} ,}$

где — вектор-строка, полученный путем транспонирования . (Как обычно, матрица 1×1 идентифицируется по ее уникальной записи.) ${\displaystyle \mathbf {x} ^{\mathsf {T}}}$ ${\displaystyle \mathbf {x} }$

В более общем смысле любая билинейная форма над векторным пространством конечной размерности может быть выражена как матричное произведение

${\displaystyle \mathbf {x} ^{\mathsf {T}}\mathbf {Ay} ,}$

и любая полуторалинейная форма может быть выражена как

${\displaystyle \mathbf {x} ^{\dagger }\mathbf {Ay} ,}$

где обозначает сопряженное транспонирование ( сопряжение транспонирования или, что эквивалентно, транспонирование сопряженного). ${\displaystyle \mathbf {x} ^{\dagger }}$ ${\displaystyle \mathbf {x} }$

Общие свойства

Умножение матриц имеет некоторые общие свойства с обычным умножением . Однако умножение матриц не определено, если число столбцов первого множителя отличается от числа строк второго множителя, и оно некоммутативно , ^[10] даже когда произведение остается определенным после изменения порядка множителей. ^{[11] [12]}

Некоммутативность

Операция является коммутативной , если для двух элементов A и B, таких что произведение определено, то также определено, и ${\displaystyle \mathbf {A} \mathbf {B} }$ ${\displaystyle \mathbf {B} \mathbf {A} }$ ${\displaystyle \mathbf {A} \mathbf {B} =\mathbf {B} \mathbf {A} .}$

Если A и B — матрицы соответствующих размеров ⁠ ⁠ ${\displaystyle m\times n}$ и ⁠ ⁠ ${\displaystyle p\times q}$ , то определено, если ⁠ ⁠ , и определено, если ⁠ ⁠ . Следовательно, если одно из произведений определено, другое не обязательно должно быть определено. Если ⁠ ⁠ , два произведения определены, но имеют разные размеры; таким образом, они не могут быть равны. Только если ⁠ ⁠ , то есть если A и B — квадратные матрицы одинакового размера, оба произведения определены и имеют одинаковый размер. Даже в этом случае в общем случае ${\displaystyle \mathbf {A} \mathbf {B} }$ ${\displaystyle n=p}$ ${\displaystyle \mathbf {B} \mathbf {A} }$ ${\displaystyle m=q}$ ${\displaystyle m=q\neq n=p}$ ${\displaystyle m=q=n=p}$

${\displaystyle \mathbf {A} \mathbf {B} \neq \mathbf {B} \mathbf {A} .}$

Например

${\displaystyle {\begin{pmatrix}0&1\\0&0\end{pmatrix}}{\begin{pmatrix}0&0\\1&0\end{pmatrix}}={\begin{pmatrix}1&0\\0&0\end{pmatrix}},}$

но

${\displaystyle {\begin{pmatrix}0&0\\1&0\end{pmatrix}}{\begin{pmatrix}0&1\\0&0\end{pmatrix}}={\begin{pmatrix}0&0\\0&1\end{pmatrix}}.}$

Этот пример можно расширить, чтобы показать, что если A — матрица с записями ${\displaystyle n\times n}$ в поле F , то для каждой матрицы B с записями в F , тогда и только тогда, когда , а I — единичная матрица . Если вместо поля предполагается, что записи принадлежат кольцу , то нужно добавить условие, что c принадлежит центру кольца . ${\displaystyle \mathbf {A} \mathbf {B} =\mathbf {B} \mathbf {A} }$ ${\displaystyle n\times n}$ ${\displaystyle \mathbf {A} =c\,\mathbf {I} }$ ${\displaystyle c\in F}$ ${\displaystyle n\times n}$

Один особый случай, когда коммутативность действительно имеет место, — это когда D и E являются двумя (квадратными) диагональными матрицами (одинакового размера); тогда DE = ED . ^[10] Опять же, если матрицы находятся над общим кольцом, а не над полем, соответствующие элементы в каждой из них также должны коммутировать друг с другом, чтобы это соблюдалось.

Распределяемость

Произведение матриц дистрибутивно относительно сложения матриц . То есть, если A , B , C , D — матрицы соответствующих размеров m × n , n × p , n × p и p × q , то имеем (левая дистрибутивность)

${\displaystyle \mathbf {A} (\mathbf {B} +\mathbf {C} )=\mathbf {AB} +\mathbf {AC} ,}$

и (правильная дистрибутивность)

${\displaystyle (\mathbf {B} +\mathbf {C} )\mathbf {D} =\mathbf {BD} +\mathbf {CD} .}$^[10]

Это следует из распределения коэффициентов по

${\displaystyle \sum _{k}a_{ik}(b_{kj}+c_{kj})=\sum _{k}a_{ik}b_{kj}+\sum _{k}a_{ik}c_{kj}}$

${\displaystyle \sum _{k}(b_{ik}+c_{ik})d_{kj}=\sum _{k}b_{ik}d_{kj}+\sum _{k}c_{ik}d_{kj}.}$

Произведение со скаляром

Если A — матрица, а c — скаляр, то матрицы и получаются путем левого или правого умножения всех элементов A на c . Если скаляры обладают коммутативным свойством , то ${\displaystyle c\mathbf {A} }$ ${\displaystyle \mathbf {A} c}$ ${\displaystyle c\mathbf {A} =\mathbf {A} c.}$

Если произведение определено (то есть количество столбцов A равно количеству строк B ), то ${\displaystyle \mathbf {AB} }$

${\displaystyle c(\mathbf {AB} )=(c\mathbf {A} )\mathbf {B} }$и ${\displaystyle (\mathbf {A} \mathbf {B} )c=\mathbf {A} (\mathbf {B} c).}$

Если скаляры обладают коммутативным свойством, то все четыре матрицы равны. В более общем случае все четыре матрицы равны, если c принадлежит центру кольца , содержащего элементы матриц, поскольку в этом случае c X = X c для всех матриц X .

Эти свойства вытекают из билинейности произведения скаляров:

${\displaystyle c\left(\sum _{k}a_{ik}b_{kj}\right)=\sum _{k}(ca_{ik})b_{kj}}$

${\displaystyle \left(\sum _{k}a_{ik}b_{kj}\right)c=\sum _{k}a_{ik}(b_{kj}c).}$

Транспонировать

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

${\displaystyle (\mathbf {AB} )^{\mathsf {T}}=\mathbf {B} ^{\mathsf {T}}\mathbf {A} ^{\mathsf {T}}}$

где ^T обозначает транспонирование, то есть перестановку строк и столбцов.

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

Комплексно сопряженный

Если A и B имеют сложные записи, то

${\displaystyle (\mathbf {AB} )^{*}=\mathbf {A} ^{*}\mathbf {B} ^{*}}$

где ^* обозначает комплексное сопряжение матрицы по элементам .

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

Транспозиция действует на индексы записей, в то время как сопряжение действует независимо на сами записи. Это приводит к тому, что если A и B имеют сложные записи, то мы имеем

${\displaystyle (\mathbf {AB} )^{\dagger }=\mathbf {B} ^{\dagger }\mathbf {A} ^{\dagger },}$

где ^† обозначает сопряженную транспонированную операцию (сопряженную транспонированную операцию или, что эквивалентно, транспонированную операцию сопряженной операции).

Ассоциативность

При наличии трех матриц A , B и C , произведения ( AB ) C и A ( BC ) определены тогда и только тогда, когда число столбцов A равно числу строк B , а число столбцов B равно числу строк C (в частности, если одно из произведений определено, то и другое также определено). В этом случае имеет место ассоциативное свойство

${\displaystyle (\mathbf {AB} )\mathbf {C} =\mathbf {A} (\mathbf {BC} ).}$

Как и любая ассоциативная операция, это позволяет опустить скобки и записать вышеуказанные произведения как ⁠ ⁠ ${\displaystyle \mathbf {ABC} .}$

Это естественным образом распространяется на произведение любого количества матриц при условии, что размеры совпадают. То есть, если A ₁ , A ₂ , ..., A _n являются матрицами, такими, что количество столбцов A _i равно количеству строк A _{i + 1} для i = 1, ..., n – 1 , то произведение

${\displaystyle \prod _{i=1}^{n}\mathbf {A} _{i}=\mathbf {A} _{1}\mathbf {A} _{2}\cdots \mathbf {A} _{n}}$

определено и не зависит от порядка умножений , если порядок матриц сохраняется фиксированным.

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

Сложность вычислений зависит от скобок

Хотя результат последовательности матричных произведений не зависит от порядка операций (при условии, что порядок матриц не меняется), вычислительная сложность может существенно зависеть от этого порядка.

Например, если A , B и C — матрицы соответствующих размеров 10×30, 30×5, 5×60 , то для вычисления ( AB ) C потребуется 10×30×5 + 10×5×60 = 4500 умножений, тогда как для вычисления A ( BC ) потребуется 30×5×60 + 10×30×60 = 27 000 умножений.

Разработаны алгоритмы для выбора наилучшего порядка продуктов; см. Умножение цепочек матриц . Когда число матриц n увеличивается, было показано, что выбор наилучшего порядка имеет сложность ^{[13] [14]} ${\displaystyle O(n\log n).}$

Применение к подобию

Любая обратимая матрица определяет преобразование подобия (для квадратных матриц того же размера, что и ) ${\displaystyle \mathbf {P} }$ ${\displaystyle \mathbf {P} }$

${\displaystyle S_{\mathbf {P} }(\mathbf {A} )=\mathbf {P} ^{-1}\mathbf {A} \mathbf {P} .}$

Преобразования подобия сопоставляют продукт с продуктом, т.е.

${\displaystyle S_{\mathbf {P} }(\mathbf {AB} )=S_{\mathbf {P} }(\mathbf {A} )S_{\mathbf {P} }(\mathbf {B} ).}$

На самом деле, у одного есть

${\displaystyle \mathbf {P} ^{-1}(\mathbf {AB} )\mathbf {P} =\mathbf {P} ^{-1}\mathbf {A} (\mathbf {P} \mathbf {P} ^{-1})\mathbf {B} \mathbf {P} =(\mathbf {P} ^{-1}\mathbf {A} \mathbf {P} )(\mathbf {P} ^{-1}\mathbf {B} \mathbf {P} ).}$

Квадратные матрицы

Обозначим множество квадратных матриц размера n × n с элементами в кольце R , которое на практике часто является полем . ${\displaystyle {\mathcal {M}}_{n}(R)}$

В , произведение определено для каждой пары матриц. Это создает кольцо , которое имеет единичную матрицу I в качестве единичного элемента (матрица, диагональные элементы которой равны 1, а все остальные элементы равны 0). Это кольцо также является ассоциативной R -алгеброй . ${\displaystyle {\mathcal {M}}_{n}(R)}$ ${\displaystyle {\mathcal {M}}_{n}(R)}$

Если n > 1 , многие матрицы не имеют мультипликативной обратной матрицы . Например, матрица, у которой все элементы строки (или столбца) равны 0, не имеет обратной матрицы. Если она существует, обратная матрица матрицы A обозначается как A ⁻¹ , и, таким образом, проверяет

${\displaystyle \mathbf {A} \mathbf {A} ^{-1}=\mathbf {A} ^{-1}\mathbf {A} =\mathbf {I} .}$

Матрица, имеющая обратную, называется обратимой матрицей . В противном случае это сингулярная матрица .

Произведение матриц обратимо тогда и только тогда, когда обратим каждый множитель. В этом случае имеем

${\displaystyle (\mathbf {A} \mathbf {B} )^{-1}=\mathbf {B} ^{-1}\mathbf {A} ^{-1}.}$

Когда R коммутативно , и, в частности, когда это поле, определитель произведения является произведением определителей. Поскольку определители являются скалярами, а скаляры коммутируют, то, таким образом ,

${\displaystyle \det(\mathbf {AB} )=\det(\mathbf {BA} )=\det(\mathbf {A} )\det(\mathbf {B} ).}$

Другие инварианты матриц не ведут себя так же хорошо с произведениями. Тем не менее, если R коммутативно, AB и BA имеют одинаковый след , одинаковый характеристический полином и одинаковые собственные значения с одинаковыми кратностями. Однако собственные векторы, как правило, различны, если AB ≠ BA .

Силы матрицы

Можно возвести квадратную матрицу в любую неотрицательную целую степень, умножая ее на себя многократно так же, как и для обычных чисел. То есть,

${\displaystyle \mathbf {A} ^{0}=\mathbf {I} ,}$

${\displaystyle \mathbf {A} ^{1}=\mathbf {A} ,}$

${\displaystyle \mathbf {A} ^{k}=\underbrace {\mathbf {A} \mathbf {A} \cdots \mathbf {A} } _{k{\text{ times}}}.}$

Вычисление k- й степени матрицы требует в k – 1 раз больше времени, чем простое умножение матриц, если это делается с помощью тривиального алгоритма (повторное умножение). Поскольку это может занять очень много времени, обычно предпочитают использовать возведение в степень путем возведения в квадрат , что требует менее 2 log ₂ k умножений матриц, и поэтому гораздо эффективнее.

Простым случаем возведения в степень является диагональная матрица . Поскольку произведение диагональных матриц сводится к простому умножению соответствующих диагональных элементов, k- я степень диагональной матрицы получается путем возведения элементов в степень k :

${\displaystyle {\begin{bmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{bmatrix}}^{k}={\begin{bmatrix}a_{11}^{k}&0&\cdots &0\\0&a_{22}^{k}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}^{k}\end{bmatrix}}.}$

Абстрактная алгебра

Определение матричного произведения требует, чтобы записи принадлежали полукольцу, и не требует, чтобы умножение элементов полукольца было коммутативным . Во многих приложениях элементы матрицы принадлежат полю, хотя тропическое полукольцо также является распространенным выбором для задач на кратчайший путь в графе. ^[15] Даже в случае матриц над полями произведение в общем случае не коммутативно, хотя оно ассоциативно и дистрибутивно относительно сложения матриц . Единичные матрицы (которые являются квадратными матрицами , элементы которых равны нулю вне главной диагонали и 1 на главной диагонали) являются единичными элементами матричного произведения. Из этого следует, что матрицы n × n над кольцом образуют кольцо, которое некоммутативно, за исключением случая, когда n = 1 , а основное кольцо коммутативно.

Квадратная матрица может иметь мультипликативную обратную матрицу , называемую обратной матрицей . В общем случае, когда элементы принадлежат коммутативному кольцу R , матрица имеет обратную матрицу тогда и только тогда, когда ее определитель имеет мультипликативную обратную матрицу в R . Определитель произведения квадратных матриц является произведением определителей множителей. Матрицы n × n , имеющие обратную матрицу, образуют группу относительно матричное умножение, подгруппы которой называются матричными группами . Многие классические группы (включая все конечные группы ) изоморфны матричным группам; это отправная точка теории представлений групп .

Матрицы являются морфизмами категории , категории матриц . Объектами являются натуральные числа , которые измеряют размер матриц, а композиция морфизмов — умножение матриц. Источником морфизма является число столбцов соответствующей матрицы, а целью — число строк.

Сложность вычислений

Улучшение оценок показателя ω с течением времени для вычислительной сложности умножения матриц ${\displaystyle O(n^{\omega })}$

Алгоритм умножения матриц , который следует из определения, требует в худшем случае ⁠ ⁠ ${\displaystyle n^{3}}$ умножений и ⁠ ⁠ ${\displaystyle (n-1)n^{2}}$ сложений скаляров для вычисления произведения двух квадратных матриц n × n . Его вычислительная сложность , таким образом, ⁠ ⁠ ${\displaystyle O(n^{3})}$ , в модели вычислений , для которой скалярные операции занимают постоянное время.

Довольно удивительно, что эта сложность не является оптимальной, как было показано в 1969 году Фолькером Штрассеном , который предоставил алгоритм, теперь называемый алгоритмом Штрассена , со сложностью ^[16] Алгоритм Штрассена можно распараллелить для дальнейшего повышения производительности. ^[17] По состоянию на январь 2024 года лучшим рецензируемым алгоритмом умножения матриц является алгоритм Вирджинии Василевской Уильямс , Иньчжан Сюй, Цзысюань Сюй и Жэньфэй Чжоу, имеющий сложность O ( n ^2,371552 ) . ^{[18] [19]} Неизвестно, можно ли выполнить умножение матриц за время n ^{2 ​​+ o(1)} . ^[20] Это было бы оптимальным, поскольку для того, чтобы умножить ее на другую матрицу, необходимо прочитать ⁠ ⁠ элементы матрицы. ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.8074}).}$^[update] ${\displaystyle n^{2}}$

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

Обобщения

Другие типы продукции матриц включают в себя:

• Операции с блочной матрицей
• Краковское произведение , определяемое как A ∧ B = B ^T A
• Внутреннее произведение Фробениуса , скалярное произведение матриц, рассматриваемых как векторы, или, что то же самое, сумма элементов произведения Адамара
• Произведение Адамара двух матриц одинакового размера, дающее в результате матрицу того же размера, которая является произведением поэлементно
• Произведение Кронекера или тензорное произведение , обобщение на любой размер предыдущего
• Продукт Хатри-Рао и продукт Face-splitting
• Внешнее произведение , также называемое диадическим произведением или тензорным произведением двух столбчатых матриц, которое является ${\displaystyle \mathbf {a} \mathbf {b} ^{\mathsf {T}}}$
• Скалярное умножение

Смотрите также

• Матричное исчисление , для взаимодействия умножения матриц с операциями из исчисления

Примечания

1. Nykamp, ​​Duane. "Умножение матриц и векторов". Math Insight . Получено 6 сентября 2020 г.
2. О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. , «Жак Филипп Мари Бине», Архив истории математики Мактьютора , Университет Сент-Эндрюс
3. Лернер, РГ ; Тригг, ГЛ (1991). Энциклопедия физики (2-е изд.). Издательство VHC. ISBN 978-3-527-26954-9.
4. Паркер, К. Б. (1994). Энциклопедия физики Макгроу-Хилла (2-е изд.). McGraw-Hill. ISBN 978-0-07-051400-3.
5. Липшуц, С.; Липсон, М. (2009). Линейная алгебра . Очерки Шаума (4-е изд.). МакГроу Хилл (США). стр. 30–31. ISBN 978-0-07-154352-1.
6. Райли, К. Ф.; Хобсон, М. П.; Бенс, С. Дж. (2010). Математические методы для физики и техники . Cambridge University Press. ISBN 978-0-521-86153-3.
7. Адамс, РА (1995). Исчисление, полный курс (3-е изд.). Addison Wesley. стр. 627. ISBN 0-201-82823-5.
8. Хорн, Джонсон (2013). Матричный анализ (2-е изд.). Cambridge University Press. стр. 6. ISBN 978-0-521-54823-6.
9. Питер Стингл (1996). Mathematik für Fachhochschulen – Technik und Informatik (на немецком языке) (5-е изд.). Мюнхен : Карл Хансер Верлаг . ISBN 3-446-18668-9.Здесь: Exm.5.4.10, стр.205-206
10. Weisstein, Eric W. "Matrix Multiplication". mathworld.wolfram.com . Получено 2020-09-06 .
11. Липшуц, С.; Липсон, М. (2009). "2". Линейная алгебра . Очерки Шаума (4-е изд.). McGraw Hill (США). ISBN 978-0-07-154352-1.
12. Хорн, Джонсон (2013). "Глава 0". Матричный анализ (2-е изд.). Cambridge University Press. ISBN 978-0-521-54823-6.
13. Ху, TC ; Шинг, М.-Т. (1982). «Вычисление матричных цепных произведений, часть I» (PDF) . Журнал SIAM по вычислениям . 11 (2): 362–373. CiteSeerX 10.1.1.695.2923 . doi :10.1137/0211028. ISSN  0097-5397. 
14. Ху, TC ; Шинг, М.-Т. (1984). «Вычисление матричных цепных произведений, часть II» (PDF) . SIAM Journal on Computing . 13 (2): 228–251. CiteSeerX 10.1.1.695.4875 . doi :10.1137/0213017. ISSN  0097-5397. 
15. Мотвани, Раджив ; Рагхаван, Прабхакар (1995). Рандомизированные алгоритмы. Cambridge University Press. стр. 280. ISBN 9780521474658.
16. Фолькер Штрассен (август 1969 г.). «Исключение по Гауссу не является оптимальным». Числовая математика . 13 (4): 354–356. дои : 10.1007/BF02165411. S2CID  121656251.
17. C.-C. Chou и Y.-F. Deng и G. Li и Y. Wang (1995). "Parallelizing Strassen's Method for Matrix Multiplication on Distributed-Memory MIMD Architectures" (PDF) . Computers Math. Applic . 30 (2): 49–69. doi :10.1016/0898-1221(95)00077-C.
18. Василевска Уильямс, Вирджиния; Сюй, Иньчжань; Сюй, Цзысюань; Чжоу, Жэньфэй. Новые границы для умножения матриц: от альфы до омеги . Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2024 года. стр. 3792–3835. arXiv : 2307.07970 . doi :10.1137/1.9781611977912.134.
19. Надис, Стив (7 марта 2024 г.). «Новый прорыв приближает матричное умножение к идеалу» . Получено 09.03.2024 .
20. то есть, за время n ^2+f(n) для некоторой функции f с f ( n ) → 0 при n →∞

Ссылки

• Генри Кон, Роберт Клейнберг , Балаж Сзегеди и Крис Уманс. Групповые теоретико-алгоритмы для умножения матриц. arXiv :math.GR/0511460. Труды 46-го ежегодного симпозиума по основам компьютерной науки , 23–25 октября 2005 г., Питтсбург, Пенсильвания, IEEE Computer Society, стр. 379–388.
• Генри Кон, Крис Уманс. Теоретико-групповой подход к быстрому умножению матриц. arXiv :math.GR/0307321. Труды 44-го ежегодного симпозиума IEEE по основам компьютерной науки , 11–14 октября 2003 г., Кембридж, Массачусетс, IEEE Computer Society, стр. 438–449.
• Копперсмит, Д.; Виноград, С. (1990). «Умножение матриц с помощью арифметических прогрессий». J. Symbolic Comput . 9 (3): 251–280. doi : 10.1016/s0747-7171(08)80013-2 .
• Хорн, Роджер А.; Джонсон, Чарльз Р. (1991), Темы анализа матриц , Cambridge University Press , ISBN 978-0-521-46713-1
• Кнут, Д.Э. , Искусство программирования . Том 2: Получисленные алгоритмы . Addison-Wesley Professional; 3-е издание (14 ноября 1997 г.). ISBN 978-0-201-89684-8 . С. 501. 
• Press, William H.; Flannery, Brian P.; Teukolsky, Saul A .; Vetterling, William T. (2007), Numerical Recipes: The Art of Scientific Computing (3-е изд.), Cambridge University Press , ISBN 978-0-521-88068-8.
• Ран Раз . О сложности матричного произведения. В трудах тридцать четвертого ежегодного симпозиума ACM по теории вычислений. ACM Press, 2002. doi :10.1145/509907.509932.
• Робинсон, Сара, На пути к оптимальному алгоритму умножения матриц, SIAM News 38(9), ноябрь 2005 г. PDF
• Штрассен, Фолькер, Гауссово исключение не является оптимальным , Numer. Math. 13, стр. 354–356, 1969.
• Styan, George PH (1973), «Произведения Адамара и многомерный статистический анализ» (PDF) , Линейная алгебра и ее приложения , 6 : 217–240, doi : 10.1016/0024-3795(73)90023-2
• Уильямс, Вирджиния Василевска (2012-05-19). "Умножение матриц быстрее, чем Coppersmith-Winograd". Труды 44-го симпозиума по теории вычислений - STOC '12 . ACM. стр. 887–898. CiteSeerX  10.1.1.297.2680 . doi :10.1145/2213977.2214056. ISBN 9781450312455. S2CID  14350287.