0
$\begingroup$

Let $\mathscr{M}[n]$ be collection of $n\times n$ matrices with real entries from $\{0,1\}$ such that every row is distinct and every column is distinct.

What is minimum real rank of matrices in $\mathscr{M}[n]$?

Given real rank $r$, then $\mathscr{N}[r]$ be collection of square matrices with real entries from $\{0,1\}$ such that every row is distinct and every column is distinct.

What is largest size of matrix in $\mathscr{N}[r]$?

Is there an algebraic or geometric way to describe these sets?

I know a separation of rank $r$ and size $2^{r/2}\times 2^{r/2}$. Is this the largest?

$M$ be $2^r\times r$ matrix that binary expansion of all integers from $0$ to $2^r-1$.

$J$ be $2^r\times 2^r$ matrix of $1$s.

$0$ be appropriate size matrix of $0$s.

First block row $[0\quad J\quad M]$, second block row $[J\quad 0\quad M]$, third block row $[M'\quad M'\quad 0]$.

Rank is at most $2+2r$ (sum of ranks of blocks).

Instead of $r/2$, can we replace by $r/c$ where $c>1$ is arbitrarily close to $1$ as $r\rightarrow\infty$ or is there a $c$ that is bounded away from $1$?

$\endgroup$
  • $\begingroup$ It is easy to produce rank of 2n/3 and probably less than log(n) for n sufficiently large. Take a "diagonal" subspace of R^n that includes the all ones vector, for example. Gerhard "Many Ways To Lose Weight" Paseman, 2015.06.22 $\endgroup$ – Gerhard Paseman Jun 22 '15 at 22:26
  • $\begingroup$ It's not log(n)? (choose a k-set of columns for the 1's and use the rows corresponding to all possible subsets of the k columns) $\endgroup$ – user71114 Jun 22 '15 at 22:26
  • $\begingroup$ Not obviously, as the matrices are square and both rows and columns have to be distinct. Gerhard "Read The Fine Print, Please" Paseman, 2015.06.22 $\endgroup$ – Gerhard Paseman Jun 22 '15 at 22:27
  • $\begingroup$ I know a separation of rank $r$ and size $2^{r/2}\times 2^{r/2}$. Is this the largest? $\endgroup$ – Brout Jun 22 '15 at 22:29
  • $\begingroup$ I don't know if it is the largest. If you post details in your question, I can think about it and try to improve upon it. Gerhard "Ask Me About Binary Matrices" Paseman, 2015.06.22 $\endgroup$ – Gerhard Paseman Jun 22 '15 at 22:30

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.