Nota 18. El principio de inducción matemática.

Por Julio César Soria Ramírez

2 respuestas

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En esta nota usaremos el quinto axioma de Peano para hacer un tipo de prueba muy frecuente en matemáticas cuando se quiere constatar que un subconjunto $A$ de los números naturales es de hecho igual que los números naturales, es decir que $A=\mathbb N$. Nosotros obtuvimos el quinto axioma de Peano de una definición conjuntista de los números naturales (ver la nota 16), que nos dice que si en un conjunto cualquiera de los números naturales: se cumple que el cero está y que para cualquier elemento del conjunto su sucesor también está, entonces, ese conjunto es el de los números naturales. Hay muchísimos ejemplos donde queremos garantizar que cierta propiedad se cumple para todos los números naturales, así que una forma de hacerlo es considerar la colección de todos los números naturales que cumplen dicha propiedad y usar el quinto axioma de Peano para ver que esa colección es de hecho el conjunto de todos los números naturales.

Procedamos a dar una basta serie de ejemplos donde se usa este principio, en todos ellos probaremos que un subconjunto $A$ de naturales es igual a $\mathbb N$, para ello veremos que

$i)\, 0\in A$ (llamada la base de inducción), y que

$ii)$ si $n\in A$, entonces $n^+=n+1\in A$ (llamado paso Inductivo (PI), para ello supondremos que $n\in A$, hipótesis que se conoce comúnmente como la hipótesis de inducción (HI), y probaremos que $n+1\in A$).

Con estas dos condiciones satisfechas podemos asegurar que $A=\mathbb N$ en virtud del quinto Axioma de Peano.

Ejemplos de demostraciones que usan el principio de inducción

En los siguientes ejemplos veremos cómo se usa el principio de inducción o quinto Axioma de Peano, que justificamos a partir de la definición de los números naturales.

Ejemplos

1. La suma de los primeros $n$ naturales está dada por la fórmula:

Para todo $n\in \mathbb N$, $0+1+\dotsc +n=\frac{n(n+1)}{2}.$

Queremos ver que la fórmula anterior se cumple para toda $n$ natural, pero hasta el momento no sabemos que así sea. Podemos entonces considerar el conjunto de naturales para los que sí se cumpla la fórmula, digamos

$A=\set{ n\in \mathbb N \mid 0+1+\dotsc +n=\frac{n(n+1)}{2} }.$

Si logramos probar que en $A$ están todos los naturales, entonces habremos probado que la fórmula se cumple para todos los naturales. Una forma de hacerlo es usando el principio de inducción:

Por demostrar que $A=\mathbb N.$

i) Base de inducción. Por demostrar que $0\in A.$

$0=\frac{0(0+1)}{2}$. Por lo tanto, $0\in A.$

ii) Paso Inductivo. (PI).

Sea $n\in A$, es decir, supondremos que

$0+1+\dotsc +n=\frac{n(n+1)}{2}$.

Ésta es nuestra hipótesis de inducción.

Demostración de que $n^+=n+1\in A$ usando la HI.

Por demostrar que el sucesor de $n$ también está en $A$, es decir por demostrar que $n^+=n+1\in A,$ o de modo equivalente por demostrar que

$0+1+\dotsc +(n+1)=\frac{(n+1)((n+1)+1)}{2}= \frac{(n+1)(n+2)}{2}.$

Usando la hipótesis de inducción sabemos que

$(0+1+\dotsc +n)+(n+1)=\frac{n(n+1)}{2}+(n+1)= \frac{(n)(n+1)+2(n+1)}{2}= \frac{(n+1)(n+2)}{2}.$

Así, $n^+=n+1\in A$ y por el principio de inducción $A=\mathbb N.$

$\square$

Observemos que probar que $0\in A$ fue equivalente a probar que la fórmula que queríamos probar se cumplía para $n=0$. Por otro lado suponer que $n\in A$ fue equivalente a suponer que la fórmula se cumplía para $n$, y demostramos a partir de ello que $n+1\in A$ verificando que la fórmula se cumplía para $n+1$. Así, comúnmente se omite el conjunto $A$ que consiste de todos los naturales que cumplen la propiedad que queremos verificar para todos los naturales y directamente se verifican los siguientes puntos:

$i)$ La propiedad se cumple para $n=0$,

