Tight upper bound on a ratio involving symmetric PSD matrices and Kronecker products

Question

Let $\mathbf{A}_i \in \mathbb{R}^{d \times d}$ ($i = 1, \dots, T$) be symmetric positive semidefinite (PSD) matrices. Define the quantity

$$ m = \frac{\lambda_{\max}\left(\sum_{i=1}^T \mathbf{A}_i^2\right)}{\lambda_{\max}\left(\sum_{i=1}^T \mathbf{A}_i \otimes \mathbf{A}_i\right)}, $$

where $\otimes$ denotes the Kronecker product, and $\lambda_{\max}(\cdot)$ is the largest eigenvalue of a matrix.

Questions:

1. What is a tight upper bound on $m$?
2. Does this bound depend on $d$ and/or $T$, or is $m$ universally bounded by a constant independent of $d$ and $T$?

Observations:

• It is straightforward to show that $m \geq 1$.
• Numerical experiments suggest that $m$ is typically small. For example, I found cases where $m \approx 1.3$, but I couldn't construct any examples where $m > 1.3$.

I am particularly interested in whether $m$ is always bounded above by some constant that does not depend on $d$ or $T$. Any insights, references, or proof sketches would be greatly appreciated!

Answer 1

There is no upper for $m$ that is independent of $d$ and $T$. In fact, for a fixed $d$, the best upper bound that works for all $T$ is of order $\sqrt{d}$, and this is already tight for $T=d$.

The bound $m \leq \sqrt{d}$ is easy. Identifying $\mathbf{R}^d \otimes\mathbf{R}^d$ with the matrices of size $d$ with scalar product $\mathrm{Tr}(A^*B)$, we have $$\lambda_{\max}(\sum_i A_i^2) = \sup_{\mathrm{Tr}(|X|)\leq 1} \mathrm{Tr}(\sum_i A_i^2 X) = \sup_{\mathrm{Tr}(|X|)\leq 1} \mathrm{Tr}(\sum_i A_i\otimes A_i X,\mathrm{id}_d) \leq \sqrt{d} \lambda_{max}(\sum_i A_i \otimes A_i),$$ because $(\mathrm{Tr}(X^*X)^2)^{\frac 1 2} \leq \mathrm{Tr}{|X|}$ and $(\mathrm{Tr}(\mathrm{id}_d^*\mathrm{id}_d)^2)^{\frac 1 2}=\sqrt{d}$.

For the converse inequality, use the following fact: if $\xi_1,\dots,\xi_T$ are unit vectors in a Hilbert space such that all pairwise scalar products are equal to some $c>0$, and if $P_i$ is the orthogonal projection on the line spanned by $\xi_i$ then $\|\sum_i P_i\| \simeq \max(1,cT)$ up to universal constants. This is because if $M=\sum_i P_i$, a straightforward computation gives that $M^2 = (1-c) M + (c^2 T^2 + (c-c^2)T)Q$ for $Q$ the rank one projection on the line spanned by $\sum_i \xi_i$.

Now, take such vectors $\xi_1,\dots,\xi_d \in \mathbf{R}^d$ with $c=\frac{1}{\sqrt{d}}$ and $A_i$ the orthogonal projection on $\xi_i$. By two applications of the fact (for $\xi_i$ and $c=1/\sqrt{d}$, and $\xi_i\otimes \xi_i$ and $c=1/d$ respectively), we get that $\|\sum_i A_i^2\|\simeq \max(1,c d) = \sqrt{d}$, whereas $\|\sum_i A_i \otimes A_i \|\simeq \max(1,c^2d)=1$.

Final comment: in the vocabulary of operator spaces, you are asking for the comparison of the operator spaces $\mathrm{OH}_n$ and $R_n \cap C_n$, in restriction to the positive-semidefinite coefficients. What I explain above is that that they are comparable with constant $\sqrt{n}$ and not better; this is certainly classical.