I hope I understand you correctly: you are trying to find a matrix that optimizes a model for a given set of data. I am led to believe that the matrix you are varying is the full statement of the model and so represents all of the parameters that aren't otherwise fixed by some conditional statement. You choose Metropolis Hastings to sample from the posterior of model space, viz., matrix space. It also follows that there is some likelihood function defined for your data that will be maximized by a good choice of your model matrix. But as usual there is some wiggle room, and M-H will indeed sample the posterior of your model space (space of matrices) based on your data and the likelihood, and reveal all of the wiggle room in the process.
It would be sensible to follow the standard M-H MCMC algorithm by making small/incremental steps in matrix space. If your matrix is positive definite, your small steps should not violate requirement. I suggest gently rescaling your matrix by multiplying it by a diagonal matrix with diagonal elements close to and centered around 1. You will also want to rotate your matrix gently by multiplying it by a randomly selected rotation matrix with a small angle centered at zero. Other options, like flipping the sign of an eigenvalue, are bolder and will help you move around in matrix space a lot fast and go a lot farther, but you may lose some essential matrix property that you should try to hold invariant, like the trace. But I really don't know what problem you are trying to solve, so it really depends on those details.
What should you be looking for? An acceptance ratio of 30-50%. Constancy of whatever invariants you hold dear. A familiar-looking distribution of your data's likelihood values, or perhaps the negative log likelihood, which is usually what you calculate and can interpret most directly (as energy/$k_BT$, for instance, in physics.) And you should make sure that the time-course of parameter values (matrix elements, trace, what-not) has an autocorrelation function with a characteristic decorrelation time much, much less than the duration of your simulation. That is, you should just be looking at all the standard diagnostics of M-H MCMC. The fact that your parameter space constitutes a set of matrix elements doesn't change any of this.