[R] reordering of matrix rows to maximize the sum of the diagonal

[Jonathan]

David, I'm not entirely sure at first glance (guess this is part of
the problem!), but after a little searching around, it does look like
this can be addressed using the "Hungarian algorithm," which reorders
the rows of a (square) matrix to minimize the sum of the elements
along the diagonal (the trace of the matrix).  I'd just need to change
the algorithm to return the maximum instead of the minimum.

Here is a link I found to a discussion thread with some information:
http://www.reddit.com/r/math/comments/aes47/anyone_know_a_good_algorithm_to_maximize_the/

And some good pseudocode:
http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html

Actually, it appears the "seriation" package in R could come in handy here..

I'll write back if I find more.

Jonathan


On Fri, Apr 23, 2010 at 4:20 PM, David Winsemius <dwinsemius at comcast.net> wrote:
> Can you specify how you would re-order this matrix:
>
> matrix(1:16, 4,4)
>
>> apply(mtx, 2, which.max)
> [1] 4 4 4 4
>
> --
> David.
> On Apr 23, 2010, at 4:10 PM, Jonathan wrote:
>
>> Hi r-help community,
>>   This question isn't so much a syntax/coding one, but here goes:
>>
>> Let's say I have matrix of arbitrary dimensions and I'd like to
>> reorder the rows in such a way that I could maximize the sum of the
>> entries along the diagonal.
>>
>> For example, for this 3x3 matrix:
>>
>>
>>    [,1] [,2] [,3]
>> [1,]    3    4   13
>> [2,]    9    1    2
>> [3,]    2   11    1
>>
>> rearranging the rows to maximize the sum along the diagonal would
>> produce this matrix:
>>
>>    [,1] [,2] [,3]
>> [1,]    9    1    2
>> [2,]    2   11    1
>> [3,]    3    4   13
>>
>>
>> I've been experimenting with some scripts of my own, but I figured I'd
>> ask if one of you R-ninjas might know of an existing function (or
>> algorithm I could look up and then code) that can do this somewhat
>> efficiently (or even just correctly!).
>>
>> Best,
>> Jonathan
>>
>> ______________________________________________
>> R-help at r-project.org mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-help
>> PLEASE do read the posting guide
>> http://www.R-project.org/posting-guide.html
>> and provide commented, minimal, self-contained, reproducible code.
>
> David Winsemius, MD
> West Hartford, CT
>
>