The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Rearranging Matrices

Date: 11/5/95 at 4:28:28
From: Ken Schmidt

Thank you for your service!  My problem involves matrices,
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 

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

Ken Schmidt

Date: 11/6/95 at 0:55:54
From: Doctor Jonathan

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 
time.  Any of these methods could be adapted to your problem.  
Basically, your problem can not be answered in polynomial time, 
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.