4
$\begingroup$

What methods are there to solve the following linear matrix equation for $X$

$$AXA^T=B$$

where $X$ and $B$ are real square matrices, $X$ is symmetric and $A$ might not be square.

OBS: I could reduce the problem to a more special case in which $B$ is diagonal.

$\endgroup$
2
  • $\begingroup$ Do you want to solve for $X$? $\endgroup$ May 11, 2017 at 19:14
  • $\begingroup$ Yes, indeed. Sorry, I forgot to mention. I just edited the post. $\endgroup$
    – Thorn
    May 11, 2017 at 19:17

3 Answers 3

4
$\begingroup$

Given $\mathrm A \in \mathbb R^{m \times n}$, we have a linear matrix equation in $\mathrm X \in \mathbb R^{n \times n}$

$$\rm A X A^{\top} = B$$

Vectorizing both sides, we obtain a system of $m^2$ linear equations in $n^2$ unknowns

$$\left( \mathrm A \otimes \mathrm A \right) \mbox{vec} (\mathrm X) = \mbox{vec} (\mathrm B)$$

If $\rm X$ is symmetric, then we use half-vectorization instead, which yields a system of $m^2$ linear equations in $\binom{n+1}{2}$ unknowns

$$\left( \mathrm A \otimes \mathrm A \right) \mathrm D_n \mbox{vech} (\mathrm X) = \mbox{vec} (\mathrm B)$$

where $\rm D_n$ is the $n^2 \times \binom{n+1}{2}$ duplication matrix.

Alternatively, if $\rm X$ is symmetric, then $\mbox{vec} (\mathrm X^{\top}) = \mbox{vec} (\mathrm X)$. Using the $n^2 \times n^2$ commutation matrix $\rm K_{n^2}$, the symmetry constraint can be written in the form $(\mathrm I_{n^2} - \mathrm K_{n^2}) \, \mbox{vec} (\mathrm X) = 0_{n^2}$. Thus, we obtain an overdetermined system of $m^2 + n^2$ linear equations in $n^2$ unknowns

$$\begin{bmatrix} \mathrm A \otimes \mathrm A\\ \mathrm I_{n^2} - \mathrm K_{n^2}\end{bmatrix} \mbox{vec} (\mathrm X) = \begin{bmatrix} \mbox{vec} (\mathrm B)\\ 0_{n^2}\end{bmatrix}$$

$\endgroup$
1
  • $\begingroup$ it is nice to cast them using kron product, however, this approach is not memory efficient from a computational viewpoint compare to other methods, say do least square twice. $\endgroup$ Jul 22, 2019 at 17:47
3
$\begingroup$

With $X=(x_{ij})\in M_n(K)$ we have a system of linear equations in the variables $x_{ij}$, which can be solved by standard methods.

$\endgroup$
2
  • $\begingroup$ I am sorry, but I forgot to mention that $X$ is symmetric. $\endgroup$
    – Thorn
    May 11, 2017 at 19:20
  • $\begingroup$ Then you only need the variables $x_{ij}$ for $i\le j$, which changes nothing else for solving the linear equations. $\endgroup$ May 11, 2017 at 19:22
0
$\begingroup$

@ Thorn, your question is badly written. If $X\in M_n$ is symmetric, then necessarily $B\in M_m$ is real symmetric and we may assume that $B$ is diagonal.

Moreover $A\in M_{m,n}$ and necessarily $rank(A)\geq rank(B)$. In particular, if $m\leq n$ and $rank(A)=m$, then there are always solutions in $X$.

Proof. We consider the Moore-Penrose inverse $A^+$ of $A$; then $AA^+A=A,A^+=A^T(AA^T)^{-1},AA^+=I$. Then a particular solution is the symmetric matrix$$X_0=A^+B(A^+)^T;$$ yet, there are other symmetric solutions: $$X=X_0+(I-A^+A)W+W^T(I-A^T(A^+)^T)$$ where $W$ is any matrix (with correct dimensions). I don't know if the above formula gives all the solutions.

$\endgroup$
1
  • $\begingroup$ Thank you a lot for your answer. I know that $X$ symmetric implies $B$ symmetric. I mentioned that I can take $B$ to be diagonal because this is a small question that I needed answered for my research. I also did the Moore-Penrose inverse, but thank you a lot for the second solution found! Also, from the way the matrix $A$ is constructed in my research, it will always have $m\leq n$ and $rank(A)=m$. However, as you also pointed out, the solution is not unique, which is not very good for my research, hence I will have to go back to the drawing board. Thx a lot for all the help! $\endgroup$
    – Thorn
    May 11, 2017 at 21:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .