Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Qual o maior número de 1s que uma matriz, formada apenas por 1s e 0s, quadrada e não singular pode ter?

+1 voto
44 visitas
perguntada Mar 13, 2015 em Matemática por danielcajueiro (5,171 pontos)  
editado Mar 15, 2015 por danielcajueiro

Escreva uma equação que dê o número de 1s em função da ordem \(n\) da matriz.

Compartilhe

1 Resposta

0 votos
respondida Mar 14, 2015 por danielcajueiro (5,171 pontos)  
editado Mar 15, 2015 por danielcajueiro

Vamos tentar entender como funciona a lógica dessa questão.

Considere \(n=1\). Nesse caso, a matriz tem apenas 1 elemento que é 1.

Considere \(n=2\). Nesse caso, a matriz triangular é o maior número de 1s possíveis, pois se adicionarmos mais um 1, teremos duas linhas inteiras iguais a 1 que torna a matriz não singular.

Para o caso \(n=3\), Comece com a matriz triangular. Obviamente, essa matriz é não-singular:

\[\left(\begin{array}{ccc} 1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{array}\right).\]

Mas será que ela é aquela com o maior número de 1s?

Não. Note que podemos introduzir um 1 na linha 3 e coluna 1 que os vetores formados pelas linhas continuam independentes e consequentemente a matriz ainda é não singular.

Agora já conseguimos ver o cenário. O número total de 1s é \(n^2\), mas precisamos remover \((n-1)\) 1s, pois em caso contrário teremos duas linhas formadas por 1 e a matriz será singular. Logo, o número máximo total de 1s é \(n^2 - (n-1)=n^2 - n +1\).

...