Dadas as matrizes [math]A[/math] de dimensão [math]m \times n[/math] e [math]B[/math] de dimensão [math]p \times q[/math], o produto de kronecker [math]C = A \otimes B[/math] (também chamado de produto direto) é uma matriz de dimensões [math](mp) \times (nq)[/math] com elementos definidos por:
- [math]c_{\alpha \beta} = a_{ij} b_{kl}[/math]
onde:
- [math]\alpha = p(i-1)+k[/math]
- [math]\beta = q(j-1)+l[/math].
O produto direto da matriz fornece a matriz da transformação linear induzida pelo produto tensorial do espaço vetorial dos espaços vetoriais originais. Mais precisamente, suponha que
- [math]S:V_1 \rightarrow W_1[/math] e [math]T:V_2 \rightarrow W_2[/math]
são dados por
- [math]S(x) = A_x[/math] e [math]T(y) = B_y[/math].
Então
- [math]S \otimes T:V_1 \otimes V_2 \rightarrow W_1 \otimes W_2[/math]
é determinado por
- [math]S \otimes T(x \otimes y) = (A_x) \otimes (B_y) = (A \otimes B)(x \otimes y)[/math].
Exemplo
Por exemplo, o produto de kronecker para uma matriz 2 × 2 [math]A[/math] com uma matriz 3 × 2 [math]B[/math] é uma matriz 6 x 4 como se segue:
[math]
\left [
\begin{array}{ccc}
a_{11} & a_{12} \\\
a_{21} & a_{22}
\end{array}
\right ]
\bigotimes
\left [
\begin{array}{ccc}
b_{11} & b_{12} \\\
b_{21} & b_{22} \\\
b_{31} & b_{32}
\end{array}
\right ]
=
\left [
\begin{array}{ccc}
a_{11} B & a_{12} B \\\
a_{21} B & a_{22} B
\end{array}
\right ]
=
\left [
\begin{array}{ccc}
a_{11}b_{11} & a_{11}b_{12} & a_{12}b_{11} & a_{12}b_{12} \\\
a_{11}b_{21} & a_{11}b_{22} & a_{12}b_{21} & a_{12}b_{22} \\\
a_{11}b_{31} & a_{11}b_{32} & a_{12}b_{31} & a_{12}b_{32} \\\
a_{21}b_{11} & a_{21}b_{12} & a_{22}b_{11} & a_{22}b_{12} \\\
a_{21}b_{21} & a_{21}b_{22} & a_{22}b_{21} & a_{22}b_{22} \\\
a_{21}b_{31} & a_{21}b_{32} & a_{22}b_{31} & a_{22}b_{32}
\end{array}
\right ]
[/math]
Algoritmo
O algoritmo do produto de Kronecker entre as matrizes [math]A_{p \times q}[/math] e [math]B_{r \times s}[/math] é apresentado a seguir e produz uma matriz [math]C_{pr \times qs}[/math]
kron(A_{p × q}, B_{r × s})
inicializar a matriz C_{pr × qs}
para i ← 1 até p
para j ← 1 até q
row ← (i - 1) * r + 1
para k ← até r
col ← (j - 1) * s + 1
para l ← 1 até s
C(row, col) ← A(i, j) * B(k, l)
col ← col + 1
fim_para
row ← row + 1
fim_para
fim_para
fim_para
retorne C_{pr × qs}
fim_kron
A complexidade no tempo desse algoritmo é [math]O(p \times r \times q \times s)[/math].