IME / ITA(IME) Recorrência Tópico resolvido

Aqui deverão ser postadas questões desses vestibulares e de outras instituições militares (EN, CN, EsPCEx etc.).

Moderador: [ Moderadores TTB ]

Autor do Tópico
Deleted User 23699
6 - Doutor
Última visita: 31-12-69
Mai 2021 17 22:36

(IME) Recorrência

Mensagem não lida por Deleted User 23699 »

Seja D o determinante da matriz A = [aij] de ordem n, tal que [tex3]a_{ij}=|i-j|[/tex3] . Mostre que [tex3]D=(-1)^{n-1}(n-1)2^{n-2}[/tex3]




Avatar do usuário
LostWalker
4 - Sabe Tudo
Mensagens: 677
Registrado em: Seg 04 Mar, 2019 16:34
Última visita: 07-03-24
Ago 2022 31 02:37

Re: (IME) Recorrência

Mensagem não lida por LostWalker »

FINALMENTE
Eu não faço ideia de quanto tempo e folha gastei nesse exercício, aí hoje eu tenho uma ideia simples e do nada o exercício inteiro sai. Faz eu ficar com raiva, feliz, me sentir um gênio, me sentir burro. Tipo, no final, a ideia era bem simples para começar, mas eu fui por todos os caminhos difíceis. Bem, imagino que, depois de resolver, tudo soará bem simples, assim como eu vejo a questão agora.




Reconhecendo a Estrutura
Os termos obedecem a [tex3]a_{ij}=|i-j|[/tex3] , então o menor valor será [tex3]0[/tex3] , todos inteiros e sem números negativos. Pela estrutura, os elementos na diagonal principal serão sempre nulos. No mais, cada variação de linha ou coluna afastando-se da diagonal principal aumenta o valor em um. De maneira expositiva, teremos:

[tex3]n=1~~\Longrightarrow~~\begin{bmatrix}0\end{bmatrix}[/tex3]

[tex3]n=2~~\Longrightarrow~~\begin{bmatrix}0&1\\1&0\end{bmatrix}[/tex3]

[tex3]n=3~~\Longrightarrow~~\begin{bmatrix}0&1&2\\1&0&1\\2&1&0\end{bmatrix}[/tex3]

[tex3]n=4~~\Longrightarrow~~\begin{bmatrix}0&1&2&3\\1&0&1&2\\2&1&0&1\\3&2&1&0\end{bmatrix}[/tex3]

[tex3]n=5~~\Longrightarrow~~\begin{bmatrix}0&1&2&3&4\\1&0&1&2&3\\2&1&0&1&2\\3&2&1&0&1\\4&3&2&1&0\end{bmatrix}[/tex3]


Nas minhas tentativas, eu fazia geralmente até a 5ª ordem, então quis manter :)




A Recorrência nos Termos
O padrão de recorrência apenas surge a partir da ordem 3, não irei explicar o motivo agora, mas iremos partir dele.

A primeira coisa que deveria ser a mais notável e meu Deus, como eu consegui ignorar isso por tanto tempo?, Olhando de linha por linha ou coluna por coluna (no caso, todas as minhas demonstrações irão observar linha por linha) variam em [tex3]1[/tex3] , Veja a de ordem 3:

[tex3]n=3~~\Longrightarrow~~\begin{bmatrix}\color{PineGreen}0&\color{PineGreen}1&\color{PineGreen}2\\\color{Purple}1&\color{Purple}0&\color{Purple}1\\\color{NavyBlue}2&\color{NavyBlue}1&\color{NavyBlue}0\end{bmatrix}[/tex3]


Ora, isso também significa que a diferença dessas colunas é [tex3]1[/tex3] , Veja que subtraindo a penúltima linha da anterior temos:

[tex3]\begin{bmatrix}0&1&2\\1&0&1\\2&1&0\end{bmatrix}~~\Longrightarrow~~\begin{bmatrix}0&1&2\\1&0&1\\1&1&-1\end{bmatrix}[/tex3]


Veja que podemos continuar essa ideia, agora subtraindo a antepenúltima da penúltima:

[tex3]\begin{bmatrix}0&1&2\\1&0&1\\2&1&0\end{bmatrix}~~\Longrightarrow~~\begin{bmatrix}0&1&2\\1&0&1\\1&1&-1\end{bmatrix}~~\Longrightarrow~~\begin{bmatrix}0&1&2\\1&-1&-1\\1&1&-1\end{bmatrix}[/tex3]


