Suppose that ${\bf A} \in \Bbb R^{n \times n}$ is invertible, ${\bf b} \in \Bbb R^{n}$. Knowing a solution of ${\bf A} {\bf x}_1 = {\bf b}$, find a solution for ${\bf A}^\top {\bf x}_2 = {\bf b}$. Express ${\bf x}_2$ without inverting $\bf A$.
This question isn't my homework. It's related with my programming problem. I'm not even sure whether this problem is solvable.
I don't see any way to do it. Of course you can write $$x_2 = A^{-T}Ax_1$$ but unless $A$ has a special form (is orthogonal, for instance) I don't see any way to compute the right-hand side without solving a linear system. You have that $$x_1 \cdot b = x_2 \cdot b$$ which does characterize $x_2$ in one dimension, but not higher.
(Naturally you never materialize an inverse matrix in numerical methods... you would use LU decomposition or another matrix solver to solve $$A^T x_2 = Ax_1$$ for $x_2$.)