Here you see an example of symbolic matrix.
Determinant zero Û perfect matching exists (all monomials are different and cannot cancel).
Problem: symbolic determinant is not polynomially computable.
Solution: assign random values to x_ij. What's the probability of finding a zero value for the determinant whilst there exists a perfect matching?