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

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

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

Умножение матриц было впервые описано французским математиком Жаком Филиппом Мари Бине в 1812 году. для представления композиции линейных карт , представленных матрицами. Таким образом, умножение матриц является основным инструментом линейной алгебры и поэтому имеет многочисленные применения во многих областях математики, а также в прикладной математике , статистике , физике , экономике и технике . Вычисление матричных произведений — центральная операция во всех вычислительных приложениях линейной алгебры.

Обозначения

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

Определения

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

Если A — матрица размера m × n , а B — матрица размера n × p , $$\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 = AB (обозначается без знаков умножения и точек) определяется как m × p матрица размера $$\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}}$$такой, что $$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,..., m и j = 1,..., p .

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

Следовательно, AB также можно записать как $$\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 , в этом случае н .

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

Вектор матричного времени

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

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

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

Матрица векторных времен

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

Вектор раз вектор

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

Иллюстрация

На рисунке справа схематически показано произведение двух матриц A и B как каждое пересечение в матрице произведения соответствует строке A и столбцу B. , показывая , $${\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}}}$$

Значения на пересечениях, отмеченных кружками на рисунке справа, следующие: $${\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 отображает вектор-столбец.

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

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

$\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 определяется матрицей

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

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

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

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

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

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

См. также: Матрица вращения.

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

Состав ротации по $\alpha$ и это по $\beta$ тогда соответствует матричному произведению $${\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}},$$где соответствующие тригонометрические тождества для второго равенства используются .То есть композиция соответствует повороту на угол $\alpha +\beta$, как и ожидалось.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например

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

но

${\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 является ⁠ $n\times n$⁠ матрица с элементами в поле F , то $\mathbf {A} \mathbf {B} =\mathbf {B} \mathbf {A}$ за каждого ⁠ $n\times n$⁠ матрица B с элементами из F когда тогда и только тогда, $\mathbf {A} =c\,\mathbf {I}$ где ⁠ $c\in F$⁠ а я ⁠ , $n\times n$⁠ единичная матрица . Если вместо поля предполагается принадлежность записей кольцу , то нужно добавить условие c принадлежности центру кольца.

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

Дистрибутивность

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

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

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

$(\mathbf {B} +\mathbf {C} )\mathbf {D} =\mathbf {BD} +\mathbf {CD} .$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\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 выбор наилучшего порядка имеет сложность Было показано, что $O(n\log n).$

Приложение к сходству

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

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

Преобразования сходства отображают продукт в продукты, то есть

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

Фактически, у человека есть

$\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} ).$

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

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

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

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

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

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

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

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

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

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

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

Полномочия матрицы

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Вычислительная сложность умножения матриц

Информацию о методах реализации (в частности, параллельных и распределенных алгоритмах) см. в разделе «Алгоритм умножения матриц» .

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

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

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

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

Обобщения

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

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

См. также

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

Ссылки

• Генри Кон, Роберт Кляйнберг , Балаж Сегеди и Крис Уманс. Теоретико-групповые алгоритмы умножения матриц. 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 по теории вычислений. АКМ Пресс, 2002. дои : 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 .