Sylvester and lyapunov matrix equations

By the definition of column stacking, $\mathrm{\parallel }\mathrm{vec}(X){\mathrm{\parallel }}_2^2={\sum }_{j=1}^n{\sum }_{i=1}^m\mathrm{\mid }{x}_{ij}{\mathrm{\mid }}^2=\mathrm{\parallel }X{\mathrm{\parallel }}_F^2$ by [F1]. Both sides are nonnegative, so taking square roots proves the isometry claim.

The $j$th block of $(I_n\otimes A)\mathrm{vec}(X)$ is $A{x}_j$, which is the $j$th column of $AX$. Hence $\mathrm{vec}(AX)=(I_n\otimes A)\mathrm{vec}(X)$.

The $j$th column of $XB$ is ${\sum }_{\mathrm{\ell }=1}^n{b}_{\mathrm{\ell }j}{x}_{\mathrm{\ell }}$. The $j$th block of $(B^T\otimes I_m)\mathrm{vec}(X)$ is the same sum because its $(j,\mathrm{\ell })$ block is $b_{\mathrm{\ell }j}{I}_m$. Thus $\mathrm{vec}(XB)=(B^T\otimes I_m)\mathrm{vec}(X)$.

Adding the identities in steps 1.2 and 1.3 gives the displayed Sylvester-map representation, completing both claims.

If $M=0$, then $\delta (M)=0={\sigma }_{\min }(M)$ by the definition and the singular values in [F1].

Suppose $M\mathrm{\ne }0$ and choose singular values $s_1\ge \cdots \ge s_q\ge 0$ from [F1], with $M=U\mathrm{diag}(s_1,\dots ,s_q)V^{\ast }$ for unitary $U,V$. By [F3], $\det (M)=\det (U)\det (\mathrm{diag}(s_1,\dots ,s_q))\det (V^{\ast })$; [F4] gives $\mathrm{\mid }\det (U)\mathrm{\mid }=\mathrm{\mid }\det (V^{\ast })\mathrm{\mid }=1$, and [F5] gives $\det (\mathrm{diag}(s_1,\dots ,s_q))={\prod }_{i=1}^q{s}_i$. Thus $\mathrm{\mid }\det M\mathrm{\mid }={\prod }_{i=1}^q{s}_i$. By [F2], every $s_i\le \mathrm{\parallel }M{\mathrm{\parallel }}_F$; hence $\mathrm{\mid }\det M\mathrm{\mid }\le s_q\mathrm{\parallel }M{\mathrm{\parallel }}_F^{q-1}$.

Since $s_q={\sigma }_{\min }(M)$ and $\mathrm{\parallel }M{\mathrm{\parallel }}_F>0$, divide the inequality in step 1.2 by $\mathrm{\parallel }M{\mathrm{\parallel }}_F^{q-1}$ to obtain $\delta (M)\le {\sigma }_{\min }(M)$. The lower bound $\delta (M)\ge 0$ follows from its definition.

For $0\le i,j<q$, [F1] makes the $(i,j)$ entry of $M\mathrm{adj}(M)$ equal to ${\sum }_{k=0}^{q-1}{m}_{ik}{C}_{jk}(M)$.

If $i=j$, this sum is $\det (M)$ by [F2]. If $i\mathrm{\ne }j$, let $M^{\mathrm{\prime }}$ be obtained by replacing row $j$ of $M$ with row $i$. Deleting row $j$ leaves each cofactor unchanged, so expansion of $\det (M^{\mathrm{\prime }})$ along row $j$ gives the sum in step 1.1. The matrix $M^{\mathrm{\prime }}$ has equal rows $i$ and $j$, so [F3] makes that determinant zero. Thus every diagonal entry of $M\mathrm{adj}(M)$ is $\det (M)$ and every off-diagonal entry is zero.

If $\det (M)\mathrm{\ne }0$, [F4] gives $M^{-1}$, and multiplying the identity in step 2.1 on the left by $M^{-1}\mathrm{/}\det (M)$ gives $\mathrm{adj}(M)\mathrm{/}\det (M)=M^{-1}$. If $\det (M)=0$, [F4] says $M$ is not invertible, which is exactly singularity for a square matrix.

For complex $A$, its characteristic polynomial splits by [F7], so [F2] gives $A=UT{U}^{\ast }$ with $T$ upper triangular. For real $A$, regard its same real-entry matrix as acting on ${\mathbb{C}}^n$; its characteristic polynomial also splits by [F7], so [F2] gives a unitary Schur triangularization there. If $z=x+iy$ with real $x,y$, then $\mathrm{\parallel }Az{\mathrm{\parallel }}_2^2=\mathrm{\parallel }Ax{\mathrm{\parallel }}_2^2+\mathrm{\parallel }Ay{\mathrm{\parallel }}_2^2$, so the real and complex operator norms agree.

Write $T=D+N$, where $D$ contains its diagonal and $N$ is strictly upper triangular. By [F3] and [F4], the exponential series is differentiable in operator norm for each finite matrix. The identity $(UT{U}^{\ast }{)}^k=U{T}^k{U}^{\ast }$ in each series term gives $e^{tA}=U{e}^{tT}{U}^{\ast }$; [F5] gives $\mathrm{\parallel }U{\mathrm{\parallel }}_2=\mathrm{\parallel }{U}^{\ast }{\mathrm{\parallel }}_2=1$. Each diagonal exponential satisfies $\mathrm{\parallel }{e}^{sD}{\mathrm{\parallel }}_2\le e^{-\alpha s}$ for $s\ge 0$.

Differentiate $e^{(t-s)D}{e}^{sT}$ with respect to $s$ and integrate from $0$ to $t$. Since $T-D=N$, this gives $e^{tT}=e^{tD}+{\int }_0^t{e}^{(t-s)D}N{e}^{sT}ds$. Iterating this identity produces ordered-integral terms with $k$ factors $N$ and diagonal exponentials between them. The remainder after $n$ iterations contains $n$ strictly upper-triangular factors, with diagonal factors between them and an upper-triangular exponential at the end; every nonzero matrix-entry path would have to increase its index at least $n$ times in an $n\times n$ matrix, so this remainder is zero.

The ordered simplex for $k$ integration variables has volume $t^k\mathrm{/}k!$. By [F6], each $k$th term has norm at most $e^{-\alpha t}\mathrm{\parallel }N{\mathrm{\parallel }}_2^k{t}^k\mathrm{/}k!$. Summing the terms $0\le k<n$ proves the bound for $e^{tT}$; [F5] and step 2.1 transfer it to $e^{tA}$.

If $A+pI$ were singular, its kernel would be nonzero: by [F2], a zero kernel would give full rank, hence a surjective and therefore invertible endomorphism of the finite-dimensional space. Choose nonzero $v$ in this kernel. Then $(A+pI)v=0$, so $Av=-pv$ and $-p$ would be an eigenvalue of $A$.

Since $\mathrm{Re}(-p)>0$, this contradicts [F1], which requires every eigenvalue of $A$ to have negative real part. Therefore $A+pI$ is invertible.

If $X=0$, the claimed inequality is equality. If $X\mathrm{\ne }0$, set $Y=X\mathrm{/}\mathrm{\parallel }X{\mathrm{\parallel }}_F$, so $\mathrm{\parallel }Y{\mathrm{\parallel }}_F=1$ and ${\mathcal{S}}_{A,B}(Y)={\mathcal{S}}_{A,B}(X)\mathrm{/}\mathrm{\parallel }X{\mathrm{\parallel }}_F$ by linearity.

By [F1], $\mathrm{sep}(A,-B)\le \mathrm{\parallel }{\mathcal{S}}_{A,B}(Y){\mathrm{\parallel }}_F=\mathrm{\parallel }{\mathcal{S}}_{A,B}(X){\mathrm{\parallel }}_F\mathrm{/}\mathrm{\parallel }X{\mathrm{\parallel }}_F$. Positivity of the separation permits multiplication and division by it, giving the desired bound.

First let $F=\mathbb{C}$. The characteristic polynomials of $A$ and $B$ split by [F10], so [F2] gives unitary $U,V$ and upper triangular $T,S$ with $A=UT{U}^{\ast }$ and $B=VS{V}^{\ast }$. Set $Y=U^{\ast }XV$ and $D=U^{\ast }CV$; multiplying $AX+XB=C$ on the left by $U^{\ast }$ and right by $V$ gives $TY+YS=D$, and this change of variables is invertible.

By [F1], the vectorized map for $Y\mapsto TY+YS$ is $K=I_n\otimes T+S^T\otimes I_m$. Viewed in $m$-entry column blocks, $K$ is block lower triangular because $S^T$ is lower triangular; its $j$th diagonal block is $K_j=T+s_{jj}{I}_m$, which is upper triangular with diagonal entries $t_{ii}+s_{jj}$. Recursively applying [F5] to the first diagonal block and the remaining block gives ${\chi }_K(x)={\prod }_{j=1}^n{\chi }_{K_j}(x)$. At $x=0$, [F6] and [F7] give $(-1{)}^{mn}\det K={\prod }_{j=1}^n((-1{)}^m\det K_j)$, so $\det K={\prod }_{j=1}^n\det K_j$. By [F8], $K$ is invertible exactly when every $K_j$ is invertible. Each $K_j$ is triangular, so [F9] and [F8] show it is invertible exactly when every diagonal entry $t_{ii}+s_{jj}$ is nonzero.

