Minimizing numbers along diagonal

Question

Please forgive my ignorance if this isn't the appropriate place to ask this question, I'm by no means an expert in statistics.

I'll omit most of the esoteric linguistic details here, but I've run up against a roadblock using Excel, where I am trying to minimize the values along the diagonal, (top left to bottom right.) I would prefer smallest numbers to be near the diagonal, and larger numbers to be farthest away from it.

There are only two constraints;

(1) Individual cells may not move, only rows and columns; i.e. the relationship between all values along the a row or column must be maintained with any move.

(2) For every shift in a row there has to be a symmetric movement in columns. e.g. if row 3 is moved down three, column C must be moved right by three as well.

I'm open to using any kind of software and reformatting my data in any way, I'll post some photos below to give some clues as to what kind of operations I am hoping to perform. It is possible that the minum values are already closest to the diagonal in the second photo, but I want to be able to statistically prove that the numbers cannot be any lower.

Thanks in advance

---

The first graph is a screenshot of the raw data; it shows the similarity (lower numbers are more similar) between letters in the pre-classical Arabic language. The data is in alphabetical order, but for my purpose this order is arbitrary.

The second is my attempt at organizing based on some educated guesses at how the phonology could have been; in this design the letters that are closest to each other are more similar to each other, and thus have lower numbers.

Answer 1

Your second example looks to me like you did a pretty good job (so I wouldn't expect to improve upon it much). Your constraint 1 is pretty typically, but I've never seen constraint 2 before, so you may need a novel solution. See the references for some examples of ordering tables, it may be possible to estimate the hierarchical clustering solutions for the rows and columns and then cut the dendrogram in an arbitrary way to suit your needs. (Or there may be other heuristic solutions based on PCA that will work for your example.) Although those don't focus specifically on the diagonal.

A simple technique is to order by row and/or column sums, so just see for your example if there are any rows/columns that stick out. That is easy enough to do in excel ;)

Also I would avoid the red-green color scale. Stephen Few has some applicable suggestions here. With only 5 values you may ditch the numbers all together and use a sequential color ramp.

References

• Pilhofer, Alexander, Alexander Gribov, Antony Unwin (2012) Comparing clustering using Bertin’s idea. IEEE Transactions on Visualization and Computer Graphics 18(12):2506-2515. PDF here.
• Wilkinson, Leland and Michael Friendly (2009). The history of the cluster heat map. The American Statistician 63(2): 179-184. Pre-print PDF here.