Archivo de la etiqueta: bases

Álgebra Lineal I: Introducción a espacio dual

Por Leonardo Ignacio Martínez Sandoval

Introducción

En esta entrada empezamos la tercera unidad del curso de Álgebra Lineal I. Los conceptos fundamentales de esta nueva unidad son el de espacio dual y el de formas bilineales.

Hagamos un pequeño recordatorio, que será útil para entender los temas que vendrán. Ya definimos qué es un espacio vectorial y qué son las transformaciones lineales.

Para los espacios vectoriales, hablamos de subespacios, de conjuntos generadores, independientes y bases. A partir de ellos definimos qué quiere decir que un espacio sea de dimensión finita y, en ese caso, dijimos cómo definir la dimensión. Un lema fundamental para hacer esto fue el lema del intercambio de Steinitz.

Dijimos que las transformaciones lineales son funciones «bonitas» entre espacios vectoriales que «abren sumas» y «sacan escalares». Dimos como ejemplos a las proyecciones y las simetrías. Vimos lo que le hacen a generadores, linealmente independientes y bases. También, vimos que podemos expresarlas a través de matrices.

Un tipo de matrices de trasformaciones lineales muy importante son las matrices de cambios de base, que permiten conocer las coordenadas de vectores en distintas bases y pasar matrices de transformaciones lineales entre distintas bases. Finalmente, hablamos del rango para matrices y transformaciones lineales.

Es muy bueno entender estos temas lo mejor posible antes de continuar. Aunque no te queden 100% claras todas las demostraciones, por lo menos intenta sí conocer las hipótesis y los enunciados de los resultados principales.

Los temas que vendrán están basados en los capítulos 6 y 10 del libro de Titu Andreescu.

Dualidad y espacio dual

Antes de continuar, el siguiente ejemplo te debe de quedar clarísimo. Dice que hay una forma de hacer un espacio vectorial cuyos elementos son transformaciones lineales. Así es, cada vector de este espacio es una transformación lineal. Esto no debería de ser tan raro pues ya estudiamos algunos espacios vectoriales de funciones.

De ser necesario, verifica que en efecto se satisfacen los axiomas de espacio vectorial, para entender todavía mejor el ejemplo.

Ejemplo 1. Si $V$ y $W$ son espacios vectoriales sobre un mismo campo $F$, entonces el conjunto de transformaciones lineales de $V$ a $W$ es un espacio vectorial con las operaciones de suma de funciones y multiplicación por escalar.

Recordemos que la suma de funciones manda a las funciones $S:V\to W$ y $T:V\to W$ a la función $S+T:V\to W$ para la cual $$(S+T)(v)=S(v)+T(v)$$ y que la multiplicación por escalar manda al escalar $c\in F$ y a la función $T:V\to W$ a la función $cT:V\to W$ para la cual $$(cT)(v)=cT(v).$$

La razón por la cual este es un espacio vectorial es que es un subconjunto del espacio vectorial de todas las funciones de $V$ a $W$, y además es cerrado bajo sumas y multiplicaciones por escalar, de modo que es un subespacio.

A este espacio vectorial le llamamos $\text{Hom}(V,W)$.

$\triangle$

En esta unidad vamos a estudiar $\text{Hom}(V,W)$, pero para un caso particular muy concreto: para cuando $W$ es $F$, el campo sobre el cual está $V$. Podemos hacer esto, pues recuerda que podemos pensar al campo $F$ como un espacio vectorial sobre sí mismo.

A partir de ahora fijaremos el campo $F$. Si quieres, puedes pensarlo como $\mathbb{R}$ o $\mathbb{C}$ pero lo que digamos funcionará para campos arbitrarios.

Definición. Sea $V$ un espacio vectorial sobre un campo $F$. El espacio dual $V^\ast$ de $V$ es el conjunto de transformaciones lineales $l:V\to F$ dotado con las operaciones suma dada por $$(l_1+l_2)(v)=l_1(v)+l_2(v)$$ y producto por escalar dado por $$(cl)(v)=c(l(v))$$ para $l_1,l_2, l$ en $V^\ast$, $v$ en $V$ y $c$ en $F$.

A cada elemento de $V^\ast$ le llamamos una forma lineal en $V$. Usamos la palabra «forma» para insistir en que es una transformación que va hacia el campo $F$ sobre el cual está $V$.

