# How to undo linear combinations of a vector

If $v$ is a row vector and $A$ a matrix, the product $w = v A$ can be seen as a vector containing a number of linear combinations of the columns of vector $v$. For instance, if $$v = \begin{bmatrix}1, 2\end{bmatrix}, \quad A = \begin{bmatrix}0 & 0 & 0 \\ 1 & 1 & 1\end{bmatrix}, \quad w = vA = \begin{bmatrix}2, 2, 2\end{bmatrix}$$ read by columns, the matrix $A$ is saying: make 3 combinations of the columns of vector $v$, each of which consists of taking 0 times the first column and 1 time the second column.

Now, the goal is to reconstruct, to the extent of possible, vector $v$ from $A$ and $w$, in other words to find a vector $v'$ such that $$v'A = w .$$

Two things to consider:

• The matrix $A$ can have any number of columns and may or may not be square or invertible.

• There are times when elements of the original vector can't be known, because $w$ contains no information about them. In the previous example, this would be the case of $v_1$. In this case, we would accept any value of $v'_1$ as correct.

How would you approach this problem? Can $v'$ be found doing simple operations with $w$ and $A$ or do I have to invent an algorithm specifically for the purpose?

-
Least squares? Side remark: Is there any particular reason you are using row vectors? –  wj32 Nov 4 '12 at 11:09
Least squares does indeed work, but not always because $A^{T}A$ may be singular. There is no particular reason I'm using row vectors. –  Ernest A Nov 4 '12 at 12:29
Well, not just least squares, but something like the Moore-Penrose pseudoinverse. (Probably not computationally efficient.) –  wj32 Nov 4 '12 at 12:32

Given $A$ and $b$, you are trying to solve for $x$ in $xA=b$. This is just solving a system of linear equations, and the usual methods apply. Well, usually the problem is presented as $Ax=b$, but that just means instead of doing elementary row operations you'll be doing elementary column operations. Or, you could take the transpose and solve $A^tx^t=b^t$, and then you'd be back in line with the rest of us.
The OP wants to know what to do when $A$ isn't invertible. –  wj32 Nov 4 '12 at 12:03
@wj32 Solving a system doesn't require $A$ to be invertible. –  EuYu Nov 4 '12 at 12:08
@wj32, yes --- what's your point? The usual methods for solving $Ax=b$ (that is, reduction to row echelon form) do not rely on $A$ being invertible, or even square. –  Gerry Myerson Nov 4 '12 at 12:08