Associated Topics || Dr. Math Home || Search Dr. Math

### Rearranging Matrices

```
Date: 11/5/95 at 4:28:28
Subject: MATH QUESTION
From: Ken Schmidt

specifically 9x9 size.  I would like to know how to determine
what order to rearrange the rows so the numbers in the diagonal
add up to the maximum possible value.  I've done this with a 6x6
matrix, but only by listing all the possibilities in a spreadsheet
and having it calculate each diagonal value.  For example,
consider the following 6x6 matrix:

Row #1    88  50  75  91  72  65
Row #2    75  65  72  30  65  75
Row #3    62  67  77  41  50  80
Row #4    90  69  73  70  57  79
Row #5    42  55  71  72  69  66
Row #6    67  60  76  62  71  57

The correct order to get the maximum diagonal sum is:

Row #4    90  69  73  70  57  79
Row #2    75  65  72  30  65  75
Row #6    67  60  76  62  71  57
Row #1    88  50  75  91  72  65
Row #5    42  55  71  72  69  66
Row #3    62  67  77  41  50  80

The diagonal total is 90+65+76+91+69+80 = 471

But listing all the possibilities isn't practical for a 9x9
matrix!

So I wondered if there is a formula or method to calculate this
maximum value.  Thank you.

Ken Schmidt
ken.schmidt@passport.com
```

```
Date: 11/6/95 at 0:55:54
From: Doctor Jonathan
Subject: Re: MATH QUESTION

I really can't think of any way to guarantee this except for
trying all the combinations of the rows. I think your problem is
analogous to the traveling salesman problem, a famous problem
whose exact solution requires a prodigious amount of computational
steps for any appreciable size of n (proportional to n factorial).

The problem is to figure out the optimal ordering of cities for a
person to visit such that they travel the least total distance. In
fact, it would actually be pretty easy to prove that the traveling
salesman problem is equivalent or harder than yours from a
standpoint of computational complexity.

You might want to look up some of the literature on the
Traveling Salesman problem. Many people have come up with methods
for making good guesses at the solution in reasonable amounts of
which is commonly considered a requirement for an algorithm to be
computable by practical standards.

-Doctor Jonathan,  The Geometry Forum

```
Associated Topics:
High School Linear Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search