# How do you find $R^2$ and $R^3$ and $R\circ T$?

Given relations $R$ and $T$ on $\{a,b,c,d,e\}$

where $R = \{(a,b), (a,e), (b,c), (c,e), (e,e)\}$

where $T = \{(a,d), (d,e), (e,a)\}$

I don't have an equation, so how do I find $R^2$ and $R^3$ and $R\circ T$?

-
How can you find them? Well, you could calculate them explicitly by using the definition of composition. – Asaf Karagila Nov 29 '12 at 16:31
what's the definition of composition? – mathnoob Nov 29 '12 at 16:45
You are trying to solve a problem without understanding it? That is never good. – Asaf Karagila Nov 29 '12 at 17:36
isn't it for some z aRz ^ zRb, but how does that help me here? – mathnoob Nov 29 '12 at 17:56
you can get the transitive closure by doing R o R n times as far as i can remember. – mathnoob Nov 29 '12 at 18:44

## 2 Answers

Using matrix multiplication:

$(a,b),(a,e),(b,c),(c,e),(e,e)$

(For $R^2$) Take the matrix $$M_R = \begin{matrix} 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}$$

Then $$M_R^2 = \begin{matrix} 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}$$

And hence you can read $R^2$ off $M_R^2$ as $$R^2 = \{ (a,c) , (a, e), (b,e), (c,e), (d,e), (e,e) \}$$

So, to answer your comment: yes, that's it.

-

Hint: Here is an equation for the composition: For relations $S, S' \subseteq \{a,b,c,d,e\}^2$ we have $$S \circ S' = \{(x,y) \in \{a,b,c,d,e\}^2 \mid \exists z: (x,z)\in S', (z,y) \in S\}$$ Now check for each pair if you can find a $z$. And $R^2 = R\circ R$, $R^3 = R \circ R^2$.

-
I can't find a z because I don;t have an equation. – mathnoob Nov 29 '12 at 16:36