For each non negative integer k, we have a 2^k* 3^k matrix M k de fined as follows:
M0 = [1] :
Mk+1 =
[Mk 2Mk 3Mk
4Mk 5Mk 6Mk]
for each k >= 0
Let n = 3^k. Design an algorithm running in time (n) which does the following: given a vector x of length n, the algorithm computes the matrix-vector product Mk .x (which is a vector of length 2^k).
Hint: recursive in some sense