## Rank of a matrix with missing entries

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?? – S. Sra 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...) – S. Sra 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

## 1 Answer

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": 20, "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}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9145463109016418, "perplexity_flag": "head"}