Outer product of two vectors (one known) is unknown but sums of matrix diagonals are known. Solve for unknown vector

Question

Suppose we have vectors $\mathbf{a}=(a_1,a_2,...,a_n)$ and $\mathbf{b}=(b_1,b_2,...,b_n)$ where $\mathbf{a}$ is known and $\mathbf{b}$ is unknown.

For the purposes of this question assume $n=3$. Then the outer product of $\mathbf{a}$ and $\mathbf{b}$ is

$$\begin{bmatrix}a_1b_1 & a_1b_2 & a_1b_3\\a_2b_1 & a_2b_2 & a_2b_3\\a_3b_1 & a_3b_2 & a_3b_3 \end{bmatrix}$$

This matrix is not fully known, but the sums of the diagonals are known. So we have the system of equations

$$c_1=a_1b_1$$ $$c_2=a_2b_1+a_1b_2$$ $$c_3=a_3b_1+a_2b_2+a_1b_3$$ $$c_4=a_3b_2+a_2b_3$$ $$c_5=a_3b_3$$

where $c_1,...,c_5$ are known.

The goal is to solve for the elements of $\mathbf{b}$.

Obv this can be done by hand for small $n$ but I am hoping someone can tell me the fastest method to do this for large $n$. Preferably something that doesn't require writing an iterative solver in R or a huge system of equations in Mathematica.

Answer 1

Note that in general, this gives us the system of equations $M\mathbf b = \mathbf c$, where $$ M = \pmatrix{ a_1\\ a_2&a_1\\ a_3&a_2&a_1 \\ \vdots&\ddots &&\ddots\\ a_n & a_{n-1} & \cdots &a_2& a_1\\ & a_{n} & \ddots & a_3 & a_2\\ & & a_n & & \vdots\\ \\ & & & &a_n}. $$ Because $M$ is a Sylvester matrix, your problem has a very nice interpretation in terms of polynomials. Let $p(x) = a_1 + a_2x + \cdots + a_n x^{n-1}$, $f(x) = c_1 + c_2 x^2 + \cdots + c_{2n-1} x^{2n-1}$, and $q(x) = b_1 + b_2 x + \cdots + b_n x^{n-1}$. If $\mathbf b, \mathbf c$ solve your system of equations, then it follows that $q(x) = p(x)f(x)$.

In other words, your problem amounts to the following: given $f(x)$ and a factor $p(x)$ of $f(x)$, find $\frac{f(x)}{p(x)}$. For computations by hand, this answer is usually computed via polynomial long division.