$(N^2 - 1)/(N - 1) = N+1$ and its relation to sorting square matrices.

Question

I'm working on a problem that involves sorting the members of square matrices into groups. Here are the sorting rules:

1. Group size equals the square root of the number of members in the matrix
2. Every member has to end up in a group
3. Every group must be composed of members who have not been together in a prior group, aka no overlap
4. The matrix must be broken into sets of groups until every member has been grouped with every other member exactly once

Take a 3x3 matrix for example:

\begin{matrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{matrix}

Following the sorting rules, all necessary sets of groups are:

\begin{matrix} 1: & [1,2,3] & [4,5,6] & [7,8,9]\\ 2: & [1,4,7] & [2,5,8] & [3,6,9]\\ 3: & [1,5,9] & [2,6,7] & [3,4,8]\\ 4: & [1,6,8] & [2,4,9] & [3,5,7] \end{matrix}

Notice that there are 4 sets of groups. For a 4x4, there are 5 sets of groups. I expect this behavior continues indefinitely which is why I brought up $(N^2-1)/(N-1) = N+1$ in the title.

I wrote a python program to compute these sets of groups for an arbitrarily sized square matrix: https://github.com/hayden-blair/squares/

PROBLEM

My member selection algorithm is greedy... For 5x5's and higher, The algorithm is selecting groups that force incomplete sets. Some members are unable to be sorted because the previously selected groups limit the choices available for future selections in such a way that the sorting criteria cannot be satisfied. I can find the solutions on paper, but I can't find a pattern that lets me do the math correctly through my algorithm.

Does anyone have any resources they could point me to on this topic? I'm sure something like this has been done before...

Thanks in advance for your thoughts!

Answer 1

Yes, this has been done before! In the language of experimental design your task is to create a balanced incomplete block design and to resolve the design into "parallel" classes.

There is a standard notation to characterize BIBDs:

1. $v$, the number of points (or "treatments", in experimental design)
2. $b$, the number of blocks
3. $r$, the number of blocks containing a given point
4. $k$, the number of points in a block
5. $\lambda$, the number of blocks containing any two distinct points

These parameters are not all independent, since $bk=vr$ and $\lambda(v-1)=r(k-1)$. Many authors will use just the three parameters $(v,k,\lambda)$ to characterize a BIBD.

In your problem, you have $(v,k,\lambda)=(N^2, N, 1)$ which corresponds to the well-known affine plane. Every affine plane is resolvable, i.e., it is possible to partition the $b:=N(N+1)$ blocks in the affine plane into $r:=N+1$ parallel classes (what you're calling "groups"), each class being a partition of the set of points. (In fact the affine plane is considered the classical example of a resolvable BIBD.)

Since every affine plane is resolvable, it's enough for you to generate any old affine plane, and then deduce the resolution by inspection. This may be cheating, but you can find BIBD generators online, for example here.