Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
column permutation to minimize the trace

Subject: column permutation to minimize the trace

From: John D'Errico

Date: 5 Feb, 2009 18:50:04

Message: 1 of 10

An interesting question popped up in something I was playing around with.

Given an nxn matrix of positive numbers, find the column permutation which minimizes the trace. trace(A) = sum(diag(A))

When n is small enough, it is simple enough to test all permutations. But for n relatively large, I'm willing to accept a decent suboptimal solution. Any ideas out there?

Thanks,
John

Subject: column permutation to minimize the trace

From: Roger Stafford

Date: 5 Feb, 2009 19:33:01

Message: 2 of 10

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <gmfccs$m11$1@fred.mathworks.com>...
> An interesting question popped up in something I was playing around with.
>
> Given an nxn matrix of positive numbers, find the column permutation which minimizes the trace. trace(A) = sum(diag(A))
>
> When n is small enough, it is simple enough to test all permutations. But for n relatively large, I'm willing to accept a decent suboptimal solution. Any ideas out there?
>
> Thanks,
> John

  Yes, I recognize that problem. An equivalent question occurred in the thread "does Matlab have any such function" at

 http://www.mathworks.com/matlabcentral/newsreader/view_thread/243618

except that it was to maximize the trace.

  I haven't thought of a good way of doing it either, John. Now that you dignify it using the "trace" concept, maybe it will trigger some ideas out there. If so, it would make the OP of that thread very happy. He is facing a several year wait with a 15 x 15 matrix to generate all 15! permutations.

  I can say that choosing the column that has the largest element in the matrix, then eliminating its column and row and choosing the largest remaining element, and so on down to the last column, does not necessarily get you there. However it makes a good start. I thought of continually switching pairs of columns whenever that reduces the trace and keeping this up until no such switch improved things. However I am not sure that will get you to the true minimum.

Roger Stafford

Subject: column permutation to minimize the trace

From: Roger Stafford

Date: 5 Feb, 2009 19:44:02

Message: 3 of 10

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gmfetd$d10$1@fred.mathworks.com>...
> ......
> I can say that choosing the column that has the largest element in the matrix, then eliminating its column and row and choosing the largest remaining element, .....

  I meant "smallest" here instead of "largest".

Roger Stafford

Subject: column permutation to minimize the trace

From: Bjorn Gustavsson

Date: 6 Feb, 2009 09:32:02

Message: 4 of 10

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <gmfccs$m11$1@fred.mathworks.com>...
> An interesting question popped up in something I was playing around with.
>
> Given an nxn matrix of positive numbers, find the column permutation which minimizes the trace. trace(A) = sum(diag(A))
>
> When n is small enough, it is simple enough to test all permutations. But for n relatively large, I'm willing to accept a decent suboptimal solution. Any ideas out there?
>
I haven't got a full solution to this...

...but sorting is cheap so I would start with:
[sM,indx] = sort(A);
...then
if length(unique(indx(1,:))) == size(M,2)
% we should have all the smallest elements in each column on
% the diagonal after
Aoptimal = A(:,indx(1,:));
else
% TBD
end

This way we can at least search for permutations starting at solutions with minimum sum for parts of the diagonal.

Subject: column permutation to minimize the trace

From: John D'Errico

Date: 6 Feb, 2009 19:26:02

Message: 5 of 10

"Bjorn Gustavsson" <bjonr@irf.se> wrote in message <gmh02h$8i5$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <gmfccs$m11$1@fred.mathworks.com>...
> > An interesting question popped up in something I was playing around with.
> >
> > Given an nxn matrix of positive numbers, find the column permutation which minimizes the trace. trace(A) = sum(diag(A))
> >
> > When n is small enough, it is simple enough to test all permutations. But for n relatively large, I'm willing to accept a decent suboptimal solution. Any ideas out there?
> >
> I haven't got a full solution to this...
>
> ...but sorting is cheap so I would start with:
> [sM,indx] = sort(A);
> ...then
> if length(unique(indx(1,:))) == size(M,2)
> % we should have all the smallest elements in each column on
> % the diagonal after
> Aoptimal = A(:,indx(1,:));
> else
> % TBD
> end
>
> This way we can at least search for permutations starting at solutions with minimum sum for parts of the diagonal.

For anyone who cares, I've got a code that solves
the 15x15 case in typically about a second.

A = rand(15);
tic,[P,tr] = mintrace(A);toc
Elapsed time is 1.169739 seconds.

tr
tr =
       1.4637

P
P =
     7 14 15 1 3 11 5 13 10 9 12 8 2 6 4
 
It is not 100% correct on all problems, but in
the 15x15 case, I get a global solution about
80-90% of the time. Even when not the global
solution, I'm within about 10% in my tests.
I've tried it on up to 100x100 problems with
reasonable success.