$ii)$ $\forall n\in\mathbb{N}$, si $n$ cumple la propiedad, entonces $n+1$ también la cumple,

y con ello demostramos que todos los números naturales cumplen la propiedad. Veamos más ejemplos.

Para los siguientes ejemplos requerimos la definición de potencia de un natural:

Definición. Potencia en $\mathbb N$

Dado $a\in \mathbb N$ definimos:

$a^0=1,$

para todo $m\in \mathbb N$, $a^{m+1}=a(a^m).$

Observación

Notemos que de acuerdo a la definición anterior, dado $a\in \mathbb N$ se tiene que $a^1=a^{0+1}=a(a^0)=a(1)=a$. Así, $a^1=a$.

2. Para todo $n\in \mathbb N$, $2^0+2^1+\dotsc+2^n=2^{n+1}-1$.

i) Base de inducción. Veamos que el cero cumple la fórmula

$2^0=1=2-1=2^1-1=2^{0+1}-1$, por lo tanto la formula se cumple para $n=0.$

ii) Paso Inductivo. (PI).

Sea $n\in \mathbb N$. Supongamos que el resultado se cumple para $n$ es decir supongamos que:

$2^0+2^1+\dotsc+2^n=2^{n+1}-1.$

Ésta es nuestra hipótesis de inducción.

Demostración de que se cumple para $n+1$ usando la HI.

Veamos ahora que se cumple para $n+1$. Usando la hipótesis de inducción

$(2^0+2^1+\dotsc+2^n)+2^{n+1}=(2^{n+1}-1)+2^{n+1}=2( 2^{n+1} )-1= 2^{(n+1)+1}-1. $

Por lo tanto,

$2^0+2^1+\dotsc+2^n=2^{n+1}-1$, $\forall n\in \mathbb N.$

$\square$

3. Para todo $n\in \mathbb N$ con $n\geq 2$, $1+2n<3^{n}.$ $\quad\quad\quad *$

Observa que, dado que $n\geq 2$ tenemos que $n=m+2$ para alguna $m\in\mathbb{N}$, así que lo que debemos probar es equivalente a demostrar que:

Para todo $n\in\mathbb{N}$, $1+2(m+2)<3^{m+2}.$ $\quad\quad\quad **$

Para ello basta ver que

i) La propiedad ** se cumple para $m=0$,

ii) Para todo $m\in\mathbb{N}$, si $m$ cumple la propiedad **, entonces $m+1$ también cumple la propiedad **.

Pero el que ** se cumpla para $m+1$ significa que $1+2((m+1)+2)<3^{(m+1)+2}$, es decir que $1+2((m+2)+1)<3^{(m+2)+1}$. Así, debemos ver que

i) La propiedad ** se cumple para $m=0$,

ii) Para todo $m\in\mathbb{N}$, si $1+2(m+2)<3^{m+2}$, entonces $1+2((m+2)+1)<3^{(m+2)+1}$,

y como $n=m+2,$ escribiendo todo en términos de $n$ esto es equivalente a probar que

i) Base de inducción. La propiedad * se cumple para $n=2$,

ii) Paso Inductivo. (PI).

Para todo $n\in\mathbb{N}$ con $n\geq 2$, si $1+2n<3^{n}$, entonces $1+2(n+1)<3^{n+1}.$

Así, cuando queramos probar una afirmación para todos los naturales a partir de un valor $k$, bastará con realizar el proceso de inducción de la manera usual sólo que la base de inducción se trabajará con $n=k$ en vez de $n=0$.

Escribamos ahora sí la prueba del ejercicio:

i) Base de inducción. Para $n=2$

$1+2(0+2)<3^{(0+2)}$ es verdadero pues

$1+2(0+2)=5<9=3^2.$

ii) Paso Inductivo. (PI).

Supongamos que el resultado se cumple para $n\geq 2$, es decir supongamos que $1+2n<3^n$.

Ésta es nuestra hipótesis de inducción.

Demostración de que se cumple para $n+1$ usando la HI.

Veamos ahora que se cumple para $n+1$, es decir mostremos que $1+2(n+1)<3^{n+1}.$

Multiplicando la HI por $3$ tenemos que

$3+6n=3(1+2n)<3(3^n)=3^{n+1}.$

