lgebra linearverso 12110 de agosto de 2015jernimo c.pellegriniVersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.PellegriniSumrioSumrio iApresentao viiNomenclatura ix1 Espaos Vetoriais 11.1 Estruturas algbricas 11.2 Grupos 41.3 Corpo 61.3.1 Operando com corpos 101.4 Espaos vetoriais 111.5 Subespaos 231.6 Aplicaes 331.6.1 Protocolo Die-Hellman para acordo de chaves [ grupo ] 331.6.2 Cubo de Rubik [ grupo ] 361.6.3 Criptanlise moderna [ corpo; sistemas lineares em corpos ] 371.6.4 Cdigos corretores de erros [ espao vetorial; subespao ] 392 Dimenso e Bases 452.1 Dependncia linear 452.2 Conjuntos geradores e bases 482.3 Isomorsmo e coordenadas 622.4 Mudana de base 672.5 Aplicaes 692.5.1 Fractais [ isomorsmo ] 693 Transformaes Lineares 733.1 O efeito em uma base determina completamente uma transformao 813.2 Kernel e imagem 883.3 Nulidade e posto 913.4 Aplicaes 953.4.1 Transformaes em imagens 954 Matrizes e Transformaes Lineares 101iVersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegriniii SUMRIO4.1 Representao de transformaes como matrizes 1014.1.1 De matrizes para transformaes 1014.1.2 De transformaes para matrizes 1024.2 Propriedades da multiplicao de matrizes 1064.2.1 Matrizes por blocos 1074.2.2 Multiplicao por vetor combinao linear 1104.2.3 Matrizes triangulares 1124.3 Propriedades de matrizes de transformaes 1134.3.1 Mudana de base 1174.3.2 Similaridade 1234.4 Espaos de transformaes 1284.5 Matrizes elementares 1294.6 Sistemas de equaes lineares 1324.6.1 Eliminao de Gauss 1354.6.2 Decomposio LU 1384.6.3 Estabilidade numrica 1444.7 Matrizes complexas 1444.8 Aplicaes 1464.8.1 Clculo de uma nica coluna da inversa [ decomposio LU ] 1464.8.2 Otimizao linear [ base; espao-coluna; dimenso; fatorao LU ] 1464.8.3 Transformaes em imagens [matriz de transformao] 1524.8.4 rbitas celestes [ mudana de base ] 1554.8.5 Cdigos corretores de erros [ base; espao-linha; multiplicao direita ] 1585 Determinantes 1675.1 Volume orientado 1675.1.1 Orientao 1705.2 Determinantes 1715.3 Existncia e unicidade do determinante 1775.4 Calculando determinantes 1785.4.1 Determinantes de ordem 3: regra de Sarrus 1795.4.2 Escalonamento e decomposio LU 1805.4.3 Expanso de Laplace 1805.4.4 Frmula de Leibniz 1825.4.5 Por blocos 1855.5 Matrizes complexas 1855.6 Aplicaes 1865.6.1 Regra de Cramer 1865.6.2 rea de tringulos, volume de pirmides 1905.6.3 Equao da circunferncia passando por tres pontos 1925.6.4 O Teorema do Valor Mdio (generalizado) 1945.6.5 O Wronskiano 1965.6.6 Interpolao 1986 Autovalores, Autovetores e Diagonalizao 207VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.PellegriniSUMRIO iii6.1 Polinmio caracterstico 2136.1.1 Autovalores complexos 2216.1.2 Matrizes complexas Hermitianas 2226.2 Diagonalizao de operadores 2246.3 Transformaes lineares e matrizes no quadradas 2276.4 Diagonalizao simultnea de dois operadores 2276.5 Clculo de autovalores e autovetores 2316.6 Aplicaes 2316.6.1 Potncia de matriz [ diagonalizao ] 2326.6.2 Relaes de recorrncia [ polinmio caracterstico; diagonalizao ] 2336.6.3 Soluo de sistemas de equaes de diferena [ diagonalizao ] 2366.6.4 Exponencial de matriz [ diagonalizao ] 2386.6.5 Soluo de sistemas de equaes diferenciais [ diagonalizao ] 2416.6.6 Cadeias de Markov [ autovalor; autovetor ] 2446.6.7 Classicao de relevncia (pagerank) [ autovalor; autovetor ] 2476.6.8 Clculo de polinmio de matriz [ polinmio caracterstico; teorema de Cayley-Hamilton ] 2486.6.9 Inverso de matrizes [ polinmio caracterstico; teorema de Cayley-Hamilton ] 2496.6.10 Grafos [ autovalores ] 2507 Produto Interno 2597.1 Produto interno e norma 2597.2 ngulos e ortogonalidade 2727.3 Projees 2797.4 Ortogonalizao 2857.5 Diagonalizao de matrizes simtricas 2887.6 Produto interno em espaos complexos 2907.7 Aplicaes 2907.7.1 Soluo de sistemas lineares e mnimos quadrados [ distncia; projeo ] 2907.7.2 Covarincia e correlao [ produto interno; ngulo ] 2917.7.3 Covarincia [ produto interno; matriz de Gram ] 2937.7.4 Otimizao linear (ane scaling) [ projeo, ncleo, escala ] 2948 Operadores Ortogonais e Normais 3038.1 Operadores Ortogonais 3038.1.1 Decomposio QR 3118.2 Operadores normais 3138.3 Decomposio em Valores Singulares 3138.4 Aplicaes 3138.4.1 Anlise de Componentes Principais 3139 Pseudoinversa 3159.1 Calculando pseudoinversas 3189.1.1 Decomposio em posto completo 3189.1.2 Por blocos 3209.1.3 Mtodo de Greville 3229.1.4 Mtodo iterativo de Ben-Israel e Cohen usando maior autovalor 3239.1.5 Usando autovalores 325VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegriniiv SUMRIO9.2 Matrizes complexas 3269.3 Aplicaes 3269.3.1 Sistemas lineares 32610 Forma de Jordan 33110.1 Existncia e clculo da forma de Jordan 33310.1.1 Subespaos invariantes 33310.1.2 Autovetores generalizados 33410.1.3 Existncia da forma de Jordan (para operadores nilpotentes) 33610.1.4 Existncia da forma de Jordan (caso geral) 33910.2 Estabilidade numrica 34010.3 Aplicaes 34010.3.1 lgebra Linear [ forma de Jordan ] 34010.3.2 Equaes Diferenciais [ forma de Jordan ] 34111 Reticulados 34511.1 Ortogonalidade de bases 34711.2 Problemas em reticulados 34811.2.1 Reduo de bases com posto dois: algoritmo de Gauss-Lagrange 34911.2.2 Vetor mais prximo com posto e ortogonalidade altos: algoritmo de Babai 35211.2.3 Posto alto, ortogonalidade baixa (reticulados difceis) 35211.3 Aplicaes 35311.3.1 Criptograa [ reticulados; desvio de ortogonalidade ] 35311.3.2 Cristalograa [ reticulados ] 35512 Formas Quadrticas e Bilineares 35712.1 Formas Bilineares 35712.2 Formas Quadrticas 35812.3 Formas multilineares 36112.4 Aplicaes 36212.4.1 Classicao de cnicas e qudricas 36212.4.2 Classicao de equaes diferenciais parciais [ formas denidas ] 37212.4.3 Mximos e mnimos de funes emRn[ formas denidas ] 37212.4.4 Otimizao quadrtica 37713 Geometria Am e Projetiva 38113.1 Geometria Am 38113.1.1 Espao Am 38313.1.2 Transformaes Am 38513.1.3 Coordenadas Homogneas 38713.2 Geometria Projetiva 38913.2.1 Noes intuitivas 38913.2.2 Coordenadas 39113.2.3 Transformaes Projetivas 39113.3 Aplicaes 391VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.PellegriniSUMRIO v14 Srie de Fourier 39314.1 Funes Peridicas 39314.2 Srie de Fourier 39814.3 Determinao de coecientes 39914.4 Forma exponencial 40614.5 Convergncia 40714.5.1 Convergncia quase sempre 40914.5.2 Convergncia pontual 41214.5.3 Convergncia uniforme 41314.6 Transformada de Fourier 41614.7 Aplicaes 41814.7.1 Equaes diferenciais [ srie de Fourier ] 41814.7.2 Equaes diferenciais parciais: a equao da onda [ srie de Fourier ] 42314.7.3 Msica 42514.7.4 Compresso de dados [ transformada de Fourier ] 42514.7.5 Espectroscopia de infravermelho [ transformada de Fourier ] 42515 Tensores 42915.1 Espao dual e funcionais lineares 42915.2 Covarincia e contravarincia 43015.3 Notao de Einstein 43015.4 Tensores 43115.4.1 Operaes com tensores 43115.4.2 Produto tensorial de espaos vetoriais 43215.5 Aplicaes 432 Reviso: Sistemas Lineares e Matrizes 433.1 Sistemas de equaes lineares 433.1.1 Resoluo de sistemas escalonados por linhas 435.1.2 Resoluo de sistemas lineares na forma geral 436.2 Matrizes 438.2.1 Operaes com matrizes 439.3 Aplicaes 444.3.1 Circuitos eltricos [ sistemas lineares ] 444.3.2 Balanceamento de equaes qumicas [ sistemas lineares ] 445.3.3 Cadeias de Markov [ matrizes ] 446.3.4 Sistemas de Votao [ matrizes ] 448 Induo Finita 451.1 Enunciado do Princpio da Induo Finita 451.2 Demonstraes de igualdades e desigualdades simples 453.3 Induo dupla 456.3.1 Induo emQ 458VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrinivi SUMRIO.4 Induo em estruturas 458.5 Induo em Geometria 459.6 Induo em nmero de operaes com matriz 462.7 Induo em ordem de matriz quadrada 463.8 Demonstrao de corretude de algoritmos 464.9 Induo para trs, com base innita 469.10 Induo emR 470 Orientao de Bases 479 Equaes Diferenciais 483.1 Equao Diferencial Ordinria 485.2 Separao de variveis 485.3 Problemas de valor inicial e de contorno 487.4 Equao Diferencial Parcial 487.5 Aplicaes 488.5.1 Qumica nuclear: decaimento radioativo [ EDO de primeira ordem ] 488.5.2 Mecnica: oscilador harmnico [ EDO de segunda ordem ] 488.5.3 Termodinmica: propagao de calor [ EDP ] 490 Alfabeto Grego 493 Dicas e Respostas 495Ficha Tcnica 513Bibliograa 515ndice Remissivo 519VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.PellegriniApresentaoEste texto foi elaborado como um primeiro curso de lgebra Linear, desenvolvendo conceitos bsicos naprimeira parte e avanando para outros tpicos e aplicaes na segunda parte.O texto comea com espaos vetoriais e aborda matrizes somente aps transformaes lineares. Isso feito por diferentes motivos: primeiro, para que o leitor tenha tempo para digerir os conceitos abstratosapresentados inicialmente. Se a abstrao construda aos poucos, corre-se o risco de no haver tempopara que essas abstraes sejamdevidamente digeridas; almdisso, para no passar inicialmente a impres-so de que a lgebra Linear trata simplesmente de lgebra de matrizes reais, para que de imediato queclaro que espaos vetoriais no so necessariamente compostos apenas de tuplas (h espaos de dimensoinnita que so facilmente descritos), e tambm para ilustrar de imediato a natureza abstrata da lgebra,e da sua relevncia em problemas prticos: ao nal do primeiro captulo h vrios exemplos de uso de es-paos vetoriais em Criptograa, cdigos corretores de erros e na soluo do cubo mgico. H tambm umaboa quantidade de aplicaes ao nal de todos os outros Captulos.Os exemplos e aplicaes so includos no nal dos captulos, e no no incio. Isso contraria a idia deque os conceitos apresentados devem ser motivados. Penso que a motivao deveria ser substituda, pelomenos no incio da leitura, por conana: o leitor deve conar em que existe uma razo para estudar todaa abstrao e o ferramental apresentado, por mais estranhos que lhe paream. Terminando cada captulo,haver a oportunidade de conrmar a utilidade dos tpicos estudados.Os pr-requisitos imprescindveis para a leitura deste livro so Clculoemuma varivel real e GeometriaAnaltica. Alguns dos exemplos farousode Clculoemvrias variveis, nmeros complexos, probabilidadebsica, grafos e equaes diferenciais mas estes exemplos podemser deixados de lado semcomprometer asequncia do texto. Para que o livro seja to autocontido quanto possvel, h umapndice comuma revisode sistemas lineares e matrizes, um introduzindo o mtodo da induo nita, e um com noes bsicas deEquaes Diferenciais.Sees, exemplos e exerccios marcados comestrela () so opcionais, ou porque so difceis ou porqueusamconceitos normalmente no abordados emumprimeiro curso de lgebra Linear, como corpos nitos.viiVersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegriniviii SUMRIOVersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.PellegriniNomenclaturaVetores (elementos de um espao vetorial, no apenas vetores emRn) so grafados em negrito: v, w, . . ..Representamos vetores emRncomo vetores-coluna em todo o texto:v =______v1v2...vn______.Emtextocorridoe emmuitas frmulas, denotamos tais vetores comotranspostas de linhas: v = (v1, v2, . . . , vn)T.Em diversas ocasies, somatrios so denotados apenas por

