Re: [sage-support] Re: Graphs from binary incidence matrices
That might not have been terribly clear -- the point is, "incidence" of edges and vertices is a binary relation. One needs to make a choice to orient the matrix to make the linear algebra coincidence work out. On Mon, Apr 22, 2013 at 8:51 AM, Tom Boothby wrote: >> Yes it does, in a way. If you want to construct the Laplacian matrix L of the >> graph from the incidence matrix E just by using matrix multiplication, >> you need to pick up an orientation for each edge, i.e. assigning +1 to >> one end, and -1 to the other. Then, bingo, you have L=E.T*E > > I've always seen that described as: "take a random orientation of an > incidence matrix and multiply it by its transpose to get the > Laplacian". -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-support] Re: Graphs from binary incidence matrices
> Yes it does, in a way. If you want to construct the Laplacian matrix L of the > graph from the incidence matrix E just by using matrix multiplication, > you need to pick up an orientation for each edge, i.e. assigning +1 to > one end, and -1 to the other. Then, bingo, you have L=E.T*E I've always seen that described as: "take a random orientation of an incidence matrix and multiply it by its transpose to get the Laplacian". -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-support] Re: Graphs from binary incidence matrices
On 2013-04-17, Tom Boothby wrote: > Dima, > > Rows correspond to vertices and columns correspond to edges. This > matrix represents an undirected triangle with a double edge. I don't > understand why the graph __init__ requires a +1 and a -1 in each > column -- that describes a directed incidence matrix, and has no place > in undirected graphs. Yes it does, in a way. If you want to construct the Laplacian matrix L of the graph from the incidence matrix E just by using matrix multiplication, you need to pick up an orientation for each edge, i.e. assigning +1 to one end, and -1 to the other. Then, bingo, you have L=E.T*E Dima -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-support] Re: Graphs from binary incidence matrices
Dima, Rows correspond to vertices and columns correspond to edges. This matrix represents an undirected triangle with a double edge. I don't understand why the graph __init__ requires a +1 and a -1 in each column -- that describes a directed incidence matrix, and has no place in undirected graphs. On Wed, Apr 17, 2013 at 4:46 AM, Dima Pasechnik wrote: > On 2013-04-17, Michael Welsh wrote: >> I have some GF(2) matrices that are incidence matrices of undirected graphs. >> When I try to construct the graphs in sage, this happens: >> >> sage: Graph(matrix(GF(2), [[1,0,1,1],[1,1,0,1],[0,1,1,0]])) > > it's not even clear what two parallel edges should lead to. Should they > "cancel" each other? > >> --- >> ValueErrorTraceback (most recent call last) >> in () >> > 1 Graph(matrix(GF(Integer(2)), >> [[Integer(1),Integer(0),Integer(1),Integer(1)],[Integer(1),Integer(1),Integer(0),Integer(1)],[Integer(0),Integer(1),Integer(1),Integer(0)]])) >> >> /Applications/sage/local/lib/python2.7/site-packages/sage/graphs/graph.pyc >> in __init__(self, data, pos, loops, format, boundary, weighted, >> implementation, sparse, vertex_labels, name, multiedges, >> convert_empty_dict_labels_to_None) >>1288 multiedges = ( len(uniq(positions)) < total ) >>1289 except AssertionError: >> -> 1290 raise ValueError(msg) >>1291 num_verts = data.nrows() >>1292 elif format == 'Graph': >> >> ValueError: Non-symmetric or non-square matrix assumed to be an incidence >> matrix: Each column represents an edge: -1 goes to 1. >> sage: >> >> Is there a way around this, apart from manually changing each column so that >> it has a -1 in it? >> >> Michael >> > > -- > You received this message because you are subscribed to the Google Groups > "sage-support" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-support+unsubscr...@googlegroups.com. > To post to this group, send email to sage-support@googlegroups.com. > Visit this group at http://groups.google.com/group/sage-support?hl=en. > For more options, visit https://groups.google.com/groups/opt_out. > > -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-support] Re: Graphs from binary incidence matrices
On 2013-04-17, Michael Welsh wrote: > I have some GF(2) matrices that are incidence matrices of undirected graphs. > When I try to construct the graphs in sage, this happens: > > sage: Graph(matrix(GF(2), [[1,0,1,1],[1,1,0,1],[0,1,1,0]])) it's not even clear what two parallel edges should lead to. Should they "cancel" each other? > --- > ValueErrorTraceback (most recent call last) > in () > > 1 Graph(matrix(GF(Integer(2)), > [[Integer(1),Integer(0),Integer(1),Integer(1)],[Integer(1),Integer(1),Integer(0),Integer(1)],[Integer(0),Integer(1),Integer(1),Integer(0)]])) > > /Applications/sage/local/lib/python2.7/site-packages/sage/graphs/graph.pyc in > __init__(self, data, pos, loops, format, boundary, weighted, implementation, > sparse, vertex_labels, name, multiedges, convert_empty_dict_labels_to_None) >1288 multiedges = ( len(uniq(positions)) < total ) >1289 except AssertionError: > -> 1290 raise ValueError(msg) >1291 num_verts = data.nrows() >1292 elif format == 'Graph': > > ValueError: Non-symmetric or non-square matrix assumed to be an incidence > matrix: Each column represents an edge: -1 goes to 1. > sage: > > Is there a way around this, apart from manually changing each column so that > it has a -1 in it? > > Michael > -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
