Archivo de la etiqueta: algoritmo de la división

Álgebra Superior II: El algoritmo de Euclides

Por Leonardo Ignacio Martínez Sandoval

Introducción

En entradas anteriores estudiamos los conceptos de máximo común divisor y de mínimo común múltiplo. Ahora nos enfocaremos en un aspecto un poco más práctico sobre el máximo común divisor que dejamos pendiente: ¿cómo lo calculamos? Para ello hablaremos de un procedimiento conocido como el algoritmo de Euclides, el cual afirma que afirma que podemos aplicar iteradas veces el algoritmo de la división en ciertos números específicos, comenzando con dos enteros $a$ y $b$ para encontrar su máximo común divisor de dos enteros positivos $a$ y $b$.

Lo primero que haremos es explicar el procedimiento mediante el cual podemos encontrar el máximo común divisor de dos números aplicando repetidamente el algoritmo de la división. En la siguiente sección daremos la demostración de por qué funciona este procedimiento. Hacia el final de la entrada también veremos que este mismo procedimiento nos permite también escribir al máximo común divisor de dos enteros $a$ y $b$ como combinación lineal de ellos, es decir, de la forma $ra+sb$ con $r$ y $s$ números enteros.

El procedimiento del algoritmo de Euclides

Sean $a, b$ cualesquiera enteros positivos, con $a \neq b$ y $a > b.$ Por el algoritmo de la división, sabemos que siempre existen $q, r \in \mathbb{Z}$ tales que podemos escribir $$a = bq + r, \enspace \text{con} \quad \quad 0 \leq r < b. $$

Luego, como $b$ y $r$ son enteros, también existen $q_1$ y $r_1$ tales que $$b = rq_1 + r_1,\enspace \text{con} \quad \quad 0 \leq r_1 < r.$$

Y como $r$ y $r_1$ son enteros, existen $q_2$ y $r_2 \in \mathbb{Z}^+$ tales que $$r = r_1q_2 + r_2,\enspace \text{con} \quad \quad 0 \leq r_2 < r_1.$$

Se puede continuar así sucesivamente. Pero este procedimiento debe de terminar, pues tenemos $b>r>r_1>r_2>\ldots \geq 0$, de modo que debe existir una $i$ tal que $r_i=0$. De esta forma, en el penúltimo paso tendremos que existen $q_{i-1}$ y $r_{i-1}$ enteros tales que $$r_{i-3} = r_{i-2}q_{i-1} + r_{i-1}, \enspace \text{con} \quad \quad 0 \leq r_{i-1} < r_{i-2}.$$

Y en el último paso tendríamos $q_i \in \mathbb{Z}^+$ y $r_i = 0$ tales que
$$r_{i-2} = r_{i-1}q_i + 0, \enspace \text{con} \quad \quad 0 = r_i < r_{i-1} .$$

Lo que nos dice el algoritmo de Euclides es que el último residuo no cero, en este caso $r_{i-1}$ es el máximo común divisor de $a$ y $b$.

Este procedimiento es particularmente útil cuando $a$ y $b$ son números tan grandes, tanto que determinar el máximo común divisor de ellos no sea inmediato. Aunque se comience con números muy grandes, el algoritmo de Euclides encuentra el MCD de manera rápida.

Ejemplo del algoritmo de Euclides

A continuación veremos el algoritmo de Euclides en acción.

Problema. Encuentra el máximo común divisor de $3456$ y $6524$.

Solución. Observamos que $6524 > 3456$. Así, $$6524 = 3456\cdot 1 + 3068, \quad \quad 0 \leq 3068 < 3456. $$
Aplicando nuevamente el algoritmo de la división, obtenemos
$$3456 = 3068 \cdot 1 + 388, \quad \quad 0 \leq 388 < 3068. $$
Aplicando una vez más el algoritmo de la división, se tiene
$$3068 = 388\cdot 7 + 352, \quad \quad 0 \leq 352 < 388. $$
Siguiendo este procedimiento,
$$388 = 352 \cdot 1 + 36, \quad \quad 0 \leq 36 < 352. $$
$$352 = 36 \cdot 9 + 28, \quad \quad 0 \leq 28 < 36. $$
$$36 = 28\cdot 1 + 8, \quad \quad 0 \leq 8 < 28.$$
$$28 = 8 \cdot 3 + 4, \quad \quad 0 \leq 4 < 8.$$
$$8 = 4\cdot 2 + 0.$$

Como el último residuo no cero es $4$, entonces $(6524, 3456)=4$.

$\square$

Observación. Aunque el algoritmo de Euclides requiere que los números $a$ y $b$ sean positivos, cuando ocurre el caso de que uno de ellos o los dos fueran negativos, no hay un gran obstáculo. Basta sacar el valor absoluto de ambos números al inicio, ya que los divisores de un número negativo son los mismos que los de su valor absoluto.

Veamos un ejemplo que usa esta observación.

Ejemplo. Obtén el máximo común divisor de $-100$ y $45$.

Solución. Como uno de los números es negativo, antes que nada sacamos valores absolutos: $|-100| = 100$ y $|45| = 45.$ Le aplicamos el algoritmo de Euclides a estos números:
$$ 100 = 45 \cdot 2 + 10, \quad \quad 0 \leq 10 < 45. $$
$$ 45 = 10 \cdot 4 + 5, \quad \quad 0 \leq 5 < 10. $$
$$10 = 5 \cdot 2 + 0.$$

Notemos que el último residuo no cero es $5$. Por lo tanto, $(-100, 45) = 5.$

$\square$

Demostración de la validez del algoritmo de Euclides

Ahora, veamos la demostración de que el algoritmo de Euclides funciona. El resultado clave para demostrarlo es la siguiente proposición.

Proposición. Sean $a,b \in \mathbb{Z}^+, $ tales que $a = bq + r.$ Entonces $(a,b) = (b,r).$

Demostración. Sean $a,b \in \mathbb{Z}^+$. Sea $d=(a,b)$ el máximo común divisor de $a$ y $b$, y sea $f=(b,r)$ el máximo común divisor de $b$ y $r$.

Tenemos que $d\mid a$. Además, $d \mid b,$ por lo que $d\mid bq$. Así, $d\mid a-bq=r$. De este modo, $d$ es un divisor común de $b$ y de $r$, de modo que $d\mid f$.

Por otro lado, $f\mid b$, de donde $f\mid bq$. Además, $f\mid r$. De este modo, $f\mid bq+r=a$. Concluimos entonces que $f$ es divisor común de $a$ y $b$. Pero entonces $f\mid d$.

Por propiedades de divisibilidad, tenemos entonces que $|f|=|d|$, pero como ambos son números no negativos concluimos entonces que $f=d$, como queríamos.

$\square$

Ya con este resultado demostrado, enunciemos formalmente el algoritmo de Euclides y demos su demostración.

Teorema. Empecemos tomando dos enteros positivos $a$ y $b$, con $a\geq b$. Usando el algoritmo de la división, definimos sucesivamente los números $r_0,r_1,\ldots,r_i$ y $q_0,q_1,\ldots,q_i$ de manera que se cumpla

\begin{align*}
b=aq_0+r_0\\
a=r_0q_1+r_1
\end{align*}

con $0\leq r_0<a$, y $0\leq r_1 < r_0$ y para $j=2,\ldots,i$ que se cumpla

\begin{align*}
r_{j-2}=r_{j-1}q_j+r_{j},
\end{align*}

con $0\leq r_j < r_{j-1}.$

Como $b\geq a > r_0 > r_1 > r_2 > \ldots > r_i$, entonces podemos suponer que $r_i=0$. Entonces $(a,b)=r_{i-1}$.

Demostración. Por la proposición anterior, tenemos que $(a,b)=(b,r_0)$. También por esa misma proposición, tenemos que $(b,r_0)=(r_0,r_1)$. Y, de hecho, aplicando repetidametne la proposición tenemos que:

$$(r_0,r_1)=(r_1,r_2)=\ldots=(r_{i-1},r_i)=(r_{i-1},0)=r_{i-1}.$$

La penúltima igualdad es porque $r_i=0$ y la última porque $(n,0)=n$ para cualquier entero positivo $n$.

$\square$

Máximo común divisor como combinación lineal entera

Una última consecuencia del algoritmo de Euclides es que nos ayuda a poner al máximo común divisor de dos números $a$ y $b$ como combinación lineal entera de ellos dos.

Una forma práctica de encontrar la combinación lineal correspondiente es mediante el siguiente procedimiento. Tomaremos como ejemplo el algoritmo de Euclides que ya habíamos hecho para encontrar $(6524,3456)$.

$$6524 = 3456\cdot 1 + 3068, \quad \quad 0 \leq 3068 < 3456. $$
$$3456 = 3068 \cdot 1 + 388, \quad \quad 0 \leq 388 < 3068. $$
$$3068 = 388\cdot 7 + 352, \quad \quad 0 \leq 352 < 388. $$
$$388 = 352 \cdot 1 + 36, \quad \quad 0 \leq 36 < 352. $$
$$352 = 36 \cdot 9 + 28, \quad \quad 0 \leq 28 < 36. $$
$$36 = 28\cdot 1 + 8, \quad \quad 0 \leq 8 < 28.$$
$$28 = 8 \cdot 3 + 4, \quad \quad 0 \leq 4 < 8.$$
$$8 = 4\cdot 2 + 0.$$

Lo que haremos es la siguiente tabla, en donde en la columna izquierda ponemos todos los residuos que vamos encontrando. Además, completaremos la primera fila con $1,0$ y la segunda con $0,1$.

$6524$$1$$0$
$3456$$0$$1$
$3068$
$388$
$352$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Vamos a ir llenando la tabla con lo que ya sabemos del algoritmo de Euclides. Por el algoritmo de Euclides, sabemos que $3456$ cabe $1$ vez en $6524$. Por esta razón, restamos $1$ vez la segunda fila de la primera, para obtener $1-0=1$ y $0-1=-1$. Estos son los números que van en la fila $3$, columnas $2$ y $3$:

$6524$$1$$0$
$3456$$0$$1$
$3068$$\mathbf{1}$$\mathbf{-1}$
$388$
$352$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

De nuevo, $3068$ cabe una vez en $3456$, así que de nuevo restamos una vez el tercer renglón del segundo. Nos queda $0-1=-1$ y $1-(-1)=2$ para las nuevas entradas:

$6524$$1$$0$
$3456$$0$$1$
$3068$$1$$-1$
$388$$\mathbf{-1}$$\mathbf{2}$
$352$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Ahora cambia un poco, pues $388$ ya sabemos que cabe $7$ veces en $3068$ (por lo que hicimos del algoritmo de Euclides). Así, para la nueva fila restamos siete veces la cuarta fila de la tercera, para obtener como nuevos números $1-7\cdot (-1)=8$ y $-1-7\cdot (2)=-15$. La tabla queda así:

$6524$$1$$0$
$3456$$0$$1$
$3068$$1$$-1$
$388$$-1$$2$
$352$$\mathbf{8}$$\mathbf{-15}$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Siguiendo este procedimiento repetidamente, llegamos a la siguiente tabla:

$6524$$1$$0$
$3456$$0$$1$
$3068$$1$$-1$
$388$$-1$$2$
$352$$8$$-15$
$36$$-9$$17$
$28$$89$$-168$
$8$$-98$$185$
$4$$383$$-723$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Los últimos dos números que pusimos en la tabla nos dan la respuesta de cómo poner a $4$ como combinación lineal entera de $6524$ y de $3456$:

$$4=383 \cdot 6524 – 723 \cdot 3456.$$

Verifica que en efecto las cuentas son correctas, y que esta expresión final es válida.

¿Cómo se demuestra que este procedimiento siempre funciona? Se puede mostrar inductivamente que, de hecho, para cada uno de los renglones con entradas $a,b,c$ se cumple que $a=6524b+3456c$. Esto queda como uno de los problemas de tarea moral.

Más adelante…

Esta entrada termina nuestra exploración introductoria al mundo de la aritmética de los números enteros. Sin embargo, todavía hay otros lugares a los que nos llevará el algoritmo de la división. Hasta ahora hemos discutido mucho el caso de la divisibilidad, es decir, cuando el residuo de la división de un número entre otro es igual a cero. Pero también podemos encontrar estructuras matemáticas muy ricas si estudiamos al resto de los posibles residuos. A partir de la siguiente entrada hablaremos del anillo de enteros módulo $n$, lo cual nos ayudará a formalizar estas ideas.

Tarea moral

Los siguientes ejercicios te ayudarán a repasar los conceptos vistos en esta entrada.

  1. Usa el algoritmo de Euclides para encontrar el máximo común divisor de las siguientes parejas de números, y para escribirlo como combinación lineal entera de ellos.
    1. $15$ y $35$
    2. $18$ y $92$
    3. $201$ y $153$
    4. $328$ y $528$
  2. ¿Cómo usarías el algoritmo de Euclides para encontrar el máximo común divisor de los números $91$, $105$ y $119$? Es decir, debes encontrar el mayor entero $d$ que divida a estos tres números de manera simultánea.
  3. Hay otra forma de encontrar el máximo común divisor de dos números si conocemos su factorización en números primos. Imagina que tenemos dos números $n$ y $m$ y que, conjuntamente, usan los números primos distintos $p_1,p_2,\ldots, p_k$ en su factorización en primos (quizás con exponente cero). Esto nos permite escribirlos como:
    \begin{align*} m=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \\ n=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k}\ \end{align*}
    1. Demuestra que la máxima potencia de $p_1$ que divide tanto a $m$ como a $n$ es $p_1^{\text{min}(\alpha_1,\beta_1)}$
    2. Demuestra que el máximo común divisor de $m$ y $n$ es $$p_1^{\text{min}(\alpha_1,\beta_1)} p_2^{\text{min}(\alpha_2,\beta_2)}\cdots p_k^{\text{min}(\alpha_k,\beta_k)}.$$
  4. Demuestra un resultado análogo al del inciso anterior para el mínimo común múltiplo y úsa ambos resultados para dar otra demostración de que $(m,n)[m,n]=mn$.
  5. Verifica que, en efecto, el método explicado en la entrada ayuda a escribir al máximo común divisor de dos enteros como combinación lineal de ellos.

Entradas relacionadas

Álgebra Superior II: Ideales en los enteros

Por Leonardo Ignacio Martínez Sandoval

Introducción

En la entrada pasada hablamos del concepto de divisibilidad en los números enteros. Enunciamos y demostramos varias de sus propiedades. La noción de divisibilidad da lugar a muchos otros conceptos importantes dentro de la teoría de los números enteros, como el máximo común divisor, el mínimo común múltiplo y los números primos. Así mismo, la noción de divisibilidad está fuertemente ligada con los ideales en los enteros.

En esta entrada hablaremos de este último concepto a detalle. Es una entrada un poco técnica, pero nos ayudará para asentar las bases necesarias para poder hablar de los máximos comunes divisores y los mínimos comunes múltiplos con comodidad un poco más adelante.

Ideales en los enteros y una equivalencia

Los ideales son ciertas estructuras importantes en matemáticas. En el caso particular de los números enteros, tenemos la siguiente definición

Definición. Un ideal de $\mathbb{Z}$ es un subconjunto $I$ de $\mathbb{Z}$ que cumple las siguientes dos propiedades:

  • No es vacío.
  • Es cerrado bajo restas, es decir, si $a$ y $b$ están en $I$, entonces $a-b$ también.

Veamos un ejemplo sencillo. Diremos que un número entero es par si es múltiplo de $2$ y que es impar si no es múltiplo de dos.

Ejemplo. El conjunto de todos los números pares son un ideal de $\mathbb{Z}$. Este conjunto claramente no es vacío, pues adentro de él está, por ejemplo, el $2$. Además, si tenemos que dos números $a$ y $b$ son pares, entonces por definición podemos encontrar enteros $k$ y $l$ tales que $a=2k$ y $b=2l$, de modo que $$a-b=2k-2l=2(k-l),$$ lo cual nos dice que $a-b$ también es par.

$\square$

Como veremos un poco más adelante, el ejemplo anterior se puede generalizar. Antes de ver esto, veremos una caracterización un poco distinta de lo que significa ser un ideal.

Proposición. Un subconjunto $I$ de $\mathbb{Z}$ es un ideal si y sólo si cumple las siguientes tres propiedaes:

  • No es vacío.
  • Es cerrado bajo sumas, es decir, si $a$ y $b$ están en $I$, entonces $a+b$ también.
  • Es absorbente, es decir, si $a$ está en $I$ y $b$ está en $\mathbb{Z}$, entonces $ab$ también está en $I$.

Demostración. Primero veremos que si $I$ es un ideal, entonces cumple las tres propiedades anteriores. Luego veremos que si $I$ cumple las tres propiedades anteriores, entonces es un idea.

Supongamos que $I$ es un ideal. Por definición, no es vacío, que es lo primero que queríamos ver. Veamos ahora que es cerrado bajo sumas. Supongamos que $a$ y $b$ están en $I$. Como $I$ es cerrado bajo restas y $b-b=0$, obtenemos que $b$ está en $I$. Usando nuevamente que $b$ es cerrado bajo restas para $0$ y $b$, obtenemos que $0-b=-b$ también está en $I$. Usando una última vez la cerradura de la resta, obtenemos ahora que $a+b=a-(-b)$ está en $I$, como queríamos.

La tercera propiedad la demostraremos primero para los $b\geq 0$ por inducción. Si $b=0$, debemos ver que $0\cdot a=0$ está en $I$. Esto es cierto pues en el párrafo anterior ya vimos por qué $0$ está en $I$. Supongamos ahora que para cierta $b$ fija se tiene que $ab$ está en $I$. Por la cerradura de la suma obtenemos que $$ab+a=ab+a\cdot 1=a(b+1)$$ también está en $I$, como queríamos. Aquí usamos que $1$ es identidad multiplicativa, la distributividad, la hipótesis inductiva y la cerradura de la suma.

Nos falta ver qué pasa con los $b<0$. Sin embargo, si $b<0$, tenemos que $a(-b)$ sí está en $I$ (pues $-b>0$). Así, por la cerradura de la resta tenemos que $0-a(-b)=ab$ está en $I$.

Apenas llevamos la mitad de la demostración, pues vimos que la definición de ideal implica las tres propiedades que se mencionan. Pero el regreso es más sencillo. Supongamos que un conjunto $I$ cumple las tres propiedades mencionadas. Como cumple la primera, entonces no es vacío. Ahora vemos que es cerrado bajo restas. Tomemos $a$ y $b$ en $I$. Como cumple la segunda propiedad, tenemos que $(-1)b=-b$ está en $I$. Como cumple la cerradura de la suma, tenemos que $a+(-b)=a-b$ está en $I$. Así, $I$ es cerrado bajo restas.

$\square$

La ventaja del resultado anterior es que nos permitirá pensar a los ideales de una o de otra forma, de acuerdo a lo que sea más conveniente para nuestros fines más adelante.

Clasificación de ideales

Veamos la generalización de nuestro ejemplo de números pares e impares.

Definición. Sea $n$ un entero. Al conjunto de todos los múltiplos de $n$ lo denotaremos por $n\mathbb{Z}$ y lo llamaremos el conjunto de los múltiplos de $n$, es decir:

$n\mathbb{Z}=\{nm: m\in \mathbb{Z}\}.$

Proposición. Si $n$ es cualquier entero, entonces $n\mathbb{Z}$ es un ideal de $\mathbb{Z}$.

Demostración. Claramente $n\mathbb{Z}$ no es vacío pues, por ejemplo, $0=0\cdot n$ está en $n\mathbb{Z}$. La demostración de la cerradura de la resta se sigue de un corolario de la entrada anterior. Si $a,b$ están en $n\mathbb{Z}$, entonces ambos son divisibles entre $n$, así que su resta $a-b$ también. Así, $a-b$ está en $n\mathbb{Z}$.

$\square$

El ejemplo anterior de hecho da todos los posibles ideales que existen en $\mathbb{Z}$. El siguiente teorema enuncia esto con precisión.

Teorema. Un conjunto $I$ de $\mathbb{Z}$ es un ideal si y sólo si existe un entero no negativo $n$ tal que $I=n\mathbb{Z}$.

Demostración. Tomemos $I$ un ideal de $\mathbb{Z}$. Existe la posibilidad de que $I=\{0\}$, pues en efecto este es un ideal: es no vacío (pues tiene a $0$) y es cerrado bajo restas (pues sólo hay que verificar que $0-0=0$ está en I). Si este es el caso, entonces $I=0\mathbb{Z}$, como queríamos. Así, a partir de ahora supondremos que $I$ no es este conjunto. Veremos que $I$ tiene por lo menos un elemento positivo.

Sea $a\in I$ cualquier elemento que no sea $0$. Si $a$ es positivo, entonces ya lo logramos. Si $a$ es negativo, entonces notamos que $0=a-a$ está en $I$, y que entonces $-a=0-a$ está en $I$. Pero entonces $-a$ es un número positivo en $I$.

Debido a esto, por el principio del buen orden podemos tomar al menor entero positivo $n$ que está en $I$. Afirmamos que $I=n\mathbb{Z}$. Por la caracterización de ideales que dimos en la sección anterior, todos los múltiplos de $n$ están en $I$, así que $I\supseteq n\mathbb{Z}$.

Veamos que $I\subseteq n\mathbb{Z}$ procediendo por contradicción. Supongamos que este no es el caso, y que entonces existe un $m\in I$ que no sea múltiplo de $n$. Por el algoritmo de la división, podemos escribir $m=qn+r$ con $0<r<n$. Como $m$ está en $I$ y $qn$ está en $I$, tendríamos entonces que $m-qn=r$ está en $I$. ¡Pero esto es una contradicción! Tendríamos que $r$ está en $I$ y que $0<r<n$, lo cual contradice que $n$ era el menor entero positivo en $I$ que tomamos con el principio del buen orden. Esta contradicción sólo puede evitarse si $m$ es múltiplo de $n$, como queríamos.

$\square$

Un teorema como el anterior se conoce como un teorema de clasificación pues nos está diciendo cómo son todas las posibles estructuras que definimos a partir de un criterio fácil de enunciar.

Ideal generado por dos elementos

Dado un conjunto de números enteros $S$, podríamos preguntarnos por el ideal más chiquito que contenga a $S$. Un ejemplo sencillo es tomar $S$ con sólo un elemento, digamos $S=\{n\}$. En este caso, es fácil convencerse de que el ideal más pequeño que contiene a $S$ es precisamente $n\mathbb{Z}$ (ve los problemas de la tarea moral).

Un caso un poco más interesante es, ¿qué sucede si tenemos dos elementos?

Ejemplo. ¿Cuál será el menor ideal posible $I$ que tiene a los números $13$ y $9$? Empecemos a jugar un poco con la propiedad de la cerradura de la resta. Como $13$ y $9$ están, entonces también está $4=13-9$. Como $9$ y $4$ están, entonces también está $5=9-4$. Así mismo, debe estar $1=5-4$. Pero aquí ya llegamos a algo especial: que el $1$ está. Recordemos los ideales también cumplen que una vez que está un número, están todos sus múltiplos. Así, $1\mathbb{Z}$ está contenido en $I$. Pero entonces $I=1\mathbb{Z}=\mathbb{Z}$.

$\square$

No siempre obtenemos $\mathbb{Z}$ como respuesta. Para un ejemplo en donde se obtiene $2\mathbb{Z}$, ve los problemas de la tarea moral. En la siguiente entrada hablaremos con más detalle de la respuesta, pero por el momento probaremos lo siguiente.

Proposición. Si $a$ y $b$ son enteros, entonces:

  • El conjunto $M=\{ra+sb: r,s\in \mathbb{Z}\}$ es un ideal de $\mathbb{Z}$ que tiene a $a$ y a $b$.
  • Si $I$ es un ideal de $\mathbb{Z}$ que tiene a $a$ y a $b$, entonces $M\subseteq I$.

En otras palabras, «$M$ es el ideal más pequeño (en contención) que tiene a $a$ y a $b$».

