Exercise 28.4-6

Solution wanted!

Exercise 28.4-5

Solution wanted!

Exercise 28.4-4

Given a n * n boolean matrix A, the transitive-closure of A is , which can be get by repeat squaring in multiplication. Given two matrix A and B, we can construct a matrix C with up-right is A and down-left is B, otherwise zero. The result of A * B can be extracted by transitive closure C’s top left sub-matrix.

Exercise 28.4-3

Solution wanted!

Exercise 28.4-2

Solution wanted!

Exercise 28.4-1

Square operation can be simulated easily by multiply itself, hence M(n) time matrix multiplication implies an O(M(n)) time squaring algorithm. If we want to multiply two matrix A and B, we can construct a matrix C with top-right is A and down-left is B, otherwise 0. The result of A * B can be extracted from .