Repita o processo sempre que possível até chegar na primeira linha. Note que após passar do zero, o resultado é [tex3]-1[/tex3] . De maneira geral, perceba que, ainda por causa da presença do [tex3]0[/tex3] como primeiro termo da matriz, todos os elementos da primeira coluna são [tex3]1's[/tex3] , enquanto a presença do [tex3]0[/tex3] como último termo termo da matriz, todos os elementos da última coluna são [tex3]-1's[/tex3] :

[tex3]\begin{bmatrix}0&1&2\\1&0&1\\2&1&0\end{bmatrix}~~\Longrightarrow~~\begin{bmatrix}0&1&2\\\color{Green}1&-1&\color{Red}-1\\\color{Green}1&1&\color{Red}-1\end{bmatrix}[/tex3]


Como, pelas regras de formação, o primeiro termo da primeira coluna é sempre [tex3]0[/tex3] e o primeiro termo da última coluna é sempre corresponde a ordem, podemos, sem nos preocuparmos, somar a primeira coluna na última, nos dando:

[tex3]\begin{bmatrix}0&1&2\\1&0&1\\2&1&0\end{bmatrix}~~\Longrightarrow~~\begin{bmatrix}0&1&2\\1&-1&-1\\1&1&-1\end{bmatrix}~~\Longrightarrow~~\begin{bmatrix}0&1&2\\1&-1&0\\1&1&0\end{bmatrix}[/tex3]





Aplicando Laplace
Veja que esses dois zeros são muito úteis para uma coisa: Laclace na primeira linha. Veja que:

[tex3]\begin{bmatrix}0&1&2\\1&0&1\\2&1&0\end{bmatrix}~~\Longrightarrow~~\begin{bmatrix}0&1&2\\1&-1&-1\\1&1&-1\end{bmatrix}~~\Longrightarrow~~\begin{bmatrix}\color{Red}0&\color{Red}1&\color{Red}2\\1&-1&0\\1&1&0\end{bmatrix}[/tex3]


Esses zeros são úteis porque, para todos os cofatores dos termos da primeira linhas, eles formarão uma coluna de termos nulos, e segundo as propriedades das matrizes, quando uma linha ou colunas apenas possui temos nulos, veja que apenas o último termo da linha gera um cofator sem os zeros:

[tex3]\begin{bmatrix}\color{Red}0&1&2\\1&\color{Green}-1&\color{Green}0\\1&\color{Green}1&\color{Green}0\end{bmatrix}~~\therefore~~\begin{bmatrix}0&\color{Red}1&2\\\color{Green}1&-1&\color{Green}0\\\color{Green}1&1&\color{Green}0\end{bmatrix}~~\therefore~~\begin{bmatrix}0&1&\color{Red}2\\\color{Green}1&\color{Green}-1&0\\\color{Green}1&\color{Green}1&0\end{bmatrix}[/tex3]

Ou seja, aplicar Laplace só nos leva a calcular o valor do determinante de um cofator.




O Determinante do Cofator
Vamos olhar o cofator, o que temos é:

[tex3]\begin{bmatrix}1&-1\\1&1\end{bmatrix}[/tex3]


O padrão que irá se estabelecer é a diagonal principal sempre será formada por [tex3]1's[/tex3] . Abaixo dela será [tex3]1's[/tex3] e acima [tex3]-1's[/tex3] , além de a última linha sempre ser formada por [tex3]1's[/tex3] . Para nos ajudar, basta somar a última linha em todas as outras, o resultado será sempre o mesmo:

[tex3]\begin{bmatrix}1&-1\\1&1\end{bmatrix}~~\Longrightarrow~~\begin{bmatrix}2&0\\1&1\end{bmatrix}[/tex3]


Uma matriz angular em que todos os termos da diagonal principal serão [tex3]2[/tex3] , exceto o último (por não poder somar a si mesmo). Logo, se começamos com ordem 3, o cofator será de ordem 2, possuirá apenas determinante [tex3]2^1[/tex3] .




Outros exemplos
Em passos rápidos, irei ilustrar o mesmo processo com a ordem 4 e 5. Veja:

[tex3]n=4~~\Longrightarrow~~\begin{bmatrix}0&1&2&3\\1&0&1&2\\2&1&0&1\\3&2&1&0\end{bmatrix}~~\Longrightarrow~~\begin{bmatrix}0&1&2&3\\1&-1&-1&-1\\1&1&-1&-1\\1&1&1&-1\end{bmatrix}~~\Longrightarrow~~\begin{bmatrix}0&1&2&3\\1&-1&-1&0\\1&1&-1&0\\1&1&1&0\end{bmatrix}[/tex3]