Demostración. Veamos primero que $M$ en efecto es un ideal. Para ello, notemos que no es vacío pues, por ejemplo, $0=0\cdot a+0\cdot b$ está en $M$. Además, es cerrado bajo restas pues si tenemos dos elementos en $M$, son de la forma $ra+sb$ y $ka+lb$, y su resta es $$(ra+sb)-(ka+lb)=(r-k)a+(s-l)b,$$ que vuelve a estar en $M$ pues $r-k$ y $s-l$ son enteros. Además, $a=1\cdot a+ 0\cdot b$, lo que muestra que $a$ está en $M$ y $b=0\cdot a + 1 \cdot b$, lo que muestra que $b$ está en $M$ también. Con esto demostramos el primer punto.

Para el segundo punto, supongamos que $a$ está en $I$ y que $b$ está en $I$ también. Como $I$ es idea, tiene a todos los múltiplos de $a$ y los de $b$, es decir, a todos los números de la forma $ra$ y $sb$. Como es ideal, también es cerrado bajo sumas, así que tiene todas las formas de números de este estilo. En particular, tiene a todos los números de la forma $ra+sb$ (variando $r$ y $s$), es decir, a todos los elementos de $I$, como queríamos.

$\square$

Quizás notaste algo raro. El conjunto $M$ es un ideal, pero se ve un poco distinto de los que obtuvimos con nuestra caracterización de la sección anterior. Parece más bien que «está hecho por dos enteros» en vez de estar hecho sólo por uno. Esto no es problema. Nuestra caracterización nos dice que debe existir un entero $d$ tal que $M=d\mathbb{Z}$. Esto nos llevará en la siguiente entrada a estudiar el máximo común divisor.

Intersección de ideales

Los ideales de $\mathbb{Z}$ son subconjuntos, así que podemos aplicarles operaciones de conjuntos. ¿Qué sucede si intersectamos dos ideales? La siguiente operación nos dice que

Proposición. Si $I$ y $J$ son ideales de $\mathbb{Z}$, entonces $I\cap J$ también.

Demostración. La demostración es sencilla. Como $I$ y $J$ son ideales, se puede ver que ambos tienen al $0$, y que por lo tanto su intersección también. Ahora veamos que $I\cap J$ es cerrada bajo restas. Si $a$ y $b$ están en $I\cap J$, entonces $a$ y $b$ están en $I$. Como $I$ es cerrado bajo restas, $a-b$ está en $I$. Análogamente, está en $J$. Así, $a-b$ está en $I\cap J$, como queríamos.

$\square$

Este resultado motivará nuestro estudio del mínimo común múltiplo un poco más adelante.

Más adelante…

Esta fue una entrada un poco técnica, pero ahora ya conocemos a los ideales en los enteros, algunas de sus propiedades y hasta los caraterizamos. La idea de tomar el ideal generado por dos elementos nos llevará a estudiar en la siguiente entrada el concepto de máximo común divisor. Y luego, la idea de intersectar ideales nos llevará en un par de entradas a explorar la noción de mínimo conún múltiplo

Tarea moral

Los siguientes ejercicios te ayudarán a repasar los conceptos vistos en esta entrada.

  1. Imagina que sabes que un ideal tiene al número $6$. Esto forza a que también tenga a $6-6=0$. Así, esto forza a que también tenga el $0-6=-6$. Sigue así sucesivamente, jugando con todas las nuevas restas que deben quedarse dentro del ideal. ¿Cuál es el menor ideal que puede tener al $6$?
  2. Repite lo anterior, pero ahora suponiendo que tu ideal tiene a los números $10$ y $12$. ¿Qué números puedes obtener si repetidamente puedes hacer restas? ¿Quién sería el menor ideal que tiene a ambos números?
  3. Sean $I_1,\ldots,I_k$ ideales de $\mathbb{N}$. Demuestra que $I_1\cap I_2 \cap \ldots \cap I_k$ también es un idea. Como sugerencia, usa inducción.
  4. Toma a los ideales $6\mathbb{Z}$ y $8\mathbb{Z}$. Por el resultado de la entrada, tenemos que su intersección $A$ también es un ideal. Intenta averiguar y demostrar quién es el $k$ tal que $A=k\mathbb{Z}$.
  5. ¿Es cierto que la unión de dos ideales siempre es un ideal? Si es falso, encuentra contraejemplos. Si es verdadero, da una demostración. Si es muy fácil, ¿puedes decir exactamente para qué enteros $m$ y $n$ sucede que $m\mathbb{Z}\cup n\mathbb{Z}$ es un ideal?

Entradas relacionadas

Álgebra Superior II: Algoritmo de la división en los enteros

Por Ana Ofelia Negrete Fernández

Introducción

Gracias a todo lo trabajado con anterioridad y en particular a la entrada anterior de inmersión de los naturales en los enteros, ya podemos pensar al conjunto de enteros como el conjunto $\mathbb{Z}=\{\ldots,-2,-1,0,1,2,\ldots\}$. Además, dentro de esta estructura tenemos operaciones de suma, resta y producto. Sin embargo, aún no tenemos una operación de «división». Hay dos caminos que podemos seguir. Uno es algo parecido a lo que hicimos para tener una operación de resta: podemos construir ciertas clases de equivalencia sobre parejas de enteros, definir operaciones, orden, etcétera. Esto es lo que se hace para construir el conjunto $\mathbb{Q}$ de números racionales, del cual hablaremos más adelante. Otro camino es quedarnos en $\mathbb{Z}$ e intentar decir todo lo que podamos, aunque no tengamos una operación de división. Eso es lo que haremos ahora mediante lo que se conoce como el algoritmo de la división.

Por ejemplo, si tenemos los números $-20$ y $5$, entonces sí «podemos hacer la división» de manera exacta. Dicho de otra forma, sí existe un entero $k$ tal que $-20=5k$. Ese entero es $k=-4$. Sin embargo, si tenemos los números $20$ y $3$ no podemos hacer la división, en el sentido de que no existe un entero $k$ tal que $20=3k$. Sin embargo, sí podemos lograr que $3k$ quede muy cerca de $20$. Por ejemplo, podemos escribir $20=3\cdot 6 + 2$, es decir, el $20$ se queda únicamente a dos unidades de tres veces un entero.

Lo que nos dice el algoritmo de la división es que dados dos enteros $a$ y $b$, siempre sucederá que $a$ puede ser escrito como $b$ veces un entero, más un residuo «pequeño» en términos de $b$. También nos dice que esta forma de escribir a $a$ será única.

La intuición del algoritmo de la división

Lo que nos permite hacer el algoritmo de la división es saber «cuántas veces cabe un entero en otro». En general, vamos a poder escribir $a=qb+r$ y esto querrá decir que «$b$ cabe $q$ veces en $a$ y sobran $r$». Lo que nos gustaría es hacer esto de manera que sobre lo menos posible.

Un ejemplo sencillo sería el siguiente. Tomemos $a=7$ y $b=2$. Si nos preguntáramos: ¿cuántos equipos de $2$ personas se necesitan para repartir a $7$ personas?, una posible respuesta sería: podemos formar $2$ equipos de dos personas cada uno y dejar fuera a $3$ personas. Esto se escribiría como $7=2\cdot 2 + 3$. Sin embargo, una mejor respuesta (y la que deja a menos personas fuera) es la siguiente: podemos formar $3$ equipos de dos personas cada uno, y dejar a alguien fuera. Esto corresponde algebraicamente a la igualdad $7=3\cdot 2 + 1$. Esta forma de escribir al $7$ es mejor pues el residuo es más pequeño.

Hay algunos casos que suenan un poco raros. Por ejemplo, tomemos $a = 2$, $b = 3$. Podría parecer que la división de $2$ entre $3$ da cero pues «el $3$ el mayor que el $2$ y no hay modo de que $3$ quepa en $2$». Esto es cierto: $3$ cabe cero veces en $2$. Pero hay un residuo que no se ha mencionado, que en este caso es $2$. La forma de escribir esto algebraicamente será $2=3\cdot 0 + 2$. Aquí el $0$ quiere decir que «el $3$ cabe cero veces en el $2$» y el $2$ de la derecha quiere decir que «sobran $2$». Si lo pensamos como equipos, no nos alcanzaría para crear ni un sólo equipo de $3$ personas teniendo sólo $2$.

