Добуток Кронекера

Добуток Кронекера — бінарна операція над матрицями довільного розміру, позначається ${\displaystyle \otimes }$. Результатом є блочна матриця.

Добуток Кронекера не слід путати зі звичайним множенням матриць. Операція названа на честь німецького математика Леопольда Кронекера.

Визначення

Якщо A — матриця розміру m×n, B — матриця розміру p×q, тоді добутком Кронекера є блочна матриця розміру mp×nq

${\displaystyle A\otimes B={\begin{bmatrix}a_{11}B&\cdots &a_{1n}B\\\vdots &\ddots &\vdots \\a_{m1}B&\cdots &a_{mn}B\end{bmatrix}}.}$

Білінійність, асоціативність та некомутативність

• Добуток Кронекера є частковим випадком тензорного добутку, отже він є білінійним та асоціативним:

${\displaystyle A\otimes (B+C)=A\otimes B+A\otimes C,}$

${\displaystyle (A+B)\otimes C=A\otimes C+B\otimes C,}$

${\displaystyle (kA)\otimes B=A\otimes (kB)=k(A\otimes B),}$

${\displaystyle (A\otimes B)\otimes C=A\otimes (B\otimes C),}$

де A, B та C є матрицями, а k — скаляр.

• Добуток Кронекера не є комутативним. Хоча, завжди існують такі матриці перестановки P та Q, що

${\displaystyle A\otimes B=P\,(B\otimes A)\,Q.}$

Якщо A та B квадратні матриці, тоді A ${\displaystyle \otimes }$ B та B ${\displaystyle \otimes }$ A є перестановочно подібними, тобто, P = Q^T.

${\displaystyle A\otimes B=(I\otimes B)(A\otimes I)}$, де ${\displaystyle I}$ - одинична матриця.

Транспонування

Операція транспонування є дистрибутивною відносно добутку Кронекера

${\displaystyle (A\otimes B)^{T}=A^{T}\otimes B^{T}.}$

Мішаний добуток

• Якщо A, B, C та D є матрицями такого розміру, що існують добутки AC та BD, тоді

${\displaystyle (A\otimes B)(C\otimes D)=AC\otimes BD.}$

• A ${\displaystyle \otimes }$ B є оборотною тоді і тільки тоді коли A та B є оборотними, і тоді

${\displaystyle (A\otimes B)^{-1}=A^{-1}\otimes B^{-1}.}$

Сума та експонента Кронекера

• Якщо A — матриця розміру n×n, B — матриця розміру m×m і ${\displaystyle I_{k}}$ — одинична матриця розміру k×k тоді ми можемо визначити суму Кронекера ${\displaystyle \oplus }$, як

${\displaystyle A\oplus B=A\otimes I_{m}+I_{n}\otimes B.}$

• Також справедливо

${\displaystyle e^{A\oplus B}=e^{A}\otimes e^{B}.}$

Спектр, слід та визначник

• Якщо A та B квадратні матриці розміру n та q відповідно. Якщо λ₁, …, λ_n — власні значення матриці A та μ₁, …, μ_q власні значення матриці B. Тоді власними значеннями A ${\displaystyle \otimes }$ B є

${\displaystyle \lambda _{i}\mu _{j},\qquad i=1,\ldots ,n,\,j=1,\ldots ,q.}$

• Слід та визначник добутку Кронекера рівні

${\displaystyle \operatorname {tr} (A\otimes B)=\operatorname {tr} (A)\,\operatorname {tr} (B),}$

${\displaystyle \det(A\otimes B)=(\det A)^{q}(\det B)^{n}.}$

Сингулярний розклад та ранг

• Якщо матриця A має r_A ненульових сингулярних значень:

${\displaystyle \sigma _{A,i},\qquad i=1,\ldots ,r_{A}.}$

Ненульові сингулярні значення матриці B:

${\displaystyle \sigma _{B,i},\qquad i=1,\ldots ,r_{B}.}$

Тоді добуток Кронекера A ${\displaystyle \otimes }$ B має r_Ar_B ненульових сингулярних значень

${\displaystyle \sigma _{A,i}\sigma _{B,j},\qquad i=1,\ldots ,r_{A},\,j=1,\ldots ,r_{B}.}$

• Ранг матриці рівний кількості ненульових сингулярних значень, отже

${\displaystyle \operatorname {rank} (A\otimes B)=\operatorname {rank} (A)\,\operatorname {rank} (B).}$

Блокові версії добутку Кронекера

У випадку блочних матриць можуть використовуватися операції, які пов'язані з добутком Кронекера однак відрізняються порядком перемноження блоків. Такими операціями є добуток Трейсі – Сінгха (англ. Tracy–Singh product) і добуток Хатрі-Рао.

Добуток Трейсі-Сінгха

Вказана операція множення блокових матриць полягає в тому, що кожен блок лівої матриці множиться послідовно на блоки правої матриці. При цьому формується структура нової матриці, яка відрізняється від характерної для добутку Кронекера. Добуток Трейсі - Сінгха визначається як

${\displaystyle \mathbf {A} \circ \mathbf {B} =\left(\mathbf {A} _{ij}\circ \mathbf {B} \right)_{ij}=\left(\left(\mathbf {A} _{ij}\otimes \mathbf {B} _{kl}\right)_{kl}\right)_{ij}}$

Наприклад:

${\displaystyle \mathbf {A} =\left[{\begin{array}{c | c}\mathbf {A} _{11}&\mathbf {A} _{12}\\\hline \mathbf {A} _{21}&\mathbf {A} _{22}\end{array}}\right]=\left[{\begin{array}{c c | c}1&2&3\\4&5&6\\\hline 7&8&9\end{array}}\right],\quad \mathbf {B} =\left[{\begin{array}{c | c}\mathbf {B} _{11}&\mathbf {B} _{12}\\\hline \mathbf {B} _{21}&\mathbf {B} _{22}\end{array}}\right]=\left[{\begin{array}{c | c c}1&4&7\\\hline 2&5&8\\3&6&9\end{array}}\right],}$

${\displaystyle {\begin{aligned}\mathbf {A} \circ \mathbf {B} =\left[{\begin{array}{c | c}\mathbf {A} _{11}\circ \mathbf {B} &\mathbf {A} _{12}\circ \mathbf {B} \\\hline \mathbf {A} _{21}\circ \mathbf {B} &\mathbf {A} _{22}\circ \mathbf {B} \end{array}}\right]={}&\left[{\begin{array}{c | c | c | c}\mathbf {A} _{11}\otimes \mathbf {B} _{11}&\mathbf {A} _{11}\otimes \mathbf {B} _{12}&\mathbf {A} _{12}\otimes \mathbf {B} _{11}&\mathbf {A} _{12}\otimes \mathbf {B} _{12}\\\hline \mathbf {A} _{11}\otimes \mathbf {B} _{21}&\mathbf {A} _{11}\otimes \mathbf {B} _{22}&\mathbf {A} _{12}\otimes \mathbf {B} _{21}&\mathbf {A} _{12}\otimes \mathbf {B} _{22}\\\hline \mathbf {A} _{21}\otimes \mathbf {B} _{11}&\mathbf {A} _{21}\otimes \mathbf {B} _{12}&\mathbf {A} _{22}\otimes \mathbf {B} _{11}&\mathbf {A} _{22}\otimes \mathbf {B} _{12}\\\hline \mathbf {A} _{21}\otimes \mathbf {B} _{21}&\mathbf {A} _{21}\otimes \mathbf {B} _{22}&\mathbf {A} _{22}\otimes \mathbf {B} _{21}&\mathbf {A} _{22}\otimes \mathbf {B} _{22}\end{array}}\right]\\={}&\left[{\begin{array}{c c | c c c c | c | c c}1&2&4&7&8&14&3&12&21\\4&5&16&28&20&35&6&24&42\\\hline 2&4&5&8&10&16&6&15&24\\3&6&6&9&12&18&9&18&27\\8&10&20&32&25&40&12&30&48\\12&15&24&36&30&45&18&36&54\\\hline 7&8&28&49&32&56&9&36&63\\\hline 14&16&35&56&40&64&18&45&72\\21&24&42&63&48&72&27&54&81\end{array}}\right].\end{aligned}}}$

Добуток Хатрі-Рао

Докладніше: добуток Хатрі-Рао

Даний варіант добутку визначений для матриц з однаковою блоковою структурою. Він передбачає, що операція кронекерівського добутку виконується поблоково, в межах однойменних матричних блоків за аналогією з поелементним добутком Адамара, тільки при цьому в якості елементів задіяні блоки матриць, а для переноження блоків використовується добуток Кронекера.

Торцевий добуток

Докладніше: торцевий добуток

Властивості мішаних добутків:
${\displaystyle \mathbf {A} \otimes (\mathbf {B} \bullet \mathbf {C} )=(\mathbf {A} \otimes \mathbf {B} )\bullet \mathbf {C} }$, де ${\displaystyle \bullet }$ означає торцевий добуток

${\displaystyle (\mathbf {A} \bullet \mathbf {B} )(\mathbf {C} \otimes \mathbf {D} )=(\mathbf {A} \mathbf {C} )\bullet (\mathbf {B} \mathbf {D} )}$,

За аналогією:
${\displaystyle (\mathbf {A} \bullet \mathbf {L} )(\mathbf {B} \otimes \mathbf {M} )...(\mathbf {C} \otimes \mathbf {S} )=(\mathbf {A} \mathbf {B} ...\mathbf {C} )\bullet (\mathbf {L} \mathbf {M} ...\mathbf {S} )}$,

