You are currently browsing the tag archive for the ‘matrix identities’ tag.

The determinant ${\det_n(A)}$ of an ${n \times n}$ matrix (with coefficients in an arbitrary field) obey many useful identities, starting of course with the fundamental multiplicativity ${\det_n(AB) = \det_n(A) \det_n(B)}$ for ${n \times n}$ matrices ${A,B}$. This multiplicativity can in turn be used to establish many further identities; in particular, as shown in this previous post, it implies the Schur determinant identity

$\displaystyle \det_{n+k}\begin{pmatrix} A & B \\ C & D \end{pmatrix} = \det_n(A) \det_k( D - C A^{-1} B ) \ \ \ \ \ (1)$

whenever ${A}$ is an invertible ${n \times n}$ matrix, ${B}$ is an ${n \times k}$ matrix, ${C}$ is a ${k \times n}$ matrix, and ${D}$ is a ${k \times k}$ matrix. The matrix ${D - CA^{-1} B}$ is known as the Schur complement of the block ${A}$.

I only recently discovered that this identity in turn immediately implies what I always found to be a somewhat curious identity, namely the Dodgson condensation identity (also known as the Desnanot-Jacobi identity)

$\displaystyle \det_n(M) \det_{n-2}(M^{1,n}_{1,n}) = \det_{n-1}( M^1_1 ) \det_{n-1}(M^n_n)$

$\displaystyle - \det_{n-1}(M^1_n) \det_{n-1}(M^n_1)$

for any ${n \geq 3}$ and ${n \times n}$ matrix ${M}$, where ${M^i_j}$ denotes the ${n-1 \times n-1}$ matrix formed from ${M}$ by removing the ${i^{th}}$ row and ${j^{th}}$ column, and similarly ${M^{i,i'}_{j,j'}}$ denotes the ${n-2 \times n-2}$ matrix formed from ${M}$ by removing the ${i^{th}}$ and ${(i')^{th}}$ rows and ${j^{th}}$ and ${(j')^{th}}$ columns. Thus for instance when ${n=3}$ we obtain

$\displaystyle \det_3 \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix} \cdot e$

$\displaystyle = \det_2 \begin{pmatrix} e & f \\ h & i \end{pmatrix} \cdot \det_2 \begin{pmatrix} a & b \\ d & e \end{pmatrix}$

$\displaystyle - \det_2 \begin{pmatrix} b & c \\ e & f \end{pmatrix} \cdot \det_2 \begin{pmatrix} d & e \\ g & h \end{pmatrix}$

for any scalars ${a,b,c,d,e,f,g,h,i}$. (Charles Dodgson, better known by his pen name Lewis Caroll, is of course also known for writing “Alice in Wonderland” and “Through the Looking Glass“.)

The derivation is not new; it is for instance noted explicitly in this paper of Brualdi and Schneider, though I do not know if this is the earliest place in the literature where it can be found. (EDIT: Apoorva Khare has pointed out to me that the original arguments of Dodgson can be interpreted as implicitly following this derivation.) I thought it is worth presenting the short derivation here, though.

Firstly, by swapping the first and ${(n-1)^{th}}$ rows, and similarly for the columns, it is easy to see that the Dodgson condensation identity is equivalent to the variant

$\displaystyle \det_n(M) \det_{n-2}(M^{n-1,n}_{n-1,n}) = \det_{n-1}( M^{n-1}_{n-1} ) \det_{n-1}(M^n_n) \ \ \ \ \ (2)$

$\displaystyle - \det_{n-1}(M^{n-1}_n) \det_{n-1}(M^n_{n-1}).$

Now write

$\displaystyle M = \begin{pmatrix} A & B_1 & B_2 \\ C_1 & d_{11} & d_{12} \\ C_2 & d_{21} & d_{22} \end{pmatrix}$

where ${A}$ is an ${n-2 \times n-2}$ matrix, ${B_1, B_2}$ are ${n-2 \times 1}$ column vectors, ${C_1, C_2}$ are ${1 \times n-2}$ row vectors, and ${d_{11}, d_{12}, d_{21}, d_{22}}$ are scalars. If ${A}$ is invertible, we may apply the Schur determinant identity repeatedly to conclude that

$\displaystyle \det_n(M) = \det_{n-2}(A) \det_2 \begin{pmatrix} d_{11} - C_1 A^{-1} B_1 & d_{12} - C_1 A^{-1} B_2 \\ d_{21} - C_2 A^{-1} B_1 & d_{22} - C_2 A^{-1} B_2 \end{pmatrix}$

