I need to bound the eigenvalues of a matrix of the form $D^\top C D$, where:
- $D \in \mathbb{R}^{n^2 \times n(n-1)/2}$ is a duplication matrix, in particular the matrix for which $D \operatorname{vechh}(X)= vec(X)$, i.e. restore the vectorization of the matrix $X$ from its strictly lower (or upper triangular part). This matrix has exactly one $1$ in each row, and two $1$'s in each column. Its rank is $n(n-1)/2$. Let me call this number $l=n(n-1)/2$.
- $C$ is a PSD matrix.
Upper Bound. Denote with $\|\cdot\|$ denoting the spectral norm, i.e. the maximum eigenvalue of $\sqrt{(X^\top X)}$, equivalently, the maximum singular value of $X$.
I was starting by $$\|D^\top C D\| \leq \|D^\top\|\| C\|\| D\| \leq \|D^\top\|_F\| C\|\| D\|_F$$
Because $\|D\|_F= \sqrt{\operatorname{trace(D^\top D)}}=\sqrt{\operatorname{trace(2 I_{l})}}=\sqrt{2l}= \sqrt{n(n-1)} $. I can then write
$$\|D^\top C D\| \leq n(n-1)\lambda_{max}(C)$$
But I think this is not really a good bound. Do you have possible improvements in mind?
Lower bound. Assuming the knowledge of the eigenvalues of $C \succ 0$, how does the pre and post multiplication for $D$ shapes the eigenvalues of $C$? I was starting with the definition of max singular value:
$$ \|D^\top C D\| = \sqrt{ \sup_{\|x\|=1} x^\top D^\top C D x} $$.
From here, could an EVD of the matrix $C$ help in moving forward?