edited by
5,170 views
1 votes
1 votes

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 by

2 Answers

3 votes
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.

edited by
1 votes
1 votes
\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
Answer:

Related questions

3 votes
3 votes
1 answer
3
Arjun asked Jul 2, 2019
1,291 views
How many different Boolean functions of degree $n$ are the$2^{2^n}$$(2^2)^n$$2^{2^n} -1$$2^n$
2 votes
2 votes
2 answers
4
Arjun asked Jul 2, 2019
7,063 views
How many ways are there to place $8$ indistinguishable balls into four distinguishable bins?$70$$165$$^8C_4$$^8P_4$