How to build a N*(N+1) matrix with number in range of 1~N*N and totally distributed?

Question

Assume for a given number N, generated a matrix which has N+1 rows, and each rows has N columns, each columns has N number in range [1, N^2]. And the matrix has this feature: every column has N number, the numbers are totally distributed in other row.

Sorry for that English is not my mother language, I tried my best to describe the problem clearly, If you have better description for this problem, please teach me how to.

For example N = 3, I can build a matrix which has 4 rows and 3 columns, and with number [1, 3^2]. the matrix is:

[1, 2, 3], [4, 5, 6], [7, 8, 9]
[1, 4, 7], [2, 5, 8], [3, 6, 9]
[1, 5, 9], [2, 6, 7], [3, 4, 8]
[1, 6, 8], [2, 4, 9], [3, 5, 7]

In this example, every row has 3 columns, every columns has 3 numbers, and the 3 numbers are distributed in 3 different columns in every other row. Following are use the 2nd row 2nd column ([2,5,8]) as a example. The three number [2,5,8] are in different column in other rows. No other any column has [2,5], [5,8] or [2,8], but every column in other rows has and only has one of them.

[1, 2, 3], [4, 5, 6], [7, 8, 9]

[1, 4, 7], [2, 5, 8], [3, 6, 9]

[1, 5, 9], [2, 6, 7], [3, 4, 8]

[1, 6, 8], [2, 4, 9], [3, 5, 7]

I have found a fast way to build matrix like this when N is a prime number.

But when N is not a prime number, I can only find a exhaustive method. But it's a O((N^(N-1)^N) algorithm. I can build a matrix in 5 seconds when N is 4, but I should take 328 days when N is 5.

This is what I build when N = 4:

[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]
[1, 5, 9, 13], [2, 6, 10, 14], [3, 7, 11, 15], [4, 8, 12, 16]
[1, 6, 11, 16], [2, 5, 12, 15], [3, 8, 9, 14], [4, 7, 10, 13]
[1, 7, 12, 14], [2, 8, 11, 13], [3, 5, 10, 16], [4, 6, 9, 15]
[1, 8, 10, 15], [2, 7, 9, 16], [3, 6, 12, 13], [4, 5, 11, 14]

I want to find out how to build the matrix with N = 100 or other greater number. Can anyone solve this problem?

Following are how I build the matrix when N is prime number. Use example also.

For example N = 3:

1. The first row is alway continuous: [1,2,3],[4,5,6],[7,8,9]
2. For the following rows, I pick a number from the first row with different offset.

Following is my code to how to generate the matrix when N is prime. But I thought there must be other way to generate the matrix when N is not prime.

#!/bin/env python

def main(n):
    data = []
    for i in range(0, n):
        data.append([n*i + x for x in range(0, n)])
    print data # the first row
    offset = 0
    while offset < n:
        row = []
        for i in range(0, n):
            idx = i
            grid = []
            for j in range(0, n):
                grid.append(data[j][idx%n])
                idx += offset # every row I use a different step. It works for prime.
            row.append(grid)
        print row
        offset += 1


if __name__ == '__main__':
    main(7)

Answer 1

Short answer: this is a known and studied problem in the field of combinatorics, and (without wanting to discourage you) seems to be very hard to solve computationally. For N a prime or prime power it's easy to generate examples, once you know how. For N=6 or N=10, it's known that there are no solutions. For many other N (e.g., N=12, N=15, etc.), people have searched, but no-one knows whether there are solutions in general.

Longer answer: What you describe corresponds to a finite affine plane. This is a finite set of "points", together with a finite collection of "lines" (which for simplicity we can think of as being subsets of the set of points), satisfying the following axioms:

