Archivo del Autor: Leo

Leo

Acerca de Leo

Hola. Soy Leonardo Martínez. Soy Profesor de Tiempo Completo en la Facultad de Ciencias de la UNAM. Hice un doctorado en Matemáticas en la UNAM, un postdoc en Israel y uno en Francia. Además, me gusta colaborar con proyectos de difusión de las matemáticas como la Olimpiada Mexicana de Matemáticas.

Seminario de Resolución de Problemas: Máximo común divisor

Con esta entrada comenzamos a tratar los temas de números enteros y su aritmética. Varios de los temas que se ven aquí se estudian a profundidad en un curso de Álgebra Superior, así que varios de los resultados los enunciaremos sin demostración. Lo que nos interesa es cómo se pueden utilizar los resultados principales de la teoría de números enteros para la resolución de problemas matemáticos.

Divisibilidad y máximo común divisor

Trabajaremos todo el tiempo con números enteros, a menos que digamos lo contrario.

Decimos que a divide a b si b es un mútiplo de a, es decir, si existe un r tal que b=ra. Lo escribimos en símbolos como a\mid b. También decimos que a es divisor de b.

Proposición 1. La relación de divisibilidad es reflexiva y transitiva, pero no es simétrica. Si a\mid b y b\mid a, entonces |a|=|b|, es decir a=b o a=-b.

Si tenemos varios números a_1,\ldots,a_n, el máximo común divisor es el mayor número que divide a todos. El mínimo común múltiplo es el menor entero positivo que es múltiplo de todos. Los denotamos respectivamente por \MCD{a_1,\ldots,a_n} y \mcm{a_1,\ldots,a_n}.

Proposición 2. Si n divide a a y a b, entonces divide a cualquier combinación lineal entera ra+sb de ellos. En particular, si n divide a dos términos de la igualdad a+b=c, entonces divide al tercero.

Notemos que a+(b-a)=b. Por la Proposición 2, un divisor de a y b será divisor de b-a, y uno de b-a y de a será divisor de b. De aquí sale que \MCD{a,b}=\MCD{a,b-a}

Problema. Determina todas las funciones f:\mathbb{Z}^+\times \mathbb{Z}^+ \to \mathbb{Z}^+ tales que cumplen las siguientes tres propiedades simultáneamente:

  1. f(a,a)=a para todo entero positivo a.
  2. f(a,b)=f(b,a) para todo par de enteros positivos a y b.
  3. f(a,b)=f(a,a+b) para todo par de enteros positivos a y b.

Sugerencia pre-solución. Haz casos particulares que puedas obtener a partir de esas propiedades para conjeturar el valor de f(a,b) para todos a y b enteros positivos. Intenta probar tu conjetura por inducción fuerte.

Solución. Vamos a mostrar que f(a,b)=\MCD{a,b} para todo par de enteros positivos a y b. Vamos a probarlo por inducción sobre la suma a+b. Como a y b son enteros positivos, la menor suma que pueden tener es 2 y en este caso a+b=2 implica a=b=1. Por la hipótesis 1, tenemos f(1,1)=1, que coincide con \MCD{1,1}.

Supongamos que el resultado es cierto cuando a+b=k para todo entero k=1,\ldots,n y tomemos a y b enteros de suma n+1. Si a=b, entonces

    \[f(a,b)=f(a,a)=a=\MCD{a,a}=\MCD{a,b},\]

como queremos. Si a\neq b, por la simetría que nos da la hipótesis 2 podemos suponer b>a. Por la hipótesis 3,

    \[f(a,b)=f(a,a+(b-a))=f(a,b-a).\]

En la expresión de la derecha, tenemos que sus entradas suman a+(b-a)=b<a+b=n+1, de modo que podemos aplicar la hipótesis inductiva para obtener que f(a,b-a)=\MCD{a,b-a}. Por la discusión antes de este problema, \MCD{a,b-a}=\MCD{a,b}. Así, concluimos que f(a,b)=\MCD{a,b}, como queríamos.

\square

El máximo común divisor y el mínimo común múltiplo de un número son especiales. No sólo son el divisor más grande y el múltiplo más chico, sino que además si hay otro divisor de todos los números (o múltiplo de todos los números), además se cumplen ciertas divisibilidades.

Proposición 3. Si tenemos otro número d que sea divisor de a_1,\ldots,a_n, entonces

    \[d\mid \MCD{a_1,\ldots,a_n}.\]

Si tenemos otro número M que sea múltiplo de a_1,\ldots,a_n, entonces

    \[\mcm{a_1,\ldots,a_n}\mid M.\]

Problema. Sean a y b enteros positivos. Muestra que

    \[\MCD{a,b}\mcm{a,b}=ab.\]

Sugerencia pre-solución: Intenta resolver el problema antes de ver la solución. Para ello, necesitarás la Proposición 1 y la Proposición 3.

Solución. Para simplificar la notación, tomamos D=\MCD{a,b} y m=\mcm{a,b}.

Como D divide a a y b, existen enteros r y s tales que a=rD y b=sD. Notemos que rsD=as=br, así que rsD es un múltiplo de a y b, y por la Proposición 3, tenemos que m\mid rsD. Multiplicando por D esta divisibilidad, tenemos que Dm\mid rsD^2=ab.

Como ab es múltiplo de a y de b, por la Proposición 3 es múltiplo de m, digamos ab=km. Notemos que de aquí, tenemos a=k(m/b) con m/b entero y b=k(m/a) con m/a entero, de modo que k divide a a y a b. Como D es máximo común divisor, por la Proposición 3 tenemos que k\mid D. Multiplicando por m esta divisibilidad, tenemos que km\mid DM, es decir, ab\mid Dm.

Con esto logramos conseguir que ab\mid Dm y Dm\mid ab. Por la Proposición 1, tenemos que |ab|=|Dm|, pero como a, b, D, m son positivos, entonces ab=Dm.

\square

Algoritmo de la división y algoritmo de Euclides

Tomemos a y b enteros. Si intentamos expresar a a como múltiplo de b, puede que no lo logremos. Pero podemos acercarnos lo más posible y dejar un residuo «pequeño». Esto es lo que dice el algoritmo de la división.

Teorema 1 (Algoritmo de la división). Para enteros a y b\neq 0, existen únicos enteros q y r tales que 0\leq r < |b| y a=bq+r.

Consideremos la igualdad a=bq+r en el algoritmo de la división y apliquemos la Proposición 2. Si d divide a a y b, entonces divide a r. Si d divide a r y a b, entonces divide a a. Así, \MCD{a,b}=\MCD{b,r}, en donde b y r ahora son números más chicos que a y b. De este modo, podemos hacer varias veces el algoritmo de la división para obtener igualdades

    \begin{align*}a&=bq_1+r_1\\b&=r_1 q_2 + r_2\\r_1&= r_2q_3 + r_3\\&\vdots\\r_{n-2}&= r_{n-1}q_n + r_n\\r_{n-1}&= r_nq_{n+1} + 0\\ \end{align*}

