Are there some good algorithm to select m by three matrices which satisfies certain conditions?

Question

I would like to find an algorithm which select matrices satisfying certain conditions.

We consider integer matrices (entries of the matrices comes from $\{1,\ldots,n\}$ for some positive integer $n$) and the numbers in each row are different from each other.

Let me first explain some definitions.

We call a matrix $M$ with m rows and k columns canonical if for all $i \in [2, m]$ and $j \in [2, k]$, $M_{i,j} > M_{i-1, j-1}$ and for all $i \in [2,m]$ and $j \in [1,k]$, $a_{ij} \ge a_{i-1,j}$. For example, $\left(\begin{array}{ccc}3 & 5 & 9\\2 & 5 & 8\\1 & 4 & 7\\1 & 4 & 6\end{array}\right)$ is canonical.

Let $M$ be a matrix with $k$ columns. Denote by $I_j$ the set of the elements in the $j$th row. We say that two rows $j_1, j_2$ of $M$ i-interlacing if $|J_{j_1} \backslash J_{j_2}|=|J_{j_2} \backslash J_{j_1}|=i$ and $J_{j_1}\backslash J_{j_2} = \{a_1,a_2,\ldots,a_i\}$, $J_{j_2} \backslash J_{j_1} = \{b_1,b_2,\ldots,b_i\}$, either $a_1 < b_1<a_2<b_2 < \cdots < b_{i-1} <a_i < b_i$ or $b_1<a_1<b_2<a_2 < \ldots < a_{i-1}<b_i<a_i$. In particular, if two rows of a matrix are identical, then we say that the two rows are $0$-interlacing.

For example, the first row and the second row of $\left(\begin{array}{ccc}3 & 5 & 9\\2 & 5 & 8\\1 & 4 & 7\\1 & 4 & 6\end{array}\right)$ are $2$-interlacing. The third row and the fourth row of the matrix are $1$-interlacing.

For a matrix $M$ with entries in $\{1, \ldots, n\}$, denote $x=x(M)=(x_1, \ldots, x_n)$, where $x_i$ is the number of entries in $M$ which equal to $i$. Denote $q(M)=\sum_{i=1}^n x_i^2 + \frac{2-k}{k^2} (\sum_{i=1}^n x_i)^2$, where $k$ is the number of columns of $M$. For example, let $M=\left(\begin{array}{ccc}3 & 5 & 9\\2 & 5 & 8\\1 & 4 & 7\\1 & 4 & 6\end{array}\right)$. Then $x(M) = (2,1,1,2,2,1,1,1,1)$ and $q(M)=2$.

I would like to find all $m \times 3$ matrices $M$ with entries in $\{1, \ldots, 9\}$ which satisfy the following conditions:

(1) in each row of $M$, any two entries are different from each other; the numbers in each row are increasing from left to right;

(2) any two rows of $M$ are $i$-interlacing for some $i \in \{0,1,2,3\}$;

(3) there are two rows of $M$ which are $3$-interlacing;

(4) $M$ is canonical;

(5) $q(M)=2$.

In the cases of $m=2,3,4$, I use many for loops to find out all such matrices. But when $m \ge 5$, it takes infinite time. Is there some fast algorithm to find out all the matrices which satisfy the conditions? Thank you very much.

Answer 1

Here is an iterative algorithm to enumerate such matrices, which proceeds by induction on $m$. I suspect it will be be better than brute force.

Let condition (2') be that every pair of rows is $i$-interlacing for some $i\in \{0,1,2\}$.

Note that every matrix that satisfies conditions (1), (2), (3), (4) can be broken up into the concatenation of a matrix $M^1$ that satisfies conditions (1), (2'), (4), a row $r^2$ that when paired with some row of $M^1$ is 3-interleaving, and a matrix $M^3$ that satisfies conditions (1), (2'), (4). So, we will enumerate all $M^1,r^2,M^3$ and look at their combinations. We'll do it in a smart way that ensures that their concatenation satisfies conditions (4), (5).

Write $r\prec r'$ if row $r$ can precede row $r'$ in a canonical matrix, i.e., $r_0<r'_1$ and $r_1<r'_2$. Write $q(x) = \sum_{i=1}^9 x_i^2 - 1/9 (\sum_{i=1}^9 x_i)^2$.

By induction, assume we have a data structure that lists all $m' \times 3$ matrices that satisfy conditions (1), (2'), (4), for all $m'<m$. Arrange the data structure as a hashtable of lists, keyed on the value of $(m',x(M),M_m')$, where $M_m'$ denotes the last row of the matrix; looking $(m',x,r)$ up in the hashtable returns a list of all $m'\times 3$ matrices $M$ such that $x(M)=x$, $M_m'=r$, and $M$ satisfies conditions (1), (2'), (4).

Similarly, assume we have a data structure that lists all $m'\times 3$ matrices that satisfy conditions (1), (2'), (4), for all $m'<m$, keyed on the value of $(m',x(M),M_1)$, where $M_1$ denotes the first row of the matrix.

Now, enumerate all $m^1,x^1,r^1,r^2,m^3,x^3,r^3$ such that $m^1,x^1,r^1$ that is a valid key of the first hashtable, $r^1 \prec r^2 \prec r^3$, $m^3,x^3,r^3$ is a valid key of the second hashtable, $m^1+1+m^3=m$, and $q(x^1+x(r^2)+x^3)=2$. Then every way of pairing a matrix $M^1$ from the first hashtable (keyed on $(m^1,x^1,r^1)$), the row $r^2$, and a matrix $M^3$ from the second hashtable (keyed on $(m^3,x^3,r^3)$) will yield a matrix $M$ (obtained by concatenating $M^1,r^2,M^3$) that satisfies conditions (1)-(5).

To do this enumeration, I suggest you first guess $r^1,r^2,r^3$ such that $r^1\prec r^2 \prec r^3$, then guess $m^1,m^3$ such that $m^1+1+m^3=m$, then enumerate all $x^1$ such that $m^1,x^1,r^1$ appears as a key of the hashtable, then enumerate all $x^3$ such that $q(x^1+x(r^3)+x^3)=2$ and check whether $m^3,x^3,r^3$ is a key in the hashtable. However you can also try other orders of enumeration.

Also, enumerate all $m^1,x^1,r^1,m^3,x^3,r^3$ such that $m^1,x^1,r^1$ that is a valid key of the first hashtable, $r_1 \prec r^3$, $m^3,x^3,r^3$ is a valid key of the second hashtable, and $m^1+m^3=m$; this gives a $m\times 3$ matrix (obtained by a concatenating $M^1$ and $M^3$) that satisfies conditions (1), (2'), (4). This lets you build up the data structure inductively for $m$ from the data structures for $1,\dots,m-1$.

Further optimization may be possible. The condition $q(M)=2$ is a fairly strong one. For instance, for $m=5$, it implies that $x$ is a permutation of $(1,1,1,1,1,1,2,2,2)$. It implies $\sum_i x_i^2=m^2+2$, and we also know $\sum_i x_i=3m$. This may be helpful for pruning entries of the data structures, when you know $m$ in advance. For instance, if you know that you only care about $m \le 5$, then you can prune all $x(M)$ that contain 3 or any larger number.

Note also that if you care only about counting the number of such matrices, this algorithm gives a way of counting them that may be more efficient than enumerating them. There is no need to store the entire list of such matrices; you can simply store the number of such matrices corresponding to each key in the hashtable.

Answer 2

A simple way to deal with this problem—which perhaps can hardly be called a "good algorithm", but nonetheless provides a variety of performance improvements—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.