Is there an efficient way to calculate the inverse of an $N \times N$ diagonal matrix plus a constant matrix? I am looking at $N$ of around $40,000$.
$$\left[\begin{array}{cccc}
a & b & \cdots & b\\
b & a & & \vdots\\
\vdots & & \ddots & b\\
b & \cdots & b & a
\end{array}\right]^{-1} = \,\,?$$
Putting this in to mathematica, for $N \in \{2, 3, 4\}$, the result is:
$$\left[
\begin{array}{cc}
a & b \\
b & a \\
\end{array}
\right]^{-1}
=
\left[
\begin{array}{cc}
\frac{a}{a^2-b^2} & -\frac{b}{a^2-b^2} \\
-\frac{b}{a^2-b^2} & \frac{a}{a^2-b^2} \\
\end{array}
\right]$$
$$\left[
\begin{array}{ccc}
a & b & b \\
b & a & b \\
b & b & a \\
\end{array}
\right]^{-1}
=
\left[
\begin{array}{ccc}
\frac{a^2-b^2}{a^3-3 a b^2+2 b^3} & \frac{-a b+b^2}{a^3-3 a b^2+2 b^3} & \frac{-a b+b^2}{a^3-3 a b^2+2 b^3} \\
\frac{-a b+b^2}{a^3-3 a b^2+2 b^3} & \frac{a^2-b^2}{a^3-3 a b^2+2 b^3} & \frac{-a b+b^2}{a^3-3 a b^2+2 b^3} \\
\frac{-a b+b^2}{a^3-3 a b^2+2 b^3} & \frac{-a b+b^2}{a^3-3 a b^2+2 b^3} & \frac{a^2-b^2}{a^3-3 a b^2+2 b^3} \\
\end{array}
\right]$$
$$\left[
\begin{array}{cccc}
a & b & b & b \\
b & a & b & b \\
b & b & a & b \\
b & b & b & a \\
\end{array}
\right]^{-1}
=
\left[
\begin{array}{cccc}
\frac{a^3-3 a b^2+2 b^3}{a^4-6 a^2 b^2+8 a b^3-3 b^4} & \frac{-a^2 b+2 a b^2-b^3}{a^4-6 a^2 b^2+8 a b^3-3 b^4} & \frac{-a^2 b+2 a b^2-b^3}{a^4-6
a^2 b^2+8 a b^3-3 b^4} & \frac{-a^2 b+2 a b^2-b^3}{a^4-6 a^2 b^2+8 a b^3-3 b^4} \\
\frac{-a^2 b+2 a b^2-b^3}{a^4-6 a^2 b^2+8 a b^3-3 b^4} & \frac{a^3-3 a b^2+2 b^3}{a^4-6 a^2 b^2+8 a b^3-3 b^4} & \frac{-a^2 b+2 a b^2-b^3}{a^4-6
a^2 b^2+8 a b^3-3 b^4} & \frac{-a^2 b+2 a b^2-b^3}{a^4-6 a^2 b^2+8 a b^3-3 b^4} \\
\frac{-a^2 b+2 a b^2-b^3}{a^4-6 a^2 b^2+8 a b^3-3 b^4} & \frac{-a^2 b+2 a b^2-b^3}{a^4-6 a^2 b^2+8 a b^3-3 b^4} & \frac{a^3-3 a b^2+2 b^3}{a^4-6
a^2 b^2+8 a b^3-3 b^4} & \frac{-a^2 b+2 a b^2-b^3}{a^4-6 a^2 b^2+8 a b^3-3 b^4} \\
\frac{-a^2 b+2 a b^2-b^3}{a^4-6 a^2 b^2+8 a b^3-3 b^4} & \frac{-a^2 b+2 a b^2-b^3}{a^4-6 a^2 b^2+8 a b^3-3 b^4} & \frac{-a^2 b+2 a b^2-b^3}{a^4-6
a^2 b^2+8 a b^3-3 b^4} & \frac{a^3-3 a b^2+2 b^3}{a^4-6 a^2 b^2+8 a b^3-3 b^4} \\
\end{array}
\right]$$
It appears that there should be a formula but I am not sure how to derive it. In the end, I am looking for a numerical result.
Best Answer
You can use
$$ \textbf{P} = \left[ \begin{array}{cccc} 1 & 1 & \cdots & 1\\ 1 & 1 & \cdots & 1\\ \vdots & \vdots & \ddots & \vdots\\ 1 & 1 & \cdots & 1\\ \end{array} \right] $$
Note that
$$ \textbf{P}^2 = n \textbf{P} $$
You want the inverse of
$$ b \textbf{P} + (a-b) \textbf{I} $$
You can try
$$ k \textbf{P} + \frac{1}{a-b} \textbf{I} $$
So
$$ \Big( b \textbf{P} + (a-b) \textbf{I} \Big) \Big( k \textbf{P} + \frac{1}{a-b} \textbf{I} \Big) = \textbf{I} $$
Then we get
$$ \Big( nbk + (a-b)k + \frac{b}{a-b}\Big) \textbf{P} + \textbf{I} = \textbf{I} $$
so you can solve $k$ and you find
$$ k = \frac{-b}{(a-b)(nb+a-b)} $$
So you would get
$$ \Big( b \textbf{P} + (a-b) \textbf{I} \Big)^{-1} = \frac{-b}{(a-b)(nb+a-b)} \textbf{P} + \frac{1}{a-b} \textbf{I} {}{}{} $$