If $q\neq 0$ and $e$ are column vectors, when do we have $A$ such that $Aq=e$? Question: if $q\neq 0$ and $e$ are $n\times 1$ column vectors, when do we have $A$ ($n\times n$) such that $Aq=e$?
I've got a feeling that such $A$ always exists. Let $q_j$ be a nonzero element of $q$ and construct the $i$-th row of $A$ as ($i=1,\ldots,n$):
$$
A_i'=\begin{pmatrix}0&\ldots&\underbrace{\frac{c_i}{q_j}}_{j\text{-th position}}&\ldots&0\end{pmatrix}
$$
and let
$$
A=\begin{pmatrix}A_1'\\ \vdots \\ A_n'\end{pmatrix}\cdot
$$
Did I miss something? I've been making a lot of mistakes all morning so my confidence is shaky.

I think you're in good shape, though I didn't check the details fully. Here's another way of looking at it.
Assemble a basis $Q$ of $\mathbb{R}^n$ whose first element is $q$; call $Q$ the matrix with these columns. Do the same to make a basis of $\mathbb{R}^n$, call it $E$, whose first element is $e$. Then your $A$, written as a map from $(\mathbb{R}^n,Q)$ to $(\mathbb{R}^n,E)$, should have its first column equal to $[1,0,\dots,0]^T$. The other columns are irrelevant for your needs. Now you just need to recall how to write $A$ as a matrix in the standard basis, which is
$$A=E [A]_Q^E Q^{-1}$$
where $[A]_Q^E$ is the representation of $A$ in the bases from before.
