Ryser, Glynn, and the discrete Fourier transform: orthogonal schemes for the permanent
The permanent of an $n \times n$ matrix is the coefficient of the fully mixed monomial $x_0 \cdots x_{n-1}$ in the product of its row forms $\prod_i\bigl(\sum_j b_{ij} x_j\bigr)$, and the classical exact algorithms of Ryser and Glynn compute it by summing $2^{n-1}$ evaluations of that product over the Boolean cube. We recast this as a single principle -- an evaluation scheme together with an orthogonality criterion that decides, in one line, whether its weighted sum equals the permanent -- and show that Ryser's formula, Glynn's formula, and a discrete Fourier transform are three instances of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.09949
curl -X POST /api/v1/records/arxiv/2607.09949/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.09949/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'