2
$\begingroup$

Prove that there exists five matrices $B_i \in \mathbb{F}_2^{5\times 10}$, $i\in \{1,2,3,4,5\}$, such that any two $B_i$'s form an invertible matrix in $\mathbb{F}_2^{10\times 10}$.

I am interested in a proof of existence that could be generalized to matrices with other dimensions.

Follow-up question when there are constraints on the $B_i$'s: Existence of matrices in $\mathbb{F}_2$ with some invertibility properties

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

If $B$, $B'$ are $5\times 10$ matrices of rank $5$ over $\mathbb{F}_2$, the condition that the matrix formed by stacking $B$ on top of $B'$ is invertible is equivalent to the condition that the row span of $B$ and the row span of $B'$ have trivial intersection. The row spans are $5$-dimensional subspaces of $\mathbb{F}_2^{10}$, so given five $5$-dimensional subspaces of $\mathbb{F}_2^{10}$ with pairwise trivial intersection, we can choose bases for them to construct matrices $B_1,\ldots,B_5$.

Note that $\mathbb{F}_2^{10}$ is isomorphic to $\mathbb{F}_{2^5}^2$ as an $\mathbb{F}_2$ vector space. A $1$-dimensional $\mathbb{F}_{2^5}$-subspace of $\mathbb{F}_{2^5}^2$ can be identified with a $5$-dimensional $\mathbb{F}_2$ subspace of $\mathbb{F}_2^{10}$, and every pair of $1$-dimensional $\mathbb{F}_{2^5}$-subpsaces of $\mathbb{F}_{2^5}^2$ have trivial intersection. There are 33 such subspaces, so we can find even find $B_1,\ldots,B_{33}\in\mathbb{F}_2^{5\times 10}$ with the desired property.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ (1) One can make this even more explicit by choosing a basis for $\mathbb F_{2^5}$, letting us write each entry as a $5 \times 5$ matrix, and forming the $5 \times 10$ matrices by stacking two of them on top of each other. (2) One can check that 33 is the optimal number, since $\mathbb F_{2^10}$ contains $2^{10}-1$ nonzero vectors, with $2^5 -1$ in each subspace, so the maximum number of nonintersecting subspaces is at most $2^{10}-1/ (2^5-1)= 2^5+1 =33$. $\endgroup$
    – Will Sawin
    Commented Oct 2, 2021 at 2:41
  • $\begingroup$ @Julian Rosen Can this solution be adapted to this case mathoverflow.net/questions/405296/… where there are some constraints on the structure of the Bi's? $\endgroup$
    – user83947
    Commented Oct 2, 2021 at 4:42

You must log in to answer this question.