Determinante

[angel relativamente]

Re: Determinante

Hola THP. Está muy bien justificada la regla de Sarrus 3x3. Lo único que en la notación que yo he visto, no conozco ese $i(\sigma)$. Normalmente se define la función "signo de la permutación" $\epsilon(\sigma)$, que vale $1$ si $\sigma$ descompone como un número par de transposiciones, y -1 si lo hace como un número impar. De esa forma se escribe $\det(A)=\dst \sum_{\sigma \in S_n} \epsilon(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} ... a_{n \sigma(n)}$. ¿Entiendo que en tu caso $i(\sigma)$ es el número de transposiciones en que descompone? Observa que ese número no es único, por lo que $i(\sigma)$ no estaría bien definido, salvo paridad (que es lo único que interesa si lo vas a poner como exponente de un -1). Así, por ejemplo observa que tu $i(\sigma_3)$ podría valer 1, sin más que transponer el 1 y el 3.

Con respecto al problema, primero dos apuntes. 1- En efecto, al cardinal de un conjunto se le suele poner el # especialmente cuando es un conjunto finito. 2- No estoy seguro qué quieres decir con $S_n = \dst \sum_{i = 1}^{n!}\sigma_i$, ya que obviamente el conjunto de las permutaciones no es igual a la suma de las mismas.
Por otro lado, el número de sumas que hace el programa es $n!-1$ (si hay $n!$ sumandos, entonces hace $n!-1$ sumas), todo y que esto no modifica apenas el resultado. No obstante, te has dejado los productos. Observa que cada sumando tiene un total de $n+1$ factores, y por tanto de $n$ productos. En total el número de productos será $nn!$ y así el número de operaciones (sumas y productos) es $(n!-1)+nn!=nn!+n!-1 = (n+1)n! -1 = (n+1)! -1 \approx (n+1)!$. Observamos que además tiene que calcular esos $(-1)^{\sigma(i)}$, que aunque supongamos que los $\sigma(i)$ los calcula instantáneamente (o se los metes tú al programa), aún tendría que hacer $n!$ potencias. En total, las operaciones contando sumas, productos y potencias es $(n+1)!+n!$ y con $n=20$ ya nos pasaríamos de la edad del universo.

Por último, dejando de lado el problema, dices que esta es la definición rigurosa de determinante. Bueno, es una de ellas, pero no es algo aceptado unilateralmente entre los matemáticos. Cuando lees diversas fuentes, te encuentras que hay distintas definiciones para una misma cosa. Y no por ello alguna está mal, ya que si tú tomas algo como definición puedes ver que las otras se deducen de la misma (son teoremas, o como suele decirse, definiciones equivalentes). Esta en particular es bastante compacta ya que te da directamente el determinante a partir de los elementos de la matriz. Es por ello que goza de fama, pero tiene detractores debido a que es muy poco intuitiva (¿a quién se le ocurrió definir eso? ¿no tiene más sentido definir el determinante como algo más sencillo, y llegar a esa expresión como teorema?). A mí en particular me gusta más la definición recurrente. Lo único que tienes que definir con esta es el determinante de una matriz 1x1 (tan simple como decir que el determinante es el único elemento que tiene). Después, defines el determinante de una matriz nxn con el método de desarrollar por una fila y utilizar los menores, por lo que obtienes el determinante de una matriz nxn como combinación lineal de determinantes (n-1)x(n-1). Y con eso ya está, porque ahora cada determinante (n-1)x(n-1) lo puedes poner como c.l. de (n-2)x(n-2), e iterando dejarás el determinante original como c.l. de determinantes 1x1. Es lo mismo que la definición de permutaciones y no es difícil demostrar que coinciden, pero esta es mucho más natural.

Saludos,

[The Higgs Particle]

Re: Determinante

Creo que ya lo he entendido. Así, en una matriz de orden 3, hay un total de $3 ! = 6$ permutaciones posibles:

$\sigma_0(1,2,3) = Id(1,2,3)$	$i(\sigma_0) = 0$
$\sigma_1(1,2,3) = (2, 1, 3)$	$i(\sigma_1) = 1$
$\sigma_2(1,2,3) = (2, 3, 1)$	$i(\sigma_2) = 2$
$\sigma_3(1,2,3) = (3, 2, 1)$	$i(\sigma_3) = 3$
$\sigma_4(1,2,3) = (1, 3, 2)$	$i(\sigma_4) = 1$
$\sigma_5(1,2,3) = (3, 1, 2)$	$i(\sigma_5) = 2$

