Finding the matrix that transforms a given input vector into a given output vector I have two vectors - the input and output. I would like to find a matrix that multiplied by the input vector gives the output vector.
What algorithms should be used? What is their complexity?
 A: So you want a matrix, which given the input vector $a$ produces the output vector $b$. 
Here is a rank-1 matrix which does that $$M=\frac{ba^T}{a^Ta}=ba^+$$ where $a^+$ is the pseudoinverse of $a$.
Later, you discover that you actually need to map a set of input vectors $\{a_k\}$ to a set of output vectors $\{b_k\}.\,\,\,$  Here is a matrix which addresses that situation $$M=BA^+$$ where $B$ is a matrix whose columns are the $\{b_k\}$ vectors, and ditto for $A$.
For a more complete solution, you can include contributions from the nullspace of $A$ 
$$M=BA^+ + G\,(I-AA^+)$$ where $G$ is an arbitrary matrix.
This solution remains valid when $A$ reverts to being the vector $a$, and is likely the answer to your original question.
A: Given an input $\mathrm a \in \mathbb R^n$ and an output $\mathrm b \in \mathbb R^m$, we would like to find $\mathrm X \in \mathbb R^{m \times n}$ such that 
$$\mathrm X \mathrm a = \mathrm b$$
Vectorizing both sides, we obtain a linear system of $m$ equations in $m n$ unknowns
$$(\mathrm a^{\top} \otimes \mathrm I_m) \, \mbox{vec} (\mathrm X) = \mathrm b$$
Since this system is underdetermined when $n > 1$, there are infinitely many solutions. Let us look for the solution with the least Frobenius norm
$$\begin{array}{ll} \text{minimize} & \| \mathrm X \|_{\text{F}}^2\\ \text{subject to} & \mathrm X \mathrm a = \mathrm b\end{array}$$
We define the Lagrangian
$$\mathcal L (\mathrm x, \lambda) := \frac 12 \| \mathrm X \|_{\text{F}}^2 - \lambda^{\top} \left( \mathrm X \mathrm a - \mathrm b \right)$$
Taking partial derivatives and finding where they vanish, we obtain
$$\mathrm X = \lambda \mathrm a^{\top} \qquad \qquad \qquad \mathrm X \mathrm a = \mathrm b$$
Right-multiplying both sides of $\mathrm X = \lambda \mathrm a^{\top}$ by vector $\mathrm a$, we obtain 
$$\lambda = \frac{\mathrm b \,\,}{\| \mathrm a \|_2^2}$$
and, thus, the least-norm solution is
$$\boxed{\mathrm X^* := \dfrac{\,\,\mathrm b \mathrm a^{\top}}{\| \mathrm a \|_2^2}}$$
