Factoring a given rank-$1$ matrix

Question

Suppose you have a $n \times 1$ column vector

$$a=\begin{bmatrix}a_1\\{a_2}\\ \vdots\\{a_n}\end{bmatrix}$$

and a $1 \times m$ row vector

$$\quad b=\begin{bmatrix}b_1 & b_2 & \ldots & b_m\end{bmatrix}$$

If you then multiply these

$$A=ab=\begin{bmatrix} a_{1}b_1 & a_{1}b_2 & \ldots & a_{1}b_m\\ a_{2}b_1 & a_{2}b_2 & \ldots & a_{2}b_m \\ \vdots&&&\vdots \\ a_{n}b_1 & a_{n}b_2 & \ldots & a_{n}b_m\end{bmatrix}$$

How difficult (if possible) is it to find the original vectors $a$ and $b$ if you are given $A$?

Answer 1

You cannot determine the original vectors $a$ and $b$, since they are not unique ($2a$ and $0.5b$ yield the same result as Rodrigo explains). However, you can construct one $a$ and $b$ such that $A=ab^T$. Just find any nonzero element in $A$. Let's assume that the (1,1) element is nonzero, but the method works in other cases too. The (1,1) element is $a_1 b_1$. Now let $a_1=1$, then you can compute $b_1$. By going through the first row and first column, you can compute all elements of the vectors $a$ and $b$.

Answer 2

Suppose I have nonzero vectors ${\bf u} \in \mathbb R^m$ and ${\bf v} \in \mathbb R^n$. I form the $m \times n$ rank-$1$ matrix

$$ {\bf A} := {\bf u} {\bf v}^{\top} $$

and tell you what $\bf A$ is. Can you reconstruct vectors $\bf u$ and $\bf v$ from matrix $\bf A$? You cannot, because

$$\left( \gamma \,{\bf u} \right) \left( \frac{1}{\gamma} {\bf v}^{\top} \right) = {\bf A}$$

for all $\gamma \neq 0$. What you can recover from $\bf A$ is two lines passing through the origin and on which $\bf u$ and $\bf v$ live. More information is needed to recover $\bf u$ and $\bf v$.

For instance, if I tell you what $\| {\bf u} \|_2$ is, then you can find where the line whose direction vector is $ {\bf u}$ intersects the Euclidean sphere of radius $\| {\bf u} \|_2$ centered at the origin. You find two points. One of them is $\bf u$ and the other is $-\bf u$, but you cannot know which is which, unfortunately. Sign ambiguity cannot be eliminated. Note that

$$(-{\bf u}) \left( -{\bf v}^{\top} \right) = {\bf A}$$

To summarize, matrix-valued function ${\bf F} ( {\bf x}, {\bf y} ) := {\bf x} {\bf y}^{\top}$ is not injective and, thus, the inputs $\bf x$ and $\bf y$ cannot be recovered from the output.

---

matrices rank-1-matrices matrix-decomposition

Answer 3

If $A$ is indeed of the form $A=ab$, then it is quite easy to recover $a,b$ up to a constant, because given any colum vector $ x \in \mathbb{R}^m$, not in $Ker(A)$, $A\,x = a (bx)$, i.e.: $a$ is $A\,x$ up to the constant $b\,x$. Likewise, given any column vector $y \in \mathbb{R}^n$, not in $Ker(A^T)$, we have $y\,A = (y\,a)b$, so $b$ is $y\,A$ up to the constant $y\,a$.