Ejemplo 2. Consideremos al espacio vectorial $\mathbb{R}^3$. Está sobre el campo $\mathbb{R}$. Una forma lineal aquí es simplemente una transformación lineal $S_1:\mathbb{R}^3\to \mathbb{R}$, por ejemplo $$S_1(x,y,z)=x+y-z.$$ Otra forma lineal es $S_2:\mathbb{R}^3\to \mathbb{R}$ dada por $$S_2(x,y,z)=y+z-x.$$ Si sumamos ambas formas lineales, obtenemos la forma lineal $S_1+S_2$, la cual cumple $$(S_1+S_2)(x,y,z)=(x+y-z)+(y+z-x)=2y.$$

Estas son sólo dos formas lineales de las que nos interesan. Si queremos construir todo el espacio dual $(\mathbb{R}^3)^\ast$, necesitamos a todas las transformaciones lineales de $\mathbb{R}^3$ a $\mathbb{R}$.

Recordemos que cada transformación lineal $T$ de estas está representada de manera única por una matriz en $M_{1,3}(\mathbb{R})$ de la forma, digamos, $\begin{pmatrix} a & b & c\end{pmatrix}$. Así, toda transformación lineal de $\mathbb{R}^3$ a $\mathbb{R}$ lo que hace es enviar a $(x,y,z)$ a $$\begin{pmatrix} a& b & c \end{pmatrix}\begin{pmatrix}x\\ y\\ z\end{pmatrix}=ax+by+cz.$$ Se puede verificar que la suma de matrices y el producto escalar corresponden precisamente con la suma de sus transformaciones lineales asociadas, y su producto escalar.

Dicho de otra forma, $(\mathbb{R}^3)^\ast$ se puede pensar como el espacio vectorial de matrices $M_{1,3}(\mathbb{R})$. Observa que $\mathbb{R}^3$ y $(\mathbb{R}^3)^\ast$ tienen ambos dimensión $3$.

$\triangle$

Ejemplo 3. Consideremos el espacio vectorial $V$ de funciones continuas del intervalo $[0,1]$ a $\mathbb{R}$. Una forma lineal es una transformación lineal que a cada vector de $V$ (cada función) lo manda a un real en $\mathbb{R}$. Un ejemplo es la forma lineal $T:V\to \mathbb{R}$ tal que $$T(f)=\int_0^1 f(t)\,dt.$$ Otro ejemplo es la forma lineal $\text{ev}_0:V\to \mathbb{R}$ que manda a cada función a lo que vale en $0$, es decir, $$\text{ev}_0(f)=f(0).$$ Aquí dimos dos formas lineales, pero hay muchas más. De hecho, en este ejemplo no está tan sencillo decir quienes son todos los elementos de $V^\ast$.

$\triangle$

Espacio dual de un espacio de dimensión finita

Sea $V$ un espacio de dimensión finita $n$ y $B=\{e_1,e_2,\ldots,e_n\}$ una base de $V$. Como ya vimos antes, una transformación lineal queda totalmente definida por lo que le hace a los elementos de una base. Más concretamente, si $v=x_1e_1+\ldots+x_ne_n$, entonces lo que hace una forma lineal $l$ en $v$ es $$l(x_1e_1+\ldots+x_ne_n)=x_1a_1+\ldots+x_na_n,$$ en donde $a_i=l(e_i)$ son elementos en $F$.

Hay una manera canónica de combinar a un elemento $l$ de $V^\ast$ y a un elemento $v$ de $V$: evaluando $l$ en $v$. Así, definimos al emparejamiento canónico entre $V$ y $V^\ast$ como la función $$\langle\cdot, \cdot \rangle: V^\ast \times V$$ definida para $l$ en $V^\ast$ y $v$ en $V$ como $$\langle l,v\rangle = l(v).$$

Observa que $\langle\cdot, \cdot \rangle$ es lineal en cada una de sus entradas por separado, es decir para $c$ en $F$, para $l_1,l_2,l$ en $V^\ast$ y para $v_1,v_2,v$ en $V$ se tiene que $$\langle cl_1+l_2,v\rangle = c\langle l_1,v\rangle + \langle l_2,v\rangle$$ y que $$\langle l,cv_1+v_2\rangle = c\langle l,v_1\rangle +\langle l,v_2\rangle.$$ Esto es un ejemplo de una forma bilineal. Estudiaremos estas formas a detalle más adelante.

Vamos a hacer una pequeña pausa. Hasta ahora, para un espacio vectorial $V$ definimos:

  • Su espacio dual $V^\ast$.
  • El emparejamiento canónico entre $V$ y $V^\ast$.

Si a $V^\ast$ le estamos llamando «el dual» es porque esperamos que sea «muy parecido» a $V$. También, en una operación de dualidad nos gustaría que al aplicar dualidad dos veces «regresemos» al espacio original.

