Solvability of matrix filling

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?

-
I think you forgot to divide the number of columns by 2. – Phira May 1 '11 at 12:13
No. It is meant to be a permutation, not a combination. – cyker May 1 '11 at 12:30
Sorry for the misreading of the problem. It would suffice to have $A$ populated by $n-1$ mutually orthogonal latin squares (columns side by side). Such designs are known to exist for prime powers n, and it is conjectured but not proven that for only such values will a complete set of MOLS exist. I'm not sure if the stated requirements are weaker than this; it seems close. – hardmath May 1 '11 at 12:45
@cyk Right, sorry. – Phira May 1 '11 at 13:26
@cyk Have you looked at small examples? For $n=1,2,3,4$ there is essentially a single choice. Do you know if this situation continues? – Phira May 1 '11 at 19:09

The requirements are equivalent to a set of $n-1$ mutually orthogonal latin squares (MOLS) of size $n$ by $n$, something that is known to exist for prime powers $n$ and conjectured to exist only in that case. A construction of such complete sets of MOLS makes use of finite fields, from which the apparent restriction to prime powers arises naturally as the order of a finite field.

Assume that the symbol set is $\{1,...,n\}$.

A pair of $n$ by $n$ latin squares are said to be mutually orthogonal iff any ordered pair of symbols $(i,j)$ occurs once and only once as entries in the same row and same column respectively of the first and second such latin squares.

The existence of a set of R mutually orthogonal latin squares of order $n$ is known to be equivalent to that of an orthogonal array of degree R+2, strength 2, and index 1 over an alphabet of size $n$. That is, an array of $n^2$ rows and R+2 columns such that any ordered pair of symbols appears exactly once in any given pair of columns.

Given an orthogonal array $M$ with $n^2$ rows and $n+1$ columns corresponding to a complete set of MOLS as above, we can construct matrix $A$ satisfying the problem requirements (1) and (2) as follows. By sorting the rows of $M$ (which does not alter its status as an orthogonal array) we can arrange that the first two columns have entries:

$$(1,1),(1,2),...,(1,n),(2,1),(2,2),....,(n,n)$$

Furthermore by applying a permutation to the symbol set of each remaining column, another symmetry that does not alter its being an orthogonal array, we can arrange WLOG that the first $n$ rows of $M$ have, after the initial entry 1 in the first column, entries in the second through last column that agree, i.e. $(1,k,...,k)$ for the k'th row, $1 \le k \le n$. We shall hereafter refer only to this "reduced" form of the orthogonal array $M$.

To obtain matrix $A$ we now remove the first column and the first $n$ rows and take the transpose of what remains, so that evidently $A$ consists of $n$ rows and $n(n-1)$ columns.

To see that $A$ satisfies (1), each column is a permutation of the symbol set, it suffices to note that all the entries are distinct. For if there were equality between two entries, this would amount to a duplication of the same equality between two entries of a corresponding row of $M$. However equality of entries in a row of $M$ occurs only in the first $n$ rows, which were removed when forming $A$. Thus (1) is established.

For property (2) of $A$, that now two rows of $A$ repeat the same column pairing, we note that this is directly inherited from the construction from orthogonal array $M$, since the pairs that arise from two rows of $A$ are precisely the $n(n-1)$ unequal pairs that arise from taking the corresponding columns of $M$ after the first $n$ rows, containing the $n$ equal pairs, are removed. So these $n(n-1)$ columns of any two rows of $A$ are necessarily all distinct.

This construction can also be made to work in reverse, so that the availability of $A$ is that such fillings are constructed for prime powers $n$ using finite field techniques linked above, and that apart from these there are no other known solutions (the Prime Power Conjecture being that there are no other solutions).

-

Do you mean none of the possible $\binom{n}{2}$ submatrices each with size $2 \times n(n-1)$ should have no identical columns? It seems to me this should be quite easy to do. What exactly is the motivation vis a vis cryptography?

-
Yes. It's meant to extract $n(n-1)$ 'mutual-exclusive' permutations from all the $n!$ permutations. But I haven't come up with an algorithm to do so. Each column can be viewed as a key which defines a mapping. Each row number is a plaintext. $A_{ij}$'s are ciphertexts. – cyker May 1 '11 at 11:11