Calculating a generalized inverse (Moore–Penrose pseudoinverse)

Question

I am considering a graph with $n$ edges with the following nicely structured adjacency matrix: \begin{equation} A_n= \begin{pmatrix} 0 & 0 & 0 &\cdots & 0 & 0 & 1\\ 0 & 0 & 0 &\cdots & 0 & 1 & 1\\ \vdots & \vdots & & & & \vdots & \vdots\\ 0 & 1 & 1 &\cdots & 1 & 1 & 1\\ 1 & 1 & 1 &\cdots & 1 & 1 & 1\\ \end{pmatrix}. \end{equation} I need to determine the pseudoinverse $L_n^+$ of its Laplacian: \begin{equation} L_n=\text{diag}(1, ...,n)-A_n. \end{equation} After playing around with Mathematica, $L_n^+$ seems to have a nice structure. However, I am not so familiar with determining pseudoinverses and therefore would like some help in determining this structure.

My question is, how would one go about calculating pseudoinverses and is it possible to get a closed-form expression for $L_n^+$ for general $n$? Thanks in advance.

Answer 1

Let's start by constructing an eigendecomposition of $L_n$.

Let $\mathbf{v}_j \in \mathbb{R}^n$, for $1 \leq j \leq \lfloor (n-1)/2 \rfloor$, be the vector defined as follows:

• its $j$-th entry is $\sqrt{\frac{2j - n}{2j - n - 1}}$;
• its $k$-th entry (for $j+1 \leq k \leq n-j$) is $\frac{-1}{\sqrt{(2j - n)(2j - n - 1)}}$;
• all other entries are $0$.

Similarly, let $\mathbf{v}_j \in \mathbb{R}^n$, for $n + 1 - \lfloor n/2 \rfloor \leq j \leq n$ be defined by:

• its $j$-th entry is $\sqrt{\frac{2j - n - 1}{2j - n}}$;
• its $k$-th entry (for $n - j + 1 \leq k \leq j-1$) is $\frac{-1}{\sqrt{(2j - n)(2j - n - 1)}}$;
• all other entries are $0$.

Finally, define $\mathbf{v}_j \in \mathbb{R}^n$ for $j = n - \lfloor n/2 \rfloor$ to be the zero vector. We have now defined $\mathbf{v}_j$ for all $1 \leq j \leq n$.

These vectors are mutually orthonormal eigenvectors for $L_n$, and the eigenvalue corresponding to eigenvector $\mathbf{v}_j$ is exactly $j$ itself:

$$ L_n = \sum_{j=1}^n j\mathbf{v}_j\mathbf{v}^*_j $$

From this it immediately follows that the pseudo-inverse $L_n^+$ is

$$ L_n^+ = \sum_{j=1}^n \frac{1}{j}\mathbf{v}_j\mathbf{v}^*_j. $$

Note that I did some trickery here, since one eigenvalue of $L_n$ is always zero -- instead of setting the eigenvalue to zero, I set the corresponding eigenvector $\mathbf{v}_j$ for $j = n - \lfloor n/2 \rfloor$ to be zero, since this made the final answer cleaner in my opinion.

Also note that I've stated a bunch of things without proof here. They can be proved easily enough in a brute-force sort of way; it's just messy and not terribly enlightening.