Determining a polynomial from its crossings with another polynomial

Question

Is it possible to determine the coefficients of two polynomials, if we are given 2n different points at which they cross each other ?

In other words, If $f(p) = \sum_{i}\alpha_{i}p^{i}$ and $g(p) = \sum_{i}\beta_{i}p^{i}$ are two $n-$degree polynomials and we have $\{p_{1}, p_{2}, \dots, p_{2n}\}$ such that:

$v_{1}f(p_{1}) = g(p_{1})$

$v_{2}f(p_{2}) = g(p_{2})$

$\vdots$

$v_{2n}f(p_{2n}) = g(p_{2n})$

where $v_{1}, \dots, v_{2n}$ are all known constants, $v_{i}\neq v_{j}$.

Is that enough to determine $\{\alpha_{0}, \dots, \alpha_{n}, \beta_{0}, \dots, \beta_{n}\}$ ?

I understand each crossing would provide us a linear constraint on the coefficients. Hence my intuition would be that 2n different crossings give 2n linearly independent constraints. But then, when I try examples or even try to express all the constraints as a matrix form, I get a homogeneous system of linear equations, whose only solution turns out to be $\alpha_{i} = 0 = \beta_{i}$.

Can anyone please help.

Answer 1

Note that there are $2n+2$ parameters $a_0, \ldots, a_n, b_0, \ldots, b_n$, not $2n$. For the new problem with the $v_i$, there will still be an overall multiplicative constant, i.e. if $v_j f(p_j) = g(p_j)$ then also $v_j c f(p_j) = c g(p_j)$ for any constant $c$. The matrix of coefficients for the system of equations you get with $k$ points is $$ M = \pmatrix{v_1 & v_1 p_1 &\ldots & v_1 p_1^n & -1 & -p_1 & \ldots & -p_1^n \cr v_2 & v_2 p_1 &\ldots & v_2 p_2^n & -1 & -p_2 & \ldots & -p_2^n \cr \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \cr v_k & v_k p_k &\ldots & v_k p_k^n & -1 & -p_k & \ldots & -p_k^n \cr} = \pmatrix{VA & -A}$$ where $A$ is a $k \times (n+1)$ Vandermonde matrix and $V$ is a diagonal matrix with diagonal entries $v_1, \ldots, v_k$. The best you can hope for is that with $k=2n+1$ this matrix has rank $2n+1$, so that its null space has dimension $1$: that means that you get a unique solution to your system up to that multiplicative constant.

I tried the case $n=2$. "Generically" the matrix does have rank $5$, but not always. For example, with all $v_i = p_i$ we get two linearly independent solutions: $f(x) = 1, g(x) = x$ and $f(x) = x, g(x) = x^2$.

Answer 2

You can not solve for the coefficients of both polynomials no matter what number of p(s) is given.

Consider the case when $p(x)=q(x)=c$ where c is a constant. You know that all values of x satisfy $p(x)=q(x)$, however you can not determine c

Answer 3

This is Julian Aguirre's comment, with more detail:

An $n$-degree polynomial is uniquely determined by its values at $n+1$ points. So the examples you tried are typical in the sense that two degree-$n$ polynomials that agree on $2n$ points must be the same polynomial.

Now, you said you are given points at which these polynomials agree. If you know the value of the polynomials at these points then you can recover the polynomials (see here).

On the other hand, if you are given only the values of the independent variable where the polynomials agree, then you cannot determine the polynomials. If $f$ and $g$ agree at $p_1,p_2,\ldots,p_{2n}$, then so do $2f$ and $2g$, as do $f+1$ and $g+1$, as do $2x^2f+3\frac{df}{dx}-7\pi+f(0)$ and $2x^2g+3\frac{dg}{dx}f-7\pi$+g(0), etc.