Expressing a fraction of two determinants as a determinant

ABSTRACT

Suppose the polynomials f and g in K[x₁,...,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₁,...,x_r. Furthermore, suppose h = f/g is a polynomial in K[x₁,..., x_r]. We construct an s x s matrix C whose entries are in K ∪ x₁,...,x_r, such that h = det(C) and s = γ (m+n)⁶, 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.

REFERENCES

• 1: Stuart J. Berkowitz, On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, v.18 n.3, p.147-150, March 1984 [doi>10.1016/0020-0190(84)90018-8]
• 2: John Canny, Generalised characteristic polynomials, Journal of Symbolic Computation, v.9 n.3, p.241-250, March 1990 [doi>10.1016/S0747-7171(08)80012-0]
• 3: David G. Cantor , Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, v.28 n.7, p.693-701, Oct. 1991 [doi>10.1007/BF01178683]
• 4: Alexander L. Chistov, Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic, Fundamentals of Computation Theory, p.63-69, September 09-13, 1985
• 5: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 6: Eisenbud, D., Schreyer, F., and Weyman, J. Resultants and Chow forms via exterior syzygies. J. Amer. Math. Soc. 16 (2003), 537--579.
• 7: Joachim Von Zur Gathen , Jurgen Gerhard, Modern Computer Algebra, Cambridge University Press, New York, NY, 2003
• 8: Erich Kaltofen, Greatest common divisors of polynomials given by straight-line programs, Journal of the ACM (JACM), v.35 n.1, p.231-264, Jan. 1988 [doi>10.1145/42267.45069]
• 9: Erich Kaltofen , Gilles Villard, On the complexity of computing determinants, Computational Complexity, v.13 n.3-4, p.91-130, February 2005 [doi>10.1007/s00037-004-0185-3]
• 10: Amit Khetan, Determinantal formula for the chow form of a toric surface, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.145-150, July 07-10, 2002, Lille, France [doi>10.1145/780506.780525]
• 11: Amit Khetan , Ning Song , Ron Goldman, Sylvester-resultants for bivariate polynomials with planar newton polygons, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.205-212, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005316]
• 12: S. Rao Kosaraju , Arthur L. Delcher, Optimal Parallel Evaluation of Tree-Structured Computations by Raking, Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, p.101-110, June 28-July 01, 1988
• 13: Macaulay, F. S. The Algebraic Theory of Modular Systems. No. 19 in Cambridge Tracts. The University Press, Cambridge, Great Britain, 1916. Reissued in the Cambridge Mathematical Library with an Introduction by Paul Roberts, 1994.
• 14: Guillaume Malod , Natacha Portier, Characterizing Valiant's algebraic complexity classes, Journal of Complexity, v.24 n.1, p.16-38, February, 2008 [doi>10.1016/j.jco.2006.09.006]
• 15: Gary L. Miller , Vijaya Ramachandran , Erich Kaltofen, Efficient parallel evaluation of straight-line code and arithmetic circuits, SIAM Journal on Computing, v.17 n.4, p.687-695, August 1988 [doi>10.1137/0217044]
• 16: Tateaki Sasaki , Hirokazu Murao, Efficient Gaussian Elimination Method for Symbolic Determinants and Linear Systems, ACM Transactions on Mathematical Software (TOMS), v.8 n.3, p.277-289, Sept. 1982 [doi>10.1145/356004.356007]
• 17: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 18: Strassen, V. Vermeidung von Divisionen. J. reine u. angew. Math. 264 (1973), 182--202. In German.
• 19: Toda, S. Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Transactions on Information and Systems E75-D, 1 (Jan. 1992), 116--124.
• 20: Valiant, L., Skyum, S., Berkowitz, S., and Rackoff, C. Fast parallel computation of polynomials using few processors. SIAM J. Comp. 12, 4 (1983), 641--644.
• 21: L. G. Valiant, Completeness classes in algebra, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.249-261, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804419]
• 22: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Simplification of expressions

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

General Terms:
Algorithms, Theory

Keywords:
algebraic complexity theory, formula complexity, strassen's removal of divisions, toda's skew circuits, valiant's universality of determinants