We wish to find A such that $$ (D_1+L_1)A(D_2+L_2^T)=L_1^TAL_2 + D_1^{1/2}D_2^{1/2} $$ where $D_i$ are diagonal matrices and $L_i$ are strict lower triangular matrices with zero diagonal entries. Is it possible obtain an expression for the matrix (A) in closed form?

More generally, given $B,C$ is it possible solve for A (if solutions exist) equations of the form $BAB^T-A=C$?


1 Answer 1


We consider the linear equation $(*)$ $BXB^T-X=C$ in the unknown $X$.

Let $spectrum(B)=(\lambda_i)_i$. Then $(*)$ can be rewritten

$\phi(X)=(B\otimes B-I_{n^2})(X)=C$ -if we stack the matrices row by row into vectors- (cf. https://en.wikipedia.org/wiki/Kronecker_product).

Then $spectrum(\phi)=(\lambda_i\lambda_j-1)_{i,j}$. For a generic $B$ (for example, choose it randomly), the eigenvalues of $\phi$ are non-zero and it's a bijection. Thus $X$ exists and is unique. There exists softwares that solve this type of linear equation in $O(n^3)$.

EDIT. Answer to the OP. There is no closed form of the solution. When $\rho(B)<1$ (the $|\lambda_i|$ are $<1$), there is a norm s.t. $||B||<1$ and the solution, in analytic form, is $X=-\sum_{i=0}^{\infty} (B^i\otimes B^i)(C)$.

Yet, this form is not interesting because the complexity of the calculation of each term $(B^i\otimes B^i)(C)$ is $O(n^4)$.

  • $\begingroup$ Ok, thank you. I was checking whether an analytic answer was available but this is helpful too. $\endgroup$
    – user212273
    Apr 13, 2020 at 15:25

You must log in to answer this question.