expressing a fraction of two determinants as a determinant
Suppose the polynomials f and g in K[x 1 ,...,x r ] over the field K are determinants of non-singular m x m and n x n matrices, respectively, whose entries are in K ? x 1 ,...,x r . Furthermore, suppose h = f/g is a polynomial in K[x 1 ,..., x r ]. We construct an s x s matrix C whose entries are in K ? x 1 ,...,x r , such that h = det(C) and s = ? (m+n) 6 , where ? = O(1) if K is an infinite field or if for the finite field K = F{q} with q elements we have m = O(q), and where ? = (log q m) 1+o(1) if q = o(m). Our construction utilizes the notion of skew circuits by Toda and WSK circuits by Malod and Portier. Our problem was motivated by resultant formulas derived from Chow forms. Additionally, we show that divisions can be removed from formulas that compute polynomials in the input variables over a sufficiently large field within polynomial formula size growth.
valiant's universality of determinants toda's skew circuits strassen's removal of divisions formula complexity algebraic complexity theory