# Determining a polynomial from its crossings with another polynomial

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}$.

-
If they agree at more than $n$ points, then they agree everywhere, so your statement is wrong: these are not points where they cross each other. –  Robert Israel Nov 20 '12 at 18:52
@RobertIsrael Sorry, I have made an edit based on your comment. So, the crossings are for different polynomials, which are all related by overall multiplicative constants, which I called v_1 , ... , v_2n. –  Pavithran Iyer Nov 20 '12 at 19:52

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$.

-

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

-
Moreover, $p-q$ is a polynomial of degree $n$ with $2n$ zeros, so that $p\equiv q$. –  Julián Aguirre Nov 20 '12 at 17:54

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.

-
Yes, you're right. Sorry, I made a small edit, which was to introduce different multiplicative constants, for the function $f$, before determining its crossing with $g$. Hence now, as you told in the previous case, if $f(p) = g(p)$ then, it is not necessary that $c f(p) = c g(p)$. –  Pavithran Iyer Nov 20 '12 at 19:57