[tex3]\mbox{Cofator }A_{14}~~\Longrightarrow~~\begin{bmatrix}1&-1&-1\\1&1&-1\\1&1&1\end{bmatrix}~~\Longrightarrow~~\begin{bmatrix}2&0&0\\2&2&0\\1&1&1\end{bmatrix}~~\Longrightarrow~~\det(A_{14})=2^2[/tex3]


[tex3]n=5~~\Longrightarrow~~\begin{bmatrix}0&1&2&3&4\\1&0&1&2&3\\2&1&0&1&2\\3&2&1&0&1\\4&3&2&1&0\end{bmatrix}~~\Longrightarrow~~\begin{bmatrix}0&1&2&3&4\\1&-1&-1&-1&-1\\1&1&-1&-1&-1\\1&1&1&-1&-1\\1&1&1&1&-1\end{bmatrix}~~\Longrightarrow~~\begin{bmatrix}0&1&2&3&4\\1&-1&-1&-1&0\\1&1&-1&-1&0\\1&1&1&-1&0\\1&1&1&1&0\end{bmatrix}[/tex3]

[tex3]\mbox{Cofator }A_{15}~~\Longrightarrow~~\begin{bmatrix}1&-1&-1&-1\\1&1&-1&-1\\1&1&1&-1\\1&1&1&1\end{bmatrix}~~\Longrightarrow~~\begin{bmatrix}2&0&0&0\\2&2&0&0\\2&2&2&0\\1&1&1&1\end{bmatrix}~~\Longrightarrow~~\det(A_{15})=2^3[/tex3]




Montando a Expressão Geral
Primeiro, o sinal do termo de Laplace, lembrando que é unicamente do último termo da primeira linha, então:

[tex3](-1)^{n+1}\cdot a_{1n}\cdot A_{1n}[/tex3]


Numericamente, podemos usar o menos no expoente sem problemas:

[tex3](-1)^{n-1}\cdot a_{1n}\cdot A_{1n}[/tex3]


De outro modo, sendo a lei de formação dos elementos, [tex3]a_{1n}=(n-1)[/tex3] , logo:

[tex3](-1)^{n-1}\cdot(n-1)\cdot A_{1n}[/tex3]


Por fim, como dito antes, o determinante do cofator será [tex3]2^{n-2}[/tex3] , tanto pela redução de ordem do cofator, quanto pelo último termo da diagonal principal do cofator não ser [tex3]2[/tex3] , o que nos concluí:

[tex3]\color{MidNightBlue}\boxed{D=(-1)^{n-1}\cdot(n-1)\cdot 2^{n-2}~~~~\mbox{C.Q.D.}}[/tex3]




Explicando a Primeira e Segunda Ordem
De maneira interessante, os dois entram na fórmula, mas eles não cumprem o processo até o fim.

No caso da primeira ordem, o Laplace seria no termo [tex3]0[/tex3] , logo, o determinante é diretamente [tex3]0[/tex3] .

Já sobre a segunda ordem, não há oportunidade (nem necessidade) de formar as matrizes triangulares, então o [tex3]2[/tex3] nem chega a parecer como termo.



"[...] Mas essa é a graça dos encontros e desencontros: a Coincidência e o Destino. Se pudesse resumir, diria: A causalidade é a Ironia do Universo."
-Melly

Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg
  • Nova mensagem Recorrência
    por magben » » em Ensino Superior
    1 Respostas
    502 Exibições
    Última msg por magben
  • Nova mensagem Relação de recorrência
    por lilith7 » » em Ensino Superior
    0 Respostas
    724 Exibições
    Última msg por lilith7
  • Nova mensagem (FB) Recorrência
    por Deleted User 23699 » » em Ensino Médio
    0 Respostas
    380 Exibições
    Última msg por Deleted User 23699
  • Nova mensagem (Banco IMO) Recorrência
    por Deleted User 23699 » » em Olimpíadas
    1 Respostas
    756 Exibições
    Última msg por FelipeMartin
  • Nova mensagem (Hungria) Recorrência
    por Deleted User 23699 » » em Olimpíadas
    0 Respostas
    613 Exibições
    Última msg por Deleted User 23699

Voltar para “IME / ITA”