Linear projections of the Vandermonde polynomial

DOI10.1016/J.TCS.2019.06.010MaRDI QIDQ2330107zbMATH OpenOpenAlexWikidataFDO

Authors C. Ramya, B. V. Raghavendra Rao

Publication date 18 October 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.03188

zbMATH Keywords

algebraic complexity theorypolynomial equivalence problemVandermonde polynomials

Mathematics Subject Classification ID

Polynomials (irreducibility, etc.) (11R09) Polynomials in real and complex fields: factorization (12D05) Determinants, permanents, traces, other special matrix functions (15A15) Numerical computation of determinants (65F40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: An n-variate Vandermonde polynomial is the determinant of the n x n matrix where the ith column is the vector (1, x_i, x_i^2, ...., x_i^{n-1})^T. Vandermonde polynomials play a crucial role in the theory of alternating polynomials and occur in Lagrangian polynomial interpolation as well as in the theory of error correcting codes. In this work we study structural and computational aspects of linear projections of Vandermonde polynomials. Firstly, we consider the problem of testing if a given polynomial is linearly equivalent to the Vandermonde polynomial. We obtain a deterministic polynomial time algorithm to test if the polynomial f is linearly equivalent to the Vandermonde polynomial when f is given as product of linear factors. In the case when the polynomial f is given as a black-box our algorithm runs in randomized polynomial time. Exploring the structure of projections of Vandermonde polynomials further, we describe the group of symmetries of a Vandermonde polynomial and show that the associated Lie algebra is simple.

Review text

An $n$-variate Vandermonde polynomial is the determinant of the $n\times n$ matrix where the $i$-th column is the vector $\langle 1, x_i, x^2_i, \dots, x^{n-1}_i \rangle^T$. In the paper, some structural and computational aspects of Vandermonde polynomial linear projections are studied. For a polynomial $f$ that is a product of linear factors, a deterministic polynomial time algorithm is constructed to test if $f$ is linearly equivalent to the Vandermonde polynomial. The group of symmetries of a Vandermonde polynomial is described. The arithmetic circuits built over projections of Vandermonde polynomials are studied.

Recommendations

• scientific article; zbMATH DE number 4086227
• scientific article; zbMATH DE number 2051092
• Generalized Taylor's Theorem
• The Generalized Vandermonde Matrix
• Vandermonde matrices for intersection points of curves

Cites work

• Affine projections of polynomials (extended abstract)
• Affine projections of symmetric polynomials.
• Diagonal Circuit Identity Testing and Lower Bounds
• Efficient algorithms for some special cases of the polynomial equivalence problem
• Finding a simple polytope from its graph in polynomial time
• Geometric complexity theory. I: An approach to the P vs. NP and related problems
• Geometry and complexity theory
• Hilbert's Nullstellensatz is in the polynomial hierarchy
• scientific article; zbMATH DE number 1332670 (Why is no real title available?)
• scientific article; zbMATH DE number 1181673 (Why is no real title available?)
• scientific article; zbMATH DE number 2151804 (Why is no real title available?)
• scientific article; zbMATH DE number 2241894 (Why is no real title available?)
• Reconstruction of full rank algebraic branching programs
• Sums of Like Powers of Multivariate Linear Forms

Cited in

(3)

• On Vandermonde varieties
• Affine projections of polynomials (extended abstract)
• Derandomizing multivariate polynomial factoring for low degree factors

This page was built for publication: Linear projections of the Vandermonde polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2330107)