×

Uniform determinantal representations. (English) Zbl 1387.13062

Let \(K\) be a field and \(d,n\in \mathbb Z_{\geq 0}\). Let \(K[x_1,\ldots, x_n]\) be the polynomial ring over \(K\), and let \(p_{n,d} = \sum_{\alpha} c_{\alpha} x^{\alpha}\) be a polynomial of degree at most \(d\). Here \(\alpha = (\alpha_1,\ldots,\alpha_n) \in \mathbb Z^n_{\geq 0}\) is a multi-index such that \(\sum_{i=1}^n \alpha_i\leq d\), and \(x^{\alpha}\) denotes the monomial \(\prod_{i=1}^n x_i^{\alpha_i}\). A determinantal representation of \(p_{n,d}\) is an \(N\times N\)-matrix \(M\) with affine-linear entries in \(x_1,\ldots, x_n\), such that \(\det(M) = p\); the integer \(N\) is the size of the representation. The minimal possible size is called determinantal complexity of \(p\). Recently, this notion has become fundamental due to its connections to several fields such as complexity theory, optimization, and scientific computing. For instance, one of the deepest conjectures in algebraic complexity is Valiant’s conjecture, which states that the permanent of an \(m\times m\)-matrix does not admit a determinantal representation of size polynomial in \(m\). (This conjecture can be also rephrased in the context of representation theory and orbit closures of permanents and determinants.) In this interesting paper, the authors study a variant of determinantal representations. Instead of looking at representations of a single polynomial, they seek for determinantal representations of subspaces of polynomials. A uniform determinantal representation of \(p_{n,d}\) is an \(N\times N\)-matrix \(M\) with entries in \(x_1,\ldots, x_n, c_{\alpha}\), of degree at most one in each of these two sets of variables, such that \(\det(M) = p_{n,d}\). Such a matrix \(M\) gives a representation for all polynomials of degree at most \(d\). For \(n,d\in \mathbb Z_{\geq 0}\), the number \(N^{*}(n,d)\in \mathbb Z_{>0}\) denotes the minimum size of uniform determinantal representations of \(p_{n,d}\). Let \(M\) be a uniform determinantal representation of \(p_{n,d}\). Let \(M = M_0+M_1\), where \(M_0\) is the matrix not containing any variable \(c_{\alpha}\). They show that for every point \(\overline{x}=(\overline{x_1},\ldots, \overline{x_n})\in K^n\), \(M_0(\overline{x})\) is singular (Lemma 2.5). Thus, they nicely connect the theory of uniform representations with the classical theory of singular matrix spaces; the connection is explained in Section 3. The main result is the following. For every integer \(n\geq 2\), there exist positive constants \(C_1,C_2\), depending on \(n\), such that \(C_1 d^{n/2} \leq N^{*}(n,d)\leq C_2 d^{n/2}\) (Theorem 1.3). These bounds improve previous results by R. Quarez [Linear Algebra Appl. 436, No. 9, 3462–3660 (2012; Zbl 1238.47010)]. They show explicit values of \(N^{*}(n,d)\) for small \(n\) and \(d\). They prove that \(N^{*}(2,2) = 3\) (Proposition 5.1) and \(N^{*}(3,2) = 4\) (Proposition 5.2). Section 7 is the computational part of this article. Here they apply the results of the paper to the problem of efficiently solving systems of bivariate polynomial equations, based on the work of B. Plestenjak and M. E. Hochstenbach [SIAM J. Sci. Comput. 38, No. 2, A765–A788 (2016; Zbl 1376.65056)]. The authors conclude presenting several questions arising from this work. Finally, appendix A describes an algorithm to compute a determinantal representation for a given polynomial, based on the proof of Theorem 1.3.

MSC:

13P15 Solving polynomial systems; resultants
65H04 Numerical computation of roots of polynomial equations
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F50 Computational methods for sparse matrices
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] F. V. Atkinson, {\it Multiparameter eigenvalue problems: Matrices and compact operators}, SIAM Rev., 15 (1973), pp. 678-679, .
[2] D. J. Bates, J. H. Hauenstein, A. J. Sommese, and C. W. Wampler, {\it Bertini: Software for Numerical Algebraic Geometry}, available online at . · Zbl 1143.65344
[3] A. Beauville, {\it Determinantal hypersurfaces}, Michigan Math. J., 48 (2000), pp. 39-64, . · Zbl 1076.14534
[4] A. Boralevi, D. Faenzi, and E. Mezzetti, {\it Linear spaces of matrices of constant rank and instanton bundles}, Adv. Math., 248 (2013), pp. 895-920, . · Zbl 1291.14063
[5] N. Bourbaki, {\it Éléments de mathématique. Fasc. XXXIV. Groupes et algèbres de Lie. Chapitre IV: Groupes de Coxeter et systèmes de Tits. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: systèmes de racines}, Actualités Scientifiques et Industrielles 1337, Hermann, Paris, 1968. · Zbl 0186.33001
[6] P. Brändén, {\it Obstructions to determinantal representability}, Adv. Math., 226 (2011), pp. 1202-1212, . · Zbl 1219.90121
[7] P. Bürgisser, C. Ikenmeyer, and G. Panova, {\it No occurrence obstructions in geometric gomplexity theory}, in 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2016, . · Zbl 1401.68088
[8] C. de Seguins Pazzis, {\it Large affine spaces of matrices with rank bounded below}, Linear Algebra Appl., 437 (2012), pp. 499-518, . · Zbl 1242.15002
[9] L. E. Dickson, {\it Determination of all general homogeneous polynomials expressible as determinants with linear elements}, Trans. Amer. Math. Soc., 22 (1921), pp. 167-179. · JFM 48.0099.02
[10] J. Dieudonné, {\it Sur une généralisation du groupe orthogonal à quatre variables}, Arch. Math., 1 (1949), pp. 282-287. · Zbl 0032.10601
[11] A. C. Dixon, {\it Note on the reduction of a ternary quartic to a symmetrical determinant}, Proc. Cambridge Philos. Soc., 11 (1900-1902), pp. 350-351. · JFM 33.0140.04
[12] J. Draisma, {\it Small maximal spaces of non-invertible matrices}, Bull. London Math. Soc., 38 (2006), pp. 764-776, . · Zbl 1112.15019
[13] D. Eisenbud and J. Harris, {\it Vector spaces of matrices of low rank}, Adv. in Math., 70 (1988), pp. 135-155, . · Zbl 0657.15013
[14] P. Fillmore, C. Laurie, and H. Radjavi, {\it On matrix spaces with zero determinant}, Linear and Multilinear Algebra, 18 (1985), pp. 255-266, . · Zbl 0592.15008
[15] H. Flanders, {\it On spaces of linear transformations with bounded rank}, J. London Math. Soc., 37 (1962), pp. 10-16, . · Zbl 0101.25403
[16] Y. Guan and J. Verschelde, {\it PHClab: A MATLAB/Octave interface to PHCpack}, in Software for Algebraic Geometry, IMA Vol. Math. Appl. 148, Springer, New York, 2008, pp. 15-32. · Zbl 1148.68578
[17] J. W. Helton and V. Vinnikov, {\it Linear matrix inequality representation of sets}, Comm. Pure Appl. Math., 60 (2007), pp. 654-674, . · Zbl 1116.15016
[18] M. E. Hochstenbach, T. Košir, and B. Plestenjak, {\it A Jacobi-Davidson type method for the two-parameter eigenvalue problem}, SIAM J. Matrix Anal. Appl., 26 (2004), pp. 477-497, . · Zbl 1077.65036
[19] J. Hüttenhain and P. Lairez, {\it The Boundary of the Orbit of the 3 by 3 Determinant Polynomial}, preprint, , 2015. · Zbl 1352.14031
[20] B. Ilic and J. M. Landsberg, {\it On symmetric degeneracy loci, spaces of symmetric matrices of constant rank and dual varieties}, Math. Ann., 314 (1999), pp. 159-174. · Zbl 0949.14028
[21] Y. Ishitsuka and T. Ito, {\it On the symmetric determinantal representations of the Fermat curves of prime degree}, Int. J. Number Theory, 12 (2016), pp. 955-967. · Zbl 1415.11062
[22] J.-B. Lasserre, M. Laurent, B. Mourrain, P. Rostalski, and P. Trébuchet, {\it Moment matrices, border bases and real radical computation}, J. Symbolic Comput., 51 (2013), pp. 63-85. · Zbl 1276.13021
[23] R. Lebreton, E. Mehrabi, and E. Schost, {\it On the complexity of solving bivariate systems: The case of non-singular solutions}, in Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC ’13, ACM, New York, 2013, pp. 251-258, . · Zbl 1360.68941
[24] A. S. Lewis, P. A. Parrilo, and M. V. Ramana, {\it The Lax conjecture is true}, Proc. Amer. Math. Soc., 133 (2005), pp. 2495-2499, . · Zbl 1073.90029
[25] L. Manivel and E. Mezzetti, {\it On linear spaces of skew-symmetric matrices of constant rank}, Manuscripta Math., 117 (2005), pp. 319-331. · Zbl 1084.14050
[26] E. Mehrabi and É. Schost, {\it A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers}, J. Complex., 34 (2016), pp. 78-128, . · Zbl 1352.68299
[27] B. Mourrain and K. Schmüdgen, {\it Flat extensions in \(*\)-algebras}, Proc. Amer. Math. Soc., 144 (2016), pp. 4873-4885. · Zbl 1364.46047
[28] A. Muhič and B. Plestenjak, {\it On the quadratic two-parameter eigenvalue problem and its linearization}, Linear Algebra Appl., 432 (2010), pp. 2529-2542, . · Zbl 1189.65070
[29] K. D. Mulmuley and M. Sohoni, {\it Geometric complexity theory. I. An approach to the P vs. NP and related problems}, SIAM J. Comput., 31 (2001), pp. 496-526, . · Zbl 0992.03048
[30] K. D. Mulmuley and M. Sohoni, {\it Geometric complexity theory. II. Towards explicit obstructions for embeddings among class varieties}, SIAM J. Comput., 38 (2008), pp. 1175-1206, . · Zbl 1168.03030
[31] Y. Nakatsukasa, V. Noferini, and A. Townsend, {\it Computing the common zeros of two bivariate functions via Bézout resultants}, Numer. Math., 129 (2015), pp. 181-209, . · Zbl 1308.65076
[32] A. Newell, {\it BertiniLab: Toolbox for solving polynomial systems, MATLAB Central File Exchange}, . · Zbl 1333.65054
[33] B. Plestenjak, {\it BiRoots, MATLAB Central File Exchange}, , (2015).
[34] B. Plestenjak and M. E. Hochstenbach, {\it Roots of bivariate polynomial systems via determinantal representations}, SIAM J. Sci. Comput., 38 (2016), pp. A765-A788, . · Zbl 1376.65056
[35] R. Quarez, {\it Symmetric determinantal representation of polynomials}, Linear Algebra Appl., 436 (2012), pp. 3642-3660, . · Zbl 1238.47010
[36] L. Robol, R. Vandebril, and P. van Dooren, {\it A framework for structured linearizations of matrix polynomials in various bases}, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 188-216, . · Zbl 1365.15028
[37] A. Sidorenko, {\it What we know and what we do not know about Turán numbers}, Graphs Combin., 11 (1995), pp. 179-199, . · Zbl 0839.05050
[38] J. Sylvester, {\it On the dimension of spaces of linear transformations satisfying rank conditions}, Linear Algebra Appl., 78 (1986), pp. 1-10, . · Zbl 0588.15002
[39] L. G. Valiant, {\it The complexity of computing the permanent}, Theoret. Comput. Sci., 8 (1979), pp. 189-201, . · Zbl 0415.68008
[40] J. Verschelde, {\it Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation}, ACM Trans. Math. Softw., 25 (1999), pp. 251-276, . · Zbl 0961.65047
[41] D. G. Wagner, {\it Multivariate stable polynomials: Theory and applications}, Bull. Amer. Math. Soc. (N.S.), 48 (2011), pp. 53-84, . · Zbl 1207.32006
[42] R. Westwick, {\it Spaces of matrices of fixed rank}, Linear and Multilinear Algebra, 20 (1987), pp. 171-174, . · Zbl 0611.15002
[43] Wolfram Research, Inc., {\it Mathematica, Version 9.0}, Champaign, IL, 2012.
[44] Z. Zeng and T.-Y. Li, {\it NAClab: A Matlab toolbox for numerical algebraic computation}, ACM Commun. Comput. Algebra, 47 (2014), pp. 170-173, .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.