Question: Is it any easier to find eigenvalues of a matrix $M$, if we have it's root $S \cdot S^T = M$? (Please note that $S$ doesn't have to be triangular so this is not Cholesky).
If the answer is "no, in general", let' see if there is a solution in my particular case, when the matrix $M$ is composed from an already decomposed matrix:
Say that we have a symmetric matrix $K$ (covariance matrix). We have it's eigendecomposition:
$$K = Q \Lambda Q^T$$
where $\Lambda$ is a diagonal matrix with eigenvalues on the diagonal, $Q$ is orthogonal matrix ($Q^T = Q^{-1}$). Let's define root of matrix $K$:
$$R = Q {\sqrt \Lambda} Q^T$$
(Now $K = R \cdot R$, $R$ is symmetric as well).
Now, the main question: What can we say about the eigenvalues of $M = R \cdot (I - {1 \over n} J) \cdot R$?
($I$ is an identity matrix, $J$ is matrix of all 1's, $n$ is the number of rows and columns of these matrices.) Can the eigenvalues of $M$ be somehow easily computed from $\Lambda$ or $\sqrt{\Lambda}$, or do I have to do the costly eigenvalue decomposition again for $M$?
PS: Not sure if this helps, but since $(I - {1 \over n} J)$ is idempotent, $M = R \cdot (I - {1 \over n} J) (I - {1 \over n} J) \cdot R$, and so if we set $S = R \cdot (I - {1 \over n} J)$, then $M = S \cdot S^T$. (Please note that $S$ doesn't have to be triangular so this is not Cholesky).
An alternative approach is as follows: you have a matrix of the form $$ M = Q {\sqrt \Lambda} Q^T \left(I - {1 \over n} J\right) Q {\sqrt \Lambda} Q^T \\ =Q {\sqrt \Lambda} Q^T (I) Q {\sqrt \Lambda} Q^T - \frac 1n Q {\sqrt \Lambda} Q^T (J) Q {\sqrt \Lambda} Q^T\\ = Q \left[\Lambda - \frac 1n [{\sqrt \Lambda} Q^Te][{\sqrt \Lambda} Q^Te]^T\right]Q^T, $$ where $e$ denotes the vector of all $1$s. In other words, you are looking for the eigenvalues of a rank-1 perturbation of a diagonal matrix. From there, you have several methods at your disposal. For instance, the BNS formula gives an expression for the eigenvectors of this matrix. The matrix determinant lemma gives you an expression for the characteristic polynomial, since $$ \det((D + vv^T) + \lambda I) = \det((D + \lambda I) + vv^T) \\= (1 + v^T(D + \lambda I)^{-1}v)\det(D + \lambda I) \\ = \det(D + \lambda I) + v^T\operatorname{adj}(D + \lambda I)v. $$