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

[Ravi Varadhan]

Jonathan,

You can find the permutation of A that maximizes its trace by minimizing
||PA - I|| in Frobenius norm, where P is the permutation matrix, A is a
square matrix, and I is the identity matrix.

Here is the code that solves the abovementioned problem:

pMatrix.min <- function(A, B) {
# finds the permutation P of A such that ||PA - B|| is minimum in Frobenius
norm 
# Uses the linear-sum assignment problem (LSAP) solver in the "clue" package

# Returns P%*%A and the permutation vector `pvec' such that 
# A[pvec, ] is the permutation of A closest to B
	n <- nrow(A)
	D <- matrix(NA, n, n)
	for (i in 1:n) {
	for (j in 1:n) {
	D[j, i] <- (sum((B[j, ] - A[i, ])^2))
	} }
vec <- c(solve_LSAP(D))
list(A=A[vec,], pvec=vec)
}

require(clue)  # need this package to solve the LSAP 

A <- matrix(sample(1:25, size=25, rep=FALSE),  5,  5)

B <- diag(1, nrow(A)) # this choice of B maximizes the trace of permuted A

X <- pMatrix.min(A,B)

A  # original square matrix

X$A  # permuted A such that its trace is maximum among all permutations


Hope this helps,
Ravi.

-----Original Message-----
From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org] On
Behalf Of Jonathan
Sent: Monday, April 26, 2010 2:53 PM
To: Dennis Murphy
Cc: r-help
Subject: Re: [R] reordering of matrix rows to maximize the sum of the
diagonal

Hi Dennis,
   Thanks for the idea, but the order of the rowSums does not
necessarily correspond to the order of rows that maximizes the "rank"
of the matrix.

Ex:
> a[1:9]<-c(1,1,30,50,1,1,1,20,1)

> a
     [,1] [,2] [,3]
[1,]    1   50    1
[2,]    1    1   20
[3,]   30    1    1

> a[order(rowSums(a)),]

     [,1] [,2] [,3]
[1,]    1    1   20
[2,]   30    1    1
[3,]    1   50    1


In this case, I would like to rearrange the original matrix into:

     [,1] [,2] [,3]
[1,]   30    1    1
[2,]    1   50    1
[3,]    1    1   20

Best,
Jonathan

On Sat, Apr 24, 2010 at 1:24 AM, Dennis Murphy <djmuser at gmail.com> wrote:
> Hi:
>
> How about this? Calling your matrix a,
>
> a[order(rowSums(a)), ]
>      [,1] [,2] [,3]
> [1,]    9    1    2
> [2,]    2   11    1
> [3,]    3    4   13
>
> HTH,
> Dennis
>
>
> On Fri, Apr 23, 2010 at 1:10 PM, Jonathan <jonsleepy at gmail.com> 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.
>
>

______________________________________________
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.