## Matrix inversion lemma with pseudoinverses

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

The utility of the Matrix Inversion Lemma has been well-exploited for several questions on MO. Thus, with some positive hope, I'd like to field a question of my own.

Suppose we pick $n$ values $x_1,\ldots,x_n$, independently sampled from $N(0,1)$ (mean 0, unit variance gaussian). Then, we form the (rank 3 at best) positive semidefinite matrix: $$A = \alpha ee^T + [\cos(x_i-x_j)],$$ where $e$ denotes the vector of all ones, and $\alpha > 0$ is a fixed scalar.

For $n \ge 3$, simple experiments lead one to conjecture that: $$e^TA^\dagger e = \alpha^{-1},$$ where $A^\dagger$ is the Moore-Penrose pseudoinverse of $A$ (obtained in Matlab using the 'pinv' function).

This should be fairly easy to prove with the right tools, such as a Matrix inversion lemma that allows rank deficient matrices or pseudoinverses. So my question is:

How to prove the above conjecture (without too much labor, if possible)?

-

1
If you just let $x_1,\dots,x_n$ be distinct scalars instead of specifying a particular probability distribution, shouldn't you get the same result? – Michael Hardy Aug 4 2011 at 4:13
Actually, I suspected it to be true as long as all the $x$'s were such that their contribution remains independent of $ee^T$ (Mikael makes this explicit in the answer below) – S. Sra Aug 4 2011 at 16:08
Why can the rank never exceed 3? – Michael Hardy Aug 5 2011 at 21:22

1
@Michael: expand $\cos(x-y)=\cos x\cos y + \sin x \sin y$ to notice that $A$ is a sum of three rank-1 matrices. – S. Sra Aug 5 2011 at 23:13

## 1 Answer

In fact more generally for any positive semidefinite matrix $A = \sum_{i=0}^k e_i e_i^T$ with $e_i$'s linearly independent, we have that $e_i^T B e_i = 1$, where $B$ is the Moore-Penrose pseudoinverse of $A$. This applies here since almost surely your matrix $A$ is of this form with $k=3$ and $e_1 = \sqrt \alpha e$.

Proof: Let $E$ be the linear span of the $e_i$'s. If I understood correctly the notion of Moore-Penrose pseudoinverse, $B$ is described in the following way: as a linear map, $B$ is zero on the orthogonal of $E$, and on $E$ it is the inverse of the restriction of $A$ to $E$. Let `$\beta_{i,j}$` be defined by `$B e_i = \sum_j \beta_{i,j} e_j$`, so that `$e_i^T B e_i = \sum_j\beta_{i,j} e_i^T e_j$`. Expressing that `$A B e_i = e_i$`, we get in particular that `$\sum_j\beta_{i,j} e_i^T e_j = 1$`, QED.

-

Nice clean answer Mikael. It seems so easy once somebody proves it :-) thanks! – S. Sra Aug 4 2011 at 16:09
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 29, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9073982834815979, "perplexity_flag": "head"}