Solving system of linear eqaution in special cases

Question

I have to solve for $Ax=B$. Here the diagonal elements of $A$ are $-1$ and all other elements are $1$. $A$ is $n \times n$ matrix . In this special case can we solve for $x$ quickly?

EDIT: quick is in terms of asymptotic complexity.

Answer 1

Note that $A= e e^T -2I$, where $e=(1,1,...,1)^T$.

It is easy to check that $\sigma(A) = \{n-2,-2\}$, hence for $n \neq 2$, $A$ is invertible.

I will assume $n \neq 2$ subsequently.

Suppose $b = \alpha e + v$, where $v \bot e$. Then if we let $x = \frac{\alpha}{n-2} e - \frac{1}{2} v$, it is easy to check that $Ax = b$.

It is trivial to compute $\alpha = \frac{1}{n} \langle b , e \rangle$, and $v = b-\alpha e$ to get $$ x = \frac{\langle b , e \rangle}{n(n-2)} e - \frac{1}{2} (b - \frac{1}{n} \langle b , e \rangle e) = \frac{\langle b , e \rangle}{2(n-2)} e - \frac{1}{2} b$$ I count $3n+2$ flops.

Answer 2

Assume $n > 2$. Let $e = [1 \cdots 1]^T \in \mathbb R^n$. Then $A = e e^T - 2I$ and I noticed from Matlab experiments that \begin{equation} A^{-1} = \frac{e e^T - (n-2)I}{2(n-2)}. \end{equation} You can check this by multiplying it out.

It follows that \begin{equation} A^{-1} b = \frac{(e^T b) e - (n-2) b}{2(n-2)}. \end{equation}

So solving $Ax = b$ in this case requires $O(n)$ flops.