Basta ver que $1+2(n+1)<3+6n$. Como $n\geq 2$, entonces $0<4n$ pero:

$0<4n\Longleftrightarrow 2n<6n \Longleftrightarrow 3+2n<3+6n \Longleftrightarrow 1+2(n+1)<3+6n.$

Así, $1+2(n+1)<3+6n$.

Tenemos entonces que $1+2(n+1)<3+6n$ y que $3+6n<3^{n+1}$ por lo que concluimos que:

$1+2(n+1)<3^{n+1},$

que es lo que queríamos probar.

Por lo tanto $1+2(n+1)<3^{n+1}$ $\forall n\in \mathbb N$, $n\geq 2$.

$\square$

A continuación enunciaremos el segundo principio de inducción y su equivalente el principio de buen orden.

Segundo principio de inducción (inducción fuerte o modificada)

Si $A\subseteq \mathbb N$ es tal que:

Para toda $n$, si para todo $m<n$, $m\in A$, implica que $n\in A,$

concluimos que $A=\mathbb N$.

Principio del buen orden PBO

Si $A$ es un subconjunto no vacío de $\mathbb N$, entonces $A$ tiene un elemento menor o igual a los demás. Es decir, si $A\subseteq \mathbb N$, $A\neq \emptyset$, entonces existe $m\in A$, tal que para todo $a\in A$ $m\leq a$.

Nota. El segundo principio de inducción y el principio del buen orden son equivalentes y ambos se pueden probar con el principio de inducción.

Ejemplo del segundo principio de inducción

Considera la sucesión de Fibonacci:

$1,1,2,3,5,8,\dotsc $

dada por

$F_0=F_1=1,$

para todo $n\in \mathbb{N}$, $F_{n+2}=F_n+F_{n+1}.$

Veamos que para todo $n\in\mathbb{N}$, $F_n\leq 2^n$.

Sea $n\in \mathbb N.$ Supongamos que para todo $n\in\mathbb{N}$ con $m<n,$ $F_m\leq 2^m.$

Por demostrar que

$F_n\leq 2^n.$

Si $n=0$ o $n=1$

$F_0=1=2^0$, $F_1=1<2=2^1$.

Podemos suponer entonces que $n>1$, así $n\geq 2.$

Entonces $n=2+k$, con $k\in \mathbb N$ y así

$F_n=F_{2+k}=F_k+F_{k+1}$ que por hipótesis de inducción es menor que $2^k+2^{k+1}$. Concluimos que:

\begin{align*}F_n=F_{2+k}&=F_k+F_{k+1}\leq 2^k+2^{k+1}=1(2^k)+2(2^k) =2^k(1+2)= 2^k(3)\\&< 2^k(4)=2(2(2^k))=2(2^{k+1})=2^{(k+1)+1}=2^{k+2}=2^n.\end{align*}

Por lo tanto para todo $n\in\mathbb{N}$, $F_n\leq 2^n.$

Tarea Moral

1. Prueba que para toda $n\in \mathbb N$

$\sum_{k=0}^{n}k^2=\frac{n(n+1)(2n+1)}{6}.$

2. Prueba que para toda $n\in \mathbb N$, $n<2^n.$

3. Prueba que la suma de los ángulos internos de un polígono de $n$ lados es $(n-2)180$ usando inducción sobre $n$.

4. Considera la secuencia definida de manera recursiva como:

$f_0=1$, $f_{n+1}=f_n+\dotsc+f_0+1.$

Prueba que $f_n=2^n$ para toda $n\in \mathbb N$.

5. Sean $a,b,n,m\in\mathbb{N}$. Demuestra que por inducción que:

i) $a^nb^n=(ab)^n,$

ii) $a^na^m=a^{n+m}.$

Sugerencia: En el inciso $ii$ considera $n$ fija y realiza inducción sobre $m$.

Más Adelante

Ahora que ya estamos más familiarizados con las pruebas por inducción, en la siguiente nota continuaremos usando el quinto Axioma de Peano para realizar demostraciones y probaremos de esta forma las propiedades de la suma y el producto de los números naturales.

Enlaces relacionados.

Página principal del curso.

Nota anterior. Nota 17. El orden en los números naturales.

Nota siguiente. Nota 18b. Demostraciones por inducción de las propiedades de las operaciones de los números naturales.

