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

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

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:

$n$$n^2 \pmod {11}$
$0$$0$
$1$$1$
$2$$4$
$3$$9$
$4$$16\equiv 5$
$5$$25\equiv 3$
$6$$36\equiv 3$
$7$$(-4)^2\equiv 5$
$8$$9$
$9$$4$
$10$$1$

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: Matrices de cambio de base

Por Leonardo Ignacio Martínez Sandoval

10 respuestas

Introducción

Anteriormente platicamos de cómo al elegir una base ordenada $B$ de un espacio vectorial $V$ de dimensión finita $n$, podemos expresar a cada uno de sus vectores en términos de «coordenadas», que vienen de los coeficientes de la combinación lineal de elementos de $B$ que da el vector. Así mismo, vimos 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 ordenadas $B_V$ y $B_W$ de $V$ y $W$ respectivamente. Tanto las coordenadas, como las matrices que representan a transformaciones lineales, dependen fuertemente de las bases ordenadas elegidas. En esta entrada hablaremos de las matrices de cambio de base, pues nos ayudarán a pasar de unas coordenadas a otras.

Siento más concretos, 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 (ordenadas) $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 (ordenadas) $B_1$ y $B_2$ de $V$ y dos bases (ordenadas) $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$?

La herramienta que necesitamos para responder ambos problemas se le conoce como matrices de cambio 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 sirven para resolver el segundo.

Matrices de cambio de base

Definición. Sea $V$ un espacio vectorial de dimensión $n$ 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 $\mathbb{R}_2[x]$, el espacio vectorial de polinomios de coeficientes reales grado a lo más $2$. Veremos que $B’=(3x^2,2x,1)$ es también una base de $\mathbb{R}_2[x]$. 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 $\mathbb{R}_2[x]$ 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á $\begin{pmatrix} 0 \\ 0 \\ 3\end{pmatrix}$. 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*}

En este caso fue sencillo hacerlo, pero en otros problemas frecuentemente esto se hace resolviendo un sistema de ecuaciones.

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}.$$

$\triangle$

Cambio de coordenadas usando matrices de cambio de base

Las matrices de cambio de base nos ayudan 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 de coordenadas en $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).$$

$\triangle$

Matrices de cambio de base como la forma matricial de una 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 las matrices de cambio de base en un espacio vectorial $V$ justo como formas matriciales correspondientes a una transformación lineal específica. 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.

Más adelante…

En esta entrada ya vimos cómo cambian las coordenadas de un vector cuando cambiamos de base. Lo que haremos en la siguiente entrada es estudiar cómo cambia la forma matricial de una transformación lineal cuando cambiamos las bases de su espacio vectorial origen y su espacio vectorial destino.

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.

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»

Seminario de Resolución de Problemas: Variantes del principio de inducción

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

En entradas anteriores ya hablamos acerca de la idea básica del principio de inducción y también vimos cómo la inducción puede interactuar con las heurísticas de trabajar hacia atrás y de generalización. En esta entrada hablaremos de dos formas adicionales y válidas en las que se puede hacer inducción.

Inducción fuerte

El principio de inducción funciona pues es un mecanismo que pasa por los números naturales «uno por uno». Al momento en el que suponemos la hipótesis inductiva para cierto natural $n$, lo que queremos hacer para continuar es mostrar la afirmación para el natural $n+1$. Es decir, el natural $n+1$ es el primer natural para el que todavía no sabemos que la afirmación funciona. Dicho de otra forma, para todo natural $m\leq n$ ya sabemos que la afirmación sí funciona.

Aunque típicamente usemos únicamente la afirmación para el paso $n$ para demostrar la validez del paso $n+1$, en realidad podríamos usar toda la información que ya tenemos de que la inducción se vale para todo $m$ entre la base inductiva y $n$. Esta es la idea detrás del principio de inducción fuerte.

Principio de inducción fuerte. 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(m)$ es cierto para todo $a\leq m \leq n$» implica la veracidad de la afirmación $P(n+1)$,

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

