2
$\begingroup$

Let $k\ge2$. The maximum number of $0$-$1$ (column) vectors of length $2k-1$ which make a rank $k$ matrix with no zero row nor two identical rows is $2^{k-1}+1$. (The rank is over the rationals.)

I have a computer-based proof for this statement, but I'm looking for a computer-free argument.

$\endgroup$
2
$\begingroup$

A construction for the lower bound: take the matrix of rank $k-1$ with $2^{k-1}$ columns consisting of all $\{0,1\}$-combinations of the vectors $e_1+e_2, e_3+e_4 \dots, e_{2k-3}+e_{2k-2}$. Then add the column $e_1+e_3+e_5+\dots+e_{2k-1}$, which will increase the rank by $1$ and make all the rows distinct.

Edit: If the rank was computed over $\mathbb{Z}_2$, the matrix with $2^k$ columns consisting of all $\{0,1\}$-combinations of the $k$ vectors above also has rank $k$ and no zero row or two identical rows:

\begin{pmatrix} 0&1&1&0\\ 0&1&0&1\\ 0&0&1&1 \end{pmatrix}

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.