# 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?

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.

• Given that you've tagged this with cr.crypto-security, it would improve the question if you could state how it relates to crypto/security. – Dave Clarke May 1 '11 at 10:53
• Simple observations: Such matrix exists for n≤4. For n≤3, take all permutations. For n=4, the only solutions are taking all even permutations or all odd permutations. – Tsuyoshi Ito May 1 '11 at 11:13
• Thanks, Ito. Actually I came up with the answer when $n \leq 4$ by hand. But things become much more difficult when $n \geq 5$. Exponential explosion occurs. – Cyker May 1 '11 at 11:20
• (1) I think that the problem is related to coding theory and added it as a tag. (2) Another observation: The problem can be stated also as follows. Find a matrix B of size n×(n^2) such that each of the first n columns of B is the n repetitions of the same number and such that B satisfies the condition 2 in the question. If such B exists, then each of the last n(n−1) columns of B must be a permutation. Conversely, any matrix A satisfying the conditions 1 and 2 can be converted to a matrix B by attaching the n stated columns to the left of A. – Tsuyoshi Ito May 1 '11 at 15:22

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).

• Thanks for the detailed analysis, Prof. Shor! So from this reasoning, 1) If there doesn't exist a set of $n - 2$ MOLS, we can assert the original problem is not feasible for $n$. 2) If there exists a set of $n - 1$ MOLS, we can assert the original problem is feasible for $n$. Since when $n$ is a prime power there exists a set of $n - 1$ MOLS, this gives an alternate view of Ito's partial solution. And we have found the original problem is not feasible when $n = 6$. Really admirable! – Cyker May 1 '11 at 18:41
• This is a very nice connection. Thanks for the answer! A minor point: According to Wikipedia, it is known that n−1 orthogonal Latin squares exist for n prime power, not only for n prime. – Tsuyoshi Ito May 2 '11 at 0:41
• @Tsuyoshi - Oops. I knew that; I just said it wrong. The construction comes from finite fields. Thanks for the correction. Fixing it now. – Peter Shor May 2 '11 at 1:18
• I guessed so. :) – Tsuyoshi Ito May 2 '11 at 1:36

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.)

• this looks a lot like MUBs. I think your construction can be used to build $n + 1$ MUBs, in much the same way as the "Unitary operators method using Galois fields" on the MUBs Wikipedia article. Is there a deeper connection between this question and MUBs? – Artem Kaznatcheev May 1 '11 at 16:50
• @Artem: There may be, especially given Peter’s answer connecting this question to orthogonal Latin squares. (Disclaimer: in my non-expert view, orthogonal Latin squares, MUBs, combinatorial designs, unitary designs and SIC-POVMs are almost indistinguishable.) – Tsuyoshi Ito May 1 '11 at 18:12
• Many thanks, Ito! This design looks really beautiful! – Cyker May 1 '11 at 18:45