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

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

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

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

• 1 Обозначение
• 2 Определение
  • 2.1 Иллюстрация
• 3 Основные приложения
  • 3.1 Линейные карты
  • 3.2 Система линейных уравнений
  • 3.3 Точечное произведение, билинейная форма и внутреннее произведение
• 4 Общие свойства
  • 4.1 Некоммутативность
  • 4.2 Распределительность
  • 4.3 Произведение со скаляром
  • 4.4 Транспонирование
  • 4.5 Комплексное сопряжение
  • 4.6 Ассоциативность
    • 4.6.1 Сложность не ассоциативна
    • 4.6.2 Применение к подобию
• 5 квадратных матриц
  • 5.1 Степени матрицы
• 6 Абстрактная алгебра
• 7 Вычислительная сложность
• 8 Обобщения
• 9 См. Также
• 10 заметок
• 11 Источники

В этой статье будут использоваться следующие условные обозначения: матрицы представлены заглавными буквами жирным шрифтом, например A ; векторы, выделенные строчными полужирными буквами, например a ; а элементы векторов и матриц выделены курсивом (поскольку они являются числами из поля), например A и a. Индексная нотация часто является самым ясным способом выражения определений и используется в литературе как стандарт. Элемент i, j матрицы A обозначается как ( A) ij, A ij или a ij, тогда как числовая метка (не элементы матрицы) в наборе матриц указывается только в нижнем индексе, например, A 1, A 2 и т. Д.

Если A - матрица размера m × n, а B - матрица размера n × p,

${\ displaystyle \ mathbf {A} = {\ begin {pmatrix} a_ {11} amp; a_ {12} amp; \ cdots amp; a_ {1n} \\ a_ {21} amp; a_ {22} amp; \ cdots amp; a_ {2n} \\\ vdots amp; \ vdots amp; \ ddots amp; \ vdots \\ a_ {m1} amp; a_ {m2} amp; \ cdots amp; a_ {mn} \\\ end {pmatrix}}, \ quad \ mathbf {B} = {\ begin {pmatrix} b_ {11} amp; b_ {12} amp; \ cdots amp; b_ {1p} \\ b_ {21} amp; b_ {22} amp; \ cdots amp; b_ {2p} \\\ vdots amp; \ vdots amp; \ ddots amp; \ vdots \\ b_ {n1 } amp; b_ {n2} amp; \ cdots amp; b_ {np} \\\ конец {pmatrix}}}$

матричное произведение С = АВ (обозначается без умножения знаков или точек) определяется, чтобы быть м × р матрица

${\ displaystyle \ mathbf {C} = {\ begin {pmatrix} c_ {11} amp; c_ {12} amp; \ cdots amp; c_ {1p} \\ c_ {21} amp; c_ {22} amp; \ cdots amp; c_ {2p} \\\ vdots amp; \ vdots amp; \ ddots amp; \ vdots \\ c_ {m1} amp; c_ {m2} amp; \ cdots amp; 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,..., m и j = 1,..., p.

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

Следовательно, AB можно также записать как

${\ displaystyle \ mathbf {C} = {\ begin {pmatrix} a_ {11} b_ {11} + \ cdots + a_ {1n} b_ {n1} amp; a_ {11} b_ {12} + \ cdots + a_ {1n } b_ {n2} amp; \ cdots amp; a_ {11} b_ {1p} + \ cdots + a_ {1n} b_ {np} \\ a_ {21} b_ {11} + \ cdots + a_ {2n} b_ {n1} amp; a_ {21} b_ {12} + \ cdots + a_ {2n} b_ {n2} amp; \ cdots amp; a_ {21} b_ {1p} + \ cdots + a_ {2n} b_ {np} \\\ vdots amp; \ vdots amp; \ ddots amp; \ vdots \\ a_ {m1} b_ {11} + \ cdots + a_ {mn} b_ {n1} amp; a_ {m1} b_ {12} + \ cdots + a_ {mn} b_ {n2} amp; \ cdots amp; a_ {m1} b_ {1p} + \ cdots + a_ {mn} b_ {np} \\\ end {pmatrix}}}$

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

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

Иллюстрация

Рисунке справа схематично иллюстрирует произведение двух матриц A и B, показывающий, как каждое пересечение в матрице продукта соответствует ряду А и столбец B.

${\ displaystyle {\ overset {4 \ times 2 {\ text {matrix}}} {\ begin {bmatrix} {a_ {11}} amp; {a_ {12}} \\\ cdot amp; \ cdot \\ {a_ { 31}} amp; {a_ {32}} \\\ cdot amp; \ cdot \\\ end {bmatrix}}} {\ overset {2 \ times 3 {\ text {matrix}}} {\ begin {bmatrix} \ cdot amp; {b_ {12}} amp; {b_ {13}} \\\ cdot amp; {b_ {22}} amp; {b_ {23}} \\\ end {bmatrix}}} = {\ overset {4 \ times 3 {\ text {matrix}}} {\ begin {bmatrix} \ cdot amp; c_ {12} amp; c_ {13} \\\ cdot amp; \ cdot amp; \ cdot \\\ cdot amp; c_ {32} amp; c_ {33} \\\ cdot amp; \ cdot amp; \ cdot \\\ конец {bmatrix}}}}$

Значения на пересечениях, отмеченных кружками:

${\ displaystyle {\ begin {align} c_ {12} amp; = {a_ {11}} {b_ {12}} + {a_ {12}} {b_ {22}} \\ c_ {33} amp; = {a_ {31}} {b_ {13}} + {a_ {32}} {b_ {23}} \ end {align}}}$

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

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

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

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

${\ 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} amp; a_ {12} amp; \ cdots amp; a_ {1n} \\ a_ {21} amp; a_ {22} amp; \ cdots amp; a_ {2n} \\\ vdots amp; \ vdots amp; \ ddots amp; \ vdots \\ a_ {m1} amp; a_ {m2} amp; \ cdots amp; 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 (В \ circ A) (\ mathbf {x}) = B (A (\ mathbf {x}))}$

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

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

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

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

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

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

Операция коммутативна, если для двух элементов 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 м \ раз п}$${\ 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 м = д = п = р}$

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

Например

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

но

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

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

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

Распределительность

Матричное произведение является распределительным по отношению к матричному сложению. То есть, если 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}.}$

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

${\ 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 с (\ mathbf {AB}) = (с \ mathbf {A}) \ mathbf {B}}$ а также ${\ displaystyle (\ mathbf {A} \ mathbf {B}) c = \ mathbf {A} (\ mathbf {B} 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 1, A 2,..., A n являются такими матрицами, что количество столбцов A i равно количеству строк A i + 1 для i = 1,..., n - 1, тогда продукт

${\ Displaystyle \ prod _ {я = 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 = 27000 умножений.

Были разработаны алгоритмы для выбора наилучшего порядка продуктов, см. Умножение цепочки матриц. Было показано, что при увеличении числа матриц n сложность выбора наилучшего порядка составляет${\ Displaystyle O (п \ журнал п).}$

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

Любая обратимая матрица определяет преобразование подобия (на квадратных матрицах того же размера, что и) ${\ 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}} _ {п} (R)}$

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

Если n gt; 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 2 k умножений матриц и, следовательно, намного более эффективно.

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

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

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

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

Основная статья: Вычислительная сложность умножения матриц О методах реализации (в частности, параллельных и распределенных алгоритмах) см. Алгоритм умножения матриц. Улучшение оценок показателя ω со временем для вычислительной сложности умножения матриц.${\ Displaystyle О (п ^ {\ omega})}$

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

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

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

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

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

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

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