Problem
For given matrices $A$, $B$ and $C$, solve the equation
$$AXB^T = C$$
for $X$ in terms of the LU decompositions of $A$ and $B$. When are there no solutions?
Attempt at a Solution
I know that every $m×n$ matrix $D$ can be expressed in the form
$$P_1DP_2 = LU$$
where $P_1$ and $P_2$ are permutation matrices, $L$ is a unit lower triangular matrix, and $U$ has the form
$$\begin{bmatrix} U_1 & U_2 \newline 0 & 0 \newline \end{bmatrix}$$
where $U_1$ is an invertible upper triangular matrix (i.e. $U_1$ has nonzero diagonal entries) with the same rank as $D$.
Furthermore, some useful properties of permutation matrices include $P_1^{-1}=P_1^T$.
Let the LU decompositions of $A$ and $B$ be
$$P_1 A P_2 = L_A U_A, \quad Q_1 B Q_2 = L_B U_B.$$
Then we can write the matrix equation that we are supposed to solve as follows:
$$P_1^T L_A U_A P_2^T X Q_2 U_B^T L_B^T Q_1 = C.$$
My plan was to try writing this equation in the form $GY=H$ for known $G$ and $H$, and unknown $Y$ (without assuming that $U_A$ and $U_B$ are invertible). This idea leads to
$$U_A P_2^T X Q_2 U_B^T = L_A^{-1} P_1 C Q_1^T (L_B^T)^{-1} .$$
Then we can read off, for example, $$G=U_A, \quad H = L_A^{-1} P_1 C Q_1^T (L_B^T)^{-1}, \quad Y=P_2^T X Q_2 U_B^T .$$
Am I on the right track? Where do I go from here?
The general least-squares solution to the equation is $$X = A^+C(B^+)^T \;+\; (I-A^+A)M \;+\; N(I-B^+B)^T$$ where $M,N$ are arbitrary matrices and $A^+$ denotes the Moore-Penrose inverse. If you're only interested in a least-norm solution, then set $M,N$ to zero.
An exact solution exists when $AA^+=I\;\;\underline {and}\;\;B^+B=I$.
While it's true that $$\eqalign{ A = PLU \implies A^+ = U^+L^+P^T \\ }$$ the matrix $U^+$ does not retain the triangular structure of $U\,$ (ditto for $L$). So the LU decomposition won't be helpful in this situation.