Умножение матриц - Matrix multiplication

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

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

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

Обозначение

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

Определение

Если А является м × п матрица и B является п × п матрица

${ 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} конец {pmatrix}}}$

то матричный продукт C = AB (обозначается без знаков умножения и точек) определяется как м × п матрица^[6][7][8][9]

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

для я = 1, ..., м и j = 1, ..., п.

То есть запись ${ displaystyle c_ {ij}}$ продукта получается путем почтового умножения записей яй ряд А и j-й столбец B, и суммируя эти п продукты. Другими словами, ${ displaystyle c_ {ij}}$ это скалярное произведение из яй ряд А и j-й столбец B.^[1]

Следовательно, 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 определяется тогда и только тогда, когда количество столбцов в А равно количеству строк в B,^[2] в таком случае п.

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

Иллюстрация

На рисунке справа схематично показано произведение двух матриц. А и B, показывая, как каждое пересечение в матрице продукта соответствует строке А и столбец 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} & c_ {13} cdot & cdot & cdot cdot & c_ {32} & c_ {33} cdot & cdot & cdot конец {bmatrix}}}}$

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

${ displaystyle { begin {align} c_ {12} & = {a_ {11}} {b_ {12}} + {a_ {12}} {b_ {22}} c_ {33} & = {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}}.}$

Линейная карта А таким образом определяется матрицей

${ 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 это еще одна линейная карта из предыдущего векторного пространства размерности м, в векторное пространство размерности п, он представлен ${ 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},}$

где ${ displaystyle mathbf {x} ^ { mathsf {T}}}$ это вектор строки получено перенос ${ displaystyle mathbf {x}}$ и результирующая матрица 1 × 1 идентифицируется с ее уникальной записью.

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

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

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

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

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

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

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

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

Операция коммутативный если, учитывая два элемента А и B так что продукт ${ displaystyle mathbf {A} mathbf {B}}$ определено, то ${ Displaystyle mathbf {B} mathbf {A}}$ также определено, и ${ displaystyle mathbf {A} mathbf {B} = mathbf {B} mathbf {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 м = д = п = р}$, то есть если А и B находятся квадратные матрицы одинакового размера, оба продукта определены и имеют одинаковый размер. Даже в этом случае в целом

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

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

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

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

Матричное произведение распределительный относительно матрица сложения. То есть, если А, B, C, D матрицы соответствующих размеров м × п, п × п, п × п, и п × 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}.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Транспонирование действует на индексы записей, в то время как конъюгация действует независимо на сами записи. Получается, что если А и B иметь сложные записи, есть

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

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

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

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

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

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

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

${ Displaystyle prod _ {я = 1} ^ {n} mathbf {A} _ {i} = mathbf {A} _ {1} mathbf {A} _ {2} cdots mathbf {A} _ {n}}$

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

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

Сложность не ассоциативна

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

Например, если А, B и C матрицы соответствующих размеров 10×30, 30×5, 5×60, вычисление (AB)C потребности 10×30×5 + 10×5×60 = 4,500 умножения при вычислении А(до н.э) потребности 30×5×60 + 10×30×60 = 27,000 умножения.

Разработаны алгоритмы выбора оптимального порядка товаров, см. Умножение матричной цепочки. Когда число п матрицы возрастает, было показано, что выбор наилучшего порядка имеет сложность ${ 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}).}$

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

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

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

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

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

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

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

