Matrix with zeros on diagonal and ones in other places is invertible

If you have studied eigenvalues and eigenvectors there is a very easy proof.

Let $A$ be your $n\times n$ matrix, with $n\ge2$. Then $A+I$ is the matrix consisting entirely of $1$s, which clearly has $n-1$ zero rows after row-reduction. Therefore $A$ has eigenvalue $-1$, repeated (at least) $n-1$ times, and since ${\rm trace}(A)=0$, the other eigenvalue is $n-1$.

Since every eigenvalue of $A$ is non-zero, the determinant of $A$ is non-zero, so $A$ is invertible.

This is easy to calculate by row reduction:

Add all rows to first: $$\det(A) =\det \begin{bmatrix} 0 & 1 & 1 &...&1 \\ 1 & 0 & 1 &...&1 \\ 1 & 1 & 0 &...&1 \\ ... & ... & ... &...&... \\ 1 & 1 & 1 &...&0 \\ \end{bmatrix}=\det \begin{bmatrix} n-1 & n-1 & n-1 &...&n-1 \\ 1 & 0 & 1 &...&1 \\ 1 & 1 & 0 &...&1 \\ ... & ... & ... &...&... \\ 1 & 1 & 1 &...&0 \\ \end{bmatrix} \\ =(n-1)\det \begin{bmatrix} 1 & 1 & 1 &...&1 \\ 1 & 0 & 1 &...&1 \\ 1 & 1 & 0 &...&1 \\ ... & ... & ... &...&... \\ 1 & 1 & 1 &...&0 \\ \end{bmatrix}=(n-1)\det \begin{bmatrix} 1 & 1 & 1 &...&1 \\ 0 & -1 & 0 &...&0 \\ 0 & 0 & -1 &...&0 \\ ... & ... & ... &...&... \\ 0 & 0 & 0 &...&-1 \\ \end{bmatrix}$$

where in the last row operation I subtracted the first row from each other row.

This shows $$\det(A)=(n-1)(-1)^{n-1}$$

Here's an alternative approach. The Woodbury matrix identity says that if we start with an invertible matrix $B$ and update it by adding a product of matrices $UCV$, then the inverse of the sum is, $$(B + U C V)^{-1} = B^{-1} - B^{-1} U (C^{-1} + V B^{-1} U)^{-1} V B^{-1}.$$ This holds whenever

1. all the matrices in the formula have sizes such that the formula makes sense, and
2. all the inverses on the right hand side in the formula exist.

The Woodbury formula can be proved by direct verification (multiply it out), and can be derived in a number of straightforward ways - see the wikipedia article linked above for more details.

Now in your situation we can take:

• $B := -I$
• $C := 1$
• $U = \mathbf{1}$, the column vector of all ones
• $V = \mathbf{1}^T$, the row vector of all ones,

so that $B + U C V = -I + \mathbf{1}\mathbf{1}^T = A$ is the matrix of all ones except on the diagonal that we wish to invert. In this case the Woodbury formula becomes,

\begin{align} (-I + \mathbf{1}\mathbf{1}^T)^{-1} &= -I - \mathbf{1}(1 - \mathbf{1}^T I \mathbf{1})^{-1}\mathbf{1}^T \\ &= -I - \mathbf{1}(1 - n)^{-1}\mathbf{1}^T \\ &= -I + \frac{1}{n-1}\mathbf{1}\mathbf{1}^T. \end{align}

So, here we have proved that the matrix is invertible for all $n$-by-$n$ matrices whenever $n > 1$ (Ie., it is not a scalar). Further we have a complete formula for the inverse, $$\boxed{A^{-1} = -I + \frac{1}{n-1}\mathbf{1}\mathbf{1}^T}$$