Let $M$ be a $0/1$ square matrix having one $1$ per row and column (permutation matrix).
If you permute the columns and rows independently what is the probability resulting permutation matrix is a complete cycle?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ See en.wikipedia.org/wiki/… $\endgroup$– Max AlekseyevCommented Jun 8, 2021 at 12:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
If $M$ is $n\times n$, the probability is $1/n$.
Indeed, by symmetry, the probability in question is the probability that a random permutation of $[n]:=\{1,\dots,n\}$ is a complete cycle: If the $(i,j)$-entry of $M$ is $M_{i,j}=1(j=\pi(i))$ for some permutation $\pi$ of $[n]$ and all $i,j$ in $[n]$, then after applying random permutations $\rho$ and $\sigma$ to the rows and columns of $M$, respectively, the $(i,j)$-entry of the resulting random permutation matrix will be $$1(\sigma(j)=\pi(\rho(i)))=1(j=(\sigma^{-1}\circ\pi\circ\rho)(i))),$$ and, by symmetry, all values of the random permutation $\sigma^{-1}\circ\pi\circ\rho$ are equally probable.
There are $n!$ permutations of $[n]$. Of these $n!$ permutations, $(n-1)!$ are complete cycles (indeed, to construct any cycle, we can set $1$ in the first position, and then put $2,\dots,n$ in any order). So, the probability in question is $(n-1)!/n!=1/n$.
answered Jun 7, 2021 at 18:10
-
$\begingroup$ I see and so we require $\#\mbox{random column permutations}\times\#\mbox{random row permutations}=n^\alpha\times n^\beta$ where $\alpha+\beta\geq1$ to get probability at least $\frac{1}{O(1)}$? $\endgroup$– TurboCommented Jun 7, 2021 at 18:15