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?

```


System of equations - Proof that a solution exists
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.


