Mostre que A=L U se, e somente se a eliminação de Gauss puder ser realizada sem pivoteamento (ou seja, cada pivô é diferente de zero). Em seguida, verifique que essa fatoração L U é única.

Passo 1

O enunciado pede duas coisas claras:
  1. Mostrar que, para uma matriz quadrada A\in\mathbb{R}^{n\times n}, vale a equivalência: existe uma fatoração A=L U (com L triangular inferior com diagional unitário e U triangular superior) se, e somente se, a eliminação de Gauss pode ser feita sem pivoteamento — isto é, em cada etapa o pivô utilizado é diferente de zero.
  2. Verificar que, sob as hipóteses acima (fatoração com L unitária), essa fatoração A=L U é única.
Dados/evidências fornecidas (ou que vamos assumir porque é padrão nesse tipo de enunciado):
  • A é uma matriz quadrada n\times n.
  • Quando falamos de L tomamos L como triangular inferior com \ell_{ii}=1 para todo i (chamada forma “unit lower triangular”).
  • Pivoteamento sem troca de linhas significa que em cada etapa o pivô (o elemento da diagonal principal da submatriz ativa) é não nulo.
A resolução efetiva começa no próximo passo.

Passo 2

Conceitos e ferramentas que vamos usar (explicados passo a passo, sem pular nada).
  1. Eliminação de Gauss em termos de multiplicação à esquerda: cada etapa da eliminação que zera entradas abaixo do pivô na coluna k pode ser escrita como multiplicação por uma matriz elementar M_k na forma
M_k = I - \begin{pmatrix}0\\\ \vdots \\\\ 0 \\\ m_{k+1,k} \\\ \vdots \\\ m_{n,k}\end{pmatrix}\!e_k^{T},
onde e_k é o k-ésimo vetor canônico e m_{i,k} (para i>k) são os multiplicadores usados para zerar a_{ik} (ou seja, m_{i,k} = a_{i,k}^{(k)}/a_{k,k}^{(k)} na notação de etapas). O ponto importante: M_k é triangular inferior com uns na diagonal exceto que tem sinais negativos dos multiplicadores abaixo da diagonal na coluna k. Essa matriz M_k é invertível sempre que o pivô a_{k,k}^{(k)} for não nulo, e
M_k^{-1} = I + \begin{pmatrix}0\\\ \vdots \\\\ 0 \\\ m_{k+1,k} \\\ \vdots \\\ m_{n,k}\end{pmatrix}\!e_k^{T},
ou seja, a inversa também é triangular inferior com uns na diagonal e com os multiplicadores (sem sinal negativo) abaixo da diagonal.
  1. Produto das etapas: se não precisamos trocar linhas (pivôs nunca nulos), aplicamos uma sequência de matrizes elementares à esquerda:
M_{n-1} \cdots M_2 M_1 A = U,
onde U é a matriz triangular superior obtida ao final da eliminação. Como cada M_k é invertível, podemos reescrever
A = M_1^{-1} M_2^{-1} \cdots M_{n-1}^{-1} U.
Definindo
L := M_1^{-1} M_2^{-1} \cdots M_{n-1}^{-1},
vemos que L é triangular inferior com diagonais iguais a 1 (produto de matrizes triangulares inferiores unitárias continua unitária) e portanto obtemos a forma A=L U.
Na prática, cada coluna abaixo da diagonal de L contém os multiplicadores usados para zerar abaixo do pivô naquela coluna da eliminação.

Passo 3

Direção "se a eliminação sem pivoteamento é possível, então existe A=L U":
  • Hipótese: durante a eliminação de Gauss em A nunca precisamos trocar linhas, isto é, em cada etapa k o pivô a_{k,k}^{(k)} é diferente de zero.
  • Como explicamos no passo anterior, para cada etapa k existe uma matriz elementar invertível M_k que realiza a operação de zerar as entradas abaixo do pivô na coluna k quando pre-multiplicamos por M_k.
  • Multiplicando todas as etapas:
U = M_{n-1}\cdots M_1 A.
  • Invertendo:
A = M_1^{-1} \cdots M_{n-1}^{-1} U.
  • Definimos L := M_1^{-1} \cdots M_{n-1}^{-1}. Cada M_k^{-1} é triangular inferior com diagonal unitária e elementos abaixo da diagonal exatamente os multiplicadores usados na etapa k; o produto de matrizes triangulares inferiores unitárias é triangular inferior unitária. Logo L é triangular inferior com \ell_{ii}=1.
  • Conclusão: existe decomposição A=L U, onde U é a matriz triangular superior final da eliminação e L armazena os multiplicadores. Assim a eliminação sem pivoteamento fornece explicitamente L e U.
Comentário prático (como você faria na prova): ao executar Gauss e anotar os multiplicadores m_{i,k} que você usou para zerar cada entrada a_{i,k}, esses m_{i,k} são precisamente os elementos \ell_{i,k} de L. O U obtido é o próprio resultado da eliminação.

Passo 4

Direção “se A=L U com L unitária e U triangular superior, então a eliminação sem pivoteamento funciona”:
  • Começamos assumindo que existe uma fatoração
A = L U,
onde L é triangular inferior com \ell_{ii}=1 e U é triangular superior.
  • Olhemos o primeiro pivô: a entrada u_{11} de U é igual à entrada a_{11} de A porque, escrevendo a primeira linha/coluna,