$\displaystyle \det_{n-2} (M^{n-1,n}_{n-1,n}) = \det_{n-2}(A)$

$\displaystyle \det_{n-1}( M^{n-1}_{n-1} ) = \det_{n-2}(A) (d_{22} - C_2 A^{-1} B_2 )$

$\displaystyle \det_{n-1}( M^{n-1}_{n} ) = \det_{n-2}(A) (d_{21} - C_2 A^{-1} B_1 )$

$\displaystyle \det_{n-1}( M^{n}_{n-1} ) = \det_{n-2}(A) (d_{12} - C_1 A^{-1} B_2 )$

$\displaystyle \det_{n-1}( M^{n}_{n} ) = \det_{n-2}(A) (d_{11} - C_1 A^{-1} B_1 )$

and the claim (2) then follows by a brief calculation (and the explicit form ${\det_2 \begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad-bc}$ of the ${2 \times 2}$ determinant). To remove the requirement that ${A}$ be invertible, one can use a limiting argument, noting that one can work without loss of generality in an algebraically closed field, and in such a field, the set of invertible matrices is dense in the Zariski topology. (In the case when the scalars are reals or complexes, one can just use density in the ordinary topology instead if desired.)

The same argument gives the more general determinant identity of Sylvester

$\displaystyle \det_n(M) \det_{n-k}(M^S_S)^{k-1} = \det_k \left( \det_{n-k+1}(M^{S \backslash \{i\}}_{S \backslash \{j\}}) \right)_{i,j \in S}$

whenever ${n > k \geq 1}$, ${S}$ is a ${k}$-element subset of ${\{1,\dots,n\}}$, and ${M^S_{S'}}$ denotes the matrix formed from ${M}$ by removing the rows associated to ${S}$ and the columns associated to ${S'}$. (The Dodgson condensation identity is basically the ${k=2}$ case of this identity.)

A closely related proof of (2) proceeds by elementary row and column operations. Observe that if one adds some multiple of one of the first ${n-2}$ rows of ${M}$ to one of the last two rows of ${M}$, then the left and right sides of (2) do not change. If the minor ${A}$ is invertible, this allows one to reduce to the case where the components ${C_1,C_2}$ of the matrix vanish. Similarly, using elementary column operations instead of row operations we may assume that ${B_1,B_2}$ vanish. All matrices involved are now block-diagonal and the identity follows from a routine computation.

The latter approach can also prove the cute identity

$\displaystyle \det_2 \begin{pmatrix} \det_n( X_1, Y_1, A ) & \det_n( X_1, Y_2, A ) \\ \det_n(X_2, Y_1, A) & \det_n(X_2,Y_2, A) \end{pmatrix} = \det_n( X_1,X_2,A) \det_n(Y_1,Y_2,A)$

for any ${n \geq 2}$, any ${n \times 1}$ column vectors ${X_1,X_2,Y_1,Y_2}$, and any ${n \times n-2}$ matrix ${A}$, which can for instance be found in page 7 of this text of Karlin. Observe that both sides of this identity are unchanged if one adds some multiple of any column of ${A}$ to one of ${X_1,X_2,Y_1,Y_2}$; for generic ${A}$, this allows one to reduce ${X_1,X_2,Y_1,Y_2}$ to have only the first two entries allowed to be non-zero, at which point the determinants split into ${2 \times 2}$ and ${n -2 \times n-2}$ determinants and we can reduce to the ${n=2}$ case (eliminating the role of ${A}$). One can now either proceed by a direct computation, or by observing that the left-hand side is quartilinear in ${X_1,X_2,Y_1,Y_2}$ and antisymmetric in ${X_1,X_2}$ and ${Y_1,Y_2}$ which forces it to be a scalar multiple of ${\det_2(X_1,X_2) \det_2(Y_1,Y_2)}$, at which point one can test the identity at a single point (e.g. ${X_1=Y_1 = e_1}$ and ${X_2=Y_2=e_2}$ for the standard basis ${e_1,e_2}$) to conclude the argument. (One can also derive this identity from the Sylvester determinant identity but I think the calculations are a little messier if one goes by that route. Conversely, one can recover the Dodgson condensation identity from Karlin’s identity by setting ${X_1=e_1}$, ${X_2=e_2}$ (for instance) and then permuting some rows and columns.)

Suppose ${F: X \rightarrow Y}$ is a continuous (but nonlinear) map from one normed vector space ${X}$ to another ${Y}$. The continuity means, roughly speaking, that if ${x_0, x \in X}$ are such that ${\|x-x_0\|_X}$ is small, then ${\|F(x)-F(x_0)\|_Y}$ is also small (though the precise notion of “smallness” may depend on ${x}$ or ${x_0}$, particularly if ${F}$ is not known to be uniformly continuous). If ${F}$ is known to be differentiable (in, say, the Fréchet sense), then we in fact have a linear bound of the form

$\displaystyle \|F(x)-F(x_0)\|_Y \leq C(x_0) \|x-x_0\|_X$

for some ${C(x_0)}$ depending on ${x_0}$, if ${\|x-x_0\|_X}$ is small enough; one can of course make ${C(x_0)}$ independent of ${x_0}$ (and drop the smallness condition) if ${F}$ is known instead to be Lipschitz continuous.

In many applications in analysis, one would like more explicit and quantitative bounds that estimate quantities like ${\|F(x)-F(x_0)\|_Y}$ in terms of quantities like ${\|x-x_0\|_X}$. There are a number of ways to do this. First of all, there is of course the trivial estimate arising from the triangle inequality:

$\displaystyle \|F(x)-F(x_0)\|_Y \leq \|F(x)\|_Y + \|F(x_0)\|_Y. \ \ \ \ \ (1)$

This estimate is usually not very good when ${x}$ and ${x_0}$ are close together. However, when ${x}$ and ${x_0}$ are far apart, this estimate can be more or less sharp. For instance, if the magnitude of ${F}$ varies so much from ${x_0}$ to ${x}$ that ${\|F(x)\|_Y}$ is more than (say) twice that of ${\|F(x_0)\|_Y}$, or vice versa, then (1) is sharp up to a multiplicative constant. Also, if ${F}$ is oscillatory in nature, and the distance between ${x}$ and ${x_0}$ exceeds the “wavelength” of the oscillation of ${F}$ at ${x_0}$ (or at ${x}$), then one also typically expects (1) to be close to sharp. Conversely, if ${F}$ does not vary much in magnitude from ${x_0}$ to ${x}$, and the distance between ${x}$ and ${x_0}$ is less than the wavelength of any oscillation present in ${F}$, one expects to be able to improve upon (1).

When ${F}$ is relatively simple in form, one can sometimes proceed simply by substituting ${x = x_0 + h}$. For instance, if ${F: R \rightarrow R}$ is the squaring function ${F(x) = x^2}$ in a commutative ring ${R}$, one has

$\displaystyle F(x_0+h) = (x_0+h)^2 = x_0^2 + 2x_0 h+ h^2$

and thus

$\displaystyle F(x_0+h) - F(x_0) = 2x_0 h + h^2$

or in terms of the original variables ${x, x_0}$ one has

$\displaystyle F(x) - F(x_0) = 2 x_0 (x-x_0) + (x-x_0)^2.$

If the ring ${R}$ is not commutative, one has to modify this to

$\displaystyle F(x) - F(x_0) = x_0 (x-x_0) + (x-x_0) x_0 + (x-x_0)^2.$

Thus, for instance, if ${A, B}$ are ${n \times n}$ matrices and ${\| \|_{op}}$ denotes the operator norm, one sees from the triangle inequality and the sub-multiplicativity ${\| AB\|_{op} \leq \| A \|_{op} \|B\|_{op}}$ of operator norm that

$\displaystyle \| A^2 - B^2 \|_{op} \leq \| A - B \|_{op} ( 2 \|B\|_{op} + \|A - B \|_{op} ). \ \ \ \ \ (2)$

If ${F(x)}$ involves ${x}$ (or various components of ${x}$) in several places, one can sometimes get a good estimate by “swapping” ${x}$ with ${x_0}$ at each of the places in turn, using a telescoping series. For instance, if we again use the squaring function ${F(x) = x^2 = x x}$ in a non-commutative ring, we have

$\displaystyle F(x) - F(x_0) = x x - x_0 x_0$

$\displaystyle = (x x - x_0 x) + (x_0 x - x_0 x_0)$

$\displaystyle = (x-x_0) x + x_0 (x-x_0)$

which for instance leads to a slight improvement of (2):

$\displaystyle \| A^2 - B^2 \|_{op} \leq \| A - B \|_{op} ( \| A\|_{op} + \|B\|_{op} ).$

More generally, for any natural number ${n}$, one has the identity

$\displaystyle x^n - x_0^n = (x-x_0) (x^{n-1} + x^{n-2} x_0 + \dots + x x_0^{n-2} + x_0^{n-1}) \ \ \ \ \ (3)$

in a commutative ring, while in a non-commutative ring one must modify this to

$\displaystyle x^n - x_0^n = \sum_{i=0}^{n-1} x_0^i (x-x_0) x^{n-1-i},$

and for matrices one has

$\displaystyle \| A^n - B^n \|_{op} \leq \| A-B\|_{op} ( \|A\|_{op}^{n-1} + \| A\|_{op}^{n-2} \| B\|_{op} + \dots + \|B\|_{op}^{n-1} ).$

Exercise 1 If ${U}$ and ${V}$ are unitary ${n \times n}$ matrices, show that the commutator ${[U,V] := U V U^{-1} V^{-1}}$ obeys the inequality

$\displaystyle \| [U,V] - I \|_{op} \leq 2 \| U - I \|_{op} \| V - I \|_{op}.$

(Hint: first control ${\| UV - VU \|_{op}}$.)

Now suppose (for simplicity) that ${F: {\bf R}^d \rightarrow {\bf R}^{d'}}$ is a map between Euclidean spaces. If ${F}$ is continuously differentiable, then one can use the fundamental theorem of calculus to write

$\displaystyle F(x) - F(x_0) = \int_0^1 \frac{d}{dt} F( \gamma(t) )\ dt$

where ${\gamma: [0,1] \rightarrow Y}$ is any continuously differentiable path from ${x_0}$ to ${x}$. For instance, if one uses the straight line path ${\gamma(t) := (1-t) x_0 + tx}$, one has

$\displaystyle F(x) - F(x_0) = \int_0^1 ((x-x_0) \cdot \nabla F)( (1-t) x_0 + t x )\ dt.$

In the one-dimensional case ${d=1}$, this simplifies to

$\displaystyle F(x) - F(x_0) = (x-x_0) \int_0^1 F'( (1-t) x_0 + t x )\ dt. \ \ \ \ \ (4)$

Among other things, this immediately implies the factor theorem for ${C^k}$ functions: if ${F}$ is a ${C^k({\bf R})}$ function for some ${k \geq 1}$ that vanishes at some point ${x_0}$, then ${F(x)}$ factors as the product of ${x-x_0}$ and some ${C^{k-1}}$ function ${G}$. Another basic consequence is that if ${\nabla F}$ is uniformly bounded in magnitude by some constant ${C}$, then ${F}$ is Lipschitz continuous with the same constant ${C}$.

Applying (4) to the power function ${x \mapsto x^n}$, we obtain the identity

$\displaystyle x^n - x_0^n = n (x-x_0) \int_0^1 ((1-t) x_0 + t x)^{n-1}\ dt \ \ \ \ \ (5)$

which can be compared with (3). Indeed, for ${x_0}$ and ${x}$ close to ${1}$, one can use logarithms and Taylor expansion to arrive at the approximation ${((1-t) x_0 + t x)^{n-1} \approx x_0^{(1-t) (n-1)} x^{t(n-1)}}$, so (3) behaves a little like a Riemann sum approximation to (5).

Exercise 2 For each ${i=1,\dots,n}$, let ${X^{(1)}_i}$ and ${X^{(0)}_i}$ be random variables taking values in a measurable space ${R_i}$, and let ${F: R_1 \times \dots \times R_n \rightarrow {\bf R}^m}$ be a bounded measurable function.

• (i) (Lindeberg exchange identity) Show that

$\displaystyle \mathop{\bf E} F(X^{(1)}_1,\dots,X^{(1)}_n) - \mathop{\bf E} F(X^{(0)}_1,\dots,X^{(0)}_n)$

$\displaystyle = \sum_{i=1}^n \mathop{\bf E} F( X^{(1)}_1,\dots, X^{(1)}_{i-1}, X^{(1)}_i, X^{(0)}_{i+1}, \dots, X^{(0)}_n)$

$\displaystyle - \mathop{\bf E} F( X^{(1)}_1,\dots, X^{(1)}_{i-1}, X^{(0)}_i, X^{(0)}_{i+1}, \dots, X^{(0)}_n).$

• (ii) (Knowles-Yin exchange identity) Show that

$\displaystyle \mathop{\bf E} F(X^{(1)}_1,\dots,X^{(1)}_n) - \mathop{\bf E} F(X^{(0)}_1,\dots,X^{(0)}_n)$

$\displaystyle = \int_0^1 \sum_{i=1}^n \mathop{\bf E} F( X^{(t)}_1,\dots, X^{(t)}_{i-1}, X^{(1)}_i, X^{(t)}_{i+1}, \dots, X^{(t)}_n)$

$\displaystyle - \mathop{\bf E} F( X^{(t)}_1,\dots, X^{(t)}_{i-1}, X^{(0)}_i, X^{(t)}_{i+1}, \dots, X^{(t)}_n)\ dt,$

where ${X^{(t)}_i = 1_{I_i \leq t} X^{(0)}_i + 1_{I_i > t} X^{(1)}_i}$ is a mixture of ${X^{(0)}_i}$ and ${X^{(1)}_i}$, with ${I_1,\dots,I_n}$ uniformly drawn from ${[0,1]}$ independently of each other and of the ${X^{(0)}_1,\dots,X^{(0)}_n, X^{(1)}_0,\dots,X^{(1)}_n}$.

• (iii) Discuss the relationship between the identities in parts (i), (ii) with the identities (3), (5).

(The identity in (i) is the starting point for the Lindeberg exchange method in probability theory, discussed for instance in this previous post. The identity in (ii) can also be used in the Lindeberg exchange method; the terms in the right-hand side are slightly more symmetric in the indices ${1,\dots,n}$, which can be a technical advantage in some applications; see this paper of Knowles and Yin for an instance of this.)

Exercise 3 If ${F: {\bf R}^d \rightarrow {\bf R}^{d'}}$ is continuously ${k}$ times differentiable, establish Taylor’s theorem with remainder

$\displaystyle F(x) = \sum_{j=0}^{k-1} \frac{1}{j!} (((x-x_0) \cdot \nabla)^j F)( x_0 )$

$\displaystyle + \int_0^1 \frac{(1-t)^{k-1}}{(k-1)!} (((x-x_0) \cdot \nabla)^k F)((1-t) x_0 + t x)\ dt.$

If ${\nabla^k F}$ is bounded, conclude that

$\displaystyle |F(x) - \sum_{j=0}^{k-1} \frac{1}{j!} (((x-x_0) \cdot \nabla)^j F)( x_0 )|$

$\displaystyle \leq \frac{|x-x_0|^k}{k!} \sup_{y \in {\bf R}^d} |\nabla^k F(y)|.$

For real scalar functions ${F: {\bf R}^d \rightarrow {\bf R}}$, the average value of the continuous real-valued function ${(x - x_0) \cdot \nabla F((1-t) x_0 + t x)}$ must be attained at some point ${t}$ in the interval ${[0,1]}$. We thus conclude the mean-value theorem

$\displaystyle F(x) - F(x_0) = ((x - x_0) \cdot \nabla F)((1-t) x_0 + t x)$

for some ${t \in [0,1]}$ (that can depend on ${x}$, ${x_0}$, and ${F}$). This can for instance give a second proof of fact that continuously differentiable functions ${F}$ with bounded derivative are Lipschitz continuous. However it is worth stressing that the mean-value theorem is only available for real scalar functions; it is false for instance for complex scalar functions. A basic counterexample is given by the function ${e(x) := e^{2\pi i x}}$; there is no ${t \in [0,1]}$ for which ${e(1) - e(0) = e'(t)}$. On the other hand, as ${e'}$ has magnitude ${2\pi}$, we still know from (4) that ${e}$ is Lipschitz of constant ${2\pi}$, and when combined with (1) we obtain the basic bounds

$\displaystyle |e(x) - e(y)| \leq \min( 2, 2\pi |x-y| )$

which are already very useful for many applications.

Exercise 4 Let ${H_0, V}$ be ${n \times n}$ matrices, and let ${t}$ be a non-negative real.

• (i) Establish the Duhamel formula

$\displaystyle e^{t(H_0+V)} = e^{tH_0} + \int_0^t e^{(t-s) H_0} V e^{s (H_0+V)}\ ds$

$\displaystyle = e^{tH_0} + \int_0^t e^{(t-s) (H_0+V)} V e^{s H_0}\ ds$

where ${e^A}$ denotes the matrix exponential of ${A}$. (Hint: Differentiate ${e^{(t-s) H_0} e^{s (H_0+V)}}$ or ${e^{(t-s) (H_0+V)} e^{s H_0}}$ in ${s}$.)

• (ii) Establish the iterated Duhamel formula

$\displaystyle e^{t(H_0+V)} = e^{tH_0} + \sum_{j=1}^k \int_{0 \leq t_1 \leq \dots \leq t_j \leq t}$

$\displaystyle e^{(t-t_j) H_0} V e^{(t_j-t_{j-1}) H_0} V \dots e^{(t_2-t_1) H_0} V e^{t_1 H_0}\ dt_1 \dots dt_j$

$\displaystyle + \int_{0 \leq t_1 \leq \dots \leq t_{k+1} \leq t}$

$\displaystyle e^{(t-t_{k+1}) (H_0+V)} V e^{(t_{k+1}-t_k) H_0} V \dots e^{(t_2-t_1) H_0} V e^{t_1 H_0}\ dt_1 \dots dt_{k+1}$

for any ${k \geq 0}$.

• (iii) Establish the infinitely iterated Duhamel formula

$\displaystyle e^{t(H_0+V)} = e^{tH_0} + \sum_{j=1}^\infty \int_{0 \leq t_1 \leq \dots \leq t_j \leq t}$

$\displaystyle e^{(t-t_j) H_0} V e^{(t_j-t_{j-1}) H_0} V \dots e^{(t_2-t_1) H_0} V e^{t_1 H_0}\ dt_1 \dots dt_j.$

• (iv) If ${H(t)}$ is an ${n \times n}$ matrix depending in a continuously differentiable fashion on ${t}$, establish the variation formula

$\displaystyle \frac{d}{dt} e^{H(t)} = (F(\mathrm{ad}(H(t))) H'(t)) e^{H(t)}$

where ${\mathrm{ad}(H)}$ is the adjoint representation ${\mathrm{ad}(H)(V) = HV - VH}$ applied to ${H}$, and ${F}$ is the function

$\displaystyle F(z) := \int_0^1 e^{sz}\ ds$

(thus ${F(z) = \frac{e^z-1}{z}}$ for non-zero ${z}$), with ${F(\mathrm{ad}(H(t)))}$ defined using functional calculus.

We remark that further manipulation of (iv) of the above exercise using the fundamental theorem of calculus eventually leads to the Baker-Campbell-Hausdorff-Dynkin formula, as discussed in this previous blog post.

Exercise 5 Let ${A, B}$ be positive definite ${n \times n}$ matrices, and let ${Y}$ be an ${n \times n}$ matrix. Show that there is a unique solution ${X}$ to the Sylvester equation

$\displaystyle AX + X B = Y$

which is given by the formula

$\displaystyle X = \int_0^\infty e^{-tA} Y e^{-tB}\ dt.$

In the above examples we had applied the fundamental theorem of calculus along linear curves ${\gamma(t) = (1-t) x_0 + t x}$. However, it is sometimes better to use other curves. For instance, the circular arc ${\gamma(t) = \cos(\pi t/2) x_0 + \sin(\pi t/2) x}$ can be useful, particularly if ${x_0}$ and ${x}$ are “orthogonal” or “independent” in some sense; a good example of this is the proof by Maurey and Pisier of the gaussian concentration inequality, given in Theorem 8 of this previous blog post. In a similar vein, if one wishes to compare a scalar random variable ${X}$ of mean zero and variance one with a Gaussian random variable ${G}$ of mean zero and variance one, it can be useful to introduce the intermediate random variables ${\gamma(t) := (1-t)^{1/2} X + t^{1/2} G}$ (where ${X}$ and ${G}$ are independent); note that these variables have mean zero and variance one, and after coupling them together appropriately they evolve by the Ornstein-Uhlenbeck process, which has many useful properties. For instance, one can use these ideas to establish monotonicity formulae for entropy; see e.g. this paper of Courtade for an example of this and further references. More generally, one can exploit curves ${\gamma}$ that flow according to some geometrically natural ODE or PDE; several examples of this occur famously in Perelman’s proof of the Poincaré conjecture via Ricci flow, discussed for instance in this previous set of lecture notes.

In some cases, it is difficult to compute ${F(x)-F(x_0)}$ or the derivative ${\nabla F}$ directly, but one can instead proceed by implicit differentiation, or some variant thereof. Consider for instance the matrix inversion map ${F(A) := A^{-1}}$ (defined on the open dense subset of ${n \times n}$ matrices consisting of invertible matrices). If one wants to compute ${F(B)-F(A)}$ for ${B}$ close to ${A}$, one can write temporarily write ${F(B) - F(A) = E}$, thus

$\displaystyle B^{-1} - A^{-1} = E.$

Multiplying both sides on the left by ${B}$ to eliminate the ${B^{-1}}$ term, and on the right by ${A}$ to eliminate the ${A^{-1}}$ term, one obtains

$\displaystyle A - B = B E A$

and thus on reversing these steps we arrive at the basic identity

$\displaystyle B^{-1} - A^{-1} = B^{-1} (A - B) A^{-1}. \ \ \ \ \ (6)$

For instance, if ${H_0, V}$ are ${n \times n}$ matrices, and we consider the resolvents

$\displaystyle R_0(z) := (H_0 - z I)^{-1}; \quad R_V(z) := (H_0 + V - zI)^{-1}$

then we have the resolvent identity

$\displaystyle R_V(z) - R_0(z) = - R_V(z) V R_0(z) \ \ \ \ \ (7)$

as long as ${z}$ does not lie in the spectrum of ${H_0}$ or ${H_0+V}$ (for instance, if ${H_0}$, ${V}$ are self-adjoint then one can take ${z}$ to be any strictly complex number). One can iterate this identity to obtain

$\displaystyle R_V(z) = \sum_{j=0}^k (-R_0(z) V)^j R_0(z) + (-R_V(z) V) (-R_0(z) V)^k R_0(z)$

for any natural number ${k}$; in particular, if ${R_0(z) V}$ has operator norm less than one, one has the Neumann series

$\displaystyle R_V(z) = \sum_{j=0}^\infty (-R_0(z) V)^j R_0(z).$

Similarly, if ${A(t)}$ is a family of invertible matrices that depends in a continuously differentiable fashion on a time variable ${t}$, then by implicitly differentiating the identity

$\displaystyle A(t) A(t)^{-1} = I$

in ${t}$ using the product rule, we obtain

$\displaystyle (\frac{d}{dt} A(t)) A(t)^{-1} + A(t) \frac{d}{dt} A(t)^{-1} = 0$

and hence

$\displaystyle \frac{d}{dt} A(t)^{-1} = - A(t)^{-1} (\frac{d}{dt} A(t)) A(t)^{-1}$

(this identity may also be easily derived from (6)). One can then use the fundamental theorem of calculus to obtain variants of (6), for instance by using the curve ${\gamma(t) = (1-t) A + tB}$ we arrive at

$\displaystyle B^{-1} - A^{-1} = \int_0^1 ((1-t)A + tB)^{-1} (A-B) ((1-t)A + tB)^{-1}\ dt$

assuming that the curve stays entirely within the set of invertible matrices. While this identity may seem more complicated than (6), it is more symmetric, which conveys some advantages. For instance, using this identity it is easy to see that if ${A, B}$ are positive definite with ${A>B}$ in the sense of positive definite matrices (that is, ${A-B}$ is positive definite), then ${B^{-1} > A^{-1}}$. (Try to prove this using (6) instead!)

Exercise 6 If ${A}$ is an invertible ${n \times n}$ matrix and ${u, v}$ are ${n \times 1}$ vectors, establish the Sherman-Morrison formula

$\displaystyle (A + t uv^T)^{-1} = A^{-1} - \frac{t}{1 + t v^T A^{-1} u} A^{-1} uv^T A^{-1}$

whenever ${t}$ is a scalar such that ${1 + t v^T A^{-1} u}$ is non-zero. (See also this previous blog post for more discussion of these sorts of identities.)

One can use the Cauchy integral formula to extend these identities to other functions of matrices. For instance, if ${F: {\bf C} \rightarrow {\bf C}}$ is an entire function, and ${\gamma}$ is a counterclockwise contour that goes around the spectrum of both ${H_0}$ and ${H_0+V}$, then we have

$\displaystyle F(H_0+V) = \frac{-1}{2\pi i} \int_\gamma F(z) R_V(z)\ dz$

and similarly

$\displaystyle F(H_0) = \frac{-1}{2\pi i} \int_\gamma F(z) R_0(z)\ dz$

and hence by (7) one has

$\displaystyle F(H_0+V) - F(H_0) = \frac{1}{2\pi i} \int_\gamma F(z) R_V(z) V F_0(z)\ dz;$

similarly, if ${H(t)}$ depends on ${t}$ in a continuously differentiable fashion, then

$\displaystyle \frac{d}{dt} F(H(t)) = \frac{1}{2\pi i} \int_\gamma F(z) (H(t) - zI)^{-1} H'(t) (z) (H(t)-zI)^{-1}\ dz$

as long as ${\gamma}$ goes around the spectrum of ${H(t)}$.

Exercise 7 If ${H(t)}$ is an ${n \times n}$ matrix depending continuously differentiably on ${t}$, and ${F: {\bf C} \rightarrow {\bf C}}$ is an entire function, establish the tracial chain rule

$\displaystyle \frac{d}{dt} \hbox{tr} F(H(t)) = \hbox{tr}(F'(H(t)) H'(t)).$

In a similar vein, given that the logarithm function is the antiderivative of the reciprocal, one can express the matrix logarithm ${\log A}$ of a positive definite matrix by the fundamental theorem of calculus identity

$\displaystyle \log A = \int_0^\infty (I + sI)^{-1} - (A + sI)^{-1}\ ds$

(with the constant term ${(I+tI)^{-1}}$ needed to prevent a logarithmic divergence in the integral). Differentiating, we see that if ${A(t)}$ is a family of positive definite matrices depending continuously on ${t}$, that

$\displaystyle \frac{d}{dt} \log A(t) = \int_0^\infty (A(t) + sI)^{-1} A'(t) (A(t)+sI)^{-1}\ dt.$

This can be used for instance to show that ${\log}$ is a monotone increasing function, in the sense that ${\log A> \log B}$ whenever ${A > B > 0}$ in the sense of positive definite matrices. One can of course integrate this formula to obtain some formulae for the difference ${\log A - \log B}$ of the logarithm of two positive definite matrices ${A,B}$.

To compare the square root ${A^{1/2} - B^{1/2}}$ of two positive definite matrices ${A,B}$ is trickier; there are multiple ways to proceed. One approach is to use contour integration as before (but one has to take some care to avoid branch cuts of the square root). Another to express the square root in terms of exponentials via the formula

$\displaystyle A^{1/2} = \frac{1}{\Gamma(-1/2)} \int_0^\infty (e^{-tA} - I) t^{-1/2} \frac{dt}{t}$

where ${\Gamma}$ is the gamma function; this formula can be verified by first diagonalising ${A}$ to reduce to the scalar case and using the definition of the Gamma function. Then one has

$\displaystyle A^{1/2} - B^{1/2} = \frac{1}{\Gamma(-1/2)} \int_0^\infty (e^{-tA} - e^{-tB}) t^{-1/2} \frac{dt}{t}$

and one can use some of the previous identities to control ${e^{-tA} - e^{-tB}}$. This is pretty messy though. A third way to proceed is via implicit differentiation. If for instance ${A(t)}$ is a family of positive definite matrices depending continuously differentiably on ${t}$, we can differentiate the identity

$\displaystyle A(t)^{1/2} A(t)^{1/2} = A(t)$

to obtain

$\displaystyle A(t)^{1/2} \frac{d}{dt} A(t)^{1/2} + (\frac{d}{dt} A(t)^{1/2}) A(t)^{1/2} = \frac{d}{dt} A(t).$

This can for instance be solved using Exercise 5 to obtain

$\displaystyle \frac{d}{dt} A(t)^{1/2} = \int_0^\infty e^{-sA(t)^{1/2}} A'(t) e^{-sA(t)^{1/2}}\ ds$

and this can in turn be integrated to obtain a formula for ${A^{1/2} - B^{1/2}}$. This is again a rather messy formula, but it does at least demonstrate that the square root is a monotone increasing function on positive definite matrices: ${A > B > 0}$ implies ${A^{1/2} > B^{1/2} > 0}$.

Several of the above identities for matrices can be (carefully) extended to operators on Hilbert spaces provided that they are sufficiently well behaved (in particular, if they have a good functional calculus, and if various spectral hypotheses are obeyed). We will not attempt to do so here, however.

### Recent Comments

 Anonymous on Polymath15, ninth thread: goin… 译 & 评 （陶哲轩：要有耐心）… on Be flexible 译 & 评 （陶哲轩：要有耐心）… on Be patient Fausto di Biase on Ultraproducts as a Bridge Betw… Anonymous on Ask yourself dumb questions –… Five methods to lear… on Learn and relearn your fi… rudolph01 on Polymath15, ninth thread: goin… rudolph01 on Polymath proposal: upper bound… Anonymous on 254A, Notes 3a: Eigenvalues an… majdoddin on 1% quasimorphisms and group… OneGuy on 1% quasimorphisms and group… majdoddin on 1% quasimorphisms and group… adityaguharoy on IMO 2009 Q6 mini-polymath proj… KM on Polymath15, ninth thread: goin… Anonymous on 1% quasimorphisms and group…