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

[yaden]

Здравствуйте!
Почему перемножение матриц вычисляется по такой формуле, а никак иначе?
$c_{ij} = \sum_{r=1}^m a_{ir}b_{rj} $

[alcoholist]

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

[Евгений Машеров]

Вообще-то есть разные способы ввести произведение матриц. Это, "строка на столбец", просто самое практически востребованное.

[yaden]

Евгений Машеров в сообщении #1136374 писал(а):

Вообще-то есть разные способы ввести произведение матриц. Это, "строка на столбец", просто самое практически востребованное.

Можете, пожалуйста, рассказать подробнее. Не может же "строка на столбец" взяться с неба:)

[Евгений Машеров]

(Оффтоп)

Командир древнегреческой фаланги решает сложную математическую задачу: k человек получают жалование по n оболов хлеба в день. Сколько всего надо? Ответ на этот вопрос - произведение k на n.
Однако военная наука усовершенствуется, в войске служат разные воины, конные и пешие, разного чина и т.п., а воинский паёк включает не один хлеб, а и мясо, и овощи, и вино, и деньгами "на соль" (saldarii), а конному ещё овёс и сено положено. И войско уже не монолитная фаланга, а разбито на отдельные подразделения.
Личный состав командир легиона записал в виде таблицы - сколько в каждом подразделении воинов каждого рода, а Сенат утвердил другую таблицу - сколько чего кому положено. А гражданский спец-интеллектуал при легионе, трибун латиклавариус, должен посчитать, что какому подразделению выдать. Как изучавший философию у лучших греческих философов, он догадывается, что умножать надо. Но уже не число на число, а таблицу на таблицу. Поэлементно умножил - непонятно что получил, попробовал для другого легиона - там вообще поэлементного умножения не получается, разные количества строк и столбцов в таблицах. Пока не догадался, что умножать надо число воинов определённой категории в подразделении на норму выдачи данного вида довольствия по этой категории, и все произведения по этому подразделению просуммировать. Тогда получится потребность этого подразделения в данном довольствии. Строка на столбец и просуммировать.

[Евгений Машеров]

Теперь о разных произведениях.
По Адамару:
- перемножаются элементы, стоящие в одинаковых позициях и произведение записывается на ту же позицию $c_{i,j}=a_{i,j}b_{i.j}$ Часто реализовано во многих программных системах. Сомножители должны иметь одинаковые числа строк и столбцов.
По Фробениусу:
Сумма произведений элементов, стоящих на одинаковых позициях.
По Кронекеру:
Матрицы размерностей m на n одна и p на q вторая при умножении дадут матрицу $mp$ на $nq$, состоящую из клеток p на q, равных второй матрице, умноженной на соответствующий элемент первой. Обобщением умножения по Кронекеру является умножение по Трейси-Сингху и по Кхатри-Рао.
Краковское произведение:
Для матриц A и B оно равно $B^TA$, где перемножение транспонированной матрицы B на A делается по обычным правилам матричного умножения.

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

[arseniiv]

Тут можно добавить, что, так же как обычное произведение — это следствие того, что используемые матрицы — матрицы каких-то линейных операторов, произведение Кронекера — это просто тензорное произведение двух тензоров второго ранга (не важно, сколько раз ковариантными и сколько контравариантными) с данными матрицами, хотя матрица после этого и «сплющена», а на самом деле она должна бы быть четырёхмерной. Произведение Фробениуса будет просто скалярным произведением, выраженным в базисе из матриц, у которых все элементы нулевые кроме одной единицы. Произведение Адамара — обычное поднятие произведения на $A$ в произведение на функциях $X\to A$. А вот краковское самому интересно чем мотивируется.

[yaden]

Большое спасибо всем отписавшимся в теме)

[Евгений Машеров]

