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=1p$. 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 submatrix. 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.
1 Answer
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!/(nk)!\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(k1)/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(k1)}/2$.
Since there is enough independence around, you expect a lower triangular submatrix of size $k$ when $n^{2k}p^{k(k1)/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.

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