Kenneth Rosen Edition 6th Exercise 7.4 Example 7 (Page No. 493)

Question

I am not getting the (2n-1) factor. n^2 is for matrix mul and multiplication is being done (n-1) times. so n^2(n-1) is understood. But what is (2n-1)??

Answer 1

I am not getting the (2n-1) factor.

When we multiply Two $n \times n$ matrices $A,B$, then We get a $n \times n$ matrix $C$. But to compute Each element $C_{ij}$ of this matrix $C$, We need to multiply $i^{th}$ Row of $A$ with $j^{th}$ column of $B$. So, For $C_{ij}$, We need to do $n$ multiplications, and $n-1$ additions. Hence, Total $2n-1$ Operations for One element. And there are Total $n^2$ elements in $C$, So, $n^2(2n-1)$ Operations for One boolean product of Two matrices. 

We have to compute Total $n-1$ such Matrix Products of $n \times n$ matrices. So, $(n-1)n^2(2n-1)$ Operations.  

Comments

Transitive closure is nothing but $M_{R^*}$ as you know it. And

$M_{R^∗} = M_R ∨ M^{[2]}_R ∨ M^{[3]}_R ∨···∨ M^{[n]}_R .$

So, $n^2(2n-1)(n-1)$ was for computing $M_R^{[i]}$ , $i = 1 \,\,to\,\,n$.

And Now, We need to Join(Union) these matrices to compute $M_{R^*}$ .. So, For that $n^2$ elements in $M_{R^*}$ and each needs $(n-1)$ boolean addition. So, that extra $n^2(n-1)$

---

sry for the silly doubt :( . I need to start reading carefully what is being asked. Thank you.

---

No problem. Just keep going.