Thought I'll add a time complexity analysis since I couldn't find one posted here(or maybe I've missed it):

If we assume T(n) is the time complexity for solving the problem of size n(n * n matrix), we have the following recursion:

T(n) = n * (T(n-1) + n^2)

Basically we have n problems of size n-1 and also n^2 to construct the matrix for each sub problem.

Expanding the above we have:

T(n) = n * T(n-1) + n^3

which gives us

T(n) = n^n

What do you guys think?