de las que obtenemos

    \[\MCD{a,b}=\MCD{b,r_1}=\ldots=\MCD{r_n,0}=r_n.\]


En las igualdades llegamos a un residuo 0 pues b>r_1>r_2>r_3>\ldots\geq 0 es una sucesión estrictamente decreciente de enteros no negativos.

En particular, obtenemos

    \[\MCD{a,b}=r_n.\]

A esto se le conoce como el algoritmo de Euclides, que enunciamos en otras palabras a continuación.

Teorema 2 (Algoritmo de Euclides). Podemos obtener el máximo común divisor de a y b aplicando el algoritmo de la división a a y b, a b y el residuo obtenido y luego repetidamente a los residuos que se van obteniendo. El último residuo no cero es \MCD{a,b}.

Hay todavía una conclusión adicional muy importante que podemos obtener a partir del algoritmo de Euclides.

Problema. Sean a\geq b enteros. Sean q_i y los r_i los números obtenidos en el algoritmo de Euclides. Definimos recursivamente una sucesión de n+1 vectores en \mathbb{R}^3 como sigue:

    \begin{align*}v_1&=(a,1,0)\\v_2&=(b,0,2)\\v_{i+2}&=v_{i}-q_iv_{i+1}\quad \text{para $i=1,\ldots,n-1$}\end{align*}

Sean r_{-1}=a y r_{0}=b. Muestra que para i=1,2,3,\ldots,n+1 se tiene que v_i=(x_i,y_i,z_i), en donde:

  • x_i=r_{i-2}
  • x_i=ay_i+bz_i

Sugerencia pre-solución. Intenta resolver el problema haciendo inducción sobre el índice. Los casos i=1,2 son inmediatos.

Solución. Procedemos por inducción fuerte en el subíndice i. Para i=1,2, el resultado es cierto pues x_1=a=r_{-1}, x_2=b=r_0, a=1\cdot a + 0 \cdot b y b=0 \cdot a + 1\cdot b. Supongamos el resultado cierto para los índices 1,2,\ldots, k para algún 2\leq k\leq n. Tomemos el índice k+1.

Estudiemos primero la entrada x_{k+1}. Por definición de la recursión e hipótesis inductiva

    \begin{align*}x_{k+1}&=x_{k-1}-q_{k-1}x_{k}\\&=r_{k-3}-q_{k-1}r_{k-2}\\&=r_{k-1},\end{align*}

que es lo que queríamos mostrar para la entrada x_{k+1}. Para la segunda parte, de nuevo usando la recursión e hipótesis inductiva, tenemos que

    \begin{align*}x_{k+1}&=x_{k-1}-q_{k-1}x_{k}\\&=ay_{k-1}+bz_{k-1} - q_{k-1} (ay_{k}+bz_{k})\\&=a(y_{k-1}-q_{k-1}y_k) + b(z_{k-1}-q_{k-1}z_k)\\&=ay_{k+1}+bz_{k+1}.\end{align*}

Con esto terminamos la inducción.

\square

El problema anterior nos dice que, en particular, r_n=ay_n+bx_n. Esta conclusión es muy importante y la enunciamos como teorema.

Teorema 3. El máximo común divisor de enteros a y b se puede escribir como combinación lineal entera de a y b, es decir, existen enteros m y n tales que \MCD{a,b}=am+bn.

Veamos un ejemplo concreto de cómo podemos usar el problema para encontrar la combinación lineal que da el máximo común.

Problema. Expresa al máximo común divisor de 754 y 221 como combinación lineal entera de estos números.

Solución. Hacemos la siguiente tabla, en donde ponemos a los vectores del problema como vectores columna (en los renglones 2,3,4). En el primer rengón vamos apuntando las q_i.

3223
7542219139130
101-25-17
01-37-1758

Explicamos un poco más de donde sale la tabla. Las primeras dos columnas son los vectores v_1 y v_2 del problema, que son (754,1,0) y (221,0,1). Para la tercer columna, nos preguntamos ¿cuántas veces cabe 221 en 754? La respuesta es 3, así que ponemos un 3 arriba (para acordarnos) y hacemos la resta de la primera columna menos tres veces la segunda. Eso va en la tercer columna.

Para la cuarta columna, nos preguntamos ¿cuántas veces cabe 91 en 221? La respuesta es 2, así que lo apuntamos arriba, y la cuarta columna es la segunda, menos dos veces la tercera. Continuamos así hasta que obtengamos un 0. La columna anterior nos dice que 13 es el máximo común divisor, y que la combinación lineal es

    \[13=754\cdot 5 + 221 \cdot 58\]

.

\square

Aquí hay otros dos problemas con aplicaciones de las ideas que vimos en esta entrada.

Problema. Muestra que para todo entero n se tiene que la fracción \frac{41-6n}{9n-61} es irreducible para todo entero.

Sugerencia pre-solución. Intenta resolver el problema. Lo que quieres mostrar es que 41-6n y 9n-61 nunca tienen divisores en común.

Solución. Notemos que 41-6n y 9n-61 tienen una combinación lineal que da 1. En efecto,

    \[3\cdot (41-6n) + 2\cdot (9n-61) = 123-18n+18n-122=1.\]

Cualquier entero d que divida a 41-6n y a 9n-61 tiene entonces que dividir a 1, lo cual muestra que \MCD{41-6n,9n-61}=1, y por lo tanto la fracción siempre es irreducible.

\square

Problema. Se tiene un número irracional \alpha para el cual \alpha^{91} y \alpha^{119} son números racionales. Muestra que \alpha^{14} es un número racional.

Sugerencia pre-solución. Encuentra el máximo común divisor de 91 y 119. Recuerda que las potencias de racionales son racionales, y productos de racionales también.

Solución. Como 91=7\cdot 13 y 119=7\cdot 13, tenemos que \MCD{91,119}=7. De esta forma, existen enteros m y n tales que 7=91m+119n, de donde 14=91 \cdot (2m)+119 \cdot(2n).

Sabemos que \alpha^{91} es racional, así que (\alpha^{91})^{2m} también. Análogamente, (\alpha^{119})^{2n} es racional. De esta forma, el número

    \[\alpha^{14}=(\alpha^{91})^{2m}\cdot (\alpha^{119})^{2n}\]

también lo es.

\square

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.1 del libro Problem Solving through Problems de Loren Larson.

El Teorema 3 es fundamental para cuando se quieren determinar inversos multiplicativos trabajando módulo n.

Álgebra Superior II: Ecuaciones en congruencias

Introducción

En entradas anteriores platicamos de congruencias y de algunos teoremas que se pueden usar para trabajar con potencias y factoriales módulo un entero. Ya que tenemos un buen manejo de la aritmética en congruencias, podemos comenzar a hacernos preguntas acerca de las ecuaciones que pueden se plantear y resolver en estos términos.

Ejemplo. ¿Cuáles son las soluciones enteras a la ecuación x\equiv 3 \pmod 6?

Solución. Un número x satisface la ecuación si y sólo si 6 divide a x-3, lo cual sucede si y sólo si x es de la forma x=6r+3, donde r es un número entero. Así, el conjunto de soluciones es de la forma

    \[6\mathbb{Z}+3:= \{6r+3: r\in \mathbb{Z}\}.\]

Dicho de otra forma, el conjunto de soluciones es la clase de equivalencia del 3 módulo 6, es decir, [3]_6.

\square

Cuando tengamos ecuaciones más complicadas, usualmente lo que haremos es dejar expresada la solución en términos de congruencias, es decir, como uno o varios elementos de \mathbb{Z}_n. Si se quiere encontrar a todos los enteros (en \mathbb{Z}) que sean solución, basta recordar este ejemplo para expresar a las soluciones en \mathbb{Z}_n como conjuntos de soluciones en \mathbb{Z}.

Ejemplo. ¿Cuáles son las soluciones enteras a la ecuación 2x+1\equiv 0 \pmod 7?

Solución. Trabajemos módulo 7. Restando 1 de ambos lados obtenemos

    \[2x\equiv -1\equiv 6 \pmod 7.\]

Multiplicando por 4 de ambos lados tenemos que

    \[8x\equiv 24\equiv 3\pmod 7.\]

Como 8x\equiv x \pmod 7, tenemos que x\equiv 3 \pmod 7 es la solución.

\square

En el ejemplo anterior encontramos las soluciones módulo 7. Si queremos encontrar las soluciones en enteros, basta expresar esta congruencia en términos de enteros: las soluciones en \mathbb{Z} son los números de la forma 7r+3 con r entero.

Ecuaciones lineales en congruencias

Una ecuación lineal en congruencias es de la forma

    \[ax\equiv b\pmod n.\]

Vamos a estudiar esta ecuación, viendo cuándo tiene solución y cuántas soluciones módulo n tiene. Hay un caso fácil de estudiar, que es cuando a y n son primos relativos.

Proposición 1. Sean a,b enteros y n un entero positivo tales que \text{MCD}(a,n)=1. Entonces la ecuación

    \[ax\equiv b \pmod n\]

tiene una única solución x módulo n.

Demostración. Como a y n son primos relativos, a tiene un inverso multiplicativo módulo n, digamos a^{-1}. Afirmamos que x=a^{-1}b es solución. En efecto, a(a^{-1}b)\equiv 1\cdot b\equiv b \pmod n.

Ahora, afirmamos que la solución es única. Supongamos que x y y son solución. Tendríamos entonces que

    \[ax\equiv b \equiv ay \pmod n.\]

Multiplicando ambos extremos de esta ecuación por a^{-1}, tenemos que

    \[x\equiv a^{-1}ax\equiv a^{-1}a y \equiv y \pmod n.\]

\square

Sin embargo, como ya vimos antes, no siempre pasa que todo elemento tenga inverso multiplicativo. Necesitamos un análisis más detallado.

Notemos que x es solución de ax\equiv b\pmod n si y sólo si n divide a ax-b, lo cual sucede si y sólo si existe un entero y tal que ax-b=ny. Reordenando, tenemos que ax-ny=b. En otras palabras, la ecuación en congruencias tiene solución si y sólo si podemos expresar a b como combinación lineal entera de a y n, lo cual sucede si y sólo si

    \[b\in a\mathbb{Z} + n \mathbb{Z}=\text{MCD}(a,n)\mathbb{Z},\]

es decir, si y sólo si b es múltiplo del máximo común divisor de a y n. Resumimos esta primer parte del análisis en la siguiente proposición.

Proposición 2. Sean a,b enteros y n un entero positivo. La ecuación ax\equiv b\pmod n tiene solución si y sólo si \text{MCD}(a,n) divide a b.

Ahora, queremos entender cuántas soluciones diferentes hay módulo n.

Ejemplo. Encuentra todas las soluciones a la ecuación 4x\equiv 1 \pmod 8 y a la ecuación 4x\equiv 0 \pmod 8.

Solución. Tenemos que \text{MCD}(4,8)=4 y que 4 no divide a 1, así que la primer ecuación no tiene solución. Tenemos que 4 sí divide a 0, así que la segunda ecuación sí tiene solución. Veamos cuántas tiene.

Notemos que al multiplicar por 4 cada uno de los elementos 0,2,4,6 obtenemos respectivamente 0,8,16,24, que son todos múltiplos de 8, así que estos elementos de \mathbb{Z}_8 son solución. Al multiplicar 4 por 1,3,5,7 obtenemos 4,12,20,28, que módulo 8 son 4,4,4,4, así que ninguno de estos números son solución. Así, las soluciones son x\equiv 0,2,4,6\pmod 8.

\square

Una forma alternativa de expresar la solución del problema anterior es darse cuenta de que las soluciones en enteros son los números pares, o bien los enteros n tales que n\equiv 0\pmod 2. En general, cuando la solución existe, podemos encontrar un módulo en la que la podemos describir de manera única. Este es el contenido de las siguientes dos proposiciones.

Proposición 3. Sean a,b enteros y n un entero positivo tales que M=\text{MCD}(a,n) divide a b. Sean a'=a/M, b'=b/M y n'=n/M (con a', b', n' enteros). El entero x es solución a la ecuación en congruencias ax\equiv b \pmod n si y sólo si es solución a la ecuación en congruencias a'x\equiv b'\pmod {n'}.

Demostración. Tenemos que x es solución a ax\equiv b \pmod n si y sólo si existe una combinación lineal entera ax-ny=b. Al dividir entre M\neq 0, esto sucede si y sólo si a'x-n'y=b', lo cual sucede si y sólo si x es solución a la ecuación en congruencias a'x\equiv b'\pmod {n'}.

\square

Estamos listos para enunciar el resultado principal de esta sección. Viene de la combinación de las ideas anteriores.

Teorema 1. Sean a,b enteros y n un entero positivo. La ecuación ax\equiv b\pmod n tiene solución si y sólo si M:=\text{MCD}(a,n) divide a b. Cuando sí hay solución, ésta se puede expresar de manera única en módulo n':=n/M.