Nota 17. El orden en los números naturales.

Por Julio César Soria Ramírez

Deja un comentario

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En esta nota continuaremos con el estudio de las propiedades de los números naturales y desarrollaremos formalmente el concepto de cuándo un número natural es más grande que otro, es decir daremos un orden en el conjunto de los números naturales que acabamos de construir, a partir del cual podremos decir cuándo un número natural es más grande que otro.

Procedamos a dar la definición formal del orden en los números naturales.

Definición. Orden en $\mathbb N$ .

Sean $n,m\in \mathbb N$.

Decimos que $n$ es menor que $m$, si existe $x\in \mathbb N$, $x\neq 0$, tal que:

$n+x=m.$

Lo denotaremos por $n<m$ (o por $m>n$).

Decimos que $n$ es menor o igual que $m$, si existe $x\in \mathbb N$, tal que:

$n+x=m.$

Lo denotaremos por $n\leq m$ (o por $m\geq n$).

En ambos casos, le llamaremos al natural $x$ la diferencia de $m$ con $n$ y lo denotaremos por $m-n$.

Observación 1

Si $n\in \mathbb N$ con $n\neq 0$, entonces $n>0$.

Demostración: Si $n\in \mathbb N$ y $n\neq 0$, tenemos que $0+n=n$, con $n\in \mathbb N$, $n\neq 0$, por lo tanto, $0<n$.

Observación 2

Para toda $n\in \mathbb N$, $n<n^+$.

Demostración: Dada $n\in \mathbb N$ , como $n+1=n^+$ (por la observación 3 de la nota previa) con $1\in \mathbb N$ (por el tercer Axioma de Peano), $1\neq 0$, por lo tanto $n<n^+$.

Observación 3

Si $n\in \mathbb N$, con $n\neq 0$, entonces $n\geq 1$.

Demostración: De acuerdo a un ejercicio de la tarea moral de la nota previa, si $n\in \mathbb N$, entonces $n=0$ o $n=m^+$ con $m\in \mathbb N$. De esta forma si $n\in \mathbb N$ y $n\neq 0$, entonces $n=m^+=m+1$ para alguna $m\in \mathbb N$ y se concluye que $n\geq 1$.

Notación

Denotaremos por $\mathbb{N}^+$ al conjunto de números naturales distintos de cero, es decir $\mathbb{N}^+=\{n\in\mathbb{N}\mid n\geq 1\}.$

Notación

En ocasiones simplificaremos la notación del producto de los naturales y escribiremos $nm$ en lugar de $n\cdot m$, para cualesquiera $n,m\in\mathbb{N}.$

Propiedades de Orden en $\mathbb N$

Sean $n,m,l\in \mathbb N$

  1. Si $n<m$ y $m<l$, entonces $n<l$. Esta es la propiedad transitiva.
  2. Si $n<m$, entonces $n+l<m+l$.
  3. Si $n<m$ y $l\neq 0$, entonces $nl<ml$.
  4. Se cumple una y sólo una de las siguientes condiciones:
    $n<m$, $n=m$ o $n>m$
    A este hecho se le conoce como tricotomía.
  5. Si $n+l<m+l$, entonces $n<m$.
  6. Si $nl<ml$, entonces $n<m$.

Demostración

Demostración de 1

Por demostrar que si $n<m$ y $m<l$, entonces $n<l$.

Supongamos que $n<m$ y que $m<l$, entonces existen $x,y \in \mathbb N$, $x\neq 0$, $y\neq 0$ tales que:

$n+x=m$

$m+y=l.$

Así, $n+(x+y)=(n+x)+y=m+y=l$, con $x,y \in \mathbb N$. Además, por las propiedades de la suma de los naturales, como $x\neq 0$ y $y\neq 0$ se tiene que $x+y\neq 0$. Por lo tanto $n<l$.

Demostración de 2

Por demostrar que si $n<m$, entonces $n+l<m+l$.

Supongamos que $n<m$, entonces existe $x\in \mathbb N$, $x\neq 0$ tal que $n+x=m$.

Por las propiedades de la suma $(n+l)+x=(n+x)+l=m+l$ con $x \in \mathbb N$, $x\neq 0$ y por lo tanto $n+l<m+l$.

Demostración de 3

Por demostrar que si $n<m$ y $l\neq 0$, entonces $nl<ml$.

Supongamos que $n<m$ y $l\neq 0$. Existe $x \in \mathbb N$, $x\neq 0$ tal que $n+x=m$.

Por las propiedades de las operaciones de los naturales $nl+xl=(n+x)l=ml$ con $xl \in \mathbb N$. Además, debido a las propiedades del producto de los naturales, como $x\neq 0$ y $l\neq 0$ tenemos que $xl\neq0$. Por lo tanto $nl<ml$.

Demostración de 4

La prueba se realiza por inducción pero en la nota 18b se dejará revisarla a manera de ejercicio debido a que preferimos estudiar primero las pruebas por inducción en casos más concretos con el fin de que se entiendan con mayor claridad.

Demostración de 5

Por demostrar que si $n+l<m+l$, entonces $n<m$.

Supongamos que $n+l<m+l.$

Por la propiedad $4$ sabemos que sólo pasa alguna de estas tres situaciones:

$n<m$, $n=m$ o $n>m.$

Si $n=m$, entonces se tiene que $n+l=m+l$, lo cual contradice nuestra hipótesis.

Si $n>m$, entonces por la propiedad $2$ se tiene que $n+l>m+l$, lo cual contradice la hipótesis.

Así, la única posibilidad es que $n<m$.

Demostración de 6

Por demostrar que si $nl<ml$ entonces $n<m$.

Supongamos que $nl<ml$, por $4$ sabemos que $n<m$, $n=m$ o $n>m$.

Si $n=m$ entonces $nl=ml$, lo cual contradice la hipótesis.

Si $n>m$ y $l=0$ tendríamos que $nl=ml$, por otro lado si $n>m$ y $l>0$, tendríamos que $nl<ml$ por la propiedad $3$. En cualquier caso esto es una contradicción a nuestra hipótesis.

Así, la única posibilidad es que $n<m$.

$\square$

Tarea Moral

1. Sean $n,m\in \mathbb N$. Prueba que si $n\geq 2$ y $m\geq2$, entonces $n+m\leq nm$.

2. Sea $n,m,l,t\in \mathbb N$, prueba o da un contraejemplo para las siguientes afirmaciones:

i) Si $n<l$ y $m<t$, entonces $n+m<l+t$.

ii) Si $n<l$ y $m<t$, entonces $nm<lt$.

iii) Si $n<l$ y $m<t$, entonces $n+m<lt$.

Más adelante

En la siguiente nota explicaremos con detalle cómo aplicar el quinto axioma de Peano para hacer pruebas por inducción. En dichas pruebas se garantiza que un subconjunto de los números naturales es de hecho el de todos los naturales y con ello se justifica que alguna propiedad se cumple para todos los números naturales.

Enlaces relacionados

Página principal del curso.

Nota anterior. Nota 16 Los números naturales.

Nota siguiente. Nota 18. El principio de inducción matemática.

Álgebra Moderna I: Primer Teorema de Isomorfía y Diagrama de Retícula

Por Cecilia del Carmen Villatoro Ramos

3 respuestas

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

La estrella de esta entrada es el primero de los cuatro Teoremas de Isomorfía que veremos. Como el nombre indica, estos teoremas relacionan dos conjuntos a través de una isomorfía, pero no sólo eso, además en los conjuntos que se relacionan aparece un cociente de grupos. El primer teorema de isomorfía nos permite entender cómo están relacionados el dominio, el núcleo y la imagen de un homomorfismo de grupos, de forma similar al teorema de la dimensión en Álgebra lineal, que establece la relación entre el dominio, el núcleo y la imagen de una transformación lineal.

El Primer Teorema de Isomorfía se usa en la prueba del resto de los teoremas de isomorfía, así que al final de esta unidad te quedará muy claro cómo se usa y para qué sirve. Normalmente se usa definiendo un homomorfismo clave para que al aplicarlo en el grupo obtengamos los cocientes necesarios.

Si quieres reforzar algunos temas que usaremos mucho a lo largo de estas entradas, puedes revisar los conceptos de Subgrupo Normal, Cociente de grupos, Isomorfísmos y Núcleo e Imagen de un Homomorfismo. Será de mucha ayuda que los tengas presentes.

