Región fundamental de un retículo

 Sea $\varLambda$ un retículo completo sobre $\mathbb{R}^n$. Sea $B$ una base que genera el retículo $\varLambda$.

Llamamos región fundamental del retículo $\varLambda(B)$ al conjunto:

$$\mathcal{F}(\varLambda(B)) = \{ \sum_{i=1}^{n}t_i·\vec{b_i} \mid t_i \in [0,1) \wedge \vec{b_i} \in B; \forall i \in \{1,...,n\} \}$$

Dicha región fundamental también es conocida como dominio fundamental o paralelepípedo fundamental.

A modo de ejemplo, retomamos el retículo completo sobre $\mathbb{R}^2$ generado por $B = \{ (5, 3), (5, 0) \}$

 

Su región fundamental tiene la siguiente representación gráfica (importante observar la frontera):

 

Una vez definida la región fundamental, podemos realizar las siguientes observaciones:

• El $\vec{0}$ siempre pertenece a la región fundamental, independientemente de la base que genera el retículo $\varLambda$.
• Excluyendo el $\vec{0}$, los vectores de la región fundamental NO pertenecen al retículo $\varLambda$.
• Si cambiamos la base generadora del retículo, la región fundamental asociada también cambia. 

Si en el mismo retículo completo del ejemplo anterior cogemos la base $C = \{(0,3), (5,0)\}$, la región fundamental queda representada de la siguiente manera:

Sin embargo,

• aunque cambie la región fundamental, el "volumen n-dimensional" de la región fundamental (n-paralelepípedo o paralelótopo) es invariante. ¿Por qué? Porque se calcula con el determinante y se explicó un resultado al respecto en la anterior entrada.
• Con la región fundamental podemos teselar todo el espacio $\mathbb{R}^n$.

Teselado de $\mathbb{R}^2$ con la región fundamental $\mathcal{F}(\varLambda(C))$.

 

 

Determinante de un retículo

 Sea $\varLambda$ un retículo completo sobre $\mathbb{R}^n$. Sea $B$ una base que genera el retículo $\varLambda$.

 Podemos definir el determinante del retículo como el valor absoluto del determinante de la matriz $B$:

$$det(\varLambda) = |det(B)|$$

Dicho resultado es independiente de la base escogida, dado que si tenemos otra base $C$ del retículo $\varLambda$, en la entrada anterior vimos que:

$\varLambda(B) = \varLambda(C) \Longleftrightarrow \exists U \in M_{nxn}(\mathbb{Z}) \mid U$ es invertible y $C = B · U$ 

 Por tanto, si escogemos otra base $C$ que genere el mismo retículo, como U es invertible:

 $$|det(C)|= |det(B · U)| = |det(B) · det(U)| = |det(B)| · |det(U)| = |det(B)| · 1 = |det(B)|$$

 

Ejemplo:

 Utilizamos de nuevo el retículo completo $\varLambda$ sobre $\mathbb{R}^2$ generado por la base $B = \pmatrix{5 && 5 \\ 3 && 0}$.

 

 El determinante de dicho retículo es:

$$det(\varLambda) = |det(B)| = |det\pmatrix{5 && 5 \\ 3 && 0}| = |5 · 0 - 5 · 3| = |-15| = 15$$

Bases que generan el mismo retículo

En la teoría de retículos sobre $\mathbb{R}^n$ hay un resultado muy interesante que es el siguiente: 

Sean $\varLambda(B)$ y $\varLambda(C)$ dos retículos completos sobre $\mathbb{R}^n$ generados por las bases $B$ y $C$ respectivamente.

$\varLambda(B) = \varLambda(C) \Longleftrightarrow \exists U \in M_{nxn}(\mathbb{Z}) \mid U$ es invertible y $B = C · U$ 

Voy a destacar dos aplicaciones del resultado anterior.

APLICACIÓN 1. Si conocemos las bases de 2 retículos completos, podemos saber si generan el mismo retículo. Como $C$ es invertible en $M(\mathbb{R})$ (por ser base):

$$B = C · U \Leftrightarrow C^{-1} · B = C^{-1} · C · U \Leftrightarrow C^{-1} · B = I · U \Leftrightarrow C^{-1} · B = U$$ 

Por tanto, si $C^{-1} · B \in M(\mathbb{Z})$ (todos sus elementos son enteros) y es invertible en $M(\mathbb{Z})$ (su determinante es 1 o -1), entonces $B$ y $C$ generan el mismo retículo.

 

Ejemplo: 

En la entrada anterior utilizamos la siguiente base $B = \pmatrix{5 && 5 \\ 3 && 0}$ de un retículo completo sobre $\mathbb{R}^2$.

 

Y acabé afirmando que era exactamente el mismo retículo que generaría el conjunto $C = \pmatrix{0 && 5 \\ 3 && 0}$ o el conjunto $D = \pmatrix{-5 && 0 \\ 3 && -3}$.

Vamos a realizar la comprobación con $D$. Es decir, queremos llegar a la conclusión de que $B$ y $D$ generan el mismo retículo.

 

Calculamos

$D^{-1} · B = \pmatrix{-5 && 0 \\ 3 && -3}^{-1} · \pmatrix{5 && 5 \\ 3 && 0} = \pmatrix{-1 && -1 \\ -2 && -1}$

 

Ahora calculamos su determinante:

$|D^{-1} · B| = \begin{vmatrix}-1 && -1 \\ -2 && -1\end{vmatrix} = -1$

 

Así pues, hemos visto que todos sus elementos son enteros y que el resultado del determinante es -1. Por tanto, podemos afirmar que $B$ y $D$ generan el mismo retículo.

 

Nota: las operaciones anteriores las he realizado con wxMaxima.

 

 APLICACIÓN 2. Si tenemos una base $B$ de un retículo completo $\varLambda(B)$, podemos construir otra base $C$ que genera el mismo retículo multiplicando $B$ por una matriz $U \in M_{nxn}(\mathbb{Z})$ con determinante 1 o -1.

 

Ejemplo: 

 Utilizamos el retículo completo del ejemplo anterior, generado por $C = \pmatrix{0 && 5 \\ 3 && 0}$.

Ahora creamos una matriz aleatoria con elementos enteros y cuyo determinante sea 1 o -1.

$U = \begin{pmatrix}2283 & -118\\1838 & -95\end{pmatrix}$; $|U| = -1$ 

Y multiplicamos la base original por esta matriz.

$C · U = \pmatrix{0 && 5 \\ 3 && 0} · \begin{pmatrix}2283 & -118\\1838 & -95\end{pmatrix} = \begin{pmatrix}9190 & -475\\6849 & -354\end{pmatrix}$

El resultado es otra base que genera el mismo retículo.

Cálculos con wxMaxima:

 

 ¿Qué utilidad puede tener generar otra base de esta manera? Esto lo trataré en otra entrada de esta serie sobre retículos.

Matrices invertibles en $M(\mathbb{Z})$

Por definición, dada una matriz $A$,

$A$ es invertible $\Longleftrightarrow$ $\exists B$ tal que $A · B = I$   y   $B · A = I$

Donde $I$ es la matriz identidad.

De lo anterior se deduce que la matriz debe ser cuadrada. 

 

Cuando trabajamos con matrices cuyos elementos son números reales ($M(\mathbb{R})$), sabemos que

$A$ es invertible $\Longleftrightarrow$ $|A|\neq 0$

 

 Sin embargo, si cambiamos el conjunto de matrices a aquellas cuyos elementos son números enteros ($M(\mathbb{Z})$) y queremos saber cuáles de ellas son invertibles (dentro de $M(\mathbb{Z})$) no basta con la condición sabida en $M(\mathbb{R})$.

Como el cálculo del determinante de una matriz solo implica sumas y multiplicaciones podemos afirmar que el determinante de una matriz cuyos elementos son enteros es un número entero:

$$A \in M_{nxn}(\mathbb{Z}) \Rightarrow|A| \in \mathbb{Z}$$

 Supongamos que tenemos una matriz invertible en $M(\mathbb{Z})$

$A \in M(\mathbb{Z})$ invertible $\Rightarrow \exists B \in M(\mathbb{Z}) \mid A · B = I$

Si aplicamos determinantes en la igualdad anterior y utilizando propiedades de los determinantes podemos deducir que:

