Matrix Differentiation and First-order Spectral Perturbation

For the sum map, $(A+H)+B=(A+B)+H$, so the linear term is already $H$. For the adjoint map, $(A+H{)}^{\ast }=A^{\ast }+H^{\ast }$, so the linear term is $H^{\ast }$. Both have zero remainder in the sense of [F1].

For the product map, $(A+H)(B+K)=AB+HB+AK+HK\mathrm{.}$ The bilinear term $HK$ satisfies $\mathrm{\parallel }HK{\mathrm{\parallel }}_F\le \mathrm{\parallel }H{\mathrm{\parallel }}_F\mathrm{\parallel }K{\mathrm{\parallel }}_F=o(\mathrm{\parallel }(H,K)\mathrm{\parallel })$, so [F1] identifies the derivative as $(H,K)\mapsto HB+AK$. This is exactly the product rule.

Because $A$ is invertible, $\det (A)\mathrm{\ne }0$. Since $\det (A+K)$ is a polynomial in the real coordinates of $K$ with value $\det (A)$ at $K=0$, there is $\epsilon >0$ such that $A+K$ is invertible whenever $\mathrm{\parallel }K{\mathrm{\parallel }}_F<\epsilon$. For such $K$, the identities $(A+K{)}^{-1}(A+K)=I=A^{-1}A$ give $(A+K{)}^{-1}-A^{-1}=-A^{-1}K(A+K{)}^{-1},$ and hence $((A+K{)}^{-1}-A^{-1})+A^{-1}K{A}^{-1}=A^{-1}K{A}^{-1}K(A+K{)}^{-1}\mathrm{.}$

Shrink $\epsilon$ so that $\mathrm{\parallel }{A}^{-1}{\mathrm{\parallel }}_2\mathrm{\parallel }K{\mathrm{\parallel }}_F\le \frac{1}{2}$ whenever $\mathrm{\parallel }K{\mathrm{\parallel }}_F<\epsilon$. From step 1.1, $\mathrm{\parallel }(A+K{)}^{-1}{\mathrm{\parallel }}_2\le \mathrm{\parallel }{A}^{-1}{\mathrm{\parallel }}_2+\mathrm{\parallel }{A}^{-1}{\mathrm{\parallel }}_2\mathrm{\parallel }K{\mathrm{\parallel }}_F\mathrm{\parallel }(A+K{)}^{-1}{\mathrm{\parallel }}_2,$ so $\mathrm{\parallel }(A+K{)}^{-1}{\mathrm{\parallel }}_2\le 2\mathrm{\parallel }{A}^{-1}{\mathrm{\parallel }}_2$. Applying this bound to the second identity in step 1.1 yields $\parallel (A+K{)}^{-1}-A^{-1}+A^{-1}K{A}^{-1}{\parallel }_F\le 2\mathrm{\parallel }{A}^{-1}{\mathrm{\parallel }}_2^3\mathrm{\parallel }K{\mathrm{\parallel }}_F^2=o(\mathrm{\parallel }K{\mathrm{\parallel }}_F)\mathrm{.}$ Therefore inversion is real Fr'echet differentiable at $A$ with derivative $K\mapsto -A^{-1}K{A}^{-1}$.

Differentiating the identity $A{A}^{-1}=I$ and using the product rule [L1] gives $H{A}^{-1}+AD\mathrm{inv}(A)[H]=0.$ Left-multiplying by $A^{-1}$ recovers $D\mathrm{inv}(A)[H]=-A^{-1}H{A}^{-1},$ which is the formula claimed in the statement.

The determinant is multilinear in the columns. In $\det (A+tH)$, the coefficient of $t$ comes from replacing exactly one column of $A$ by the corresponding column of $H$. Those cofactors are precisely the entries of $\mathrm{adj}(A)$, so $D\det (A)[H]=\mathrm{tr}(\mathrm{adj}(A)H)$.

If $A$ is invertible, then $\mathrm{adj}(A)=\det (A)A^{-1}$. Substituting this identity into step 1.1 gives $D\det (A)[H]=\det (A)\mathrm{tr}(A^{-1}H)$, which is Jacobi's formula on the invertible locus. The domain restriction matters because $A^{-1}$ appears explicitly there, unlike the adjugate formula of step 1.1.

The trace is linear, so $\mathrm{tr}(A+H)-\mathrm{tr}(A)=\mathrm{tr}(H)$. Likewise, ${\mathrm{\Phi }}_B(A+H)-{\mathrm{\Phi }}_B(A)=\mathrm{Re}\mathrm{tr}(B^{\ast }H)\mathrm{.}$ Each increment is already linear in $H$.

Therefore [F1] gives the displayed derivatives. The Frobenius gradient is the unique matrix $G$ satisfying $D{\mathrm{\Phi }}_B(A)[H]=\mathrm{Re}\mathrm{tr}(G^{\ast }H)$ for every $H$, and step 1.1 shows that $G=B$.

Expanding at $x+h$ gives $q(x+h)=\frac{1}{2}\mathrm{\parallel }Cx+Ch{\mathrm{\parallel }}_2^2=\frac{1}{2}\mathrm{\parallel }Cx{\mathrm{\parallel }}_2^2+\mathrm{Re}⟨Cx,Ch⟩+\frac{1}{2}\mathrm{\parallel }Ch{\mathrm{\parallel }}_2^2\mathrm{.}$ Hence $Dq(x)[h]=\mathrm{Re}⟨C^{\ast }Cx,h⟩,$ so the gradient is $C^{\ast }Cx$.

The derivative of the gradient map $x\mapsto C^{\ast }Cx$ is the constant linear map $h\mapsto C^{\ast }Ch$. Therefore the Hessian is $C^{\ast }C$.

Write $f(x)=\frac{1}{2}\mathrm{\parallel }A(x-A^{+}b){\mathrm{\parallel }}_2^2+\text{constant}$ only heuristically; directly, $f(x+h)-f(x)=\frac{1}{2}\mathrm{\parallel }Ax-b+Ah{\mathrm{\parallel }}_2^2-\frac{1}{2}\mathrm{\parallel }Ax-b{\mathrm{\parallel }}_2^2\mathrm{.}$ Expanding yields $Df(x)[h]=\mathrm{Re}⟨Ax-b,Ah⟩=\mathrm{Re}⟨A^{\ast }(Ax-b),h⟩\mathrm{.}$

The gradient map from step 1.1 is $x\mapsto A^{\ast }(Ax-b)$, whose derivative is the constant linear map $h\mapsto A^{\ast }Ah$. Thus the Hessian is $A^{\ast }A$.

Assume for contradiction that $y^{\ast }x=0$. Then $x\in \ker y^{\ast }$. Also $y^{\ast }(A-\lambda I)=0$, so $\mathrm{range}(A-\lambda I)\subseteq \ker y^{\ast }$. Because $\lambda$ is simple, $\mathrm{rank}(A-\lambda I)=n-1$ and $\dim \ker y^{\ast }=n-1$, hence $\mathrm{range}(A-\lambda I)=\ker y^{\ast }$. Therefore $x=(A-\lambda I)z$ for some $z$.

Step 1.1 gives $(A-\lambda I{)}^{2}z=0$ while $(A-\lambda I)z=x\mathrm{\ne }0$, so $z$ starts a Jordan chain of length $2$ for $\lambda$. That contradicts the simplicity of $\lambda$. Hence $y^{\ast }x\mathrm{\ne }0$. Scaling $x$ by $(y^{\ast }x{)}^{-1}$ yields the normalization $y^{\ast }x=1$.

