6.4: Matrices de Relaciones

Hemos discutido dos de las muchas formas posibles de representar una relación, a saber, como dígrafo o como conjunto de pares ordenados. En esta sección discutiremos la representación de las relaciones por matrices.

Representación de una relación con una matriz

Definición\(\PageIndex{1}\): Adjacency Matrix

Dejar\(A = \{a_1,a_2,\ldots , a_m\}\) y\(B= \{b_1,b_2,\ldots , b_n\}\) ser conjuntos finitos de cardinalidad\(m\) y\(n\text{,}\) respectivamente. Let\(r\) be a relation from\(A\) into\(B\text{.}\) then\(r\) can be represented by the\(m\times n\) matrix\(R\) defined by

\ begin {ecuación*} R_ {ij} =\ left\ {\ begin {array} {cc} 1 &\ textrm {if} a_i r b_j\\ 0 &\ textrm {de lo contrario}\\\ end {array}\ derecho. \ end {ecuación*}

\(R\)se llama la matriz de adyacencia (o la matriz de relación) de\(r\text{.}\)

Ejemplo\(\PageIndex{1}\): A Simple Example

Let\(A = \{2, 5, 6\}\) and let\(r\) be the relation\(\{(2, 2), (2, 5), (5, 6), (6, 6)\}\) on\(A\text{.}\)\(r\) Since es una relación desde\(A\) dentro del mismo conjunto\(A\) (el\(B\) de la definición), tenemos\(a_1= 2\text{,}\)\(a_2=5\text{,}\) y\(a_3=6\text{,}\) while\(b_1= 2\text{,}\)\(b_2=5\text{,}\) y\(b_3=6\text{.}\) Next, since

• \(2 r 2\text{,}\)tenemos\(R_{11}= 1\)
• \(2 r 5\text{,}\)tenemos\(R_{12}= 1\)
• \(5 r 6\text{,}\)tenemos\(R_{23}= 1\)
• \(6 r 6\text{,}\)tenemos\(R_{33}= 1\)

Todas las demás entradas de\(R\) son cero, entonces

\ begin {ecuación*} R =\ left (\ begin {array} {ccc} 1 & 1 & 0\\ 0 & 0 & 1\\ 0 & 0 & 1\\\ end {array}\ derecha)\ end {ecuación*}

Composición como Multiplicación Matricial

De la definición de\(r\) y de composición, observamos que

\ begin {ecuación*} r^2 =\ {(2, 2), (2, 5), (2, 6), (5, 6), (6, 6)\}\ end {ecuación*}

La matriz de adyacencia de\(r^2\) es

\ begin {ecuación*} R^2 =\ left (\ begin {array} {ccc} 1 & 1\\ 0 & 0 & 1\\ 0 & 1\\ 0 & 0 & 1\\\ end {array}\ right)\ text {.} \ end {ecuación*}

No escribimos\(R^2\) sólo con fines notacionales. De hecho, se\(R^2\) puede obtener del producto matriz\(R R\text{;}\) sin embargo, debemos usar una forma ligeramente diferente de aritmética.

Definición\(\PageIndex{2}\): Boolean Arithmetic

La aritmética booleana es la aritmética definida al\(\{0,1\}\) usar la suma booleana y la multiplicación booleana, definida por

Mesa\(\PageIndex{1}\)

\(0 + 0 = 0\)	\(0+1 = 1 + 0=1\)	\(1 + 1 = 1\)
\(0\cdot 0=0\)	\(0 \cdot 1 = 1 \cdot 0 = 0\)	\(1 \cdot 1 = 1\)

Observe que del Capítulo 3, esta es la “aritmética de la lógica”, donde\(+\) reemplaza “o” y\(\cdot\) reemplaza “y”.

Ejemplo\(\PageIndex{2}\): Composition by Multiplication

Supongamos que\(R=\left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right)\) y\(S=\left( \begin{array}{cccc} 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{array} \right)\text{.}\) Luego usando aritmética booleana,\(R S =\left( \begin{array}{cccc} 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ \end{array} \right)\) y\(S R=\left( \begin{array}{cccc} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{array} \right)\text{.}\)

Teorema\(\PageIndex{1}\): Composition is Matrix Multiplication

Let\(A_1\text{,}\)\(A_2\text{,}\) y\(A_3\) ser conjuntos finitos donde\(r_1\) es una relación desde\(A_1\) dentro\(A_2\) y\(r_2\) es una relación desde\(A_2\) hacia\(A_3\text{.}\) If\(R_1\) y\(R_2\) son las matrices de adyacencia de\(r_1\) y\(r_2\text{,}\) respectivamente, entonces el producto \(R_1R_2\)usando aritmética booleana es la matriz de adyacencia de la composición\(r_1r_2\text{.}\)

