subspaces of incidence matrices

*To*: mathgroup at smc.vnet.net*Subject*: [mg21676] subspaces of incidence matrices*From*: axc at gamow.ces.cwru.edu*Date*: Fri, 21 Jan 2000 04:00:36 -0500 (EST)*Organization*: Case Western Reserve University*Sender*: owner-wri-mathgroup at wolfram.com

the incidence matrix of a digraph with n vertices and m unweighed (directed) edges is an nxm matrix over {-1,0,1}. it's a representation of the boundary operator for the graph and its kernel is the basis for the space of (1) cycles. however, these basis elements may have some edges 'flipped'. in my application it's important to keep track of the cycles which are oriented in the same way as in the original graph. seems obvious that such cycles obey the 'sector' condition that their nonzero entries must agree in sign. however, the vectors returned by NullSpace[] are not invariant with respect to permutations of columns of the incidence matrix. anyone know if it's possible to determine at least the size of the subspace spanned by such sector cycles or even how to manipulate the incidence to get a basis for these special cycles directly? as an example: let a graph on 4 vertices have incidence matrix D1 = {{-1,0,1,0,1},{1,-1,0,0,0},{0,1,-1,-1,0},{0,0,0,1,-1}}. NullSpace[D1] returns {{1,1,0,1,1},{1,1,1,0,0}} both of these cycles are sector cycles since each of their nonzero entries have the same sign. however, interchanging the 1st and 3rd columns of D1 gives D2 = {{1,0,-1,0,1},{0,-1,1,0,0},{-1,1,0,-1,0},{0,0,0,1,-1}} NullSpace[D2] returns {{-1,0,0,1,1},{1,1,1,0,0}}. if i had not known about D1 this might lead me to believe (simplistically) that the subspace of sector cycles is 1-dimensional, but in reality {-1,0,0,1,1}+{1,1,1,0,0}={0,1,1,1,1} which is a sector cycle, so there is no invariance in that sense. alan calvitti systems and control case western reserve university