i. . . ,ao invs den

i=1. . . ,sendo sempre possvel determinar, a partir do contexto, quais os valores do ndice i.Fraes so fatoradas para fora de matrizes sempre que possvel faz-lo, para tornar matrizes maisfacilmente legveis e simplicar operaes de multiplicao:___0161676265613116136___ 16___0 1 172 52 11 13___.No usamos setas para representar os eixos emR2e R3, porque as reservamos para vetores. Por exemplo,o grco da funox45x3x2+5x 1 mostrado na prxima gura.ixVersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrinix SUMRIO6 4 2 2 4 610864224600xyA nomenclatura usada no livro detalhada a seguir.x| O inteiro mais prximo de x, pgina 393(an) sequncia, pgina 17(fn) Sequencia de funes, pgina 4082AConjunto de todos os subconjuntos do conjunto A, pgina 43[v]BCoordenadas do vetor v na base B, pgina 67[A]ijMatriz Aaps remoo da linha i e coluna j, pgina 180[X] Espao gerado pelo conjunto de vetores X, pgina 49[id]Matriz de mudana de base, de para , pgina 117,x| arredondamento para cima (menor inteiro maior ou igual a x), pgina 508 Composio de transformaes lineares (e de funes), pgina 78cof(A, i, j) Cofator do elemento aij da matriz A, pgina 180(X, Y) Correlao entre variveis aleatrias X e Y, pgina 293cov(X, Y) Covarincia entre variveis aleatrias X e Y, pgina 292det A Determinante da matriz A, pgina 171diag(A1, . . . Ak) Matriz diagonal com blocos A1, . . . , Ak formando a diagonal., pgina 108diag(a1, . . . , an) Matriz diagonal com elementos a1, . . . , an na diagonal., pgina 439dimV Dimenso do espao vetorial V, pgina 55E(X) Esperana da varivel aleatria X, pgina 75VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.PellegriniSUMRIO xix| arredondamento para baixo (maior inteiro menor ou igual a x), pgina 508F(f(x)) Transformada de Fourier de f(x), pgina 417T Conjunto de todas as funes de R emR, pgina 15T(L) domnio fundamental do reticulado L, pgina 346id Funo (e transformao) identidade, pgina 73ImT Imagem da transformao T, pgina 88In(M) Inrcia da matriz M, pgina 369u, v Produto interno dos vetores u e v, pgina 259Z2Corpo nito com dois elementos, pgina 8ker T Kernel da transformao T, pgina 88/(B) reticulado com base B, pgina 345 desvio de ortogonalidade, pgina 347 Produto de Hadamard, pgina 40 Frequncia angular de funo peridica, pgina 393 Soma direta de espaos vetoriais, pgina 31 Ou-exclusivo lgico, pgina 8A Matriz dos conjugados de A, pgina 145x Conjugado, pgina 290 Frequncia de funo peridica, pgina 393Projx(v) Projeo de v em vetor ou subespao x, pgina 282Rn[x] Conjunto (e espao vetorial) dos polinmios com grau n, pgina 14XDesvio padro da varivel aleatria X, pgina 2922XVarincia da varivel aleatria X, pgina 292sgn Paridade de uma permutao, pgina 183 Expanso formal/simblica, pgina 398[T]Transformao T. Base para domnio e para contradomnio, pgina 117eiVetor (0, . . . , 1, . . . , 0), pertencente base cannica, pgina 53v w Produto vetorial dos vetores v e w, pgina 3VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrinixii SUMRIOvol A volume do objeto geomtrico A, pgina 391vol A volume do objeto geomtrico A, pgina 170 E lgico, pgina 8AConjugado transposto de A, pgina 145A+Pseudoinversa da matriz A, pgina 315AHConjugado transposto de A, pgina 145AHMatriz adjunta de A, pgina 222C[a, b] Conjunto (e espao vetorial) das funes contnuas em [a, b], pgina 28C0Conjnuto (e espao vetorial) das funes contnuas emR, pgina 27CkConjnuto (e espao vetorial) das funes k vezes diferenciveis emR, pgina 27d(v, w) Distncia entre os vetores v e w, pgina 268EnErro na aproximao de srie comn termos, pgina 409L2Espao de funes quadrado-integrveis, pgina 410LGMatriz Laplaciana do grafo G, pgina 250Mm,nConjunto (e espao vetorial) das matrizes mn, pgina 62O(B) Orientao da base B, pgina 171SnConjunto de todas as permutaes de n elementos, pgina 182SnSoma parcial de srie, pgina 409V(k1, . . . , kn) Matriz de Vandermonde obtida de k1, . . . , kn, pgina 198VEspao dual, pgina 430VEspao dual, pgina 129VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.PellegriniCaptulo 1Espaos VetoriaisA lgebra Linear pode ser vista como uma generalizao natural da Geometria Analtica. Da mesma formaque, na Geometria, somamos pares de vetores e multiplicamos vetores por escalares, podemos faz-lo comoutros objetos matrizes (A+B, kA), funes ((f +g)(x), kf(x)), sequncias ((an) + (bn), k(an)).A lgebra tem como objeto de estudo o comportamento de operaes denidas sobre conjuntos. Algebra Linear trata epecicamente de espaos vetoriais: conjuntos onde so denidas as operaes de somae multiplicao, de forma que que bem denida tambm a expresso ax +b.Os espaos vetoriais so um dos mais importantes exemplos de estrutura algbrica.A idia abstratade espao vetorial generaliza o conceito de vetores no espao tridimensional de duas maneiras. Primeiro,espaos vetoriais podem ter dimenso maior que tres. E segundo, denimos espaos vetoriais no apenascom vetores geomtricos, mas com diferentes objetos matemticos (por exemplo nmeros, matrizes,polinmios, funes) e podemos tratar desses objetos de forma unicada.A m de melhor contextualizar a denio de espao vetorial, este Captulo traz uma breve descriodo que uma estrutura algbrica, descrevendo tambm grupos e corpos.1.1 Estruturas algbricasAlm de nmeros, podemos somar e multiplicar outros objetos o exemplo mais simples talvez seja ode matrizes. Quando denimos soma e multiplicao para objetos diferentes, estas operaes podem ouno ter propriedades semelhantes.Tanto para nmeros reais como para matrizes, a soma associativa:a + (b +c) = (a +b) +c. No entanto, a multiplicao de nmeros reais comutativa (ab = ba), mas acomutatividade no vale, de forma geral, para a multiplicao de matrizes.Ao estudar diferetes tipos de objetos e operaes denidas sobre eles, identicamos algumas classes deobjetos para os quais as operaes se comportam de maneira semelhante. Damos a essas classes de objetoscom operaes algbricas o nome de estrutura algbrica.Estrutura algbrica (ou sistema algbrico) o nome dado a um conjunto com algumas operaes denidassobre ele. Por exemplo, o conjunto dos nmeros reais com as operaes de soma e multiplicao, (R, +, ) uma estrutura algbrica. O conjunto das matrizes com a operao de soma de matrizes e a operao demultiplicao por escalar (M, +, ) outra estrutura algbrica. Umterceiro exemplo de estrutura algbrica o conjunto dos inteiros com a operao de soma, (Z, +). Cada um destas estruturas tem caractersticasdiferentes, e pode ser classicada de maneiras diferentes, como veremos a seguir.1VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini2 CAPTULO 1.ESPAOS VETORIAISAntes de denirmos algumas estruturas algbricas, denimos o tipo de operao que acompanharoestas estruturas. Neste texto, trataremos de operaes com dois argumentos, chamadas de operaes bin-rias.Denio 1.1 (Operao binria). Uma operao em um conjunto A uma funo que leva um ou maiselementos de Aem outro elemento de A ou seja, uma funo f : AA A A.Dizemos que uma operao binria se aceita dois argumentos ou seja, da forma f : AA A.Dizemos que uma operao binria associativa, se a(bc) = (ab)c e comutativa, se ab = ba.Um elemento e A neutro para a operaose para todo a A, ae = ea = a. Exemplo 1.2. EmR, as operaes de soma e multiplicao so associativas e comutativas, porquex +y = y +x (comutatividade)x + (y +z) = (x +y) +z (associatividade)xy = yx (comutatividade)x(yz) = (xy)z (associatividade)No entanto, as operaes de diviso e subtrao no so comutativas. A subtrao associativa, e a divisono :x y ,= y x (no vale a comutatividade)x (y z) = (x y) z (associatividade)x/y ,= y/x (no vale a comutatividade)x/(y/z) ,= (x/y)/z (no vale associatividade)O neutro para soma o zero, e o neutro para multiplicao o um porque0 +x = x(1)x = xNo denimos neste texto neutro para subtrao e diviso, porque as operaes no so comutativas, e oneutro e teria que satisfazer x e = e x = x, e x/e = e/x = x, que no sera possvel. Exemplo 1.3. No conjunto de matrizes quadradas de ordemn, a operao de soma comutativa e associ-ativa, porque para duas matrizes Ae B, temosA+B = B +A (comutatividade)A+ (B +C) = (A+B) +C (associatividade)No entanto, a operao de multiplicao associativa, mas no comutativa:AB ,= BA (no vale a comutatividade)A(BC) = (AB)C (associatividade)O neutro para a soma de matrizes a matriz zero (ou seja, a matriz cujos elementos so todos zero).VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.1.ESTRUTURAS ALGBRICAS 3O neutro para multiplicao de matrizes a identidade, porque, apesar da multiplicao de matrizes noser comutativa, temosJA = AJ= A,para toda matriz quadrada A. Exemplo 1.4. O produto vetorial emR3 denido comov w = (x2y3 x3y2)e1+ (x3y1 x1y3)e2+ (x1y2 x2y1)e3,onde e1, e2 e e3 so os vetores unitrios nas direes dos eixos x, y e z (tambm os chamamos de versores).O resultado do produto vetorial v w um vetor s, perpendicular tanto a v como a w. Por exemplo, sev = (3, 0, 0)Te w = (0, 2, 0)T, o produto vetorial s = v w (0, 0, 6)T, ortogonal a ambos.A magnitude de s zero quando v e w so paralelos e igual ao produto das magnitudes de v e w quandoestes so perpendiculares.Esta operao no comutativa, porquev w = (w v).A operao tambm no associativa, porqueu (v w) um vetor no mesmo plano que v e w, enquanto(u v) w um vetor no mesmo plano que u e v. Denio 1.5 (Fechamento).Seja A um conjunto com uma operao , e seja B A. Dizemos que B dito fechado sob a operaose e somente se a operao com dois elementos de Bsempre resulta em outroelemento de B ou seja, x, y B, xy B. VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini4 CAPTULO 1.ESPAOS VETORIAISExemplo 1.6. As quatro operaes aritmticas denidas nos reais so operaes binrias. Alm disso, nosreais a soma e a multiplicao so comutativas (a+b = b+a) e associativas (a+ (b+c) = (a+b) +c).Os reais so fechados para as quatro operaes.Poderamos tentar denir as quatro operaes aritmticas para os inteiros, mas no vale o fechamento:a operao de diviso no temcomo ser denida. Aintuio nos diz que podemos dividir 9/3 e obter 3, masno o podemos fazer para quaisquer dois inteiros por isso no denimos esta operao para o conjuntodos inteiros, porque os inteiros no so fechados para a diviso. 1.2 GruposComo primeiro exemplo de estrutura algbrica, tomamos os grupos.Denio 1.7 (Grupo). Umgrupo umconjunto no-vazio Gassociado a uma operao binria: GG Gtendo as propriedades listadas a seguir. Associatividade: (ab)c = a(bc). Existencia de neutro: Deve existir um elemento neutro e Gpara a operao de grupo: e G :ae = ea = a. Existencia de inverso: Para todo a G, h um inverso at Gtal que aat= ata = e.Se a operao do grupo for comutativa, dizemos que o grupo comutativo (ou abeliano1). Exemplo 1.8.Os inteiros com a operao usual de soma formam um grupo: (i) a soma de dois inteiros uminteiro; (ii) a soma associativa; (iii) o inteiro zero neutro para soma; e (iv), para todo inteiro a, existeum inteiro a tal que a + (a) = 0. O grupo tambm comutativo. Os conjuntos Q, R e C tambm formam grupo com a operao usual de adio.Demonstramos um teorema bsico sobre grupos.Teorema 1.9. Seja Gum grupo e x G. Ento o inverso xt de x nico emG.Demonstrao.Seja x Ge a, b inversos de x. Entoa = ae= a(xb) xb = e, b inverso de x= (ax)b associatividade= eb ax = e, a inverso de x= b. Exemplo 1.10.O conjunto { +1, 1 } com a operao usual de multiplicao um grupo: (i) 11, 11,11, 11 pertencem ao grupo; (ii) a operao associativa; (iii) 1 neutro; (iv) tanto 1 como 1 soseus prprios inversos. 1Abeliano refere-se ao matemtico Noruegus Niels Henrick Abel, que deerminou que a comutatividade de certos grupos estavarelacionada com a possibilidade de clculo das razes de polinmios.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.2.GRUPOS 5Exemplo 1.11. O conjunto de triplas2(x, y, z)T R3, que representamvetores no espao tridimensional,com a operao de soma de vetores:(x, y, z) + (a, b, c) = (x +a, y +b, z +c) umgrupo: (i) a soma de dois vetores umvetor tambmcomtrs nmeros reais; (ii) a soma associativa;(iii) o vetor zero neutro; (iv) para todo vetor v=(x, y, z), existe um vetor v=(x, y, z) tal quev + (v) = (0, 0, 0). Alm disso, o grupo comutativo. Exemplo 1.12.O conjunto R com a operao de exponenciao no um grupo, porque no vale a asso-ciatividade ((ab)c,= a(bc)). Exemplo 1.13. Oconjunto de todas as funes de RemR, coma operao de soma de funes, umgrupo. A soma de funes associativa:f(x) + (g(x) + h(x)) = (f(x) + g(x)) + h(x), para todas funesf, g, h e todo x R. Afuno zero, z(x) = 0, o elemento neutro para a operao de soma: f(x)+z(x) = f(x)+0 = f(x),para todos f e x. H um inverso para toda funo: f(x) tem como inversa a funog(x) =f(x), porquef(x) +[f(x)] = z(x). Exemplo 1.14. Dadas duas funes f e g, a composio de f comg, que denotamos f g, tal que f g(x) =f(g(x)).Por exemplo, se f(x) = 1/x e g(x) = log(x), ento (f g)(x) 1/ log(x).O conjunto de todas as funes bijetoras de reais em reais com a operao de composio um grupo: a composio de funes associativa: f (g h) = (f g) h. A funo identidade f(x) = x o elemento neutro para a operao de composio porque para todafuno g, f(g(x)) = g(x). Como nos restringimos ao conjunto das funes bijetoras, todas tem inversa: f f1 a identidade.

