4
$\begingroup$

I'm trying to understand a method for calculating the Moore-Penrose inverse of an incidence matrix of a graph as outlined in "Graphs and Matrices" (you can find the book here: https://link.springer.com/book/10.1007/978-1-4471-6569-9). I can execute all the steps for calculating the inverse but I haven't yet fully understood why the method works:

The line I don't understand is on page 20 and reads "By Lemma 2.14 it follows that $Y=D'X$." I don't see how Lemma 2.14 is connected to this statement and would appreciate it if anyone could help me understand this line.

If you cannot access the book or don't want to get familiar with the notation the author uses, here's a summary of what I don't understand which hopefully includes all the relevant information:

Summary of the problem

The transpose of a matrix $A$ will be denoted by $A'$.

Consider a connected directed graph $G$ with vertices $V=\left\{1,\ldots,n\right\}$ and edges $E=\left\{e_1,\ldots,e_m\right\}$ with the edges ordered in such a way that $\left\{e_1,\ldots,e_{n-1}\right\}$ form a spanning tree of $G$. Let $Q$ be the $n\times m$ incidence matrix of $G$. To cite "Graphs and Matrices", "the rows and the columns of $Q$ are indexed by $V$ and $E$, respectively. The $\left(i,j\right)$- entry of $Q$ is $0$ if vertex $i$ and edge $e_j$ are not incident, and otherwise it is $1$ or $-1$ according as $e_j$ originates or terminates at $i$, respectively."

See the following example where the spanning tree is highlighted in red:

Incidence Matrix

Now, one wants to calculate the Moore-Penrose inverse $Q^+$ of $Q$ (which implies that the following four conditions hold: (1) $QQ^+Q=Q$, (2) $Q^+QQ^+=Q^+$, (3) $\left(QQ^+\right)'=QQ^+$, (4) $\left(Q^+Q\right)'=Q^+Q$).

To do so, the author partitions $Q$ as $Q=\begin{bmatrix} U & V \end{bmatrix}$ where $U$ is $n\times\left(n-1\right)$ and $V$ is $n\times\left(m-n+1\right)$ and $Q^+$ as $Q^+=\begin{bmatrix} X \\ Y \end{bmatrix}$ where $X$ is $\left(n-1\right)\times n$ and $Y$ is $\left(m-n+1\right)\times n$. He then notes that "there exists an $\left(n-1\right)\times\left(m-n+1\right)$ matrix $D$ such that $V=UD$." I still understand why this is the case. However, I'm stuck at the next sentence, which says "By Lemma 2.14 it follows that $Y=D'X$."

Lemma 2.14 says:

If $A$ is an $m\times n$ matrix, then for an $n\times1$ vector $x$, $Ax=0$ if and only if $x'A^+=0$.

I don't see how the Lemma can be applied to see that $Y=D'X$.

I tried a few approaches but none led to any result and I don't want to list them all here. Just leave a comment for more details.

Maybe I'm missing something obvious but I really can't seem to find a way to reach the same conclusion as the author. Thanks in advance for any help!

$\endgroup$
2
$\begingroup$

For any $(m-n+1)\times1$ vector $x$, \begin{align*} \begin{bmatrix} U & V \end{bmatrix} \begin{bmatrix} -Dx \\ x \end{bmatrix} =-UDx+UDx=0 &\stackrel{\text{L}}\implies \begin{bmatrix} X' & Y' \end{bmatrix} \begin{bmatrix} -Dx \\ x \end{bmatrix} =0\\ &\implies-X'Dx+Y'x=0\\ &\implies Y'x=X'Dx\,, \end{align*} so $Y'=X'D\implies Y=D'X$.

$\endgroup$

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.