Otro caso extraño es cuando tenemos números negativos. Por ejemplo, si $a=-7$ y $b=3$ entonces la forma en la que queremos expresar a $a$ es como sigue: $-7=(-3)\cdot 3 + 2$. Lo hacemos de esta manera pues siempre querremos que el residuo que queda sea positivo. Y de entre los residuos que se pueden obtener, lo mejor es que sobren únicamente $2$.

Resulta que la cantidad que sobra siempre se puede garantizar que sea «chica». Si estamos repartiendo $a$ en cachos de tamaño $b$, siempre podremos garantizar que lo que sobra esté entre $0$ y $|b|-1$. En símbolos, el algoritmo de la división dice que dados $a, b \in \mathbb{Z}$, con $b\neq 0$, es posible encontrar $q$ y $r$ únicos, tales que $a = bq + r,$ con $0 \leq r < |b|$. A $q$ se le llama el cociente y a $r$ le llamamos el residuo.

Que no espante el valor absoluto que se le añade a la $b$. Aún no hemos definido qué es, pero lo explicaremos un poco más abajo. Sin embargo, antes de enunciar y demostrar el teorema daremos un ejemplo con números un poco más grandes y su intuición numérica.

Otro ejemplo para entender el algoritmo de la división en $\mathbb{Z}$

Comencemos planteando el problema para $a=3531$ y $b=8$. Es decir, queremos encontrar $q$ y $r$ enteros tales que $3531 = 8q + r$, donde además $0 \leq r < 8$. Ya que $r$ debe ser un número muy pequeño entre $0$ y $8$, podemos ir dando valores a $r$ hasta que $3531-r$ se pueda escribir como $8$ veces un entero.

Si $r = 0$, habríamos de verificar si $3531$ se puede escribir como $8$ veces un entero. Nuestra intuición nos dice que esto no debería poderse, pues $3531$ es un número impar, pero $8$ veces un entero siempre será un número par.

Si $r = 1$, entonces querríamos ver si $8q = 3530$. Pero esto tampoco se puede pues con $q=441$ tenemos $8q=3528<3530$ y con $q=442$ tenemos $8q=3536>3530$ y entonces ya se pasa. Si $r = 2$, buscaríamos si $8q = 3529$, pero de nuevo este es un número impar.

Finalmente, si $r = 3$, entonces queremos ver si se puede lograr $3528= 8q$. Esto sí se puede: se toma $q=441$. Así, hemos logrado determinar que con $q = 441$, $r = 3$ se cumple que $3531 = 8q + r$, con lo que terminamos el problema.

Geométricamente, esto significa que $3531$, en la recta de los números enteros, estará situado entre números que sean $8$ veces un entero, a saber, $8\cdot 441$ y $8\cdot 442$:

$$ \ldots < 8\cdot 441 < 3531 < 8\cdot 442 < \ldots \text{.}$$

Más precisamente, como $3531$ es un entero positivo, el problema consistió en encontrar el entero que sea $8$ veces un entero más cercano por la izquierda y añadir $3$ unidades. Esto también lo podemos enunciar como que «$3531$ está a $3$ unidades a la derecha de un número que es $8$ veces un entero»:

$$ 8\cdot 441 < 8\cdot 441 + 1 < 8\cdot 441 +2 < 3531 < 8\cdot 441 +4 < 8\cdot 441 +5 < 8\cdot 441 +6 < 8\cdot 441 +7 < 8\cdot 442 \text{.}$$

En realidad esto funciona sin importar los valores de $a$ y $b$. Dado un entero $b$, podemos poner los enteros de la forma $mb$ en la recta numérica y siempre podremos situar al entero $a$ entre dos de ellos:

$$qb \leq a < (q+1)b, \qquad q\in \mathbb{Z}.$$

Si $b>0$, los múltiplos de $b$ en la recta numérica se verían así:

$$\ldots -4b, -3b, -2b, -b, 0, b, 2b, 3b, 4b, \ldots $$

De este modo, $q$ sería el mayor múltiplo de $b$ más cercano a $a$, sin excederse de $a$.

Enunciado y demostración del algoritmo de la división en $\mathbb{Z}$

Para poder enunciar el algoritmo de la división sin importar el signo de $a$ y $b$, debemos introducir un símbolo adicional.

Definición. Si $b \in \mathbb{Z}$, definimos el valor absoluto de $b$, denotado por $|b|$, como sigue: $$|b| = \left\lbrace \begin{matrix} b & \text{si $b\geq 0$}\\ -b & \text{si $ b < 0$} \end{matrix}\right.$$

En el algoritmo de la división nos darán dos números enteros $a$ y $b$. Para la restricción $0 \leq r \leq |b|$, sucederá que, no importa si $b$ sea un número positivo o negativo, nosotros nos fijaremos en el número siempre positivo que resulta de aplicarle valor absoluto a $b$. El resultado dice lo siguiente.

Teorema. Sean $a$ y $b$ en $\mathbb{Z}$ con $b\neq 0$. Entonces existen únicos enteros $q$ y $r$ enteros únicos tales que $$ a = qb + r$$ y $0 \leq r < |b|$.

Para la demostración del algoritmo de la división, necesitaremos el principio del buen orden. Como recordatorio, dice que todo subconjunto no vacío de $\mathbb{N}$ tiene un elemento mínimo.

Demostración. Primero hay que demostrar que siempre existen $q$ y $r$ enteros que satisfacen las condiciones que queremos. Vamos a suponer que $b>0$. El caso $b<0$ es muy parecido y quedará como tarea moral.

Lo que haremos es considerar al conjunto $S$ de todos los elementos de la forma $a-tb$ en donde $t$ es un entero, y tales que sean mayores o iguales a cero. Primero veremos que $S$ en efecto es un conjunto no vacío.

  • Si $a\geq 0$, tomamos $t=0$ y obtenemos la expresión $a-tb=a\geq 0$.
  • Si $a<0$, tomamos $t=a$ y obtenemos $a-tb=a-ab=a(1-b)$. Como $b>0$, entonces $b\geq 1$ y por lo tanto $(1-b)\leq 0$. Como $a<0$, obtenemos $a(1-b)\geq 0$, como queríamos.

Como $S$ es un conjunto no vacío de naturales, debe tener un elemento mínimo, al que le llamaremos $r$. Como $r$ está en $S$, obtenemos que $r=a-qb$ para algún entero $q$. Esto es un buen primer paso, pues nos muestra que $a=qb+r$. Sin embargo, todavía nos falta demostrar la importante desigualdad $0\leq r < |b|$. Como $b>0$, debemos mostrar $0\leq r < b$. Como $r$ está en $S$, obtenemos de manera inmediata que $r\geq 0$.

Sólo nos falta mostrar que $r<b$. Supongamos, con el fin de encontrar una contradicción, que $r\geq b$. Si este fuera el caso, sucedería que $r-b\geq 0$ además tendríamos la siguiente cadena de igualdades: $$r-b=a-tb-b=a-(t+1)b.$$

Esto lo que nos diría es que $r-b$ también está en $S$. ¡Pero eso es una contradicción!. Por construcción, $r$ era el menor elemento de $S$ y $r-b$ es un número menor que $r$ y que también está en $S$. Esta contradicción salió de suponer que $r\geq b$, así que en realidad debe pasar $r<b$, como queríamos.

Con esto queda demostrada la existencia de los enteros $q$ y $r$, tales que $a = bq + r$, con $0 \leq r < b$. Falta ver la unicidad. Supongamos que existen $q’$ y $r’$ enteros que también cumplen $$a = bq’ + r’$$ con $0\leq r’ < b$.

Demostramos primero que $r = r’$. Al hacer la resta $r-r’$ por un lado notamos que como mucho, puede valer $(b-1)-0=b-1$, lo cual pasa cuando $r=b-1$ y $r’=0$. Así mismo, por lo menos debe valer $0-(b-1)=-b+1$, lo cual sucede cuando $r=0$ y $r’=b-1$. Pero esta resta también se puede escribir de la siguiente manera: $$r-r’=(a-qb)-(a-q’b)=(q’-q)b.$

El único número de la forma $bk$ en $\{-b+1,-b+2,\ldots,0,\ldots,b-2,b-2\}$ es el entero $0$, pues justo no alcanza para llegar a $b$ ni a $-b$. De esta forma, $r-r’=0$, es decir $r=r’$. Y de aquí, obtenemos que $(q’-q)b=r-r’=0$. Como $b\neq 0$, obtenemos $q’-q=0$ y por lo tanto $q’=q$. Esto termina la demostración de la unicidad.

$\square$

Quizás el uso del principio del buen orden de la impresión de que la demostración anterior es «muy sofisiticada». En realidad, esto no es así. Simplemente es la forma en la que se formaliza una idea muy intuitiva: si el residuo queda mayor a $b$, entonces todavía le podemos «transferir» un sumando $b$ de $r$ a $qb$. El principio del buen orden simplemente nos garantiza que en algún momento este proceso de «transferir» sumandos $b$ debe de concluir.

Más adelante…

Cuando aplicamos el algoritmo de la división nos puede pasar un caso muy especial: que $r$ sea igual a cero. En otras palabras, en este caso podemos escribir $a=qb$ y por lo tanto $b$ cabe en $a$ «de manera exacta». Este caso es muy interesante y amerita un profundo estudio. Cuando esto sucede, decimos que $a$ es múltiplo de $b$, o bien que $b$ divide a $a$. En la siguiente entrada estudiaremos con más detalle la relación de divisibilidad en $\mathbb{Z}$. Un poco más adelante hablaremos de los ideales de $\mathbb{Z}$, que son un tipo de subconjuntos fuertemente relacionados con la noción de divisibilidad.

Tarea moral

Los siguientes ejercicios te ayudarán a repasar los conceptos vistos en esta entrada.

  1. Encuentra $q$ y $r$ enteros tales que $-1873 = 31q + r$ y $0\leq r < 31$.
  2. Demuestra las siguientes propiedades de la función valor absoluto de $\mathbb{Z}$:
    • $|a|\geq 0$ para cualquier entero $a$.
    • $|ab|=|a||b|$ para cualesquiera enteros $a$ y $b$.
    • $|a+b|\leq |a|+|b|$ para cualesquiera enteros $a$ y $b$.
  3. En general, ¿cómo se calcula $q$, para $a<0$? ¿y para $b<0$? Completa los detalles de la demostración del algoritmo de la división para cuando $b<0$.
  4. Encuentra un número que al dividirse entre $2$ deje residuo $1$, que al dividirse entre $3$ deje residuo $2$ y que al dividirse entre $4$ deje residuo $3$.
  5. Demuestra que cualquier entero se puede escribir de la forma $3q+r$ en donde $r$ es $-1$, $0$ ó $1$.

Entradas relacionadas

Álgebra Lineal II: Polinomio mínimo de transformaciones lineales y matrices

Por Julio Sampietro

Introducción

Anteriormente definimos qué quiere decir evaluar un polinomio en una matriz o en una transformación lineal. En esta entrada definiremos uno de los objetos más importantes del álgebra lineal: el polinomio mínimo. Si bien al principio nos va a costar un poco calcularlo, esto se compensa por la cantidad de propiedades teóricas que cumple. Comenzaremos dando su definición, y mostrando su existencia y unicidad. Luego exploraremos algunas propiedades y veremos ejemplos, seguido de un pequeño teorema de cambio de campos. Finalmente introduciremos un objeto similar (el polinomio mínimo puntual) y haremos unos ejercicios para cerrar.

El concepto de polinomio mínimo podría resultarle familiar a los más algebraicos de mente: ¡todo se debe a que trabajamos con dominios de ideales principales, o incluso euclidianos! Si has trabajado anteriormente con conceptos como el mínimo común múltiplo en enteros, puede que varios de los argumentos de esta entrada te suenen conocidos.

Existencia y unicidad

Comenzamos con un espacio vectorial $V$ de dimensión $n$ sobre un campo $F$. Fijando una transformación lineal $T:V\to V$, queremos entender para qué polinomios se cumple que $P(T)=0$. Nota como podríamos haber cambiado la pregunta: si fijamos un polinomio $P$, podríamos buscar todas las transformaciones $T$ tales que $P(T)=0$. Ésta pregunta la estudiaremos más adelante.

Definimos el conjunto

\begin{align*}
I(T)=\lbrace P\in F[X]\mid P(T)=0\rbrace.
\end{align*}

El polinomio cero pertenece a $I(T)$ de manera trivial. Una cosa importante es que este conjunto $I(T)$ que vamos a estudiar en verdad es «interesante», en el sentido de que debemos ver que hay más polinomios adentro y no es únicamente el conjunto $\lbrace 0\rbrace$. Una manera de ver esto es sabiendo que el espacio de transformaciones lineales de $V$ en $V$ tiene dimensión $n^2$ (lo puedes pensar como el espacio de matrices). Entonces, las $n^2+1$ transformaciones $\operatorname{Id}, T, T^2, \dots, T^{n^2}$ no pueden ser todas linealmente independientes: uno de los corolarios del lema de Steinitz es que en un espacio de dimensión $n$ a lo más se pueden tener $n$ vectores linealmente independientes. Entonces existe una combinación lineal no trivial y nula

\begin{align*}
a_0 \operatorname{Id}+a_1 T+\dots + a_{n^2} T^{n^2}=0.
\end{align*}

Luego $a_0+a_1X+\dots+a_{n^2}X^{n^2}$ es un polinomio no cero tal que $P(T)=0$, es decir $P\in I(T)$.

Con el argumento de arriba vimos que $I(T)$ es «interesante» en el sentido de que tiene polinomios no cero. El siguiente teorema se puede entender como que $I(T)$ se puede describir muy fácilmente.

Teorema. Existe un único polinomio mónico, distinto de cero $\mu_T$ tal que $I(T)$ es precisamente el conjunto de múltiplos de $\mu_T$. Es decir

\begin{align*}
I(T)=\mu_T \cdot F[X]=\lbrace \mu_T \cdot P(X)\mid P(X)\in F[X]\rbrace.
\end{align*}

La demostración hará uso del algoritmo de la división para polinomios. Te lo compartimos aquí, sin demostración, por si no lo conoces o no lo recuerdas.

Teorema (algoritmo de la división en $\mathbb{F}[x]$). Sean $f(x)$ y $g(x)$ polinomios en $F[x]$, donde $g(x)$ no es el polinomio cero. Entonces, existen únicos polinomios $q(x)$ y $r(x)$ en $F[x]$ tales que $$f(x)=q(x)g(x)+r(x),$$ en donde $r(x)$ es el polinomio cero, o $\deg(r(x))<\deg(g(x))$.

Si te interesa saber cómo se demuestra, puedes seguir la teoría de polinomios disponible en la Unidad 4 del curso de Álgebra Superior II.

Demostración. Una de las proposiciones de la entrada pasada nos dice que $I(T)$ es un subespacio de $F[X]$. Por otro lado si $P\in I(T)$ y $Q\in F[X]$ entonces

\begin{align*}
(PQ)(T)= P(T)\circ Q(T)=0\circ Q(T)=0.
\end{align*}

Lo que discutimos antes de enunciar el teorema nos dice que $I(T)\neq\{0\}$. Escogemos entonces $P\in I(T)$ un polinomio no cero de grado mínimo. Podemos suponer sin perdida de generalidad que $P$ es mónico, de no serlo, podemos dividir a $P$ por su coeficiente principal sin cambiar el grado.

La ecuación previa nos indica que todos los múltiplos de $P$ también están en $I(T)$. Veamos que todo elemento de $I(T)$ es de hecho un múltiplo de $P$. Si $S\in I(T)$, usamos el algoritmo de la división polinomial para escribir $S=QP+R$ con $Q,R\in F[X]$. Aquí hay dos casos, que $R$ sea el polinomio cero, o bien que no lo sea y entonces $\deg R <\deg P$. Nota que $R=S-QP\in I(T)$ dado que $I(T)$ es un subespacio de $F[X]$ y $S,QP\in I(T)$. Si $R\neq 0$, entonces como $\deg R<\deg P$ llegamos a una contradicción de la minimalidad del grado de $P$. Luego $R=0$ y por tanto $S=QP$. Entonces $I(T)$ es precisamente el conjunto de todos los múltiplos de $P$ y así podemos tomar $\mu_T=P$.

Para verificar la unicidad de $\mu_T$, si otro polinomio $S$ tuviera las mismas propiedades, entonces $S$ dividiría a $\mu_T$ y $\mu_T$ dividiría a $S$. Sin embargo, como ambos son mónicos se sigue que deben ser iguales: en efecto, si $\mu_T=S\cdot Q$ y $S=\mu_T \cdot R$ entonces $\deg Q=\deg R=0$, porlo tanto son constantes, y como el coeficiente principal de ambos es $1$, se sigue que ambos son la constante $1$ y así $\mu_T=S$. Esto completa la demostración.

$\square$

Definición. Al polinomio $\mu_T$ se le conoce como el polinomio mínimo de $T$.

Primeras propiedades y ejemplos

Debido a su importancia, recalcamos las propiedades esenciales del polinomio mínimo $\mu_T$:

  • Es mónico y cumple $\mu_T(T)=0$.
  • Para cualquier otro polinomio $P\in F[X]$, sucede que $P(T)=0$ si y sólo si $\mu_T$ divide a $P$.

Toda la teoría que hemos trabajado hasta ahora se traduce directamente a matrices usando exactamente los mismos argumentos. Lo enunciamos de todas maneras: si $A\in M_n(F)$ es una matriz cuadrada, entonces existe un único polinomio mónico $\mu_A\in F[X]$ con las siguientes propiedades:

  • $\mu_A(A)=O_n$,
  • si $P\in F[X]$, entonces $P(A)=O_n$ si y sólo si $\mu_A$ divide a $P$.

Como jerga, a veces diremos que un polinomio «anula $T$» si $P(T)=0$. En este sentido los polinomios que anulan a $T$ son precisamente los múltiplos de $\mu_T$.

Vimos antes de enunciar el teorema que podemos encontrar un polinomio $P$ no cero de grado menor o igual a $n^2$ tal que $P(T)=0$. Como $\mu_T$ divide a $P$ se sigue que $\deg \mu_T\leq n^2$. Esta cota resulta ser débil, y de hecho un objeto que hemos estudiado previamente nos ayudará a mejorarla: el polinomio característico. Este también va a anular a $T$ y con ello obtendremos una mejor cota: $\deg \mu_T\leq n$.

Ejemplo. Si $A=O_n$, entonces $\mu_A=X$. En efecto, $\mu_A(A)=0$ y además es el polinomio de menor grado que cumple esto, pues ningún polinomio constante y no cero anula a $O_n$ (¿por qué?). Nota como además $I(A)$ es precisamente el conjunto de polinomios sin término constante.

$\square$

Ejemplo. Considera la matriz $A\in M_2(\mathbb{R})$ dada por

\begin{align*}
A= \begin{pmatrix}
0 & -1\\
1 & 0
\end{pmatrix}.
\end{align*}

Nos proponemos calcular $\mu_A$. Nota que $A$ satisface $A^2=-I_2$. Por tanto el polinomio $P(X)=X^2+1$ cumple $P(A)=0$. Así, $\mu_A$ tiene que dividir a este polinomio ¡pero este es irreducible sobre los números reales! En efecto, si existiese un factor propio de $P$ sobre $\mathbb{R}$, tendríamos que la ecuación $X^2=-1$ tiene solución, y sabemos que este no es el caso. Entonces $\mu_A$ tiene que ser $X^2+1$.

$\square$

Ejemplo. Sean $d_1,\dots, d_n\in F$ escalares y $A$ una matriz diagonal tal que $[a_{ii}]=d_i$. Los elementos pueden no ser distintos entre sí, así que escogemos una colección máxima $d_{i_1},\dots, d_{i_k}$ de elementos distintos. Para cualquier polinomio $P$, tenemos que $P(A)$ es simplemente la matriz diagonal con entradas $P(d_i)$ (esto porque el producto $A^n$ tiene como entradas a $d_i^n$). Entonces para que $P(A)=0$ se tiene que cumplir que $P(d_i)=0$, y para que esto pase es suficiente que $P(d_{i_k})=0$. Eso quiere decir que $P$ tiene al menos a los $d_{i_k}$ como raíces, y entonces $(X-d_{i_1})(X-d_{i_2})\cdots (X-d_{i_k})$ divide a $P$.

Nota como esto es suficiente: encontramos un polinomio mónico, $(X-d_{i_1})(X-d_{i_2})\cdots (X-d_{i_k})$ que divide a cualquier $P$ tal que $P(A)=0$. Así

\begin{align*}
\mu_A(X)=(X-d_{i_1})\cdots (X-d_{i_k}).
\end{align*}

$\square$

Cambio de campos

En uno de los ejemplos argumentamos que el polinomio mínimo era $X^2+1$ porque este es irreducible sobre $\mathbb{R}$. Pero, ¿qué pasaría si cambiáramos nuestro campo a $\mathbb{C}$? La situación puede ser incluso más delicada: a una matriz con entradas racionales la podemos considerar como una instancia particular de una matriz con entradas reales, que a su vez podemos considerar como una matriz compleja. ¿Hay tres polinomios mínimos distintos? El siguiente teorema nos da una respuesta tranquilizante.

Teorema. Sean $F_1\subset F_2$ dos campos y $A\in M_n(F_1)$ una matriz, entonces el polinomio mínimo de $A$ vista como elemento de $M_n(F_1)$ y el polinomio mínimo de $A$ vista como elemento de $M_n(F_2)$ son iguales.

Demostración. Sea $\mu_1$ el polinomio de $A\in M_n(F_1)$ y $\mu_2$ el polinomio mínimo de $A\in M_n(F_2)$. Puesto que $F_1[X]\subset F_2[X]$, se tiene que $\mu_1\in F_2[X]$ y además $\mu_1(A)=0$ por definición. Luego $\mu_2$ necesariamente divide a $\mu_1$. Sean $d_1=\deg \mu_1$ y $d_2=\deg \mu_2$, basta verificar que $d_2\geq d_1$ y para que esto se cumpla basta con encontrar $P\in F_1[X]$ de grado a lo más $d_2$ tal que $P(A)=0$ (entonces $\mu_1$ dividiría a este polinomio y se sigue la desigualdad).

Desarrollando que $\mu_2(A)=0$ en todas sus letras (o mejor dicho, en todos sus coeficientes) se tiene

\begin{align*}
a_0 I_n+ a_1 A+\dots + a_{d_2} A^{d_2}=O_n.
\end{align*}

Esto es equivalente a tener $n^2$ ecuaciones homogéneas en las variables $a_0,\dots, a_{d_2}$. Como $A$ tiene entradas en $F_1$ los coeficientes de estas ecuaciones todos pertenecen a $F_1$. Tenemos un sistema de ecuaciones con coeficientes en $F_1$ que tiene una solución no trivial en $F_2$: tiene automáticamente una solución no trivial en $F_1$ por un ejercicio de la entrada de Álgebra Lineal I de resolver sistemas de ecuaciones usando determinantes. Esto nos da el polinomio buscado.

$\square$

Mínimos puntuales

Ahora hablaremos (principalmente a través de problemas resueltos) de otro objeto muy parecido al polinomio mínimo: el polinomio mínimo puntual. Este es, esencialmente un «polinomio mínimo en un punto». Más específicamente si $T:V\to V$ es lineal con polinomio mínimo $\mu_T$ y $x\in V$ definimos

\begin{align*}
I_x=\lbrace P\in F[X]\mid P(T)(x)=0\rbrace.
\end{align*}

Nota que la suma y diferencia de dos elementos en $I_x$ también está en $I_x$.

Problema. Demuestra que existe un único polinomio mónico $\mu_x\in F[X]$ tal que $I_x$ es el conjunto de múltiplos de $\mu_x$ en $F[X]$. Más aún, demuestra que $\mu_x$ divide a $\mu_T$.

