Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 124 / 4 / ii

View $M$ as a directed graph with nonnegative integer edge weights. For an edge of weightbuild a binary path-counting gadget with one entrance and one exit and exactly $w$ entrance-to-exit routes. Starting with one route, a constant-size diamond doubles the number of routes; processing the bits from most significant to least significant repeatedly doubles and, when $b_j=1$, adds one bypass route. The gadget has $O(n)$ vertices and only zero-one edges.

Add forced internal edges and self-loops so that a cycle cover not using the simulated edge extends uniquely across the gadget, whereas a cycle cover using it has exactly one extension for each entrance-to-exit route. Replacing every weighted edge therefore multiplies each original cycle cover by precisely the product of its selected edge weights. Summing over covers givesThere are $n^2$ entries and each gadget has $O(n)$ size, so $N$ is constructed in polynomial time.