Problema del vector más cercano (CVP) en un retículo

Definición del problema: 

Sea $\varLambda$ un retículo completo sobre $\mathbb{R}^n$ y sea $\vec{w} \in \mathbb{R}^n$.

Queremos encontrar un vector $\vec{z} \in \varLambda$ tal que:

$$\|\vec{w}-\vec{z}\| = mín\{\|\vec{w}-\vec{b}\|, \forall \vec{b} \in \varLambda\}$$

Es decir, dado un vector del espacio queremos encontrar el vector del retículo más cercano al primero. Esto se conoce como el Problema del Vector más Cercano (CVP, por las siglas en inglés "Closest Vector Problem").

 

Teniendo en cuenta que la región fundamental de un retículo es un n-paralelepípedo, es inmediato ver la relación con las entradas anteriores (1 y 2) en las que se plantea encontrar el vértice del n-paralelepípedo más cercano a un punto.

Resumiendo, para dimensiones altas el método exhaustivo consistente en calcular la distancia con todos los vértices del n-paralelepípedo tiene un coste computacional demasiado elevado. 

Por otra parte, el algoritmo de Babai solo ofrece garantías de obtener la solución correcta si la base es lo "suficientemente ortogonal". Pero a esto además le añadimos que con bases que tienen mucho defecto de ortogonalidad (muy "lejos" de ser ortogonales) resulta que el vector más cercano ni tan siquiera tiene porqué ser vértice del n-paralelepípedo que lo contiene.

Puede verse que hay un punto naranja (del retículo) más próximo a $Q$ que los vértices del n-paralelepípedo que lo contiene

Con todo lo anterior, podemos concluir lo siguiente sobre la resolución del problema del vector más próximo en un retículo: una persona que conozca una base "bastante próxima" a ser ortogonal podrá realizar los cálculos de manera relativamente sencilla, mientras que otra persona que conozca una base "suficientemente lejos" de ser ortogonal tendrá mucha más dificultad para resolverlo.

Algoritmo de Babai con Python

 En la entrada anterior expliqué y ejemplifiqué el Algoritmo de Babai para encontrar el vértice del n-paralelepípedo más cercano a un punto.

Podemos realizar un script en Python para dicho algoritmo. Utilizando la librería NumPy queda muy sencillo:

 

import numpy as np

def babai(B, w):
    # Calculamos los coeficientes del vector w en la base B
    v = np.linalg.solve(B, w)
    # Devolvemos el producto matricial de B por las coordenadas de v redondeadas
    return B @ np.round(v).astype(int) 

 

By www.python.org - www.python.org, GPL,

 https://commons.wikimedia.org/w/index.php?curid=34991651

 

PD: Podéis encontrar en uno de mis repositorios de Github un script para probar el Algoritmo de Babai y la razón de Hadamard. 

Vértice de un n-paralelepípedo más cercano a un punto. Algoritmo de Babai.

 En una entrada anterior planteé el siguiente problema:

 Sea $\mathcal{F}$ un n-paralelepípedo (sólido) generado por el conjunto de vectores linealmente independientes $B = \{\vec{b}_1,...,\vec{b}_n\}$. Sea $P\in\mathcal{F}$ un punto de dicho n-paralelepípedo. ¿Cuál es el vértice del n-paralelepípedo más cercano a $P$?

Expliqué y ejemplifiqué una posible estrategia consistente en el método exhaustivo, es decir, comprobar todos los posibles vértices. Concluí la entrada con la observación de que el número de vértices crece de manera exponencial con la dimensión y esto supone un problema de coste computacional en dimensiones grandes.

En esta entrada vamos a trabajar otra posible estrategia, basada en el algoritmo de Babai, desarrollado por el matemático húngaro László Babai.

El fundamento detrás del procedimiento es relativamente sencillo.

Si $P\in\mathcal{F}$ entonces $P$ se puede escribir como combinación lineal de la base $B$:

$$P = \sum_{i=1}^{n}{a_i·\vec{b}_i}$$

Lo que hacemos es redondear al entero los coeficientes $0 \leq a_i \leq 1$ de la combinación lineal:

$$z_i = redondear(a_i)$$