Por último, junto con los Teoremas de Isomorfía usaremos una ayuda visual llamada Diagrama de Retícula, es importante para describir las relaciones entre los distintos grupos, subgrupos y subgrupos normales que estaremos manejando.

El Teorema que vamos a tratar

Teorema. (Primer Teorema de Isomorfía)
Sean $G,\bar{G}$ grupos y $\varphi: G\to \bar{G}$ un homomorfismo. Entonces
\begin{align*}
G/\text{Núc }\varphi \cong \text{Im }\varphi.
\end{align*}

Demostración.
Sean $G,\bar{G}$ grupos, $\varphi: G\to \bar{G}$ un homomorfismo y $N =\text{Núc }\varphi$.

En la entrada anterior probamos que $N \unlhd G$, de modo que $G/\text{Núc }\varphi$ tiene estructura de grupo.

Para probar que $G/\text{Núc }\varphi$ y $\text{Im }\varphi$ son isomorfos, tenemos que dar un isomorfismo entre ellos. Primero construiremos una función que vaya de $G/N$ a $\text{Im }\varphi$. Sea
\begin{align*}
\psi : G/N &\to \text{Im }\varphi \\
a N &\to \varphi(a) \quad \forall a \in G.
\end{align*}

Definiremos nuestra función $\psi$ como aquella que manda una clase $aN$ de $G/N$ a $\varphi(a)$, pero no queda claro si al tomar otro representante de la clase, digamos $b$, sucederá que $\varphi(a) = \varphi(b)$. Esto tenemos que probarlo.

Tomemos $a,b\in G$ tales que $aN = bN$. Entonces,

\begin{align*}
aN = bN &\Leftrightarrow a^{-1}b\in N \\
&\Leftrightarrow \varphi(a^{-1}b) = e_{\bar{G}}\\
& \Leftrightarrow \varphi(a^{-1}) \varphi(b) = e_{\bar{G}}\\
& \Leftrightarrow (\varphi(a))^{-1}\varphi(b) = e_{\bar{G}} &\text{Propiedades de homomorfismos}\\
& \Leftrightarrow \varphi(b) = \varphi(a).
\end{align*}
En realidad todas las equivalencias anteriores son producto de las propiedades de homomorfismos que ya vimos. Las implicaciones de ida ($\Rightarrow$) nos dicen que $\psi$ está bien definida, como queríamos probar. Pero las implicaciones de regreso ($\Leftarrow$) nos dicen algo más: nuestra $\psi$ es inyectiva.

Por lo tanto $\psi$ está bien definida y es inyectiva.

Ahora nos falta ver que en efecto $\psi$ es un homomorfismo y es suprayectiva.

Para ver que es un homomorfismo consideremos $a,b\in G$. Luego,
\begin{align*}
\psi(aNbN) &= \psi(abN) &\text{Producto de clases laterales}\\
&= \varphi(ab) &\text{Definición de }\psi\\
&= \varphi(a)\varphi(b)& \varphi \text{ es homomorfismo} \\
&= \psi(aN)\psi(bN) &\text{Definición de }\psi.
\end{align*}
Lo anterior sale de la definición de $\psi$ y de que $\varphi$ es un homomorfismo. Así, $\psi$ es un homomorfismo.

Finalmente, si $c \in \text{Im }\varphi$, $c = \varphi(a)$ con $a\in G$. Entonces, por definición:
\begin{align*}
c = \varphi(a) = \psi(aN) \in \text{Im }\psi.
\end{align*}

Así, $\psi$ es suprayectiva.

Por lo tanto tenemos que $\psi$ es un homomorfismo inyectivo y suprayectivo, es decir, $\psi$ es un isomorfismo. En consecuencia, $G/N \cong \text{Im }\varphi$.

$\blacksquare$

Diagrama de retícula

A partir de las siguientes entradas comenzaremos a usar algo llamado diagrama de retícula, también conocido como diagrama de Hassel. Este diagrama es una manera de representar la relación de ser subgrupo. Se escriben todos o algunos subgrupos de un grupo $G$, y se unen dos subgrupos $H$ y $K$ con una arista si $H$ es subgrupo de $K$, de modo que $H$ quede más abajo que $K$. De esta manera, si se consideran todos los sugrupos de $G$ el grupo $G$ aparece hasta arriba y el subrgupo $\{e\}$ hasta abajo del diagrama.

