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