An inequality for the spectral radius of block matrices

Question

Let $d,m$ be positive integers. Suppose that $A_{i,j}$ is a $d\times d$-matrix with real entries whenever $i,j\in\{1,\dots m\}$.

Let $A$ be the $dm\times dm$ matrix that can be written as a block matrix as $$A=\begin{bmatrix} A_{1,1} & \cdots & A_{1,m} \\ \vdots & \ddots & \vdots \\ A_{m,1} & \dots & A_{m,m} \end{bmatrix}.$$

1. Is $$\rho(A)^2\leq\min(d,m)\cdot \rho\left(\sum_{i,j}A_{i,j}\otimes A_{i,j}\right)?$$

2. For all $d,m$, can we select real matrices $A_{i,j}$ so that $$\rho(A)^2=\min(d,m)\cdot \rho\left(\sum_{i,j}A_{i,j}\otimes A_{i,j}\right)>0?$$

3. If $$\rho(A)^2=\min(d,m)\cdot \rho\left(\sum_{i,j}A_{i,j}\otimes A_{i,j}\right)>0,$$ and $d\leq m$ then is $\text{Rank}(A_{i,j})\leq 1$ for each $i,j$?

My computer calculations suggest that the answer to these questions is 'yes'. This is a follow up of this question. This question can be generalized to the case when each $A_{i,j}$ is a complex matrix. One can rephrase the complex version of this question in terms of the completely depolarizing channel in quantum information theory.

Answer 1

I'll answer #1 only, leaving the rest to you or someone else to figure out. The answer is affirmative.

Dropping the trivial case $m=1$, we may assume by density that we are in the generic position, i.e., that $A_{ij}^T\ne 0$ and together have no non-trivial invariant subspace (this is just to avoid considering degenerate cases, which can also be done using dimension reduction but I prefer not to bother with this extra technicality).

Consider the mapping $X\mapsto F(X)=\sum_{i,j}A_{ij}XA_{ij}^T$ on the cone $K$ of symmetric non-negative definite $d\times d$ matrices $X$. Notice that if $X\ne 0$ and $F(X)=0$, then all $A_{ij}^T$ map the entire space to the kernel of $X$, which contradicts our generic position assumption. Thus the mapping $X\mapsto \frac 1{\operatorname{Tr}F(X)}F(X)$ is well-defined on the convex compact $Q=K\cap\{X:\operatorname{Tr}X=1\}$ and maps $Q$ to itself. So, by the Brouwer fixed point theorem, the linear mapping $F$ has an eigenvector in the cone with positive eigenvalue, which we can normalize to $1$ by scaling $A$, i.e., we have $$ \sum_{i,j}A_{ij}XA_{ij}^T=X\,, $$ which, clearly, implies $\rho(\sum_{i,j}A_{ij}\otimes A_{ij})\ge 1$.

I now claim that $X$ is non-degenerate. Indeed, otherwise the kernel of $X$ would be non-trivial and invariant under all $A_{ij}^T$.

Now for a vector $y=(y_1,\dots,y_m)\in\mathbb R^{md}$ define its norm by $$ \|y\|^2=\sum_j|X^{-1/2}y_j|^2 $$ where $|\cdot|$ stands for the usual Euclidean norm in $\mathbb R^d$. Let $y$ be a unit vector (in this norm) on which the induced operator norm of $A$ is attained.

Then $\|Ay\|^2=\sum_{i} \langle X^{-1/2}(Ay)_i,\xi_i\rangle^2$ for some unit vectors $\xi_i\in\mathbb R^d$. Now use Cauchy-Schwarz: $$ \langle X^{-1/2}(Ay)_i,\xi_i\rangle^2= \left[\sum_j \langle X^{-1/2}A_{ij}y_j,\xi_i\rangle\right]^2 \\ = \left[\sum_j \langle X^{-1/2}y_j,X^{1/2}A_{ij}^TX^{-1/2}\xi_i\rangle\right]^2 \\ \le \left[\sum_j |X^{-1/2}y_j|^2\right]\left[\sum_j |X^{1/2}A_{ij}^TX^{-1/2}\xi_i|^2\right] $$ This allows one to estimate the induced operator norm of $A$ and, thereby $\rho(A)$ by $$ \rho(A)^2\le\|A\|^2\le \sum_{i,j}|X^{1/2}A_{ij}^TX^{-1/2}\xi_i|^2 \\ =\sum_{i,j}\langle X^{-1/2}A_{ij}XA_{ij}^TX^{-1/2}\xi_i,\xi_i\rangle\,. $$ Now let $L$ be the linear subspace of $\mathbb R^d$ spanned by all vectors $\xi_i$. Obviously, $\operatorname{dim}L\le\min(d,m)$. Let $P$ be the orthogonal projection to $L$. Then for every non-negative definite operator $S$ in $\mathbb R^d$, we have $\langle S\xi_i,\xi_i\rangle\le\operatorname{Tr} (PSP)$, which yields the bound $$ \sum_{i,j} \operatorname{Tr}(PX^{-1/2}A_{ij}XA_{ij}^TX^{-1/2}P) = \operatorname{Tr}\left(\sum_{i,j} PX^{-1/2}A_{ij}XA_{ij}^TX^{-1/2}P\right) \\ = \operatorname{Tr}\left(PX^{-1/2}\left[\sum_{i,j} A_{ij}XA_{ij}^T\right]X^{-1/2}P\right)= \operatorname{Tr}(PX^{-1/2}XX^{-1/2}P) \\ =\operatorname{Tr} P=\operatorname{dim}L\le\min(d,m) $$ as required.

Answer 2

The answer to all three questions is Yes.

#2 This part is easy. If $i>d$ or $j>d$, then set $A_{i,j}=0_{d\times d}$, and if $i\leq d$ and $j\leq d$, then let $A_{i,j}$ be the $d\times d$-matrix where the $i,j$-th entry is $1$ but every other entry is zero. Then $\rho(A)^2=\min(m,d)\cdot\rho(\sum_{i,j}A_{i,j}\otimes A_{i,j})$. Therefore, this inequality is sharp.

#1 and #3

For generality and to put this answer in the context of quantum information theory, let me answer in the case when each $A_{i,j}$ is a complex matrix (we have to modify the statements of 1,2,3 though). We will only answer this question in the case when $d\leq m$ since fedja's answer already answers #1 for all real cases.

For this answer, we shall hold to the convention that if $A$ is a $dm\times dm$-matrix, then $(A_{i,j})_{i,j}$ are the submatrices of $A$ such that $A$ becomes a block matrix with blocks $A_{i,j}\in M_{d}(\mathbb{C})$ whenever $1\leq i\leq m,1\leq j\leq m$.

Let $L(\mathbb{C}^d)$ denote the collection of all linear operators $A:\mathbb{C}^d\rightarrow\mathbb{C}^d$. Suppose that $\mathcal{E}:L(\mathbb{C}^d)\rightarrow L(\mathbb{C}^d)$ is a linear operator. Then $\mathcal{E}$ is said to be trace preserving if $\text{Tr}(\mathcal{E}(A))=\text{Tr}(A).$ We say that $\mathcal{E}$ is positive if $\mathcal{E}(A)$ is positive semidefinite whenever $A$ is positive semidefinite. We say that $\mathcal{E}$ is completely positive if whenever $V$ is a finite dimensional complex Hilbert space, we have $\mathcal{E}\otimes 1_{L(V)}:L(\mathbb{C}^{d}\otimes V)\rightarrow L(\mathbb{C}^{d}\otimes V)$. We say that $\mathcal{E}$ is a quantum channel if $\mathcal{E}$ is completely positive and trace preserving.