a_{11} = \sum_{k=1}^n \ell_{1k} u_{k1} = \ell_{11}u_{11} = u_{11},
pois \ell_{11}=1 e u_{k1}=0 para k>1. Portanto u_{11}=a_{11}. Se u_{11}=0 então a_{11}=0 e o pivô para a primeira etapa seria zero; para que a eliminação sem trocas prossiga precisamos desse pivô diferente de zero. Para que a fatoração exista com U triangular superior compatível com a eliminação, o natural é exigir u_{11}\neq0. Mas supondo a fatoração dada, se u_{11}=0 então a eliminação direta sem pivoteamento já falha na primeira etapa; portanto a existência da fatoração com U triangular com u_{11}\neq0 garante o primeiro pivô não nulo.
  • Determinando multiplicadores: para i>1 temos, olhando a coluna 1,
a_{i1} = \sum_{k=1}^n \ell_{ik} u_{k1} = \ell_{i1} u_{11},
pois u_{k1}=0 para k>1. Assim os valores \ell_{i1} são exatamente a_{i1}/u_{11}. Esses são os multiplicadores que a eliminação usaria na primeira etapa para zerar as entradas abaixo do pivô. Como u_{11}\neq0, esses multiplicadores estão bem definidos. Se aplicarmos as operações correspondentes, a coluna 1 abaixo do pivô fica zerada e a matriz restante (o chamado “resto” ou “Schur complement”) é precisamente a parte que resta de U (ou seja, a eliminação reproduz as partes superiores de U).
  • Repetição por indução: após zerar a primeira coluna com esses multiplicadores (os quais existem graças à decomposição), obtemos uma submatriz (o complemento) de tamanho (n-1)\times(n-1). A fatoração A=L U implica que esse complemento também se fatorará como produto da submatriz correspondente de L pela submatriz correspondente de U. Então o mesmo argumento se aplica recursivamente: o pivô seguinte é u_{22}, que é a diagonal do bloco U correspondente e, por hipótese da existência da fatoração, é o pivô que a eliminação verá; se u_{22}=0 a eliminação sem trocas falharia nessa etapa; se u_{22}\neq0 segue-se. Portanto, desde que o U da fatoração tenha todas as entradas diagonais não nulas (o que é equivalente à eliminação sem pivoteamento completa), a eliminação sem pivoteamento é realizável e os multiplicadores são precisamente os elementos abaixo da diagonal de L.
  • Conclusão do sentido inverso: a existência de A=L U com L unitária e U com diagonais não nulas garante que a eliminação de Gauss procede sem trocar linhas, com os pivôs sendo as entradas diagonais de U e os multiplicadores sendo os elementos de L.
Observação útil: uma condição comumente citada é que os menores principais (determinantes dos subblocos superiores esquerdos) sejam todos não nulos; essa condição é equivalente à existência de eliminação sem pivotamento e à existência de L U com L unitária. Mas para a prova pedida aqui basta o raciocínio via matrizes elementares e via igualdade de colunas mostrado acima.

Passo 5

Prova da unicidade da fatoração A=L U quando se exige L unitária:
  • Suponha que existam duas fatorações
A = L U = \tilde L \tilde U,
onde L,\tilde L são triangulares inferiores unitárias e U,\tilde U são triangulares superiores.
  • Reescrevendo, multiplicamos à esquerda por L^{-1} (que existe porque L é triangular com diagonal de uns, logo invertível):
U = L^{-1}\tilde L \,\tilde U.
Ou equivalentemente
L^{-1}\tilde L = U \tilde U^{-1}.
  • Agora observe as estruturas:
    • L^{-1}\tilde L é um produto de duas matrizes triangulares inferiores, logo é triangular inferior. Além disso, como L e \tilde L têm diagonal constituída por 1, a diagonal de L^{-1}\tilde L é também toda composta por 1. Portanto L^{-1}\tilde L é triangular inferior com 1's na diagonal.
    • U \tilde U^{-1} é produto de duas matrizes triangulares superiores, logo é triangular superior.
  • Como L^{-1}\tilde L = U \tilde U^{-1}, esta matriz comum é ao mesmo tempo triangular inferior e triangular superior, logo é uma matriz diagonal. Mas a diagonal dessa matriz é forçada a ser toda composta por 1's (porque a diagonal de L^{-1}\tilde L é toda 1). Assim a matriz comum é a identidade I.
  • Da igualdade L^{-1}\tilde L = I vem \tilde L = L. Substituindo em A=L U = \tilde L \tilde U fica L U = L \tilde U, e multiplicando à esquerda por L^{-1} obtemos U=\tilde U.
  • Conclusão: não podem existir duas fatorações distintas com L unitária; a fatoração A=L U é única sob a condição \ell_{ii}=1 para todo i.
Comentário intuitivo: os multiplicadores que você obtém na eliminação são fixos — não há liberdade — e, portanto, as entradas de L (e consequentemente de U) ficam determinadas de maneira única.

Resposta

A existência de A=L U (com L triangular inferior unitária e U triangular superior) é equivalente à possibilidade de realizar a eliminação de Gauss sem pivoteamento; em particular os pivôs são exatamente as entradas diagonais de U e os multiplicadores são as entradas abaixo da diagonal de L.
Essa fatoração A=L U, sob a condição de que L tenha diagonal unitária, é única.

Exercícios relacionados