Rearranging MatricesDate: 11/5/95 at 4:28:28 Subject: MATH QUESTION 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 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 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 |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/