Map to symmetric matrices is surjective. 
Let $M_{k,n}$ be the set of all $k\times n$ matrices, $S_k$ be the set of all symmetric $k\times k$ matrices, and $I_k$ the identity $k\times k$ matrix. Suppose $A\in M_{k,n}$ is such that $AA^t=I_k$. Let $f:M_{k,n}\rightarrow S_k$ be the map $f(B)=BA^t+AB^t$. Prove that $f$ is onto (surjective). (Note: all matrices have entries in $\mathbb{R}$.)

Clearly the matrix $BA^t+AB^t$ is symmetric, since $$(BA^t+AB^t)^t=(BA^t)^t+(AB^t)^t=AB^t+BA^t.$$
We want to show that for every $C\in S_k$, there exists $B\in M_{k,n}$ such that $$C=BA^t+AB^t.$$
How can we do that?
 A: Let $B = \frac{1}{2}CA \in M_{k, n}$.
A: First observation: $C=BA^t+AB^t=BA^t+(BA^t)^t$. Also, since $C$ is a symmetric matrix, there is an upper-triangular matrix $U$ such that $C=U+U^t$ (just take the $C$'s entries for the off-diagonal entries, and take a half of $C$'s diagonal entries). 
Therefore it is enough to prove that for any $k\times k$ upper-triangular matrix $U$, there exists $B\in M_{k,n}$ such that $U=BA^t$. 
Let $U$ be an arbitrary but fixed $k\times k$ upper-triangular matrix. Because $AA^t=I_k$, $(UA)A^t=U$. Take $B=UA$, and we are through. 
A: In fact it is sufficient that $A$ has maximal rank, that is, since $n\geq k$, $rank(A)=k$. Consequently $AA^T$ is SPD and we may assume that $AA^T=D=diag((\lambda_i)_i)$ where $\lambda_i>0$. We want to find a solution in $B$ of $C=BA^T+AB^T$. Put $B=EA$. Then we seek a $k\times k$ matrix $E$ s.t. $C=E(AA^T)+(AA^T)E=ED+DE^T$. There is a solution in $E=[e_{i,j}]$ that is symmetric.
Indeed $C=ED+DE$ is equivalent to $e_{i,j}=\dfrac{c_{i,j}}{\lambda_i+\lambda_j}$.
