Please see attached files.
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 returns 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 relation 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 representation 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 by 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 corresponding non-zero element in R. Essential Mathematics for Data Scientists Assessment 2E: Characterising relations Tasks Instructions