# Inverse of matrix of ones + nI

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?

• You are taking the inverse of $\left( n\mathbf{I}+\mathbf{1}\mathbf{1}^T \right)$, not of $\left(\mathbf{1}\mathbf{1}^T \right)$. The first matrix has $2n$ on the main diagonal and $n$ elsewhere.
– mlc
Mar 25, 2017 at 17:44
• @mlc oh yeah, that's true, but how do I calculate the inverse on the right side of the equation knowing this fact? Mar 25, 2017 at 17:55
• to check the formula try to multiply the matrices with each other and see if you obtain the identity matrix.
– Surb
Mar 25, 2017 at 18:02
• In other words: $$(nI+\mathbf{11}^T)(I-\frac{1}{2n}\mathbf{11}^T)=nI+\mathbf{11}^T-\frac{n}{2n}\mathbf{11}^T-\frac{1}{2n}\mathbf{11}^T\mathbf{11}^T\\ =nI+\mathbf{11}^T-\frac{1}{2}\mathbf{11}^T-\frac{1}{2n}(\mathbf{1^T1})\mathbf{11}^T\\ = nI+\mathbf{11}^T-\frac{1}{2}\mathbf{11}^T-\frac{1}{2}\mathbf{11}^T= nI$$
– Surb
Mar 25, 2017 at 18:05
• Look up the Woodbury formula. It is used to compute the inverse of a matrix that has been updated by adding a product of matrices to it Mar 25, 2017 at 21:18

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}

• Yeah, I also just did the calculations as @NickAlger mentioned in his comment and got the same result. I would accept his answer as the correct one, but as you are the one who did post it as an answer, I guess I need to accept yours then. Thanks! Mar 26, 2017 at 11:31

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 }

• Thank you for this explanation, but I still got some questions on this. $P=n^{-1} \mathbf{1}\mathbf{1}^T$ is being an idempotent matrix, as well as $I-P$ is. (Applied Multivariate Analysis, Timm Neil, p. 30) But how is $nI + nP$ or $I + P$ idempotent as well? I also don't understand the Sylvester Interpolation where you say $f(1)= \dots = c_0 + c_1$. How are we getting this from $c_o I + c_1 P$? I never heard of Sylvester Interpolation and after some reading still didn't get how it's possible here. Mar 26, 2017 at 10:39
• @zunder I added another example of Sylvester interpolation to my answer. Also note that it does not depend on the properties of $(mI+nP)$ or any other combination of matrices. It only depends on the properties of $P$ itself. So functions must be formulated as $f(P)$ to make use of this method.
– greg
Mar 26, 2017 at 14:52

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}$$

• Thank you, that looks like what I am after. Do you also have a source for the general property somewhere? Or how to derive it? Mar 25, 2017 at 18:29
• This may help: math.stackexchange.com/questions/525334/… Mar 25, 2017 at 19:33