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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.