Skip to main content
7 of 11
added 113 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}}{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}}{2\log_2r}\quad?$$

Turbo
  • 13.9k
  • 1
  • 27
  • 76