v cannot have negative entries. It appears that are you are forgetting the signs in the formula for the adjugate.

v is guaranteed to exist and be a valid probability vector as long as M is an irreducible Markov matrix (that is, any state can eventually be reached from any other state). An equivalent and intuitively easier way to calculate v is by repeatedly squaring M: when you do this, all rows of M^k converge to v. This is a consequence of the fact that v is an equilibrium state, i.e., the probability distribution you end up with if you let the Markov chain run forever (from any starting state).