Archivo de la categoría: Matemáticas

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

Seminario de Resolución de Problemas: Principio de inducción combinado con heurísticas

Por Leonardo Ignacio Martínez Sandoval

3 respuestas

Introducción

En esta entrada continuaremos con ejemplos de uso del principio de inducción en la resolución de problemas. Es una continuación de la entrada anterior. Como recordatorio, aquí está el principio de inducción en la forma en la que lo hemos estado usando:

Principio de inducción. Sea $P(n)$ una afirmación (o proposición o propiedad) que depende del número natural $n$. Si

  • la afirmación $P(a)$ es cierta y
  • la veracidad de la afirmación $P(n)$ implica la veracidad de la afirmación $P(n+1)$,

entonces la afirmación $P(n)$ es cierta para toda $n \geq a$.

Lo que nos interesa ahora es ver cómo el principio de inducción se mezcla con algunas de las heurísticas de resolución de problemas.

Inducción y trabajar hacia atrás

Lo que hemos hecho hasta ahora es lo siguiente. Tomamos un enunciado que depende de un entero $n$. Comenzamos probándolo para la base inductiva. Luego, suponemos la veracidad del enunciado para cierto entero $n$. A partir de ahí, intentamos conseguir la veracidad del enunciado para el entero $n+1$.

Como vimos cuando platicamos de trabajar hacia atrás, eso no siempre es lo más natural en la resolución de un problema. En algunas ocasiones nos conviene más empezar con el enunciado que queremos demostrar y mostrar que mediante pasos reversibles podemos llegar a algo cierto. Queremos aplicar esta idea para la demostración del paso inductivo.

Consideremos el siguiente ejemplo.

Problema. Demuestra que para todo entero no negativo $n$ se tiene que $$\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}$$ es un número entero.

Solución. Tenemos que probar la afirmación para $n\geq 0$ entero. Procedemos por inducción sobre $n$. Si $n=0$, la expresión es igual a $0$, así que la afirmación es cierta. Supongamos entonces que
$$\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}$$ es entero y consideremos la expresión
$$\frac{(n+1)^5}{5}+\frac{(n+1)^4}{2}+\frac{(n+1)^3}{3}-\frac{(n+1)}{30}.$$

Nuestro objetivo es mostrar que esta expresión es entera. Nos gustaría usar la hipótesis inductiva, así que queremos intentar encontrar dentro de esta expresión la expresión para $n$. Esto lo podemos hacer usando el binomio de Newton para abrir los binomios a potencias y luego agrupando. Tenemos que

\begin{align*}
\frac{(n+1)^5}{5}&=\frac{n^5+5n^4+10n^3+10n^2+5n+1}{5}\\
&=\frac{n^5}{5}+n^4+2n^3+2n^2+n+\frac{1}{5}\\
\frac{(n+1)^4}{2}&=\frac{n^4+4n^3+6n^2+4n+1}{2}\\
&=\frac{n^4}{4}+2n^3+3n^2+2n+\frac{1}{2}\\
\frac{(n+1)^3}{3}&=\frac{n^3+3n^2+3n+1}{3}\\&
=\frac{n^3}{3}+n^2+n+\frac{1}{3}\\
-\frac{n+1}{30}&=-\frac{n}{30}-\frac{1}{30}.
\end{align*}

Así, cuando hagamos la suma tenemos los términos
$$\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30},$$ cuya suma es entera por hipótesis inductiva, $$n^4+2n^3+2n^2+n+2n^3+3n^2+2n+n^2+n,$$ que es entero pues $n$ es entero y $\frac{1}{5}+\frac{1}{2}+\frac{1}{3}-\frac{1}{30}=1$, de modo que la suma total es suma de enteros y por lo tanto es un entero. Esto termina la prueba por inducción.

$\square$

Si no comenzábamos a manipular la expresión para $n+1$, hubiera sido muy difícil, sólo a partir de la de $n$, llegar a la de $n+1$.

Inducción y generalización

Una forma sencilla de combinar inducción con generalización es la siguiente:

  • Nos piden demostrar una afirmación para un natural muy específico.
  • En vez de eso, construimos un problema más general que funcione «para todos los naturales».
  • Resolvermos ese problema por inducción.

Veamos un ejemplo.

Problema. Muestra que $$\left(\frac{3+\sqrt{17}}{2}\right)^{2020}+
\left(\frac{3-\sqrt{17}}{2}\right)^{2020}$$ es un entero impar.

Solución. Sean $\alpha=\frac{3+\sqrt{17}}{2}$ y $\beta=\frac{3-\sqrt{17}}{2}$. Se pide mostrar que $\alpha^{2020}+\beta^{2020}$ es un entero impar. Mostraremos que, de hecho, $\alpha^n+\beta^n$ es un entero impar para todo entero $n\geq 1$. Vamos a proceder por inducción fuerte (hablaremos un poco más de eso más adelante).

El primer caso es $n=1$ y notemos que $\alpha^1+\beta^1=\alpha+\beta=3.$ Notemos también que $\alpha\beta=\frac{9-17}{4}=-2$, de modo que $\alpha^2+\beta^2=(\alpha+\beta)^2-2ab=9+4=13$, que también es impar. Supongamos ahora que sabemos que la afirmación es cierta para exponentes $n-1$ y $n$.