Por esta razón, nos gustaría a cada elemento $v$ de $V$ asociarle un elemento de $V^ {\ast \ast} $, el espacio dual del espacio dual. Afortunadamente, hay una forma muy natural de hacerlo. Para cada $v$ en $V$ podemos considerar la forma lineal $\text{ev}_v:V^\ast \to F$ que a cada forma lineal $l$ en $V^\ast$ le asigna $l(v)$.

Ejemplo. Considera el espacio vectorial de matrices $M_{2}(\mathbb{R})$. El espacio dual $M_{2}(\mathbb{R})^\ast$ consiste de todas las transformaciones lineales $T: M_{2}(\mathbb{R}) \to \mathbb{R}$. Un ejemplo de estas transformaciones es la transformación $T$ que a cada matriz la manda a la suma de sus entradas, $T\begin{pmatrix}a& b\\c & d\end{pmatrix}=a+b+c+d$. Otro ejemplo es la transformación $S$ que a cada matriz la manda a su traza, es decir, $S\begin{pmatrix}a& b\\c & d\end{pmatrix}=a+d$.

Consideremos ahora a la matriz $A=\begin{pmatrix} 5 & 2\\ 1 & 1\end{pmatrix}$.

A esta matriz le podemos asociar la transformación $\text{ev}_A:M_{2}(\mathbb{R})^\ast\to F$ tal que a cualquier transformación lineal $L$ de $ M_{2}(\mathbb{R})$ a $\mathbb{R}$ la manda a $L(A)$. Por ejemplo, a las $T$ y $S$ de arriba les hace lo siguiente $$\text{ev}_A(T)=T(A)=5+2+1+1=9$$ y $$\text{ev}_A(S)=S(A)=5+1=6.$$

$\triangle$

La discusión anterior nos permite dar una transformación lineal $\iota: V \to V {\ast \ast}$ tal que a cada $v$ la manda a $\text{ev}_v$, a la cual le llamamos la bidualidad canónica entre $V$ y $V^ {\ast \ast} $. Nota que $$\langle \iota(v), l\rangle=\langle l, v\rangle.$$ Un teorema importante que no probaremos en general, sino sólo para espacios vectoriales de dimensión finita, es el siguiente.

Teorema. Para cualquier espacio vectorial $V$, la bidualidad canónica es inyectiva.

De hecho, para espacios vectoriales de dimensión finita veremos que es inyectiva y suprayectiva, es decir, que es un isomorfismo entre $V$ y $V^{\ast \ast}$.

Formas coordenadas

En esta sección hablaremos de cómo encontrar una base para el espacio dual de un espacio vectorial $V$ de dimensión finita.

Supongamos que $V$ es de dimensión finita $n$ y sea $B=\{e_1,\ldots,e_n\}$ una base de $V$. A partir de la base $B$ podemos obtener $n$ formas lineales $e_i^\ast:V\to F$ como sigue. Para obtener el valor de $e_i^\ast$ en un vector $v$, expresamos a $v$ en términos de la base $$v=x_1e_1+x_2e_2+\ldots+x_n e_n$$ y definimos $e_i^\ast(v)=x_i$. A $e_i^\ast$ le llamamos la $i$-ésima forma coordenada para la base $B$ de $V$.

Directamente de las definiciones que hemos dado, tenemos que $$v=\sum_{i=1}^n e_i^\ast(v) e_i = \sum_{i=1}^n \langle e_i^\ast, v\rangle e_i.$$

Otra relación importante es que $e_i^\ast(e_j)=0$ si $i\neq j$ y $e_i^\ast(e_j)=1$ si $i=j$. De hecho, muchas veces tomaremos esta como la definición de la base dual.

Ejemplo. Si estamos trabajando en $F^n$ y tomamos la base canónica $e_i$, entonces la forma canónica $e_i^\ast$ manda al vector $(x_1,\ldots,x_n)$ a $x_i$, que es precisamente la $i$-ésima coordenada. De aquí el nombre de formas coordenadas. En efecto, tenemos que $$v=x_1e_1+x_2e_2+\ldots+x_ne_n.$$

$\triangle$

Estamos listos para enunciar el teorema principal de esta entrada introductoria a dualidad lineal.

Teorema. Sea $V$ un espacio vectorial de dimensión finita $n$ y $B=\{e_1,\ldots,e_n\}$ una base de $V$. Entonces el conjunto de formas coordenadas $B^\ast=\{e_1^\ast, \ldots,e_n^\ast\}$ es una base de $V^\ast$. En particular, $V^\ast$ es de dimensión finita $n$. Además, la bidualidad canónica $\iota:V\to V^{\ast \ast}$ es un isomorfismo de espacios vectoriales.

