Inversion of an almost identity matrix

Question

Say we have a square matrix like so

1 c c c ... c
c 1 c c ... c
...
c c c c ... 1

What would be the inverse of this matrix? Calling an inv function is expensive, especially for a very large matrix. I am almost certain there's a simple formula to quickly find this inversion since the inversion also has a very similar form of

x y y y ... y
y x y y ... y
...
y y y y ... x 

Though I am not sure what the exact formula is, I appreciate any help.

Answer 1

A few examples with WA seem to indicate that the inverse of that matrix has the same form, except that the diagonal element is $-((n-2)c+1)$ and we have to divide by the determinant, which seems to be $(n-1)c^2-(n-2)c-1=(c-1)((n-1)c+1)$.

Here is the inverse for $n=5$:

This is probably easy to prove directly or using that the original matrix is a circulant matrix.

Answer 2

Assuming that the inverse matrix to $$ M_{ij}=c+(1-c)\delta_{ij}\tag1 $$ has the form: $$ M^{-1}_{ij}=y+(x-y)\delta_{ij}\tag2 $$ one easily obtains from $$ M^{-1}M=I $$ the equations: $$\begin{align} x+(n-1)y c&=1\\ x c+ y +(n-2)yc&=0 \end{align}. $$ The equations can be easily solved giving the result: $$ x=-\frac{(n-2)c+1}{(c-1)(1+(n-1)c)};\quad y=\frac{c}{(c-1)(1+(n-1)c)}, $$ which provided that $c\ne1$, $c\ne-\dfrac1{n-1} $ justifies the assumption $(2) $.