Exemplo 1.15. O conjunto das matrizes quadradas de ordemn, coma operao de soma de matrizes, umgrupo, porque: A soma de duas matrizes n n resulta em outra matriz n n. A soma de matrizes associativa. A matriz Z com todas as entradas iguais a zero funciona como elemento neutro, porque A+Z = Apara toda matriz A. Toda matriz Atem inverso para a operao de soma: A+ [(1)A] = Z, onde (1)A a matriz Acom seus elementos multiplicados por 1, e Z a matriz zero.2Neste texto, adotamos a representao de vetores como coluna por padro.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini6 CAPTULO 1.ESPAOS VETORIAISJ o mesmo conjunto, das matrizes quadradas de ordem n, com a operao de multiplicao de matrizes,no um grupo, porque nem toda matriz tem inversa.No entanto, o conjunto das matrizes no-singulares de ordem n, com a operao de multiplicao dematrizes, um grupo. Exemplo 1.16. O conjunto R \ { 1 } com a operao , denida comoab = ab +a +b um grupo: (i) se a, b ,=1, ento ab + a + b ,=1 e portanto pertence ao grupo; (ii) a operao associativa; (iii) zero identidade para ; (iv) o inverso de a a/(a +1).Desenvolvemos detalhadamente as propriedades (ii) e (iii).(ii)(ab)c = (ab +a +b)c= (ab +a +b)c + (ab +a +b) +c= abc +ac +bc +ab +a +b +c= abc +ac +ab +a +bc +b +c= a(bc +b +c) +a +bc +b +c= a(bc)(iii)a aa +1=a2a +1+a aa +1=a2a +1a(a +1) aa +1=a2+a2+a aa +1= 0.O grupo tambm comutativo. Exemplo 1.17. Dado um natural n>0, o conjunto de todas as matrizes invertveis nn um grupocom a operao usual de multiplicao de matrizes: (i) se A,B so nn, ento AB ser tambm umamatriz nn; (ii) a multiplicao de matrizes operao associativa; (iii) o elemento identidade a matrizidentidade (iv) todas as matrizes do grupo so invertveis.Este grupo, no entanto, no comutativo, j que a multiplicao de matrizes no , de maneira geral,comutativa. 1.3 CorpoDenio 1.18. Umcorpo consiste de umconjunto e duas operaes, denotadase +, comas propriedadeslistadas a seguir. As duas operaes so associativas.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.3.CORPO 7 As duas operaes so comutativas. Vale a distributividade desobre +. H elementos neutros 0 para soma e 1 para multiplicao. Todo elemento do corpo tem um inverso aditivo. Todo elemento diferente de 0 tem inverso multiplicativo. Exemplo 1.19. (Q, +, ), (R, +, ) e (C, +, ) so corpos.Para todos estes conjuntos, + eso associativas e comutativas para nmeros reais. Vale a distributividade: a(b +c) = ab +ac para quaisquer a, b e c reais. Ozero neutro para soma de reais: a+0 = apara todo a; Oum neutro para multiplicao: 1a = apara todo a. Para todo real a existe um inverso aditivo, (1)a, tal que (1)a +a = 0. Todo a ,= 0 tem inverso multiplicativo, que denotamos a1, tal que aa1= 1.O mesmo argumento pode ser repetido para Qe C.H diferenas importantes entre estes trs corpos: o corpo dos racionais no completo (no contmos irracionais, que no podem ser representados como frao); o corpo dos reais completo e ordenado,mas no inclui solues para a inequao x23 perde-mos a possibilidade de visualizar o espao, mas ainda assim as operaes comn coordenadas so anlogasquelas emR2e R3). Exemplo 1.28. Considere o conjunto de vetores emR2, com as seguintes operaes: A operao usual de multiplicao or escalarVersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.4.ESPAOS VETORIAIS 13 A seguinte operao de soma de vetores:(a, b)T(x, y)T=_ax,_by_T.Se trocarmos a soma de vetores por esta operao, no teremos um espao vetorial, porque esta operaono associativa, como ca claro ao calcularmos (i) (uv)w (a seguir, esquerda); e (ii) u(vw)(a seguir, direita):(i)(u v) w = (u1v1,u2v2)T(w1, w2)T=__w1u1v1,_w2u2v2_T(ii)u (v w) = (u1, u2)T(v1w1,v2w2)T=__u1v1w1,_u2v2w2_TAssim, (R2, , ) no espao vetorial. Antes dos prximos exemplos, demonstramos alguns fatos bsicos a respeito de espaos vetoriais.Teorema 1.29. Seja V um espao vetorial e u, v V. Entoi) Se u + v = v ento u = 0.ii) 0v = 0.iii) Para todo v, v nico, e v = (1)v.iv) c0 = 0 para qualquer escalar cv) Existe um nico w V tal que u + w = v.Demonstrao.Demonstraremos cada item na ordem em que aparecem no enunciado.(i)u + v = vu + v + (v) = v + (v)u = 0(ii) 0v = (0 +0)v = (0v) + (0v). Pela propriedade anterior (i) temos necessariamente v = 0.(iii) Sejam v e vt dois opostos de v, ou seja,v + v = 0vt + v = 0.Ento v e vt so iguais:v = v +0 = v + (v + vt)= (v + v) + vt= 0 + vt= v.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini14 CAPTULO 1.ESPAOS VETORIAISAlm disso, temosv + (1)v = 1v + (1)v = (1 1)v = 0v = 0.e portanto = v = (1)v.(iv) k0 = k(v + (v)) para todo v. Usando (iii) que acabamos de provar, temosk(v + (v)) = k(v + (1)(v))= kv + (k)(v)= (k k)v= 0v,que pela propriedade (ii) acima, igual a 0.(v) Sejam u, v, w tais que u + w = v. Entou + w = vu u + w = v uw = v u.Como v + (u) denido de forma nica porque u nico (conforme a propriedade (iii) acima), w nico. Exemplo 1.30 (polinmios).Denotamos o conjunto de todos os polinmios emx com grau n e coeci-entes reais por Rn[x].Polinmios podem ser somados e multiplicados por escalares: A soma de dois polinmios anxn+an1xn1+ +a0 e bnxn+bn1xn1+ +b0 (an +bn)xn+ (an1 +bn1)xn1+ + (a0 +b0). (1.1)Por exemplo,_3x3+2x28_+_x3+x +1_ = (3 1)x3+ (2 +0)x2+ (0 +1)x + (8 +1)= 2x3+2x2+x 7. A multiplicao de um real k por um polinmio anxn+an1xn1+ +a0 igual akanxn+kan1xn1+ +ka0. (1.2)Por exemplo,7_3x3+4x21_ = 7(3)x3+7(4)x2+7(1)= 21x3+28x27.Para qualquer n 0, Rn[x] um espao vetorial. Como estamos trabalhando compolinmios reais, consideramos que o o corpo subjacente comsendoR.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.4.ESPAOS VETORIAIS 15 A soma de dois polinmios de grau n resulta em outro polinmio de grau n, conforme a equa-o 1.1. A multiplicao de um polinmio de grau npor um escalar resulta em outro polinmio de mesmograu (ou em zero, se o escalar for zero), conforme a equao 1.2. A soma de polinmios associativa: dados tres polinmios p(x), q(x), e r(x), ento(p(x) +q(x)) +r(x) = p(x) + (q(x) +r(x)). A multiplicao de um polinmio por um escalar associativa: sejamp(x), q(x), e r(x) trs polin-mios e c, d nmeros reais. Entoc_dp(x) = (cd)p(x)p(x) +_q(x) +r(x) =_p(x) +q(x)+r(x). A soma de polinmios comutativa: p(x) +q(x) = q(x) +p(x). Vale a distributividade da multiplicao sobre a soma. Sejamp(x) e q(x) polinmios e c, d nmerosreais. Temosc_p(x) +q(x) = cp(x) +cq(x)(c +d)p(x) = cp(x) +dp(x) O nmero zero , ele mesmo, um polinmio, e a soma de um polinmio p(x) com zero resulta emp(x). Assim, 0 elemento neutro para soma. para todo polinmio p(x) com grau n h um outro, de mesmo grau (p(x), o polinmio p(x)multiplicado por 1), tal que p(x) + (p(x)) = 0. A multiplicao de um polinmio por 1 no modica o polinmio. Exemplo 1.31 (funes).Seja T(R) o conjunto de todas as funes de R em R. Por exemplo, f(x)=2x,g(x)= tan(x) so elementos de T(R). Podemos somar duas funes e multiplicar uma funo por umescalar: sejamf, g T. Ento, A soma de f comg f +g, tal que (f +g)(x) = f(x) +g(x). A multiplicao de f por um nmero real k kf, tal que (kf)(x) = k(f(x)).O conjunto T, com as operaes de soma de funes e multiplicao por escalar, um espao vetorial: A soma de funes comutativa:(f +g)(x) = f(x) +g(x) = g(x) +f(x) = (g +f)(x). A multiplicao de funo por escalar associativa:c(d(f(x)) = (cd)f(x)VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini16 CAPTULO 1.ESPAOS VETORIAIS A soma de funes associativa:_(f +g) +h(x) =_f(x) +g(x)+h(x)= f(x) +g(x) +h(x)= f(x) +_g(x) +h(x)]=_f + (g +h)(x). Vale a distributividade da multiplicao sobre a soma:k(f +g)(x) = k_f(x) +g(x)_ = kf(x) +kg(x). A funo constante f(x) = 0 o neutro aditivo: para toda funo g,(f +g)(x) = f(x) +g(x) = 0 +g(x) = g(x). Toda funo f tem um inverso aditivo, que (1)f._f + (1)f(x) = f(x) + (1)f(x) = f(x) f(x) = 0 = z(x),onde z(x) a funo constante zero. A multiplicao de uma funo por 1 no a modica. Exemplo 1.32 (nmeros reais, operaes trocadas).As operaes usadas em espaos vetoriais no preci-sam ser a soma e multiplicao usuais. Elas precisam apenas ter as propriedades listadas na denio deespao vetorial. Por exemplo, podemos denir o seguinte espao vetorial: O conjunto de vetores R (os nmeros reais exceto o zero); O corpo usado R; A operao de soma de vetores a multiplicao de reais: u v = uv A operao de multiplicao por escalar a exponenciao: c v = vcNeste espao, o elemento identidade para soma deve ser necessariamente 1: x1=x. O inverso aditivode cada elemento x x1. Exemplo 1.33 (matrizes). O conjunto de todas as matrizes reais mn, que denotamos /mn, umespao vetorial: podemos somar matrizes e multiplic-las por escalares reais, e as propriedades necessriasso mantidas. Este um espao vetorial sobre R, j que os escalares que multiplicamos pelas matrizes soreais. Exemplo 1.34.Este exemplo aborda a relao entre os vetores de umespao e o corpo subjacente, e ilustraum fato muito importante.Tentaremos construir um espao vetorial de duas maneiras parecidas.Umadelas funcionar e a outra no.Se tomarmos todas as matrizes 2 2 com coecientes reais, mas usarmos o corpo Qpara os escalares,no teremos problemas.Ao multiplicarmos um escalar racional pela matriz real, obtemos outra matrizreal. Por exemplo,mn_ 0e2_ =_mn0emnm2n_.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.4.ESPAOS VETORIAIS 17Assim, podemos ter o corpo subjacente igual a Q, mas com matrizes reais como vetores. Temos um espaovetorial sobre Q.J o contrrio no possvel: suponha que queiramos usar apenas matrizes 2 2 racionais e escalaresreais, portanto V o conjunto destas matrizes e exclumos assim todas as matrizes que tem elementosirracionais. As operaes podero resultar em matrizes reais:3_1 03 2_ =_ 3 033 23_.Esta ltima matriz tem elementos irracionais, e no pertence a V, portanto no temos um espao vetorial.

