Skip to main content
4 of 11
deleted 94 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$.

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

$$\mathsf{\mbox{Is }}\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)\rightarrow1?$$

Turbo
  • 13.9k
  • 1
  • 27
  • 76