Hello everyone, I have a problem related to using Linear algebra package to help me diagonalize a matrix. Normally, one would use function like eig(). But as I found out that the returned eigenvalues are sorted automatically, so I am wondering if there is way I can keep the original order of my diagonal elements, because they actually have subindex which is ordered in my original matrix.
Does your initial matrix have a special structure? Triangular?
1 Like
Actually, right now it is 100*100 matrix, so it is not big enough to consider optimization for now. Just testing the basic function.
I was asking because I don’t understand why do you expect the order of your diagonal coefficients to be respected. The diagonal coefficients of an arbitrary matrix are not its eigenvalues, but you probably know that of course.
1 Like
It is not a special matrix. The reason is that each diagonal element is actually related a physical index, so if the output eigenvalue don’t respect that, then it will ruin the correspondence.
Hm, that is not so easy, if you for example look at Diagonalizable matrix - Wikipedia – so assuming your matrix is diagonalisable
P and D in A = P^{-1}DP are not unique in the following sense: If you permute the columns of P the elements in (on the diagonal of) D permute the same way.
So with that in mind there is nothing to respect, because there is no relation between the diagonal of A and the eigenvalues (=diagonal of D), you can chose any permutation of the columns of P and obtain any order.
eig had the convention to therefore order increasingly, which is still not unique for P, if eigenvalues repeat.
2 Likes
Thanks, I can see the difficulty now, then I guess it means I have to use another approach to diagonalize the matrix.
I suggest you to have a look at the documentation of the eigen function of LinearAlgebra and the sortby keyword.
There is no other approach. Diagonalizing a matrix is synonymous with finding eigenvalues and eigenvectors: you are finding a change of basis (eigenvectors) that makes the matrix diagonal (the eigenvalues). I think you need to re-think your whole conception of what diagonalization means and how it relates to your problem.
8 Likes
Thanks, I read the documents before, but I don’t see any example on how to design a custom sortby function. Also As @kellertuer was mentioned, in the numerical procedure I am afraid there is no way that I can keep track of every diagonal elements.
Actually I am thinking use a way which is called flow equation method, which will make diagonalization process becomes solving coupled differential equations. The amazing part of this method is that you can keep track of the flow of the diagonal and off-diagonal part of your matrix, at the end of the day you can see all the off-diagonal coefficients are gone guaranteed (Btw, this method is implemented to solve one-body quantum problems, the Hamiltonian is our matrix). The reference is:
https://onlinelibrary.wiley.com/doi/10.1002/andp.19945060203
Of course there are many algorithms to find a matrix diagonalization — but at the end of the day they are all computing equivalent things: the diagonal matrix must consist of the eigenvalues (in some order), and the change of basis to make it diagonal must consist of eigenvectors.
The ordering of the eigenvalues can always be permuted arbitrarily by permuting the eigenvectors correspondingly. Because of this, it’s not clear what connection you are hoping to maintain between the diagonal entries of your original matrix (?) and the ordering of the eigenvalues (the diagonal entries of the diagonalized matrix).
Maybe the flow method yields the ordering you want? But if there is some symmetry that you are trying to preserve I would try to express that more explicitly algebraically, to give you more freedom in exploiting state-of-the-art eigensolver algorithms. e.g. if you have a group of symmetry operators that commutes with your Hamiltonian then you can use it to categorize and partially order the eigenvectors (according to the irreps of the symmetry group).
1 Like
To make it clear, my original matrix has momentum indices, and the diagonal elements represents a dispersion relationship, there are off-diagonal couplings in this case. I want to see after this diagonalization, what will my band dispersion get renormalized, so if the eigenvalue solver messed up my coherence, meaning the eigenvalue’s indices are not corresponding to my original indices, then I can not figuring that out easily. And I think Flow equation method intrinsically protect this property. Hope this can make my problem more clear, and thx for your question and response.
You said “my original matrix has momentum indices”. Do you mean you discretize a Hamiltonian H(k,k') to get a matrix H_{i,j} with i,j corresponding to some momenta?
Yes, all momentum indices not real space.
Then the eigenvalue problem is H_{k,k'}u_{k'}=Eu_{k'}. As many people have said in the above, the eigenvalue E in general has no relation to the original k. You need to introduce additional structure to “keep” the original indices.
I think the confusion is from perturbation theory, where you can discuss the perturbed eigenvalues and thus you can keep the original index. Maybe this is related to the paper you mentioned.
1 Like
Yes, this can be understood as a perturbation. But the method I mentioned before doesn’t necessarily need perturbation assumptions.
I think what you might be able to do is using the eigenvectors to relate the eigenvalues to their “original” position by considering the overlaps between the original basis vectors and the eigenvectors. Since the original basis vectors are just vectors where one index is 1 and the rest are zeros, you can simply take the absolute values of the components of each eigenvector and the index of the largest value gives you the “original” basis index (which is the vector with the greatest overlap). If the “perturbations” are reasonably small, this should work well. However if there are degeneracies in your original matrix, then the corresponding states could hybridize and then your question is not quite well-defined I think.
If you are using a flow equation method, it might make sense to keep track of these correspondences along the flow. IIUC, the eigenvalues/eigenvectors are deformed continuously along the flow (well in the absence of degeneracies at least) so this approach should work well.
3 Likes
Thanks for your response and suggestion. In my problem, the effect of the off-diagonal coupling should generally not work in a perturbative sense. A easy version of my problem is to consider a plane wave scattering off from a negative potential, and bound state solution can’t be generated from the perturbation type calculation. Yes you are absolutely right on the idea of flow equation method.
I wasn’t able to look at the paper you cited to see exactly what the flow equations are. That was partly because I lack institutional access to the online article, but also I doubt I have enough background in physics to find the explanations clear. Explanations in terms of physics, instead of just math, will do more to confuse me than to enlighten me.
With very limited understanding of what you are trying to do, what I have taken away from the discussion is that you want to diagonalize and end up with the eigenvalues and eigenvectors in the same order you would have gotten with the flow equations, without actually using the flow equations for the computation. That sounds hard to do unless you know something in advance about the ordering of eigenvalues your flow will give you.
With that in mind, in case you don’t know, I wanted to point out that there is prior work in the literature on numerical analysis on diagonalizing with flows. You might want to look at the paper Deift, Nanda, and Tomei, “Ordinary Differential Equations and the Symmetric Eigenvalue Problem”. Some flows do produce sorted eigenvalues in the sense that the only stable equilibrium point is a diagonal matrix with the eigenvalues sorted in descending order. Maybe there is some ordering imposed by your flow that you can exploit.