Essential Mathematics for Data Scientists
Assessment 2E: Characterising relations
Tasks
1. Create an isreflexive function that tests for reflexivity in the same way that the
issymmetric function tests for symmetry. Recall that this function must check if all the
diagonal elements are true. (3 marks)
2. Create an istransitive function that tests for transitivity. Recall that this function
eturns true if all non-zero elements in ??2 are accompanied by non-zero (true) elements
at the same locations in ??. (5 marks)
3. Using MATLAB’s issymmetric function alongside your isreflexive and
istransitive functions, determine which of R1, R2 and R3 is an equivalence relation,
as well as how many equivalence classes it has. (2 marks)
Example solution:
load R.mat
issymmetric(R1) % true
isreflexive(R1) % true
istransitive(R1) % also true, therefore R1 is an equivalence
elation
plot(digraph(R1)) % shows a graph made up of 5 disjoint
graphs, therefore R1 is an equivalence relation with 5
equivalence classes
Instructions
This exercise forms a part of your code workbook. Include answers to the tasks below in your
workbook as appropriately commented MATLAB code.
For this MATLAB exercise, we are interested in and characterising a relation through its
epresentation as a matrix.
You should have the file “R.mat” ready. It contains three 50 × 50 relation matrices that each
describe a relation between the elements of the set ?? = {1,2,3, … ,49,50}. You can load the matrices
into MATLAB with
load R.mat
These matrices will then appear as the variables R1, R2 and R3.
Recall that MATLAB stores true and false values as 1 and 0, respectively. To see the overall
structure of each matrix, the spy function can be used to plot all non-zero elements (i.e. elements
for which the relation is true). For example:
spy(R3)
Notice that a relation matrix with 1 and 0 in place of true and false is also the adjacency matrix
for its relation’s digraph. Thus, plotting the graphical representation of the relation described by R3
is as simple as
plot(digraph(R3))
Your goal in this exercise is to determine which of these matrices (R1, R2 and R3) describes an
equivalence relation, as well as how many equivalence classes that relation has.
Recall, an equivalence relation is:
• Symmetric
• Reflexive
• Transitive
Fortunately, MATLAB already has an issymmetric function, which you are free to use. You will,
however, need to create your own isreflexive and istransitive functions to complete this
exercise.
To determine reflexivity, it is a simple matter of checking that there are no zeros on the main
diagonal. For the trickier case of transitivity, it turns out that is useful to first quantify the various
paths in the digraph form of a relation. Consider the following example relation, in graph form:
and in matrix form:
R = �
?? ?? ?? ??
?? ?? ?? ??
?? ?? ?? ??
?? ?? ?? ??
�
Notice that a ?? for element ??, ?? means that there is a path between vertex ?? and vertex ??, and that an
?? means there isn’t one. We can thus quantify the number of direct paths (of length 1) between
each pair of vertices ?? and ?? by replacing all ??’s with 1 and ??’s with 0:
R = �
0 1 1 1
0 0 1 1
0 0 0 1
0 0 0 0
�
This is, coincidently, how MATLAB would represent the true’s and false’s in the relation matrix.
It turns out that, in general, the ??-th power of the relation matrix, R??, gives the number of length-??
paths that exist between each pair of vertices. For example, the number of length-0 paths are given
y the zeroth power (the identity matrix):
R0 = �
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
�
This makes sense, as the only way to reach a vertex after moving along a “path” of length 0 is to
start at that same vertex.
As we have already established, the relation matrix itself gives the number of length-1 paths:
R1 = �
0 1 1 1
0 0 1 1
0 0 0 1
0 0 0 0
�
e.g. there is 1 such path from vertex 1 to vertex 2. The fact that there is a lower triangle of zeros is
due to the lack of any paths from larger numbers toward smaller numbers. Also, the diagonal of
zeros shows that there are no loop edges (no length-1 paths from a vertex to itself).
Similarly, we can consider the number of length-2 paths by squaring the relation matrix:
R2 = �
0 0 1 2
0 0 0 1
0 0 0 0
0 0 0 0
�
There are thus 4 total length-2 paths for this graph. One from vertex 1 to vertex 3 (via 2), another
from vertex 2 to vertex 4 (via 3) and two from vertex 1 to vertex 4 (one via 2, the other via 3).
The number of length-3 paths can also be found:
R3 = �
0 0 0 1
0 0 0 0
0 0 0 0
0 0 0 0
�
i.e. there is a single path of length 3 from vertex 1 to vertex 4 (via 2 and 3).
Finally, there are no length-4 paths or above for this graph:
R4 = R5 = R6 = ⋯ = �
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
�
i.e. no matter where you start, you eventually get stuck at vertex 4.
Recall now that a relation ?? over a set ?? is transitive if ?????? and ?????? imply ??????, for all ??,??, ?? ∈ ??.
Here, “?????? and ??????” describe a path of length 2 from ?? to ?? and “??????” describes a path of length 1
from ?? to ??. This gives us a way to determine transitivity. That is, a relation is transitive if every
length-2 path is accompanied by a length-1 path. i.e. all non-zero elements in R2 must also have a
co
esponding non-zero element in R.
Essential Mathematics for Data Scientists
Assessment 2E: Characterising relations
Tasks
Instructions