This paper was converted on www.awesomepapers.org from LaTeX by an anonymous user.
Want to know more? Visit the Converter page.

Improved bounds in Weaver’s KSr{\rm KS}_{r} conjecture for high rank positive semidefinite matrices

Zhiqiang Xu LSEC, Inst. Comp. Math., Academy of Mathematics and System Science, Chinese Academy of Sciences, Beijing, 100091, China
School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China [email protected] ,  Zili Xu LSEC, Inst. Comp. Math., Academy of Mathematics and System Science, Chinese Academy of Sciences, Beijing, 100091, China
School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China [email protected]  and  Ziheng Zhu LSEC, Inst. Comp. Math., Academy of Mathematics and System Science, Chinese Academy of Sciences, Beijing, 100091, China
School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China [email protected]
Abstract.

Recently Marcus, Spielman and Srivastava proved Weaver’s KSr{\rm{KS}}_{r} conjecture, which gives a positive solution to the Kadison-Singer problem. In [Coh16, Bra¨{\rm\ddot{a}}18], Cohen and Brändén independently extended this result to obtain the arbitrary-rank version of Weaver’s KSr{\rm{KS}}_{r} conjecture. In this paper, we present a new bound in Weaver’s KSr{\rm{KS}}_{r} conjecture for the arbitrary-rank case. To do that, we introduce the definition of (k,m)(k,m)-characteristic polynomials and employ it to improve the previous estimate on the largest root of the mixed characteristic polynomials. For the rank-one case, our bound agrees with the Bownik-Casazza-Marcus-Speegle’s bound when r=2r=2 [BCMS19] and with the Ravichandran-Leake’s bound when r>2r>2 [RL20]. For the higher-rank case, we sharpen the previous bounds from Cohen and from Brändén.

1. Introduction

1.1. The Kadison-Singer problem

The Kadison-Singer problem, posed by Richard Kadison and Isadore Singer in 1959 [KS59], is a fundamental problem that relates to a dozen areas of research in pure mathematics, applied mathematics and engineering. Basically, it asked whether each pure state on the diagonal subalgebra l∞​(ℕ)l^{\infty}(\mathbb{N}) to ℬ​(l2​(ℕ))\mathcal{B}(l^{2}(\mathbb{N})) has a unique extension. This problem was known to be equivalent to a large number of problems in analysis such as the Anderson Paving Conjecture [And79, And79, And81], Bourgain-Tzafriri Restricted Invertibility Conjecture [BT89, CT06], Feichtinger Conjecture [BS06, CCLV05, Gro¨{\rm\ddot{o}}03] and Weaver Conjecture [Wea04].

In a seminal work [MSS15b], Marcus, Spielman and Srivastava resolved the Kadison-Singer problem by proving the Weaver’s KSr{\rm{KS}}_{r} conjecture. The case r=2r=2 of Weaver’s KSr{\rm{KS}}_{r} conjecture can be stated as follows.

Conjecture 1.1.

(KS2{\rm{KS}}_{2}) There exist universal constants η≥2\eta\geq 2 and θ>0\theta>0 such that the following holds. Let 𝐮1,…,𝐮m∈ℂd\mathbf{u}_{1},\ldots,\mathbf{u}_{m}\in\mathbb{C}^{d} satisfy ‖𝐮i‖≤1\|\mathbf{u}_{i}\|\leq 1 for all ii and

(1.1) ∑i=1m|⟨𝐮,𝐮i⟩|2=η\sum\limits_{i=1}^{m}|\langle\mathbf{u},\mathbf{u}_{i}\rangle|^{2}=\eta

for every unit vector 𝐮∈ℂd\mathbf{u}\in\mathbb{C}^{d}. Then there exists a partition S1,S2S_{1},S_{2} of [m]:={1,…,m}[m]:=\{1,\ldots,m\} such that

(1.2) ∑i∈Sj|⟨𝐮,𝐮i⟩|2≤η−θ\sum\limits_{i\in S_{j}}|\langle\mathbf{u},\mathbf{u}_{i}\rangle|^{2}\leq\eta-\theta

for every unit vector 𝐮∈ℂd\mathbf{u}\in\mathbb{C}^{d} and each j∈{1,2}j\in\{1,2\}.

The following theorem plays an important role in their proof of Weaver’s KSr{\rm{KS}}_{r} conjecture.

Theorem 1.2.

( see [MSS15b, Theorem 1.4] ) Let ε>0\varepsilon>0 and let 𝐖1,…,𝐖m\mathbf{W}_{1},\ldots,\mathbf{W}_{m} be independent random positive semidefinite Hermitian matrices in ℂd×d\mathbb{C}^{d\times d} of rank 1 with finite support. If

∑i=1m𝔼​𝐖i=𝐈d\sum_{i=1}^{m}\mathbb{E}\mathbf{W}_{i}=\mathbf{I}_{d}

and

tr⁡(𝔼​𝐖i)≤ε,for all i∈[m],\operatorname{tr}(\mathbb{E}\mathbf{W}_{i})\leq\varepsilon,\quad\text{for all $i\in[m]$,}

then

(1.3) ℙ​[‖∑i=1m𝐖i‖≤(1+ε)2]>0.\mathbb{P}\bigg{[}\bigg{\|}\sum_{i=1}^{m}\mathbf{W}_{i}\bigg{\|}\leq(1+\sqrt{\varepsilon})^{2}\bigg{]}>0.

Theorem 1.3 directly follows from Theorem 1.2 and implies a positive solution to Weaver’s KSr{\rm{KS}}_{r} conjecture.

Theorem 1.3.

( see [MSS15b, Corollary 1.5] ) Let r≥2r\geq 2 be an integer. Assume that 𝐗1,…,𝐗m∈ℂd×d\mathbf{X}_{1},\ldots,\mathbf{X}_{m}\in\mathbb{C}^{d\times d} are positive semidefinite Hermitian matrices of rank at most 11 such that

𝐗1+⋯+𝐗m=𝐈d.\mathbf{X}_{1}+\cdots+\mathbf{X}_{m}=\mathbf{I}_{d}.

Let ε:=max1≤i≤m⁡tr⁡(𝐗i)\varepsilon:=\max\limits_{1\leq i\leq m}\operatorname{tr}(\mathbf{X}_{i}). Then there exists a partition S1∪⋯∪Sr=[m]S_{1}\cup\cdots\cup S_{r}=[m] such that

(1.4) ‖∑i∈Sj𝐗i‖≤1r⋅(1+r​ε)2for all j∈[r].\bigg{\|}\sum\limits_{i\in S_{j}}\mathbf{X}_{i}\bigg{\|}\leq\frac{1}{r}\cdot(1+\sqrt{r\varepsilon})^{2}\quad\text{for all $j\in[r]$.}

In particular, when r=2r=2, if we set 𝐗i=1η⋅𝐮i​𝐮i∗\mathbf{X}_{i}=\frac{1}{\eta}\cdot\mathbf{u}_{i}\mathbf{u}_{i}^{*} and ε=1η\varepsilon=\frac{1}{\eta}, then Theorem 1.3 implies Conjecture 1.1 with any constant η>(2+2)2≈11.6569\eta>(2+\sqrt{2})^{2}\approx 11.6569.

1.2. Related work

Here we briefly introduce the previous improvements on Theorem 1.3.

1.2.1. The rank-one case

When r=2r=2, Bownik, Casazza, Marcus and Speegle [BCMS19] improves the upper bound in (1.4) to 12⋅(1−2​ε+2​ε)2\frac{1}{2}\cdot(\sqrt{1-2\varepsilon}+\sqrt{2\varepsilon})^{2} when ε≤14\varepsilon\leq\frac{1}{4}. This bound implies the same result in Conjecture 1.1, but with any constant η>4\eta>4. To our knowledge, this is the best known estimate on the constant η\eta in Conjecture 1.1.

Ravichandran and Leake in [RL20] adapted the method of interlacing families to directly prove Anderson’s paving conjecture, which is well-known to be equivalent to Weaver’s KSr{\rm{KS}}_{r} conjecture. They showed that, for any integer r≥2r\geq 2 and any real number 0<ε≤(r−1)2r20<\varepsilon\leq\frac{(r-1)^{2}}{r^{2}}, if 𝐀∈ℂm×m\mathbf{A}\in\mathbb{C}^{m\times m} is a positive semidefinite matrix satisfying 𝟎⪯𝐀⪯𝐈m\mathbf{0}\preceq\mathbf{A}\preceq\mathbf{I}_{m} and 𝐀​(i,i)≤ε\mathbf{A}(i,i)\leq\varepsilon for all ii, then there exists a partition S1∪⋯∪Sr=[m]S_{1}\cup\cdots\cup S_{r}=[m] such that

(1.5) ‖𝐀​(Sj)‖≤1r⋅(1−r​εr−1+r​ε)2for all j∈[r].\|\mathbf{A}(S_{j})\|\leq\frac{1}{r}\cdot(\sqrt{1-\frac{r\varepsilon}{r-1}}+\sqrt{r\varepsilon})^{2}\quad\text{for all $j\in[r]$.}

Here, 𝐀​(S)\mathbf{A}(S) denotes the submatrix of 𝐀\mathbf{A} with rows and columns indexed by S⊂[m]S\subset[m]. Their result implies that the upper bound in (1.4) can be improved to

(1.6) ‖∑i∈Sj𝐗i‖≤1r⋅(1−r​εr−1+r​ε)2for all j∈[r]\bigg{\|}\sum\limits_{i\in S_{j}}\mathbf{X}_{i}\bigg{\|}\leq\frac{1}{r}\cdot(\sqrt{1-\frac{r\varepsilon}{r-1}}+\sqrt{r\varepsilon})^{2}\quad\text{for all $j\in[r]$}

when ε≤(r−1)2r2\varepsilon\leq\frac{(r-1)^{2}}{r^{2}}. To see this, we write 𝐗i=𝐮i​𝐮i∗\mathbf{X}_{i}=\mathbf{u}_{i}\mathbf{u}_{i}^{*} for each i∈[m]i\in[m] and set 𝐀=𝐔∗​𝐔\mathbf{A}=\mathbf{U}^{*}\mathbf{U} where 𝐔=[𝐮1,…,𝐮m]∈ℂd×m\mathbf{U}=[\mathbf{u}_{1},\ldots,\mathbf{u}_{m}]\in\mathbb{C}^{d\times m}. Then (1.6) immediately follows since

‖𝐀​(Sj)‖=‖∑i∈Sj𝐗i‖\|\mathbf{A}(S_{j})\|=\bigg{\|}\sum\limits_{i\in S_{j}}\mathbf{X}_{i}\bigg{\|}

for each j∈[r]j\in[r]. When r=2r=2, Ravichandran and Leake’s bound in (1.6) coincides with the estimate of Bownik et. al. from [BCMS19]. In [AB20], Alishahi and Barzegar extended Ravichandran and Leake’s result to the case of real stable polynomials and studied the paving property for strongly Rayleigh process.

1.2.2. The higher-rank case

In [Coh16], Cohen showed that Theorem 1.3 holds for matrices with higher ranks and the upper bound in (1.4) still holds in this case. Brändén also got rid of the rank constraints in [Bra¨{\rm\ddot{a}}18] and extended Theorem 1.3 to the realm of hyperbolic polynomials. For each ε>0\varepsilon>0 and each integer k>2k>2, let δε,k\delta_{\varepsilon,k} be defined as

(1.7) δε,k:={(1−εk+ε)2,if ε≤kk+1,2+2⋅ε​(1−1k),otherwise.\delta_{\varepsilon,k}:=\begin{cases}(\sqrt{1-\frac{\varepsilon}{k}}+\sqrt{\varepsilon})^{2},&\text{if $\varepsilon\leq\frac{k}{k+1}$,}\\ 2+2\cdot\varepsilon(1-\frac{1}{k}),&\text{otherwise.}\end{cases}

In the setting of Theorem 1.3, Brändén proved that, if the rank of each 𝐗i\mathbf{X}_{i} is at most kk, then the upper bound (1.4) can be improved to 1r⋅δr​ε,k​r\frac{1}{r}\cdot\delta_{r\varepsilon,kr} when k​r>2kr>2. For the case where k=1k=1 and r=2r=2, Brändén also obtained the same bound with that of [BCMS19]. One can check that Ravichandran and Leake’s bound (1.6) is better than Br​a¨​nd​e´​n{\rm Br\ddot{a}nd\acute{e}n}’s bound when k=1k=1 and r>2r>2, but Br​a¨​nd​e´​n{\rm Br\ddot{a}nd\acute{e}n}’s bound is more general since it is available for k>1k>1.

1.3. Our contribution

In this paper we focus on extending the results in Theorem 1.2 and Theorem 1.3 to the higher-rank case. We first present the following theorem, which improves the previous bounds from (1.3) and from[Bra¨{\rm\ddot{a}}18, Theorem 6.1].

Theorem 1.4.

Let k≥2k\geq 2 be an integer and let ε∈(0,(k−1)2k]\varepsilon\in(0,\frac{(k-1)^{2}}{k}]. Let 𝐖1,…,𝐖m\mathbf{W}_{1},\ldots,\mathbf{W}_{m} be independent random positive semidefinite Hermitian matrices in ℂd×d\mathbb{C}^{d\times d} with finite support. Suppose that ∑i=1m𝔼​𝐖i=𝐈d\sum_{i=1}^{m}\mathbb{E}\mathbf{W}_{i}=\mathbf{I}_{d} and

tr⁡(𝔼​𝐖i)≤ε,rank⁡(𝔼​𝐖i)≤kfor all i∈[m].\operatorname{tr}(\mathbb{E}\mathbf{W}_{i})\leq\varepsilon,\,\,\operatorname{rank}(\mathbb{E}\mathbf{W}_{i})\leq k\quad\text{for all $i\in[m]$}.

Then,

ℙ​[‖∑i=1m𝐖i‖≤(1−εk−1+ε)2]>0.\mathbb{P}\bigg{[}\bigg{\|}\sum_{i=1}^{m}\mathbf{W}_{i}\bigg{\|}\leq\bigg{(}\sqrt{1-\frac{\varepsilon}{k-1}}+\sqrt{\varepsilon}\bigg{)}^{2}\bigg{]}>0.

We immediately obtain the following corollary with a similar argument in [MSS15b, Corollary 1.5].

Corollary 1.5.

Let r≥2r\geq 2 and k≥1k\geq 1 be integers. Assume that 𝐗1,…,𝐗m∈ℂd×d\mathbf{X}_{1},\ldots,\mathbf{X}_{m}\in\mathbb{C}^{d\times d} are positive semidefinite Hermitian matrices of rank at most kk such that

(1.8) 𝐗1+⋯+𝐗m=𝐈d.\mathbf{X}_{1}+\cdots+\mathbf{X}_{m}=\mathbf{I}_{d}.

Let ε:=max1≤i≤m⁡tr⁡(𝐗i)\varepsilon:=\max\limits_{1\leq i\leq m}\operatorname{tr}(\mathbf{X}_{i}). If ε≤(k​r−1)2k​r2\varepsilon\leq\frac{(kr-1)^{2}}{kr^{2}}, then there exists a partition S1∪⋯∪Sr=[m]S_{1}\cup\cdots\cup S_{r}=[m] such that

(1.9) ‖∑i∈Sj𝐗i‖≤1r⋅(1−r​εk​r−1+r​ε)2for all j∈[r].\bigg{\|}\sum\limits_{i\in S_{j}}\mathbf{X}_{i}\bigg{\|}\leq\frac{1}{r}\cdot\bigg{(}\sqrt{1-\frac{r\varepsilon}{kr-1}}+\sqrt{r\varepsilon}\bigg{)}^{2}\quad\text{for all $j\in[r]$.}
Proof.

For each i∈[m]i\in[m], let 𝐖i\mathbf{W}_{i} be a random matrix that takes the following matrices of size r​d×r​drd\times rd with equal probability:

𝐖i,1:=[r⋅𝐗i0⋱0],𝐖i,2:=[0r⋅𝐗i⋱0],…,𝐖i,r:=[00⋱r⋅𝐗i].\mathbf{W}_{i,1}:=\begin{bmatrix}r\cdot\mathbf{X}_{i}&&&\\ &0&&\\ &&\ddots&\\ &&&0\end{bmatrix},\mathbf{W}_{i,2}:=\begin{bmatrix}0&&&\\ &r\cdot\mathbf{X}_{i}&&\\ &&\ddots&\\ &&&0\end{bmatrix},\ldots,\mathbf{W}_{i,r}:=\begin{bmatrix}0&&&\\ &0&&\\ &&\ddots&\\ &&&r\cdot\mathbf{X}_{i}\end{bmatrix}.

A simple calculation shows that

𝔼​𝐖i=[𝐗i𝐗i⋱𝐗i]∈ℂr​d×r​d,for all i∈[m].\mathbb{E}\mathbf{W}_{i}=\begin{bmatrix}\mathbf{X}_{i}&&&\\ &\mathbf{X}_{i}&&\\ &&\ddots&\\ &&&\mathbf{X}_{i}\end{bmatrix}\in\mathbb{C}^{rd\times rd},\quad\text{for all $i\in[m]$.}

This gives

tr⁡(𝔼​𝐖i)≤r​εandrank​(𝔼​𝐖i)≤k​rfor all i∈[m].\operatorname{tr}(\mathbb{E}\mathbf{W}_{i})\leq r\varepsilon\quad\text{and}\quad{\rm rank}(\mathbb{E}\mathbf{W}_{i})\leq kr\quad\text{for all $i\in[m]$}.

We also have ∑i=1m𝔼​𝐖i=𝐈r​d\sum_{i=1}^{m}\mathbb{E}\mathbf{W}_{i}=\mathbf{I}_{rd}. By Theorem 1.4, we obtain

(1.10) ℙ​[‖∑i=1m𝐖i‖≤(1−r​εk​r−1+r​ε)2]>0.\mathbb{P}\bigg{[}\bigg{\|}\sum_{i=1}^{m}\mathbf{W}_{i}\bigg{\|}\leq\bigg{(}\sqrt{1-\frac{r\varepsilon}{kr-1}}+\sqrt{r\varepsilon}\bigg{)}^{2}\bigg{]}>0.

Hence, for each i∈[m]i\in[m] there exists ji∈[r]j_{i}\in[r] so that

‖∑i=1m𝐖i,ji‖≤(1−r​εk​r−1+r​ε)2.\bigg{\|}\sum_{i=1}^{m}\mathbf{W}_{i,j_{i}}\bigg{\|}\leq\bigg{(}\sqrt{1-\frac{r\varepsilon}{kr-1}}+\sqrt{r\varepsilon}\bigg{)}^{2}.

For each j∈[r]j\in[r], set Sj:={i∈[m]:ji=j}S_{j}:=\{i\in[m]:j_{i}=j\}. Then S1,…,SrS_{1},\ldots,S_{r} form a partition of [m][m], and the (1.10) gives

‖∑i∈Sj𝐗i‖≤1r​(1−r​εk​r−1+r​ε)2for all j∈[r].\bigg{\|}\sum_{i\in S_{j}}\mathbf{X}_{i}\bigg{\|}\leq\frac{1}{r}\bigg{(}\sqrt{1-\frac{r\varepsilon}{kr-1}}+\sqrt{r\varepsilon}\bigg{)}^{2}\quad\text{for all $j\in[r]$}.

∎

Remark 1.6.

Motivated by the argument in [FY19, Proposition 2.2], we can relax the condition (1.8) in Corollary 1.5 to ∑i=1m𝐗i⪯𝐈d\sum_{i=1}^{m}\mathbf{X}_{i}\preceq\mathbf{I}_{d}. More specifically, we can find rank-one matrices {𝐯j​𝐯j∗}1≤j≤M\{{\mathbf{v}}_{j}{\mathbf{v}}_{j}^{*}\}_{1\leq j\leq M} with trace at most ε\varepsilon such that ∑i=1m𝐗i+∑j=1M𝐯j​𝐯j∗=𝐈d\sum_{i=1}^{m}\mathbf{X}_{i}+\sum_{j=1}^{M}{\mathbf{v}}_{j}{\mathbf{v}}_{j}^{*}=\mathbf{I}_{d}. Then there exists an partition of [m+M][m+M] satisfying (1.9) by Corollary 1.5. We can get a desired partition of [m][m] by restricting each subset in the partition of [m+M][m+M] to [m][m].

Our bound in (1.9) coincides with that of [RL20] for each r≥2r\geq 2 when k=1k=1. In particular, our bound is also the same with that of [BCMS19] when r=2r=2 and k=1k=1. For the case when k≥2k\geq 2, our bound (1.9) slightly improves Brändén’s bound, i.e., 1r⋅δr​ε,k​r=1r⋅(1−εk+r​ε)2\frac{1}{r}\cdot\delta_{r\varepsilon,kr}=\frac{1}{r}\cdot(\sqrt{1-\frac{\varepsilon}{k}}+\sqrt{r\varepsilon})^{2}. We summarize the related works in Table 1.3.

Table 1. The estimate on the paving bound in Corollary 1.5
The value of kk and rr Paving bound in (1.9)
k=1,r=2k=1,r=2 12⋅(1−2​ε+2​ε)2\frac{1}{2}\cdot(\sqrt{1-2\varepsilon}+\sqrt{2\varepsilon})^{2} for ε≤14\varepsilon\leq\frac{1}{4} [BCMS19, RL20, Bra¨{\rm\ddot{a}}18]
k=1,r≥2k=1,r\geq 2 1r⋅(1+r​ϵ)2\frac{1}{r}\cdot(1+\sqrt{r\epsilon})^{2} [MSS15b]
1r⋅(1−r​εr−1+r​ε)2\frac{1}{r}\cdot(\sqrt{1-\frac{r\varepsilon}{r-1}}+\sqrt{r\varepsilon})^{2} for ε≤(r−1)2r2\varepsilon\leq\frac{(r-1)^{2}}{r^{2}} [RL20]
k≥1,r≥2k\geq 1,r\geq 2 1r⋅(1+r​ϵ)2\frac{1}{r}\cdot(1+\sqrt{r\epsilon})^{2} [Coh16]
1r⋅(1−εk+r​ε)2\frac{1}{r}\cdot(\sqrt{1-\frac{\varepsilon}{k}}+\sqrt{r\varepsilon})^{2} for ε≤kk​r+1\varepsilon\leq\frac{k}{kr+1}[Bra¨{\rm\ddot{a}}18]
1r⋅(2+2⋅r​ε​(1−1k​r))\frac{1}{r}\cdot(2+2\cdot r\varepsilon(1-\frac{1}{kr})) for ε>kk​r+1\varepsilon>\frac{k}{kr+1}[Bra¨{\rm\ddot{a}}18]
1r⋅(1−r​εk​r−1+r​ε)2\frac{1}{r}\cdot(\sqrt{1-\frac{r\varepsilon}{kr-1}}+\sqrt{r\varepsilon})^{2} for ε≤(k​r−1)2k​r2\varepsilon\leq\frac{(kr-1)^{2}}{kr^{2}} (Corollary 1.5)

We next provide an application of Corollary 1.5, which specifies a simultaneous paving bound for multiple positive semidefinite Hermitian matrices. In [RS19], Ravichandran and Srivastava proved a simultaneous paving bound for a tuple of zero-diagonal Hermitian matrices. Therefore, the following corollary serves as a counterpart of [RS19, Theorem 1.1]. The result also coincides with [RL20, Theorem 2] when paving just one matrix.

Corollary 1.7.

Let r≥2r\geq 2 and k≥1k\geq 1 be integers. Assume that 𝐀1,…,𝐀k∈ℂm×m\mathbf{A}_{1},\ldots,\mathbf{A}_{k}\in\mathbb{C}^{m\times m} are positive semidefinite Hermitian matrices satisfying 𝟎⪯𝐀i⪯𝐈m\mathbf{0}\preceq\mathbf{A}_{i}\preceq\mathbf{I}_{m} for 1≤i≤k1\leq i\leq k. Let α:=max1≤i≤k⁡max1≤l≤m⁡𝐀i​(l,l)\alpha:=\max\limits_{1\leq i\leq k}\max\limits_{1\leq l\leq m}\mathbf{A}_{i}(l,l). If α≤(k​r−1)2k2​r2\alpha\leq\frac{(kr-1)^{2}}{k^{2}r^{2}}, then there exists a partition S1∪⋯∪Sr=[m]S_{1}\cup\cdots\cup S_{r}=[m] such that

‖𝐀i​(Sj)‖≤(1r−k​αk​r−1+k​α)2for all i∈[k] and j∈[r]..\|\mathbf{A}_{i}(S_{j})\|\leq\bigg{(}\sqrt{\frac{1}{r}-\frac{k\alpha}{kr-1}}+\sqrt{k\alpha}\bigg{)}^{2}\quad\text{for all $i\in[k]$ and $j\in[r]$.}.
Proof.

For 1≤i≤k1\leq i\leq k, let the vectors {𝐮i,l}l∈[m]⊂ℂd\{\mathbf{u}_{i,l}\}_{l\in[m]}\subset\mathbb{C}^{d} satisfy 𝐀i=(⟨𝐮i,l1,𝐮i,l2⟩)1≤l1,l2≤m\mathbf{A}_{i}=(\left<\mathbf{u}_{i,l_{1}},\mathbf{u}_{i,l_{2}}\right>)_{1\leq l_{1},l_{2}\leq m}, and then we have ∑l=1m𝐮i,l​𝐮i,l∗⪯𝐈d\sum_{l=1}^{m}{\mathbf{u}}_{i,l}{\mathbf{u}}_{i,l}^{*}\preceq\mathbf{I}_{d} and ‖𝐮i,l‖2≤α\|\mathbf{u}_{i,l}\|^{2}\leq\alpha for 1≤l≤m1\leq l\leq m. For 1≤l≤m1\leq l\leq m, define a block diagonal matrix

𝐗l:=[𝐮1,l​𝐮1,l∗𝐮2,l​𝐮2,l∗⋱𝐮k,l​𝐮k,l∗]∈ℂk​d×k​d.\mathbf{X}_{l}:=\begin{bmatrix}{\mathbf{u}}_{1,l}{\mathbf{u}}_{1,l}^{*}&&&\\ &{\mathbf{u}}_{2,l}{\mathbf{u}}_{2,l}^{*}&&\\ &&\ddots&\\ &&&{\mathbf{u}}_{k,l}{\mathbf{u}}_{k,l}^{*}\end{bmatrix}\in\mathbb{C}^{kd\times kd}.

Then max1≤l≤m⁡tr⁡(𝐗l)≤k​α≤(k​r−1)2k​r2\max\limits_{1\leq l\leq m}\operatorname{tr}(\mathbf{X}_{l})\leq k\alpha\leq\frac{(kr-1)^{2}}{kr^{2}} . Note that ∑l=1m𝐗l⪯𝐈k​d.\sum_{l=1}^{m}\mathbf{X}_{l}\preceq\mathbf{I}_{kd}. By Collolary 1.5, there exists a partition S1∪⋯∪Sr=[m]S_{1}\cup\cdots\cup S_{r}=[m] such that

(1.11) ‖∑l∈Sj𝐗l‖≤1r⋅(1−r​k​αk​r−1+r​k​α)2for all j∈[r]..\bigg{\|}\sum_{l\in S_{j}}\mathbf{X}_{l}\bigg{\|}\leq\frac{1}{r}\cdot\bigg{(}\sqrt{1-\frac{rk\alpha}{kr-1}}+\sqrt{rk\alpha}\bigg{)}^{2}\quad\text{for all $j\in[r]$.}.

Note that

∑l∈Sj𝐗l=[∑l∈Sj𝐮1,l​𝐮1,l∗∑l∈Sj𝐮2,l​𝐮2,l∗⋱∑l∈Sj𝐮k,l​𝐮k,l∗].\sum_{l\in S_{j}}\mathbf{X}_{l}=\begin{bmatrix}\sum\limits_{l\in S_{j}}{\mathbf{u}}_{1,l}{\mathbf{u}}_{1,l}^{*}&&&\\ &\sum\limits_{l\in S_{j}}{\mathbf{u}}_{2,l}{\mathbf{u}}_{2,l}^{*}&&\\ &&\ddots&\\ &&&\sum\limits_{l\in S_{j}}{\mathbf{u}}_{k,l}{\mathbf{u}}_{k,l}^{*}\end{bmatrix}.

Then we have

(1.12) ‖∑l∈Sj𝐗l‖=max1≤i≤k⁡‖∑l∈Sj𝐮i,l​𝐮i,l∗‖=max1≤i≤k⁡‖𝐀i​(Sj)‖.\bigg{\|}\sum_{l\in S_{j}}\mathbf{X}_{l}\bigg{\|}=\max_{1\leq i\leq k}\bigg{\|}\sum\limits_{l\in S_{j}}{\mathbf{u}}_{i,l}{\mathbf{u}}_{i,l}^{*}\bigg{\|}=\max_{1\leq i\leq k}\|\mathbf{A}_{i}(S_{j})\|.

Combining (1.11) and (1.12), we arrive at the conclusion. ∎

1.4. Our techniques

To introduce our techniques, let us briefly recall the proof of Theorem 1.2 and how [Coh16] and [Bra¨{\rm\ddot{a}}18] extended Theorem 1.2 to the higher-rank case.

For the rank-one case, let {𝐖i}1≤i≤m\{\mathbf{W}_{i}\}_{1\leq i\leq m} be as defined in Theorem 1.2. For 1≤i≤m1\leq i\leq m, let the support of 𝐖i\mathbf{W}_{i} be Wi:={𝐖i,1,…,𝐖i,li}W_{i}:=\{\mathbf{W}_{i,1},\ldots,\mathbf{W}_{i,l_{i}}\}. In [MSS15b], Marcus, Spielman and Srivastava showed that the characteristic polynomials of {∑i=1m𝐖i,ji:1≤ji≤li,i=1,…,m}\{\sum_{i=1}^{m}\mathbf{W}_{i,j_{i}}:1\leq j_{i}\leq l_{i},\,i=1,\ldots,m\} form a so-called interlacing family. This implies that there exists a polynomial in this family whose largest root is at most that of the expectation of the characteristic polynomial of ∑i=1m𝐖i\sum_{i=1}^{m}\mathbf{W}_{i}. Hence, it is enough to estimate the largest root of this expected characteristic polynomial. This expected characteristic polynomial is referred to as the mixed characteristic polynomial:

Definition 1.8.

(see [MSS15b]) Given 𝐗1,…,𝐗m∈ℂd×d\mathbf{X}_{1},\ldots,\mathbf{X}_{m}\in\mathbb{C}^{d\times d}, the mixed characteristic polynomial of 𝐗1,…,𝐗m\mathbf{X}_{1},\ldots,\mathbf{X}_{m} is defined as

(1.13) μ​[𝐗1,…,𝐗m]​(x):=∏i=1m(1−∂zi)​det[x⋅𝐈d+∑i=1mzi​𝐗i]|z1=⋯=zm=0.\mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}](x):=\prod_{i=1}^{m}(1-\partial_{z_{i}})\det[x\cdot\mathbf{I}_{d}+\sum_{i=1}^{m}z_{i}\mathbf{X}_{i}]|_{z_{1}=\cdots=z_{m}=0}.

Assume that 𝐖1,…,𝐖m\mathbf{W}_{1},\ldots,\mathbf{W}_{m} are independent random matrices of rank one in ℂd×d\mathbb{C}^{d\times d} satisfying 𝔼​𝐖i=𝐗i\mathbb{E}\mathbf{W}_{i}=\mathbf{X}_{i} for each i∈[m]i\in[m]. Marcus, Spielman and Srivastava in [MSS15b, Theorem 4.1] showed that

(1.14) μ​[𝐗1,…,𝐗m]​(x)=𝔼​det[x⋅𝐈d−∑i=1m𝐖i].\mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}](x)=\mathbb{E}\ \det[x\cdot\mathbf{I}_{d}-\sum\limits_{i=1}^{m}\mathbf{W}_{i}].

Based on the above formula, they employed an argument of the barrier function that was developed in [BSS12] to estimate the largest root of the mixed characteristic polynomials.

For the higher-rank case, instead of studying the characteristic polynomials of {∑i=1m𝐖i,ji:1≤ji≤li,i=1,…,m}\{\sum_{i=1}^{m}\mathbf{W}_{i,j_{i}}:1\leq j_{i}\leq l_{i},\,i=1,\ldots,m\} , the authors of [Coh16] and [Bra¨{\rm\ddot{a}}18] concentrated their attention on the mixed characteristic polynomials of 𝐖1,j1,…,𝐖m,jm\mathbf{W}_{1,j_{1}},\ldots,\mathbf{W}_{m,j_{m}}. They showed that this family of polynomials also form an interlacing family. Furthermore, they proved that, for any positive semidefinite Hermitian matrices 𝐗1,…,𝐗m∈ℂd×d\mathbf{X}_{1},\ldots,\mathbf{X}_{m}\in\mathbb{C}^{d\times d}, the operator norm of ∑i=1m𝐗i\sum_{i=1}^{m}\mathbf{X}_{i} is upper bounded by the largest root of μ​[𝐗1,…,𝐗m]\mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}], i.e.

‖∑i=1m𝐗i‖≤maxroot⁡μ​[𝐗1,…,𝐗m].\bigg{\|}\sum_{i=1}^{m}\mathbf{X}_{i}\bigg{\|}\leq\operatorname{maxroot}\ \mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}].

Hence, the original problem is reduced to estimating the largest root of the expectation of the mixed characteristic polynomials, which can be done with a similar argument of barrier function.

To prove Theorem 1.4, we follow the above framework of [Coh16] and [Bra¨{\rm\ddot{a}}18]. Our main technique is that we derive a new formula for the mixed characteristic polynomials (see Theorem 3.8). Based on this new formula and the method of barrier function, we obtain an improved estimate on the largest root of the mixed characteristic polynomials. We state it as follows.

Theorem 1.9.

Assume that 𝐗1,…,𝐗m∈ℂd×d\mathbf{X}_{1},\ldots,\mathbf{X}_{m}\in\mathbb{C}^{d\times d} are positive semidefinite Hermitian matrices of rank at most kk such that ∑i=1m𝐗i⪯𝐈d\sum\limits_{i=1}^{m}\mathbf{X}_{i}\preceq\mathbf{I}_{d}. Let ε:=max1≤i≤m⁡tr⁡(𝐗i)\varepsilon:=\max\limits_{1\leq i\leq m}\operatorname{tr}(\mathbf{X}_{i}). If ε≤(k−1)2k\varepsilon\leq\frac{(k-1)^{2}}{k}, then we have

(1.15) maxroot⁡μ​[𝐗1,…,𝐗m]≤(1−εk−1+ε)2.\operatorname{maxroot}\ \mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}]\leq\bigg{(}\sqrt{1-\frac{\varepsilon}{k-1}}+\sqrt{\varepsilon}\bigg{)}^{2}.

1.5. Organization

This paper is organized as follows. After introducing some useful notation and lemmas in Section 2, we introduce the definition of (k,m)(k,m)-characteristic polynomials, showing the connection between (k,m)(k,m)-characteristic polynomials and the mixed characteristic polynomials in Section 3. In Section 4, we use the method of barrier function to present a proof of Theorem 1.9. The proof of Theorem 1.4 is presented in Section 5.

2. Preliminaries

2.1. Notations

We first introduce some notations. For a vector 𝐱∈ℂm\mathbf{x}\in\mathbb{C}^{m}, we let ‖𝐱‖\|\mathbf{x}\| denote its Euclidean 2-norm. For a matrix 𝐁∈ℂm×m\mathbf{B}\in\mathbb{C}^{m\times m}, we use ‖𝐁‖=max‖𝐱‖=1⁡‖𝐁𝐱‖\|\mathbf{B}\|=\max_{\|\mathbf{x}\|=1}\|\mathbf{Bx}\| to denote its operator norm. We write ∂zi\partial_{z_{i}} to indicate the partial differential ∂/∂zi\partial/\partial_{z_{i}}. For each t∈[m]t\in[m], let 𝐞t∈ℝm\mathbf{e}_{t}\in\mathbb{R}^{m} denote the vector whose tt-th entry equals 11 and the rest entries equal to 0. For a polynomial p∈ℝ​[z]p\in\mathbb{R}[z] with real roots, we use maxroot⁡p\operatorname{maxroot}\ p and minroot⁡p\operatorname{minroot}\ p to denote the maximum and minimum root of pp respectively.

For an integer mm, we use [m][m] to denote the set {1,2,…,m}\{1,2,\ldots,m\}. For any two positive integers kk and mm, we call 𝒮=(S1,…,Sk)∈[m]k\mathcal{S}=(S_{1},\ldots,S_{k})\in[m]^{k} an kk-partition of [m][m] if S1,…,SkS_{1},\ldots,S_{k} are disjoint and S1∪⋯∪Sk=[m]S_{1}\cup\cdots\cup S_{k}=[m]. We use the notation 𝒫k​(m)\mathcal{P}_{k}(m) to denote the set of all kk-partitions of [m][m].

Given a matrix 𝐀∈ℂm×m\mathbf{A}\in\mathbb{C}^{m\times m}, for a subset S⊂[m]S\subset[m], we use 𝐀​(S)\mathbf{A}(S) to denote the principal submatrix of 𝐀\mathbf{A} whose rows and columns are indexed by SS. Let k≥1k\geq 1 be an integer. Given a matrix 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km}, for 𝒮=(S1,…,Sk)∈[m]k\mathcal{S}=(S_{1},\ldots,S_{k})\in[m]^{k}, we use 𝐀​(𝒮)\mathbf{A}(\mathcal{S}) to denote the principal submatrix 𝐀​(S1∪(m+S2)∪…∪((k−1)⋅m+Sk))\mathbf{A}(S_{1}\cup(m+S_{2})\cup\ldots\cup((k-1)\cdot m+S_{k})). For example, let m=4,k=3m=4,k=3 and let S1={1,2},S2={2,3,4},S3={3}S_{1}=\{1,2\},S_{2}=\{2,3,4\},S_{3}=\{3\}. If we set 𝒮=(S1,S2,S3)\mathcal{S}=(S_{1},S_{2},S_{3}), then for a matrix 𝐀∈ℂ12×12\mathbf{A}\in\mathbb{C}^{12\times 12} the principal submatrix 𝐀​(𝒮)∈ℂ6×6\mathbf{A}(\mathcal{S})\in\mathbb{C}^{6\times 6} is composed of the shaded part in Figure  1.

Refer to caption
Figure 1. The principal submatrix 𝐀​(𝒮)∈ℂ6×6\mathbf{A}(\mathcal{S})\in\mathbb{C}^{6\times 6} for m=4,k=3m=4,k=3, 𝒮=({1,2},{2,3,4},{3})\mathcal{S}=(\{1,2\},\{2,3,4\},\{3\}), and 𝐀∈ℂ12×12.\mathbf{A}\in\mathbb{C}^{12\times 12.}

2.2. Interlacing families

The method of interlacing families is a powerful tool to show the existence of some combinatorial objects. Marcus, Spielman and Srivastava employed this tool to prove the existence of bipartite Ramanujan graphs of all sizes and degrees, solved the Kadison-Singer problem and proved a sharper restricted invertibility [MSS15a, MSS15b, MSS17, MSS18].

Here we recall the definition and related results of interlacing families from [MSS15b]. Throughout this paper, we say that a univariate polynomial is real-rooted if all of its coefficients and roots are real.

Definition 2.1.

(see [MSS15b, Definition 3.1] ) We say a real-rooted polynomial g​(x)=α0​∏i=1n−1(x−αi)g(x)=\alpha_{0}\prod_{i=1}^{n-1}(x-\alpha_{i}) interlaces a real-rooted polynomial f​(x)=β0​∏i=1n(x−βi)f(x)=\beta_{0}\prod_{i=1}^{n}(x-\beta_{i}) if β1≤α1≤β2≤α2≤⋯≤αn−1≤βn\beta_{1}\leq\alpha_{1}\leq\beta_{2}\leq\alpha_{2}\leq\cdots\leq\alpha_{n-1}\leq\beta_{n}. For polynomials f1,…,fkf_{1},\ldots,f_{k}, if there exists a polynomial gg that interlaces fif_{i} for each ii, then we say that f1,…,fkf_{1},\ldots,f_{k} have a common interlacing.

We next introduce the definition of interlacing families.

Definition 2.2.

(see [MSS15b, Definition 3.3] ) Assume that S1,…,SmS_{1},\ldots,S_{m} are finite sets. For every assignment s1,…,sm∈S1×⋯×Sms_{1},\ldots,s_{m}\in S_{1}\times\cdots\times S_{m}, let fs1,…,sm​(x)f_{s_{1},\ldots,s_{m}}(x) be a real-rooted degree nn polynomial with positive leading coefficient. For each k<mk<m and each partial assignment s1,…,sk∈S1×⋯×Sks_{1},\ldots,s_{k}\in S_{1}\times\cdots\times S_{k}, we define

fs1,…,sk:=∑sk+1∈Sk+1,…,sm∈Smfs1,…,sk,sk+1,…,sm.f_{s_{1},\ldots,s_{k}}:=\sum\limits_{s_{k+1}\in S_{k+1},\ldots,s_{m}\in S_{m}}f_{s_{1},\ldots,s_{k},s_{k+1},\ldots,s_{m}}.

We also define

f∅:=∑s1∈S1,…,sm∈Smfs1,…,sm.f_{\emptyset}:=\sum\limits_{s_{1}\in S_{1},\ldots,s_{m}\in S_{m}}f_{s_{1},\ldots,s_{m}}.

We say that the polynomials {fs1,…,sm:s1,…,sm∈S1×⋯×Sm}\{f_{s_{1},\ldots,s_{m}}:s_{1},\ldots,s_{m}\in S_{1}\times\cdots\times S_{m}\} form an interlacing family if for all integers k=0,…,m−1k=0,\ldots,m-1 and all partial assignments s1,…,sk∈S1×⋯×Sks_{1},\ldots,s_{k}\in S_{1}\times\cdots\times S_{k}, the polynomials {fs1,…,sk,t}t∈Sk+1\{f_{s_{1},\ldots,s_{k},t}\}_{t\in S_{k+1}} have a common interlacing.

We state the main property of interlacing families as the following lemma.

Lemma 2.3.

(see [MSS15b, Theorem 3.4] ) Assume that S1,…,SmS_{1},\ldots,S_{m} be finite sets and let {fs1,…,sm:s1,…,sm∈S1×⋯×Sm}\{f_{s_{1},\ldots,s_{m}}:s_{1},\ldots,s_{m}\in S_{1}\times\cdots\times S_{m}\} be an interlacing family. Then there exists some s1′,…,sm′∈S1×⋯×Sms^{\prime}_{1},\ldots,s^{\prime}_{m}\in S_{1}\times\cdots\times S_{m} such that the largest root of fs1′,…,sm′f_{s^{\prime}_{1},\ldots,s^{\prime}_{m}} is upper bounded by the largest root of f∅f_{\emptyset}.

2.3. Real stable polynomials

Through our analysis, we exploit the notion of real stable polynomials, which can be viewed as a multivariate generalization of real-rooted polynomials. For more details, see [BB10, Wag11].

We first introduce the definition of real stable polynomials.

Definition 2.4.

A polynomial p∈ℝ​[z1,…,zm]p\in\mathbb{R}[z_{1},\ldots,z_{m}] is real stable if p​(z1,…,zm)≠0p(z_{1},\ldots,z_{m})\neq 0 for all (z1,…,zn)∈ℂn(z_{1},\ldots,z_{n})\in\mathbb{C}^{n} with 𝐈𝐦​(zi)>0\mathbf{Im}(z_{i})>0 and i∈[m]i\in[m].

To show the polynomial we concern in this paper is real stable, we need the following lemma.

Lemma 2.5.

(see [BB08, Proposition 2.4] ) For any positive semidefinite Hermitian matrices 𝐀1,…,𝐀m∈ℂd×d\mathbf{A}_{1},\ldots,\mathbf{A}_{m}\in\mathbb{C}^{d\times d} and any Hermitian matrix 𝐁∈ℂd×d\mathbf{B}\in\mathbb{C}^{d\times d}, the polynomial

(2.1) det[𝐀1​z1+⋯+𝐀m​zm+𝐁]∈ℝ​[z1,…,zm]\det[\mathbf{A}_{1}z_{1}+\cdots+\mathbf{A}_{m}z_{m}+\mathbf{B}]\in\mathbb{R}[z_{1},\ldots,z_{m}]

is either real stable or identically zero.

Real stability can be preserved under some certain transformations. In our proof, we use some real stability preservers to reduce multivariate polynomials to a univariate one which is a real-rooted polynomial.

Lemma 2.6.

(see [Wag11, Lemma 2.4] ) If p∈ℝ​[z1,…,zm]p\in\mathbb{R}[z_{1},\ldots,z_{m}] is real stable and a∈ℝa\in\mathbb{R}, then the following polynomials are also real stable:

  • •

    p​(a,z2,…,zm)∈ℝ​[z2,…,zm]p(a,z_{2},\ldots,z_{m})\in\mathbb{R}[z_{2},...,z_{m}],

  • •

    p​(z1,…,zm)|zi=zjp(z_{1},\ldots,z_{m})|_{z_{i}=z_{j}}, for all {i,j}⊂[m]\{i,j\}\subset[m],

  • •

    ∂zip​(z1,…,zm)\partial_{z_{i}}p(z_{1},\ldots,z_{m}), for all i∈[m]i\in[m].

2.4. The mixed characteristic polynomial

The mixed characteristic polynomial plays a key role in the proof of Theorem 1.2. In this subsection we introduce some basic properties of mixed characteristic polynomials which is useful in our proof of Theorem 1.4.

Lemma 2.7.

(see [Bra¨{\rm\ddot{a}}18, Theorem 5.2] and [Coh16]) Assume that 𝐗1,…,𝐗m∈ℂd×d\mathbf{X}_{1},\ldots,\mathbf{X}_{m}\in\mathbb{C}^{d\times d} are positive semidefinite Hermitian matrices. Then we have

(2.2) ‖∑i=1m𝐗i‖≤maxroot⁡μ​[𝐗1,…,𝐗m],\bigg{\|}\sum\limits_{i=1}^{m}\mathbf{X}_{i}\bigg{\|}\leq\operatorname{maxroot}\ \mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}],

where μ​[𝐗1,…,𝐗m]\mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}] is defined in (1.13).

Lemma 2.8.

(see [Bra¨{\rm\ddot{a}}18, Theorem 3.5] and [Coh16]) Assume that 𝐖1,…,𝐖m\mathbf{W}_{1},\ldots,\mathbf{W}_{m} are independent random positive semidefinite Hermitian matrices in ℂd×d\mathbb{C}^{d\times d} with finite support. For each i∈[m]i\in[m] let Wi:={𝐖i,1,…,𝐖i,li}W_{i}:=\{\mathbf{W}_{i,1},\ldots,\mathbf{W}_{i,l_{i}}\} be the support of 𝐖i\mathbf{W}_{i}. Then, the mixed characteristic polynomials

(2.3) μ​[𝐖1,j1,…,𝐖m,jm]​(x),1≤ji≤li,i=1,…,m\mu[\mathbf{W}_{1,j_{1}},\ldots,\mathbf{W}_{m,j_{m}}](x),\quad 1\leq j_{i}\leq l_{i},\,\,i=1,\ldots,m

form an interlacing family.

It is also pointed out by Brändén in [Bra¨{\rm\ddot{a}}18] that the mixed characteristic polynomial μ​[𝐗1,…,𝐗m]​(x)\mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}](x) is affine linear in each 𝐗i\mathbf{X}_{i}, i.e., for all α∈ℝ\alpha\in\mathbb{R} and all i∈[m]i\in[m]:

(2.4) μ​[𝐗1,…,(1−α)⋅𝐗i+α⋅𝐗i′,…,𝐗m]​(x)\displaystyle\quad\ \ \mu[\mathbf{X}_{1},\ldots,(1-\alpha)\cdot\mathbf{X}_{i}+\alpha\cdot\mathbf{X}_{i}^{\prime},\ldots,\mathbf{X}_{m}](x)
=(1−α)⋅μ​[𝐗1,…,𝐗i,…,𝐗m]​(x)+α⋅μ​[𝐗1,…,𝐗i′,…,𝐗m]​(x),\displaystyle=(1-\alpha)\cdot\mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{i},\ldots,\mathbf{X}_{m}](x)+\alpha\cdot\mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{i}^{\prime},\ldots,\mathbf{X}_{m}](x),

where 𝐗1,…,𝐗m,𝐗i′∈ℂd×d\mathbf{X}_{1},\ldots,\mathbf{X}_{m},\mathbf{X}_{i}^{\prime}\in\mathbb{C}^{d\times d}. Hence, if 𝐖1,…,𝐖m\mathbf{W}_{1},\ldots,\mathbf{W}_{m} are independent random matrices with finite support, then we have

(2.5) 𝔼​μ​[𝐖1,…,𝐖m]​(x)=μ​[𝔼​𝐖1,…,𝔼​𝐖m]​(x).\mathbb{E}\ \mu[\mathbf{W}_{1},\ldots,\mathbf{W}_{m}](x)=\mu[\mathbb{E}\mathbf{W}_{1},\ldots,\mathbb{E}\mathbf{W}_{m}](x).

3. A new formula for mixed characteristic polynomials

For positive integers kk and mm, we first introduce the (k,m)(k,m)-determinant and (k,m)(k,m)-characteristic polynomial of a matrix 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km}. Then we show some connections between (k,m)(k,m)-characteristic polynomials and mixed characteristic polynomials. Recall that we use 𝒫k​(m)\mathcal{P}_{k}(m) to denote the set of all kk-partitions of [m][m]. Also recall that for each 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km} and each 𝒮=(S1,…,Sk)∈[m]k\mathcal{S}=(S_{1},\ldots,S_{k})\in[m]^{k} we use 𝐀​(𝒮)\mathbf{A}(\mathcal{S}) to denote the principal submatrix of 𝐀\mathbf{A} with rows and columns indexed by S1∪(m+S2)∪⋯∪((k−1)⋅m+Sk)S_{1}\cup(m+S_{2})\cup\cdots\cup((k-1)\cdot m+S_{k}).

Definition 3.1.

Let k,mk,m be two positive integers. For any matrix 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km}, the (k,m)(k,m)-determinant Dk,m​[𝐀]D_{k,m}[\mathbf{A}] of 𝐀\mathbf{A} is defined as

Dk,m​[𝐀]:=∑𝒮∈𝒫k​(m)det[𝐀​(𝒮)].D_{k,m}[\mathbf{A}]:=\sum\limits_{\mathcal{S}\in\mathcal{P}_{k}(m)}\det[\mathbf{A}(\mathcal{S})].

The (k,m)(k,m)-characteristic polynomial ψk,m​[𝐀]​(x)\psi_{k,m}[\mathbf{A}](x) of 𝐀\mathbf{A} is defined as

(3.1) ψk,m​[𝐀]​(x):=1km⋅Dk,m​[x⋅𝐈k​m−𝐀].\psi_{k,m}[\mathbf{A}](x):=\frac{1}{k^{m}}\cdot D_{k,m}[x\cdot\mathbf{I}_{km}-\mathbf{A}].
Remark 3.2.

A simple calculation shows that ψk,m​[𝐀]​(x)\psi_{k,m}[\mathbf{A}](x) is a monic polynomial of degree mm. For k=1k=1, we have D1,m​[𝐀]=det[𝐀]D_{1,m}[\mathbf{A}]=\det[\mathbf{A}], and ψ1,m​[𝐀]​(x)\psi_{1,m}[\mathbf{A}](x) is the regular characteristic polynomial of 𝐀∈ℂm×m\mathbf{A}\in\mathbb{C}^{m\times m}. If we take m=1m=1, then ψk,1​[𝐀]​(x)\psi_{k,1}[\mathbf{A}](x) is a multiple of the (k−1)(k-1)-th order derivative of the characteristic polynomial of 𝐀∈ℂk×k\mathbf{A}\in\mathbb{C}^{k\times k} (see Proposition 3.3).

We next introduce some connections among Dk,m​[𝐀],ψk,m​[𝐀]​(x)D_{k,m}[\mathbf{A}],\psi_{k,m}[\mathbf{A}](x) and other generalizations of the determinant and the characteristic polynomial in the literature.

  1. 1.

    (Borcea-Brändén [BB08]) For a kk-tuple (𝐀1,…,𝐀k)(\mathbf{A}_{1},\ldots,\mathbf{A}_{k}) of matrices in ℂm×m\mathbb{C}^{m\times m}, the mixed determinant, first introduced by Borcea and Brändén in [BB08], is defined as

    D​[𝐀1,…,𝐀k]:=∑(S1,…,Sk)∈𝒫k​(m)∏i=1kdet[𝐀i​(Si)].D[\mathbf{A}_{1},\ldots,\mathbf{A}_{k}]:=\sum_{(S_{1},\ldots,S_{k})\in\mathcal{P}_{k}(m)}\prod_{i=1}^{k}\det[\mathbf{A}_{i}(S_{i})].

    Note that D​(x⋅𝐈m,−𝐁)=det(x⋅𝐈m−𝐁)D(x\cdot\mathbf{I}_{m},-\mathbf{B})=\det(x\cdot\mathbf{I}_{m}-\mathbf{B}) is the regular characteristic polynomial of 𝐁∈ℂm×m\mathbf{B}\in\mathbb{C}^{m\times m}. In [BB08], Borcea and Brändén used the notion of the mixed determinant to prove a stronger version of Johnson’s Conjecture. We remark here that the (k,m)(k,m)-determinant introduced in Definition 3.1 can be viewed as a generalization of the mixed determinant by the following identity:

    (3.2) Dk,m​[𝐀]=D​[𝐀1,…,𝐀k],D_{k,m}[\mathbf{A}]\,\,=\,\,D[\mathbf{A}_{1},\ldots,\mathbf{A}_{k}],

    where 𝐀=diag​(𝐀1,𝐀2,…,𝐀k)∈ℂk​m×k​m\mathbf{A}={\rm diag}(\mathbf{A}_{1},\mathbf{A}_{2},\ldots,\mathbf{A}_{k})\in\mathbb{C}^{km\times km} is a block diagonal matrix.

  2. 2.

    (Ravichandran-Leake [RL20]) For a matrix 𝐁∈ℂm×m\mathbf{B}\in\mathbb{C}^{m\times m}, the kk-characteristic polynomial of the matrix 𝐁\mathbf{B} is defined as (see [RL20, Proposition 2])

    (3.3) χk​[𝐁]​(x):=D​[x⋅𝐈m−𝐁,…,x⋅𝐈m−𝐁⏟k].\chi_{k}[\mathbf{B}](x):=D[\underbrace{x\cdot\mathbf{I}_{m}-\mathbf{B},\ldots,x\cdot\mathbf{I}_{m}-\mathbf{B}}_{k}].

    Ravichandran and Leake used the kk-characteristic polynomial to prove Anderson’s paving formulation of Kadison-Singer problem [RL20]. It is easy to see the relationship between χk\chi_{k} and ψk,m\psi_{k,m} :

    (3.4) χk​[𝐁]​(x)=km⋅ψk,m​[diag​(𝐁,…,𝐁⏟k)]​(x).\chi_{k}[\mathbf{B}](x)=k^{m}\cdot\psi_{k,m}[{\rm diag}(\underbrace{\mathbf{B},\ldots,\mathbf{B}}_{k})](x).
  3. 3.

    (Ravichandran-Srivastava [RS19]) For a kk-tuple (𝐀1,…,𝐀k)(\mathbf{A}_{1},\ldots,\mathbf{A}_{k}) of matrices in ℂm×m\mathbb{C}^{m\times m}, the mixed determinantal polynomial is defined as

    (3.5) χ​[𝐀1,…,𝐀k]​(x):=1km⋅D​[x⋅𝐈m−𝐀1,…,x⋅𝐈m−𝐀k].\chi[\mathbf{A}_{1},\ldots,\mathbf{A}_{k}](x):=\frac{1}{k^{m}}\cdot D[x\cdot\mathbf{I}_{m}-\mathbf{A}_{1},\ldots,x\cdot\mathbf{I}_{m}-\mathbf{A}_{k}].

    Ravichandran and Srivastava used the mixed determinantal polynomial to provide a simultaneous paving of a kk-tuple of zero-diagonal Hermitian matrices [RL20]. According to (3.2), we immediately have the following identity:

    (3.6) χ​[𝐀1,…,𝐀k]​(x)=ψk,m​[diag​(𝐀1,…,𝐀k)]​(x).\chi[\mathbf{A}_{1},\ldots,\mathbf{A}_{k}](x)=\psi_{k,m}[{\rm diag}(\mathbf{A}_{1},\ldots,\mathbf{A}_{k})](x).

    Hence, the (k,m)(k,m)-characteristic polynomial can be considered as a generalization of the mixed determinantal polynomial.

We next provide several basic properties about the (k,m)(k,m)-characteristic polynomial. The first one provides an alternative expression of (k,m)(k,m)-characteristic polynomial.

Proposition 3.3.

Let k,mk,m be two positive integers. Let

𝐙k:=diag​(𝐳,…,𝐳⏟k)and𝐳:=(z1,…,zm).\mathbf{Z}_{k}:={\rm diag}(\underbrace{\mathbf{z},\ldots,\mathbf{z}}_{k})\quad{\rm and}\quad\mathbf{z}:=(z_{1},\ldots,z_{m}).

Then, for any matrix 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km}, we have

(3.7) ψk,m​[𝐀]​(x)=1(k!)m⋅∏i=1m∂zik−1⋅det[𝐙k−𝐀]|z1=⋯=zm=x.\psi_{k,m}[\mathbf{A}](x)=\frac{1}{(k!)^{m}}\cdot\prod\limits_{i=1}^{m}\partial_{z_{i}}^{k-1}\cdot\det[\mathbf{Z}_{k}-\mathbf{A}]|_{z_{1}=\cdots=z_{m}=x}.
Remark 3.4.

Proposition 3.3 can be considered as a generalization of [RL20, Proposition 1] and [RS19, Proposition 2.3], which express the kk-characteristic polynomial and the mixed determinantal polynomial both in differential formulas. In [RL20], Ravichandran and Leake showed that

χk​[𝐁]​(x)=∏i=1m∂zik−1det[𝐙−𝐁]k|z1=…=zm=x\chi_{k}[\mathbf{B}](x)=\prod_{i=1}^{m}\partial_{z_{i}}^{k-1}\det[\mathbf{Z}-\mathbf{B}]^{k}|_{z_{1}=\ldots=z_{m}=x}

for matrix 𝐁∈ℂm×m\mathbf{B}\in\mathbb{C}^{m\times m}, where 𝐙=diag​(z1,…,zm)\mathbf{Z}={\rm diag}(z_{1},\ldots,z_{m}). In [RS19], Ravichandran and Srivastava showed that

χ​[𝐀1,…​𝐀k]​(x)=1(k!)m​∏i=1m∂zik−1∏j=1kdet[𝐙−𝐀i]|z1=…=zm=x.\chi[\mathbf{A}_{1},\ldots\mathbf{A}_{k}](x)=\frac{1}{(k!)^{m}}\prod_{i=1}^{m}\partial_{z_{i}}^{k-1}\prod_{j=1}^{k}\det[\mathbf{Z}-\mathbf{A}_{i}]|_{z_{1}=\ldots=z_{m}=x}.

for matrices 𝐀1,…,𝐀k∈ℂm×m\mathbf{A}_{1},\ldots,\mathbf{A}_{k}\in\mathbb{C}^{m\times m}. These two formulas correspond to the case where 𝐀\mathbf{A} is a block-diagoal matrices in Proposition 3.3.

Proof of Proposition 3.3.

To prove the conclusion, according to (3.1), it is enough to show that

1km⋅Dk,m​[x⋅𝐈k​m−𝐀]=1(k!)m⋅∏i=1m∂zik−1⋅det[𝐙k−𝐀]|z1=⋯=zm=x.\frac{1}{k^{m}}\cdot D_{k,m}[x\cdot\mathbf{I}_{km}-\mathbf{A}]=\frac{1}{(k!)^{m}}\cdot\prod\limits_{i=1}^{m}\partial_{z_{i}}^{k-1}\cdot\det[\mathbf{Z}_{k}-\mathbf{A}]|_{z_{1}=\cdots=z_{m}=x}.

A simple calculation shows that the following algebraic identity holds for any polynomial f​(x1,…,xk)f(x_{1},\ldots,x_{k}):

(3.8) ∑j=1k∂xjf​(x1,…,xk)|x1=⋯=xk=x=∂xf​(x,…,x).\sum\limits_{j=1}^{k}\partial_{x_{j}}f(x_{1},\ldots,x_{k})\ |_{x_{1}=\cdots=x_{k}=x}=\partial_{x}f(x,\ldots,x).

For ρ​(x1,…,xk):=∏j∈Sxj\rho(x_{1},\ldots,x_{k}):=\prod_{j\in S}x_{j} with S⊂[k]S\subset[k], we have

(k−1)!⋅∑j=1k(∏l≠j∂xl)​ρ|x1=⋯=xk=x=∂xk−1ρ​(x,…,x),(k-1)!\cdot\sum\limits_{j=1}^{k}(\prod_{l\neq j}\partial_{x_{l}})\rho\ |_{x_{1}=\cdots=x_{k}=x}=\partial_{x}^{k-1}\rho(x,\ldots,x),

which implies

(3.9) (k−1)!⋅∑j=1k(∏l≠j∂xl)​f|x1=⋯=xk=x=∂xk−1f​(x,…,x),(k-1)!\cdot\sum\limits_{j=1}^{k}(\prod_{l\neq j}\partial_{x_{l}})f\ |_{x_{1}=\cdots=x_{k}=x}=\partial_{x}^{k-1}f(x,\ldots,x),

where f​(x1,…,xk)f(x_{1},\ldots,x_{k}) is a polynomial which has degree 11 in each xjx_{j}. Now we define the polynomial

(3.10) pt​(z1,…,zm):=(∏i=1t∂zik−1)​det[𝐙k−𝐀],p_{t}(z_{1},\ldots,z_{m}):=(\prod\limits_{i=1}^{t}\partial_{z_{i}}^{k-1})\det[\mathbf{Z}_{k}-\mathbf{A}],

for each t∈[m]t\in[m]. We set

g​(z1,1,…,zm,1,…,z1,k,…,zm,k):=det[𝐙−𝐀],g(z_{1,1},\ldots,z_{m,1},\ldots,z_{1,k},\ldots,z_{m,k}):=\det[\mathbf{Z}-\mathbf{A}],

where

𝐙:=diag​(z1,1,…,zm,1,…,z1,k,…,zm,k).\mathbf{Z}:={\rm diag}(z_{1,1},\ldots,z_{m,1},\ldots,z_{1,k},\ldots,z_{m,k}).

For each t∈[m]t\in[m], we use (3.9) to obtain that

(3.11) pt​(z1,…,zm)=((k−1)!)t​∏i=1t(∑j=1k(∏l≠j∂zi,l))​g​(z1,1,…,zm,1,…,z1,k,…,zm,k)|zs,t=zs,∀s∈[k],∀t∈[m].\displaystyle p_{t}(z_{1},\ldots,z_{m})=((k-1)!)^{t}\prod_{i=1}^{t}(\sum\limits_{j=1}^{k}(\prod_{l\neq j}\partial_{z_{i,l}}))g(z_{1,1},\ldots,z_{m,1},\ldots,z_{1,k},\ldots,z_{m,k})\ |_{z_{s,t}=z_{s},\ \forall s\in[k],\ \forall t\in[m]}.

A simple calculation shows that

(3.12) ∏i=1t(∑j=1k(∏l≠j∂zi,l))=∑𝒮=(S1,…,Sk)∈𝒫k​(t)∏j=1k∏i∈Sj∏l≠j∂zi,l.\prod_{i=1}^{t}(\sum\limits_{j=1}^{k}(\prod_{l\neq j}\partial_{z_{i,l}}))=\sum\limits_{\mathcal{S}=(S_{1},\ldots,S_{k})\in\mathcal{P}_{k}(t)}\prod_{j=1}^{k}\prod_{i\in S_{j}}\prod_{l\neq j}\partial_{z_{i,l}}.

Also note that, for each 𝒮=(S1,…,Sk)∈𝒫k​(t)\mathcal{S}=(S_{1},\ldots,S_{k})\in\mathcal{P}_{k}(t), we have

(3.13) (∏j=1k∏i∈Sj∏l≠j∂zi,l)⋅g=det[(𝐙−𝐀)​(𝒯t,𝒮)],(\prod_{j=1}^{k}\prod_{i\in S_{j}}\prod_{l\neq j}\partial_{z_{i,l}})\cdot g=\det[(\mathbf{Z}-\mathbf{A})(\mathcal{T}_{t,\mathcal{S}})],

where 𝒯t,𝒮\mathcal{T}_{t,\mathcal{S}} is defined as

(3.14) 𝒯t,𝒮:=(S1∪{t+1,t+2,…,m},…,Sk∪{t+1,t+2,…,m})∈[m]k.\mathcal{T}_{t,\mathcal{S}}:=(S_{1}\cup\{t+1,t+2,\ldots,m\},\ldots,S_{k}\cup\{t+1,t+2,\ldots,m\})\in[m]^{k}.

Combining (3.11), (3.12) and (3.13), we obtain that, for each t∈[m]t\in[m],

(3.15) pt​(z1,…,zm)\displaystyle p_{t}(z_{1},\ldots,z_{m}) =((k−1)!)t​∑𝒮=(S1,…,Sk)∈𝒫k​(t)det[(𝐙−𝐀)​(𝒯t,𝒮)]|zi,j=zi,∀i∈[k],∀j∈[m]\displaystyle=((k-1)!)^{t}\sum\limits_{\mathcal{S}=(S_{1},\ldots,S_{k})\in\mathcal{P}_{k}(t)}\det[(\mathbf{Z}-\mathbf{A})(\mathcal{T}_{t,\mathcal{S}})]\ |_{z_{i,j}=z_{i},\ \forall i\in[k],\ \forall j\in[m]}
=((k−1)!)t​∑𝒮=(S1,…,Sk)∈𝒫k​(t)det[(𝐙k−𝐀)​(𝒯t,𝒮)].\displaystyle=((k-1)!)^{t}\sum\limits_{\mathcal{S}=(S_{1},\ldots,S_{k})\in\mathcal{P}_{k}(t)}\det[(\mathbf{Z}_{k}-\mathbf{A})(\mathcal{T}_{t,\mathcal{S}})].

In particular, when t=mt=m, we have

(3.16) pm​(z1,…,zm)=((k−1)!)m​∑𝒮=(S1,…,Sk)∈𝒫k​(m)det[(𝐙k−𝐀)​(𝒮)].\displaystyle p_{m}(z_{1},\ldots,z_{m})=((k-1)!)^{m}\sum\limits_{\mathcal{S}=(S_{1},\ldots,S_{k})\in\mathcal{P}_{k}(m)}\det[(\mathbf{Z}_{k}-\mathbf{A})(\mathcal{S})].

Combining (3.10) and (3.16), we obtain that

1(k!)m⋅(∏i=1m∂zik−1)​det[𝐙k−𝐀]|z1=⋯=zm=x\displaystyle\quad\frac{1}{(k!)^{m}}\cdot(\prod\limits_{i=1}^{m}\partial_{z_{i}}^{k-1})\det[\mathbf{Z}_{k}-\mathbf{A}]\ |_{z_{1}=\cdots=z_{m}=x}
=1km⋅∑𝒮=(S1,…,Sk)∈𝒫k​(m)det[(𝐙k−𝐀)​(𝒮)]|z1=⋯=zm=x\displaystyle=\frac{1}{k^{m}}\cdot\sum\limits_{\mathcal{S}=(S_{1},\ldots,S_{k})\in\mathcal{P}_{k}(m)}\det[(\mathbf{Z}_{k}-\mathbf{A})(\mathcal{S})]\ |_{z_{1}=\cdots=z_{m}=x}
=1km⋅∑𝒮=(S1,…,Sk)∈𝒫k​(m)det[x⋅𝐈m−𝐀​(𝒮)]\displaystyle=\frac{1}{k^{m}}\cdot\sum\limits_{\mathcal{S}=(S_{1},\ldots,S_{k})\in\mathcal{P}_{k}(m)}\det[x\cdot\mathbf{I}_{m}-\mathbf{A}(\mathcal{S})]
=1km⋅Dk,m​[x⋅𝐈k​m−𝐀]=ψk,m​[𝐀]​(x).\displaystyle=\frac{1}{k^{m}}\cdot D_{k,m}[x\cdot\mathbf{I}_{km}-\mathbf{A}]=\psi_{k,m}[\mathbf{A}](x).

∎

The next proposition shows that ψk,m​[𝐀]​(x)\psi_{k,m}[\mathbf{A}](x) is real-rooted if 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km} is Hermitian.

Proposition 3.5.

Let k,mk,m be two positive integers. For any Hermitian matrix 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km}, the (k,m)(k,m)-characteristic polynomial ψk,m​[𝐀]​(x)\psi_{k,m}[\mathbf{A}](x) is real-rooted.

Proof.

Since 𝐀\mathbf{A} is Hermitian, by Lemma 2.5, we see that the polynomial

det[𝐙k−𝐀]∈ℝ​[z1,…,zm]\det[\mathbf{Z}_{k}-\mathbf{A}]\in\mathbb{R}[z_{1},\ldots,z_{m}]

is either real stable or identically zero. If it is zero, then we are done. We assume that det[𝐙k−𝐀]≢0\det[\mathbf{Z}_{k}-\mathbf{A}]\not\equiv 0. Lemma 2.6 shows that the differential operator ∏i=1m∂zik−1\prod\limits_{i=1}^{m}\partial_{z_{i}}^{k-1} and setting all variables to xx preserve real stability. Then, by Proposition 3.3, we conclude that ψk,m​[𝐀]​(x)\psi_{k,m}[\mathbf{A}](x) is a univariate real stable polynomial, which is real-rooted. ∎

We next present several properties about the roots of the (k,m)(k,m)-characteristic polynomial ψk,m​[𝐀]​(x)\psi_{k,m}[\mathbf{A}](x) of a Hermitian matrix 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km}.

Proposition 3.6.

Let k,mk,m be two positive integers. Assume that 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km} is a Hermitian matrix. Then we have the following results:

  1. (i)

    The sum of the roots of ψk,m​[𝐀]​(x)\psi_{k,m}[\mathbf{A}](x) equals tr⁡(𝐀)k\frac{\operatorname{tr}(\mathbf{A})}{k}.

  2. (ii)

    For any vector 𝐯∈ℂk​m\mathbf{v}\in\mathbb{C}^{km} we have

    (3.17) maxroot⁡ψk,m​[𝐀]≤maxroot⁡ψk,m​[𝐀+𝐯𝐯∗].\operatorname{maxroot}\ \psi_{k,m}[\mathbf{A}]\leq\operatorname{maxroot}\ \psi_{k,m}[\mathbf{A+\mathbf{v}\mathbf{v}^{*}}].
  3. (iii)

    If 𝐀\mathbf{A} is positive semidefinite, then we have

    (3.18) ‖𝐀‖≤k⋅maxroot⁡ψk,m​[𝐀].\|\mathbf{A}\|\leq k\cdot\operatorname{maxroot}\ \psi_{k,m}[\mathbf{A}].
