Solvability of matrix filling

Question

Matrix $A$ has dimension $n \times n(n-1)$. We want to fill $A$ using integers between $1$ and $n$, inclusive.

Requirements:

1. Each column of $A$ is a permutation of $1, \dots, n$.
2. Any submatrix formed by two rows of $A$ cannot have identical columns.

Question:

Is it possible to fill the matrix satisfying the requirements?

Relation to cryptography:

Each row number corresponds to a plaintext. Each column corresponds to a key. Since a key defines an injection, each column must be a permutation. The second requirement is for perfect secrecy for two messages.

Answer 1

Tsuyoshi, great observation in your comment! I think this nearly solves the problem.

Consider the following two questions

1. Do there exist $k$ rows of length $n(n-1)$ so that no number appears twice in any column, and for each pair of rows all ordered pairs given by the columns are distinct?
2. Do there exist $k$ rows of length $n^2$ so that for each pair of rows, all ordered pairs given by the columns are distinct?

Tsuyoshi's observation in his comment shows that if you can achieve some value $k$ for question (1), you can achieve the same value $k$ for question (2). We now show that if we can achieve some value $k$ for question (2), we can achieve the value $k-1$ for question (1). Thus, the answer to these two questions are nearly the same.

The construction goes as follows: Ignore the first row, except put all the $1$'s in the first $n$ positions. You can now apply a permutation of the values $\lbrace 1, 2, \ldots, n \rbrace$ to each of the $k-1$ remaining rows so that, except for the first entry, each of the first $n$ columns contains identical values, and by Tsuyoshi's observation in the comment, this gives you a set of $k-1$ rows satisfying your condition.

Now, if you have a set of $k$ rows of length $n^2$ with every pair of rows containing all ordered pairs in each column, then this is equivalent to a set of $k-2$ orthogonal Latin squares. Each of the rows $3$, $4$, $\ldots$, $k$ gives a Latin square. To get the Latin square associated with row $j$, put the value in the $i$'th column of row $j$ in the cell whose coordinates are given by the ordered pair in the $i$'th column in the first two rows.

If $n$ is not a prime power, how many mutually orthogonal Latin squares of order $n$ exist is a famous open problem, and I do not believe any set of $n-2$ orthogonal Latin squares is known to exist for $n$ not a prime power; the general consensus is that such sets do not exist. The only result proven so far is that such a set does not exist for $n=6$. What is known is that the number $k$ of possible rows grows at least as $k=\Omega(n^c)$ for some $c$. I believe whether there are 8 orthogonal Latin squares of order 10 is still open. (It is known that there are not 9, but because of the possible difference of $1$ in the answer to the two questions, this doesn't tell us anything about the original problem.)

For $n=6$, the maximum $k$ you can get is 3, and it turns out you can obtain three rows for problem (1) by looking at any $6\times 6$ Latin square with a transversal, of which there are many non-equivalent examples. For $n=10$, there are known constructions giving two orthogonal Latin squares. If these squares have a common transversal, then you can get $k=4$ for problem (1).

Answer 2

This is a partial solution. Such a matrix exists if n is a prime power.

Let F be the finite field of order n. We construct an n×n(n−1) matrix whose rows are labeled by F, whose columns are labeled by (F∖{0})×F, and whose entries are in F as follows: the i-th row of the column labeled (a, b) is given by ai+b. In words, each column corresponds to a degree-one polynomial in F. Then each column contains each element of F exactly once, and no two columns have equal entries in more than one row because the values of two distinct degree-one polynomials can coincide at at most one point.

(If you want a matrix whose entries are in {1,…,n} instead of in F, replace the elements of F with {1,…,n} arbitrarily.)