Veamos un ejemplo de teoría de gráficas. No entraremos en detalles de las definiciones. Aunque no conozcas mucho de teoría de gráficas, es posible que de cualquier forma las definiciones te hagan sentido.

Problema. Un árbol es una gráfica que no tiene ciclos y que es conexa. Demuestra que todo árbol de $n$ vértices tiene $n-1$ aristas.

Solución. Lo vamos a demostrar por inducción sobre el número de vértices que tiene el árbol. Si el árbol tiene $1$ vértice, entonces el resultado es cierto, pues tiene $0$ aristas.

Tomemos ahora un entero $n$ y supongamos que el resultado es cierto para cuando el número de vértices es cualquier entero entre $1$ y $n$. Tomemos un árbol $T$ de $n+1$ vértices.

Árbol con $n+1$ vértices.

Tomemos una arista cualquiera de $T$ y quitémosla. Esto parte a $T$ en dos árboles (¡demuéstralo!) con, digamos $a$ y $b$ vértices, de modo que $a+b=n+1$.

Después de quitar la arista

Tenemos $1\leq a < n$ y $1\leq b <n$, así que cada uno de esos árboles tiene, por hipótesis inductiva, $a-1$ y $b-1$ aristas, respectivamente. Así, $T$ tiene esas aristas, y la que quitamos, es decir, $(a-1)+(b-1)+1=a+b-1=n$ aristas, como queríamos demostrar.

$\square$

Los que han estudiado teoría de gráficas quizás noten que pudimos haber evitado usar inducción fuerte si en vez de usar una arista arbitraria usábamos una que llegaba a un vértice hoja (de grado $1$). Haciendo eso se puede usar inducción «normal». La demostración anterior tiene la ventaja de no necesitar definir qué es una hoja.

Inducción de Cauchy

Hablemos ahora de otra variante. El principio de inducción es un mecanismo que nos permite probar una afirmación para los naturales «pasando por todos ellos» de una manera muy natural se prueba para el primero, luego para el siguiente, luego para el siguiente y así sucesivamente. Hay otras formas de cubrir a los números enteros.

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

  • la afirmación $P(1)$ es cierta,
  • la veracidad de la afirmación $P(n)$ implica la veracidad de la afirmación $P(2n)$ y
  • la veracidad de la afirmación $P(n)$ para un $n>a$ implica la veracidad de la afirmación $P(n-1)$,

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

Intuitivamente, lo que está pasando es que al probar $P(1)$ y la segunda afirmación, estamos probando $P(2)$, de ahí $P(4)$, de ahí $P(8)$ y en general $P(n)$ para cuando $n$ es potencia de $2$. Luego, con $P(4)$ y la tercera afirmación sale $P(3)$. Con $P(8)$ y la tercera afirmación sale $P(7), P(6),P(5)$. Esto garantiza cubrir todos los naturales pues para cualquier natural $n$ hay una potencia de dos $2^m$ mayor que él para la que sabemos que el resultado es cierto, y de ahí con la tercera afirmación «vamos bajando cubriendo todos los naturales», incluido $n$.

Como ejemplo, presentamos una demostración de la desigualdad entre la media aritmética y la media geométrica,

Problema. Sea $n$ un entero positivo y $x_1,x_2,\ldots,x_n$ números reales positivos. Demuestra que $$\frac{x_1+x_2+\ldots+x_n}{n}\geq \sqrt[n]{x_1x_2\cdots x_n}.$$

Solución. Vamos a proceder por inducción de Cauchy sobre $n$. Sea $P(n)$ la afirmación del problema.

En el caso $n=1$ tenemos sólo un real $x_1$ y tenemos que demostrar que $\frac{x_1}{1}\geq \sqrt[1]{x_1}$, lo cual es cierto pues en ambos lados tenemos $x_1$. Así, $P(1)$ es cierta.

Para el resto de la demostración, será útil que probemos también por separado el caso para dos números, es decir, $P(2)$. Pero esto es sencillo pues si tenemos reales positivos $a$ y $b$, entonces $\frac{a+b}{2}\geq \sqrt{ab}$ es equivalente a $a-2\sqrt{ab}+b\geq 0$, la cual es cierta pues el lado izquierdo es el número no negativo $(\sqrt{a}-\sqrt{b})^2$.

Ahora veremos que $P(n)$ implica $P(2n)$. Supongamos la veracidad de $P(n)$ y tomemos $2n$ números reales $x_1,x_2,\ldots,x_{2n}$. Queremos demostrar que $$\frac{x_1+\ldots+x_{2n}}{2n}\geq \sqrt[2n]{x_1\cdots x_{2n}}.$$ Llamemos $A$ al lado izquierdo y $G$ al lado derecho.

Sea $B$ la media aritmética de $x_1,\ldots, x_n$ y $C$ la de $x_{n+1},\ldots, x_{2n}$. Aplicando por separado $P(n)$ a estos números, tenemos que
\begin{align*}
B:=\frac{x_1+\ldots+x_n}{n}&\geq \sqrt[n]{x_1\cdots x_n}\\
C:=\frac{x_{n+1}+\ldots+x_{2n}}{n}&\geq \sqrt[n]{x_{n+1}\cdots x_{2n}}\\
\end{align*}

Notemos que $A=\frac{B+C}{2}$. Aplicando $P(2)$ a los números $B$ y $C$ tenemos que
\begin{align*}
A&=\frac{B+C}{2}\\
&\geq \sqrt[2]{BC} \\
&\geq \sqrt[2]{\sqrt[n]{x_1\cdots x_n} \cdot \sqrt[n]{x_{n+1}\cdots x_{2n}}}\\
& = G.
\end{align*}

Es decir, $P(2n)$ es cierta.

Para terminar con la inducción de Cauchy, el último paso es suponer la veracidad de $P(n)$ para $n>1$ y con ella demostrar la veracidad de $P(n-1)$. Supongamos entonces la veracidad de $P(n)$ y tomemos $n-1$ números $x_1,\ldots, x_{n-1}$. Queremos usar la veracidad de $P(n)$, así que tenemos que «inventarnos» otro número $m$ para poder aplicar $P(n)$. Tomemos $m=\frac{x_1+\ldots+x_{n-1}}{n-1}$, es decir, la media aritmética de los números de $x_1$ hasta $x_{n-1}$.

Observemos que $$\frac{x_1+\ldots+x_{n-1}+m}{n}=m.$$ Usando la veracidad de $P(n)$ para los números $x_1,\ldots, x_{n-1},m$ tenemos que $$m=\frac{x_1+\ldots+x_{n-1}+m}{n}\geq \sqrt[n]{x_1\cdots x_{n-1}m}.$$

Dividiendo entre $\sqrt[n]{m}=m^{1/n}$ en ambos extremos de la cadena, obtenemos $$m^{\frac{n-1}{n}}\geq \sqrt[n]{x_1 \cdots x_{n-1}}.$$

Elevando ambos lados de esta desigualdad a la $n/(n-1)$ obtenemos
$$m\geq \sqrt[n-1]{x_1 \cdots x_{n-1}}.$$

Esto es exactamente lo que queríamos probar. Con esto se comprueba la veracidad de $P(n-1)$ y así terminamos la inducción de Cauchy.

$\square$

La elección de $m$ en la última parte de la demostración parece un poco sacada de la manga. En realidad, sí tiene una cierta motivación. En la hipótesis $P(n)$ tenemos a la izquierda $\frac{x_1+x_2+\ldots+x_n}{n}$, pero lo que queremos es tener $\frac{x_1+x_2+\ldots+x_{n-1}}{n-1}$. Nuestra elección de $x_n=m$ vino de igualar ambas expresiones y despejar $x_n$.

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:

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»