Proof.

(i) We use α\alpha to denote the sum of the roots of ψk,m​[𝐀]​(x)\psi_{k,m}[\mathbf{A}](x). Since ψk,m​[𝐀]​(x)\psi_{k,m}[\mathbf{A}](x) is a real-rooted polynomial of degree mm with leading coefficient being 11, it is known that α\alpha equals the negative value of the coefficient of xm−1x^{m-1} in ψk,m​[𝐀]​(x)\psi_{k,m}[\mathbf{A}](x). Note that, for each kk-partition 𝒮\mathcal{S} of [m][m], the characteristic polynomial of 𝐀​(𝒮)\mathbf{A}(\mathcal{S}) is of the form

xm−tr⁡(𝐀​(𝒮))⋅xm−1+lower order terms.x^{m}-\operatorname{tr}(\mathbf{A}(\mathcal{S}))\cdot x^{m-1}+\ \text{lower order terms.}

According to (3.1), we have

(3.19) α=1km⋅∑𝒮∈𝒫k​(m)tr⁡(𝐀​(𝒮)).\alpha=\frac{1}{k^{m}}\cdot\sum\limits_{\mathcal{S}\in\mathcal{P}_{k}(m)}\operatorname{tr}(\mathbf{A}(\mathcal{S})).

Observing that each diagonal entry of 𝐀\mathbf{A} appears in exactly km−1k^{m-1} distinct kk-partitions of [m][m], we can rewrite equation (3.19) as

α=1km⋅km−1⋅tr⁡(𝐀)=tr⁡(𝐀)k,\alpha=\frac{1}{k^{m}}\cdot k^{m-1}\cdot\operatorname{tr}(\mathbf{A})=\frac{\operatorname{tr}(\mathbf{A})}{k},

which gives the desired result.

(ii) For each t∈ℝt\in\mathbb{R} we set

pt​(x):=ψk,m​[𝐀+t⋅𝐯𝐯∗]​(x).p_{t}(x):=\psi_{k,m}[\mathbf{A}+t\cdot\mathbf{v}\mathbf{v}^{*}](x).

According to Proposition 3.5, pt​(x)p_{t}(x) is real-rooted for each t∈ℝt\in\mathbb{R}. Define f:ℝ→ℝf:\mathbb{R}\to\mathbb{R} as

f​(t):=maxroot⁡pt​(x).f(t):=\operatorname{maxroot}\ p_{t}(x).

Since the maximal root of a real-rooted polynomial is continuous in its coefficients, we obtain that ff is a continuous function. Also note that

(3.20) p0​(x)=ψk,m​[𝐀]​(x),p1​(x)=ψk,m​[𝐀+𝐯𝐯∗]​(x).p_{0}(x)=\psi_{k,m}[\mathbf{A}](x),\ p_{1}(x)=\psi_{k,m}[\mathbf{A}+\mathbf{v}\mathbf{v}^{*}](x).

Hence, it is enough to show that f​(t)f(t) is monotone increasing in tt which implies f​(0)≤f​(1)f(0)\leq f(1) and hence (3.17).

According to Definition 3.1 we have

pt​(x)=1km⋅∑𝒮∈𝒫k​(m)det[x⋅𝐈m−𝐀​(𝒮)−t⋅𝐯𝒮​𝐯𝒮∗],p_{t}(x)=\frac{1}{k^{m}}\cdot\sum\limits_{\mathcal{S}\in\mathcal{P}_{k}(m)}\det[x\cdot\mathbf{I}_{m}-\mathbf{A}(\mathcal{S})-t\cdot\mathbf{v}_{\mathcal{S}}\mathbf{v}_{\mathcal{S}}^{*}],

where 𝐯𝒮\mathbf{v}_{\mathcal{S}} denotes the subvector of 𝐯\mathbf{v} by extracting the entries of 𝐯\mathbf{v} indexed by S1∪(m+S2)∪⋯∪((k−1)⋅m+Sk)S_{1}\cup(m+S_{2})\cup\cdots\cup((k-1)\cdot m+S_{k}). Note that, for each 𝒮∈𝒫k​(m)\mathcal{S}\in\mathcal{P}_{k}(m), det[x⋅𝐈m−𝐀​(𝒮)−t⋅𝐯𝒮​𝐯𝒮∗]\det[x\cdot\mathbf{I}_{m}-\mathbf{A}(\mathcal{S})-t\cdot\mathbf{v}_{\mathcal{S}}\mathbf{v}_{\mathcal{S}}^{*}] is a polynomial in tt of degree at most one, which implies that we can write pt​(x)p_{t}(x) in the form of

(3.21) pt​(x)=(1−t)⋅p0​(x)+t⋅p1​(x).p_{t}(x)=(1-t)\cdot p_{0}(x)+t\cdot p_{1}(x).

We next prove that ff is monotone by contradiction. For the aim of contradiction, we assume that ff is not monotone. Since ff is continuous, there exist t1,s1∈ℝt_{1},s_{1}\in\mathbb{R} such that t1<s1t_{1}<s_{1} and f​(t1)=f​(s1)=z1f(t_{1})=f(s_{1})=z_{1}. We use (3.21) to obtain

(1−t1)⋅p0​(z1)+t1⋅p1​(z1)=(1−s1)⋅p0​(z1)+s1⋅p1​(z1)=0,(1-t_{1})\cdot p_{0}(z_{1})+t_{1}\cdot p_{1}(z_{1})=(1-s_{1})\cdot p_{0}(z_{1})+s_{1}\cdot p_{1}(z_{1})=0,

which implies

(3.22) p0​(z1)=p1​(z1)=0.p_{0}(z_{1})=p_{1}(z_{1})=0.

Then we substitute (3.22) into (3.21) and obtain pt​(z1)=0p_{t}(z_{1})=0 for any t∈ℝt\in\mathbb{R}. By the definition of ff, this means that f​(t)≥z1f(t)\geq z_{1} for any t∈ℝt\in\mathbb{R}. Let zm​a​x:=maxt1≤t≤s1⁡f​(t)z_{max}:=\max\limits_{t_{1}\leq t\leq s_{1}}f(t). Since ff is not monotone, we have zm​a​x>z1z_{max}>z_{1}. Set z2=12⋅(z1+zm​a​x)>z1z_{2}=\frac{1}{2}\cdot(z_{1}+z_{max})>z_{1}. By continuity, there exist t2,s2∈[t1,s1]t_{2},s_{2}\in[t_{1},s_{1}] such that t2<s2t_{2}<s_{2} and f​(t2)=f​(s2)=z2f(t_{2})=f(s_{2})=z_{2}. Then the preceding argument shows that f​(t)≥z2f(t)\geq z_{2} for any t∈ℝt\in\mathbb{R}, which contradicts with f​(t1)=f​(s1)=z1<z2f(t_{1})=f(s_{1})=z_{1}<z_{2}. Hence, ff is monotone.

We next show that ff is monotone increasing. Let αt\alpha_{t} denote the sum of the roots of pt​(x)p_{t}(x). It follows from (i) that

αt=tr⁡(𝐀)k+𝐯∗​𝐯k⋅t.\alpha_{t}=\frac{\operatorname{tr}(\mathbf{A})}{k}+\frac{\mathbf{v}^{*}\mathbf{v}}{k}\cdot t.

Hence, when t→+∞t\to+\infty, we have αt→+∞\alpha_{t}\to+\infty. Since αt≤m⋅maxroot⁡pt​(x)\alpha_{t}\leq m\cdot\operatorname{maxroot}\ p_{t}(x), we have

f​(t)=maxroot⁡pt​(x)→+∞f(t)=\operatorname{maxroot}\ p_{t}(x)\to+\infty

with t→+∞t\to+\infty. Thus, ff is monotone increasing in tt which implies f​(1)≥f​(0)f(1)\geq f(0). We arrive at the conclusion.

(iii) By the spectral decomposition, we can write

𝐀=∑i=1k​mλi​(𝐀)​𝐯i​𝐯i∗,\mathbf{A}=\sum\limits_{i=1}^{km}\lambda_{i}(\mathbf{A})\mathbf{v}_{i}\mathbf{v}_{i}^{*},

where 𝐯i∈ℂk​m\mathbf{v}_{i}\in\mathbb{C}^{km} is the unit-norm eigenvector of 𝐀\mathbf{A} corresponding to the ii-th largest eigenvalue λi​(𝐀)\lambda_{i}(\mathbf{A}). Since 𝐀\mathbf{A} is positive semidefinite, we have λi​(𝐀)≥0\lambda_{i}(\mathbf{A})\geq 0 for each i∈[k​m]i\in[km]. According to (3.17), we have

(3.23) maxroot⁡ψk,m​[λ1​(𝐀)​𝐯1​𝐯1∗]≤maxroot⁡ψk,m​[𝐀].\operatorname{maxroot}\ \psi_{k,m}[\lambda_{1}(\mathbf{A})\mathbf{v}_{1}\mathbf{v}_{1}^{*}]\leq\operatorname{maxroot}\ \psi_{k,m}[\mathbf{A}].

A simple calculation shows that

ψk,m​[λ1​(𝐀)​𝐯1​𝐯1∗]​(x)=xm−1​(x−1k⋅λ1​(𝐀)​𝐯1∗​𝐯1),\psi_{k,m}[\lambda_{1}(\mathbf{A})\mathbf{v}_{1}\mathbf{v}_{1}^{*}](x)=x^{m-1}(x-\frac{1}{k}\cdot\lambda_{1}(\mathbf{A})\mathbf{v}_{1}^{*}\mathbf{v}_{1}),

which implies

(3.24) maxroot⁡ψk,m​[λ1​(𝐀)​𝐯1​𝐯1∗]=1k⋅λ1​(𝐀).\operatorname{maxroot}\ \psi_{k,m}[\lambda_{1}(\mathbf{A})\mathbf{v}_{1}\mathbf{v}_{1}^{*}]=\frac{1}{k}\cdot\lambda_{1}(\mathbf{A}).

Since 𝐀\mathbf{A} is positive semidefinite, its operator norm is exactly λ1​(𝐀)\lambda_{1}(\mathbf{A}). Hence, combining (3.23) with (3.24), we arrive at

‖𝐀‖≤k⋅maxroot⁡ψk,m​[𝐀].\|\mathbf{A}\|\leq k\cdot\operatorname{maxroot}\ \psi_{k,m}[\mathbf{A}].

∎

Remark 3.7.

In [RS19, Theorem 1.9], Ravichandran and Srivastava proved that

(3.25) maxroot​det[x⋅𝐈k​m−𝐀]≤k⋅maxroot⁡ψk,m​[𝐀],\operatorname{maxroot}\ \det[x\cdot\mathbf{I}_{km}-\mathbf{A}]\leq k\cdot\operatorname{maxroot}\ \psi_{k,m}[\mathbf{A}],

where 𝐀=diag​(𝐀1,…,𝐀k)∈ℂk​m×k​m\mathbf{A}={\rm diag}(\mathbf{A}_{1},\ldots,\mathbf{A}_{k})\in\mathbb{C}^{km\times km} is a block diagonal matrix with 𝐀i∈ℂm×m\mathbf{A}_{i}\in\mathbb{C}^{m\times m} being zero-diagonal Hermitian. Recall that (3.18) requires that 𝐀\mathbf{A} is positive semidefinite. Motivated by these results, we conjecture (3.18) holds provided 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km} is diagonal-non-negative Hermitian.

Inspired by [RS19, Lemma 5.5], we next show a connection between the (k,m)(k,m)-characteristic polynomial and the mixed characteristic polynomial, which is the main result of this section.

Theorem 3.8.

Let 𝐗1,…,𝐗m∈ℂd×d\mathbf{X}_{1},\ldots,\mathbf{X}_{m}\in\mathbb{C}^{d\times d} be matrices of rank at most kk. Suppose that {𝐮i,j}i∈[m],j∈[k]⊂ℂd\{\mathbf{u}_{i,j}\}_{i\in[m],j\in[k]}\subset\mathbb{C}^{d} and {𝐯i,j}i∈[m],j∈[k]⊂ℂd\{\mathbf{v}_{i,j}\}_{i\in[m],j\in[k]}\subset\mathbb{C}^{d} satisfy

𝐗i=∑j=1k𝐮i,j​𝐯i,j∗for all i∈[m].\mathbf{X}_{i}=\sum\limits_{j=1}^{k}\mathbf{u}_{i,j}\mathbf{v}_{i,j}^{*}\quad\text{for all $i\in[m]$.}

We set 𝐔j:=[𝐮1,j,…,𝐮m,j]∈ℂd×m,𝐕j:=[𝐯1,j,…,𝐯m,j]∈ℂd×m\mathbf{U}_{j}:=[\mathbf{u}_{1,j},\ldots,\mathbf{u}_{m,j}]\in\mathbb{C}^{d\times m},\mathbf{V}_{j}:=[\mathbf{v}_{1,j},\ldots,\mathbf{v}_{m,j}]\in\mathbb{C}^{d\times m} for all j∈[k]j\in[k] and

(3.26) 𝐀:=(𝐕1∗⋮𝐕k∗)​(𝐔1,…,𝐔k)∈ℂk​m×k​m.\mathbf{A}:=\left(\begin{matrix}\mathbf{V}_{1}^{*}\\ \vdots\\ \mathbf{V}_{k}^{*}\end{matrix}\right)(\mathbf{U}_{1},\ldots,\mathbf{U}_{k})\in\mathbb{C}^{km\times km}.

Then, we have

μ​[𝐗1,…,𝐗m]​(x)=xd−m⋅ψk,m​[k⋅𝐀]​(x).\mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}](x)=x^{d-m}\cdot\psi_{k,m}[k\cdot\mathbf{A}](x).
Proof.

For each i∈[m]i\in[m], let 𝐖i\mathbf{W}_{i} be the random rank one matrix taking values in

{k⋅𝐮i,1​𝐯i,1∗,…,k⋅𝐮i,k​𝐯i,k∗}⊂ℂd×d\{\sqrt{k}\cdot\mathbf{u}_{i,1}\mathbf{v}_{i,1}^{*},\ldots,\sqrt{k}\cdot\mathbf{u}_{i,k}\mathbf{v}_{i,k}^{*}\}\subset\mathbb{C}^{d\times d}

with equal probability. Then, we have

𝔼​𝐖i=1k⋅∑j=1kk⋅𝐮i,j​𝐯i,j∗=𝐗i.\mathbb{E}\ \mathbf{W}_{i}=\frac{1}{k}\cdot\sum\limits_{j=1}^{k}k\cdot\mathbf{u}_{i,j}\mathbf{v}_{i,j}^{*}=\mathbf{X}_{i}.

For each subset S⊂[m]S\subset[m] and each j∈[k]j\in[k], we let 𝐔j,S,𝐕j,S∈ℂd×|S|\mathbf{U}_{j,S},\mathbf{V}_{j,S}\in\mathbb{C}^{d\times|S|} denote the submatrix of 𝐔j\mathbf{U}_{j} and 𝐕j\mathbf{V}_{j}, respectively, obtained by extracting the columns indexed by SS. Now a simple calculation shows

μ​[𝐗1,…,𝐗m]​(x)\displaystyle\mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}](x) =𝔼​det[x⋅𝐈d−∑i=1m𝐖i]\displaystyle=\mathbb{E}\ \det[x\cdot\mathbf{I}_{d}-\sum\limits_{i=1}^{m}\mathbf{W}_{i}]
=1km​∑𝒮=(S1,…,Sk)∈𝒫k​(m)det[x⋅𝐈d−k⋅∑j=1k∑i∈Sj𝐮i,j​𝐯i,j∗]\displaystyle=\frac{1}{k^{m}}\sum\limits_{\mathcal{S}=(S_{1},\ldots,S_{k})\in\mathcal{P}_{k}(m)}\det[x\cdot\mathbf{I}_{d}-k\cdot\sum\limits_{j=1}^{k}\sum\limits_{i\in S_{j}}\mathbf{u}_{i,j}\mathbf{v}_{i,j}^{*}]
=1km​∑𝒮=(S1,…,Sk)∈𝒫k​(m)det[x⋅𝐈d−k⋅∑j=1k𝐔j,Sj​𝐕j,Sj∗].\displaystyle=\frac{1}{k^{m}}\sum\limits_{\mathcal{S}=(S_{1},\ldots,S_{k})\in\mathcal{P}_{k}(m)}\det[x\cdot\mathbf{I}_{d}-k\cdot\sum\limits_{j=1}^{k}\mathbf{U}_{j,S_{j}}\mathbf{V}_{j,S_{j}}^{*}].

Note that for each 𝒮=(S1,…,Sk)∈𝒫k​(m)\mathcal{S}=(S_{1},\ldots,S_{k})\in\mathcal{P}_{k}(m) we have

det[x⋅𝐈d−k⋅∑j=1k𝐔j,Sj​𝐕j,Sj∗]\displaystyle\det[x\cdot\mathbf{I}_{d}-k\cdot\sum\limits_{j=1}^{k}\mathbf{U}_{j,S_{j}}\mathbf{V}_{j,S_{j}}^{*}] =det[x⋅𝐈d−k⋅(𝐔1,S1,…,𝐔k,Sk)​(𝐕1,S1∗⋮𝐕k,Sk∗)]\displaystyle=\det[x\cdot\mathbf{I}_{d}-k\cdot(\mathbf{U}_{1,S_{1}},\ldots,\mathbf{U}_{k,S_{k}})\left(\begin{matrix}\mathbf{V}_{1,S_{1}}^{*}\\ \vdots\\ \mathbf{V}_{k,S_{k}}^{*}\end{matrix}\right)]
=xd−m⋅det[x⋅𝐈m−k⋅(𝐕1,S1∗⋮𝐕k,Sk∗)​(𝐔1,S1,…,𝐔k,Sk)]\displaystyle=x^{d-m}\cdot\det[x\cdot\mathbf{I}_{m}-k\cdot\left(\begin{matrix}\mathbf{V}_{1,S_{1}}^{*}\\ \vdots\\ \mathbf{V}_{k,S_{k}}^{*}\end{matrix}\right)(\mathbf{U}_{1,S_{1}},\ldots,\mathbf{U}_{k,S_{k}})]
=xd−m⋅det[x⋅𝐈m−k⋅𝐀​(𝒮)].\displaystyle=x^{d-m}\cdot\det[x\cdot\mathbf{I}_{m}-k\cdot\mathbf{A}(\mathcal{S})].

Hence, we arrive at

μ​[𝐗1,…,𝐗m]​(x)\displaystyle\mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}](x) =xd−m⋅1km​∑𝒮=(S1,…,Sk)∈𝒫k​(m)det[x⋅𝐈m−k⋅𝐀​(𝒮)]\displaystyle=x^{d-m}\cdot\frac{1}{k^{m}}\sum\limits_{\mathcal{S}=(S_{1},\ldots,S_{k})\in\mathcal{P}_{k}(m)}\det[x\cdot\mathbf{I}_{m}-k\cdot\mathbf{A}(\mathcal{S})]
=xd−m⋅ψk,m​[k⋅𝐀]​(x).\displaystyle=x^{d-m}\cdot\psi_{k,m}[k\cdot\mathbf{A}](x).

∎

Remark 3.9.

Note that rank⁡(𝐀)≤d\operatorname{rank}(\mathbf{A})\leq d where 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km} is presented in (3.26). We next assume that 𝐗1,…,𝐗m∈ℂd×d\mathbf{X}_{1},\ldots,\mathbf{X}_{m}\in\mathbb{C}^{d\times d} are positive semidefinite. Combining Proposition 3.5 and Theorem 3.8, we obtain that μ​[𝐗1,…,𝐗m]\mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}] is real-rooted, which conincides with the well-known result in [MSS15b, Corollary 4.4]. Note that

ψk,m​[k⋅𝐀]​(x)=km⋅ψk,m​[𝐀]​(xk).\psi_{k,m}[k\cdot\mathbf{A}](x)=k^{m}\cdot\psi_{k,m}[\mathbf{A}](\frac{x}{k}).

It immediately follows from Theorem 3.8 that

(3.27) maxroot⁡μ​[𝐗1,…,𝐗m]=maxroot⁡ψk,m​[k⋅𝐀]=k⋅maxroot⁡ψk,m​[𝐀].\operatorname{maxroot}\ \mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}]=\operatorname{maxroot}\ \psi_{k,m}[k\cdot\mathbf{A}]=k\cdot\operatorname{maxroot}\ \psi_{k,m}[\mathbf{A}].

Also note that

(3.28) ‖∑i=1m𝐗i‖=‖𝐀‖.\bigg{\|}\sum_{i=1}^{m}\mathbf{X}_{i}\bigg{\|}\,\,=\,\,\|\mathbf{A}\|.

Combining Proposition 3.6 (iii) , (3.27) and (3.28), we obtain that

(3.29) ‖∑i=1m𝐗i‖≤maxroot⁡μ​[𝐗1,…,𝐗m],\bigg{\|}\sum\limits_{i=1}^{m}\mathbf{X}_{i}\bigg{\|}\leq\operatorname{maxroot}\ \mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}],

which is the same with the result in Proposition 2.7.

4. Proof of Theorem 1.9

The aim of this section is to prove Theorem 1.9, which shows an upper bound for the maximum root of μ​[𝐗1,…,𝐗m]\mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}]. To do that, we first present an upper bound of the maximum root of ψk,m​[𝐀]​(x)\psi_{k,m}[\mathbf{A}](x), and then we employ the connection between μ​[𝐗1,…,𝐗m]\mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}] and ψk,m​[𝐀]​(x)\psi_{k,m}[\mathbf{A}](x) (see equation (3.27)) to prove Theorem 1.9.

Theorem 4.1.

Let k≥2k\geq 2 and m≥1m\geq 1 be two positive integers. Assume that 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km} is a positive semidefinite Hermitian matrix such that 𝟎⪯𝐀⪯𝐈k​m\mathbf{0}\preceq\mathbf{A}\preceq\mathbf{I}_{km}. Set

ε:=max1≤i≤m​∑j=1k𝐀​(i+(j−1)​m,i+(j−1)​m).\varepsilon:=\max\limits_{1\leq i\leq m}\sum\limits_{j=1}^{k}\mathbf{A}(i+(j-1)m,i+(j-1)m).

If ε≤(k−1)2k\varepsilon\leq\frac{(k-1)^{2}}{k}, then we have

(4.1) maxroot⁡ψk,m​[𝐀]≤1k⋅(1−εk−1+ε)2.\operatorname{maxroot}\ \psi_{k,m}[\mathbf{A}]\leq\frac{1}{k}\cdot\bigg{(}\sqrt{1-\frac{\varepsilon}{k-1}}+\sqrt{\varepsilon}\bigg{)}^{2}.
Remark 4.2.

Theorem 4.1 generalizes Ravichandran and Leake’s result in [RL20, Theorem 9] which presents an upper bound for the largest root of the kk-characteristic polynomial χk​[𝐁]=km​ψk,m​[diag​(𝐁,…,𝐁⏟k)]\chi_{k}[\mathbf{B}]=k^{m}\psi_{k,m}[{\rm diag}(\underbrace{\mathbf{B},\ldots,\mathbf{B}}_{k})] for matrix 𝐁∈ℂm×m\mathbf{B}\in\mathbb{C}^{m\times m}. Particularly, they showed that

(4.2) maxroot⁡χk​[𝐁]≤1k⋅(1−k​αk−1+k​α)2\operatorname{maxroot}\ \chi_{k}[\mathbf{B}]\leq\frac{1}{k}\cdot\bigg{(}\sqrt{1-\frac{k\alpha}{k-1}}+\sqrt{k\alpha}\bigg{)}^{2}

provided α:=max1≤i≤m⁡𝐁​(i,i)≤(k−1)2k2\alpha:=\max_{1\leq i\leq m}\mathbf{B}(i,i)\leq\frac{(k-1)^{2}}{k^{2}}.

We next give a proof of Theorem 1.9. The proof of Theorem 4.1 is postponed to the end of this section.

Proof of Theorem 1.9.

Recall that 𝐗1,…,𝐗m∈ℂd×d\mathbf{X}_{1},\ldots,\mathbf{X}_{m}\in\mathbb{C}^{d\times d} are positive semidefinite Hermitian matrices of rank at most kk such that ∑i=1m𝐗i⪯𝐈d\sum\limits_{i=1}^{m}\mathbf{X}_{i}\preceq\mathbf{I}_{d}. Suppose that {𝐮i,j}i∈[m],j∈[k]\{\mathbf{u}_{i,j}\}_{i\in[m],j\in[k]} are the vectors in ℂd\mathbb{C}^{d} such that

𝐗i=∑j=1k𝐮i,j​𝐮i,j∗for all i∈[m].\mathbf{X}_{i}=\sum\limits_{j=1}^{k}\mathbf{u}_{i,j}\mathbf{u}_{i,j}^{*}\quad\text{for all $i\in[m]$.}

We set 𝐔:=[𝐮1,1,…,𝐮m,1,…,𝐮1,k,…,𝐮m,k]∈ℂd×k​m\mathbf{U}:=[\mathbf{u}_{1,1},\ldots,\mathbf{u}_{m,1},\ldots,\mathbf{u}_{1,k},\ldots,\mathbf{u}_{m,k}]\in\mathbb{C}^{d\times km} and set 𝐀=𝐔∗​𝐔\mathbf{A}=\mathbf{U}^{*}\mathbf{U}. Note that

𝟎⪯∑i=1m𝐗i=∑i=1m∑j=1k𝐮i,j​𝐮i,j∗=𝐔𝐔∗⪯𝐈d.\mathbf{0}\preceq\sum\limits_{i=1}^{m}\mathbf{X}_{i}=\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{k}\mathbf{u}_{i,j}\mathbf{u}_{i,j}^{*}=\mathbf{U}\mathbf{U}^{*}\preceq\mathbf{I}_{d}.

Since 𝐔𝐔∗\mathbf{U}\mathbf{U}^{*} and 𝐔∗​𝐔\mathbf{U}^{*}\mathbf{U} have the same nonzero eigenvalues, we obtain

𝟎⪯𝐀⪯𝐈k​m.\mathbf{0}\preceq\mathbf{A}\preceq\mathbf{I}_{km}.

Moreover, for each i∈[m]i\in[m] we have

tr⁡(𝐗i)=tr⁡(∑j=1k𝐮i,j​𝐮i,j∗)=∑j=1k𝐀​(i+(j−1)​m,i+(j−1)​m)≤ε.\operatorname{tr}(\mathbf{X}_{i})=\operatorname{tr}(\sum\limits_{j=1}^{k}\mathbf{u}_{i,j}\mathbf{u}_{i,j}^{*})=\sum\limits_{j=1}^{k}\mathbf{A}(i+(j-1)m,i+(j-1)m)\leq\varepsilon.

Since ε≤(k−1)2/k\varepsilon\leq(k-1)^{2}/k, Theorem 4.1 gives

maxroot⁡ψk,m​[𝐀]≤1k⋅(1−εk−1+ε)2,\operatorname{maxroot}\ \psi_{k,m}[\mathbf{A}]\leq\frac{1}{k}\cdot\bigg{(}\sqrt{1-\frac{\varepsilon}{k-1}}+\sqrt{\varepsilon}\bigg{)}^{2},

which implies

maxroot⁡μ​[𝐗1,…,𝐗m]≤(1−εk−1+ε)2.\operatorname{maxroot}\ \mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}]\leq\bigg{(}\sqrt{1-\frac{\varepsilon}{k-1}}+\sqrt{\varepsilon}\bigg{)}^{2}.

Here, we use Theorem 3.8, i.e.,

maxroot⁡μ​[𝐗1,…,𝐗m]=k⋅maxroot⁡ψk,m​[𝐀].\operatorname{maxroot}\ \mu[\mathbf{X}_{1},\ldots,\mathbf{X}_{m}]=k\cdot\operatorname{maxroot}\ \psi_{k,m}[\mathbf{A}].

∎

In the remainder of this section, we aim to prove Theorem 4.1 by adapting the method of multivariate barrier function. We first introduce the barrier function of a real stable polynomial (see also [MSS15b]).

Definition 4.3.

Let p​(z1,…,zm)∈ℝ​[z1,…,zm]p(z_{1},\ldots,z_{m})\in\mathbb{R}[z_{1},\ldots,z_{m}] be a multivariate polynomial. We say that a point 𝐳∈ℝm\mathbf{z}\in\mathbb{R}^{m} is above the roots of p​(z1,…,zm)p(z_{1},\ldots,z_{m}) if p​(𝐳+𝐭)≠0p(\mathbf{z}+\mathbf{t})\neq 0 for all 𝐭∈ℝ≥0m\mathbf{t}\in\mathbb{R}_{\geq 0}^{m}. We use 𝐀𝐛p\mathbf{Ab}_{p} to denote the set of points that are above the roots of pp.

Definition 4.4.

Let p∈ℝ​[z1,…,zm]p\in\mathbb{R}[z_{1},\ldots,z_{m}] be a real stable polynomial. The barrier function of pp at a point 𝐳∈𝐀𝐛p\mathbf{z}\in\mathbf{Ab}_{p} in the direction ii is defined as

(4.3) Φpi​(𝐳):=∂zipp​(𝐳).\Phi_{p}^{i}(\mathbf{z}):=\frac{\partial_{z_{i}}p}{p}(\mathbf{z}).

Here we briefly introduce our proof of Theorem 4.1. According to Proposition 3.3, we have

ψk,m​[𝐀]​(x)=1(k!)m⋅∏i=1m∂zik−1⋅det[𝐙k−𝐀]|z1=⋯=zm=x,\psi_{k,m}[\mathbf{A}](x)=\frac{1}{(k!)^{m}}\cdot\prod\limits_{i=1}^{m}\partial_{z_{i}}^{k-1}\cdot\det[\mathbf{Z}_{k}-\mathbf{A}]|_{z_{1}=\cdots=z_{m}=x},

where 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km}. For Hermitian matrix 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km}, we consider the real stable polynomial

(4.4) p0​(z1,⋯,zm):=det[𝐙k−𝐀],p_{0}(z_{1},\cdots,z_{m}):=\det[\mathbf{Z}_{k}-\mathbf{A}],

where

(4.5) 𝐙k=diag​(𝐳,…,𝐳⏟k),𝐳=(z1,…,zm).\mathbf{Z}_{k}={\rm diag}(\underbrace{\mathbf{z},\ldots,\mathbf{z}}_{k}),\quad\mathbf{z}=(z_{1},\ldots,z_{m}).

We iteratively define the polynomials

(4.6) pt​(z1,…,zm):=∂ztk−1pt−1​(z1,…,zm),t=1,…,m.p_{t}(z_{1},\ldots,z_{m}):=\partial_{z_{t}}^{k-1}p_{t-1}(z_{1},\ldots,z_{m}),\quad t=1,\ldots,m.

We start with an initial point 𝐛0:=a​𝟏∈ℝm\mathbf{b}_{0}:=a\mathbf{1}\in\mathbb{R}^{m} with a>1a>1 that is above the roots of p0p_{0}. For each t∈[m]t\in[m], we aim to find a positive number δt\delta_{t} such that each entries of 𝐛m=𝐛0−∑t=1mδt​𝐞t∈𝐀𝐛p0\mathbf{b}_{m}=\mathbf{b}_{0}-\sum_{t=1}^{m}\delta_{t}\mathbf{e}_{t}\in\mathbf{Ab}_{p_{0}} less than or equal to 1k​(1−ϵk−1+ϵ)2\frac{1}{k}(\sqrt{1-\frac{\epsilon}{k-1}}+\sqrt{\epsilon})^{2}, which implies the result in Theorem 4.1.

We need the following result which depicts the behavior of barrier functions of polynomials affected by taking derivatives.

Proposition 4.5.

[RL20, Proposition 9, Proposition 10] Let j∈[m]j\in[m] be any integer. Assume that p​(z1,…,zm)p(z_{1},\ldots,z_{m}) is a real stable polynomial of degree kk in zjz_{j}. Let 𝐚=(a1,…,am)∈𝐀𝐛p\mathbf{a}=(a_{1},\ldots,a_{m})\in\mathbf{Ab}_{p} and let λk\lambda_{k} be the smallest root of the univariate polynomial q​(z):=p​(a1,⋯,aj−1,z,aj+1,⋯,am)q(z):=p(a_{1},\cdots,a_{j-1},z,a_{j+1},\cdots,a_{m}). Let

(4.7) δ=(k−1)2k​(1Φpj​(𝐚)−1aj−λk).\delta=\frac{(k-1)^{2}}{k}\bigg{(}\frac{1}{\Phi_{p}^{j}(\mathbf{a})-\frac{1}{a_{j}-\lambda_{k}}}\bigg{)}.

Then, we have 𝐚−δ⋅𝐞j∈𝐀𝐛∂zjk−1p\mathbf{a}-\delta\cdot\mathbf{e}_{j}\in\mathbf{Ab}_{\partial_{z_{j}}^{k-1}p} and

Φ∂zjk−1pi​(𝐚−δ⋅𝐞j)≤Φpi​(𝐚).\Phi_{\partial_{z_{j}}^{k-1}p}^{i}(\mathbf{a}-\delta\cdot\mathbf{e}_{j})\leq\Phi_{p}^{i}(\mathbf{a}).

We introduce a well-known result of the zeros of the real stable polynomials (see also [RL20, Proposition 8]).

Lemma 4.6.

[Tao13, Lemma 17] Let p​(z1,z2)p(z_{1},z_{2}) be a real stable polynomial of degree kk in z2z_{2}. For each (a,b)∈𝐀𝐛p(a,b)\in\mathbf{Ab}_{p}, denote the roots of the univariate polynomial qa​(z):=p​(a,z)q_{a}(z):=p(a,z) by λk​(a)≤⋯≤λ1​(a)\lambda_{k}(a)\leq\cdots\leq\lambda_{1}(a). Then for each j∈[k]j\in[k], the map a↦λj​(a)a\mapsto\lambda_{j}(a) defined on {a∈ℝ:(a,b)∈𝐀𝐛p​for some​b∈ℝ}\{a\in\mathbb{R}:(a,b)\in\mathbf{Ab}_{p}\,\,\text{for some}\,\,b\in\mathbb{R}\} is non-increasing.

The following lemma is useful for our analysis.

Lemma 4.7.

Let 𝐀∈ℂm×m\mathbf{A}\in\mathbb{C}^{m\times m} be a positive semidefinite Hermitian matrix. Set

(4.8) p​(z1,…,zm):=det[diag⁡(z1,…,zm)−𝐀].p(z_{1},\ldots,z_{m}):=\det[\operatorname{diag}(z_{1},\ldots,z_{m})-\mathbf{A}].

Assume that 𝐚=(a1,…,am)∈𝐀𝐛p\mathbf{a}=(a_{1},\ldots,a_{m})\in\mathbf{Ab}_{p}. Then, for each t∈[m]t\in[m], the smallest root of the univariate polynomial q​(z):=p​(z,…,z⏟t,at+1,…,am)q(z):=p(\underbrace{z,\ldots,z}_{t},a_{t+1},\ldots,a_{m}) is non-negative.

Proof.

