Un algoritmo es un método que a partir de una entrada numérica escalar o vectorial, $v_0=v$, inicia un número finito de iteraciones, donde en cada una de ellas se realizan los mismos tipos de cálculo, produciendo a partir de una entrada $v_i$ una salida $v_{i+1}$. La última $v_n$ es la salida del algoritmo.
Si en cada paso, la salida $v_{i+1}$ es única el algoritmo se llama determinista. En caso contrario, se llama probabilístico.
Los algoritmos probabilísticos son aquellos que en cada iteración hay que elegir en un
conjunto una de las posibles salidas del cálculo
Dada una matriz cuadrada $A$, $n\times n$, cuando hay solo, $r<n$, vectores $$\lbrace v_1,\dots ,v_r\rbrace$$ propios l.i., $A$ no es diagonalizable. Pero en este caso, se puede usar un algoritmo probabilístico para hallar los $n-r$ vectores l.i. que faltan para hallar una matriz $P$ de cambio tal que $P^{-1}AP=J$ sea más sencilla.
Para cada valor propio $\lambda$ tal que tenga mult. geom. menor que su mult. alg., $\beta< \alpha$, consideramos la matriz $B=A-\lambda I$, su espacio propio $$N(B)=\lbrace u\in\mathbb{R}^n:\ Bu=0\rbrace$$ y su espacio de columnas $$C(B)=\lbrace v\in\mathbb{R}^n:\ (\exists u) Bu=v\rbrace$$ y calculamos su intersección $N(B)\cap C(B)$.
Clasificamos los autovectores l.i. asociados a $\lambda$, en aquellos que pertenecen a la intersección y los que no. Para los $v$ que pertenecen, consideramos la matriz ampliada $B|Y$ con la columna $Y=v$:
1) Mientras $rango(B)= rango(B|Y)$ e $Y\in C(B)$, se resuelve el s.l. $(A-\lambda I)X=Y$, se cambia $Y$ por $X$ y se reitera.
2) En cada paso, se intercala el vector solución $Y$ entre $v=v_i$, $v_{i+1}$.
Los vectores intercalados se llaman vectores propios generalizados de A
El algoritmo anterior es probabilístico porque en cada iteración se resuelve un s.l. y hay que elegir una entre sus infinitas soluciones.
El criterio de elección es elegir una en $C(B)$. Si no existe intersección con $C(B)$ entonces se elige una cualquiera y se pasa a otro autovector.
Así, cuando las soluciones dependen de un único parámetro sirve cualquier elección. El algoritmo comienza calculando una base de autovectores ampliando una de la intersección $N(B)\cap C(B)$.
Esto se hace para cada valor propio que tenga mult. geom. menor que su mult. alg. En cuyo caso, hay en total sólo $r<n$ autovectores l.i.
La verificación del algoritmo consiste en demostrar que calcula los $n-r$ vectores l.i. que faltan para encontrar una matriz de cambio $P$.
La demostración será por inducción sobre la dimensión $n$ de la matriz, pero antes de darla veremos un ejemplo.
La salida del algoritmo anterior es una matriz de cambio $P$ que tiene por columnas los $n-r$ vectores propios mas $r$ vectores intercalados. Así,
Cada columna de P es un vector propio o un vector propio generalizado de A
Siempre sale una matriz regular tal que $P^{-1}AP=B$ es una matriz semejante a $A$ que es casi diagonal:
$B$ tiene en la diagonal principal el valor propio, $b_{ii}=\lambda$ correspondiente al vector propio (puede ser generalizado) que aparece en la columna $i$ de $P$ y si este es generalizado tiene además un 1 en la posición $b_{i-1,i}$.
O sea, justo por encima de la diagonal (posición llamada subdiagonal).
Cada submatriz principal de B que contiene un mismo valor propio y unos por encima se llama
una caja de Jordan. La matriz B está formada por cajas de Jordan y otros valores propios en
la diagonal que corresponden a los que cumplen el teorema espectral. El resto ceros.
Una matriz $B$ que cumple lo anterior se llama una Forma de Jordan.
Desarrollando por filas y columnas, el pol. car. definido por la matriz $A$ es el siguiente determinante $$A=\begin{pmatrix} 2 & 0 & 0 & 0 & 0 & 0 \newline 1 & 2 & 0 & 0 & 0 & 0 \newline -1 & -1 & 2 & 0 & 0 & 0 \newline 0 & 1 & 0 & 2 & 1 & 0 \newline -1 & 0 & 0 & 0 & 2 & 0 \newline 1 & 0 & 0 & 0 & -1 & 2 \newline \end{pmatrix}\Rightarrow p(\lambda)=(2-\lambda)^6 $$ Su espectro real es unitario $\lbrace 2\rbrace$ y su multiplicidad algebraica es $\alpha = 6$.
Para $\lambda=2$ hay que calcular $r=rango(A-2 I)$. Como, por transformaciones de filas, la matriz $B=A-2 I$ es equivalente a $$\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 & 0 & 0 \newline -1 & -1 & 0 & 0 & 0 & 0 \newline 0 & 1 & 0 & 0 & 1 & 0 \newline -1 & 0 & 0 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 & -1 & 0 \end{pmatrix}\sim \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 & 0 & 0 \newline 0 & -1 & 0 & 0 & 0 & 0 \newline 0 & 0 & 0 & 0 & 1 & 0 \newline 0 & 0 & 0 & 0 & 0 & 0 \newline 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$$ donde hay sólo 3 filas distintas de cero, su rango es $r=3$ y la multiplicidad geométrica es $\beta=dim(V_\lambda)=6-3=3$. Entonces
No se verifica el teorema espectral porque 3 < 6
La matriz A no es diagonalizable por semejanza pero se puede hallar su forma de Jordan
El espacio propio asociado a $\lambda=2$ es la solución al s.l. reducido $$\begin{array}{l} \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \newline 0 & -1 & 0 & 0 & 0 & 0 \newline 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} x_1 \newline x_2 \newline x_3 \newline x_4 \newline x_5 \newline x_6 \end{pmatrix}=\begin{pmatrix} 0 \newline 0 \newline 0 \end{pmatrix}\Leftrightarrow x_1=x_2=x_5=0\newline \text{Por tanto, para } B=A-2 I \text{ las soluciones son}\newline V_1=N(B)=\lbrace (0,0,a,b,0,c)\in \mathbb{R}^3:\ a,b,c\in \mathbb{R}\rbrace \end{array} $$ Ahora, calcularemos la intersección $N(B)\cap C(B)$. Como $N(B)$ es el espacio anterior sólo necesitamos el espacio de columnas $C(B)$.
Como la matriz, $B=A-2 I$, tiene sólo 3 columnas distintas de cero, las e.p. y las e.c. de $C(B)$ respectivamente son $$\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 & 0 & 0 \newline -1 & -1 & 0 & 0 & 0 & 0 \newline 0 & 1 & 0 & 0 & 1 & 0 \newline -1 & 0 & 0 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 & -1 & 0 \end{pmatrix}\Rightarrow \left\lbrace\begin{array}{l} x_1 = 0\newline x_2 = \lambda_1\newline x_3 =-\lambda_1-\lambda_2\newline x_4 =\lambda_2+\lambda_3\newline x_5 =-\lambda_1\newline x_6 =\lambda_1-\lambda_3 \end{array}\right.\Leftrightarrow\left\lbrace\begin{array}{l} x_1 = 0 \newline x_5 = -x_2 \newline x_6 =-x_3 - x_4 \end{array}\right. $$ Juntando las e.c. de ambos subespacios, la intersección es $$\begin{array}{l} N(B)\cap C(B)\equiv\left\lbrace\begin{array}{l} x_1=x_2=x_5=0 \newline x_6 =-x_3 - x_4 \end{array}\right.\newline N(B)\cap C(B)=\lbrace (0,0,a,b,0,-a-b)\in \mathbb{R}^3:\ a,b\in \mathbb{R}\rbrace \end{array} $$
Y claramente se tiene que $dim_{\mathbb{R}}(N(B)\cap C(B))=2$
Sabemos que $dim_{\mathbb{R}}(N(B))=3$, luego podemos encontrar 3 autovectores l.i. eligiendo dos en la intersección $N(B)\cap C(B)$, con los valores $x_3=0, x_4=1$ y respectivamente $x_3=1, x_4=0$ $$ \begin{array}{l} v_1=(0, 0, 0, 1, 0, -1) \newline v_2=(0, 0, 1, 0, 0, -1) \end{array} $$ y otro adicional l.i. en $N(B)$, con los valores $x_3=0, x_4=0, x_6=1$: $$v_3=(0, 0, 0, 0, 0, 1)$$
Con $v_1$ y $v_2$, comienzan dos procesos de completación, eligiendo autovectores generalizados, resolviendo los s.l. correspondientes y continuando mientras se encuentre una solución en $C(B)$.
Para el autvector $v_1=(0, 0, 0, 1, 0, -1)$, resolvemos el s.l. $BX=v_1$ $$\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 & 0 & 0 \newline -1 & -1 & 0 & 0 & 0 & 0 \newline 0 & 1 & 0 & 0 & 1 & 0 \newline -1 & 0 & 0 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 & -1 & 0 \end{pmatrix}\begin{pmatrix} x_1 \newline x_2 \newline x_3 \newline x_4 \newline x_5 \newline x_6 \end{pmatrix}=\begin{pmatrix} 0 \newline 0 \newline 0 \newline 1 \newline 0 \newline -1 \end{pmatrix} $$ Igual que el correspondiente s.l. homogéneo, por transformaciones de filas, este sistema es equivalente a otro con sólo 3 filas distintas de cero que además se resuelve de forma inmediata.
$$ \begin{array}{l} \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \newline 0 & -1 & 0 & 0 & 0 & 0 \newline 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} x_1 \newline x_2 \newline x_3 \newline x_4 \newline x_5 \newline x_6 \end{pmatrix}=\begin{pmatrix} 0 \newline 0 \newline 1 \end{pmatrix}\Leftrightarrow\left\lbrace\begin{array}{l} x_1 = 0 \newline x_2 = 0 \newline x_5 =1 \end{array}\right.\newline \text{Por tanto, para } BX=v_1 \text{ el subesp. afín de las soluciones es}\newline W_1=\lbrace (0,0,a,b,1,c)\in \mathbb{R}^3:\ a,b,c\in \mathbb{R}\rbrace\Rightarrow W_1\cap C(B)=\emptyset \end{array} $$ Y la intersección sale vacía, ya que una de las e.p. del espacio de columnas, $x_5 = -x_2$, no es satisfecha por ninguna de estas soluciones.
Y elegimos el autovector generalizado y pasamos a otro proceso. $$a=b=c=0\Rightarrow v_4=(0, 0, 0, 0, 1, 0)$$
Para el autvector $v_2=(0, 0, 1, 0, 0, -1) $, resolvemos el s.l. $BX=v_2$ $$\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 & 0 & 0 \newline -1 & -1 & 0 & 0 & 0 & 0 \newline 0 & 1 & 0 & 0 & 1 & 0 \newline -1 & 0 & 0 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 & -1 & 0 \end{pmatrix}\begin{pmatrix} x_1 \newline x_2 \newline x_3 \newline x_4 \newline x_5 \newline x_6 \end{pmatrix}=\begin{pmatrix} 0 \newline 0 \newline 1 \newline 0 \newline 0 \newline -1 \end{pmatrix} $$ Igual que el correspondiente s.l. homogéneo, por transformaciones de filas, este sistema es equivalente a otro con sólo 3 filas distintas de cero que además se resuelve de forma inmediata.
$$ \begin{array}{l} \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \newline 0 & -1 & 0 & 0 & 0 & 0 \newline 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} x_1 \newline x_2 \newline x_3 \newline x_4 \newline x_5 \newline x_6 \end{pmatrix}=\begin{pmatrix} 0 \newline -1 \newline 1 \end{pmatrix}\Leftrightarrow\left\lbrace\begin{array}{l} x_1 = 0 \newline x_2 = -1 \newline x_5 =1 \end{array}\right. \end{array} $$ Por tanto, para $BX=v_2$, el subesp. afín de las soluciones es $$W_2=\lbrace (0,-1,a,b,1,c)\in \mathbb{R}^3:\ a,b,c\in \mathbb{R}\rbrace$$ Ahora, hay intersección no vacía con el subespacio de columnas $$ W_2\cap C(B)\equiv \left\lbrace\begin{array}{l} x_1 = 0 \newline x_5 = -x_2 = 1 \newline x_6 =-x_3 - x_4 \end{array}\right. $$ Elegimos el siguiente autovector generalizado y continuamos el proceso. $$a=b=c=0\Rightarrow v_5=(0, -1, 0, 0, 1, 0)$$
Para el autvector $v_5=(0, -1, 0, 0, 1, 0)$, resolvemos el s.l. $BX=v_5$ $$\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 & 0 & 0 \newline -1 & -1 & 0 & 0 & 0 & 0 \newline 0 & 1 & 0 & 0 & 1 & 0 \newline -1 & 0 & 0 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 & -1 & 0 \end{pmatrix}\begin{pmatrix} x_1 \newline x_2 \newline x_3 \newline x_4 \newline x_5 \newline x_6 \end{pmatrix}=\begin{pmatrix} 0 \newline -1 \newline 0 \newline 0 \newline 1 \newline 0 \end{pmatrix} $$ Igual que el correspondiente s.l. homogéneo, por transformaciones de filas, este sistema es equivalente a otro con sólo 3 filas distintas de cero que además se resuelve de forma inmediata.
$$ \begin{array}{l} \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \newline 0 & -1 & 0 & 0 & 0 & 0 \newline 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} x_1 \newline x_2 \newline x_3 \newline x_4 \newline x_5 \newline x_6 \end{pmatrix}=\begin{pmatrix} -1 \newline -1 \newline -1 \end{pmatrix}\Leftrightarrow\left\lbrace\begin{array}{l} x_1 = -1 \newline x_2 = 1 \newline x_5 = -1 \end{array}\right.\newline \text{Por tanto, para } BX=v_5 \text{ el subesp. afín de las soluciones es}\newline W_3=\lbrace (-1,1,a,b,-1,c)\in \mathbb{R}^3:\ a,b,c\in \mathbb{R}\rbrace\Rightarrow W_3\cap C(B)=\emptyset \end{array} $$ Y la intersección sale vacía, ya que una de las e.p. del espacio de columnas, $x_1 = 0$, no es satisfecha por ninguna de estas soluciones.
El algoritmo termina eligiendo el último autovector generalizado. $$a=b=c=0\Rightarrow v_6=(-1, 1, 0, 0, -1, 0)$$
Intercalando los autovectores generalizados sucesivamente detrás del autovector con que comienzan se obtiene una matriz de cambio, escrita por columnas $P=\lbrace v_3,v_1,v_4,v_2,v_5,v_6\rbrace$, que simplifica $A$: $$ \begin{array}{l}P= \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & -1 \newline 0 & 0 & 0 & 0 & -1 & 1 \newline 0 & 0 & 0 & 1 & 0 & 0 \newline 0 & 1 & 0 & 0 & 0 & 0 \newline 0 & 0 & 1 & 0 & 1 & -1 \newline 1 & -1 & 0 & -1 & 0 & 0 \newline \end{pmatrix} \end{array} $$ donde $P^{-1}AP=J$ es una matriz de Jordan con 3 cajas:
1) Una $1\times 1$, correspondiente a $v_3$ que no comienza proceso.
2) Una $2\times 2$, correspondiente al proceso $v_1, v_4$.
3) Una $3\times 3$, correspondiente al proceso $v_2,v_5,v_6$.
Con el orden dado a los vectores, en la matriz de cambio $$P=\lbrace v_3,v_1,v_4,v_2,v_5,v_6\rbrace$$ obtenemos la siguiente matriz de Jordan: $$ \begin{array}{l}P^{-1}AP= \begin{pmatrix} 2 & 0 & 0 & 0 & 0 & 0 \newline 0 & 2 & 1 & 0 & 0 & 0 \newline 0 & 0 & 2 & 0 & 0 & 0 \newline 0 & 0 & 0 & 2 & 1 & 0 \newline 0 & 0 & 0 & 0 & 2 & 1 \newline 0 & 0 & 0 & 0 & 0 & 2 \newline \end{pmatrix}=J \end{array} $$ que efectivamente es una matriz de Jordan con 3 cajas.
Por los 2 procesos del algoritmo se tienen las igualdades $$v_1=Bv_4,\ v_5=Bv_6,\ v_2=Bv_5=B^2v_6$$ Por tanto, el orden dado a las columnas de $P$ es $$P=\lbrace v_3,Bv_4,v_4,B^2v_6,Bv_6,v_6\rbrace$$ Si cambiamos el orden de las columnas, tenemos otra matriz de cambio $$ \begin{array}{l}P_1=\lbrace v_3,v_4,Bv_4,v_6,Bv_6,B^2v_6\rbrace=\newline =\begin{pmatrix} 0 & 0 & 0 & -1 & 0 & 0 \newline 0 & 0 & 0 & 1 & -1 & 1 \newline 0 & 0 & 0 & 0 & 0 & 1 \newline 0 & 0 & 1 & 0 & 0 & 0 \newline 0 & 1 & 0 & -1 & 1 & 0 \newline 1 & 0 & -1 & 0 & 0 & -1 \newline \end{pmatrix} \end{array} $$
Con esta matriz $P_1$ obtenemos la siguiente matriz de Jordan: $$ \begin{array}{l}P_1^{-1}AP_1= \begin{pmatrix} 2 & 0 & 0 & 0 & 0 & 0 \newline 0 & 2 & 0 & 0 & 0 & 0 \newline 0 & 1 & 2 & 0 & 0 & 0 \newline 0 & 0 & 0 & 2 & 0 & 0 \newline 0 & 0 & 0 & 1 & 2 & 0 \newline 0 & 0 & 0 & 0 & 1 & 2 \newline \end{pmatrix}=J_1 \end{array} $$ que coincide can la trapuesta de la anterior, $J_1=J^t$, y es una matriz de Jordan con 3 cajas pero que tiene los unos por debajo de la diagonal.
con las dos descomposiciones de Jordan tenemos $$ \begin{array}{l} P_1^{-1}AP_1=J_1=J^t=(P^{-1}AP)^t=P^tA^t(P^{-1})^t \Leftrightarrow\newline (P^t)^{-1}P_1^{-1}AP_1P^t=A^t\Leftrightarrow (P_1P^t)^{-1}A(P_1P^t)=A^t \end{array} $$ Por tanto, el producto $Q=P_1P^t$ nos convierte $A$ en $A^t$ y entonces
Toda matriz es semejante a su traspuesta
Estas transparencias han sido realizadas modificando ligeramente revealz, que se basa en reveal.js