Entonces, el vértice del n-paralelepípedo más próximo a $P$ viene dado por:

$$V = \sum_{i=1}^{n}{z_i·\vec{b}_i}$$

 

Ejemplo: Hagamos este método con el mismo ejemplo que utilizamos en el método exhaustivo, en $\mathbb{R}^2$.

$B=\{(30, 3), (5, 0)\}$ y el punto del paralelogramo $Q=(25.5, 2.5)$. Queremos hallar el vértice del paralelogramo más cercano a $Q$.

 Primero calcularemos la combinación lineal de la base $B$ que da el punto $Q$:

$$\vec{a} = B^{-1} · \overrightarrow{OQ} =\begin{pmatrix}30 & 5\\3 & 0\end{pmatrix}^{-1} · \begin{pmatrix}25.5 \\ 2.5\end{pmatrix} \simeq \begin{pmatrix}0.8333333333333333 \\ 0.10000000000000053\end{pmatrix}$$

Ahora redondeamos los coeficientes obtenidos:

$$\vec{z} = \begin{pmatrix}1 \\ 0\end{pmatrix}$$

Y calculamos a qué vértice corresponde dicha combinación lineal:

$$\overrightarrow{OV} = B · \vec{z} = \begin{pmatrix}30 & 5\\3 & 0\end{pmatrix} · \begin{pmatrix}1 \\ 0\end{pmatrix} = \begin{pmatrix}30 \\ 3\end{pmatrix}$$

Es decir, el vértice más cercano al punto $Q$ es (30, 3). (Coincide con el obtenido por el método exhaustivo)

Los cálculos del ejemplo han sido realizados con wxMaxima:

 

Desde un punto de vista geométrico e informal podríamos decir que el procedimiento anterior es equivalente a dividir con "hiperplanos medianeros" el n-paralelepípedo y seleccionar el vértice del "trozo" en el que queda el punto.

 

 El algoritmo de Babai rebaja considerablemente el coste computacional, dado que no necesita recorrer todos los vértices del n-paralelepípedo y se basa en operaciones bastante rápidas desde el punto de vista del cálculo computacional.

Sin embargo, el algoritmo de Babai presenta un gran problema: solo en determinadas condiciones la solución que devuelve es la correcta.

Veamos esto con un ejemplo. Seguimos utilizando la misma base que en el ejemplo anterior, pero cambiamos el punto a "aproximar" (encontrar el vértice más cercano) por $R=(30, 2.7)$.

Los cálculos del algoritmo devuelven el vértice $(35, 3)$ como el más cercano al punto $R$.

 

Sin embargo, esto no es cierto. El vértice más cercano es claramente el $(30, 3)$. 

 

Puede observarse en la representación gráfica que, tras trazar las medianas, el punto cae en el "trozo" del vértice $(35, 3)$ y por eso es la respuesta que devuelve el algoritmo de Babai. Pero no es el vértice más cercano.

Llegados a este punto lo razonable es descartar por completo este algoritmo porque ni tan siquiera devuelve la solución correcta.

Sin embargo, el algoritmo sí funciona con fiabilidad cuando la base es ortogonal (o "cerca" de ser ortogonal).

¿Y esto tiene alguna utilidad práctica? Habrá que esperar a las siguientes entradas para averiguarlo. 

Razón de ortogonalidad de Hadamard con Python

 En una entrada anterior hablé sobre la razón de ortogonalidad de Hadamard:

$$H(B) = \sqrt[n]{\frac{|det(B)|}{\prod_{i=1}^{n}\|\vec{b}_i\|}} $$

Podemos realizar un script en Python para calcular dicha razón, utilizando la librería NumPy:

import numpy as np

def razon_hadamard(B):
    # Calculamos el valor absoluto del determinante de la matriz
    det = np.abs(np.linalg.det(B))
    # Si el determinante es 0 la matriz no es una base y la función devuelve 0
    if not det:
        return 0
    n = len(B)
    # Definimos una variable prod_norm que calcula el producto de la norma de cada vector (columna)
    prod_norm = np.prod(np.linalg.norm(B, axis=0))
    # Devolvemos la razón
    return (det / prod_norm) ** (1/n) 

 

