Archivo de la categoría: Matemáticas

Posts de matemáticas, la ciencia más cercana a las artes.

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

Por Aldo Romero

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 ver cómo podemos llegar a un cierto formato (forma estándar o forma canónica).

Forma canónica de un problema lineal

A continuación introducimos el primer formato que nos facilitará el trabajo.

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

  1. El problema es de maximización.
  2. Las restricciones del problema son todas del tipo $\leq$ (menor o igual).
  3. Las variables de decisión son no negativas.

Así, tenemos entonces que un problema en forma canónica se ve como sigue:

\begin{align*}
Max \quad z &= c_1x_1+\ldots+c_nx_n\\
s.a.&\\
&\left\{\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. \\
x_1\geq 0, x_2\geq 0, \ldots, x_n\geq 0.\end{matrix}\right.
\end{align*}

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

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

en donde:

  • $c=(c_1,\ldots,c_n)\in \mathbb R^n$ es el vector de costos (vector renglón)
  • $x = (x_1,\ldots,x_n)\in \mathbb R^n$ es el vector de variables de decisión (vector columna),
  • $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 constantes que acotan las combinaciones lineales de variables.

Todo problema de programación lineal puede ser expresado en forma canónica; es decir, puede definirse un problema en forma canónica equivalente a él. En efecto:

  • Si el problema es de minimización, puede considerarse en vez de $z$ la función $z’ = -z$ y en el problema equivalente se busca maximizar $z’$.
  • Si una restricción es del tipo $\geq$ puede ser mutiplicada por -1 para obtener una del tipo $\leq$.
  • Una ecuación puede ser substituida por una desigualdad del tipo $\leq$ y otra del tipo $\geq$. Luego, la del tipo $\geq$ puede ser substituida por una del tipo $\leq$ como en el punto anterior.
  • Para una variable $x_i\leq 0$ puede definirse $x_i’ = -x_i$, resultando $x_i’ \geq 0$. Claramente hay una biyección entre elegir el valor de $x_i$ y $x_i’$.
  • Para una $x_i$ no restringida pueden ser definidas dos variables no negativas $x_i’$ y $x_i^\ast$ tales que $x_i’-x_i^\ast = x_i$. Para cualquier $x_i$ dado podemos construir dichas variables, y viceversa, para $x_i’$ y $x_i^\ast$ se puede construir $x_i$.

Ejemplo de pasar un problema a forma canónica

Transformaremos el siguiente modelo a su forma canónica
\begin{align*}
Min \quad z &= x_1-3x_2+7x_3\\
&s.a.\\
3x_1+&x_2+3x_3 &\leq 40\\
x_1+&9x_2-7x_3 &\geq 50\\
5x_1+&3x_2 &= 20\\
&5x_2 + 8x_3 &\leq 80\\
x_1, x_2 &\geq 0, \quad x_3 \quad libre.\\
\end{align*}

Primeramente se definen las variables no negativas $x_3’$ y $x_3^{\ast}$, tales que $x’_3-x_3^{\ast} = x_3$, con objeto de satisfacer el punto (3) de la definición. Para satisfacer el punto (1) se considera la función:
\begin{align*}
z’ &= -z \\&= -x_1+3x_2-7x_3\\&=-x_1+3 x_2-7 x’_3+7x_3^{\ast}
\end{align*}

y se busca maximiza ésta (equivalente a minimizar $z$). Finalmente se realizan cambios en las restricciones para satisfacer el punto (2). La primera y cuarta desigualdad cumplen con la definición por lo que no se modifican (más allá de la sustitución de $x_3$ por $x’_3-x_3^{\ast}$); la segunda desigualdad se multiplica por $-1$ para obtener una del tipo $\leq$: $$ x_1 + 9x_2 – 7x_3 \geq 50 \quad \Leftrightarrow \quad -x_1 – 9x_2 + 7x_3 \leq -50.$$

Substituyendo las nuevas variables se obtiene: $$-x_1-9x_2+7x’_3-7x_3^{\ast}\leq -50.$$

Para la tercera desigualdad se tiene lo siguiente:

\begin{align*}
5x_1+3x_2 &= 20\\
&\Leftrightarrow\\
5x_1 + 3x_2 \leq 20 \quad& y \quad 5x_1 + 3x_2 \geq 20\\
&\Leftrightarrow\\
5x_1 + 3x_2 \leq 20 \quad& y \quad -5x_1 – 3x_2 \leq -20.\\
\end{align*}

Finalmente el problema queda expresado en forma canónica como:

\begin{align*}
Max \quad z’ &= -x_1+3x_2-7x’_3+7x_3^{\ast}\\
&s.a.\\
3x_1+&x_2+3x’_3-3x_3^{\ast} &\leq 40\\
-x_1-&9x_2+7x’_3-7x_3^{\ast} &\leq -50\\
5x_1+&3x_2 &\leq 20\\
-5x_1-&3x_2 &\leq -20\\
&5x_2+8x’_3-8x_3^{\ast} &\leq 80\\
x_1, x_2&, x’_3, x_3^{\ast} \geq 0.\\
\end{align*}

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 restricciones son ecuaciones.
  2. Todas las variables son no negativas.
  3. La función objetivo puede pedirse que se optimice maximizándola, o minimizándola.

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.&\\
&\left\{\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}\right.\\
\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 &= cx\\
&s.a.\\
Ax &= b\\
x &\geq 0\\
\end{align*}

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

Así como cualquier problema de programación lineal puede ser expresado en forma canónica, también cualquier problema de programación lineal puede expresarse en forma estándar. Una restricción del tipo $\leq$ ($\geq$) puede ser transformada en una ecuación sumando (o restando) una variable no negativa que recibe el nombre de variable de holgura.

Ejemplo de pasar un problema a forma estándar

Retomemos el problema ejemplo anterior, antes de expresarlo en forma canónica.

\begin{align*}
Min \quad z &= x_1-3x_2+7x_3\\
&s.a.\\
3x_1+&x_2+3x_3 &\leq 40\\
x_1+&9x_2-7x_3 &\geq 50\\
5x_1+&3x_2 &= 20\\
&5x_2 + 8x_3 &\leq 80\\
x_1, x_2 &\geq 0, \quad x_3 \quad libre.\\
\end{align*}

Vamos a expresarlo ahora en forma estándar. Como lo hicimos anteriormente, hacemos la sustitución $x=x’_3-x_3^\ast$ para que la variable libre se convierta en dos con restricciones de ser no negativas.

Para satisfacer (1) se introducen las variables de holgura, $x_4$, $x_5$ y $x_6$ que pediremos que sean no negativas. A la primera desigualdad le sumamos $x_4$. A la quinta le sumamos $x_6$. Y finalment, a la segunda le restamos $x_5$. Esto transforma las desigualdades en igualdades. De esta manera, el problema queda expresado de la siguiente manera:

\begin{align*}
Min \quad z &= x_1 – 3x_2+7x’_3-7x_3^\ast\\
&s.a.\\
3x_1 + &x_2 + 3x’_3 – 3x_3^\ast + x_4 &= 40\\
x_1 + &9x_2 – 7x’_3 + 7x_3^\ast – x_5 &= 50\\
5x_1 + &3x_2 &= 20\\
&5x_2 + 8x’_3 – 8x_3^\ast + x_6 &= 80\\
x_1,&x_2,x’_3,x_3^\ast,x_4,x_5,x_6 \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 algunos otros conceptos relativos a la teoría de problemas lineales y posibles propiedades que puede tener una asignación de variables. Diremos qué 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 estándar del problema de maximizar $x+y$ sujeto a $x-y\leq 8$ y $y\leq 0$? ¿Y su forma canónica?
  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.\\
    4x_1 – &x_2 – 5x_3 &= 10\\
    2x_1 + &3x_2 + 2x_3 &\geq 12\\
    x_1 &\geq 0, \quad x_2, x_3 \quad irrestrictas\\
    \end{align*}
  3. Revisa nuevamente las entradas anteriores y encuentra las formas canónicas y formas estándar de los problemas que hemos planteado hasta ahora.
  4. La forma estándar (o bien la forma canónica) de un programa lineal «es equivalente» al problema original. Justifica esta afirmación formalmente. Es decir, explica por qué una solución $x_1,\ldots,x_n$ que optimiza el problema original está asociada a una solución de su forma estándar (o canónica) y viceversa.
  5. Imagina que tenemos un sistema de ecuaciones de la forma $Ax=B$ con $A$ matriz en $M_{m,n}(\mathbb{R})$ y $b$ vector en $\mathbb{R}^m$. Queremos encontrar de todas las posibles soluciones al sistema aquella que minimiza la suma de las entradas de $x$. Plantea esto como un problema lineal y transfórmalo a su forma canónica y a su forma estándar.

Entradas relacionadas

Cálculo Diferencial e Integral III: Polinomio característico

Por Alejandro Antonio Estrada Franco

Introducción

En la entrada anterior estudiamos las representaciones matriciales de una transformación lineal. Vimos cómo dadas ciertas bases del espacio dominio y codominio, existe un isomorfismo entre matrices y transformaciones lineales. Así mismo, planteamos la pregunta de cómo encontrar bases para que dicha forma matricial sea sencilla. Vimos que unos conceptos cruciales para entender esta pregunta son los de eigenvalor, eigenvector y eigenespacio. Lo que haremos ahora es introducir una nueva herramienta que nos permitirá encontrar los eigenvalores de una transformación: el polinomio característico.

A partir del polinomio característico daremos un método para encontrar también a los eigenvectores y, en algunos casos especiales, encontrar una representación de una transformación lineal como matriz diagonal. Todo lo que hacemos es una versión resumida de lo que se puede encontrar en un curso más completo de álgebra lineal. Dentro del blog, te recomendamos consultar las siguientes entradas:

Polinomio característico

Pensemos en el problema de hallar los eigenvalores de una transformación lineal $T:\mathbb{R}^n\rightarrow \mathbb{R}^n$. Si $\lambda \in \mathbb{R}$ es uno de estos eigenvalores, queremos poder encontrar vectores $\bar{v}\neq \bar{0}$ tales que $T(\bar{v})=\lambda \bar{v}$. Esto sucede si y sólo si $\lambda \bar{v}-T(\bar{v})=\bar{0}$, lo cual sucede si y sólo si $(\lambda \text{Id}-T)(\bar{v})=\bar{0}$, en donde $\text{Id}:\mathbb{R}^n\to \mathbb{R}^n$ es la transformación identidad de $\mathbb{R}^n$ en $\mathbb{R}^n$. Tenemos de esta manera que $\bar{v}$ es un eigenvector si y sólo si $\bar{v}\in \ker(\lambda\text{Id}-T)$.

Si existe $\bar{v}\neq \bar{0}$ tal que $\bar{v}\in \ker(\lambda \text{Id}-T)$; entonces $\ker(\lambda \text{Id}-T)\neq \{ \bar{0}\}$ por lo cual la transformación $\lambda \text{Id}-T$ no es invertible, pues no es inyectiva. Así, en ninguna base $\text{Mat}_\beta(\lambda \text{Id}-T)$ es invertible, y por tanto su determinante es $0$. Estos pasos son reversibles. Concluimos entonces que $\lambda\in \mathbb{R}$ es un eigenvalor de $T$ si y sólo si en alguna base $\beta$ se cumple que $\det(\text{Mat}_\beta(\lambda \text{Id} – T))=0.$ Esto motiva la siguiente definición.

Definición. Sea $T:\mathbb{R}^n\to \mathbb{R}^n$ una transformación lineal. Llamamos a $\det(\text{Mat}_\beta(\lambda \text{Id} – T))$ al polinomio característico de $T$ en la base $\beta$.

Por la discusión anterior, los escalares que cumplen $\det(\text{Mat}_\beta(\lambda \text{Id} – T))=0$ son los eigenvalores $T$. Para obtener los correspondientes eigenvectores, basta con resolver $\text{Mat}_\beta(T)X=\lambda X$, lo cual es un sistema de ecuaciones en el vector de variables $X$. Las soluciones $X$ nos darán las representaciones matriciales de vectores propios $\bar{v}\in \mathbb{R}^n$ en la base $\beta$.

Por el momento parece ser que tenemos mucha notación, pues debemos considerar la base en la que estamos trabajando. Un poco más adelante veremos que en realidad la base no importa mucho para determinar el polinomio característico. Pero por ahora, veamos un ejemplo concreto de las ideas platicadas hasta ahora.

Ejemplo: Consideremos $T:\mathbb{R}^{3}\rightarrow \mathbb{R}^{3}$ dada por $T(x,y,z)=(2x+z,y+x,-z)$. Calculemos su representación matricial con respecto a la base canónica $\beta$. Para ello, realizamos las siguientes evaluaciones:
\begin{align*}
T(1,0,0)&=(2,1,0)\\
T(0,1,0)&=(0,1,0)\\
T(0,0,1)&=(1,0,-1),
\end{align*}

de donde: $$\text{Mat}_\beta=\begin{pmatrix} 2 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & -1 \end{pmatrix}.$$

Calculando el polinomio característico obtenemos: \[ det\begin{pmatrix} \lambda-2 & 0 & -1 \\ -1 & \lambda-1 & 0 \\ 0 & 0 & \lambda+1 \end{pmatrix}= (\lambda-2)(\lambda-1)(\lambda+1). \]

Las raíces de $(\lambda-2)(\lambda-1)(\lambda+1)$ son $\lambda_{1}=2$, $\lambda_{2}=1$ y $\lambda_{3}=-1$. Pensemos ahora en quiénes son los eigenvectores asociados a cada eigenvalor. Tomemos como ejemplo el eigenvalor $\lambda=2$. Para que $(x,y,z)$ represente a un eigenvector en la base canónica, debe pasar que:

\[ \begin{pmatrix} 2 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & -1 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = 2\begin{pmatrix} x \\ y \\ z \end{pmatrix},\]

lo cual sucede si y sólo si:

\[\begin{pmatrix} 2 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & -1 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} – 2\begin{pmatrix} x \\ y \\ z \end{pmatrix}= \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix};\]

