Produto de Kronecker

 Nota: Para o produto de Kronecker de representações de grupos simétricos, veja Coeficiente de Kronecker.

Na matemática, o produto de Kronecker, por vezes denotado por ⊗, é uma operação em duas matrizes de tamanho arbitrário, resultando numa matriz em blocos. É uma especialização do produto tensorial (que é denotado pelo mesmo símbolo) de vetores para matrizes, e dá a matriz da transformação linear do produto tensorial em relação a uma escolha padrão de base. O produto de Kronecker deve ser distinguido da multiplicação de matrizes usual, que é uma operação inteiramente diferente. O produto de Kronecker também é por vezes chamado de produto direto de matrizes.

O produto de Kronecker tem o nome do matemático alemão Leopold Kronecker (1823–1891), embora haja poucas evidências de que ele tenha sido o primeiro a defini-lo e usá-lo. O produto de Kronecker também já foi chamado de matriz de Zehfuss e produto de Zehfuss, em homenagem a Johann Georg Zehfuss, que em 1858 descreveu esta operação de matriz, mas produto de Kronecker é atualmente o termo mais amplamente usado. A atribuição errônea a Kronecker em vez de a Zehfuss deveu-se a Kurt Hensel.

Definição

Se A for uma matriz m × n e B for uma matriz p × q, então o produto de Kronecker A ⊗ B é a matriz em blocos pm × qn:

𝐀⊗𝐁=[a11𝐁⋯a1n𝐁⋮⋱⋮am1𝐁⋯amn𝐁],

mais explicitamente:

𝐀⊗𝐁=[a11b11a11b12⋯a11b1q⋯⋯a1nb11a1nb12⋯a1nb1qa11b21a11b22⋯a11b2q⋯⋯a1nb21a1nb22⋯a1nb2q⋮⋮⋱⋮⋮⋮⋱⋮a11bp1a11bp2⋯a11bpq⋯⋯a1nbp1a1nbp2⋯a1nbpq⋮⋮⋮⋱⋮⋮⋮⋮⋮⋮⋱⋮⋮⋮am1b11am1b12⋯am1b1q⋯⋯amnb11amnb12⋯amnb1qam1b21am1b22⋯am1b2q⋯⋯amnb21amnb22⋯amnb2q⋮⋮⋱⋮⋮⋮⋱⋮am1bp1am1bp2⋯am1bpq⋯⋯amnbp1amnbp2⋯amnbpq].

Usando // e % para denotar a divisão inteira (truncada) e o resto, respectivamente, e numerando os elementos da matriz a partir de 0, obtém-se

(A⊗B)pr+v,qs+w=arsbvw
(A⊗B)i,j=ai//p,j//qbi%p,j%q.

Para a numeração usual começando em 1, obtém-se

(A⊗B)p(r−1)+v,q(s−1)+w=arsbvw
(A⊗B)i,j=a⌈i/p⌉,⌈j/q⌉b(i−1)%p+1,(j−1)%q+1.

Se A e B representam transformações lineares V1 → W1 e V2 → W2, respectivamente, então o produto tensorial dos dois mapas é um mapa V1 ⊗ V2 → W1 ⊗ W2 representado por A ⊗ B.

Exemplos

[1234]⊗[0567]=[1[0567]2[0567]3[0567]4[0567]]=[1×01×52×02×51×61×72×62×73×03×54×04×53×63×74×64×7]=[0501067121401502018212428].

Da mesma forma:

[1−47−233]⊗[8−9−651−3−4728−8−312−5−1]=[8−9−65−323624−2056−63−42351−3−47−41216−287−21−284928−8−3−8−3232121456−56−2112−5−1−4−8204714−35−7−161812−1024−27−181524−27−1815−268−143−9−12213−9−1221−4−16166624−24−9624−24−9−2−410236−15−336−15−3]

Propriedades

Relações com outras operações de matrizes

1. Bilinearidade e associatividade:

O produto de Kronecker é um caso especial do produto tensorial, por isso é bilinear e associativo:

𝐀⊗(𝐁+𝐂)=𝐀⊗𝐁+𝐀⊗𝐂,(𝐁+𝐂)⊗𝐀=𝐁⊗𝐀+𝐂⊗𝐀,(k𝐀)⊗𝐁=𝐀⊗(k𝐁)=k(𝐀⊗𝐁),(𝐀⊗𝐁)⊗𝐂=𝐀⊗(𝐁⊗𝐂),𝐀⊗𝟎=𝟎⊗𝐀=𝟎,

