If $M$ is $n\times n$, the the probability is $1/n$. 

Indeed, by symmetry, the probability in question is the probability that a random permutation of $\{1,\dots,n\}$ is a complete cycle. Here there are $n!$ permutations and $(n-1)!$ complete cycles. So, the probability is $(n-1)!/n!=1/n$.