Observación: Una ayuda conveniente para construir la matriz de adyacencia de una relación de un conjunto\(A\) en un conjunto\(B\) es escribir los elementos desde\(A\) una columna que precede a la primera columna de la matriz de adyacencia, y los elementos de\(B\) en una fila por encima de la primera fila. Inicialmente,\(R\) en Ejemplo\(\PageIndex{1}\) sería

\ begin {ecuation*}\ begin {array} {cc} &\ begin {array} {ccc} 2 & 5 & 6\\ end {array}\\ begin {array} {c} 2\\ 5\ 6\\ end {array} &\ left (\ begin {array} {ccc} & &\\ & &\\ end {array}\\ right)\\\ end {array}\ end {ecuación*}

Para rellenar la matriz,\(R_{ij}\) es 1 si y sólo si\(\left(a_i,b_j\right) \in r\text{.}\) Así que, ya que el par\((2, 5) \in r\text{,}\) la entrada de\(R\) correspondiente a la fila etiquetada 2 y la columna etiquetada 5 en la matriz es un 1.

Ejemplo\(\PageIndex{3}\): Relations and Information

Este último ejemplo da una idea de cómo los programas de base de datos relacionales pueden responder sistemáticamente preguntas relacionadas con grandes masas de información. Matrices\(R\) (a la izquierda) y\(S\) (a la derecha) definen las relaciones\(r\) y\(s\) donde\(a r b\) si el software se\(a\) puede ejecutar con el sistema operativo\(b\text{,}\) y\(b s c\) si el sistema operativo\(b\) puede ejecutarse en la computadora\(c\text{.}\)

\ begin {ecuación*}\ begin {array} {cc}\ begin {array} {cc} &\ begin {array} {cccc}\ text {OS1} &\ text {OS2} &\ text {OS3} &\ text {OS4}\ end {array}\\ begin {array} {c}\ text {P1}\\ texto {P2}\\ texto {P2}\\ texto {P3}\\\ text {P4}\ end {array} &\ left (\ begin {array} {cccc} 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 1 & 1\ end {array}\ derecha)\ end {array}\ begin {array} {cc} &\ begin {array} {ccc}\ text {C1} &\ text {C2} &\ text {C3}\ end {array}\\ begin {array} {c}\ text {OS1}\\ text {OS1}\\ texto {OS1}\\ texto {OS1}\\ texto {OS1}\\ texto {OS1}\ 2}\\\ texto {OS3}\\\ texto {OS4}\\\ end {array} &\ left (\ begin {array} {ccc} 1 & 1 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\\ 0 & 1 & 1\ end {array}\ right)\ end {array}\ end {array}\ end {equation*}

Aunque la relación entre el software y las computadoras no está implícita a partir de los datos dados, podemos calcular fácilmente esta información. La matriz de\(rs\) es\(RS\text{,}\) cual es

\ begin {ecuation*}\ begin {array} {cc} &\ begin {array} {ccc}\ text {C1} &\ text {C2} &\ text {C3}\ end {array}\\ begin {array} {c}\ text {P1}\\ text {P2}\\ text {P3}\\ text {P3}\\ text {P4}\ end {array} &\ left (begin\ {array} {ccc} 1 & 1 & 1\\ 1 & 1 & 0\\ 0 & 1 & 1\\ 0 & 1 & 1 & 1\ end { array}\ derecha)\ end {array}\ end {ecuación*}

Esta matriz nos dice de un vistazo qué software se ejecutará en las computadoras enumeradas. En este caso, todo el software se ejecutará en todas las computadoras con la excepción del programa P2, que no se ejecutará en la computadora C3, y los programas P3 y P4, que no se ejecutarán en la computadora C1.

Ejercicios

Ejercicio\(\PageIndex{1}\)

Dejar\(A_1 = \{1,2, 3, 4\}\text{,}\)\(A_2 = \{4, 5, 6\}\text{,}\) y\(A_3 = \{6, 7, 8\}\text{.}\) dejar\(r_1\) ser la relación desde\(A_1\) dentro\(A_2\) definida por\(r_1 = \{(x, y) \mid y - x = 2\}\text{,}\) y dejar\(r_2\) ser la relación desde\(A_2\) dentro\(A_3\) definida por\(r_2 = \{(x, y) \mid y - x = 1\}\text{.}\)

1. Determinar las matrices de adyacencia de\(r_1\) y\(r_2\text{.}\)
2. Usa la definición de composición para encontrar\(r_1r_2\text{.}\)
3. Verificar el resultado en la parte b encontrando el producto de las matrices de adyacencia de\(r_1\) y\(r_2\text{.}\)

