Think how many permutations of the first column there can be, now many of the second, ... think how many matricies you will have when you "want to generate all matrix." Is that perhaps a problem?

Think why first doing Transpose, then doing some other things and finally doing another Transpose might be interesting.

Think what that "then doing some other things" might be.

Is this possibly related to a homework problem?

My suggestion to consider Transpose wasn't meant to change your problem, it was meant to put each column into a separate list, work on permuting those lists and then put the result back into the original form. Without considering your condition limiting the number in each row the number of matricies seems to be (5!)^4 and that is big.

Here is different idea. Suppose you leave the first column untouched. Can you think of a way to generate all the 120 different second columns and discard those columns which are not acceptable. Then repeat that process using first and second to eliminate from third...

When you are done with that then you could do the 5! permutations on every one of those solutions.