Vijay Venkat Raghavan N a écrit :
> hi, > > well am not really sure about this stuff, but i guess if theres a 1 in each > row and each coloum initially, then it is rearrangeable. i am not able to > think of a rigorous proof as of now. > > -Vijay > > On 3/18/06, kool_guy <[EMAIL PROTECTED]> wrote: > > > > > > Let A be a "n by n" matrix. A is rearrangeable if there is a way to > > swap rows with rows, and columns with columns, such that after the > > swapping, all diagonal entries of A are equal to 1. > > > > Can someone give an algorithm that determines whether a matrix is > > rearrangeable? Thanks. > > > hi, > well am not really sure about this stuff, but i guess if theres a 1 in > each row and each coloum initially, then it is rearrangeable. i am not > able to think of a rigorous proof as of now.<br> I think you cannot think of a proof because it is false. For example the matrix 0 1 0 0 1 0 1 0 1 So you need to add some conditions, for example, there is one and only one 1 in every row and every column than the matrix is rearrangeable (you can prove it recursively). This isn't the strongest condition though. Intuitively, you need to be able to remove the "extra" 1's and get a single 1 in every row and every column. Something like "if there are 1 in one row than there needs to be another 1 in the same position as one of the 1's in that column" hope you can work it out! thx --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
