Acredito que a dúvida já tenha sido sanada. Para fins de completude, segue o texto da segunda edição (o Lucas, provavelmente, deve ter a primeira) do Cormen americano que fala sobre a definição alternativa.
"(...) An alternate, but equivalent and often more useful, definition is that the rank of a nonzero mxn matriz A is the *smallest* number r such that there exist matrices B and C of respective sizes mxr and rxn such that A = BC." (grifo meu) []'s Cesar 2010/3/30 Bernardo Freitas Paulo da Costa <[email protected]>: > 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 > ========================================================================= > ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