Demostración. La primer parte es la Proposición 2. Una vez que sabemos que la ecuación tiene solución, por la Proposición 3 podemos encontrar la ecuación equivalente a'x\equiv b'\pmod {n'}, en donde a'=a/M y b'=b/M. En esta ecuación, a' y n' son primos relativos (ver Tarea moral abajo). Por la Proposición 1, tiene una solución única módulo n'.

\square

Como empezamos con una ecuación módulo n, quizás queremos saber cuántas soluciones tiene módulo n, y no módulo n'. De manera inmediata, obtenemos el siguiente resultado.

Corolario. Con la notación del teorema anterior, cuando la ecuación tiene solución, entonces tiene M soluciones módulo n.

Ejercicio. Resuelve la ecuación lineal en congruencias

    \[12x\equiv 18 \pmod {30}.\]

Intenta resolver este ejercicio antes de ver la solución. Puedes comenzar calculando el máximo común divisor de 12 y 30.

Solución. El máximo común divisor de 12 y 30 es 6, que sí divide a 18. Entonces sí hay soluciones, y habrá 6 soluciones módulo 30. Para encontrar la ecuación reducida equivalente, dividimos entre 6 para obtener

    \[2x\equiv 3 \pmod 5.\]

El inverso de 2 módulo 5 es 3. Multiplicando en ambos lados por 3 obtenemos la solución

    \[x\equiv 9 \equiv 4 \pmod 5.\]

Para recuperar las soluciones módulo 30, a cada una de estas soluciones le sumamos 30/6=5 repetidamente para obtener las soluciones x\equiv 4, 9, 14, 19, 24, 29 \pmod {30}.

\square

En la siguiente entrada veremos cómo resolver sistemas de ecuaciones lineales en los que tenemos más de una congruencia.

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.

  • Sea a un entero y n un entero positivo. Sea M=\text{MCD}(a,n) y sean a'=a/M y n'=n/M. Muestra que \text{MCD}(a',n')=1.
  • Demuestra el corolario al Teorema 1.
  • Verifica que, en efecto, las soluciones que obtuvimos en el ejemplo después del Teorema 1 sí son soluciones de la ecuación original.
  • Diseña una ecuación lineal módulo 60 que tenga exactamente 15 soluciones módulo 60.
  • Para prepararte para la siguiente entrada, intenta resolver por completo el sistema de congruencias

    \begin{align*}x&\equiv -1 \pmod{77}\\x&\equiv -1 \pmod{55}\\\end{align*}

Seminario de Resolución de Problemas: Bases numéricas y dígitos

Introducción

En las entradas anteriores de teoría de números hemos hablado acerca de divisibilidad, de aritmética modular y de factorización única en primos. En esta entrada vamos a hablar de propiedades que podemos deducir de ciertos números a partir de su dígitos.

Usualmente escribimos a los números en base 10, usando los dígitos de 1 a 9. En realidad, esto es relativamente arbitrario. Podemos usar bases distintas de 10 para expresar cualquier número de manera (casi) única. Conocer la expresión de un número en cierta base nos permite deducir propiedades algebraicas y de divisibilidad que nos ayuden a resolver problemas.

Expresión en una base arbitraria

Para cualquier base entera b\geq 2 que elijamos, cualquier número real se puede expresar de manera (casi) única en base b. La afirmación precisa es el siguiente resultado.

Teorema. Sea r un número real y b\geq 2 un entero. Entonces, existen únicos enteros A_0,A_1,\ldots, a_1,a_2,\ldots en \{0,1,\ldots,b-1\} tales que

    \[r=\sum_{i=0}^\infty A_i b^i + \sum_{i=0}^{\infty} a_i 10^{-i}\]

y a_i\neq b-1 para una infinidad de i‘s.

Para estos a_i y A_i escribimos

    \[r=(\ldots A_2A_1A_0.a_1a_2\ldots)_b,\]

en donde el subíndice indica la base que se está usando.

La condición de a_i\neq b-1 para una infinidad de i's está ahí para garantizar que la expresión sea única pues, por ejemplo, 1=\sum_{i=0}^\infty 9\cdot 10^{-i}=0.9999\ldots, pero esa condición descarta la expresión de la derecha.

Si b=2, a esta expresión le llamamos la expresión binaria de r.

Ejemplo. La expresión binaria de 4/3 es (1.010101\ldots)_2. ¿Por qué?

Multiplicar y dividir entre 10 cuando tenemos números en base 10 es sencillo: simplemente recorremos el punto decimal. Lo mismo sucede en cualquier base b.

Proposición. Cuando tenemos un número en base b y multiplicamos por b, el «punto decimal» se recorre a la derecha. Cuando dividimos entre b se recorre a la izquierda.

Problema. Determina si existe un real x tal que

    \[\floor{x}+\floor{2x}+\floor{4x}+\floor{8x}= 2222.\]

Sugerencia pre-solución. Trabaja hacia atrás suponiendo que la ecuación sí tiene una solución para determinar cómo tiene que verse x. Usa la expresión binaria de x.

Solución. Tenemos que r\geq \floor{r} para todo real r, de modo que si dicho número x existe, se cumple

    \[17x\geq \floor{x}+\floor{2x}+\floor{4x}+\floor{8x} = 2222.\]

De aquí, x\geq 2222/17 = 130.705\ldots\geq 130. También, r\leq \floor{r}+1, de modo que si x existe necesitamos

    \[17x\leq \floor{x}+\floor{2x}+\floor{4x}+\floor{8x} + 4 = 2226.\]

De aquí, x\leq 2226/17 =130.94\leq 131.

Esto nos dice que x es un real entre 130 y 131. Escribámoslo como 130 más una parte fraccional en base 2, es decir, de la forma x=130+(abcde\ldots)_2. Multiplicar por 2 simplemente recorre el punto decimal en base 2 un lugar hacia la derecha, de modo que

    \begin{align*}2x&=260+(a.bcde\ldots)_2\\4x&=520+(ab.cde\ldots)_2\\8x&=1040+(abc.de\ldots)_2,\end{align*}

y por lo tanto

    \begin{align*}\floor{x}&=130\\\floor{2x}&=260+(a)_2=260+a\\\floor{4x}&=520+(ab)_2=520+2a+b\\\floor{8x}&=1040+(abc)_2=1040+4a+2b+c.\end{align*}

Concluimos entonces que la suma buscada es igual a 1950+7a+3b+c. Si existe el número que queremos, la ecuación

    \[1950+7a+3b+c=2222\]

debe tener una solución con a, b y c iguales a 0 o a 1. Pero esto es imposible, pues incluso aunque los tres sean iguales a 1, tenemos a lo más 1950+11=1961. De esta forma, no existe la x que buscamos.

\square

Bases y números racionales

Una sucesión infinita \{a_1,a_2,\ldots,\} es preperiódica si existen enteros positivos n y d tales que a_m=a_{m+d} para todo entero m\geq n. A d se le llama un periodo de la sucesión, y decimos que \{a_1,a_2,\ldots\} es periódica a partir de a_n.

Teorema. Sea r un número real. Las siguientes tres afirmaciones son equivalentes:

  • r es racional
  • Para toda base b la sucesión de dígitos después del punto \{a_1,a_2,\ldots\} es preperiódica.
  • Para alguna base b la sucesión de dígitos después del punto \{a_1,a_2,\ldots\} es preperiódica.

Problema. Considera el número en binario

    \[r=(0.a_1a_2a_3\ldots)_2\]

en donde a_i=0 si i es primo y a_i=1 si no. Determina si r es un número racional o irracional.

Sugerencia pre-solución. Procede por contradicción, suponiendo que r es racional.

Solución. Si r fuera racional, la sucesión \{a_1,a_2,\ldots\} sería preperiódica, de modo que existirían n y d tales que a_{m+d}=a_m para todo m\geq n. Consideremos el bloque de d dígitos (a_na_{n+1}\ldots a_{n+d-1})_2. Como el periodo de la sucesión es d, a partir de a_n este bloque de dígitos se repite.

Los números M=n(2d+1)!+2, M+1=n(2d+1)!+3, \ldots, M+(2d-1)=n(2d+1)!+(2d+1) son 2d números consecutivos mayores a n y tales que ninguno de ellos es primo, pues el primero es divisible entre 2, el segundo entre 3, …, y el último entre 2d+1. Esto muestra que el bloque de d dígitos debe consistir de puros 1‘s, pues uno de los bloques del ciclo queda contenido en el bloque de 2d dígitos (a_Ma_{M+1}\ldots a_{M+2d-1})_2. Así, a partir de a_n todos los dígitos son iguales a 1.

Pero esto es imposible, pues quiere decir que todos los enteros mayores o iguales a n no son primos. Esto contradice que hay una infinidad de números primos.

\square

Criterios de divisibilidad

Si sabemos cómo es la expresión de un número en una base, entonces a veces podemos decir cosas acerca de su divisibilidad o residuo al dividirse entre algunos enteros relacionados con la base. Cuando estamos trabajando módulo 10 tenemos el siguiente resultado.

Proposición (criterios de divisibilidad base 10). Sea n un entero positivo. En base 10,

  • n es congruente con el número formado por sus últimos k dígitos módulo 10^k, y por lo tanto también módulo 2^k y módulo 5^k.
  • n es congruente con la suma de sus dígitos módulo 9, y por lo tanto también módulo 3.
  • Agrupemos los dígitos de n de derecha a izquierda en grupos de j elementos, donde el último puede tener menos de j. Un número es congruente con la suma alternada (más, menos, más, etc) de estos grupos módulo 10^{j}+1.

Demostrar estos criterios es sencillo. Por ejemplo, un número (A_nA_{n-1}\ldots A_0)_{10} en base 10 es igual a

    \[10^{n}A_n+10^{n-1}A_{n-1}+\ldots+10 A_1+ A_0.\]

Trabajando módulo 9, todos los 10 son 1, así que

    \[n=10^nA_n+\ldots+A_0\equiv A_n + A_{n-1}+\ldots+A_0.\]

Como ejemplo del último criterio, considera el siguiente problema:

Problema. ¿Cuál es el residuo que queda al dividir n=1512513514515 entre 13?

Sugerencia pre-solución. Usa el tercer criterio de divisibilidad base 10 para j=3. Factoriza 1001.

Solución. Vamos a estudiar al número módulo 1001. Para esto, agrupamos los dígitos de tres en tres, de derecha a izquierda

    \[515, 514, 513, 512, 1\]

y hacemos la suma alternada

    \[515-514+513-512+1=3.\]

Por el tercer criterio de divisibilidad, tenemos que n\equiv 3 \pmod{1001}. Notemos que 1001=7\cdot 11 \cdot 13, de modo que n\equiv 3 \pmod{13}. Así, el residuo al dividir n entre 13 es 3.

\square

En general, tenemos lo siguiente.

Proposición (criterios de divisibilidad base b). Sea n un entero positivo. En base b:

  • n es congruente con el número formado por sus últimos k dígitos módulo b^k, y por lo tanto también módulo d^k para cualquier divisor d de b.
  • n es congruente con la suma de sus dígitos módulo b-1 (y por lo tanto también módulo cualquier divisor de b-1)
  • Agrupemos los dígitos de n de derecha a izquierda en grupos de j elementos, donde el último puede tener menos de j. Un número es congruente con la suma alternada (más, menos, más, etc) de estos grupos módulo b^{j}+1.

Problema. Considera los números del 1 al 500 (inclusive). ¿Cuántos de estos números tienen una cantidad impar de 1‘s en su expresión en base 3? ¿Cuántos de estos números tienen una cantidad impar de 1‘s en su expresión en binario?

Sugerencia pre-solución. Haz casos pequeños para encontrar un patrón que te diga cuántos números del 1 al n tienen una cantidad impar de 1‘s en su expresión en base 2 y 3. Para demostrar el resultado para base 3, usa criterios de divisibilidad generalizados. Para base 2 usa paridad y aprovecha la simetría.

Solución. Un número en base 3 es congruente con la suma de sus dígitos módulo 2. En base 3 el único dígito impar es el 1. Así, un número en base 3 es congruente a su cantidad de dígitos 1 módulo 2. De esta forma, n tiene una cantidad impar de 1‘s si y sólo si es impar. Por lo tanto, hay 250 números entre 1 y 500 que tienen una cantidad impar de 1‘s en su expresión en base 3.

En base 1 el patrón no es tan claro. Los primeros números son 1, 10, 11, 100, 101, 110, 111. A veces cuando se cambia de cantidad de dígitos se cambia la paridad de 1‘s (como de 11 a 100) y a veces no (como de 111 a 1000). Haremos entonces un argumento de emparejamiento.

Notemos que cualquier número par 2n termina en 0 en binario y que 2n+1 tiene la misma expansión salvo el último dígito, que ahora es 1.Así, a los números del 2 al 499 los podemos agrupar en parejas en donde en cada pareja los números tienen distinta paridad de 1‘s. De esta forma, aquí hay 498/2=249 números con una cantidad impar de 1‘s. El 1 tiene una cantidad impar de 1‘s. El 500 en binario es (111110100)_2, que tiene una cantidad par de 1‘s. Así, hay 250 números entre 1 y 500 con una cantidad impar de 1‘s en binario.

\square

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.4 del libro Problem Solving through Problems de Loren Larson.

Seminario de Resolución de Problemas: Aritmética modular

Introducción

En la entrada anterior hablamos de divisibilidad, máximo común divisor y combinaciones lineales enteras. Cuando hablamos de trabajar en artimética modular nos referimos a que tomamos un entero n y realizamos todas las operaciones «sólo en el mundo de n«, es decir, aplicando las operaciones únicamente en los residuos que deja un número al ser dividido entre n.

Cuando estamos trabajando módulo n, dos enteros a y b «son los mismos» si n divide a a-b. En este caso decimos que a\equiv b \pmod n, que se lee «a es congruente con b módulo n«.

En esta entrada de blog discutimos la relación «ser congruente con» y cómo se puede enunciar en términos de anillos. Ahí damos las demostraciones de varias de las propiedades que no probaremos aquí. Es recomendable por lo menos echarle un ojo.

Aritmética modular

Para recordar los principios básicos de la aritmética modular, comencemos con el siguiente problema.

Problema. Determina cuál es el residuo obtenido de dividir 1305\cdot 1302+1314\cdot 1311 al dividirse entre 11.

Sugerencia pre-solución. Intenta resolver este problema trabajando módulo 11.

Solución. Tenemos que 1305, 1302, 1314 y 1311 los podemos poner como un múltiplo de 13 más un residuo como sigue: 1300+5, 1300+2 y 1313+1, 1300+11. Así, 1305\equiv 5\pmod {13}, 1302\equiv 2 \pmod {13}, 1314\equiv 1 \pmod {13} y 1311\equiv 11 \pmod {13}. Así, trabajando módulo 1 tenemos que:

    \begin{align*}1305\cdot 1302+1314\cdot 1311 &\equiv 5\cdot 2 + 1\cdot 11 \\&\equiv 10 + 11 \equiv 21 \\&\equiv 8 \pmod {13}\end{align*}


De esta forma, 1305\cdot 1302+1314\cdot 1311 deja residuo 8 al dividirse entre 13.

\square

Utilizando el algoritmo de la división, que vimos en la entrada anterior, se puede probar el siguiente resultado.

Proposición. Para cada entero a y entero positivo n, existe un único número r en \{0,1,\ldots,n-1\} tal que a\equiv r\pmod n, que es justo el residuo obtenido al dividir a entre n.

Dicho en otras palabras, sólo hay n posibles residuos al dividir entre n. Esto nos permite que las operaciones módulo n siempre las hagamos con números chiquitos, y que afirmaciones sencillas de divisibilidad entre n dependen sólo de n casos. Esto lo podemos aprovechar para resolver problemas como el siguiente.

Problema. Se tienen 13 números enteros. Muestra que hay tres de ellos a,b,c que satisfacen que

    \[1331\mid (a-b)(b-c)(c-a).\]

Sugerencia pre-solución. Notemos que 1331=11^3, así que trabajamos módulo 11. Encuentra todas las posibilidades que pueden tener los números cuadrados.

Solución. Un entero n sólo puede ser congruente con alguno de los números 0,1,2,3,4,5,6,7,8,9,10 módulo 11. Los cuadrados tienen entonces las siguientes posibilidades:

nn^2 \pmod {11}
00
11
24
39
416\equiv 5
525\equiv 3
636\equiv 3
7(-4)^2\equiv 5
89
94
101

A partir del 6 estamos aprovechando que ya conocemos los del 1 al 6 y que a \equiv a-11 \pmod {11}. Notemos que sólo hay 6 residuos posibles para los cuadrados módulo 11, que son 0, 1, 4, 9, 5 y 3.

Ahora sí, resolvamos el problema. Como tenemos 13 números enteros y sólo hay 6 posibles residuos para los cuadrados módulo 11, entonces por principio de las casillas hay tres de estos enteros cuyo cuadrado deja el mismo residuo al dividirse entre 11, digamos a,b,c. Como dejan los tres el mismo residuo, tenemos 11\mid a-b, 11\mid b-c y 11\mid c-a, de donde se sigue la conclusión que queremos.

\square

Últimos dígitos

Los últimos m dígitos de un entero n corresponden con el residuo de dividir n entre 10^m. Por esta razón, en este tipo de problemas es conveniente usar módulos.

Problema. Determina los últimos dos dígitos de 7^{25}+25^7.

Sugerencia pre-solución. Trabajamos módulo 100, así que todas las congruencias son módulo 100. Hay muchas formas de proceder para encontrar 7^{21}. Notemos que 7^{2}\equiv 49. y que

    \[7^4\equiv 49\times 49 = 2401 \equiv 1.\]

Esto es una gran ventaja, pues entonces 7^{24}\equiv (7^4)^6 \equiv 1^6 \equiv 1, así que 7^{25}\equiv 7.

Para 25^7, nos conviene notar que 25=20+5, de modo que

    \begin{align*}25^2&=(20+5)^2\\&=20^2+2\cdot 20 \cdot 5 + 25\\&\equiv 25,\end{align*}

pues los primeros dos sumandos son múltiplos de 100. De esta forma, 25^7\equiv 25. Así, 7^{25}+25^7\equiv 7+25\equiv 32, por lo que los dos últimos dígitos de la expresión son 32.

\square

Veamos otro ejemplo en el que además combinamos un poco de la teoría mencionada en la entrada anterior.

Problema. Demuestra que existe un entero que es múltiplo de 2002 y que tiene por lo menos 2002 dígitos iguales a 7.

Sugerencia pre-solución. Intenta hacer que los 2002 dígitos 7 que se necesitan aparezcan hacia el final. Esto te permitirá usar congruencias. Además, necesitarás el resultado de la entrada anterior que dice que el máximo común divisor de dos números se puede expresar como combinación lineal entera de ellos.

Solución. Tomemos el número N=777\cdots770, en donde hay 2002 dígitos iguales a 7.

El máximo común divisor de 2002 y 10^{2003} es 2, de modo que existen enteros m y n tales que 2002m+10^{2003}n=2.

Multiplicando esta igualdad por el entero N/2, obtenemos que 2002\cdot \frac{mN}{2}+10^{2003}\frac{nN}{2}=N. Aplicando módulo 10^{2003} obtenemos que 2002\cdot \frac{mN}{2} \equiv N \pmod {10^{2003}}.

Como N<10^{2003}, esto nos dice que 2002\cdot \frac{mN}{2} es un múltiplo de 2002 cuyos últimos 2003 dígitos son los de N, es decir, que tiene por lo menos 2002 dígitos iguales a 7.

\square

Teorema chino del residuo

En algunos problemas necesitamos construir un entero que satisfaga un conjunto de congruencias. El teorema chino del residuo nos da una condición bajo la cual podemos garantizar la existencia de dicho número.

Teorema. Sea n\geq 2 un entero, b_i enteros para i\in\{1,2,\ldots,n\} y m_i enteros positivos para i\in\{1,\ldots,n\}. Supongamos además que cada par m_i, m_j de enteros (i\neq j) son primos relativos. Entonces el sistema lineal de congruencias

    \begin{align*}x&\equiv b_1\pmod {m_1}\\ x&\equiv b_2\pmod {m_2}\\&\vdots\\ x&\equiv b_n\pmod {m_n}\end{align*}


tiene una y sólo una solución módulo m_1m_2\ldots m_n.

El teorema tiene muchas aplicaciones tanto en resolución de problemas, como en matemáticas en general. Veamos un ejemplo.

Problema. ¿Será posible encontrar 5 enteros consecutivos tales que cada uno de ellos sea divisible entre un cubo distinto de 1?

Sugerencia pre-solución. Intenta construir el ejemplo usando el teorema chino del residuo con 5 módulos y en donde los b_i son consecutivos.

Solución. Por el teorema chino del residuo, existe un entero positivo n tal que

    \begin{align*}n&\equiv 0 \pmod{2^3}\\n&\equiv -1\pmod{3^3}\\n&\equiv -2\pmod{5^3}\\n&\equiv -3\pmod{7^3}\\n&\equiv -4\pmod{11^3}\end{align*}

Para este entero, se tiene que 2^3 divide a n, 3^3 divide a n+1, 5^3 divide a n+2, 7^3 divide a n+3 y 11^3 divide a n+4.

\square

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.2 del libro Problem Solving through Problems de Loren Larson.

Hay otros dos teoremas que sirven cuando estamos trabajando módulo n, de los cuales hemos escrito aquí en el blog. Para empezar, aquí hay una entrada con videos de ejercicios de trabajar módulo n.

El teorema de Fermat y el de Wilson ayudan a entender potencias y factoriales, respectivamente. En la entrada sobre el teorema chino del residuo damos una demostración al teorema.

Álgebra Lineal I: Cambios de base, parte 1

Introducción

En la entrada anterior platicamos de cómo podemos comenzar con una transformación lineal T:V\to W entre espacios vectoriales V y W y de ahí obtener una «matriz que la represente». Para ello, necesitamos elegir bases B_V y B_W de V y W respectivamente. Si elegimos bases diferentes, entonces la matriz que obtendremos será diferente, por lo cual es muy importante siempre recordar qué bases elegimos.

Es posible que en algunas aplicaciones de álgebra lineal tengamos una transformación T:V\to W, y que los vectores de V o los de W los tengamos que entender en más de una base. Así, los dos siguientes problemas aparecen frecuentemente:

  • Supongamos que tenemos dos bases B_1 y B_2 de un espacio vectorial V y que tomamos un vector v en V. Si ya sabemos la combinación lineal de elementos de B_1 que da v, ¿cómo podemos saber la combinación lineal de elementos de B_2 que da v? En otras palabras, ¿cómo podemos pasar a v de su expresión en base B_1 a su expresión en base B_2?
  • Supongamos que tenemos una transformación lineal T:V\to W entre dos espacios vectoriales V y W, dos bases B_1 y B_2 de V y dos bases C_1 y C_2 de W. Si ya sabemos qué le hace T a los elementos de V en términos de las bases B_1 y C_1, ¿cómo podemos saber qué hace T en términos de las bases B_2 y C_2?

Las herramientas que necesitamos para responder ambos problemas se llaman matrices de cambios de base. El objetivo de esta entrada es definir estas matrices, ver algunas propiedades básicas que cumplen y ver cómo nos ayudan a resolver el primero de los problemas de aquí arriba. En una segunda entrada veremos cómo también servirán para resolver el segundo.

Matriz de cambio de base

Definición. Sea V un espacio vectorial sobre el campo F. Sean B=(v_1,\ldots,v_n) y B'=(v_1', \ldots, v_n') dos bases ordenadas de V. La matriz de cambio de base de B a B' es la matriz P=[p_{ij}] en M_{n}(F) cuya columna j tiene como entradas a las coordenadas de v_j' escrito en términos de la base B. En otras palabras, las entradas p_{1j},\ldots,p_{nj} de la j-ésima columna de P son los únicos elementos de F para los cuales

    \[v_j'=p_{1j}v_1+\ldots +p_{nj} v_n,\]

para toda j=1,2,\ldots,n.

Ejemplo. Considera la base ordenada B=(1,x,x^2) de R[x]_2, el espacio vectorial de polinomios de coeficientes reales grado a lo más 2. Veremos que B'=(3x^2,2x,1) es una base de R[x]_2. Encontraremos la matriz de cambio de base de B a B' y la matriz de cambio de base de B' a B.

La dimensión de R[x]_2 es 3 y B' tiene 3 elementos, así que basta ver que los elementos de B' son linealmente independientes para ver que B' es base. Una combinación lineal a(3x^2)+b(2x)+c(1)=0 es equivalente a que 3ax^2+2bx+c=0, lo cual sucede si y sólo si a=b=c=0. Esto muestra que B' es base.

Para encontrar a la matriz de cambio de base de B a B' lo que tenemos que hacer es escribir a los elementos de B' como combinación lineal de los elementos de B. Esto lo hacemos de la siguiente manera (recuerda que el orden es importante):

    \begin{align*}3x^2 &= 0 \cdot 1 + 0 \cdot x + 3 \cdot x^2\\2x &= 0\cdot 1+ 2\cdot x + 0 \cdot x^2\\1 & = 1\cdot 1 + 0 \cdot x + 0 \cdot x^2.\end{align*}

Como los coeficientes de 3x^2 en la base ordenada B son 0, 0 y 3, entonces la primer columna de la matriz de cambio de base será (0,0,3). Argumentando de manera similar para 2x y 1, tenemos que la matriz de cambio de base de B a B' es

    \[\begin{pmatrix}0 & 0 & 1\\0 & 2 & 0 \\3 & 0 & 0\end{pmatrix}.\]

Para encontrar a la matriz de cambio de base de B' a B, expresamos a los elementos de B en términos de la base B' como sigue:

    \begin{align*}1 &= 0 \cdot (3x^2) + 0 \cdot (2x) + 1 \cdot 1\\x &= 0\cdot (3x^2)+ \frac{1}{2} \cdot (2x) + 0 \cdot 1\\x^2 & = \frac{1}{3} \cdot (3x^2) + 0 \cdot (2x) + 0 \cdot 1.\end{align*}


De esta manera, tenemos que la matriz de cambio de base de B' a B es

    \[\begin{pmatrix}0 & 0 & \frac{1}{3}\\0 & \frac{1}{2} & 0 \\1 & 0 & 0\end{pmatrix}.\]

\square

La matriz de cambio de base nos ayuda a responder la primer pregunta que planteamos al inicio de esta entrada. Si conocemos las coordenadas de un vector en una base, podemos usar la matriz de cambio de base para encontrar las coordenadas del vector en otra base.

Proposición. Sea V un espacio vectorial de dimensión n, B=(v_1,\ldots,v_n), B'=(v_1',\ldots,v_n') bases ordenadas de V y P la matriz de cambio de base de B a B'. Supongamos que el vector v de V se escribe en base B como

    \[v=c_1v_1+c_2v_2+\ldots+c_nv_n\]

y en base B' como

    \[v=c_1'v_1'+c_2'v_2'+\ldots+c_n'v_n'.\]

Entonces:

    \[P \begin{pmatrix}c_1' \\\vdots \\c'_n\end{pmatrix}=\begin{pmatrix}c_1 \\\vdots \\c_n\end{pmatrix} .\]

En otras palabras, la matriz P de cambio de base de B a B' manda las coordenadas de un vector en base B' a coordenadas en base B al multiplicar por la izquierda. Ojo: para construir P expresamos a B' en términos de B, pero lo que hace P es expresar a alguien en de coordenadas B' a coordenadas en B.

Demostración. El vector de coordenadas de v_j' escrito en base B' es el vector canónico e_j de F^n. Además, Pe_j es la j-ésima columna de P, que por construcción es el vector de coordenadas de v_j' en la base B. Así, el resultado es cierto para los vectores v_j' de la base B'. Para cualquier otro vector v, basta expresarlo en términos de la base B' y usar la linealidad de asignar el vector de coordenadas y la linealidad de P.

\square

Problema. Escribe a los vectores v_1=(4,3,5,2), v_2=(2,2,2,2) y v_3(0,0,0,1) de \mathbb{R}^4 como combinación lineal de los elementos de la base B de \mathbb{R}^4 conformada por los vectores (1,0,0,0), (1,1,0,0), (1,1,1,0) y (1,1,1,1).

Solución. Conocemos las coordenadas de v_1,v_2,v_3 en la base canónica (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1). De hecho, el vector de coordenadas de v_1 es exactamente v_1 (esto es algo que sucede pues estamos trabajando en \mathbb{R}^4). Lo que nos estan pidiendo son las coordenadas de v_1,v_2,v_3 en la base B. Nos gustaría usar la proposición anterior. Para ello, necesitamos encontrar la matriz de cambio de base de B a la base canónica. Escribamos entonces a la base canónica en términos de los vectores de B:

    \begin{align*}(1,0,0,0)&=1\cdot (1,0,0,0)+0\cdot (1,1,0,0)+0\cdot (1,1,1,0)+0\cdot (1,1,1,1)\\(0,1,0,0)&= -1\cdot (1,0,0,0)+1\cdot (1,1,0,0)+0\cdot (1,1,1,0)+0\cdot (1,1,1,1)\\(0,0,1,0)&= 0\cdot (1,0,0,0)-1\cdot (1,1,0,0)+1\cdot (1,1,1,0)+0\cdot (1,1,1,1)\\(0,0,0,1)&= 0\cdot (1,0,0,0)+0\cdot (1,1,0,0)-1\cdot (1,1,1,0)+1\cdot (1,1,1,1)\\\end{align*}

A estas coordenadas las ponemos como columnas para encontrar la matriz de cambio de base de B a la base canónica:

    \[\begin{pmatrix}1 & -1 & 0 & 0\\0 & 1 & -1 & 0\\ 0 & 0 & 1 & -1\\ 0 & 0 & 0 & 1\end{pmatrix}.\]

Para encontrar las coordenadas de v_1, v_2, v_3 en términos de la base B, basta con multiplicar esta matriz a la izquierda para cada uno de ellos:

    \[\begin{pmatrix}1 & -1 & 0 & 0\\0 & 1 & -1 & 0\\ 0 & 0 & 1 & -1\\ 0 & 0 & 0 & 1\end{pmatrix} \begin{pmatrix}4 \\3 \\ 5 \\ 2\end{pmatrix} =  \begin{pmatrix}1 \\-2 \\ 3\\ 2\end{pmatrix},\]

    \[\begin{pmatrix}1 & -1 & 0 & 0\\0 & 1 & -1 & 0\\ 0 & 0 & 1 & -1\\ 0 & 0 & 0 & 1\end{pmatrix} \begin{pmatrix}2 \\2 \\ 2 \\ 2\end{pmatrix} = \begin{pmatrix}0 \\0 \\ 0\\ 2\end{pmatrix}\]

y

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

En efecto, se puede verificar que estos nuevos vectores dan las combinaciones lineales de la base B que hacen a v_1, v_2 y v_3, por ejemplo, para v_1 tenemos:

    \[(4,5,3,2)=(1,0,0,0)-2(1,1,0,0)+3(1,1,1,0)+2(1,1,1,1).\]

\square

Matriz de cambio de base como matriz de transformación lineal

A la matriz de cambio de base de B a B' la denotamos por \text{Mat}_B(B').

Una observación crucial es que podemos pensar a una matriz de cambio de base en un espacio vectorial V justo como como una matriz correspondiente a una transformación lineal de las que vimos en la entrada pasada. De hecho, la transformación lineal que le corresponde es muy bonita: es la identidad \text{id}_V que manda a cada vector de V a sí mismo.

De manera más concreta, si B y B' son bases de V y \text{Mat}_B(B') es la matriz de cambio de base de B a B', entonces

    \[\text{Mat}_B(B')=\text{Mat}_{B,B'}(\text{id}_V).\]

