Mat01098 - Seminário Integrador II - UFRGS

Prof. João Batista Carvalho

Assunto: Complexidade computacional. Cálculo de determinantes pela Regra de Laplace.

$n=1:$ $A = \left[ a \right] , \mbox{ det}(A) = a$ com $0$ produtos e $0$ somas

$n=2:$ $$A = \left[ \begin{array}{cc} a & b \\ c & d \end{array} \right] , \mbox{ det}(A)=ad - bc$$ com $2$ produtos e $1$ soma

$n\geq 3:$ $$A = \left[ \begin{array}{ccccc} a_{11} & \dots & a_{1j} & \dots &... ...dots & \dots \\ a_{n1} & \dots & a_{nj} & \dots & a_{nn} \end{array} \right]$$

$$\mbox{ det}(A) = a_{11} \cdot \mbox{cof}(a_{11}) + \dots + a_{i1} \cdot \mbox{cof}(a_{i1}) + \dots + a_{n1} \cdot \mbox{cof}(a_{n1})$$, onde

$\mbox{cof}(a_{ij}) = (-1)^{i+j} \cdot (\mbox{determinante de submatriz obtida removendo a linha i e a coluna j})$.

Tarefa: obter expressões para

• $p_n$, o número de produtos no cálculo de determinante de matriz $n\times n$;
• $s_n$, o número de somas no cálculo de determinante de matriz $n\times n$;

Pela Regra de Laplace, obtemos fórmulas recursivas

$$\left\{ \begin{array}{ll} p_2 = 2 & \\ p_{n} = n \cdot p_{n-1} + n &, n \geq 3 \end{array} \right.$$ ; $$\left\{ \begin{array}{ll} s_2 = 1 & \\ s_{n} = n \cdot s_{n-1} + n-1 &, n \geq 3 \end{array} \right.$$

que então nos permitem calcular:

$n$	$p_n$	$c_n$
2	2	1
3	9	5
4	40	23
5	205	119
6	1236	719

Expressão analítica para $p_n$ e $s_n$ ?

Um problema mais simples: $$\left\{ \begin{array}{ll} u_2 = 2 & \\ u_{n} = n \cdot u_{n-1} &, n \geq 3 \end{array} \right.$$ , tem solução $u_n = n!, n\geq 2$.

Definimos $a_n = p_n/n!$, de maneira que $p_n = a_n n!$, $n\geq 2$. Aplicando na fórmula de recorrência acima, temos $a_2 = 1$ e

$$a_{n} = a_{n-1} + \frac{1}{(n-1)!}, \ n \geq 3$$

e assim $$a_n = 1 + \frac{1}{2!}+\frac{1}{3!} + \dots + \frac{1}{(n-1)!}$$, $n\geq 2$. Do Cálculo Infinitesimal, sabemos

$$e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots + \frac{x^n}{n!} + \dots , x \in {\mathbb{R}}$$

o que implica $$\lim_{n \rightarrow \infty} a_n = e^1-1$$, e assim $$p_n \approx (e-1) n!$$ quando $n$ grande.

Por outro lado, definindo $b_n = s_n/n!$, de maneira que $s_n = b_n n!$, $n\geq 2$, temos $b_2 = 1/2$ e

$$b_n = b_{n-1} + \frac{1}{(n-1)!} - \frac{1}{n!}, \ n \geq 3$$

e simples exercício de indução mostra que

$$b_n = 1 - \frac{1}{n!} , n \geq 2$$

e assim $$\lim_{n \rightarrow \infty} b_n = 1$$ e podemos escrever $$s_n \approx n!$$ quando $n$ grande.

Finalmente, definimos $c_n = p_n + s_n$, o número de somas e produtos envolvidos no cálculo do determinante de uma matriz $n\times n$ usando a Regra de Laplace. Segue que $c_n \approx e \cdot n!$ quando $n$ grande (complexidade fatorial).