Determine the expected size of a lower triangular sub-matrix of a random matrix?

Question

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.

Answer 1

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.