The determinant can be written as follows. Where  (1j ) is the matrix obtained from  by removing row 1 and column I.
The quantity x_1j det Â(1j ) is an even multiple of 2^c* if x_ij is not in the optimal matching
and an odd multiple if x_ij is (under assumption of unicity). Just matter of testing all values.