By www.python.org - www.python.org, GPL,

 https://commons.wikimedia.org/w/index.php?curid=34991651

 

Vértice de un n-paralelepípedo más cercano a un punto. Método exhaustivo.

 

Sea $\mathcal{F}$ un n-paralelepípedo (sólido) generado por el conjunto de vectores linealmente independientes $B = \{\vec{b}_1,...,\vec{b}_n\}$. Sea $P\in\mathcal{F}$ un punto de dicho n-paralelepípedo. ¿Cuál es el vértice del n-paralelepípedo más cercano a $P$?

 Estrategia 1. Método exhaustivo.

Podemos calcular las coordenadas de todos los vértices del n-paralelepípedo.

Por ejemplo, en $\mathbb{R}^3$, los 8 vértices del paralelepípedo son:

$V_1 = \vec{0} = (0,0,0)$

$V_2 = \vec{b}_1$

$V_3 = \vec{b}_2$

$V_4 = \vec{b}_3$

$V_5 = \vec{b}_1 + \vec{b}_2$

$V_6 = \vec{b}_1 + \vec{b}_3$

$V_7 = \vec{b}_2 + \vec{b}_3$

$V_8 = \vec{b}_1 + \vec{b}_2 + \vec{b}_3$ 

Después calculamos la distancia de cada uno de ellos al punto $P$

$$d_i = \|P-V_i\|$$ 

 Y nos quedamos con el que tenga menor distancia (puede haber más de uno).

 

Ejemplo: Hagamos este método con un caso muy sencillo en $\mathbb{R}^2$.

$B=\{(30, 3), (5, 0)\}$ y el punto del paralelogramo $Q=(25.5, 2.5)$. Queremos hallar el vértice del paralelogramo más cercano a $Q$.

Los vértices del paralelogramo son:

$V_1=(0, 0); V_2=(30, 3); V_3=(5, 0); V_4=(35, 3)$

Y las correspondientes distancias al punto $Q$:

$d_1 \simeq 25.622255950637914$

$d_2 \simeq 4.527692569068709$

$d_3 \simeq 20.65187642806338$

$d_4 \simeq 9.513148795220223$ 

Por tanto, el vértice con menor distancia al punto $Q$ es $V_2=(30, 3)$.

 

Los cálculos han sido realizados con wxMaxima:

 

Contras del método exhaustivo.

Para dimensiones pequeñas el método exhaustivo es rápido y muy eficiente, pero para dimensiones grandes el coste computacional se incrementa exponencialmente, dado que el número de vértices de un n-paralelogramo es $2^n$.

Por ejemplo, en $\mathbb{R}^{100}$ tenemos $2^{100} = 1267650600228229401496703205376$ vértices.

Medir la ortogonalidad de una base

En la entrada anterior hice un repaso rápido de qué son las bases ortogonales. Ahora voy a tratar el siguiente tema:

¿Hay alguna manera de cuantificar si una base está cerca o lejos de ser ortogonal?

La respuesta es sí.

Una manera de hacerlo es utilizando una aplicación de la desigualdad de Hadamard.

Dada una base $B = \{ \vec{b}_1, ..., \vec{b}_n \}$ del espacio euclídeo $\mathbb{R}^n$:

$$|det(B)| \leq \prod_{i=1}^{n}\|\vec{b}_i\|$$

Desde el punto de vista geométrico, la desigualdad anterior nos aporta una cota superior del volumen del n-paralelepídedo formado por $B$.

Pero para el caso que nos ocupa, es muy útil conocer que dicha desigualdad se convierte en igualdad cuando la base es ortogonal por lo que nos permite definir la siguiente "razón de ortogonalidad de Hadamart":

$$\frac{|det(B)|}{\prod_{i=1}^{n}\|\vec{b}_i\|} $$

 Dicho valor estará comprendido en el intervalo $(0,1]$ y será exactamente 1 cuando la base sea ortogonal. Cuanto más "cerca" esté una base de ser ortogonal, más cerca de 1 estará el valor de la razón anterior. Cuanto más "lejos" esté una base de ser ortogonal, más cerca de 0 estará dicho valor.

