3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ the pseudoinverse of $L_n$ has some obvious structure, each row or column adds up to zero. $\endgroup$ – Carlo Beenakker Feb 27 '14 at 13:18
  • 1
    $\begingroup$ One possibility for you to compute $L_n^+$ is to find a diagonalization $L_n = V_n D_n V_n^*$ ($L_n$ seems to be diagonalizable in this case, I run some Matlab tests) and then put $L_n^+ = V_n D_n^+ V_n^*$, where the pseudoinverse of the diagonal matrix $D_n$ is easily computable: you just have to take the reciprocal of each non-zero element on the main diagonal, and leave the zeros elements at their own place. $\endgroup$ – Paglia Feb 27 '14 at 13:36
  • $\begingroup$ That indeed looks promising, Paglia. $V_n$ and $V_n^*$ both seem to have a simple structure. $\endgroup$ – MthQ Feb 27 '14 at 13:53
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you sure about those eigenvectors? When I compute the eigenvectors of $L_n$, they completely consist of integers. Am I not getting something? $\endgroup$ – MthQ Feb 28 '14 at 9:37
  • 1
    $\begingroup$ @Thomas -- I coded my answer above in MATLAB to double-check that it works for $n \leq 10$. The eigenvectors above do consist entirely of integers, up to being normalized (i.e., up to being divided by $\sqrt{(2j-n)(2j-n-1)}$, which is the norm of the integer vector). $\endgroup$ – Nathaniel Johnston Feb 28 '14 at 12:05
  • $\begingroup$ Ok, I understand now. I guess I should not normalize in order to get nicer expression. Thank you very much $\endgroup$ – MthQ Feb 28 '14 at 13:10
  • 1
    $\begingroup$ @Thomas -- Yep, if you don't normalize then the $\mathbf{v}_j$'s become nicer, but at the expense that the form of $L_n^+$ becomes slightly messier. Explicitly, if $\mathbf{w_j} = \sqrt{(2j-n)(2j-n-1)}\mathbf{v}_j$ (i.e., the all-integer eigenvector) then $L_n^+ = \sum_{j=1}^n \frac{1}{j(2j-n)(2j-n-1)}\mathbf{w}_j\mathbf{w}_j^*$. $\endgroup$ – Nathaniel Johnston Feb 28 '14 at 13:38
  • $\begingroup$ Is there any kind of proof of your answer? I am very interested in it. $\endgroup$ – TommasoF Nov 18 '16 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.