Representación Matricial de una Relación | Matemáticas Discretas

Definición: Representación Matricial de una Relación

Definición (Representación matricial de una relación):

Sea $R$ una relación de $A$ en $B$, con $A$ y $B$ finitos. Si consideramos

$$A = \{x_1,x_2,\ldots,x_m\} \text{ y } B = \{y_1,y_2,\ldots,y_n\}$$

($|A|=m$ y $|B|=n$), se define la representación matricial de $R$ por la matriz $M_R = (m_{ij})$, elemento de $\mathbb{R}^{m\times n}$, definida por

$$m_{ij}= \begin{cases} 1 &\text{si } x_iRy_j,\\ 0 &\text{si no.} \end{cases}$$

La representación matricial de una relación nos permite trabajar con relaciones utilizando álgebra matricial.

Cada entrada de la matriz $M_R$ es 1 si existe la relación entre los elementos correspondientes, y 0 en caso contrario.

Ejemplo

Considera el conjunto $A = \{\text{Manzana}, \text{Banana}\}$ y el conjunto $B = \{\text{Rojo}, \text{Amarillo}, \text{Verde}\}$. Definamos una relación $R$ donde un elemento de $A$ está relacionado con un color de $B$ si puede tener ese color:

$$R = \{(\text{Manzana}, \text{Rojo}), (\text{Manzana}, \text{Verde}), (\text{Banana}, \text{Amarillo})\}.$$

La matriz $M_R$ sería:

$$M_R = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}.$$

Aquí, la primera fila es para «Manzana» y la segunda para «Banana». Las columnas son para «Rojo», «Amarillo» y «Verde» respectivamente.

Proposición: Relación Inversa

Proposición:

Sea $R$ una relación de $A$ en $B$, con $A$ y $B$ finitos. Se tiene que

$$M_{R^{-1}} = (M_R)^T.$$

Esto tiene mucho sentido: si $(x, y)$ está en $R$, entonces $(y, x)$ está en $R^{-1}$. Al transponer la matriz, lo que era una conexión de $x_i$ a $y_j$ (entrada $m_{ij}$) se convierte en una conexión de $y_j$ a $x_i$ (entrada $m_{ji}$ en la transpuesta).

Ejemplo

Retomando nuestro ejemplo anterior, $M_R$ era:

$$M_R = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix},$$

entonces, la matriz de la relación inversa $M_{R^{-1}}$ (que nos diría qué colores están relacionados con qué frutas) sería:

$$M_{R^{-1}} = (M_R)^T = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 0 \end{pmatrix}.$$

Esta matriz nos muestra, por ejemplo, que «Rojo» está relacionado con «Manzana», «Amarillo» con «Banana», y «Verde» con «Manzana».

Proposición: Inclusión de Relaciones

Proposición:

Sean $R$ y $S$ relaciones de $A$ en $B$, con $A$ y $B$ finitos. Se tiene que

$$R\subseteq S \quad\text{si y solo si}\quad M_R \leq M_S.$$

¿Qué significa $M_R \leq M_S$? Significa que, si comparas cada entrada $m_{ij}$ de $M_R$ con la correspondiente entrada $s_{ij}$ de $M_S$, siempre se cumple que $m_{ij} \leq s_{ij}$. En otras palabras, si hay un 1 en $M_R$, debe haber un 1 en la misma posición en $M_S$. Si hay un 0 en $M_R$, puede haber un 0 o un 1 en $M_S$.

Proposición: Composición de Relaciones y Producto Matricial

Proposición:

Sean $R$ una relación de $A$ en $B$ y $S$ una relación de $B$ en $C$, con $A$, $B$ y $C$ conjuntos finitos. Se tiene que

$$M_R M_S \text{ y } M_{S\circ R}$$

tienen los mismos elementos distintos de $0$.

Importante: La entrada $(i,j)$ de la matriz $M_R M_S$ nos dice el número de «caminos» que existen entre el elemento $x_i$ de $A$ y el elemento $z_j$ de $C$ pasando por los elementos de $B$. Es como contar cuántas rutas diferentes puedes tomar para ir de $x_i$ a $z_j$ a través de un punto intermedio en $B$. Si este número es mayor que cero, significa que existe al menos un camino, y por lo tanto, una relación compuesta.

Ejemplo

Sea $A = \{\text{Juan}\}$, $B = \{\text{Libro}, \text{Computadora}\}$, y $C = \{\text{Comprar}, \text{Leer}\}$.

Sea $R$ la relación «posee»: Juan posee Libro, Juan posee Computadora. Con esto, la matriz $M_R$ es:

$$M_R = \begin{pmatrix} 1 & 1 \end{pmatrix}.$$

Sea $S$ la relación «se puede»: Libro se puede Leer, Computadora se puede Comprar, Computadora se puede Leer. Con esto, la matriz $M_S$ es:

$$M_S = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}.$$

Ahora, calculamos el producto $M_R M_S$:

$$M_R M_S = \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} (1 \cdot 0 + 1 \cdot 1) & (1 \cdot 1 + 1 \cdot 1) \end{pmatrix} = \begin{pmatrix} 1 & 2 \end{pmatrix}.$$

Las entradas de $M_R M_S$ nos dicen:

La primera entrada (1) indica que hay 1 camino de «Juan» a «Comprar» (Juan posee Computadora, y Computadora se puede Comprar).
La segunda entrada (2) indica que hay 2 caminos de «Juan» a «Leer» (Juan posee Libro, y Libro se puede Leer; Juan posee Computadora, y Computadora se puede Leer).

La matriz de la composición $M_{S \circ R}$ (que nos diría qué puede hacer Juan con lo que posee) sería:

$$M_{S \circ R} = \begin{pmatrix} 1 & 1 \end{pmatrix}.$$

Aquí, la primera entrada es 1 porque Juan puede Comprar (a través de la Computadora), y la segunda es 1 porque Juan puede Leer (a través del Libro o la Computadora). Como puedes ver, $M_{S \circ R}$ tiene 1s donde $M_R M_S$ tiene valores distintos de cero. La diferencia es que $M_R M_S$ cuenta los caminos, mientras que $M_{S \circ R}$ solo indica si un camino existe (1) o no (0).

Corolario 1: Relación entre $M_{S \circ R}$ y $M_R M_S$

Corolario:

Sean $R$ una relación de $A$ en $B$ y $S$ una relación de $B$ en $C$, con $A$, $B$ y $C$ conjuntos finitos. Se tiene que

$$M_{S\circ R} \leq M_R M_S \quad\text{ y }\quad M_R M_S \leq |B| M_{S\circ R}.$$

Ejemplo

Usando el ejemplo anterior donde $M_R M_S = \begin{pmatrix} 1 & 2 \end{pmatrix}$ y $M_{S \circ R} = \begin{pmatrix} 1 & 1 \end{pmatrix}$.

Vemos que $M_{S \circ R} \leq M_R M_S$ se cumple, ya que $\begin{pmatrix} 1 & 1 \end{pmatrix} \leq \begin{pmatrix} 1 & 2 \end{pmatrix}$.

Además, $|B| = 2$. Así que $M_R M_S \leq |B| M_{S \circ R}$ se traduce a $\begin{pmatrix} 1 & 2 \end{pmatrix} \leq 2 \begin{pmatrix} 1 & 1 \end{pmatrix} = \begin{pmatrix} 2 & 2 \end{pmatrix}$, lo cual también es cierto.

Corolario 2: Obtener $M_{S \circ R}$ a partir de $M_R M_S$

Para obtener la matriz de la composición de relaciones $M_{S \circ R}$ a partir del producto de matrices $M_R M_S$, podemos usar la siguiente fórmula:

$$M_{S\circ R} = \left\lceil \frac{1}{|B|} M_R M_S \right\rceil.$$

Aquí, $\lceil \cdot \rceil$ es la función techo aplicada a cada elemento de la matriz. La función techo $\lceil x \rceil$ redondea $x$ al entero más cercano hacia arriba. Por ejemplo, $\lceil 0.5 \rceil = 1$, $\lceil 2 \rceil = 2$.

En el contexto de nuestras matrices, esto significa que cualquier entrada de $M_R M_S$ que sea mayor que cero (lo que indica que hay al menos un camino) se convertirá en 1 después de dividirla por $|B|$ y aplicar la función techo. Si es cero, seguirá siendo cero.

Ejemplo

Retomando nuestro ejemplo, $M_R M_S = \begin{pmatrix} 1 & 2 \end{pmatrix}$ y $|B| = 2$.

Aplicando la fórmula:

$$M_{S\circ R} = \left\lceil \frac{1}{2} \begin{pmatrix} 1 & 2 \end{pmatrix} \right\rceil = \left\lceil \begin{pmatrix} 0.5 & 1 \end{pmatrix} \right\rceil.$$

Aplicando la función techo a cada elemento:

$$M_{S\circ R} = \begin{pmatrix} \lceil 0.5 \rceil & \lceil 1 \rceil \end{pmatrix} = \begin{pmatrix} 1 & 1 \end{pmatrix}.$$

Esto coincide con la matriz $M_{S \circ R}$ que obtuvimos directamente, demostrando la utilidad de esta fórmula.

Corolario 3: Potencias de Relaciones

Corolario:

Sean $R$ una relación sobre $A$, con $A$ un conjunto finito. Se tiene que

$$M_{R^2} = \left\lceil \frac{1}{|A|} (M_R)^2 \right\rceil,$$

además, si $n\in\mathbb{N}^*$,

$$M_{R^n} = \left\lceil \frac{1}{|A|^{n-1}}(M_R)^n \right\rceil.$$

Este corolario es muy útil porque nos permite determinar si existe una secuencia de $n$ relaciones entre dos elementos usando solo operaciones matriciales. Por ejemplo, $R^2$ nos diría si puedes ir de un elemento a otro en dos «pasos» a través de la relación $R$.

Ejemplo

Sea $A = \{\text{A}, \text{B}, \text{C}\}$ y una relación $R$ en $A$ que representa «puede llegar a»:

A puede llegar a B.
B puede llegar a C.
C puede llegar a B.

La matriz $M_R$ sería:

$$M_R = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}.$$

Ahora, calculemos $(M_R)^2$ para ver los caminos de 2 pasos:

$$(M_R)^2 = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}.$$

Aquí, $|A| = 3$. Aplicamos la fórmula para $M_{R^2}$:

$$M_{R^2} = \left\lceil \frac{1}{3} (M_R)^2 \right\rceil = \left\lceil \frac{1}{3} \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \right\rceil = \left\lceil \begin{pmatrix} 0 & 0 & 1/3 \\ 0 & 1/3 & 0 \\ 0 & 0 & 1/3 \end{pmatrix} \right\rceil.$$

Aplicando la función techo a cada elemento:

$$M_{R^2} = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}.$$

Esto nos dice, por ejemplo:

A puede llegar a C en 2 pasos (A $\to$ B $\to$ C).
B puede llegar a B en 2 pasos (B $\to$ C $\to$ B).
C puede llegar a C en 2 pasos (C $\to$ B $\to$ C).