Другая матрица инварианты плохо себя вести с продуктами. Тем не менее, если р коммутативен, ${ displaystyle mathbf {AB}}$ и ${ displaystyle mathbf {BA}}$ имеют те же след, тоже самое характеристический многочлен, и то же самое собственные значения с одинаковой кратностью, но, вообще говоря, собственные векторы разные, если ${ displaystyle mathbf {AB} neq mathbf {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 журнала₂ k умножение матриц, и поэтому намного более эффективно.

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

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

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

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

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

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

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

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

Довольно удивительно, что эта сложность не оптимальна, как было показано в 1969 г. Фолькер Штрассен, который предоставил алгоритм, теперь называется Алгоритм Штрассена, со сложностью ${ displaystyle O (n ^ { log _ {2} 7}) приблизительно O (n ^ {2.8074}).}$^[14] Показатель степени сложности умножения матриц был улучшен в несколько раз,^{[15][16][17][18][19][20]} ведущий к Алгоритм Копперсмита – Винограда со сложностью О(п^2.3755) (1990).^[21][22] Этот алгоритм был немного улучшен в 2010 году Stothers до сложности О(п^2.3737),^[23] в 2013 г. Вирджиния Василевска Уильямс к О(п^2.3729),^[22] а в 2014 году Франсуа Ле Галл О(п^2.3728639).^[24] В 2020 году Джош Алман и Вирджиния Василевска Уильямс доработали это до окончательной (актуальной) сложности О(п^2.3728596).^[25]

В наибольшая нижняя граница для показателя степени алгоритма умножения матриц обычно называют ${ displaystyle omega}$. Надо ${ displaystyle 2 leq omega}$, потому что нужно читать ${ Displaystyle п ^ {2}}$ элементы матрицы для ее умножения на другую матрицу. Таким образом ${ displaystyle 2 leq omega <2.373}$. Неизвестно, были ли ${ displaystyle 2 < omega}$. Наибольшая известная нижняя оценка сложности матричного умножения равна Ω (п² журнал(п)), для ограниченного вида арифметические схемы, и это связано с Ран Раз.^[26]

Связанные сложности

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

Есть несколько преимуществ выражения сложности в терминах экспоненты ${ displaystyle omega}$ матричного умножения. Во-первых, если ${ displaystyle omega}$ улучшено, это автоматически улучшит известную верхнюю границу сложности многих алгоритмов. Во-вторых, в практических реализациях никогда не используется алгоритм умножения матриц, который имеет лучшую асимптотическую сложность, потому что константа, скрытая за нотация большой O слишком велик, чтобы сделать алгоритм конкурентоспособным для размеров матриц, которыми можно манипулировать на компьютере.^{[нужна цитата ]} Таким образом, выражая сложности с точки зрения ${ displaystyle omega}$ обеспечивают более реалистичную сложность, поскольку остаются в силе независимо от того, какой алгоритм выбран для вычисления матрицы.

Задачи, которые имеют ту же асимптотическую сложность, что и умножение матриц, включают: детерминант, инверсия матриц, Гауссово исключение (см. следующий раздел). Проблемы со сложностью, которые можно выразить с помощью ${ displaystyle omega}$ включать характеристический полином, собственные значения (но не собственные векторы), Нормальная форма Эрмита, и Нормальная форма Смита.^{[нужна цитата ]}

Обращение матрицы, определитель и исключение Гаусса

В своей статье 1969 года, где он доказал сложность ${ Displaystyle О (п ^ {2.807})}$ для вычисления матриц Штрассен доказал также, что инверсия матриц, детерминант и Гауссово исключение с точностью до мультипликативной константы одинаковые вычислительная сложность как матричное умножение. Доказательство не делает никаких предположений об используемом умножении матриц, за исключением того, что его сложность составляет ${ Displaystyle О (п ^ { omega})}$ для некоторых ${ displaystyle omega geq 2}$

Отправной точкой доказательства Штрассена является использование блочная матрица умножение. В частности, матрица четной размерности 2п×2п может быть разделен на четыре п×п блоки

${ displaystyle { begin {bmatrix} {A} & {B} {C} & {D} end {bmatrix}}.}$

В этой форме его обратное

${ displaystyle { begin {bmatrix} {A} & {B} {C} & {D} end {bmatrix}} ^ {- 1} = { begin {bmatrix} {A} ^ {- 1 } + {A} ^ {- 1} {B} ({D} - {CA} ^ {- 1} {B}) ^ {- 1} {CA} ^ {- 1} & - {A} ^ { -1} {B} ({D} - {CA} ^ {- 1} {B}) ^ {- 1} - ({D} - {CA} ^ {- 1} {B}) ^ { -1} {CA} ^ {- 1} & ({D} - {CA} ^ {- 1} {B}) ^ {- 1} end {bmatrix}},}$

при условии, что А и ${ displaystyle {D} - {CA} ^ {- 1} {B}}$ обратимы.

Таким образом, обратное 2п×2п Матрица может быть вычислена с помощью двух инверсий, шести умножений и четырех сложений или аддитивных обращений п×п матрицы. Отсюда следует, что, обозначая соответственно я(п), M(п) и А(п) = п² количество операций, необходимых для инвертирования, умножения и сложения п×п матрицы, есть

${ Displaystyle I (2n) leq 2I (n) + 6M (n) + 4A (n).}$

Если ${ Displaystyle п = 2 ^ {к},}$ можно применить эту формулу рекурсивно:

${ displaystyle { begin {align} I (2 ^ {k}) & leq 2I (2 ^ {k-1}) + 6M (2 ^ {k-1}) + 4A (2 ^ {k-1 }) & leq 2 ^ {2} I (2 ^ {k-2}) + 6 (M (2 ^ {k-1}) + 2M (2 ^ {k-2})) + 4 ( A (2 ^ {k-1}) + 2A (2 ^ {k-2})) & ldots end {align}}}$

Если ${ Displaystyle М (п) leq cn ^ { omega},}$ и ${ Displaystyle альфа = 2 ^ { omega} geq 4,}$ в конце концов получается

${ Displaystyle { begin {align} I (2 ^ {k}) & leq 2 ^ {k} I (1) + 6c ( alpha ^ {k-1} +2 alpha ^ {k-2} + cdots + 2 ^ {k-1} alpha ^ {0}) + k2 ^ {k + 1} & leq 2 ^ {k} + 6c { frac { alpha ^ {k} -2 ^ {k}} { alpha -2}} + k2 ^ {k + 1} & leq d (2 ^ {k}) ^ { omega}. end {align}}}$

для некоторой постоянной d.

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

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

Тот же аргумент применим к LU разложение, как если бы матрица А обратимо, равенство

${ displaystyle { begin {bmatrix} {A} & {B} {C} & {D} end {bmatrix}} = { begin {bmatrix} I & 0 CA ^ {- 1} & I end {bmatrix}} , { begin {bmatrix} A&B 0 & D-CA ^ {- 1} B end {bmatrix}}}$

определяет декомпозицию блочного LU, которая может рекурсивно применяться к ${ displaystyle A}$ и ${ displaystyle D-CA ^ {- 1} B,}$ для получения в конечном итоге истинного LU-разложения исходной матрицы.

Этот аргумент применим также к определителю, поскольку он является результатом разложения блочного LU, что

${ displaystyle det { begin {bmatrix} {A} & {B} {C} & {D} end {bmatrix}} = det (A) det (D-CA ^ {- 1} Б).}$

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

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

Заметки

использованная литература