Skip to main content
5 of 11
deleted 18 characters in body
Denis Serre
  • 52.3k
  • 10
  • 146
  • 300

Probabilistic statement on matrix ranks

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

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?$$

Turbo
  • 13.9k
  • 1
  • 27
  • 76