$$A · B = I \Rightarrow |A · B| = |I|\Rightarrow |A| · |B| = |I| \Rightarrow |A| · |B| = 1$$

 De lo anterior se concluye que:

• $|A| \neq 0$  y  $|B| \neq 0$
• $|A|· |B| = 1 \Rightarrow |B| = \frac{1}{|A|} \Rightarrow \frac{1}{|A|} \in \mathbb{Z}$ 

 Por tanto, si $\frac{1}{|A|}$ debe ser un número entero solo hay dos opciones:

$|A|=1$  ó  $|A|=-1$

Es decir, hemos demostrado que si una matriz es invertible en $M(\mathbb{Z})$, entonces su determinante es 1 o -1.

La otra dirección de la implicación es igual que en $M(\mathbb{R})$, es decir, definimos la inversa como la adjunta de la traspuesta dividida por el determinante (ojo aquí con las diferencias entre autores con la definición de matriz adjunta).

Solo hay que añadir que la inversa construida de esa manera pertenece a $M(\mathbb{Z})$. La transpuesta de una matriz con elementos enteros es otra matriz con elementos enteros (solo los cambiamos de lugar, no operamos nada con los números). Y la adjunta de una matriz con elementos enteros también es otra matriz con elementos enteros (solo hacemos determinantes y en su caso cambios de signo). Finalmente, como el determinante es 1 o -1, al dividir seguimos dentro de los números enteros.

Por tanto, en $M(\mathbb{Z})$

$A$ es invertible $\Longleftrightarrow$ $|A|=1$  ó  $|A|=-1$

Ejemplo: $\pmatrix{4 && 1 && 2 \\ 3 && 1 && 1 \\ 2 && 1 && 1}$ ¿Es invertible en $M(\mathbb{Z})$?

PD: A lo mejor esta entrada aporta algo de interés a esta otra que hice.

Matrices cuadradas aleatorias con determinante 1 o -1

Objetivo: generar una matriz cuadrada de números enteros aleatorios cuyo determinante sea 1 o -1.

Una primera idea puede ser realizar un bucle en el que generamos una matriz cuadrada de números enteros aleatorios hasta que se satisfaga la condición de que su determinante sea 1 o -1. El problema estaría resuelto, pero el algoritmo no es muy eficiente.

Voy a proponer a continuación otra solución. 

Problema previo: generar una matriz triangular de números enteros aleatorios cuyo determinante sea 1 o -1.

Este problema es muy sencillo teniendo en cuenta que el determinante de una matriz triangular es igual al producto de los elementos de su diagonal.

Únicamente necesitamos rellenar la diagonal con elementos del conjunto {-1, 1}, ceros por encima (o por debajo) de la diagonal y números enteros aleatorios en el resto de elementos de la matriz. 

Ejemplo de función en Python que calcula una matriz triangular de enteros aleatorios (entre -10 y 10, ambos incluidos) utilizando la librería NumPy.

import numpy as np
# Función para crear una matriz triangular de enteros con determinante 1 o -1
# n es la dimensión de la matriz
def matriz_det1(n):
    # Se crea una matriz M_azar con todos sus elementos aleatorios
    M_azar = np.random.randint(-10, 11, size=(n, n))
    # Se elige al azar si se construye una matriz triangular superior o inferior
    if np.random.randint(2):
        # Triangular superior: se cogen los elementos de M_azar por encima de la diagonal
        # con el resto de elementos iguales a 0 y se le suma una matriz diagonal con elementos 1 y -1
        MU = np.triu(M_azar, k=1) + np.diag(np.random.choice([-1, 1], size=n))
    else:
        # Triangular inferior: se cogen los elementos de M_azar por debajo de la diagonal
        # con el resto de elementos iguales a 0 y se le suma una matriz diagonal con elementos 1 y -1
        MU = np.tril(M_azar, k=-1)+ np.diag(np.random.choice([-1, 1], size=n))
    return MU 

Ejemplo de matriz (10x10) creada con dicho algoritmo:

 

Teniendo resuelto el problema previo, ahora podemos abordar el problema original. Las matrices resultantes del algoritmo anterior tienen el "inconveniente" de no ser lo suficientemente aleatorias, dado que son triangulares y tienen demasiados elementos 0 no aleatorios.

Sin embargo, sabemos que: 

- El determinante del producto de matrices es igual al producto de los determinates (|A·B|=|A|·|B|). Por tanto, si multiplicamos matrices cuyo determinante es 1 o -1 el resultado será una matriz cuyo determinante es 1 o -1.

- El producto de matrices triangulares no tiene porqué ser una matriz triangular.

Utilizando esto, podemos idear un algoritmo para el objetivo principal que consista en crear varias matrices triangulares resultantes del algoritmo anterior y multiplicarlas:

# Función para crear una matriz con determinante 1 o -1
# mediante la multiplicación de matrices triangulares
# n es la dimensión de la matriz y m el número de iteraciones
def genU(n, m):
    # Comenzamos con la matriz identidad
    U = np.eye(n, dtype=int)
    # Creamos "m" matrices triangulares con determinante 1 o -1 y las multiplicamos
    for k in range(m):
        U = U @ matriz_det1(n)
    return U

 Ejemplo de matriz creada con dicho algoritmo (n=5, m=10):

 

 

 

Problema de los cartones de bingo especiales: una solución con Python

 En la entrada anterior puse un problema en el que teníamos que contar cuántos cartones de bingo diferentes podíamos construir siguiendo unas reglas dadas: sin que se repita ninguna fila, columna o diagonal.

 Que ninguna pareja de cartones tenga alguna fila igual se entiende perfectamente. Lo mismo con columnas. Pero, ¿qué se entiende por diagonal del cartón? Si vemos el cartón como una matriz de 5x5, ¿hablamos sólo de la diagonal principal de la matriz? ¿también la diagonal secundaria (antidiagonal)? En este sentido el enunciado me genera dudas de interpretación. Así que desarrollaré un programa que pueda contestar a la pregunta interpretando ambas opciones.

El código en Python puede encontrarse en el repositorio de Matemática Recreativa que creé en GitHub.

Si queremos quitar la condición de la antidiagonal podemos comentar las líneas:

    if antidiagonal in antidiagonales:
        continue

 De hecho, el resultado no varía. Pero es que tampoco lo hace si quitamos la condición de las diagonales. Y aún más "sorprendente" es que tampoco varía si quitamos la condición de que no pueda haber dos matrices con alguna fila común.

Imagen extraída de https://www.youtube.com/watch?v=aumxFs2DO5o

 Pero eso no lo explica el algoritmo, sino que lo hacen las Matemáticas. La columna con menos combinaciones es la tercera, dado que hay una casilla negra a la que no hay que asignarle un número. Como en dicha columna podemos poner números en orden ascendente desde el 31 al 45 incluidos y sin poder repetirlos, tenemos el número combinatorio 15C4 que da 1365. Por tanto, tenemos una cota superior del número de soluciones al problema dado que podríamos tener cartones/matrices dentro de esas combinaciones con filas, diagonales o antidiagonales en común.

 Lo que pasa es que la solución al problema es exactamente 1365. ¿Por qué la restricción de la tercera columna es la más restrictiva sobre las condiciones de filas, diagonal y antidiagonal? Es decir, ¿por qué podemos asegurar que para cada una de las 1365 combinaciones para la tercera columna podemos rellenar un cartón completo que no comparta alguna fila, diagonal ni antidiagonal con el resto de cartones?

 La justificación no me parece tan fácil como podría pensarse en un principio. ¿Cuál es tu justificación?

Auto-evaluación con TIC (III): sistemas de ecuaciones lineales con parámetros con software

Esta entrada pertenece a la serie de entradas "Auto-evaluación con TIC". Podéis consultar las entradas anteriores:

- Auto-evaluación con TIC (I): álgebra de matrices con software.

- Auto-evaluación con TIC (II): sistemas de ecuaciones lineales con software.

En esta ocasión he preparado unos ejemplos de la utilización de software para la resolución de sistemas de ecuaciones lineales con parámetros. Aquí están los enlaces para descargar los documentos:

- Sistemas de ecuaciones lineales con parámetros con wxMaxima.

- Sistemas de ecuaciones lineales con parámetros con Wolfram Alpha.

