Eigenvalues of products of symmetric matrices

Recall that Sym:Rn×nSn\operatorname{Sym}:{\mathbb{R}}^{n\times n}\to{\mathbb{S}}^n by Sym:AA+A2\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 λmin(Sym(i=1mAiAi))\lambda_{\min}\left(\operatorname{Sym}\left(\prod_{i=1}^m \frac{A_i}{\left\lVert A_i \right\rVert}\right)\right) take if AiA_i are positive semidefinite?


Note that by convexity and submultiplicativity, we have Sym(iAiAi)iAiAi1,\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 ISym(iAiAi)I.\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 A1==Am=IA_1= \dots = A_m = I). In this post, we will consider the first bound more carefully and show:

Proposition 1. Suppose n2n\geq 2. Let A1,,AmS+nA_1,\dots,A_m\in{\mathbb{S}}^n_+. Then, Sym(iAiAi)cos(πm+1)m+1I.\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,C0A,B,C\succeq 0, we have 18ISym(AB)AopBopI,14ISym(ABC)AopBopCopI.\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 A1==Am1\left\lVert A_1 \right\rVert=\dots=\left\lVert A_m \right\rVert \leq 1. Let A1,,AmS+nA_1,\dots,A_m\in{\mathbb{S}}^n_+ minimize OptminA1,,Am{λmin(Sym(iAi)):0AiI}.\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 AiA_i is a rank-one matrix. Indeed, suppose rank(Ak)2\operatorname{rank}(A_k)\geq 2. Let v0Sn1v_0\in{\mathbf{S}}^{n-1} correspond to a minimum eigenvalue of Sym(iAi)\operatorname{Sym}\left(\prod_i A_i\right). Let w=(i>kAi)v0w = (\prod_{i>k} A_i) v_0 and set A~k=(Akw)(Akw)Akw2\tilde A_k = \frac{(A_kw)(A_kw)^\top}{\left\lVert A_k w \right\rVert^2}. Note that A~kw=wAkww(Ak)2wAkw\tilde A_k w = \frac{w^\top A_k w}{w^\top (A_k)^2 w}A_kw. Then λmin(Sym(i<kAiA~ki>kAi))v0(i<kAiA~ki>kAi)v0=wAkww(Ak)2wλmin(Sym(iAi))Opt.\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 0AkI0\preceq A_k \preceq I.

We may thus write each Ai=viviA_i=v_iv_i^\top for some viSn1v_i\in{\mathbf{S}}^{n-1}. Equivalently, v0,v1,,vmv_0,v_1,\dots,v_m minimizes minv0,v1,,vmSn1v0,v1v1,v2vm,v0.\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 viv_i if necessary, we may assume that v0,v1,,vm1,vm>0\left\langle v_0, v_1 \right\rangle, \dots, \left\langle v_{m-1}, v_m \right\rangle > 0 and vm,v0<0\left\langle v_m, v_0 \right\rangle <0. By optimality and our assumptions on the signs, we have that for each i=1,,m1i = 1,\dots, m-1, vi=vi1+vi+1vi1+vi+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 v1,,vm1span{v0,vm}v_1,\dots, v_{m-1} \in \operatorname{span}\left\{v_0, v_m\right\} so that without loss of generality v0,v1,,vmS1v_0,v_1,\dots, v_m \in{\mathbf{S}}^{1}. In particular, we may parameterize vi=(cos(θ0+iη),sin(θ0+iη))v_i = (\cos(\theta_0 + i \eta), \sin(\theta_0 + i \eta)) for some θ0\theta_0 and η\eta. Then, Opt=minηRcos(η)ncos(nη).\begin{aligned} \operatorname{Opt}= \min_{\eta\in{\mathbb{R}}} \cos(\eta)^n\cos(n\eta).\end{aligned} This expression is minimized at η=πn+1\eta = \frac{\pi}{n+1} where cos(nη)=cos(η)\cos(n\eta) = -\cos(\eta). ◻

Last updated Jan 30, 2022