Invertibility of a matrix defined using inner product

Question

Let $n,m \geq 1$. We fix $n$ distinct vectors $x_1, ... , x_n \in \mathbb{R}^m$. We define $A \in \mathbb{R}^{n\times n}$ as \begin{equation} A_{ij} = x_i^T \left(n x_j - \sum_{1 \leq k \leq n} x_k \right) \end{equation} Can we show that (i) $Id + A$ is invertible and (ii) provide an explicit expression of its inverse (if it exists) in terms of the $x_i$?

Remark. For $m = 1$, we have that $A_{ij} = x_i (nx_j - \sum_k x_k)$, therefore $A = x y^T$ where $y_i = n x_i - \sum_{1 \leq k \leq n} x_k$ for $1 \leq i \leq n$. Therefore, $A$ is of rank $1$ and we have that, after simplification, \begin{equation} (Id+A)^{-1} = Id - \frac{A}{1 + y^T x} = Id - \frac{A}{1 + y^T x}, \end{equation} which is valid since $y^T x = \sum_{i\neq j} (x_i - x_j)^2 > 0$ for distinct $x_i$. Is there something similar for $m \geq 2$?

Answer 1

Let $X \in \mathbb{R}^{m \times n}$ be the matrix with columns $x_1$, $\ldots$, $x_n$. Then your matrix $A$ can be written as $$ A = X^TX(nI - J), $$ where $J$ is the $n \times n$ matrix with every entry equal to $1$. The matrices $X^TX$ and $nI-J$ are both positive semidefinite and thus have non-negative real eigenvalues. It follows that the same is true of the eigenvalues of their product $A$, so $I + A$ has all of its eigenvalues real and at least $1$, so it is invertible.

It's worth pointing out that this doesn't depend at all on the $x_i$'s being distinct: $I + A$ is invertible regardless.

As for an explicit formula for the inverse, I doubt that one exists, since too many matrices can be written in this form: every positive semidefinite matrix can be written in the form $X^TX$, and multiplying by $nI - J$ doesn't do much to eigenstuff other than ensure than one eigenvalue equals $0$. With so few restrictions, this is too close to just asking for a formula for the inverse of any matrix with positive eigenvalues.