An expression subtly different from the one in Sherman-Morrison formula

Question

Let $0\ne x\in\mathbb{R},\,\mathbf{y} \in \mathbb{R}^{n},\,\mathbf{1}=(1,1, \cdots, 1)^{T} \in \mathbb{R}^{n}$ and assume that $\Sigma=x I_{n}+\mathbf{y} \mathbf{1}^{T}+\mathbf{1} \mathbf{y}^{T}$ is positive definite. Prove that $$ \Sigma^{-1}-\frac{\Sigma^{-1} \mathbf{1 1}^{T} \Sigma^{-1}}{\mathbf{1}^{T} \Sigma^{-1} \mathbf{1}}=\frac{1}{x}\left(I_{n}-\frac{1}{n} \mathbf{1 1}^{T}\right). $$

Answer 1

With the Sherman Morrison identity, $$ \Sigma^{-1} - \frac{\Sigma^{-1}11^T\Sigma^{-1}}{1^T\Sigma 1} = \lim_{m \to \infty} \Sigma^{-1} - \frac{\Sigma^{-1}(m1)(m1)^T\Sigma^{-1}}{1 + (m1)^T\Sigma (m1)} \\ = \lim_{m \to \infty}(\Sigma + (m \mathbf 1)(m \mathbf 1)^T)^{-1}. $$ On the other hand, we can write $$ \Sigma(m) := \Sigma + (m \mathbf 1)(m \mathbf 1)^T = x I_n + \pmatrix{\mathbf 1 & \mathbf y} \pmatrix{m^2 & 1\\1 & 0} \pmatrix{\mathbf 1 & \mathbf y}^T. $$ To show that $\Sigma(m)^{-1} \to \frac 1x (I - \frac{11^T}{n})$, it suffices to block-diagonalize $\Sigma$. We see that $\Sigma \mathbf z = x\mathbf z$ for all $\mathbf z$ perpendicular to both $\mathbf 1,\mathbf y$. On the other hand, let $v_1 = \mathbf 1/\sqrt{n}$, let $v_2$ be the component of $\mathbf y$ orthogonal to $\mathbf 1$. We have $$ v_1^T\pmatrix{\mathbf 1 & \mathbf y} \pmatrix{m^2 & 1\\1 & 0} \pmatrix{\mathbf 1 & \mathbf y}^Tv_1 = m^2n + 2(v_1^Ty)^2\\ $$

$$ v_1^T\pmatrix{\mathbf 1 & \mathbf y} \pmatrix{m^2 & 1\\1 & 0} \pmatrix{\mathbf 1 & \mathbf y}^Tv_2 = \sqrt{n}\, v_2^Ty. $$

$$ v_2^T\pmatrix{\mathbf 1 & \mathbf y} \pmatrix{m^2 & 1\\1 & 0} \pmatrix{\mathbf 1 & \mathbf y}^Tv_2 = \pmatrix{0 & v_2^Ty} \pmatrix{m^2 & 1\\1 & 0}\pmatrix{0 & v_2^Ty} = 0 $$

So, relative to an orthogonal basis that extends $v_1,v_2$, the matrix of $\Sigma$ is $$ x I_n + \pmatrix{m^2n + 2(v_1^Ty)^2 & \sqrt{n}\, v_2^Ty\\ \sqrt{n}\, v_2^Ty & 0} \oplus 0_{(n-2) \times (n-2)}. $$ The inverse of this matrix is $$ \pmatrix{x + m^2n + 2(v_1^Ty)^2 & \sqrt{n}\, v_2^Ty\\ \sqrt{n}\, v_2^Ty & x}^{-1} \oplus \frac 1x I = \\ \frac 1{xm^2 n + o(m)}\pmatrix{x & -\sqrt{n}\,v_2^Ty\\ -\sqrt{n}\, v_2^Ty & x + m^2n + 2(v_1^Ty)^2} \oplus \frac 1x I. $$ As $m \to \infty$, this approaches $$ \pmatrix{0 & 0\\ 0 & 1/x} \oplus \frac 1x I, $$ which is the matrix of $(I - \frac 1n 11^T)$ relative to the new basis. Thus, we have the desired conclusion.

