Archivo de la etiqueta: forma canónica

Álgebra Lineal II: Aplicaciones de la forma canónica de Jordan

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

En las entradas anteriores demostramos que cualquier matriz (o transformación lineal) tiene una y sólo una forma canónica de Jordan. Además, explicamos cómo se puede obtener siguiendo un procedimiento específico. Para terminar nuestro curso, platicaremos de algunas de las consecuencias del teorema de Jordan.

Clasificación de matrices por similaridad

Una pregunta que aún no hemos podido responder es la siguiente: si nos dan dos matrices $A$ y $B$ en $M_n(F)$, ¿son similares? Con la maquinaria desarrollada hasta ahora podemos dar una muy buena respuesta.

Proposición. Sean $A$ y $B$ matrices en $M_n(F)$ tales que el polinomio característico de $A$ se divide en $F$. Entonces, $A$ y $B$ son similares si y sólo si se cumplen las siguientes dos cosas:

  • El polinomio característico de $B$ también se divide en $M_n(F)$ y
  • $A$ y $B$ tienen la misma forma canónica de Jordan.

Demostración. Sea $J$ la forma canónica de Jordan de $A$.

Si $A$ y $B$ son similares, como $A$ es similar a $J$, se tiene que $B$ es similar a $J$. Entonces, $B$ tiene el mismo polinomio característico que $A$ y por lo tanto se divide en $F$. Además, como $J$ es similar a $B$, entonces por la unicidad de la forma canónica de Jordan, precisamente $J$ es la forma canónica de Jordan de $B$. Esto es un lado de nuestra proposición.

Supongamos ahora que el polinomio característico de $B$ también se divide en $M_n(F)$ y que la forma canónica de Jordan de $B$ también es $J$. Por transitividad de similaridad, $A$ es similar a $B$.

$\square$

Veamos un ejemplo de cómo usar esto en un problema específico.

Problema. Encuentra dos matrices en $M_2(\mathbb{R})$ que tengan como polinomio característico a $x^2-3x+2$, pero que no sean similares.

Solución. Las matrices $A=\begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix}$ y $B=\begin{pmatrix} 1 & 1 \\ 0 & 2 \end{pmatrix}$ ya están en forma canónica de Jordan y son distintas, así que por la proposición anterior no pueden ser similares. Además, por ser triangulares superiores, en ambos casos el polinomio característico es $$(X-1)(X-2)=X^2-3X+2.$$

$\triangle$

El problema anterior fue sumamente sencillo. Piensa en lo difícil que sería argumentar con cuentas de producto de matrices que no hay ninguna matriz $P\in M_2(\mathbb{R})$ tal que $A=P^{-1}B P$.

Forma canónica de Jordan «para cualquier matriz»

Como en $\mathbb{C}[X]$ todos los polinomios se dividen, entonces tenemos el siguiente corolario del teorema de Jordan.

Corolario. Toda matriz en $M_n(\mathbb{C})$ tiene una única forma canónica de Jordan.

Aquí $\mathbb{C}$ es muy especial pues es un campo completo, es decir, en el cual cualquier polinomio no constante tiene por lo menos una raíz. En general esto no es cierto, y es muy fácil dar ejemplos: $x^2-2$ no tiene raíces en $\mathbb{Q}$ y $x^2+1$ no tiene raíces en $\mathbb{R}$.

Sin embargo, existe toda un área del álgebra llamada teoría de campos en donde se puede hablar de extensiones de campos. Un ejemplo de extensión de campo es que $\mathbb{C}$ es una extensión de $\mathbb{R}$ pues podemos encontrar «una copia de» $\mathbb{R}$ dentro de $\mathbb{C}$ (fijando la parte imaginaria igual a cero).

Un resultado importante de teoría de campos es el siguiente:

Teorema. Sea $F$ un campo y $P(X)$ un polinomio en $F[X]$. Existe una extensión de campo $G$ de $F$ tal que $P(X)$ se divide en $G$.

¿Puedes notar la consecuencia que esto trae para nuestra teoría de álgebra lineal? Para cualquier matriz en $M_n(F)$, podemos considerar a su polinomio característico y encontrar campo $G$ que extiende a $F$ en donde el polinomio se divide. Por el teorema de Jordan, tendríamos entonces lo siguiente.

Corolario. Sea $A$ una matriz en $M_n(F)$. Entonces, $A$ tiene una forma canónica de Jordan en un campo $G$ que extiende a $F$.

Por supuesto, la matriz $P$ invertible que lleva $A$ a su forma canónica quizás sea una matriz en $M_n(G)$.

Toda matriz compleja es similar a su transpuesta

Ya demostramos que para cualquier matriz $A$ en $M_n(F)$ se cumple que $\chi_A(X)=\chi_(A^T)(X)$. Esto implica que $A$ y su transpuesta $A^T$ tienen los mismos eigenvalores, traza y determinante. También vimos que $\mu_A(X)=\mu_{A^T}(X)$. Las matrices $A$ y $A^T$ comparten muchas propiedades. ¿Será que siempre son similares? A continuación desarrollamos un poco de teoría para resolver esto en el caso de los complejos.

Proposición. Sea $J_{\lambda,n}$ un bloque de Jordan en $M_n(F)$. Entonces, $J_{\lambda,n}$ y $J_{\lambda,n}^T$ son similares.

Demostración. Para bloques de Jordan, podemos dar explícitamente la matriz de similitud. Es la siguiente matriz, con unos en la diagonal no principal:

$$P=\begin{pmatrix} 0 & 0 & \ldots & 0 & 1 \\ 0 & 0 & \ldots & 1 & 0 \\ \vdots & & \ddots & \vdots & \\ 0 & 1 & \ldots & 0 & 0 \\ 1 & 0 & \ldots & 0 & 0 \end{pmatrix}.$$

Esta matriz es invertible, su inversa es ella misma y cumple lo siguiente (ver ejercicios). Si $A$ es una matriz en $M_n(F)$, entonces:

  • Si $A$ tiene columnas $C_1,\ldots, C_n$, entonces $AP$ tiene columnas $C_n, \ldots, C_1$.
  • Si $A$ tiene filas $R_1,\ldots, R_n$, entonces $PA$ tiene filas $R_n, \ldots, R_1$.

Para los bloques de Jordan, si revertimos el orden de las filas y luego el de las columnas, llegamos a la transpuesta. Así, $J_{\lambda,n}^T=PJ_{\lambda,n}P$ es la similitud entre las matrices dadas.

$\square$

La prueba anterior no funciona en general pues para matrices arbitrarias no pasa que $A^T=PAP$ (hay un contraejemplo en los ejercicios). Para probar lo que buscamos, hay que usar la forma canónica de Jordan.

Teorema. En $M_n(\mathbb{C})$, toda matriz es similar a su transpuesta.

Demostración. Sea $A$ una matriz en $M_n(\mathbb{C})$. Como en $\mathbb{C}$ todo polinomio se divide, tanto $A$ como $A^T$ tienen forma canónica de Jordan. Digamos que la forma canónica de Jordan es

\begin{equation}J=\begin{pmatrix} J_{\lambda_1,k_1} & 0 & 0 & \ldots & 0 \\ 0 & J_{\lambda_2,k_2} & 0 & \ldots & 0 \\ 0 & 0 & J_{\lambda_3,k_3} & \ldots & 0 \\ & \vdots & & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & J_{\lambda_d,k_d}\end{pmatrix}.\end{equation}

Si $P$ es la matriz de similitud, tenemos que $A=P^{-1}JP$ y al transponer obtenemos que:

$$A^T=P^T\begin{pmatrix} J_{\lambda_1,k_1}^T & 0 & 0 & \ldots & 0 \\ 0 & J_{\lambda_2,k_2}^T & 0 & \ldots & 0 \\ 0 & 0 & J_{\lambda_3,k_3}^T & \ldots & 0 \\ & \vdots & & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & J_{\lambda_d,k_d}^T\end{pmatrix}(P^T)^{-1}.$$

Como por la proposición anterior cada bloque de Jordan es similar a su transpuesta, existen matrices invertibles $Q_1,\ldots,Q_d$ tales $J_{\lambda_i,k_i}^T=Q_i^{-1}J_{\lambda_i,k_i}Q_i$ para todo $i\in\{1,\ldots,d\}$. Pero entonces al definir $Q$ como la matriz de bloques

$$Q=\begin{pmatrix} Q_1 & 0 & \ldots & 0 \\ 0 & Q_2 & \ldots & 0 \\ 0 & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & Q_d \end{pmatrix},$$

obtenemos la similaridad

$$A^T=P^TQ^{-1} \begin{pmatrix} J_{\lambda_1,k_1} & 0 & 0 & \ldots & 0 \\ 0 & J_{\lambda_2,k_2} & 0 & \ldots & 0 \\ 0 & 0 & J_{\lambda_3,k_3} & \ldots & 0 \\ & \vdots & & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & J_{\lambda_d,k_d}\end{pmatrix} Q (P^T)^{-1}.$$

Así, $A$ y $A^T$ tienen la misma forma canónica de Jordan y por lo tanto son matrices similares.

$\square$

Más adelante…

¡Hemos terminado el curso de Álgebra Lineal II! Por supuesto, hay muchos temas de Álgebra Lineal adicionales que uno podría estudiar.

Un tema conectado con lo que hemos platicado es qué hacer con las matrices cuyo polinomio característico no se divide en el campo con el que estamos trabajando. Por ejemplo si tenemos una matriz $A$ en $M_n(\mathbb{R})$ cuyo polinomio característico no se divide, una opción es pensarla como matriz en $M_n(\mathbb{C})$ y ahí encontrar su forma canónica de Jordan. ¿Pero si queremos quedarnos en $\mathbb{R}$? Sí hay resultados que llevan una matriz a algo así como una «forma canónica» en $\mathbb{R}$ muy cercana a la forma canónica de Jordan.

Otro posible camino es profundizar en la pregunta de cuándo dos matrices en $M_n(F)$ son similares. Si tienen forma canónica de Jordan, ya dimos una buena caracterización en esta entrada. En los ejercicios encontrarás otra. Pero, ¿y si no tienen forma canónica de Jordan? Podríamos extender el campo a otro campo $G$ y comprar las formas canónicas ahí, pero en caso de existir la similaridad, sólo la tendremos en $M_n(G)$. Existe otra manera de expresar a una matriz en forma canónica, que se llama la forma canónica de Frobenius y precisamente está pensada para determinar si dos matrices son similares sin que sea necesario encontrar las raíces del polinomio característico, ni extender el campo.

Estos son sólo dos ejemplos de que la teoría de álgebra lineal es muy extensa. En caso de que estés interesado, hay mucho más por aprender.

Tarea moral

  1. Sea $A$ una matriz en $M_n(F)$ y tomemos $P$ en $M_n(F)$ la matriz
    $$P=\begin{pmatrix} 0 & 0 & \ldots & 0 & 1 \\ 0 & 0 & \ldots & 1 & 0 \\ \vdots & & \ddots & \vdots & \\ 0 & 1 & \ldots & 0 & 0 \\ 1 & 0 & \ldots & 0 & 0 \end{pmatrix}.$$
    • Demuestra que si $A$ tiene columnas $C_1,\ldots, C_n$, entonces $AP$ tiene columnas $C_n, \ldots, C_1$.
    • Demuestra que si $A$ tiene filas $R_1,\ldots,R_1$, entonces $PA$ tiene filas $R_n,\ldots,R_n$.
    • Concluye con cualquiera de los incisos anteriores que $P$ es invertible y su inversa es ella misma.
    • Tomemos explicitamente $n=2$ y $A=\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$. Encuentra explícitamente $PAP$. ¿Es $A^T$?
  2. ¿Cuál es la máxima cantidad de matrices que se pueden dar en $M_5(\mathbb{C})$ de manera que cada una de ellas tenga polinomio característico $x^2(x^2+1)(x+3)$ y tales que no haya dos de ellas que sean similares entre sí.
  3. Sea $A$ una matriz en $M_n(\mathbb{R})$ tal que su polinomio característico se divide en $\mathbb{R}$, con forma canónica de Jordan $J$. Sea $P(X)$ un polinomio en $\mathbb{R}[X]$.
    • Demuestra que el polinomio característico de $P(A)$ se divide en $\mathbb{R}$.
    • La forma canónica de Jordan de $P(A)$ no necesariamente será $P(J)$ pues puede que el polinomio altere el orden de los eigenvalores pero, ¿cómo se obtiene la forma canónica de $P(A)$ a partir de $J$?
  4. Sean $A$ y $B$ matrices en $M_n(F)$ cuyo polinomio característico se divide en $F$. Muestra que $A$ y $B$ son similares si y sólo si para cualquier polinomio $P(X)$ en $F[X]$ se tiene que $\text{rango}(P(A))=\text{rango}(P(B))$.
  5. Investiga sobre la forma canónica de Frobenius y sobre la variante a la forma canónica de Jordan restringida a $\mathbb{R}$.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

Investigación de Operaciones: Forma canónica y forma estándar de un problema lineal (9)

Por Aldo Romero

1 respuesta

Introducción

En las entradas anteriores hemos dado ejemplos de varios problemas de aplicación que pueden ser planteados mediante un problema de programación lineal. Una vez que llegamos a un modelo, se pueden tener restricciones de los tipos $\leq$, $=$ y $\geq$. Además, puede haber restricciones de signo sobre las variables. Puede que se les pida ser no positivas, no negativas o irrestrictas (no restringidas) en signo. Lo que haremos ahora es recordar forma estándar y forma canónica de un problema lineal; y como pasar de un formato a otro.

Forma canónica de un problema lineal

Definición. Se dice que un problema de programación lineal está en forma canónica si cumple las siguientes tres propiedades:

  1. Las variables de decisión son todas no negativas ($x_i \geq 0$).
  2. El problema es de maximización ($Max \quad z = c_1x_1+\ldots+c_nx_n$).
  3. Las restricciones del problema son todas del tipo $\leq$ ($a_{i1}x_1+ \ldots + a_{in}x_n \leq b_i$).

Tenemos entonces que un problema en forma canónica se ve de la siguiente manera:

\begin{align*}
Max \quad z &= c_1x_1+\ldots+c_nx_n\\
s.a.&\\
&\begin{matrix} a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n \leq b_1\\
a_{21}x_1+a_{22}x_2+\ldots + a_{2n}x_n \leq b_2\\
\vdots \\
a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n\leq b_n\end{matrix}\\
& x_1\geq 0, x_2\geq 0, \ldots, x_n\geq 0.
\end{align*}

En términos matriciales, esto podemos reescribirlo de manera mucho más compacta como sigue:

\begin{align*}
Max \quad z &= c^tx\\
s.a.&\\
Ax &\leq b\\
x &\geq \bar 0,\\
\end{align*}

en donde:

  • $c=(c_1,\ldots,c_n)\in \mathbb R^n$ es el vector de costos
  • $x = (x_1,\ldots,x_n)\in \mathbb R^n$ es el vector de variables de decisión,
  • $A=[a_{ij}]$ es la matriz de restricciones, que es una matriz de $m \times n$ y
  • $b = (b_1,\ldots,b_m) \in \mathbb R^m$ es el vector de términos independientes o vector de recursos,
  • Entendemos $\bar{0}$ como el vector en $\mathbb{R}^n$ cuyas entradas son todas cero.

Dado un problema de programación lineal, este siempre se puede ser expresar en su forma canónica; es decir, puede definirse un problema en forma canónica equivalente a él. Esta expresión del problema nos ayuda a resolverlo con métodos de solución que veremos más adelante, pero que requieren que el problema esté en su forma canónica.

