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