Desde un punto de vista intuitivo e informal, estamos diciendo que si fijamos el módulo de los vectores que generan un n-paralelepídedo entonces el volumen es máximo cuando estos son ortogonales (en el momento en el que variamos alguno de los ángulos el volumen del n-paralelepípedo baja). Por tanto, si comparamos el volumen del n-paralelepípedo generado por los vectores de la base con el volumen máximo (caso ortogonal) podemos tener una idea de si la base está "cerca" o "lejos" de ser ortogonal.

Vamos a calcular dicha razón en los ejemplos de la entrada anterior en $\mathbb{R}^3$.

Comenzamos con la base canónica $C = \{(1,0,0),(0,1,0),(0,0,1)\}$:

 

 $|det(C)|=1$

 $\|(1,0,0)\|=\sqrt{1^2+0^2+0^2}=1$ 

 $\|(0,1,0)\|=\sqrt{0^2+1^2+0^2}=1$ 

 $\|(0,0,1)\|=\sqrt{0^2+0^2+1^2}=1$

Por tanto,

$$\frac{|det(C)|}{\prod_{i=1}^{n}||\vec{c}_i||} = \frac{1}{1} = 1$$

Es decir, como el valor da 1 podemos afirmar que la base es ortogonal.

 

En el caso de la otra base utilizada, $D = \{(1,0,0),(1,1,1),(0,2,1)\}$ 

 $|det(D)|=1$

 $\|(1,0,0)\|=\sqrt{1^2+0^2+0^2}=1$ 

 $\|(1,1,1)\|=\sqrt{1^2+1^2+1^2}=\sqrt{3}$ 

 $\|(0,2,1)\|=\sqrt{0^2+2^2+1^2}=\sqrt{5}$

 Por tanto,

$$\frac{|det(D)|}{\prod_{i=1}^{n}\|\vec{d}_i\|} = \frac{1}{\sqrt{15}} = \frac{\sqrt{15}}{15} \simeq 0.2581$$

Da un valor alejado de 1 por lo que podemos afirmar que la base "está lejos" de ser ortogonal. 

 

En realidad resultaría de utilidad tener una "medida" normalizada y comparable entre dimensiones. Si añadimos una raíz n-ésima tendremos una especie de "media geométrica del grado de normalidad por vector". Así pues, es más frecuente utilizar la siguiente expresión cuando se habla de la razón de ortogonalidad de Hadamart:

$$H(B) = \sqrt[n]{\frac{|det(B)|}{\prod_{i=1}^{n}\|\vec{b}_i\|}} $$

Otros autores hablan del defecto de ortogonalidad de una base definiéndola de la siguiente manera:

$$\vartriangle(B) = \frac{\prod_{i=1}^{n}\|\vec{b}_i\|}{|det(B)|} $$

de manera que cuánto mayor es el cociente "menor" es la ortogonalidad de la base (que sigue siendo 1 para bases ortogonales).

PD: Entrada de Wikipedia sobre el matemático francés Jacques Hadamard. 

Bases ortogonales

Es sabido que en el espacio euclídeo $\mathbb{R}^n$ un conjunto de $n$ vectores linealmente independientes forman una base del espacio.

Decimos que una base es ortogonal cuando los vectores de la base son ortogonales dos a dos, es decir, que su producto escalar es 0:

$$ b_{i} · b_{j} = 0; \forall i,j \in \{1,...,n\} \mid i \neq j$$

Por ejemplo, en $\mathbb{R}^3$ la base canónica $\{(1,0,0),(0,1,0),(0,0,1)\}$ es una base ortogonal. Todos los productos escalares dan 0:

$(1,0,0)·(0,1,0)=0+0+0=0$

$(1,0,0)·(0,0,1)=0+0+0=0$

$(0,1,0)·(0,0,1)=0+0+0=0$

Los vectores forman ángulos rectos entre ellos.

Sin embargo, la base $\{(1,0,0),(1,1,1),(0,2,1)\}$ no es una base ortogonal. Por ejemplo, el siguiente producto escalar no da 0:

$(1,1,1)·(0,2,1)=0+2+1=3 \neq 0$

Existen vectores que no forman un ángulo recto.

 

