Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
On thinking it through, this seems pretty much what I search. Thanks! –  Verhoevenv May 27 '10 at 21:11

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.

share|improve this answer
    
Interesting! Bit too much work for me now but I like the idea. –  Verhoevenv May 27 '10 at 21:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.