Exemplo 1.35 (sequncias). Comeamos este exemplo com a denio de sequncias.Denio 1.36 (sequncia). Uma sequncia uma funo de N emR. Sequencias normalmente so deno-tadas por (an), (bn). O n-simo termo da sequncia (ou seja, a valor funo para o argumento igual a n) usualmente denotado por an, bn, etc, sem os parnteses, ao invs da notao tradicional para funesa(n), b(n), etc. Por exemplo, podemos denir uma sequncia (an):a1= 2an= 2an1 +1Temos ento a1= 5, a2= 11, a3= 23, . . ..Um exemplo bastante conhecido a sequncia de Fibonacci, dada porF1= 1F2= 1Fn= Fn1 +Fn2.A seguir mostramos os primeiros nmeros da sequncia de Fibonacci.F1= 1 F5= 5F2= 1 F6= 8F3= 2 F7= 13F4= 3 F8= 21Sejam(an), (bn), . . . sequncias. Denimos as operaes de soma de sequncias e multiplicaode sequn-cia por escalar da maneira natural: A soma de duas sequncias (cn) = (an) + (bn) sequencia onde cada termo ci a soma de termosa +i +bi. A multiplicao de uma sequncia (an) por um nmeor real k a sequncia (cn)=k(an), cujostermos so ci= kci.Por exemplo, se (an) = (2, 4, 6, 8, . . .) a sequencia dos pares comeandocomdois, e (bn) = (10, 20, 30, 40, . . .) a sequncia dos mltiplis de dez, comeando com dez, ento(an) + (bn) = (12, 24, 36, 48, . . .)3(an) = (6, 12, 18, 24, . . .)Ento o conjunto de todas as sequencias um espao vetorial:VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini18 CAPTULO 1.ESPAOS VETORIAISi) a soma de sequncias associativa e comutativa;ii) a multiplicao de sequncia por escalar associativa;iii) a sequncia zn= 0 neutra para soma de sequncias;iv) para toda sequncia (an), existe uma sequencia (an) tal que (an) + (an) = (zn). Exemplo 1.37 (solues de equao diferencial).Uma equao diferencial ordinria uma equao envol-vendo uma funo e uma ou mais de suas derivadas. Uma resumida introduo s Equaes Diferenciais dada no Apndice .Considere a equao diferencialytt y = 0. (1.3) A equao linear, porque da forma any(n)+an1y(n1)+ +a1y +a0= f(x). A equao homognea, porque apenas a varivel dependente aparece na equao no vemos avarivel independente nem constantes (a0= 0, f(x) = 0).As solues da equao 1.3 so da formay = aexbex,porque para todo x R,d2dx2aenbeyddxaenbey= 0.onde a e b so constantes arbitrrias. As solues formam um espao vetorial: a soma de duas soluesresulta emoutra soluo sejam(a,b) e (, ) as constantes que determinamduas solues diferentes paraa EDO. Entoaexbex+exex= (a +)ex (b +)exA multiplicao por escalar tambm resulta em outra soluo:c(aex+bex) = (ca)ex+ (cb)ex.Finalmente, as propriedades de espao vetorial valem: (i) a soma de solues associativa e comutativa;(ii) a multiplicao por escalar associativa; (iii) y = 0 soluo (coma = b = 0), e funciona como neutroaditivo; (iv) toda soluo tem oposto basta multiplic-la por 1; (v) multiplicar 1 por uma soluo no amodica.O conjunto de solues para qualquer EDO linear homognea sempre um espao vetorial.Uma excelente introduo s Equaes Diferenciais o livro de Tenenbaum em Pollard [TP63]. Maisresumidos, os livros de Coddington [Cod61] e Bear [Bea62] so tambm timos textos sobre o assunto. Exemplo 1.38 (variveis aleatrias). Seja o espao amostral de um experimento aleatrio. Uma varivelaleatria real uma funo X : R.Por exemplo, se o espao amostral o conjunto de pessoas em um prdio, a funo que mapeia cadapessoa em sua massa corporal uma varivel aleatria.O conjunto de todas as variveis aleatrias em umespao vetorial quando usamos a operao usualde soma de variveis aleatrias, e a multiplicao de uma varivel aleatria por escalar real.SejamAe B duas variveis aleatrias denidas no mesmo espao amostral , e seja C = A+B. Paratodo evento simples , C() = A() +B(). Fica portanto claro que:VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.4.ESPAOS VETORIAIS 19 A soma de variveis aleatrias associativa e comutativa. A multiplicao de varivel aleatria por escalar distributiva sobre a soma. A varivel aleatria Z, que leva todo elemento de em0, o elemento neutro para adio. Se A varivel aleatria, ento a varivel aleatria A, que leva os elementos do espao amostralaos valores opostos aos que Aleva, tambm . Multiplicar uma varivel aleatria por 1 no a modica.Mostramos ento que o conjunto das variveis aleatrias reais emummesmo espao amostral umespaovetorial sobre R. Exemplo 1.39 (sequncias de bits).Mencionamos no exemplo 1.22 o corpo Z2, onde as operaes so oe () e o ou-exclusivo (). Denimos agora um espao vetorial sobre este corpo, de maneira anlogaa Rnsobre os reais. Cada vetor uma sequncia de n bits, e as operaes so: Soma: feita elementoa elemento somar ovetor b = (b1, b2, . . . , bn) comovetor bt= (bt1, bt2, . . . , btn)resulta em (b1 bt1, b2 bt2, . . . , bn btn). Por exemplo,(0, 1, 0, 1, 1) (0, 0, 1, 1, 0)= (0, 1, 1, 0, 1) Multiplicao por escalar: feita elemento a elemento multiplicar c pelo vetor (b1, b2, . . . , bn) re-sulta em(cb1, cb2, . . . , cbn). Como h somente dois escalares no corpo (0 e 1), listamos aqui o efeitoda multiplicao de vetores por eles.1 (b1, b2, . . . , bn) = (b1, b2, . . . , bn)0 (b1, b2, . . . , bn) = (0, 0, . . . , 0).Este espao chamado de Zn2. Exemplo 1.40 (ciclos em grafo).Um grafo uma representao grca de uma relao em um conjunto.Grafos tem aplicao em uma enorme quantidade de reas das Engenharias, da Computao e da Matem-tica. A gura a seguir mostra exemplos de grafos.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini20 CAPTULO 1.ESPAOS VETORIAIS usual dar nomes aos ns, e desenhar o grafo com os nomes de cada n seu lado.Para poder trabalhar com grafos como objetos matemticos, precisamos dar a eles uma denio for-mal. Denimos um grafo como um par (V, E), onde V um conjunto de vrtices (representados graca-mente como pontos) e E um conjunto de arestas (gracamente so os traos que unem vrtices), deforma que cada aresta emE seja um conjunto de dois dos vrtices emV.Damos um exemplo de grafo na prxima gura.abcdefO conjunto de vrtices do grafo V= {a, b, c, d, e, f}.As arestas soE =_{a, c}, {a, d}, {b, c},{b, e}, {b, f}, {c, d}_.Um subgrafo uma parte de um grafo.Denio 1.41 (subgrafo).Seja G = (V, E) um grafo. Um subgrafo de G um grafo Gt= (Vt, Et) tal queVt V e Et E. O grafo em negrito na gura a seguir um subgrafo do grafo anterior. Neste texto, quando quisermosmostrar um subgrafo, ele ser desenhado em negrito sobre o grafo original, que ser desenhado em tomde cinza claro.abcdefVersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.4.ESPAOS VETORIAIS 21O vetor caracterstico de um conjunto de arestas um vetor comE posies. A posio i do vetor um se eiest no subgrafo, e zero se no est. Por exemplo, o vetor caracterstico do subgrafo que mostramos {a, b} {a, c} {a, d} {a, e} {a, f} {b, c} {b, d} {b, e} {b, f} {c, d} {c, e} {c, f} {d, e} {d, f} __________________________01000000110000__________________________Os elementos do vetor caracterstico so 0 e 1. Ser conveniente usarmos as operaes de Z2 nestes vetores.Multiplicar um vetor por 1 o mesmo que realizar a operao de e, e portanto resulta no mesmo vetor(no modica o subgrafo):1(0, 1, 1, 0, 0, 1)T= (0, 1, 1, 0, 0, 1)T.A multiplicao por zero resulta no vetor zero (e portanto no grafo sem arestas, contendo somente osvrtices), ou seja, multiplicar um subgrafo por zero o faz desaparecer.A soma de dois vetores feita elemento-a-elemento, com a operao de soma em Z2 (ou seja, usandoou-exclusivo):(0, 1, 1, 0, 0, 1)T(1, 1, 0, 1, 0, 1)T= (1, 0, 1, 1, 0, 0)T.Em um grafo, esta operao representa a soma de dois subrafos: se uma aresta existe somente em um dossubgrafos, ela passa a existir na soma. Se uma aresta existe nos dois subgrafos, ela deixa de existir na soma.A gura a seguir ilustra a soma de dois subgrafos. Observe que as arestas (a, b), (b, c) e (d, e) existiam emambos os grafos, e no existem na soma (elas aparecem em cinza claro na ilustrao, apenas para facilitarsua identicao).abcdeabcdeVersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini22 CAPTULO 1.ESPAOS VETORIAIS=abcdeUm ciclo em um grafo uma sequncia de arestas (e1, e2, . . . , ek) formam um caminho, iniciando com umvrtice e terminando nele mesmo6. A gura a seguir ilustra um ciclo em um grafo; o ciclo formado pelosvrtices (a2, a3, b1, b0).a0a1a2a3a4b0b1b2b3b4Quando somamos dois grafos, cada um composto por ciclos disjuntos (isto , ciclos que no compartilhamarestas), o resultado tambm umgrafo composto por ciclos disjuntos. No demonstraremos este fato, masilustramos com um exemplo. A gura a seguir mostra dois grafos, Ge H. Estes grafos tem dois vrtices (ce d) e uma aresta (cd) em comum.G =acdbkjlH =cdehgiO resultado da soma dos dois grafos, GH, mostrado a seguir.6Esta denio est simplicada. Para mais detalhes, o leitor poder consultar a literatura de Teoria dos Grafos por exemplo, olivro de Bondy e Murty [BM08]VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.5.SUBESPAOS 23acehdbgikjlSeja C a unio dos subgrafos sem arestas com o conjunto dos subgrafos de G que consistem de unies deciclos. C com as operaes que denimos um espao vetorial sobre Z2: Grafos sem arestas so o elemento neutro (zero), e sua soma com qualquer outro grafo de ciclosresulta no prprio grafo de ciclos; A soma de dois ciclos resulta em um ciclo; A multiplicao de um elemento por 1 resulta no prprio elemento; por 0 resulta no grafo sem ares-tas. 1.5 SubespaosDenio 1.42 (Subespao).Seja V um espao vetorial, e seja tambm U V. Se as mesmas operaesque tornamV umespao vetorial7tambmtornamUumespao vetorial, ento U umsubespao de V. Teorema 1.43. Todo espao vetorial V no trivial tem pelo menos dois subespaos: o prprio V e o espao trivial.Demonstrao.O espao trivial subespao de qualquer espao V porque { 0 } V. Como s h um elemento no espao trivial, no h vetores a somar. A multiplicao de qualquer escalar por 0 associativa: (cd)0 = c(d0) = 0. O zero neutro para adio (0 + 0 = 0). Para todo vetor no espao trivial (ou seja, somente para o zero), 0 + 0 = 0. A multiplicao de 1 por 0 igual a 0 (ou seja, no modica o vetor zero).Claramente V tambm subespao de V, porque V V. Exemplo 1.44. Considere o espao R3. O conjunto de pontos da forma (v1, v2, 0) umsubespao, porque:(i) a soma de dois pontos desta forma resulta emoutro tambmda mesma forma: (u1, u2, 0)+ (v1, v2, 0) =(u1 + v1, u2 + v2, 0), e (ii) a multiplicao por escalar tambm resulta em outro ponto da mesma forma:7Alguns autores dizem que U munido das mesmas operaes de V.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini24 CAPTULO 1.ESPAOS VETORIAISc(v1, v2, 0)= (cv1, cv2, 0). Alm disso, (i) a soma de vetores (os pontos) associativa e comutativa; (ii) amultiplicao de vetores por escalar associativa:c(du) = c(d(u1, u2, 0))= c(du1, du2, 0)= (cdu1, cdu2, 0)= (cd)(u1, u2, 0)= (cd)u,eu + (v + w) = (u1, u2, 0) + [(v1, v2, 0) + (w1, w2, 0)]= (u1, u2, 0) + (v1 +w1, v2 +w2, 0)= (u1 +v1 +w1, u2 +v2 +w2, 0)= [(u1 +v1, u2 +v2, 0)] + (w1, w2, 0)= [(u1, u2, 0) + (v1, v2, 0)] + (w1, w2, 0)= (u + v) + w;(iii) a multiplicao por escalar distributiva:c(u + v) = c [(u1, u2, 0) + (v1, v2, 0)]= c(u1, u2, 0) +c(v1, v2, 0)= cu +cv,e(c +d)v = (c +d)(v1, v2, 0)= c(v1, v2, 0) +d(v1, v2, 0)= cv +dv;(iv) o vetor 0 = (0, 0, 0) neutro para soma; (v) para todo vetor (u1, u2, 0) existe um vetor (u1, u2, 0)tal que (u1, u2, 0) + (u1, u2, 0) = 0; (vi) multiplicar 1 por um vetor v no modica o vetor.Este exemplo mostra tambm que podemos visualizar R2como subespao de R3uma vez que igno-rando a terceira coordenada (que igual a zero), temos um plano. Exemplo 1.45. Sabemos que os reais so um espao vetorial (os vetores so nmeros reais, e o corposubjacente o prprio R). Os racionais no so subespao dos reais, porque a multiplicao dex Qpor escalar real no necessariamente racional: (2/3) = 2/3. Se sabemos que V um espao vetorial e U V, j sabemos tambm que todas as propriedades dasoperaes em V tambm valem em U (porque as operaes so as mesmas). Resta apenas determinar seeste subconjunto fechado para as operaes de soma de vetores e multiplicao por escalar. Para isso,vericamos que: (i) o vetor zero pertence a U; (ii) as operaes de soma e multiplicao por escalar deelementos de Uresultam em elementos tambm de U.A gura a seguir mostra, por exemplo, dois subconjuntos de um espao vetorial V. No primeiro caso,U subconjunto, mas h vetores x e y tais que x + y= z / U. Como esta condio j no satisfeita,podemos dizer que Uno subespao de V. No segundo caso, a soma de quaiquer x e y est emW, o zeroest emW, e para todo x e todo c, cx est emW, portanto W subespao de V.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.5.SUBESPAOS 25UVxyz +WVxyz +0cxcTeorema 1.46. Se V um espao vetorial e U V, de forma que 0 U e U fechado para as operaes demultiplicao por escalar e soma de vetores, ento U subespao de V.Exemplo 1.47.Considere o subconjunto de R2, X ={ (x, y) : x +y = 0 }. X subespao de R2, porque(0, 0) X; a soma de dois vetores de X resulta em outro vetor de X. Sejam (a, b) e (x, y) pontos de X.(a, b) + (x, y) = (a +x, b +y)Somando as coordenadas do novo vetor, temos(a +x) + (b +y) = (a +b) + (x +y) = 0 +0 = 0.a multiplicao de vetores de X por escalar resulta em outro vetor de X.Seja (x, y) vetor em X e c umescalar.c(x, y) = (cx, cy)Entocx +cy = c(x +y) = 0c = 0.O conjunto X denido acima a reta y = x. H outras retas que so subespaos de R2: basta que passempela origem (porque precisamos do vetor 0).Geometricamente, podemos vericar que a adio de vetores nesta reta resulta sempre em outro vetortambm sobre a mesma reta e que a multiplicao por escalar tambm mantmos vetores na reta. Comoalmdisso a reta pasa pela origem, o vetor zero est tambmna reta, e portanto, como soma e multiplicaopor escalar resultam em vetores na reta, e ela contm o zero, trata-se de um subespao de R2.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini26 CAPTULO 1.ESPAOS VETORIAIS4 2 2 4422400xyO raciocnio geomtrico que zemos obviamente vale para qualquer reta passando pela origem (e real-mente, so todas subespaos de R2).De maneira geral, o conjunto { (x1, x2, . . . , xn) :

xi= 0 } subespao de Rn. Exemplo 1.48. Considere o conjunto de pontos X={ (x, y) : x +y = 1 }. X subconjunto de R2, masno um subespao de R2, porquei) (0, 0)/ X.ii) A soma de dois vetores de X no resulta em outro vetor de X.iii) A multiplicao de um vetor de X por escalar no resulta em outro vetor de X.4 2 2 4422400xy

Exemplo 1.49. Considere o conjunto de pontos X = { (x, y) : x, y Z}, ilustrado na gura a seguir.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.5.SUBESPAOS 274 2 2 4422400xyX subconjunto de R2, mas no um subespao de R2, porque a multiplicao de um vetor de X por escalarreal no resulta em outro vetor de X. Os escalares em um espao vetorial no podem ser inteiros, porqueisto seria o mesmo que denir o espao vetorial sobre Z, que no formam um corpo. Exemplo 1.50.Considere o subconjunto de R3, X=(x, 2x, x2)T, ou seja, vetores onde a segunda coor-denada o dobro da primeira e a terceira o quadrado da primeira.X no um subespao vetorial de R3,porque (1, 2, 1)Te (2, 4, 4)Tpertencema X, mas sua soma, (3, 6, 5)Tno pertence a X(porque 32,= 5). Exemplo 1.51. Para r R, o conjunto de pontos em uma circunferncia,C={ x2+y2 r2} no subespao de R2: a multiplicao por escalar leva pontos de C a pontos fora de C: para todo r podemosencontrar um c tal que cx2+ cy2>r. Geometricamente, o conjunto C dene os vetores dentro de umacircunferncia comraio r e qualquer vetor emCdiferente de zero pode ser multiplicado por algumescalargrande o suciente para passar a ter magnitude maior que o raio. Exemplo 1.52.Podemos tambm voltar a ateno para o conjunto das funes contnuas cujo domnio R, que denotado C0.Para vericar que C0 um espao vetorial, vericamos que um conjunto de funes de R em R, eportanto valem os argumentos postos nos itens do exemplo 1.31 e de fato, este conjunto subconjuntode T(R). No entanto, como o conjunto diferente, precisamos garantir a presena do vetor (funo) zeroe o fechamento das operaes: A funo constante zero, z(x) = 0, contnua e est denida emR. A soma de duas funes contnuas denidas emR tambm contnua emR. A multiplicao de uma funo contnua por um escalar resulta em outra funo, tambm contnua.

Exemplo 1.53.Uma funo contnua pode no ser diferencivel (como |x|, por exemplo) ou pode ser de-rivvel k vezes (onde k pode ser innito). O conjunto de funes k vezes diferenciveis (ou seja, para asquais a k-sima derivada denida) denotado por Ck.Vericamos que Ck um espao vetorial: A funo constante zero, z(x) = 0, derivvel innitas vezes. A soma de duas funes coma k-sima derivada denida ser uma funo tambmk vezes derivvel.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini28 CAPTULO 1.ESPAOS VETORIAIS A multiplicao de uma funo com a k-sima derivada denida por um escalar resulta em outrafuno, tambmk vezes derivvel. Exemplo 1.54.O conjunto das funes f : R R contnuas em um dado intervalo [a, b] denotado porC[a, b]. Para qualquer intervalo [a, b] no-vazio de R, C[a, b] um espao vetorial.Para vericar que este um espao vetorial, observamos inicialmente que este no um subconjuntode T(R), porque os domnios das funes so diferentes: f : R R, f(x) =x2 diferente deg:[a, b] R, g(x) =x2. No entanto, podemos argumentar que o conjunto formado pelas funes emT(R), restritas ao intervalo [a, b] um espao vetorial, e que C[a, b] subespao desse conjunto, pelosmesmos argumentos que apresentamos para mostrar que C0 subespao de T(R). Exemplo 1.55.Vimos no exemplo 1.37 que o conjunto de solues de uma EDO linear homognea umespao vetorial. Mencionamos ali tambm que as solues deytt y = 0so as funes da formay(x) = aexbex= 0.O conjunto de funesg(x) = aex subespao das solues para esta EDO: A funo zero da forma aex, coma = 0; A soma fechada: aex+ex= (a +)ex; A multiplicao por escalar fechada: k(aex) = (ka)ex.A soluo geral especica duas constantes arbitrrias, a e b. Fixando qualquer uma delas em zero, temosum subespao. Exemplo 1.56. As funes pares, mpares, racionais e as funes denidas por polinmios so tambmsubespaos de T(R). Exemplo 1.57. Considere o sistema homogneo de equaes lineares, comn variveis e mequaes.a11x1 +a12x2 + +a1nxn= 0a21x1 +a22x2 + +a2nxn= 0...am1x1 +am2x2 + +amnxn= 0.O mesmo sistema pode ser escrito da forma Ax= 0, onde A uma matriz m n, com o coeciente aijna linha i e coluna j, x o vetor coluna (x1, . . . , xn)Te 0 o vetor coluna zero.Assim, podemos dizerque as solues para Ax = 0 so todos os vetores coluna x Rnque satisfazem o sistema homogneo deequaes denido por A. Este conjunto de vetores subespao de Rn, como vericamos a seguir.Faremos a demonstrao de duas maneiras: primeiro, com o sistema na forma de equaes, e depoisusando a forma matricial.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.5.SUBESPAOS 29i) A soluo comx1= x2== xn= 0 sempre vlida para sistemas homogneos (ou seja, o vetor0 sempre soluo). Para cada linha i, temosai1x1 +ai2x1 + +ainxn=ai1(0) +ai2(0) + +ain(0)=0.ii) Asoma de duas solues uma soluo: Sejam(x1, x2, . . . , xn) e (y1, y2, . . . , yn) duas solues parao sistema. Ento (x1 +y1, x2 +y2, . . . , xn +yn) tambm soluo: para cada linha i, vericamosqueai1(x1 +y1) +ai2(x2 +y2) + +ain(xn +yn)=ai1x1 +ai1y1 +ai2x2 +ai2y2 + +ainxn +ainyn=_ai1x1 +ai2x2 + +ainxn +ainxn_+_ai1y1 +ai2y2 + +ainyn +ainyn_=0.iii) A multiplicao de uma soluo por escalar resulta em outra soluo. O exerccio 25 pede a demons-trao deste item.i) A soluo com x = 0 sempre vlida para Ax = 0, porque A0 = 0.ii) A soma de duas solues uma soluo: Se Ax = 0 e Ay = 0, entoA(x + y) = Ax +Ay (multiplicao distributiva para matrizes)= 0 + 0= 0.iii) A multiplicao de uma soluo por escalar resulta em outra soluo. Se Ax = 0, entoA(kx) = kAx= k0= 0.Note que sistemas homogneos de equaes lineares podemser tambmdenidos comcoecientes e vari-veis emcorpos diferentes de R. Assim, As solues de umsistema deste tipo onde as variveis e coecientesso complexos formam um subespao de Cn, e de maneira geral, a solues de um sistema como este emum corpo K qualquer subespao de Kn. Exemplo 1.58.No espao Z52, os vetores da forma 0xxx0 (ou seja, o primeiro e ltimo elemento so zero)formam um subespao: O vetor zero 00000 est contido no subespao; A soma 0xxx0 0yyy0 resulta em um vetor da forma 0zzz0; A multiplicao por escalar tambm resulta em vetores da mesma forma: 0 (0xxx0) = (00000), e1 (0xxx0) = 0xxx0. VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini30 CAPTULO 1.ESPAOS VETORIAISExemplo 1.59.Considere o espao Z42. O conjunto a seguir seu subespao:C = { 0000, 0011, 1101, 1110 } . 0000 C. A soma () de elementos de C resulta em outro elemento de C:0011 1101 = 11100011 1110 = 11011101 1110 = 0011Alm disso, a soma de qualquer vetor com ele mesmo resulta em 0000, e a soma de qualquer vetorcom zero resulta no prprio vetor. A multiplicao () pelos escalares resulta em elemento de C: 0 x = 0 e 1 x = x.

Teorema 1.60. SejamU, W subespaos de um espao vetorial V. Ento U W tambm subespao de W.Demonstrao.Como ambos so subconjuntos de V, basta mostrar que UW fechado para as operaes.Sejam x, y U W e c um escalar.Como x U e x W, temos cx U e cx W, e portantocx U W,Similarmente, como x, y esto tanto em U como em W, x + y tambm devem pertencer a U e a W.Conclumos que x + y U W. Exemplo 1.61. Considere os subespaos de R3:A =_(x, y, 0)T: x, y R_B =_(x, y, 2y)T: x, y R_.Estes subespaos so planos passando pela origem. A interseo deles R=_(x, y, 0)T: x R_, quetambm subespao de R3. Exemplo 1.62. Seja Ao espao das matrizes diagonais de ordemtres, e Bo espao das matrizes quadradasde ordem tres com trao zero.A interseo A B o conjunto das matrizes diagonais de ordem tres com trao zero. Este , tambmum espao vetorial, com as mesmas operaes usuais de soma de matrizes e multiplicao por escalar. Exemplo 1.63. Seja T(R) o espao vetorial das funes reais. Considere dois subespaos de T(R):i) O conjunto das funes reais contnuas, C0;ii) O conjunto das funes reais pares P.A interseo desses dois formada pelo conjunto das funes reais contnuas pares. Esta interseo tambm subespao de T(R): A funo constante zero contnua e par;VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.5.SUBESPAOS 31 Multiplicar uma funo contnua e par por um escalar resulta em outra funo contnua e par; A soma de duas funes contnuas pares uma funo contnua par. Exemplo 1.64.Seja A o espao de todas as sequencias reais constantes, e B o espao de todas as sequen-cias de nmeros inteiros pares. A interseo dos dois conjuntos o conjunto das sequencia de constantesinteiros pares, que tambm espao vetorial. Denio 1.65 (Soma de espaos vetoriais). Se V um espao vetorial e U, W V, ento dizemos queU+W= {u +w : u U, w W} a soma de Ue W. Exemplo 1.66. Os conjuntos A, da forma (0, x, y, 0)T, B da forma (0, 0, y, z)Tso subespaos de R4. Asoma destes dois subespaos A+B = { u + v : u A, v B} .o conjunto A + B contm vetores da forma (0, x, y, 0)T+ (0, 0, y, z)T, que o mesmo que (0, x, 2y, z)T,ou (0, x, y, z)T a primeira coordenada zero, e as outras trs so livres (nenhuma depende da outra).Note que h muitos vetores em A B. Por exemplo, (0, 0, 1, 0)Test tanto em A como em B, assimcomo (0, 0, 2, 0)T na verdade, (0, 0, c, 0)T A B para todo c R. Denio 1.67 (Soma direta).Seja um espao vetorial V com subespaos U e W. Dizemos que V somadireta de Ue W se V soma de Ue W, e U W= { 0 }. Denotamos a soma direta por V= UW. Proposio 1.68. Seja V umespao vetorial comsubespaos Ue W. Ento V= UWse e somente se, para todov V, existe um nico u Ue um nico w W tal que v = u + w,Exemplo 1.69.Seja Ao subespao de R3formado pelos vetores da forma (x, y, 0)T, e seja B o subespaode R3formado por vetores da forma (0, 0, z)T.Qualquer vetor de R3pode ser descrito de forma nicacomo a soma de um vetor de Acom outro de B:(x, y, z)T= (x, y, 0)T+ (0, 0, z)T,portanto R3=A B. Outra maneira de decompor R3 em trs subespaos, X, Y e Z, contendo vetoresda forma (x, 0, 0)T, (0, y, 0)Te (0, 0, z)T, respectivamente. Um vetor de R3ento pode ser decompostounicamente em(x, y, z)T= (x, 0, 0)T+ (0, y, 0)T+ (0, 0, z)T.Podemos generalizar, denindo que para qualquer n, Rnpode ser decomposto em subespaos onde cadasubespao representa algumas das dimenses:(v1, v2, . . . , vn)T= (v1, 0, 0, . . .)T+ (0, v2, v3, 0, 0, . . .)T+. . .+ (0, 0, . . . , vn)T.De maneira geral, R3pode ser decomposto na soma direta de trs retas no colineares, ou de um plano euma reta no pertenente a este plano (todos sempre passando pela origem). VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini32 CAPTULO 1.ESPAOS VETORIAISExemplo 1.70. A soma do exemplo 1.66 no soma direta, porque um vetor (0, a, b, c) emA+B pode serdecomposto de diferentes maneiras:(0, a, b, c)T= (0, a, b, c)T+ (0, 0, 0, 0)T= (0, a, 0, c)T+ (0, 0, b, 0)T= (0, a, b2, 0)T+ (0, 0, b2, c)T... Exemplo 1.71.Os conjuntos A={ (x, y)T: x +y = 0 } e B={ (x, y)T: x y = 0 } descrevem duasretas emR2, ambas contendo a origem.4 2 2 4422400xyEntoA+B = { (x, y)T: x +y = 0 ou x y = 0 } ,mas como A B = { 0 } e A+B = R2, logo temosAB = A+B = R2.Podemos tambm observar que possvel escrever qualquer vetor de R2como soma de um vetor dentrode cada reta na gura. Exemplo 1.72. Seja Rn[x] o espao vetorial dos polinmios com grau mximo n e coecientes reais. Con-sidere os dois subconjuntos de Rn[x]: Rm1[x], o espao dos polinmios com grau mximo m1; Rm..n[x], o espao dos polinmios com grau entre me n, mais o polinmio zero, com0 < m < n.Qualquer polinmio de Rn[x] pode ser descrito unicamente como a soma de um polinmio de Rm1(x)com outro de Rm..n[x]:anxn+an1xn1+. . . +amxm+am1xm1+. . . +a1x +a0=_anxn+an1xn1+. . . +amxm_. .Rm..n[x]+_am1xm1+. . . +a1x +a0_. .Rm1[x].VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.6.APLICAES 33Note que o lado esquerdo pode ser zero (que pertence a Rm..n[x]) se todos os coecientes ali forem zero.Assim, temos Rn[x] = Rm[x] Rm..n[x].Mais concretamente: seja R4[x] o conjunto de todos os polinmios comgrau no mximo 4. Ento R4[x]pode ser decomposto, por exemplo, em R2[x], o espao dos polinmios com grau mximo 2; R3..4[x], o espao dos polinmios com grau entre 3 e 4, mais o polinmio zero.Qualquer polinmio de grau menor ou igual a quatro pode ser escrito como a soma de (i) um polinmio degrau entre 3 e 4, ou zero, e um polinmio de grau no mximo 2:a4x4+a3x3+a2x2+a1x +a0=_a4x4+a3x3_. .R3..4[x]+_a2x2+a1x +a0_. .R2[x]. Exemplo 1.73.Sejami) Ao espao gerado pelas sequencias de bits 0110 e 1001;ii) B o espao gerado pela sequencia de bits 0100;iii) C o espao gerado pela sequencia de bits 1000.O espao Z42 igual a AB C. TemosA = {0000, 0110, 1001, 1111},B = {0000, 0100},C = {0000, 1000}.Qualquer vetor (sequencia de bits) de Z42 pode ser escrita como soma de vetores desses conjuntos. 1.6 AplicaesEsta Seo detalha trs exemplos prticos do uso de estruturas algbricas: o primeiro e o terceiro em Crip-tograa; o segundo na determinao de um mtodo para resolver o cubo mgico (ou cubo de Rubik); oterceiro em Criptanlise; e o ltimo em cdigos corretores de erros. Grupos so tambm muito usados emalgumas reas da Qumica e da Fsica [Bis93; Ham89; Cor97].1.6.1 Protocolo Die-Hellman para acordo de chaves [ grupo ]A Criptograa nos oferece mtodos para realizar comunicao privada, mesmo que o canal (meio) usadoseja pblico. Por exemplo, podemos usar Criptograa para enviar mensagens secretas pela Internet, epara acessar sistemas bancrios sem que intrusos obtenham nossa senha, e poderamos citar uma grandequantidade de outras situaes onde a Criptograa nos protege, garantindo sigilo.Antes da era moderna da Criptograa, o mtodo usado para encriptar e decriptar mensagens envolviaapenas uma chave secreta: se uma mensagem encriptada com chave (senha) k, ela pode ser decriptadapor qualquer um que conhea aquela chave.Suponha que Alice e Bob queiram trocar mensagens em segredo8, mas estejam sicamente distantes8 comum em Criptograa darmos nomes aos dois usurios de um sistema criptogrco de Alice e Bob.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini34 CAPTULO 1.ESPAOS VETORIAIS(em pases diferentes, por exemplo). Suponha tambm que eles s podem se comunicar por um canalinseguro: cartas que so bisbilhotadas pelo servio secreto, telefone grampeado, ou conexo insegura porrede de computadores. Aparentemente impossvel que os dois consigam faz-lo sem se encontraremsicamente, porque teriamque denir uma chave secreta para poderemencriptar as mensagens e ambosprecisam conhecer a mesma chave.Em1976, Whiteld Die e Martin Hellman mostraramcomo resolver este problema, apresentando ummtodo para que duas pessoas possam denir conjuntamente um segredo, comunicando-se apenas porcanais pblicos9. Este mtodo foi publicado com o ttulo New directions in Cryptography [DH76]. Hojeo mtodo conhecido como protocolo Die-Hellman para acordo de chaves. A seguir descrevemos de maneirasimplicada o mtodo desenvolvido por eles.Alice e Bob devero portanto determinar, de comum acordo, um segredo (a chave criptogrca parase comunicarem, por exemplo) mas que s podem se comunicar em pblico (postando recados em umquadro de avisos, usando uma linha telefnica grampeada, ou atravs de uma rede de computadores des-protegida).O protocolo Die-Hellman usa operaes em um grupo. Para um exemplo simples10, usaremos umgrupo denido da seguinte forma: o conjunto de elementos { 1, 2, . . . , p 1 }, onde p umnmero primo.A operao de grupo para dois elementos a e b ab= resto da diviso de ab por p. Por exemplo, sep = 7, ento para calcular 56, fazemos 5 6 = 30, e tomamos o resto da diviso de 30 por 7, que 2.Observe que como p (neste exemplo,5 primo), o resultado da operao nunca ser zero, portantonunca obteremos um elemento fora doExemplo 1.74. Escolhemos, para ns didticos11, p = 5. Os elementos do grupo so { 1, 2, 3, 4 }.Calculamos como exemplo 22. Temos 2 2 = 4, e o resto de 4 5 4, portanto 22 = 4.Agora calculamos 32. Temos 3 2 = 6. O resto de 6 4 2, portanto 32 = 2. Em grupos denidos desta forma, sempre haver pelo menos um elemento g que podemos usar paraescrever todos os outros elementos usando a operao de grupo. Chamamos este elemento de gerador dogrupo. No exemplo anterior, podemos escrever todos os elementos usando somente g = 2. Por exemplo, O elemento 4 pode ser escrito como 22, porque calculamos 2 2 = 4, e o resto de 4 5 4. O elemento 3 pode ser escrito como 222:222 = (22)2 (a operao associativa)= 42 (j calculado antes, 22 = 4)= resto de 8 5= 3.O mesmo pode ser feito para o elemento 1:2222 = (22)(22) (a operao associativa)= 44 (j calculado antes, 22 = 4)= resto de 16 5= 1.9O mtodo funciona de forma que duas pessoas poderiam us-lo em uma sala com diversas outras pessoas: os dois participantesditam em voz alta nmeros um ao outro, e depois de um tempo ambos conhecem um segredo que ningum mais na sala conhece.10Em situaes prticas, h diversas restries quanto forma como o grupo denido; a apresentao do protocolo neste textofoi simplicada.11Na prtica, p deve ser muito grande.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.6.APLICAES 35Vemos portanto que podemos escrever todos os elementos usando somente 2:2 = 24 = 22 (2 2 = 4. Resto de 4 5 4)3 = 222 (Resto de 8 5 3)1 = 2222 (Resto de 16 5 1) comum usar a notao gaparaavezes .. ggg g, portanto2 = 214 = 223 = 231 = 24Em grupos como este, calcular gaa partir de g e a pode ser feito rapidamente, mas calcular a a partir dega extremamente demorado: para p perto de 22048, um computador demoraria centenas de anos paraterminar o clculo.Depois de denir p e determinar g (que podem ser pblicos), Alice e Bob seguem os passos a seguir.1.Alice escolhe aleatoriamente seu segredo, 1 < a < p.2.Bob tambm escolhe seu segredo, 1 < b < p.3.Alice envia para Bob ga.4.Bob envia para Alice gb.5.Alice, tendo o valor enviado por Bob, calcula (gb)a, que igual a gab(verique!).6.Bob faz o mesmo, e calcula (ga)b, obtendo tambmgab.Agora Alice e Bob tem o mesmo valor, gab, que pode ser usado como senha, porque conhecido apenaspor eles. Os dados enviados em pblico e que podem ser capturados pelo adversrio so gae gb, mas comestes dois valores seria difcil calcular a, b ou gab, e portanto Alice e Bob atingiram seu objetivo.O grupo que apresentamos neste exemplo no o nico usado com o protocolo Die-Hellman emaplicaes prticas grupos diferentes, com operaes mais complexas so usados. No entanto, o protocolo denido para quaisquer grupos onde haja um gerador12, facilitando sua exposio e estudo.Adiculdade de determinar adado ganeste grupo fundamental emCriptograa: dizemos que f(a) =ga uma funo de mo nica, porque fcil de calcular mas difcil de inverter13(a denio precisade difcil ca fora do escopo deste texto, mas est relacionada com o tempo necessrio para efetuar aoperao).A exposio do protocolo Die-Hellman e de diferentes usos de grupos em Criptograa padro naliteratura da rea. O livro de Douglas Stinson bastante acessvel [Sti06]; o de Katz e Lindell traz umadiscusso mais aprofundada dos fundamentos tericos [KL08].12H grupos que no so gerados por um nico elemento.13Mais precisamente, dado y = f(x), difcil encontrar algum elemento em sua pr-imagem.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini36 CAPTULO 1.ESPAOS VETORIAIS1.6.2 Cubo de Rubik [ grupo ]Grupos so usados no estudo do mtodo para soluo do cubo de Rubik, e este um exemplo importantede grupo (e de estrutura algbrica) porque os elementos do grupo so movimentos.O cubo de Rubik um quebra-cabeas tridimensional no formato de cubo que permite rotacionar cadauma de suas seis faces nos dois sentidos (horrio e anti-horrio). Desta forma, o cubo temcada face divididaem nove pequenos quadrados, e cada face tem inicialmente uma cor diferente das outras.Ao rotacionar as faces, elas cam em conguraes diferentes. Em cada congurao as faces podem apre-sentar suas parties (os pequenos quadrados) com diversas cores diferentes.O objetivo do jogador levar o cubo da congurao em que estiver para a congurao inicial, comcada face tendo uma nica cor.O grupo usado no estudo do cubo de Rubik tem como elementos o conjunto de todas as possveis mo-dicaes na congurao do cubo (ou seja, todas as sequncias de rotaes das faces) mais o movimentonulo, e a operao do grupo a concatenao (aplicao em sequncia). As rotaes so descritas usandoa seguinte notao: F a face da frente (Front); B a face de trs (Back); U a face de cima (Up); D a dace de baixo (Down); L a face da esquerda (Left); R a face da direita (Right).A gura a seguir mostra as faces F, T e R.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.6.APLICAES 37Denotamos a rotao no sentido horrio pelo nome da face: F a rotao da face frontal 90ono sentidohorrio.A rotao no sentido anti-horrio denotada pelo nome da face com a marca de um apstrofo: Ft arotao da face frontal 90ono sentido anti-horrio.Duas rotaes iguais em seguida formam uma rotao de 180o, que denotada pelo nome da face comuma indicao: F2 o mesmo que F seguida de F.Os elementos do grupo so as rotaes bsicas, j mencionadas (F,B,U,. . .,Ft,. . . ,F2,. . .) e suascomposies em sequncia, FUB, F2DU, etc. Note que FFF = F2F = Ft.O movimento nulo denotado por E (Empty).Vericamos que o conjunto e operao dados realmente um grupo: A operao de grupo (duas rotaes) resulta em outro elemento do grupo. A operao associativa. O movimento nulo o elemento neutro. Para cada rotao existe outra no sentido contrrio, e se as realizarmos em sequncia no alteramosa congurao do cubo (e isso portanto equivalente ao movimento nulo).A operao do grupo no comutativa basta observar que de maneira geral, FR leva a uma congu-rao diferente de RF.Um dos fatos bsicos sobre grupos que podemos usar ao raciocinar sobre o cubo o primeiro teoremaque provamos: todo elemento em um grupo tem um nico inverso e portanto toda sequencia de movi-mentos, da maneira como as denimos, tem uma nica sequncia inversa.O grupo descrito nesta Seo pode ser usado para derivar um mtodo para soluo do cubo de Rubik(onde soluo signica levar o cubo de qualquer congurao para a inicial) o leitor poder consultar,por exemplo os livros Notes on Rubiks Magic Cube, de David Singmaster [Sin81] e Adventures in GroupTheory: Rubiks Cube, Merlins Machine, and Other Mathematical Toys, de David Joyner [Joy08].1.6.3 Criptanlise moderna [ corpo; sistemas lineares em corpos ]Uma cifra uma ferramenta criptogrca usada para garantir sigilo emcomunicaes: uma mensagemqualquer, representada como uma sequncia de bits (e portanto um elemento de Zn2), misturada auma chave secreta (que outra sequncia de bits), de forma que um intruso no possa identicar mais amensagem (e nem possa, claro, obter a chave secreta).Quando a mensagem chegar ao destinatrio, achave secreta novamente usada para decodicar a mensagem.textoclarocifra(encriptao)textoencriptadochaveVersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini38 CAPTULO 1.ESPAOS VETORIAISA Criptanlise trata de vericar se uma ferramenta criptogrca segura: tenta-se quebrar mtodos crip-togrcos a m de realizar algo semelhante a um controle de qualidade.Omtodo da criptanlise algbrica consiste emrepresentar umcriptossistema como umsistema de equa-es. A soluo deste sistema poder ser uma chave ou mensagem secreta (e portanto resolver o sistemadeveria ser difcil).Desenvolveremos um exemplo muito simplicado de cifra e mostraremos como ele pode ser quebrado.Suponha que a entrada seja uma sequncia de quatro bits, b=b3b2b1b0, e uma chave, que umasequncia de quatro bits, k=k3k2k1k0. A sada uma sequncia de quatro bits, c=c3c2c1c0, e a cifraopera da seguinte maneira:k1 b0 b3k2= c3k2 b1 b2k3= c2k3 b2 b1k0= c1k0 b3 b0k1= c0Se conhecermos um par de texto claro e encriptado, podemos simplesmente substituir os bi e cj, obtendoum sistema linear. Suponha, por exemplo, que b = 1001 e c = 1010. Ento o sistema linear a resolver emZ2 ___k1 1 1k2= 0k2 0 0k3= 1k3 0 0k0= 0k0 1 1k1= 1Facilmente determinamos que a chave usada foik = k3k2k1k0= 0100,como fcil vericar subtituindo k e b e obtendo o texto cifrado c.O sistema descrito fcil de quebrar por vrios motivos, mas o mais evidente que ele se resume a umsistema linear. Suponha que a cifra fosse, ao invs disso, determinada pork1k2 b0 b3k0k1k2= c3k2k3 b1 b2k1k2k3= c2k3k0 b2 b1k0k1= c1k0k1 b3 b0k3k2= c0Ainda que conheamos um par de texto claro e o texto cifrado obtido dele, no to simples determinar achave: supondo que b = 1100 e c = 1010, o sistema que teramos que resolver ___k1k2 0 1k0k1k2= 1k2k3 0 1k1k2k3= 0k3k0 1 0k0k1= 1k0k1 1 0k3k2= 0que no linear, e envolve equaes de grautrs. Assim, a no-linearidade uma essencial para a seguranade uma cifra criptogrca.Algoritmos criptogrcos so projetados como sequencias de operaes em estruturas algbricas, deforma que seja fcil execut-las e que seja difcil invert-las sem a chave.Alguns exemplos de critpossistemas quebrados usando criptanlise algbrica so o AS/5, usado no pa-dro GSM de telefonia mvel, e o Keeloq, usado em dispositivos digitais em chaves de automveis.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.6.APLICAES 39O livro de Douglas Stinson [Sti06] traz uma breve introduo Criptanlise, embora no aborde a Crip-tanlise Algbrica, que tem como pr-requisito um curso bsico de lgebra Abstrata. Sobre CriptanliseAlgbrica h o livro de Gregory Bard [Bar09] e o de Andreas Klein [Kle13] (estes dois ltimos requeremconsidervel capacidade de abstrao e preparo em lgebra, Combinatria e Estatstica).1.6.4 Cdigos corretores de erros [ espao vetorial; subespao ]Quandouma mensagemeletrnica transmitida na forma de sequncia de bits, possvel que a transmissoinclua erros na mensagem alguns dos bits podem vir trocados, porque os canais de transmisso no soperfeitos.Para detectar e automaticamente corrigir estes erros as mensagens podem ser codicadas deuma forma especial, usando um cdigo corretor de erros.Ao usar um cdigo corretor de erros, enviamos mais informao do que apenas a mensagem, para queseja possvel detectar quando um erro ocorre. fcil perceber que informao adicional permite detectare corrigir erros: se enviarmos cada mensagem cinco vezes, e em uma das vezes ela for transmitida comerro, o receptor decidir que as quatro mensagens iguais devem ser aquela correta, e a quinta, diferente,deve ter sido transmitida com erro. O envio de mltiplas cpias, no entanto, no eciente: na verdade possvel corrigir erros usando menos redundncia.Em cdigos corretores de erros necessrio medir quo diferentes duas palavras so. Para isso usadaa distncia de Hamming14.Denio 1.75 (Distncia de Hamming). A distncia de Hamming entre duas sequncias de bits (ou seja, en-tre dois vetores de Zn2) a quantidade de posies emque eles diferem. Denotamos a distncia de Hammingentre a e b por d(a, b). Exemplo 1.76. Exemplicamos com a distncia entre alguns vetores.d(01011, 01000) = 2d(0101, 0101) = 0d(0001, 1010) = 3. Supomos aqui que as mensagens a serem enviadas so divididas em blocos de k bits.O emissor codica as mensagens de k bits em palavras maiores, comn > k bits. Os bits adicionais serousados para permitir a deteco e correo de erros. Por exemplo, suponha que k = 2 e n = 5. O emissorento transforma as mensagens originais de 2 bits em outras mensagens com5 bits:00 0000001 0101110 1011011 11101Este um cdigo que permite representar 4 palavras diferentes usando 5 bits, por isso chamado de [5, 4]-cdigo. Est claro que o emissor no usar todas as possveis sequncias de 5 bits.A palavra enviada do emissor ao receptor sempre uma daquelas quatro palavras de cinco bits. Amensagemcodicada temmais bits para adicionar redundncia. Ocdigo que demos de exemplo transforma14Trataremos em mais detalhes da denio de distncia no Captulo 7.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini40 CAPTULO 1.ESPAOS VETORIAISmensagens de dois bits em mensagens codicadas de cinco bits:(m1, m2)codicao(c1, c2, c3, c4, c5).Observamos que, como h somente 22palavras de dois bits, que estamos descrevendo com cinco bits, notemos como usar todas as palavras de Z52 as palavras codicadas formam um subespao de Z52: o zeroest contido no conjunto; a multiplicao () por 0 ou por 1 resulta em palavra tambm no conjunto; enalmente, a soma tambm resulta em palavra deste conjunto:01011 10110 = 1110101011 11101 = 1011010110 11101 = 01001Aps uma mensagem ser enviada, o receptor ter cinco bits. Se os bits corresponderem a uma das quatropalavras do cdigo, ele decidir que no houve erro e aceitar a mensagem. Se os bits no formarem umapalavra do cdigo (ou seja se os bits pertencerem a Z52 mas no ao subespao do cdigo), ele decidir quehouve um erro.Quando o receptor detecta um erro, ele automaticamente troca a mensagem recebida por uma do c-digo aquela que for mais prxima (usando a distncia de Hamming) da que foi recebida.Um subespao de Zn2 pode ento ser visto como um cdigo corretor de erros. O fato de cdigos destetipo seremdescritos como subespaos de Zn2 no coicidncia: para que os algoritmos usados para detectare corrigir erros funcionem como projetados, o cdigo deve necessariamente ser subespao de Zn2, e noapenas subconjunto.Discutiremos mais sobre cdigos corretores de erros na seo 4.8.4.O livro de Hefez e Villela [HV08] um texto introdutrio aos cdigos corretores de erros.ExercciosEx. 1 Mostre que ({ 0, 1 } , ) um grupo.Ex. 2 Na Seo 1.6.1 apresentamos uma estrutura e dissemos que um grupo.Verique que de fatose trata de um grupo (isso inclui, alm de demonstrar que as propriedades valem, mostrar tambm que aoperao de grupo sempre resulta em outro elemento do grupo e que nunca resultar em zero, que nopertence ao grupo). Tambm dissemos que usando aquela operao do grupo, (ga)b=gab. Mostre queisso verdade.Ex. 3 Prove que em qualquer grupo, o elemento neutro nico.Ex. 4 No exemplo 1.21 exibimos o corpo Q[2], formado pelos nmeros da forma a + b2. Pode-seobter innitos corpos como este, trocando2 por outros nmeros. Que nmeros so estes? Demonstre oque foi armado neste exerccio (que realmente se pode obter innitos corpos desta forma).Ex. 5 O produto de Hadamard de duas matrizes Ae B a matriz Ctal que cij= aijbij. Dados me n, sejaMo conjunto de matrizes mn com coecientes reais. Determine se (M, +, ) um corpo, onde oproduto de Hadamard.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.6.APLICAES 41Ex. 6 Prove que o conjunto de todas as sequncias de Fibonacci um espao vetorial (h innitas pos-sveis sequncias de Fibonacci, cada uma comeando com diferentes valores para f1 e f2).Ex. 7 Alm da operao lgicas e (denotada por ) denida no texto, em Lgica denimos a operaoou, denotada por , de forma que ab = 1 se e somente se pelo menos um dentre a e b for 1. Determinese ({ 0, 1 } , , ) um corpo.Ex. 8 Seja X=_p(x)q(x)_onde p e q so polinmios com q(x) ,=0. X o conjunto de todas as funesracionais. Determine se X um corpo com as operaes usuais de soma e multiplicao para polinmios.Ex. 9 No exemplo 1.22, denimos as operaes E lgico () e Ou-exclusivo (). Verique que estasduas operaes so na verdade o mesmo que multiplicar e tomar o resto da diviso por 2; somar e tomar oresto da diviso por 2.Ex. 10 Resolva o sistema emZ2:___1x 1y 1z = 10x 1y 0z = 11x 0y 1z = 0.Ex. 11 Mostre um sistema linear emZ2 que no tenha soluo.Ex. 12 Diga se so espaos vetoriais. Quando no especicadas, as operaes so a soma e multiplicaousuais; o corpo usado nos espaos vetoriais sempre R.i) O conjunto das funes constantes de R emR.ii) { (a, b) R2: a < b}.iii) O conjunto das matrizes diagonais.iv) O conjunto das matrizes triangulares superiores.v) O conjunto dos nmeros complexos com coecientes racionais (a +bi, a, b Q).vi)O conjunto de todas as distribuies de probabilidade sobre um conjunto nito e enumervel. A ope-rao de soma de vetores p=(p1, p2, . . . , pn) e q=(q1, q2, . . . , qn) a distribuio onde cadaevento i tem probabilidade (pi +qi)/2:p + q =_(p1 +q1)2, (p2 +q2)2, . . . , (pn +qn)2_O corpo R. O vetor p multiplicado pelo escalar c =1n

