1
$\begingroup$

Given a Laplacian matrix $A\in\mathbb{R}^{n\times n}$ (symmetric, positive semi-definite matrix with positive diagonal elements and non-positive off-diagonal), and its Moore-Penrose pseudoinverse $A^+$, why is $A^+Ab=b,$ for some vector $b\in\mathbb{R}^n$ whose elements sum to zero. Note that the null-space of $A$ is spanned by vector of all ones, $1_n=(1,1,...1)\in\mathbb{R}^n$.

I find that $A^+=(A+1_n1_n^T)^{-1}-n^{-2}1_n1_n^T$, but the second term will vanish in multiplication with $A$.

  • 0
    @MartinArgerami see the edit.2012-11-26

1 Answers 1

2

Since $A$ is real symmetric, it can be orthogonally diagonalized. Let's say $A=Q\ \mathrm{diag}(\lambda_1,\ldots,\lambda_r,0,\ldots,0)\,Q^T$, where $Q$ is orthogonal and $\lambda_1,\ldots,\lambda_r$ are its nonzero eigenvalues. As the nullspace of $A$ is one-dimensional and spanned by $1_n$, we have $r=n-1$ and the last column of $Q$ is $\pm\frac1{\sqrt{n}}1_n$. Furthermore, since $A$ is positive semidefinite, its eigenvalue decomposition is automatically a singular value decomposition. Hence $A^+A=Q(I_{n-1}\oplus0)Q^T$. Now let $b$ be any of the first $n-1$ columns of $Q$. Then $AA^+b=b$.