Assume that we have $2k$ matrices $S_1,\ldots,S_k$ and $\Phi_1,\ldots,\Phi_k$ over some finite field $F$ such that

(i) $S_i\in F^{l/2\times l}$ and $\dim S_i=l/2$ for any $i\in\{1,\ldots,k\}$;

(ii) $\Phi_i\in F^{l\times l}$ and $\dim \Phi=l$ for any $i\in\{1,\ldots,k\}$;

If we further view a matrix as the subspace spanned by its rows, the following conditions must hold

(iii) $S_i\cap S_i\Phi_i=\{0\}$ for any $i\in\{1,\ldots,k\}$ (i.e. the intersection of the spaces spanned by the rows of $S_i$ and $S_i\Phi_i$ is trivial);

(iv) $S_i\approx S_i\Phi_j$ for every $i\neq j$ and $i,j\in\{1,\ldots,k\}$ (i.e. the spaces spanned by the rows of $S_i$ and $S_i\Phi_j$ are the same).

The question is, what is the maximum $k$ such that these $2k$ matrices must exist? This problem looks like some Bollobas-type problem in extremal set theory but they are very different. There are constructions showing that $k=\Omega(\log l)$ and using linear algebra (by constructing linearly independent matrices in $F^{l\times l}$, e.g. one can show $\Phi_1,\ldots,\Phi_k$ are linearly independent and one can construct as many as $\Omega(2^{k/\log l}$) linearly independent matrices by taking multiplications of the $\Phi_i$'s) one can show $k=O(\log^2 l)$.

I find that these constraints can be naturally expressed by exterior algebra, so I want to find a new proof (perhaps with better result) using exterior algebra. Do you have any idea?

  • 1
    $\begingroup$ What is a dimension of a matrix? $\endgroup$ – Fedor Petrov Sep 13 '17 at 20:24
  • $\begingroup$ oh, I mean the rank $\endgroup$ – SGC Sep 14 '17 at 7:49

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.