Lucas,
"Rank" quer dizer o posto da matriz mxn. Basicamente, se voce tem uma
transformacao linear T de um espaco em T:R^m -> R^{n} , o posto vai te dizer
qual e a dimensao da imagem dessa transformacao. Como cada coluna da matriz
associada a T e a imagem de um dos vetores da base canonica em R^{m}, entao, o
numero de colunas linearmente independentes vai lhe fornecer informacao sobre a
dimensao da imagem. O livro do Elon tem uma excelente explicacao sobre o
assunto e inclusive prova o que voce esta querendo.
Leandro.
From: [email protected]
Date: Tue, 30 Mar 2010 10:51:16 -0300
Subject: [obm-l] Teorema sobre "rank" de matrizes
To: [email protected]
Olá,
eu estava resolvendo os exercícios do livro "Introdução a algoritmos" de Cormen
et al. E encontrei o que eu acredito ser um erro.
No livro, a definição dita alternativa para o "rank" (não sei traduzir) de uma
matriz 'A' mxn é o maior valor 'r' tal que existam duas matrizes (uma mxr e
outra rxn) tais que seu produto seja igual à 'A'. (A definição principal é a de
que uma matriz tem rank 'r' se existirem no máximo 'r' linhas/colunas
linearmente independentes).
O livro também fala que para uma matriz 'A' mxn, rank(A) <= min(m, n).
Então, na questão 31.1-9, é pedido pra provar que rank(AB) <= min( rank(A),
rank(B) ).
No entanto, eu consegui provar que min( rank(A), rank(B) ) <= rank(AB)
Este é meu argumento:
Seja 'A' uma matriz mxk
e seja 'B' uma matriz kxn
Então rank(AB) >= k, já que é possível multiplicar duas matrizes mxk e kxn pra
encontrar AB, mas não se sabe se é possível encontrar duas matrizes de maiores
dimensões para se obter AB. (Ver definição acima)
Sabemos que rank(A) <= min(m, k) e que rank(B) <= min(k, n)
E sabemos que k >= min(m, k) e que k >= min(k, n)
Para a matriz A, temos:
rank(A) <= min(m, k) <= k <= rank(AB)
Portanto, rank(A) <= rank(AB). De forma análoga, rank(B) <= rank(AB) e,
portanto,
rank(AB) >= max( rank(A), rank(B) ) >= min( rank(A), rank(B) )
Eu cometi algum engano? Se eu realmente cometi e alguém pudesse responder este
exercício pra mim, eu ficaria grato ;)
