Permute a sparse random matrix to resemble a diagonal matrix as much as possible

Question

Say we generate an $N \times N$ sparse random matrix $W$, where each element $W_{ij}$ was independently chosen to be $1$ with probability $p=\frac{a}{N}$, and $0$ with probability $1-p$. We are interested in the case where $N \rightarrow \infty$.

I wonder what happens if we permute the rows and the columns of $W$ so that the non-zero entries are moved as close as possible to the diagonal of the matrix. My intuition is that, if $a=1$ and $N \rightarrow \infty$, we can find a permuted version of the matrix that is exactly an identity matrix with high probability (perhaps with probability 1). Expanding on this intuition, if $a>1$, we will get a permuted matrix that has a band of width $a$ along the diagonal of the matrix. Is this intuition correct? How do I prove/disprove this?

Answer 1

When $a=1$, the probability to get a permutation matrix is $$N! \left(\frac{1}{N}\right)^N \left(1-\frac{1}{N}\right)^{N^2-N} < \frac{N!}{N^N}e^{-(N-1)} < \sqrt{2\pi N}\,e^{-2N + 1 + \frac1{12N}}.$$ So, it's not high, but rather tends to 0 exponentially.