Archivo de la etiqueta: heurísticas

Seminario de Resolución de Problemas: Polinomios asociados a matrices y el teorema de Cayley-Hamilton

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

Para terminar esta serie de entradas de álgebra lineal, y con ello el curso de resolución de problemas, hablaremos de polinomios especiales asociados a una matriz: el polinomio mínimo y el polinomio característico. Después, hablaremos del teorema de Cayley-Hamilton, que a grandes rasgos dice que una matriz se anula en su polinomio característico.

Estos resultados forman parte fundamental de la teoría que se aprende en un curso de álgebra lineal. En resolución de problemas, ayudan mucho para entender a los eigenvalores de una matriz, y expresiones polinomiales de matrices.

Polinomio mínimo de una matriz

Podemos evaluar un polinomio en una matriz cuadrada de acuerdo a la siguiente definición.

Definición. Si $A$ es una matriz de $n\times n$ con entradas reales y $p(x)$ es un polinomio en $\mathbb{R}[x]$ de la forma $$p(x)=a_0+a_1x+a_2x^2+\ldots+a_nx^n,$$ definimos a la matriz $p(A)$ como la matriz $$a_0I_n+a_1A+a_2A^2+\ldots+a_nA^n.$$

De manera análoga se puede dar una definición cuando las entradas de la matriz, o los coeficientes del polinomio, son números complejos.

Cuando una matriz está diagonalizada, digamos $A=P^{-1}DP$ con $P$ invertible y $D$ diagonal, entonces evaluar polinomios en $A$ es sencillo. Se tiene que $p(A)=P^{-1} p(D) P$, y si las entradas en la diagonal principal de $D$ son $d_1,\ldots,d_n$, entonces $p(D)$ es diagonal con entradas en la diagonal principal iguales a $p(d_1),\ldots,p(d_n)$.

Dada una matriz $A$, habrá algunos polinomios $p(x)$ en $\mathbb{R}[x]$ para los cuales $p(A)=0$. Si $p(x)$ es uno de estos, entonces cualquier eigenvalor de $A$ debe ser raíz de $p(x)$. Veamos un problema de la International Mathematics Competition de 2011 que usa esto. Es el Problema 2 del día 1.

Problema. Determina si existe una matriz $A$ de $3\times 3$ con entradas reales tal que su traza es cero y $A^2+ {^tA} = I_3$.

Sugerencia pre-solución. Busca un polinomio $p(x)$ tal que $p(A)=0$.

Solución. La respuesta es que no existe dicha matriz. Procedamos por contradicción. Si existiera, podríamos transponer la identidad dada para obtener que
\begin{align*}
A&=I _3- {^t(A^2)}\\
&=I_3-({^tA})^2\\
&=I_3-(I_3 – A^2)^2\\
&=2A^2 – A^4.
\end{align*}

De aquí, tendríamos que $A^4-2A^2+A = 0$, de modo que cualquier eigenvalor de $A$ debe ser una raíz del polinomio $$p(x)=x^4-2x^2+x=x(x-1)(x^2+x-1),$$

es decir, debe ser alguno de los números $$0,1,\frac{-1+\sqrt{5}}{2}, \frac{-1-\sqrt{5}}{2}.$$

Los eigenvalores de $A^2$ son los cuadrados de los eigenvalores de $A$, así que son algunos de los números $$0,1,\frac{3+\sqrt{5}}{2}, \frac{3-\sqrt{5}}{2}.$$

Como la traza de $A$ es $0$, la suma de sus tres eigenvalores (con multiplicidades), debe ser $0$. Como la traza de $A^2$ es la de $I_3-{ ^tA}$, que es $3$, entonces la suma de los eigenvalores de $A$ al cuadrado (con multiplicidades), debe ser $0$. Un sencillo análisis de casos muestra que esto no es posible.

$\square$

De entre los polinomios que se anulan en $A$, hay uno especial. El polinomio mínimo de una matriz $A$ con entradas reales es el polinomio mónico $\mu_A(x)$ de menor grado tal que $\mu_A(A)=O_n$, donde $O_n$ es la matriz de $n\times n$ con puros ceros. Este polinomio siempre es de grado menor o igual a $n$.

Una propiedad fundamental del polinomio mínimo de una matriz es que es mínimo no sólo en un sentido de grado, sino también de divisibilidad.

Teorema. Sea $A$ una matriz de $n\times n$ con entradas reales. Entonces para cualquier polinomio $p(x)$ en $\mathbb{R}[x]$ tal que $p(A)=O_n$, se tiene que $\mu_A(x)$ divide a $p(x)$ en $\mathbb{R}[x]$.

Veamos cómo se puede usar este resultado.

Problema. La matriz $A$ de $2\times 2$ con entradas reales cumple que $$A^3-A^2+A=O_2.$$ Determina los posibles valores que puede tener $A^2-A$.

Sugerencia pre-solución. Encuentra las posibles opciones que puede tener el polinomio mínimo de $A$ y haz un análisis de casos con respecto a esto.

Solución. La matriz $A$ se anula en el polinomio $$p(x)=x^3-x^2+x=x(x^2-x+1),$$ en donde $x^2-x+1$ tiene discriminante negativo y por lo tanto es irreducible.

El polinomio mínimo $\mu_A(x)$ debe ser un divisor de $p(x)$. Además, es de grado a lo más $2$. Esto nos deja con las siguientes opciones:

  • $\mu_A(x)=x$, de donde $A=O_2$, y por lo tanto $A^2=O_2$. De aquí, $A^2-A=O_2$.
  • $\mu_A(x)=x^2-x+1$. En este caso, tenemos que $A^2-A+I_2=0$. Así, $A^2-A=-I_2$.

Para mostrar que ambas opciones son posibles, en el primer caso usamos $A=O_2$ y en el segundo caso usamos $$A=\begin{pmatrix} 0 & -1 \\ 1 & 1 \end{pmatrix}.$$

$\square$

Polinomio característico de una matriz

El polinomio característico de una matriz $A$ de $n\times n$ se define como $$\chi_A(x)=\det(xI_n – A).$$

Teorema. El polinomio característico de una matriz $A$ cumple que:

  • Es un polinomio mónico en $x$ de grado $n$.
  • El coeficiente del término de grado $n-1$ es la traza de $A$.
  • El coeficiente libre es $\chi_A(0)=(-1)^n\det(A)$.
  • Es igual al polinomio característico de cualquier matriz similar a $A$.

Para ver ejemplos de cómo obtener el polinomio característico y cómo usar sus propiedades, hacemos referencia a la siguiente entrada:

Propiedades del polinomio característico

En particular, para fines de este curso, es importante leer los ejemplos y problemas resueltos de esa entrada.

El teorema de Cayley-Hamilton y una demostración con densidad

Finalmente, hablaremos de uno de los resultados fundamentales en álgebra lineal.

Teorema (Cayley-Hamilton). Si $A$ es una matriz de $n\times n$ con entradas en $\mathbb{C}$ y $\chi_A(x)$ es su polinomio característico, entonces $$\chi_A(A)=O_n.$$

En realidad el teorema de Cayley-Hamilton es válido para matrices más generales. Daremos un esbozo de demostración sólo para matrices con entradas complejas pues eso nos permite introducir una técnica de perturbaciones.

Esbozo de demostración. Vamos a hacer la técnica de la bola de nieve, construyendo familias poco a poco más grandes de matrices que satisfacen el teorema.

Si $A$ es una matriz diagonal, las entradas en su diagonal son sus eigenvalores $\lambda_1,\ldots, \lambda_n$. Por la discusión al inicio de esta entrada, $\chi_A(A)$ es diagonal con entradas $\chi_A(\lambda_1),\ldots,\chi_A(\lambda_n)$, y como los eigenvalores son raíces del polinomio característico, entonces todos estos valores son $0$, y por lo tanto $\chi_A(A)=0$.

Si $A$ es diagonalizable, digamos, de la forma $A=P^{-1} D P$, entonces $A$ y $D$ tienen el mismo polinomio característico. Por la discusión al inicio de la entrada, y por el caso anterior:
\begin{align*}
\chi_A(A) &= \chi_D(A)\\
&= \chi_D(P^{-1} D P)\\
&=P^{-1}\chi_D(D) P\\
&=P^{-1}O_n P \\
&=O_n.
\end{align*}

Si $A$ tiene todos sus eigenvalores distintos, se puede mostrar que $A$ es diagonalizable. Ahora viene la idea clave del argumento de continuidad.

Pensemos al espacio métrico de matrices de $n\times n$. Afirmamos que las matrices con eigenvalores todos distintos son densas en este espacio métrico. Para ello, tomemos una matriz $A$. En efecto, como estamos trabajando en $\mathbb{C}$, existe una matriz invertible $P$ tal que $P^{-1}A P$ es triangular. Como $P$ es invertible, define una transformación continua. Los eigenvalores de $P^{-1} A P$ son sus entradas en la diagonal, y podemos perturbarlos tan poquito como queramos para hacer que todos sean distintos.