The mapping $\mathcal{E}$ is completely positive if and only if there are $A_1,\dots,A_r$ with $\mathcal{E}(X)=A_1XA_1^*+\dots+A_rXA_r^*$ for each $X\in L(\mathbb{C}^d)$. The mapping $\mathcal{E}$ is a quantum channel if and only if there are $A_1,\dots,A_r$ with $\mathcal{E}(X)=A_1XA_1^*+\dots+A_rXA_r^*$ for each $X\in L(\mathbb{C}^d)$ and $A_1^*A_1+\dots+A_r^*A_r=1_{d}$. Observe that if $\mathcal{E}$ is a quantum channel, then $\rho(\mathcal{E})=1$.

If $A_{i,j}$ is an $d\times d$-matrix whenever $1\leq i\leq m$ and $1\leq j\leq m$, then define a superoperator $\Phi((A_{i,j})_{i,j}):L(\mathbb{C}^d)\rightarrow L(\mathbb{C}^d)$ by letting $\Phi((A_{i,j})_{i,j})(X)=\sum_{i,j}A_{i,j}XA_{i,j}^*$. When we generalize #1 to complex matrices, this statement becomes $\rho(A)^2\leq\min(d,m)\rho(\Phi((A_{i,j})_{i,j})$. #3 when generalized states that if $\rho(A)^2=d\cdot\rho(\Phi((A_{i,j})_{i,j})$ and $d\leq m$, then $\text{Rank}(A_{i,j})=1$ for each $i,j$.

Let $O$ be the collection of all systems $(A_{i,j})_{i,j}\in M_d(\mathbb{C})^{m\times m}$ where $\Phi((A_{i,j})_{i,j})$ is not nilpotent. Let $E$ be the collection of all systems $(A_{i,j})_{i,j}\in M_d(\mathbb{C})^{m\times m}$ where there is some $\lambda>0$ and $B$ where $\Phi((\lambda BA_{i,j}B^{-1})_{i,j})$ is a quantum channel. By the arguments that I gave in this answer, the set $E$ is dense in $L(\mathbb{C}^{d})^{m\times m}$. Let $E^{\uparrow}$ (respectively $O^{\uparrow}$) be the collection of all matrices $A\in M_{md}(\mathbb{C})$ where $(A_{i,j})_{i,j}\in E$ (respectively $(A_{i,j})_{i,j}\in O$).

Suppose that $\Phi((A_{i,j})_{i,j})$ is a quantum channel. Then

$$d=\text{Tr}(1_d)=\text{Tr}(\sum_{i,j}A_{i,j}^{*}A_{i,j})=\sum_{i,j}\|A_{i,j}\|_{2}^{2}.$$

Therefore, we have $\rho(A)^2\leq\|A\|_{\infty}^2\leq \|A\|_{2}^2\leq d$. Furthermore, if $\rho(A)^2=d$, then $\|A\|_{\infty}=\|A\|_{2}$, and this is only possible if $\text{Rank}(A)=1$ which implies that $\text{Rank}(A_{i,j})\leq 1$ as well.

Suppose that $(A_{i,j})_{i,j}\in E$. Then there is some $\lambda>0$ and some invertible $B$ where $\Phi((\lambda BA_{i,j}B^{-1})_{i,j})$ is a quantum channel. Suppose now that $C$ is the block matrix with blocks $(\lambda BA_{i,j}B^{-1})_{i,j}$. Then

