# On the solution of a generalized Lyapunov equation

We shall reconsider the following equation $$X=F_{1}XF_{1}^{T}+...+F_{p}XF_{p}^{T}+C$$ where $p$ is a positive integer and $C$ is a known symmetric positive semidefinite matrix.

I met with this problem for dealing with stability analysis for filtering problems with multiple multiplicative noise.

Recall the following property of the Kronecker product \begin{equation*} \text{vec}(AXB) = (B^T \otimes A)\text{vec}(X), \end{equation*} where the $\text{vec}(\cdot)$ stacks columns of $X$ into one long vector.

Defining now $x := \text{vec}(X)$ and $c = \text{vec}(C)$, with the above observation the original equation can be written as the following large (but highly structured) linear system:

\begin{equation*} \left(\sum\nolimits_i F_i \otimes F_i - (I \otimes I)\right)x = c. \end{equation*}

In a special case, for $i=1$, the equation reduces to the normal discrete-time Lyapunov equation, and if $F$ is stable, the solution will be symmetric positive semidefinite, i.e. $$X=F_{1}XF_{1}^{T}+C$$ with $X=\sum\nolimits_{j}^{\infty}F_{1}^{j}C(F_{1}^{T})^{j}$

My question is that, given a symmetric positive semidefinite matrix $C$, under what conditions can we find a symmetric positive semidefinite solution $X$?

• It is unusual (and frowned upon) to thank other users in questions on this site, so I have removed a couple of sentences from your post. Back to business now: you say that it is 'clear' that $X$ is positive definite under those conditions; based on what exactly? The usual criterion for positive-definiteness in the Lyapunov case ($B=A^T$, one term) is that all the eigenvalues of $A$ have negative real part, which seem different from (and contradicting with) with your proposed one. Aug 5, 2014 at 8:39
• Yep, you are right. I have edited moments ago. The condition I gave may not be correct. But the usual criterion you raised is for continuous case not for discrete one. The discrete form is the eigenvalues of $A$ fall into the unit circle. Aug 5, 2014 at 9:38
• @FedericoPoloni: thank you. meta.mathoverflow.net/questions/410/… Aug 5, 2014 at 9:46
• Ok, buddies, let's focus on the problem. I remembered that last year, Dr. Suvrit proposed a iterative method, i.e. "if ∥∑iFi\kronFi∥<1, then starting from X0=I, you can iterate Xk+1=∑iFiXkFTi+C, and converge to the unique semidefinite solution. If the operators don't satisfy this sufficient condition, then more thought is needed" Aug 5, 2014 at 9:50
• @JorisBierkens I did not know of this discussion, thanks for pointing it out. On the other hand, I find your sarcastic "thank you" slightly out of line; a simple link would have been sufficient. Aug 5, 2014 at 11:58

These sufficient conditions are, in terms of your notation: $\sum_{i=1}^p ||F_i||^2 < 1$, which looks very similar to the condition you state but is perhaps more restrictive. Unfortunately at the moment I am not too fluent in Kronecker products, so I find it difficult to compare.
• For the record, $\|F_i\otimes F_i\|=\|F_i\|^2$, so this should coincide with the bound mentioned in the comments. Aug 5, 2014 at 12:02