# Ordering of eigenvectors to maximise trace of diagonalising matrix

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.

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).