Since $A=UT{U}^{\ast }$ and $B=VS{V}^{\ast }$ with $U,V$ unitary, $A-\lambda I=U(T-\lambda I)U^{\ast }$ and $B-\lambda I=V(S-\lambda I)V^{\ast }$; these factors are invertible exactly when the corresponding middle factor is, so $\sigma (A)=\sigma (T)$ and $\sigma (B)=\sigma (S)$. By [F9], $\det (T-\lambda I)={\prod }_i(t_{ii}-\lambda )$ and $\det (S-\lambda I)={\prod }_j(s_{jj}-\lambda )$; [F8] therefore gives $\sigma (A)=\{t_{ii}\}$ and $\sigma (B)=\{s_{jj}\}$. Thus step 1.2 says that ${\mathcal{S}}_{A,B}$ is invertible exactly when $\sigma (A)\cap (-\sigma (B))=\mathrm{\varnothing }$.

For real $A,B$, the matrix $K=I_n\otimes A+B^T\otimes I_m$ has real entries, and its real determinant is nonzero exactly when it is nonzero over $\mathbb{C}$. Applying the complex criterion from step 2.1 to this same real matrix viewed over $\mathbb{C}$ therefore gives the same spectral condition for invertibility over $\mathbb{R}$.

A square finite-dimensional linear map is bijective exactly when every right-hand side has one solution. By [F3] and [F4], its smallest singular value is positive exactly when it is invertible. This proves all equivalences.

Put $M(t)=e^{tA}$. For finite matrices $P,R$, $\mathrm{\parallel }PR{\mathrm{\parallel }}_F^2={\sum }_j\mathrm{\parallel }PR{e}_j{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }P{\mathrm{\parallel }}_2^2{\sum }_j\mathrm{\parallel }R{e}_j{\mathrm{\parallel }}_2^2=\mathrm{\parallel }P{\mathrm{\parallel }}_2^2\mathrm{\parallel }R{\mathrm{\parallel }}_F^2$ by the operator-norm definition and [F4]. The entry formula in [F4] gives $\mathrm{\parallel }{R}^{\ast }{\mathrm{\parallel }}_F=\mathrm{\parallel }R{\mathrm{\parallel }}_F$. The SVD in [F5] gives the same positive singular values for $P$ and $P^{\ast }$; [F6] therefore gives $\mathrm{\parallel }{P}^{\ast }{\mathrm{\parallel }}_2=\mathrm{\parallel }P{\mathrm{\parallel }}_2$. Applying the left-multiplication estimate to adjoints yields $\mathrm{\parallel }RP{\mathrm{\parallel }}_F\le \mathrm{\parallel }R{\mathrm{\parallel }}_F\mathrm{\parallel }P{\mathrm{\parallel }}_2$. Applying these inequalities successively gives $\mathrm{\parallel }M(t)QM(t{)}^{\ast }{\mathrm{\parallel }}_F\le \mathrm{\parallel }M(t){\mathrm{\parallel }}_2^2\mathrm{\parallel }Q{\mathrm{\parallel }}_F$.

For $X_T={\int }_0^{T}M(t)QM(t{)}^{\ast }dt$, [F2] and the product rule give $\frac{d}{dt}(M(t)QM(t{)}^{\ast })=AM(t)QM(t{)}^{\ast }+M(t)QM(t{)}^{\ast }{A}^{\ast }$. Integrating this identity yields $A{X}_T+X_T{A}^{\ast }=M(T)QM(T{)}^{\ast }-Q$.

By [F1], the right side in step 1.1 is bounded by a finite sum of polynomial multiples of $e^{-2\alpha t}$. Each such term is integrable on $[0,\mathrm{\infty })$ by repeated integration by parts. Every entry of the integrand is therefore absolutely integrable; define $X$ by the finitely many scalar improper entry integrals. The entrywise tails tend to zero, so $X_T\to X$ in Frobenius norm and the matrix integral converges absolutely in that norm. The integrand is self-adjoint because $Q=Q^{\ast }$.

By [F1], $M(T)QM(T{)}^{\ast }\to 0$ as $T\to \mathrm{\infty }$, and by step 2.1, $X_T\to X$. Taking limits in step 1.2 gives $AX+X{A}^{\ast }=-Q$.