\[\left[ \begin{pmatrix} 2 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & -1 \end{pmatrix} – 2\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}\right] \begin{pmatrix} x \\ y \\ z \end{pmatrix}= \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix};\]

\[\begin{pmatrix} 0 & 0 & 1 \\ 1 & -1& 0 \\ 0 & 0 & -3 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}.\]

De aquí, podemos llegar a la siguiente forma escalonada reducida del sistema de ecuaciones:

\[\begin{pmatrix} 1 & -1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}.\]

En esta forma es sencillo leer las soluciones. Tenemos que $z$ es variable pivote con $z=0$, que $y$ es variable libre, y que $x$ es variable pivote dada por $x=y$. Concluimos entonces que todos los posibles eigenvectores para el eigenvalor $2$ son de la forma $(y,y,0)$, es decir $E_2=\{(y,y,0): y \in \mathbb{R}\}$.

Queda como tarea moral que encuentres los eigenvectores correspondientes a los eigenvalores $1$ y $-1$.

$\triangle$

Matrices similares

En la sección anterior definimos el polinomio de una transformación lineal en términos de la base que elegimos para representarla. En realidad, la base elegida no es muy importante. Demostraremos un poco más abajo que dos representaciones matriciales cualesquiera de una misma transformación lineal tienen el mismo polinomio característico. Para ello, comencemos con la siguiente discusión.

Sea $T:\mathbb{R}^n\rightarrow \mathbb{R}^n$ una transformación lineal y sean $\beta_1=\{ \bar{e}_{1}, \dots , \bar{e}_{n}\}$, $\beta_2=\{ \bar{u}_{1}, \dots , \bar{u}_{n}\}$ dos bases (ordenadas) de $\mathbb{R}^n$. Supongamos que:

\begin{align*}
A&=\text{Mat}_{\beta_1}(T)=[a_{ij}]\\
B&=\text{Mat}_{\beta_2}(T)=[b_{ij}].
\end{align*}

Por cómo se construyen las matrices $A$ y $B$, tenemos que:

\begin{align*}
T(\bar{e}_j)&=\sum_{i=1}^n a_{ij} \bar{e}_i\quad\text{para $j=1,\ldots,n$}\\
T(\bar{u}_k)&=\sum_{j=1}^n b_{jk} \bar{u}_j\quad\text{para $k=1,\ldots,n$}.
\end{align*}

Como $\beta_{1}$ es base, podemos poner a cada un de los $\bar{u}_k$ de $\beta_{2}$ en términos de la base $\beta_{1}$ mediante combinaciones lineales, digamos:

\begin{equation}
\bar{u}_{k}=\sum_{j=1}^{n}c_{jk}\bar{e}_{j}
\label{eq:valor-u}
\end{equation}

en donde los $c_{jk}$ son escalares para $j=1,\ldots, n$ y $k=1,\ldots,n$. La matriz $C$ de $n\times n$, con entradas $c_{jk}$ representa a una transformación lineal invertible, ya que es una transformación que lleva uno a uno los vectores de una base a otra. Afirmamos que $CB=AC$. Para ello, tomaremos una $k$ en $[n]$ y expresaremos $T(\bar{u}_k)$ de dos formas distintas.

Por un lado, usando \eqref{eq:valor-u} y por como es cada $T(\bar{e}_k)$ en la base $\beta_{1}$ tenemos que:

\begin{align*}
T(\bar{u}_k)&=\sum_{j=1}^n c_{jk} T(\bar{e}_j)\\
&=\sum_{j=1}^n c_{jk} \sum_{i=1}^n a_{ij} \bar{e}_i\\
&=\sum_{j=1}^n \sum_{i=1}^n (c_{jk} a_{ij} \bar{e}_i)\\
&=\sum_{i=1}^n \sum_{j=1}^n (c_{jk} a_{ij} \bar{e}_i)\\
&=\sum_{i=1}^n \left(\sum_{j=1}^n a_{ij} c_{jk}\right) \bar{e}_i.
\end{align*}

Por otro lado, usando $\eqref{eq:valor-u}$ y por como es cada $T(\bar{u}_k)$ en la base $\beta_{2}$:

\begin{align*}
T(\bar{u}_k)&=\sum_{j=1}^nb_{jk} \bar{u}_j\\
&=\sum_{j=1}^n b_{jk} \sum_{i=1}^{n}c_{ji}\bar{e}_{j} \\
&=\sum_{j=1}^n \sum_{i=1}^n (b_{jk} c_{ij} \bar{e}_i)\\
&=\sum_{i=1}^n \sum_{j=1}^n (b_{jk} c_{ij} \bar{e}_i)\\
&=\sum_{i=1}^n \left(\sum_{j=1}^n c_{ij} b_{jk} \right) \bar{e}_i.
\end{align*}

Comparemos ambas expresiones para $T(\bar{u}_k)$. La primera es una combinación lineal de los $\bar{e}_i$ y la segunda también. Como $T(\bar{u}_k)$ tiene una única expresión como combinación lineal de los $\bar{e}_i$, entonces los coeficientes de la combinación lineal deben coincidir. Concluimos que para cada $i$ se cumple:

$$\sum_{j=1}^n a_{ij} c_{jk}=\sum_{j=1}^n c_{ij} b_{jk}.$$

Pero esto precisamente nos dice que la entrada $(i,k)$ de la matriz $AC$ es igual a la entrada $(i,k)$ de la matriz $CB$. Con esto concluimos que $AC=CB$, como queríamos.

En resumen, obtuvimos que para dos matrices $A$ y $B$ que representan a la misma transformación lineal, existe una matriz invertible $C$ tal que: $B=C^{-1}AC$. Además $C$ es la matriz con entradas dadas por \eqref{eq:valor-u}.

Introduciremos una definición que nos permitirá condensar en un enunciado corto el resultado que hemos obtenido.

Definición. Dos matrices $A$ y $B$ se llamarán similares (o semejantes), cuando existe otra matriz $C$ invertible tal que $B=C^{-1}AC$.

Sintetizamos nuestro resultado de la siguiente manera.

Proposición. Si dos matrices representan a la misma transformación lineal, entonces estas matrices son similares.

El recíproco de la proposición también se cumple, tal y como lo afirma el siguiente resultado.

Proposición. Sean $A$ y $B$ matrices similares. Entonces $A$ y $B$ representan a una misma transformación lineal $T$, quizás bajo distintas bases.

Demostración: Supongamos que las matrices $A$ y $B$ son similares con $B=C^{-1}AC$, donde las matrices $A$, $B$, $C$ están dadas por entradas $A=[a_{ij}]$ $B=[b_{ij}]$, $C=[c_{jk}]$. Tomemos una base ordenada $\beta=\{\bar{e}_{1}, \dots ,\bar{e}_{n}\}$ de $\mathbb{R}^n$. Consideremos la transformación lineal $T\in \mathcal{L}(\mathbb{R}^n,\mathbb{R}^n)$ dada por $$T(\bar{e}_j)=\sum_{i=1}^n a_{ij} \bar{e}_i.$$

De esta manera $T$ tiene forma matricial $A$ en la base $\beta$.

Construyamos ahora una nueva base ordenada de $\mathbb{R}^n$ dada por vectores $\bar{u}_k$ para $k=1,\ldots,n$ construidos como sigue:

$$\bar{u}_{k}=\sum_{j=1}^{n}c_{jk}\bar{e}_{j}.$$

Como $C$ es invertible, en efecto tenemos que $\beta’:=\{\bar{u}_1,\ldots,\bar{u}_n\}$ también es base de $\mathbb{R}^n$. Además, de acuerdo con las cuentas que hicimos anteriormente, tenemos que precisamente la forma matricial de $T$ en la base $\beta’$ será $B$.

Así, hemos exhibido una transformación $T$ que en una base tiene representación $A$ y en otra tiene representación $B$.

$\square$

Juntando ambos resultados en uno solo, llegamos a lo siguiente.

Teorema. Dos matrices $A$ y $B$ en $M_n(\mathbb{R})$ son similares si y sólo si representan a una misma transformación lineal $T:\mathbb{R}^n\to \mathbb{R}^n$, quizás bajo distintas bases.

El polinomio característico no depende de la base

Si dos matrices son similares, entonces comparten varias propiedades relevantes para el álgebra lineal. Veamos un ejemplo de esto.

Teorema. Sea $T:\mathbb{R}^n\to \mathbb{R}^n$ una transformación lineal en un espacio sobre $\mathbb{R}$ de dimensión finita. Sean $\beta$ y $\beta’$ bases de $\mathbb{R}^n$. Entonces se obtiene lo mismo calculando el polinomio característico de $T$ en la base $\beta$, que en la base $\beta’$.

Demostración. Tomemos $A=\text{Mat}_{\beta}(T)$ y $B=\text{Mat}_{\beta’}(T)$. Como $A$ y $B$ representan a la misma transformación lineal $T$, entonces son similares y por lo tanto existe $C$ invertible con $B=C^{-1}AC$.

Para encontrar el polinomio característico de $T$ en la base $\beta$, necesitamos $\Mat_{\beta}(\lambda\text{Id}-T)$, que justo es $\lambda I -A$. Así mismo, en la base $\beta’$ tenemos $\lambda I – B$. Debemos mostrar que el determinante de estas dos matrices es el mismo. Para ello, procedemos como sigue:

\begin{align*}
\det(\lambda I -B) &= \det (\lambda C^{-1}C – C^{-1} A C)\\
&=\det(C^{-1}(\lambda I – A) C)\\
&=\det(C^{-1})\det(\lambda I – A) \det(C)\\
&=\det(C^{-1})\det(C)\det(\lambda I-A)\\
&=\det(I)\det(\lambda I-A)\\
&=\det(\lambda I-A).
\end{align*}

Aquí estamos usando que el determinante es multiplicativo. Cuando reordenamos expresiones con $\det$, lo hicimos pues los determinantes son reales, cuyo producto es conmutativo.

$\square$

Este teorema nos permite hablar del polinomio característico de una transformación lineal.

Concluimos esta entrada con un resultado que relaciona al polinomio característico de una transformación lineal, con la posibilidad de que exista una base cuya representación matricial sea diagonal.

Teorema. Sea $T:\mathbb{R}^n\to \mathbb{R}^n$ una transformación lineal. Supongamos que el polinomio característico de $T$ tiene raíces distintas $\lambda_{1}, \dots ,\lambda_{n}$. Entonces se cumple lo siguiente:

  1. Si tomamos un eigenvector $\bar{u}_i$ para cada eigenvalor $\lambda_i$, entonces $\bar{u}_{1},\dots ,\bar{u}_{n}$ forman una base $\beta$ para $\mathbb{R}^n$.
  2. Con dicha base $\beta$, se cumple que $\text{Mat}_\beta(T)$ es una matriz diagonal con entradas $\lambda_{1},\dots ,\lambda_{n}$ en su diagonal.
  3. Si $\beta’$ es otra base de $\mathbb{R}^n$ y $A=\text{Mat}_{\beta’}(T)$, entonces $\text{Mat}_\beta(T) = C^{-1}AC$ para una matriz invertible $C$ con entradas dadas por \eqref{eq:valor-u}.

La demostración de este resultado queda como tarea moral.

Más adelante…

En la entrada planteamos entonces un método para encontrar los eigenvectores de una transformación $T$: 1) la transformamos en una matriz $A$, 2) encontramos el polinomio característico mediante $\det(\lambda I – A)$, 3) encontramos las raíces de este polinomio, 4) cada raíz es un eigenvalor y las soluciones al sistema lineal de ecuaciones $(\lambda I – A) X=0$ dan los vectores coordenada de los eigenvectores.

Como platicamos en la entrada, una condición suficiente para que una transformación de $\mathbb{R}^n$ a sí mismo sea diagonalizable es que tenga $n$ eigenvalores distintos. Otro resultado muy bonito de álgebra lineal es que si la transformación tiene alguna forma matricial simétrica, entonces también es diagonalizable. A esto se le conoce como el teorema espectral para matrices simétricas reales. En otros cursos de álgebra lineal se estudia la diagonalizabilidad con mucho detalle. Aquí en el blog puedes consultar el curso de Álgebra Lineal II.

Otra herramienta de álgebra lineal que usaremos en el estudio de la diferenciabilidad y continuidad de las funciones de $\mathbb{R}^{n}$ a $\mathbb{R}^{m}$ son las formas bilineales y las formas cuadráticas. En la siguiente entrada comenzaremos con estos temas.

Tarea moral

  1. Encuentra los eigenvectores faltantes del ejemplo de la sección de polinomio característico.
  2. Considera la transformación lineal $T(x,y,z)=(2x+z,y+x,-z)$ de $\mathbb{R}^3$ en $\mathbb{R}^3$. Nota que es la misma que la del ejemplo de la entrada. Encuentra su representación matricial con respecto a la base $\{(1,1,1),(1,2,3),(0,1,1)\}$ de $\mathbb{R}^3$. Verifica explícitamente que, en efecto, al calcular el polinomio característico con esta base se obtiene lo mismo que con la dada en el ejemplo.
  3. Demuestra que si $A$ y $B$ son dos representaciones matriciales de una misma transformación lineal $T$, entonces $\det(A)=\det(B)$.
  4. Sea $T:\mathbb{R}^{3}\to \mathbb{R}^{3}$ dada por $T(x,y,z)=(x+y+z,x,y)$. Encuentra los eigenvalores correspondientes a la transformación, y responde si es posible representarla con una matriz diagonal. En caso de que sí, encuentra explícitamente la base $\beta$ en la cual $\text{Mat}_{\beta}(T)$ es diagonal.
  5. Demuestra el último teorema de la entrada. Necesitarás usar resultados de la entrada anterior.

Entradas relacionadas

Cálculo Diferencial e Integral III: Representaciones matriciales, eigenvalores y eigenvectores

Por Alejandro Antonio Estrada Franco

Introducción

Como se ha mencionado anteriormente el objetivo de introducir ideas de álgebra lineal en cálculo diferencial es poder establecer una transformación lineal que sea la mejor aproximación lineal en un punto a una función dada. Esto nos ayudará a entender a la función dada en el punto en términos de otra función «más simple». Pero así mismo, las transformaciones lineales pueden ellas mismas pensarse en términos de transformaciones más sencillas. En esta entrada revisaremos esta idea y la conectaremos con la noción de eigenvectores.

Por un lado, recordaremos cómo es que una transformación lineal puede ser representada mediante una matriz una vez que se ha elegido una base del espacio vectorial. Luego, hablaremos de cómo elegir, de entre todas las bases, aquella que nos de una representación matricial lo más sencilla posible.

Representación matricial de las transformaciones lineales

Comencemos esta entrada repasando la importante relación entre transformaciones lineales y matrices. Denotaremos como $\mathcal{L}(\mathbb{R}^n,\mathbb{R}^m)$ al espacio vectorial de transformaciones lineales de $\mathbb{R}^n$ a $\mathbb{R}^m$.

Si tomamos cualquier transformación lineal $T\in \mathcal{L}(\mathbb{R}^n,\mathbb{R}^m)$, entonces los valores de $T$ en cualquier vector de $\mathbb{R}^n$ quedan totalmente determinados por los valores de $T$ en los elementos de alguna base $\beta$ para $\mathbb{R}^n$. Tomemos $\gamma=\{\bar{w}_{1},\dots ,\bar{w}_{m}\}$ una base ordenada para $\mathbb{R}^m$, y $\beta=\{\bar{e}_{1},\dots ,\bar{e}_{n}\}$ una base ordenada para $\mathbb{R}^n$. Para cada $\bar{e}_{k}$ tenemos:

$$\begin{equation} T(\bar{e}_{k})=\sum_{i=1}^{m}t_{ik}\bar{w}_{i} \end{equation},$$

para algunos escalares $t_{1k},\dots ,t_{mk}$ que justo son las componentes de $T(\bar{e}_{k})$ en la base $\gamma$. Con estos escalares, podemos considerar la matriz: \[ \text{Mat}_{\gamma,\beta}(T)= \begin{pmatrix} t_{11} & \dots & t_{1n} \\ \vdots & \ddots & \vdots \\ t_{m1} & \dots & t_{mn} \end{pmatrix} \]

Esta es llamada la representación matricial de la transformación $T$ con respecto a las bases $\beta$ y $\gamma$. Esta matriz ayuda a calcular $T$ en cualquier vector de $\mathbb{R}^n$ como explicamos a continuación.

