Кронекер продукт - Kronecker product

По поводу кронекеровского произведения представлений симметрических групп см. Коэффициент Кронекера.

В математика, то Кронекер продукт, иногда обозначаемый ⊗,[1] является операция на двух матрицы произвольного размера, что дает блочная матрица. Это обобщение внешний продукт (который обозначается тем же символом) от векторов к матрицам, и дает матрицу тензорное произведение относительно стандартного выбора основа. Произведение Кронекера следует отличать от обычного матричное умножение, что является совершенно другой операцией. Произведение Кронекера также иногда называют матричным прямым произведением.[2]

Произведение Кронекера названо в честь немецкого математика. Леопольд Кронекер (1823-1891), хотя есть мало свидетельств того, что он был первым, кто определил и использовал это. Продукт Кронекера также называют Матрица Зефусса, после Иоганн Георг Зефус, который в 1858 г. описал эту матричную операцию, но в настоящее время наиболее широко используется произведение Кронекера.[3]

Определение

Если А является м × п матрица и B это п × q матрица, то произведение Кронекера А ⊗ B это вечера × qn блочная матрица:

более подробно:

Более компактно мы имеем

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

Если А и B представлять линейные преобразования V1 → W1 и V2 → W2соответственно, то А ⊗ B представляет тензорное произведение из двух карт, V1 ⊗ V2 → W1 ⊗ W2.

Примеры

По аналогии:

Характеристики

Связь с другими матричными операциями

  1. Билинейность и ассоциативность:

    Произведение Кронекера - это частный случай тензорное произведение, так что, это билинейный и ассоциативный:

    куда А, B и C матрицы, 0 - нулевая матрица, а k является скаляром.
  2. Не-коммутативный:

    В целом, А ⊗ B и B ⊗ А это разные матрицы. Тем не мение, А ⊗ B и B ⊗ А эквивалентны перестановкам, что означает, что существуют матрицы перестановок п и Q такой, что[4]

    Если А и B квадратные матрицы, то А ⊗ B и B ⊗ А даже перестановка похожий, что означает, что мы можем взять п = QТ.

    Матрицы п и Q идеальные матрицы тасования.[5] Идеальная матрица тасования Sр, д можно построить, взяв срезы яр единичная матрица, где .

    MATLAB двоеточие используется здесь для обозначения подматриц, и яр это р × р единичная матрица. Если и , тогда

  3. Свойство смешанного продукта:

    Если А, B, C и D матрицы такого размера, что можно сформировать матричные продукты AC и BD, тогда

    Это называется смешанная собственность, потому что он смешивает обычное матричное произведение и произведение Кронекера.

    Как непосредственное следствие,

    .

    В частности, используя транспонировать свойство снизу, это означает, что если

    и Q и U находятся ортогональный (или же унитарный ), тогда А также ортогонален (соответственно унитарен).
  4. Произведение Адамара (поэлементное умножение):

    Свойство смешанного продукта также работает для поэлементного продукта. Если А и C матрицы одинакового размера, B и D матрицы одинакового размера, то

  5. Обратное произведение Кронекера:

    Следует, что А ⊗ B является обратимый если и только если обе А и B обратимы, и в этом случае обратное дается формулой

    Свойство обратимого произведения выполняется для Псевдообратная матрица Мура – ​​Пенроуза также,[6] то есть

    На языке Теория категорий, свойство смешанного произведения кронекеровского произведения (и более общего тензорного произведения) показывает, что категория МатF матриц над поле F, на самом деле моноидальная категория, с объектами натуральные числа п, морфизмы п → м находятся п-к-м матрицы с записями в F, состав задается умножением матриц, стрелки идентичности просто п × п матрицы идентичности яп, а тензорное произведение дается произведением Кронекера.[7]

    МатF бетонный категория скелета для эквивалентная категория FinVectF конечномерных векторных пространств над F, объектами которого являются такие конечномерные векторные пространства V, стрелки F-линейные карты L : V → W, а тождественные стрелки - это тождественные отображения пространств. Эквивалентность категорий составляет одновременно выбор основы в конечномерном векторном пространстве V над F; элементы матриц представляют собой эти отображения относительно выбранных баз; и аналогично произведение Кронекера является представлением тензорное произведение в выбранных базах.
  6. Транспонировать:

    Транспонирование и сопряженная транспозиция распространяются по продукту Кронекера:

    и
  7. Детерминант:

    Позволять А быть п × п матрица и пусть B быть м × м матрица. потом

    Показатель в |А| это порядок B и показатель степени в |B| это порядок А.
  8. Сумма Кронекера и возведение в степень:

    Если А является п × п, B является м × м и яk обозначает k × k единичная матрица тогда мы можем определить то, что иногда называют Сумма Кронекера, ⊕, пользователем

    Это разные от прямая сумма двух матриц. Эта операция связана с тензорным произведением на Алгебры Ли.

    У нас есть следующая формула для матричная экспонента, что полезно при некоторых численных расчетах.[8]

    Суммы Кронекера естественно появляются в физика при рассмотрении ансамблей невзаимодействующих системы.[нужна цитата ] Позволять ЧАСя быть гамильтонианом я-я такая система. Тогда полный гамильтониан ансамбля равен

    .

Абстрактные свойства

  1. Спектр:

    Предположим, что А и B квадратные матрицы размера п и м соответственно. Позволять λ1, ..., λп быть собственные значения из А и μ1, ..., μм быть теми из B (перечислены согласно множественность ). Тогда собственные значения из А ⊗ B находятся

    Отсюда следует, что след и детерминант продукта Кронекера даются

  2. Особые значения:

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

    Аналогично обозначим ненулевые особые значения B к

    Тогда произведение Кронекера А ⊗ B имеет рАрB ненулевые особые значения, а именно

    Поскольку ранг матрицы равно количеству ненулевых сингулярных значений, находим, что

  3. Отношение к абстрактному тензорное произведение:

    Кронекеровское произведение матриц соответствует абстрактному тензорному произведению линейных отображений. В частности, если векторные пространства V, W, Икс, и Y иметь базы {v1, ..., vм}, {ш1, ..., шп}, {Икс1, ..., Иксd}, и {у1, ..., уе}, соответственно, а если матрицы А и B представляют собой линейные преобразования S : V → Икс и Т : W → Yсоответственно в соответствующих базисах, то матрица А ⊗ B представляет собой тензорное произведение двух карт, S ⊗ Т : V ⊗ W → Икс ⊗ Y относительно основы {v1 ⊗ ш1, v1 ⊗ ш2, ..., v2 ⊗ ш1, ..., vм ⊗ шп} из V ⊗ W и аналогично определенный базис Икс ⊗ Y со свойством, что А ⊗ B(vя ⊗ шj) = (Среднийя) ⊗ (Чбj), куда я и j являются целыми числами в правильном диапазоне.[9]

    Когда V и W находятся Алгебры Ли, и S : V → V и Т : W → W находятся Гомоморфизмы алгебр Ли, сумма Кронекера А и B представляет собой индуцированные гомоморфизмы алгебры Ли V ⊗ W → V ⊗ W.
  4. Отношении товары из графики:
    Произведение Кронекера матрицы смежности из двух графики матрица смежности граф тензорного произведения. В Сумма Кронекера матриц смежности двух графики матрица смежности Декартов граф произведения.[10]

Матричные уравнения

Произведение Кронекера можно использовать для получения удобного представления для некоторых матричных уравнений. Рассмотрим, например, уравнение AXB = C, куда А, B и C заданы матрицы, а матрица Икс является неизвестным. Мы можем использовать "vec-трюк", чтобы переписать это уравнение как

Здесь vec (Икс) обозначает векторизация матрицы ИКС, сформированный путем укладки столбцов Икс в один вектор столбца.

Теперь из свойств произведения Кронекера следует, что уравнение AXB = C имеет единственное решение тогда и только тогда, когда А и B неособые (Хорн и Джонсон 1991, Лемма 4.3.1).

Если Икс и AXB упорядочены по строкам в векторах-столбцах ты и vсоответственно, то (Джайн 1989, 2.8 Блочные матрицы и произведения Кронекера)

Причина в том, что

Приложения

Пример применения этой формулы см. В статье о Уравнение Ляпунова.Эта формула также помогает показать, что матричное нормальное распределение это частный случай многомерное нормальное распределение. Эта формула также полезна для представления 2D обработка изображений операции в матрично-векторной форме.

Другой пример - когда матрица может быть разложена на множители как Произведение Адамара, то умножение матриц можно выполнить быстрее с помощью приведенной выше формулы. Это можно применить рекурсивно, как это сделано в основание 2 БПФ и Быстрое преобразование Уолша – Адамара. Разделение известной матрицы на произведение Адамара двух меньших матриц известно как проблема «ближайшего произведения Кронекера» и может быть решена точно.[11] используя СВД. Оптимальное разделение матрицы на произведение Адамара, состоящее из более чем двух матриц, является сложной задачей и предметом текущих исследований; некоторые авторы называют это проблемой разложения на тензор.[12][13]

В сочетании с метод наименьших квадратов, продукт Кронекера можно использовать как точное решение проблема калибровки глаза.[14]

Связанные матричные операции

Две связанные матричные операции: Трейси-Сингх и Khatri – Rao продукты, которые работают на разделенные матрицы. Пусть м × п матрица А быть разделенным на мя × пj блоки Аij и п × q матрица B в пk × qℓ блоки Bkl, конечно Σя мя = м, Σj пj = п, Σk пk = п и Σℓ qℓ = q.

Продукт Трейси – Сингха

В Продукт Трейси – Сингха определяется как[15][16]

что означает, что (ij) -й подблок mp × nq товар А B это мя п × пj q матрица Аij B, из которых (kℓ) -й подблок равен мя пk × пj qℓ матрица Аij ⊗ Bkℓ. По сути, произведение Трэйси – Сингха - это попарное произведение Кронекера для каждой пары разбиений в двух матрицах.

Например, если А и B оба 2 × 2 разделенные матрицы, например:

мы получили:

Хатри – Рао продукт

Основная статья: Хатри – Рао продукт
  • Блокировать продукт Кронекера
  • По столбцам произведение Хатри – Рао

Продукт для разделения лиц

Основная статья: Хатри – Рао продукт

Свойства смешанных продуктов

,[17]

куда обозначает Продукт для разделения лиц

,[18][19]

По аналогии:

,
,[20]

куда и находятся векторов,

,[21]

куда и находятся векторов, обозначает Произведение Адамара

По аналогии:

,

куда вектор свертка и это Матрица преобразования Фурье (этот результат является развитием считать эскиз характеристики[22]),

,[18][19]

куда обозначает По столбцам произведение Хатри – Рао.

По аналогии:

,
, куда и находятся векторов

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

Примечания

  1. ^ «Исчерпывающий список символов алгебры». Математическое хранилище. 2020-03-25. Получено 2020-09-06.
  2. ^ Вайсштейн, Эрик В. «Продукт Кронекера». mathworld.wolfram.com. Получено 2020-09-06.
  3. ^ Г. Зефусс (1858 г.), "Ueber eine gewisse Determinante", Zeitschrift für Mathematik und Physik, 3: 298–301.
  4. ^ Х. В. Хендерсон; С. Р. Серл (1980). «Матрица перестановки векторов, оператор вектора и произведения Кронекера: обзор» (PDF). Линейная и полилинейная алгебра. 9 (4): 271–288. Дои:10.1080/03081088108817379. HDL:1813/32747.
  5. ^ Чарльз Ф. Ван Лоан (2000). «Вездесущий продукт Кронекера». Журнал вычислительной и прикладной математики. 123 (1–2): 85–100. Bibcode:2000JCoAM.123 ... 85L. Дои:10.1016 / s0377-0427 (00) 00393-9.
  6. ^ Лэнгвилл, Эми Н.; Стюарт, Уильям Дж. (1 июня 2004 г.). «Произведение Кронекера и сети стохастических автоматов». Журнал вычислительной и прикладной математики. 167 (2): 429–447. Bibcode:2004JCoAM.167..429L. Дои:10.1016 / j.cam.2003.10.010.
  7. ^ МакЭдо, Хьюго Даниэль; Оливейра, Хосе Нуно (2013). "Набор линейной алгебры: двупродукт-ориентированный подход". Наука компьютерного программирования. 78 (11): 2160–2191. arXiv:1312.4818. Bibcode:2013arXiv1312.4818M. CiteSeerX  10.1.1.747.2083. Дои:10.1016 / j.scico.2012.07.012. S2CID  9846072.
  8. ^ Дж. У. Брюэр (1969). «Заметка о матричных произведениях Кронекера и системах матричных уравнений». Журнал SIAM по прикладной математике. 17 (3): 603–606. Дои:10.1137/0117057.
  9. ^ Даммит, Дэвид С .; Фут, Ричард М. (1999). Абстрактная алгебра (2-е изд.). Нью-Йорк: Джон Уайли и сыновья. С. 401–402. ISBN  978-0-471-36857-1.
  10. ^ См. Ответ к упражнению 96, Д. Э. Кнут: "Pre-Fascicle 0a: Введение в комбинаторные алгоритмы", нулевая печать (версия 2), которая появится как часть D.E. Кнут: Искусство программирования Vol. 4А
  11. ^ Ван Лоан, К; Пицианис, Н. (1992). Аппроксимация произведениями Кронекера. Итака, Нью-Йорк: Корнельский университет.
  12. ^ Король Кеунг Ву; Ям, Йунг; Мэн, Хелен; Месбахи, Мехран (2016). «Аппроксимация произведения Кронекера с многофакторными матрицами с помощью алгоритма тензорного произведения». Международная конференция IEEE по системам, человеку и кибернетике (SMC), 2016 г.. С. 004277–004282. Дои:10.1109 / SMC.2016.7844903. ISBN  978-1-5090-1897-0. S2CID  30695585.
  13. ^ Дантас, Касио Ф .; Коэн, Джереми Э .; Грибонваль, Реми (2018). «Изучение быстрых словарей для разреженных представлений с помощью тензорной декомпозиции низкого ранга». Скрытый анализ переменных и разделение сигналов (PDF). Конспект лекций по информатике. 10891. С. 456–466. Дои:10.1007/978-3-319-93764-9_42. ISBN  978-3-319-93763-2.
  14. ^ Алго Ли и др. «Одновременная калибровка мира роботов и глаз-руки с использованием двойных кватернионов и продукта Кронекера». Международный журнал физических наук, том. 5 (10), pp. 1530-1536, 4 сентября 2010 г.
  15. ^ Трейси, Д. С .; Сингх Р. П. (1972). «Новый матричный продукт и его приложения в матричной дифференциации». Statistica Neerlandica. 26 (4): 143–157. Дои:10.1111 / j.1467-9574.1972.tb00199.x.
  16. ^ Лю С. (1999). «Матричные результаты по произведениям Катри – Рао и Трейси – Сингха». Линейная алгебра и ее приложения. 289 (1–3): 267–277. Дои:10.1016 / S0024-3795 (98) 10209-4.
  17. ^ Слюсарь В. И. (27 декабря 1996 г.). «Конечные продукты в матрицах для радарных приложений» (PDF). Радиоэлектроника и системы связи.– 1998, Вып. 41; Число 3: 50–53.
  18. ^ а б Слюсарь В. И. (13 марта 1998 г.). «Семейство граней произведений матриц и его свойства» (PDF). Кибернетика и системный анализ C / C Кибернетика и Системный анализ. 1999 г.. 35 (3): 379–384. Дои:10.1007 / BF02733426. S2CID  119661450.
  19. ^ а б Слюсарь, Вадим (1999). «Новые матричные операции для DSP». Дои:10.13140 / RG.2.2.31620.76164 / 1. Цитировать журнал требует | журнал = (помощь)
  20. ^ Слюсарь, В. И. (15.09.1997). «Новые операции матричного продукта для приложений радаров» (PDF). Proc. Прямые и обратные задачи теории электромагнитных и акустических волн (ДИПЭД-97), Львов.: 73–74.
  21. ^ Томас Д. Але, Якоб Бак Тейс Кнудсен. Почти оптимальный тензорный набросок. Опубликовано 2019. Математика, информатика, ArXiv
  22. ^ Нинь, Фам; Расмус, Паг (2013). Быстрые и масштабируемые полиномиальные ядра с помощью явных карт функций. Международная конференция SIGKDD по обнаружению знаний и интеллектуальному анализу данных. Ассоциация вычислительной техники. Дои:10.1145/2487575.2487591.

Рекомендации

внешняя ссылка