GATE DISCRETE MATHS

Question

The matrix of a relation R: A->A is given by 

                           

                M_{R =}    

Determine R^-1  and compliment of R.                             

Comments

source of this question ?

---

whats the need of source just solve sir if you know :(

---

This is a question Of Discrete MAthematics paper only !

---

Then what is R²?

Answer 1

Here M_R is the matrix representation of the relation R.

Inverse (R^-1):-Every relation, however, has an inverse relation,so for any relation R , MR-1 exists Recall that if R is relation on A

R^-1 = { (y,x)∈ A $\times$ A:(x,y) ∈ R }

it’s the relation that you get from R by ‘turning all the ordered pairs around’. This operation actually does have an effect on the matrix that is familiar from linear algebra, but it’s not taking the inverse of the matrix.it’s taking the transpose.

We take the transpose of the matrix, since we want the ( i, j ) ^th entry of the matrix for R ^-1 to be 1 if and only if the ( j, i ) ^th entry of the matrix for R is 1.

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

M_R^-1=$\begin{bmatrix} 1 &1 &1 \\ 0& 1&1 \\ 0& 1& 0\\ 0& 1& 0 \end{bmatrix}$

Note :-Here we are finding M_R^-1 not ( M_R )^-1. 

Complement ($\bar R$) :- In $\bar R$ If the ij^th entry of M_R is x, then the ij^th entry of M_{$\bar R$} is (x+1) mod 2.  In other words, every 0 is replaced by 1 and every 1 is replaced by 0.

M_{$\bar R$} =$\begin{bmatrix} 0 &1 &1 &0 \\ 0& 0 & 0 & 0\\ 0& 0 & 1 &1 \end{bmatrix}$

Comments

@Leen. Whats intuition behind (x+1)%2 ?