I have poste this question on StackExchange but there were no takers - would I be luckier on this site?
Most of this is well known, so let me just restate the corresponding Math:
Given a connected, directed, simple (no loops, no parallel edges) graph with $m$ vertices and $n$ edges, one first builds its $m$ by $n$ incidence matrix marking (by $1$ or $-1$ for 'in' or 'out', $0$ otherwise) incident edges of each vertex. One row of this matrix is then deleted; since the matrix is of rank $m-1$ (the only liner combination of rows yielding the zero vector is their sum, as each column has only two nonzero elements, equal to $1$ and $-1$), the resulting matrix (say $K$) consists of linearly independent rows (each row is a vector representing a 'star' - incident edges to a single vertex).
One then finds all fundamental cycles of the corresponding undirected graph (yet, the cycles are oriented, following one of the two possible directions); one can prove that there are exactly $n-m+1$ such cycles. The result is then converted into a similar, $n-m+1$ by $n$ matrix (say $C$) whose rows indicate which edges are a part of the corresponding cycle ($1$ when the cycle's orientation agrees with the graph's orientation, $-1$ when not, $0$ otherwise). It's again easy to prove that the rows of $C$ are linearly independent (each cycle has a unique edge found in no other cycle); each of them is also orthogonal to every row of $K$.
This implies that the two matrices, when joined to create an $n$ by $n$ matrix, create a single REGULAR (non-singular) matrix - no problem there.
What I need to show next (which I cannot find in literature and failed to do so myself) is that this remains true even after each column of $C$ has been multiplied by an arbitrary (one for each column) positive number (equivalent to assigning weights to edges).
A secondary (more difficult) question is: can some of these numbers be $0$ and still yield a regular matrix? The answer is yes, and my conjecture is that this is the case whenever the corresponding 'zero' edges (or their subset) do not form a cycle. Again, how do I prove that?