Para cada $\bar{v}\in \mathbb{R}^n$, podemos expresarlo como combinación lineal de elementos de la base $\beta$ digamos que $\bar{v}=\sum_{i=1}^{n} v_{i}\bar{e}_{i}$. Mediante estos coeficientes, podemos entonces asociar a $\bar{v}$ al siguiente vector columna de $\mathbb{R}^n$ \[ [\bar{v}]_{\beta}=\begin{pmatrix} v_{1} \\ \vdots \\ v_{n} \end{pmatrix}, \]

al que llamamos el vector de coordenadas de $\bar{v}$ con respecto a la base $\beta$.

Realicemos por un lado el siguiente cálculo:

\[ \text{Mat}_{\gamma,\beta}(T)[\bar{v}]_{\beta}=\begin{pmatrix} t_{11} & \dots & t_{1n}\\ \vdots & \ddots & \vdots \\ t_{m1} & \dots & t_{mn} \end{pmatrix} \begin{pmatrix} v_{1} \\ \vdots \\ v_{n} \end{pmatrix}=\begin{pmatrix} \displaystyle\sum_{k=1}^{n}t_{1k}v_{k} \\ \vdots \\ \displaystyle\sum_{k=1}^{n}t_{mk}v_{k}.\end{pmatrix} \]

Por otro lado tenemos lo siguiente:

\begin{align*}
T(\bar{v})&=T \left( \sum_{k=1}^{n}v_{k}\bar{e}_{k} \right)\\&=\sum_{k=1}^{n}v_{k}T(\bar{e}_{k})\\&=\sum_{k=1}^{n}v_{k}T\left( \sum_{i=1}^{m}t_{ik}\bar{w}_{i} \right)\\&=\sum_{i=1}^{m}\left( \sum_{k=1}^{n}v_{k}t_{ik} \right)\bar{w}_{i}.
\end{align*}

Juntando ambos cálculos: \[ [T(\bar{v})]_{\gamma}=\begin{pmatrix} \sum_{k=1}^{n}v_{k}t_{1k} \\ \vdots \\ \sum_{k=1}^{n}v_{k}t_{mk} \end{pmatrix} = \text{Mat}_{\gamma,\beta}(T)[\bar{v}]_{\beta}.\]

En otras palabras, aplicar $T$ a un vector $\bar{v}$ equivale a multiplicar $\text{Mat}_{\gamma,\beta}$ por el vector columna asociado a $\bar{v}$ en la base $\beta$, en el sentido de que tras hacer este producto recuperamos el vector de coordenadas para $T(\bar{v})$ en la base $\gamma$.

Isomorfismo entre transformaciones lineales y matrices

Con las operaciones de suma y multiplicación por escalar que vimos en la entrada de Matrices, se tiene que $M_{m,n}\left( \mathbb{R} \right)$ es un espacio vectorial sobre $\mathbb{R}$. De igual manera $\mathcal{L}(\mathbb{R}^n,\mathbb{R}^m)$ es un espacio vectorial sobre $\mathbb{R}$ con las siguientes operaciones:

  • Si $T$ y $U$ son dos transformaciones, la transformación $T+U$ es aquella que envía a todo vector $\bar{v}\in \mathbb{R}^n$ al vector $T(\bar{v})+U(\bar{v})$.
  • Si $r\in \mathbb{R}$ la transformación $rT$ es la que a todo $\bar{v}\in \mathbb{R}^n$ lo envía al vector $rT(\bar{v})$.

Queda como ejercicio que verifiques que esto dota efectivamente a $\mathcal{L}(\mathbb{R}^n,\mathbb{R}^m)$ de la estructura de espacio vectorial.

A continuación veremos que estos dos espacios vectoriales son, prácticamente, el mismo. Lo que haremos es construir una función $$\Phi :M_{m,n}\left( \mathbb{R} \right) \to\mathcal{L}(\mathbb{R}^n,\mathbb{R}^m)$$ que sea biyectiva y que preserve las operaciones de suma y de producto escalar.

Para ello, tomemos una base $\beta=\{\bar{e}_1,\ldots,\bar{e}_n\}$ de $\mathbb{R}^{n}$ y una base $\gamma=\{\bar{u}_1,\ldots,\bar{u}_m\}$ de $\mathbb{R}^m$. Tomemos una matriz $A\in M_{m,n}(\mathbb{R})$. Explicaremos a continuación cómo construir la transformación $\Phi(A)$, para lo cual diremos qué hace con cada elemento de la base $\beta$. Tomaremos aquella transformación lineal $T_A\in \mathcal{L}(\mathbb{R}^n,\mathbb{R}^m)$ tal que

$$T_A(\bar{e}_j)=\sum_{i=1}^n a_{ij} \bar{u}_i.$$

Tomamos entonces $\Phi(A)=T_A$. Veamos que $\Phi$ tiene todas las propiedades que queremos.

  • $\Phi$ es suprayectiva. Si tenemos una transformación $T:\mathbb{R}^n\to \mathbb{R}^m$, entonces por la construcción anterior se tiene que su forma matricial $A:=\text{Mat}_{\gamma,\beta}(T)$ justo cumple $T_A=T$, de modo que $\Phi(A)=T$.
  • $\Phi$ es inyectiva. Si $A$ y $B$ son matrices distintas, entonces difieren en alguna entrada, digamos $(i,j)$. Pero entonces $T_A$ y $T_B$ difieren ya que $T_A(\bar{e}_j)\neq T_B(\bar{e}_j)$ ya que en las combinaciones lineales creadas hay un coeficiente distinto. Así, $\Phi(A)\neq \Phi(B)$.
  • $\Phi $ es lineal. Para $r\in \mathbb{R}$, $A$ y $B$ matrices con entradas $a_{ij}$ y $b_{ij}$, respectivamente, se cumple que $\Phi \left( rA+B \right)=T_{(rA+B)}$ y entonces se satisface para cada $j=1,\dots ,n$ lo siguiente:
    \begin{align*}
    (rA+B)[\bar{e}_{j}]_{\beta}&=rA[\bar{e}_{j}]_{\beta}+B[\bar{e}_{j}]_{\beta}\\&=r[T_A(\bar{e}_{i})]_{\gamma}+[T_{B}(\bar{e}_{i})]_{\gamma}.
    \end{align*}
    Por tanto para cada $\bar{e}_{i}$ tenemos que $$T_{(rA+B)}(\bar{e}_{i})=rT_{A}(\bar{e}_{i})+T_{B}(\bar{e}_{i})$$ y en consecuencia $$T_{(rA+B)}=rT_{A}+T_{B}.$$ Así $$\Phi (rA+B)=r\Phi (A)+\Phi(B).$$

Todo lo anterior implica que $M_{m,n}\left( \mathbb{R} \right)\simeq \mathcal{L}(\mathbb{R}^n,\mathbb{R}^m)$, es decir, que ambos espacios vectoriales son isomorfos.

En búsqueda de una matriz sencilla

Por lo que hemos platicado hasta ahora, a cada transformación lineal le corresponde una matriz, y viceversa. De hecho, esta asociación respeta operaciones como la suma y el producto por escalar. Esta equivalencia está dada a partir de la función $\Phi$ encontrada en la sección anterior.

Si $\Phi $ es biyectiva, ¿por qué hablamos entonces de encontrar una representación matricial simple para una transformación lineal $T$? Esto parecería no tener sentido, pues a cada transformación le corresponde una y sólo una matriz. Sin embargo, esto es cierto únicamente tras haber fijado las bases $\beta$ y $\gamma$ para $\mathbb{R}^n$ y $\mathbb{R}^m$, respectivamente. Así, dependiendo de la elección de las bases las representaciones matriciales cambian y si tenemos una transformación lineal $T$, es posible que querramos encontrar bases $\beta$ y $\gamma$ en donde la representación matricial sea sencilla.

Nos enfocaremos únicamente en transformaciones lineales que van de un espacio vectorial a sí mismo. Tomemos entonces $T:\mathbb{R}^n\to \mathbb{R}^n$ y una base $\beta$ de $\mathbb{R}^n$. Por simplicidad, escribiremos $\text{Mat}_{\beta, \beta}(T)$ simplemente como $\text{Mat}_{\beta}(T)$. Hay propiedades de $T$ que podemos leer en su matriz $\text{Mat}_{\beta}(T)$ y que no dependen de la base $\beta$ que hayamos elegido. Si con una base $\beta$ especial resulta que $\text{Mat}_{\beta}(T)$ es muy sencilla, entonces podremos leer estas propiedades de $T$ muy fácilmente. Un ejemplo es la siguiente proposición, la cual queda como tarea moral.

Proposición. La transformación lineal $T:\mathbb{R}^n\to\mathbb{R}^n$ es invertible si y sólo si $\text{Mat}_{\beta}(T)$ es invertible.

Si $A=\text{Mat}_{\beta}(T)$ fuera muy muy sencilla, por ejemplo, si fuera una matriz diagonal, entonces podríamos saber la invertibilidad de $T$ sabiendo la invertibilidad de $A$, y la de $A$ sería muy fácil de ver pues por ser matriz diagonal bastaría hacer el producto de las entradas de su diagonal para obtener su determinante y estudiar si es distinto de cero.

Motivados por el ejemplo anterior, estudiemos la siguiente pregunta: ¿toda transformación lineal se puede representar con una matriz diagonal? Si una transformación lineal se puede representar de esta manera, diremos que es diagonalizable.

Eigenvalores, eigenvectores y eigenespacios

En lo que sigue repasaremos el aparato conceptual que nos permitirá dar una respuesta parcial de cuándo una matriz es diagonalizable. Un tratamiento mucho más detallado se puede encontrar aquí en el blog, en el curso de Álgebra Lineal II, comenzando con la entrada Eigenvectores y eigenvalores.

Para nuestro repaso, debemos introducir algunos conceptos y estudiarlos.

Definición. Sea $T:\mathbb{R}^n\rightarrow \mathbb{R}^n$ una transformación lineal. Diremos que un escalar $r \in \mathbb{R}$ es un eigenvalor de $T$ si existe $\bar{v}\in \mathbb{R}^n\setminus\{ \bar{0} \}$ tal que $T(\bar{v})=r\bar{v}$. A dicho vector $\bar{v}$ le llamaremos un eigenvector de $T$ con eigenvalor asociado $r$.