De esta forma, existe una sucesión de matrices $A_k$, todas ellas diagonalizables, tales que $A_k \to A$ conforme $k\to \infty$. El resultado se sigue entonces de las siguientes observaciones:

  • Los coeficientes del polinomio característico de una matriz dependen continuamente de sus entradas.
  • Las entradas de potencias de una matriz dependen continuamente de sus entradas.
  • Así, la función $\chi_{M}(M)$ es continua en la matriz variable $M$.

Concluimos como sigue $\chi_{A_k}(A_k)=0$, por ser cada una de las matrices $A_k$ diagonalizables. Por la continuidad de $\chi_{M}(M)$, tenemos que
\begin{align*}
\chi_A(A)&=\lim_{k\to \infty} \chi_{A_k}(A_k)\\
&= \lim_{k\to \infty} O_n \\
&= O_n.
\end{align*}

$\square$

Terminamos esta entrada con un problema que usa el teorema de Cayley-Hamilton.

Problema. Muestra que para cualesquiera matrices $X,Y,Z$ de $2\times 2$ con entradas reales se cumple que
\begin{align*}
&ZXYXY + ZYXYX + XYYXZ + YXXYZ\\
= &XYXYZ + YXYXZ + ZXYYX + ZYXXY.
\end{align*}

Sugerencia pre-solución. Muestra que las matrices reales de $2\times 2$ de traza cero conmutan con cualquier matriz de $2\times 2$.

Solución. Si $A$ es una matriz de $2\times 2$ de traza cero, su polinomio característico es
\begin{align*}
\chi_A(x)&=x^2 – \text{tr}(A) x + \det(A)\\
&=x^2 + \det(A).
\end{align*}

Por el teorema de Cayley-Hamilton, se satisface entonces que $A^2=-\det(A) I_2$, así que $A^2$ es un múltiplo de la identidad, y por lo tanto conmuta con cualquier matriz de $2\times 2$.

La identidad que queremos mostrar se puede reescribir como $$Z(XY-YX)^2 = (XY-YX)^2Z.$$

La traza de $XY$ es igual a la traza de $YX$, y como la traza es una transformación lineal, tenemos que $$\text{tr}(XY-YX)= \text{tr}(XY)-\text{tr}(YX)=0.$$ El problema se termina aplicando la discusión de arriba a la matriz $$A=XY-YX.$$

$\square$

Más problemas

Puedes encontrar más problemas relacionados con el polinomio mínimo, el polinomio característico y el teorema de Cayley-Hamilton en la Sección 8.2, 8.4 y 8.5 del libro Essential Linear Algebra de Titu Andreescu. También hay más problemas relacionados con el teorema de Cayley-Hamilton en el Capítulo 4 del libro Mathematical Bridges de Andreescu, Mortici y Tetiva.

Seminario de Resolución de Problemas: Cálculo de determinantes

Por Leonardo Ignacio Martínez Sandoval

1 respuesta

Introducción

Una de las habilidades fundamentales que hay que desarrollar para resolver problemas de álgebra lineal es el cálculo de determinantes. Como vimos en la entrada anterior, conocer el determinante de una matriz nos permite saber si es invertible. Así mismo, los determinantes permiten encontrar soluciones a sistemas de ecuaciones lineales, y más adelante veremos que están relacionados con el rango. Además, los determinantes juegan un papel muy importante en otras áreas de las matemáticas, como cálculo y teoría de gráficas.

Todo parte de la siguiente definición:

Definición. Para una matriz $A$ de $n \times n$ con entradas reales $A=[a_{ij}]$, el determinante de $A$ es $$\det A = \sum_{\sigma \in S_n} \text{sign}(\sigma)a_{1\sigma(1)}\cdot\ldots\cdot a_{n\sigma(n)},$$ donde la suma se hace sobre todas las permutaciones (funciones biyectivas) $\sigma$ de $\{1,\ldots,n\}$ a sí mismo y $\text{sign}(\sigma)$ es el signo de la permutación.

A $\det A$ también lo escribimos a veces en notación de «matriz con barras verticales» como sigue:

\begin{align*}
\det A = \begin{vmatrix}
a_{11} & a_{12} & \ldots & a_{1n}\\
a_{21} & a_{22} & \ldots & a_{2n}\\
\vdots & & \ddots & \vdots\\
a_{n1} & a_{n2} & \ldots & a_{nn}.
\end{vmatrix}.
\end{align*}

La definición permite mostrar de maneras muy elegantes las propiedades que cumplen los determinantes, pero no es nada práctica para cuando se quieren hacer las cuentas. Como la suma se hace sobre todas las permutaciones $\sigma$ de un conjunto de $n$ elementos, si quisiéramos calcular determinantes por definición se tendrían que hacer $n!$ productos, y luego sumar todos estos resultados.

Por esta razón, es muy importante encontrar otras formas de evaluar determinantes. Para empezar, esta entrada hará referencia a dos enlaces del blog en los que se discuten las propiedades básicas de determinantes. Luego, se hablará de dos tipos especiales de determinantes: los de Vandermonde y los de matrices circulantes.

Técnicas básicas de cálculo de determinantes

Lo primero y más importante es que conozcas las teoría básica para cálculo de determinantes. Aquí en el blog hay una entrada que sirve justo para conocer las propiedades y técnicas principales para encontrar determinantes.

Técnicas básicas de cálculo de determinantes

Además, es también muy importante que sepas calcular determinantes usando la expansión de Laplace. En la siguiente entrada puedes ver el enunciado de la técnica, y cómo se usa en varios ejemplos:

Problemas de cálculo de determinantes

Para fines de este curso, es importante que revises esas entradas. Puedes saltarte las demostraciones de los resultados principales, pero presta atención a cómo se usan en cada uno de los problemas.

Las siguientes secciones presentan técnicas avanzadas que a veces resultan útiles. Sin embargo, tómalas como temas optativos, dando prioridad a primero dominar los básicos.

Determinantes de Vandermonde

Teorema (determinante de Vandermonde). Sean $a_1,\ldots,a_n$ números reales. El determinante de la matriz de Vandermonde \begin{align*}
\begin{pmatrix}
1&a_1 & a_1^2 & \ldots & a_1^{n-1}\\
1 & a_2 & a_2^2 & \ldots & a_2^{n-1}\\
1&a_3 & a_3^2 & \ldots & a_3^{n-1}\\
\vdots& & & \ddots & \vdots\\
1& a_n & a_n^2 & \ldots & a_n^{n-1}\\
\end{pmatrix}
\end{align*} es igual a $$\prod_{1\leq i < j \leq n} (a_j-a_i).$$

Ejemplo. La matriz $$\begin{pmatrix} 1 & a & a^2 \\ 1 & b & b^2 \\ 1 & c & c^2\end{pmatrix}$$ es una matriz de Vandermonde, así que su determinante es $$(b-a)(c-a)(c-b).$$

$\square$

Veamos un problema en el que aparece una matriz de Vandermonde.

Problema. Sean $a$, $b$ y $c$ reales distintos de $0$. Muestra que el determinante de $$\begin{vmatrix}a^2 & b^2 & c^2\\ c^2& a^2 & b^2 \\ ca & ab & bc \end{vmatrix}$$ es $$(a^2-bc)(b^2-ca)(c^2-ab).$$

Sugerencia pre-solución. Formula un problema equivalente usando propiedades de determinantes para que quede un determinante del tipo de Vandermonde. Aprovecha la simetría para ahorrar algunas cuentas.

Solución. Como el determinante es homogéneo en cada columna, podemos factorizar $a^2$ de la primera, $b^2$ de la segunda y $c^2$ de la tercera para obtener que
\begin{align*}
\begin{vmatrix}a^2 & b^2 & c^2\\ c^2& a^2 & b^2 \\ ca & ab & bc \end{vmatrix} &= (abc)^2 \begin{vmatrix}1 & 1 & 1 \\ \frac{c^2}{a^2}& \frac{a^2}{b^2} & \frac{b^2}{c^2} \\ \frac{c}{a} & \frac{a}{b} & \frac{b}{c} \end{vmatrix}\\
&=-(abc)^2 \begin{vmatrix}1 & 1 & 1 \\ \frac{c}{a} & \frac{a}{b} & \frac{b}{c} \\ \frac{c^2}{a^2}& \frac{a^2}{b^2} & \frac{b^2}{c^2} \end{vmatrix}.
\end{align*}

Aquí también usamos que al intercambiar dos filas (o columnas), el determinante de una matriz cambia de signo.

Una matriz tiene el mismo determinante que su transpuesta, y la transpuesta de esta última matriz es de Vandermonde, de modo que $$-(abc)^2 \begin{vmatrix}1 & 1 & 1 \\ \frac{c}{a} & \frac{a}{b} & \frac{b}{c} \\ \frac{c^2}{a^2}& \frac{a^2}{b^2} & \frac{b^2}{c^2} \end{vmatrix} = -(abc)^2 \left(\frac{a}{b}-\frac{c}{a}\right)\left(\frac{b}{c}-\frac{c}{a}\right)\left(\frac{b}{c}-\frac{a}{b}\right).$$

Vamos a partir esta última expresión en factores simétricos. Tenemos que $$ab\left(\frac{a}{b}-\frac{c}{a}\right)=a^2-bc.$$ De manera similar, tenemos también $$-ca\left(\frac{b}{c}-\frac{c}{a}\right)=c^2-ab$$ y $$bc\left(\frac{b}{c}-\frac{a}{b}\right)=b^2-ac.$$

Así, concluimos que $$\begin{vmatrix}a^2 & b^2 & c^2\\ c^2& a^2 & b^2 \\ ca & ab & bc \end{vmatrix}= (a^2-bc)(b^2-ca)(c^2-ab).$$

$\square$

Determinantes de matrices circulantes

Teorema (determinantes circulantes) Sean $a_1,\ldots, a_n$ números reales. El determinante de la matriz circulante
\begin{align*}
\begin{pmatrix}
a_1& a_n & a_{n-1} & \ldots & a_2\\
a_2&a_1& a_{n}& \ldots & a_3\\
a_3 & a_2& a_1& \ldots & a_4\\
\vdots& & & \ddots & \vdots\\
a_n& a_{n-1} & a_{n-2} &\ldots & a_1.
\end{pmatrix}
\end{align*}

es $$\prod_{j=0}^{n-1} (a_1 + a_n \omega_j + a_{n-1} \omega_j^2 + \ldots + a_2 \omega_j^{n-1}),$$ en donde $\omega_j$ es la $n$-ésima raíz de la unidad dada por $\omega_j:= e^{j \cdot \frac{2\pi i}{n}}$.

Ejemplo. La matriz $$\begin{pmatrix} a & b & c \\ c & a & b \\ b & c & a\end{pmatrix}$$ es una matriz circulante, así que su determinante es $$(a+b+c)(a+\omega b + \omega^2 c)(a+\omega^2 b+ \omega c),$$ donde $\omega$ es la raíz cúbica de la unidad de argumento positivo mínimo.

$\square$

El siguiente problema apareció en la tercera edición de la Olimpiada Iberoamericana de Matemática Universitaria. El enunciado en esa ocasión fue un poco distinto, pero lo adaptamos a la notación de esta entrada.

Problema. Sea $n\geq 3$ un entero Muestra que el determinante de la matriz circulante en donde $a_1=a_n=a_{n-1}=1$ y $a_2=\ldots=a_{n-1}=0$ es $3$ si $n$ no es un múltiplo de $3$ y es $0$ si $n$ es un múltiplo de $3$.

Sugerencia pre-solución. Para empezar, aplica el teorema de determinantes de matrices circulantes. Luego, necesitarás además un argumento de polinomios y de números complejos.

Solución. Para empezar, llamemos $A_n$ a la matriz del problema. Como $A_n$ es una matriz circulante, su determinante es $$\det(A_n) = \prod_{j=0}^{n-1} (1 + \omega_j + \omega_j^2).$$

El polinomio $1+x+x^2$ se factoriza como $(\eta-x)(\eta^2-x)$, donde $\eta$ es la raíz cúbica de la unidad de argumento positivo mínimo. De esta forma, podemos reescribir al determinante de $A_n$ como $$\det(A_n) = \prod_{j=0}^{n-1} (\eta-\omega_j)(\eta^2-\omega_j).$$

El polinomio $h(x)=x^n-1$ se factoriza como $$h(x)=(x-\omega_0)(x-\omega_1)\ldots(x-\omega_{n-1}),$$ así que $\det(A_n)$ es precisamente el producto de $h(\eta)$ con $h(\eta^2)$. En otras palabras,
\begin{align*}
\det(A_n)&= (\eta^n-1)(\eta^{2n}-1)\\
&=\eta^{3n}+1-(\eta^n+\eta^{2n})\\
&=2-(\eta^n+\eta^{2n})
\end{align*}

Finalmente, hacemos un análisis de casos:

  • Si $n$ es múltiplo de $3$, entonces $\eta^n = \eta^{2n} = 1$ y entonces $\det(A_n)=0$.
  • Si $n$ no es múltiplo de $3$, entonces $n$ y $2n$ no son congruentes módulo $3$, y entonces $\eta^n$ y $\eta^{2n}$ son $\eta$ y $\eta^2$ en algún orden. Así, $$(\eta^n+\eta^{2n})=\eta+\eta^2=-1,$$ y por lo tanto $\det(A_n)=3$.

$\square$

Más problemas

Puedes encontrar más problemas de cálculo de determinantes en la Sección 7.4 y la Sección 7.5 del libro Essential Linear Algebra de Titu Andreescu.

Seminario de Resolución de Problemas: Geometría discreta

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

Como última entradaen esta parte de geometría, hablaremos de algunos temas de geometría discreta. Esta área de las matemáticas se dedica a estudiar propiedades combinatorias de familias de objetos geométricos. Estos objetos pueden ser puntos, rectas, rectángulos, convexos, politopos, etc. Las relaciones que nos interesan son que formen un tipo de acomodo especial, que se intersecten, que podamos contar ciertas configuraciones, etc.

Sólo hablaremos superficialmente de un área que es profunda y bastante interesante. Un libro genial que cubre varios temas de geometría discreta de manera sistemática es Lectures on Discrete Geometry de Jiří Matoušek.

Convexos y el teorema de Helly

Un convexo de $\mathbb{R}^d$ es un conjunto tal que cualquier segmento recto definido por dos de sus puntos queda totalmente contenido en el conjunto. Por ejemplo, los convexos de $\mathbb{R}$ son los intervalos, mientras que en el plano hay muchos más ejemplos, como lo muestra la figura.

Ejemplos de conjuntos convexos y no convexos
Ejemplos de conjuntos convexos y no convexos

Si tenemos un conjunto $X$ de $\mathbb{R}^d$, su envolvente convexa es el conjunto convexo más pequeño (por contención), que contiene a $X$. Cuando $X$ es un conjunto de puntos, tenemos algo como lo de la figura. Si todos los puntos de $X$ están sobre la frontera de su envolvente convexa, y no hay tres alineados, decimos que $X$ son puntos en posición convexa.

Envolvente convexa de un conjunto de puntos
Envolvente convexa de un conjunto de puntos. El conjunto $X$ no está en posición convexa.

Los conjuntos convexos son especiales en muchos sentidos. Uno de ellos es que la intersección de una familia de convexos se puede detectar «localmente».

Problema. A una plática de matemáticas de una hora asistieron una cantidad finita de matemáticos. La plática estaba tan aburrida, que cada matemático se durmió en cierto intervalo de tiempo de esa hora, pero sólo una vez. A la hora del café, los matemáticos platicaron entre sí, y si se dieron cuenta de que para cualesquiera dos de ellos, $I$ y $J$, hubo un momento en el que $I$ y $J$ estuvieron dormidos simultáneamente. Muestra que hubo un momento de la plática en la que todos los matemáticos estuvieron dormidos.

Sugerencia pre-solución. Hay muchas soluciones. Una es mediante un argumento de maximalidad.

Solución. En términos matemáticos, queremos ver que si tenemos una cantidad finita de intervalos acotados y cerrados en la recta real que se intersectan de dos en dos, entonces todos ellos se intersectan.

Tomemos el intervalo $I$ cuyo extremo derecho sea mínimo. Llamemos $x$ a este extremo derecho. Afirmamos que cualquier otro intervalo tiene a $x$. Sea $J$ cualquiera de estos intervalos, con extremo izquierdo $y$ y extremo derecho $z$.

Imagen auxiliar para intersección de intervalos
Imaten auxiliar para intersección de intervalos

Por la minimalidad de $x$, tenemos que $x\leq z$. Si $y>x$, entonces $J$ no intersecta a $I$ y se contradice la hipótesis. Entonces, para que $J$ pueda intersectar a $I$, necesitamos que $y \leq x$. Pero entonces $x$ queda entre los extremos del intervalo $J$ y por lo tanto $x$ está en $J$. Esto termina la prueba.

$\square$

En dimensiones más altas, tenemos el siguiente resultado.

Teorema (Helly). Sea $\mathcal{F}$ una familia finita de al menos $d+1$ conjuntos convexos compactos en $\mathbb{R}^d$. Si cada subfamilia de $\mathcal{F}$ de $d+1$ convexos tiene intersección no vacía, entonces $\mathcal{F}$ tiene intersección no vacía.

El teorema de Helly es una de las piedras angulares de la geometría discreta. Una cantidad de enorme de investigación ha resultado de considerar variantes del teorema con hipótesis más débiles o más fuertes.

Politopos y la fórmula de Euler

Otra área muy rica de la geometría discreta es la teoría de politopos. Un politopo es la generalización a altas dimensiones de un polígono, o de un poliedro. Hay dos formas de definir politopos. Una es tomar puntos en $\mathbb{R}^d$ y considerar su envolvente convexa. Esto es un $V$-politopo. Para la otra necesitamos algunas definiciones adicionales.

Un subespacio afín de $\mathbb{R}^d$ es la traslación de un subespacio lineal, y su dimensión es la dimensión del subespacio lineal trasladado. Por ejemplo, cualquier punto de $\mathbb{R}^d$ es un subespacio afín de dimensión $0$ pues es la traslación del subespacio trivial $\{0\}$. Las rectas en $\mathbb{R}^d$, incluso aquellas que no pasan por el $0$, son subespacios afines de dimensión $0$. A los subespacios afines de dimensión $n-1$ les llamamos hiperplanos. Así, las líneas son los hiperplanos de $\mathbb{R}^2$, los planos los hiperplanos de $\mathbb{R}^3$, etc.

Si $P$ es un hiperplano de $\mathbb{R}^d$, un semiespacio definido por $P$ es todo lo que queda en uno de los lados de $P$. Si es abierto, no incluye a $P$, y si es cerrado, sí incluye a $P$. Un hiperplano siempre define dos semiespacios abiertos, y dos cerrados.

Hay otra forma de pensar a los politopos: tomamos una cantidad finita de semiespacios cerrados y los intersectamos. Si esa intersección está acotada, entonces a lo que obtenemos le llamamos un $H$-politopo. Piensa, por ejemplo, en los hiperplanos que determinan las caras de un cubo, y en los semiespacios «hacia adentro».

Un resultado clásico es que todo $H$-politopo es un $V$-politopo, así que podemos usar la descripción que nos convenga de acuerdo al problema que estemos resolviendo.

Un hiperplano $H$ es hiperplano soporte de un politopo $P$ si el politopo se queda totalmente contenido en alguno de los semiespacios definidos por $H$. Una cara de $P$ es la intersección de $P$ con alguno de sus hiperplanos soporte. Resulta que las caras de politopos son politopos. Para que todo funcione bien, debemos considerar al vacío como un politopo.

La dimensión de un politopo es la menor dimensión de un subespacio afín que lo contiene. Por definición, la dimensión del vacío es $-1$. Si una cara de un politopo es $k$, entonces la llamamos una $k$-cara. Los valores de $k$ sólo pueden ir de $0$ a $d$. A las $0$-caras les llamamos los vértices de $P$. A las $1$-caras les llamamos las aristas.

Para cada $k$ de $0$ a $n$, usamos $f_k$ para denotar la cantidad de $k$ caras del politopo, y a $$(f_0,f_1,f_2,\ldots,f_d)$$ le llamamos el $f$-vector del politopo. Estamos listos para enunciar un resultado crucial en la teoría de politopos.

Teorema (fórmula de Euler). Sea $P$ un politopo de dimensión $d$ en $\mathbb{R}^d$. Entonces

$$f_0-f_1+f_2-\ldots + (-1)^d f_d = 1.$$

Observa que $f_d$ siempre es $1$ pues la única $d$ cara de un politopo $P$ de dimensión $d$ es $P$ mismo.

En $\mathbb{R}^2$ esta fórmula no es tan útil, pues simplemente nos dice que si un polígono tiene $V$ vértices y $A$ aristas, entonces $V-A=0$, es decir, que tiene la misma cantidad de vértices y aristas, lo cual es inmediato.

En $\mathbb{R}^3$ la fórmula nos dice que si un poliedros tiene $V$ vértices, $A$ aristas y $F$ caras, entonces $$V-A+F=2.$$ Este fórmula se puede usar en varios problemas matemáticos de poliedros.

Problema. Muestra que el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro son los únicos poliedros en $\mathbb{R}^3$ tales que a cada vértice una misma cantidad $a$ de caras, y cada cara consiste de la misma cantidad $b$ de vértices.

Sugerencia pre-solución. Usa notación adecuada, poniendo la cantidad de vértices, aristas y caras en términos de $a$ y $b$. Usa la fórmula de Euler. Luego, da un argumento de desigualdades.

Solución. A cada vértice llegan por lo menos $3$ caras, y cada cara tiene por lo menos $3$ vértices. Así, $a\geq 3$ y $b\geq 3$.

Si hay $A$ aristas, entonces tanto $2A$ como $bF$ cuentan la cantidad de parejas $(e,c)$ donde $e$ es una arista y $c$ una cara que lo tiene. Esto se debe a que cada arista está exactamente en dos caras, y a que como cada cara tiene $b$ vértices, entonces tiene $b$ aristas. Por lo tanto, $2A=bF$, de donde $$A=\frac{bF}{2}.$$

De manera similar, si hay $V$ vértices y $F$ caras, entonces tanto $aV$ como $bF$ cuentan la cantidad de parejas $(v,c)$, donde $v$ es un vértice y $c$ es una cara que lo tiene. De esta forma, $aV=bF$, de lo cual $$V=\frac{bF}{a}.$$

Por la fórmula de Euler, tenemos entonces que $$\frac{bF}{a}-\frac{bF}{2}+F = 2.$$ Esta igualdad implica, en particular, que al determinar los valores de $a$ y $b$, se determinan $F$ y entonces $V$ y $A$.

Si multiplicamos por $\frac{2}{bF}$ de ambos lados, y sumamos $1$ de ambos lados, tenemos que \begin{equation}
\frac{2}{a}+\frac{2}{b}= \frac{4}{bF}+1 > 1.
\end{equation}

Como $a\geq 3$, entonces $\frac{2}{a}\leq \frac{2}{3}$. De este modo,
\begin{align*}
\frac{2}{b}&> 1 – \frac{2}{a}\\
&\geq 1-\frac{2}{3} \\
&= \frac{1}{3}.
\end{align*}

Esto muestra que $b<6$, de modo que $b\leq 5$. Por simetría, $a\leq 5$. Podemos entonces simplemente estudiar los casos $a=2,3,4$ y $b=2,3,4$.

Si $a=5$, entonces la desigualdad (1) se cumple sólo si $b=3$. Si $a=4$, la desigualdad (1) se cumple sólo si $b=3$. Finalmente, si $a=3$, la desigualdad se cumple para $b=3,4,5$. De este modo, las únicas parejas de $(a,b)$ que sirven son:

  • $(3,3)$, que nos da el tetraedro.
  • $(3,4)$, que nos da el cubo.
  • $(4,3)$, que nos da el octaedro.
  • $(3,5)$, que nos da el dodecaedro.
  • $(5,3)$, que nos da el icosaedro.

$\square$

La fórmula de Euler es sólo una de las relaciones lineales que satisfacen las entradas del $f$-vector de un politopo. Otros dos resultados interesantes del área son:

  • Las relaciones de Dehn-Sommerville, que dan otras relaciones lineales que satisfacen las entradas del $f$-vector.
  • El teorema de la cota superior que para $d$, $n$ y $k$ fijas acota el número de $k$-caras que puede tener un politopo de dimensión $d$ con $n$-vértices.

Un libro canónico para aprender de politopos de manera sistemática es el Lectures on Polytopes de Günter M. Ziegler.

Conjuntos de puntos y teoremas extremales

La última área de la que hablaremos serán los problemas extremales en geometría discreta. Nos enfocaremos únicamente en problemas sobre conjuntos de puntos, pero se podrían hacer preguntas análogas para otras familias de objetos geométricos. De manera informal, pero intuitiva, un problema extremal de geometría consiste en mostrar que si un número es suficientemente grande, entonces empiezan a pasar cosas interesantes con ciertos objetos geométricos.

Uno de los resultados clásicos es el teorema de Erdős-Szekeres. A grandes rasgos, lo que dice es que si tenemos muchos puntos en posición general en el plano (no hay tres colineales), entonces siempre es posible encontrar un subconjunto grande de ellos que está en posición convexa.

Teorema (Erdős-Szekeres). Sea $n$ un entero positivo. Entonces, existe un entero $f(n)$ tal que si se tiene un conjunto $S$ con $f(n)$ o más puntos en el plano en posición general, entonces hay un subconjunto de tamaño $n$ de $S$ que consiste de puntos en posición convexa.

Típicamente, es bastante difícil encontrar los valores exactos de las funciones involucradas en problemas extremales de geometría discreta. El tipo de resultados de interés para la investigación matemática es encontrar las mejores «cotas asintóticas», que digan, más o menos, cómo se comporta la función que se está estudiando. En el caso del teorema de Erdős-Szekeres, las mejores cotas se enuncian así:

$$1+2^{n-2}\leq f(n) \leq 2^{n+o(n)}.$$

La notación $h(n)=o(g(n))$ quiere decir que $\frac{h(n)}{g(n)}\to 0$ cuando $n\to \infty$.

Aunque sea difícil determinar los valores exactos de $f(n)$ para toda $n$, hay algunos valores pequeños que sí se pueden determinar.

Problema. Demuestra que $f(4)=5$, es decir:

  • Que hay conjuntos de $4$ puntos en posición general en el plano que no tienen subconjuntos de tamaño $4$ en posición convexa.
  • Que cualquier subconjunto de $5$ puntos en posición general en el plano tiene un subconjunto de $4$ puntos en posición convexa.

Sugerencia pre-solución. Encontrar el ejemplo para el primer punto es fácil, simplemente explora el problema haciendo varias figuras. Divide el problema en casos de acuerdo a la cantidad de puntos que forman la envolvente convexa. Para uno de los casos, usa el principio de las casillas.

Solución. El siguiente ejemplo son $4$ puntos que no están en posición convexa, y que por lo tanto no tienen subconjuntos de tamaño $4$ en posición convexa.

Cuatro puntos que no están en posición convexa
Cuatro puntos que no están en posición convexa

Mostraremos ahora que $5$ puntos en posición general en el plano siempre tienen un subconjunto de tamaño $4$ en posición convexa. Procedemos por casos de acuerdo a la cantidad de puntos que están en la frontera de la envolvente convexa. Si son $4$ ó $5$, entonces inmediatamente entre ellos hay $4$ en posición convexa.

Si son $3$, entonces llamemos $A$, $B$, $C$ a esos puntos y $D$ y $E$ a los otros dos, que quedan dentro de $\triangle ABC$. La recta $DE$ divide al plano en dos semiplanos. Por principio de las casillas, hay dos puntos de entre $A$, $B$ y $C$ que yacen en el mismo semiplano, digamos $A$ y $B$.

Caso con tres puntos en la envolvente convexa
Caso con tres puntos en la envolvente convexa

Como la recta $DE$ no corta al segmento $AB$ (por estar $D$ y $E$ en el mismo semiplano), y la recta $AB$ no corta al segmento $DE$ (por ser $AB$ un lado de la envolvente convexa), entonces los puntos $A$, $B$, $D$, $E$ están en posición convexa.

$\square$

Finalmente, presentamos un par de resultados más. También son problemas extremales, pero en vez de hablar de envolventes convexas, hablan acerca de distancias.

Si lo piensas un poco, es imposible colocar $4$ puntos distintos en el plano de modo que todas las parejas estén a distancia uno. Si tienes $n$ puntos en el plano, entonces ellos definen $\binom{n}{2}=\frac{n(n-1)}{2}\approx \frac{n^2}{2}$ parejas de puntos. ¿Cuántos de ellos pueden estar a distancia $1$? Estudiar esta cantidad es un problema que fue propuesto por Paul Erdős. Si $u(n)$ denota este máximo, las mejores cotas que hay para el problema son $$n^{1+d/\log \log n} \leq f(n) \leq O(n^{4/3}).$$

Aquí $d$ es una constante que sirve para toda $n$. La notación $h(n)\leq O(g(n))$ se refiere a que existe una constante $c$ tal que $h(n)\leq cg(n)$ para $n$ suficientemente grande.

Por supuesto, la distancia $1$ no tiene nada de especial. En realidad, ninguna distancia puede repetirse demasiado. Ya que ninguna distancia aparece muchas veces, la intuición (por principio de las casillas), nos debe decir que entonces para un conjunto de puntos, sus parejas deben definir muchas distancias diferentes. Llamemos $d(n)$ a la cantidad de distancias diferentes que define un conjunto de $n$ puntos en el plano. Erdős también preguntó, ¿cómo se comporta este número?. Las mejores cotas son $$\Omega\left(\frac{n}{\log }\right)\leq d(n) \leq O\left(\frac{n}{\sqrt{\log n}}\right).$$

La notación $h(n)\geq\Omega(g(n))$ se refiere a que existe una constante $c$ tal que $h(n)\geq cg(n)$ para $n$ suficientemente grande.

El problema de las distancias unitarias y el problema de las distancias diferentes han estimulado mucha de la investigación en geometría discreta. Las demostraciones de sus cotas, han introducido al área varias técnicas de teoría de números, del método probabilista y de geometría algebraica.

Un libro con mucho material de problemas extremales y otros temas es Combinatorial Geometry and its Algorithmic Applications de Janos Pach y Micha Sharir.

Más problemas

En resumen, en los siguientes libros hay bastante material para aprender los temas de esta entrada:

Seminario de Resolución de Problemas: Desigualdades básicas

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

En las entradas correspondientes a esta parte del curso aprenderemos varias técnicas que nos permitirán resolver problemas que involucren desigualdades. El área es enorme y hay libros enteros dedicados a ello. Nosotros sólo veremos algunas técnicas. Comenzaremos con desigualdades básicas y nos enfocaremos en los siguientes temas:

  • Desigualdad $x^2\geq 0$ y desigualdad del triángulo
  • Desigualdades de medias
  • La desigualdad de Cauchy-Schwarz
  • Técnicas de cálculo en desigualdades

En esta entrada veremos el primer inciso, que consiste de dos ideas muy sencillas:

Desigualdad $x^2\geq 0$. El cuadrado de cualquier número real es mayor o igual a cero. Es cero si y sólo si el número es cero.

Desigualdad del triángulo. Si $V$ es un espacio vectorial con norma $\norm{\cdot}$, entonces para cualesquiera vectores $u$ y $v$ se tiene que $$\norm{u}+\norm{v}\geq \norm{u+v}.$$

La desigualdad $x^2\geq 0$ parece muy inocente. Sin embargo, es una herramienta muy versátil cuando se combina con manipulaciones algebraicas creativas. La desigualdad del triángulo la estamos enunciando para espacios vectoriales con norma en general. Dos casos particulares que a lo mejor te son más familiares son los siguientes:

Desigualdad del triángulo para $\mathbb{R}$. Si $a$ y $b$ son números reales, entonces $|a|+|b| \geq |a+b|$.

Desigualdad del triángulo en $\mathbb{R}^n$. Si $ABC$ es un triángulo en el plano (o dimensiones más altas) , de lados de longitudes $\overline{AB}=c$, $\overline{BC}=a$ y $\overline{CA}=b$, entonces
\begin{align*}
a+b&\geq c\\
b+c &\geq a\\
c+a &\geq b.
\end{align*}

Si una de las igualdades se da, $ABC$ es un triángulo degenerado, es decir, con sus tres vértices alineados. En otro caso, todas las desigualdades son estrictas.

Veamos aplicaciones de estas desigualdades básicas.

La desigualdad $\frac{a^2+b^2}{2}\geq \sqrt{ab}$

Comenzaremos probando de dos formas distintas una desigualdad que también resulta útil en otras ocasiones.

Problema. Sean $a$ y $b$ números reales mayores o iguales a cero. Muestra que $$\frac{a+b}{2}\geq \sqrt{ab},$$ y que la igualdad se da si y sólo si $a$ y $b$ son iguales.

A esta desigualdad se le conoce como la desigualdad MA-MG para dos números reales. También forma parte de las desigualdades básicas que te ayudará conocer. Se llama así pues en el lado izquierdo tenemos a la media aritmética de los números $a$ y $b$, y al lado derecho tenemos la media geométrica de los números $a$ y $b$. En realidad la desigualdad se vale para más reales no negativos, pero esto lo veremos en otra entrada.

Sugerencia pre-solución. El problema se puede resolver tanto de manera algebraica, (usando $x^2\geq 0$) como de manera geométrica (usando la desigualdad del triángulo).

Para resolverlo de la primera forma, trabaja hacia atrás. Haz manipulaciones algebraicas para formular problemas equivalentes hasta que llegues a una desigualdad obvia.

Para resolverlo de la segunda forma, haz una figura en la que puedas representar tanto a la media geométrica como a la aritmética. Una forma de hacerlo es comenzar con una semicircunferencia de diámetro $a+b$.

Para identificar el caso de igualdad, haz un análisis de casos.

Solución algebraica. Queremos mostrar que $$\frac{a+b}{2}\geq \sqrt{ab}.$$ Pasando el dos multiplicando, y luego $2\sqrt{ab}$ restando al lado izquierdo, esta desigualdad igualdad ocurre si y sólo si $$a+b-2\sqrt{ab}\geq 0.$$ En el lado izquierdo identificamos un binomio al cuadrado, que se puede factorizar para dar la desigualdad equivalente $$\left(\sqrt{a}-\sqrt{b}\right)^2\geq 0.$$

Esta desigualdad es de la forma $x^2\geq 0$, así que es claramente cierta. La igualdad ocurre si y sólo si $\sqrt{a}-\sqrt{b}=0$, lo cual sucede si y sólo si $a=b$. Todos los pasos que hicimos son reversibles. Esto termina la solución.

$\square$

Solución geométrica. Consideremos la siguiente figura, en donde tenemos una semicircunferencia de diámetro $\overline{AB}=a+b$ y centro $O$. Aquí $C$ es un punto en $AB$ tal que $\overline{AC}=a$ y entonces $\overline{CB}=b$. Además, $D$ es un punto sobre la circunferencia tal que $DC$ es perpendicular a $AB$. Llamemos $d=\overline{CD}$.

Prueba visual de la desigualdad entre la media aritmética y media geométrica usando desigualdades básicas
Prueba visual de MA-MG

Como $\triangle AOD$ y $\triangle BOD$ son isósceles por tener dos lados iguales al radio de la circunferencia, tenemos que $\angle ADO = \angle DAO$ y $\angle BDO = \angle DBO$. Usando estas igualdades y que la suma de los ángulos internos de $\triangle ABD$ es $180^\circ$, se puede mostrar que el ángulo $ADB$ es de $90^\circ$.

De este modo, $\triangle ACD$ y $\triangle DCB$ son semejantes (por ser ambos semejantes a $\triangle ABD$ por criterio AA). Por la semejanza, tenemos que $$\frac{a}{d}=\frac{d}{b},$$ de donde $d=\sqrt{ab}$.

Para terminar la demostración, tomamos un punto $E$ sobre $DO$ tal que $\angle EOC = \angle ECO$. Por la desigualdad del triángulo en $\triangle DEC$, tenemos que

\begin{align*}
\sqrt{ab}&=\overline{DC}\\
&\leq \overline{DE} + \overline{EC}\\
&= \overline{DE} + \overline {EO}\\
&= \overline{DO}\\
&=\frac{a+b}{2}.
\end{align*}

Con esto demostramos la desigualdad. Para terminar el problema, necesitamos ver cuándo se dan los casos de igualdad. Se tiene la igualdad si y sólo si $\triangle DEC$ es un triángulo degenerado, lo cual sucede si y sólo si $E$ está en el segmento $DC$. Esto sólo es posible cuando $DO$ es perpendicular a $AB$, lo cual sucede si y sólo si $C=O$, si y sólo si $AC=CB$, si y sólo si $a=b$.

$\square$

Desigualdades básicas aplicadas a un problema de la Olimpiada Mexicana de Matemáticas

El siguiente problema apareció como parte de los exámenes selectivos que el Comité Nacional de la Olimpiada Mexicana de Matemáticas envía a los estados para seleccionar a sus estudiantes en distintas etapas. Tiene muchas formas de resolverse, pero veamos cómo se puede resolver con desigualdades básicas.

Problema. Sean $a,b,c,d$ reales positivos con $a^2+b^2+c^2+d^2=4$. Muestra que $$a^5+b^5+c^5+d^5 \geq a+b+c+d$$

Sugerencia pre-solución. Modifica el problema a mostrar como desigualdad auxiliar que para un real no negativo $x$ se tiene que $$x^5-2x^2-x+2\geq 0.$$ Esta desigualdad se puede demostrar usando que los cuadrados son no negativos.

Solución. Vamos a probar primero la desigualdad $$x^5-2x^2-x+2\geq 0.$$ Para que sea un poco más fácil, factorizaremos la expresión del lado izquierdo.

Notemos que $1$ es una raíz de $x^5-2x^2-x+2$, de modo que por el teorema del factor podemos factorizar $x-1$ del polinomio. Obtenemos que $$x^5-2x^2-x+2=(x-1)(x^4+x^3+x^2-x-2).$$

Notemos que, nuevamente, $1$ es una raíz de $(x^4+x^3+x^2-x-2)$. Al factorizar $x-1$ de nuevo, obtenemos que $$x^5-2x^2-x+2=(x-1)^2(x^3+2x^2+3x+2).$$

Ya estamos listos para probar la desigualdad que queremos. Notemos que $(x-1)^2\geq 0$ y que $x^3+2x^2+3x+2$ es mayor o igual que cero para $x\geq 0$ pues es un polinomio con puros coeficientes positivos. Esto prueba la desigualdad auxiliar. Reescribiéndola, tenemos que $$x^5\geq 2x^2+x-2.$$ Aplicándola en esta forma a los cuatro reales positivos $a,b,c,d$ del problema, y usando que la suma de cuadardos es $4$, obtenemos que
\begin{align*}
a^5 & + b^5+c^5+d^5\\
&\geq 2(a^2+b^2+c^2+d^2)+a+b+c+d-8\\
&=2\cdot 4 + a+b+c+d-8\\
&=a+b+c+d.
\end{align*}

Esto termina el problema.

$\square$

El primer paso parece un poco artificial. ¿Por qué queremos probar esa desigualdad auxiliar? En otra entrada de blog escribí cómo se puede llegar a las ideas de esta solución.

Desigualdad del triángulo aplicada a la construcción de tetraedros

Si pegamos cuatro triángulos equiláteros en el espacio se hace un tetraedro regular. De manera similar, si pegamos cuatro triángulos como el siguiente, también se hace un tetraedro en el espacio:

Pegar cuatro triángulos congruentes para hacer un tetraedro

La intuición nos dice que debería poderse con cualquier triángulo. Pero esta intuición está mal.

Problema. Sea $ABC$ un triángulo con un ángulo mayor a $90^\circ$. Muestra que no existe ningún tetraedro en el espacio tal que sus cuatro caras sean congruentes a $ABC$.

Sugerencia pre-solución. Procede por contradicción. Por simetría, puedes asumir que el ángulo mayor a $90^\circ$ es el ángulo en $A$. Usa como punto auxiliar al punto medio de $BC$ y usa desigualdades.

Solución. Una observación inicial es que si $ABC$ es un triángulo, $M$ es el punto medio de $BC$ y su ángulo interno en $A$ es mayor a $90^\circ$, entonces $2\overline{AM}<\overline{BC}$. Esto se muestra trazando una circunferencia de diámetro $BC$.

Desigualdad para la mediana en términos del ángulo que hace.

De hecho,

  • Un punto $X$ está sobre la circunfencia si y sólo si $\angle BXC = 90 ^\circ$, si y sólo si $\overline{OX}=\overline{OA}$.
  • $X$ está dentro de la circunferencia si y sólo si $\angle BXC > 90^\circ$, si y sólo si $\overline{OX}<\overline{OA}$ y
  • $X$ está fuera de la circunferencia si y sólo si $\angle BXC < 90^\circ$, si y sólo si $\overline{OX}>\overline{OA}$.

Resolvamos el problema. Sin pérdida de generalidad, el ángulo en $A$ es mayor a $90^\circ$. Entonces $\overline{AM}<\frac{\overline{BC}}{2}$, de donde $2\overline{AM}<\overline{BC}$.

Supongamos que se pudiera hacer en el espacio un tetraedro $WXYZ$ tal que cada una de las caras es congruente al triángulo $ABC$. Sin pérdida de generalidad, tenemos que
\begin{align*}
\overline{WX}&=\overline{YZ}=\overline{AB}\\
\overline{XY}&=\overline{ZW}=\overline{BC}\\
\overline{WY}&=\overline{XZ}=\overline{CA}.
\end{align*}

Tomemos el punto medio $M$ de $XY$. En $\triangle ZMW$, tenemos que
\begin{align*}
\overline{ZM}&=\overline{AM}\\
\overline{WM}&=\overline{AM}.
\end{align*}

Así, usando la desigualdad del triángulo en $\triangle ZMW$ tenemos que \begin{align*}
2\overline{AM}&=\overline{ZM}+\overline{WM}\\
&\geq \overline{ZW}\\
&=\overline{BC}.
\end{align*}

Esto es una contradicción con la desigualdad $2\overline{AM}<\overline{BC}$ que ya habíamos mostrado.

$\square$

Más problemas

Puedes encontrar más problemas de desigualdades básicas en la sección 7.1 del libro Problem Solving through Problems de Loren Larson. También puedes consultar más técnicas y problemas en el libro Desigualdades de la Olimpiada Mexicana de Matemáticas.

Seminario de Resolución de Problemas: Grupos, anillos y campos

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

En estas entradas hemos visto cómo distintas herramientas de álgebra nos pueden ayudar en la resolución de problemas. En las primeras dos entradas, hablamos de identidades algebraicas básicas y un par de avanzadas. Luego, hablamos de factorización en polinomios y del teorema de la identidad. Ahora platicaremos de cómo estructuras un poco más abstractas nos pueden ayudar. De manera particular, nos enfocaremos en aplicaciones de teoría de grupos a la resolución de problemas. Sin embargo, hacia el final de la entrada también hablaremos un poco acerca de anillos, dominios enteros y campos.

Teoría de grupos básica

Una de las nociones de álgebra abstracta más básicas, y a la vez más flexibles, es la de grupo. La teoría de grupos es muy rica y se estudia a profundidad en un curso de álgebra abstracta o álgebra moderna. Aquí veremos únicamente un poco de esta teoría y algunas aplicaciones a resolución de problemas. Comenzamos con la definición.

Definición. Un grupo es un conjunto no vacío $G$ con una operación binaria $\cdot$ que cumple lo siguiente:

  • Asociatividad: Para cualesquiera elementos $x,y,z$ en $G$ tenemos que $x\cdot (y\cdot z) = (x\cdot y) \cdot z$.
  • Neutro: Existe un elemento $e$ en $G$ tal que $x\cdot e = x = e\cdot x$ para todo elemento x.
  • Inversos: Para cada elemento $x$ en $G$, existe un elemento $y$ en $G$ tal que $x\cdot y = e = y\cdot x$.

Usualmente se simplifica la notación de la siguiente manera. Por un lado, en vez de poner el símbolo de producto, simplemente se ponen elementos consecutivos, por ejemplo $a\cdot b = ab$. Además, por la asociatividad, muchas veces no se ponen los paréntesis, de modo que expresiones como $(a\cdot b)\cdot c$ se escriben simplemente como $abc$, a menos que los paréntesis ayuden a entender un argumento.

Hay que tener cuidado con invertir el orden de factores. En grupos, no necesariamente sucede que la operación es conmutativa, es decir, que $ab=ba$ para todo par de elementos $a$ y $b$. Si $ab=ba$ decimos que $a$ y $b$ conmutan y si todo par de elementos de $G$ conmutan, decimos que $G$ es conmutativo. Un elemento siempre conmuta consigo mismo. Para $n$ un entero positivo definimos $a^n$ como el producto formado por $n$ veces el elemento $a$.

A partir de la definición se puede ver que el neutro es único, pues si hubiera dos neutros $e$ y $e’$ tendríamos $e=e\cdot e’=e’$, en donde primero usamos que $e’$ es neutro y después que $e$ lo es. Para $a$ en $G$, definimos $a^0$ como $e$.

En grupos se vale «cancelar». Por ejemplo, si $ab=ac$, entonces podemos multiplicar esta igualdad a la izquierda por un inverso $d$ de $a$ y obtendríamos $$b=eb=dab=dac=ec=c.$$ Del mismo modo, la igualdad $ba=ca$ implica $b=c$.

En particular, si $d$ y $d’$ son inversos de $a$, tenemos $da=e=d’a$, de donde $d=d’$. Esto muestra que los inversos también son únicos, así que al inverso de $a$ le llamamos $a^{-1}$. Observa que $e^{-1}=e$. Nota que si $a$ y $b$ son elementos de $G$, entonces $$ab(b^{-1}a^{-1})=aea^{-1}=aa^{-1}=e,$$ de modo que el inverso de un producto $ab$ es el producto $b^{-1}a^{-1}$. Para $n$ un entero positivo, definimos $a^{-n}$ como el inverso de $a^n$, que por lo anterior, es precisamente $(a^{-1})^n$. De hecho, ya definido $a^n$ para todo entero, se puede verificar que se satisfacen las leyes usuales de los exponentes.

Problema. Sean $a$ y $b$ dos elementos en un grupo $G$ con neutro $e$ tales que $aba=ba^2b$, $a^3=e$ y $b^{2021}=e$. Muestra que $b=e$.

Sugerencia pre-solución. Observa que si $a$ y $b$ conmutaran, entonces el resultado se deduce fácilmente de la primer igualdad. Así, intenta modificar el problema a demostrar que $a$ y $b$ conmutan. Para ello tienes que hacer un paso intermedio que necesita inducción.

Solución. Lo primero que veremos es que $a$ y $b^2$ conmutan. Poniendo una identidad entre ambas $b$ en el producto $ab^2$, tenemos que $$ab^2=abaa^{-1}b=ba^2ba^{-1}b.$$ De $a^3=e$, tenemos $a^{-1}=a^2$, así que siguiendo con la cadena de igualdades, \begin{align*}
ba^2ba^{-1}b&=ba^2ba^2b\\
&=ba^2aba\\
&=bba=b^2a.
\end{align*} Así, $ab^2=b^2a$.

Ahora veremos que $a$ y $b$ conmutan. Para ello, como $a$ y $b^2$ conmutan, tenemos que $a$ y $b^{2k}$ conmutan para cualquier entero $k$. Esto se puede probar por inducción. El caso $k=1$ es lo que ya probamos. Si es válido para cierta $k$, se sigue que $$ab^{2k+2}=b^{2k}ab^2=b^{2k+2}a.$$ Por hipótesis, $b^{2020}=b$, así que el resultado anterior nos dice que $a$ y $b$ conmutan.

Por esta razón, la primer hipótesis $aba=ba^2b$ se puede reescribir como $a^2b=a^2b^2$, que por cancelación izquierda da $e=b$, como queríamos mostrar.

$\square$

Subgrupos y órdenes

Dentro de un grupo pueden vivir grupos más pequeños.

Definición. Un subgrupo de un grupo $G$ es un subconjunto $H$ de $G$ que es un grupo con las operaciones de $G$ restringidas a $H$.

Para que $H$ sea subgrupo, basta con que no sea vacío y que sea cerrado bajo la operación de grupos y la operación «sacar inverso».

Por ejemplo, se puede ver que $\mathbb{Z}_{12}$, los enteros módulo $12$ con la suma, forman un grupo. De aquí, $H_1=\{0,3,6,9\}$ es un subgrupo y $H_2=\{0,4,8\}$ es otro.

Proposición. Si $a$ es un elemento de un grupo $G$, entonces o bien $$1,a, a^2, a^3,\ldots$$ son todos elementos distintos de $G$, o bien existe un entero positivo $n$ tal que $a^n=1$ y $1,a,\ldots,a^{n-1}$ son todos distintos. En este segundo caso, $\{1,a,\ldots,a^{n-1}\}$ es un subgrupo de $G$.

Sugerencia pre-demostración. Divide en casos. Luego, usa el principio de cancelación o las leyes de exponentes para grupos.

Demostración. Si todos los elementos son distintos, entonces no hay nada que hacer. De otra forma, existen $i<j$ tales que $a^j=a^i$, de donde por la ley de cancelación tenemos que $a^{j-i}=e$ y $j-i\geq 1$. Así, el conjunto de enteros positivos $m$ tales que $a^m=e$ es no vacío, de modo que por el principio de buen orden tiene un mínimo, digamos $n$.

Afirmamos que $$1,a,a^2,\ldots,a^{n-1}$$ son todos distintos. En efecto, de no ser así, como en el argumento de arriba existirían $0\leq i < j \leq {n-1}$ tales que $a^{j-i}=e$, pero $j-i\leq n-1$ sería una contradicción a la elección de $n$ como elemento mínimo.

Probemos ahora que $A=\{1,a,\ldots,a^{n-1}\}$ es subgrupo de $G$. Si tenemos $a^k$ y $a^l$ en $A$, su producto es $a^{k+l}$. Por el algoritmo de la división, $k+l=qn+r$, con $r\in \{0,\ldots,n-1\}$, de modo que $$a^ka^l=a^{qn+r}=(a^n)^qa^r=e^qa^r=a^r,$$ así que $A$ es cerrado bajo productos. Además, si $1\leq k\leq n-1$, entonces $1\leq n-k \leq n-1$ y $a^ka^{n-k}=a^n=e$. Así, $A$ es cerrado bajo inversos. Esto muestra que $A$ es subgrupo de $G$.

$\square$

En teoría de grupos, la palabra «orden» se usa de dos maneras. Por un lado si $G$ es un grupo, su orden $\text{ord}(G)$ es la cantidad de elementos que tiene. Por otro, dado un elemento $a$, el orden $\text{ord}(a)$ de $a$ es el menor entero positivo $n$ tal que $a^n=e$, si es que existe.

Definimos al subgrupo generado por $a$ como $$\langle a\rangle:=\{a^n:n\in \mathbb{Z}\}.$$ La proposición anterior dice que si $\langle a \rangle$ es finito, entonces es un subgrupo de $G$ de orden $\text{ord}(\langle a \rangle) = \text{ord}(a).$ A los grupos de la forma $\langle a \rangle$ se les llama cíclicos.

Teorema de Lagrange

Cuando estamos trabajando con grupos finitos, el orden de un subgrupo debe cumplir una condición de divisibilidad.

Teorema (de Lagrange). Sea $G$ un grupo finito y $H$ un subgrupo de $G$. Entonces $\text{ord}(H)$ divide a $\text{ord}(G)$.

No daremos la demostración de este teorema, pero veremos algunos corolarios que sirven en la resolución de problemas.

Proposición. Sea $G$ un grupo finito.

  • Si $\text{ord}(G)$ es un primo $p$, entonces $G$ es cíclico.
  • El orden de cualquier elemento $a$ de $G$ divide al orden de $G$, y por lo tanto $a^{\text{ord}(G)}=1$.
  • Si $a$ es un elemento de $G$ de orden $n$ y $a^m=e$, entonces $n$ divide a $m$.

Demostración. Para la primer parte, si tomamos un elemento $a$ de $G$ que no sea $e$, ya vimos que $\langle a \rangle$ es un subgrupo cíclico de $G$. Por el teorema de Lagrange, su orden debe dividir al primo $p$. Pero el orden de $\langle a \rangle$ es al menos $2$, así que el orden de $\langle a \rangle$ debe ser $p$ y por lo tanto $\langle a \rangle=G$.

Como vimos arriba, el orden de $a$ es el orden de $\langle a \rangle$, que divide a $G$. Así,
\begin{align*}
a^{\text{ord}(G)}&=(a^{\text{ord}{a}})^{\text{ord}(G)/ \text{ord}(a)}\\
&=e^{\text{ord}(G)/ \text{ord}(a)}\\
&=e.
\end{align*} Con esto queda probado el segundo punto.

Para el último punto, usamos el algoritmo de la división para escribir $m=qn+r,$ con $r$ entre $0$ y $n-1$. Tenemos que $$e=a^m=a^{qn+r}=a^r.$$ Por lo visto en la sección anterior, necesariamente $r=0$, así que $n$ divide a $m$.

$\square$

Veamos cómo se pueden aplicar algunas de las ideas anteriores a un problema de teoría de grupos concreto.

Problema. En un grupo $G$, tenemos elementos $a$ y $b$ tales que $a^7=1$ y $aba^{-1}=b^2$. Determina qué posibles valores puede tener el orden de $b$.

Sugerencia pre-solución. Conjetura una fórmula para $b^{2n}$ buscando un patrón. Establécela por inducción.

Solución. El orden de $a$ debe dividir a $7$, así que es o $1$ o $7$. Si es $1$, entonces $a=e$, por lo que por la hipótesis tenemos $b=b^2$. De aquí $b=e$, así que el orden de $b$ es $1$. La otra opción es que el orden de $a$ sea $7$.

Afirmamos que para todo entero $n$ se tiene que $a^nba^{-n}=b^{2^n}$. Esto se prueba inductivamente. Es cierto para $n=1$ por hipótesis. Si se cumple para cierta $n$ y elevamos la igualdad al cuadrado, tenemos que
\begin{align*}
b^{2^{n+1}}&=(b^{2n})^2\\
&=a^nba^{-n}a^nba^{-n}\\
&=a^nb^2a^{-n}\\
&=a^{n+1}ba^{-(n+1)},
\end{align*}

lo cual termina la inducción.

En particular, para $n=7$ tenemos que $a^7=a^{-7}=e$, por lo que $b=b^{2^7}$, y por lo tanto $b^{127}=e$. Como $127$ es primo, el orden de $b$ puede ser $1$ ó $127$.

$\square$

En realidad, en el problema anterior falta mostrar que en efecto existe un grupo que satisfaga las hipótesis, y para el cual el orden de $b$ sea exactamente $127$. Esto no lo verificaremos aquí.

Teoría de grupos en teoría de números

Lo que hemos platicado de teoría de grupos se vale para grupos en general. Cuando aplicamos estos resultados a grupos particulares, tenemos nuevas técnicas para resolver problemas. Uno de los casos que aparecen más frecuentemente es aplicar teoría de grupos en problemas de teoría de números.

Si tomamos un entero $n$, los enteros entre $1$ y $n-1$ que son primos relativos con $n$ forman un grupo con la operación de producto módulo $n$. Si llamamos $\varphi(n)$ a la cantidad de primos relativos con $n$ entre $1$ y $n-1$, el teorema de Lagrange da el siguiente corolario.

Teorema (de Euler). Para todo entero positivo $n$ y $a$ un entero primo relativo con $n$, se tiene que $$a^\varphi(n)\equiv 1\pmod n.$$

Como corolario al teorema de Euler, tenemos el pequeño teorema de Fermat, que hemos discutido previamente aquí en el blog.

Teorema (pequeño teorema de Fermat). Para $p$ un primo y $a$ un entero que no sea múltiplo de $p$, se tiene que $$a^{p-1}\equiv 1 \pmod p.$$

Así, cuando $p$ es primo y $a$ no es múltiplo de $p$, se tiene que el orden de $a$ divide a $p-1$. Veamos un ejemplo en donde esta idea forma parte fundamental de la solución.

Problema. Muestra que para ningún entero $n>1$ se tiene que $n$ divide a $2^n-1$.

Sugerencia pre-solución. Procede por contradicción, suponiendo que sí existe. Considera un primo $p$ que divida a $n$ y que además sea extremo en algún sentido. Trabaja módulo $p$.

Solución. Supongamos que existe un entero $n>1$ tal que $n$ divide a $2^n-1$. Sea $p$ el primo más pequeño que divide a $n$. Tomemos $a$ el orden de $2$ en el grupo multiplicativo $\mathbb{Z}_p$.

Por un lado, como $p$ divide a $n$ y $n$ divide a $2^n-1$, se tiene que $p$ divide a $2^n-1$ y por lo tanto $$2^n\equiv 1 \pmod p.$$ De esta forma, $a$ divide a $n$.

Por otro lado, por el pequeño teorema de Fermat, tenemos que $$2^{p-1}\equiv 1 \pmod p,$$ así que $a$ divide a $p-1$ y por lo tanto $a\leq p-1$.

Si $a\neq 1$, entonces $a$ tiene un divisor primo que divide a $n$ y es menor que $a\leq p-1$, lo cual es imposible pues elegimos a $p$ como el menor divisor primo de $n$. De esta forma, $a=1$. Pero esto da la contradicción $2\equiv 1 \pmod p$.

$\square$

Anillos, dominios enteros y campos

Cuando se están resolviendo problemas, es importante tener en mente que existen otras estructuras algebraicas. Definiremos sólo las más comunes y veremos un problema ejemplo.

Definición. Un anillo es un conjunto $R$ con dos operaciones binarias suma y producto tales que:

  • $R$ con la suma es un grupo conmutativo.
  • El producto en $R$ es asociativo, es decir $(ab)c=a(bc)$ para $a,b,c$ en $R$.
  • Se cumple la ley distributiva, es decir $a(b+c)=ab+ac$ y $(b+c)a=ba+ca$ para $a,b,c$ en $R$.

El producto en $R$ no tiene por qué ser un grupo. De hecho, ni siquiera tiene que tener neutro.

Definición. Si un anillo $R$ tiene neutro, decimos que $R$ es un anillo con $1$. Si la multiplicación de $R$ es conmutativa, decimos que $R$ es conmutativo.

Definición. Un dominio entero es un anillo conmutativo con uno en donde además se vale cancelar, es decir, $ab=ac$ implica $b=c$ y $ba=ca$ implica $b=c$.

Definición. Un campo es un anillo conmutativo con uno en donde cada elemento distinto de la identidad aditiva tiene inverso multiplicativo. En otras palabras, es un anillo en donde la suma y el producto son grupos.

Problema. Muestra que todo dominio entero finito es un campo.

Sugerencia pre-solución. Usa el principio de las casillas.

Solución. Supongamos que $R=\{a_1,\ldots,a_n\}$ es un dominio entero con una cantidad finita de elementos. Lo único que falta para que sea campo es que los elementos tengan inversos multiplicativos.

Sea $a$ un elemento de $R$ y supongamos que $a$ no tiene inverso multiplicativo. Entonces, los números $$a_1a, a_2a,\ldots,a_n a$$ sólo pueden tomar a lo más $n-1$ valores diferentes, de modo que por principio de las casillas existen dos de ellos que son iguales, digamos $a_ia=a_ja$ para $i\neq j$.

Como $R$ es dominio entero, se vale cancelar, lo cual muestra $a_i=a_j$. Esto es una contradicción, pues $a_i$ y $a_j$ eran elementos distintos de $R$. Así, todo elemento tiene inverso multiplicativo.

$\square$

En cursos de matemáticas a nivel superior se ven muchos ejemplos de estas estructuras algebraicas. En cursos de Álgebra Superior se construye el dominio entero de enteros $\mathbb{Z}$. Se construyen los campos $\mathbb{R}$, $\mathbb{Q}$ y $\mathbb{C}$. También, se construyen los anillos de polinomios $\mathbb{F}[x]$. La noción de campo es fundamental cuando se construye la teoría de Álgebra Lineal. Como se puede ver, la teoría de álgebra es muy amplia, así que esta entrada sólo queda como invitación al tema.

Más problemas

Puedes encontrar más problemas de estructuras algebraicas en la Sección 4.4 del libro Problem Solving through Problems de Loren Larson.