2
$\begingroup$

Let $ a = (a_1,a_2, \ldots,a_{10})\in \{ 0,1\}^{10}$ be a binary vector of length $10$.

Question: Without using a computer-aided method, how to prove that there exists binary vectors $x_{i,j} \in \{ 0,1\}^{10}$, $i\in \{1,2,3,4,5\}$, $j \in \{1,2,3\}$ such that one can recover $a$ from any two rows of the following matrix $M \in \{ 0,1\}^{5 \times 5}$?

$$M:= \begin{bmatrix} x_{1,1}. a & x_{1,2}. a & x_{1,3}. a & a_{1} & a_{2} \\ x_{2,1}. a & x_{2,2}. a & x_{2,3}. a & a_{3} & a_{4} \\ x_{3,1}. a & x_{3,2}. a & x_{3,3}. a & a_{5} & a_{6} \\ x_{4,1}. a & x_{4,2}. a & x_{4,3}. a & a_{7} & a_{8} \\ x_{5,1}. a & x_{5,2}. a & x_{5,3}. a & a_{9} & a_{10} \\ \end{bmatrix},$$ where $x_{i,j}. a$ denotes the scalar product between $x_{i,j}$ and $a$ modulo 2.

Max Alekseyev proved that a solution exists with a computer-aided method. How to prove it analytically instead? I am also interested in the following:

 - Can one determine the number of solutions?
 - Can the problem be solved using MDS codes or polynomial interpolation in finite fields? 
 - If no positive answer can be given to the previous question, is there a method that would be computationally tractable for large matrices?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
+50
$\begingroup$

We can recover $a$ as soon as $\det(X_{i,k})=1$ over the field $\mathbb{F}_2:=\{0,1\}$ for all pairs $i<k$ from $\{1,2,3,4,5\}$, where $X_{i,k}$ is the $6\times 6$ matrix formed by rows $x_{i,j}$ and $x_{k,j}$ for $j\in\{1,2,3\}$ excluding the columns indexed by $2i-1,2i,2k-1,2k$. There are total of $10$ such matrices and equations.

We can notice that some components of $x_{i,j}$ are silent (such as fist two components of $x_{1,j}$, the third and fourth components of $x_{2,j}$, etc.), i.e. they do not appear in any of the equations. Call the other components essential.

We can construct a suitable set of vectors as follows. Let make some of their essential components variable and fill out the others with random elements from $\mathbb{F}_2$ such that all the above equations become linear over the chosen variables. In fact, we can choose as many as $20$ such variables: $(x_{1,1})_t$ for $t\in\{3,4,\dots,10\}$, and $(x_{i,j})_1$ for $i\in\{2,3,4,5\}$ and $j\in\{1,2,3\}$.

It is easy to verify if the resulted system of linear equations has a solution. If it does, we get a required set of vectors; if it does not, then we try a different random filling, and so on.

This approach leads to a solution within a few seconds of computation. One particular solution is $$\begin{split} x_{1,1} &= [. . 0 0 0 0 0 1 1 0] \\ x_{1,2} &= [. . 0 0 0 1 1 1 1 1] \\ x_{1,3} &= [. . 1 1 1 0 1 0 0 0] \\ x_{2,1} &= [1 1 . . 0 0 1 1 1 1] \\ x_{2,2} &= [0 0 . . 1 1 1 1 0 0] \\ x_{2,3} &= [0 1 . . 1 0 1 1 1 1] \\ x_{3,1} &= [1 0 1 0 . . 1 0 1 0] \\ x_{3,2} &= [1 0 1 1 . . 1 1 0 1] \\ x_{3,3} &= [0 1 1 0 . . 0 1 1 1] \\ x_{4,1} &= [1 0 0 1 1 0 . . 1 1] \\ x_{4,2} &= [0 0 1 0 1 0 . . 1 1] \\ x_{4,3} &= [0 0 0 1 1 1 . . 0 1] \\ x_{5,1} &= [0 1 0 1 1 1 0 1 . .] \\ x_{5,2} &= [0 1 1 1 1 0 0 1 . .] \\ x_{5,3} &= [0 1 0 0 1 0 1 0 . .] \end{split} $$ where dots denote the silent components, whose values can be chosen arbitrarily.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ That answers my question so I marked it as a solution. How did you come up with choosing 20 variables? I am also interested in the following questions: Without any computations, can one say that a solution exists? Is there a method that would be computationally tractable for larger matrices? $\endgroup$ Commented Jul 4, 2020 at 0:02
  • 1
    $\begingroup$ I listed which components I chose as variables, and it's easy to verify that they do the job. Essentially they represent the first row and first column of the matrix formed by $x_{i,j}$. As for the need of computation, I do not see how the problem can be approached without computation. The computational method I described can work for larger matrices, although I did not check its range of applicability. $\endgroup$ Commented Jul 4, 2020 at 1:09

You must log in to answer this question.