If $M$ is $ntimes 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. There are $n!$ permutations and $(n-1)!$ complete cycles. So, the probability is $(n-1)!/n!=1/n$.