Una cuestión importante es que empecé la serie con 3 programas (wxMaxima, Sage y Wolfram Alpha), pero como podéis observar para este tema he abandonado el uso de Sage. Las razones son varias pero, teniendo en cuenta que la intención de esta serie de entradas es que sirvan como pequeñas guías para la auto-evaluación de los alumnos, puedo resumirlas diciendo que el trabajo con dicho software se torna un poco complejo al discutir expresiones literales. Para que quede totalmente claro, no estoy diciendo que Sage no pueda llevar a cabo dichas discusiones, sino que no he encontrado una manera lo suficientemente sencilla como para considerarla ajustada al objetivo que persigo. Si alguien conoce alguna manera estaremos todos encantados de que nos la cuente en los comentarios.

Ahora que ya he trabajado un poco con estos programas, considero que las otras dos opciones son buenas. Cada una de ellas tiene aspectos positivos que la otra no tiene y por ello hay temas en los que optaría como primera opción por una de ellas y otros temas en los que optaría por la otra. En estos momentos Wolfram Alpha me parece la mejor opción si lo que se pretende es hallar la solución de la forma más sencilla y corta posible para compararla con la nuestra y wxMaxima me parece la mejor opción si lo que se pretende es un mejor análisis del proceso de resolución realizado.

Auto-evaluación con TIC (II): sistemas de ecuaciones lineales con software

Esta entrada es una continuación de "Auto-evaluación con TIC (I): álgebra de matrices con software" en la que hice una introducción con una reflexión sobre el papel que puede desempeñar el software como facilitador de la auto-evaluación.

En esta ocasión he realizado las pequeñas guías sobre la resolución de sistemas de ecuaciones lineales (2º Bachillerato) con el mismo software de la entrada anterior: wxMaxima (de código abierto y multiplataforma), Sage (de código abierto y multiplataforma) y la versión on-line gratuita de Wolfram Alpha (software privativo).

A continuación tenéis los enlaces. Espero que también os resulten útiles.

Sistemas de ecuaciones lineales con wxMaxima.
Sistemas de ecuaciones lineales con Sage.
Sistemas de ecuaciones lineales con Wolfram Alpha.

Sistemas de ecuaciones lineales - tabla de síntesis.

Auto-evaluación con TIC (I): álgebra de matrices con software

Siempre he sido un defensor de la utilización de variedad de recursos en las clases de Matemáticas. Los recursos TIC, al igual que cualquier otro recurso, no son ni buenos ni malos en si mismos sino que depende del uso que se haga de ellos, siempre sopesando si aportan algo beneficioso a la tarea. 

Cada vez que escribo algo que me parece una obviedad sigo reflexionando acerca de la razón de tener que seguir repitiéndolas. Pero eso es otro tema.

Considero que hay varios escenarios en los que los recursos TIC pueden desempeñar un papel muy importante. Uno de ellos es la investigación de situaciones problemáticas, en las que la potencia (en muchos sentidos, no sólo de cálculo) de algunos recursos TIC posibilitan un análisis matemático conceptual y práctico mucho más profundo, sin dar tanta importancia a la realización manual de los complejos o largos procedimientos que requieren dichas situaciones.

Otro escenario es la práctica y evaluación de procedimientos mecánicos. Teniendo en cuenta que el tiempo del que disponemos en clase está bastante limitado (sin quitar el ojo a la cantidad de contenidos del currículum), en ocasiones se emplea demasiado tiempo en corregir muchos ejercicios cuyo único objetivo es la adquisición de alguna regla o procedimiento mecánico. En este punto, la auto-evaluación puede desempeñar un papel útil. Si el alumno tiene (o puede obtener) la solución del ejercicio puede evaluar si ha llegado a la solución correcta o no. Si además, el recurso le permite auto-evaluar el proceso seguido e identificar los posibles errores cometidos en él, estamos ante un buen recurso de auto-evaluación.

Con esta idea en mente he elaborado unas pequeñas guías para trabajar el álgebra de matrices (2º Bachillerato) con software: wxMaxima (de código abierto y multiplataforma), Sage (de código abierto y multiplataforma) y la versión on-line gratuita de Wolfram Alpha (software privativo).

A continuación tenéis los enlaces. Espero que os resulten útiles.

Álgebra de matrices con wxMaxima.
Álgebra de matrices con Sage.
Álgebra de matrices con Wolfram Alpha.

Álgebra de matrices - tabla de síntesis.