By [F1], one has $y^{\ast }x\mathrm{\ne }0$. Since also $\alpha ,\beta \mathrm{\ne }0$, the rescaled denominator satisfies ${\tilde{y}}^{\ast }\tilde{x}=\bar{\beta }\alpha y^{\ast }x\mathrm{\ne }0.$ Therefore the rescaled projector is well defined, and using [F1] again gives $\frac{\tilde{x}{\tilde{y}}^{\ast }}{{\tilde{y}}^{\ast }\tilde{x}}=\frac{(\alpha x)(\bar{\beta }{y}^{\ast })}{\bar{\beta }\alpha y^{\ast }x}=\frac{x{y}^{\ast }}{y^{\ast }x}=P\mathrm{.}$

Thus nonzero rescaling changes numerator and denominator by the same nonzero factor and leaves the spectral projector unchanged.

Every vector $v$ decomposes uniquely as $v=(y^{\ast }v)x+(v-(y^{\ast }v)x)$, with the second term in $\ker y^{\ast }$. If $z\in \ker y^{\ast }$ and $(A-\lambda I)z=0$, then $z$ is a right eigenvector for the simple eigenvalue $\lambda$, so $z=cx$ for some scalar $c$. Applying $y^{\ast }$ gives $0=y^{\ast }z=c{y}^{\ast }x=c$, hence $z=0$. Therefore the restriction of $A-\lambda I$ to $\ker y^{\ast }$ is injective, and since both domain and codomain have dimension $n-1$, it is bijective.

Define $S$ to be the inverse of that restriction on $\ker y^{\ast }$ and to vanish on $\mathrm{span}\{x\}$. Then $SP=PS=0$ by construction. For $v=\alpha x+z$ with $z\in \ker y^{\ast }$, [F1] gives $Pv=(y^{\ast }v)x=(\alpha +y^{\ast }z)x=\alpha x$, so $(I-P)v=z$. Therefore $S(A-\lambda I)v=S(A-\lambda I)z=z=(I-P)v$, and similarly $(A-\lambda I)Sv=(A-\lambda I)Sz=z=(I-P)v$. Thus all displayed identities hold.

If $S^{\mathrm{\prime }}$ is another linear map with the same identities, then $S^{\mathrm{\prime }}x=0$ because $S^{\mathrm{\prime }}P=0$ and $Px=x$. On $\ker y^{\ast }$ one has $(A-\lambda I)S^{\mathrm{\prime }}z=z=(A-\lambda I)Sz$, and the injectivity from step 1.1 gives $S^{\mathrm{\prime }}z=Sz$. Hence $S^{\mathrm{\prime }}=S$, so the reduced resolvent of The reduced resolvent, or group inverse, on the complementary invariant subspace of a simple eigenvalue is well defined and unique.

Consider the real map $F(A,\lambda ,x)=((A-\lambda I)x,y_0^{\ast }x-1)$. Its derivative in $(\lambda ,x)$ at $(A_0,{\lambda }_0,x_0)$ is $(\mu ,h)\mapsto ((A_0-{\lambda }_{0}I)h-\mu x_0,y_0^{\ast }h)$. If this derivative vanishes, then left-multiplying the first component by $y_0^{\ast }$ gives $-\mu y_0^{\ast }{x}_0=0$, hence $\mu =0$ by [L1]. Then $(A_0-{\lambda }_{0}I)h=0$ and $y_0^{\ast }h=0$, so $h$ is a multiple of $x_0$ whose pairing with $y_0$ is zero; therefore $h=0$. Thus the derivative is injective. Because domain and codomain have the same real dimension, it is invertible.

The hypotheses of [L2] now apply to $F$ at $(A_0,{\lambda }_0,x_0)$. Therefore there are neighborhoods and unique $C^1$ maps $A\mapsto \lambda (A)$ and $A\mapsto x(A)$ solving $F(A,\lambda (A),x(A))=0$. Those equations are exactly $Ax(A)=\lambda (A)x(A)$ and $y_0^{\ast }x(A)=1$, with the required base values.

Differentiate the eigenvalue equation $A(t)x(t)=\lambda (t)x(t)$: $A^{\mathrm{\prime }}(t)x(t)+A(t)x^{\mathrm{\prime }}(t)={\lambda }^{\mathrm{\prime }}(t)x(t)+\lambda (t)x^{\mathrm{\prime }}(t)\mathrm{.}$ Left-multiply by $y(t{)}^{\ast }$. Since $y(t{)}^{\ast }A(t)=\lambda (t)y(t{)}^{\ast }$, the terms with $x^{\mathrm{\prime }}(t)$ cancel.