Más adelante…

Esta primera entrada introduce los conceptos de espacio dual. Estos conceptos son bastante útiles más adelante. Veremos que gracias a ellos, podemos dar una interpretación en términos de transformaciones lineales de la matriz transpuesta. En esta primer entrada también hablamos de formas lineales. Más adelante, veremos como éstas nos llevan de manera natural al concepto de «hiperplanos» en cualquier espacio vectorial. Uno de los resultados clave que demostraremos con la teoría de dualidad es que cualquier subespacio de un espacio vectorial de dimensión finita se puede pensar como intersección de hiperplanos. Gracias a esto encontraremos una fuerte relación entre subespacios y sistemas de ecuaciones lineales.

Antes de poder hacer estas cosas bien, necesitamos desarrollar bases sólidas. Por ello, en la siguiente entrada demostraremos el último teorema enunciado. También, veremos algunas recetas para resolver problemas de bases duales.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  • Revisa por definición que si $V$ y $W$ son espacios vectoriales sobre $F$, entonces $\text{Hom}(V,W)$ es un espacio vectorial sobre $F$.
  • Encuentra más formas lineales en el espacio de funciones continuas del intervalo $[0,1]$ a $\mathbb{R}$.
  • Justifica por qué $\iota:V\to V^{\ast \ast}$ es una transformación lineal y argumenta por qué $\langle \iota (v),l\rangle = \langle l,v\rangle$.
  • En el espacio de polinomios $\mathbb{R}_n[x]$ con coeficientes reales y grado a lo más $n$, ¿quienes son las formas coordenadas para la base ordenada $(1,x,x^2,\ldots,x^{n-1},x^n)$?, ¿quiénes son las formas coordenadas para la base ordenada $(1,1+x,\ldots,1+\ldots+x^{n-1},1+\ldots+x^n)$?
  • Aplica el último teorema a la base canónica $E_{ij}$ de $M_2(\mathbb{R})$ para encontrar una base de $M_2(\mathbb{R})^\ast$
  • Considera el espacio vectorial $V$ de matrices en $M_2(\mathbb{R})$. ¿Quién es el kernel de la forma lineal en $V$ que a cada matriz la manda a su traza? ¿Quién es el kernel de la forma lineal $\text{ev}_A$ en $V^\ast$, donde $A=\begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$?

Entradas relacionadas

Agradecimientos

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

Álgebra Lineal I: Problemas de cambio de base

Por Blanca Radillo

Introducción

En las entradas anteriores platicamos acerca de matrices de cambio de base. Vimos cómo nos ayudan a pasar un vector expresado en una base a otra. También vimos cómo nos ayudan a entender una transformación lineal en bases distintas. En esta entrada, veremos algunos ejemplos para repasar estos conceptos.

Problemas resueltos

Problema 1. Considera las familias de vectores $B=\{v_1,v_2,v_3\}$, $B’=\{w_1,w_2,w_3\}$, donde $$v_1=(0,1,1), \ v_2=(1,0,1), \ v_3=(1,1,0)$$ y $$w_1=(1,1,-1), \ w_2=(1,0,-1), \ w_3=(-1,-1,0).$$

  1. Prueba que $B$ y $B’$ son bases de $\mathbb{R}^3$.
  2. Encuentra la matriz de cambio de base $P$ de $B$ a $B’$ usando la definición de $P$.
  3. Encuentra la matriz de cambio de base $P$ usando la base canónica de $\mathbb{R}^3$ y la última proposición de esta entrada.

Solución. (1) Dado que $\dim \mathbb{R}^3=3$ y estas familias son de tres vectores, basta con demostrar que son vectores linealmente independientes. Una manera de hacerlo es formando la matriz obtenida al colocar a los vectores como renglones y reducirla hasta la matriz identidad $I_3$.

Para $B$, la matriz asociada es $$\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}.$$

Haciendo los cálculos de la reducción, obtenemos que

\begin{align*}
&\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}\\
\to&\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}\\
\to &\begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & -1 \\ 0 & 1 & 1 \end{pmatrix}\\
\to &\begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{pmatrix} \\
\to &\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}.
\end{align*}

Esto implica que los vectores en $B$ son linealmente independientes y, por lo tanto, forman una base $\mathbb{R}^3$.

Para $B’$, la matriz asociada es $$\begin{pmatrix} 1 & 1 & -1 \\ 1 & 0 & -1 \\ -1 & -1 & 0 \end{pmatrix}.$$

