Skip to main content
8 of 11
added 24 characters in body
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Probabilistic statement on matrix ranks

Given $A\in\{0,1\}^{n\times n}$ with $rank(A)=r=2^{O(\sqrt{\log_2n})}$.

Denote $\mathsf{1_n}\in\{0,1\}^n$ as vector with $1$s.

Does $$\lim_{n\rightarrow\infty}\mathsf{P_{A\in\{0,1\}^{n\times n}}}\Bigg(\mathsf{1_n}'A\mathsf{1_n}>\frac{(r-1)r^{(\log_2r)^c}}{2\log_2r}\Bigg)=1\quad?$$

Infact is there a matrix (family) such that $$\mathsf{1_n}'A\mathsf{1_n}<\frac{(r-1)r^{(\log_2r)^c}}{2\log_2r}\quad?$$

$c>1$ fixed.

Turbo
  • 13.9k
  • 1
  • 27
  • 76