A continuación de presenta una serie de posibilidades que podria tener un problema de programación lineal formulado y qué se debe de hacer para que cumpla las condiciones para pasarlo a su forma estándar.

  • Para una variable negativa ($x_i\leq 0$), se puede sustituir por una nueva variable $x_i’$ definida como $x_i’ = -x_i$, siendo ahora $x_i’ \geq 0$. El valor de $x_i$ está directamente relacionado con el valor de $x_i’$ ya que es su opuesto negativo.
  • Para una variable $x_i$ sin restricción de signo (SRS), se pueden definir dos variables no negativas $x_i’$ y $x_i»$ tales que el resultado de su resta sea $x_i$ ($x_i = x_i’-x_i$»). Dada cualquier $x_i$, podemos construir dichas variables, y así mismo; dadas cualesquiera $x_i’$ y $x_i»$, se puede construir $x_i$.
  • Si el problema formulado es a minimizar ($Min \quad z = c_1x_1+\ldots+c_nx_n$), puede considerarse en vez de la función $z$, su opuesta negativa $z’$ (es decir, $z’ = -z$). Así, minimizar la función $z$ equivale a maximizar la función $z’$ ($Max \quad z’ = -c_1x_1 – \ldots -c_nx_n$).
  • Si dada una restricción, esta es del tipo $\geq$ ($a_{i1}x_1+ \ldots + a_{in}x_n \geq b_i$), se pueden multiplicar ambos lados de la restricción por un $-1$ para que la desigualdad se invierta y nos quede una restricción del tipo $\leq$ ($-a_{i1}x_1- \ldots – a_{in}x_n \leq -b_i$).
  • Una ecuación ($a_{i1}x_1+ \ldots + a_{in}x_n = b_i$) puede ser substituida por dos desigualdades, una del tipo $\leq$ ($a_{i1}x_1+ \ldots + a_{in}x_n \leq b_i$) y otra del tipo $\geq$ ($a_{i1}x_1+ \ldots + a_{in}x_n \geq b_i$). Luego, la ecuación del tipo $\geq$ puede se multiplica de ambos lados por un $-1$ para que sea una ecuación del tipo $\leq$ ($-a_{i1}x_1 – \ldots -a_{in}x_n \leq -b_i$).

Ejemplo 1 de pasar un problema a forma canónica

Transformemos el siguiente problema a su forma canónica:
\begin{align*}
Min \quad z &= 3x_1-x_2\\
s.a&\\
&\begin{matrix}2x_1&+x_2& \leq 50\\
-x_1&+3x_2& \geq 20\end{matrix}\\
& x_1\geq 0, x_2 \leq 0\\
\end{align*}

Primero, observemos que la primera condición se cumple para la variable $x_1$, pero para $x_2$ no ya que $x_2 \geq 0$. Entonces definimos $x_2′ = -x_2$ y de esa manera, $x_2′ \leq 0$.

Ahora, la segunda condición nos dice que el problema tiene que ser de maximización y en este momento es de minimización. Para transformar nuestro problema a uno de maximización solo tenemos que invertir el signo de la función objetivo, ya que el minimizar la primera función ($z$) es equivalente a maximizar la función negativa ($-z$).

$$Max \quad z = -3x_1 + x_2$$

Y por último verifiquemos que se cumpla la tercera condición. La primera restricción claramente es del tipo $\leq$, pero la segunda restricción no es del tipo $\leq$ sino que es del tipo $\geq$. A esta restricción se le puede multiplicar por -1 de ambos lados y se convierte en una restricción del tipo $\leq$.

\begin{matrix}2x_1&+x_2& \leq 50\\
x_1&-3x_2& \leq -20\end{matrix}

Entonces nuestro problema ya cumple las 3 condiciones y podemos decir que está en forma canónica:

\begin{align*}
Max \quad z &= -3x_1 + x_2\\
&s.a\\
&\begin{matrix}2x_1&+x_2& \leq& 50\\
x_1&-3x_2& \leq& -20\end{matrix}\\
& x_1, x_2\geq 0\\
\end{align*}

Ejemplo 2 de pasar un problema a forma canónica

Transformemos el siguiente problema a su forma canónica.

\begin{align*}
Max \quad z &= 2x_1 + 5x_2 -3x_3\\
&s.a\\
&\begin{matrix}-x_1&+2x_2&-4x_3 =& -9\\
3x_1&+x_2&-5x_3 \geq& 10\\
4x_1&-6x_2&+7x_3 \geq& 2\\
\end{matrix}\\
& x_1, x_2\geq 0, \quad x_3 \quad SRS\\
\end{align*}

Primero observemos que la primera condición se cumple para $x_1$ y $x_2$ pero $x_3$ está sin restricción de signo, por lo que vamos a definir $x_3’$ y $x_3″$ no negativos tales que $x_3 = x_3′- x_3″$.

Ahora, observemos que el problema ya es de maximización. Lo único que haremos es sustituir la variable $x_3$ que acabamos de re definir:

$$Max \quad z = 2x_1 + 5x_2 – 3x_3′ + 3x_3″$$

Y por último, para cumplir la tercera restricción tenemos que hacer a todas nuestras restricciones del tipo $\leq$.

Para la primera restricción, primero sustituimos la variable $x_3$ en términos de $x_3’$ y $x_3″$:

$$-x_1 + 2x_2 – 4x_3′ + 4x_3″ = -9$$

Y dado que es una igualdad, la podemos sustituir por dos desigualdades. Estas son:

\begin{matrix}-x_1&+2x_2&-4x_3’& + 4x_3″& \leq -9\\
-x_1&+2x_2& -4x_3’& +4x_3″& \geq -9\end{matrix}

La primera de estas dos nuevas restricciones ya es del tipo $\leq$, pero la segunda es del tipo $\geq$, por lo que lo único que hay que hacer es multiplicar por $-1$ de cada lado para que la desigualdad se invierta y la restricción sea del tipo $\leq$:

\begin{matrix}-x_1&+2x_2&-4x_3’& + 4x_3″& \leq -9\\
x_1&-2x_2& +4x_3’& -4x_3″& \leq 9\end{matrix}

Para la segunda y tercera restricción del problema original, primero sustituimos a variable $x_3$ en términos de $x_3’$ y $x_3″$:

\begin{matrix}3x_1&+x_2&-5x_3’& + 5x_3″& \geq 10\\
4x_1&-6x_2& +7x_3’& -7x_3″& \geq 2\end{matrix}

Y luego transformamos estas restricciones en restricciones del tipo \leq como acabamos de hacer.

\begin{matrix}-3x_1&-x_2&+5x_3’& -5x_3″& \leq -10\\
-4x_1&+6x_2& -7x_3’& +7x_3″& \leq -2\end{matrix}

Y así, juntando todo, el problema quedaría planteado de la siguiente manera:

\begin{align*}
Max \quad z = 2x_1 + 5x_2 – 3x_3′ + 3x_3″\\
\begin{matrix}-x_1&+2x_2&-4x_3’& + 4x_3″& \leq -9\\
x_1&-2x_2& +4x_3’& -4x_3″& \leq 9\\
3x_1&-x_2&+5x_3’& -5x_3″& \leq -10\\
-4x_1&+6x_2& -7x_3’& +7x_3″& \leq -2\end{matrix}\\
x_1, x_2, x_3′, x_3″ \geq 0\\
\end{align*}

Y así este segundo problema quedaría en su forma canónica.

Forma estándar de un problema lineal

Definición. Se dice que un problema de programación lineal está en forma estándar si

  1. Todas las variables son no negativas.
  2. Todas las restricciones son ecuaciones.
  3. Todos los elementos del vector de recursos son no negativos

De esta manera, un problema en forma estándar se ve como sigue:

\begin{align*}
Max\, (\text{o } Min) \quad z &= c_1x_1+\ldots+c_nx_n\\
s.a.&\\
&\begin{matrix} a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n = b_1\\
a_{21}x_1+a_{22}x_2+\ldots + a_{2n}x_n = b_2\\
\vdots \\
a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n= b_n\\
x_1\geq 0, x_2\geq 0, \ldots, x_n\geq 0.
\end{matrix}\\
\end{align*}

En notación matricial, el problema en forma canónica queda expresado de la siguiente manera:

\begin{align*}
Max\, (\text{o } Min) \quad z &= c^tx\\
s.a.&\\
Ax &= b\\
x &\geq \bar 0\\
\end{align*}

en donde $c, x, A$ y $b \geq \bar 0$ son como se mencionó antes.

Así como cualquier problema de programación lineal puede ser escrito en su forma canónica, así también cualquier problema de programación lineal puede ser escrito en forma estándar.

Aparte de las indicaciones anteriores que dimos para pasar un problema a su forma canónica, daremos una indicación de qué hacer cuando tenemos una desigualdad y queremos convertirla en igualdad:

  • Si tenemos una restricción del tipo $\leq$ ($a_{i1}x_1+ \ldots + a_{in}x_n \leq b_i$), definiremos una variable de holgura no negativa $x_{n+1}$ tal que $a_{i1}x_1+ \ldots + a_{in}x_n + x_{n+1} = b_i$.
  • Si tenemos una restricción del tipo $\geq$ ($a_{i1}x_1+ \ldots + a_{in}x_n \geq b_i$), definiremos una variable de holgura no negativa $x_{n+1}$ tal que $a_{i1}x_1+ \ldots + a_{in}x_n – x_{n+1} = b_i$.

Ejemplo 1 de pasar un problema a forma estándar

Retomemos el primer ejemplo, antes de expresarlo en forma estándar.

\begin{align*}
Min \quad z &= 3x_1-x_2\\
s.a&\\
&\begin{matrix}2x_1&+x_2& \leq 50\\
-x_1&+3x_2& \geq 20 \end{matrix}\\
& x_1 \geq 0, x_2 \leq 0\\
\end{align*}

Observemos que la primera condición se cumple para la variable $x_1$, pero para $x_2$ no ya que $x_2 \geq 0$. Entonces definimos $x_2′ = -x_2$ y de esa manera, $x_2′ \leq 0$.

Para la función objetivo, solo hay que sustituir $x_2$ en términos de $x_2’$, ya que recordemos la función puede ser a maximizar o minimizar:

$$Min \quad z = 3x_1+x_2’$$

Para cumplir la segunda condición, debemos añadir variables de holgura a las restricciones que son desigualdades como se acaba de mencionar. En la primera restricción, se define un variable no negativa $x_3$ tal que $2x_1+x_2 +x_3 = 50$. En la segunda restricción, se define una variable no negativa $x_4$ tal que $-x_1+3x_2 -x_4 = 20$

Y la tercera condición se cumple, ya que 50 y 20 son no negativos.

Así, juntando todos estos cambios, la forma estándar de este problema quedaría de la siguiente manera:

\begin{align*} Min \quad z &= 3x_1+x_2’\\
s.a&\\
&\begin{matrix}2x_1&+x_2& +x_3 = 50\\
-x_1&+3x_2& -x_4 = 20 \end{matrix}\\
& x_1, x_2′ \geq 0\\
\end{align*}

Ejemplo 2 de pasar un problema a forma estándar

Retomemos el segundo ejemplo, antes de expresarlo en forma estándar.

\begin{align*}
Max \quad z &= 2x_1 + 5x_2 -3x_3\\
&s.a\\
&\begin{matrix}-x_1&+2x_2&-4x_3 =& -9\\
3x_1&+x_2&-5x_3 \geq& 10\\
4x_1&-6x_2&+7x_3 \geq& 2\\
\end{matrix}\\
& x_1, x_2\geq 0, \quad x_3 \quad SRS\\
\end{align*}

Para la primera condición, las variables $x_1$ y $x_2$ cumplen con la no negatividad. La variable $x_3$ en cambio es una variable sin restricción de signo (SRS), por lo que, como se hizo anteriormente, definiremos variables no negativas $x_3’$ y $x_3″$ tales que $x_3 = x_3′ – x_3″$. En la función objetivo solo reemplazamos $x_3$ en términos de $x_3’$ y $x_3″$:

$$Max \quad z = 2x_1 + 5x_2 -3x_3′ + x_3″$$

La primera restricción ya cumple la segunda condición, por lo que solo hay que sustituir a $x_3$.

$$-x_1 +2x_2 -4x_3′ +4x_3″ = -9$$

En la segunda restricción definimos una variable de holgura no negativa $x_4$ tal que $3x_1 +x_2 -5x_3 -x_4 = 10$. Y sustituimos $x_3$ de igual forma:

$$3x_1 +x_2 -5x_3′ + 5x_3″ -x_4 = 10$$

Y para la tercera restricción definimos una variable de holgura no negativa $x_5$ tal que $4x_1-6x_2+7x_3 -x_5 = 2$. Y también sustituimos $x_3$:

$$4x_1-6x_2+7x_3′ – 7x_3″ -x_5 = 2$$

Y por último, la única restricción que no cumple la tercera condición es la primera, por lo que multiplicamos la ecuación por $-1$ para invertir el signo del valor independiente y sea no negativo:

$$x_1 -2x_2 +4x_3′ -4x_3″ = 9$$

Por lo que, juntando los cambios anteriores, la forma estándar de este problema sería la siguiente:

\begin{align*}
Max \quad z &= 2x_1 + 5x_2 -3x_3′ + 3x_3″\\
&s.a\\
&\begin{matrix}x_1&-2x_2&+4x_3’&-4x_3″& =& 9\\
3x_1&+x_2&-5x_3’& +5x_3″& -x_4& = 10\\
4x_1&-6x_2&+7x_3’& -7x_3″& -x_5& = 2\\
\end{matrix}\\
& x_1, x_2, x_3′, x_3″,x_4, x_5\geq 0\\
\end{align*}

Más adelante…

Las formas que estudiamos en esta entrada nos ayudarán posteriormente para plantear soluciones para problemas de programación lineal.

Mientras tanto, en la siguiente entrada hablaremos de otros conceptos relativos a la teoría de problemas lineales y propiedades que puede tener una asignación de variables. Recordaremos también lo que es una solución básica, una solución factible y un punto extremo para un problema lineal.

Tarea moral

  1. ¿Cuál sería la forma canónica del problema de maximizar $x+3y$ sujeto a $x-y\leq 8$ y $x + y \leq 0$, con $x \geq 0, y \quad \text{SRS}$? ¿Y su forma estándar?
  2. Transforma el siguiente problema de programación lineal a su forma canónica y a su forma estándar:
    \begin{align*}
    Max \quad z &= -2x_1 + 3x_2 – 2x_3\\
    &s.a.\\
    &\begin{matrix}4x_1 &-x_2 &- 5x_3 &=& 10\\
    2x_1 &+ 3x_2 &+ 2x_3 &\geq &12\end{matrix}\\
    & x_1 \leq 0, \quad x_2 \geq 0, x_3 \quad SRS.
    \end{align*}
  3. Encontrar la solución a la forma estándar (y también la canónica) de un problema de programación lineal es equivalente a encontrar la solución al problema original. ¿Porqué crees que se da esto? Justifica con tus propias palabras.

Respuestas

1.- \begin{align*}
Max \quad z &= x + 3y\\
&s.a\\
x-y &\geq -8\\
x+y &\leq 15 \\
x &\geq 0, y \quad SRS\\
\end{align*}

Primero, vamos a pasar el problema a su forma canónica.

Notemos que $x$ es no negativa. Sin embargo, $y$ es una variable sin restricción de signo, por lo que definimos variables no negativas $y’$ y $y»$ tales que $y = y’ – y»$

Sustituimos $y$ en la función objetivo que ya es a maximizar:

$$Max \quad z = x + 3y’ -3y»$$

Ahora, la segunda restricción ya es del tipo \leq, pero la primera restricción no, por lo que multiplicamos por $-1$ ambos lados de la desigualdad para invertirla y que ya sea del tipo $\leq$.

Juntando todo tenemos el problema en su forma canónica:

\begin{align*}
Max \quad z &= x + 3y’ – 3y»\\
&s.a\\
-x+y’+y» &\leq 8\\
x+y’+y» &\leq 15 \\
x,y’,y» &\geq 0\\
\end{align*}

Para la forma estándar solo hay que hacer cambios en las restricciones. Para la primera restricción definimos una variable de holgura no negativa $z_1$ tal que $-x+y’+y» +z_1 = 8$. Para la segunda restricción definimos una variable de holgura no negativa $z_2$ tal que $x+y’+y» +z_2 = 15$.

Entonces el problema en su forma estándar sería de la siguiente manera:

\begin{align*}
Max \quad z &= x + 3y’ – 3y»\\
&s.a\\
-x+y’+y» +z_1 &= 8\\
x+y’+y» +z_2 &= 15 \\
x,y’,y»,z_1,z_2 &\geq 0\\
\end{align*}

2.- \begin{align*}
Max \quad z &= -2x_1 + 3x_2 – 2x_3\\
&s.a.\\
&\begin{matrix}4x_1 &-x_2 &- 5x_3 &=& 10\\
2x_1 &+ 3x_2 &+ 2x_3 &\geq &12\end{matrix}\\
& x_1 \leq 0, \quad x_2 \geq 0, x_3 \quad SRS
\end{align*}

Primero vamos a expresar el problema en su forma estándar.

La variable $x_2$ ya es no negativa. La variable $x_1$ es no positiva por lo que definimos $x_1’$ tal que $x_1′ = -x_1$. $x_3$ es una variable sin restricción de signo, por lo que definimos variables no negativas $x_3’$ y $x_3″$ tal que $x_3= x_3′ – x_3″$.

En la función objetivo solo sustituimos los valores de $x_1$ y $x_3$:

$Max \quad z = 2x_1′ + 3x_2 – 2x_3′ + 2x_3″$$

La primera restricción ya es una ecuación. La segunda restricción es del tipo $\geq$, entonces definimos una variable de holgura no negativa $x_4$ tal que $2x_1 + 3x_2 + 2x_3 – x_4 = 12$. Ahora sustituimos $x_1$ y $x_3$ en ambas restricciones.

\begin{matrix}-4x_1′ & – x_2& – 5x_3’& + 5x_3″=& 10\\
-2x_1’& + 3x_2& + 2x_3’& – 2x_3″& – x_4 =& 12\end{matrix}

Y el vector de recursos es no negativo ya que $10,12 \geq 0$

Entonces la forma estándar de este problema sería la siguiente:

\begin{align*}
Max \quad z &= 2x_1′ + 3x_2 – 2x_3′ + 2x_3″\\
&s.a.\\
&\begin{matrix}
-4x_1’& – x_2& – 5x_3’& + 5x_3″& =& 10\\
-2x_1’& + 3x_2& + 2x_3’& – 2x_3″& – x_4 =& 12\\
\end{matrix}\\
&x_1′,x_2,x_3′,x_3″,x_4 \geq 0
\end{align*}

Para la forma canónica, vamos a hacer cambios a las restricciones resultantes de pasar el problema a su forma estándar.

Para la primera restricción que es una ecuación, la vamos a expresar como dos desigualdades:

\begin{align*}
-4x_1’& – x_2& – 5x_3’& + 5x_3″& \leq& 10\\
-4x_1’& – x_2& – 5x_3’& + 5x_3″& \geq& 10\\
\end{align*}

Para la restricción del tipo $\geq$, multiplicamos por $-1$ de ambos lados para invertir la desigualdad y que sea del tipo $\leq$:

\begin{align}
-4x_1’& – x_2& – 5x_3’& + 5x_3″& \leq& 10\\
4x_1’& + x_2& + 5x_3’& – 5x_3″& \leq& -10\\
\end{align}

Ahora, para la segunda restricción del problema estandarizado, retiramos la variable de holgura no negativa:

$$-2x_1′ + 3x_2 + 2x_3′ – 2x_3″ \geq 12$$

Y multiplicamos por $-1$ para invertir la desigualdad:

$$2x_1′ – 3x_2 – 2x_3′ + 2x_3″ \leq -12$$

Entonces la forma canónica de este problema sería la siguiente:

\begin{align*}
Max \quad z &= 2x_1′ + 3x_2 – 2x_3′ + 2x_3″\\
&s.a.\\
&\begin{matrix}
-4x_1’& – x_2& – 5x_3’& + 5x_3″& \leq& 10\\
4x_1’& + x_2& + 5x_3’& – 5x_3″& \leq& -10\\
2x_1’& – 3x_2& – 2x_3’& + 2x_3″& \leq& -12\\
\end{matrix}\\
&x_1′,x_2,x_3′,x_3″ \geq 0
\end{align*}

Entradas relacionadas

Álgebra Lineal II: Unicidad de la forma de Jordan para nilpotentes

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

En la entrada anterior enunciamos el teorema de la forma canónica de Jordan para matrices nilpotentes. Demostramos una parte: la existencia de la forma canónica de Jordan. Para ello, nos enfocamos en el teorema en su versión en términos de transformaciones lineales. En esta entrada nos enfocaremos en demostrar la unicidad de la forma canónica de Jordan. Curiosamente, en este caso será un poco más cómodo trabajar con la forma matricial del teorema. Para recordar lo que queremos probar, volvemos a poner el enunciado del teorema a continuación. Lo que buscamos es ver que los enteros $k_1,\ldots, k_d$ que menciona el teorema son únicos.

Teorema. Sea $A$ una matriz nilpotente en $M_n(F)$. Entonces existen únicos enteros $k_1,\ldots,k_d$ tales que \begin{align*} &k_1+k_2+\ldots+k_d = n,\\ &k_1\leq k_2 \leq \ldots \leq k_d,\end{align*} y para los cuales $A$ es similar a la siguiente matriz de bloques: $$\begin{pmatrix} J_{0,k_1} & 0 & \cdots & 0 \\ 0 & J_{0,k_2} & \cdots & 0 \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & J_{0,k_d}\end{pmatrix}.$$

Nuestra estrategia para mostrar la unicidad será el estudio del rango de las potencias de $A$. Si $A$ es similar una matriz en forma canónica $J$, entonces existe $P$ invertible tal que $A=P^{-1}JP$, de donde se puede mostrar indutivamente que $A^k=P^{-1}J^kP$, mostrando que $A^k$ y $J^k$ son similares. Además, sabemos por teoría anterior que matrices similares tienen el mismo rango. De modo que si $A$ es similar a $J$ entonces todas las potencias de $A$ tienen el mismo rango que todas las potencias de $J$. Con esta idea en mente estudiaremos cómo es el rango de matrices de bloques de Jordan de eigenvalor cero.

Rango de potencias de bloques de Jordan

Claramente el rango del bloque de Jordan $J_{0,n}$ es $n-1$, pues ya está en forma escalonada reducida y tiene $n-1$ vectores distintos de cero. El siguiente resultado generaliza esta observación.

Proposición. Sea $n$ un entero positivo, $F$ un campo y $J_{0,n}$ el bloque de Jordan de eigenvalor $0$ y tamaño $n$ en $M_n(F)$. Para $k=1,\ldots,n$ se tiene que el rango de $J_{0,n}^k$ es igual a $n-k$. Para valores de $k$ más grandes, el rango es igual a cero.

