Computing the permanent of (some) complex matrices (Q285430)

The author describes an algorithm for computing the permanent of an \(n\times n\) real or complex matrix \(A\). The idea of the presented approach is the following: The function \(f(z) = \ln \mathrm{per} (J + z(A-J))\), where \(J\) denotes an \(n \times n\) matrix in which all entries are equal to one, is considered. For this function \(f(1) = \ln \mathrm{per} A\) holds. Then, \(f(1)\) is approximated by a Taylor polynomial expansion of \(f\) at \(z = 0\). An algorithm for computing this Taylor expansion is described and analysed. It is shown that the permanent can be computed for a matrix \(A = (a_{ij})\) with \(| a_{ij} - 1| \leq 0.19\) for all \(i\) and \(j\) and for any relative error \(\varepsilon \in (0,1)\) in \(n^{O(\ln n - \ln \varepsilon)}\) time. This means that for the approximation \(\alpha\) of \(\mathrm{per} A\) the relation \(\mathrm{per} A = \alpha(1+ \rho)\) with \(| \rho | <\varepsilon\) holds. Finally, it is discussed how the presented method can be extended to the computation of hafnians and multidimensional permanents.