Since the 15x15 case requires 1e12 tests for
the brute force solution, I'm happy with this.
The 100x100 case needs a few more tests.

933262154439441526816992388562667004907
159682643816214685929638952175999932299
156089414639761565182862536979208272237
582511852109168640000000000000000000000
00
 
John

Subject: column permutation to minimize the trace

From: Roger Stafford

Date: 6 Feb, 2009 20:13:02

Message: 6 of 10

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <gmi2sa$jbc$1@fred.mathworks.com>...
> For anyone who cares, I've got a code that solves
> the 15x15 case in typically about a second.
>
> A = rand(15);
> tic,[P,tr] = mintrace(A);toc
> Elapsed time is 1.169739 seconds.
>
> tr
> tr =
> 1.4637
>
> P
> P =
> 7 14 15 1 3 11 5 13 10 9 12 8 2 6 4
>
> It is not 100% correct on all problems, but in
> the 15x15 case, I get a global solution about
> 80-90% of the time. Even when not the global
> solution, I'm within about 10% in my tests.
> I've tried it on up to 100x100 problems with
> reasonable success.
>
> Since the 15x15 case requires 1e12 tests for
> the brute force solution, I'm happy with this.
> The 100x100 case needs a few more tests.
>
> 933262154439441526816992388562667004907
> 159682643816214685929638952175999932299
> 156089414639761565182862536979208272237
> 582511852109168640000000000000000000000
> 00
>
> John

  Yesterday working only with the simpler 6 x 6 case, I had similar results to yours John. I was using the method of interchanging pairs whenever that helped until no further progress is made, and it was easy to check for accurate minimality by comparison with all 720 possibilities. Starting with a randperm permutation it arrived at the correct minimum something like your percentage of the time. However, repeating this process with random starting points a number of times got there about 99% of the time.

  For the 15 x 15 case clearly this method of switching pairs would take longer but it would probably not be prohibitively long. I rather suspect that the odds of getting to a true minimum would be rather small this way however and would require a large number of random repeats to have a likely success. I don't know of any practical way of checking the results except to note the nature of gradual improvements in the minimums found by the various random starts.

Roger Stafford

Subject: column permutation to minimize the trace

From: John D'Errico

Date: 6 Feb, 2009 21:44:02

Message: 7 of 10

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gmi5ke$lnj$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <gmi2sa$jbc$1@fred.mathworks.com>...
> > For anyone who cares, I've got a code that solves
> > the 15x15 case in typically about a second.
> >
> > A = rand(15);
> > tic,[P,tr] = mintrace(A);toc
> > Elapsed time is 1.169739 seconds.
> >
> > tr
> > tr =
> > 1.4637
> >
> > P
> > P =
> > 7 14 15 1 3 11 5 13 10 9 12 8 2 6 4
> >
> > It is not 100% correct on all problems, but in
> > the 15x15 case, I get a global solution about
> > 80-90% of the time. Even when not the global
> > solution, I'm within about 10% in my tests.
> > I've tried it on up to 100x100 problems with
> > reasonable success.
> >
> > Since the 15x15 case requires 1e12 tests for
> > the brute force solution, I'm happy with this.
> > The 100x100 case needs a few more tests.
> >
> > 933262154439441526816992388562667004907
> > 159682643816214685929638952175999932299
> > 156089414639761565182862536979208272237
> > 582511852109168640000000000000000000000
> > 00
> >
> > John
>
> Yesterday working only with the simpler 6 x 6 case, I had similar results to yours John. I was using the method of interchanging pairs whenever that helped until no further progress is made, and it was easy to check for accurate minimality by comparison with all 720 possibilities. Starting with a randperm permutation it arrived at the correct minimum something like your percentage of the time. However, repeating this process with random starting points a number of times got there about 99% of the time.
>
> For the 15 x 15 case clearly this method of switching pairs would take longer but it would probably not be prohibitively long. I rather suspect that the odds of getting to a true minimum would be rather small this way however and would require a large number of random repeats to have a likely success. I don't know of any practical way of checking the results except to note the nature of gradual improvements in the minimums found by the various random starts.
>
> Roger Stafford

The probem with only swapping pairs is you can
get stuck in a local minimum on these problems.
I'd not be surprised if there exists a small matrix
such that purely pairwise swaps of columns will
fail to work. Since I did try a pairwise scheme,
and I saw it fail to converge on some problems,
I'll claim this to be true without constructing an
example.

It helps to do some other things too, like a quick
check to verify that a global solution is possible
via a direct sort.

John

Subject: column permutation to minimize the trace

From: Roger Stafford

Date: 6 Feb, 2009 22:23:01

Message: 8 of 10

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <gmiav2$8pe$1@fred.mathworks.com>...
> The probem with only swapping pairs is you can
> get stuck in a local minimum on these problems.
> I'd not be surprised if there exists a small matrix
> such that purely pairwise swaps of columns will
> fail to work. Since I did try a pairwise scheme,
> and I saw it fail to converge on some problems,
> I'll claim this to be true without constructing an
> example.
>
> It helps to do some other things too, like a quick
> check to verify that a global solution is possible
> via a direct sort.
>
> John

  Well, yes that is indeed what occurs. When all n*(n-1)/2 pairwise swaps have been tried without improvement, that is where my trials stopped, either at a true minimum or, as you say, "stuck in a local minimum". It all depends on where you start. It was only by restarting with a number of randomly selected initial permutations from randperm that a true minimum could be attained, but for 6 x 6 matrices that was almost always possible with a few tries. For 15 x 15 it might be a very different matter, though it does puzzle me how you can be sure you are not merely at a "local minimum" by any method without the several-year wait from the brute force method for verification. What have you tried - using three-element permutation adjustments or something like that?

Roger Stafford

Subject: column permutation to minimize the trace

From: John D'Errico

Date: 6 Feb, 2009 23:57:02

Message: 9 of 10

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gmid85$8ts$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <gmiav2$8pe$1@fred.mathworks.com>...
> > The probem with only swapping pairs is you can
> > get stuck in a local minimum on these problems.
> > I'd not be surprised if there exists a small matrix
> > such that purely pairwise swaps of columns will
> > fail to work. Since I did try a pairwise scheme,
> > and I saw it fail to converge on some problems,
> > I'll claim this to be true without constructing an
> > example.
> >
> > It helps to do some other things too, like a quick
> > check to verify that a global solution is possible
> > via a direct sort.
> >
> > John
>
> Well, yes that is indeed what occurs. When all n*(n-1)/2 pairwise swaps have been tried without improvement, that is where my trials stopped, either at a true minimum or, as you say, "stuck in a local minimum". It all depends on where you start. It was only by restarting with a number of randomly selected initial permutations from randperm that a true minimum could be attained, but for 6 x 6 matrices that was almost always possible with a few tries. For 15 x 15 it might be a very different matter, though it does puzzle me how you can be sure you are not merely at a "local minimum" by any method without the several-year wait from the brute force method for verification. What have you tried - using three-element permutation adjustments or something like that?
>
> Roger Stafford

Yes, my scheme searches for multiple swaps. Even
if you check all sets of 5 columns, there are only
a few thousand of them to look at.

nchoosek(15,5)
ans =
        3003

I also did a few other things to accelerate the
search. Even with that, I can still get stuck on some
larger problems.

As for testing, I did a few things to be confident
of whether I had found a global solution. For n=15,
it is small enough that I could be confident of
whether I'd succeeded just by doing multiple runs
with a randomly permuted starting point.

A better approach was to start with a matrix that I
knew had a solution, but that might be moderately
difficult to solve. Then permute the matrix, and see
if I could recover the known minimal trace. For
example try this one:

  A = 1 - eye(40);
  A = A.*(rand(40)>.15);
  nnz(A)
ans =
        1328

Now, permute the columns of A randomly.

  Ap = A(:,randperm(40));

We know that A had a trace of zero, and that no
smaller trace can exist. Also, because all of the
elements are 0 or 1, it might get stuck at times.
While there may be several permutations that will
recover a trace of zero, can I find any such
permutation?

 tic
 [P,tr] = mintrace(A);
 toc
 tr

Elapsed time is 1.642908 seconds.

tr =
     0

Did I find the original permutation?

nnz(A-A(:,P))
ans =
   228

Clearly not. No surprise there.

John

Subject: column permutation to minimize the trace

From: Steven Lord

Date: 11 Feb, 2009 04:42:11

Message: 10 of 10


"John D'Errico" <woodchips@rochester.rr.com> wrote in message
news:gmfccs$m11$1@fred.mathworks.com...
> An interesting question popped up in something I was playing around with.
>
> Given an nxn matrix of positive numbers, find the column permutation which
> minimizes the trace. trace(A) = sum(diag(A))
>
> When n is small enough, it is simple enough to test all permutations. But
> for n relatively large, I'm willing to accept a decent suboptimal
> solution. Any ideas out there?

Treat the matrix as an assignment problem, solve it, and find the
permutation that puts the selected elements on the diagonal of A?

http://en.wikipedia.org/wiki/Assignment_problem

Looking at the Wikipedia page for the Hungarian Algorithm (used for solving
the assignment problem) there's a link to a File Exchange submission:

http://www.mathworks.com/matlabcentral/fileexchange/6543

--
Steve Lord
slord@mathworks.com

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us