7
$\begingroup$

$\DeclareMathOperator\perm{perm}\DeclareMathOperator\diag{diag}$Using MacMahon's master theorem, the properties of complex gaussian integrals, and Cauchy's integral theorem one can show that the permanent of a matrix $A$ satisfies \begin{equation} \perm(A) = \frac{1}{\pi^N} \int_{\mathbb{R}^{2N}} d^N\mathbf{u} \, \exp\Bigl( -\sum_{i=1}^N \mathbf{u}_i^2 \Bigr) \prod_{i=1}^{N} \Bigl(\mathbf{u}_i\cdot\sum_{j=1}^NA_{ij} \mathbf{u}_j\Bigr), \end{equation} where $\mathbf{u}_i \equiv (u_{i1}, u_{i2})$ and $d^{N}\mathbf{u} \equiv \prod^{N}_{i =1}du_{i1} \wedge du_{i2}$.

My guess is that this result is not new, but I'm not familiar with the literature on such identities. Is this identity known? Alternatively, where would be a good place to check for similar such identities?


Proof of Identity

The truth of the identity could be inferred from noting that we need our gaussian to integrate a function where $\mathbf{u}_i$ for each $i$ appears exactly twice.

To prove it directly, we note that MacMahon's master theorem states that the permanent of a matrix $A$ is the $x_1x_2\dotsm x_N$ coefficient of the quantity \begin{equation} \frac{1}{\det(I - XA)}, \end{equation} where $I$ is the $N\times N$ identity matrix and $X \equiv \diag(x_1, x_2, \dotsc, x_N)$. Thus, we have \begin{equation} \perm(A) = \frac{1}{(2\pi i)^N} \oint \left[\prod_{i=1}^{N} \frac{dq_i}{q_i^2} \right] \frac{1}{\det(I- QA)}, \label{eq:perm_def} \end{equation} where $Q = \diag(q_1, q_2, \ldots, q_N)$, $q_i$ is a complex variable, and we are performing $N$ contour integrations in sequence. Defining a set of $N$ two-dimensional vectors $\{\mathbf{u}_i\}$ as $\textbf{u}_i \equiv (u_{i1}, u_{i2})$, we have \begin{equation} \frac{1}{\det(I-QA)} = \frac{1}{\pi^N} \int_{\mathbb{R}^{2N}} d^{N}\mathbf{u}\,\exp\Bigl(- \sum_{i, j=1}^N \mathbf{u}_i \cdot \left(\delta_{ij} - q_{i} A_{ij}\right) \mathbf{u}_{j}\Bigr). \label{eq:gauss_result} \end{equation} Using this determinant expression in MacMahon's theorem and performing the contour integrations yields the stated result.

$\endgroup$
3
  • $\begingroup$ How is it related to MacMahon master theorem? This identity looks pretty straightforward: if we expand the brackets, any term not contributing to the permanent is odd with respect to at least one of variables, thus it disappears after integration. $\endgroup$ Commented Nov 1, 2020 at 18:43
  • $\begingroup$ @Fedor I agree that checking the identity is straightforward, but personally I wouldn't have thought to write it down without the prior derivation. Perhaps, the straightforwardness is a reason it is not in the literature? Though with the well known connection between determinants and gaussian integrals, I would have expected to see some reciprocal connection between permanents and gaussians $\endgroup$ Commented Nov 1, 2020 at 19:45
  • $\begingroup$ Also @ Fedor, I'll write up the explicit connection to MacMahon's master theorem as an addendum to this question. $\endgroup$ Commented Nov 1, 2020 at 19:58

1 Answer 1

3
$\begingroup$

In case anyone from the future comes to this post:

I wasn't able to find relevant literature that answered my question so I wrote a preprint on it (https://arxiv.org/abs/2106.11861). It turns out that the gaussian above is more complicated than necessary. The main result of the paper is a generalization of the identity above:

Let $p_X: \Omega_X \to \mathbb{R}$ be a probability distribution defined over the domain $\Omega_X$ with zero mean and unit variance. Let $A$ be an $n\times n$ matrix with elements $a_{i, j}$. Then the permanent of $A$ is \begin{equation} \text{perm}(A) = \int_{\Omega^n_{X}} d^n\textbf{x}\, \prod_{i=1}^n p_{X}(x_i) \, x_{i} \sum_{j=1}^n a_{i, j} x_j, \label{eq:fund_thm} \end{equation} where $\Omega^n_X = \Omega_X \otimes \cdots \otimes \Omega_X$ is the $n$-factor product over the single-variable domain of integration. In condensed notation, we can write this result as the expectation value \begin{equation} \text{perm}(A) = \left\langle \prod_{i=1}^nx_{i} \sum_{j=1}^n a_{i, j} x_j \right\rangle_{x_i \sim p_X}, \end{equation} where the average is over $\{x_i\}$, a set of independent identically distributed random variables each of which is drawn from $p_X$.

When $p_X = N(0, 1)$, we get something like the equation in the question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.