${\displaystyle c^{\textsf {T}}\bullet d^{\textsf {T}}=c^{\textsf {T}}\otimes d^{\textsf {T}}}$, де ${\displaystyle c}$ і ${\displaystyle d}$ - вектори,

${\displaystyle (\mathbf {A} \bullet \mathbf {B} )(c\otimes d)=(\mathbf {A} c)\circ (\mathbf {B} d)}$,
Аналогічно:

${\displaystyle (\mathbf {A} \bullet \mathbf {B} )(\mathbf {M} \mathbf {N} c\otimes \mathbf {Q} \mathbf {P} d)=(\mathbf {A} \mathbf {M} \mathbf {N} c)\circ (\mathbf {B} \mathbf {Q} \mathbf {P} d),}$

${\displaystyle {\mathcal {F}}(C^{(1)}x\star C^{(2)}y)=({\mathcal {F}}C^{(1)}\bullet {\mathcal {F}}C^{(2)})(x\otimes y)={\mathcal {F}}C^{(1)}x\circ {\mathcal {F}}C^{(2)}y}$,
де ${\displaystyle \star }$ означає векторну згортку, а ${\displaystyle {\mathcal {F}}}$ є матрицею дискретного перетворення Фур'є,

${\displaystyle (\mathbf {A} \bullet \mathbf {L} )(\mathbf {B} \otimes \mathbf {M} )...(\mathbf {C} \otimes \mathbf {S} )(\mathbf {K} \ast \mathbf {T} )=(\mathbf {A} \mathbf {B} ...\mathbf {C} \mathbf {K} )\circ (\mathbf {L} \mathbf {M} ...\mathbf {S} \mathbf {T} )}$, де ${\displaystyle \ast }$ означає (стовпцевий добуток Хатрі-Рао)

Окрім того:
${\displaystyle (\mathbf {A} \bullet \mathbf {L} )(\mathbf {B} \otimes \mathbf {M} )...(\mathbf {C} \otimes \mathbf {S} )(c\otimes d)=(\mathbf {A} \mathbf {B} ...\mathbf {C} c)\circ (\mathbf {L} \mathbf {M} ...\mathbf {S} d)}$,

${\displaystyle (\mathbf {A} \bullet \mathbf {L} )(\mathbf {B} \otimes \mathbf {M} )...(\mathbf {C} \otimes \mathbf {S} )(\mathbf {P} c\otimes \mathbf {Q} d)=(\mathbf {A} \mathbf {B} ...\mathbf {C} \mathbf {P} c)\circ (\mathbf {L} \mathbf {M} ...\mathbf {S} \mathbf {Q} d)}$, де ${\displaystyle c}$ і ${\displaystyle d}$ - вектори.

Див. також

• Список об'єктів, названих на честь Леопольда Кронекера
• Добуток Хатрі-Рао

Джерела

• Гантмахер Ф. Р. Теория матриц. — 5-е. — М: : Физматлит, 2010. — 559 с. — .(рос.)
• Теория матриц. — 2. — Москва : Наука, 1982. — 272 с.(рос.)
• , . Матричный анализ. — М: : Мир, 1989. — 653 с.(рос.)

Примітки

1. Tracy, D. S.; Singh, R. P. (1972). A New Matrix Product and Its Applications in Matrix Differentiation. Statistica Neerlandica. 26 (4): 143—157. doi:10.1111/j.1467-9574.1972.tb00199.x.
2. Liu, S. (1999). Matrix Results on the Khatri–Rao and Tracy–Singh Products. Linear Algebra and Its Applications. 289 (1–3): 267—277. doi:10.1016/S0024-3795(98)10209-4.
3. Slyusar, V. I. (27 грудня 1996). (PDF). Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50—53. Архів оригіналу (PDF) за 27 липня 2020. Процитовано 11 серпня 2020.
4. Slyusar, V. I. (13 березня 1998). (PDF). Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz. 1999. 35 (3): 379—384. doi:10.1007/BF02733426. Архів оригіналу (PDF) за 25 січня 2020. Процитовано 11 серпня 2020.
5. Vadym Slyusar. New Matrix Operations for DSP (Lecture). April 1999. – DOI: 10.13140/RG.2.2.31620.76164/1
6. Slyusar, V. I. (15 вересня 1997). (PDF). Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.: 73—74. Архів оригіналу (PDF) за 25 січня 2020. Процитовано 11 серпня 2020.
7. Thomas D. Ahle, Jakob Bæk Tejs Knudsen. Almost Optimal Tensor Sketch. Published 2019. Mathematics, Computer Science, ArXiv [ 28 липня 2020 у Wayback Machine.]
8. Ninh, Pham; Rasmus, Pagh (2013). Fast and scalable polynomial kernels via explicit feature maps. SIGKDD international conference on Knowledge discovery and data mining. Association for Computing Machinery. doi:10.1145/2487575.2487591.