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

 A: 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.