Particiones de $\mathbb{R}^n$ utilizando la región fundamental de un retículo

 La entrada anterior finalizó observando que con la región fundamental de un retículo completo podemos teselar todo el espacio $\mathbb{R}^n$.

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

 

 Esto es equivalente a afirmar que el conjunto $\{\vec{v}+\mathcal{F}(\varLambda) \mid \vec{v} \in \varLambda \}$ es una partición de $\mathbb{R}^n$. Es decir, que si hacemos la traslación de la región fundamental utilizando todos los vectores del retículo cubrimos todo el espacio y los "trozos" no se solapan.

 

Ejemplo de 2 traslaciones de una región fundamental

 

Así pues, conociendo una base $B$ de un retículo completo $\varLambda(B)$, podemos caracterizar de manera única cualquier punto/vector de $\mathbb{R}^n$ como la suma de un vector del retículo $\varLambda(B)$ con un vector de la región fundamental $\mathcal{F}(\varLambda(B))$.

 

Por ejemplo, si retomamos el retículo completo sobre $\mathbb{R}^2$ generado por $B = \{(5, 3), (5, 0)\}$ podemos escribir el vector $\overrightarrow{OP}=(9.2,6.8) \in \mathbb{R}^2$ como la suma de un vector del retículo $\vec{w}_1=(5,6) \in \varLambda(B)$ y un vector de la región fundamental $\vec{t}_1=(4.2,0.8) \in \mathcal{F}(\varLambda(B))$.

 

 

 

 

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

 

 

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.

Retículos sobre espacios euclídeos $\mathbb{R}^n$

 Un retículo (lattice) sobre un espacio euclídeo $\mathbb{R}^n$ es un subgrupo discreto de $\mathbb{R}^n$.

Dicho de otra manera, un retículo es un subconjunto no vacío de vectores de $\mathbb{R}^n$ que cumplen:

• Conjunto discreto. Intuitivamente podemos decir que puede hallarse una distancia mínima que cumplen TODOS los pares de vectores (no hay continuidad).
• Contiene el elemento neutro (el vector $\vec{0}$).
• Cerrado respecto a la suma. Es decir, si dos vectores ($\vec{u}$ y $\vec{v}$) pertenecen al retículo, entonces el resultado de su suma ($\vec{u} + \vec{v}$) también debe pertenecer al retículo.
• Cerrado respecto al opuesto. Es decir, si un vector ($\vec{u}$) pertenece al retículo, entonces su opuesto ($-\vec{u}$) también debe pertenecer al retículo.

Por ejemplo, sobre $\mathbb{R}^2$, los vectores del tipo (2·m, 0) con m entero (vectores con final en el eje X con coordenada x par) forman un retículo.

Representación de algunos vectores del primer retículo

Otro ejemplo sobre $\mathbb{R}^2$ son los vectores de la forma (5·a, 3·b) con a y b enteros.

Representación de algunos vectores del segundo retículo

Estas representaciones, aún siendo parciales, pueden llegar a ser bastante densas así que no representaremos los vectores completos sino únicamente el punto final al que apuntan. Si hacemos esto se observa que se forma una especie de red/malla/retículo.

Puntos finales de los vectores del primer retículo

Puntos finales de los vectores del segundo retículo

 Dichas mallas forman "trozos".

Los trozos que se forman en el primer retículo son segmentos de una recta (eje X)

 

Los "trozos" que se forman en el segundo retículo son rectángulos.

Si los "trozos" llenan todo el espacio decimos que el retículo es completo (otros nombres: de rango completo y de dimensión completa).

Sobre $\mathbb{R}^2$ el primer retículo no es completo porque no cubre todo el plano, pero el segundo retículo sí.

Ecuación vectorial del plano

 En una entrada anterior se analizó la interpretación geométrica de la ecuación vectorial de una recta en el plano ($\mathbb{R}^2$) y se mencionó la correspondencia con la ecuación vectorial de una recta en el espacio ($\mathbb{R}^3$): 

$(x, y, z) = P + k · \vec{u}$

 $(x, y, z) = (P_{x}, P_{y}, P_{z}) + k · (u_{x}, u_{y}, u_{z})$  [Forma desplegando coordenadas]

