I added the "probability" tag (although it doesn't have to do anything with the solution) as Markov chain convergence was the motivation. A convergence criterion is "no zeroes in some power of M", where M is the transition matrix.               
Let's drop the condition that the rows sum to 1 and just insist that all elements of M are zero or positive. (Uhm, can the number of zeroes increase when going from a lower to a higher power of M?) Assume there is one finite m such that the m-th power of M (and thus all higher ones) have no zeroes. How is the maximum attainable m related to the size of M? Using        
"M(i,i+1)=M(1,1)=M(1,n)=1,else M(i,j)=0"             
I got m=6,12,18 for n=4,7,10. So m=2n-2?