Step 1.1 leaves $y(t{)}^{\ast }{A}^{\mathrm{\prime }}(t)x(t)={\lambda }^{\mathrm{\prime }}(t)y(t{)}^{\ast }x(t)$. The normalization $y(t{)}^{\ast }x(t)=1$ therefore gives ${\lambda }^{\mathrm{\prime }}(t)=y(t{)}^{\ast }{A}^{\mathrm{\prime }}(t)x(t)$.

Normalize first so that $y^{\ast }x=1$. Then [L1] gives $\mathrm{\mid }D\lambda (A)[H]\mathrm{\mid }=\mathrm{\mid }{y}^{\ast }Hx\mathrm{\mid }\le \mathrm{\parallel }y{\mathrm{\parallel }}_2\mathrm{\parallel }H{\mathrm{\parallel }}_2\mathrm{\parallel }x{\mathrm{\parallel }}_2$ by Cauchy-Schwarz. Taking the supremum over $\mathrm{\parallel }H{\mathrm{\parallel }}_2=1$ in [F1] yields $\kappa (\lambda ;A)\le \mathrm{\parallel }x{\mathrm{\parallel }}_2\mathrm{\parallel }y{\mathrm{\parallel }}_2$.

Let $u=y\mathrm{/}\mathrm{\parallel }y{\mathrm{\parallel }}_2$ and $v=x\mathrm{/}\mathrm{\parallel }x{\mathrm{\parallel }}_2$, and define $H=u{v}^{\ast }$. Then $\mathrm{\parallel }H{\mathrm{\parallel }}_2=1$ and $y^{\ast }Hx=\mathrm{\parallel }y{\mathrm{\parallel }}_2\mathrm{\parallel }x{\mathrm{\parallel }}_2$. Hence [F1] and [L1] give the reverse inequality, so $\kappa (\lambda ;A)=\mathrm{\parallel }x{\mathrm{\parallel }}_2\mathrm{\parallel }y{\mathrm{\parallel }}_2$ under the normalization $y^{\ast }x=1$. Undoing the normalization inserts the factor $\mathrm{\mid }{y}^{\ast }x{\mathrm{\mid }}^{-1}$ and gives the general formula.

Differentiate $(A-\lambda I)P=0$ at $t=0$: $(A^{\mathrm{\prime }}(0)-{\lambda }^{\mathrm{\prime }}(0)I)P+(A-\lambda I)P^{\mathrm{\prime }}=0.$ Left-multiplying by $S$ and using [L1] together with $SP=0$ gives $(I-P)P^{\mathrm{\prime }}=-S{A}^{\mathrm{\prime }}(0)P\mathrm{.}$ Differentiating $P(A-\lambda I)=0$ and right-multiplying by $S$ similarly gives $P^{\mathrm{\prime }}(I-P)=-P{A}^{\mathrm{\prime }}(0)S\mathrm{.}$

Differentiating $P^2=P$ gives $P^{\mathrm{\prime }}=P^{\mathrm{\prime }}P+P{P}^{\mathrm{\prime }}$. Because $P{P}^{\mathrm{\prime }}P=0$, this decomposes as $P^{\mathrm{\prime }}=(I-P)P^{\mathrm{\prime }}P+P{P}^{\mathrm{\prime }}(I-P)$. Substituting the two identities from step 1.1 yields $P^{\mathrm{\prime }}=-S{A}^{\mathrm{\prime }}(0)P-P{A}^{\mathrm{\prime }}(0)S,$ which is the claimed formula.

