Vetores e Matrizes

Parte 1: Vetores - Posições e Transformações

Imagine que você está desenvolvendo um jogo 2D e precisa controlar a posição de um personagem no mapa.

• "Onde está o personagem?" → Você precisa de coordenadas, como (15, 8).
• "Para qual direção ele se moverá?" → Você precisa de uma direção e distância, como "mover 5 unidades para a direita e 3 unidades para cima".

Ambas as informações podem ser representadas por uma mesma estrutura matemática: o vetor.

Em programação, um vetor é basicamente um array unidimensional.

• posicao_atual = [15, 8] pode representar a localização do personagem.
• deslocamento = [5, 3] pode representar o próximo movimento do personagem.

Resumo para programadores competitivos:

1. Vetor como posição (Position): Descreve a localização de algo no espaço. Pode ser 2D [x, y], 3D [x, y, z], ou até dimensões superiores (por exemplo, um personagem com atributos: [vida, ataque, defesa, velocidade], que é um vetor 4D!).
2. Vetor como deslocamento (Displacement): Descreve uma operação de movimento, como "aumentar x em 5, aumentar y em 3".

Portanto, um vetor é simplesmente uma sequência ordenada de números que representa uma posição ou uma operação.

Parte 2: Matrizes - Operadores de Transformação

Se um vetor representa um "estado", uma matriz representa uma "regra de transição de estado". Ela funciona como um "transformador" ou "função". Quando você aplica uma matriz a um estado (vetor), ela resulta em um novo estado (outro vetor).

Em programação, uma matriz é um array bidimensional.

Por exemplo, uma matriz 2x2 pode ser escrita como:

M = [[a, b],
     [c, d]]

Qual a utilidade disto? O papel principal de uma matriz é "transformar" vetores.

Pense em uma máquina onde você insere um vetor v_antigo = [x, y] do lado esquerdo, e após processamento, a máquina (matriz M) produz um novo vetor v_novo = [x', y'] do lado direito.

Esse processo é chamado de multiplicação de matriz por vetor.

Alguns exemplos práticos:

• Transformador de rotação: Uma matriz específica pode receber o vetor de coordenadas [x, y] de um personagem e retornar as coordenadas após uma rotação de 90 graus.
• Transformador de escala: Outra matriz pode ampliar todas as coordenadas em um fator de 2.
• Transformador de espelhamento: Uma matriz pode criar uma imagem espelhada do personagem em relação ao eixo y.

Resumo sobre matrizes:

1. Uma tabela bidimensional de números.
2. Sua principal característica é ser uma operação, um transformador, não apenas dados.
3. Seu funcionamento é: matriz × vetor = novo vetor.

Parte 3: Multiplicação de Matrizes - Composição de Transformações

Aqui está o conceito mais importante.

Se a matriz M1 representa "rotacionar 90 graus" e a matriz M2 representa "escalar por 2", como aplicar ambas as transformações a um personagem?

• Método direto: Primeiro multiplicar o vetor do personagem por M1 para obter um vetor intermediário. Depois multiplicar esse vetor intermediário por M2 para obter o resultado final. resultado_final = M2 * (M1 * vetor_personagem)
• Método eficiente: Criar uma "matriz composta" M_composta que representa ambas as transformações aplicadas sequencialmente.

É possível! Essa matriz composta é o produto de M1 e M2: M_composta = M2 * M1 (atenção à ordem! a transformação aplicada primeiro vem à direita)

Esta é a essência da multiplicação de matrizes: ela representa a composição/combinação de transformações. Quando duas matrizes são multiplicadas, o resultado é uma nova matriz que equivale à aplicação das duas transformações originais em sequência.

Parte 4: Aplicação em Programação Competitiva - Exponenciação de Matrizes

Vamos ao ponto: como isso é útil em programação competitiva?

Considere um problema de recorrência, como a sequência de Fibonacci: f(n) = f(n-1) + f(n-2)

Qual é nosso estado em cada passo? É o vetor [f(n), f(n-1)]. Queremos transformar o estado antigo [f(n-1), f(n-2)] no novo estado [f(n), f(n-1)].

Existe um "transformador" (matriz) que faça essa conversão? [novo_estado] = matriz × [estado_antigo]

Ou seja: [ f(n) ] = [ ? ? ] * [ f(n-1) ]``[f(n-1)] [ ? ? ] [ f(n-2) ]

