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.

Improve this question
$\endgroup$
3
  • $\begingroup$ the pseudoinverse of $L_n$ has some obvious structure, each row or column adds up to zero. $\endgroup$
    – Carlo Beenakker
    Commented Feb 27, 2014 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
    Commented Feb 27, 2014 at 13:36
  • $\begingroup$ That indeed looks promising, Paglia. $V_n$ and $V_n^*$ both seem to have a simple structure. $\endgroup$
    – MthQ
    Commented Feb 27, 2014 at 13:53

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Feb 28, 2014 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
    Commented Feb 28, 2014 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
    Commented Feb 28, 2014 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
    Commented Feb 28, 2014 at 13:38
  • $\begingroup$ Is there any kind of proof of your answer? I am very interested in it. $\endgroup$
    – TommasoF
    Commented Nov 18, 2016 at 14:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .