"Main" diagonal of a matrix

Question

Hello!

I'm in search of some (possibly statistical) measure for matrices. I want to classify a square matrix as having the largest numbers running along the main diagonal or along the anitdiagonal. It isn't necessarily on the diagonals, the numbers can be some rows to the left or right, so a simple trace wouldn't work. I want to incorporate the entire matrix in the calculation.

To see how I came to this problem: the matrix A is a transition matrix, for example in a Markov process (I have a CS background). The probability of going from state i to state j is given by $A_{i,j}$. Each row sums up to 1. The states are ordered though, and I would like to know if a certain matrix makes small or no jumps (largest probabilities along main diagonal) or if huge jumps are present (largest probabilities along antidiagonal).

I don't think this problem is very hard, but I'm at loss for the terminology. Thanks!

Answer 1

The following very coarse invariant is perhaps useful:

The argument of the sum $\sum_{s,t}a_{s,t}e^{i(s-t)\pi/n}$ (where $n$ is the size of the matrix and where the sum is over all entries) should be related to a typical jump. It is close to $0$ if the matrix is "concentrated" near the diagonal and close to $\pi$ if the matrix is "concentrated" near the antidiagonal. The modulus of the above sum indicates somehow how much the matrix is concentrated.

Answer 2

One rigorous idea which is similar to your question is to look for the largest "transversal" of the matrix. A transversal is a collection of entries of the matrix with one entry from each row and column. The terms in the determinant of the matrix are multiplicative transversals, but for this question, you would be interested in the maximum additive transversal. There are polynomial time algorithms to find the largest transversal. You can view it as the optimum marriage problem, or as a min-cut, max-flow problem, but it ultimately comes from the fact that you are maximizing a linear functional (the value of the transversal) on the Birkhoff polytope, which is the convex hull of the permutation matrices. As such, it is a linear programming problem. The remaining question is how best to speed it up further, using the fact that it is a special case rather than general linear programming. There is a noted paper on this subject, On Algorithms for Obtaining a Maximum Transversal, by Duff.

Note that the question isn't an either-or between the diagonal and the anti-diagonal. There are many things that a transversal can do other than be close to the diagonal or anti-diagonal. Even so, you can look at how close the transversal is to one or the other extreme. For instance, you can look at its inversion number. The diagonal has the smallest inversion number, 0, while the antidiagonal has the unique largest inversion number, $n(n-1)/2$.

A slightly different idea is to look at correlations between the inversion number and the value of the transversal. I think some types of correlation can also be computed in polynomial time.