---

Alternatively it suffices to show that $\Sigma(m)^{-1} \mathbf z \to (I - \frac{11^T}{n}) \mathbf z$ for all $\mathbf z$. In particular,

1. If $\mathbf z \perp \mathbf 1$, then $\Sigma(m)^{-1} \mathbf z \to \frac 1x \mathbf z$, and
2. $\Sigma(m)^{-1} \mathbf 1 \to 0$.

Alternatively, with the Woodbury identity, we have $$ (x I_n)^{-1} - \Sigma^{-1} = \frac 1{x^2} \pmatrix{y & 1}\left(\pmatrix{m^2&1\\1&0}^{-1} + \pmatrix{n & 1^Ty\\ 1^Ty & y^Ty}\right)^{-1}\pmatrix{y & 1}^T. $$ It would therefore suffice to compute the limit of the middle term $$ \left(\pmatrix{m^2&1\\1&0}^{-1} + \pmatrix{n & 1^Ty\\ 1^Ty & y^Ty}\right)^{-1}, $$ and show that $(x I_n)^{-1} - \Sigma^{-1} \to \frac 1{xn}11^T$.

Answer 2

Alternative solution:

Clearly, $x > 0$. From $\Sigma = xI + y 1^\mathsf{T} + 1 y^\mathsf{T}$, we have $$I = x\Sigma^{-1} + y 1^\mathsf{T}\Sigma^{-1} + 1 y^\mathsf{T}\Sigma^{-1}. \tag{1}$$ From (1), we have \begin{align} 1^\mathsf{T}1 &= x \cdot 1^\mathsf{T}\Sigma^{-1} 1 + 1^\mathsf{T}y \cdot 1^\mathsf{T}\Sigma^{-1} 1 + n \cdot y^\mathsf{T}\Sigma^{-1} 1, \tag{2}\\ 1^\mathsf{T} y &= x\cdot 1^\mathsf{T} \Sigma^{-1}y + 1^\mathsf{T}y \cdot 1^\mathsf{T}\Sigma^{-1}y + n \cdot y^\mathsf{T}\Sigma^{-1}y, \tag{3}\\ y^\mathsf{T} y &= x\cdot y^\mathsf{T} \Sigma^{-1}y + y^\mathsf{T}y \cdot 1^\mathsf{T}\Sigma^{-1}y + y^\mathsf{T}1 \cdot y^\mathsf{T}\Sigma^{-1}y. \tag{4} \end{align} $(2)\times [(x+y^\mathsf{T}1)^2 - ny^\mathsf{T}y] - (3)\times n(x+y^\mathsf{T}1) + (4) \times n^2$ results in $$[(x+y^\mathsf{T}1)^2 - ny^\mathsf{T}y] 1^\mathsf{T}\Sigma^{-1} 1 = nx.\tag{5}$$ Thus, $(x+y^\mathsf{T}1)^2 - ny^\mathsf{T}y > 0$ and $$1^\mathsf{T}\Sigma^{-1} 1 = \frac{nx}{(x+y^\mathsf{T}1)^2 - ny^\mathsf{T}y}.\tag{6}$$

