# Can a sum of polynomially many determinants be expressed as a single determinant of a poly-size matrix?

(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$$.

• 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
Oct 22, 2022 at 7:44
• 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$. Oct 22, 2022 at 17:44
• Yes, holf's answer is correct. Det is what is called a "linearly closed family", meaning precisely a positive answer to your question. Oct 23, 2022 at 4:10

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.