Determinantal complexities and field extensions
- Publication Type:
- Conference Proceeding
- Citation:
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, 8283 LNCS pp. 119 - 129
- Issue Date:
- 2013-12-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
 | 2013005433OK.pdf | 255.5 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
Let double-struck F be a field of characteristic ≠ 2. The determinantal complexity of a polynomial P ∈ double-struck F[x1,..., x n] is defined as the smallest size of a matrix M whose entries are linear polynomials of xi 's over double-struck F, such that P = det(M) as polynomials in double-struck F[x1,..., xn]. To determine the determinantal complexity of the permanent polynomial is a long-standing open problem. Let double-struck K be an extension field of double-struck F; then P can be viewed as a polynomial over double-struck K. We are interested in the comparison between the determinantal complexity of P over double-struck K (denoted as dcdouble-struck K(P))), and that of P over double-struck F (denoted as dcdouble-struck F(P). It is clear that dcdouble-struck K(P) ≤, dcdouble-struck F(P) and the question is whether strict inequality can happen. In this note we consider polynomials defined over ℚ. For P = x12 + ⋯ + xn2, there exists a constant multiplicative gap between dcℝ(P) and dcℂ(P): we prove dc ℝ(P) ≥ n while ⌈n/2⌉ + 1 ≥ dc ℂ(P). We also consider additive constant gaps: (1) there exists a quadratic polynomial Q ∈ ℚ [x, y], such that dcℚ-(Q) = 3 and ; (2) there exists a cubic polynomial C ∈ ℚ[x, y] with a rational zero, such that dcℚ(C) = 4 and dcℚ-(C) = 3. For additive constant gaps, geometric criteria are presented to decide when dcℚ = dcℚ-. © 2013 Springer-Verlag.
Please use this identifier to cite or link to this item: