<p>For <span class="math-container">$f = (f_n)$</span> a family of polynomials where <span class="math-container">$f_n$</span> is a polynomial in <span class="math-container">$n^2$</span> variables (which we can think of as the entries of an <span class="math-container">$n \times n$</span> matrix), say a function <span class="math-container">$S(A,B)$</span> is an addition function for <span class="math-container">$f$</span> if for all square matrices <span class="math-container">$A,B$</span>, <span class="math-container">$f(S(A,B)) = f(A) + f(B)$</span>.</p>
<p>Since both the determinant [https://doi.org/10.1016/j.jco.2006.09.006] and the permanent [https://cstheory.stackexchange.com/a/51348/129] are linearly closed families, they both have addition functions.</p>
<p>If instead of addition functions, we ask for product functions, there is a <em>single</em> construction that works for both det and perm, namely the block-diagonal direct sum of matrices: <span class="math-container">$\det(A \oplus B) = \det(A)\det(B)$</span> and <span class="math-container">$perm(A \oplus B)=perm(A)perm(B)$</span>.</p>
<blockquote>
<p>Is there a single function <span class="math-container">$S(A,B)$</span> that is an addition function for both det and perm?</p>
</blockquote>
<p>I suppose in principle <span class="math-container">$S$</span> could depend on the sizes of <span class="math-container">$A,B$</span>, but it'd be even nicer if it were &quot;uniform&quot; in a similar sense to how the direct sum is uniform. I leave this a bit vague as there are many ways the direct sum construction is uniform, and I'm not sure I have a preference.</p>
<p>Edit: As pointed out by @GeoffreyIrving in the comments, the construction <span class="math-container">$\begin{bmatrix} 1 &amp; 1\\ y &amp; x \end{bmatrix}$</span> works, where <span class="math-container">$x+y=perm(A) +perm(B)$</span> and <span class="math-container">$x-y=det(A) +det(B)$</span>. But this requires computing det and perm in the first place. So let's say at the very least I'd want a construction with poly-size formulas (hence, we think, easier than det). And really what I want is a projection in Valiant's sense, since all the constructions in the OQ above are of that form. Meaning that each entry of S(A, B) should be either a constant or an entry of A or B.</p>

CC BY-SA 4.0
2022-04-23T14:09:59.480Z
Is true that for any $d, p \in \mathbb{R}$, there exists a $2 \times 2$ matrix with determinant $d$ and permanent $p$?  If so, I think the answer is yes, but not necessarily in an interesting way.
Geoffrey Irving
CC BY-SA 4.0
2022-04-23T16:03:51.020Z
@GeoffreyIrving: yes. Let x, y be such that x+y=p and x-y=d. Then the matrix ((1,1),(y,x)) does it (this works over any field, which is nice because ideally I'd want the construction over an arbitrary field). Can you say more?
Joshua Grochow
CC BY-SA 4.0
2022-04-23T18:02:00.120Z
Well, as stated one can just compute the determinants and permanents and the map to the appropriate $2 \times 2$ matrix.  But presumably you want a tractability constraint?
Geoffrey Irving
CC BY-SA 4.0
2022-04-23T18:23:24.327Z
@GeoffreyIrving Oh, uh, yeah. Or at least that the construction itself should not use perm or det. Maybe I want S to be a projection (in Valiant's sense).  I'll have to think about that and update the question.
Joshua Grochow
<cc.complexity-theory><algebraic-complexity><arithmetic-circuits><permanent><determinant>
"Addition function" that works for both perm and det simultaneously?
Joshua Grochow
# "Addition function" that works for both perm and det simultaneously?

(Asked by: username_0 on 2022-04-23)

For $f = (f\_n)$ a family of polynomials where $f\_n$ is a polynomial in $n^2$ variables (which we can think of as the entries of an $n \times n$ matrix), say a function $S(A,B)$ is an addition function for $f$ if for all square matrices $A,B$, $f(S(A,B)) = f(A) + f(B)$.

Since both the determinant [https://doi.org/10.1016/j.jco.2006.09.006] and the permanent [https://cstheory.stackexchange.com/a/51348/129] are linearly closed families, they both have addition functions.

If instead of addition functions, we ask for product functions, there is a *single* construction that works for both det and perm, namely the block-diagonal direct sum of matrices: $\det(A \oplus B) = \det(A)\det(B)$ and $perm(A \oplus B)=perm(A)perm(B)$.

> Is there a single function $S(A,B)$ that is an addition function for both det and perm?

I suppose in principle $S$ could depend on the sizes of $A,B$, but it'd be even nicer if it were "uniform" in a similar sense to how the direct sum is uniform. I leave this a bit vague as there are many ways the direct sum construction is uniform, and I'm not sure I have a preference.

Edit: As pointed out by @GeoffreyIrving in the comments, the construction $\begin{bmatrix} 1 & 1\\ y & x \end{bmatrix}$ works, where $x+y=perm(A) +perm(B)$ and $x-y=det(A) +det(B)$. But this requires computing det and perm in the first place. So let's say at the very least I'd want a construction with poly-size formulas (hence, we think, easier than det). And really what I want is a projection in Valiant's sense, since all the constructions in the OQ above are of that form. Meaning that each entry of S(A, B) should be either a constant or an entry of A or B.

**Tags:** cc.complexity-theory, algebraic-complexity, arithmetic-circuits, permanent, determinant
> **Comments:**
> **username_1**: Is true that for any $d, p \in \mathbb{R}$, there exists a $2 \times 2$ matrix with determinant $d$ and permanent $p$?  If so, I think the answer is yes, but not necessarily in an interesting way.  
> **username_0**: @GeoffreyIrving: yes. Let x, y be such that x+y=p and x-y=d. Then the matrix ((1,1),(y,x)) does it (this works over any field, which is nice because ideally I'd want the construction over an arbitrary field). Can you say more?  
> **username_1**: Well, as stated one can just compute the determinants and permanents and the map to the appropriate $2 \times 2$ matrix.  But presumably you want a tractability constraint?  
> **username_0**: @GeoffreyIrving Oh, uh, yeah. Or at least that the construction itself should not use perm or det. Maybe I want S to be a projection (in Valiant's sense).  I'll have to think about that and update the question.  

---

## 0 answers