We can write 𝐀\mathbf{A} in the form of (𝐏𝐐𝐐∗𝐒)\begin{pmatrix}\mathbf{P}&\mathbf{Q}\\ \mathbf{Q}^{*}&\mathbf{S}\end{pmatrix}, where 𝐏∈ℂt×t,𝐒∈ℂ(m−t)×(m−t)\mathbf{P}\in\mathbb{C}^{t\times t},\mathbf{S}\in\mathbb{C}^{(m-t)\times(m-t)} are both positive semidefinite Hermitian and 𝐐∈ℂt×(m−t)\mathbf{Q}\in\mathbb{C}^{t\times(m-t)}. Since 𝐚=(a1,…,am)∈𝐀𝐛p\mathbf{a}=(a_{1},\ldots,a_{m})\in\mathbf{Ab}_{p}, we obtain that diag​(a1,…,am)−𝐀{\rm diag}(a_{1},\ldots,a_{m})-\mathbf{A} is positive definite. Set 𝐃t:=diag​(at+1,…,am)\mathbf{D}_{t}:={\rm diag}(a_{t+1},\ldots,a_{m}). Noting that 𝐃t−𝐒∈ℂ(m−t)×(m−t)\mathbf{D}_{t}-\mathbf{S}\in\mathbb{C}^{(m-t)\times(m-t)} is a principal submatrix of diag​(a1,…,am)−𝐀{\rm diag}(a_{1},\ldots,a_{m})-\mathbf{A}, we obtain that 𝐃t−𝐒\mathbf{D}_{t}-\mathbf{S} is positive definite. We use the Schur complement to obtain that

q​(z)\displaystyle q(z) =det(z⋅𝐈t−𝐏−𝐐−𝐐∗𝐃t−𝐒)\displaystyle=\det\begin{pmatrix}z\cdot\mathbf{I}_{t}-\mathbf{P}&-\mathbf{Q}\\ -\mathbf{Q}^{*}&\mathbf{D}_{t}-\mathbf{S}\end{pmatrix}
=det(𝐃t−𝐒)​det(z⋅𝐈t−𝐏−𝐐​(𝐃t−𝐒)−1​𝐐∗).\displaystyle=\det(\mathbf{D}_{t}-\mathbf{S})\det\left(z\cdot\mathbf{I}_{t}-\mathbf{P}-\mathbf{Q}(\mathbf{D}_{t}-\mathbf{S})^{-1}\mathbf{Q}^{*}\right).

Hence, the roots of q​(z)q(z) are the eigenvalues of the positive semidefinite matrix 𝐏+𝐐​(𝐃t−𝐒)−1​𝐐∗∈ℂt×t\mathbf{P}+\mathbf{Q}(\mathbf{D}_{t}-\mathbf{S})^{-1}\mathbf{Q}^{*}\in\mathbb{C}^{t\times t}, which implies that all roots of q​(z)q(z) are non-negative. ∎

We next extend Lemma 4.7 to the polynomials that we will use in our proof of Theorem 4.1.

Proposition 4.8.

Let k,mk,m be two positive integers. Let 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km} be a positive semidefinite Hermitian matrix. Let p0​(z1,…,zm)p_{0}(z_{1},\ldots,z_{m}) be defined as in (4.4). Assume that 𝐚=(a1,…,am)∈𝐀𝐛p0\mathbf{a}=(a_{1},\ldots,a_{m})\in\mathbf{Ab}_{p_{0}}. For each t∈[m]t\in[m], let pt​(z1,…,zm)p_{t}(z_{1},\ldots,z_{m}) be defined as in (4.6). Set

qt​(z):=pt−1​(a1,…,at−1,z,at+1,…,am).q_{t}(z):=p_{t-1}(a_{1},\ldots,a_{t-1},z,a_{t+1},\ldots,a_{m}).

Then, for each t∈[m]t\in[m], the smallest root of qt​(z)q_{t}(z) is non-negative.

Proof.

By equation (3.15), we can write the univariate polynomial qt​(z)q_{t}(z) in the form of

qt​(z)=((k−1)!)(t−1)​∑𝒮=(S1,…,Sk)∈𝒫k​(t−1)g𝒮​(a1,…,at−1,z,at+1,…,an),q_{t}(z)=((k-1)!)^{(t-1)}\sum\limits_{\mathcal{S}=(S_{1},\ldots,S_{k})\in\mathcal{P}_{k}(t-1)}g_{\mathcal{S}}(a_{1},\ldots,a_{t-1},z,a_{t+1},\ldots,a_{n}),

where

g𝒮​(z1,…,zm):=det[(𝐙k−𝐀)​(𝒯t−1,𝒮)],g_{\mathcal{S}}(z_{1},\ldots,z_{m}):=\det[(\mathbf{Z}_{k}-\mathbf{A})(\mathcal{T}_{t-1,\mathcal{S}})],

and 𝒯t−1,𝒮\mathcal{T}_{t-1,\mathcal{S}} is defined in (3.14). Since 𝐚∈𝐀𝐛p0\mathbf{a}\in\mathbf{Ab}_{p_{0}}, we have

diag⁡(𝐚,…,𝐚)−𝐀≻𝟎,\operatorname{diag}(\mathbf{a},\ldots,\mathbf{a})-\mathbf{A}\succ\mathbf{0},

which implies that the principal matrix

(diag⁡(𝐚,…,𝐚)−𝐀)​(𝒯t−1,𝒮)≻𝟎.(\operatorname{diag}(\mathbf{a},\ldots,\mathbf{a})-\mathbf{A})(\mathcal{T}_{t-1,\mathcal{S}})\succ\mathbf{0}.

Then we obtain that 𝐚∈𝐀𝐛g𝒮\mathbf{a}\in\mathbf{Ab}_{g_{\mathcal{S}}}. Lemma 4.7 shows that the smallest root of the polynomial

g𝒮​(a1,…,at−1,z,at+1,…,an)∈ℝ​[z]g_{\mathcal{S}}(a_{1},\ldots,a_{t-1},z,a_{t+1},\ldots,a_{n})\in\mathbb{R}[z]

is non-negative. Since qt​(z)q_{t}(z) is a multiple of the sum of monic polynomials whose smallest root is non-negative, it follows that the smallest root of qt​(z)q_{t}(z) is non-negative. ∎

We need the following lemma to provide an estimate on the value of δt\delta_{t}.

Lemma 4.9.

Let k,mk,m be two positive integers. Let 𝐀∈ℂk​m×k​m\mathbf{A}\in\mathbb{C}^{km\times km} be a positive semidefinite Hermitian matrix satisfying 𝟎⪯𝐀⪯𝐈k​m\mathbf{0}\preceq\mathbf{A}\preceq\mathbf{I}_{km}. Set

ε:=max1≤i≤m​∑j=1k𝐀​(i+(j−1)​m,i+(j−1)​m).\varepsilon:=\max_{1\leq i\leq m}\sum_{j=1}^{k}\mathbf{A}(i+(j-1)m,i+(j-1)m).

Let p0​(z1,…,zm)p_{0}(z_{1},\ldots,z_{m}) be defined as in (4.4). Then for any a>1a>1 we have

Φp0i​(a​𝟏)≤εa−1+k−εafor all i∈[m].\Phi_{p_{0}}^{i}(a\mathbf{1})\leq\frac{\varepsilon}{a-1}+\frac{k-\varepsilon}{a}\quad\text{for all $i\in[m]$}.
Proof.

Define the polynomial

g​(z1,…,zk​m):=det[𝐙−𝐀],g(z_{1},\ldots,z_{km}):=\det[\mathbf{Z}-\mathbf{A}],

where

𝐙:=diag​(z1,…,zk​m).\mathbf{Z}:={\rm diag}(z_{1},\ldots,z_{km}).

By equation (3.8), for each i∈[m]i\in[m], we have

(4.9) Φp0i​(a​𝟏)=∂zip0p0​(a​𝟏)=∑j=1k∂zi+(j−1)​mgg|𝐙=a​𝐈k​m.\Phi_{p_{0}}^{i}(a\mathbf{1})=\frac{\partial_{z_{i}}p_{0}}{p_{0}}(a\mathbf{1})=\sum_{j=1}^{k}\frac{\partial_{z_{i+(j-1)m}}g}{g}\bigg{|}_{\mathbf{Z}=a\mathbf{I}_{km}}.

For each i∈[m],j∈[k]i\in[m],j\in[k], we have

∂zi+(j−1)​mdet[𝐙−𝐀]=det[(𝐙−𝐀)i+(j−1)​m],\partial_{z_{i+(j-1)m}}\det[\mathbf{Z}-\mathbf{A}]=\det[(\mathbf{Z}-\mathbf{A})_{i+(j-1)m}],

where (𝐙−𝐀)i+(j−1)​m(\mathbf{Z}-\mathbf{A})_{i+(j-1)m} denotes the principle submatrix of 𝐙−𝐀\mathbf{Z}-\mathbf{A} whose the (i+(j−1)​m)(i+(j-1)m)-th row and (i+(j−1)​m)(i+(j-1)m)-th column are deleted. By the expression of the inverse of a matrix, we obtain that

(4.10) (𝐙−𝐀)−1=1det[𝐙−𝐀]⋅adj⁡(𝐙−𝐀).(\mathbf{Z}-\mathbf{A})^{-1}=\frac{1}{\det[\mathbf{Z}-\mathbf{A}]}\cdot\operatorname{adj}(\mathbf{Z}-\mathbf{A}).

Taking the (i+(j−1)​m)(i+(j-1)m)-th diagonal element of each side of (4.10), we have

𝐞i+(j−1)​m∗​(𝐙−𝐀)−1​𝐞i+(j−1)​m=1det[𝐙−𝐀]⋅det[(𝐙−𝐀)i+(j−1)​m]\mathbf{e}_{i+(j-1)m}^{*}(\mathbf{Z}-\mathbf{A})^{-1}\mathbf{e}_{i+(j-1)m}=\frac{1}{\det[\mathbf{Z}-\mathbf{A}]}\cdot\det[(\mathbf{Z}-\mathbf{A})_{i+(j-1)m}]

Then for each i∈[m],j∈[k]i\in[m],j\in[k], we have

(4.11) ∂zi+(j−1)​mgg=∂zi+(j−1)​mdet[𝐙−𝐀]det[𝐙−𝐀]=𝐞i+(j−1)​m∗​(𝐙−𝐀)−1​𝐞i+(j−1)​m.\frac{\partial_{z_{i+(j-1)m}}g}{g}=\frac{\partial_{z_{i+(j-1)m}}\det[\mathbf{Z}-\mathbf{A}]}{\det[\mathbf{Z}-\mathbf{A}]}=\mathbf{e}_{i+(j-1)m}^{*}(\mathbf{Z}-\mathbf{A})^{-1}\mathbf{e}_{i+(j-1)m}.

Combining (4.9) and (4.11), we obtain that

Φp0i​(a​𝟏)=∑j=1k𝐞i+(j−1)​m∗​(a​𝐈k​m−𝐀)−1​𝐞i+(j−1)​m.\Phi_{p_{0}}^{i}(a\mathbf{1})=\sum\limits_{j=1}^{k}\mathbf{e}_{i+(j-1)m}^{*}(a\mathbf{I}_{km}-\mathbf{A})^{-1}\mathbf{e}_{i+(j-1)m}.

Suppose that the spectral decomposition of 𝐀\mathbf{A} is

(4.12) 𝐀=𝐔𝐃𝐔∗,\mathbf{A}=\mathbf{U}\mathbf{D}\mathbf{U}^{*},

where 𝐔∈ℂk​m×k​m\mathbf{U}\in\mathbb{C}^{km\times km} is a unitary matrix and 𝐃=diag​(λ1,…,λk​m)\mathbf{D}={\rm diag}(\lambda_{1},\ldots,\lambda_{km}) is a diagonal matrix of eigenvalues of 𝐀\mathbf{A}. It follows that (a​𝐈k​m−𝐀)−1=𝐔​(a​𝐈k​m−𝐃)−1​𝐔∗(a\mathbf{I}_{km}-\mathbf{A})^{-1}=\mathbf{U}(a\mathbf{I}_{km}-\mathbf{D})^{-1}\mathbf{U}^{*}. Thus we have

(4.13) Φp0i​(a​𝟏)\displaystyle\Phi_{p_{0}}^{i}(a\mathbf{1}) =∑j=1k𝐞i+(j−1)​m∗​𝐔​(a​𝐈k​m−𝐃)−1​𝐔∗​𝐞i+(j−1)​m\displaystyle=\sum\limits_{j=1}^{k}\mathbf{e}_{i+(j-1)m}^{*}\mathbf{U}(a\mathbf{I}_{km}-\mathbf{D})^{-1}\mathbf{U}^{*}\mathbf{e}_{i+(j-1)m}
=∑j=1k∑l=1k​m|𝐔​(i+(j−1)​m,l)|2a−λl.\displaystyle=\sum\limits_{j=1}^{k}\sum\limits_{l=1}^{km}\frac{|\mathbf{U}(i+(j-1)m,l)|^{2}}{a-\lambda_{l}}.

Set cl:=∑j=1k|𝐔​(i+(j−1)​m,l)|2c_{l}:=\sum\limits_{j=1}^{k}|\mathbf{U}(i+(j-1)m,l)|^{2} for each l∈[k​m]l\in[km]. Then we have

(4.14) Φp0i​(a​𝟏)=∑l=1k​mcla−λl\displaystyle\Phi_{p_{0}}^{i}(a\mathbf{1})=\sum\limits_{l=1}^{km}\frac{c_{l}}{a-\lambda_{l}} ≤∑l=1k​m(cl⋅λla−1+cl⋅(1−λl)a)\displaystyle\leq\sum\limits_{l=1}^{km}\bigg{(}\frac{c_{l}\cdot\lambda_{l}}{a-1}+\frac{c_{l}\cdot(1-\lambda_{l})}{a}\bigg{)}
=(1a−1−1a)⋅∑l=1k​mλl​cl+1a⋅∑l=1k​mcl.\displaystyle=\bigg{(}\frac{1}{a-1}-\frac{1}{a}\bigg{)}\cdot\sum\limits_{l=1}^{km}\lambda_{l}c_{l}+\frac{1}{a}\cdot\sum\limits_{l=1}^{km}c_{l}.

Here, we use the following inequality:

1a−λl≤λla−1+1−λla,\frac{1}{a-\lambda_{l}}\leq\frac{\lambda_{l}}{a-1}+\frac{1-\lambda_{l}}{a},

where a>1a>1 and λl∈[0,1]\lambda_{l}\in[0,1]. Note that

(4.15) ∑l=1k​mcl=∑j=1k∑l=1k​m|𝐔​(i+(j−1)​m,l)|2=∑j=1k1=k,\sum_{l=1}^{km}c_{l}=\sum_{j=1}^{k}\sum_{l=1}^{km}|\mathbf{U}(i+(j-1)m,l)|^{2}=\sum_{j=1}^{k}1=k,

since each column of 𝐔\mathbf{U} is a unit vector. We use (4.12) to obtain that

𝐀​(i+(j−1)​m,i+(j−1)​m)=∑l=1k​mλl​|𝐔​(i+(j−1)​m,l)|2.\mathbf{A}(i+(j-1)m,i+(j-1)m)=\sum_{l=1}^{km}\lambda_{l}|\mathbf{U}(i+(j-1)m,l)|^{2}.

Then we have

(4.16) ∑l=1k​mλl​cl\displaystyle\sum_{l=1}^{km}\lambda_{l}c_{l} =∑j=1k∑l=1k​mλl​|𝐔​(i+(j−1)​m,l)|2\displaystyle=\sum_{j=1}^{k}\sum_{l=1}^{km}\lambda_{l}|\mathbf{U}(i+(j-1)m,l)|^{2}
=∑j=1k𝐀​(i+(j−1)​m,i+(j−1)​m)\displaystyle=\sum_{j=1}^{k}\mathbf{A}(i+(j-1)m,i+(j-1)m)
≤ε.\displaystyle\leq\varepsilon.

Thus, combining (4.14), (4.15) and (4.16), we obtain that

Φp0i​(a​𝟏)≤ε⋅(1a−1−1a)+ka=εa−1+k−εa.\Phi_{p_{0}}^{i}(a\mathbf{1})\leq\varepsilon\cdot\bigg{(}\frac{1}{a-1}-\frac{1}{a}\bigg{)}+\frac{k}{a}=\frac{\varepsilon}{a-1}+\frac{k-\varepsilon}{a}.

∎

Now we have all the materials to prove Theorem 4.1.

Proof of Theorem 4.1.

Suppose that a>1a>1 is a constant which is chosen later. Set 𝐛0=a​𝟏∈ℝm\mathbf{b}_{0}=a\mathbf{1}\in{\mathbb{R}}^{m}. Let p0​(z1,…,zm)p_{0}(z_{1},\ldots,z_{m}) be defined as in (4.4). According to 𝐀⪯𝐈k​m\mathbf{A}\preceq\mathbf{I}_{km}, we obtain that 𝐛0\mathbf{b}_{0} is above the roots of p0p_{0} . Recall that

pt=∂ztk−1pt−1,t=1,…,m.p_{t}=\partial_{z_{t}}^{k-1}p_{t-1},\quad t=1,\ldots,m.

A simple observation is that

ψk,m​[𝐀]​(x)=1(k!)m⋅pm​(z1,…,zm)|z1=⋯=zm=x.\psi_{k,m}[\mathbf{A}](x)=\frac{1}{(k!)^{m}}\cdot p_{m}(z_{1},\ldots,z_{m})|_{z_{1}=\cdots=z_{m}=x}.

Hence, to prove the conclusion, it is enough to show that 1k​(1−εk−1+ε)2⋅𝟏\frac{1}{k}\big{(}\sqrt{1-\frac{\varepsilon}{k-1}}+\sqrt{\varepsilon}\big{)}^{2}\cdot\mathbf{1} is above the roots of pmp_{m}. For each t∈[m]t\in[m], set

