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: luca...@dcc.ufba.br
Date: Tue, 30 Mar 2010 10:51:16 -0300
Subject: [obm-l] Teorema sobre "rank" de matrizes
To: obm-l@mat.puc-rio.br

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 ;)
                                          

Responder a