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?