Solución. El caso $x=0$ se queda como ejercicio. Asumamos entonces que $x\neq 0$. Nota que $\mu_T\in I_x$ puesto que $\mu_T(T)=0$. Sea $\mu_x$ el polinomio mónico de menor grado en $I_x$. Demostraremos que $I_x=\mu_x\cdot F[X]$.

Primero si $P\in \mu_x \cdot F[X]$ entonces por definición $P=\mu_x Q$ para algún $Q\in F[X]$ y entonces

\begin{align*}
P(T)(x)=Q(T)(\mu_x(T)(x))=Q(T)(0)=0.
\end{align*}

Así $P\in I_x$, y queda demostrado que $\mu_x \cdot F[X]\subset I_x$.

Conversamente, si $P\in I_x$ podemos usar el algoritmo de la división para llegar a una expresión de la forma $P=Q\mu_x+R$ para algunos polinomios $Q,R$ con $\deg R<\deg \mu_x$. Supongamos que $R\neq 0$. Similarmente a como procedimos antes, se cumple que $R= P-Q\mu_x\in I_x$ dado que $I_x$ es cerrado bajo sumas y diferencias. Dividiendo por el coeficiente principal de $R$, podemos asumir que $R$ es mónico. Entonces $R$ es un polinomio mónico de grado estrictamente menor que el grado de $\mu_x$, una contradicción a nuestra suposición: $\mu_x$ es el polinomio de grado menor con esta propiedad. Luego $R=0$ y $\mu_x$ divide a $P$.

Así queda probado que si $P\in I_x$ entonces $P\in \mu_x\cdot F[X]$, lo que concluye la primera parte del problema. Para la segunda, vimos que $\mu_T\in I_x$ y por tanto $\mu_x$ divide a $\mu_T$.

$\square$

Problema. Sea $V_x$ el subespacio generado por $x, T(x), T^2(x), \dots$. Demuestra que $V_x$ es un subespacio de $V$ de dimensión $\deg \mu_x$, estable bajo $T$.

Solución. Es claro que $V_x$ es un subespacio de $V$. Además, dado que $T$ manda a generadores en generadores, también es estable bajo $T$. Sea $d=\deg\mu_x$. Demostraremos que $x, T(x),\dots, T^{d-1}(x)$ forman una base de $V_x$, lo que concluiría el ejercicio.

Veamos que son linealmente independientes. Si $$a_0x+a_1T(x)+a_2T^2(x)+\dots+a_{d-1}T^{d-1}(x)=0$$ para algunos escalares $a_i$ no todos cero, entonces el polinomio

\begin{align*}
P=a_0+a_1X+\dots+a_{d-1}X^{d-1}
\end{align*}

es un elemento de $I_x$, pues $P(T)(x)=0$. Luego $\mu_x$ necesariamente divide a $P$, pero esto es imposible puesto que el grado de $P$ es $d-1$, estrictamente menor que el grado de $\mu_x$. Luego los $a_i$ deben ser todos nulos, lo que muestra que $x,T(x),T^2(x),\dots,T^{d-1}(x)$ es una colección linealmente independiente.

Sea $W$ el espacio generado por $x,T(x),\dots, T^{d-1}(x)$. Afirmamos que $W$ es invariante bajo $T$. Es claro que $T(x)\in W$, similarmente $T(T(x))=T^2(x)\in W$ y así sucesivamente. El único elemento «sospechoso» es $T^{d-1}(x)$, para el cual basta verificar que $T(T^{d-1}(x))=T^d(x)\in W$. Dado que $\mu_x(T)(x)=0$ y $\mu_x$ es mónico de grado $d$, existen escalares $b_i$ (más precisamente, los coeficientes de $\mu_x$) no todos cero tales que

\begin{align*}
T^{d}(x)+b_{d-1}T^{d-1}(x)+\dots+b_0 x=0.
\end{align*}

Esto nos muestra que podemos expresar a $T^d(x)$ en términos de $x, T(x),\dots, T^{d-1}(x)$ y por tanto $T^d(x)$ pertenece a $W$.

Ahora, dado que $W$ es estable bajo $T$ y contiene a $x$, se cumple que $T^{k}(x)\in W$ para todo $k\geq 0$. En particular $V_x\leq W$. Luego $V_x=W$ (la otra contención es clara) y $x,T(x),\dots, T^{d-1}(x)$ genera a $W$, o sea a $V_x$.

Mostramos entonces que $x,T(x),\dots, T^{d-1}(x)$ es una base para $V_x$ y así $\dim V_x=d$.

$\square$

Unos ejercicios para terminar

Presentamos unos últimos ejercicios para calcular polinomios mínimos.

Problema. Calcula el polinomio mínimo de $A$ donde

\begin{align*}
A= \begin{pmatrix}
0 & 1 & 0\\
1 & 0 & 0\\
0 & 0 & 1\end{pmatrix}.
\end{align*}

Solución. A estas alturas no tenemos muchas herramientas que usar. Comenzamos con calcular $A^2$:

\begin{align*}
A^2= \begin{pmatrix}
0 & 1 & 0\\
1 & 0 & 0\\
0 & 0 & 1\end{pmatrix}\cdot \begin{pmatrix}
0 & 1 & 0\\
1 & 0 & 0\\
0 & 0 & 1\end{pmatrix}= \begin{pmatrix} 1 & 0 & 0\\ 0 &1 & 0 \\ 0 & 0 & 1\end{pmatrix}.
\end{align*}

Entonces en particular $A^2=I_3$. Así, el polinomio mínimo $\mu_A$ tiene que dividir a $X^2-1$. Este último se factoriza como $(X-1)(X+1)$, pero es claro que $A$ no satisface ni $A-I_3=0$ ni $A+I_3=0$. Entonces $\mu_A$ no puede dividir propiamente a $X^2-1$, y por tanto tienen que ser iguales.

$\square$

Problema. Calcula el polinomio mínimo de la matriz $A$ con

\begin{align*}
A=\begin{pmatrix}
1 & 2\\
0 & 1
\end{pmatrix}.
\end{align*}

Solución. Nota como

\begin{align*}
A-I_2=\begin{pmatrix} 0 & 2\\ 0 & 0\end{pmatrix}
\end{align*}

y es fácil verificar que el cuadrado de la matriz de la derecha es cero. Así $(A-I_2)^2=0$, o sea, el polinomio $P(X)=(X-1)^2$ anula a $A$. Similarmente al problema anterior, $\mu_A$ tiene que dividir a $P$, pero $P$ sólo tiene un factor: $X-1$. Dado que $A$ no satisface $A-I_2=0$ se tiene que $\mu_A$ no puede dividir propiamente a $P$, y entonces tienen que ser iguales. Luego $\mu_A=(X-1)^2=X^2-2X+1$.

$\square$

Más adelante…

En las entradas subsecuentes repasaremos los eigenvalores y eigenvectores de una matriz, y (como mencionamos) ligaremos el polinomio característico de una matriz con su polinomio mínimo para entender mejor a ambos.

Tarea moral

Aquí unos ejercicios para practicar lo que vimos.

  1. Encuentra una matriz $A$ cuyo polinomio mínimo sea $X^2$. Para cada $n$, ¿puedes encontrar una matriz cuyo polinomio mínimo sea $X^n$?
  2. Encuentra una matriz $A$ cuyo polinomio mínimo sea $X^2-1$. Para cada $n$, ¿puedes encontrar una matriz cuyo polinomio mínimo sea $X^n-1$?
  3. Encuentra el polinomio de la matriz $A$ en $M_n(F)$ cuyas entradas son todas $1$.
  4. Si $T:M_n(\mathbb{R})\to M_n(\mathbb{R})$ es la transformación que manda a cada matriz en su transpuesta, encuentra el polinomio mínimo de $T$.
  5. Sea $V$ un espacio vectorial y $x,y$ vectores linealmente independientes. Sea $T:V\to V$ una transformación lineal. ¿Cómo son los polinomios $P$ tales que $P(T)$ se anula en todo el subespacio generado por $x$ y $y$? ¿Cómo se relacionan con los polinomios mínimos puntuales de $T$ para $x$ y $y$?

Entradas relacionadas