# Show that if the transitive closure can be computed in T(|V |) time then BMM can be solved in O(T(3n)) time

Show that if the transitive closure can be computed in T(|V |) time then BMM can be solved in O(T(3n)) time. I didn't understand the proof in the context of building edges. I added the proof

i tried to write an example

Michael P. Kim, Editted by: Bill Kuszmaul people.csail.mit.edu/virgi/6.890/lecture3.pdf

Thanks

• What exactly you did not understand? – dkaeae Jan 10 at 16:42
• Also, the proof seems to have been taken from some paper or similar. Please give the original author credit for their work. – dkaeae Jan 10 at 16:44
• Scribe: Michael P. Kim, Editted by: Bill Kuszmaul people.csail.mit.edu/virgi/6.890/lecture3.pdf – Kate Jan 10 at 17:15
• I wrote an example, now how to proceed after I have duplicated the matrices and created a graph? what is the next step? – Kate Jan 10 at 20:10
• You compute which nodes on the right are reachable from which nodes on the left. This is transitive closure, and also the product of the two matrices. – Yuval Filmus Jan 11 at 7:37