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

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

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