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

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):