onde A, B e C são matrizes, 0 é uma matriz nula, e k é um escalar.

2. Não comutativo:

Em geral, A ⊗ B e B ⊗ A são matrizes diferentes. No entanto, A ⊗ B e B ⊗ A são equivalentes por permutação, o que significa que existem matrizes de permutação P e Q tais que

𝐁⊗𝐀=𝐏(𝐀⊗𝐁)𝐐.

Se A e B forem quadradas, então A ⊗ B e B ⊗ A são até semelhantes por permutação, o que significa que podemos tomar P = QT.

As matrizes P e Q são matrizes de embaralhamento perfeito (perfect shuffle matrices), chamadas de matriz "comutadora". A matriz de comutação Sp, q pode ser construída tomando fatias da matriz identidade Ir, onde r=pq.

𝐒p,q=[𝐈r(1:q:r,:)𝐈r(2:q:r,:)⋮𝐈r(q:q:r,:)]

A notação de dois pontos do MATLAB é usada aqui para indicar submatrizes, e Ir é a matriz identidade r × r. Se 𝐀∈ℝm1×n1 e 𝐁∈ℝm2×n2, então

𝐁⊗𝐀=𝐒m1,m2(𝐀⊗𝐁)𝐒n1,n2𝖳

3. A propriedade do produto misto:

Se A, B, C e D são matrizes de tal tamanho que se pode formar os produtos de matrizes AC e BD, então

(𝐀⊗𝐁)(𝐂⊗𝐃)=(𝐀𝐂)⊗(𝐁𝐃).

Isto é chamado de propriedade do produto misto, porque mistura o produto matricial ordinário com o produto de Kronecker.

Como uma consequência imediata (novamente, tomando 𝐀∈ℝm1×n1 e 𝐁∈ℝm2×n2),

𝐀⊗𝐁=(𝐈m1⊗𝐁)(𝐀⊗𝐈n2)=(𝐀⊗𝐈m2)(𝐈n1⊗𝐁).

Em particular, usando a propriedade de transposição mostrada abaixo, isto significa que se

𝐀=𝐐⊗𝐔

e Q e U forem ortogonais (ou unitárias), então A também é ortogonal (resp., unitária).

O produto misto matriz-vetor de Kronecker pode ser escrito como:

(𝐀⊗𝐁)vec⁡(𝐕)=vec⁡(𝐁𝐕𝐀T)

onde vec⁡(𝐕) é o operador de vetorização aplicado a 𝐕 (formado pela reformatação da matriz).

4. Propriedade do comutador:

Se 𝐀 e 𝐂 são matrizes quadradas de dimensão m, e 𝐁 e 𝐃 são matrizes quadradas de dimensão n, então o comutador é

[𝐀⊗𝐁,𝐂⊗𝐃]=[𝐀,𝐂]⊗(𝐁𝐃)+(𝐂𝐀)⊗[𝐁,𝐃],

ou

[𝐀⊗𝐁,𝐂⊗𝐃]=[𝐀,𝐂]⊗(𝐃𝐁)+(𝐀𝐂)⊗[𝐁,𝐃].


5. Produto de Hadamard (multiplicação elemento a elemento):

A propriedade do produto misto também funciona para o produto elemento a elemento. Se A e C são matrizes do mesmo tamanho, B e D são matrizes do mesmo tamanho, então

(𝐀⊗𝐁)∘(𝐂⊗𝐃)=(𝐀∘𝐂)⊗(𝐁∘𝐃).

6. A inversa de um produto de Kronecker:

Segue-se que A ⊗ B é invertível se e somente se tanto A quanto B forem invertíveis, neste caso a inversa é dada por

(𝐀⊗𝐁)−1=𝐀−1⊗𝐁−1.

A propriedade do produto invertível também vale para a pseudoinversa de Moore-Penrose, ou seja

(𝐀⊗𝐁)+=𝐀+⊗𝐁+.

Na linguagem da teoria das categorias, a propriedade do produto misto do produto de Kronecker (e do produto tensorial mais geral) mostra que a categoria MatF de matrizes sobre um corpo F, é de fato uma categoria monoidal, cujos objetos são números naturais n, morfismos n → m são matrizes n × m com entradas em F, a composição é dada pela multiplicação de matrizes, setas identidade são simplesmente as matrizes identidades n × n In, e o produto tensorial é dado pelo produto de Kronecker.