Dado un eigenvector $\bar{v}\in \mathbb{R}^n$, sólo hay un eigenvalor correspondiente a éste. Si $T(\bar{v})=r\bar{v}$ y $T(\bar{v})=t\bar{v}$, entonces $r\bar{v}=t\bar{v}$ de donde $(r-t)\bar{v}=\bar{0}$. Como $\bar{v}\neq \bar{0}$, se sigue que $r=t$.

Por otro lado, para un eigenvalor $r$ puede haber más de un eigenvector con eigenvalor asociado $r$. Consideremos para un eigenvalor $r$ el conjunto $E(r)=\{ \bar{v}\in V |T(\bar{v})=r\bar{v}\}$. Notemos que $\bar{0}\in E(r)$ y también todos los eigenvectores de $r$ están en $E(r)$. Además, $E(r)$ es un subespacio de $\mathbb{R}^n$, pues si $\bar{u},\bar{v} \in E(r)$, y $a\in \mathbb{R}$, tenemos

\begin{align*}
T(a\bar{u}+\bar{v})&=aT(\bar{u})+T(\bar{v})\\
&=a(r\bar{u})+(r\bar{v})\\
&=r(a\bar{u}+\bar{v}),
\end{align*}

lo cual implica que $a\bar{u}+\bar{v} \in E(r)$.

Definición. Para una transformación lineal $T:\mathbb{R}^n\to \mathbb{R}^n$ y un eigenvalor $r$ de $T$ llamaremos a

$$E(r)=\{ \bar{v}\in V |T(\bar{v})=r\bar{v}\}$$

el eigenespacio de $T$ correspondiente a $r$.

Cuando tenemos eigenvectores correspondientes a eigenvalores distintos, cumplen algo especial.

Proposición. Si $\bar{v}_{1}, \dots ,\bar{v}_{l}$ son eigenvectores de una transformación lineal $T:\mathbb{R}^n \rightarrow \mathbb{R}^n$ con eigenvalores correspondientes $r_{1}, \dots ,r_{l}$ distintos entonces $\bar{v}_{1}, \dots ,\bar{v}_{l}$ son linealmente independientes.

Demostración. La ruta para establecer la demostración de este teorema será por inducción sobre $l$. Para un conjunto con sólo un eigenvector el resultado es evidente (¿por qué?). Supongamos cierto para cualquier subconjunto de $l-1$ eigenvectores que pertenecen a eigenespacios distintos. Sean $\bar{v}_{1}, \dots ,\bar{v}_{l}$ eigenvectores en distintos eigenespacios y consideremos $\alpha _{1}, \dots ,\alpha_{l}$ escalares tales que:

\begin{equation}
\label{eq:comb-cero}
\sum_{k=1}^{l}\alpha _{k}\bar{v}_{k}=\bar{0}.
\end{equation}

Aplicamos $T$ a la igualdad anterior. Usando que cada $\bar{v}_{k}$ es eigenvector correspondiente al eigenvalor $r_{k}$ obtenemos:

\begin{align*}
\bar{0}=T(\bar{0})&=T\left(\sum_{k=1}^{l}\alpha _{k}\bar{v}_{k} \right)\\&=\sum_{k=1}^{l}\alpha _{k}T(\bar{v}_{k})\\&=\sum_{k=1}^{l}\alpha _{k}r_{k}\bar{v}_{k}.
\end{align*}

Es decir,

\begin{equation}
\label{eq:aplicarT}
\textbf{0}=\sum_{k=1}^{l}\alpha _{k}r_{k}\bar{v}_{k}
\end{equation}

Multipliquemos \eqref{eq:comb-cero} por $r_{l}$ y restemos el resultado de \eqref{eq:aplicarT} para obtener que

\begin{align*}
\bar{0}=\bar{0}-\bar{0}&=\sum_{k=1}^{l}\alpha _{k}r_{k}\bar{v}_{k}-r_{l}\sum_{k=1}^{l}\alpha _{k}\bar{v}_{k}\\&=\sum_{k=1}^{l-1}\alpha _{k}(r_{k}-r_{l})\bar{v}_{k}.
\end{align*}

Tenemos entonces:

\[ \sum_{k=1}^{l-1}\alpha _{k}(r_{k}-r_{l})\bar{v}_{k}=\bar{0}.\]

Ya que por hipótesis de inducción $\bar{v}_{1}, \dots ,\bar{v}_{l-1}$ son linealmente independientes entonces $\alpha _{k}(r_{k}-r_{l})=0$ para todo $k$, pero los eigenvalores son todos distintos entre sí por lo tanto para todo $k$ de $1$ a $l-1$ se tiene $r_{k}-r_{l}\neq 0$ y así $\alpha _{k}=0$. Finalmente, usando \eqref{eq:comb-cero} obtenemos $\alpha_l=0$. Por lo tanto $\bar{v}_{1}, \dots ,\bar{v}_{l}$ son linealmente independientes.

$\square$

Eigenvectores y transformaciones diagonalizables

Recuerda que dijimos que una transformación lineal $T:\mathbb{R}^n\to \mathbb{R}^n$ es diagonalizable si existe una base $\beta$ de $\mathbb{R}^n$ tal que $\text{Mat}_{\beta}(T)$ es una matriz diagonal. El siguiente resultado conecta las dos ideas que hemos estado explorando: los eigenvectores y la representabilidad sencilla de $T$.

Teorema. Sea $T:\mathbb{R}^{n}\rightarrow \mathbb{R}^{n}$ transformación lineal. Una matriz $T$ es diagonalizable si y sólo si existe una base de $\mathbb{R}^n$ conformada por eigenvectores de $T$.

En realidad la demostración consiste únicamente en entender correctamente cómo se construyen las matrices para una base dada.

Demostración. $\Rightarrow )$ Supongamos que $T$ tiene una representación matricial que es una matriz diagonal $A:=\text{Mat}_{\beta}(T)=\text{diag}(r_{1}, \dots ,r_{n})$ con respecto a la base $\beta=\{\bar{v}_{1}, \dots ,\bar{v}_{n}\}$. Afirmamos que para cada $j=1,\ldots,n$ se tiene $\bar{v}_j$ es eigevector de eigenvalor $r_j$. En efecto, la forma en la que se construyó la matriz $A$ nos dice que

\begin{align*}
T(\bar{e}_j)&=\sum_{i=1}^n a_{ij} \bar{e}_i \\&= a_{jj} \bar{e}_j \\&= r_j \bar{e}_j,
\end{align*}

en donde estamos usando que las entradas $a_{ij}$ de la matriz son cero si $i\neq j$ (por ser diagonal), y son $r_j$ si $i=j$. Por supuesto, como $\bar{e}_j$ forma parte de una base, tampoco es el vector cero. Así, $\bar{e}_j$ es eigenvector de eigenvalor $\bar{e}_j$.

$\Leftarrow )$ Supongamos ahora que $\bar{v}_{1},\dots ,\bar{v}_{n}$ son una base $\beta$ de $\mathbb{R}^n$ conformada por eigenvectores de $T$ con eigenvalores asociados, digamos, $r_{1},\dots ,r_{n}$. Aquí se puede mostrar que $\text{Mat}_\beta(T)$ es diagonal. Queda como tarea moral hacer las cuentas.

$\square$

Hay una situación particular en la que podemos aprovechar el teorema anterior de manera inmediata: cuando la transformación tiene $n$ eigenvalores distintos. Esta consecuencia queda establecida en el siguiente resultado.

Corolario. Toda transformación lineal $T:\mathbb{R}^n\rightarrow \mathbb{R}^n$ tiene a lo más $n$ eigenvalores distintos. Si $T$ tiene exactamente $n$ eigenvalores distintos, entonces los eigenvectores correspondientes forman una base para $\mathbb{R}^n$ y la matriz de $T$ relativa a esa base es una matriz diagonal con los eigenvalores como elementos diagonales.

Demostración. Queda como tarea moral. Como sugerencia, recuerda que mostramos arriba que los eigenvectores de eigenvalores distintos son linealmente independientes.

$\square$

Al parecer los eigenvalores, eigenvectores y eigenespacios de una transformación lineal son cruciales para poder expresarla de manera sencilla. ¿Cómo los encontramos? Esto lo veremos en la siguiente entrada.

Antes de concluir, mencionamos que hay otro teorema crucial sobre diagonalización de matrices. Diremos que una matriz $P\in M_n(\mathbb{R})$ es ortogonal si $P^tP=I$.

Teorema (el teorema espectral). Sea $A\in M_n(\mathbb{R})$ una matriz simétrica. Entonces, existe una matriz ortogonal $P$ tal que $PAP^t$ es una matriz diagonal.

El teorema anterior nos dice no únicamente que la matriz $A$ es diagonalizable, sino que además es diagonalizable mediante un tipo muy especial de matrices. Un estudio y demostración de este teorema queda fuera de los alcances de nuestro curso, pero puedes revisar, por ejemplo la entrada teorema espectral del curso de Álgebra Lineal I que tenemos en el blog.

Más adelante

Lo que haremos en la siguiente entrada es desarrollar un método para conocer los eigenvalores de una matriz. A partir de ellos podremos encontrar sus eigenvectores. Y en ciertos casos especiales, esto nos permitirá mostrar que la transformación es diagonalizable y, de hecho, nos dará la base para la cual la matriz asociada es diagonal.

Tarea moral

  1. Considera la transformación lineal de $\mathbb{R}^{3}$ en $\mathbb{R}^{2}$, dada como $T(x,y,z)=(x+y,z+y)$. Encuentra su representación matricial con las bases canónicas de $\mathbb{R}^3$ y $\mathbb{R}^2$. Luego, encuentra su representación matricial con las bases $\{(1,2,3),(1,0,1),(0,-1,0)\}$ de $\mathbb{R}^3$ y $\{(1,1),(1,-1)\}$ de $\mathbb{R}^2$.
  2. Considera la siguiente matriz: \[ \begin{pmatrix} 1 & 0 & 2 & 3 \\ 0 & -1 & 0 & 2 \\ \end{pmatrix}\] Da una transformación lineal $T:\mathbb{R}^4\to \mathbb{R}^2$ y ciertas bases $\beta$ de $\mathbb{R}^4$ y $\gamma$ de $\mathbb{R}^2$ para las cuales esta matriz sea la representación matricial de $T$ en las bases $\beta$ y $\gamma$.
  3. Fija bases $\beta$, $\gamma$ y $\delta$ para $\mathbb{R}^n$, $\mathbb{R}^m$ y $\mathbb{R}^l$. Considera dos transformaciones lineales $T:\mathbb{R}^n\to \mathbb{R}^m$ y $S:\mathbb{R}^m\to \mathbb{R}^l$. Demuestra que:
    $$\text{Mat}_{\delta, \beta} (S \circ T) = \text{Mat}_{\delta,\gamma}(S) \text{Mat}_{\gamma, \beta} (T).$$
    En otras palabras que la «composición de transformaciones corresponde al producto de sus matrices».
  4. Sea $T:\mathbb{R}^n\to\mathbb{R}^n$ una transformación lineal y $\beta$ una base de $\mathbb{R}^n$. Demuestra que $T$ es biyectiva si y sólo si $\text{Mat}_{\beta}(T)$ es invertible.
  5. Verifica que los vectores $\bar{v}_1,\ldots,\bar{v}_n$ dados en el último teorema en efecto ayudan a dar una representación matricial diagonal para $T$.
  6. La demostración del último corolario es un conjunto de sencillas consecuencias de las definiciones y teoremas desarrollados en esta entrada con respecto a los eigenvalores y eigenvectores. Realiza esta demostración.

Entradas relacionadas

Teoría de los Conjuntos I: Bases para cualquier espacio vectorial

Por Gabriela Hernández Aguilar

Introducción

Lo que haremos en esta última entrada es utilizar el axioma de elección para probar un resultado muy conocido en álgebra lineal: que todo espacio vectorial tiene una base. Para comprender algunos de los términos que utilizaremos en esta sección puedes consultar el curso de Álgebra Lineal I disponible aquí en el blog.

Recordatorio de definiciones

Daremos un breve recordatorio sobre qué quiere decir que un subconjunto arbitrario (finito o no) de un espacio vectorial sea generador, linealmente independiente o base.

Definición. Sea $V$ un espacio vectorial sobre un campo $F$ y $S\subseteq V$. Decimos que $S$ es generador si para cualquier $v\in V$ existe una cantidad finita de vectores $v_1,\ldots,v_n$ en $V$ y de escalares $\alpha_1,\ldots,\alpha_n$ en $F$ tales que $$v=\alpha_1v_1+\ldots+\alpha_nv_n.$$

Definición. Sea $V$ un espacio vectorial sobre un campo $F$ y $L\subseteq V$. Decimos que $L$ es linealmente independiente si para cualquier elección finita de vectores distintos $v_1,\ldots,v_n$ en $L$ y escalares $\alpha_1,\ldots,\alpha_n$, la igualdad $$0=\alpha_1v_1+\ldots+\alpha_nv_n$$ implica que $\alpha_1=\ldots=\alpha_n=0$.

Definición. Sea $V$ un espacio vectorial sobre un campo $F$ y $B\subseteq V$. Decimos que $B$ es una base de $V$ si $B$ es generador y linealmente independiente.

Todo espacio vectorial tiene una base

Demostraremos el siguiente resultado

Teorema. Todo espacio vectorial tiene una base.

Demostración.

Sea $V$ un espacio vectorial sobre un campo $F$. Lo que queremos mostrar es que existe un subconjunto $B$ de $V$ que genera a $B$ y que es linealmente independiente.

Si $V=\set{0}$, entonces $\emptyset$ es una base para $V$. Supongamos ahora que $V$ tiene al menos dos vectores distintos. Sea $\mathcal{F}=\set{L\subseteq V:L\ \textnormal{es un conjunto linealmente independiente}}$. Notemos que $\mathcal{F}$ es no vacío. En efecto, sea $v\in V$ un elemento distinto del vector cero. Luego, $\set{v}$ es linealmente independiente, por lo que $\set{v}\in\mathcal{F}$.

Lo que haremos ahora es probar que $\mathcal{F}$ es una familia de conjuntos de carácter finito. Sea $L$ un conjunto tal que $L\in\mathcal{F}$. Luego, $L$ es linealmente independiente y, por tanto, cualquier subconjunto de $L$ es linealmente independiente, en particular todos los subconjuntos finitos de $L$ son linealmente independientes. En consecuencia, cualquier subconjunto finito de $L$ pertence a $\mathcal{F}$.

Ahora, sea $L$ un conjunto tal que todo subconjunto finito de $L$ pertenece a $\mathcal{F}$. Para cualquier elección de vectores distintos $v_1,\ldots,v_n$ tenemos entonces que $\{v_1,\ldots,v_n\}$ es linealmente independiente. Pero entonces cualquier elección de escalares $\alpha_1,\ldots,\alpha_n$ tales que $$0=\alpha_1v_1+\ldots+\alpha_nv_n$$ cumple que $\alpha_1=\ldots=\alpha_n=0$. Concluimos entonces que $L$ es linealmente independiente. Por tanto, $L\in\mathcal{F}$. Esto demuestra que $\mathcal{F}$ es una familia de conjuntos de carácter finito.

Ahora, por el axioma de elección (en la versión de lema de Tukey-Teichmüller) toda familia no vacía de carácter finito tiene un elemento $\subseteq$-maximal. Sea $B$ un elemento $\subseteq$-maximal en $\mathcal{F}$. Afirmamos que $B$ es una base para $V$. Como $B$ es linealmente independiente, sólo basta probar que $B$ genera a $V$.

Procedamos por contradicción y supongamos que $B$ no genera a $V$. Sea $v\in V$ que no esté en el espacio generado por $B$. Entonces $B\cup\set{v}$ sería un subconjunto de $V$ linealmente independiente que contiene propiamente a $B$ (ver, por ejemplo la última proposición en la entrada Conjuntos generadores e independencia lineal). ¡Esto contradice la maximalidad de $B$ con respecto a la contención en $\mathcal{F}$!

Así, $B$ es linealmente independientes y generador, y por lo tanto es una base de $V$.

$\square$

Tarea moral

Los siguientes resultados presentan algunos refinamientos del resultado mencionado. Por ejemplo, enuncian que «cualquier base parcial se puede completar» a una base, o que «de cualquier conjunto generador se puede extraer una base», etc.

  1. Sea $V$ un espacio vectorial sobre un campo $K$. Muestra que todo conjunto linealmente independiente está contenido en una base de $V$.
  2. Sea $V$ un espacio vectorial. Muestra que si $S$ es un subconjunto generador de $V$, entonces existe $\beta\subseteq S$ tal que $\beta$ es una base para $V$.
  3. Sea $V$ un espacio vectorial con base $\beta$. Si $S$ es un conjunto linealmente independiente, muestra que existe un subconjunto $S_1$ de $\beta$ tal que $S\cup S_1$ es una base para $V$.

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»

Teoría de los Conjuntos I: El lema de Zorn

Por Gabriela Hernández Aguilar

Introducción

En la entrada anterior vimos algunas equivalencias del axioma de elección. En esta nueva entrada veremos algunas otras equivalencias del mismo axioma, pero en términos de órdenes. Estas versiones no son tan evidentes e incluso resultan sorprendentes. En muchas ramas de las matemáticas se apela a las formas equivalentes del axioma de elección que veremos a continuación, por lo que es importante tratarlas.

Familias de caracter finito

Para llegar al lema de Zorn, necesitaremos desarrollar previamente algo de teoría. La siguiente definición jugará un papel clave a lo largo de esta entrada.

Definición. Sea $\mathcal{F}$ una familia de conjuntos. Decimos que $\mathcal{F}$ es de carácter finito si dado un conjunto $A$ se tiene que $A\in\mathcal{F}$ si y sólo si todo subconjunto finito de $A$ está en $\mathcal{F}$.

Veamos los siguientes ejemplos.

Ejemplo.

Sea $\mathcal{F}$ la familia vacía. Luego, por vacuidad, un conjunto $A\in\mathcal{F}$ si y sólo si todo subconjunto finito de $A$ está en $\mathcal{F}$.

$\square$

Ejemplo.

Sea $X$ un conjunto y $\mathcal{F}=\mathcal{P}(X)$ su conjunto potencia. Luego, si $A$ es un conjunto tal que $A\in\mathcal{F}$, entonces $A\subseteq X$ y, por tanto, todo subconjunto finito de $A$ es un subconjunto de $X$, por lo que todo subconjunto finito de $A$ está en $\mathcal{P}(X)$. Ahora, sea $A$ un conjunto tal que cualquiera de sus subconjuntos finitos está en $\mathcal{P}(X)$. Veamos que $A\in\mathcal{P}(X)$, es decir, que $A\subseteq X$. Sea pues $a\in A$ cualquier elemento. Luego, $\set{a}$ es un subconjunto finito de $A$ por lo que $\set{a}\in\mathcal{P}(X)$ y, en consecuencia, $\set{a}\subseteq X$, lo cual es equivalente a que $a\in X$. Por tanto, $A\subseteq X$, lo que muestra que $A\in\mathcal{P}(X)$. De modo que para todo conjunto $X$ su conjunto potencia $\mathcal{P}(X)$ es una familia de conjuntos de carácter finito.

En el último ejemplo tenemos una familia de carácter finito no vacía que tiene al vacío como elemento, pues el conjunto potencia de cualquier conjunto siempre tiene al vacío Esto no sólo ocurre para este caso particular, si tenemos una familia no vacía de carácter finito, entonces el conjunto vacío es un elemento de dicha familia. En efecto, sea $\mathcal{F}$ cualquier familia no vacía de carácter finito. Luego, sea $A\in\mathcal{F}$. Dado que $\emptyset\subseteq A$ y $\emptyset$ es finito, entonces $\emptyset\in\mathcal{F}$.

$\square$

Un poco más adelante necesitaremos del siguiente lema. En un conjunto parcialmente ordenado $(X,\leq)$, una cadena es un subconjunto $Y$ de $X$ tal que la restricción de $\leq$ a $Y$ es un orden total. Dicho de otra forma, en $Y$ cualesquiera dos elementos son $\leq$-comparables.