Reduciendo la matriz, tenemos que

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

Por lo tanto, $B’$ también es una base de $\mathbb{R}^3$.

(2) Recordemos que la matriz de cambio de base $P$ está definida como la matriz $[p_{ij}]$ cuya columna $j$ tiene como entradas a las coordenadas de $w_j$ escrito en términos de la base $B$. Entonces, expresemos

\begin{align*}
(1,1,-1)&=w_1=av_1+bv_2+cv_3=(b+c,a+c,a+b),\\
(1,0,-1)&=w_2=dv_1+ev_2+fv_3=(e+f,d+f,d+e),\\
(-1,-1,0)&=w_3=gv_1+hv_2+kv_3=(h+k,g+k,g+h),
\end{align*}

obteniendo que

\begin{align*}
b+c&=1\\
a+c&=1\\
a+b&=-1\\
e+f&=1\\
d+f&=0\\
d+e&=-1\\
h+k&=-1\\
g+k&=-1\\
g+h&=0.
\end{align*}

Si resolvemos el sistema anterior, concluimos que $a=b=-\frac{1}{2}$, $c=\frac{3}{2}$, $d=-1$, $e=0$, $f=1$, $g=h=0$, $k=-1$. Por lo tanto

$$P=\begin{pmatrix} a & d & g \\ b & e & h \\ c & f & k \end{pmatrix}= \begin{pmatrix} -\frac{1}{2} & -1 & 0 \\ -\frac{1}{2} & 0 & 0 \\ \frac{3}{2} & 1 & -1 \end{pmatrix}.$$

(3) Sea $B»=\{e_1,e_2,e_3\}$ la base canónica de $\mathbb{R}^3$. Queremos encontrar la matriz de cambio de base denotada como $\text{Mat}_B (B’)$. Usando la última proposición de la clase del lunes, tenemos que

$$\text{Mat}_B (B’)=\text{Mat}_{B} (B») \cdot \text{Mat}_{B»} (B’)=(\text{Mat}_{B»} (B))^{-1} \cdot \text{Mat}_{B»} (B’).$$

Por definición,

$$\text{Mat}_{B»} (B)=\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}, \ \text{Mat}_{B»} (B’)=\begin{pmatrix} 1 & 1 & -1 \\ 1 & 0 & -1 \\ -1 & -1 & 0 \end{pmatrix}.$$

Para calcular $(\text{Mat}_{B»} (B))^{-1}$, lo haremos como ya lo hemos visto en clases: pegando a la derecha una matriz identidad y aplicando reducción gaussiana:

\begin{align*} &\left( \begin{array}{ccc|ccc} 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{array} \right) \\
\rightarrow &\left( \begin{array}{ccc|ccc} 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 \end{array} \right) \\ \rightarrow &\left( \begin{array}{ccc|ccc} 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & -1 & 0 & -1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 \end{array} \right) \\
\rightarrow &\left( \begin{array}{ccc|ccc} 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 2 & 0 & 1 & -1 & 1 \\ 0 & 0 & 2 & 1 & 1 & -1 \end{array} \right) \\ \rightarrow &\left( \begin{array}{ccc|ccc} 1 & 0 & 0 & -1/2 & 1/2 & 1/2 \\ 0 & 1 & 0 & 1/2 & -1/2 & 1/2 \\ 0 & 0 & 1 & 1/2 & 1/2 & -1/2 \end{array} \right).
\end{align*}

Por lo tanto, $$(\text{Mat}_{B»}(B))^{-1}=\begin{pmatrix} -1/2 & 1/2 & 1/2 \\ 1/2 & -1/2 & 1/2 \\ 1/2 & 1/2 & -1/2 \end{pmatrix}.$$

Finalmente, usando la proposición, tenemos que

$$P=\text{Mat}_B (B’)=\begin{pmatrix} -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \end{pmatrix}\cdot\begin{pmatrix} 1 & 1 & -1 \\ 1 & 0 & -1 \\ -1 & -1 & 0 \end{pmatrix}$$

$$=\begin{pmatrix} -\frac{1}{2} & -1 & 0 \\ -\frac{1}{2} & 0 & 0 \\ \frac{3}{2} & 1 & -1 \end{pmatrix}. $$

Esto coincide con el cálculo que hicimos previamente.

$\square$

Problema 2. Considera la matriz $$A=\begin{pmatrix} 2 & -1 & 0 \\ -2 & 1 & -2 \\ 1 & 1 & 3 \end{pmatrix}$$