Com base na relação de recorrência f(n) = 1*f(n-1) + 1*f(n-2) e f(n-1) = 1*f(n-1) + 0*f(n-2), podemos construir a matriz:

[ f(n) ] = [ 1 1 ] * [ f(n-1) ]``[f(n-1)] [ 1 0 ] [ f(n-2) ]

Chamamos a matriz [[1, 1], [1, 0]] de T (matriz de transição).

Veja que cada passo de recorrência equivale a multiplicar pela matriz T uma vez.

Para calcular f(n), partindo do estado inicial [f(1), f(0)] = [1, 0], precisamos multiplicar por T repetidamente n-1 vezes. [f(n), f(n-1)] = T * T * ... * T (n-1 vezes) * [f(1), f(0)]

Ou seja: [f(n), f(n-1)] = T^(n-1) * [f(1), f(0)]

Se n for muito grande, como 10^18, realizar n-1 multiplicações seria inviável. Mas, você conhece o algoritmo de exponenciação rápida, que calcula a^n em tempo O(log n).

A multiplicação de matrizes também é associativa (A*B)*C = A*(B*C), então podemos usar exponenciação rápida com matrizes!

Podemos calcular T^(n-1) em O(k^3 * log n) (onde k é a dimensão da matriz, no caso 2). Depois, multipilcamos essa "matriz transformadora final" pelo vetor de estado inicial para obter f(n) diretamente!

Resumo final para programadores competitivos:

1. Vetor: Um array unidimensional que representa um estado (como [f(n), f(n-1)]).
2. Matriz: Um array bidimensional que representa uma transição de estado (a regra que transforma o estado de n-1 para n).
3. Multiplicação de matrizes: Combina múltiplas transições de estado em uma única transição equivalente.
4. Exponenciação rápida de matrizes: Quando precisamos aplicar muitas (como 10^18) mesmas transições de estado, usamos exponenciação rápida para combinar todas essas transições em uma "transição final", que é aplicada de uma vez ao estado inicial, alcançando uma complexidade O(log n).

Todos os problemas de programação dinâmica ou recorrência que podem ser otimizados com exponenciação de matrizes trabalham com esse princípio. Espero que esta explicação seja útil!

Operações Elementares em Matrizes

Vamos continuar explorando matrizes de forma intuitiva.

Na seção anterior, tratamos matrizes como "transformadores" que alteram estados (vetores) através da multiplicação. Agora, vamos abordar uma perspectiva diferente: ver matrizes como "tabuleiros de quebra-cabeça" cheios de equações, e nosso objetivo é resolvê-los.

Parte 1: O Problema Central - Resolvendo Sistemas de Equações

Todos nós já resolvemos sistemas de equações lineares no ensino fundamental, como:

2x + 3y = 7
x  -  y = 2

Usando métodos de eliminação ou substitiução, conseguimos encontrar os valores de x e y.

E se tivéssemos 10 equações com 10 incógnitas? O cálculo manual seria impraticável. Em computação, usamos matrizes para representar e resolver esse problema.

O sistema acima pode ser representado na forma matricial: A * x = b

• A (matriz de coeficientes): A "tabela" com todos os coeficientes das variáveis.``` A = [[2, 3], [1,-1]]

- **x (vetor de incógnitas):** As variáveis que queremos encontrar.```
x = [[x],
     [y]]

• b (vetor de termos independentes): Os resultados do lado direito das equações.``` b = [[7], [2]]

Portanto, **resolver um sistema de equações lineares**, na visão computacional, é o processo de encontrar o vetor `x` quando conhecemos a matriz `A` e o vetor `b`.

Como fazer isso? Precisamos realizar algumas operações no "tabuleiro" (matriz A) para simplificá-lo até que a solução fique evidente. Essas operações são as **transformações elementares de linha**.

### Parte 2: As Ferramentas Mágicas - Transformações Elementares de Linha

Ao resolver sistemas de equações, você realiza três tipos de operações:

1. **Trocar a posição de duas equações.** (Claramente não altera a solução)
2. **Multiplicar ambos os lados de uma equação por um número não nulo.** (Ex: `x - y = 2` se torna `2x - 2y = 4`)
3. **Somar a múltiplo de uma equação a outra equação.** (Este é o coração do método de eliminação)

No contexto matricial, essas operações correspondem às **transformações elementares de linha**, nossas ferramentas versáteis para resolver qualquer sistema.

1. **Trocar duas linhas (Swap):** `trocar(linha_i, linha_j)`
2. **Multiplicar uma linha por uma constante não nula (Scale):** `multiplicar(linha_i, k)`
3. **Somar múltiplo de uma linha a outra (Add):** `adicionar(linha_i, linha_j, k)`

**Ideia central:** Ao realizar essas operações na matriz A, se aplicarmos as mesmas operações ao vetor b, a solução do sistema permanece inalterada!

### Parte 3: O Algoritmo - Eliminação de Gauss (Gaussian Elimination)

A eliminação de Gauss é um algoritmo padronizado que utiliza as ferramentas acima para resolver sistemas de equações. Seu objetivo é claro: transformar a matriz de coeficientes A em uma **"matriz triangular superior"** (ou "matriz escada").

O que é uma matriz triangular superior? É uma matriz onde todos os elementos abaixo da diagonal principal são zero:

[[a, b, c], [0, d, e], [0, 0, f]]

Por que isso facilita a solução? Observe a última linha, que corresponde à equação `f * z = ...`, permitindo calcular `z` diretamente. Com `z` conhecido, substituímos na penúltima linha `d * y + e * z = ...` para encontrar `y`. Finalmente, com `y` e `z`, substituímos na primeira linha para encontrar `x`. Esse processo é chamado de **retrosubstituição**.

**Passos da eliminação de Gauss (como uma receita):**

Para facilitar, geralmente combinamos a matriz A e o vetor b em uma **matriz aumentada `[A | b]`** e realizamos operações nela.

**Objetivo:** Transformar a parte A da matriz aumentada em triangular superior.

**Fluxo do algoritmo:** (supondo uma matriz n x n)

1. **Enumere as colunas dos pivôs:** Comece com a coluna `c = 0` e vá até `n-1`.
2. **Encontre o "pivô" na coluna atual:** Na coluna `c`, a partir da linha `r` (inicialmente 0), procure o elemento de maior valor absoluto. Troque a linha contendo esse elemento com a linha `r`.
- **Por que procurar o maior?** Para minimizar erros de precisão em cálculos com números de ponto flutuante. Essa técnica é chamada "eliminação de Gauss com pivoteamento parcial".
- Se todos os elementos da coluna `c` a partir da linha `r` forem zero, o sistema pode ter infinitas soluções ou não ter solução. Nesse caso, pule para a próxima coluna (`c++`) e mantenha `r` inalterado.
3. **Normalização (opcional, mas recomendado):** Divida toda a linha `r` pelo valor do pivô `A[r][c]`. Isso torna o pivô igual a 1, simplificando cálculos posteriores.
4. **Eliminação:** Para todas as outras linhas `i` (de 0 a n-1, `i != r`), transforme o elemento na coluna `c` em zero. Como?
- `adicionar(linha_i, linha_r, -A[i][c])`
- Ou seja, some à linha `i` o resultado de multiplicar a linha `r` (linha do pivô) por `-A[i][c]`. Isso faz com que `A[i][c]` se torne `A[i][c] - A[i][c] = 0`.
5. **Avance:** A linha e coluna atuais foram processadas. Incremente `r` e volte ao passo 1 para processar a próxima coluna.

Após processar todas as colunas, sua matriz aumentada `[A | b]` terá se transformado em `[triangular superior | novo b]`. Agora, comece pela última linha e faça a retrosubstituição para encontrar todas as incógnitas.

**Eliminação de Gauss-Jordan:**
Esta é uma versão "avançada" da eliminação de Gauss. Durante a etapa de eliminação, além de zerar os elementos abaixo do pivô, também se zeram os elementos acima. Quando o processo termina, a parte A da matriz se torna uma **matriz identidade** (diagonal principal com 1s e o resto com zeros).

[[1, 0, 0], [0, 1, 0], [0, 0, 1]]

A vantagem é que não é necessário fazer a retrosubstituição! O vetor b já contém a solução diretamente.

### Parte 4: Aplicações em Programação Competitiva

A eliminação de Gauss tem várias aplicações importantes:

1. **Resolver sistemas de equações lineares:** É sua aplicação principal. Alguns problemas aparentemente de teoria dos grafos, programação dinâmica ou fluxo em redes podem ser reduzidos a sistemas de equações lineares.
2. **Calcular matriz inversa:** Para encontrar a inversa de uma matriz A, construa uma matriz aumentada `[A | I]`, onde I é a matriz identidade. Aplique eliminação de Gauss-Jordan para transformar A em I. Quando isso for alcançado, a parte direita da matriz aumentada será A⁻¹: `[I | A⁻¹]`.
3. **Calcular determinante:** As transformações elementares afetam o determinante de formas previsíveis:
- Trocar duas linhas inverte o sinal do determinante.
- Multiplicar uma linha por k multiplica o determinante por k.
- Somar múltiplo de uma linha a outra não altera o determinante.
Usando isso, podemos transformar a matriz em triangular superior e calcular o determinante como o produto dos elementos da diagonal principal.
4. **Base linear (avançado):** O processo de encontrar uma base linear para um conjunto de vetores no espaço binário (com operações XOR) é essencialmente uma eliminação de Gauss em uma matriz com apenas 0s e 1s.

### Resumo

- **Transformações elementares de linha** são as três operações básicas e legais para manipular sistemas de equações.
- **Eliminação de Gauss** é um algoritmo que padroniza essas operações para transformar matrizes em formas mais simples (triangular superior), facilitando a solução.
- Na implementação, usamos geralmente um array bidimensional para representar a matriz aumentada e seguimos a "receita" da eliminação de Gauss passo a passo.

Espero que esta explicação ajude a conectar conceitos matemáticos abstratos com sua familiaridade com algoritmos!

Eliminação de Gauss
-----

Programadores competitivos, hoje vamos desmistificar o algoritmo de "Eliminação de Gauss", transformando-o em um procedimento que você poderá implementar com os olhos fechados.

Esqueça álgebra linear vetorial por um momento. Vamos tratar isso como um **jogo de quebra-cabeça**.

### Contexto do Jogo: Resolvendo Equações

Você já resolveu sistemas de equações como este:

3x + 2y = 7 (Equação ①) x - 4y = 5 (Equação ②)

Como resolveu? Provavelmente usando "eliminação por adição/subtração":

1. Multiplicou a equação ② por 3, obtendo `3x - 12y = 15` (Equação ③).
2. Subtraiu a equação ③ da equação ①: `(3x - 3x) + (2y - (-12y)) = 7 - 15`, resultando em `14y = -8`.
3. Instantaneamente, descobriu que `y = -8/14 = -4/7`.
4. Substituiu `y` em qualquer equação original para encontrar `x`.

Percebeu o padrão? A operação central é: **usar uma equação para "eliminar" uma variável de outra equação.**

A eliminação de Gauss formaliza esse processo, tornando-o algo que computadores podem executar facilmente.

### Objetivo do Jogo: Simplificar o Quebra-Cabeça

Imagine ter n equações com n incógnitas. Em programação, representamos os coeficientes com uma **matriz 2D** `A` e os termos independentes com um **vetor** `b`.

Para o exemplo acima, teríamos:
`A = [[3, 2], [1, -4]]`
`b = [7, 5]`

O objetivo da eliminação de Gauss é claro: através de operações válidas, transformar a matriz de coeficientes `A` em uma **"matriz triangular superior"**.

O que é uma matriz triangular superior? É uma matriz onde todos os elementos abaixo da diagonal principal são zero:

[[a, b, c], [0, d, e], [0, 0, f]]

Por que essa forma é útil? Porque torna o sistema trivial de resolver!

- A última linha corresponde à equação: `0*x + 0*y + f*z = ...`, permitindo calcular `z` diretamente.
- Com `z` conhecido, a penúltima linha `0*x + d*y + e*z = ...` permite calcular `y`.
- Progressivamente, todas as incógnitas são encontradas. Esse processo é chamado **retrosubstituição**.

### Regras do Jogo: As Ferramentas (Transformações Elementares)

Durante o jogo, você só tem três movimentos permitidos:

1. **Trocar duas linhas:** Equivalente a reorganizar as equações, sem alterar a solução.
2. **Multiplicar uma linha por um número não nulo:** Equivalente a multiplicar ambos os lados de uma equação por uma constante.
3. **Somar múltiplo de uma linha a outra:** A ferramenta principal para "eliminar" variáveis.

### Estratégia do Jogo: Algoritmo de Eliminação de Gauss

Aqui está o passo a passo, perfeitamente traduzível para código. Para facilitar, combinamos `A` e `b` em uma **matriz aumentada `[A | b]`**, onde todas as operações afetam uma linha inteira.

**Objetivo:** Transformar a parte `A` de `[A | b]` em triangular superior.

**Fluxo do algoritmo (suponha uma matriz aumentada com n linhas e n+1 colunas):**

**Passo 1: Selecionar o "pivô"**
Processamos coluna por coluna, começando pela `c = 0`. Nosso objetivo é usar a linha `r` (inicialmente 0) para zerar todos os elementos abaixo dela na coluna `c`.

for (int c = 0, r = 0; c < n; ++c) { // c é a coluna atual // r é a linha atual (linha do pivô)

**Passo 2: Encontrar o "melhor pivô" (Pivoteamento)**
Na coluna `c`, a partir da linha `r`, encontramos o elemento com maior valor absoluto. Suponha que ele esteja na linha `max_r`. **Trocamos as linhas `r` e `max_r`**.

- **Por que o maior valor?** Para evitar divisões por números muito pequenos, que causariam problemas de precisão numérica. Essa é uma prática essencial em implementações reais!
- **Se todos os elementos da coluna `c` abaixo de `r` forem zero?** O sistema pode não ter solução única. Nesse caso, pulamos essa coluna (`continue`) e incrementamos `c`, mantendo `r` inalterado.

int max_r = r;
for (int i = r + 1; i < n; ++i) {
    if (abs(matriz[i][c]) > abs(matriz[max_r][c])) {
        max_r = i;
    }
}
trocar_linhas(matriz, r, max_r);

**Passo 3: Eliminar variáveis**
Agora, `matriz[r][c]` é nosso pivô. Usaremos ele para zerar todos os elementos abaixo dele na coluna `c`.

Para cada linha `i` abaixo de `r` (de `r+1` a `n-1`):

1. Calcule o fator `fator = matriz[i][c] / matriz[r][c]`.
2. Subtraia da linha `i` o resultado de multiplicar a linha `r` por `fator`.
`matriz[i][j] -= matriz[r][j] * fator` (para `j` de `c` a `n`)

Com isso, `matriz[i][c]` se torna `matriz[i][c] - matriz[r][c] * (matriz[i][c] / matriz[r][c]) = 0`.

// Eliminação
for (int i = r + 1; i < n; ++i) {
    double fator = matriz[i][c] / matriz[r][c];
    for (int j = c; j <= n; ++j) { // Note que inclui a coluna de termos independentes
        matriz[i][j] -= matriz[r][j] * fator;
    }
}
r++; // Linha atual processada, movemos para a próxima

}

**Passo 4: Colher os Frutos (Retrosubstituição)**
Após as operações acima, a parte `A` da matriz está triangular. Agora, resolvemos do fundo para o topo.

- Última linha `n-1`: `A[n-1][n-1] * x[n-1] = b[n-1]`, então `x[n-1] = b[n-1] / A[n-1][n-1]`.
- Penúltima linha `n-2`: `A[n-2][n-2] * x[n-2] + A[n-2][n-1] * x[n-1] = b[n-2]`. Como `x[n-1]` é conhecido, calculamos `x[n-2]`.
- Progressivamente, resolvemos para todas as incógnitas.

### Resumo do Esqueleto do Código:

1. **Laço externo** `c` de `0` a `n-1`, indicando a coluna atual a ser zerada. `r` indica a linha do pivô.
2. **Encontrar pivô:** Na coluna `c`, abaixo da linha `r`, encontrar o elemento de maior valor absoluto e trocar para a linha `r`.
3. **Verificar solução:** Se o pivô encontrado for zero, o sistema pode ter problemas.
4. **Eliminação:** **Laço intermediário** `i` de `r+1` a `n-1`, percorrendo as linhas abaixo do pivô.
5. **Dentro do laço intermediário,** um **laço interno** `j` de `c` a `n`, atualizando cada elemento da linha `i`.
6. Após todos os laços, a matriz está triangular superior.
7. **Retrosubstituição:** Laço de `n-1` a `0`, calculando cada incógnita.

A eliminação de Gauss é um algoritmo simples porém poderoso, que transforma a intuição humana (eliminação de variáveis) em um procedimento mecânico para computadores. Dominá-lo permite resolver uma vasta gama de problemas relacionados a sistemas de equações em programação competitiva!