5
$\begingroup$

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

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

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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