Oi Lucas, Bom, claramente há um erro. Mas eu acho que é na definição. (e como você usou uma definição errada, nada mais natural do que chegar numa situação estranha)
Veja bem: seja A uma matriz m x n. Considere a seguinte matriz m x (n + r) : (A | 0), ou seja, a matriz A seguida de um monte de zeros. Chame-a de X. Em seguida, considere a matriz Y que é (n+r) x n, cujas primeiras n linhas dão a matriz identidade, e no resto, você bota o que você quiser. Por exemplo, zeros :) Ou seja, Id --- = Y 0 Bom, agora multiplique X por Y, vai dar A, é claro. Mas peraí, isso faz matrizes de tamanho cada vez maior, e o rank (posto, em português) não existiria... Deduz-se que, na verdade, deve ser o MENOR valor de r tal que existam X (m x r) e Y (r x n) tal que XY = A. Como exercício (importantíssimo quando se lê um livro), verifique que as duas definições que você tem para o posto da matriz dão o mesmo resultado! (Vai ajudar você ter provado a tal da questão sobre o posto do produto e o mínimo dos postos) abraços, -- Bernardo Freitas Paulo da Costa 2010/3/30 Lucas Prado Melo <[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 ;) > ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
