Alex L. Wang – Eigenvalues of products of symmetric matrices

Recall that $\operatorname{Sym}:{\mathbb{R}}^{n\times n}\to{\mathbb{S}}^n$ by $\operatorname{Sym}:A\mapsto \frac{A+A^\top}{2}$ . Let $\left\lVert \cdot \right\rVert$ denote the usual operator norm. For positive semidefinite matrices, this corresponds to the maximum eigenvalue.

Question 1. What values can $\lambda_{\min}\left(\operatorname{Sym}\left(\prod_{i=1}^m \frac{A_i}{\left\lVert A_i \right\rVert}\right)\right)$ take if $A_i$ are positive semidefinite?

Note that by convexity and submultiplicativity, we have $\begin{aligned} \left\lVert \operatorname{Sym}\left(\prod_i \frac{A_i}{\left\lVert A_i \right\rVert}\right) \right\rVert \leq \left\lVert \prod_i \frac{A_i}{\left\lVert A_i \right\rVert} \right\rVert \leq 1,\end{aligned}$ so that $\begin{aligned} -I\preceq\operatorname{Sym}\left(\prod_i \frac{A_i}{\left\lVert A_i \right\rVert}\right)\preceq I.\end{aligned}$ Clearly, the latter bound is tight (e.g., take $A_1= \dots = A_m = I$ ). In this post, we will consider the first bound more carefully and show:

Proposition 1. Suppose $n\geq 2$ . Let $A_1,\dots,A_m\in{\mathbb{S}}^n_+$ . Then, $\begin{aligned} \operatorname{Sym}\left(\prod_i \frac{A_i}{\left\lVert A_i \right\rVert}\right)\succeq - \cos\left(\frac{\pi}{m+1}\right)^{m+1}I.\end{aligned}$

For example, the above proposition implies that for any $A,B,C\succeq 0$ , we have $\begin{gathered} -\frac{1}{8}I\preceq\frac{\operatorname{Sym}(AB)}{\left\lVert A \right\rVert_\textup{op}\left\lVert B \right\rVert_\textup{op}} \preceq I,\\ -\frac{1}{4}I\preceq\frac{\operatorname{Sym}(ABC)}{\left\lVert A \right\rVert_\textup{op}\left\lVert B \right\rVert_\textup{op}\left\lVert C \right\rVert_\textup{op}} \preceq I.\end{gathered}$

Proof. By homogeneity, it suffices to consider the case where $\left\lVert A_1 \right\rVert=\dots=\left\lVert A_m \right\rVert \leq 1$ . Let $A_1,\dots,A_m\in{\mathbb{S}}^n_+$ minimize $\begin{aligned} \operatorname{Opt}\coloneqq \min_{A_1,\dots,A_m}\left\{\lambda_{\min}\left(\operatorname{Sym}\left(\prod_i A_i\right)\right):\, 0\preceq A_i \preceq I\right\}.\end{aligned}$

Without loss of generality, each $A_i$ is a rank-one matrix. Indeed, suppose $\operatorname{rank}(A_k)\geq 2$ . Let $v_0\in{\mathbf{S}}^{n-1}$ correspond to a minimum eigenvalue of $\operatorname{Sym}\left(\prod_i A_i\right)$ . Let $w = (\prod_{i>k} A_i) v_0$ and set $\tilde A_k = \frac{(A_kw)(A_kw)^\top}{\left\lVert A_k w \right\rVert^2}$ . Note that $\tilde A_k w = \frac{w^\top A_k w}{w^\top (A_k)^2 w}A_kw$ . Then $\begin{aligned} &\lambda_{\min}\left(\operatorname{Sym}\left(\prod_{i<k} A_i \cdot \tilde A_k \cdot\prod_{i>k} A_i \right)\right)\\ &\qquad\leq v_0^\top \left(\prod_{i<k} A_i \cdot \tilde A_k \cdot\prod_{i>k} A_i \right) v_0\\ &\qquad = \frac{w^\top A_k w}{w^\top (A_k)^2 w} \lambda_{\min}\left(\operatorname{Sym}\left(\prod_i A_i\right)\right)\\ &\qquad \leq \operatorname{Opt}. \end{aligned}$ The last inequality follows from the assumption that $0\preceq A_k \preceq I$ .

We may thus write each $A_i=v_iv_i^\top$ for some $v_i\in{\mathbf{S}}^{n-1}$ . Equivalently, $v_0,v_1,\dots,v_m$ minimizes $\begin{aligned} \min_{v_0,v_1,\dots,v_m\in{\mathbf{S}}^{n-1}} \left\langle v_0,v_1 \right\rangle\left\langle v_1,v_2 \right\rangle\dots\left\langle v_m,v_0 \right\rangle.\end{aligned}$ By negating $v_i$ if necessary, we may assume that $\left\langle v_0, v_1 \right\rangle, \dots, \left\langle v_{m-1}, v_m \right\rangle > 0$ and $\left\langle v_m, v_0 \right\rangle <0$ . By optimality and our assumptions on the signs, we have that for each $i = 1,\dots, m-1$ , $\begin{aligned} v_i = \frac{v_{i-1} + v_{i+1}}{\left\lVert v_{i-1}+ v_{i+1} \right\rVert}.\end{aligned}$ We deduce that $v_1,\dots, v_{m-1} \in \operatorname{span}\left\{v_0, v_m\right\}$ so that without loss of generality $v_0,v_1,\dots, v_m \in{\mathbf{S}}^{1}$ . In particular, we may parameterize $v_i = (\cos(\theta_0 + i \eta), \sin(\theta_0 + i \eta))$ for some $\theta_0$ and $\eta$ . Then, $\begin{aligned} \operatorname{Opt}= \min_{\eta\in{\mathbb{R}}} \cos(\eta)^n\cos(n\eta).\end{aligned}$ This expression is minimized at $\eta = \frac{\pi}{n+1}$ where $\cos(n\eta) = -\cos(\eta)$ . ◻