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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy