1
$\begingroup$

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

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\geq1$ fixed.

$\endgroup$

1 Answer 1

1
$\begingroup$

Consider the set of $n\times n$-matrices with entries in $\{0,1\}$ which have at most $r$ distinct rows. The number of such matrices is $2^{rn}r^n$. As long as $n$ and $n-r$ tend to infinity, we have that such a matrix almost surely has rank $r$, and contains close to $n^2/2$ entries equal to 1.

Next the number of $n\times n$-matrices with all entries 0 with $N$ exceptions is $\binom{n^2}{N}\leq n^{2N}$. Hence the probability that a random matrix with rank $r$ has at most $N$ entries 1 is bounded above by $(1+o(1))\frac{n^{2N}}{2^{rn}r^n}$, which tends to 0 provided that $N\leq\frac{rn\log 2}{2\log n}$. We obtain that almost all random matrices with rank $r$ have more than $\frac{rn\log 2}{2\log n}$ entries equal to 1.

For the second question just take diagonal matrices.

$\endgroup$
3
  • $\begingroup$ You are saying that: $$\forall r>0,c>0\exists n\in \Bbb N, A\in\{0,1\}^{n\times n}\mbox{ with }rank(A)=r: \frac{n}{2\log_2n}\ll\frac{r^{({\log_2r})^c}}{2\log_2r}?$$ This gives: $$1_n'A1_n<\frac{rn}{2\log_2n}\ll\frac{(r-1)r^{({\log_2r})^c}}{2\log_2r}?$$ $\endgroup$
    – Turbo
    Jan 29, 2015 at 20:01
  • 1
    $\begingroup$ For all $r$ in the range given we have $\frac{rn}{2\log_2 n}>\frac{r^{\log_2^c r}}{2\log_2 r}$, so almost all rank $r$-matrices with entries in $\{0,1\}$ satisfy $1'_nA1_n >\frac{rn}{2\log_2 n}>\frac{r^{\log_2^c r}}{2\log_2 r}$. $\endgroup$ Feb 4, 2015 at 16:28
  • $\begingroup$ Is there a way to quantify number of matrices which do not fit pattern? $\endgroup$
    – Turbo
    Feb 10, 2015 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.