Consideremos el polinomio cuadrático $$(x-\alpha)(x-\beta)=x^2-(\alpha+\beta)x+\alpha\beta=x^2-3x-2.$$ Como $\alpha$ y $\beta$ son raíces, tenemos que $\alpha^2-3\alpha-2=0$ y $\beta^2-3\beta -2=0$. Multiplicando estas igualdades por $\alpha^{n-1}$ y $\beta^{n-1}$ respectivamente, sumando ambas igualdades obtenidas, y despejando $\alpha^{n+1}+\beta^{n+1}$ llegamos a $$\alpha^{n+1}+\beta^{n+1}=3(\alpha^n+\beta^n)+2(\alpha^{n-1}+\beta^{n-1}).$$

De aquí la conclusión inductiva es inmediata. Como la hipótesis inductiva es que el resultado es cierto para los exponentes $n$ y $n-1$, entonces en el lado derecho tenemos una suma de un entero impar con un entero par, que es un entero impar. Esto muestra que la afirmación es cierta para cuando los exponentes son $n+1$.

Para demostrar el problema original, basta con hacer la observación de que, en particular, $\alpha^{2020}+\beta^{2020}$ es un entero impar.

$\square$

Hay otra forma de combinar inducción con generalización, pero es un poco más sofisticada. Para explicarla, es mejor comenzar con un ejemplo.

Problema. Demuestra que para todo entero $n\geq 1$ se tiene que $$\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+\ldots + \frac{1}{n(n+1)} <1.$$

Antes de resolver el problema, intentemos hacer una solución «ingenua» que quiera usar inducción de manera directa. No hay ningún problema con hacer la base de inducción, pues para $n=1$ al lado izquierdo tenemos únicamente $\frac{1}{2}$ y al lado derecho $1$. Supongamos que el resultado es cierto para $n$, es decir, que $$\frac{1}{1\cdot 2}+\ldots + \frac{1}{n(n+1)} <1.$$

Llamémosle $M$ a la expresión del lado izquierdo. Lo que queremos probar ahora es que el resultado es cierto para $n+1$, es decir, que $M+\frac{1}{(n+1)(n+2)}<1$. Sabemos que $M<1$, pero ahora estamos sumando un término positivo adicional. Es posible que este término arruine la desigualdad, pues $M<1$ es una afirmación «muy débil». Veamos cómo darle la vuelta a esta dificultad.

Solución. Sea $P(n)$ la afirmación del problema. Consideremos la afirmación $Q(n)$ que dice que para todo entero $n\geq 1$ se tiene que
$$\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\ldots + \frac{1}{n(n+1)} =1-\frac{1}{n+1}.$$

Si logramos demostrar $Q(n)$, entonces $P(n)$ será cierta de manera inmediata, pues $1-\frac{1}{n+1}<1$. Vamos a demostrar $Q(n)$ por inducción.

Tenemos que $Q(1)$ es cierto pues en ambos lados de la igualdad queda $\frac{1}{2}$. Supongamos que $Q(n)$ es cierto. Usando esto, tenemos que
\begin{align*}
\frac{1}{1\cdot 2}+\ldots+\frac{1}{n(n+1)} + \frac{1}{(n+1)(n+2)} &=\left(1-\frac{1}{n+1}\right)+\frac{1}{(n+1)(n+2)}\\
&=1-\frac{(n+2)-1}{(n+1)(n+2)}\\
&=1-\frac{1}{n+2},
\end{align*}

es decir, que $Q(n+1)$ es cierto. Así, por inducción $Q(n)$ es cierto para todo entero $n$ y con eso $P(n)$ también.

$\square$

Lo que sucedió fue lo siguiente. Al hacer el paso inductivo, intentamos mostrar que $P(n)$ implica $P(n+1)$. Pero esto es imposible pues $P(n)$ «es muy débil», o bien «pierde información de todo lo que está pasando». Sin embargo, cuando consideramos la afirmación auxiliar $Q(n)$, resulta que esta «tiene más información». Aquí, esta información es «qué tal lejos está la expresión de $1$ «

La afirmación $Q(n)$ tiene tanta información, que ahora sí con ella se puede probar $Q(n+1)$. Se termina el problema usando que $Q(n)$ implica $P(n)$. Así, la estrategia fue la siguiente:

  • Se tiene una afirmación $P(n)$ que se quiere demostrar para todos los naturales. Hacer inducción no parece funcionar, pues $P(n)$ parece no ser suficiente para probar $P(n+1)$
  • Se considera entonces una afirmación $Q(n)$ más fuerte (que implique a $P(n)$), pero para la cual $Q(n)$ sí pueda probar $Q(n+1)$.
  • Se prueba $Q(n)$ por inducción, y se concluye que $P(n)$ es cierta.

Hay que ser cuidadosos. Parte del ingenio en usar esta estrategia consiste en poder identificar un balance en la generalización $Q(n)$ que necesitamos de modo que sí sirva para solucionar el problema original, pero que no sea demasiado ambiciosa como para que sea falsa.

Más ejemplos

Hay más ejemplos bastante elaborados del uso de estas ideas en Problem Solving Through Problems de Loren Larson, Secciones 2.1, 2.2, 2.3 y 2.4. Otro libro con muchos ejemplos interesantes es el Putnam and Beyond, de Gelca y Andreescu. También hay otros ejemplos de inducción en las siguientes entradas:

Álgebra Lineal I: Forma matricial de una transformación lineal

Por Ayax Calderón

5 respuestas

Introducción

Durante la primera unidad de este curso vimos que las transformaciones lineales $T:F^n \to F^m$ pueden ser descritas por medio de matrices $A\in M_{m,n}(F)$. Nuestro objetivo ahora es extender este resultado para describir transformaciones lineales $T:V\to W$ entre espacios vectoriales de dimensión finita $V$ y $W$. Es decir, para cada una de estas transformaciones, queremos ver cómo se ven en forma matricial.

Sin embargo, a diferencia de lo que sucedía antes, la descripción en esta forma no será única. Para construir una matriz que represente a una transformación lineal, necesitaremos fijar bases para $V$ y $W$. Distintas bases nos darán distintas matrices.

Para esta entrada todos los espacios vectoriales que usemos son de dimensión finita sobre el campo $F$. Usaremos los resultados de la entrada pasada, en la que estudiamos qué le hacen las transformaciones lineales a los conjuntos linealmente independientes, a los generadores y a las bases.

Un paréntesis técnico de isomorfismos

Quizás a estas alturas ya te hayas dado cuenta de que, en cierto sentido, los espacios vectoriales con la misma dimensión se parecen mucho entre sí. Por ejemplo, los espacios vectoriales $\mathbb{R}^4$, $M_2(\mathbb{R}) $ y $\mathbb{R}_3[x]$ pueden pensarse «como el mismo» si identificamos a cada vector $(a,b,c,d)$ con la matriz $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$, o bien con el polinomio $a+bx+cx^2+dx^3$. Esta identificación es biyectiva y «respeta las operaciones».

Con esta motivación, veamos una definición formal.

Definición. Decimos que una transformación lineal $T:V\to W$ es un isomorfismo de espacios vectoriales si es biyectiva. Lo denotamos como $V\simeq_{T} W$, que se lee «$V$ isomorfo a $W$ mediante $T$».

Problema. Sea $T:V\to W$ un isomorfismo de espacios vectoriales. Prueba que su inversa $T^{-1}:W\to V$ es un isomorfismo de espacios vectoriales.

Demostración. La transformación $T^{-1}$ es biyectiva, pues es invertible de inversa $T$, así que sólo hace falta checar que $T^{-1}$ es lineal. Tomemos $w_1$, $w_2$ en $W$, y $c$ en el campo. Como $T$ es suprayectiva, podemos tomar $v_1=T^{-1}(w_1)$ y $v_2=T^{-1}(w_2)$. Entonces $T(v_1)=w_1$ y $T(v_2)=w_2$, así
\begin{align*}
T^{-1}(w_1+cw_2)&=T^{-1}(T(v_1)+cT(v_2))\\
&=T^{-1}(T(v_1+cv_2))\\
&=v_1+cv_2
\end{align*}

En la segunda igualdad estamos usando que $T$ es lineal. De esta forma, concluimos que $T^{-1}$ es lineal también.

$\square$

Formalicemos ahora sí nuestra intuición de que «todos los espacios vectoriales de la misma dimensión finta $n$ sobre un mismo campo se comportan igual». En términos matemáticos, decimos que «es posible clasificar los espacios vectoriales de dimensión finita distintos de $\{0\}$, salvo isomorfismos». Para mostrar esto, veremos que para cada entero positivo $n$ todos los espacios vectoriales de dimensión $n$ son isomorfos a $F^n$. El siguiente resultado da el isomorfismo de manera explícita.

Teorema. Sea $n$ un entero positivo y sea $V$ un espacio vectorial de dimensión finita sobre $F$. Si $B={e_1,\dots,e_n}$ es una base de $V$, entonces la transformación $i_B:F^n\to V$ definida por $$i_B(x_1,\dots,x_n)=x_1e_1+x_2e_2+\dots+x_ne_n$$ es un isomorfismo de espacios vectoriales.

La verificación de los detalles de este teorema queda como tarea moral. Como sugerencia, recuerda que una base $B$ de $V$ te permite expresar a cada vector de $V$ (de aquí saldrá la suprayectividad) de manera única (de aquí saldrá la inyectividad) como combinación lineal de elementos de $B$.

Corolario. Si $T:V\to W$ es un isomorfismo de espacios vectoriales, entonces $\dim V=\dim W$.

Bases ordenadas

Sea $V$ un espacio vectorial de dimensión finita $n$. Una base ordenada de $V$ es simplemente una base para la cual nos importa en qué orden están sus elementos. La escribimos con notación de paréntesis en vez de llaves, es decir, en vez de poner $B=\{v_1,\ldots,v_n\}$, ponemos $B=(v_1,\ldots,v_n)$ para hacer énfasis en el orden.

Ejemplo 1. El conjunto $\{(1,2),(3,4)\}$ es una base de $\mathbb{R}^2$. De aquí, podemos obtener dos bases ordenadas, $B=((1,2),(3,4))$ y $B’=((3,4),(1,2))$. Aunque tienen a los mismos elementos, las pensamos como bases ordenadas diferentes pues sus elementos aparecen en diferente orden.

Del mismo modo, las bases $B=(1,x,x^2,x^3)$ y $B’=(x^3,x^2,x,1)$ son la misma base de $\mathbb{R}_2[x]$, pero son distintas como bases ordenadas.

$\triangle$

Por las discusión en la sección anterior, la elección de una base ordenada en un espacio vectorial $V$ de dimensión $n$ nos permite identificar $V$ con $F^{n}$. Es decir, dada una base $B$, podemos «ponerle coordenadas» a los elementos de $V$. Dependiendo de la base ordenada escogida, es posible que obtengamos diferentes coordenadas.

Ejemplo 2. Consideremos el espacio vectorial $M_2(\mathbb{R})$. Se puede verificar que cada uno de los siguientes conjuntos ordenados son una base:

