1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Note: 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}. $$ $M$ is a Sylvester matrix, and can be interpreted in terms of polynomials. $\endgroup$ Apr 21 '20 at 1:18
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.