MatF é uma categoria esqueleto concreta para a categoria equivalente FinVectF de espaços vetoriais de dimensão finita sobre F, cujos objetos são tais espaços vetoriais de dimensão finita V, as setas são mapas F-lineares L : V → W, e as setas identidade são os mapas identidade dos espaços. A equivalência de categorias equivale a escolher simultaneamente uma base em cada espaço vetorial de dimensão finita V sobre F; os elementos das matrizes representam estes mapeamentos com respeito às bases escolhidas; e da mesma forma o produto de Kronecker é a representação do produto tensorial nas bases escolhidas.

7. Transposta:

A transposição e a transposição conjugada são distributivas sobre o produto de Kronecker:

(𝐀⊗𝐁)𝖳=𝐀𝖳⊗𝐁𝖳 e (𝐀⊗𝐁)∗=𝐀∗⊗𝐁∗.

8. Determinante:

Seja A uma matriz n × n e seja B uma matriz m × m. Então

|𝐀⊗𝐁|=|𝐀|m|𝐁|n.

O expoente em |A| é a ordem de B e o expoente em |B| é a ordem de A.

9. Soma de Kronecker e exponenciação:

Se A for n × n, B for m × m, e Ik denotar a matriz identidade k × k então podemos definir o que às vezes é chamado de soma de Kronecker, ⊕‾, por

𝐀⊕‾𝐁=𝐀⊗𝐈m+𝐈n⊗𝐁.