donde:

   $P = (P_x, P_y, P_z)$ es un punto por el que pasa la recta

   $\vec{u} =  (u_x, u_y, u_z)$ es un vector director de la recta

   $k$ es un escalar (número real)

Al "estirar", "encoger" y/o "dar la vuelta" al vector sin cambiar la dirección todos los puntos que obtenemos están sobre una recta.

 

Analicemos ahora la siguiente ecuación en el espacio ($\mathbb{R}^3$): 

$(x, y, z) = P + k · \vec{u} + q · \vec{v}$

$(x, y, z) = (P_x, P_y, P_z) + k · (u_x, u_y, u_z) + q · (v_x, v_y, v_z)$

donde:

   $P$ es un punto

   $\vec{u}$ y $\vec{v}$ son vectores (con direcciones diferentes)

   $k$ y $q$ son escalares (número real)

Teniendo en cuenta lo que se vio en la anterior entrada sobre la combinación lineal de dos vectores, no es difícil llegar a la conclusión de que la anterior ecuación vectorial describe todos los puntos que se hallan sobre un plano.

 A diferencia de las entradas anteriores, dado que es una visualización 3D, en lugar de incrustar el script dinámico pongo el enlace a la web de Geogebra:

https://www.geogebra.org/classic/z2svwz9g 

 Veréis dos deslizadores en la barra algebraica de la izquierda que podéis mover (o darle al play) para ver el rastro que va dejando la combinación lineal acotada por el rango definido para dichos escalares.

Pinchando en cualquier punto vacío y arrastrando podemos mover la perspectiva. 

 

Multiplicación de vector por escalar

 En la entrada anterior repasamos cómo se suman dos vectores y su interpretación geométrica.

Ahora vamos a hacer lo correspondiente con la multiplicación de un vector por un escalar. La operación algebraica es muy sencilla, hay que multiplicar todas las componentes del vector por el escalar.

Por ejemplo, si en $\mathbb{R}^2$, queremos multiplicar el vector $\vec{u} = (3, -2)$ por el escalar 3:

$$3 · \vec{u} = 3 · (3, -2) = (3 · 3, 3 · (-2)) = (9, -6)$$

Al multiplicar un vector por un escalar obtenemos otro vector con:

- La misma dirección que el primero.

- Módulo igual al módulo del primero multiplicado por el escalar.

- Mismo sentido si el escalar es positivo y sentido contrario si el escalar es negativo. 

Desde el punto de vista geométrico, el resultado es como "estirar" o "encoger" el vector tanto como diga el escalar (0.5 implica "encogerlo" a su mitad y 3 implica estirarlo a su triple), así como "darle la vuelta" si el escalar es negativo (-2 implica cambiarle el sentido y "estirarlo" a su doble).

Para visualizarlo y experimentar podéis utilizar el siguiente script de Geogebra en el que se representa un vector $\vec{u}$ y el resultado de multiplicarlo por un escalar $k$, cuyo valor se define mediante un deslizador.

Se puede mover el deslizador para cambiar el escalar y el punto B para cambiar el vector. Podéis cambiar el zoom con la rueda del ratón y moveros por el plano pinchando y arrastrando sobre una zona libre.

NOTA: Si desde el listado de entradas del blog no se visualiza el script abrid esta entrada en otra ventana. 

 

Suma de vectores

Sumar vectores es una operación muy sencilla, hay que sumar sus correspondientes componentes.

Por ejemplo, en el espacio $\mathbb{R}^2$, dado el vector $\vec{u} = (1, 2)$ y el vector $\vec{v} = (5, -1)$, el vector resultante de sumar $\vec{u}$ y $\vec{v}$ es:

$$\vec{u} + \vec{v} = (1, 2) + (5, -1) = (1 + 5, 2 + (-1)) = (6, 1)$$

Desde un punto de vista geométrico, sumar dos vectores es equivalente a trazar la diagonal del paralelogramo que generan ambos vectores.

Os dejo un script interactivo con Geogebra para que podáis "jugar" un poco.

Los puntos que pueden moverse son B y C. Podéis cambiar el zoom con la rueda del ratón y moveros por el plano pinchando y arrastrando sobre una zona libre.

NOTA: Si desde el listado de entradas del blog no se visualiza el script abrid esta entrada en otra ventana.  

 

Representación gráfica de vectores con wxMaxima

En esta entrada voy a explicar una forma de representar gráficamente vectores con wxMaxima. Después de probar varias formas y diferentes funciones, la que más se adapta a lo que necesito es utilizar lo siguiente:

draw2d(vector([0,0],[x,y]))

Sin embargo, he tenido que retocar algunas opciones para que el dibujo quede decente. Veamos el siguiente ejemplo: la representación del vector con coordenadas (2,-3).

draw2d(vector([0,0],[2,-3]))

Como podéis observar, el resultado muestra un vector "cabezón" y, además, estaría bien que la zona del plano representada fuera mayor que la estrictamente ocupada por el vector.

Para solucionar lo primero (el cabezón del vector) podemos utilizar la opción head_length. Es importante poner las opciones antes del vector. En nuestro ejemplo:

 

draw2d(head_length=0.2, vector([0,0],[2,-3]))

Y para cambiar la zona del plano representada utilizamos los parámetros xrange (para el eje X) e yrange (para el eje Y). En nuestro ejemplo:

draw2d(head_length=0.2, xrange=[-5,5], yrange=[-5,5], vector([0,0],[2,-3]))

 

Si además queremos que aparezcan los ejes en el dibujo activamos los parámetros xaxis e yaxis. En nuestro ejemplo:

draw2d(head_length=0.2, xrange=[-5,5], yrange=[-5,5],

xaxis=true, yaxis=true, vector([0,0],[2,-3]))

En caso de que queramos representar más de un vector en la gráfica, no tenemos más que añadir a la función los vectores correspondientes. Ejemplo: añadimos al vector del ejemplo anterior los vectores con coordenadas (-1, -1) y (-2,4):

draw2d(head_length=0.2, xrange=[-5,5], yrange=[-5,5],

xaxis=true, yaxis=true, vector([0,0],[2,-3]),

vector([0,0],[-1,-1]), vector([0,0],[-2,4]))

También podemos configurar los colores de los vectores, simplemente añadiendo el parámetro color delante de cada vector. En nuestro ejemplo queremos poner el primer vector de color rojo, el segundo de color azul y el tercero de color verde:

draw2d(head_length=0.2, xrange=[-5,5], yrange=[-5,5],

xaxis=true, yaxis=true, color=red, vector([0,0],[2,-3],

color=blue, vector([0,0],[-1,-1]), color=green, vector([0,0],[-2,4])))

Si os fijáis, desde el principio hemos estado utilizando vector([0,0],[x,y]) y es por eso que todos los vectores representados anteriormente empiezan en el origen de coordenadas. Si estamos interesados en representar gráficamente un vector que tiene su inicio en otro punto debemos cambiar [0,0] por las coordenadas del punto de inicio. En ese caso, debemos tener en cuenta que el segundo par de coordenadas NO se corresponde con las del punto final, sino que son las dimensiones orientadas del vector. Es decir, vector([1.5,-1.75],[2,-3]) representa un vector cuyo punto de origen es (1.5,-1.75) y que avanza 2 unidades en el eje X y baja 3 unidades en el eje de las Y. Lo representamos:

draw2d(head_length=0.2, xrange=[-5,5], yrange=[-5,5],

xaxis=true, yaxis=true, vector([1.5,-1.75],[2,-3]))

Hay muchas otras opciones en la función draw2d (como por ejemplo añadir grid=true si queremos visualizar la cuadrícula cartesiana) pero lo anterior cubre las necesidades básicas para representar gráficamente vectores de una manera satisfactoria.

Lo que sí puede resultar interesante es conocer que todo lo anterior funciona prácticamente igual con la función draw3d para representar gráficamente vectores en el espacio (añadiendo la tercera coordenada). Un ejemplo:

draw3d(head_length=0.2, xrange=[-4,4], yrange=[-4,4], zrange=[-4,4],

xaxis=true, yaxis=true, zaxis=true,

vector([0,0,0],[2,3,1]), color=red, vector([0,0,0],[-1,-1,-3]))

 

Entradas relacionadas:

- Otras entradas que hablan de wxMaxima.