Veamos un ejemplo: Sean $G$ un grupo abeliano y $H,K$ subgrupos de $G$. Si consideramos $HK$ tal que $HK=KH$, sabemos que es subgrupo de $G$. Además, sabemos que $H\leq HK$ y $K\leq HK$. Por último, consideremos $H\cap K$, que es a su vez un subgrupo de $H$ y $K$.

Todo esto se puede resumir en el siguiente diagrama de retícula:

Diagrama de Retícula.

¿Por qué no unimos $H$ con $G$? Pues porque este diagrama es transitivo, es decir como $H \leq HK \leq G$, está implícito que $H \leq G$. Tampoco unimos un grupo consigo mismo.

Además, si un subgrupo es un subgrupo normal, anotaremos el símbolo $\unlhd$.

Observemos que si $H\unlhd G$, entonces todo elemento en $H$ al ser conjugado con elementos de $G$, sigue siendo un elemento de $H$. En particular, si conjugamos a un elemento de $H$ con un elemento de $HK$ seguimos obteniendo un elemento de $H$. Esto nos dice que $H$ también es normal en $HK$. En el diagrama, la propiedad de ser normal se escribe de la siguiente manera:

Diagrama de Retícula donde se muestra una relación de subgrupo normal.

Este resultado es parte del Segundo Teorema de Isomorfía, que veremos en la siguiente entrada.

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. Sea $G$ un grupo cíclico con $G = \left<a\right>$. Considera el homomorfismo $\varphi: \z \to G$ dado por $\varphi(m) = a^m$ para toda $m\in \z$.
    • Si $a$ es de orden finito con $o(a) = n$ ¿qué concluyes al aplicar el 1er Teorema de Isomorfía? ¿Qué relación existe entre dos grupos cíclicos finitos de orden $n$?
    • Si $a$ es de orden infinito ¿qué concluyes al aplicar en 1er Teorema de Isomorfía? ¿Qué relación existe entre dos grupos cíclicos infinitos?
  2. Puedes revisar los siguientes videos que hablan de homomorfismos:

Más adelante…

Uno de los principales usos del Primer Teorema de Isomorfía es definiendo una $\varphi$ ideal para que el núcleo y la imagen de $\varphi$ sean justo lo que queremos probar. Esto lo veremos en la siguiente entrada, donde lo usamos para probar el Segundo Teorema de Isomorfía.

El diagrama de retícula se volverá fundamental sobre todo cuando veamos el Cuarto Teorema de Isomorfía, porque veremos cómo relacionar muchos subgrupos con grupos cocientes correspondientes.

Entradas relacionadas

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 &= cx\\
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 (vector fila)
  • $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 términos independientes o vector de recursos (vector columna),
  • Entendemos $\bar{0}$ como el vector en $\mathbb{R}^n$ cuyas entradas son todas cero (vector fila o vector columna según sea el caso).

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 se presentarán dos ejemplos de problemas de programación lineal y se explicará como transformarlos a su forma canónica.

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.

Claves para pasar a 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$).

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.

A continuación se presentarán dos ejemplos de problemas de programación lineal y se explicará como transformarlos a su forma estandar.

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*}

Claves para pasar a 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$.

Más adelante…

Las forma canónica que estudiamos en esta entrada nos servirá posteriormente para diferentes fines, entre los cuales están:

  • La interpretación geométrica y de región factible, ya que es la representación más directa de un poliedro en el espacio $R^n$.
  • Pasar del problema Primal al Dual es casi automático cuando el problema está en forma canónica (más adelante recordaremos cual es la forma Dual de un problema).
  • Para análisis de sensibilidad teórico, ya que al manejar desigualdades, es más sencillo realizar análisis sobre qué pasaría si los límites de los recursos ($b$) cambian

Y la forma estándar tiene los siguientes fines, entre algunos otros:

  • Habilitar el uso del Álgebra Lineal, ya que transformas un espacio de desigualdades en un sistema de ecuaciones lineales del tipo $Ax = b$.
  • La forma estándar permite dividir tus variables en dos grupos claros: Las variables básicas que son las que forman una matriz identidad y te dan el valor de la solución actual y las variables no básicas que son las que valen cero.

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

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

Por Alejandro Antonio Estrada Franco

Deja un comentario

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