1
$\begingroup$

All the matrices in this statement are in the field $\mathbb{F}_2$. Let $I$ be the identity matrix of size $10 \times 10$ and let $e_1$, $e_2$, $\ldots$, $e_{10}$ denote its rows. For $i\in \{1,5 \}$, define the $2 \times 10$ matrix $A_{i} = \left( \begin{matrix} e_{2i-1} \\ e_{2i}\end{matrix} \right)$.

Without a computer-aided method, can one prove that there exist five matrices $X_i$, $i\in\{1,5\}$, with size $ 3 \times 10$ such that $ \forall i\in \{1,5\},\forall j\in \{1,5\}\backslash\{i\}, \left( \begin{matrix} X_i \\ X_j \\ A_i \\A_j \end{matrix}\right) $ is a $10\times 10 $ invertible matrix?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You may set the rows of $X_i$ to be $e_{2i-1-k}+e_{2i+k}$, for $k=1,2,3$. Due to symmetry, there are only two cases to check, and both work.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ It should be mentioned that indices are cyclic. With this provision, there is a computer check via the following MATLAB snippet: I = gf(eye(10)); A = []; X = []; for i = 1:5, A{i} = I([2*i-1,2*i],:); ind0 = mod(2*i-1-(1:3)-1,10)+1; ind1 = mod(2*i+(1:3)-1,10)+1; X{i} = I(ind0,:)+I(ind1,:); end; r = nan(5); for i = 1:5, for j = 1:5 r(i,j) = rank([X{i};X{j};A{i};A{j}]); end, end; assert(isequal(r+5*eye(5),10*ones(5)),'oops'); $\endgroup$
    – Steve Huntsman
    Mar 18, 2021 at 13:34
  • $\begingroup$ @Ilya Bogdanov How did you come up with this solution? For instance, I see that it makes sense that the $2(i-1)+1$-th and $2i$-th columns of $X_i$ can be set to zero (because $X_i$ is always considered with $A_i$), and that among the five $j$-th columns of the $X_i$'s only three need to be non-zero (because we consider two $X_i$'s and the corresponding $A_i$'s). Which other constraints or other reasonings did you use? $\endgroup$
    – user83947
    Mar 19, 2021 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.