\begin{align*}
B&=\left(\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix},\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix},\begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix},\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}\right)\\
B’&=\left(\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix},\begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix},\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix},\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}\right)\\
B»&=\left(\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix},\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix},\begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix},\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}\right)
\end{align*}

Como cada uno de ellos es una base, entonces podemos escribir a la matriz $A=\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$ como combinación lineal de elementos de cada uno de $B$, $B’$ o $B»$.

Si lo hacemos para $B$, tendríamos (en orden), a los coeficientes $1,2,3,4$, así que las coordenadas de $A$ en la base ordenada $B$ serían $(1,2,3,4)$.

Si lo hacemos para $B’$, tendríamos (en orden), a los coeficientes $1,3,2,4$, así que las coordenadas de $A$ en la base ordenada $B’$ serían $(1,3,2,4)$. Aunque $B$ y $B’$ tengan los mismos elementos, las coordenadas difieren pues como bases ordenadas $B$ y $B’$ son distintas.

Si lo hacemos para $B»$, tendríamos (en orden), a los coeficientes $1,1,1,1$, así que las coordenadas de $A$ en la base ordenada $B»$ serían $(1,1,1,1)$. Aquí obtenemos coordenadas muy distintas pues $B$ y $B»$ ni siquiera tienen a los mismos elementos.

$\triangle$

La forma matricial de una transformación lineal

Consideremos ahora espacios vectoriales $V$ y $W$ de dimensiones $n$ y $m$ respectivamente. Supongamos que tenemos una transformación lineal $T:V\to W$. Escogemos bases ordenadas $B_V=(v_1,\dots, v_n)$ y $B_W=(w_1,\dots,w_m)$ de $V$ y $W$ respectivamente. Ten cuidado, aquí $(v_1,\dots, v_n)$ no es un vector de $F^n$, sino una colección ordenada de vectores de $V$.

Por el teorema de caracterización de espacios vectoriales de dimensión finita, tenemos los isomorfismos $$i_{B_{V}}:F^n\to V,$$ $$i_{B_{W}}:F^m\to W.$$

¿Cómo podemos usar todas estas transformaciones para construir una transformación $F^n\to F^m$? La idea es usar el inverso de $i_{B_W}$ y componer todo.

Así, consideramos $\psi_T$ como la composición de las transformaciones $i_{B_{V}}, T, i_{B_{W}}^{-1}$, es decir, $$\psi_T:F^n\to F^m,$$ está dada por $$\psi_T=i_{B_W}^{-1}\circ T\circ i_{B_{V}}.$$

De esta forma, $\psi_T$ es una transformación lineal entre $F^n$ y $F^m$. ¡Este tipo de transformaciones ya las conocemos! Sabemos que $\psi_T$ se describe de manera única por medio de una matriz $A\in M_{m,n}(F).$ Esta es, por definición, la matriz asociada a $T$ con respecto a las bases $B_V$ y $B_W$ o bien la forma matricial de $T$. Dicha matriz depende fuertemente de las dos bases, así que la denotaremos como $\text{Mat}_{B_W,B_V}(T)$ . Por el momento sólo pongamos mucha atención en el orden en el que escribimos las bases en los subíndices. Es importante más adelante veremos que resulta útil escribirlo así.

Cuando $T:V\to V$ va de un espacio vectorial a sí mismo y usamos sólo una base $B$, simplificamos la notación a $\text{Mat}_B(T)$.

Evaluar $T$ usando su forma matricial

La construcción anterior parece muy complicada, pero en realidad es muy natural. Lo que está sucediendo es lo siguiente. Ya sabemos que toda transformación lineal entre $F^n$ y $F^m$ está dada por matrices. Podemos extender esto a una descripción de transformaciones lineales entre $V$ y $W$ identificando $V$ con $F^n$ y $W$ con $F^m$ vía la elección de bases en $V$ y $W$.

Notemos que si definimos $A:=\text{Mat}_{B_{W},B_{V}}(T)$, entonces tenemos que

$i_{B_{W}}(Ax)=T(i_{B_{V}}(x))$ … (1)

Esta igualdad nos va a ayudar a decir quién es $T$ en términos de las entradas de la matriz $A$. Sea $\{e_1,\dots,e_n\}$ la base canónica de $F^n$ y $\{f_1,\dots,f_m\}$ la base canónica de $F^m$. Si$ A=[a_{ij}]$, entonces por definición $Ae_i=a_{1i}f_1+\dots+a_{mi}f_{m}$, así para $x=e_i$ se tiene

$i_{B_{W}}(Ax)=i_{B_{W}}(a_{1i}f_1+\dots + a_{mi}f_m) = a_{1i}w_1+\dots + a_{mi}w_m.$

Por otro lado, $i_{B_{V}}(e_i)=v_i$, de manera que la relación (1) es equivalente a la relación

$T(v_i)=a_{1i}w_1+\dots + a_{mi}w_m$

Aquí empieza a haber mucha notación, pero no hay que perderse. Hasta ahora lo que tenemos es que «podemos saber cuánto vale la transformación $T$ en cada elemento de la base de $V$ en términos de la matriz $A$». ¡Este es un paso importante, pues en la entrada anterior vimos que basta saber qué le hace una transformación a los elementos de la base para saber qué le hace a cualquier vector! Resumimos lo obtenido hasta ahora.

