2
$\begingroup$

Given $A$ and $C$ two real symmetric matrices, solve $$ AX + XA = C $$

This equation can be solved using standard algorithm solving the Sylvester equation like the Bartels–Stewart algorithm.

But since there are additional symmetry hypothesis on $A$ and $C$ (and so on $X$), is their any easier way to solve it ?

By easier I mean is there a closed form expression of the solution?

If not, what would be a fast implementation of the algorithm in terms of number of operations?

$\endgroup$
2
  • $\begingroup$ Related: mathoverflow.net/q/339878/91764 $\endgroup$ Commented Mar 30, 2020 at 20:39
  • $\begingroup$ "But since there are additional symmetry hypothesis on $A$ and $C$ (and so on $X$)"... sorry, but $X$ is not necessarily symmetric. E.g. $AX+XA=0$ when $A=\pmatrix{1\\ &-1}$ and $X=\pmatrix{0&-1\\ 1&0}$. But surely, when the equation is solvable, there always exists a symmetric solution $X$. $\endgroup$
    – user1551
    Commented Mar 30, 2020 at 20:54

1 Answer 1

3
$\begingroup$

We can assume that $A$ is diagonal, $A=diag((\lambda_i)_i)$ (the complexity of the calculation of the eigen-elements is $\approx 20 n^3$). If $X=[x_{i,j}],C=[c_{i,j}]$, then

$(\lambda_i+\lambda_j)x_{i,j}=c_{i,j}$. Thus, if

  1. $\lambda_i+\lambda_j=0,c_{i,j}\not= 0$ then no solution.

  2. $\lambda_i+\lambda_j=0,c_{i,j}= 0$ then $x_{î,j}$ is arbitrary.

  3. $\lambda_i+\lambda_j\not= 0$ then $x_{i,j}=\dfrac{c_{i,j}}{\lambda_i+\lambda_j}$.

The complexity of the previous calculation is $O(n^2)$.

The set $S$ of solutions (if there are any) is an affine space of dimension $\#\{(i,j);\lambda_i+\lambda_j=0\}$.

Note 1. if there is at least one solution $X_0$, then $X_0^T$ and $(X_0+X_0^T)/2$ are also solutions, that is, there is always at least one symmetric solution.

Note 2. The Bartels–Stewart algorithm works only when $S$ is an empty set, that is, when there is a sole solution.

$\endgroup$

You must log in to answer this question.

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