[sage-support] Re: Graphs from binary incidence matrices
On 2013-04-17, Tom Boothby tomas.boot...@gmail.com 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
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
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 tomas.boot...@gmail.com 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.
[sage-support] Re: Graphs from binary incidence matrices
On 2013-04-17, Michael Welsh yom...@yomcat.geek.nz 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) ipython-input-1-cf6c24cef566 in module() 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.
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 dimp...@gmail.com wrote: On 2013-04-17, Michael Welsh yom...@yomcat.geek.nz 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) ipython-input-1-cf6c24cef566 in module() 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.