A estas alturas tienes todas las herramientas necesarias para demostrar esto.

¿Qué sucede si ahora tenemos tres bases B, B' y B'' de V y componemos a la identidad consigo misma? Utilizando los argumentos de la entrada anterior, la matriz correspondiente a la composición es el producto de las matrices de cada transformación. Juntando esto con la observación anterior, tenemos la siguiente propiedad para matrices de cambio de base:

    \[\text{Mat}_B(B'')=\text{Mat}_{B}(B')\cdot \text{Mat}_{B'}(B'').\]

Finalmente, ¿qué sucede si en la igualdad anterior ponemos B''=B? Al lado izquierdo tenemos la matriz de cambio de base de B a sí misma, que puedes verificar que es la identidad. Al lado derecho tenemos al producto de la matriz de cambio de base de B a B' con la matriz de cambio de B' a B. Esto muestra que las matrices de cambio de base son invertibles.

Resumimos todas estas observaciones en la siguiente proposición:

Proposición. Sean B, B' y B'' bases del espacio vectorial de dimensión finita V.

  • La matriz de cambio de base de B a B' corresponde a la matriz de la transformación identidad de V a V, en donde el primer V lo pensamos con la base B' y al segundo con la base B.
  • El producto de matrices de cambio de base de B a B' y de B' a B'' es la matriz de cambio de base de B a B''.
  • La matriz de cambio de base de B a B' es invertible, y su inversa es la de cambio de base de B' a B.

En la próxima entrada veremos cómo las matrices de cambio de base también nos ayudan a entender transformaciones lineales bajo distintas bases.

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.

  • ¿Qué sucede en el primer ejemplo si multiplicas ambas matrices de cambio de base que encontramos?
  • En el segundo ejemplo, encuentra la matriz de cambio de base de la base canónica a la matriz B
  • Considera las cuatro matrices de 2\times 2 que puedes formar colocando tres unos y un cero. Muestra que estas cuatro matrices forman una base B de M_{2,2}(\mathbb{R}). Determina la matriz de cambio de base de B a la base canónica de M_{2,2}(\mathbb{R}). Ojo: Una cosa son los elementos del espacio vectorial y otra cosa van a ser las matrices de cambio de base. Como M_{2,2}(\mathbb{R}) es de dimensión 4, la matriz de cambio de base que tienes que determinar en realidad es de 4\times 4.
  • Da una demostración de que, en efecto

        \[\text{Mat}_B(B')=\text{Mat}_{B,B'}(\text{id}_V).\]

  • Verifica que la matriz de cambio de base B a sí misma es la identidad.