The Gateway to Computer Science Excellence
+1 vote
422 views

Find the zero-one matrix of the transitive closure of the relation given by the matrix $A$ :

$$A =\begin{bmatrix} 1 & 0& 1\\ 0 & 1 & 0\\ 1& 1& 0 \end{bmatrix}$$

  1. $\begin{bmatrix} 1 & 1& 1\\ 0 & 1 & 0\\ 1& 1& 1 \end{bmatrix}$
  2. $\begin{bmatrix} 1 & 0& 1\\ 0 & 1 & 0\\ 1& 1& 0 \end{bmatrix}$
  3. $\begin{bmatrix} 1 & 0& 1\\ 0 & 1 & 0\\ 1& 0& 1 \end{bmatrix}$
  4. $\begin{bmatrix} 1 & 1& 1\\ 0 & 1 & 0\\ 1& 0& 1 \end{bmatrix}$
in Set Theory & Algebra by Veteran (431k points)
edited by | 422 views
0
Answer $1)$ finding transitive closer will get the answer.

2 Answers

+3 votes

Let the elements be $a,b,c$ on which the relation is defined.

Then from the matrix  we can say that the relation given is $\{ (a,a),(a,c),(b,b),(c,a),(c,b)\}$

Now, what are the minimum number of ordered pairs that we should add to the given relation that it becomes transitive relation?

Using Warshall's Algorithm we can see that $(c,c)$ and $(a,b)$ are missing.

After adding them to the relation and making the matrix again the matrix will become

$\begin{bmatrix} 1 & 1&1 \\ 0& 1&0 \\ 1 & 1 & 1 \end{bmatrix}$

$\therefore$ Option $1.$ is correct.

by Boss (24k points)
edited by
+1 vote
\begin{bmatrix} & 1 0 1& \\ & 010& \\ &110 & \end{bmatrix}

Matrix contain 3rows like as 1,2,3 and 3 columns like as 1,2,3

Set A={1,2,3}

From matrix the relation can be formed

A={(1,1),(1,3),(2,2),(3,1),(3,2)}

transitive closure={(1,1),(1,3),(1,2),(2,2),(3,1),(3,2),(3,3)}

Represent into matrix form

=$\begin{bmatrix} & 1 1 1& \\ &0 1 0 & \\ &1 1 1 & \end{bmatrix}$

Hence 1 is right answer
by Loyal (5.4k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,321 answers
198,401 comments
105,156 users