1. For any two points, there's a unique line that contains those two points.
2. Given any line L and any point P not on L, there's a unique line M that's parallel to L and goes through (i.e., contains) P. (Here M and L are considered parallel if they have no points in common - i.e., they don't intersect.)
3. There's a configuration of 4 points such that no three are collinear.

To make this correspond to your example: in the 3x3 case, your "points" are the numbers 1 through 9. Your "lines" are the "columns", and each row in your configuration gives a collection of mutually parallel lines.

Axiom 1 above roughly corresponds to your "totally distributed" property; axiom 2 is what lets you organise your "columns" into rows so that each row contains each number exactly once. Axiom 3 isn't all that interesting: it's a non-degeneracy condition designed to exclude degenerate configurations that are permitted under the first two axioms, but otherwise don't have much in common with the non-degenerate cases.

If you start searching, you'll find lots of results for finite projective planes, but fewer for finite affine planes. That's because any affine plane can easily be completed to a projective plane, by adding a line of points at infinity. Conversely, given a finite projective plane, you can remove a line and all the points on it to get an affine plane. So if you can create finite projective planes, you can create finite affine planes, and vice versa.

Here's an example of that completion process starting from the affine plane you have for N=3. You had:

[1, 2, 3], [4, 5, 6], [7, 8, 9]
[1, 4, 7], [2, 5, 8], [3, 6, 9]
[1, 5, 9], [2, 6, 7], [3, 4, 8]
[1, 6, 8], [2, 4, 9], [3, 5, 7]

We add four new points ("points at infinity") which we'll call "A", "B", "C" and "D". Every current line gets a new point (one of these points at infinity) added to it, and we also get one new line, consisting of exactly these new points at infinity. Note that any two lines which were previously parallel (i.e., were in the same row above) have been completed with the same point at infinity, so now we have a very concrete meaning for the oft-heard phrase "two parallel lines meet at infinity". The new structure looks like this:

[1, 2, 3, A], [4, 5, 6, A], [7, 8, 9, A]
[1, 4, 7, B], [2, 5, 8, B], [3, 6, 9, B]
[1, 5, 9, C], [2, 6, 7, C], [3, 4, 8, C]
[1, 6, 8, D], [2, 4, 9, D], [3, 5, 7, D]
[A, B, C, D]

So now we have 13 points, and 13 lines, such that for every pair of distinct points there's a unique line through those two points, and for every pair of distinct lines, those lines intersect in exactly one point. And this beautifully symmetric situation is pretty much exactly what a finite projective plane is (modulo another non-degeneracy condition). In this case, we've just described the (unique up to isomorphism) finite projective plane of order 3.

Here are some known facts about finite projective planes of order n (where the n here corresponds exactly to your N):

• if n is a prime or prime power, there's a finite projective plane of order n; this can be created directly and simply from the finite field of order n, which is what your algorithm already does in the case where n is prime
• there are also finite projective planes that don't arise this way: so-called non-Desarguesian planes. There are three known non-Desarguesian planes of order 9, for example
• there are no finite projective planes of orders 6 or 10 (the latter was proved by a computer search that took ~2000 hours of supercomputer time in the late 1980s)
• it's unknown whether there's a finite projective plane of order 12 (though it's conjectured that there isn't)
• there's no known finite projective plane whose order is not either a prime or a prime power
• some orders (including n=14) can be ruled out directly by the Bruck-Ryser-Chowla theorem

Here's some code that constructs the solution for N=4 directly as the affine plane over the finite field with four elements, which I'll call GF4. First we need an implementation of that field. The one below is perhaps unnecessarily non-obvious, and was chosen for the simplicity of the multiplication operation.

class GF4:
    """
    A quick and dirty implementation of the finite field
    (Galois field) of order 4. Elements are GF4(0), GF4(1),
    GF4(8), GF4(9). This representation was chosen for the
    simplicity of implementation of multiplication.
    """
    def __init__(self, bits):
        self.bits = bits

    def __add__(self, other):
        return GF4(self.bits ^ other.bits)

    __sub__ = __add__  # because we're in characteristic 2

    def __mul__(self, other):
        return GF4(self.bits * other.bits % 55 & 9)

    def __eq__(self, other):
        return self.bits == other.bits

    def __hash__(self):
        return hash(self.bits)

Now we construct the scalars over the field, then use those to create first the collection of all points in the plane (just pairs of scalars), then the collection of all lines in the plane (by enumerating pairs of points):

# Our scalars are all four elements of GF4.
scalars = list(map(GF4, [0, 1, 8, 9]))

# Points are simply pairs of scalars
points = [(x, y) for x in scalars for y in scalars]

# Every pair of nonequal points determines a line.
def line_through(p, q):
    """
    Return a frozenset of all the points on the line through p and q.
    """
    # We want our lines to be hashable, so use a frozenset.
    return frozenset(
        (p[0] + t*(q[0] - p[0]), p[1] + t*(q[1] - p[1]))
        for t in scalars
    )

# Create all lines; every line is created multiple times, so use
# a set to get unique lines.
lines = {line_through(p, q) for p in points for q in points if p != q}

Our points are currently pairs of objects of type GF4; to show the correspondence with your problem, we want to relabel those, replacing the points with integers 1 through 16:

relabel = dict(zip(points, range(1, 17)))
lines = [sorted(map(relabel.get, line)) for line in lines]

We can now print the lines one by one, but to get your rows, we also need to group lines into mutually parallel groups:

def parallel(l, m):
    """Return True if l and m are parallel, else False."""
    return not(set(l) & set(m))

rows = []
while lines:
    l = lines.pop()
    parallel_to_l = {m for m in lines if parallel(m, l)}
    lines -= parallel_to_l
    rows.append(sorted({l} | parallel_to_l))

And now we can print the results, sorting for friendliness:

for row in sorted(rows):
    print(row)

Here's the output; it's essentially identical to the output you computed.

[(1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 16)]
[(1, 5, 9, 13), (2, 6, 10, 14), (3, 7, 11, 15), (4, 8, 12, 16)]
[(1, 6, 11, 16), (2, 5, 12, 15), (3, 8, 9, 14), (4, 7, 10, 13)]
[(1, 7, 12, 14), (2, 8, 11, 13), (3, 5, 10, 16), (4, 6, 9, 15)]
[(1, 8, 10, 15), (2, 7, 9, 16), (3, 6, 12, 13), (4, 5, 11, 14)]