# Solutions of Matrix Equation $AXB^T = C$

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.