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?
Best Answer
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
$\lambda_i+\lambda_j=0,c_{i,j}\not= 0$ then no solution.
$\lambda_i+\lambda_j=0,c_{i,j}= 0$ then $x_{î,j}$ is arbitrary.
$\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.