MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Rank of a matrix with missing entries

Let $M$ be a $2^n \times 2^n$ matrix over real number field, where the rows and columns are indexed by subsets of $[n] := {1,2,\ldots,n}$, and defined as follows, $M_{A, B} = 1$ if $A \subseteq B$; $M_{A, B} = -1$ if $B \subsetneq A$; $M_{A, B}$ can take arbitrary value over $\mathbb{R}$.

In words, $M$ is a matrix with some missing entries. Is there some result lower bounds the rank of matrix $M$, for example, $rk(M) \ge n^{\Omega(\log n)}$.

-
 What does "undefined" mean? Do you need the lower bound for all matrices with some prescribed values? – Ilya Bogdanov Feb 7 at 15:16 "undefined" = could take any value. Lower bound means the lower bound for all such matrices – jsliyuan Feb 8 at 0:43 Do you have constructions that allow reducing the rank so much?? – suVRit Feb 8 at 3:57 (it seems to be easy to reduce the rank $2^{n/2}$, but one needs something more clever to reduce it even further...) – suVRit Feb 8 at 4:00 I think I have constructions achieving this bound. But I don't know how to prove the lower bound. – jsliyuan Feb 8 at 7:26

Amazingly (to me) the rank can be as low as $n$. Simply define $M_{A,B}=1$ when $|A| \le |B|$ and $M_{A,B}=-1$ when $|A| \gt |B|.$ This is consistent with the previous requirements and makes the $A$ row depend only on $|A|.$