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

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

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

Визначення

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

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

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

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

A\otimes (B+C)=A\otimes B+A\otimes C,

(A+B)\otimes C=A\otimes C+B\otimes C,

(kA)\otimes B=A\otimes (kB)=k(A\otimes B),

(A\otimes B)\otimes C=A\otimes (B\otimes C),

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

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

A\otimes B=P\,(B\otimes A)\,Q.

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

A\otimes B=(I\otimes B)(A\otimes I)

, де

I

- одинична матриця.

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

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

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

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

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

(A\otimes B)(C\otimes D)=AC\otimes BD.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\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}

Наприклад:

\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],

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

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

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

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

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

$(\mathbf {A} \bullet \mathbf {B} )(\mathbf {C} \otimes \mathbf {D} )=(\mathbf {A} \mathbf {C} )\bullet (\mathbf {B} \mathbf {D} )$ [4][5],

За аналогією:
$(\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} )$ ,

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

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

(\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),

${\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$ ,
де $\star$ означає векторну згортку, а ${\mathcal {F}}$ є матрицею дискретного перетворення Фур'є[8],

$(\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} )$ [4][5], де $\ast$ означає стовпцевий добуток Хатрі-Рао

Окрім того:
$(\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)$ ,

$(\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)$ , де $c$ і $d$ - вектори.

Див. також

Примітки

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.
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.
Slyusar, V. I. (27 грудня 1996). End products in matrices in radar applications.. Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50–53.
Slyusar, V. I. (13 березня 1998). A Family of Face Products of Matrices and its Properties. Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz. 1999. 35 (3): 379–384. doi:10.1007/BF02733426.
Vadym Slyusar. New Matrix Operations for DSP (Lecture). April 1999. – DOI: 10.13140/RG.2.2.31620.76164/1
Slyusar, V. I. (15 вересня 1997). New operations of matrices product for applications of radars. Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.: 73–74.
Thomas D. Ahle, Jakob Bæk Tejs Knudsen. Almost Optimal Tensor Sketch. Published 2019. Mathematics, Computer Science, ArXiv
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.

Джерела

Хорн Р. Матричный анализ: Пер. с англ. / Р. Хорн, Ч. Джонсон. – М.: Мир, 1989.– 655 с.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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.

[slyusar-3] Slyusar, V. I. (27 грудня 1996). End products in matrices in radar applications.. Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50–53.

[slyusar2-4] Slyusar, V. I. (13 березня 1998). A Family of Face Products of Matrices and its Properties. Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz. 1999. 35 (3): 379–384. doi:10.1007/BF02733426.

[lecture-5] Vadym Slyusar. New Matrix Operations for DSP (Lecture). April 1999. – DOI: 10.13140/RG.2.2.31620.76164/1

[DIPED-6] Slyusar, V. I. (15 вересня 1997). New operations of matrices product for applications of radars. Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.: 73–74.

[tensorsketch-7] Thomas D. Ahle, Jakob Bæk Tejs Knudsen. Almost Optimal Tensor Sketch. Published 2019. Mathematics, Computer Science, ArXiv

[ninh-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.