most recent 30 from http://mathoverflow.net 2013-05-24T20:53:19Z http://mathoverflow.net/feeds/question/121028 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/121028/rank-of-a-matrix-with-missing-entries jsliyuan 2013-02-07T00:26:22Z 2013-02-09T05:24:32Z

<p>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}$.</p> <p>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)}$.</p>

http://mathoverflow.net/questions/121028/rank-of-a-matrix-with-missing-entries/121275#121275 Aaron Meyerowitz 2013-02-09T05:24:32Z 2013-02-09T05:24:32Z

<p>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|.$</p>