Demostración. Si $e_1,\ldots,e_n$ es la base canónica de $F^n$, tenemos que $J_{0,n}e_i=e_{i-1}$ para $i=2,\ldots,n$ y $J_{0,n}e_1=0$. De manera intuitiva, la multiplicación matricial por $J_{0,n}$ va «desplazando los elementos de la base $e_1,\ldots,e_n$ a la izquierda, hasta sacarlos». De este modo, $J_{0,n}^k$ para $k=1,\ldots,n$ hace lo siguiente:

$$J_{0,n}^k e_i=\begin{cases} 0 & \text{para $k\geq i$}\\ e_{i-k} & \text{para $k\leq i-1$.}\end{cases}$$

Así, $J_{0,n}^k$ manda a la base $e_1,\ldots,e_n$ a los vectores $e_1,\ldots,e_{n-k}$ y a $k$ copias del vector cero. Como los primeros son $n-k$ vectores linealmente independientes, obtenemos que el rango de $J_{0,n}^k$ es $n-k$.

Para valores de $k$ más grandes la potencia se hace la matriz cero, así que su rango es cero.

$\square$

Rango de potencias de matrices de bloques de Jordan

¿Qué sucede si ahora estudiamos el rango de las potencias de una matriz de bloques de Jordan? Consideremos, por ejemplo, la siguiente matriz, en donde $k_1,\ldots,k_d$ son enteros positivos de suma $n$ y con $k_1\leq \ldots \leq k_d$:

$$J=\begin{pmatrix} J_{0,k_1} & 0 & \cdots & 0 \\ 0 & J_{0,k_2} & \cdots & 0 \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & J_{0,k_d}\end{pmatrix}.$$

Por un lado, es sencillo elevar esta matriz a potencias, pues simplemente los bloques se elevan a las potencias correspondientes. En símbolos:

$$J^r=\begin{pmatrix} J_{0,k_1}^r& 0 & \cdots & 0 \\ 0 & J_{0,k_2}^r& \cdots & 0 \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & J_{0,k_d}^r\end{pmatrix}.$$

¿Cuál es el rango de esta potencia? Nos conviene cambiar un poco de notación. En vez de considerar a los $k_i$ por separado, los agruparemos de acuerdo a su valor, que puede ir de $1$ a $n$. Así, para cada $j=1,\ldots,n$ definimos $m_j$ como la cantidad de valores $k_i$ iguales a $j$. Bajo esta notación, la igualdad $k_1+\ldots+k_d=n$ se puede reescribir como $$m_1+2m_2+3m_3+\ldots+nm_n=n.$$

Una primera observación es que el rango de $J$ es simplemente la suma de los rangos de cada una de las $J_{0,k_i}$. Cada una de éstas contribuye con rango $k_i-1$. Así, en términos de las $m_j$ tenemos lo siguiente:

\begin{align*}
\text{rango}(J)&=\sum_{i=1}^d (k_i-1)\\
&=\sum_{j=1}^n (j-1) m_j \\
&=0\cdot m_1 + 1\cdot m_2 + 2 \cdot m_3 + \ldots + (n-1) \cdot m_n.
\end{align*}

De manera similar,

\begin{align*}
\text{rango}(J^r)&=\sum_{i=1}^d \text{rango}(J_{0,k_i}^r)\\
&=\sum_{j=1}^n m_j \text{rango}(J_{0,j}^r).
\end{align*}

El término $\text{rango}(J_{0,j}^r)$ lo podemos calcular con la proposición de la sección anterior, cuidando la restricción entre el tamaño y las potencias que queremos. De aquí y de la restricción original para la las $m_j$ salen todas las siguientes igualdades:

\begin{align*}
n&= 1\cdot m_1 + 2\cdot m_2 + 3 \cdot m_3 + \ldots + n \cdot m_n\\
\text{rango}(J)&=0\cdot m_1 + 1\cdot m_2 + 2 \cdot m_3 + \ldots + (n-1) \cdot m_n\\
\text{rango}(J^2)&= 0 \cdot m_1 + 0 \cdot m_2 + 1 \cdot m_3 + \ldots + (n-2)\cdot m_n\\
\text{rango}(J^3)&= 0 \cdot m_1 + 0 \cdot m_2 + 0 \cdot m_3 + \ldots + (n-3)\cdot m_n\\
&\vdots\\
\text{rango}(J^{n-1})&= 0\cdot m_1 + 0 \cdot m_2 + 0 \cdot m_3 + \ldots + 1 \cdot m_n.
\end{align*}

A partir de aquí el rango de $J^n$ es $0$. Esto nos da una manera de entender con mucha precisión el rango de cualquier potencia de una matriz diagonal por bloques hecha con bloques de Jordan.

Unicidad de la forma canónica de Jordan

Estamos listos para justificar la unicidad de la forma canónica de Jordan. Una matriz diagonal por bloques hecha por bloques de Jordan queda totalmente determinada por los valores de $m_j$ de la sección anterior. Supongamos que $A$ tiene como forma canónica de Jordan tanto a una matriz $J$ con valores $m_j$, como a otra matriz $J’$ con valores $m_j’$.

Como dos matrices similares cumplen que sus potencias son todas del mismo rango, entonces para cualquier $r$ de $1$ a $n-1$ se cumple que $$\text{rango}(J^r)=\text{rango}(A^r)=\text{rango}(J’^r).$$ Así, tanto $(m_1,\ldots,m_n)$ como $({m_1}’,\ldots,{m_n}’)$ son soluciones al siguiente sistema de ecuaciones en variables $x_1,\ldots,x_n$.

\begin{align*}
n&= 1\cdot x_1 + 2\cdot x_2 + 3 \cdot x_3 + \ldots + n \cdot x_n\\
\text{rango}(A)&=0\cdot x_1 + 1\cdot x_2 + 2 \cdot x_3 + \ldots + (n-1) \cdot x_n\\
\text{rango}(A^2)&= 0 \cdot x_1 + 0 \cdot x_2 + 1 \cdot x_3 + \ldots + (n-2)\cdot x_n\\
\text{rango}(A^3)&= 0 \cdot x_1 + 0 \cdot x_2 + 0 \cdot x_3 + \ldots + (n-3)\cdot x_n\\
&\vdots\\
\text{rango}(A^{n-1})&= 0\cdot x_1 + 0 \cdot x_2 + 0 \cdot x_3 + \ldots + 1 \cdot x_n.
\end{align*}

Pero este es un sistema de $n$ ecuaciones en $n$ variables y con matriz asociada de determinante $1$, así que su solución es única. Esto muestra que $(m_1,\ldots,m_n)=({m_1}’,\ldots,{m_n}’)$. Entonces, en $J$ y $J’$ aparecen la misma cantidad de bloques de cada tamaño. Como además los bloques van de tamaño menor a mayor tanto en $J$ como en $J’$, concluimos que $J=J’$.

Como consecuencia de toda esta discusión, obtenemos de hecho lo siguiente.

Corolario. Dos matrices nilpotentes son semejantes si y sólo si tienen la misma forma canónica de Jordan. Distintas formas canónicas de Jordan dan distintas clases de semejanza.

Una receta para encontrar la forma canónica de Jordan de nilpotentes

La demostración anterior no sólo demuestra la unicidad de la forma canónica de Jordan. Además, nos dice exactamente cómo obtenerla. Para ello:

  1. Calculamos todas las potencias de $A$ hasta $n-1$.
  2. Usando reducción gaussiana (o de otro modo), calculamos el rango de cada una de estas potencias.
  3. Resolvemos el sistema de ecuaciones en variables $x_j$ de la sección anterior.
  4. La forma canónica de Jordan de $A$ tiene $x_j$ bloques de tamaño $j$, que debemos colocar en orden creciente de tamaño.

Ejemplo. Consideremos la siguiente matriz en $M_7(\mathbb{R})$: $$C=\begin{pmatrix}-27 & 266 & 1 & -37 & 135 & -125 & 53\\217 & -1563 & 118 & 33 & -1251 & 1020 & 361\\236 & -1784 & 188 & 16 & -1512 & 1234 & 585\\11 & -10 & -25 & 12 & 28 & -29 & -80\\-159 & 1133 & -114 & -98 & 878 & -690 & -232\\197 & -1409 & 88 & -19 & -1151 & 952 & 348\\-230 & 1605 & -179 & -100 & 1316 & -1031 & -440\end{pmatrix}$$

Sus números son muy complicados, sin embargo, nos podemos auxiliar de herramientas computacionales para encontrar sus potencias. Soprendentemente esta es una matriz nilpotente de índice $3$ pues:

$$C^2=\begin{pmatrix}0 & -10209 & -3403 & -6806 & -6806 & 10209 & 0\\0 & 14691 & 4897 & 9794 & 9794 & -14691 & 0\\0 & 2739 & 913 & 1826 & 1826 & -2739 & 0\\0 & 7221 & 2407 & 4814 & 4814 & -7221 & 0\\0 & -14193 & -4731 & -9462 & -9462 & 14193 & 0\\0 & 10956 & 3652 & 7304 & 7304 & -10956 & 0\\0 & -11952 & -3984 & -7968 & -7968 & 11952 & 0\end{pmatrix}$$

y

$$C^3=\begin{pmatrix}0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0\end{pmatrix}.$$

Usando reducción gaussiana, o herramientas computacionales, obtenemos que el rango de $C$ es $4$ y que el rango de $C^2$ es $2$. A partir de $k\geq 3$ obtenemos que $\text{rango}(C^k)=\text{rango}(O_7)=0$. Si queremos encontrar la forma canónica de Jordan de $C$, necesitamos entonces resolver el siguiente sistema de ecuaciones, que nos dirá cuántos bloques $x_j$ de tamaño $j$ hay:

\begin{align*}
7&= x_1+2x_2+3x_3+4x_4+5x_5+6x_6+7x_7\\
4&=x_2 + 2x_3 + 3x_4+4x_5+5x_6+6x_7\\
2&= x_3 + 2x_4+3x_5+4x_6+5x_7 \\
0&= x_4+2x_5+3x_6+4x_7\\
0 &= x_5+2x_6+3x_7\\
0&= x_6+2x_7\\
0&= x_7
\end{align*}

Para resolverlo lo mejor es proceder «de abajo hacia arriba». Las últimas cuatro ecuaciones nos dicen que $x_7=x_6=x_5=x_4=0$. Así, el sistema queda un poco más simple, como:

\begin{align*}
7&= x_1+2x_2+3x_3\\
4&=x_2 + 2x_3\\
2&= x_3.
\end{align*}

De la última igualdad, tenemos $x_3=2$, lo que nos dice que la forma canónica de Jordan tendría dos bloques de tamaño $3$. Sustituyendo en la penúltima igualdad obtenemos que $4=x_2+4$, de donde $x_2=0$. Así, no tendremos ningún bloque de tamaño $2$. Finalmente, sustituyendo ambos valores en la primera igualdad obtenemos que $7=x_1+0+6$. De aquí obtenemos $x_1=1$, así que la forma canónica de Jordan tendrá un bloque de tamaño $1$. En resumen, la forma canónica de Jordan es la matriz $$\begin{pmatrix} J_{0,1} & 0 & 0 \\ 0 & J_{0,3} & 0 \\ 0 & 0 & J_{0,3}\end{pmatrix}.$$ Explícitamente, ésta es la siguiente matriz:

$$\begin{pmatrix} 0& 0 & 0 & 0 & 0 & 0 & 0 \\ 0& 0 & 1 & 0 & 0 & 0 & 0 \\ 0& 0 & 0 & 1 & 0 & 0 & 0 \\ 0& 0 & 0 & 0 & 0 & 0 & 0 \\ 0& 0 & 0 & 0 & 0 & 1 & 0 \\ 0& 0 & 0 & 0 & 0 & 0 & 1 \\ 0& 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}.$$

Para verla un poco más «como de bloques» la podemos reescribir de la siguiente manera:

$$\left(\begin{array}{c|ccc|ccc} 0& 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 0& 0 & 1 & 0 & 0 & 0 & 0 \\ 0& 0 & 0 & 1 & 0 & 0 & 0 \\ 0& 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 0& 0 & 0 & 0 & 0 & 1 & 0 \\ 0& 0 & 0 & 0 & 0 & 0 & 1 \\ 0& 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right).$$

$\triangle$

Más adelante…

Hemos demostrado la existencia y unicidad de la forma canónica de Jordan para matrices nilpotentes. Este es un resultado interesante por sí mismo. Sin embargo, también es un paso intermedio para un resultado más general. En las siguientes entradas hablaremos de una versión más general del teorema de Jordan, para matrices tales que su polinomio característico se descomponga totalmente en el campo en el que estemos trabajando.

Tarea moral

  1. Considera la siguiente matriz: $$M=\begin{pmatrix}11 & 11 & -11 & -11\\-1 & -1 & 1 & 1\\3 & 3 & -3 & -3\\7 & 7 & -7 & -7\end{pmatrix}.$$
    1. Muestra que $M$ es una matriz nilpotente y determina su índice.
    2. ¿Cuál es la forma canónica de Jordan de $M$?
  2. Describe las posibles formas canónicas de Jordan para una matriz nilpotente $A \in M_{5}(F)$ de índice $2$.
  3. Describe las posibles formas canónicas de Jordan para una matriz nilpotente $A \in M_{7}(F)$ de rango $5$.
  4. Encuentra de manera explícita la inversa de la siguiente matriz en $M_n(\mathbb{R})$ y usa esto para dar de manera explícita la solución al sistema de ecuación en las variables $x_i$ que aparece en la entrada: $$\begin{pmatrix} 1 & 2 & 3 & \cdots & n-1 & n \\ 0 & 1 & 2 & \cdots & n-2 & n-1 \\ 0 & 0 & 1 & \cdots & n-3 & n-2 \\ & \vdots & & \ddots & & \vdots\\ 0 & 0 & 0 & \cdots & 1 & 2 \\ 0 & 0 & 0 & \cdots & 0 & 1\end{pmatrix}.$$
  5. Sea $A$ una matriz nilpotente en $M_n(\mathbb{R})$. Muestra que las matrices $A$ y $5A$ son similares entre sí.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

Álgebra Lineal II: Introducción al curso

Por Leonardo Ignacio Martínez Sandoval

4 respuestas

Introducción

En esta serie de entradas continuaremos platicando acerca de álgebra lineal. Son una continuación a las entradas de Álgebra Lineal I que también se encuentran disponibles en el blog. En el transcurso de ellas, cubriremos los temas que establece el temario de la materia Álgebra Lineal II de la Licenciatura en Matemáticas de la UNAM.

Primero comenzaremos dando un pequeño repaso de lo que se ha visto en Álgebra Lineal I y después daremos un pequeño panorama de lo que se cubrirá en este curso.

Algunos recordatorios de Álgebra Lineal I

En el primer curso de álgebra lineal se establecieron muchos fundamentos del área, relacionados con espacios vectoriales, transformaciones lineales, matrices y más. A continuación damos un breve recordatorio de cada unidad temática. Usaremos letras cursivas para mencionar términos que ya deberías conocer. Si algunos de ellos no los recuerdas. Usaremos letras negritas para hacer énfasis en resultados fundamentales del primer curso, que es muy importante que recuerdes qué dicen y cómo se usan. Todo esto lo puedes encontrar en las notas anteriores.

En la primer parte de ese curso, recordamos las definiciones básicas de vector, matriz y transformación lineal, pero únicamente nos enfocamos en un espacio vectorial muy sencillo: $F^n$, que consiste de todos los vectores con $n$ entradas en un campo $F$. Se definieron operaciones de suma y producto escalar en este espacio. También hablamos de cómo multiplicar matrices. Esto fue suficiente para plantear la idea de resolver sistemas de ecuaciones lineales. Primero estudiamos los sistemas de ecuaciones lineales homogéneos, pues de acuerdo al principio de superposición, esto es suficiente. Luego, vimos el algoritmo de reducción gaussiana, que nos permite llevar cualquier matriz a su forma escalonada reducida. Esto resulta fundamental para calcular todo tipo de cosas en álgebra lineal: resolver sistemas de ecuaciones, invertir matrices, encontrar determinantes, encontrar espacios generados, etc.

En la segunda parte introdujimos el concepto de espacio vectorial en general. Hablamos de $F^n$, pero también del espacio de matrices $M_{m,n}(F)$, del espacio de polinomios $F[x]$, de los espacios de polinomios de grado a lo más $n$, $F_n[x]$, y de algunos otros como los de funciones con ciertas propiedades (continuas, diferenciables, limitadas a un intervalo, acotadas, etc.) A partir de las nociones de combinación lineal, independencia lineal y generadores, desarrollamos la teoría de dimensión. Un resultado crucial en dimensión finita es el lema de Steinitz. Tras hablar de un espacio vectorial, comenzamos a hablar de «funciones bonitas» entre ellos. Las primeras que tratamos fueron las transformaciones lineales. Un resultado crucial es que, en dimensión finita y tras elegir una base cada transformación lineal corresponde a una matriz y viceversa. Como bases distintas dan matrices distintas, fue necesario discutir qué sucede al cambiar de base, por lo que se introdujeron matrices de cambio de base. Otro resultado crucial es el teorema rango-nulidad.

La tercera parte fue mucho más geométrica. En ella hablamos de las formas lineales y de las formas bilineales. A partir de las formas lineales construimos a los espacios duales y desarrollamos la teoría de dualidad. Definimos el concepto de hiperplano. Una de las principales aplicaciones de la teoría de dualidad fue mostrar que en dimensión finita todo subespacio es intersección de hiperplanos. En el caso de formas bilineales, nos enfocamos mucho más en aquellas que van a $\mathbb{R}$. A partir de ellas definimos formas cuadráticas. Estudiamos el caso muy especial de espacios euclideanos, que son, a grandes rasgos espacios vectoriales reales con una forma bilineal «bonita». En este tipo de espacios se puede hablar de normas, distancias y ángulos. Los resultados cruciales fueron la desigualdad de Cauchy-Schwarz y la existencia de bases ortonormales. Para encontrarlas, hablamos del proceso de Gram-Schmidt.

Finalmente, vino la unidad 4 en la que se desarrolló de manera formal el concepto de determinante, tanto para vectores, como para matrices y transformaciones lineales. Para ello fue importante hablar de formas $n$-lineales (que en cierta forma generalizan a las bilineales) con propiedades especiales, como ser alternantes. Se vieron muchas propiedades de los determinantes para entenderlos a profundidad de manera teórica y práctica, en particular la expansión de Laplace. Se vio cómo los determinantes pueden ayudar a resolver sistemas de ecuaciones mediante las fórmulas de Cramer. También, con toda la teoría desarrollada hasta aquí pudimos finalmente entender con mucha profundidad los sistemas de ecuaciones lineales mediante el teorema de Rouché-Capelli. Para cerrar el curso, vimos muy por encima las ideas de eigenvalores, eigenvectores y polinomio característico. Esto nos llevó a la idea de diagonalización. Juntando toda la teoría del curso, llegamos a la cereza del pastel: el teorema espectral para matrices simétricas reales.

La idea general del segundo curso

El teorema espectral para matrices simétricas reales es un resultado precioso: bajo ciertas condiciones nos permite «llevar» una transformación (o matriz) a una «forma sencilla». Nos debe de dar la intuición de que toda la teoría que se desarrolló anteriormente la podemos utilizar para demostrar muchos otros resultados lindos de ese estilo. En Álgebra Lineal II haremos precisamente esto.

En la primer parte del curso profundizaremos en la teoría de eigenespacios, que nos permitirán entender mucho mejor cómo son los eigenvectores. Para hacer eso, será importante introducir un nuevo polinomio: el polinomio mínimo. Mostraremos muchas más propiedades de eigenvectores, eigenvalores, polinomios mínimos y característicos. Usaremos estas ideas para profundizar en las nociones de diagonalización y triangulización y enunciaremos teoremas que nos permitirán saber cuándo una matriz (o transformación) se puede llevar mediante un cambio de base a una forma más sencilla. En esta primer parte también demostraremos el bello teorema de Cayley-Hamilton, que afirma que cualquier matriz se anula en su polinomio característico.

Después de esto, en la segunda parte del curso trabajaremos para entender mejor a las formas bilineales que introdujimos en el primer curso. Ya no sólo nos limitaremos a aquellas que caen a los reales, sino que hablaremos también de aquellas que caen al campo $\mathbb{C}$ de los números complejos. Uno podría pensar que el tratamiento es análogo, pero esto dista mucho de la realidad: se requiere pensar en nuevas definiciones que involucren a los conjugados de las entradas de las matrices.

Tras establecer las propiedades principales que nos interesan en espacios vectoriales sobre $\mathbb{R}$ y $\mathbb{C}$, retomaremos la idea de demostrar teoremas de diagonalización. Ahora tendremos el teorema espectral para matrices reales y el teorema espectral para matrices complejas. Además de garantizarnos una diagonalización, estos teoremas nos garantizan que esa diagonalización es de una forma muy especial. Veremos las consecuencias teóricas que esto tiene.

Finalmente, en la última unidad temática, veremos que aunque las matrices no sean diagonalizables, en realidad no todo está perdido. Hablaremos de la forma canónica de Jordan, que es algo así como una versión débil de diagonalizar. Terminaremos el curso aprovechando todo lo visto hasta ahora para ver que cualquier matriz, sin importar sobre qué campo esté, siempre podrá ser llevada a esta forma tras un cambio de base.

Más adelante…

En la siguiente entrada ya comenzaremos con el contenido teórico del curso. Lo primero que haremos es formalizar qué quiere decir «aplicar un polinomio a una transformación lineal» y qué qué quiere decir aplicarlo a una matriz.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Recuerda el algoritmo de reducción gaussiana y úsalo para determinar si la matriz $\begin{pmatrix} 1 & 5 & 0 \\ 0 & 1 & 2 \\ 5 & 3 & -1\end{pmatrix}$ es invertible y, en caso de que sí, encontrar su inversa. Hazlo a mano y comprueba tu respuesta con alguna calculadora de forma escalonada reducida en línea.
  2. Encuentra una base ortogonal para el espacio de polinomios $\mathbb{R}_4[x]$ de grado a lo más $4$ con producto bilineal $\langle p, q \rangle = \sum_{j=0}^4 p(j)q(j)$. Encuentra la forma matricial de la transformación «derivar» en esta base y da su determinante.
  3. Escribe al subespacio de matrices antisimétricas en $M_3(\mathbb{R})$ como intersección de hiperplanos. ¿Qué dimensión tiene?
  4. Encuentra un sistema de $4$ ecuaciones lineales en $5$ variables cuyo espacio de soluciones tenga dimensión $2$. Después, resuélvelo usando los siguientes dos métodos: reducción gaussiana y fórmulas de Cramer.
  5. Explica qué nos garantiza el teorema espectral visto en el curso anterior para las matrices $A=\begin{pmatrix} 1 & 2 & 3 \\ 2 & 0 & 1 \\ 3 & 1 & 4 \end{pmatrix}$ y $B=\begin{pmatrix} 0 & 1 & -1 \\ 1 & 2 & -4 \\ 0 & 0 & 2 \end{pmatrix}$. Encuentra el polinomio característico de cada una de estas matrices. Esboza (sin hacerlo) cómo encontrarías los valores y vectores propios de $A$ y $B$.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»