Space saving matrix multiplication

on 28 Jun 2010 by Mukund (@muks)

This problem was given to me by Marius Eriksen while chatting on IRC many years ago. He said that he didn't use this during recruitment as it was not straightforward. I solved it later that day, but I remember that my head hurt after that. ;)

Given a square-matrix A[a_{i,j}]_{n\times n} and values x and y where 1\leq x\leq n and 1\leq y\leq n, devise a space-optimized algorithm to find A^n[x,y].

Hint: This is not your run-of-the-mill matrix multiplication. Your algorithm should only allocate and use c_0n+c_1 or less bytes of memory, where c_0 and c_1 are constants.


Untar and read the implementation in matrix.tar.gz. It needs a POSIX environment to build.