Title: Orbits of monomials and factorization into products of linear forms,
Abstract: This paper is devoted to the factorization of multivariate polynomials into
products of linear forms, a problem which has applications to differential
algebra, to the resolution of systems of polynomial equations and to Waring
decomposition (i.e., decomposition in sums of d-th powers of linear forms; this
problem is also known as symmetric tensor decomposition). We provide three
black box algorithms for this problem. Our main contribution is an algorithm
motivated by the application to Waring decomposition. This algorithm reduces
the corresponding factorization problem to simultaenous matrix diagonalization,
a standard task in linear algebra. The algorithm relies on ideas from invariant
theory, and more specifically on Lie algebras. Our second algorithm
reconstructs a factorization from several bi-variate projections. Our third
algorithm reconstructs it from the determination of the zero set of the input
polynomial, which is a union of hyperplanes.