Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

When I was working on my PhD dissertation, I came across a physical situation involving nodes and flows between them. It turned out that I was working with a complete oriented graph $K_n$ (all nodes are connected to each other), and I needed to calculate the pseudoinverse of its incidence matrix T, i.e. the rectangular matrix N(V) x N(E) where N(E) = n is the number of edges and N(V) is the number of vertices, with matrix element 1 if the edge enters the vertex, -1 if the edge leaves the vertex, and 0 otherwise.

To my surprise the pseudoinverse turns out to be proportional to the transpose of the incidence matrix! Specifically

$T^{+} (K\_n) = \frac{1}{n} T^{\prime} (K\_n)$

where the prime denotes transposition.


My question is:

A) What other graphs $G$, if any, have this property, i.e. that

$T^+(G) \propto T^\prime(G)$,

or some suitable generalization thereof, and

B) How can I show that this result is invariant of orientation? (I determined empirically is certainly true for all possible orientations of the small complete graphs, and I haven't been able to find a counterexample, but I don't have a proof of this statement yet)

I'm not a professional mathematician, so any thoughts would be welcome.


One class of generalizations that is possible (but not so interesting IMO) are disconnected graphs where each subgraph is a complete graph, i.e.

$G = K_{n_1} \oplus K_{n_2} \oplus \dots \oplus K_{n_m}$

In this case one gets

$T^+(G) = \frac{1}{n_1} T^\prime(K_{n_1}) \oplus \frac{1}{n_2} T^\prime(K_{n_2}) \oplus \dots \oplus \frac{1}{n_m} T^\prime(K_{n_m})$

which is not really that exciting, but perhaps could point the way to a more interesting generalization.


P.S. There is a short proof of the first fact, which relies on the fact that the complete graph has a Laplacian of the form

$\Delta = n \mathbf{I} - \mathbf{1} \mathbf{1}^\prime$

where $\mathbf{I}$ is the n x n identity matrix and $\mathbf{1}$ is a column vector of ones.

With this fact, together with knowing that the column sums of $T$ are all zero, it is straightforward to show that $T^\prime(K_n)/n$ satifies all the Moore-Penrose conditions for the pseudoinverse.


P.P.S. If anyone is interested in the physical context, here is where it came from.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

Let the vertices be numbered $1,\ldots,n$. For a vertex $i$, let $\mathrm{deg}(i)$ be the total number of (unsigned) edges incident to $i$. If $A$ is the incidence matrix, consider $AA^TA$. An entry of $AA^TA$ is indexed by a vertex $i$ and an edge $e=(j,k)$. If I did this correctly, it's straightforward to show that $[AA^TA]_{i,(j,k)}$ is:

  • $-\mathrm{deg}(i)$ if $i=j$,
  • $\mathrm{deg}(i)$ if $i=k$,
  • the number of undirected edges $(i,k)$ minus the number of undirected edges $(i,j)$ otherwise.

If $A^T$ is a scalar multiple of the pseudoinverse of $A$, then $AA^TA$ must be a scalar multiple of $A$. It's easy to see from the above that this is equivalent to requiring that each connected component of the graph is complete, each vertex has the same (undirected) degree, and within each component, all edges have the same (undirected) multiplicity. (For example, I think you could have two components $K\_3$ and $K\_5$, where there are two edges between each pair of vertices in the $K\_3$ component and one edge between each pair in the $K\_5$ component.) None of this depends on the orientations of the edges: flipping an edge of the graph is equivalent to negating a column of $A$, and if $AA^TA$ was a scalar multiple of $A$ before, then it still is now. Since $(AA^TA)^T = A^TAA^T$, if $AA^TA = cA$, then $A^TAA^T = cA^T$, so $(1/c)A^T$ is the Moore-Penrose pseudoinverse of $A$. ($AA^T$ and $A^TA$ are obviously symmetric.) This completely characterizes graphs with your property.

share|improve this answer
    
I agree with the first two cases of your calculation of A A^T A, but for the third case I don't get the same answer. A A^T is the Laplacian matrix L, so L A is the product. L = degree matrix (D) - adjacency matrix (Ad). The product D A gives the first two cases. Denoting i---j as an unconnected edge, i-->j as a directed edge, and #(x) for number of x's. Then I get (Ad A)_{i, (j,k)} = sum_l #(i---l) * (+1 if l=k and j-->k or l=j and k-->j, -1 if l=k and k-->j or l=j and j-->k, 0 else) = ( #(i---k) - #(i---j) ) * ( #(j-->k) - #(k-->j) ) , which differs from your answer by the second term. –  Jiahao Chen Nov 11 '09 at 21:44
    
The case G = K_3 + K_5 doesn't satisfy strict proportionality because the constants for K_3 and K_5 differ. However they do obey the generalization described in the original question. –  Jiahao Chen Nov 11 '09 at 21:49
    
Thanks, though, for pointing out that I should just do the calculation A A^T A for the generic case. When I read that, it was head-smackingly obvious that I should have done that right away. –  Jiahao Chen Nov 11 '09 at 21:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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