В математике , особенно в линейной алгебре , умножение матриц — это бинарная операция , которая создает матрицу из двух матриц. Для умножения матриц количество столбцов в первой матрице должно быть равно количеству строк во второй матрице. Результирующая матрица, известная как матричное произведение , имеет количество строк первой и количество столбцов второй матрицы. Произведение матриц A и B обозначается как AB . [1]
Умножение матриц было впервые описано французским математиком Жаком Филиппом Мари Бине в 1812 году [2] для представления композиции линейных карт , представленных матрицами. Таким образом, умножение матриц является основным инструментом линейной алгебры и поэтому имеет многочисленные применения во многих областях математики, а также в прикладной математике , статистике , физике , экономике и технике . [3] [4]
Вычисление матричных произведений является центральной операцией во всех вычислительных приложениях линейной алгебры.
Обозначения
В этой статье будут использоваться следующие обозначения: матрицы обозначаются заглавными буквами, выделенными жирным шрифтом, например A ; векторы выделены строчными буквами и жирным шрифтом, например a ; а записи векторов и матриц выделены курсивом (это числа из поля), например A и a . Обозначение индекса часто является самым ясным способом выражения определений и используется в качестве стандарта в литературе. Запись в строке i , столбце j матрицы A обозначается ( A ) ij , A ij или a ij . Напротив, один индекс, например A 1 , A 2 , используется для выбора матрицы (а не элемента матрицы) из набора матриц.
Определение
Если A — матрица размера m × n , а B — матрица размера n × p ,
произведение C = ABm × p [5] [6] [7] [8]
i = 1,..., mj = 1,..., p
То есть запись продукта получается путем почленного умножения записей i -й строки A и j -го столбца B и суммирования этих n произведений. Другими словами, это скалярное произведение i - й строки A и j -го столбца B.
Следовательно, AB также можно записать как
Таким образом, произведение AB определяется тогда и только тогда, когда количество столбцов в A равно количеству строк в B , [1] в данном случае n .
В большинстве сценариев записи представляют собой числа, но они могут быть любыми математическими объектами , для которых определены сложение и умножение, которые являются ассоциативными и такими, что сложение является коммутативным , а умножение является распределительным по отношению к сложению. . В частности, записи сами могут быть матрицами (см. блочную матрицу ).
Иллюстрация
На рисунке справа схематически показано произведение двух матриц A и B , показывая, как каждое пересечение в матрице произведения соответствует строке A и столбцу B.
Значения на пересечениях, отмеченных кружками на рисунке справа, следующие:
Фундаментальные приложения
Исторически умножение матриц было введено для облегчения и уточнения вычислений в линейной алгебре . Эта сильная связь между умножением матриц и линейной алгеброй остается фундаментальной во всей математике, а также в физике , химии , технике и информатике .
Линейные карты
Если векторное пространство имеет конечный базис , каждый его вектор однозначно представлен конечной последовательностью скаляров, называемой координатным вектором , элементами которого являются координаты вектора в базисе. Эти координатные векторы образуют другое векторное пространство, изоморфное исходному векторному пространству. Координатный вектор обычно организуется как матрица-столбец (также называемая вектор -столбец ), которая представляет собой матрицу только с одним столбцом. Итак, вектор-столбец представляет собой как вектор координат, так и вектор исходного векторного пространства.
Линейное отображение A из векторного пространства размерности n в векторное пространство размерности m отображает вектор-столбец.
на вектор-столбец
Таким образом, линейное отображение A определяется матрицей
и сопоставляет вектор-столбец с матричным произведением
Если B — еще одна линейная карта из предыдущего векторного пространства размерности m в векторное пространство размерности p , она представлена матрицей. Непосредственное вычисление показывает, что матрица составной карты является матричным произведением. Общая формула ), определяющая композиция функций рассматривается здесь как частный случай ассоциативности матричного произведения (см. § Ассоциативность ниже):
обеспечить количество основных товаров, необходимых для данного количества промежуточных товаров, и количество промежуточных товаров, необходимых для данного количества конечной продукции, соответственно. Например, для производства одной единицы промежуточного товара , одной единицы основного товара , необходимы две единицы , никаких единиц и одна единица , что соответствует первому столбцу .
Используя умножение матриц, вычислите
эта матрица напрямую показывает количество основных товаров, необходимых для данного количества конечной продукции. Например, нижняя левая запись вычисляется как , что отражает то, что для производства одной единицы необходимы единицы . Действительно, одна единица нужна для , по одной для каждого из двух и для каждой из четырех единиц, входящих в единицу, см. рисунок.
Чтобы произвести, например, 100 единиц конечного продукта , 80 единиц и 60 единиц , необходимое количество основных товаров можно вычислить как
то есть нужны единицы , единицы , единицы , единицы . Аналогично, матрица продуктов может использоваться для расчета необходимого количества основных товаров для других данных о количестве конечного товара. [9]
где обозначает сопряженное транспонирование ( сопряженное транспонирование или, что эквивалентно, транспонирование сопряженного).
Общие свойства
Умножение матриц имеет некоторые общие свойства с обычным умножением . Однако умножение матриц не определено, если число столбцов первого сомножителя отличается от количества строк второго сомножителя, и оно некоммутативно [10] , даже если произведение остается определенным после изменения порядка сомножителей. . [11] [12]
Некоммутативность
Операция является коммутативной , если для данных двух элементов A и B такое, что произведение определено, то оно также определено и
Если A и B являются матрицами соответствующих размеров и , то определяется, если , и определяется, если . Следовательно, если один из продуктов определен, другой определять не требуется. Если , два продукта определены, но имеют разные размеры; поэтому они не могут быть равными. Только если , то есть если A и B — квадратные матрицы одинакового размера, оба произведения определены и имеют одинаковый размер. Даже в этом случае в целом
Например
но
Этот пример можно расширить, чтобы показать, что если A является матрицей с элементами в поле F , то для каждой матрицы B с элементами в F тогда и только тогда, когда где и I является единичной матрицей . Если вместо поля предполагается принадлежность записей кольцу , то нужно добавить условие принадлежности c центру кольца .
Один особый случай, когда коммутативность действительно имеет место, - это когда D и E представляют собой две (квадратные) диагональные матрицы (одного и того же размера); тогда DE = ED . [10] Опять же, если матрицы расположены над общим кольцом, а не над полем, соответствующие элементы в каждой из них также должны коммутировать друг с другом, чтобы это выполнялось.
Дистрибутивность
Матричное произведение является дистрибутивным относительно сложения матриц . То есть, если A , B , C , D являются матрицами соответствующих размеров m × n , n × p , n × p и p × q , имеет место (левая дистрибутивность)
и (правая дистрибутивность)
[10]
Это следует из распределения коэффициентов по формуле
Произведение со скаляром
Если A — матрица, а c — скаляр, то матрицы и получаются умножением всех элементов A на c слева или справа . Если скаляры обладают коммутативным свойством , то
Если произведение определено (то есть количество столбцов A равно количеству строк B ), то
и
Если скаляры обладают свойством коммутативности, то все четыре матрицы равны. В более общем смысле, все четыре равны, если c принадлежит центру кольца , содержащего элементы матриц, потому что в этом случае c X = X c для всех матриц X .
Эти свойства являются результатом билинейности произведения скаляров:
Транспонировать
Если скаляры обладают коммутативным свойством , транспонирование произведения матриц является произведением транспонированных множителей в обратном порядке. То есть
где T обозначает транспонирование, то есть замену строк и столбцов.
Это тождество не справедливо для некоммутативных элементов, поскольку порядок между элементами A и B меняется на обратный, когда расширяется определение матричного произведения.
Это является результатом применения к определению матричного произведения того факта, что сопряженная сумма является суммой сопряженных слагаемых, а сопряженная часть произведения является произведением сопряженных множителей.
Транспозиция действует на индексы статей, а сопряжение действует независимо на сами записи. В результате, если A и B имеют комплексные записи, то
где † обозначает сопряженное транспонирование (сопряженное транспонирование или, что эквивалентно, транспонирование сопряженного).
Ассоциативность
Учитывая три матрицы A , B и C , произведения ( AB ) C и A ( BC ) определяются тогда и только тогда, когда количество столбцов A равно количеству строк B , а количество столбцов B равно числу строк C (в частности, если определено одно из произведений, то определено и другое). В этом случае имеется ассоциативное свойство
Как и любая ассоциативная операция, это позволяет опустить круглые скобки и записать приведенные выше произведения в виде
Это естественным образом распространяется на произведение любого количества матриц при условии совпадения размеров. То есть, если A 1 , A 2 , ..., An являются матрицами такими, что количество столбцов A i равно количеству строк A i + 1 для i = 1, ..., n – 1 , тогда продукт
определена и не зависит от порядка умножения , если порядок матриц сохраняется фиксированным.
Эти свойства можно доказать с помощью простых, но сложных манипуляций с суммированием . Этот результат также следует из того, что матрицы представляют собой линейные отображения . Следовательно, ассоциативное свойство матриц — это просто частный случай ассоциативного свойства композиции функций .
Сложность вычислений зависит от скобок
Хотя результат последовательности произведений матриц не зависит от порядка выполнения операции (при условии, что порядок матриц не изменяется), сложность вычислений может существенно зависеть от этого порядка.
Например, если 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 выбор наилучшего порядка имеет сложность
В продукт определен для каждой пары матриц. Это создает кольцо , которое имеет единичную матрицу I в качестве единичного элемента (матрица, диагональные элементы которой равны 1, а все остальные элементы равны 0) . Это кольцо также является ассоциативной R -алгеброй .
Если n > 1 , многие матрицы не имеют мультипликативной обратной . Например, матрица, в которой все элементы строки (или столбца) равны 0, не имеет обратной. Если она существует, обратная матрица A обозначается A −1 и, таким образом, проверяется
Произведение матриц обратимо тогда и только тогда, когда обратим каждый множитель. В этом случае имеется
Когда R коммутативно и, в частности, когда оно является полем, определитель произведения является произведением определителей. Поскольку определители являются скалярами, а скаляры коммутируют, то имеем
Другие инварианты матрицы ведут себя с произведениями не так хорошо. Тем не менее, если R коммутативно, AB и BA имеют одинаковый след , один и тот же характеристический полином и одни и те же собственные значения с одинаковыми кратностями. Однако собственные векторы, как правило, различны, если AB ≠ BA .
Полномочия матрицы
Квадратную матрицу можно возвести в любую неотрицательную целую степень, многократно умножив ее на себя так же, как и для обычных чисел. То есть,
Для вычисления k- й степени матрицы требуется в k – 1 раз больше времени, чем умножение одной матрицы, если это делается с помощью тривиального алгоритма (повторное умножение). Поскольку это может занять очень много времени, обычно предпочитают использовать возведение в степень возведением в квадрат , которое требует менее 2 log 2 k умножений матриц и, следовательно, намного более эффективно.
Самый простой случай возведения в степень — это случай диагональной матрицы . Поскольку произведение диагональных матриц представляет собой простое умножение соответствующих диагональных элементов вместе, k -я степень диагональной матрицы получается путем возведения элементов в степень k :
Абстрактная алгебра
Определение матричного произведения требует, чтобы элементы принадлежали полукольцу, и не требует, чтобы умножение элементов полукольца было коммутативным . Во многих приложениях элементы матрицы принадлежат полю, хотя тропическое полукольцо также является распространенным выбором для задач о кратчайшем пути графа . [13] Даже в случае матриц над полями произведение вообще не является коммутативным, хотя оно ассоциативно и дистрибутивно относительно сложения матриц . Единичные матрицы (которые представляют собой квадратные матрицы , элементы которых равны нулю вне главной диагонали и 1 на главной диагонали) являются единичными элементами матричного произведения. Отсюда следует, что матрицы размера n × n над кольцом образуют кольцо, которое некоммутативно, за исключением случаев, когда n = 1 и основное кольцо коммутативно.
Квадратная матрица может иметь мультипликативную обратную матрицу , называемую обратной матрицей . В общем случае, когда элементы принадлежат коммутативному кольцу R , матрица имеет обратную тогда и только тогда, когда ее определитель имеет мультипликативную обратную в R. Определителем произведения квадратных матриц является произведение определителей множителей. Матрицы размера n × n , имеющие обратную форму, при умножении матриц образуют группу , подгруппы которой называются группами матриц . Многие классические группы (включая все конечные группы ) изоморфны матричным группам; это отправная точка теории представлений групп .
Вычислительная сложность
Алгоритм умножения матриц , вытекающий из определения, в худшем случае требует умножения и сложения скаляров для вычисления произведения двух квадратных матриц размера n × n . Таким образом, его вычислительная сложность равна , в модели вычислений , для которой скалярные операции занимают постоянное время.
Довольно удивительно, что эта сложность не является оптимальной, как показал в 1969 году Фолькер Штрассен , который предоставил алгоритм, теперь называемый алгоритмом Штрассена , со сложностью [14].
Алгоритм Штрассена можно распараллелить для дальнейшего улучшения производительности. [15]
По состоянию на декабрь 2020 года лучший рецензируемый алгоритм умножения матриц принадлежит Джошу Алману и Вирджинии Василевской Уильямс и имеет сложность O ( n 2,3728596 ) . [16]
Неизвестно, можно ли выполнить умножение матриц за n 2 + o(1) время. [17] Это было бы оптимально, поскольку необходимо прочитать элементы матрицы, чтобы умножить ее на другую матрицу.[update]
Поскольку умножение матриц составляет основу многих алгоритмов, а многие операции над матрицами даже имеют ту же сложность, что и умножение матриц (с точностью до мультипликативной константы), вычислительная сложность умножения матриц проявляется во всей числовой линейной алгебре и теоретической информатике .
Произведение Адамара двух матриц одинакового размера, в результате чего получается матрица одинакового размера, которая представляет собой произведение по каждому элементу.
^ Райли, К.Ф.; Хобсон, член парламента; Бенс, SJ (2010). Математические методы в физике и технике . Издательство Кембриджского университета. ISBN978-0-521-86153-3.
^ Адамс, РА (1995). Исчисление, полный курс (3-е изд.). Эддисон Уэсли. п. 627. ИСБН0-201-82823-5.
^ Хорн, Джонсон (2013). Матричный анализ (2-е изд.). Издательство Кембриджского университета. п. 6. ISBN978-0-521-54823-6.
^ Питер Стингл (1996). Mathematik für Fachhochschulen – Technik und Informatik (на немецком языке) (5-е изд.). Мюнхен : Карл Хансер Верлаг . ISBN3-446-18668-9.Здесь: Пример.5.4.10, стр.205-206.
^ abc Вайсштейн, Эрик В. «Умножение матриц». mathworld.wolfram.com . Проверено 6 сентября 2020 г.
^ Фолькер Штрассен (август 1969 г.). «Исключение по Гауссу не является оптимальным». Нумерическая математика . 13 (4): 354–356. дои : 10.1007/BF02165411. S2CID 121656251.
^ К.-К. Чжоу и Ю.-Ф. Дэн, Г. Ли и Ю. Ван (1995). «Распараллеливание метода Штрассена для умножения матриц в архитектурах MIMD с распределенной памятью» (PDF) . Компьютеры Математика. Приложение . 30 (2): 49–69. дои : 10.1016/0898-1221(95)00077-C.
^ Алман, Джош; Уильямс, Вирджиния Василевска (2020), «Усовершенствованный лазерный метод и более быстрое умножение матриц», 32-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2021), arXiv : 2010.05846
^ то есть за время n 2+f(n) для некоторой функции f с f ( n ) → 0 при n → ∞
Рекомендации
Викискладе есть медиафайлы, связанные с умножением матриц .
В Wikibook Linear Algebra есть страница на тему: Умножение матриц.
В Wikibook Applicable Mathematics есть страница на тему: Умножение матриц.
Генри Кон, Роберт Кляйнберг , Балаж Сегеди и Крис Уманс. Теоретико-групповые алгоритмы умножения матриц. 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 .
Ран Раз . О сложности матричного произведения. В материалах тридцать четвертого ежегодного симпозиума ACM по теории вычислений. ACM Press, 2002. doi : 10.1145/509907.509932.
Робинсон, Сара, К оптимальному алгоритму умножения матриц, SIAM News 38 (9), ноябрь 2005 г. PDF.
Штрассен, Волкер, Исключение по Гауссу не оптимально , Числ. Математика. 13, с. 354-356, 1969.
Стян, Джордж П.Х. (1973), «Произведение Адамара и многомерный статистический анализ» (PDF) , Линейная алгебра и ее приложения , 6 : 217–240, doi : 10.1016/0024-3795(73)90023-2
Уильямс, Вирджиния Василевска (19 мая 2012 г.). «Умножение матриц быстрее, чем медник-виноград». Материалы 44-го симпозиума по теории вычислений - STOC '12 . АКМ. стр. 887–898. CiteSeerX 10.1.1.297.2680 . дои : 10.1145/2213977.2214056. ISBN 9781450312455. S2CID 14350287.