2
$\begingroup$

I asked a similar question on the Mathematics stack exchange here without much success, so I thought I'd ask it with a more practical bent here.

Suppose we have a Hermitian matrix $H$ with (for the moment) distinct eigenvalues. Let $\{u_1,u_2,\ldots,u_n\}$ be an orthonormal eigenbasis. Most linear algebra packages I know will order these vectors so that the corresponding eigenvalues are in ascending order. However, instead I would like them to be ordered so that the trace of the diagonalising matrix $U$ is maximised; i.e. I would like to find $\max\limits_{\sigma\in S(n)}\sum_j|u_{\sigma(j)j}|$.

Is there any way to avoid simply exhaustively searching the space? Possibly in special cases or to find an approximate solution? For example if $H$ is close to diagonal one would expect $U$ to be close to the identity and thus each $u_j$ to have a unique maximum at different indices; one could then find the location of the maximum for each eigenvector separately and order appropriately, but this breaks down as soon as an eigenvector does not have a unique maximum or two eigenvectors have their maxima at the same index.

$\endgroup$
4
$\begingroup$

The way you want to reorder the matrix $U$ is a special case of the assignment problem, and it is solved by standard algorithms like the Hungarian algorithm implemented in standard libraries (e.g., scipy). Note that its time complexity is $O(n^3)$, so it won't work on large matrices.

In the assignment problem you are given a cost matrix $C$, and asked to find a mapping $\sigma$ (in your case the matrix is square, so it is a permutation) that maximizes $$ \sum_i C_{i,\sigma(i)}. $$ So your question is equivalent to this, taking the cost matrix to be $C=|U^\top|$ (transpose because you're reordering matrix rows rather than columns).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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