Produto de Kronecker

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 (também chamado de produto direto) [math]C = A \otimes B[/math] é 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].