Also, we have \begin{align} &\Sigma^{-1} - \frac{\Sigma^{-1}11^\mathsf{T}\Sigma^{-1}}{1^\mathsf{T}\Sigma^{-1}1} = \frac{1}{x}\left(I - \frac{1}{n}11^\mathsf{T}\right)\\ \Longleftrightarrow\quad & x\Sigma - x\frac{11^\mathsf{T}}{1^\mathsf{T}\Sigma^{-1}1} = \Sigma^2 - \frac{1}{n}\Sigma 1 1^\mathsf{T}\Sigma \\ \Longleftrightarrow\quad & x\frac{11^\mathsf{T}}{1^\mathsf{T}\Sigma^{-1}1} = x\Sigma - \Sigma^2 + \frac{1}{n}\Sigma 1 1^\mathsf{T}\Sigma\\ \Longleftrightarrow\quad & x\frac{11^\mathsf{T}}{1^\mathsf{T}\Sigma^{-1}1} = \left(\frac{(x+y^\mathsf{T}1)^2}{n} - y^\mathsf{T}y\right)1 1^\mathsf{T}\\ \Longleftrightarrow\quad & \frac{x}{1^\mathsf{T}\Sigma^{-1}1} = \frac{(x+y^\mathsf{T}1)^2}{n} - y^\mathsf{T}y \tag{7} \end{align} where we have used $x\Sigma - \Sigma^2 + \frac{1}{n}\Sigma 1 1^\mathsf{T}\Sigma = \left(\frac{(x+y^\mathsf{T}1)^2}{n} - y^\mathsf{T}y\right)1 1^\mathsf{T}$ (by some easy calculation). From (6), we know that (7) is true. (Q.E.D.)

Answer 3

As we shall shortly see, it isn't hard to verify the identity in question. The truly difficult question, of which I have no answer, is how one came up with such an identity.

Let us prove the identity. The case $n=1$ is omitted. When $n\ge2$, in order that $\Sigma\succ0$, $x$ is necessarily positive. Let $\mathbf u=\frac{\mathbf1}{\|\mathbf1\|}=\frac{1}{\sqrt{n}}\mathbf1,\ \mathbf z=\frac{\sqrt{n}}{x}\mathbf y$ and $S=I+\mathbf z\mathbf u^T+\mathbf u\mathbf z^T$. The equality in question can be rewritten as $$ \underbrace{S^{-1} - \frac{S^{-1}\mathbf u\mathbf u^TS^{-1}}{\mathbf u^TS^{-1}\mathbf u}}_A = \underbrace{I_n-\mathbf u\mathbf u^T}_\Pi.\tag{1} $$ Let $\mathbf v$ be a unit vector orthogonal to $\mathbf u$ such that $V=\operatorname{span}\{\mathbf u,\mathbf v\}\supseteq\operatorname{span}\{\mathbf u,\mathbf z\}$. Then $V$ and $V^\perp$ are invariant subspaces of $S,A$ and $\Pi$. Moreover, $S_{V^\perp}=S_{V^\perp}^{-1}=\Pi_{V^\perp}=\operatorname{Id}$. Therefore, to prove $(1)$, it suffices to prove that $\mathbf p^TA\mathbf q=\mathbf p^T\Pi\mathbf q$ for all $\mathbf p,\mathbf q\in\{\mathbf u,\mathbf v\}$. It is straightforward to verify that $\mathbf u^TA\mathbf q=0=\mathbf u^T\Pi\mathbf q$ for any $\mathbf q\in\mathbb R^n$. So, we only need to consider the case where $\mathbf p=\mathbf q=\mathbf v$ and show that $$ \mathbf v^TS^{-1}\mathbf v - \frac{(\mathbf u^TS^{-1}\mathbf v)^2}{\mathbf u^TS^{-1}\mathbf u} = 1.\tag{2} $$ Since $\mathbf v^TS\mathbf v=1$, the matrix representations of $S|_V$ and $S^{-1}|_V$ with respect to the ordered basis $\{\mathbf u,\mathbf v\}$ are in the form of $$ S=\pmatrix{\ast&\ast\\ \ast&1} \text{ and } S^{-1}=\pmatrix{a&b\\ b&c}. $$ Now $(2)$ is equivalent to the statement that $c-\frac{b^2}{a}=1$, but this is true because $$ c-\frac{b^2}{a}=\frac{\det(S^{-1})}{a}=\frac{1}{\det(S)(S^{-1})_{11}}=\frac{1}{(\operatorname{adj}(S))_{11}}=\frac{1}{S_{22}}=1. $$