# rank one update

Given a matrix $X$, we can compute its matrix exponential $e^X$. Now one entry of $X$ (say $x_{i,j}$) is changed to $b$, the updated matrix is denoted by $X'$. My problem is how to compute $e^{X'}$ from $e^X$ in a fast way?

PS: I know that if our goal is to calculate the matrix inversion (not matrix exponential), we can use Sherman–Morrison formula to compute ${X'}^{-1}$ from $X^{-1}$ easily, but currently I have not found a way to deal with the matrix exponential. Hope you can give me a hand. Thanks!

-
I can't seem to find appropriate results for $\exp(\mathbf A+\mathbf u\mathbf v^\top)$. Note, however, that in practice $\exp(\cdot)$ is usually approximated by a truncation of its Taylor series or its Padé approximant, and thus a generalization of the Sherman-Morrison-Woodbury formula, due to Bernstein and Van Loan and discussed here (or see this) might be useful. – J. M. May 10 '12 at 11:10
It seems too complicated for rank-one update of $exp(\cdot)$. Is there any other simple way? – John Smith May 10 '12 at 14:33
$(A + uv^T)^n$ can simplify quite a bit, using the fact $v^T A^k u$ is a scalar (in fact, a linear recursive sequence). It's not immediately obvious if it will simplify enough that you can manipulate the Taylor series conveniently.... – Hurkyl Aug 13 '12 at 16:35

To expand on my comment, observe that

$$vw^* A^n vw^* = \left( w^* A^n v \right) vw^*$$

so in any product of $A$'s and $vw^*$'s with more than one copy of $vw^*$, we can convert the middle part to a scalar and extract it.

Applying this and grouping like terms gives the formula

\begin{align} (A + vw^*)^n = A^n + \sum_{i=0}^{n-1} A^i v w^* A^{n-1-i} + \sum_{i=0}^{n-2} \sum_{j=0}^{n-2-i} A^i v w^* A^j \left( w^* (A + vw^*)^{n-2-i-j} v \right) \end{align}

Summing this to get $\exp(A + vw^*)$, the second term yields

$$\sum_{n=1}^{+\infty} \frac{1}{n!} \sum_{i=0}^{n-1} A^i v w^* A^{n-1-i} = \sum_{i=0}^{+\infty} A^i v w^* \sum_{n=i+1}^{+\infty} \frac{1}{n!}A^{n-1-i}$$

I'm not particularly inclined to deal with truncated exponentials of $A$. :( The third term also involves truncated exponentials of $A + vw^*$.

The path forward with this idea is not clear. I only see two ideas, and both promise to be irritating:

• Try to come up with a simplified formula for all truncated exponentials, hoping the complicated terms cancel or otherwise collect together or have a nice recursion
• Use combinatorics to further simplify $w^* (A + vw^*)^{n-2-i-j} v$ and hope something nice falls out.
-

What you are looking for is the Baker–Campbell–Hausdorff formula. You are trying to compute $$e^{X+B}$$ where $B=X'-X$ has only one non-vanishing entry. If you are lucky then $X$ and $B$ commute and you can apply the standard formula $$e^{X+B}=e^X\cdot e^B,$$ where $e^B$ is easy to compute. In gnereal you will get higher terms which involve (iterated) commutators. It is then up to the form of $X$ and $B$ whether you can find suitable bounds and appoximate the series with a finite sum.

-
The likelihood of $X$ and $B$ being commutative is small. You see that Sherman–Morrison formula for matrix inversion is elegant. Is there some simple way to update $exp(\cdot)$ ? – John Smith May 10 '12 at 17:07