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

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

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

В математике , особенно в линейной алгебре , умножение матриц — это бинарная операция , которая создает матрицу из двух матриц. Для умножения матриц количество столбцов в первой матрице должно быть равно количеству строк во второй матрице. Результирующая матрица, известная как матричное произведение , имеет количество строк первой и количество столбцов второй матрицы. Произведение матриц 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 ,

$${\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}}}$$

произведение C = ABm × p ^{[5] [6] [7] [8]}

$${\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},}$$

i = 1,..., mj = 1,..., p

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

Следовательно, 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 .

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

Иллюстрация

На рисунке справа схематически показано произведение двух матриц 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 являются матрицами соответствующих размеров и , то определяется, если , и определяется, если . Следовательно, если один из продуктов определен, другой определять не требуется. Если , два продукта определены, но имеют разные размеры; поэтому они не могут быть равными. Только если , то есть если A и B — квадратные матрицы одинакового размера, оба произведения определены и имеют одинаковый размер. Даже в этом случае в целом ${\displaystyle m\times n}$ ${\displaystyle p\times q}$ ${\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 является матрицей с элементами в поле F , то для каждой матрицы B с элементами в F тогда и только тогда, когда где и I является единичной матрицей . Если вместо поля предполагается принадлежность записей кольцу , то нужно добавить условие принадлежности c центру кольца . ${\displaystyle n\times n}$ ${\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 ₂ , ..., An _{являются} матрицами такими, что количество столбцов 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 выбор наилучшего порядка имеет сложность ${\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}}.}$

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

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

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

Вычислительная сложность

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

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

Довольно удивительно, что эта сложность не является оптимальной, как показал в 1969 году Фолькер Штрассен , который предоставил алгоритм, теперь называемый алгоритмом Штрассена , со сложностью ^[14]. Алгоритм Штрассена можно распараллелить для дальнейшего улучшения производительности. ^[15] По состоянию на декабрь 2020 года лучший рецензируемый алгоритм умножения матриц принадлежит Джошу Алману и Вирджинии Василевской Уильямс и имеет сложность O ( n ^2,3728596 ) . ^[16] Неизвестно, можно ли выполнить умножение матриц за n ^{2 + o(1)} время. ^[17] Это было бы оптимально, поскольку необходимо прочитать элементы матрицы, чтобы умножить ее на другую матрицу. ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.8074}).}$^[update] ${\displaystyle n^{2}}$

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

Обобщения

К другим видам изделий из матриц относятся:

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

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

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

Примечания

