Baixe Multiplicação matrizes e outras Notas de estudo em PDF para Matemática, somente na Docsity! Introdução Aplicações bilineares Característica de µ A característica da multiplicação de matrizes Novos Talentos em Matemática Eduardo Dias 10 de Setembro de 2006 Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ O problema Quantas multiplicações escalares são necessárias para efectuar a multiplicação de duas matrizes reais do tipo 2× 2? [ x y z w ] · [ a b c d ] = [ xa + yc xb + yd za + wc zb + wd ] 8 multiplicações. Problema Conseguiremos efectuar este produto fazendo menos que oito multiplicações? E qual é o mínimo de multiplicações necessárias? Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Exemplos • Diferença de quadrados: x2 − y2 = x · x − y · y = (x − y)(x + y). À partida, efectuamos duas multiplicações, mas usando o caso notável, apenas uma multiplicação. • Multiplicação de complexos: Por definição: (a + b i)× (c + d i) = (a · c − b · d) + (a · d + b · c)i . À partida, 4 multiplicações. No entanto, calculando: x = a(c + d), y = (a + b)d , z = b(d − c) obtém-se: (a + bi)× (c + di) = (x− y) + (y − z)i ou seja, apenas três multiplicações. Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Exemplos • Diferença de quadrados: x2 − y2 = x · x − y · y = (x − y)(x + y). À partida, efectuamos duas multiplicações, mas usando o caso notável, apenas uma multiplicação. • Multiplicação de complexos: Por definição: (a + b i)× (c + d i) = (a · c − b · d) + (a · d + b · c)i . À partida, 4 multiplicações. No entanto, calculando: x = a(c + d), y = (a + b)d , z = b(d − c) obtém-se: (a + bi)× (c + di) = (x− y) + (y − z)i ou seja, apenas três multiplicações. Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ O algoritmo de Strassen No caso da multiplicação de matrizes 2× 2,calculando as expressões: I = (x + w)(a + d) V = (x + y)d II = (z + w)a VI = (−x + z)(a + b) III = x(b − d) VII = (y − w)(c + d) IV = w(−a + c) [ x y z w ] · [ a b c d ] = [ I + IV −V + VII III + V II + IV I + II + III + VI ] ou seja, com este algoritmo, são necessárias apenas sete multiplicações. (V. Strassen 1969.) Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Mínimo de multiplicações Questões É possível efectuar a multiplicação de duas matrizes 2× 2 com menos de sete multiplicações? Existe uma fórmula para a multiplicação de dois números complexos com menos de três multiplicações? Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ O que é uma multiplicação? Definição (Forma bilinear de característica 1) Uma forma bilinear de característica 1 é uma a aplicação Rn × Rm −→ R dada por: (x, y) → x(uTv)yT onde u = (u1, . . . , un) ∈ Rn e v = (v1, . . . , vm) ∈ Rm são dois vectores. Denotemos esta aplicação por u⊗ v. Temos as seguintes relações: (v1 + v2)⊗ u = v1 ⊗ u + v2 ⊗ u v ⊗ (u1 + u2) = v ⊗ u1 + v2 ⊗ u2 (λv)⊗ u = λ(v ⊗ u) = v ⊗ (λu) Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ O que é uma multiplicação? Definição (Forma bilinear de característica 1) Uma forma bilinear de característica 1 é uma a aplicação Rn × Rm −→ R dada por: (x, y) → x(uTv)yT onde u = (u1, . . . , un) ∈ Rn e v = (v1, . . . , vm) ∈ Rm são dois vectores. Denotemos esta aplicação por u⊗ v. Temos as seguintes relações: (v1 + v2)⊗ u = v1 ⊗ u + v2 ⊗ u v ⊗ (u1 + u2) = v ⊗ u1 + v2 ⊗ u2 (λv)⊗ u = λ(v ⊗ u) = v ⊗ (λu) Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Problema da multiplicação de complexos Podemos fazer o mesmo para os números complexos chegando a: x = a(c + d) = (a, b)(1, 0)T (1, 1)(c, d)T y = (a + b)d = (a, b)(1, 1)T (0, 1)(c, d)T z = b(d − c) = (a, b)(0, 1)T (−1, 1)(c, d)T Dizer que o produto de dois números complexos pode ser realizado com apenas 3 multiplicações, equivale à igualdade: (a + bi)(c + di) = x · 1 + y · (−1 + i) + z · (−i) Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Problema da multiplicação de complexos Podemos fazer o mesmo para os números complexos chegando a: x = a(c + d) = (a, b)(1, 0)T (1, 1)(c, d)T y = (a + b)d = (a, b)(1, 1)T (0, 1)(c, d)T z = b(d − c) = (a, b)(0, 1)T (−1, 1)(c, d)T Dizer que o produto de dois números complexos pode ser realizado com apenas 3 multiplicações, equivale à igualdade: (a + bi)(c + di) = x · 1 + y · (−1 + i) + z · (−i) Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Problema da multiplicação de complexos Suponhamos que existem u, v, s, t ∈ R2 e W1, W2 ∈ C, tais que: (a + bi)(c + di) = (a, b)(uTv)(c , d)T ·W1 + (a, b)(sT t)(c , d)T ·W2 Mas com isto chegamos a uma contradição pois, tomando 0 6= (a, b) ∈ L{u}⊥ e 0 6= (c, d) ∈ L{t}⊥, obtém-se: (a + bi)(c + di) = (a, b)(uTv)(c , d)TW1 + (a, b)(sT t)(c , d)TW2 = ( (a, b)uT ) ( v(c , d)T ) W1 + ( (a, b)sT ) ( t(c , d)T ) W2 = [ 0 · v(c , d)T ] W1 + [ (a, b)sT · 0 ] W2 = 0 Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Aplicações bilineares Definição (Aplicação Bilinear) Sejam E , V , W espaços vectoriais sobre um corpo. Seja ϕ : E × V → W uma aplicação que satisfaz as seguintes propriedades: ϕ(v1 + v2,u) = ϕ(v1,u) + ϕ(v2,u) ϕ(v,u1 + u2) = ϕ(v,u1) + ϕ(v,u2) ϕ(λv,u) = λϕ(v,u) = ϕ(v, λu) então ϕ diz-se uma aplicação bilinear. Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Notação Denotemos o espaço das matrizes reais, quadradas de ordem n por Mn e denotemos por µn a aplicação Mn ×Mn →Mn dada pela multiplicação de matrizes, (A, B) 7→ AB. (Abreviamos µ2 para µ.) Sejam u, v vectores de Rn e Rm respectivamente e w um vector de W então (u⊗ v)w é a aplicação bilinear de Rn × Rm → W dada por (x, y) 7→ (x(uTv)yT )w. Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Exemplos A aplicação µn : Mn ×Mn −→Mn é bilinear pois: A(B + C ) = AB + AC (A + B)C = AC + BC (λA)B = λ(AB) = A(λB) Encarando C como espaço real (de dimensão 2), a aplicação C× C → C dada pelo produto de dois números complexos é bilinear. A aplicação ϕ : Rn × Rm → Rp dada por ϕ = ∑ (ui ⊗ vi )zi onde ui ∈ Rn, vi ∈ Rm e zi ∈ Rp é bilinear. Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Teorema Seja ϕ : Rn × Rm → W uma aplicação bilinear. Então existem ui ∈ Rn, vj ∈ Rm, wij ∈ W tais que ϕ = ∑ i ,j(ui ⊗ vj)wij . Sejam (ui ) e (vj) bases ortonormadas de Rn e Rm respectivamente. x ∈ Rn e y ∈ Rm =⇒ x = ∑ αiui e y = ∑ βjvj . (ui ) e (vj) bases ortonormadas =⇒ xuTi = αi e vjyT = βj . ϕ bilinear =⇒ ϕ(x, y) = ∑ i ,j αiβjϕ(ui , vj). Assim, ϕ(x, y) = ∑ i ,j(xu T i )(v T j y)ϕ(ui , vj). Conclui-se que ϕ = ∑ i ,j(ui ⊗ vj)wij com wij = ϕ(ui , vj) ∈ W . Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Teorema Seja ϕ : Rn × Rm → W uma aplicação bilinear. Então existem ui ∈ Rn, vj ∈ Rm, wij ∈ W tais que ϕ = ∑ i ,j(ui ⊗ vj)wij . Sejam (ui ) e (vj) bases ortonormadas de Rn e Rm respectivamente. x ∈ Rn e y ∈ Rm =⇒ x = ∑ αiui e y = ∑ βjvj . (ui ) e (vj) bases ortonormadas =⇒ xuTi = αi e vjyT = βj . ϕ bilinear =⇒ ϕ(x, y) = ∑ i ,j αiβjϕ(ui , vj). Assim, ϕ(x, y) = ∑ i ,j(xu T i )(v T j y)ϕ(ui , vj). Conclui-se que ϕ = ∑ i ,j(ui ⊗ vj)wij com wij = ϕ(ui , vj) ∈ W . Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Teorema Seja ϕ : Rn × Rm → W uma aplicação bilinear. Então existem ui ∈ Rn, vj ∈ Rm, wij ∈ W tais que ϕ = ∑ i ,j(ui ⊗ vj)wij . Sejam (ui ) e (vj) bases ortonormadas de Rn e Rm respectivamente. x ∈ Rn e y ∈ Rm =⇒ x = ∑ αiui e y = ∑ βjvj . (ui ) e (vj) bases ortonormadas =⇒ xuTi = αi e vjyT = βj . ϕ bilinear =⇒ ϕ(x, y) = ∑ i ,j αiβjϕ(ui , vj). Assim, ϕ(x, y) = ∑ i ,j(xu T i )(v T j y)ϕ(ui , vj). Conclui-se que ϕ = ∑ i ,j(ui ⊗ vj)wij com wij = ϕ(ui , vj) ∈ W . Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Teorema Seja ϕ : Rn × Rm → W uma aplicação bilinear. Então existem ui ∈ Rn, vj ∈ Rm, wij ∈ W tais que ϕ = ∑ i ,j(ui ⊗ vj)wij . Sejam (ui ) e (vj) bases ortonormadas de Rn e Rm respectivamente. x ∈ Rn e y ∈ Rm =⇒ x = ∑ αiui e y = ∑ βjvj . (ui ) e (vj) bases ortonormadas =⇒ xuTi = αi e vjyT = βj . ϕ bilinear =⇒ ϕ(x, y) = ∑ i ,j αiβjϕ(ui , vj). Assim, ϕ(x, y) = ∑ i ,j(xu T i )(v T j y)ϕ(ui , vj). Conclui-se que ϕ = ∑ i ,j(ui ⊗ vj)wij com wij = ϕ(ui , vj) ∈ W . Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Característica de uma aplicação bilinear Definição (Característica) Seja ϕ : Rn × Rm → W uma aplicação bilinear. A característica de ϕ é o menor natural k para o qual existem u1, . . . ,uk ∈ Rn, v1, . . . , vk ∈ Rm e w1, . . . ,wk ∈ W tais que ϕ = ∑k i=1(ui ⊗ vi )wi (No caso da forma bilinear a característica de ϕ coincide com a característica da matriz que a representa.) Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Exemplos (u⊗ v)w tem característica ≤ 1. A multiplicação de complexos tem característica 3. O produto interno de Rn tem característica n. µ tem característica ≤ 7. Identificando M2 com R4 através de a b c d 7→ (a, b, c, d) µ = u1 ⊗ v1 1 0 0 1 + u2 ⊗ v2 0 0 1 1 + u3 ⊗ v3 0 1 0 1 + +u4⊗v4 1 0 1 0 +u5⊗v5 −1 1 0 0 +u6⊗v6 0 0 0 1 +u7⊗v7 1 0 0 0 . u1 = (1, 0, 0, 1) u2 = (0, 0, 1, 1) u5 = (1, 1, 0, 0) u3 = (1, 0, 0, 0) u6 = (−1, 0, 1, 0) u4 = (1, 0, 0, 1) u7 = (0, 1, 0,−1) v1 = (1, 0, 0, 1) v2 = (1, 0, 0, 0) v5 = (0, 0, 0, 1) v3 = (0, 1, 0,−1) v6 = (1, 1, 0, 0) v4 = (−1, 0, 1, 0) v7 = (0, 0, 1, 1) Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Problema Qual a característica de µ? Se característica de µ for 6, então existem seis pares de vectores ui , vi ∈ R4 e seis matrizes Ai ∈M2 tais que µ = (u1 ⊗ v1)A1 + (u2 ⊗ v2)A2 + · · ·+ (u6 ⊗ v6)A6 Aplicando a ideia usada no caso dos complexos, tomemos 0 6= a ∈ L{u1,u2,u3}⊥ e 0 6= b ∈ L{v4, v5, v6}⊥ e assim µ(a,b) = 3∑ i=1 a(uTi vi )b TAi + 6∑ i=4 a(uTi vi )b TAi = 0 + 0 = 0. Mas isto não nos permite concluir pois, por exemplo, 1 0 0 0 · 0 0 0 1 = 0 0 0 0 . Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Problema Qual a característica de µ? Se característica de µ for 6, então existem seis pares de vectores ui , vi ∈ R4 e seis matrizes Ai ∈M2 tais que µ = (u1 ⊗ v1)A1 + (u2 ⊗ v2)A2 + · · ·+ (u6 ⊗ v6)A6 Aplicando a ideia usada no caso dos complexos, tomemos 0 6= a ∈ L{u1,u2,u3}⊥ e 0 6= b ∈ L{v4, v5, v6}⊥ e assim µ(a,b) = 3∑ i=1 a(uTi vi )b TAi + 6∑ i=4 a(uTi vi )b TAi = 0 + 0 = 0. Mas isto não nos permite concluir pois, por exemplo, 1 0 0 0 · 0 0 0 1 = 0 0 0 0 . Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ O ideal gerado por uma matriz Definição Seja a = (a1, a2, a3, a4). Define-se o conjunto aM2 através de aM2 = {[ a1 a2 a3 a4 ] B : B ∈M2 } . aM2 é um subespaço de M2. aM2 é um ideal direito de M2, pois C ∈ aM2 e B ∈M2 =⇒ CB ∈ aM2 Dado b ∈ R4, define-se o ideal (esquerdo), M2b, de forma análoga. Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Demonstração Supomos que µ tem característica 6: µ = (u1 ⊗ v1)A1 + (u2 ⊗ v2)A2 + · · ·+ (u6 ⊗ v6)A6 L{u1,u2, . . . ,u6} = R4 e assim podemos supor, sem perda de generalidade, que {u1,u2,u3,u4} formam uma base de R4. Seja 0 6= b ∈ L{v4, v5, v6}⊥ então para todo a ∈ R4, µ(a,b) = ∑3 i=1 a(u T i vi )b TAi + ∑6 i=4 a(u T i vi )b TAi = = a(uT1 v1)b TA1 + a(uT2 v2)b TA2 + a(uT3 v3)b TA3. Logo M2b ⊂ L{A1, A2, A3} 6= M2. Conclui-se que M2b tem dimensão 2. Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Demonstração Supomos que µ tem característica 6: µ = (u1 ⊗ v1)A1 + (u2 ⊗ v2)A2 + · · ·+ (u6 ⊗ v6)A6 L{u1,u2, . . . ,u6} = R4 e assim podemos supor, sem perda de generalidade, que {u1,u2,u3,u4} formam uma base de R4. Seja 0 6= b ∈ L{v4, v5, v6}⊥ então para todo a ∈ R4, µ(a,b) = ∑3 i=1 a(u T i vi )b TAi + ∑6 i=4 a(u T i vi )b TAi = = a(uT1 v1)b TA1 + a(uT2 v2)b TA2 + a(uT3 v3)b TA3. Logo M2b ⊂ L{A1, A2, A3} 6= M2. Conclui-se que M2b tem dimensão 2. Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Demonstração Supomos que µ tem característica 6: µ = (u1 ⊗ v1)A1 + (u2 ⊗ v2)A2 + · · ·+ (u6 ⊗ v6)A6 L{u1,u2, . . . ,u6} = R4 e assim podemos supor, sem perda de generalidade, que {u1,u2,u3,u4} formam uma base de R4. Seja 0 6= b ∈ L{v4, v5, v6}⊥ então para todo a ∈ R4, µ(a,b) = ∑3 i=1 a(u T i vi )b TAi + ∑6 i=4 a(u T i vi )b TAi = = a(uT1 v1)b TA1 + a(uT2 v2)b TA2 + a(uT3 v3)b TA3. Logo M2b ⊂ L{A1, A2, A3} 6= M2. Conclui-se que M2b tem dimensão 2. Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Demonstração. Se µ = (u1 ⊗ v1)A1 + (u2 ⊗ v2)A2 + · · · + (u6 ⊗ v6)A6... Teorema Se a,b 6= 0 então a dimensão de aM2 e de M2b é 2 ou 4. De entre v1bT , v2bT , v3bT existem dois não nulos. Suponhamos que v1bT = v2bT = 0. Então de M2b ⊂ L{A3} deduz-se que dimM2b = 1, contradição. Suponhamos que v1bT , v2bT 6= 0. L{A1, A2} ⊂ M2b. u1, u2, u3 lin. indep. =⇒ L{u2, u3}⊥ 6⊂ L{u1}⊥ logo ∃ c ∈ L{u2, u3}⊥ \ L{u1}⊥ e assim M2b 3 (cuT1 v1bT )A1 = µ(c, b), etc. Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Demonstração. Se µ = (u1 ⊗ v1)A1 + (u2 ⊗ v2)A2 + · · · + (u6 ⊗ v6)A6... L{v2, v3, . . . , v6} = R4. Se M2b ⊂ L{v3, v4, v5, v6}⊥ =⇒ L{v3, v4, v5, v6} ⊂ M2b⊥. ∃ vj ∈ {v3, v4, v5, v6} tal que M2b 6⊂ L{vj}⊥. Suponhamos que M2b 6⊂ L{v3}⊥. Seja 0 6= a ∈ L{u4,u5,u6}⊥. Então aM2 ⊂ L{A1, A2, A3}. Teorema Se a 6= 0 e aM2 ⊂M2b então M2b = M2. Para cada x ∈ R4 existe y ∈M2b tal que v3xT = v3yT . µ(a, x)− µ(a, y) ∈ L{A1, A2} ⊂ M2b Logo aM2 ⊂M2b + L{A1, A2} = M2b. Contradição. Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Demonstração. Se µ = (u1 ⊗ v1)A1 + (u2 ⊗ v2)A2 + · · · + (u6 ⊗ v6)A6... L{v2, v3, . . . , v6} = R4. Se M2b ⊂ L{v3, v4, v5, v6}⊥ =⇒ L{v3, v4, v5, v6} ⊂ M2b⊥. ∃ vj ∈ {v3, v4, v5, v6} tal que M2b 6⊂ L{vj}⊥. Suponhamos que M2b 6⊂ L{v3}⊥. Seja 0 6= a ∈ L{u4,u5,u6}⊥. Então aM2 ⊂ L{A1, A2, A3}. Teorema Se a 6= 0 e aM2 ⊂M2b então M2b = M2. Para cada x ∈ R4 existe y ∈M2b tal que v3xT = v3yT . µ(a, x)− µ(a, y) ∈ L{A1, A2} ⊂ M2b Logo aM2 ⊂M2b + L{A1, A2} = M2b. Contradição. Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Demonstração. Se µ = (u1 ⊗ v1)A1 + (u2 ⊗ v2)A2 + · · · + (u6 ⊗ v6)A6... L{v2, v3, . . . , v6} = R4. Se M2b ⊂ L{v3, v4, v5, v6}⊥ =⇒ L{v3, v4, v5, v6} ⊂ M2b⊥. ∃ vj ∈ {v3, v4, v5, v6} tal que M2b 6⊂ L{vj}⊥. Suponhamos que M2b 6⊂ L{v3}⊥. Seja 0 6= a ∈ L{u4,u5,u6}⊥. Então aM2 ⊂ L{A1, A2, A3}. Teorema Se a 6= 0 e aM2 ⊂M2b então M2b = M2. Para cada x ∈ R4 existe y ∈M2b tal que v3xT = v3yT . µ(a, x)− µ(a, y) ∈ L{A1, A2} ⊂ M2b Logo aM2 ⊂M2b + L{A1, A2} = M2b. Contradição. Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Demonstração. Se µ = (u1 ⊗ v1)A1 + (u2 ⊗ v2)A2 + · · · + (u6 ⊗ v6)A6... L{v2, v3, . . . , v6} = R4. Se M2b ⊂ L{v3, v4, v5, v6}⊥ =⇒ L{v3, v4, v5, v6} ⊂ M2b⊥. ∃ vj ∈ {v3, v4, v5, v6} tal que M2b 6⊂ L{vj}⊥. Suponhamos que M2b 6⊂ L{v3}⊥. Seja 0 6= a ∈ L{u4,u5,u6}⊥. Então aM2 ⊂ L{A1, A2, A3}. Teorema Se a 6= 0 e aM2 ⊂M2b então M2b = M2. Para cada x ∈ R4 existe y ∈M2b tal que v3xT = v3yT . µ(a, x)− µ(a, y) ∈ L{A1, A2} ⊂ M2b Logo aM2 ⊂M2b + L{A1, A2} = M2b. Contradição. Eduardo Dias A característica da multiplicação de matrizes Introdução Aplicações bilineares Característica de µ Outros Resultados A característica de µn é maior ou igual a 3n2 − 3n + 1. Em particular, a característica de µ3 é maior ou igual a 19. Existe uma fórmula para µ3 que usa 23 multiplicações. Eduardo Dias A característica da multiplicação de matrizes