Gregory Bard wrote: > Once in a while one has a sparse square matrix, and one might wonder > if it is > a matrix in block form, but permuted. This can be hard to recognize by > eye > if the matrix is big. It turns out one can determine this VERY > quickly. The > graph which has an adjacency matrix equal to the matrix under > discussion > will have a connected component for each block. In fact, a Depth First > Search > will not only identify the number of connected-components but also > their memberships, > essentially producing the permutation matrix that we want. > > So one could imagine a SAGE command, given a matrix A, that would > output > the number of blocks, and a permutation matrix P such that PAP^-1 is > in > block form. > > Perhaps this is already in SAGE. If not, perhaps I should write it?
That would be great! Here is some functionality that is in sage to help you get started. Please let me know if there is something you don't understand in the sage session below. sage: a=matrix([[1,2,0,0],[3,4,0,0],[0,0,5,6],[0,0,7,8]]); a [1 2 0 0] [3 4 0 0] [0 0 5 6] [0 0 7 8] sage: p=Permutation([1,3,2,4]) sage: p.to_matrix() [1 0 0 0] [0 0 1 0] [0 1 0 0] [0 0 0 1] sage: perm_matrix=p.to_matrix() sage: (perm_matrix^-1) # inverse [1 0 0 0] [0 0 1 0] [0 1 0 0] [0 0 0 1] sage: permuted_a=(perm_matrix^-1)*a*perm_matrix; permuted_a [1 0 2 0] [0 5 0 6] [3 0 4 0] [0 7 0 8] sage: g=Graph(permuted_a); g Graph on 4 vertices sage: blocks=g.connected_components(); blocks [[0, 2], [1, 3]] sage: g.connected_components_number() 2 sage: g.connected_component_containing_vertex(0) [0, 2] sage: # Graphs are 0-based indexing, while permutations are 1-based. sage: graph_p=Permutation([i+1 for i in flatten(blocks)]); graph_p [1, 3, 2, 4] sage: graph_p.to_matrix() [1 0 0 0] [0 0 1 0] [0 1 0 0] [0 0 0 1] sage: graph_p==p True > This came up > in a real research problem that a colleague of mine, Prof Robert > Lewis, is > working on. Surely this small function doesn't really need a package > of its own... > like the Method of Four Russians got... so how do you handle that? > Does it get > coded into an existing package? Shall I just write up the pseudocode > for one > of your more junior project members to code up? Or is this already > built-in? I don't think the function is already there. I think the best way to do things is to write it up as a function and post it back here on the mailing list and work from there. Thanks for helping! Jason --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
