11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Dave Clarke May 1 '11 at 10:53
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito May 1 '11 at 11:13
  • $\begingroup$ 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. $\endgroup$ – Cyker May 1 '11 at 11:20
  • 3
    $\begingroup$ (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. $\endgroup$ – Tsuyoshi Ito May 1 '11 at 15:22
11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Cyker May 1 '11 at 18:41
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito May 2 '11 at 0:41
  • $\begingroup$ @Tsuyoshi - Oops. I knew that; I just said it wrong. The construction comes from finite fields. Thanks for the correction. Fixing it now. $\endgroup$ – Peter Shor May 2 '11 at 1:18
  • $\begingroup$ I guessed so. :) $\endgroup$ – Tsuyoshi Ito May 2 '11 at 1:36
11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Artem Kaznatcheev May 1 '11 at 16:50
  • $\begingroup$ @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.) $\endgroup$ – Tsuyoshi Ito May 1 '11 at 18:12
  • $\begingroup$ Many thanks, Ito! This design looks really beautiful! $\endgroup$ – Cyker May 1 '11 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.