δt:=(k−1)2k​(1Φpt−1t​(𝐛t−1)−1a−λk(t)),\delta_{t}:=\frac{(k-1)^{2}}{k}\bigg{(}\frac{1}{\Phi_{p_{t-1}}^{t}(\mathbf{b}_{t-1})-\frac{1}{a-\lambda_{k}^{(t)}}}\bigg{)},

where

𝐛t:=𝐛0−∑j=1tδj​𝐞j=(a−δ1,…,a−δt,a,…,a).\mathbf{b}_{t}:=\mathbf{b}_{0}-\sum_{j=1}^{t}\delta_{j}{\mathbf{e}}_{j}=(a-\delta_{1},\ldots,a-\delta_{t},a,\ldots,a).

Let λk(t)\lambda_{k}^{(t)} be the smallest root of the univariate polynomial

(4.17) qt​(z):=pt−1​(a−δ1,…,a−δt−1,z,a,…,a).q_{t}(z):=p_{t-1}(a-\delta_{1},\ldots,a-\delta_{t-1},z,a,\ldots,a).

By Proposition 4.5 , we have 𝐛t∈𝐀𝐛pt\mathbf{b}_{t}\in\mathbf{Ab}_{p_{t}} and

(4.18) Φpti​(𝐛t)≤Φpt−1i​(𝐛t−1)for all t∈[m] and i∈[m].\Phi_{p_{t}}^{i}(\mathbf{b}_{t})\leq\Phi_{p_{t-1}}^{i}(\mathbf{b}_{t-1})\quad\text{for all $t\in[m]$ and $i\in[m]$}.

we claim that

(4.19) maxt∈[m]​infa>1(a−δt)≤1k​(1−εk−1+ε)2.\max_{t\in[m]}\inf_{a>1}(a-\delta_{t})\leq\frac{1}{k}\bigg{(}\sqrt{1-\frac{\varepsilon}{k-1}}+\sqrt{\varepsilon}\bigg{)}^{2}.

Noting that 𝐛m=a​𝟏−∑t=1mδt⋅𝐞t\mathbf{b}_{m}=a\mathbf{1}-\sum\limits_{t=1}^{m}\delta_{t}\cdot\mathbf{e}_{t} is above the roots of pmp_{m}, we can use (4.19) to obtain the conclusion.

It remains to prove (4.19). We first show that λk(t)≥0\lambda_{k}^{(t)}\geq 0 for each t∈[m]t\in[m]. For each t∈[m]t\in[m] we define the univariate polynomial

(4.20) gt​(z):=pt−1​(a,…,a⏟t−1,z,a,…,a).g_{t}(z):=p_{t-1}\left(\underbrace{a,\ldots,a}_{t-1},z,a,\ldots,a\right).

Since 𝐚\mathbf{a} and 𝐛t−1=𝐚−∑i=1t−1δi⋅𝐞i∈𝐀𝐛pt−1\mathbf{b}_{t-1}=\mathbf{a}-\sum\limits_{i=1}^{t-1}\delta_{i}\cdot\mathbf{e}_{i}\in\mathbf{Ab}_{p_{t-1}}, we obtain that

(4.21) λk(t)=minroot​qt≥minroot​gt≥0,\lambda_{k}^{(t)}=\text{minroot}\ q_{t}\geq\text{minroot}\ g_{t}\geq 0,

where the first inequality follows from Lemma 4.6 and the second inequality follows from Proposition 4.8. Then, combining (4.21), (4.18) and Lemma 4.9, for each t∈[m]t\in[m], we have

δt\displaystyle\delta_{t} ≥(k−1)2k​(1Φpt−1t​(𝐛t−1)−1a)\displaystyle\geq\frac{(k-1)^{2}}{k}\bigg{(}\frac{1}{\Phi_{p_{t-1}}^{t}(\mathbf{b}_{t-1})-\frac{1}{a}}\bigg{)}
≥(k−1)2k​(1Φp0t​(𝐛0)−1a)\displaystyle\geq\frac{(k-1)^{2}}{k}\bigg{(}\frac{1}{\Phi_{p_{0}}^{t}(\mathbf{b}_{0})-\frac{1}{a}}\bigg{)}
≥(k−1)2k​(1εa−1+k−εa−1a).\displaystyle\geq\frac{(k-1)^{2}}{k}\bigg{(}\frac{1}{\frac{\varepsilon}{a-1}+\frac{k-\varepsilon}{a}-\frac{1}{a}}\bigg{)}.

So, for each t∈[m]t\in[m], we have

(4.22) infa>1(a−δt)≤infa>1(a−(k−1)2k​(1εa−1+k−εa−1a)).\inf\limits_{a>1}(a-\delta_{t})\,\,\leq\,\,\inf\limits_{a>1}\bigg{(}a-\frac{(k-1)^{2}}{k}\bigg{(}\frac{1}{\frac{\varepsilon}{a-1}+\frac{k-\varepsilon}{a}-\frac{1}{a}}\bigg{)}\bigg{)}.

Set α:=a−(1−εk−1)>0\alpha:=a-(1-\frac{\varepsilon}{k-1})>0. A simple calculation shows that

a−(k−1)2k​(1εa−1+k−εa−1a)\displaystyle a-\frac{(k-1)^{2}}{k}\bigg{(}\frac{1}{\frac{\varepsilon}{a-1}+\frac{k-\varepsilon}{a}-\frac{1}{a}}\bigg{)} =1k⋅(α+(1−εk−1)​εα+(1−εk−1)+ε)\displaystyle=\frac{1}{k}\cdot\bigg{(}\alpha+\frac{(1-\frac{\varepsilon}{k-1})\varepsilon}{\alpha}+(1-\frac{\varepsilon}{k-1})+\varepsilon\bigg{)}
≥1k⋅(2​(1−εk−1)​ε+(1−εk−1)+ε)\displaystyle\geq\frac{1}{k}\cdot\bigg{(}2\sqrt{(1-\frac{\varepsilon}{k-1})\varepsilon}+(1-\frac{\varepsilon}{k-1})+\varepsilon\bigg{)}
=1k⋅(1−εk−1+ε)2,\displaystyle=\frac{1}{k}\cdot\bigg{(}\sqrt{1-\frac{\varepsilon}{k-1}}+\sqrt{\varepsilon}\bigg{)}^{2},

where the equality holds if and only if α=(1−εk−1)​ε\alpha=\sqrt{(1-\frac{\varepsilon}{k-1})\varepsilon}, i.e.,

a=a0:=(1−εk−1)​ε+(1−εk−1).a=a_{0}:=\sqrt{(1-\frac{\varepsilon}{k-1})\varepsilon}+(1-\frac{\varepsilon}{k-1}).

This implies that if a0≥1a_{0}\geq 1, i.e., ε≤(k−1)2/k\varepsilon\leq(k-1)^{2}/k, then

(4.23) infa>1(a−(k−1)2k​(1εa−1+k−εa−1a))=1k⋅(1−εk−1+ε)2.\inf\limits_{a>1}\bigg{(}a-\frac{(k-1)^{2}}{k}\bigg{(}\frac{1}{\frac{\varepsilon}{a-1}+\frac{k-\varepsilon}{a}-\frac{1}{a}}\bigg{)}\bigg{)}=\frac{1}{k}\cdot\bigg{(}\sqrt{1-\frac{\varepsilon}{k-1}}+\sqrt{\varepsilon}\bigg{)}^{2}.

Combing (4.22) and (4.23), we arrive at (4.19). ∎

5. Proof of Theorem 1.4

Following [Coh16] and [Bra¨{\rm\ddot{a}}18, Theorem 6.1], we now prove Theorem 1.4 by employing Theorem 1.9.

Proof of Theorem 1.4.

For each i∈[m]i\in[m], let Wi:={𝐖i,1,…,𝐖i,li}W_{i}:=\{\mathbf{W}_{i,1},\ldots,\mathbf{W}_{i,l_{i}}\} be the support of 𝐖i\mathbf{W}_{i}. By Lemma 2.8, we see that the polynomials

μ​[𝐖1,j1,…,𝐖m,jm]​(x),ji∈[li],i=1,…,m\mu[\mathbf{W}_{1,j_{1}},\ldots,\mathbf{W}_{m,j_{m}}](x),\,j_{i}\in[l_{i}],i=1,\ldots,m

form an interlacing family. Then Lemma 2.3 implies that there exists j1∈[l1],…,jm∈[lm]j_{1}\in[l_{1}],\ldots,j_{m}\in[l_{m}] such that

(5.1) maxroot⁡μ​[𝐖1,j1,…,𝐖m,jm]≤maxroot⁡𝔼​μ​[𝐖1,…,𝐖m].\operatorname{maxroot}\ \mu[\mathbf{W}_{1,j_{1}},\ldots,\mathbf{W}_{m,j_{m}}]\leq\operatorname{maxroot}\ \mathbb{E}\ \mu[\mathbf{W}_{1},\ldots,\mathbf{W}_{m}].

Combining (2.5) and (5.1), we obtain that

(5.2) maxroot⁡μ​[𝐖1,j1,…,𝐖m,jm]≤maxroot⁡μ​[𝔼​𝐖1,…,𝔼​𝐖m].\operatorname{maxroot}\ \mu[\mathbf{W}_{1,j_{1}},\ldots,\mathbf{W}_{m,j_{m}}]\leq\operatorname{maxroot}\ \mu[\mathbb{E}\mathbf{W}_{1},\ldots,\mathbb{E}\mathbf{W}_{m}].

Since

tr⁡(𝔼​𝐖i)≤ε,rank⁡(𝔼​𝐖i)≤kfor all i∈[m],\operatorname{tr}(\mathbb{E}\mathbf{W}_{i})\leq\varepsilon,\quad\,\operatorname{rank}(\mathbb{E}\mathbf{W}_{i})\leq k\quad\text{for all $i\in[m]$},

and ∑i=1m𝔼​𝐖i=𝐈d\sum_{i=1}^{m}\mathbb{E}\mathbf{W}_{i}=\mathbf{I}_{d}, Theorem 1.9 gives

maxroot⁡μ​[𝔼​𝐖1,…,𝔼​𝐖m]≤(1−εk−1+ε)2.\operatorname{maxroot}\ \mu[\mathbb{E}\mathbf{W}_{1},\ldots,\mathbb{E}\mathbf{W}_{m}]\leq\bigg{(}\sqrt{1-\frac{\varepsilon}{k-1}}+\sqrt{\varepsilon}\bigg{)}^{2}.

Finally, combining Lemma 2.7 and (5.2) we arrive at

‖∑i=1m𝐖i,ji‖≤maxroot⁡μ​[𝐖1,j1,…,𝐖m,jm]≤(1−εk−1+ε)2.\bigg{\|}\sum_{i=1}^{m}\mathbf{W}_{i,j_{i}}\bigg{\|}\leq\operatorname{maxroot}\ \mu[\mathbf{W}_{1,j_{1}},\ldots,\mathbf{W}_{m,j_{m}}]\leq\bigg{(}\sqrt{1-\frac{\varepsilon}{k-1}}+\sqrt{\varepsilon}\bigg{)}^{2}.

This implies the desired conclusion.

∎

References

  • [AB20] K. Alishahi and M. Barzegar, Paving property for real stable polynomials and strongly rayleigh processes, arXiv preprint arXiv:2006.13923, 2020.
  • [And79] J. Anderson, Extensions, restrictions, and representations of states on C∗C^{*}-algebras, Trans. Amer. Math. Soc., 249 (1979), 303-329. MR 0525675. Zbl 0408. 46049. http://dx.doi.org/10.2307/1998793.
  • [And79] J. Anderson, Extreme points in sets of positive linear maps on ℬ​(ℋ)\mathcal{B}(\mathcal{H}), J. Funct. Anal., 31 (1979), 195-217. MR 0525951. Zbl 0422.46049. http://dx.doi.org/10. 1016/0022-1236(79)90061-2.
  • [And81] J. Anderson, A conjecture concerning the pure states of ℬ​(ℋ)\mathcal{B}(\mathcal{H}) and a related theorem, in Topics in Modern Operator Theory (Timisoara/Herculane, 1980), Operator Theory: Adv. Appl. 2, Birkha¨{\rm\ddot{a}}user, Boston, 1981, pp. 27-43. MR 0672813. Zbl 0455.47026.
  • [BSS12] J. Batson, D. A. Spielman, and N. Srivastava, Twice-Ramanujan sparsifiers, SIAM J. Comput. 41 (2012), 1704-1721. MR 3029269. Zbl 1260.05092. http: //dx.doi.org/10.1137/090772873.
  • [BB08] J. Borcea and P. Brändén Applications of stable polynomials to mixed determinants: Johnson’s conjectures, unimodality, and symmetrized Fischer products, Duke Math. J. 143 (2008), 205-223. MR 2420507. Zbl 1151.15013. http://dx.doi.org/10.1215/00127094-2008-018.
  • [BB10] J. Borcea and P. Brändén, Multivariate Pólya-Schur classification problems in the Weyl algebra, Proceedings of the London Mathematical Society, 101(1):73-104, 2010.
  • [BT89] J. Bourgain and L. Tzafriri, Restricted invertibility of matrices and applications, in Analysis at Urbana, Vol. II (Urbana, IL, 1986-1987), London Math. Soc. Lecture Note Ser. 138, Cambridge Univ. Press, Cambridge, (1989), pp. 61-107. MR 1009186. Zbl 0698.47018. http://dx.doi.org/10.1017/CBO9781107360204.006.
  • [BCMS19] M. Bownik, P. Casazza, A. Marcus and D. Speelge Improved bounds in Weaver and Feichtinger conjectures, Journal für die reine und angewandte Mathematik (2019), 749:267-293
  • [BS06] M. Bownik and D. Speegle, The Feichtinger conjecture for wavelet frames, Gabor frames and frames of translates, Canad. J. Math. 58 (2006), no. 6, 1121-1143.
  • [Bra¨{\rm\ddot{a}}11] P. Brändén Obstructions to determinantal representability. Advances in Mathematics, 226(2):1202-1212, 2011.
  • [Bra¨{\rm\ddot{a}}18] P. Brändén Hyperbolic polynomials and the Kadison-Singer problem, In arXiv preprint. https://arxiv.org/pdf/1809.03255, 2018.
  • [CCLV05] P. Casazza, O. Christensen, A. Lindner and R. Vershynin, Frames and the Feichtinger conjecture, Proc. Amer. Math. Soc. 133 (2005), no. 4, 1025-1033.
  • [CT06] P. G. Casazza and J. C. Tremain, The Kadison-Singer problem in mathematics and engineering, Proc. Natl. Acad. Sci. USA 103, (2006), 2032-2039. MR 2204073. Zbl 1160.46333. http://dx.doi.org/10.1073/pnas.0507888103.
  • [Coh16] M. Cohen, Improved Spectral Sparsification and Kadison-Singer for Sums of Higher-rank Matrices, 2016, from http://www.birs.ca/events/2016/5-day-workshops/16w5111/videos/watch/201608011534-Cohen.html.
  • [FY19] O. Friedland and P. Youssef. Approximating matrices and convex bodies, International Mathematics Research Notices, 2019(8):2519–2537, 2019.
  • [Gro¨{\rm\ddot{o}}03] K. Gro¨{\rm\ddot{o}}chenig, Localized frames are finite unions of Riesz sequences, Adv. Comput. Math. 18 (2003), no. 2-4, 149-157.
  • [KS59] R. V. Kadison and I. M. Singer, Extensions of pure states, Amer. J. Math., 81 (1959), 383-400. MR 0123922. Zbl 0086.09704. http://dx.doi.org/10.2307/ 2372748.
  • [LPR05] A. Lewis, P. Parrilo, and M. Ramana. The lax conjecture is true. Proceedings of the American Mathematical Society, 133(9): 2495-2499, 2005.
  • [MSS15a] A. Marcus, D. A. Spielman, and N. Srivastava, Interlacing families I: Bipartite Ramanujan graphs of all degrees, Ann. of Math. 182 (2015), 307-325. http://dx.doi.org/10.4007/2015.182.1.7.
  • [MSS15b] A. Marcus, D. A. Spielman, and N. Srivastava, Interlacing families II: mixed characteristic polynomials and the Kadison-Singer problem, Ann. of Math. (2) 182, no. 1 (2015): 327-350.
  • [MSS17] A. W. Marcus, D. A. Spielman, and N. Srivastava, Interlacing Families III: Sharper restricted invertibility estimates, arXiv: 1712.07766, 2017, to appear in Israel J. Math.
  • [MSS18] A. W. Marcus, D. A. Spielman, and N. Srivastava, Interlacing families IV: Bipartite ramanujan graphs of all sizes, SIAM Journal on Computing, 47(6): 2488-2509, 2018.
  • [Rav20] M. Ravichandran, Principal submatrices, restricted invertibility and a quantitative Gauss-Lucas theorem, International Mathematics Research Notices, Volume 2020, Issue 15, August 2020, Pages 4809-4832, https://doi.org/10.1093/imrn/rny163.
  • [RL20] M. Ravichandran and J. Leake, Mixed determinants and the Kadison-Singer problem., Mathematische Annalen (2020) 377:511-541 https://doi.org/10.1007/s00208-020-01986-7
  • [RS19] M. Ravichandran and N. Srivastava, Asymptotically Optimal Multi-Paving, International Mathematics Research Notices, (2019) Vol. 00, No. 0, pp. 1-33 doi:10.1093/imrn/rnz111
  • [Tao13] T.Tao, Real stable polynomials and the Kadison-Singer problem, 2013, from https://terrytao.wordpress.com/2013/11/04/real-stable-polynomials-and-the-kadison-singer-problem/#more-7109.
  • [Wag11] D. Wagner, Multivariate stable polynomials: theory and applications. Bulletin of the American Mathematical Society, 48(1):53-84, January 2011.
  • [Wea04] N. Weaver, The Kadison-Singer problem in discrepancy theory, Discrete Math. 278 (2004), 227-239. MR 2035401. Zbl 1040.46040. http://dx.doi.org/10.1016/ S0012-365X(03)00253-X.