2
$\begingroup$

Consider a $N\times N$ random matrix $A=[A_{ij}]$, whose elements are independently randomly chosen from the binary field $\mathbb{F}_2=\{0,1\}$ with probabilities $p_0=p$ and $p_1=1-p$. Suppose that we are allowed for rows and columns reordering on $A$ to transform it to the form $$ A = \left[\begin{array}{cc}L & A_1\\ A_2 & A_3\end{array}\right] $$ where $L$ is a lower triangular sub-matrix. My question is: is that possible to determine the expected size of the largest $L$ (as a function of $N$ and $p$)? Can anyone point me to some references if there is any. Thanks sincerely.

$\endgroup$

1 Answer 1

3
$\begingroup$

A reasonable first estimate is $\ell$ (the size of $L$) is approximately $4\log n/|\log p|$.

To get this, consider choosing a sequence of $k$ rows $i_1,\ldots,i_k$ and $k$ columns, $j_1,\ldots j_k$. There are $n!/(n-k)!\approx n^k$ ways of choosing the $i$'s and the same number of ways of choosing the $j$'s. There are therefore approximately $n^{2k}$ choices of a sequence of $k$ rows and a sequence of $k$ columns.

For each choice $(I,J)$, you look at the submatrix $L^{(I,J)}$ with entries $L_{a,b}=A_{i_a,j_b}$. This is lower triangular precisely when $A_{i_a,j_b}=0$ for each $b>a$. For a fixed choice $(I,J)$, the probability that $L^{(I,J)}$ is lower triangular is $p^{k(k-1)/2}$. Hence the expected number (using linearity of expectation) of choices of $(I,J)$ such that $L^{(I,J)}$ is lower triangular is approximately $n^{2k}p^{k(k-1)}/2$.

Since there is enough independence around, you expect a lower triangular submatrix of size $k$ when $n^{2k}p^{k(k-1)/2}>1$. Taking logs, you obtain the bound $k>4\log n/|\log p|$.

A good reference for this kind of argument is the book "The Probabilistic Method" by Alon and Spencer.

$\endgroup$
2
  • $\begingroup$ Anthony, few remarks. i) For your first approximation, you assume $k/n$ is small. ii) The last inequality is $k<4\log(n)/|\log(p)|+1$. iii) About your "Since there is enough independence around": a choice $(I,J)$ means, in particular, a choice of the orderings of $I,J$. Then if you keep the sets $I,J$ and change only the orderings, you are far from independence, except again, if $k/n$ is very small, that is, if $p$ is small. $\endgroup$
    – loup blanc
    Feb 8, 2014 at 13:19
  • $\begingroup$ I interpreted the question as being about the large $N$ / fixed $p$ limit. Similar problems with dependence arise if you try and find the largest clique in a random graph, but there (as shown in Alon+Spencer), even though many of the same edges are used, there's enough independence to make the 2nd moment method work. $\endgroup$ Feb 8, 2014 at 17:02

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.