The qestion: Let M be an n × n matrix satisfying the property that M[i; j] = M[i − 1; j − 1] where 1 ≤ i ≤ n − 1 and 1 ≤ j ≤ n − 1 (note that the rows and columns of M are indexed from 0 to n−1). Given a length-n vector V , show that MV can be computed in O(n log n) time. (Hint. Make use of the fact that polynomial multiplication can be computed in O(n log n) time using the FFT algorithm.)
My current strategy: I understand that I have to rewrite the matrix M and vector V into two polynomial representation , i.e. M(x) and V(x). So, I can directly apply FFT algorithm to do the polynomial multiplication.
However, I encounter a problem on computing M(x) as I do not know how the property of matrix M can be used to form the polynomial M(x) while I do know how to rewrite vector V into V(x) where V(x) = v0 * x^0 + v1 * x^1 + ... + vn-1 * x^n-1 such that V = [v0,v1,v2,...,vn-1] Can somebody give me some idea on the computation of M(x)?