Suppose $Q⪰0$. By [F3], $Q^{1\mathrm{/}2}$ exists and is self-adjoint, so $Q=(Q^{1\mathrm{/}2}{)}^{\ast }{Q}^{1\mathrm{/}2}$. Hence for every $v$, $v^{\ast }Xv={\int }_0^{\mathrm{\infty }}\mathrm{\parallel }{Q}^{1\mathrm{/}2}{e}^{t{A}^{\ast }}v{\mathrm{\parallel }}_2^{2}dt\ge 0$. Thus $X⪰0$. If $Q\succ 0$ and $v\mathrm{\ne }0$, the integrand at $t=0$ is $v^{\ast }Qv>0$ and is continuous, so it stays positive on an interval of positive length; therefore $v^{\ast }Xv>0$ and $X\succ 0$.

If $Y$ is another solution, $H=Y-X$ satisfies $AH+H{A}^{\ast }=0$. The derivative of $M(t)HM(t{)}^{\ast }$ is therefore zero by [F2], so it is constant and equals $H$ at $t=0$. By [F1] it tends to zero as $t\to \mathrm{\infty }$, hence $H=0$ and the solution is unique.

For $Q⪰0$ and nonzero $v$, the continuous integrand in step 3.2 has integral zero exactly when it vanishes for all $t\ge 0$: if it were positive at one time, continuity would make its integral over a neighboring interval positive. It vanishes at time $t$ exactly when $e^{t{A}^{\ast }}v\in \ker Q^{1\mathrm{/}2}$. Hence $v^{\ast }Xv>0$ for every nonzero $v$ exactly when no nonzero trajectory remains in that kernel for all $t\ge 0$.

Put $E=X-\widehat{X}$. By linearity of ${\mathcal{S}}_{A,B}$ and the two equations, ${\mathcal{S}}_{A,B}(E)={\mathcal{S}}_{A,B}(X)-{\mathcal{S}}_{A,B}(\widehat{X})=C-(A\widehat{X}+\widehat{X}B)=R$.

Apply [F2] to $E$ and substitute step 1.1 to obtain $\mathrm{\parallel }X-\widehat{X}{\mathrm{\parallel }}_F=\mathrm{\parallel }E{\mathrm{\parallel }}_F\le \mathrm{\parallel }R{\mathrm{\parallel }}_F\mathrm{/}\mathrm{sep}(A,-B)$. The unique solution used here is guaranteed by [F3].

At $j=0$, $A{X}_0+X_0{A}^{\ast }+B{B}^{\ast }=B{B}^{\ast }=R_0{R}_0^{\ast }$ by the initialization.

Fix $j\ge 1$, write $p=p_j$, $c=c_j$, $V=V_j$, and $R=R_{j-1}$. The shifted solve gives $AV=R-pV$, and taking adjoints gives $V^{\ast }{A}^{\ast }=R^{\ast }-\bar{p}{V}^{\ast }$.

Using $c=-(p+\bar{p})$ and [F1], expand the new Lyapunov residual as $A{X}_j+X_j{A}^{\ast }+B{B}^{\ast }=A{X}_{j-1}+X_{j-1}{A}^{\ast }+B{B}^{\ast }+c((AV)V^{\ast }+V(V^{\ast }{A}^{\ast }))$. Substituting step 1.2 and [A1] yields $R{R}^{\ast }+c(R{V}^{\ast }+V{R}^{\ast })+c^{2}V{V}^{\ast }$.

The expression in step 2.1 factors as $(R+cV)(R+cV{)}^{\ast }=R_j{R}_j^{\ast }$ by [F1]. Together with base step 1.1, the induction step in 1.2–2.1 proves the identity for every completed iterate.

From [F1], $R_j=(I-2\mathrm{Re}(p_j)(A+p_{j}I{)}^{-1})R_{j-1}=(A-\overline{p_j}I)(A+p_{j}I{)}^{-1}{R}_{j-1}$, since $-2\mathrm{Re}(p_j)=-(p_j+\overline{p_j})$. All factors are rational functions of $A$ and commute, so iterating gives $R_j={\rho }_j(A)B$.

In the standard orthonormal basis, [F7] represents $A^{\ast }$ by ${\bar{A}}^{\mathsf{T}}$. For $z\in \mathbb{C}$, [F8] and [F10] give $\det (zI-A^{\ast })=\det ((zI-\bar{A}{)}^{\mathsf{T}})=\det (zI-\bar{A})$, and [F9] applied to the Leibniz formula gives $\det (zI-\bar{A})=\overline{\det (\stackrel{‾}{z}I-A)}$. Hence $\sigma (A^{\ast })=\overline{\sigma (A)}$, so both $A$ and $A^{\ast }$ have spectrum in the open left half-plane; therefore $\sigma (A)\cap (-\sigma (A^{\ast }))=\mathrm{\varnothing }$. By [F3], $\mathrm{sep}(A,-A^{\ast })>0$. Subtracting the equation for $X_j$ in [F2] from the exact equation in [F5] gives ${\mathcal{S}}_{A,A^{\ast }}(X-X_j)=-R_j{R}_j^{\ast }$.