Proposición. Sea $T:V\to W$ una transformación lineal y sean $B_V=\{v_1,\dots v_n\}, B_W=\{w_1,\dots,w_m\}$ bases en $V$ y $W$, respectivamente. Escribamos $\text{Mat}_{B_W,B_V}(T)=[a_{ij}]$. Entonces para toda $1\leq i\leq n$ se tiene $$T(v_i)=\displaystyle\sum_{j=1}^m a_{ji}w_j.$$

Así, si tenemos la matriz $A$ que representa a $T$ en las bases $B_V$ y $B_W$ y un vector arbitrario $v$ en $V$, para saber quién es $T(V)$ basta:

  • Usar la proposición anterior para saber quién es $T(v_i)$ para cada $v_i$ en la base $B_V$.
  • Expresar a $v$ en términos de la base $B_V$ como, digamos, $v=c_1v_1+\ldots+c_nv_n$.
  • Usar que $T$ es lineal para concluir que $T(v)=c_1T(v_1)+\ldots+c_nT(v_n)$ y usar los valores de $T(v_i)$ encontrados en el primer inciso.

Forma matricial de composiciones de transformaciones lineales

Para finalizar esta entrada queremos entender la relación entre la composición $S\circ T$ de transformaciones lineales y las matrices asociadas de $T$ y $S$. En otras palabras, sean $T:V\to W$ y $S:W\to U$ transformaciones lineales fijas y supongamos que $m=dimV$, $n=dimW$, $p=dimU$. También fijemos las bases $B_U, B_V, B_W$ en $U,V,W$, respectivamente. Para simplificar las cosas escribamos

$\mathcal{A}=\text{Mat}_{B_U,B_W}(S)$ y $\mathcal{B}=\text{Mat}_{B_W,B_V}(T)$

Con respecto a las bases $B_U,B_V,B_W$ se tienen los isomorfismos $i_{B_U}, i_{B_V}, i_{B_W}$ definidos como lo hicimos anteriormente en esta misma entrada del blog, y por definición de $\mathcal{A}, \mathcal{B}$ se tiene

$i_{B_W}(\mathcal{B}x)=T(i_{B_V}(x))$ con $x\in F^m$,

$i_{B_U}(\mathcal{A}y)=S(i_{B_W}(y))$ con $y\in F^n$.

Aplicando $S$ en la primera relación y después usando la segunda relación, se tiene para $x\in F^m$

$(S\circ T)(i_{B_V}(x))=S(i_{B_W}(\mathcal{B}x))=i_{B_U}(\mathcal{A} \mathcal{B}x)$.

Esta última relación y la definición de $\text{Mat}_{B_U,B_V}(S\circ T)$ nos muestra que

$\text{Mat}_{B_U,B_V}(S\circ T)=\mathcal{A} \cdot \mathcal{B}$.

En otras palabras, la composición de transformaciones lineales se reduce a multiplicar sus matrices asociadas o de manera más formal

Teorema. Sean $T:V\to W$ y $S:W\to U$ transformaciones lineales entre espacios vectoriales de dimensión finita y sean $B_U, B_V, B_W$ bases de $U,V,W$, respectivamente. Entonces

$\text{Mat}_{B_U,B_V}(S\circ T)=\text{Mat}_{B_U,B_W}(S)\cdot \text{Mat}_{B_W,B_V}(T).$

Cuando tenemos transformaciones lineales de un espacio vectorial $V$ a sí mismo, y usamos la misma base $B$, el resultado anterior se puede escribir de una manera más sencilla.

Corolario. Sean $T_1,T_2:V\to V$ transformaciones lineales en un espacio vectorial de dimensión finita $V$, y sea $B$ una base de $V$. Entonces

$\text{Mat}_{B}(T_1\circ T_2)=\text{Mat}_{B}(T_1)\cdot \text{Mat}_{B}(T_2)$.

Más adelante…

En esta entrada comenzamos con una transformación lineal $T:V\to W$ y bases ordenadas de de $V$ y $W$ para representar a $T$ como una matriz. Así mismo, vimos cómo tras una elección de base podemos pensar a cualquier vector en términos de sus «coordenadas», usando a los coeficientes que permiten expresarlo (de manera única) como combinación lineal de elementos de la base. Las matrices y coordenadas que así obtenemos nos ayudarán mucho. Sin embargo, será fundamental entender qué es lo que sucede con estas representaciones cuando elegimos bases diferentes, y cómo podemos cambiar de ciertas coordenadas o matrices a otras cuando hacemos un cambio de base. Esto es lo que estudiaremos en las siguientes entradas.

Tarea moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  • Verifica que la relación «son isomorfos» para espacios vectoriales es una relación de equivalencia.
  • Muestra que la transformación $i_B$ dada en el teorema de clasificación de espacios vectoriales de dimensión finita en efecto es un isomorfismo.
  • Asegúrate de entender el último corolario.

Entradas relacionadas

Agradecimientos

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

Álgebra Superior II: Teoremas de Fermat y de Wilson

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

En las entradas anteriores hablamos de congruencias, del anillo de enteros módulo $n$ y vimos algunos problemas. La gran ventaja de trabajar en $\mathbb{Z}_n$, o bien, de trabajar módulo $n$, es que para $n$ pequeña hay una cantidad pequeña de elementos y entonces las operaciones se vuelven muy sencillas.

Problema. Determina cuál es el residuo obtenido de dividir $705\cdot 702+714\cdot 711$ al dividirse entre $7$.

Solución. Tenemos que $705$, $702$, $714$ y $711$ los podemos poner como un múltiplo de $7$ más un residuo como sigue: $700+5$, $700+2$ y $714=714+0$, $711=707+4$. Así, $705\equiv 5\pmod 7$, $702\equiv 2 \pmod 7$, $714\equiv 0 \pmod 7$ y $711\equiv 4 \pmod 7$. Así, trabajando módulo $7$ tenemos que:

