# 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 '13 at 15:16
"undefined" = could take any value. Lower bound means the lower bound for all such matrices – jsliyuan Feb 8 '13 at 0:43
Do you have constructions that allow reducing the rank so much?? – Suvrit Feb 8 '13 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 '13 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 '13 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|.$