+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}$

edited | 422 views
0
Answer $1)$ finding transitive closer will get the answer.

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
+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}$

by Loyal (5.4k points)