1. Никамп, Дуэйн. «Умножение матриц и векторов». Математическое понимание . Проверено 6 сентября 2020 г.
2. О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. , «Жак Филипп Мари Бине», Архив истории математики MacTutor , Университет Сент-Эндрюс
3. Лернер, Р.Г .; Тригг, Г.Л. (1991). Энциклопедия физики (2-е изд.). Издатели ВХК. ISBN 978-3-527-26954-9.
4. Паркер, CB (1994). Энциклопедия физики МакГроу Хилла (2-е изд.). МакГроу-Хилл. ISBN 978-0-07-051400-3.
5. Липшуц, С.; Липсон, М. (2009). Линейная алгебра . Очерки Шаума (4-е изд.). МакГроу Хилл (США). стр. 30–31. ISBN 978-0-07-154352-1.
6. Райли, К.Ф.; Хобсон, член парламента; Бенс, SJ (2010). Математические методы в физике и технике . Издательство Кембриджского университета. ISBN 978-0-521-86153-3.
7. Адамс, РА (1995). Исчисление, полный курс (3-е изд.). Эддисон Уэсли. п. 627. ИСБН 0-201-82823-5.
8. Хорн, Джонсон (2013). Матричный анализ (2-е изд.). Издательство Кембриджского университета. п. 6. ISBN 978-0-521-54823-6.
9. Питер Стингл (1996). Mathematik für Fachhochschulen – Technik und Informatik (на немецком языке) (5-е изд.). Мюнхен : Карл Хансер Верлаг . ISBN 3-446-18668-9.Здесь: Пример.5.4.10, стр.205-206.
10. Вайсштейн, Эрик В. «Умножение матриц». mathworld.wolfram.com . Проверено 6 сентября 2020 г.
11. Липшуц, С.; Липсон, М. (2009). «2». Линейная алгебра . Очерки Шаума (4-е изд.). МакГроу Хилл (США). ISBN 978-0-07-154352-1.
12. Хорн, Джонсон (2013). «Глава 0». Матричный анализ (2-е изд.). Издательство Кембриджского университета. ISBN 978-0-521-54823-6.
13. Мотвани, Раджив ; Рагхаван, Прабхакар (1995). Рандомизированные алгоритмы. Издательство Кембриджского университета. п. 280. ИСБН 9780521474658.
14. Фолькер Штрассен (август 1969 г.). «Исключение по Гауссу не является оптимальным». Нумерическая математика . 13 (4): 354–356. дои : 10.1007/BF02165411. S2CID  121656251.
15. К.-К. Чжоу и Ю.-Ф. Дэн, Г. Ли и Ю. Ван (1995). «Распараллеливание метода Штрассена для умножения матриц в архитектурах MIMD с распределенной памятью» (PDF) . Компьютеры Математика. Приложение . 30 (2): 49–69. дои : 10.1016/0898-1221(95)00077-C.
16. Алман, Джош; Уильямс, Вирджиния Василевска (2020), «Усовершенствованный лазерный метод и более быстрое умножение матриц», 32-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2021), arXiv : 2010.05846
17. то есть за время n ^2+f(n) для некоторой функции f с f ( n ) → 0 при n → ∞

Рекомендации

• Генри Кон, Роберт Кляйнберг , Балаж Сегеди и Крис Уманс. Теоретико-групповые алгоритмы умножения матриц. arXiv : math.GR/0511460. Материалы 46-го ежегодного симпозиума по основам информатики , 23–25 октября 2005 г., Питтсбург, Пенсильвания, Компьютерное общество IEEE, стр. 379–388.
• Генри Кон, Крис Уманс. Теоретико-групповой подход к быстрому умножению матриц. arXiv : math.GR/0307321. Материалы 44-го ежегодного симпозиума IEEE по основам информатики , 11–14 октября 2003 г., Кембридж, Массачусетс, Компьютерное общество IEEE, стр. 438–449.
• Копперсмит, Д.; Виноград, С. (1990). «Умножение матриц с помощью арифметических прогрессий». J. Символические вычисления . 9 (3): 251–280. дои : 10.1016/s0747-7171(08)80013-2 .
• Хорн, Роджер А.; Джонсон, Чарльз Р. (1991), Темы матричного анализа , издательство Кембриджского университета , ISBN 978-0-521-46713-1
• Кнут, Д.Э. , Искусство компьютерного программирования , том 2: Получисловые алгоритмы . Аддисон-Уэсли Профессионал; 3-е издание (14 ноября 1997 г.). ISBN 978-0-201-89684-8 . стр. 501. 
• Пресс, Уильям Х.; Фланнери, Брайан П.; Теукольский, Саул А. ; Веттерлинг, Уильям Т. (2007), Численные рецепты: искусство научных вычислений (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.
• Штрассен, Волкер, Исключение по Гауссу не оптимально , Числ. Математика. 13, с. 354-356, 1969.
• Стян, Джордж П.Х. (1973), «Произведение Адамара и многомерный статистический анализ» (PDF) , Линейная алгебра и ее приложения , 6 : 217–240, doi : 10.1016/0024-3795(73)90023-2
• Уильямс, Вирджиния Василевска (19 мая 2012 г.). «Умножение матриц быстрее, чем медник-виноград». Материалы 44-го симпозиума по теории вычислений - STOC '12 . АКМ. стр. 887–898. CiteSeerX  10.1.1.297.2680 . дои : 10.1145/2213977.2214056. ISBN 9781450312455. S2CID  14350287.