# 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|.$
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9819857478141785, "perplexity": 303.3124789211287}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-11/segments/1424936462577.56/warc/CC-MAIN-20150226074102-00251-ip-10-28-5-156.ec2.internal.warc.gz"}