Isto é diferente da soma direta de duas matrizes. Esta operação está relacionada com o produto tensorial em álgebras de Lie, como detalhado abaixo (#Propriedades abstratas) no ponto "Relação com o produto tensorial abstrato".

Temos a seguinte fórmula para a exponencial de matriz, que é útil nalgumas avaliações numéricas.

exp⁡(𝐍⊕‾𝐌)=exp⁡(𝐍)⊗exp⁡(𝐌)

As somas de Kronecker aparecem naturalmente em física quando se considera conjuntos de sistemas não interagentes.

Se Hr for o Hamiltoniano do r-ésimo sistema de tal tipo. Então o Hamiltoniano total do conjunto é

HTot=⨁r‾Hr.

10. Vetorização de um produto de Kronecker:

Seja A uma matriz m×n e B uma matriz p×q. Quando a ordem do produto de Kronecker e da vetorização é invertida, as duas operações podem ser ligadas linearmente através de uma função que envolve a matriz de comutação, Kqm. Isto é, vec⁡(Kron⁡(A,B)) e Kron⁡(vec⁡A,vec⁡B) têm a seguinte relação:

vec⁡(A⊗B)=(In⊗Kqm⊗Ip)(vec⁡A⊗vec⁡B).

Além disso, a relação acima pode ser rearranjada em termos de vec⁡A ou vec⁡B da seguinte forma:

vec⁡(A⊗B)=(In⊗G)vec⁡A=(H⊗Ip)vec⁡B,

onde

G=(Kqm⊗Ip)(Im⊗vec⁡B) e H=(In⊗Kqm)(vec⁡A⊗Iq).

11. Produto externo:

Se x∈ℝn e y∈ℝm são vetores arbitrários, então o produto externo entre x e y é definido como xyT. O produto de Kronecker está relacionado ao produto externo por: y⊗x=vec⁡(xyT).

Propriedades abstratas

1. Espectro:

Suponha que A e B são matrizes quadradas de tamanho n e m respectivamente. Sejam λ1, ..., λn os autovalores de A e μ1, ..., μm os de B (listados de acordo com a multiplicidade). Então os autovalores de A ⊗ B são

λiμj,i=1,…,n,j=1,…,m.

Segue-se que o traço e o determinante de um produto de Kronecker são dados por

tr⁡(𝐀⊗𝐁)=tr⁡𝐀tr⁡𝐁edet⁡(𝐀⊗𝐁)=(det⁡𝐀)m(det⁡𝐁)n.

2. Valores singulares:

Se A e B são matrizes retangulares, então pode-se considerar sua decomposição em valores singulares. Suponha que A tenha rA valores singulares não nulos, a saber

σ𝐀,i,i=1,…,r𝐀.

De forma análoga, denote os valores singulares não nulos de B por

σ𝐁,i,i=1,…,r𝐁.

Então o produto de Kronecker A ⊗ B tem rArB valores singulares não nulos, a saber

σ𝐀,iσ𝐁,j,i=1,…,r𝐀,j=1,…,r𝐁.

Dado que o posto de uma matriz é igual ao número de valores singulares não nulos, verificamos que

rank⁡(𝐀⊗𝐁)=rank⁡𝐀rank⁡𝐁.

3. Relação com o produto tensorial abstrato:

O produto de Kronecker de matrizes corresponde ao produto tensorial abstrato de mapas lineares. Especificamente, se os espaços vetoriais V, W, X e Y têm as bases {v1, ..., vm}, {w1, ..., wn}, {x1, ..., xd}, e {y1, ..., ye}, respectivamente, e se as matrizes A e B representam as transformações lineares S : V → X e T : W → Y, respectivamente, nas bases apropriadas, então a matriz A ⊗ B representa o produto tensorial dos dois mapas, S ⊗ T : V ⊗ W → X ⊗ Y em relação à base {v1 ⊗ w1, v1 ⊗ w2, ..., v2 ⊗ w1, ..., vm ⊗ wn} de V ⊗ W e à base definida de forma análoga de X ⊗ Y com a propriedade de que A ⊗ B(vi ⊗ wj) = (Avi) ⊗ (Bwj), onde i e j são números inteiros no intervalo adequado.

Quando V e W são álgebras de Lie, e S : V → V e T : W → W são homomorfismos de álgebra de Lie, a soma de Kronecker de A e B representa os homomorfismos induzidos da álgebra de Lie V ⊗ W → V ⊗ W.

4. Relação a produtos de grafos:

O produto de Kronecker das matrizes de adjacência de dois grafos é a matriz de adjacência do grafo produto tensorial. A soma de Kronecker das matrizes de adjacência de dois grafos é a matriz de adjacência do grafo produto cartesiano.

Equações de matriz

O produto de Kronecker pode ser usado para obter uma representação conveniente para algumas equações de matriz. Considere, por exemplo, a equação AXB = C, onde A, B e C são matrizes dadas e a matriz X é a incógnita. Podemos usar o "truque vec" para reescrever esta equação como

(𝐁𝖳⊗𝐀)vec⁡(𝐗)=vec⁡(𝐀𝐗𝐁)=vec⁡(𝐂).

Aqui, vec(X) denota a vetorização da matriz X, formada empilhando as colunas de X num único vetor coluna.

Decorre agora das propriedades do produto de Kronecker que a equação AXB = C tem uma solução única, se e somente se A e B forem invertíveis (Horn & Johnson 1991, Lema 4.3.1).

Se X e C forem ordenadas por linha nos vetores de coluna u e v, respectivamente, então (Jain 1989, 2.8 Block Matrices and Kronecker Products)

𝐯=(𝐀⊗𝐁𝖳)𝐮.

A razão é que

𝐯=vec⁡((𝐀𝐗𝐁)𝖳)=vec⁡(𝐁𝖳𝐗𝖳𝐀𝖳)=(𝐀⊗𝐁𝖳)vec⁡(𝐗𝖳)=(𝐀⊗𝐁𝖳)𝐮.

Aplicações

Para um exemplo da aplicação desta fórmula, veja o artigo sobre a equação de Lyapunov. Esta fórmula também é útil para mostrar que a distribuição normal de matriz é um caso especial da distribuição normal multivariada. Esta fórmula também é útil para representar as operações de processamento de imagem 2D na forma matriz-vetor.

Outro exemplo é quando uma matriz pode ser fatorada como um produto de Kronecker, então a multiplicação de matrizes pode ser efetuada mais rapidamente usando a fórmula acima. Isto pode ser aplicado de forma recursiva, tal como na FFT de base 2 e na Transformação rápida de Walsh-Hadamard. Separar uma matriz conhecida no produto de Kronecker de duas matrizes mais pequenas é conhecido como o problema do "produto de Kronecker mais próximo", e pode ser resolvido exatamente através do uso da SVD. Separar uma matriz no produto de Kronecker de mais do que duas matrizes, de uma forma ideal, é um problema difícil e que é tema de investigação contínua; alguns autores abordam o assunto como um problema de decomposição tensorial.

Em combinação com o método dos mínimos quadrados, o produto de Kronecker pode ser usado como uma solução precisa para o problema de calibração mão-olho.

Operações de matrizes relacionadas

Duas operações de matrizes relacionadas são os produtos de Tracy-Singh e os produtos de Khatri-Rao, que operam em matrizes em blocos. Seja a matriz m × n A subdividida em blocos mi × nj Aij e a matriz p × q B subdividida em blocos pk × qℓ Bkl, naturalmente com Σi mi = m, Σj nj = n, Σk pk = p e Σℓ qℓ = q.

Produto de Tracy–Singh

O produto de Tracy–Singh é definido como

𝐀∘𝐁=(𝐀ij∘𝐁)ij=((𝐀ij⊗𝐁kl)kl)ij

o que significa que o (ij)-ésimo sub-bloco do produto mp × nq A ∘ B é a matriz mi p × nj q Aij ∘ B, da qual o (kℓ)-ésimo sub-bloco é igual à matriz mi pk × nj qℓ Aij ⊗ Bkℓ. Essencialmente, o produto de Tracy-Singh é o produto de Kronecker par a par para cada par de partições nas duas matrizes.

Por exemplo, se A e B forem matrizes particionadas 2 × 2 ex.:

𝐀=[𝐀11𝐀12𝐀21𝐀22]=[123456789],𝐁=[𝐁11𝐁12𝐁21𝐁22]=[147258369],

obtemos:

𝐀∘𝐁=[𝐀11∘𝐁𝐀12∘𝐁𝐀21∘𝐁𝐀22∘𝐁]=[𝐀11⊗𝐁11𝐀11⊗𝐁12𝐀12⊗𝐁11𝐀12⊗𝐁12𝐀11⊗𝐁21𝐀11⊗𝐁22𝐀12⊗𝐁21𝐀12⊗𝐁22𝐀21⊗𝐁11𝐀21⊗𝐁12𝐀22⊗𝐁11𝐀22⊗𝐁12𝐀21⊗𝐁21𝐀21⊗𝐁22𝐀22⊗𝐁21𝐀22⊗𝐁22]=[1247814312214516282035624422458101661524366912189182781020322540123048121524363045183654782849325693663141635564064184572212442634872275481].

Produto de Khatri–Rao

  • Produto de bloco de Kronecker
  • Produto de Khatri-Rao por colunas

Produto de divisão de face (Face-splitting product)

Propriedades de produtos mistos

𝐀⊗(𝐁∙𝐂)=(𝐀⊗𝐁)∙𝐂,

onde ∙ denota o produto de divisão de face.

(𝐀∙𝐁)(𝐂⊗𝐃)=(𝐀𝐂)∙(𝐁𝐃),

De forma semelhante:

(𝐀∙𝐋)(𝐁⊗𝐌)⋯(𝐂⊗𝐒)=(𝐀𝐁⋯𝐂)∙(𝐋𝐌⋯𝐒),
𝐜𝖳∙𝐝𝖳=𝐜𝖳⊗𝐝𝖳,

onde 𝐜 e 𝐝 são vetores,

(𝐀∙𝐁)(𝐜⊗𝐝)=(𝐀𝐜)∘(𝐁𝐝),

onde 𝐜 e 𝐝 são vetores, e ∘ denota o produto de Hadamard.

Da mesma forma:

(𝐀∙𝐁)(𝐌𝐍𝐜⊗𝐐𝐏𝐝)=(𝐀𝐌𝐍𝐜)∘(𝐁𝐐𝐏𝐝),
ℱ(C(1)x⋆C(2)y)=(ℱC(1)∙ℱC(2))(x⊗y)=ℱC(1)x∘ℱC(2)y,

onde ⋆ é a convolução de vetor e ℱ é a matriz da transformada de Fourier (este resultado é uma evolução das propriedades do count sketch),

(𝐀∙𝐋)(𝐁⊗𝐌)⋯(𝐂⊗𝐒)(𝐊∗𝐓)=(𝐀𝐁⋅𝐂𝐊)∘(𝐋𝐌⋯𝐒𝐓),

onde ∗ denota o produto de Khatri-Rao por colunas.

Similarmente:

(𝐀∙𝐋)(𝐁⊗𝐌)⋯(𝐂⊗𝐒)(c⊗d)=(𝐀𝐁⋯𝐂𝐜)∘(𝐋𝐌⋯𝐒𝐝),
(𝐀∙𝐋)(𝐁⊗𝐌)⋯(𝐂⊗𝐒)(𝐏𝐜⊗𝐐𝐝)=(𝐀𝐁⋯𝐂𝐏𝐜)∘(𝐋𝐌⋯𝐒𝐐𝐝),

onde 𝐜 e 𝐝 são vetores.

Ver também