\begin{align*}
705\cdot 702+714\cdot 711 \equiv 5\cdot 2 + 0\cdot 4 \equiv 10 + 0 \equiv 10 \equiv 3 \pmod 7
\end{align*}
De esta forma, $705\cdot 702+714\cdot 711$ deja residuo $3$ al dividirse entre $7$.

$\square$

Trabajando de esta forma, podemos encontrar el residuo al dividirse por $n$ de expresiones que involucran sumas y productos. El objetivo de esta entrada es entender qué sucede cuando queremos encontrar el residuo de expresiones que tienen potencias y factoriales.

Pequeño teorema de Fermat

Intentemos entender qué sucede con las potencias de un número $a$ en cierto módulo $n$.

Ejemplo. Imagina que tomamos al número $3$ y queremos elevarlo a distintas potencias y entender el residuo que deja al dividirse entre $7$. Tenemos, trabajando módulo $7$:
\begin{align*}
3^0\equiv 1\\
3^1\equiv 3\\
3^2\equiv 9 \equiv 2\\
3^3=27\equiv 21+6\equiv 6
\end{align*}

Nota que podríamos seguir, poniendo $3^4=81$. Pero podemos ahorrarnos trabajo pues $3^4\equiv 3\cdot 3^3 \equiv 3 \cdot 6 \equiv 18\equiv 4$, en donde usamos que ya sabíamos que $3^3\equiv 6$. Del mismo modo, podemos seguir substituyendo cada potencia en la siguiente para obtener
\begin{align*}
3^5\equiv 3\cdot 4\equiv 12\equiv 5\\
3^6\equiv 3\cdot 5 = 15\equiv 1\\
3^7\equiv 3\cdot 1 = 3\\
3^8\equiv 3\cdot 3 = 9 \equiv 2
\end{align*}

Podríamos seguir y seguir, pero ya no tiene mucho caso. A partir de aquí es fácil convencerse de que los residuos se ciclan: $1,3,2,6,4,5,1,3,2,6,4,5,1\ldots$. Notemos que si la potencia es múltiplo de $6$, entonces el residuo será $1$, es decir, $3^{6k}\equiv 1 \pmod 7$. Esto es fantástico, pues entonces si queremos determinar el residuo de dividir, digamos, $3^{605}$ entre $7$, basta ver que módulo $7$ tenemos $$3^{605}=3^{600}\cdot 3^5 \equiv 1\cdot 5 \equiv 5,$$

en donde estamos usando lo que mencionamos para $k=100$ y que ya hicimos $3^5$ módulo $7$.

A partir del ejemplo anterior, nos damos cuenta de que es importante saber cuándo $a^m\equiv 1\pmod n$, pues en ese momento las potencias «se empiezan a ciclar». El pequeño teorema de Fermat es un resultado que podemos aplicar cuando trabajamos módulo un número primo $p$. Dice que la potencia $p-1$ funciona para esto.

Teorema. Si $p$ es un número primo y $p$ no divide a $a$, entonces $p$ divide a $a^{p-1}-1$ o, dicho en otras palabras $a^{p-1}\equiv 1 \pmod p$.

Demostración. Afirmamos que los números $a$, $2a$, $3a$, $\ldots$, $(p-1)a$ dejan todos ellos residuos distintos al dividirse entre $p$ y, además, que ninguno de esos residuos es $0$. Probemos esto. Tomemos $0<i<j<p-1$. En una entrada anterior vimos que $[a]_p$ tiene inverso en $Z_p$. Sea $[b]_p$ su inverso. Si $[ia]_p=[ja]_p$, entonces multiplicando por $[b]_p$ de ambos lados tendríamos $$[i]_p=[i(ab)]_p=[j(ab)]_p=[j]_p.$$

Pero como $i$ y $j$ están entre $1$ y $p-1$, esto implica que $i=j$. Ninguno es cero pues si $[ia]_p=[0]_p$, entonces al multiplicar por $b$ tendríamos la contradicción $[i]_p=[i(ab)]_p=[0b]_p=[0]_p$. Esto muestra la afirmación.

Así, usando la afirmación en el segundo paso de la siguiente cadena módulo $p$, tenemos:
\begin{align*}
(p-1)! a^{p-1} &= (a)(2a)(3a)\cdots((p-1)a)\\
&\equiv 1\cdot 2 \cdot \ldots \cdot (p-1)\\
&= (p-1)!.
\end{align*}

El número $(p-1)!$ no es divisible entre $p$, pues es producto de puros números menores que $p$, de modo que $\text{MCD}(p, (p-1)!)=1$, así que tiene inverso módulo $p$, de modo que podemos cancelarlo de la congruencia anterior multiplicando en ambos lados por su inverso. De aquí obtenemos la igualdad que queremos: $$a^{p-1}\equiv 1 \pmod p.$$

$\square$

Ya que demostramos este teorema, podemos aprovecharlo para resolver problemas que parecen ser difíciles.

Problema. Demuestra que $13$ divide a $25^{181}-181^{25}$

Solución. Notemos primero que $13$ es primo y que no divide ni a $25$ ni a $181$. Por el pequeño teorema de Fermat, tenemos módulo $13$ que $25^{12}\equiv 1$ y que $181^{12}\equiv 1$. Así, módulo $13$ tenemos que $$25^{181}\equiv 25^{15\cdot 12}\cdot 25 \equiv 25 \equiv 12,$$ y que $$181^{25}\equiv 181^{2\cdot 12}\cdot 181\equiv 181 \equiv 12.$$