Differentiate $(A-\lambda I)x=0$ at $t=0$: $(A^{\mathrm{\prime }}(0)-{\lambda }^{\mathrm{\prime }}(0)I)x+(A-\lambda I)x^{\mathrm{\prime }}=0.$ Apply $S$ and use [L1]: $x^{\mathrm{\prime }}-P{x}^{\mathrm{\prime }}=-S(A^{\mathrm{\prime }}(0)-{\lambda }^{\mathrm{\prime }}(0)I)x\mathrm{.}$ Because the fixed gauge gives $y_0^{\ast }{x}^{\mathrm{\prime }}(0)=0$, the derivative $x^{\mathrm{\prime }}(0)$ lies in $\ker y_0^{\ast }$, so $P{x}^{\mathrm{\prime }}(0)=x(y_0^{\ast }{x}^{\mathrm{\prime }}(0))=0$.

Step 1.1 therefore gives $x^{\mathrm{\prime }}(0)=-S(A^{\mathrm{\prime }}(0)-{\lambda }^{\mathrm{\prime }}(0)I)x(0)$. Since $Sx(0)=0$ by [L1], the ${\lambda }^{\mathrm{\prime }}(0)$ term disappears and $x^{\mathrm{\prime }}(0)=-S{A}^{\mathrm{\prime }}(0)x(0)$.

If $A(t)=A(t{)}^{\ast }$ and $A(t)x(t)=\lambda (t)x(t)$, then taking adjoints shows $x(t{)}^{\ast }A(t)=\lambda (t)x(t{)}^{\ast }$. Thus the same unit eigenvector can serve as both left and right eigenvector. Multiplying $x(t)$ by a unit complex phase if necessary imposes the gauge $x(t{)}^{\ast }{x}^{\mathrm{\prime }}(t)=0$.

Substitute $y=x$ into the formulas summarized in [L1]. This gives ${\lambda }^{\mathrm{\prime }}(t)=x(t{)}^{\ast }{A}^{\mathrm{\prime }}(t)x(t)$ and, in the chosen gauge, $x^{\mathrm{\prime }}(0)=-S{A}^{\mathrm{\prime }}(0)x(0)$.

Form the Hermitian block path $B(t):=\left(\begin{array}{cc}0& A+tH\\ (A+tH{)}^{\ast }& 0\end{array}\right)\mathrm{.}$ Then $w=\frac{1}{\sqrt{2}}(u,v{)}^{\mathsf{T}}$ is a unit eigenvector of $B(0)$ with eigenvalue $\sigma$, because $B(0)w=\frac{1}{\sqrt{2}}(Av,A^{\ast }u{)}^{\mathsf{T}}=\frac{1}{\sqrt{2}}(\sigma u,\sigma v{)}^{\mathsf{T}}=\sigma w\mathrm{.}$ If $B(0)(x,y{)}^{\mathsf{T}}=\sigma (x,y{)}^{\mathsf{T}}$, then $Ay=\sigma x$ and $A^{\ast }x=\sigma y$, so $A^{\ast }Ay={\sigma }^{2}y$. Since $\sigma$ is a simple positive singular value, the eigenspace of $A^{\ast }A$ for ${\sigma }^2$ is one-dimensional, and then $x={\sigma }^{-1}Ay$ is determined by $y$. Hence $\sigma$ is a simple eigenvalue of the Hermitian matrix $B(0)$.

Because $t\mapsto B(t)$ is differentiable and step 1.1 shows that $\sigma$ is a simple eigenvalue of $B(0)$, [L2] gives a local $C^1$ eigenvalue branch through $\sigma$. The derivative of the block path is $B^{\mathrm{\prime }}(0)=\left(\begin{array}{cc}0& H\\ H^{\ast }& 0\end{array}\right)\mathrm{.}$ Applying [L1] to this Hermitian simple eigenvalue branch gives $D\sigma (A)[H]=w^{\ast }{B}^{\mathrm{\prime }}(0)w\mathrm{.}$

Expanding the quadratic form from step 2.1 gives $D\sigma (A)[H]=\frac{1}{2}(u^{\ast }Hv+v^{\ast }{H}^{\ast }u)=\mathrm{Re}(u^{\ast }Hv)\mathrm{.}$