Trouble choosing an appropriate arXiv category for a paper
This question may be considered too specific for this site, but I'll try an answer anyway.

As someone who works in numerical linear algebra and has used M-matrices extensively, I think a submission with this topic would be welcome in math.NA. Math.RA would be my second choice, followed closely by Math.PR (probablity) which you haven't considered. One of the main results of your paper is an algorithm, and it must be an algorithm which is (at least partly) numerical in nature if it can recognize M-matrices. As you correctly note, M-matrices and algorithms involving them are a first-class citizen in numerical analysis, and they are featured in articles appearing in journals in the field. Even abstract properties of them would be on-topic, because their main use is (probably) going to be proving the properties of algorithms.

I must say that the arguments you list in favor of math.FA and math.RA seem quite vague to me; they would apply to almost all of numerical linear algebra. As for cs.DM, as I said earlier, your algorithm necessarily is not entirely discrete, so it seems less appropriate.

Anyway, you probably won't go wrong with any of NA, RA or PR. Arxiv's categories have some overlap. As Pieter Naaijkens's answer suggests, you may get slightly more visibility from the people in your field if you go for NA.