Eigenvalues of sum $\lambda_i(X(D_1 + D_2)X^T) = \lambda_{\sigma_1(i)}(XD_1X^T) + \lambda_{\sigma_2(i)}(XD_2X^T)$ where $D_1, D_2$ are diagonal.

Question

Let $D_1, D_2\in\mathbb{R}^{d}$ be positive definite diagonal matrices. Let $X\in\mathbb{R}^{n\times d}$ satisfy $\text{rank}(X) = n < d$. Is it true that $$\lambda_i(X(D_1+D_2)X^T) = \lambda_{\sigma_1(i)}(XD_1X^T) + \lambda_{\sigma_2(i)}(XD_2X^T),$$ for some bijections $\sigma_1,\sigma_2:\{1,\dots,n\} \longrightarrow \{1,\dots,n\}$? Here, $\lambda_i(\cdot)$ is the $i^{\text{th}}$ largest eigenvalue.

Answer 1

For most such matrices $X,D_1,D_2$, this statement will not hold. As an example, take $$ X = \pmatrix{0&1&2\\3&4&5}, \quad D_1 = \pmatrix{\epsilon\\&1\\&&\epsilon}, \quad D_2 = \pmatrix{1\\&\epsilon\\&&\epsilon} $$ For a sufficiently small $\epsilon > 0$.

If we take $\epsilon = 0$, the eigenvalues of the matrices are:

• $XD_1X^T: 0,17$
• $XD_2X^T: 0,9$
• $X(D_1 + D_2)X^T: 0.35088936, 25.64911064$.

It is clear that there is no suitable bijection in the case that $\epsilon = 0$. By the continuity of eigenvalues, it follows that a suitable bijection also does not exist for a sufficiently small $\epsilon > 0$ (for example, $\epsilon = 0.01$ works).

---

Suppose that $Y$ is a matrix that is close to $X$ such that $YY^T$ is a multiple of the identity (i.e. its rows are orthogonal and of equal length). The condition $$ \lambda_i(Y(D_1+D_2)Y^T) = \lambda_{\sigma_1(i)}(YD_1Y^T) + \lambda_{\sigma_2(i)}(YD_2Y^T) $$ will hold for some bijections $\sigma_1,\sigma_2$. On the other hand, for a diagonal matrix $D$, we have $$ XDX^T - Y^TDY = (X + (Y - X))D(X + (Y-X))^T - X^TDX\\ = XD(Y-X)^T + (Y-X)^TDX + (Y-X)D(Y-X)^T, $$ so that $$ \|XDX^T - YDY^T\| = \|XD(Y-X)^T + (Y-X)^TDX + (Y-X)D(Y-X)^T\| \\ \leq 2 \|X\| \cdot \|D\| \cdot \|X-Y\| + \|D\|\cdot \|X-Y\|^2, $$ where $\|X\|$ denotes the spectral norm (maximal singular value) of $X$. If we know that $\|X - Y\| \leq \|X\|$, we can weaken this bound to $\|XDX^T - YDY^T\| \leq 3 \|X\| \cdot \|D\| \cdot \|X-Y\|$.

With this weaker bound, we have $$ |\lambda_i(XDX^T) - \lambda_i(YDY^T)| \leq \|XDX^T - YDY^T\| \leq 3 \|X\| \cdot \|D\| \cdot \|X-Y\|. $$ Putting this all together, we can get the bound $$ |\lambda_i(X(D_1+D_2)X^T) - (\lambda_{\sigma_1(i)}(XD_1X^T) + \lambda_{\sigma_2(i)}(XD_2X^T))| \leq \\ 9 \|X\|\,\|D_1 + D_2\|\,\|X-Y\|. $$