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?



Probability permutation in turned to cycle
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$.