De esta forma, $25^{181}-181^{25}\equiv 12-12\equiv 0\pmod {13}$, es decir, $13$ divide a $25^{181}-181^{25}$

$\triangle$

Teorema de Wilson

En la demostración del teorema de Fermat aparece la expresión $(p-1)!$. ¿Qué residuo dejará al dividirse entre $p$? Hagamos una prueba.

Problema. Encuentra el residuo que se obtiene al dividir $10!$ entre $11$.

Solución. Para no trabajar con números tan grandes, notemos que en $$10!=1\cdot 2\cdot 3\cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10$$ podemos cambiar a $6,7,8,9,10$ por $-5, -4, -3, -2, -1$ al trabajar módulo $11$, así que basta encontrar $-(1\cdot 2\cdot 3 \cdot 4 \cdot 5)^2$ módulo $11$. Notemos que $3\cdot 4\equiv 12 \equiv 1 \pmod {11}$ y que $2\cdot 5 =10 \equiv -1 \pmod {11}$. Así, $$10!\equiv -(1\cdot 2\cdot 3 \cdot 4 \cdot 5)^2 \equiv -(1\cdot 1 \cdot -1)^2 \equiv -1 \equiv 10 \pmod {11},$$

es decir, el residuo que deja $10!$ al dividirse entre $11$ es $10$.

$\triangle$

El teorema de Wilson ayuda a cuando queremos encontrar el residuo de un factorial al dividirse entre un número primo. Una de las ideas del ejercicio anterior fue buena: nos conviene agrupar a números del factorial en productos sencillos. Lo más conveniente es que agrupemos a cada número con su inverso multiplicativo, pues así obtendremos un $1$. Eso lo podemos hacer si el inverso es diferente. La siguiente proposición nos ayuda a entender cuándo pasa esto.

Proposición. Sea $p$ un número primo. Los únicos elementos en $\mathbb{Z}_p$ que son inversos de sí mismos son $[1]_p$ y $[p-1]_p$.

Demostración. Claramente $[1]_p$ y $[p-1]_p=[-1]_p$ son inversos multiplicativos de sí mismos, pues $1\cdot 1=1=(-1)\cdot(-1)$. Ahora, si tenemos $a$ tal que $a$ es inverso multiplicativo de sí mismo, tenemos que $[a^2]_p\equiv [1]_p$, que por definición quiere decir que $p$ divide a $a^2-1=(a+1)(a-1)$. Cuando un primo divide a un producto, tiene que dividir a uno de los factores. Entonces $p$ divide a $a+1$ o a $a-1$, y obtenemos, respectivamente, que $[a]_p=[-1]_p=[p-1]_p$ o que $[a]_p=[1]_p$, como queríamos.

$\square$

Estamos listos para enunciar y demostrar el teorema de Wilson.

Teorema. Si $p$ es un número primo, entonces $p$ divide a $(p-1)!+1$ o, dicho en otras palabras, $(p-1)!\equiv -1 \pmod p$.

Demostración. Si $p=2$, el resultado es inmediato. Supongamos que $p\geq 3$. En $(p-1)!$ aparecen todos los números de $1$ a $p-1$. Todos ellos son primos relativos con $p$, así que tienen inverso módulo $p$. Ese inverso también aparece en $(p-1)!$. Así, podemos agrupar esos números en $(p-3)/2$ parejas de inversos multiplicativos, en donde por la proposición anterior sólo nos va a sobrar el $1$ y el $-1$. De esta forma, $$(p-1)!\equiv (1)(-1)(1\cdot 1\cdot \ldots\cdot 1) \equiv -1 \pmod p,$$

en donde en la expresión intermedia tenemos un $1$, un $-1$ y $(p-3)/2$ unos, uno por cada pareja de inversos que se multiplicaron. Esto termina la prueba.

$\square$

Veamos una posible aplicación.

Problema. Determina el residuo que se obtiene al dividir $15!+16!+17!$ entre $17$.

Solución. Notemos que $17$ divide a $17!$, así que $17!\equiv 0 \pmod {17}$. Por el teorema de Wilson, $16!\equiv -1 \pmod {17}$. Podemos multiplicar esa igualdad por $-1$ para obtener módulo $17$ que $$15! = 15! (-1)(-1) \equiv 15! \cdot 16 \cdot (-1) \equiv 16! (-1)\equiv (-1)(-1)\equiv 1.$$ Así, $15!+16!+17!\equiv 1 + (-1) + 0 \equiv 0 \pmod {17}$.

$\square$

Una solución alternativa es darse cuenta de que $$15!+16!+17!=15!(1+16)+17\cdot 16!=17\cdot (15!+16!)$$ y por lo tanto es múltiplo de $17$. Aunque tengamos herramientas fuertes, ¡siempre hay que recordar los básicos!

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

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

Álgebra Superior II: Problemas de congruencias

Por Claudia Silva

2 respuestas

Introducción

Aquí les mando los vídeos correspondientes al día de hoy, jueves 19 de marzo, todos relacionados con congruencias.

Ejercicio. Realizar la tabla de multiplicación módulo 5:

¿Cómo realizar la tabla de multiplicación módulo 5?

Ejercicio 186. Encuentre las unidades de ${\mathbb{Z}}_{18}$, y encuentre un elemento no nulo que no tenga inverso multiplicativo:
Nota: Me equivoqué en un detalle: $(3,18)=3$, no $6$.