$\det(A) = |A| = \left|\begin{array}{rrr}a_{11} & a_{12} & a_{13} \\a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33}\end{array}\right|<br /> =$ $= \dst \sum_{\sigma \epsilon S_n} \dst \left( -1\right)^{i(\sigma)} a_{1 \sigma(1)} a_{2 \sigma(2)} a_{3 \sigma(3)}<br />$ $=\left[ (-1)^{0}a_{11}a_{23}a_{33}\right] + \left[ (-1)^{1}a_{12}a_{21}a_{33}\right] + \left[ (-1)^{2}a_{12}a_{23}a_{31}\right] + \left[ (-1)^{3}a_{13}a_{22}a_{31}\right] +$ $\left[ (-1)^{1}a_{11}a_{23}a_{32}\right] + \left[ (-1)^{2}a_{13}a_{21}a_{32}\right]$

Llegando así al conocido:

$|A| = a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32}$ $- a_{12}a_{21}a_{33} - a_{13}a_{22}a_{31} - a_{11}a_{23}a_{32}$

PD: A modo de juego, te dejo un ejercicio típico para ver qué poco eficiente es este método: Supón que tienes un ordenador que tarda 0.1s en realizar una operación (suma, resta, multiplicación...). Se pide calcular, para qué valor de $n$, el tiempo que tardará en calcular $\det(A)$, con $A\in M_{n\times n}$, es superior a la edad del universo. Te sorprenderá el valor

El número de operaciones (sumas, en este caso), que debe realizar la máquina serían:

$|S_n| = n!$

donde $|S_n|$ es el cardinal (leí que también se podría representar como $\# S_n$, ¿no?) del conjunto de todas las permutaciones posibles $\left( S_n = \dst \sum_{i = 1}^{n!}\sigma_i \right)$

Entonces, el tiempo total invertido sería:

$t_t = t |S_n| = \dst \frac{n!}{10}$

Como la edad del universo es, aproximadamente, $4.35 \times 10^{17} (s)$, entonces, sabiendo que $20! = 2.43 \times 10^{18}$, podemos decir que $\forall n \epsilon \mathbb{N}$ $|$ $n > 20$, se cumple que la máquina tardará más tiempo en realizar $|M|$, $M_{n \times n}$, que el transcurrido desde el inicio del universo.

¿Es así?

[angel relativamente]

Re: Determinante

Claro, $a_{i\sigma(i)}$ es el elemento de $A$ que está en la fila $i$ y en la columna $\sigma(i)$. Te pongo el ejemplo 2x2. En el conjunto $S_2$ solo hay 2 permutaciones, la identidad y la que permuta dos elementos $\sigma(1,2)=(2,1)$. Tenemos pues que el primer sumando asociado a la permutación identidad sería $a_{1Id(1)}a_{2Id(2)}=a_{11}a_{22}$, y el término asociado a la transposición será $-a_{1\sigma(1)}a_{2\sigma(2)}=-a_{12}a_{21}$ por lo que
$\det(A)=a_{11}a_{22}-a_{12}a_{21}$

PD: A modo de juego, te dejo un ejercicio típico para ver qué poco eficiente es este método: Supón que tienes un ordenador que tarda 0.1s en realizar una operación (suma, resta, multiplicación...). Se pide calcular, para qué valor de $n$, el tiempo que tardará en calcular $\det(A)$, con $A\in M_{n\times n}$, es superior a la edad del universo. Te sorprenderá el valor

Saludos,

[The Higgs Particle]

Estoy viendo que la definición rigurosa de determinante es:

$\det(A) = |A| = \left|\begin{array}{rrrr}a_{11} & a_{12} & ... & a_{1n} \\a_{21} & a_{22} & ... & a_{2n}\\ ... & ... & ... & ... \\ a_{n1} & a_{n2} & ... & a_{nn}\end{array}\right|$ $= \dst \sum_{\sigma \epsilon S_n} \left( -1\right)^{i(\sigma)} a_{1 \sigma(1)} a_{2 \sigma(2)} ... a_{n \sigma(n)}$

Entiendo que $S_n$ es el conjunto de todas las permutaciones ($\sigma$) de $n$ elementos (así, en una matriz de orden $3$, se tratará de jugar con las posiciones de $1,2,3$); también entiendo lo que es $i(\sigma)$ y cómo se calcula. Sin embargo, lo que no sé es qué significan los subíndices "$n \sigma(n)$".

Podríais echarme un cable?