Permanent of distorted matrix

Question

Let $J$ be all $1$ matrix. Suppose permanent of $M$ is $p$ and $a\in\Bbb Z$. Is there a closed formula or at least a faster than Ryser's technique to find $Permanent(M+aJ)$?

Answer 1

Say $M$ is $n \times n$. For $1 \leq k \leq n$, let $P_k(M)$ be the sum of all of the permanents of $k \times k$ minors of $M$; and let $P_0(M) = 1$. For example $P_n(M)$ is the permanent of $M$, which you denoted $p$ in your question. Then we have $$ \operatorname{permanent}(M+aJ) = \sum_{k=0}^n (n-k)! a^{n-k} P_k(M). $$ (Note that $(n-k)! a^{n-k}$ is the permanent of the $(n-k) \times (n-k)$ matrix with all entries $a$.)

Why is this? Consider one of the terms in the naive expansion of the permanent. It is a product of entries of the form $m_{ij}+a$. The expansion of this product is a sum of terms which are products of some $m_{ij}$ entries and some $a$ entries. The $a$ entries come from rows and columns complementary to the locations of $m_{ij}$ entries. Perhaps a better way to say this is that we have a product of some $m_{ij}$s, corresponding to one of the terms in the (naive) expansion of the permanent of a minor of $M$, multiplied with some $a$s, corresponding to one of the terms in the (naive) expansion of the permanent of the complementary minor of $J$.

For example, if $M = \begin{pmatrix} x & y \\ z & w \end{pmatrix}$, then $P_2(M) = xw + yz$, $P_1(M) = x+y+z+w$, and $$ \begin{split} \operatorname{permanent}\begin{pmatrix} x+a & y+a \\ z+a & w+a \end{pmatrix} &= (x+a)(w+a) + (y+a)(z+a) \\ &= (xw+yz) + (x+y+z+w)a + 2a^2. \end{split} $$

In particular it seems that you need more than just $p$. And I don't know if there is any shortcut for finding the $P_k$, but it seems unlikely.

Finally you might be interested in Glynn's formula http://www.ams.org/mathscinet-getitem?mr=2673027 which might be a useful alternative to Ryser's.