Contestar

1. \(\begin{array}{cc} & \begin{array}{ccc} 4 & 5 & 6 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{ccc} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) \\ \end{array}\)y\(\begin{array}{cc} & \begin{array}{ccc} 6 & 7 & 8 \\ \end{array} \\ \begin{array}{c} 4 \\ 5 \\ 6 \\ \end{array} & \left( \begin{array}{ccc} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{array} \right) \\ \end{array}\)
2. \(\displaystyle r_1r_2 =\{(3,6),(4,7)\}\)
3. \(\displaystyle \begin{array}{cc} & \begin{array}{ccc} 6 & 7 & 8 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{array} \right) \\ \end{array}\)

Ejercicio\(\PageIndex{2}\)

1. Determinar la matriz de adyacencia de cada relación dada a través de los dígrafos en el Ejercicio 6.3.3 de la Sección 6.3.
2. Utilizando las matrices encontradas en la parte (a) anterior, se encuentra\(r^2\) de cada relación en el Ejercicio 6.3.3 de la Sección 6.3.
3. Encuentra el dígrafo de\(r^2\) directamente del dígrafo dado y compara tus resultados con los de la parte (b).

Ejercicio\(\PageIndex{3}\)

Supongamos que las matrices en Ejemplo\(\PageIndex{2}\) son relaciones sobre\(\{1, 2, 3, 4\}\text{.}\) ¿Qué relaciones hacen\(R\) y\(S\) describen?

Contestar

Mesa\(\PageIndex{2}\)

R:\(x r y\) si y solo si\(\lvert x -y \rvert = 1\)

S:\(x s y\) si y solo si\(x\) es menor que\(y\text{.}\)

Ejercicio\(\PageIndex{4}\)

Dejar\(D\) ser el conjunto de días de la semana, de lunes a viernes, dejar\(W\) ser un conjunto\(\{1, 2, 3\}\) de empleados de un centro de tutoría, y dejar\(V\) ser un conjunto de lenguajes de computadora para los que se ofrece la tutoría,\(\{A(PL), B(asic), C(++), J(ava), L(isp), P(ython)\}\text{.}\) Definimos\(s\) (horario) de\(D\) a\(W\) por\(d s w\) si \(w\)está programado para trabajar el día También\(d\text{.}\) definimos\(r\) desde\(W\) dentro\(V\) por\(w r l\) si\(w\) puede tutoría de alumnos en lenguaje\(l\text{.}\) Si\(s\) y\(r\) están definidos por matrices

\ begin {ecuation*} S =\ begin {array} {cc} &\ begin {array} {ccc} 1 & 2 & 3\\ end {array}\\\ begin {array} {c} M\\ T\ W\\ R\ F\\ end {array} &\ left (\ begin {array} {ccc} 1 & 0 & 1\ 0 & 1 & 1\ 1 & 0 & 1\\ 0 & 1 & 0\\ 1 & 1 & 0\\\ end {array}\ derecha)\\ \ end {array}\ textrm {y} R=\ begin {array} {cc} &\ begin {array} {cccccc} A & B & C & J & L & P\\ end {array}\\\ begin {array} {c} 1\\ 2\ 3\\ end {array} &\ left (\ begin {array} {cccccc} 0 & 1 & 1 & 0 & 0 & 1\\ 1 & 1 & 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 0 & 1 & 1\\ end {array}\ right)\\ end {array}\ end {equation*}

1. computar\(S R\) usando aritmética booleana y dar una interpretación de la relación que define, y
2. computar\(S R\) usando aritmética regular y dar una interpretación de lo que describe el resultado.

Ejercicio\(\PageIndex{5}\)

¿Cuántas relaciones reflexivas y simétricas diferentes hay en un conjunto con tres elementos?

Pista

Considerar las posibles matrices.

Contestar

Las entradas diagonales de la matriz para tal relación deben ser 1. Cuando se determinan las tres entradas por encima de la diagonal, también se determinan las entradas a continuación. Por lo tanto, están\(2^3\) ajustando la descripción.

Ejercicio\(\PageIndex{6}\)

\(A = \{a, b, c, d\}\text{.}\)Let\(r\) Ser la relación on\(A\) con la matriz de adyacencia\(\begin{array}{cc} & \begin{array}{cccc} a & b & c & d \\ \end{array} \\ \begin{array}{c} a \\ b \\ c \\ d \\ \end{array} & \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} \right) \\ \end{array}\)

1. \(r\)Explique por qué es un pedido parcial en\(A\text{.}\)
2. Dibuja su diagrama de Hasse.

Ejercicio\(\PageIndex{7}\)

Definir relaciones\(p\) y\(q\) sobre\(\{1, 2, 3, 4\}\) por\(p = \{(a, b) \mid \lvert a-b\rvert=1\}\) y\(q=\{(a,b) \mid a-b \textrm{ is even}\}\text{.}\)

1. Representar\(p\) y\(q\) como tanto gráficas como matrices.
2. Determinar\(p q\text{,}\)\(p^2\text{,}\)\(q^2\text{;}\) y representarlos claramente de cualquier manera.

Contestar

1. \(\begin{array}{cc} & \begin{array}{cccc} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right) \\ \end{array}\)y\(\begin{array}{cc} & \begin{array}{cccc} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} \right) \\ \end{array}\)
2. \(P Q= \begin{array}{cc} & \begin{array}{cccc} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right) \\ \end{array}\)\(P^2 =\text{ } \begin{array}{cc} & \begin{array}{cccc} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right) \\ \end{array}\)\(=Q^2\)

Ejercicio\(\PageIndex{8}\)

1. Demostrar que si\(r\) es una relación transitiva en un conjunto\(A\text{,}\) entonces\(r^2 \subseteq r\text{.}\)
2. Encuentre un ejemplo de una relación transitiva para la cual\(r^2\neq r\text{.}\)

Ejercicio\(\PageIndex{9}\)

Definimos\(\leq\) en el conjunto de todas las matrices de\(n\times n\) relación por la regla que si\(R\) y\(S\) son cualesquiera dos matrices de\(n\times n\) relación,\(R \leq S\) si y solo si\(R_{ij} \leq S_{ij}\) para todos\(1 \leq i, j \leq n\text{.}\)

1. Demostrar que\(\leq\) es un orden parcial en todas las matrices de\(n\times n\) relación.
2. Demuéstrale eso\(R \leq S \Rightarrow R^2\leq S^2\), pero lo contrario no es cierto.
3. Si\(R\) y\(S\) son matrices de relaciones de equivalencia y\(R \leq S\text{,}\) cómo se definen las clases de equivalencia\(R\) relacionadas con las clases de equivalencia definidas por\(S\text{?}\)

Contestar

1. Reflejo:\(R_{ij}=R_{ij}\) para todos\(i\)\(j\), por lo tanto\(R_{ij}\leq R_{ij}\)
   antisimétrico: Asumir\(R_{ij}\leq S_{ij}\) y\(S_{ij}\leq R_{ij}\) para todos\(1\leq i\),\(j\leq n\). Por lo tanto,\(R_{ij}=S_{ij}\) para todos\(1\leq i\),\(j\leq n\) y así\(R=S\)
   Transitivo: Asumir\(R,\: S\), y\(T\) son matrices donde\(R_{ij}\leq S_{ij}\) y\(S_{ij}\leq T_{ij}\), para todos\(1\leq i\),\(j\leq n\). Entonces\(R_{ij}\leq T_{ij}\) para todos\(1\leq i\),\(j\leq n\), y así\(R\leq T\).
2. \[\begin{aligned}(R^{2})_{ij}&=R_{i1}R_{1j}+R_{i2}R_{2j}+\cdots +R_{in}R_{nj} \\ &\leq S_{i1}S_{1j}+S_{i2}S_{2j}+\cdots +S_{in}S_{nj} \\ &=(S^{2})_{ij}\Rightarrow R^{2}\leq S^{2}\end{aligned}\]
   Para verificar que lo contrario no es cierto solo necesitamos un ejemplo. For\(n=2\), let\(R_{12}=1\) y todas las demás entradas iguales\(0\), y let\(S\) ser la matriz cero. Ya que\(R^{2}\) y\(S^{2}\) son tanto la matriz cero,\(R^{2}\leq S^{2}\), pero ya que\(R_{12}>S_{12}\),\(R\leq S\) es falsa.
3. Las matrices se definen en el mismo conjunto\(A=\{a_1,\: a_2,\cdots ,a_n\}\). Dejar\(c(a_{i})\),\(i=1,\: 2,\cdots, n\) ser las clases de equivalencia definidas por\(R\) y let\(d(a_{i}\)) ser las definidas por\(S\). Reclamación:\(c(a_{i})⊆ d(a_{i})\).
   \[\begin{aligned}a_{j}\in c(a_{i})&\Rightarrow a_{i}ra_{j} \\ &\Rightarrow R_{ij}=1\Rightarrow S_{ij}=1 \\ &\Rightarrow a_{i}sa_{j} \\ &\Rightarrow a_{j}\in d(a_{i})\end{aligned}\]