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.
A very interesting weighting is obtained by just working with directed multigraphs (dimgraphs). 7 or 8 years ago, I applied the matrix-tree theorem applied to dimgraphs in conjunction with the BEST theorem to provide a structure theory for the equilibrium thermodynamics of hybridization for oligomeric (short) DNA strands.
Briefly, the SantaLucia model of DNA hybridization takes a finite word $w$ on four letters (A, C, G, T) and associates to it various thermodynamical characteristics (e.g., free energy $\Delta G$ of hybridization) based on the sequence. Assuming the words are cyclic (which is not fair, but also not a very bad approximation practically), one has $\Delta G (w) = \sum_k \Delta G (w_kw_{k+1})$ where the index $k$ is cyclic and the 16 parameters $\Delta G(AA), \dots, \Delta G(TT)$ are given.
Assuming for convenience that the $\Delta G(\cdot,\cdot)$ are independent over $\mathbb{Q}$, it is not hard to see that $\Delta G$ projects from the space of all words of length $N$ to the space of dimgraphs on 4 vertices (again, A, C, G, T) with $N$ edges, where (e.g.) an edge from A to G corresponds to the subsequence AG. Using matrix-tree and BEST provides a functional expression for the number of words of length $N$ with a given number of AA's, AC's, ... and TT's, and thus for the desired $\Delta G$.
Going a step further, one can use generalized Euler-Maclaurin identities for evaluating sums of functions over lattice polytopes to characterize the space of all (cyclic) words of length $N$ with $\Delta G$ lying in a narrow range. This effectively completes the structure theory and shows how one can construct DNA sequences having desired thermodynamical and combinatorial properties. Among other things, I used this to design a protocol for (as David Harlan Wood put it) "simulating simulated annealing by annealing DNA".
Best Answer
The first answer identifies "incidence matrix" with "adjacency matrix". The latter is the vertices-by-vertices matrix that Sciriha writes about. But the original question appears to concern the incidence matrix, which is vertices-by-edges. The precise answer is as follows.
Theorem: The rows of the incidence matrix of a graph are linearly independent over the reals if and only if no connected component is bipartite.
Proof. Some steps are left for the reader :-)
Note first that the sum of rows indexed by the vertices in one color class of a bipartite component is equal to the sum of the rows indexed by the other color class. Hence if some component is bipartite, the rows of the incidence matrix are linearly dependent.
For the converse, we have to show that the incidence matrix of a connected non-bipartite graph has full rank. Select a spanning tree $T$ of our graph $G$. Since $G$ is not bipartite, there is an edge $e$ of $G$ such that the subgraph $H$ formed by $T$ and $e$ is not bipartite.
The trick is to show that the columns of the incidence matrix indexed by the edges of H form an invertible matrix. We see that $H$ is built by "planting trees on an odd cycle". We complete the proof by induction on the number of edges not in the cycle.
The base case is when $H$ is an odd cycle. It is easy to show that its incidence matrix is invertible. Otherwise there is a vertex of valency one, $x$ say, such that $H \setminus x$ is connected and not bipartite. Then the incidence matrix of $H \setminus x$ is invertible and again it is easy to see this implies that the incidence matrix of $H$ is invertible.
Remark: I do not know who first wrote this result down. It is old, and is rediscovered at regular intervals.