Lema. Sea $\mathcal{F}$ una familia de carácter finito y sea $\mathcal{B}$ una cadena en $\mathcal{F}$ con respecto a la contención, entonces $\bigcup\mathcal{B}\in\mathcal{F}$.

Demostración.

Dado que $\mathcal{F}$ es de carácter finito basta mostrar que cada subconjunto finito de $\bigcup\mathcal{B}$ está en $\mathcal{F}$. Sea $F$ un subconjunto finito de $\bigcup\mathcal{B}$. Luego, para cada $x\in F$ existe $B_x\in\mathcal{B}$ tal que $x\in B_x$. Dado que $F$ es finito existe un natural $n$ y una función biyectiva $f:n\to F$, por lo que podemos expresar a $F$ como el conjunto $\set{f(m):m\in n}$. Luego, $F\subseteq\cup_{m\in n}B_{f(m)}$. Ahora, como $\mathcal{B}$ es una cadena, entonces existe $m_0\in n$ tal que $B_{f(m)}\subseteq B_{f(m_0)}$ para todo $m\in n$, así que $F\subseteq B_{f(m_0)}$. Finalmente, como $B_{f(m_0)}\in\mathcal{F}$ y $F$ es un subconjunto finito de $B_{f(m_0)}$, entonces $F\in\mathcal{F}$. Esto muestra que $\bigcup\mathcal{B}\in\mathcal{F}$.

$\square$

El lema de Tukey-Teichmüller

Para probar el siguiente teorema debemos asumir que el axioma de elección se cumple. El resultado que enunciamos a continuación John W. Tukey lo enuncia y demuestra en su tesis doctoral en 1939.

Teorema. (Lema de Tukey-Teichmüller). Toda familia no vacía de carácter finito tiene un elemento $\subseteq$-maximal.

Demostración.

La prueba será por contradicción. Supongamos entonces que existe una familia no vacía $\mathcal{F}$ de carácter finito tal que no tiene elementos $\subseteq$-maximales. Luego, para cada $F\in\mathcal{F}$ definamos $\mathcal{A}_F=\set{E\in\mathcal{F}:F\subset E}$, es decir, $\mathcal{A}_F$ es el conjunto de todos los elementos de $\mathcal{F}$ que contienen propiamente a $F$. Dado que $\mathcal{F}$ no tiene elementos $\subseteq$-maximales, para cada $F\in\mathcal{F}$ el conjunto $\mathcal{A}_F$ es no vacío.

Sea $\mathcal{E}=\set{\mathcal{A}_F:F\in\mathcal{F}}$, la cual es una famila no vacía de conjuntos no vacíos. Por el teorema de la entrada anterior sobre algunas de las equivalencias del axioma de elección, existe una función $f:\mathcal{F}\to\mathcal{E}$ de tal forma que $f(F)\in\mathcal{A}_F$ para todo $F\in\mathcal{F}$. Luego, como $f(F)\in\mathcal{A}_F$ para cada $F\in\mathcal{F}$, entonces $F\subset f(F)$ para todo $F\in\mathcal{F}$.

Utilizando esta función $f$ diremos que una subfamilia $\mathcal{G}$ de $\mathcal{F}$ es $f$-inductiva si tiene las siguientes propiedades:

  1. $\emptyset\in\mathcal{G}$.
  2. $A\in\mathcal{G}$ implica $f(A)\in\mathcal{G}$.
  3. Si $\mathcal{B}$ es una $\subseteq$-cadena contenida en $\mathcal{G}$, entonces $\bigcup\mathcal{B}\in\mathcal{G}$.

Dado que $\mathcal{F}$ es una familia de carácter finito no vacía tenemos que $\emptyset\in\mathcal{F}$. Ahora, si $F\in\mathcal{F}$, entonces $f(F)\in\mathcal{F}$ por la elección de la función $f$. Finalmente, si $\mathcal{B}$ es una $\subseteq$-cadena contenida en $\mathcal{F}$, entonces, por el lema previo, $\bigcup\mathcal{B}\in\mathcal{F}$. Así pues, $\mathcal{F}$ es una subfamilia de $\mathcal{F}$ que es $f$-inductiva. Consecuentemente, la familia de conjuntos $\set{\mathcal{G}\subseteq\mathcal{F}:\mathcal{G}\ \textnormal{es $f$-inductiva}}$ es no vacía. Podemos considerar así al conjunto $\mathcal{G}_0:=\bigcap\set{\mathcal{G}\subseteq\mathcal{F}:\mathcal{G}\ \textnormal{es $f$-inductiva}}$.

Veamos que $\mathcal{G}_0$ es $f$-inductiva. Primero, como $\emptyset\in\mathcal{G}$ para toda subfamilia $f$-inductiva de $\mathcal{F}$, entonces $\emptyset\in\mathcal{G}_0$. Ahora, si $A\in\mathcal{G}_0$, entonces $A\in\mathcal{G}$ para toda familia $f$-inductiva de $\mathcal{F}$, por lo que, por definición de subfamilia $f$-inductiva, $f(A)\in\mathcal{G}$ para toda familia $f$-inductiva de $\mathcal{F}$ y, por ende, $f(A)\in\mathcal{G}_0$. Por último, si $\mathcal{B}$ es un $\subseteq$-cadena contenida en $\mathcal{G_0}$, entonces $\mathcal{B}$ es una $\subseteq$-cadena contenida en cada subfamilia $f$-inductiva de $\mathcal{F}$, por lo que $\bigcup\mathcal{B}$ pertenece a cada una de estas subfamilias $f$-inductivas y, consecuentemente, $\bigcup\mathcal{B}\in\mathcal{G}_0$. Esto muestra que $\mathcal{G}_0$ es $f$-inductiva.

Por el párrafo anterior tenemos que toda subfamilia $f$-inductiva de $\mathcal{F}$ contiene a $\mathcal{G}_0$. Lo que haremos ahora es probar que $\mathcal{G}_0$ es una $\subseteq$-cadena, es decir, que para cualesquiera $A$ y $B$ elementos de $\mathcal{G}_0$ se tiene que $A\subseteq B$ o $B\subseteq A$.

Definamos el conjunto $$\mathcal{H}=\{A\in\mathcal{G}_0:\textnormal{si $B\in\mathcal{G}_0$ y $B\subset A$, entonces $f(B)\subseteq A$}\}.$$

Notemos que $\mathcal{H}$ es no vacío. En efecto, si consideramos $A=\emptyset$, entonces $A\in\mathcal{H}$, ya que si $B\in\mathcal{G}_0$ es un subconjunto propio de $A$, entonces, por vacuidad, $f(B)\subseteq A$, pues $\emptyset$ no tiene subconjuntos propios.

Veamos ahora que para cualquier $A\in\mathcal{H}$ y cualquier $C\in\mathcal{G}_0$, se cumple que $C\subseteq A$ o $f(A)\subseteq C$. Sea pues $A\in\mathcal{H}$ cualquier elemento. Definamos $\mathcal{G}_A=\set{C\in\mathcal{G}_0:C\subseteq A\ o\ f(A)\subseteq C}$. Notemos que si $C\in\mathcal{G}_A$, entonces $C\subseteq A$ o bien, $f(A)\subseteq C$ por lo que $A\subseteq C$, ya que $A\subset f(A)$. Así que para probar que $A\subseteq C$ o $C\subseteq A$ para cualquier $C\in\mathcal{G}_0$, basta probar que $\mathcal{G}_A=\mathcal{G}_0$.

Lo que haremos será mostrar que $\mathcal{G}_A$ es una subfamilia de $\mathcal{F}$ que es $f$-inductiva. Primero, como $\emptyset\in\mathcal{G}_0$ y $\emptyset\subseteq A$, entonces $\emptyset\in\mathcal{G}_A$. Luego, si $C\in\mathcal{G}_A$, entonces o bien $C\subset A$ o $C=A$ o $f(A)\subseteq C$. Si $C\subset A$, entonces $f(C)\subseteq A$ pues $A\in\mathcal{H}$. Si $C=A$, entonces $f(A)=f(C)$ y por tanto $A\subseteq f(A)=f(C)$. Si $f(A)\subseteq C$, entonces $A\subseteq C$ y, por ende, $A\subseteq f(C)$, ya que $C\subset f(C)$. En cualquier posibilidad tenemos que $f(C)\subseteq A$ o $f(A)\subseteq f(C)$, lo que implica que $f(C)\in\mathcal{G}_A$. Sea ahora $\mathcal{B}$ una cadena en $\mathcal{G}_A$. Si $C\subseteq A$ para todo $C\in\mathcal{B}$, entonces $\bigcup\mathcal{B}\subseteq A$. Si existe $C\in\mathcal{B}$ tal que $f(A)\subseteq C$, entonces $f(A)\subseteq\bigcup\mathcal{B}$, pues $C\subseteq\bigcup\mathcal{B}$. Como estas son las únicas posibilidades, concluimos que o bien $\bigcup\mathcal{B}\subseteq A$ o $f(A)\subseteq\bigcup\mathcal{B}$ y, por tanto, $\bigcup\mathcal{B}\in\mathcal{G}_A$. Estas propiedades muestran que $\mathcal{G}_A$ es una subfamilia de $\mathcal{F}$ que es $f$-inductiva.

En consecuencia, $\mathcal{G}_0\subseteq\mathcal{G}_A$. Luego, por definición tenemos que $\mathcal{G}_A\subseteq\mathcal{G}_0$ y, por consiguiente, tenemos la igualdad $\mathcal{G}_0=\mathcal{G}_A$.

Así pues, para todo $A\in\mathcal{H}$ y cualquier $C\in\mathcal{G}_0$, o bien $C\subseteq A$ o $A\subseteq C$.

Para terminar de probar que $\mathcal{G}_0$ es una cadena basta probar que $\mathcal{H}$ es una subfamilia $f$-inductiva de $\mathcal{F}$. Primero, ya vimos que $\emptyset\in\mathcal{H}$. Ahora, sea $A\in\mathcal{H}$ y sea $B\in\mathcal{G}_0$ cualquier elemento tal que $B\subset f(A)$. Dado que $B\in\mathcal{G}_A=\mathcal{G}_0$, entonces $B\subseteq A$ o $f(A)\subseteq B$, pero hemos supuesto que $B\subset f(A)$, por lo que es imposible que $f(A)\subseteq B$ y, en consecuencia, $B\subseteq A$. Luego, si $B\subset A$, entonces $f(B)\subseteq A$ pues $A\in\mathcal{H}$ y, por tanto, $f(B)\subseteq f(A)$. Si $B=A$, entonces $f(B)=f(A)\subseteq f(A)$. Por lo tanto, $f(B)\subseteq f(A)$. Esto muestra que $f(A)\in\mathcal{H}$. Para finalizar, sea $\mathcal{B}$ una $\subseteq$-cadena de $\mathcal{H}$. Sea $B\in\mathcal{G}_0$ cualquier elemento tal que $B\subset\bigcup\mathcal{B}$. Si existe $C\in\mathcal{B}$ tal que $B\subseteq C$, entonces $B\subset C$ o $B=C$, en el primer caso tendríamos que $f(B)\subseteq C$, porque $C\in\mathcal{H}$, y por ende que $f(B)\subseteq\bigcup\mathcal{B}$; supongamos ahora que $B=C$, entonces, $B\in\mathcal{H}$ (pues $C$ es un elemento de $\mathcal{H}$) y $\bigcup\mathcal{B}\in\mathcal{G}_0=\mathcal{G}_B$. Así, $\bigcup\mathcal{B}\subseteq B$ o $f(B)\subseteq\bigcup\mathcal{B}$, pero $\bigcup\mathcal{B}\subseteq B$ es imposible pues asumimos que $B\subset\bigcup\mathcal{B}$, por lo que debe ocurrir necesariamente que $f(B)\subseteq\bigcup\mathcal{B}$. De modo que si existe $C\in\mathcal{B}$ tal que $B\subseteq C$, entonces $f(B)\subseteq\bigcup\mathcal{B}$. Supongamos ahora que $B\nsubseteq C$ para todo $C\in\mathcal{B}$. Ahora, como $B\in\mathcal{G}_0$ y $\mathcal{G}_0=\mathcal{G}_C$ para todo $C\in\mathcal{B}\subseteq\mathcal{H}$, entonces $B\in\mathcal{G}_C$ para todo $C\in\mathcal{B}$. Consecuentemente, $B\subseteq C$ o $f(C)\subseteq B$ para cada $C\in\mathcal{B}$, pero asumimos ahora que $B\nsubseteq C$ para todo $C\in\mathcal{B}$, por lo que $f(C)\subseteq B$ para todo $C\in\mathcal{B}$ y, por consiguiente, $C\subseteq B$ para todo $C\in\mathcal{B}$, lo cual implica que $\bigcup\mathcal{B}\subseteq B$ pero esto contradice el hecho de que $B\subset\bigcup\mathcal{B}$. De modo que, necesariamente, debe existir $C\in\mathcal{B}$ tal que $B\subseteq C$, lo cual vimos implica que $f(B)\subseteq\bigcup\mathcal{B}$. Esto demuestra que $\bigcup\mathcal{B}\in\mathcal{H}$. Por lo tanto, $\mathcal{H}$ es una subfamilia de $\mathcal{F}$ que es $f$-inductiva.

Como consecuencia del párrafo anterior tenemos que $\mathcal{G}_0\subseteq\mathcal{H}$, pero por definición sabemos que $\mathcal{H}\subseteq\mathcal{G_0}$, lo cual implica $\mathcal{G}_0=\mathcal{H}$.

De esta serie de argumentos tenemos que si $A,B\in\mathcal{G}_0$, entonces $A\in\mathcal{H}$ y $B\in\mathcal{G}_A$, por lo que $B\subseteq A$ o bien $f(A)\subseteq B$, es decir, $B\subseteq A$ o $A\subseteq B$. Por lo tanto, cualesquiera dos elementos de $\mathcal{G}_0$ son $\subseteq$-comparables y, en consecuencia, $\mathcal{G}_0$ es una $\subseteq$-cadena.

Consideremos ahora $M=\bigcup\mathcal{G_0}$, el cual es un elemento de $\mathcal{G_0}$ por ser $\mathcal{G}_0$ $f$-inductiva y una subcadena de sí misma. Ahora para todo $A\in\mathcal{G}_0$ se tiene que $A\subseteq\bigcup\mathcal{G}_0=M$. Por otro lado, como $M\in\mathcal{G}_0$, entonces $f(M)\in\mathcal{G}_0$ y, por tanto, $f(M)\subseteq M$; sin embargo, como $M\in\mathcal{F}$, entonces $M\subset f(M)$, pero esto es una contradicción.

Dado que esta contradicción viene de suponer que $\mathcal{F}$ no tiene un elemento $\subseteq$-maximal, concluimos que $\mathcal{F}$ sí tiene un elemento $\subseteq$-maximal.

$\square$

El principio maximal de Hausdorff

Pasemos ahora a un resultado muy cercano al lema de Zorn, demostrado por Felix Hausdorff en 1914. Se obtiene rápidamente al aplicar el lema de Tukey-Teichmüller.

Teorema. (Principio Maximal de Hausdorff). Cualquier conjunto no vacío y parcialmente ordenado tiene una cadena $\subseteq$-maximal.

Demostración.

Sea $A\neq \emptyset$ y $\leq$ un orden parcial para $A$. Sea $\mathcal{C}=\set{B\subseteq A:B\ \textnormal{es una cadena}}$. Recordemos que $B\subseteq A$ es una cadena en $A$ si cualesquiera dos elementos en $B$ son comparables con el orden de $A$.

Lo que queremos probar es que existe $C\in\mathcal{C}$ tal que ningún otro elemento de $\mathcal{C}$ contiene propiamente a $C$. Para ello probaremos que $\mathcal{C}$ es una familia no vacía de carácter finito y aplicaremos el lema de Tukey-Teichmüller para concluir que $\mathcal{C}$ tiene un elemento $\subseteq$-maximal.

Supongamos que $B\in\mathcal{C}$ es cualquier elemento. Luego, sea $B’\subseteq B$ un conjunto finito. Veamos que $B’$ es una cadena en $A$, es decir, que cualesquiera dos elementos de $B’$ son comparables con el orden de $A$. Si $B’=\emptyset$, por vacuidad $B’$ es una cadena en $A$. Asumamos ahora que $B’\not=\emptyset$ y sean $a,b\in B’$ cualesquiera elementos. Luego, como $a,b\in B’$, entonces $a,b\in B$ y como $B$ es una cadena en $A$, entonces $a$ y $b$ son comparables con el orden de $A$, y esto muestra que $B’$ es también una cadena en $A$, por lo que $B’\in\mathcal{C}$.

Supongamos ahora que $B$ es un conjunto tal que cualquiera de sus subconjuntos finitos está en $\mathcal{C}$. Ciertamente $B\subseteq A$, pues si $a\in B$, entonces $\set{a}\in\mathcal{C}$, es decir, $\set{a}$ es una cadena en $A$, por lo que $a\in A$. Ahora, si $a,b\in B$, entonces $\set{a,b}\in\mathcal{C}$ y, por tanto, $\set{a,b}$ es una cadena en $A$, es decir, $a$ y $b$ son comparables con el orden de $A$. Por tanto, $B$ es una cadena en $A$, ya que cualesquiera dos de sus elementos son comparables con el orden de $A$.

Esta serie de argumentos muestra que $\mathcal{C}$ es una familia de conjuntos de carácter finito. Por el lema de Tukey-Teichmüller, $\mathcal{C}$ tiene un elemento $\subseteq$-maximal, es decir, existe una cadena en $A$ $\subseteq$-maximal.

$\square$

El lema de Zorn

Finalmente enunciaremos y demostraremos una de las versiones más usadas del axioma de elección: el conocido lema de Zorn. Este resultado fue demostrado por Max Zorn en 1935 (y de manera independiente por Kazimierz Kuratowski en 1922). Para nuestra demostración usaremos el principio maximal de Hausdorff.

Teorema. (Lema de Kuratowski-Zorn). Cualquier conjunto parcialmente ordenado y no vacío en el cual toda cadena tiene una cota superior tiene un elemento maximal.

Demostración.

Sea $(A,\leq)$ un conjunto parcialmente ordenado no vacío en el que toda cadena tiene una cota superior. Por el principio maximal de Hausdorff el conjunto $A$ tiene una cadena $\subseteq$-maximal. Sea pues $C\subseteq A$ una cadena $\subseteq$-maximal de $A$. Luego, por hipótesis, existe $a\in A$ cota superior de $C$, es decir, $c\leq a$ para todo $c\in C$. Ahora, notemos que $a$ es maximal con respecto a $\leq$, ya que si existiera $x\in A$ tal que $a<x$, entonces $x\not=a$ y $x\notin C$, por lo que $C\cup\set{x}$ sería una cadena en $A$ que contiene propiamente a $C$ y esto contradice la maximalidad de $C$ con respecto a la contención en el conjunto de cadenas de $A$. Por lo tanto, $a$ es un elemento maximal en $A$.

$\square$

Tarea moral

  1. Prueba que la intersección de un sistema de familias $f$-inductivas es una familia $f$-inductiva.
  2. Sea $X$ un conjunto. Prueba que si $X$ puede ser bien ordenado, entonces $\mathcal{P}(X)$ puede ser linealmente ordenado. (Sugerencia: dados $A,B\in\mathcal{P}(X)$ considera al mínimo de $A\Delta B$).
  3. Demuestra que para cualesquiera dos conjuntos $A$ y $B$, o bien existe una función inyectiva $f:A\to B$, o bien existe una función inyectiva $g:B\to A$.
  4. Demuestra que la colección $\mathcal{F}$ de subconjuntos finitos de $\mathbb{N}$ no es de caracter finito.

Más adelante…

En la siguiente entrada comenzaremos probando un resultado algo antintuitivo: que cualquier conjunto puede ser bien ordenado. Por ejemplo, a $\mathbb{R}$ se le podrá dar un orden de manera que cualquier subconjunto no vacío tenga mínimo. ¡Esto es muy difícil de imaginar! Sobre todo si pensamos en el orden usual de $\mathbb{R}$. El resultado que probaremos será existencial (y no constructivo), así que aunque tengamos la garantía de que dicho buen orden existe, no podremos saber muy bien cuál es.

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»