I'll give two equivalent statements of the setup, then give my questions.

  1. Fix integers $M \leq N$ and define the Vandermonde-like matrix $V_{M,N}[i,j] = (1 - \frac{i}{M})^{j-1}$ for $i \in \{1,2,\ldots,M \}$ and $j \in \{1,2,\ldots, N \}$. For some vector $v \in \mathbb{R}^{M}$ with nonnegative entries, I am interested in finding out when there exists $u \in \mathbb{R}^{N}$ with nonnegative entries so that

\begin{equation} V_{M,N} u = v. \end{equation}

  1. This is equivalent to finding a degree-$N$ polynomial $f$ with nonnegative coefficients that satisfies $f(1 - \frac{i}{M}) = v[j]$ for all $i \in \{1,2,\ldots,M\}$.

So, onto my questions:

  1. Is there an easy way to check that for $N > N(M,v)$ sufficiently large, such a nonnegative solution exists?

  2. If a solution exists, is there a "nice" description of it? I'm not sure exactly what I mean by "nice," but papers such as http://math.mit.edu/~plamen/files/44033.pdf suggest that finding solutions to Vandermonde-like systems of equations is computationally much easier than finding solutions to generic systems of equations, and of course there are all sorts of great formulas for minors of Vandermonde matrices in terms of Schur polynomials.

In case it makes a difference, I only care about the answer for some specific families of nonnegative vectors $v$; the simplest of these is given by $v[j] = \frac{M}{j^{2}}$ for $ j \in \{1,2,\ldots,M\}$.

Thanks for any help!

In case it is useful, I mention what little I know so far:

  1. $N = M$ clearly doesn't work - there is a unique solution to $V_{M,N} u = v$ and it generally has negative entries.

  2. If $V_{M,N}$ were `generic' matrices, this sort of thing does tend to happen, in part because you would eventually get elements of the nullspace that had only nonnegative entries. Unfortunately, that clearly can't happen here - for any $M,N$, any element of the nullspace of $V_{M,N}$ has at least one positive entry.

  3. Previous math overflow questions that looked similar pointed me to various papers giving conditions for the existence of nonnegative solutions to systems of equations (e.g. "On Positive Solutions of a System of Linear Equations" from Annals of Math, 1927). Unfortunately, none of these conditions seem terribly easy to use (perhaps there is some `trick' to using them for nice families of systems of equations, but if so I have not seen anybody use such a trick).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.