Produto de Kronecker

Dadas as matrizes $A$ de dimensão $m \times n$ e $B$ de dimensão $p \times q$, o produto de kronecker (também chamado de produto direto) $C = A \otimes B$ é uma matriz de dimensões $(mp) \times (nq)$ com elementos definidos por:

$c_{\alpha \beta} = a_{ij} b_{kl}$

onde:

• $\alpha = p(i-1)+k$
• $\beta = q(j-1)+l$.

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

$S:V_1 \rightarrow W_1$ e $T:V_2 \rightarrow W_2$

são dados por

$S(x) = A_x$ e $T(y) = B_y$.

Então

$S \otimes T:V_1 \otimes V_2 \rightarrow W_1 \otimes W_2$

é determinado por

$S \otimes T(x \otimes y) = (A_x) \otimes (B_y) = (A \otimes B)(x \otimes y)$.

Exemplo

Por exemplo, o produto de kronecker para uma matriz 2 × 2 $A$ com uma matriz 3 × 2 $B$ é uma matriz 6 x 4 como se segue:

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

Algoritmo

O algoritmo do produto de Kronecker entre as matrizes $A_{p \times q}$ e $B_{r \times s}$ é apresentado a seguir e produz uma matriz $C_{pr \times qs}$

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 é $O(p \times r \times q \times s)$.

Veja Também

• Wikipedia: Kronecker Product
• Proof Wiki Definition: Kronecker Product
• Wolfram MathWorld: Kronecker Product
• Blog Cyberini: Algoritmo do Produto de Kronecer