5
$\begingroup$

Dear math stack exchange community,

I was told that in the paper

http://www.tandfonline.com/doi/abs/10.1080/03081088708817770

there was a formula for the permanent of the sum of two matrices $X$ and $Y$ via permanents of certain submatrices of $X$ and $Y$.

Unfortunately, I don't have access to this paper (and thus, to this formula) at the moment.

I would be very grateful. if somebody could give the formula here.

$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

For all $k\leq n$, let $Q_{k,n}$ the set of all finite sequences of positive integer $\alpha=\{\alpha_{i}\}_{i=1}^{i=k}$ such that $$ 1\leq \alpha_1 < \alpha_2< \ldots <\alpha_{k-1}< \alpha_k\leq n. $$
If $A$ happens to be a $n\times n$ matrix and if $\alpha,\beta\in Q_{k,n}$ then $A(\alpha|\beta)$ denote a $(n-k)\times(n-k)$ submatrix submatrix of $A$ obtained by deleting the rows $\alpha$ and the columns $\beta$; Let $A[\alpha|\beta]$ the complement of $A(\alpha|\beta)$ in $A$.

THEOREM 1 (Expansion of the permanent of the sum of two matrices) Let $A$ and $B$ be arbitrary $m\times m$ matrices. Then $$ \mathrm{per}(A+B)=\mathrm{per}(B)+\sum_{k=1}^{m-1}\sum_{\alpha,\beta\in Q_{k,m}}\mathrm{per}A[\alpha|\beta]\cdot\mathrm{per}A(\alpha|\beta)+\mathrm{per}(A) $$

See also in wikipedia verbete on the permanents and its references.

$\endgroup$
4
  • $\begingroup$ Is there a typo and it should be per$B(\alpha | \beta)$ ? $\endgroup$
    – Bernhard Boehmler
    Jan 22, 2018 at 22:26
  • $\begingroup$ @BernhardBoehmler, No, there is no such type in the article. The notation of the article is just the one that was posted in the answer. $\endgroup$
    – Elias Costa
    Jan 23, 2018 at 11:22
  • 1
    $\begingroup$ So it is really $ \mathrm{per}(A+B)=\mathrm{per}(B)+\sum_{k=1}^{m-1}\sum_{\alpha,\beta\in Q_{k,m}}\mathrm{per}A[\alpha|\beta]\cdot\mathrm{per}A(\alpha|\beta)+\mathrm{per}(A) $ and not $ \mathrm{per}(A+B)=\mathrm{per}(B)+\sum_{k=1}^{m-1}\sum_{\alpha,\beta\in Q_{k,m}}\mathrm{per}A[\alpha|\beta]\cdot\mathrm{per}B(\alpha|\beta)+\mathrm{per}(A) $ ? $\endgroup$
    – Bernhard Boehmler
    Jan 24, 2018 at 12:15
  • 1
    $\begingroup$ There is in fact a typo in the above answer. It should be perB(α|β) rather than perA(α|β). $\endgroup$
    – jkuck
    Jun 18, 2018 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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