y sea $T:\mathbb{R}^3 \rightarrow \mathbb{R}^3$ la transformación lineal asociada, es decir $T(X)=AX$ para todo $X\in\mathbb{R}^3$. Considera los vectores

$$v_1=\begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix}, \ v_2=\begin{pmatrix} 1 \\ 0 \\ -1 \end{pmatrix}, \ v_3=\begin{pmatrix} 1 \\ -1 \\ 0 \end{pmatrix}.$$

  1. Prueba que $v_1,v_2,v_3$ forman una base de $\mathbb{R}^3$ y calcula la matriz de $T$ con respecto a esta base.
  2. Encuentra la matriz de cambio de base de la base canónica a la base $\{v_1,v_2,v_3\}$.
  3. Calcula $A^n$ para todo entero positivo $n$.

Antes de ver la solución a este problema este problema, observa que sería muy difícil decir quién es $A^{100}$ «a mano» si procedes directamente. Se tendrían que hacer muchas multiplicaciones matriciales, que son difíciles. Ten en mente esto cuando leas la solución de la parte 3.

Solución. (1) Dado que la dimensión de $\mathbb{R}^3$ es 3 y $\{v_1,v_2,v_3\}$ son tres vectores, basta con demostrar que éstos son linealmente independientes para probar que forman una base. Sean $a,b,c\in\mathbb{R}$ tales que $av_1+bv_2+cv_3=0$, entonces

\begin{align*}
&a+b+c=0, \ a-c=0, \ -a-b=\\
\Rightarrow &a=c, -a=b, a-a+a=0 \\
\Rightarrow &a=0, c=0, b=0.
\end{align*}

Entonces, son linealmente independientes y, por lo tanto, forman una base de $\mathbb{R}^3$.

Nota: Otra manera de demostrarlo es considerar la matriz formada por los vectores $v_1,v_2,v_3$ como sus columnas, reducirla y llegar a que la matriz reducida es la matriz identidad.

Ahora, para calcular la matriz de $T$ con respecto a la nueva base, expresaremos $T(v_1),T(v_2), T(v_3)$ en términos de $v_1,v_2,v_3$. Entonces tenemos que

$$T(v_1)=Av_1=\begin{pmatrix} 2 & -1 & 0 \\ -2 & 1 & -2 \\ 1 & 1 & 3 \end{pmatrix}\cdot \begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix}=\begin{pmatrix} 1 \\ 1 \\ -1 \end{pmatrix}=v_1,$$

$$T(v_2)=Av_2=\begin{pmatrix} 2 & -1 & 0 \\ -2 & 1 & -2 \\ 1 & 1 & 3 \end{pmatrix}\cdot \begin{pmatrix} 1 \\ 0 \\ -1 \end{pmatrix}=\begin{pmatrix} 2 \\ 0 \\ -2 \end{pmatrix}=2v_2,$$

$$T(v_3)=Av_3=\begin{pmatrix} 2 & -1 & 0 \\ -2 & 1 & -2 \\ 1 & 1 & 3 \end{pmatrix}\cdot \begin{pmatrix} 1 \\ -1 \\ 0 \end{pmatrix}=\begin{pmatrix} 3 \\ -3 \\ 0 \end{pmatrix}=3v_3.$$

Por lo tanto, la matriz que buscamos es $$B=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{pmatrix}.$$

(2) Lo haremos de la misma manera que en el inciso (2) del problema anterior, que consiste en escribir a los $v_1,v_2,v_3$ en la base canónica, pero ésto es obvio ya que están escritos de esa manera, por lo tanto $$P=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & -1 \\ -1 & -1 & 0 \end{pmatrix}.$$

(3) Sabemos que la matriz de $T$ con respecto a $v_1,v_2,v_3$ (que nombramos en el inciso (1) como $B$) es igual a $P^{-1}AP$, gracias al último corolario de la sección «Matrices de cambio de base y transformaciones lineales» de la entrada anterior. Entonces $$P^{-1}AP=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{pmatrix}.$$

Es fácil ver (pero lo pueden demostrar por inducción en $n$) que $$(P^{-1}AP)^n=(P^{-1}AP)(P^{-1}AP)\dots (P^{-1}AP)=P^{-1}A^n P.$$

Esto implica que $P^{-1}A^n P=B^n$, es decir $$P^{-1}A^n P=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 2^n & 0 \\ 0 & 0 & 3^n \end{pmatrix}.$$

Multiplicando por $P$ a la izquierda y por $P^{-1}$ a la derecha, obtenemos que $$A^n=P\begin{pmatrix} 1 & 0 & 0 \\ 0 & 2^n & 0 \\ 0 & 0 & 3^n \end{pmatrix}P^{-1} .$$

Para ello, nos falta calcular la inversa de $P$, y eso lo haremos como siempre lo hemos hecho: reduciendo la matriz. Entonces

\begin{align*} &\left( \begin{array}{ccc|ccc} 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & -1 & 0 & 1 & 0 \\ -1 & -1 & 0 & 0 & 0 & 1 \end{array} \right) \\\rightarrow &\left( \begin{array}{ccc|ccc} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 2 & 1 & -1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \end{array} \right) \\
\rightarrow &\left( \begin{array}{ccc|ccc} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & -1 & -1 & -2 \\ 0 & 0 & 1 & 1 & 0 & 1 \end{array} \right) \\\rightarrow &\left( \begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & -1 & -1 & -2 \\ 0 & 0 & 1 & 1 & 0 & 1 \end{array} \right). \end{align*}

Como consecuencia, tenemos que $$P^{-1}=\begin{pmatrix} 1 & 1 & 1 \\ -1 & -1 & -2 \\ 1 & 0 & 1 \end{pmatrix}.$$

Por lo tanto,

\begin{align*}
A^n &=P \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2^n & 0 \\ 0 & 0 & 3^n \end{pmatrix} P^{-1}\\
&=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & -1 \\ -1 & -1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2^n & 0 \\ 0 & 0 & 3^n \end{pmatrix}\begin{pmatrix} 1 & 1 & 1 \\ -1 & -1 & -2 \\ 1 & 0 & 1 \end{pmatrix}
\end{align*}

$$A^n= \begin{pmatrix} 1-2^n+3^n & 1-2^n & 1-2^{n+1}+3^n \\ 1-3^n & 1 & 1-3^n \\ 2^n-1 & 2^n-1 & 2^{n+1}-1 \end{pmatrix}.$$

$\square$

El ejercicio anterior deja una moraleja importante de álgebra lineal: si tenemos una matriz $A$ y logramos encontrar una matriz diagonal $B$ similar a ella, entonces será fácil encontrar $A^n$. Para finalizar esta sesión, tenemos el siguiente problema.

Problema 3. Prueba que las matrices $$A=\begin{pmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{pmatrix} \ \text{y} \ B=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 0 & 1 & 2 & 3 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$ son similares.

Solución. Para resolverlo usaremos el corolario de la entrada anterior. Al escribirlo en este contexto, dice lo siguiente:

Corolario. Sea $T:\mathbb{R}^4\rightarrow \mathbb{R}^4$ una transformación lineal. Sean $B’$ y $B»$ bases de $\mathbb{R}^4$ y $P$ la matriz de cambio de base de $B’$ a $B»$. Entonces $\text{Mat}_{B»}(T)=P^{-1} \text{Mat}_{B’}(T) P.$

Si podemos encontrar una transformación $T$ y bases $B’$ y $B»$ tales que $\text{Mat}_{B’}(T)=A$ y $\text{Mat}_{B»} (T)=B$, podemos calcular la matriz de cambio de base $P$, y satisface que $B=P^{-1}AP$, implicando que $A$ y $B$ sean matrices similares. Entonces, el problema se reduce a encontrar la transformación, las bases y calcular $P$.

Dado que $\text{Mat}_{B’}(T)=A$, si $B’$ es la base canónica, es claro que la transformación $T$ satisface que $T(X)=AX$ para todo $X\in\mathbb{R}^4$.

Ahora, encontremos $B»$. Sea $B»=\{ v_1,v_2,v_3,v_4 \}$ con

$$v_1=\begin{pmatrix} x_1 \\ y_1 \\ z_1 \\ w_1 \end{pmatrix}, v_2=\begin{pmatrix} x_2 \\ y_2 \\ z_2 \\ w_2 \end{pmatrix}, v_3=\begin{pmatrix} x_3 \\ y_3 \\ z_3 \\ w_3 \end{pmatrix}, v_4=\begin{pmatrix} x_4 \\ y_4 \\ z_4 \\ w_4 \end{pmatrix}.$$

Dado que $\text{Mat}_{B»}(T)=B$, entonces satisface

$$T(v_1)=Av_1=v_1, \ T(v_2)=Av_2=2v_1+v_2,$$

$$T(v_3)=Av_3=3v_1+2v_2+v_3, \ T(v_4)=Av_4=4v_1+3v_2+2v_3+v_4.$$

Resolviendo lo anterior, obtenemos que

$$Av_1=\begin{pmatrix} x_1+y_1 \\ y_1+z_1 \\ z_1+w_1 \\ w_1 \end{pmatrix}=\begin{pmatrix} x_1 \\ y_1 \\ z_1 \\ w_1 \end{pmatrix} \ \Rightarrow \ v_1=\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix},$$

