# Inverse of a diagonal matrix plus a constant

I am looking for an efficient solution for inverting a matrix of the following form:

$$D+aP$$

where $D$ is a (full-rank) diagonal matrix, $a$ is a constant, and $P$ is an all-ones matrix.

Inverse of constant matrix plus diagonal matrix gives a solution to the special case where all diagonal entries of $D$ are the same.

The Sherman-Morrison formula is also capable of providing a solution to this problem by setting appropriate $u$ and $v$, but it loses efficiency ($O(n^3)$ time complexity to compute) at high dimension. I am hoping to get a result in the same form so the space and time complexity are both $O(n)$.

• I don't think that the inverse of a matrix of the form $D + aP$ is of the same form in general. – J. J. Sep 22 '14 at 9:19
• I guess you are right. Maybe the best I could do is to find efficient approximations. – aaronqli Sep 22 '14 at 10:01

What is wrong with using Sheman-Morrison? If $P$ is a matrix of all ones, then setting $$u=(1,\dots,1)^T, \ v = a\cdot u$$ will do the trick. The matrix-vector product $(D+\alpha P)^{-1}$ can be computed in $O(n)$. The matrix $(D+\alpha P)^{-1}$ it self in $O(n^2)$.
Edit: Here is how to evaluate $(D+\alpha P)^{-1}x$. Let $e=(1,\dots,1)^T$. By Sherman-Morrison $$\begin{split} (D+a P)^{-1}x = (D+aee^T)^{-1}x&= D^{-1}x + a\frac{D^{-1}ee^TD^{-1}}{1+ae^TD^{-1}e}x\\ &=D^{-1}x + a\frac{(D^{-1}e)(e^T(D^{-1}x))}{1+ae^T(D^{-1}e)}. \end{split}$$ The multiplication $D^{-1}y$ is $O(n)$, computing $e^Ty$ is $O(n)$, so the matrix-vector product above costs $O(n)$ operations.
To compute the inverse you can do $$(D+a P)^{-1} = D^{-1} + a\frac{(D^{-1}e)(e^TD^{-1})}{1+ae^T(D^{-1}e)}.$$ Here the costly operation is to compute the rank-one matrix $(D^{-1}e)(e^TD^{-1})$ and to add matrices. Filling a $n\times n$ matrix in $O(n^2)$ time is optimal. After all, there are $n^2$ elements that need to be written.
• Do you mean $u=a\mathbb{1}^T$? And can you explain more on how matrix-vector product is computed in $O(n)$ (I presume you mean $(D+aP)^{-1}x$ for some vector $x$?)? $O(n^2)$ is still not very efficient. – aaronqli Sep 22 '14 at 9:54