Es fundamental durante la crisis del COVID implementar estrategias de distanciamiento social que eviten la propagación del virus. Si bien el virus tiene efectos tenues en el 80% de la población, queremos alentar lo más posible la propagación del virus para que el 20% restante pueda ser atendido sin rebasar la capacidad del sistema de salud.
Con esto en mente, la UNAM ya anunció la suspensión gradual de clases. La Facultad de Ciencias suspende clases ya desde mañana martes.
En estos días he estado pensando bastante en cómo enfrentar la situación como profesor universitario en la UNAM. Tomando en cuenta lo que les he preguntado por acá y pláticas que he tenido con otros colegas, me convencido de que:
No podemos asumir que los estudiantes tendrán acceso a computadora o a un buen internet continuamente.
No podemos asumir que los estudiantes estarán disponibles exactamente a la hora en la que usualmente es la clase.
No a todos los profesores se les hará fácil impartir de improvisto una versión de su clase de manera inmediata.
El material que se prepare debe ser gratuito, de libre acceso y de calidad.
Hay herramientas maravillosas como Google Classroom, Moodle y otras más. Pero desde mi perspectiva, no cumplen con los estándares de universalidad y libre acceso que este caso requiere.
Debido a esto, he decidido enfrentar a la crisis mediante la siguiente estrategia:
No usaré streamings o «medios en vivo» como chats para impartir la clase.
Para cada sesión, indicaré exactamente qué contenido de la bibliografía veríamos durante la clase.
Para cada sesión prepararé, además, con apoyo de los ayudantes del curso, una entrada aquí en el blog para que los estudiantes tengan ejemplos y explicaciones adicionales.
Acabo de avisar a la Coordinación de la Carrera de Matemáticas que ayudaré a los colegas del Departamento de Matemáticas que así lo requieran en orientarlos en escribir entradas de blog (con LaTeX y todo).
Así mismo, ofreceré de manera gratuita espacio de almacenamiento aquí en el blog para los colegas que requieran subir entradas o tareas. Esto con el fin de que no tengan que abrir cuentas de WordPress o buscar un servidor, y puedan dedicarse a escribir material para su curso de manera inmediata.
Si eres uno de estos colegas, o cualquier otro profesor, me puedes contactar por aquí o por FB para detalles.
En esta entrada platicaré de un lema muy útil en álgebra lineal, sobre todo cuando se están definiendo las nociones de base y de dimensión para espacios vectoriales de dimensión finita. Se trata del lema de intercambio de Steinitz.
Supondré que el lector ya sabe un poco de álgebra lineal, pero muy poquito. Basta con saber la definición de espacio vectorial. Lo demás lo definiremos sobre el camino.
El nombre del lema es en honor al matemático alemán Ernst Steinitz. Sin embargo, personalmente a mi me gusta pensarlo como el lema del «regalo de vectores», por razones que ahorita platicaremos. El enunciado es el siguiente:
Teorema (Lema de intercambio de Steinitz). Sea $V$ un espacio vectorial. Tomemos un conjunto finito y linealmente independiente $L$ de $V$, y un conjunto finito y generador $S$ de $V$. Supongamos que $L$ tiene $m$ elementos y que $S$ tiene $n$ elementos. Entonces:
$m\leq n$
Se puede tomar un subconjunto $T$ de $S$ de tamaño $n-m$ tal que $L\cup T$ sea generador de $V$.
En pocas palabras, «cualquier conjunto linealmente independiente tiene a lo mucho tantos elementos como cualquier conjunto generador y, además, cualquier generador le puede regalar vectores al linealmente independiente para volverlo generador».
De manera esquemática, está pasando lo siguiente:
Diagrama del lema de intercambio de Steinitz
Lo que haremos es hablar de las definiciones necesarias para entender el lema, hablar de la intuición detrás, dar un par de ejemplos y luego dar la demostración. La presentación está ligeramente basada en el libro de álgebra lineal de Titu Andreescu.
Definiciones e intuición
Sea $V$ un espacio vectorial sobre un campo $F$.
Si tenemos vectores $v_1,\ldots,v_n$ de $V$ y escalares $a_1,\ldots,a_n$ en $F$, podemos considerar al vector formado por multiplicar los vectores por los escalares correspondientes y sumarlos todos, es decir al vector $v$ dado por la expresión $a_1v_1+\cdots+a_nv_n$ . En este caso, decimos que $v$ es una combinación lineal de $v_1,\ldots,v_n$, o a veces que $v_1,\ldots,v_n$ generan a $v$.
Un conjunto $S=\{v_1,v_2,\ldots,v_n\}$ de vectores de $V$ es generador si para cualquier $v$ de $V$ existen escalares $a_1,\ldots,a_n$ en $F$ para los cuales $v=a_1v_1+\cdots+a_nv_n$. Dicho de otra forma, «$S$ es generador si cualquier vector del espacio vectorial es combinación lineal de vectores de $S$».
De esta definición es fácil ver que si $S$ es un conjunto generador y $T$ es un conjunto que contiene a $S$ (es decir, $T\supset S$), entonces $T$ también es generador: simplemente para cualquier $v$ usamos la combinación lineal que tenemos en $S$ y al resto de los vectores (los de $T\setminus S$) les ponemos coeficientes cero.
Un conjunto $L=\{w_1,w_2,\ldots,w_m\}$ de vectores de $V$ es linealmente independiente si la única combinación lineal de vectores de $L$ que da $0$ es aquella en la que todos los escalares son $0$. Dicho de otra forma, «$L$ es linealmente independiente si $a_1w_1+\ldots+a_mw_m=0$ implica que $a_1=a_2=\ldots=a_m=0$.»
Con los conjuntos linealmente independientes pasa lo contrario a lo de los generadores. Si $L$ es un conjunto linealmente independiente y $M$ está contenido en $L$ (es decir, ahora $M\subset L$), entonces $M$ es linealmente independiente. Esto sucede pues cualquier combinación lineal de $M$ también es una combinación lineal de $L$. Como no hay ninguna combinación lineal no trivial de elementos de $L$ que sea igual a cero, entonces tampoco la hay para $M$.
Los párrafos anteriores dejan la idea de que «los conjuntos generadores tienen que ser grandes» y que «los conjuntos linealmente independientes tienen que ser chiquitos». El lema de intercambio de Steinitz es una manera en la que podemos formalizar esta intuición.
Como los conjuntos generadores son «grandes», entonces son bien buena onda y bien generosos. Tienen muchos elementos. Como los conjuntos linealmente independientes son «chiquitos», entonces necesitan elementos. Lo que dice el lema de intercambio de Steinitz es que si tenemos a un generador $S$ y a un linealmente independiente $L$, entonces $S$ tiene más elementos y que puede regalar al linealmente independiente $L$ algunos elementos $T$ para que ahora $L\cup T$ tenga tantos elementos como tenía $S$ y además se vuelva generador. Una cosa importante es que no cualquier subconjunto $T$ funciona. Este tiene que estar bien elegido.
Ejemplo concreto del lema de intercamio de Steinitz
Veamos un ejemplo muy concreto. Supongamos que nuestro espacio vectorial es $\mathbb{R}^3$, osea, los vectores con $3$ entradas reales. Tomemos a los siguientes conjuntos de vectores:
$L=\{(1,2,3), (0,3,0)\}$
$S=\{(0,1,0), (1,0,0), (0,0,-1), (2,4,6)\}$
Por un lado, el conjunto $L$ es linealmente idependiente. Una combinación lineal $a(1,2,3)+b(0,3,0)=(0,0,0)$ implica de manera directa que $a=0$ (por la primer o tercer coordenadas) y de ahí $b=0$ (por la segunda coordenada).
Por otro lado, el conjunto $S$ es generador, pues con $(0,0,-1)$ podemos obtener a $(0,0,1)$ como combinación lineal, de modo que $S$ genera a los tres de la base canónica y por tanto genera a todo $\mathbb{R}^3$.
Notemos que en efecto $L$ tiene menos elementos que $S$. Además, el lema de intercambio de Steinitz garantiza que $S$ puede pasarle $|S|-|L|=4-2=2$ elementos a $L$ para volverlo generador. Pero hay que ser cuidadosos. Si le regala los elementos $(0,1,0)$ y $(2,4,6)$, entonces no funciona (se puede verificar que este conjunto no genera a $\mathbb{R}^3$). Pero si le regala, por ejemplo, los elementos $(1,0,0)$ y $(0,0,-1)$ entonces ahora sí generará (se puede argumentar viendo que entonces ahora genera a los tres de la base canónica).
Demostración del lema de intercambio de Steinitz
Pasemos ahora a la demostración del lema de Steinitz. Lo demostraremos por inducción en la cantidad de elementos que tiene $L$, el linealmente independiente. Si $|L|=m=0$, entonces claramente $m=0\leq n$, y además $S$ le puede pasar $n-0=n$ elementos (todos) a $L$ y volverlo generador.
Supongamos entonces que es cierta la siguiente afirmación.
Hipótesis inductiva Sea $V$ un espacio vectorial. Tomemos un conjunto finito y linealmente independiente $L$ de $V$, y un conjunto finito y generador $S$ de $V$. Supongamos que $L$ tiene $m$ elementos y que $S$ tiene $n$ elementos. Entonces:
$m\leq n$
Se puede tomar un subconjunto $T$ de $S$ de tamaño $n-m$ tal que $L\cup T$ sea generador de $V$.
Para el paso inductivo, tomemos $L=\{w_1,w_2,\ldots,w_m,w_{m+1}\}$ un linealmente independiente de $V$ y $S=\{v_1,v_2,\ldots,v_n\}$ un generador de $V$. Aplicándole la hipótesis inductiva al linealmente independiente $L’=L\setminus \{w_{m+1}\}=\{w_1,\ldots,w_m\}$ y al generador $S$, tenemos que:
$m\leq n$
Se puede tomar un subconjunto $T’=\{s_1,s_2,\ldots,s_{n-m}\}$ de $S$ tal que $L’\cup T’= \{w_1,w_2,\ldots,w_m,s_1,\ldots,s_{n-m}\}$ sea generador de $V$.
Como $L’\cup T’$ es generador, entonces podemos poner a $w_{m+1}$ como combinación lineal de elementos de $L’\cup T’$, es decir, existen $a_1,\ldots, a_m, b_1,\ldots,b_{n-m}$ tales que $$w_{m+1}=a_1w_1+\ldots+a_mw_m+b_1s_1+\ldots+b_{n-m}s_{n-m}.$$
Ya sabemos que $m\leq n$. Si $m=n$, la combinación lineal anterior no tendría ningún $s_i$, y entonces sería una combinación lineal no trivial para los elementos de $L$, lo cual es una contradicción pues $L$ es linealmente independiente. Entonces $m\neq n$ y $m\leq n$, así que $m+1\leq n$, que era el primer punto que queríamos probar.
También, como $L$ es linealmente independiente, no se vale que todos los $b_i$ sean iguales a cero. Sin perder generalidad, podemos suponer que $b_1\neq 0$. Así, $s_1$ se puede despejar como combinación lineal en términos de $w_1,\ldots,w_n,w_{n+1}, s_2,\ldots,s_{n-m}$ y por lo tanto $L\cup (T’\setminus \{s_1\})$ genera lo mismo que $L’\cup T’$, que era todo $V$. Así, $T:=T’\setminus \{s_1\}$ es el subconjunto de $S$ de tamaño $n-(m+1)$ tal que $L\cup T$ es generador. Esto termina la prueba del lema.
Algunas aplicaciones
El lema de intercambio de Steinitz se puede utilizar para probar varias afirmaciones con respecto a bases de un espacio vectorial de dimensión finita.
Un espacio vectorial es de dimensión finita si tiene un conjunto generador con una cantidad finita de elementos. Una base de un espacio vectorial es un conjunto que sea simultáneamente generador y linealmente independiente.
Las siguientes afirmaciones se siguen directamente del lema de Steinitz.
Todas las bases de un espacio vectorial finito tienen la misma cantidad de elementos.
En un espacio vectorial de dimensión $d$:
Todo conjunto linealmente independiente tiene a lo más $d$ elementos.
Todo conjunto generador tiene al menos $d$ elementos.
Si $S$ es un conjunto con $n$ vectores de un espacio vectorial de dimensión $n$, entonces las siguientes tres afirmaciones son equivalentes:
El conjunto $S$ es base.
$S$ es linealmente independiente.
$S$ es generador.
Como primer ejemplo, haremos (1). Tomemos $B_1$ y $B_2$ bases de un espacio vectorial de dimensión finita $B$. Pensando a $B_1$ como linealmente independiente y a $B_2$ como generador, tenemos $|B_1|\leq |B_2|$. Pensando a $B_2$ como linealmente independiente y a $B_1$ como generador, tenemos $|B_2|\leq |B_1|$. Así, $|B_1|=|B_2|$.
Como segundo ejemplo, haremos una parte de (3). Suponiendo que $S$ es un conjunto de $n$ vectores de un espacio vectorial de dimensión $n$, veremos que su independencia lineal implica $S$ es base. Sea $B$ una base de $V$. Por el lema de Steinitz, podemos pasar $|B|-|S|=n-n=0$ elementos de $B$ a $S$ para volverlo generador. Es decir, $S$ ya es generador. Como además es linealmente independiente, entonces es base.
El resto de las demostraciones son igual de sencillas, como puedes verificar.
Más adelante…
El lema de Steinitz es la herramienta clave para definir dar la definición de dimensión de espacios vectoriales en el caso de dimensión finita. Lo usaremos una y otra vez. Por esta razón, es muy recomendable repasar su demostración y entender a profundidad qué dice.
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.
Replica por tu cuenta la demostración del lema de Steinitz hasta que te sientas cómodo con los argumentos.
En el ejemplo que se dio de la aplicación del lema de Steinitz, ¿cuáles son todas las posibilidades de $2$ elementos que se pueden pasar para que $L$ se convierta en generador?
Usa el lema de Steinitz para demostrar el resto de consecuencias que mencionamos.
¿Qué te dice el lema de Steinitz cuando $L$ y $S$ son inicialmente del mismo tamaño?
Muestra que en el lema de Steinitz la hipótesis de que $L$ sea finito no es necesaria, es decir, que incluso sin esta hipótesis se pueden mostrar todas las conclusiones.
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»
Una de las nociones más importantes en álgebra lineal es la de «matriz invertible». Llamemos $I_n$ a la matriz identidad de $n\times n$, es decir, a la que tiene $1$ en cada entrada de la diagonal principal, y $0$ en las demás.
Una matriz $A$ de $n\times n$ es invertible si existe una matriz $B$ de $n\times n$ tal que $AB=I_n=BA$.
Una consecuencia rápida es que dicha matriz $B$ es única, así que le podemos dar la notación $A^{-1}$. De la definición (y asociatividad) se puede ver rápido que si $A_1$ y $A_2$ son invertibles, entonces su producto $A_1A_2$ también, con inversa $A_2^{-1}A_1^{-1}$, en otras palabras, «producto de invertibles es invertible».
Un detalle curioso de la definición es que pide no sólo que $AB=I_n$, sino que para la misma matriz $B$ también se tenga que $BA=I_n$. Por un lado, a priori esto tiene sentido pues el producto de matrices no es conmutativo, es decir, ocurre a veces que $AB\neq BA$. Sin embargo, como veremos más adelante en esta entrada, en la definición de matriz invertible basta con tener una de estas igualdades.
De hecho, la idea de esta entrada es presentar y demostrar varias equivalencias a la afirmación «$A$ es una matriz invertible». La presentación sigue un poco el orden de ideas del capítulo 3.4 del libro Essential Linear Algebra with Applications: A Problem-Solving Approach de Titu Andreescu. La idea es explicar el siguiente diagrama, en donde agrupamos a las equivalencias en grupitos que corresponden a partes de una mariposa:
Algunas definiciones
Antes de enunciar el resultado principal, conviene recordar algunas definiciones y un par de resultados importantes.
Una operación elemental es aplicar a una matriz de las siguientes operaciones:
Intercambio de dos filas.
Multiplicar todas las entradas de alguna de sus filas por un elemento $c$ no cero.
Sumar a una fila un múltiplo de otra fila.
Una matriz elemental es una matriz obtenida de aplicar a $I_n$ exactamente una operación elemental.
Una fila de una matriz es una fila cero si todas sus entradas son iguales a cero. A la primer entrada no cero (de izquierda a derecha) de una fila que no sea fila cero se le llama pivote. Una matriz es escalonada reducida si cumple las siguientes tres propiedades:
Todas las filas cero están hasta abajo.
En todas las filas no cero los pivotes son iguales a $1$.
Si una fila no cero $F_1$ está arriba de otra fila no cero $F_2$, entonces el pivote de $F_1$ está estrictamente a la izquierda del pivote de $F_2$.
Si una entrada tiene al pivote de una fila, entonces todas las demás entradas de la columna son iguales a $0$.
Un resultado (no trivial) es que cualquier matriz se puede llevar a una (y sólo una) matriz escalonada reducida $A_{\text{red}}$ usando únicamente operaciones elementales, a la cual le llamamos su forma escalonada reducida. Estas son todas las definiciones que necesitamos. Estamos listos para pasar al enunciado del teorema principal.
Teorema de la mariposa de equivalencias
Teorema: Sea $A$ una matriz de $n\times n$ con entradas en un campo $F$. Entonces, todas las siguientes afirmaciones son equivalentes:
$A$ es una matriz invertible.
La forma escalonada reducida $A_{\text{red}}$ de $A$ es $I_n$.
$A$ es producto de matrices elementales.
Para todo $b\in F^n$, el sistema de ecuaciones $Ax=b$ tiene una única solución $x\in F^n$.
Para todo $b\in F^n$, el sistema de ecuaciones $Ax=b$ tiene una solución $x\in F^n$.
Existe una matriz $B$ de $n\times n$ tal que $AB=I_n$.
Existe una matriz $B$ de $n\times n$ tal que $BA=I_n$.
Por supuesto, estas no son todas las formas de caracterizar una matriz invertible. Hay otras formas de hacerlo en términos de determinantes, por ejemplo. En el camino recordaremos varias de las definiciones que están en este teorema.
Le llamo el teorema de la mariposa de equivalencias porque podemos agrupar a estos números en tres «grupos» principales de equivalencias «parecidas», que además nos van a recordar cómo va la prueba.
Primero veremos la equivalencia entre 1, 2 y 3 (un ala). Luego, entre 1,4,5 (otra ala). Después, entre 1 y 6 (antena derecha). Finalmente, entre 1 y 7 (antena izquierda).
Un par de lemas auxiliar
Antes de demostrar el teorema de equivalencias, enunciamos y argumentamos dos resultados útiles
Es fácil convencerse de que aplicar una operación elemental a una matriz $A$ es lo mismo que multiplicar a $A$ por la izquierda por la matriz elemental correspondiente a la operación. Como toda matriz $A$ se puede llevar a su forma escalonada reducida mediante operaciones elementales, concluimos lo siguiente.
Lema 1: Para toda matriz $A$ existe una matriz $E$ que es producto de matrices elementales tal que $EA$ es la forma escalonada reducida de $A$, es decir $EA=A_{\text{red}}$.
También es fácil convencerse de que cada matriz elemental es invertible, pues las operaciones elementales se pueden revertir, y la inversa de la matriz elemental $M$ es precisamente la matriz elemental correspondiente a la operación inversa. Además, producto de matrices invertibles es invertible. De este modo, concluimos lo siguiente:
Lema 2: Si $E$ es una matriz que es producto de matrices elementales, entonces $E$ es invertible y también es producto de matrices elementales.
La demostración del teorema de la mariposa
Usaremos el diagrama de la mariposa para demostrar todas las equivalencias. Lo que haremos es probar una implicación por cada una de las siguientes flechas:
Empezamos con el ala izquierda de la mariposa.
(1) implica (2): Tomemos una matriz invertible $A$. Por el Lema 1, existe una matriz producto de elementales tal que $EA=A_{\text{red}}$. Como $E$ y $A$ son invertibles, entonces $A_{\text{red}}$ también es invertible.
Si $A_{\text{red}}$ tuviera una fila cero, digamos la $j$, no sería invertible. Esto sucede ya que para cualquier matriz $B$ de $n\times n$ tendríamos que la fila $j$ de $AB$ también sería cero, y entonces $AB$ nunca sería $I_n$. Como sabemos que $A_{\text{red}}$ es invertible, entonces todas sus filas no son cero y por lo tanto todas tienen pivote. Así, tenemos $n$ pivotes y por lo tanto tiene que haber exactamente un pivote por columna. Como $A_{\text{red}}$ es escalonada reducida, estos pivotes tienen que estar exactamente uno en cada entrada de la diagonal principal. Como además cada pivote es la única entrada no cero de su columna, concluimos que $A_{\text{red}}$ es la identidad.
(2) implica (3): Tomemos una matriz $A$ cuya forma escalonada reducida es la identidad. Por el Lema 1, existe una matriz producto de elementales tal que $EA=A_{\text{red}}=I_n$. Por el Lema 2, $E$ es invertible y $E^{-1}$ es producto de matrices elementales. Multiplicando por $E^{-1}$ a la izquierda a la identidad $EA=I_n$ obtenemos $A=E^{-1}$, es decir, $A$ es producto de matrices elementales.
(3) implica (1): Finalmente, si $A$ es producto de matrices elementales, por el Lema 2 tenemos que $A$ es invertible.
Con esto terminamos la primer ala de la mariposa. Notemos que cierran un ciclo, así que a partir de ahora podemos usar libremente la equivalencia entre 1, 2 y 3. Hagamos la segunda ala.
(1) implica (4): Supongamos que $A$ es invertible y tomemos cualquier $b$ en $F^n$. Notemos que $A^{-1}b$ es solución de $Ax=b$ pues satisface $A(A^{-1}b)=I_n b=b$. Además, si $x$ y $y$ son soluciones de $Ax=b$, tendríamos que $Ax=Ay$ y mutiplicando por $A^{-1}$ a la izquierda tendríamos que $x=y$. De este modo, $Ax=b$ tiene una única solución para todo $b$ en $F^n$.
(4) implica (5): Esta demostración es inmediata. Si $Ax=b$ tiene una única solución, en particular tiene una solución.
(5) implica (1): Supongemos que $Ax=b$ tiene una solución $x$ en $F^n$ para todo $b$ en $F^n$. Afirmamos que esto implica que $A_{\text{red}}x=b$ tiene solución para para todo $b$ en $F^n$. Tomemos una $b$ en $F^n$. Por el Lema 1, hay una matriz invertible $E$ tal que $A_{\text{red}}=EA$. Por hipótesis, existe una solución $x$ para $Ax=E^{-1}b$. Tomemos esa $x$. Notemos que $A_{\text{red}}x=(EA)x=E(Ax)=E(E^{-1}b)=b$. Es decir, justo esa $x$ es solución para $A_{\text{red}}x=b$.
En particular, $A_{\text{red}}x=e_j$ tiene solución para cuando $e_j$ es el vector cuya $j$-ésima entrada es $1$ y las demás cero. Así, es imposible que la $j$-ésima fila de $A_{\text{red}}$ sea cero, ya que en caso contrario $Ax$ siempre tendría $j$-ésima entrada cero y $Ax=e_j$ no tendría solución. Como ya vimos antes, si $A_{\text{red}}$ no tiene filas cero, entonces es la identidad. Por la equivalencia entre (1) y (2) concluimos que $A$ es invertible.
Esto termina las equivalencias en la segunda ala, así que ahora podemos usar libremente las implicaciones entre 1, 2, 3, 4 y 5. Ya nada más nos faltan las antenas.
Por supuesto, las implicaciones (1) implica (6) y (1) implica (7) son triviales, pues la matriz de (1) en particular funciona para (6) y (7). Lo que falta ver son los regresos de estas implicaciones.
(6) implica (1): Supongamos que existe una matriz $B$ tal que $AB=I_n$. Tomemos $b$ en $F^n$. Notemos que $Bb$ es solución de $Ax=b$ pues $A(Bb)=(AB)b=I_nb=b$. De este modo, $Ax=b$ tiene solución para todo $b$ en $F^n$ y por la equivalencia entre (1) y (5) tenemos que $A$ es invertible. Si tomamos a su inversa $A^{-1}$ y la multiplicamos a la izquierda en la hipótesis, obtenemos $B=A^{-1}$, de modo que también $BA=I_n$.
(7) implica (1): Supongamos que existe una matriz $B$ tal que $BA=I_n$. Por la equivalencia entre (1) y (6), tenemos que $B$ es invertible, de inversa $B^{-1}$. De este modo, $A=(B^{-1}B)A=B^{-1}(BA)=B^{-1}I_n=B^{-1}$. De este modo, $A$ es la inversa de una matriz invertible y por tanto es invertible, y por lo tanto $AB=B^{-1}B=I_n$.
¡Listo! Con esto tenemos la equivalencia entre todas las afirmaciones.
¿Ahora qué?
Si te gustó esta entrada, puedes compartirla o revisar otras relacionadas con matemáticas a nivel universitario:
Se nos acaba el año, y con él los años 10’s. Cada década ha traído muchas cosas buenas y malas.
Las cosas malas están en los medios y ya las tenemos presentes. Tenemos que seguir trabajando para que cada vez sean menos. Me enorgullece mucho la fuente lucha que están haciendo mis amigos y conocidos contemporáneos en causas importantes como el feminismo, la ecología, la normalización/atención a problemas psicológicos/psiquiátricos y el desarrollo científico/tecnológico.
Las cosas buenas también han sido bastantes, y qué mejor momento para recordarlas y agradecerlas, que cuando cambia el dígito de las decenas del año actual.
De los 80’s no recuerdo prácticamente nada, pero agradezco enormemente los cuidados de mis padres en mi primer año de vida.
De los 90’s agradezco y recuerdo mi infancia, los videojuegos, la educación primaria y las experiencias de vivir en cuatro estados.
De los 00’s agradezco y recuerdo el boom de internet, el campamento de mate en Stanford, mi primer amor y encontrar a través de la Olimpiada mi rumbo profesional.
De los 10’s agradezco y recuerdo mi vida independiente, mi maduración profesional, mi vida como extranjero y superar con éxito una delicada situación de salud.
Los 20’s me dan una enorme curiosidad, una pizca de miedo, pero sobre todo un gran entusiasmo.
Espero que pasen este último día de diciembre en grata compañía de sus seres queridos. Si tienen chance, entre sidra, calzones rojos y campanadas, los invito a acordarse y agradecer un ratito lo que les ha pasado en cada década.
Les comparto un problema que se me ocurrió en las (muchas) horas que he pasado en el carro escuchando música, cuando vivía en la Ciudad de México. El estéreo del carro ordena las canciones alfabéticamente. Tiene un botón que permite «avanzar una canción». Pero a veces tarda mucho: si estoy escuchando «Adele – Hello», hay que apretar el botón muchas veces para llegar a «Shakira – Dónde están los ladrones».
En esas épocas descubrí una estrategia «intuitiva» para llegar más rápido a la canción. La idea es la siguiente: pasar temporalmente al modo de «canción aleatoria», apretar el botón unas cuantas veces para acercarme a la canción que quiero (en el ejemplo anterior, digamos que después de dos o tres veces el botón me lleva a «Paquita la del Barrio – Rata de dos Patas»), y de ahí quitar el aleatorio y avanzar normal. Eso, intuitivamente, siempre me ahorró muchos pasos. El problema consiste en encontrar la estrategia óptima, en donde se permiten mezclar pasos normales y aleatorios.
Para eso, voy a plantear un problema muy concreto. De aquí en adelante supondré que el lector sabe un poco de probabilidad. Pensemos que hay $2n$ canciones, numeradas de $1$ a $2n$. Estoy en la canción $n$ y quiero llegar a la canción $2n$. Pensemos que el estéreo tiene exactamente dos botones, el $A$ que avanza $1$ (y de $2n$ lleva a $1$), y el $B$ que lleva a una canción aleatoria (cualquiera de las canciones, incluida la actual, tiene probabilidad $1/2n$ de ser elegida). En cada paso se permite ver en qué canción estoy, y de ahí decidir apretar $A$ o $B$. ¿Cuál es la estrategia que en valor esperado tiene menos pasos? ¿Cuál es ese valor esperado?
En la imagen de aquí abajo se muestra un ejemplo de una forma de apretar los botones para $n=5$, con $2n=10$ canciones. Las flechas rojas corresponden a avanzar $1$ apretando el botón $A$. Las flechas azules corresponden a ir a un lugar aleatorio apretando el botón $B$. Se apretaron los botones en el orden $ABBAA$, de modo que se hicieron $5$ pasos.
Un ejemplo en el que se usa la estrategia ABBAA. La canción 1 es de ABBA. Es Dancing Queen. «Feel the beat form the tambourine… Oh yeah…».
Ese es el enunciado del problema. De aquí en adelante empiezo a hablar de ideas para resolverlo, así que si quieres intentarlo, este es el momento correcto.
Primeras ideas
Notemos que la estrategia «siempre $A$, hasta llegar a $2n$» toma exactamente $n$ pasos siempre. La estrategia «siempre $B$» es para intentar atinarle, y en cada paso tiene probabilidad de éxito $1/2n$. Entonces, en esta segunda estrategia la cantidad de pasos requeridos es una variable aleatoria con distribución geométrica de parámetro $p=1/2n$, de modo que el número esperado de pasos es $1/p=2n$.
Sin embargo, suena a que la estrategia esbozada al inicio de esta entrada es intuitivamente mejor: usar el $B$ para acercarse y luego el $A$ para llegar.
La solución
Vamos a mostrar que la mejor estrategia en valor esperado es la siguiente: «apretar el botón $B$ hasta llegar aproximadamente al intervalo $[n-2\sqrt{n}, n]$, y de ahí apretar el botón $A$» hasta llegar a $n$.
El primer argumento es que en cada paso, lo que hace la estrategia sólo depende de en qué canción estamos. En efecto, el paso $A$ es determinista y el $B$ es una variable uniforme independiente de todo lo demás.
El segundo argumento es que, si en algún momento de la estrategia usamos el botón $A$, entonces después de ello nunca nos conviene usar el botón $B$. Lo probamos por contradicción: supongamos que por cualquier razón en la estrategia óptima tenemos que hacer un $AB$. El paso $A$ es determinista, y sabíamos exactamente a qué canción nos iba a llevar (a la siguiente). Pero hacer el paso $B$ en cualquier lugar que estemos es simétrico, pues nos lleva a una canción aleatoria. Si a priori sabíamos que íbamos a hacer un paso $B$, lo mejor es hacerlo lo antes posible. Así, la estrategia que substituye esos pasos $AB$ por $B$ se ahorra un paso, y no es óptima. Contradicción.
Ahora, afirmo lo siguiente. Si la estrategia óptima es apretar $A$ cuando estamos en la canción $j$, entonces también va a ser apretar $A$ cuando estemos en cualquier canción $k$ con $j\leq k < 2n$. Esto es debido al argumento anterior: al apretar $A$ llegamos a $j+1$, que por el párrafo de arriba, no le puede tocar $B$. Entonces le toca $A$. De ahí llegamos a $j+2$, que de nuevo no le puede tocar $B$. Y así sucesivamente (inductivamente), hasta llegar a $2n-1$.
Lo que acabamos de probar es que la estrategia óptima se ve de la siguiente manera para algún entero $k$: «Apretar $B$ hasta que lleguemos a alguno de los últimos $k$ elementos. De ahí, apretar $A$ hasta llegar a $2n$.» Nos falta determinar cuál es la mejor $k$ que podemos usar.
A estas alturas ya podemos calcular explícitamente el valor esperado de pasos en esta estrategia. El evento «llegar a alguno de los últimos $k$ elementos» tiene probabilidad $k/2n$ de ocurrir cada que se aprieta el botón $B$, así que la cantidad de veces que hay que apretar $B$ para ello es una variable aleatoria geométrica de valor esperado $2n/k$. Una vez que llegamos a los últimos $k$ elementos, caemos a cualquier elemento del intervalo $\{2n-k+1, 2n-k+2,\ldots,2n\}$ con la misma probabilidad, y respectivamente nos tomará $\{k-1, k-2,\ldots, 0\}$ pasos en llegar a $2n$, es decir, la cantidad de pasos que hacemos es una variable aleatoria uniforme discreta de media $(k-1)/2$.
Así, en total usamos $(2n/k) + (k-1)/2$ pasos para llegar. Queremos lograr que esta expresión sea lo más pequeña posible. Usando la desigualdad entre la media geométrica y la aritmética, notamos que $$\frac{2n}{k}+\frac{k-1}{2}=\frac{2n}{k}+\frac{k}{2}-\frac{1}{2} \geq 2\sqrt{n} – \frac{1}{2},$$ y que la igualdad se da si y sólo si $\frac{2n}{k}=\frac{k}{2}$, es decir, si y sólo si $k=2\sqrt{n}$. En este caso, la cantidad media de pasos que usamos es $2\sqrt{n}-\frac{1}{2}$.
Aquí arriba hicimos un poquito de trampa. En realidad $k=2\sqrt{n}$ tiene sentido para la estrategia sólo cuando $\sqrt{n}$ es un número entero. Sin embargo, por la convexidad de la función $ \frac{2n}{k}+\frac{k}{2}$ tenemos la garantía de que o bien $\lfloor 2\sqrt{n} \rfloor$ o bien $\lceil 2\sqrt{n} \rceil$ dan el máximo.
Conclusión y otros problemas
Está cool que hayamos bajado la cantidad de pasos que se necesitan de valor esperado de algo que era $n$ a algo que es del tamaño $2\sqrt{n}$. Para hacerse una idea de los pasos que se pueden ahorrar, toma una colección de $800$ canciones. Originalmente se necesitaban $400$ pasos $+1$ para ir de la mitad al final. Con la nueva estrategia se requieren como $40$.
Hacer esta estrategia en la vida real es un poco complicado pues los estéreos no muestran el número exacto de la canción en la que se está, además de que es difícil memorizar a qué canción le toca qué número. Pero a veces sí muestran el nombre de la canción y más o menos «se le puede aproximar».
Hay un par de variantes interesantes. Una es ¿qué sucede si además de tener botón $+1$ y aleatorio, también tenemos botón $-1$?. En esta variante la solución no cambia mucho, pero es bueno intentarla para repasar las ideas de la prueba.
La otra variante es la siguiente. La estrategia óptima, como está descrita arriba, tiene un problema: es posible que nunca termine, o que tome muchísimos pasos en terminar (esto será muy improbable y por eso el valor medio se compensa). Así, imaginemos que queremos la restricción adicional de que la estrategia que usemos nunca use más de, digamos, 4n pasos. En esta variante: ¿cuál es la estrategia óptima? ¿cuántos pasos toma?
¿Ahora qué?
Si te gustó esta entrada, puedes compartirla o revisar otras relacionadas con matemáticas a nivel universitario:
