Given the spectral decompositions of a non-commuting collection of symmetric positive definite $N\times N$ matrices $$\left\{ K\_{i}\right\} \_{i=1}^{M}, U\_{i}D\_{i}U\_{i}^{T}=K\_{i},\quad i=1,\dots,M,$$ is there any $O(N^{2})$ method for computing the eigenvalues of a given convex combination$$\mathcal{D}^{T}=\mathcal{U}^{T}\left(\sum\alpha\_{i}K\_{i}\right)\mathcal{U}\text{ where }\sum\alpha\_{i}=1\text{ and each }\alpha\_{i}\geq0?$$


[This answer to a related question](https://mathoverflow.net/a/4238/97437) suggests that there might some such methods but I have yet to find anything.


**Edit:** In the above linked question I'm referring not to Tao and Knutson's results but rather the additional comment: *"Depending on what you want, there should be simpler results giving estimates on the eigenvalues of the sum".* 



Computing spectrum of convex combination of SPD matrices given individual spectral decompositions
No, there isn't such a method. It's difficult to find a reference that "proves a negative", but I can tell you that many people in my field (numerical linear algebra) would be very happy to know about one. :)


A partial argument to convince you could be: if this were possible, then you could write for any $2n\times 2n$ matrix $\begin{bmatrix} A &B \\ C & D\end{bmatrix} = \begin{bmatrix} A &B \\ 0 & 0\end{bmatrix} + \begin{bmatrix} 0 &0 \\ C & D\end{bmatrix}$, and solve arbitrary eigenvalue problems iteratively via "divide and conquer" in quadratic+logarithmic time. (Not really a valid argument as it is because I did not discuss how to compute eigenvector matrices).


What Knutson and Tao solved is a different, more abstract problem: given two (multi)sets of real numbers $\alpha\_1,\dots,\alpha\_n$, and $\beta\_1,\dots,\beta\_n$, for which choices of $\gamma\_1,\dots,\gamma\_n$ can one find Hermitian matrices $A$ and $B$ such that $A$ has spectrum $\alpha\_1,\dots,\alpha\_n$, $B$ has spectrum $\beta\_1,\dots,\beta\_n$, and $A+B$ has spectrum $\gamma\_1,\dots,\gamma\_n$?