Encuentrar las unidades de ${\mathbb{Z}}_{18}$, y un elemento no nulo que no tenga inverso multiplicativo

Ejercicio 191. Demuestra que todo entero es congruente módulo $7$ con un número del siguiente conjunto: $\{193,7,54,31,36,20,765\}$.

Ejercicio de congruencias (191 del libro)

Ejercicio 193. Muestra que para $a$ y $b$ enteros, si $a \equiv b \pmod m$, entonces $(a,m)\mid(b,m)$.

$a \equiv b$ mod $m \Rightarrow (a,m)|(b,m)$

Más adelante…

Tarea moral

Entradas relacionadas

Agradecimientos

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

Seminario de Resolución de Problemas: Principio de las Casillas, Parte 2

Por Fabian Ferrari

Deja un comentario

En esta entrada vemos algunos ejemplos más en donde se aplica el Principio de las Casillas.

Problema 5. Sean $a_1, a_2, … , a_n$ números enteros, no necesariamente todos diferentes. Prueba que existe un subconjunto de estos números, tal que su suma es divisible por $n$.

Solución. Consideremos los números $s_1, s_2,…, s_n$ los cuales definimos como sigue

\begin{align*}
s_1&=a_1\\
s_2&=a_1+a_2\\
s_3&=a_1+a_2+a_3\\
&\vdots\\
s_n&=a_1+a_2+ … +a_n.
\end{align*}

Tenemos que al dividir cada $s_i$ entre $n$ tenemos que el residuo varía de $0$ a $n-1$. Si el residuo es $0$ ya acabamos. Por otro lado, si ninguno de los residuos es cero, por el principio de las casillas tenemos que deben de existir al menos dos de los $s_i$´s que tengan el mismo residuo. Supongamos que son $s_j$ y $s_k$ con $j<k$.

Como $s_j$ y $s_k$ tienen el mismo residuo, tenemos que $s_k-s_j$ es divisible por $n$. Así el conjunto $S=\{s_{j+1}, s_{j+2}, \ldots , s_k \}$ es el conjunto tal que la suma de sus elementos es divisible por $n$.

$\square$

Problema 6.  Cada cuadrito de un tablero de ajedrez de $4\times 7$ es coloreado de blanco o negro. Prueba que en cualquier coloración siempre hay un rectángulo del tablero que tiene los cuatro cuadritos de las esquinas coloreadas del mismo color.

Solución. Podemos reducir el problema a un tablero de $3\times 7$, dado que cualquier rectángulo que se pueda crear en un tablero de $3\times 7$, también será un rectángulo en el tablero original. Ahora bien, pensemos en las posibles coloraciones que puede tener una columna en el tablero de $3\times 7$. Son dos colores acomodados en 3 lugares, así que tenemos 8 acomodos diferentes de coloración: $BBB, BBN, BNB, NBB, BNN, NBN, NNB, NNN$.

Notemos que si dos columnas tienen el mismo acomodo de colores, entonces acabamos (por ejemplo, dos columnas $BNB$ hacen un rectángulo de cuatro esquinas blancas).

Supongamos que usamos la coloración $BBB$ en una columna. Si en otra columna pintamos con alguno de $BBB, BBN, BNB, NBB$, entonces acabamos (usando dos de la $BBB$ y dos de esa otra). Si no, es que en las seis columnas restantes pintamos sólo con acomodos $BNN, NBN, NNB, NNN$. Por principio de las casillas, hay dos columnas pintadas con el mismo acomodo, y terminamos. Por simetría, si usamos la coloración $NNN$ entonces podemos hacer un argumento análogo.

Ya sólo nos quedan los casos en los que ninguna columna queda pintada ni con $BBB$ ni con $NNN$. Pero entonces tenemos que pintar las $7$ columnas con $6$ acomodos posibles. Por principio de las casillas, hay dos columnas que quedan pintadas con el mismo acomodo, y como ya vimos, esto crea el rectángulo con esquinas del mismo color.

$\square$

Problema 7. Si seleccionamos $n + 1$ enteros del conjunto $\{1, 2, \ldots 2n\}$, siempre hay dos de ellos tales que su máximo común divisor es $1$.

Solución. Tomemos al conjunto $\{1, 2, \ldots, 2n\}$. Si al tomar $n+1$ de ellos siempre logramos encontrar dos consecutivos, entonces el problema estará resuelto, ya que cualesquiera dos consecutivos son primos relativos. A la hora que seleccionamos $n+1$ enteros del conjunto dado, tenemos por el principio de casillas que al menos dos de ellos serán consecutivos. En efecto, dividamos a los números en las parejas $\{1,2\}$, $\{3,4\}$, $\ldots$, $\{2n-1,2n\}$. Estas son $n$ parejas, así que por casillas hubo una pareja de la que elegimos dos números. Estos son dos números consecutivos, así que que su máximo común divisor es $1$.

$\square$

Problema 8. En una grafo con un número finito de vértices, hay dos vértices con el mismo grado.

Solución. Sea $n$ el número de vértices de la gráfica, dado que el grado del vértice de un grafo es el número de aristas que concurren en dicho vértice. Tenemos que el grado de cada vértice varía de $0$ a $n-1$. Sin embargo si un vértice tiene grado cero, no existirá algún vértice con grado $n-1$. Por el principio de las casillas teniendo en cuenta que tenemos que distribuir $n-1$ valores en $n$ lugares, concluimos que al menos dos de los vértices deben de tener el mismo grado.

$\square$