<p>It is possible and proven in [1, Proposition 7]. More precisely, Malod and Portier show that the determinant is linearly closed, that is, every linear combination of the form <span class="math-container">$\sum_{i=1}^n \lambda_i det(A_i)$</span> can be expressed as <span class="math-container">$det(B)$</span> for a matrix <span class="math-container">$B$</span> of size <span class="math-container">$poly(N) \times poly(N)$</span> where <span class="math-container">$N \times N$</span> is the size of the biggest matrix among matrices <span class="math-container">$A_1,\dots,A_n$</span>.</p>
<p>The proof uses results previously established in the paper concerning the completeness of the determinant for the subclass of polynomial size weakly skew algebraic circuits known as <span class="math-container">$\mathsf{VP_{ws}}$</span> (a circuit is weakly skew if every multiplication gate has one input that is an input of the circuit).</p>
<p>They show in Lemma 6 that any circuits of size <span class="math-container">$m$</span> in this class can be expressed as <span class="math-container">$det(B)$</span> for an <span class="math-container">$(m+1) \times (m+1)$</span> matrix having entries that are elements of the field or variables.</p>
<p>They also show in Proposition 5 that the determinant polynomial belongs to this class.</p>
<p>Since this class is linearly closed, that is, every linear combination of weakly skew circuits is still weakly skew, <span class="math-container">$\sum_{i=1}^n \lambda_i det(A_i)$</span> is computed by a polynomial size weakly skew circuit by Proposition 5 which itself is expressible as the determinant of a polynomial size matrix by Lemma 6.</p>
<p><strong>References</strong></p>
<p>[1] Malod, G., &amp; Portier, N. (2008). Characterizing Valiant's algebraic complexity classes. Journal of complexity, 24(1), 16-38.</p>

CC BY-SA 4.0
2022-10-23T07:17:05.517Z
2022-10-23T07:17:05.517Z
holf
<p>(copied from a mathoverflow question because I realized this may be more appropriate for it) Let <span class="math-container">$A_1,A_2,...,A_k$</span> be <span class="math-container">$N$</span>-by-<span class="math-container">$N$</span> matrices, with indeterminate entries in some field (say real or complex numbers), with <span class="math-container">$k={\rm poly}(N)$</span>.  Is there a matrix <span class="math-container">$B$</span>, of size <span class="math-container">$m$</span>-by-<span class="math-container">$m$</span>, for some <span class="math-container">$m={\rm poly}(N)$</span>, with the entries of <span class="math-container">$B$</span> being linear functions of the entries of the <span class="math-container">$A_i$</span>, such that <span class="math-container">$\sum_i {\rm det}(A_i)={\rm det}(B)$</span>?</p>
<p>Note, by results of Valiant and others, such a <span class="math-container">$B$</span> exists of size <span class="math-container">$N^{{\cal O}(\log(N))}$</span>.  But I want to know if <span class="math-container">$B$</span> can be only polynomially large.  And if it can, is there any elegant expression for <span class="math-container">$B$</span>?  Indeed, it's not obvious how to find such a poly size <span class="math-container">$B$</span> even when <span class="math-container">$k=2$</span>.</p>

CC BY-SA 4.0
2022-10-22T07:44:44.747Z
Don't have time for a full answer but that should work: Determinant is complete for the class of weakly skew circuits (see Lemma 6 in Characterizing Valiant's algebraic complexity classes, Malod, Portier) which is itself stable by addition. So you have a polysize weakly skew circuit for $\sum_i det(A_i)$, hence a matrix $B$ of polynomial size such that $det(B) = \sum_i det(A_i)$
holf
CC BY-SA 4.0
2022-10-22T17:44:29.633Z
Thanks.  Add it as an answer so I can accept it.  Interestingly, this seems like even if $k=2$ then $B$ may be polynomially larger than $A_i$.
Matt Hastings
CC BY-SA 4.0
2022-10-23T04:10:05.973Z
Yes, holf's answer is correct. Det is what is called a "linearly closed family", meaning precisely a positive answer to your question.
Joshua Grochow
<circuit-complexity><arithmetic-circuits><determinant>
Can a sum of polynomially many determinants be expressed as a single determinant of a poly-size matrix?
Matt Hastings
# Can a sum of polynomially many determinants be expressed as a single determinant of a poly-size matrix?

(Asked by: username_0 on 2022-10-22)

(copied from a mathoverflow question because I realized this may be more appropriate for it) Let $A\_1,A\_2,...,A\_k$ be $N$-by-$N$ matrices, with indeterminate entries in some field (say real or complex numbers), with $k={\rm poly}(N)$. Is there a matrix $B$, of size $m$-by-$m$, for some $m={\rm poly}(N)$, with the entries of $B$ being linear functions of the entries of the $A\_i$, such that $\sum\_i {\rm det}(A\_i)={\rm det}(B)$?

Note, by results of Valiant and others, such a $B$ exists of size $N^{{\cal O}(\log(N))}$. But I want to know if $B$ can be only polynomially large. And if it can, is there any elegant expression for $B$? Indeed, it's not obvious how to find such a poly size $B$ even when $k=2$.

**Tags:** circuit-complexity, arithmetic-circuits, determinant
> **Comments:**
> **username_1**: Don't have time for a full answer but that should work: Determinant is complete for the class of weakly skew circuits (see Lemma 6 in Characterizing Valiant's algebraic complexity classes, Malod, Portier) which is itself stable by addition. So you have a polysize weakly skew circuit for $\sum_i det(A_i)$, hence a matrix $B$ of polynomial size such that $det(B) = \sum_i det(A_i)$  
> **username_0**: Thanks.  Add it as an answer so I can accept it.  Interestingly, this seems like even if $k=2$ then $B$ may be polynomially larger than $A_i$.  
> **username_2**: Yes, holf's answer is correct. Det is what is called a "linearly closed family", meaning precisely a positive answer to your question.  

---

## 1 answers

### Answer by username_1 on 2022-10-23. Score: 5 | Accepted answer

It is possible and proven in [1, Proposition 7]. More precisely, Malod and Portier show that the determinant is linearly closed, that is, every linear combination of the form $\sum\_{i=1}^n \lambda\_i det(A\_i)$ can be expressed as $det(B)$ for a matrix $B$ of size $poly(N) \times poly(N)$ where $N \times N$ is the size of the biggest matrix among matrices $A\_1,\dots,A\_n$.

The proof uses results previously established in the paper concerning the completeness of the determinant for the subclass of polynomial size weakly skew algebraic circuits known as $\mathsf{VP\_{ws}}$ (a circuit is weakly skew if every multiplication gate has one input that is an input of the circuit).

They show in Lemma 6 that any circuits of size $m$ in this class can be expressed as $det(B)$ for an $(m+1) \times (m+1)$ matrix having entries that are elements of the field or variables.

They also show in Proposition 5 that the determinant polynomial belongs to this class.

Since this class is linearly closed, that is, every linear combination of weakly skew circuits is still weakly skew, $\sum\_{i=1}^n \lambda\_i det(A\_i)$ is computed by a polynomial size weakly skew circuit by Proposition 5 which itself is expressible as the determinant of a polynomial size matrix by Lemma 6.

**References**

[1] Malod, G., & Portier, N. (2008). Characterizing Valiant's algebraic complexity classes. Journal of complexity, 24(1), 16-38.


---