$$\frac{\rho(A)^2}{\rho(\Phi((A_{i,j})_{i,j})}=\frac{\rho(C)^2}{\rho(\Phi((\lambda BA_{i,j}B^{-1})_{i,j})}=\rho(C)\leq d.$$

Therefore, $$\rho(A)^2\leq d\cdot \rho(\Phi((A_{i,j})_{i,j}).$$

Furthermore, if $(A_{i,j})_{i,j}\in E$, and $\rho(A)^2=d\cdot \rho(\Phi((A_{i,j})_{i,j})$, then we know that $\text{Rank}(C)=1$, so $\text{Rank}(A)=1$ as well, and therefore $\text{Rank}(A_{i,j})=1$ for each $i,j$.

Since $E$ is dense $(L(\mathbb{C}^{d}))^{m\times m}$, we conclude that $$\rho(A)^2\leq d\cdot \rho(\Phi((A_{i,j})_{i,j})$$ whenever $(A_{i,j})_{i,j}\in (L(\mathbb{C}^{d}))^{m\times m}.$

I now claim that whenever $A\in L(\mathbb{C}^{m\times d})$, if $\rho(A)^2=d\cdot \rho(\Phi((A_{i,j})_{i,j})\neq 0$, then $\text{Rank}(A)=1$.

We shall now define functions $f:O^{\uparrow}\rightarrow\mathbb{R},g:M_{md}(\mathbb{C})\rightarrow\mathbb{R}$. Set $f(A)=\frac{\rho(A)^2}{\rho(\Phi((A_{i,j})_{i,j})}$ for $A\in O^{\uparrow}$. Then the function $f$ is continuous. Let $$g(A)=\frac{|\lambda_{2}^2|}{\rho(\Phi((A_{i,j})_{i,j}))}$$ where $\lambda_{1},\dots,\lambda_{m\cdot d}$ are the eigenvalues of $A$ ordered so that $|\lambda_{1}|\geq|\lambda_{2}|\geq\dots\geq|\lambda_{m\cdot d}|$. The motivation behind the function $g$ is that for $A\in O^{\uparrow}$, $\text{Rank}(A)\leq 1$ precisely when $g(A)=0$ and that $g(A)=g(C)$ whenever there is some $\lambda\neq 0$ and $B$ where $A_{i,j}=\lambda\cdot BC_{i,j}B^{-1}$ for all $i,j$.

Let $f(A)=d\leq m$. Let $\delta>0$. Then there is some $\epsilon>0$ where if $\|A-H\|_2<\epsilon$, then $f(H)>d-\delta$.

Suppose that $\epsilon>0$. Then there is some $H\in E^{\uparrow}$ where $\|A-H\|_2<\epsilon$, and therefore $f(H)>d-\delta$. Now, since $H\in E^{\uparrow}$, there are $\lambda,B$ where if $C_{i,j}=\lambda\cdot B\cdot H_{i,j}\cdot B^{-1}$ for each $i,j$, then $\Phi((C_{i,j})_{i,j})$ is a quantum channel. Therefore, $f(C)=f(H)>d-\delta$.

Therefore, we have $d-\delta\leq\rho(C)^2\leq\|C\|^2_\infty\leq\|C\|_2^2\leq d.$ Now, let $\lambda_1,\dots,\lambda_{md}$ be the eigenvalues of $C$, and let $\sigma_1,\dots,\sigma_{md}$ be the singular values of $C$. Suppose that $|\lambda_1|\geq|\lambda_2|\geq\dots\geq|\lambda_{md}|$. Then $$d-\delta\leq\max(|\lambda_1|^2,\dots,|\lambda_{md}|^2)\leq |\lambda_1|^2+\dots+|\lambda_{md}|^2\leq \sigma_1^2+\dots+\sigma_{md}^2\leq d.$$

Thus $d-\delta\leq|\lambda_1|^2\leq|\lambda_1|^2+|\lambda_2|^2\leq d$, so $d-\delta+|\lambda_2^2|\leq d$. Therefore, $|\lambda_2^2|\leq\delta$.

We conclude that $g(H)=g(C)\leq\delta$.

Therefore, $g(H)\rightarrow 0$ as $H\rightarrow A,H\in E^{\uparrow}$. Therefore, $g(A)=0$ which means that $\text{Rank}(A)\leq 1$ and therefore $\text{Rank}(A_{i,j})\leq 1$ for all $i,j$.