For what size of `M` should this work? In general computing determinants for solving linear systems is much to expensive.
Even for sparse matrices there are well known efficient (fraction free) gauss elimination algorithms:
http://dl.acm.org/citation.cfm?id=219918