Inverse of matrix of ones + nI

Question

Having a vector $\mathbf{1} \in \mathbb{R}^{n}$ containing only ones, following equality should be true according to a paper I am currently reading:

\begin{equation} \left( nI+\mathbf{1}\mathbf{1}^T \right)^{-1}= \frac{1}{n}\left( I - \frac{1}{2n} \mathbf{1}\mathbf{1}^T \right) \end{equation}

EDIT: what is the general rule for constructing an inverse of a matrix with $n$ on diagonal and $1$ elsewhere and how is this rule derived?

Answer 1

As mentioned in one of the comments, you should consider using the Sherman-Morrison formula or the Woodbury identity which states that for a nonsingular matrix $A$ and column vectors $ b, c$ such that $ {A+bc^\top}$ is nonsingular,

$$( {A+bc^\top})^{-1}={A^{-1}}-\frac{1}{1+{c^\top A^{-1}b}} {A^{-1}bc^\top A^{-1}}$$

Therefore,

\begin{align} (n I+\mathbf{11}^\top)^{-1}&=\frac{1}{n} I-\frac{1}{1+\frac{1}{n}{ 1^\top 1}}\frac{1}{n^2}\mathbf{11}^\top \\&=\frac{1}{n} I-\frac{1}{n+n}\frac{1}{n}\mathbf{11}^\top \\&=\frac{1}{n}\left( I-\frac{1}{2n}\mathbf{11}^\top\right) \end{align}

---

To see how the general formula is derived, first note that

$$\det (A+bc^\top)\ne 0 \implies 1+{c^\top A^{-1}b}\ne 0$$

Suppose $A$ is of order $p\times p$, and $b$ and ${c}$ are both $p\times 1$ column vectors.

Let $$d={A+bc^\top}$$

Then,

\begin{align} {dA^{-1}}&={I_p}+{bc^\top A^{-1}} \\\\&\implies {dA^{-1}b}=b+{bc^\top A^{-1}b}= b (1+{c^\top A^{-1}b}) \\\\&\implies ({dA^{-1}b})(1+{c^\top A^{-1}b})^{-1}=b \\\\&\implies ({dA^{-1}b})(1+{c^\top A^{-1}b})^{-1} c^\top={bc^\top} \\\\&\implies A+({dA^{-1}b})(1+{c^\top A^{-1}b})^{-1} c^\top= A+{bc^\top}= d \\\\&\implies A= d (1-{A^{-1}b}(1+{c^\top A^{-1}b})^{-1} c^\top) \\\\&\implies {I_p}= d (1-{A^{-1}b}(1+{c^\top A^{-1}b})^{-1} c^\top){A^{-1}} \\\\&\implies {d^{-1}}=(1-{A^{-1}b}(1+{c^\top A^{-1}b})^{-1} c^\top){A^{-1}} \end{align}

That is,

\begin{align} ( {A+bc^\top})^{-1}&={A^{-1}}-{A^{-1}b}(1+{c^\top A^{-1}b})^{-1} c^\top{A^{-1}} \\\\&={A^{-1}}-\dfrac{1}{1+{c^\top A^{-1}b}} {A^{-1}bc^\top A^{-1}} \end{align}

Answer 2

Notice that the matrix $$P=\frac{11^T}{n}$$ is an orthoprojector, meaning $P^2=P=P^T$.

Such matrices are also called idempotent, and they have just 2 distinct eigenvalues $\{0,1\},\,$ since those are the only 2 idempotent scalars.

You wish to evaluate the function $$f(x)=(n+nx)^{-1}$$ with a matrix argument of $P$, i.e. $$f(P)=(nI+nP)^{-1}$$

Now the nice thing about an idempotent matrix is that the power series for any function only has 2 terms $$f(P) = c_0I+c_1P$$ Using Sylvester Interpolation, substitute each eigenvalue into the function and into the power series $$\eqalign{ f(1) &= \frac{1}{2n} &= c_0+c_1 \cr f(0) &= \frac{1}{n} &= c_0 \cr }$$ and solve for the coefficients.

Looks like $c_0$ is already "solved", and the remaining coefficient is simply $$c_1 = \frac{1}{2n}-\frac{1}{n} =-\frac{1}{2n}$$ Therefore $$\eqalign{ f(P) &= \frac{1}{n}I-\frac{1}{2n}P \cr &= \frac{1}{n}\Big(I-\frac{1}{2}P\Big) \cr &= \frac{1}{n}\Big(I-\frac{1}{2n}11^T\Big) \cr\cr }$$

Update

Since you can't find anything on Sylvester interpolation, let me work out a second example.

Let's say that you wanted to calculate the exponential rather than the inverse of your matrix. $$\exp(nI+11^T)=\exp(nI+nP)$$ This corresponds to the scalar function $$f(x)=\exp(n+nx)$$ We have the same 2-term series expansion as last time $$f(P)=c_0I+c_1P$$ Substituting the eigenvalues yields $$\eqalign{ f(1) &= e^{n+1} &= c_0+c_1 \cr f(0) &= e^n &= c_0 \cr }$$ Once again, the $c_0$ is "solved" and the remaining coefficient is $$c_1=e^{n+1}-e^{n}=e^{n}(e-1)$$ Therefore we have $$\eqalign{ \exp(nI+11^T) &= e^{n}I+e^{n}(e-1)P \cr &= e^{n}\Big(I+\frac{e-1}{n}11^T\Big) \cr }$$

Answer 3

Example

Example for $n=5$: $$ \mathbf{A}(n) = \left( \begin{array}{ccccc} 6 & 1 & 1 & 1 & 1 \\ 1 & 6 & 1 & 1 & 1 \\ 1 & 1 & 6 & 1 & 1 \\ 1 & 1 & 1 & 6 & 1 \\ 1 & 1 & 1 & 1 & 6 \\ \end{array} \right), \qquad \mathbf{A}^{-1}(n) = \frac{1}{50} \left( \begin{array}{rrrrr} 9 & -1 & -1 & -1 & -1 \\ -1 & 9 & -1 & -1 & -1 \\ -1 & -1 & 9 & -1 & -1 \\ -1 & -1 & -1 & 9 & -1 \\ -1 & -1 & -1 & -1 & 9 \\ \end{array} \right) $$

Result

In general, $$ \mathbf{A}_{r,c}(n) = \begin{cases} 1 & r\ne c \\ n+1 & r = c \end{cases} \qquad \mathbf{A}^{-1}_{r,c}(n) = \begin{cases} -\frac{1}{2n^{2}} & r\ne c \\ \frac{2n-1}{2n^{2}} & r = c \end{cases} $$

Proof strategy: induction

To compute the inverse matrix, $$ \mathbf{A}^{-1} = \frac{\text{adj } \mathbf{A}} {\det \mathbf{A}} $$ where the adjugate matrix, $\text{adj } \mathbf{A}$, is the transpose of the matrix of cofactors.

1. Establish $\det \mathbf{A}(n) = 2n^{-2}$.

2. Establish the matrix of minors is an $n\times n$ matrix of the form $$ \left[ \begin{array}{rrrr} \alpha & \beta & -\beta & \dots \\ \beta & \alpha & \beta & \dots \\ -\beta & \beta & \alpha \\ \vdots & \vdots & & \ddots \end{array} \right] $$ with $$ \alpha = \left(2n-1 \right) n^{n-2}, \qquad \beta = n^{n-2} $$