Are there some good algorithm to select m by three matrices which satisfies certain conditions?
A simple way to deal with this problem&mdash;which perhaps can hardly be called a "good algorithm", but nonetheless provides a variety of performance improvements&mdash;is to treat it as a constraint satisfaction / combinatorial search problem and apply backtracking. Each matrix entry branches the search tree 9 ways, but many of these subtrees can be trivially eliminated because they immediately violate one of the conditions.

Take the $m = 5$ case that you got stuck on as an example. For condition 1, note that already there are only $\binom{9}{3}^5 = 4,182,119,424$ matrices of size 5x3 with elements in [1..9] which have elements strictly increasing from left to right in each row. It's $\binom{9}{3}^5$ because condition 1 is equivalent to, for each row, choosing 3 distinct elements from [1..9]. You can of course iterate over such rows with

for i in 1 to 7, for j in i + 1 to 8, for k in j + 1 to 9

Moreover, conditions 2 and 4 can be checked as you are generating the rows, rather than only checking these conditions once you have the entire matrix. This should drastically prune the search tree.

Tassle adds (and provides this sample code):


  You can also prune on condition (5) by first computing all possible profiles $x(M)$ which lead to $q(M)=2$, and then trying to find all satisfying matrices with a specific profile. Out of all 490314 ways to choose 15 numbers in {1...9}, only 84 lead to $q(M)=2$. In fact, using this, even python on my quite slow machine can manage m = 5 in a reasonable time. 


This sort of brute forcing is also embarrassingly parallel and requires hardly any memory, so consider dividing the space of matrices among however many CPU cores you have.