Matrizes elementares

Nesta secção, iremos apresentar um tipo de matrizes que terão um papel relevante em resultados vindouros: as matrizes elementares. Estas dividem-se em três tipos:

$$a\ne 0; D_k (a)= \begin{array}{cc}\left[\begin{array}{ccccccc... ... \leftarrow k \end{array}\\ \uparrow & \\ k & \end{array}$$

$$i\ne j; E_{ij}\left( a \right) =\begin{array}{cc} \left[\begin{ar... ...ftarrow i \end{array}\\ \uparrow & \\ j & \end{array}$$

$$P_{ij} = \begin{array}{cl} \left[\begin{array}{cccccccccccc}... ...parrow&&&&&&&\uparrow\\ &i&&&&&&&j \end{array}\par \end{array}$$

Ou seja, as matrizes elementares de ordem $n$ são obtidas da matriz identidade $I_n$ fazendo:

• para $D_k(a)$, substituindo a entrada $(k,k)$ por $a$;
• para $E_{ij}(a)$, substituindo a entrada $(i,j)$ por $a$;
• para $P_{ij}$, trocando as linhas $i$ e $j$ (ou de outra forma, as colunas $i$ e $j$).

É óbvio que $D_\ell(1)=E_{ij}(0)=P_{kk}=I_n$.

A primeira propriedade que interessa referir sobre estas matrizes é que são invertíveis. Mais, para $a,b\in {\mathbb{K}}, a\ne 0$,

$$\left(D_k(a) \right) ^{-1}=D_k\left(\frac{1}{a}\right)$$

$$\left(E_{ij}(b) \right) ^{-1}=E_{ij}(-b),$$    para $$i\ne j$$

$$\left(P_{ij} \right) ^{-1}=P_{ij}$$

A segunda, relevante para o que se segue, indica outro o modo de se obter as matrizes $D_k(a)$ e $E_{ij}(a)$ da matriz identidade, cujas linhas são denotadas por $l_1,l_2,\dots, l_n$:

• para $D_k(a)$, substituindo a linha $k$ por $a l_k$;
• para $E_{ij}(a)$, substituindo a linha $i$ por $l_i+a l_j$.

Aplicando o mesmo raciocínio, mas considerando as colunas $c_1,c_2,\dots ,c_n$ da matriz identidade:

• para $D_k(a)$, substituindo a coluna $k$ por $a c_k$;
• para $E_{ij}(a)$, substituindo a coluna $j$ por $c_j+a c_i$.

Octave
Considere as matrizes $3\times 3$ elementares $D=D_2(5);E=E_{23}(3); P=P_{13}$. Recorde que a matriz $I_3$ é dada por eye(3).

> D=eye(3);
> D(2,2)=5;
> D
D =

  1  0  0
  0  5  0
  0  0  1

> E=eye(3);
> E(2,3)=3;
> E
E =

  1  0  0
  0  1  3
  0  0  1

> I3=eye(3);
> P=I3;
> P(1,:)=I3(3,:); P(3,:)=I3(1,:);
> P
P =

  0  0  1
  0  1  0
  1  0  0

Nesta última matriz, as instruções P(1,:)=I3(3,:); P(3,:)=I3(1,:); indicam que a primeira linha de $P$ é a terceira de $I_3$ e a terceira de $P$ é a primeira de $I_3$.

O que sucede se, dada uma matriz $A$, a multiplicarmos à esquerda ou à direita^2.2 por uma matriz elementar? Vejamos com alguns exemplos, tomando

$$A=\left[\begin{array}{ccc} 4 &2 &0\\ 1 & 1 & 0\\ 2 & -1 & 4\end{array}\right], P=P_{12}, E=E_{31}(-2), D=D_2\left(\frac{1}{2}\right).$$

Vamos usar o Octave para determinar o produto $DEPA$. Para tal, faremos primeiro $PA$, a este produto fazemos a multiplicação, à esquerda, por $E$, e finalmente ao produto obtido a multiplicação por $D$, de novo à esquerda.

Octave
Vamos então definir as matrizes A,P,E,D no Octave:

> A=[4 2 0; 1 1 0; 2 -1 4];
> I3=eye(3);
> E=I3; E(3,1)=-2;
> P=I3; P(1,:)=I3(2,:); P(2,:)=I3(1,:);
> D=I3; D(2,2)=1/2;

Façamos o produto $PA$:

> P*A
ans =

   1   1   0
   4   2   0
   2  -1   4

Qual a relação entre $A$ e $PA$? Repare que ocorreu uma troca da primeira e da segunda linha de $A$. Que por sinal foram as mesmas trocas que se efectuaram a $I_3$ de forma a obtermos $P_{12}$.

À matriz $PA$, multiplicamo-la, à esquerda, por $E$:

> E*P*A
ans =

   1   1   0
   4   2   0
   0  -3   4

> D*E*P*A
ans =

   1   1   0
   2   1   0
   0  -3   4

Uma matriz permutação de ordem $n$ é uma matriz obtida de $I_n$ à custa de trocas de suas linhas (ou colunas). Aqui entra o conceito de permutação. Uma permutação no conjunto $N_n=\left\{1,2,\dots , n\right\}$ é uma bijecção (ou seja, uma aplicação simultaneamente injectiva e sobrejectiva) de $N_n$ em $N_n$. Uma permutação $\varphi:N_n \rightarrow N_n$ pode ser representada pela tabela $\left( \begin{array}{cccc} 1 & 2 & \cdots &n\\ \varphi(1) & \varphi(2) & \cdots & \varphi(n)\end{array}\right)$. Para simplificar a escrita, é habitual omitir-se a primeira linha, já que a posição da imagem na segunda linha indica o (único) objecto que lhe deu origem.

Definição 2.3.1   O conjunto de todas as permutações em $N_n$ é denotado por $S_n$ e denominado por grupo simétrico.

Como exemplo, considere a permutação $\gamma = \left( 2, 1, 5, 3, 4 \right) \in S_5$. Tal significa que

$$\gamma(1)=2,\gamma(2)=1 ,\gamma(3)=5 ,\gamma(4)=3 ,\gamma(5)=4.$$

Note que $S_n$ tem $n!=n(n-1)(n-2)\dots2\cdot 1$ elementos. De facto, para $\gamma =(i_1,i_2,\dots ,i_n)\in S_n$, $i_1$ pode tomar $n$ valores distintos. Mas $i_2$ apenas pode tomar um dos $n-1$ restantes, já que não se podem repetir elementos. E assim por diante. Obtemos então $n!$ permutações distintas.

Dada a permutação $\varphi =(i_1,i_2,\dots ,i_n)\in S_n$, se $1\le j<k\le n$ e $i_j >i_k$ então $i_j >i_k$ diz-se uma inversão de $\varphi$. Na permutação $\gamma=(2,1,5,3,4)$ acima exemplificada existem três inversões, já que $\gamma(1)>\gamma(2),\gamma(3)>\gamma(4),\gamma(3)>\gamma(5)$. O sinal de uma permutação $\varphi$, denotado por $sgn(\varphi)$, toma o valor $+1$ caso o número de inversões seja par, e $-1$ caso contrário. Portanto, $sgn(\gamma)=-1$. As permutações com sinal $+1$ chamam-se permutações pares (e o conjunto por elas formado chama-se grupo alterno, $A_n$), e as cujo sinal é $-1$ denominam-se por permutações ímpares.

Uma transposição é uma permutação que fixa todos os pontos à excepção de dois. Ou seja, $\tau\in S_n$ é uma transposição se existirem $i,j$ distintos para os quais $\tau(i)=j,\tau(j)=i$ e $\tau(k)=k$ para todo o $k$ diferente de $i$ e $j$. Verifica-se que toda a permutação $\varphi$ se pode escrever como composição de transposições $\tau_1 ,\tau_2, \dots ,\tau_r$. Ou seja, $\varphi=\tau_1\circ \tau_2 \circ \dots \circ \tau_r$. Esta decomposição não é única, mas quaisquer duas decomposições têm a mesma paridade de transposições. Ou seja, se existe uma decomposição com um número par [resp. ímpar] de intervenientes, então qualquer outra decomposição tem um número par [resp. ímpar] de transposições. Mais, esse número tem a mesma paridade da do número de inversões. Por consequência, o sinal de qualquer transposição é $-1$. A permutação $\gamma$ definida atrás pode-se decompor como $(2,1,5,3,4)=(2,1,5,3,4)\circ (1,2,5,4,3)\circ(1,2,4,3,5)$.

O conjunto das permutações $S_n$ pode ser identificado com o conjunto das matrizes permutação de ordem $n$, em que a composição de permutação é de uma forma natural identificado com o produto de matrizes. A matriz permutação $P$ associada à permutação $\gamma$ é a matriz obtida de $I_5$ realizando as trocas de linhas segundo $\gamma$. Para fácil compreensão, vamos recorrer ao Octave.

Octave

> I5=eye(5);
> P=I5([2 1 5 3 4], :)
P =

  0  1  0  0  0
  1  0  0  0  0
  0  0  0  0  1
  0  0  1  0  0
  0  0  0  1  0

Na primeira linha de $P$ surge a segunda de $I_3$, na segunda a primeira, na terceira a quinta de $I_3$, e assim por diante.

De facto, toda a matriz permutação pode-se escrever como produto de matrizes da forma $P_{ij}$, tal como definidas atrás. Tal é consequência da existência de uma decomposição da permutação em transposições. Note que as transposições se identificam com as matrizes $P_{ij}$. Voltemos ao Octave e ao exemplo acima:

Octave
Em primeiro lugar, definamos as matrizes associadas às transposições, e façamos o seu produto:

> P1=I5([2 1 3 4 5], :);
> P2=I5([1 2 5 4 3], :);
> P3=I5([1 2 4 3 5], :);
> P1*P2*P3
ans =

  0  1  0  0  0
  1  0  0  0  0
  0  0  0  0  1
  0  0  1  0  0
  0  0  0  1  0

O produto iguala a matriz $P$ associada à permutação escolhida:

> all(all(P==P1*P2*P3))
ans = 1

Operações elementares sobre as linhas de $A$ são as que resultam pela sua multiplicação à esquerda por matrizes elementares. Ou seja, são operações elementares por linhas de uma matriz

• a troca de duas linhas,
• a multiplicação de uma linha por um escalar não nulo,
• a substituição de uma linha pela sua sua com um múltiplo de outra linha.

De forma análoga se definem as operações elementares sobre as colunas de uma matriz, sendo a multiplicação por matrizes elementares feita à direita da matriz. Na prática, tal resulta em substituir a palavra ``linha'' pela palavra ``coluna'' na descrição acima.

Considere a matriz $A=\left[\begin{array}{ccc} 2& 4 &6 1& 4& 2 -1 &0& 1\end{array}\right]$. Em primeiro lugar, e efectuando operações elementares nas linhas de $A$, tentaremos obter zeros por debaixo da entrada $(A)_{11}$. Ou seja, pretendemos obter algo como $\left[\begin{array}{ccc} 2 & 4 & 6\\ 0 & ? & ?\\ 0 & ? & ?\end{array}\right]$. Substitua-se a segunda linha, $l_2$, pela sua soma com o simétrico de metade da primeira. Ou seja,

$$\left[\begin{array}{ccc} 2& 4 &6 1& 4& 2 -1 &0& 1\end{array}\... ...2}l_1} \left[\begin{array}{ccc} 2& 4 &6 0& 2& -1 -1 &0& 1\end{array}\right]$$

Tal corresponde a multiplicar à esquerda a matriz $A$ por $E_{21}(-\frac{1}{2})=\left[\begin{array}{ccc}1 & 0&0\\ -\frac{1}{2}&1&0\\ 0&0&1\end{array}\right]$. Façamos o mesmo raciocínio para a terceira linha:

$$\left[\begin{array}{ccc} 2& 4 &6 1& 4& 2 -1 &0& 1\end{array}\... ...}{2}l_1} \left[\begin{array}{ccc} 2 & 4 &6\\ 0&2&-1\\ 0&2&4\end{array}\right]$$

Tal correspondeu a multiplicar o produto obtido no passo anterior, à esquerda, por $E_{31}(\frac{1}{2})$. Ou seja, e até ao momento, obteve-se

$$E_{31}(\frac{1}{2})E_{21}(-\frac{1}{2})A=\left[\begin{array}{ccc} 2 & 4 &6\\ 0&2&-1\\ 0&2&4\end{array}\right]=B.$$

Todos os elementos na primeira coluna de $B$, à excepção de $(B)_{11}$, são nulos. Concentremo-nos agora na segunda coluna, e na segunda linha. Pretendem-se efectuar operações elementares nas linhas de $B$ por forma a obter uma matriz da forma $\left[\begin{array}{ccc} 2 & 4 & 6\\ 0 & 2 & -1\\ 0 & 0 & ?\end{array}\right]$. Para tal,

$$\left[\begin{array}{ccc} 2 & 4 &6\\ 0&2&-1\\ 0&2&4\end{array}\r... ...l_2} \left[\begin{array}{ccc} 2 & 4 &6\\ 0&2&-1\\ 0&0&3\end{array}\right]=U.$$

Ou seja, multiplicou-se $B$, à esquerda, pela matriz $E_{32}(-1)$. Como $B=E_{31}(\frac{1}{2})E_{21}(-\frac{1}{2})A$ e $E_{32}(-1)B=U$ podemos concluir que

$$E_{32}(-1)E_{31}(\frac{1}{2})E_{21}(-\frac{1}{2})A=U=\left[\begin{array}{ccc} 2 & 4 &6\\ 0&2&-1\\ 0&0&3\end{array}\right]$$

Repare que $U$ é uma matriz triangular superior, e que neste exemplo tem elementos diagonais não nulos, e portanto é uma matriz invertível. Como as matrizes elementares são invertíveis e $(E_{32}(-1)E_{31}(\frac{1}{2})E_{21}(-\frac{1}{2}))^{-1}U=A$, segue que a matriz $A$ é também ela invertível. Note ainda que $(E_{32}(-1)E_{31}(\frac{1}{2})E_{21}(-\frac{1}{2}))^{-1}=E_{21}(\frac{1}{2})E_{31}(-\frac{1}{2})E_{32}(1)$. A estratégia descrita acima aplicada à matriz $A$ é denominada por algoritmo de eliminação de Gauss. O resultado final foi a factorização $A=LU$, onde $U$ é uma matriz triangular superior (veremos mais adiante que de facto pertence a uma subclasse desse tipo de matrizes) e $L$ é uma matriz invertível triangular inferior (por ser a inversa de produto de matrizes invertíveis triangulares inferiores). Nem sempre é possível percorrer estes passos do algoritmo, para uma matriz dada arbitrariamente. Veremos, na próxima secção, que modificações se realizam na estratégia apresentada acima por forma a que se garanta algum tipo de factorização.

Octave
Consideremos a matriz A dada por

> A=[2 4 6;2 2 2;-1 0 1];

À segunda linha de $A$ soma-se o simétrico da primeira linha:

> I3=eye(3); E21=I3; E21(2,1)=-1;
> A2=E21*A
A2 =

   2   4   6
   0  -2  -4
  -1   0   1

À terceira, somamos a primeira multiplicada por $\frac{1}{2}$:

> E31=I3; E31(3,1)=0.5;
> A3=E31*A2
ans =

   2   4   6
   0  -2  -4
   0   2   4

Finalmente, à terceira somamos a segunda linha:

> E32=I3; E32(3,2)=1;
> A4=E32*A3
A4 =

   2   4   6
   0  -2  -4
   0   0   0

A matriz A4 obtida é triangular superior, com um elemento diagonal nulo. Logo, a matriz inicial $A$ não é invertível.

O Octave contém o algoritmo numa sua rotina:

> [l,u,p]=lu(A)
l =

   1.00000   0.00000   0.00000
   1.00000   1.00000   0.00000
  -0.50000  -1.00000   1.00000

u =

   2   4   6
   0  -2  -4
   0   0   0

p =

  1  0  0
  0  1  0
  0  0  1

Aqui, u indica a matriz final do algoritmo e l a inversa do produto das matrizes elementares da forma $E_{ij}(\alpha)$ envolvidas:

> (E32*E31*E21)^-1

A matriz p é neste caso a identidade, e não tem nenhum papel. Mais à frente veremos a importância desta matriz (quando não é a identidade).

Obtivemos, então, a factorização lu=A.

O exemplo escolhido foi, de facto, simples na aplicação. Alguns passos podem não ser possíveis, nomeadamente o primeiro. Repare que o primeiro passo envolve uma divisão (no nosso caso, dividimos a linha 1 por $(A)_{11}$). A propósito, os elementos-chave na divisão, ou de forma mais clara, o primeiro elemento não nulo da linha a que vamos tomar um seu múltiplo denomina-se por pivot. Ora esse pivot tem que ser não nulo. E se for nulo? Nesse caso, trocamos essa linha por outra mais abaixo que tenha, nessa coluna, um elemento não nulo. E se todos forem nulos? Então o processo terminou para essa coluna e consideramos a coluna seguinte. Apresentamos dois exemplos, um para cada um dos casos descritos:

$$\left[\begin{array}{ccc}0 & 1 &2\\ 1& 1 & 2\\ -3& 2 &9\end{arra... ...\left[\begin{array}{ccc}0 & 1 & 1\\ 0 & 6 & 7\\ 0 & 1 & -2\end{array}\right].$$

No primeiro caso, a troca da primeira linha pela linha dois ou três resolve o problema. No segundo caso, aplicamos a estratégia a partir da segunda coluna. Recorde que a troca da linha $i$ pela linha $j$ é uma operação elementar de linhas que corresponde à multiplicação, à esquerda, por $P_{ij}$.

Apresentamos, de seguida, o algoritmo de eliminação de Gauss de uma forma mais formal.