An illustrated example right-away
Not to immediately bore you with lengthy preliminary remarks, let me begin with an illustration which, in a sense, already is an answer in itself. Here is an example that such a basis can look very different from the familiar spanning-tree-bases, and still be highly structured:
(source: [H2014; p. 83], color added, and some notation in [H2014] not needed here removed)
Figure 1. This is an example of a representation of the flow on the left-hand side in terms of a basis consisting of Hamilton-flows only.
The left-hand flow is not a Hamilton flow (since vertices $3$ and $5$ are not in the support of the flow). Since 'flow' is just another term for 'element of the null space of the constraint matrix of a flow problem', this is an example of exactly the kind the OP was asking for: the basis of the 'constraint matrix' of a flow problem (better called: incidence matrix) can look very special, in particular, they can look very different from the familiar spanning tree bases, i.e. bases obtained from choosing a spanning tree and adding missing edges one by one.
The relevant directed graph here is represented by each of the nine undirected graphs underlying the pictures (the graph is the same everywhere), the edge-directions are not drawn but defined by letting any undirected edge $\{i,j\}$ with $i<j$ (natural order) represent the directed edge $(i,j)$.
(In other words, direct each edge from the smaller to the larger vertex.)
On the left-hand side of the equation, the thick black lines with the white inlays represent a flow, i.e., in your notation, an element of $N_A$, with a support equal to a 'circuit'; this circuit is not a 'Hamilton-circuit', because two vertices are not used by the circuit. (Incidentally, the circuit on the left-hand side is a so-called *fundamental circuit, i.e. it can be constructed by choosing a suitable spanning tree, and then adding one more edge not in the tree.)
On the right-hand side, you see the eight elements of a Hamilton-basis (explained below) among the many bases of $N_A = Z_1(G)$, together with the unique integer coefficients which make the eight Hamilton-flows add-up to the given non-Hamilton-flow.
The basis you see in Figure 1 is a basis each of whose eight elements has its support equal to a Hamilton-circuit of $G$. (This is called a 'Hamilton-basis'). This is in some sense an answer to how these bases
can 'look like'. (An important point is that the above example looks very different from the so-called fundamental cycles that a commentator mentioned at 2017-08-23 22:50:19Z in this thread.)
You can check (in Figure 1) that 'on' each particular edge the relevant calculation works out to the value given on the left-hand side. A remarkable feature are the small magnitudes of the $\mathbb{Z}$-valued coefficients in the linear combination (all coefficients have absolute value at most $2$). In my experience, it is relatively easy in a moderately dense graph to find a Hamilton-circuit-supported basis by choosing rank-many Hamilton-flows randomly, but it is not easy to find a Hamilton-basis such that the coefficients in the (unique) linear combination representing a given flow are all small. The small coefficients are not a purposeless gimmick: to write the proof in [H2014] for general $n$, it was (at least pragmatically) necessary to keep the coefficients small and reasonably structured; otherwise the proof would have been unmanageably complicated (in [H2014], a Hamilton-basis is given which is structured enough to carry out the proof for general $n$ without even having to resort to induction, and this basis was not found by randomly mining the available Hamilton-bases, rather by a rather tedious mixture of machine-experimentation and human intuition).
To give an explicit example, on e.g. the directed edge $(1,10)$, the relevant calculation works out to (note that blue coefficients match Figure 1)
$\small 0= \color{blue}{(+)} \cdot 0 {\ \scriptsize\text{+}\ } \color{blue}{0} \cdot (+) {\ \scriptsize\text{+}\ } \color{blue}{(-)} \cdot (+) {\ \scriptsize\text{+}\ } \color{blue}{(+2)} \cdot (+) {\ \scriptsize\text{+}\ } \color{blue}{(-2)} \cdot (+) {\ \scriptsize\text{+}\ } \color{blue}{(-2)} \cdot 0 {\ \scriptsize\text{+}\ } \color{blue}{(+2)} \cdot 0 {\ \scriptsize\text{+}\ } \color{blue}{(+1)} \cdot (+)$
$=$
$\small 0 {\ \scriptsize\text{+}\ } 0 {\ \scriptsize\text{+}\ } (-) {\ \scriptsize\text{+}\ } (+2) {\ \scriptsize\text{+}\ } (-2) {\ \scriptsize\text{+}\ } 0 {\ \scriptsize\text{+}\ } 0 {\ \scriptsize\text{+}\ } (+)$
$=$
$\small (-) {\ \scriptsize\text{+}\ } (+)$
$=$
$\small 0$
where $-:=-1$ and $+:=+1$ and the second factors correspond to the flows given by the black lines, the inlays indicating the direction of the respective flow.
Needless to say, since this is a basis, the $\mathbb{Z}$-linear representation of the non-Hamilton-flow in terms of the eight Hamilton-flows, more precisely, the coefficient vector $(1,0,-1,2,-2,-2,2,1)\in\mathbb{Z}^8$ is the only one among the infinitely-many in $\mathbb{Z}^8$.
Six preliminary remarks on the syntax of the OP
Remark 0 I think the form of the OP (its title included) should be improved.
Instead of rewriting it from scratch, I will leave the question untouched and instead offer an equivalent formulation of the question here:
My suggestion of an equivalent reformulation of the title of the OP: what structural results are known about elements of the kernel of the incidence matrix of a directed graph? ${}\hspace{79pt}$ (e.0)
My suggestion of an equivalent reformulation of the OP: what is known about how to describe the null space of the signed incidence matrix of a specified finite directed graph in combinatorial/structural/graph-theoretic terms? ${}\hspace{256pt}$ (e.1)
I think that (e.0) is equivalent to the title, and (e.1) is equivalent to the OP. The alternative formulations are better because 'incidence matrix' is a more usual and neutral technical term than 'constraint matrix', which belongs to the rather specialized context of combinatorial optimization.
Remark 1 To say "set of flow constraints" and "constraint matrix" is misleading, or at least the wrong emphasis, since this "constraint matrix" is determined by the given digraph alone, not by the constraints; that is, your matrix $A$ is independent of the values $x_{u,v}$ in the OP. I therefore recommend to not call $A$ a 'constraint matrix'.
- in your OP, you use 'constraint' in a slightly
unusual sense: you don't use it to mean some kind of capacity or costs
specified for the edges, but rather you simply mean the usual
flow condition.
Remark 2 For simplicity, in this answer I simply assume that
in the OP, "directed graph" means 'oriented graph'='digraph without any 2-cycles'='1-dimensional finite abstract simplicial complex'.
This implies: in this answer, no multiple edges whatsoever are allowed, not even 2-cycles(=antiparallel arcs) are allowed, which are allowed in digraphs.
Remark 3 I hope you don't mind a nitpick and piece of good advice: while I am well aware that,
especially in applied mathematics, sets of matrices tend to be written in the form
$(\text{codomain of the linear map described by the matrix})^{(\text{finite cardinal})\times(\text{finite cardinal})}$,
this is only seemingly natural, and I would like to recommend to simply write your matrix as
$\{0,-1,+1\}^{V\times\mathbb{A}}$
instead of the unnecessarily complicated $\{0,-1,+1\}^{\lvert V\rvert\times\lvert\mathbb{A}\rvert}$, which in particular involves the concept of cardinal numbers, which is quite irrelevant to the problem. My recommendation is to simply to label rows and colums by the very things whose relation to one another the matrix is meant to express, unless there is some compelling reason to label the entries by numbers. (And here there is no such reason). This is actually simpler, since then you do not need a total ordering, with numerical labels, on the sets indexing the rows and columns.
Remark 4 A more important criticism: the OP has "$N_A = \{y\colon Ay = 0 \}$" as the definition of the null space, which is simply undefined: it was not specified which module the vector $y$ is supposed to come from. In other words, if $R$ is a commutative ring (as such, it automatically contains $\{0,-1,1\}$), and if $M$ and $N$ are suitable free finite-rank $R$-modules, and if $f_A\colon M\rightarrow N$ is the linear map defined by $A$, then $N_A = \ker(f_A)$, and yet the OP has not specified what the domain $M$ is supposed to be.
One could interpret the appearance of $\mathbb{R}$ in the OP to mean that the asker is only interested in the linear map $\mathbb{R}^{\mathbb{A}}\xrightarrow[]{v\mapsto Av}\mathbb{R}^V$, whereupon e.g. the (problem) below would be moot (since then we would only be dealing with vector spaces), yet it is not completely clear to me that the OP is only interested in real numbers. I recommend to also study the case of integer coefficients; this case is arguably simpler as far as the underlying set-theoretic foundations are concerned, and it is both mathematically more interesting and relevant to some applications.
Remark 5 Permit me to end these syntactical remarks with some carping and cavilling at grammatical minutiae: the OP contains the grammatically correct, but misplaced and unintentionally-funny formulation "Consider $\{y\colon Ay=0\}$ [...] to be its null space." The trouble is that there is nothing to willfully "consider" here: the set defined by the OP already is the null space.
Answer to what seems to be the substance of the OP.
The right setting for your question is the usual linear algebra over principal ideal domains; the question then is a question about the cycle group of a 1-dimensional finite abstract simplicial complex.
I think that a relevant answer to your question is:
Let $G$ denote the undirected graph whose $\{0,1\}$-valued incidence matrix is obtained by forgetting all signs in your matrix $A$. Then the kernel of your matrix $A$ is just the flow lattice of $G$, and it is fair to say that no general theorem about the structure of the set of all $\mathbb{Z}$-bases of a graph is known, and, sadly, probably no noteworthy such general theorem exists .
The flow lattice(terminology) is the same as the cycle group $Z_1(G)=Z_1(G;\mathbb{Z})$ in the sense of classical simplicial homology, in the familiar sense usual at least since Seifert and Threfall's 1934 textbook. It has been generalized to the notion of the flow lattice of an oriented matroid.
I think that currently the best, and sadly perhaps the only, general structural statement relevant to your question is:
Proposition. Every basis of your $N_A$ (and, notably, regardless of the ring or field of coefficients that you use), has the property that every element of the basis has its support equal to a union of graph-theoretic circuits. Somewhat conversely, if $H\subseteq G$ is any subgraph wich is a union of circuits, then there exists a flow $f\in Z_1(G)$ with $\mathrm{Supp}(f) = E(H)$. $\hspace{40pt}$ (circuit-union)
This is well-known, easily proved, and almost obvious. Perhaps the most interesting aspect of it (strictly speaking this is irrelevant to your question) is that this generalizes to arbitrary finite regular matroids: cf. Lemma 9 in [Y. Su, D.G. Wagner, The lattice of integer flows of a regular matroid. Journal of Combinatorial Theory, Series B 100 (2010) 691–70]. (Incidentally, beware that in that article, 'circuit' means the matroid-theoretic notion, not 'graph-theoretic circuit'='2-regular connected graph').
One should certainly also point out to you that:
if $S$ is a rank-sized generating set of a finitely-generated abelian group $A$, then $S$ is a basis of $A$
and hence
whatever set $S$ of $\mathbb{Z}$-generating set of the abelian group $Z_1(G)$ you choose (and such sets can look very unstructured), and if $\lvert S\rvert = \lvert E(G)\rvert - \lvert V(G)\rvert + 1$, then $S$ is a basis of $Z_1(G)$ (which I take to be equal to 'your' null space of $N_A$).
Furthermore, to the question
What's so good about spanning tree bases, i.e. what mathematical reasons are there to give so much prominence to spanning tree bases for $N_A$?
I personally would not have anything better to say than that these bases are the most well-studied and traditional ones, which is not a mathematical reason at all. In particular, the choice of what spanning tree to use to construct a basis is highly arbitrary (typically, the number of spanning trees is exponential in the order of the graph); also, the bases thus obtained are not known to have any noteworthy mathematical quality. In particular, spanning tree bases for $N_A$ tend to contain rather 'long' cycles, which in some contexts can be disadvantageous (think e.g. of fault-tolerance of the basis: if there are many 'long' basis-elements, they are more prone to get damaged).
If the above has not made it clear enough yet, let me spell out explicitly that
A basis of your $N_A$ need not consist of circuit-supported flows only (and probably most bases don't).
(The statistical conjecture just made has not been proved as far as I know.)
Moreover,
I think there does not exist a 'canonical' basis of $N_A$, in any sense deserving the (undefined) term 'canonical'
An open research problem.
The OP clarified their question in a somwewhat unclear comment at Aug 16 '17 at 11:37:
"All incidence vectors of cycles are in the kernel. Also all incidence vectors of cycles that "disregard orientation" are in the kernel if we swap some one entries for -1, to obtain a cycle with correct orientation. I assume they span the whole kernel. There are cases however when we can construct simple cycles from other simple cycles. So we wouldn't get a basis but just a generating set."
It take this to mean:
The signed incidence vector of any oriented circuit is in the kernel. Also, the incidence vector of any flow obtained from an undirected cycle by choosing any of its two orientations is in the cycle. The set of all such flows spans the whole kernel. However, in all but the trivial cases, this set is not a basis but just a generating set.
and that is obviously true.
The OP also remarks in a comment
So we wouldn't get a basis but just a generating set.
which seems to suggest that theh OP may also be interested in knowing more about how generating sets and bases of the flow lattice $Z_1(G)$ are related.
There is an interesting open problem about the relationship between generating sets and bases of $N_A$. This, to the best of my knowledge, is still an open research problem (I find it somewhat deplorable that this 'basic' question seems to be open---of course, it is somewhat undefined):
Research problem. Find an appreciable graph-theoretic/combinatorial/topological characterization of the class of all finite undirected simple graphs $G$ with the property that each generating set of the free finitely-generated abelian group $Z_1(G)$ contains a $\mathbb{Z}$-module basis of $Z_1(G)$.
Hopefully needless to say: for free modules, and even for free $\mathbb{Z}$-modules (= free abelian groups), it is not true4 that every generating set contains a basis, so the above problem is not moot.
I feel duty-bound to have to tell you upfront that even though your question shows some interest in this subject matter, and even though I personally think this is an interesting and open problem, you should not spend your time working on it, for two reasons: (0) it is quite possible that an appreciable answer simply does not exist, (1) in my experience, no one finds the question interesting, sadly.
I have a few conjectures with regard to the above problem, maybe even suitable for an MO question of its own. And yet I think better not to mention them here, if only not to bias anyone trying to solve the problem.
The problem is open, does not require much mathematical knowledge, and is also amenable to computational experimentation. Since you say you are interested in computing, this might be a plus.
Of course, the problem is a rather open-ended and aesthetic problem, in that "appreciable graph-theoretic/combinatorial/topological characterization" is not a mathematically defined term.
A generating set of $N_A$ not containing any basis
Quite unbelievably (since for other modules than $Z_1(G)$, such questions have been studied in detail, cf. e.g. [M2007a][M2007b][MS2012]) the first example of a generating set of $Z_1(G)$ not containing any basis was given in [H2014; Section 1.2.1]. (I would appreciate being shown an earlier publication containing such an example, or even a mention of its existence; I have searched much for this much, in vain.) This example is this:
Figure 2. The elements of the generating set of $N_A$ are represented by the thick black lines,
with the white inlays indicating the direction of the respective flow. Each of the seven
flows in the generating set has its support equal to a graph-theoretic circuit. The underlying
graph is the wheel-graph. Its flow-lattice $N_A$
has $\mathbb{Z}$-rank equal to $12-7+1=6$, hence a basis must have six elements only. The
generating set show has $7>6$ elements, and it can be checked by explicity computations of the
relevant Smith normal forms that leaving out any one of the seven
flows in the generating set results in a non-basis, more precisely, a $\mathbb{Z}$-linearly
independent subset of $N_A$ which generates a subgroup of index larger than one. The large gray arrows indicate the directed edges.
(source: [H2014; p. 4])
The example in Figure 2 sheds on your question, in the sense that the set of all bases of $N_A$ is mysterious and ill-understood, even for rather structured graphsf. E.g., the example in Figure 2 shows that
in general one cannot find all generating sets of $N_A=Z_1(G)$ by first finding all bases and then taking supersets thereof (as one could if one was facing a vector space).
The above, strangely enough, seems not to have been known before [H2014]. Of course, for modules in general, this is a very well-known fact, but for modules of the special form $Z_1(G)$ with $G$ a finite simple undirected graph, this seems not to have been known before, and questions remain.
A theorem about Hamilton-bases for $N_A=Z_1(G)$.
In [H2014], the following was proved, which can be seen as another variation on the theme that the bases for $N_A$ oftentimes can look very different from the familiar spanning-tree-bases:
Theorem. For every $\gamma>0$ there exists $n_0\in\omega$ such that if $n_0\leq n\equiv 3\quad(\text{mod $8$})$, then every finite simple undirected graph $G$ with $n$ vertices and minimum vertex degree at least $(\frac12+\gamma)n$ has the property that the free $\mathbb{Z}$-module $Z_1(G)$ admits a basis consisting only of flows whose support equals a Hamilton-circuit of $G$.
It is almost unimaginable that for the other congruence classes $n_0\leq n\equiv 1\quad(\text{mod $8$})$, $n_0\leq n\equiv 5\quad(\text{mod $8$})$, $n_0\leq n\equiv 7\quad(\text{mod $8$})$ (note that it is necessary for such a result that $n$ be odd), the analogous statement is true, too, but this is not proved. Somewhat interestingly, the only known method for proving such a result depends, simultaneously in a boring yet delicate way, on the remainder of $n$ modulo $8$. With the current methods, it seems that one would basically have to carry out a sizeable part of the proof in [H2014] four times over in order to prove it for every $n_0\leq n\equiv 1\quad(\text{mod $2$})$.
It is probably much more difficult, and perhaps impossible, to get rid of the lower bound $n_0$ (which is super-exponentially large in $\frac{1}{\gamma}$); new methods would be needed, and it seems unlikely that this will ever be done.
Further literature references that the OP may be interested in.
F. Berger, P. Gritzmann, S. de Vries, Minimum Cycle Bases and Their Applications. Springer, LNCS, volume 5515
If you would like to read something reasonably self-contained and textbook-like, and are willing to read a French text, then
[L2012] Francis Lazarus, Topologie Combinatoire et Algorithmique. Notes de Cours. GIPSA-lab. Grenoble. 2012
seems extremely relevant to your question: in a sense, Lazarus's text has just the right emphasis for (what I read into) your question: Lazarus in particular places emphasis on graph-homology with real-valued coefficients.
In particular, Lazarus in the proof of "Proposition 1.1.9" gives a separate argument for why any spanning-tree-obtained set of fundamental cycles is a generating set. To be honest, the author does not really emphasize the fundamental $\mathbb{Z}$-coefficient case, rather does the proof in the context of $\mathbb{R}$-coefficients. In particular, Chapter 2 of Lazarus' text seems extremely relevant to your question. It is concerned with calculating 'good' (in some specified sense) bases of $N_A = Z_1(G)$.
Chapter 3 then broaches the topic of integer coefficients. Chapter 7 treats optimization questions, that you might be particularly interested in.
Footnotes.
(terminology) While the 'flow lattice' is indeed isomorphic to the usual cycle group of $G$ qua simplicial complex, as an abstract abelian group, the term 'cycle group' seems the wrong emphasis, in particular in view of results such as Su and Wagner's on characterizing circuit-supported elements of the flow lattice via the bilinear form on $Z_1(G)$. These are metric, not purely group-theoretic considerations.The lattice $Z_1(G)$ is less interesting as an abstract abelian group, more interesting as a concrete lattice $\subset\mathbb{R}^{ \lvert E(G)\rvert - \lvert V(G) \rvert + 1 }$. Insisting that $Z_1(G) \simeq N_A = \ker (\mathbb{Z}^{\mathbb{A}}\xrightarrow[]{v\mapsto Av}\mathbb{Z}^V) $. Viewing $Z_1(G)$ as a concrete discrete subgroup of $\mathbb{R}^{ \lvert E(G)\rvert - \lvert V(G) \rvert + 1 }$ provides additional structure, and in the case of the flow-lattice, such additional structure can be used in at least three ways:
- The lattice-viewpoint makes it possible to improve the obvious and hackneyed statement 'the orientations of the edge do not matter since the cycle groups are all the same': with the metric point of view, one can use the additional structure to make a stronger statement: not only are all the lattices $Z_1(G)$ obtained by flipping orientations isomorphic as abstract abelian groups, they are even isometric as lattices $\subset$ $\mathbb{R}^{ \lvert E(G)\rvert - \lvert V(G) \rvert + 1 }$ w.r.t the standard inner product (see [SW2010; p. 692).
- The lattice-viewpoint has been put to use by Su and Wagner in [SW2010] to give a metric characterization of circuit-supported elements of $N_A$.
- The lattice-viewpoint has been put to use by Amini in [A2010] to formulate a theorem on Voronoi cells: the abstract abelian group would not enable such results.
Glossary.
'circuit' = '2-regular simple undirected graph', more usually called 'cycles', which is however a less suitable term than the more distinctive 'cycle' in contexts in which $Z_1(G)$ plays a role, since the latter's elements are usually called 'cycles' too. Moreover, the use of 'circuit' in graph theory, though unusual nowadays, is not unheard of: Tutte uses 'circuit' in [T1956], A. Bondy uses 'circuit' in Chapter I.1 of [B1995],
[DG2016] use 'circuit' as opposed to 'cycle', too.
'lattice' = lattice as in lattice, not as in lattice, an unfortunate terminological clash of mathematical English, a clash especially acute in the title of Amini's preprint (where 'lattice-in-the-number-theoretic-sense' occurs side by side with 'poset')
'simple flow' = 'flow in the digraph whose support is a circuit and whose values all have absolute value one' (i.e., arguably the simplest flow one can think of, bar the zero flow; cf. [SW2010])
'spanning-tree basis' = 'the set of elements of $Z_1(G)$ obtained after arbitrarily selecting a spanning tree $T$ of $G$, then (one after another) adding-in an edge of $G$ not in $T$, arbitrarily choosing one of the two orientations of the unique so-called fundamental circuit obtained, and adding the 'simple flow' corresponding to said oriented circuit to the nascent set of flows'
References.
[T1956] W. T. Tutte, A class of abelian groups. Canadian Journal of Mathematics. 1956
[BHN1997] Roland Bacher, Pierre de la Harpe, Tatiana Nagnibeda, The lattice of integral flows and the lattice of integral cuts on a finite graph. Bulletin de la Société mathématique de France 125, fascicule 2 (1997), 167-198
[N2004] Robert Nickel, Das Flussgitter affiner Punktkonfigurationen. Talk. 2004
[NH2007] Robert Nickel, Winfried Hochstättler, The flow lattice of oriented matroids. Contrib. Discrete Math. 2(1). 2007
[M2007a] Jacques Martinet, Bases of minimal vectors in lattices. I., Archiv der Mathematik, Arch. Math. 89, No. 5, 404-410 (2007)
[M2007b] Jacques Martinet, Bases of minimal vectors in lattices. II., Archiv der Mathematik, Arch. Math. 89, No. 6, 541-551 (2007)
[BJG2009] Jørgen Bang-Jensen, Gregory Gutin, Digraphs. Second Edition. Springer. 2009
[SW2010] Yi Su, David G. Wagner, The lattice of integer flows of a regular matroid. Journal of Combinatorial Theory, Series B 100 (2010) 691–703
[A2010] Omid Amini, Lattice of Integer Flows and Poset of Strongly Connected Orientations. arXiv:1007.2456
[L2012] Francis Lazarus, Topologie Combinatoire et Algorithmique. Notes de Cours. GIPSA-lab. Grenoble. 2012
[MS2012] Jacques Martinet, Achill Schürmann,Bases of minimal vectors in lattices. III. Int. J. Number Theory 8, No. 2, 551-567 (2012)
[D2013] Zsuzsanna Dancso, Bipartite algebras and a categorification of the flow lattice of graphs. Talk. 2013
[H2014] Peter Heinig, Hamilton-based flow-lattices, logical limit-laws, and a measure on sign-matrices. Dissertation. TUM. 2014
[DG2016] Zsuzsanna Dancso, Stavros Garoufalidis, A construction of the graphic matroid from the lattice of integer flows. Preprint. arXiv:1611.06282 [math.CO]
