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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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$
    – Jan-Christoph Schlage-Puchta
    Commented Feb 4, 2015 at 16:28
  • $\begingroup$ Is there a way to quantify number of matrices which do not fit pattern? $\endgroup$
    – Turbo
    Commented Feb 10, 2015 at 11:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .