9.3 Representing Relations Flashcards
Representing Relations Using Matrices:
A relation between finite sets can be represented using a zero–one matrix. Suppose that R is a
relation from A = {a1, a2, … , am} to B = {b1, b2, … , bn}. (Here the elements of the sets A and
B have been listed in a particular, but arbitrary, order. Furthermore, when A = B we use the
same ordering for A and B.) The relation R can be represented by the matrix MR = [mij], where
mij = 1 if (ai, bj) ∈ R,
0 if (ai, bj) ∉ R
In other words, the zero–one matrix representing R has a 1 as its (i, j) entry when ai is related
to bj, and a 0 in this position if ai is not related to bj.
(Such a representation depends on the
orderings used for A and B.)
Representation of Reflexive relation by matrix:
[ Mij = 1 –> i = j ]
The zero-one matrix for a reflexive relation. (Off diagonal elements can be 0 or 1.)
What can u say about Matrix of a relation on a set:
It will be a square matrix.
Matrix of symmetric Relation:
R is symmetric if and only if mji = 1 whenever
mij = 1. This also means mji = 0 whenever mij = 0. Consequently, R is symmetric if and only
if mij = mji, for all pairs of integers i and j with i = 1, 2, … , n and j = 1, 2, … , n
Mr = (Mr)^t ( transpose)
Matrix of Antisymmetric Relation:
The matrix of an antisymmetric relation has the property that if mij = 1 with i ≠ j,
then mji = 0. Or, in other words, either mij = 0 or mji = 0 when i ≠ j
Think it through, take a look at the graphic pg 623.
Matrices representing Union and intersection of relations:
M r1∪r2 = Mr1 ∨ Mr2 - Join
M r1∩r2 = Mr1 ∧ Mr2 - Meet
Matrix of composite relation:
In particular, suppose that R is a relation from A to B and S is a relation from B to C.
Suppose that A, B, and C have m, n, and p elements, respectively. Let the zero–
one matrices for S ◦R, R, and S be MS ◦R = [tij], MR = [rij], and MS = [sij], respectively
(these matrices have sizes m × p, m × n, and n × p, respectively).
The ordered pair (ai, cj) belongs to
S ◦R if and only if there is an element bk such that (ai,bk) belongs to R and (bk, cj) belongs to S.
It follows that tij = 1 if and only if rik = skj = 1 for some k. From the definition of the Boolean
product, this means that
Ms ◦r = Mr ⊙ Ms.
Digraphs:
A directed graph, or digraph, consists of a set V of vertices (or nodes) together with a set
E of ordered pairs of elements of V called edges (or arcs). The vertex a is called the initial
vertex of the edge (a, b), and the vertex b is called the terminal vertex of this edge.
An edge of the form (a, a) is represented using an arc from the vertex a back to itself. Such
an edge is called a loop.
The relation R on a set A is represented by the directed graph that has the elements of A as its
vertices and the ordered pairs (a, b), where (a, b) ∈ R, as edges. This assignment sets up a one to-one correspondence between the relations on a set A and the directed graphs with A as their
set of vertices. Thus, every statement about relations corresponds to a statement about directed
graphs, and vice versa
When are digraphs reflexive, symmetric:
A relation is reflexive if and only if there is a loop at every vertex of the directed graph, so that every ordered pair of the form (x, x) occurs in the
relation.
A relation is symmetric if and only if for every edge between distinct vertices in its
digraph there is an edge in the opposite direction, so that (y, x) is in the relation whenever
(x, y) is in the relation.
[Note that a symmetric relation can be represented by an undirected graph, which is a
graph where edges do not have directions.]
When are digraphs antisymmetric, transitive:
A relation is antisymmetric if and only if there are never 2 edges in opposite directions between distinct vertices.
A relation is transitive if and only
if whenever there is an edge from a vertex x to a vertex y and an edge from a vertex y to a
vertex z, there is an edge from x to z (completing a triangle where each side is a directed edge
with the correct direction)
When are digraphs, matrix irreflexive:
If and only if every entry on the main diagonal of the matrix is 0.
When are diagraphs, matrix asymmetric:
Mij = 1 –> Mji = 0
