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 and values and where and , devise a space-optimized algorithm to find .

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

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