ipik = sen2_c2_cp = (kp1 + (1 k), kp2 + (1 k), . . . , kpn + (1 k)) .vii) O conjunto de todas as funes f : R R com perodo .VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini42 CAPTULO 1.ESPAOS VETORIAISviii) O conjunto de pontos com coordenadas pares emR2.ix) O conjunto dos pontos com pelo menos uma coordenada prima emR2.x) O conjunto de todas as funes reais com derivada positiva em todo o domnio.xi)Dada uma partio dos reais em intervalos, o conjunto de funes que tem derivada com o mesmosinal em cada um dos intervalos.xii) Os vetores emRnque, quando lidos, so palndromos (ou seja, todos os vetores da forma15(x1, x2, x3, . . . , x|n/2|, . . . , x3, x2, x1)).xiii) O conjunto de funes F = { f(x) = acos x +bsen x : a, b R}Ex. 13 Demonstre a proposio 1.68.Ex. 14 Dissemos no exemplo 1.37 que o conjunto de solues para qualquer EDO linear homognea umespao vetorial. Demonstre este fato.Ex. 15 Mostre que h equaes diferenciais no lineares cujas solues tambm formam um espaovetorial.Ex. 16 Mostre que para a EDO ytt +yt= 0, as funes da forma g(x) = aexbex, coma+b = 0, soum subespao do conjunto de solues.Ex. 17 Prove que em qualquer espao vetorial o elemento neutro para adio nico.Ex. 18 O conjunto de matrizes reais simtricas quadradas subespao do espao de matrizes reais qua-dradas?Ex. 19 Seja Auma matriz mn. Para quais vetores b o conjunto { x : Ax = b } subespao de Rn?Ex. 20 Prove que em um espao vetorial,i) 0v = 0.ii) 1v + v = 0.iii) c0 = 0.iv) Se u + v = u ento v = 0.v) Dado v, v nico.vi) Se cv = 0 ento c = 0 ou v = 0.Ex. 21 Prove que a quantidade de vetores em um espao vetorial sobre um corpo F nita se e somentese F nito.Ex. 22 O primeiro quadrante um subespao de R2? Ou, de maneira geral, o primeiro ortante subes-pao de Rn?Ex. 23 Encontre subespaos no-triviais do espao vetorial de n bits, denido no exemplo 1.39.15Na frmula descrevendo o vetor, n/2 o menor inteiro maior ou igual a n/2. Por exemplo, 3 = 3 e 4.2 = 5.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini1.6.APLICAES 43Ex. 24 O exemplo 1.56 lista alguns subespaos de T(R). Prove que so de fato subespaos.Ex. 25 No exemplo 1.57 no vericamos que a multiplicao de uma soluo por escalar resulta emoutrasoluo. Verique.Ex. 26 Considere os dois sistemas lineares com os mesmos coecientes (a mesma matriz A):i) Ax = 0ii) Ax = bSe v soluo para (i) e w soluo para (ii), ento v +w soluo para um dos dois sistemas. Qual deles?Explique.Ex. 27 No exemplo 1.57 vericamos que o conjunto de solues para um sistema homogneo de equa-es lineares subespao de Rn. Explique porque isso no vale para sistemas no homogneos.Ex. 28 Para qualquer conjunto X, denotamos por 2Xo conjunto de todos os subconjuntos de X.Porexemplo,A = { 1, 2, 3 }2A= {, { 1 } , { 2 } , { 3 } ,{ 1, 2 } , { 1, 3 } , { 2, 3 } ,{ 1, 2, 3 }}Agora considere as seguintes operaes que levam um elemento de Z2 (ou seja, 0 ou 1) e um conjunto emum outro conjunto:1 A = A0 A = Dado um conjunto X, determine se 2Xcom a operao um espao vetorial sobre Z2.Ex. 29 Considere o conjunto de todas as matrizes reais diagonais de ordemn, para algumn xo. Quaisso as duas operaes que poderamos usar sobre este conjunto para obter um corpo?Ex. 30 Mostre que o conjunto de todas as variveis aleatrias relacionadas a um mesmo experimento eque tenhamvarincia nita formamumespao vetorial quando usamos a operao usual de soma de variveisaleatrias e a multiplicao de uma varivel por nmero real.Ex. 31 Mostre que as funes constantes de R emR so subespao de C[a, b].Ex. 32 Mostre que um conjunto de pontos (x, y) tais que y=p(x), onde p um polinmio de graumaior ou igual a dois, no subespao de R2.Ex. 33 Mostramos neste texto que o conjunto grafos de ciclos disjuntos um espao vetorial. usando asmesmas operaes, diga se so espaos vetoriais:i) O conjunto de subgrafos de um grafo;VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini44 CAPTULO 1.ESPAOS VETORIAISii) O conjunto de subgrafos conexos de um grafo (um grafo conexo se sempre h caminho entre quais-quer dois de seus vrtices).Ex. 34 Em Mnn, a funo que d o trao (somatrio da diagonal) de uma matriz Tr: Mnn R.Mostre que o conjunto das matrizes n n com trao zero um subespao de Mnn.Ex. 35 Identique o complemento do subespao mencionado no exerccio 34.Ex. 36 Sabemos que Mnn espao vetorial.Prove que o conjunto das matrizes simtricas Snn subespao de Mnn, e que o conjunto Snn das matrizes antissimtricas complemento de Snn.Ex. 37 O conjunto T(R) de funes reais soma direta dos conjuntos de funes pares e funes mpa-res?Ex. 38 O conjunto M33 das matrizes quadradas de ordem3 pode soma direta de:i) Matrizes de ordem3 no-positivas e matrizes de ordem3 no-negativas?ii) Matrizes de ordem3 singulares e matrizes no-singulares?Ex. 39 Diga quando se trata de soma, soma direta ou nenhum deles.i) Sequncias reais; sequncias constantes; sequncias no constantes.ii) Sequncias estritamente crescentes; sequncias no estritamente crescentes.iii) Todas as solues da equao diferencial ytt y=0; as solues da forma kex; a soluo trivialmais as solues da forma jexkex, comk, j ,= 0.VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.PellegriniCaptulo 2Dimenso e BasesNeste Captulo, revemos os conceitos de combinao e dependncia linear, presumidamente j estudadosem Geometria Analtica, desta vez de forma mais abstrata, e os usamos para construir os conceitos de basede um espao vetorial e de coordenadas de vetores em diferentes bases.2.1 Dependncia linearDenio 2.1 (Combinao linear). Uma combinao linear de umconjunto nito de vetores v1, v2, . . . , vkem um espao vetorial V sobre um corpo F um vetor da formaa1v1 +a2v2 +. . . +akvkonde os ai so escalares (elementos do corpo F). Exemplo 2.2.EmR3, considere os vetores u = (0, 2, 0)Te v = (0, 0, 1)T. Ento os seguintes vetores socombinaes lineares de u e v:u +v = (0, 2, 1)u +2v = (0, 2, 2)u/2 +v = (0, 1, 1)10u = (0, 20, 0)Note que no h combinao linear de u e v com o primeiro elemento diferente de zero. Denio 2.3 (Dependncia linear). Seja S=_v1, v2, . . . , vk_um conjunto de vetores em um espaovetorial V. Se um dos vetores em S puder ser escrito como combinao linear dos outros, o conjunto S linearmente dependente, ou LD. Caso contrrio, linearmente independente, ou LI. Equivalentemente, um conjunto de vetores v1, . . . vk LI se a combinao lineara1v1 +a2v2 +. . . +akvk= 0implica ema1= a2= . . . = ak= 0.45VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini46 CAPTULO 2.DIMENSO E BASESExemplo 2.4. Temos a seguir conjuntos de vetores emR2.A =_(1, 1)T, (2, 2)T_B =_(1, 1)T, (1, 1)T_C =_(1, 1)T, (1, 2)T_D =_(1, 1)T, (1, 2)T, (1, 1)T_os conjuntos A, B e Dso LD, porque2(1, 1)T= (2, 2)T1(1, 1)T= (1, 1)T32(1, 1) +12(1, 1) = (1, 2)TO conjunto C LI. Se tentarmos obter valores a e b tais que a(1, 1)T= b(1, 2)T, teremosa = b,a = 2b,o que s possvel coma = b = 0.A Figura a seguir ilustra geometricamente estes conjuntos de vetores.(1, 1)(2, 2)A, conjunto LD(1, 1)(1, 1)B, conjunto LDVersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini2.1.DEPENDNCIA LINEAR 47(1, 1)(1, 2)C, conjunto LI(1, 1)(1, 2)(1, 1)D, conjunto LDO conjunto Ctem exatamente dois vetores no colineares. Os outros tem vetores colienares (A, B) ou temmais de dois vetores (D). Exemplo 2.5. EmR3, os vetoresu = (1/2, 1, 1/2)T,v = (1/2, 2, 1)T,w = (1/4, 2, 0)Tso LD, porque u = v + (1/2)w. Exemplo 2.6. No espao de polinmios R2[x], os vetores (polinmios) x2+2, x 1 e 3x2+2x +4 so umconjunto L.D., porque o ltimo combinao linear dos outros dois: 3x2+2x+4 = 3(x2+2)+2(x1). Exemplo 2.7. No espao das funes de RemR, os vetores (ou seja, as funes) f(x) = 3x, g(x) = cos(x)e h(x)= ln(x) so L.I., porque nenhuma delas pode ser escrita como combinao linear das outras: noexistema, b e c diferentes de zero tais quea(3x) +bcos(x) +c ln(x) = 0 (2.1)para todo x. Para mostrar este fato, supomos que existambe c tais que a equao 2.1 valha. Ento, teramosa =c ln(x) bcos(x)3x, (2.2)para todo x, comb e c constantes. Mas o valor de a, que presumimos ser constante, dependeria do valor dex, porque o lado direito da equao 2.2 no constante: como contraexemplo basta tomar x=e, x=1,x = e x = 2, por exemplo, e temosa =c ln(1) bcos(1)3 0.1801c,a =c ln() bcos()3 0.1061b 0.1214c,a =c ln(2) bcos(2)6 0.0530b 0.0975c,VersoPreliminarlgebraLinear-notasdeaulaverso121JernimoC.Pellegrini48 CAPTULO 2.DIMENSO E BASESa =c ln(e) bcos(e)3e 0.1118b 0.1226c.Este sistema linear s tem a soluo trivial coma=b=c =0, que portanto a nica maneira desatisfazer a equao 2.1. Exemplo 2.8. As matrizes A, B e C a seguir formam um conjunto L.I.A =_1 10 0_B =_7 00 7_C =_1 11 1_No entanto, A, B, Cacima junto coma matriz Dabaixo formamumconjunto L.D., porque D = (1/7)B+C, ou seja,D =_0 11 0_. Exemplo 2.9.No espao das funes contnuas complexas, eix, eix, seno e cosseno so LD, porque asduas ltimas podem ser escritas como combinaes lineares das duas primeiras:cos =12ei+12ei,sin = 12iei+12iei.Note que especicamos o espao das funes contnuas complexas, porque as funes eixe eixso com-plexas Exemplo 2.10.No espao Z52, os vetores 01101 e 11100 so linearmente independentes, porque nenhum mltiplo de outro. Mas se tomarmos tambm o vetor 10001, obteremos o conjunto{01101, 11100, 10001} ,que linearmente dependente, porque1(01101) 1(11100) = 01101 11100 = 10001. Teorema 2.11. Qualquer conjunto que contenha o vetor zero, 0, linearmente dependente.Demonstrao.Seja A = {0, v1, v2, . . .}. Ento0 = 1(0) +0(v1) +0(v2), . . . ,e como h uma combinao linear dos vetores comumcoeciente no-nulo resultando emzero, o conjunto linearmente dependente. 2.2 Conjuntos geradores e basesUm espao vetorial, mesmo tendo innitos elementos, pode ser descrito por uma quantidade nita deles.Na leitura da denio a seguir deve-se ter em mente que uma combinao linear sempre de umaquantidade nita de vetores, mesmo que estes sejam escolhidos de um conjunto innito (ou seja, no con-sideramos somas innitas da forma a1v1 +a2v2 + ).VersoPrel