<p>This is a partial solution.  Such a matrix exists if <i>n</i> is a prime power.</p>

<p>Let <i>F</i> be the finite field of order <i>n</i>.  We construct an <i>n</i>×<i>n</i>(<i>n</i>−1) matrix whose rows are labeled by <i>F</i>, whose columns are labeled by (<i>F</i>∖{0})×<i>F</i>, and whose entries are in <i>F</i> as follows: the <i>i</i>-th row of the column labeled (<i>a</i>, <i>b</i>) is given by <i>ai</i>+<i>b</i>.  In words, each column corresponds to a degree-one polynomial in <i>F</i>.  Then each column contains each element of <i>F</i> 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.</p>

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

CC BY-SA 3.0
2011-05-01T16:50:28.517Z
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](http://en.wikipedia.org/wiki/Mutually_unbiased_bases). Is there a deeper connection between this question and MUBs?
Artem Kaznatcheev
CC BY-SA 3.0
2011-05-01T18:12:29.460Z
@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
CC BY-SA 3.0
2011-05-01T18:45:50.680Z
Many thanks, Ito! This design looks really beautiful!
Cyker
CC BY-SA 3.0
2011-05-01T11:24:52.793Z
2011-05-01T13:10:13.260Z
2011-05-01T13:10:13.260Z
Tsuyoshi Ito
<p>Tsuyoshi, great observation in your comment! I think this nearly solves the problem.</p>

<p>Consider the following two questions</p>

<ol>
<li>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?</li>
<li>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?</li>
</ol>

<p>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.</p>

<p>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. </p>

<p>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$ <a href="http://en.wikipedia.org/wiki/Graeco-Latin_square#Mutually_orthogonal_Latin_squares" rel="nofollow">orthogonal Latin squares</a>. 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. </p>

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

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

CC BY-SA 3.0
2011-05-01T18:41:52.680Z
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
CC BY-SA 3.0
2011-05-02T00:41:54.263Z
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
CC BY-SA 3.0
2011-05-02T01:18:43.040Z
@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 
CC BY-SA 3.0
2011-05-02T01:36:10.367Z
I guessed so. :)
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-01T16:00:31.437Z
2011-05-02T01:06:35.957Z
2011-05-02T01:06:35.957Z
Peter Shor 
<p>Matrix $A$ has dimension $n \times n(n-1)$. We want to fill $A$ using integers between $1$ and $n$, inclusive.</p>

<p>Requirements:</p>

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

<p>Question:</p>

<p>Is it possible to fill the matrix satisfying the requirements?</p>

<p>Relation to cryptography:</p>

<p>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.</p>

CC BY-SA 3.0
2011-05-01T10:53:46.577Z
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
CC BY-SA 3.0
2011-05-01T11:13:13.470Z
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
CC BY-SA 3.0
2011-05-01T11:20:23.153Z
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
CC BY-SA 3.0
2011-05-01T15:22:02.347Z
(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
<co.combinatorics><cr.crypto-security><coding-theory>
Solvability of matrix filling
Cyker
# Solvability of matrix filling

(Asked by: username_0 on 2011-05-01)

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.

**Tags:** co.combinatorics, cr.crypto-security, coding-theory

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_2**: (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.  

---

## 2 answers

### Answer by username_4 on 2011-05-01. Score: 11 | Accepted answer

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](http://en.wikipedia.org/wiki/Graeco-Latin_square#Mutually_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).

> **Comments:**
> **username_0**: 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!  
> **username_2**: 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.  
> **username_4**: @Tsuyoshi - Oops. I knew that; I just said it wrong. The construction comes from finite fields. Thanks for the correction. Fixing it now.  
> **username_2**: I guessed so. :)  

---

### Answer by username_2 on 2011-05-01. Score: 11

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

> **Comments:**
> **username_3**: 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](http://en.wikipedia.org/wiki/Mutually_unbiased_bases). Is there a deeper connection between this question and MUBs?  
> **username_2**: @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.)  
> **username_0**: Many thanks, Ito! This design looks really beautiful!  

---