$$Av_2=\begin{pmatrix} x_2+y_2 \\ y_2+z_2 \\ z_2+w_2 \\ w_2 \end{pmatrix}=\begin{pmatrix} x_2+2 \\ y_2 \\ z_2 \\ w_2 \end{pmatrix} \ \Rightarrow \ v_2=\begin{pmatrix} 1 \\ 2 \\ 0 \\ 0 \end{pmatrix},$$

$$Av_3=\begin{pmatrix} x_3+y_3 \\ y_3+z_3 \\ z_3+w_3 \\ w_3 \end{pmatrix}=\begin{pmatrix} x_3+5 \\ y_3+4 \\ z_3 \\ w_3 \end{pmatrix} \ \Rightarrow \ v_3=\begin{pmatrix} 1 \\ 5 \\ 4 \\ 0 \end{pmatrix},$$

y por último

$$Av_4=\begin{pmatrix} x_4+y_4 \\ y_4+z_4 \\ z_4+w_4 \\ w_4 \end{pmatrix}=\begin{pmatrix} x_4+9 \\ y_4+16 \\ z_4+8 \\ w_4 \end{pmatrix} \ \Rightarrow \ v_4=\begin{pmatrix} 1 \\ 9 \\ 16 \\ 8 \end{pmatrix}$$

Aquí estamos usando que los sistemas de ecuaciones que se obtienen tienen como variables libres a $x_1,x_2,x_3,x_4$, las cuales las estamos tomando todas ellas iguales a $1$.

Estos vectores son linealmente independientes pues la matriz con ellos como columnas es triangular superior con entradas en la diagonal distintas de cero, de modo que su matriz reducida es la identidad. Como $\mathbb{R}^4$ es de dimensión $4$ y $B»$ es un conjunto de cuatro vectores linealmente independientes, entonces $B»$ es una base. Más aún, $B»$ es una base tal que $\text{Mat}_{B»} (T)=B$, por construcción.

Finalmente, podemos calcular la matriz de cambio de base $P$ de $B’$ a $B»$, pero es fácil ya que $B’$ es la base canónica, entonces $$P=\begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 2 & 5 & 9 \\ 0 & 0 & 4 & 16 \\ 0 & 0 & 0 & 8 \end{pmatrix}.$$

Por propiedades de la matriz de cambio de base, sabemos que $P$ es invertible. Entonces, para terminar la prueba, podemos encontrar $P^{-1}$ y verificar que $B=P^{-1}AP$, o simplemente verificamos que $PB=AP$, y por lo tanto $A$ y $B$ son matrices similares. Lo haremos de la segunda manera. En efecto,

$$PB=\begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 2 & 5 & 9 \\ 0 & 0 & 4 & 16 \\ 0 & 0 & 0 & 8 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3 & 4 \\ 0 & 1 & 2 & 3 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 \end{pmatrix}=\begin{pmatrix} 1 & 3 & 6 & 10 \\ 0 & 2 & 9 & 25 \\ 0 & 0 & 4 & 24 \\ 0 & 0 & 0 & 8 \end{pmatrix}$$

$$AP=\begin{pmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 2 & 5 & 9 \\ 0 & 0 & 4 & 16 \\ 0 & 0 & 0 & 8 \end{pmatrix}=\begin{pmatrix} 1 & 3 & 6 & 10 \\ 0 & 2 & 9 & 25 \\ 0 & 0 & 4 & 24 \\ 0 & 0 & 0 & 8 \end{pmatrix}.$$

Por lo tanto, $A$ y $B$ son matrices similares.

Nota: si calculas la inversa de $P$, obtienes como resultado que $$P^{-1}=\begin{pmatrix} 1 & -\frac{1}{2} & \frac{3}{8} & -\frac{5}{16} \\ 0 & \frac{1}{2} & -\frac{5}{8} & \frac{11}{16} \\ 0 & 0 & \frac{1}{4} & -\frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{8} \end{pmatrix}.$$

$\square$

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: Bases numéricas y dígitos

Por Leonardo Ignacio Martínez Sandoval

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

\begin{align*}
M&=n(2d+1)!+2,\\
M+1&=n(2d+1)!+3,\\
&\vdots\\
M+(2d-1)&=n(2d+1)!+(2d+1)
\end{align*}

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.