Насколько я понял, "краковское произведение" ввёл известный польский астроном Банахевич для упрощения ручных расчётов (умножение получается "столбец на столбец", что должно снижать вероятность ошибки из-за путаницы в номерах строк), что в 1930-е представляло известную пользу. Позже, в 1950-е интерес возобновился, в связи с использованием внешней памяти последовательного доступа (лент и т.п.) и ограниченностью оперативной, поскольку такое умножение могло быть реализовано с более эффективным доступом (уменьшая количество перемоток ленты), но с развитием вычтехники он угас. Сейчас это скорее математический курьёз, упоминаемый, как пример практически полезного неассоциативного умножения.

[venco]

Евгений Машеров в сообщении #1136622 писал(а):

Насколько я понял, "краковское произведение" ввёл известный польский астроном Банахевич для упрощения ручных расчётов (умножение получается "столбец на столбец", что должно снижать вероятность ошибки из-за путаницы в номерах строк), что в 1930-е представляло известную пользу. Позже, в 1950-е интерес возобновился, в связи с использованием внешней памяти последовательного доступа (лент и т.п.) и ограниченностью оперативной, поскольку такое умножение могло быть реализовано с более эффективным доступом (уменьшая количество перемоток ленты), но с развитием вычтехники он угас. Сейчас это скорее математический курьёз, упоминаемый, как пример практически полезного неассоциативного умножения.

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

[Евгений Машеров]

Ну, под "интерес угас" я имел в виду, что уже не вводится, как самостоятельный объект, оптимизированная последовательность вычислений определяется через транспонирование и обычное умножение. Хотя вот даже монография недавняя есть:

Цитата:

Cracovian Algebra

Retail Price: $120.00

Cracovian Algebra

Authors: Kociñski, Jerzy

Book Description:
Cracovians are matrices with a redefined product, namely, the row-by-column product is replaced by the column-by-column product (or, alternatively by the row-by-row product). This alteration in the product definition implies that the multiplication of Cracovians is noncommutative and nonassociative. An exposition of cracovian algebra on “Cracovian Calculus”, and on the original papers of Banachiewics and his coworkers, together with applications to solutions of Systems of Linear Equations and to Spherical Polygonometry represents the main subjects of this book. The last three sections contain also new applications of cracovian algebra.

Table of Contents:
Preface; Chapter 1. Basic Definitions and Properties; Chapter 2. Division of Cracovians and Solutions of Systems of Linear Equations; Chapter 3. The Inverse Cracovian; Chapter 4. The Cracovian Square Root; Chapter 5. Cracovian and Matrix Expressions in Linear Algebra; Chapter 6. Rotation Cracovians; Chapter 7. An Outlook on Quasigroups; Index.

Binding: Hardcover
Pub. Date: 2004
ISBN: 1-59454-105-1

Но в Сети не нашёл (а платить сто с лишним баксов за удовлетворение случайного любопытства амфибиогенная асфиксия не даёт), так что оценить, историко-математическая ли, или с практическим выходом, не могу.

[Chifu]

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

[Евгений Машеров]

В порядке гипотезы - отличие расположения элементов массива в памяти в Фортране (по столбцам) в отличие от последующих языков программирования могло быть связано с интересом к такому умножению.
А угасание интереса к нему могло быть обусловлено его неассоциативностью, что повышает вероятность ошибки не при вычислениях (которыми занимается машина), а при аналитических выкладках.
Сейчас оно осталось разве что, как пример квазигруппы. Тогда как "по Адамару" и "по Кронекеру" имеют практическое применение, хотя и меньшее, чем "обычное матричное умножение".

[arseniiv]

Chifu в сообщении #1136686 писал(а):

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

Ни с той, ни с другой. Разумеется, операций будет столько же. venco ведь выше написал, с какой. Менять порядок доступа как раз не очень осмысленно.

[Chifu]

arseniiv в сообщении #1136749 писал(а):

Chifu в сообщении #1136686 писал(а):

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

Ни с той, ни с другой. Разумеется, операций будет столько же. venco ведь выше написал, с какой. Менять порядок доступа как раз не очень осмысленно.

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