Lower dimensional approximations to the L_2-spectral radius

In this post, we shall discuss various generalizations of the notion of the spectral radius to a sort of spectral radius for collections of multiple operators, and we shall develop the theory of the L_{2,d}-spectral radius \rho_{2,d}. This post consists of the new mathematical research on spectral radii which I will apply to measure the cryptographic security of block cipher round functions with very small key space and small message space. The results that are about the L_{2,d}-spectral radii \rho_{2,d}(A_1,\dots,A_r) are due to J. Van Name unless otherwise stated while all other results stated are due to others unless otherwise or are standard results in quantum information theory. This post shall be a purely mathematical post, so this post will not contain any cryptography nor will we discuss algorithms that one can use to compute the spectral radii or at least bounds for the spectral radii. I expect for the notion of the L_{2,d}-spectral radius to extend to infinite dimensional Hilbert spaces, but no one has formulated such a generalization yet. Future posts about spectral radii will be about the application of spectral radii to cryptography, algorithms, the results of these computations, and possible an L_{2,d}-spectral radius for infinite dimensional spaces.

This post includes a large amount of linear algebra and quantum information theory. I recommend the book The Theory of Quantum Information by John Watrous (2018) for information about quantum information theory; most of the facts about linear algebra and quantum information theory that I state but do not prove can be found in The Theory of Quantum Information. I intend for this post to be accessible to people who understand linear algebra but who do not necessarily have much knowledge about functional analysis, quantum information theory, quantum computation, or quantum mechanics.

Spectral radius

Suppose that A is a complex Banach space that contains an operation \cdot that makes A into a unital ring. Then we say that A is a unital Banach algebra if \|x\cdot y\|\leq\|x\|\cdot\|y\| whenever x,y\in A and if \|1\|=1.

If x\in A, then the spectrum \sigma(x) of x is the set of all complex numbers \lambda where x-\lambda\cdot 1 is not invertible. If x is a square complex matrix, then \sigma(x) is simply the set of all eigenvalues of x. The spectrum \sigma(x) is always a compact non-empty subset of \mathbb{C}. Define the spectral radius \rho(x) of x to be \max\{|\lambda|:\lambda\in\sigma(x)\}. The following theorem motivates the spectral radius \rho(x) as a measure of the growth rate of x^n.

Theorem: If x\in A, then \rho(x)=\lim_{n\rightarrow\infty}\|x^{n}\|^{1/n}.

We have \frac{1}{1-a}=\sum_{k=0}^{\infty}a^k whenever \rho(a)<1 and this sum converges absolutely. On the other hand, \sum_{k=0}^{\infty}a^k diverges whenever \rho(a)>1. More generally, \rho(a)^{-1} is the radius of convergence of the power series \sum_{k=0}^{\infty}z^k\cdot a^k.

We may generalize the notion of the spectral radius to a spectral radius of multiple operators in several different ways. If A is a Banach algebra, x_{1},\dots,x_{r}\in A, and 1\leq p<\infty, then define the L_p-spectral radius as \rho_{p}(x_{1},\dots,x_{r})=\lim_{n\rightarrow\infty}[\sum_{(i_{1},\dots,i_{n})\in\{1,\dots,r\}^{n}}\|x_{i_{1}}\dots x_{i_{n}}\|^{p}]^{1/(np)} (it is not too hard to show that this limit exists). Observe that when A=M_c(\mathbb{C}), this definition of \rho_{p}(x_{1},\dots,x_{r}) does not depend on the choice of norm, and this definition still holds even if we drop the requirement that the norm is sub-multiplicative. Define \rho_{\infty}(x_1,\dots,x_r)=\lim_{n\rightarrow\infty}[\sup_{(i_{1},\dots,i_{n})\in\{1,\dots,r\}^{n}}\|x_{i_{1}}\dots x_{i_{n}}\|]^{1/n} (this limit exists) . We can also write \rho_p in terms of the \ell^p norm for 1\leq p\leq\infty by letting \rho_p(x_1,\dots,x_r)=\lim_{n\rightarrow\infty}\|(\|x_1\dots x_{i_n}\|)_{i_1,\dots,i_n\in\{1,\dots,r\}^n}\|_p^n. Here, \|\cdot\|_p denotes the \ell^p norm.

If R is a ring and x_1,\dots,x_r\in R, then we say that (x_1,\dots,x_r) is jointly nilpotent if x_{i_1} \dots x_{i_m}=0 for all but finitely many strings i_1,\dots,i_m.

Basic observations: Suppose that A is a Banach algebra and x_1,\dots,x_r\in A. Let y be an invertible element in A. Suppose that X_1,\dots,X_r,Y_1,\dots,Y_r,Z_1,\dots,Z_r\in M_n(\mathbb{C}). Let 1\leq p\leq q\leq \infty.

  1. \rho_p(x_1,\dots,x_r)=\rho_p(yx_1y^{-1},\dots,yx_ry^{-1}) whenever y is an invertible element in A.
  2. \rho_p(\lambda x_1,\dots,\lambda x_r)=|\lambda|\cdot \rho_p(x_1,\dots,x_r) for each scalar \lambda.
  3. \rho_p(x_1,\dots,x_r)\leq\rho_p(x_1,\dots,x_s) whenever r\leq s.
  4. \rho_p(x_1,\dots,x_r)=\rho_p(x_1,\dots,x_r,0).
  5. \rho_q(x_1,\dots,x_r)\leq\rho_p(x_1,\dots,x_r)\leq r^{(1/p)-(1/q)}\rho_q(x_1,\dots,x_r).
  6. \rho_p(X_1,\dots,X_r)=\rho_p(X_1^*,\dots,X_r^*)=\rho_p(X_1^T,\dots,X_r^T)=\rho_p(\overline{X_1},\dots,\overline{X_r}).
  7. \rho_p(X_1,\dots,X_r)=0 if and only if (X_1,\dots,X_r) is jointly nilpotent.
  8. \rho_p(\begin{bmatrix} X_1 & Y_1 \\ 0 & Z_1\end{bmatrix},\dots,\begin{bmatrix} X_r & Y_r \\ 0 & Z_r\end{bmatrix})=\max(\rho_p(X_1,\dots,X_r),\rho_p(Z_1,\dots,Z_r))

To prove the above fact, we use the fact that if \mathbf{x}\in\mathbb{C}^N, then \|\mathbf{x}\|_q\leq\|\mathbf{x}\|_p\leq N^{(1/p)-(1/q)}\|\mathbf{x}\|_q.

While the spectral radii \rho_1(x_1,\dots,x_r),\rho_2(x_1,\dots,x_r),\rho_\infty(x_1,\dots,x_r) are distinct important generalizations of the notion of a spectral radius, for this post, we shall be primarily concerned with the spectral radius \rho_2(x_1,\dots,x_r). For the rest of this post, we shall assume all vector spaces are finite dimensional inner product spaces.

Let V,W be a finite dimensional complex inner product spaces. Let L(V,W) denote the space of all linear operators from V to W, and let L(V)=L(V,V). If A_1,\dots,A_r\in L(V), then define a mapping \Phi(A_1,\dots,A_r):L(V)\rightarrow L(V) by letting \Phi(A_1,\dots,A_r)(X)=A_{1}XA_{1}^{*}+\dots+A_{r}XA_{r}^{*}. Throughout this post, we shall implicitly use the fact that the operator \Phi(A_1,\dots,A_r) is similar to A_1\otimes\overline{A_1}+\dots+A_r\otimes\overline{A_r}.

If 1\leq p\leq\infty, then recall that the p-Schatten norm of a complex matrix A is defined by letting \|A\|_p=(\text{Tr}((AA^*)^{p/2}))^{1/p} for 1\leq p<\infty and \|A\|_\infty=\{\|Ax\|_2:\|x\|_2\leq 1\}. If \sigma_1,\dots,\sigma_n are the singular values of A, then \|A\|_p=\|(\sigma_1,\dots,\sigma_n)\|_p. If A,B are real or complex matrices with the same dimensions, then define the Frobenius inner product \langle A,B\rangle=\text{Tr}(AB^{*}). Observe that \|A\|_{2}=\langle A,A\rangle^{1/2}. If A=(a_{i,j})_{1\leq i\leq m,1\leq j\leq n}, then \|A\|_{2}=\sqrt{\sum_{i=1}^{m}\sum_{j=1}^{n}|a_{i,j}|^{2}}.

The following proposition was originally proven by Ding-Xuan Zhou in the 1998 paper titled The p-norm joint spectral radius for even integers.

Proposition: \rho(\Phi(A_{1},\dots,A_{r}))=\rho_{2}(A_{1},\dots,A_{r})^2.

Proof: Let D be the collection of all positive semidefinite matrices X with \|X\|_\infty\leq 1. Observe that if X is positive semidefinite, then X\in D if and only if \sqrt{X}\in D. We will need to use the fact that \max_{X\in D}\|A\sqrt{X}\|_2=\|A\|_2.

For this proof, the norm \|\mathcal{E}\| on an operator \mathcal{E} from L(V) to L(V) shall be the maximum value of \|\Phi(A)\|_{1} such that A\in D. We have

\rho(\Phi(A_{1},\dots,A_{r}))=\lim_{n\rightarrow\infty}\|\Phi(A_{1},\dots,A_{r})^{n}\|^{1/n}

=\lim_{n\rightarrow\infty}\|\sum_{i_{1},\dots,i_{n}\in\{1,\dots,r\}^{n}}\Phi(A_{i_{1}})\dots\Phi(A_{i_{n}})\|^{1/n}

=\lim_{n\rightarrow\infty}\|\max_{X\in D}\sum_{i_{1},\dots,i_{n}\in\{1,\dots,r\}^{n}}\Phi(A_{i_{1}})\dots\Phi(A_{i_{n}})X\|_{1}^{1/n}

=\lim_{n\rightarrow\infty}\|\max_{X\in D}\sum_{i_{1},\dots,i_{n}\in\{1,\dots,r\}^{n}}A_{i_{1}}\dots A_{i_{n}}XA_{i_{n}}^{*}\dots A_{i_{1}}^{*}\|_{1}^{1/n}

=\lim_{n\rightarrow\infty}[\max_{X\in D}\sum_{i_{1},\dots,i_{n}\in\{1,\dots,r\}^{n}}\text{Tr}(\sqrt{X}A_{i_{n}}^{*}\dots A_{i_{1}}^{*}A_{i_{1}}\dots A_{i_{n}}\sqrt{X})]^{1/n}

=\lim_{n\rightarrow\infty}[\max_{X\in D}\sum_{i_{1},\dots,i_{n}\in\{1,\dots,r\}^{n}}\|A_{i_{1}}\dots A_{i_{n}}\sqrt{X}\|^{2}_{2}]^{1/n}

==\lim_{n\rightarrow\infty}[\sum_{i_{1},\dots,i_{n}\in\{1,\dots,r\}^{n}}\|A_{i_{1}}\dots A_{i_{n}}\|^{2}_{2}]^{1/n}=\rho_{2}(A_{1},\dots,A_{r})^{2}. Q.E.D.

Corollary: If p is an even integer, then \rho(\Phi(A_{1}^{\otimes p},\dots,A_{r}^{\otimes p}))=\rho_{2p}(A_{1},\dots,A_{r})^{2p}.

Proposition: Suppose that p,q are positive real numbers with 1=\frac{1}{p}+\frac{1}{q}. Then \rho(A_{1}\otimes B_{1}+\dots+A_{r}\otimes B_{r})\leq \rho_{p}(A_{1},\dots,A_{r})\rho_{q}(B_{1},\dots,B_{r}).

Proof: Assume that our matrix norm satisfies the property \|A\otimes B\|=\|A\|\cdot\|B\| for all matrices A,B. By applying Holder’s inequality, we perform the following calculations.

\rho(A_{1}\otimes B_{1}+\dots+A_{r}\otimes B_{r})

=\lim_{n\rightarrow\infty}\|(A_{1}\otimes B_{1}+\dots+A_{r}\otimes B_{r})^{n}\|^{1/n}

=\lim_{n\rightarrow\infty}\|\sum_{i_{1},\dots,i_{n}\in\{1,\dots,r\}}(A_{i_{1}}\otimes B_{i_{1}})\dots(A_{i_{n}}\otimes B_{i_{n}})\|^{1/n}

=\lim_{n\rightarrow\infty}\|\sum_{i_{1},\dots,i_{n}\in\{1,\dots,r\}}(A_{i_{1}}\dots A_{i_{n}})\otimes(B_{i_{1}}\dots B_{i_{n}})\|^{1/n}

\leq\lim_{n\rightarrow\infty}[\sum_{i_{1},\dots,i_{n}\in\{1,\dots,r\}}\|(A_{i_{1}}\dots A_{i_{n}})\otimes(B_{i_{1}}\dots B_{i_{n}})\|]^{1/n}

=\lim_{n\rightarrow\infty}[\sum_{i_{1},\dots,i_{n}\in\{1,\dots,r\}}\|A_{i_{1}}\dots A_{i_{n}}\|\cdot\|B_{i_{1}}\dots B_{i_{n}}\|]^{1/n}

=\lim_{n\rightarrow\infty}[\sum_{i_{1},\dots,i_{n}\in\{1,\dots,r\}}\|A_{i_{1}}\dots A_{i_{n}}\|\cdot\|B_{i_{1}}\dots B_{i_{n}}\|]^{1/n}

\leq\lim_{n\rightarrow\infty}(\sum_{i_{1},\dots,i_{n}\in\{1,\dots,r\}}\|A_{i_{1}}\dots A_{i_{n}}\|^p)^{1/(np)}\cdot(\sum_{i_{1},\dots,i_{n}\in\{1,\dots,r\}}\|B_{i_{1}}\dots B_{i_{n}})\|^q)^{1/(nq)}

=\rho_p(A_{1},\dots,A_{r})_{2}\rho_q(B_{1},\dots,B_{r})_{2}.

Q.E.D.

The above inequality is sharp when p=q=2 since \rho(A_{1}\otimes \overline{A_{1}}+\dots+A_{r}\otimes \overline{A_{r}})=\rho_{2}(A_{1},\dots,A_{r})\rho_{2}(\overline{A_{1}},\dots,\overline{A_{r}}).

Example: If U_{1},\dots,U_{r} are unitary matrices, then \rho_{2}(U_{1},\dots,U_{r})=\sqrt{r}. More generally, if \alpha_{1},\dots,\alpha_{r} are constants, then \rho_{p}(\alpha_{1}U_{1},\dots,\alpha_{r}U_{r})=(|\alpha_{1}|^{p}+\dots+|\alpha_{r}|^{p})^{1/p}.

Example: Suppose that A_1,\dots,A_r,B_1,\dots,B_s are matrices. Then \rho_{p}((A_{i}\otimes B_j)_{i,j})=\rho_p(A_1,\dots,A_r)\rho_p(B_1,\dots,B_s).

Example: If A_1,\dots,A_r are matrices, then \rho_{p}(A_1^{\otimes n},\dots,A_r^{\otimes n})=\rho_{pn}(A_1,\dots,A_r)^n.

Quantum information theory

A mapping \Phi\in L(L(V),L(W)) is said to be positive if \Phi(A) is positive semidefinite whenever A\in L(V) is positive semidefinite. The mapping \Phi is said to be completely positive if \Phi\otimes 1_{L(Z)}:L(L(V\otimes Z),L(W\otimes Z)) is positive whenever Z is a finite dimensional complex inner product space. The mapping \Phi\in L(L(V),L(W)) is said to be trace preserving if \Phi(\text{Tr}(A))=\text{Tr}(A) for each A\in L(V). The mapping \Phi\in L(L(V),L(W)) is said to be unital if \Phi(1_{V})=1_{W}. A mapping \Phi\in L(L(V),L(W)) is said to be a quantum channel if \Phi is completely positive and trace preserving.

If U,V,W are complex vector spaces, then there is a unique linear mapping \text{Tr}_W:L(U\otimes W,V\otimes W)\rightarrow L(U,V) where \text{Tr}_W(A\otimes B)=\text{Tr}(B)\cdot A whenever B\in L(W),A\in L(U,V). This linear mapping is known as the partial trace.

Observation: Suppose that B:V_1\rightarrow V_2,X:V_2\otimes W\rightarrow V_3\otimes W,A:V_3\rightarrow V_4, S:W\rightarrow W, and Y:V\otimes W\rightarrow V\otimes W. Then

  1. A\cdot \text{Tr}_W(X)B=\text{Tr}_W((A\otimes 1_W)X(B\otimes 1_W)),
  2. \text{Tr}_W((1_{V_3}\otimes S)X)=\text{Tr}_W(X(1_{V_2}\otimes S)), and
  3. \text{Tr}(Y)=\text{Tr}(\text{Tr}_W(Y)).

If V_1,V_2,V_3,V_4 are finite dimensional complex inner product spaces, then L(V_1,V_2),L(V_3,V_4) are inner product spaces with the Frobenius norm. In this case, if \mathcal{E}:L(V_1,V_2)\rightarrow L(V_3,V_4) is a linear mapping, then the adjoint \mathcal{E}^* of \mathcal{E} is the adjoint with respect to the Frobenius norms on L(V_1,V_2) and L(V_3,V_4).

Let U_1,U_2,V_1,V_2 be finite dimensional complex inner product spaces. Every mapping in L(L(U_1,U_2),L(V_1,V_2)) is a linear combinational of mappings of the form X\mapsto AXB^* where A\in L(U_2,V_2),B\in L(U_1,V_1). Therefore, if A_1,\dots,A_r\in L(U_2,V_2),B_1,\dots,B_r\in L(U_1,V_1), then let \Gamma(A_1,\dots,A_r;B_1,\dots,B_r)\in L(L(U_1,U_2),L(V_1,V_2)) be the mapping defined by letting \Gamma(A_1,\dots,A_r;B_1,\dots,B_r)(X)=A_1XB_1^*+\dots+A_rXB_r^* whenever X\in L(U_1,U_2). If A\in L(U_2,V_2\otimes W),B\in L(U_1,V_1\otimes W), then let \Gamma(A;B)\in L(L(U_1,U_2),L(V_1,V_2)) be the mapping defined by letting \Gamma(A;B)(X)=\text{Tr}_W(AXB^*), and define \Phi(A) by letting \Phi(A)=\Gamma(A;A). We shall sometimes write \Gamma_W(A;B) for \Gamma(A;B) and \Phi_W(A) for \Phi(A) in order to specify the vector space W. Observe that \Gamma(A_1,\dots,A_r;B_1,\dots,B_r)^*=\Gamma(A_1^*,\dots,A_r^*;B_1^*,\dots,B_r^*) and \Gamma(A;B)^*(Y)=A^*(Y\otimes 1_W)B, and \Phi(A)^*(Y)=A^*(Y\otimes 1_W)A whenever these equations make sense.

The linear operator \Gamma(A_1,\dots,A_r;B_1,\dots,B_r) is similar to the linear operator A_1\otimes\overline{B_1}+\dots+A_r\otimes\overline{B_r}.

Theorem: Let U,V be finite dimensional complex inner product spaces. Let \mathcal{E}:L(U)\rightarrow L(V) be a linear mapping. The following are equivalent:

Theorem: Let U,V be finite dimensional complex inner product spaces. Let \mathcal{E}:L(U)\rightarrow L(V) be a linear mapping. The following are equivalent:

  1. \mathcal{E} is completely positive.
  2. \mathcal{E}\otimes 1_{L(U)} is positive.
  3. \mathcal{E}=\Phi(A_1,\dots,A_r) for some r\geq 0 and A_1,\dots,A_r\in L(U,V).
  4. \mathcal{E}=\Phi(A) for some finite dimensional complex inner product space W and A\in L(U,V\otimes W).

Theorem: Let U,V be finite dimensional complex inner product spaces. Let \mathcal{E}:L(U)\rightarrow L(V) be a linear mapping. Then the operator \mathcal{E} is trace preserving if and only if its adjoint \mathcal{E}^* is unital.

Theorem

1: Let A_1,\dots,A_r,B_1,\dots,B_r\in L(U,V). Then

i. The following are equivalent:

a. \Gamma(A_1,\dots,A_r;B_1,\dots,B_r) is trace preserving.

b. A_1^*B_1+\dots+A_r^*B_r=1_U.

c. B_1^*A_1+\dots+B_r^*A_r=1_U.

ii. The following are equivalent:

a. \Gamma(A_1,\dots,A_r;B_1,\dots,B_r) is unital.

b. A_1B_1^*+\dots+A_rB_r^*=1_V.

c. B_1A_1^*+\dots+B_rA_r^*=1_V.

2. Let A,B\in L(U,V\otimes W). Then

i. The following are equivalent:

a. \Gamma_W(A;B) is trace preserving.

b. A^*B=1_U.

c. B^*A=1_U.

ii. The following are equivalent:

a. \Gamma_W(A;B) is unital.

b. \text{Tr}_W(AB^*)=1_V.

c. \text{Tr}_W(BA^*)=1_V.

Theorem: Suppose that A:U\rightarrow V\otimes W and A_1,\dots,A_r:U\rightarrow V are linear. The mapping \Phi_W(A) is a quantum channel if and only if A is an isometry. The mapping \Phi(A_1,\dots,A_r) is a quantum channel if and only if A_1^*A_1+\dots+A_r^*A_r=1.

Example: The completely depolarizing channel is the channel \Omega:L(V)\rightarrow L(V) defined by letting \Omega(A)=\frac{1}{\dim(V)}\cdot 1_{V}\cdot\text{Tr}(A). The completely depolarizing channel is unital. If V=\mathbb{C}^n, then let A_{i,j} be the n\times n-matrix defined by letting A_{i,j}=(a_{\delta((i,j),(r,s))})_{r,s} where \delta refers to the Kronecker delta function. Then \Omega=\Phi((A_{i,j})_{i,j})/r. We shall write \Omega_V in order to specify the space V, and we shall write \Omega_n for \Omega_{\mathbb{C}^n}.

Example: Suppose that (p_1,\dots,p_r) is a probability vector. Let V be a finite dimensional complex inner product space. Let U_1,\dots,U_r:V\rightarrow V be unitary operators. Then let \Phi:L(V)\rightarrow L(V) be the function where \phi(X)=p_1 U_1XU_1^*+\dots+p_r U_rXU_r^* for each X\in L(V). Then we say that \phi is mixed unitary. Every mixed unitary operator is a unital channel, but not every unitary channel is mixed unitary. However, John Watrous has shown that there is a neighborhood O of the completely depolarizing channel where if A\in O, then A is mixed unitary if and only if it is unital.

Example: The complete dephasing channel is the channel \Delta\in L(L(\mathbb{C}^n)) defined by letting \Delta((a_{i,j})_{i,j})=(b_{i,j}) precisely when b_{i,j}=0 for i\neq j and b_{i,i}=a_{i,i} for 1\leq i\leq n. Suppose that B_1,\dots,B_n are the matrices where B_i=(\delta_{(i,i),(r,s)})_{r,s} for 1\leq i\leq n and where the addition in the subscript is taken modulo n. Then \Delta=\Phi(B_1,\dots,B_n).

Example: The shifted complete dephasing channel is the channel \Delta^{S}\in T(\mathbb{C}^n) defined by letting \Delta((a_{i,j})_{i,j})=(b_{i,j}) precisely when b_{i,j}=0 for i\neq j and b_{i,i}=a_{i+1,i+1} for 1\leq i\leq n where the addition in the subscripts is taken modulo n. Suppose now that C_1,\dots,C_n are the matrices where C_i=(\delta_{(i,i+1),(r,s)})_{r,s} for 1\leq i\leq n and where the addition in the subscript is taken modulo n. Then \Delta^S=\Phi(C_1,\dots,C_n).

Example: The shifted complete dephasing channel is the channel \Delta^{S}\in T(\mathbb{C}^n) defined by letting \Delta((a_{i,j})_{i,j})=(b_{i,j}) precisely when b_{i,j}=0 for i\neq j and b_{i,i}=a_{i+1,i+1} for 1\leq i\leq n where the addition in the subscripts is taken modulo n. Suppose now that C_1,\dots,C_n are the matrices where C_i=(\delta_{(i,i+1),(r,s)})_{r,s} for 1\leq i\leq n and where the addition in the subscript is taken modulo n. Then \Delta^S=\Phi(C_1,\dots,C_n).

Proposition: If \mathcal{E}\in T(V) is positive and either trace preserving or unital, then \rho(\mathcal{E})=1.

Proof outline: Since \mathcal{E} is trace preserving if and only if its adjoint \mathcal{E}^* is unital, we only have to prove this result when \mathcal{E} is trace preserving.

If P is positive and trace preserving, then whenever P is positive semidefinite, we have \|\mathcal{E}^n(P)\|_1=\text{Tr}(\mathcal{E}^n(P))=\text{Tr}(P)=\|P\|_1. From this fact, one can easily conclude that \rho(\mathcal{E})=1. Q.E.D.

Proposition: If \mathcal{E}:L(V)\rightarrow L(V) is positive and \mathcal{E}(P)\neq 0 whenever P is a positive semidefinite matrix with P\neq 0, then \mathcal{E} has a positive semidefinite eigenvector with non-zero eigenvector.

Proof: Let C be the collection of all positive semidefinite operators P\in L(V) with \text{Tr}(P)=1. Define a mapping f:C\rightarrow C by letting f(P)=\frac{\mathcal{E}(P)}{\text{Tr}(\mathcal{E}(P))}. Then by Brouwer’s fixed point theorem, there is some P\in C with P=f(P). Therefore, \mathcal{E}(P)=\text{Tr}(\mathcal{E}(P))\cdot P.

Q.E.D.

Corollary: If \mathcal{E}:L(V)\rightarrow L(V) is positive and trace preserving, then there is a positive semidefinite P with P\neq 0 and \mathcal{E}(P)=P.

Proposition: If \mathcal{E}:L(V)\rightarrow L(V) is a positive mapping. If P is a positive definite eigenvector, then \mathcal{E}(P)=\rho(P)\cdot P.

Proof: Suppose that \lambda is an eigenvalue with |\lambda|=\rho(\mathcal{E}) and X is an eigenvector with \mathcal{E}(X)=\lambda X. Then there are positive semidefinite P_1,P_2,P_3,P_4 with X=P_1-P_2+i(P_3-P_4). Therefore, there is some \alpha>0 with P_j\leq \alpha P for all j.

For all n, we have \rho(\mathcal{E})^n\cdot \|X\|_1=\|\mathcal{E}^n(X)\|_1 \leq\sum_{k=1}^4\|\mathcal{E}^n(P_k)\|_1 \leq\sum_{k=1}^4\alpha\cdot\|\mathcal{E}^n(P)\|_1=4\alpha\mu^n\cdot\|P\|_1. This is only possible if \mu\geq\rho(P).

Q.E.D.

Tensor products

We will apply the following observations about tensor products and related constructions to the L_{2,d}-spectral radius.

Proposition: Suppose that A_1,\dots,A_r,B_1,\dots,B_r are m\times n-complex matrices. Then \Phi(A_1,\dots,A_r)=\Phi(B_1,\dots,B_r) if and only if there is an r\times r-unitary matrix u such that A_{i}=\sum_{j=1}^ru_{i,j}B_{j} for 1\leq i\leq r.

Lemma: Suppose that A,B:V_1\rightarrow V_2\otimes W are linear operators. Then \Phi_W(A)=\Phi_W(B) if and only if there is a unitary U:W\rightarrow W such that A=(1_{V_2}\otimes U)B.

Lemma: Suppose that A_1,\dots,A_r,X_1,\dots,X_r,B_1,\dots,B_r,Y_1,\dots,Y_r are matrices over a field F where A_1,\dots,A_r,B_1,\dots,B_r are of the same dimensions and X_1,\dots,X_r,Y_1,\dots,Y_r are of the same dimensions. Let (u_{i,j})_{i,j},(v_{i,j})_{i,j} be r\times r-matrices over the field F. Suppose furthermore that B_i=\sum_{j=1}^r u_{i,j}A_j and Y_i=\sum_{j=1}^rv_{i,j}X_{j} for 1\leq i\leq r. If (u_{i,j})_{i,j}=((v_{i,j})^{T})^{-1}, then A_1\otimes X_1+\dots+A_r\otimes X_r=B_1\otimes Y_1+\dots+B_r\otimes Y_r.

Lemma: Suppose that A_1,\dots,A_r,X_1,\dots,X_r,B_1,\dots,B_r,Y_1,\dots,Y_r are complex matrices where A_1,\dots,A_r,B_1,\dots,B_r have the same dimensions, and X_1,\dots,X_r,Y_1,\dots,Y_r have the same dimensions. Let (u_{i,j})_{i,j},(v_{i,j})_{i,j} be complex r\times r-matrices. Suppose that B_i=\sum_{j=1}^r u_{i,j}A_j and Y_i=\sum_k v_{i,j}X_j for 1\leq i\leq r and (v_{i,j})_{i,j}^*=(u_{i,j})_{i,j}^{-1}, then \Gamma(A_1,\dots,A_r;X_1,\dots,X_r)=\Gamma(B_1,\dots,B_r;Y_1,\dots,Y_r).

Lemma: Let V_1,V_2,V_3,V_4,W be finite dimensional complex inner product spaces. Suppose that A,B:V_1\rightarrow V_2\otimes W and X,Y:V_3\rightarrow V_4\otimes W are linear mappings. Let U,O:W\rightarrow W be linear mappings. Suppose that B=(1_{V_2}\otimes U)A,Y=(1_{V_4}\otimes O)X and U^*=O^{-1}. Then \Gamma_W(A;X)=\Gamma_W(B;Y).

Proposition: Let V_1,V_2,V_3,V_4,W be finite dimensional complex inner product spaces. Let B:V_1\rightarrow V_2\otimes W,A:V_3\rightarrow V_4\otimes W be linear. Let (e_1,\dots,e_r) be an orthonormal basis for W. Let A_1,\dots,A_r:V_1\rightarrow V_2,B_1,\dots,B_r:V_3\rightarrow V_4 be linear. Suppose that A=\sum_{k=1}^rA_k\otimes e_k,B=\sum_{k=1}^rB_k\otimes e_k. Then \Gamma(A;B)=\Gamma(A_1,\dots,A_r;B_1,\dots,B_r).

Observation: Let V_1,V_2,V_3,V_4,W be finite dimensional complex inner product spaces. Suppose that (e_1,\dots,e_r) is an orthonormal basis for W. Let A:V_1\rightarrow V_2\otimes W,B:V_3\rightarrow V_4\otimes W be linear operators. Suppose that A_1,\dots,A_r:V_1\rightarrow V_2,B_1,\dots,B_r:V_3\rightarrow V_4 are linear operators and A=\sum_{k=1}^{r}A_k\otimes e_k,B=\sum_{k=1}^{r}B_k\otimes e_k. Let Y:V_4\rightarrow V_2 be linear. Then A^*(Y\otimes 1_W)B=\Gamma(A;B)^*(Y)=\Gamma(A_1,\dots,A_r;B_1,\dots,B_r)^*(Y)=\Gamma(A_1^*,\dots,A_r^*;B_1^*,\dots,B_r^*)(Y).

Proposition: Let U_1,U_2,V_1,V_1,W be finite dimensional complex inner product spaces. Suppose that A:V_1\rightarrow V_2\otimes W,B:U_2\rightarrow W\otimes U_1 are linear mappings. Let (e_1,\dots,e_r) be an orthonormal basis for W. Let A_1,\dots,A_r:V_1\rightarrow V_2,B_1,\dots,B_r:U_2\rightarrow U_1 be linear maps. Suppose that A=\sum_{k=1}^rA_k\otimes e_k,B=\sum_{k=1}^re_k\otimes B_k. Then \text{Tr}_{W}(A\otimes B^*)=(1_{V_2}\otimes B^*)(A\otimes 1_{U_1})=\sum_{k=1}^rA_k\otimes B_k^*.

L_{2,d}-spectral radius.

Let M_d(\mathbb{C})^{r++} be the collection of all tuples (A_1,\dots,A_r)\in M_d(\mathbb{C})^r which are not jointly nilpotent. Suppose that A_1,\dots,A_r are complex matrices. Then define the L_{2,d}-spectral radius of (A_1,\dots,A_r) by \rho_{2,d}(A_1,\dots,A_r)=\sup\{\frac{\rho(A_1\otimes X_1+\dots+A_r\otimes X_r)}{\rho_2(X_1,\dots,X_r)}\mid (X_1,\dots,X_r)\in M_{d}(\mathbb{C})^{r++}\}.

By the Cauchy-Schwarz inequality \rho(A_1\otimes X_1+\dots+A_r\otimes X_r)\leq\rho_2(X_1,\dots,X_r)\rho_2(A_1,\dots,A_r), we know that \rho_{2,d}(A_1,\dots,A_r)\leq\rho_{2,g}(A_1,\dots,A_r)\leq\rho_2(A_1,\dots,A_r) whenever 1\leq d\leq g, and since \rho_2(A_1,\dots,A_r)^2=\rho_2(A_1\otimes\overline{A_1}+\dots+A_r\otimes\overline{A_r}), we know that if d\geq\dim(A_1), then \rho_{2,d}(A_1,\dots,A_r)=\rho_2(A_1,\dots,A_r).

Proposition: Suppose that (A_1,\dots,A_r),(B_1,\dots,B_r) are n\times n complex matrices. Suppose that there is a r\times r unitary matrix (u_{i,j})_{i,j} such that B_{i}=\sum_{j=1}^{r}u_{i,j}\cdot A_{j} for 1\leq i\leq r. Then \rho_{2,d}(B_1,\dots,B_r)=\rho_{2,d}(A_1,\dots,A_r).

Proof: Let (v_{i,j})_{i,j}=((u_{i,j})_{i,j}^{-1})^T=(\overline{u_{i,j}})_{i,j}. Then (v_{i,j})_{i,j} is unitary. Suppose now that \mu<\rho_{2,d}(A_1,\dots,A_r). Then there are X_1,\dots,X_r\in M_d(\mathbb{C}) with \frac{\rho(A_1\otimes X_1+\dots+A_r\otimes X_r)}{\rho_2(X_1,\dots,X_r)}>\mu. Now set Y_i=\sum_{j=1}^{r}v_{i,j}X_j for 1\leq i\leq r, then \sum_{i=1}^{r}B_{i}\otimes Y_{i}=\sum_{i=1}^{r}A_i\otimes X_i and \Phi(X_1,\dots,X_r)=\Phi(Y_1,\dots,Y_r). Therefore, \rho_2(X_1,\dots,X_r)=\rho_2(Y_1,\dots,Y_r), so \mu<\frac{\rho(A_1\otimes X_1+\dots+A_r\otimes X_r)}{\rho_2(X_1,\dots,X_r)}=\frac{\rho(B_1\otimes Y_1+\dots+B_r\otimes Y_r)}{\rho_2(Y_1,\dots,Y_r)}\leq\rho_2(B_1,\dots,B_r). We can therefore conclude that \rho_2(A_1,\dots,A_r)\leq\rho_2(B_1,\dots,B_r).

For the reverse inequality, observe that if (w_{i,j})_{i,j}=(u_{i,j})_{i,j}^{-1}, then A_i=\sum_{j=1}^{r}w_{i,j}\cdot B_j and (w_{i,j})_{i,j} is unitary, so we can conclude that \rho_2(B_1,\dots,B_r)\leq\rho_2(A_1,\dots,A_r) as well.

Q.E.D.

Corollary: If \Phi(A_1,\dots,A_r)=\Phi(B_1,\dots,B_r), then \rho_{2,d}(A_1,\dots,A_r)=\rho_{2,d}(B_1,\dots,B_r) for all d.

If \mathcal{E}:L(V)\rightarrow L(V) is a completely positive superoperator, then define \rho_{2,d}(\mathcal{E}) by letting \rho_{2,d}(\mathcal{E})=\rho_{2,d}(A_1,\dots,A_r)^2 whenever \mathcal{E}=\Phi(A_1,\dots,A_r). By the above corollary, the quantity \rho_{2,d}(\mathcal{E}) is well-defined. If A:V\rightarrow V\otimes W is a linear operator, then define \rho_{2,d}(A)=\rho_{2,d}(\Phi(A))^{1/2}.

Observation: Let U,V,W be finite dimensional complex inner product spaces with \dim(U)=d. Let e_1,\dots,e_r be an orthonormal basis for W. Let A_1,\dots,A_r:V\rightarrow V and let A:V\rightarrow V\otimes W. Let A=A_1\otimes e_1+\dots+A_r\otimes e_r, and let \mathcal{E}=\Phi(A)=\Phi(A_1,\dots,A_r). Then the following quantities are equivalent:

  1. \rho_{2,d}(A_1,\dots,A_r).
  2. \rho_{2,d}(A).
  3. \rho_{2,d}(\mathcal{E})^{1/2}.
  4. \sup\{\frac{\rho(\Gamma(A_1,\dots,A_r;X_1,\dots,X_r))}{\rho_{2}(X_1,\dots,X_r)}\mid (X_1,\dots,X_r)\in M_d(\mathbb{C})^{r++}\}.
  5. \sup\{\frac{\rho(\Gamma(A;X))}{\rho_{2}(X)}\mid X\in L(U,U\otimes W),\rho_{2}(X)\neq 0\}.
  6. \sup\{\frac{\rho((1_V\otimes X^*)(A\otimes 1_U))}{\rho_2(X)}\mid X\in L(U,W\otimes U),\rho_2(X)\neq 0\}.
  7. \sup\{\frac{\rho(\text{Tr}_W(A\otimes X^*))}{\rho_2(X)}\mid X\in L(U,W\otimes U),\rho_2(X)\neq 0\}.

Proof outline: By definition 1-3 are equivalent to each other. The equivalence between 1 and 4 follows from the fact that \rho(\Gamma(A_1,\dots,A_r;X_1,\dots,X_r))=\rho(A_1\otimes\overline{X_1}+\dots+A_r\otimes\overline{X_r}) and \rho_2(X_1,\dots,X_r)=\rho_2(\overline{X_1},\dots,\overline{X_r}). The equivalence between 4 and 5 follows from the fact that if X_1,\dots,X_r\in L(U) and X=\sum_{k=1}^rX_k\otimes e_k, then \Gamma(A;X)=\Gamma(A_1,\dots,A_r;X_1,\dots,X_r) and \rho_2(X)=\rho_2(X_1,\dots,X_r). The equivalence between 6 and 7 follows from the fact that \text{Tr}_W(A\otimes X^*)=(1_V\otimes X^*)(A\otimes 1_U). The equivalence between 1 and 7 follows from the fact that \text{Tr}_W(A\otimes X^*)=\sum_{k=1}^r(A_k\otimes X_k^*) and \rho_2(X_1,\dots,X_r)=\rho_2(X_1^*,\dots,X_r^*).

Q.E.D.

We shall soon see how in the above result, each of the suprema can actually be reached, so we can replace each supremum with a maximum.

Proposition: Suppose that (A_1,\dots,A_r),(B_1,\dots,B_r) are n\times n-complex matrices. Suppose furthermore that there is an invertible n\times n-complex matrix C, a complex number \lambda and a r\times r unitary matrix (u_{i,j})_{i,j} such that B_{i}=\sum_{j=1}^{r}\lambda u_{i,j}\cdot CA_{j}C^{-1} for 1\leq i\leq r. Then \rho_{2,d}(B_1,\dots,B_r)=|\lambda|\cdot\rho_{2,d}(A_1,\dots,A_r).

Proof: It is easy to see that |\lambda|\cdot\rho_{2,d}(A_1,\dots,A_r)=\rho_{2,d}(\lambda CA_1C^{-1},\dots,\lambda CA_rC^{-1}). Furthermore, since \Phi(\lambda CA_1C^{-1},\dots,\lambda CA_rC^{-1})=\Phi(B_1,\dots,B_r), we know that \rho_{2,d}(\lambda CA_1C^{-1},\dots,\lambda CA_rC^{-1})=\rho_{2,d}(B_1,\dots,B_r) as well. Q.E.D.

Lemma: Suppose that A,B:V\rightarrow V\otimes W are linear operators. If A=\lambda(C \otimes U)BC^{-1}, then \rho_2(A)=|\lambda|\cdot\rho_2(B).

Proof: We have \Phi((C\otimes 1_W)BC^{-1})(X)=\text{Tr}_W((C\otimes _W1)BC^{-1}X(C^{-1})^*B^*(C^*\otimes 1_W)) =C\text{Tr}_W(BC^{-1}X(C^{-1})^*B^*)C^*=C\Phi(B)(C^{-1}X(C^{-1})^*)C^*. Therefore, \Phi((C\otimes 1_W)BC^{-1}) is similar to \Phi(B), so \rho(\Phi((C\otimes 1_W)BC^{-1}))=\rho(\Phi(B)). We therefore conclude that \rho_2((C\otimes 1_W)BC^{-1})=\rho_2(B). Furthermore, we have \Phi((C\otimes 1_W)BC^{-1})=\Phi((1_V\otimes U)(C\otimes 1_W)BC^{-1})=\Phi((C\otimes U)BC^{-1}), so \rho_2((C\otimes 1_W)BC^{-1})=\rho_2((C\otimes U)BC^{-1}) as well.

Q.E.D.

Lemma: Suppose that A,B:V\rightarrow V\otimes W are linear operators. If A=\lambda(C\otimes U)BC^{-1}, then \rho_{2,d}(A)=|\lambda|\rho_{2,d}(B).

Proof: Observe that \Gamma_W((C\otimes 1_W)BC^{-1},X)(Z)=\text{Tr}_W((C\otimes 1_W)BC^{-1}ZX^*) =C\text{Tr}_W(BC^{-1}ZX^*)=C\Gamma(B,X)(C^{-1}Z). Therefore, \Gamma_W(B,X) is similar to \Gamma_W((C\otimes 1_W)BC^{-1},X), so \rho(\Gamma_W(B,X))=\rho(\Gamma_W((C\otimes 1_W)BC^{-1},X)). We conclude that \rho_{2,d}(B)=\rho_{2,d}((C\otimes 1_W)BC^{-1}), and clearly \rho_{2,d}(\lambda(C\otimes 1_W)BC^{-1})=|\lambda|\rho_{2,d}((C\otimes 1_W)BC^{-1})=|\lambda|\cdot\rho_{2,d}(B).

Now, since \Phi((C\otimes 1_W)BC^{-1})=\Phi((1_V\otimes U)(C\otimes 1_W)BC^{-1})=\Phi((C\otimes U)BC^{-1}), we know that

|\lambda|\rho_{2,d}(B)=\rho_{2,d}(\lambda(C\otimes 1_W)BC^{-1})=\rho_{2,d}(\lambda(C\otimes U)BC^{-1}). Q.E.D.

Quantum channels and spectral radii

Here, we give theorems that interpret the spectral radii in terms of quantum channels.

Let V,W be finite dimensional complex Hilbert spaces. Suppose that \mathcal{E}:L(V)\rightarrow L(V) is a positive mapping. Suppose that \mathcal{E} has a positive definite eigenvector P with non-zero (necessarily positive) eigenvalue \lambda. Then define a positive operator \mathcal{F} by \mathcal{F}(X)=\lambda^{-1}\sqrt{P}^{-1}\mathcal{E}(\sqrt{P}X\sqrt{P})\sqrt{P}^{-1}. Then \mathcal{F} is unital.

Suppose that \mathcal{E}:L(V)\rightarrow L(V) is a positive mapping. Suppose that \mathcal{E}^* has a positive definite eigenvector P with non-zero (necessarily positive) eigenvalue \lambda. Then define a mapping \mathcal{F} by letting \mathcal{F}(X)=\lambda^{-1}\sqrt{P}\mathcal{E}(\sqrt{P}^{-1}X\sqrt{P}^{-1})\sqrt{P}. Then \mathcal{F} is trace preserving and positive. In particular, if \mathcal{E} is a completely positive, and \mathcal{E}^* has a positive definite eigenvector P, then \mathcal{F} is a quantum channel.

We say that a positive operator \mathcal{E} is pre-unital if \mathcal{E} has a positive definite eigenvector P with non-zero (necessarily positive) eigenvalue \lambda. We say that a positive operator \mathcal{E} is pre-trace preserving if \mathcal{E}^* has a positive definite eigenvector P with non-zero (necessarily positive) eigenvalue \lambda.

We say that a tuple (A_1,\dots,A_r)\in L(V)^r is pre-unital (pre-trace preserving) if \Phi(A_1,\dots,A_r) is pre-unital (pre-trace preserving). We say that A\in L(V\otimes W) is pre-unital (pre-trace preserving) if \Phi(A) is pre-unital (pre-trace preserving).

Proposition: Let V be a finite dimensional complex inner product space. Let \mathcal{E}:L(V)\rightarrow L(V) be a positive operator. The following are equivalent:

  1. \mathcal{E} is pre-unital.
  2. There is some positive definite P and non-zero \lambda where if \mathcal{F}(X)=\lambda\cdot P^{-1}\mathcal{E}(PXP)P^{-1}, then \mathcal{F} is unital.
  3. There is some invertible A and non-zero \lambda where if \mathcal{F}(X)=\lambda\cdot A^{-1}\mathcal{E}(AXA^*)(A^*)^{-1}, then \mathcal{F} is unital.

In particular, |\lambda| is the spectral radius of the operator \mathcal{E}

Proposition: Let V be a finite dimensional complex inner product space. Let \mathcal{E}:L(V)\rightarrow L(V) be a positive operator. The following are equivalent:

  1. \mathcal{E} is pre-trace preserving.
  2. There is some positive definite P and non-zero \lambda where if \mathcal{F}(X)=\lambda\cdot P^{-1}\mathcal{E}(PXP)P^{-1}, then \mathcal{F} is trace preserving.
  3. There is some invertible A and non-zero \lambda where if \mathcal{F}(X)=\lambda\cdot A^{-1}\mathcal{E}(AXA^*)(A^*)^{-1}, then \mathcal{F} is trace preserving.

Proposition: Let V,W be finite dimensional complex inner product spaces where (e_1,\dots,e_r) is an orthonormal basis for W. Let A_1,\dots,A_r\in L(V),A\in L(V,V\otimes W) and suppose that A=A_1\otimes e_1+\dots+A_r\otimes e_r. Then the following are equivalent:

  1. A is pre unital.
  2. There exists some invertible Q and some \lambda\neq 0 where (\lambda QA_1Q^{-1},\dots,\lambda QA_rQ^{-1}) is unital.
  3. There is some positive definite Q and some \lambda\neq 0 where (\lambda QA_1Q^{-1},\dots,\lambda QA_rQ^{-1}) is unital.
  4. There exists some invertible Q and some \lambda\neq 0 where \lambda (Q\otimes 1_W)AQ^{-1} is unital.
  5. There exists some positive definite Q and some \lambda\neq 0 where \lambda (Q\otimes 1_W)AQ^{-1} is unital.

Proposition: Let V,W be finite dimensional complex inner product spaces where W has orthonormal basis (e_1,\dots,e_r). Let A_1,\dots,A_r\in L(V),A\in L(V,V\otimes W), and suppose that A=A_1\otimes e_1+\dots+A_r\otimes e_r. Then the following are equivalent:

  1. A is pre-trace preserving.
  2. There exists some invertible Q and some \lambda\neq 0 where \Phi(\lambda QA_1Q^{-1},\dots,\lambda QA_rQ^{-1}) is trace preserving.
  3. There is some positive definite Q and some \lambda\neq 0 where \Phi(\lambda QA_1Q^{-1},\dots,\lambda QA_rQ^{-1}) is trace preserving.
  4. There exists some invertible Q and some \lambda\neq 0 where \lambda (Q\otimes 1_W)AQ^{-1} is trace-preserving.
  5. There exists some positive definite Q and some \lambda\neq 0 where \lambda (Q\otimes 1_W)AQ^{-1} is trace-preserving.

Observation: Let V,W be finite dimensional complex vector spaces and let U be a subspace of V. Let A,A_1,\dots,A_r:V\rightarrow V be linear operators. Let B:V\rightarrow V\otimes W be a linear operator. Let P,Q:V\rightarrow V be positive semidefinite.

  1. \ker(A)=\text{ran}(A^*)^{\perp}.
  2. A^*[U]^\perp=A^{-1}[U^\perp]
  3. \ker(P)=\{x\in V\mid\langle Px,x\rangle=0\}.
  4. \ker(A)=\ker(A^*A).
  5. \text{ran}(A)=\text{ran}(AA^*).
  6. \ker(P+Q)=\ker(P)\cap\ker(Q).
  7. \ker(A^*PA)=A^{-1}[\ker(P)].
  8. \text{ran}(P+Q)=\text{ran}(P)+\text{ran}(Q).
  9. \text{ran}(APA^*)=A[\text{ran}(P)].
  10. \text{ran}(\Phi(A_1,\dots,A_r)(P))=A_1[\text{ran}(P)]+\dots+A_r[\text{ran}(P)].
  11. \ker(\Phi(A^*_1,\dots,A^*_r)(P))=A_1^{-1}[\ker(P)]\cap\dots\cap A_r^{-1}[\ker(P)].
  12. \text{ran}(\Phi(B)(P))=\sum_{w\in W}((1_V\otimes w^*)B)[\text{ran}(P)].
  13. \ker(\phi(B)^*(P))=\bigcap_{w\in W}((1_V\otimes w^*)B)^{-1}[\ker(P)].

From the following proposition, we can conclude that if r>1, then almost all tuples (A_1,\dots,A_r)\in L(V)^r are both pre-unital and pre-trace preserving.

Proposition: Let V be a finite dimensional complex inner product space. Let (A_1,\dots,A_r)\in L(V)^r. Suppose that (A_1,\dots,A_r) has no irreducible subspace other than \{0\} and V. Then (A_1,\dots,A_r) is both pre-unital and pre-trace preserving.

Theorem: (J. Van Name) Let U,V,W be finite dimensional complex vector spaces where W has orthonormal basis (e_1,\dots,e_r) and \dim(U)=d. Let A_1,\dots A_r\in L(V,V),A\in L(V,V\otimes W), and suppose that A=A_1\otimes e_1+\dots+A_r\otimes e_r. Suppose that \mathcal{E}=\Phi(A)=\Phi(A_1,\dots,A_r). The following quantities are equivalent:

  1. \rho_{2,d}(A_1,\dots,A_r).
  2. \rho_{2,d}(A).
  3. \max\{\rho(A_1\otimes X_1+\dots+A_r\otimes X_r)\mid X_1,\dots,X_r\in M_d(\mathbb{C}),X_1^*X_1+\dots+X_r^*X_r=1_d\}.
  4. \max\{\rho(A_1\otimes X_1+\dots+A_r\otimes X_r)\mid X_1,\dots,X_r\in M_d(\mathbb{C}),X_1X_1^*+\dots+X_rX_r^*=1_d\}.
  5. \max\{\rho(\Gamma(A_1,\dots,A_r;X_1,\dots,X_r))\mid X_1,\dots,X_r\in M_d(\mathbb{C}),X_1X_1^*+\dots+X_rX_r^*=1_d\}.
  6. \max\{\rho(\Gamma(A_1,\dots,A_r;X_1,\dots,X_r))\mid X_1,\dots,X_r\in M_d(\mathbb{C}),X_1^*X_1+\dots+X_r^*X_r=1_d\}.
  7. \max\{\rho(\Gamma(A;X))\mid X:U\rightarrow U\otimes W,X^*X=1_U\}
  8. \max(\rho((1_V\otimes X^*)(A\otimes 1_U))\mid X:U\rightarrow W\otimes U,X^*X=1_U\}.
  9. \max(\rho(\text{Tr}_W(A\otimes X^*))\mid X:U\rightarrow W\otimes U,X^*X=1_U\}.

Proof: Observe that \{(X_1,\dots,X_r)\in M_d(\mathbb{C})^r\mid X_1^*X_1+\dots+X_r^*X_r=1\} is compact, so the maximum \{\rho(A_1\otimes X_1+\dots+A_r\otimes X_r)\mid X_1,\dots,X_r\in M_d(\mathbb{C}),X_1^*X_1+\dots+X_r^*X_r=1\} actually exists. By similar arguments, one can show that the maximum exists in 3-9. Furthermore, observe that the quantities in 3-9 are all less than or equal to \rho_{2,d}(A).

(1)\leq(3): Suppose that \epsilon>0. Then there is some (X_1,\dots,X_r)\in M_d(\mathbb{C})^r where \frac{\rho(A_1\otimes X_1+\dots+A_r\otimes X_r)}{\rho_2(X_1,\dots,X_r)}>\rho_{2,d}(A_1,\dots,A_r)-\epsilon. Therefore, there is a pre-trace preserving and pre-unital (Y_1,\dots,Y_r)\in M_d(\mathbb{C})^r with \frac{\rho(A_1\otimes Y_1+\dots+A_r\otimes Y_r)}{\rho_2(Y_1,\dots,Y_r)}>\rho_{2,d}(A_1,\dots,A_r)-\epsilon. Since (Y_1,\dots,Y_r) is pre-trace preserving, there is some \lambda\neq 0 and invertible B where (\lambda BY_1B^{-1},\dots,\lambda BY_rB^{-1}) is trace preserving. In this case, if Z_j=\lambda BY_jB^{-1} for 1\leq j\leq r, then \rho_{2,d}(A_1,\dots,A_r)-\epsilon<\frac{\rho(A_1\otimes Z_1+\dots+A_r\otimes Z_r)}{\rho_2(Z_1,\dots,Z_r)}=\rho(A_1\otimes Z_1+\dots+A_r\otimes Z_r).

Therefore, since \rho_{2,d}(A_1,\dots,A_r)-\epsilon

\leq\max\{\rho(A_1\otimes Z_1+\dots+A_r\otimes Z_r)\mid (Z_1,\dots,Z_r)\in M_d(\mathbb{C})^r,Z_1^*Z_1+\dots+Z_r^*Z_r=1_d\}.

Therefore, \rho_{2,d}(A_1,\dots,A_r)

\leq\max\{\rho(A_1\otimes Z_1+\dots+A_r\otimes Z_r)\mid (Z_1,\dots,Z_r)\in M_d(\mathbb{C})^r,Z_1^*Z_1+\dots+Z_r^*Z_r=1_d\}.

Since (Y_1,\dots,Y_r) is pre-unital, there is some \mu\neq 0 and invertible C where (\mu CY_1C^{-1},\dots,\mu CY_rC^{-1}) is unital. Let W_j=\mu CY_jC^{-1} for 1\leq j\leq r. In this case, we have \rho_{2,d}(A_1,\dots,A_r)-\epsilon<\frac{\rho(A_1\otimes W_1+\dots+A_r\otimes W_r)}{\rho_2(W_1,\dots,W_r)}=\rho(A_1\otimes W_1+\dots+A_r\otimes W_r), so

\rho_{2,d}(A_1,\dots,A_r)

\leq\max\{\rho(A_1\otimes W_1+\dots+A_r\otimes W_r)\mid(W_1,\dots,W_r)\in M_d(\mathbb{C})^r,W_1W_1^*+\dots+W_rW_r^*=1_d\}.

Thus (1)\leq(4) as well.

The proofs that (5)-(9) are all greater than or equal to \rho_{2,d}(A) are similar to the proofs that (1)\leq(3),(1)\leq(4).

Q.E.D.

Let U,V be finite dimensional complex Hilbert spaces. Suppose that \mathcal{E}:L(U)\rightarrow L(V) is a linear operator. Then define the induced trace norm of \mathcal{E} as \|\mathcal{E}\|_1=\max\{\|\mathcal{E}(X)\|_1:\|X\|_1\leq 1\}, and define the completely bounded trace norm of \mathcal{E} as \|\mathcal{E}\|_{CB,1}=\|\mathcal{E}\otimes 1_{L(V)}\|_1. Both the induced trace norm and the completely bounded trace norm are submultiplicative, so \rho(\mathcal{E})\leq\|\mathcal{E}\|_1\leq\|\mathcal{E}\|_{CB,1} whenever U=V.

The proof of following lemma can be found in the 2012 paper ‘Relations for certain symmetric norms and anti-norms before and after partial trace’ by Alexey E. Rastegin.

Lemma: Let U,V,W be finite dimensional complex inner product spaces. Let A:U\otimes W\rightarrow V\otimes W be a linear operator. Suppose that 1\leq p\leq\infty. Then \|\text{Tr}_W(A)\|_p\leq \dim(W)^{(p-1)/p}\cdot\|A\|_p. In particular, \|\text{Tr}_W(A)\|_1\leq \|A\|_1.

If \mathcal{E}\in L(L(U),L(V)) is a positive and trace preserving map, then \|\mathcal{E}\|_1=1. If \mathcal{E}\in L(L(U),L(V)) is a quantum channel, then \|\mathcal{E}\|_{CB,1}=1.

Observe that if \|\Phi(A)(X)\|_1=\|\text{Tr}_W(AXA^*)\|_1\leq\|AXA^*\|_1\leq\|A\|_\infty\|X\|_1\|A^*\|_\infty. Therefore, \|\Phi(A)\|_1\leq\|A\|_{\infty}\cdot\|A^*\|_\infty=\|A\|_\infty^2.

Observation: (J. Van Name) Let U,V,W be finite dimensional complex Hilbert spaces with \dim(U)=d and where W has orthonormal basis (e_1,\dots,e_r). Let A_1,\dots,A_r\in L(V) and suppose that A\in L(V,V\otimes W) is the mapping where A=\sum_{k=1}^rA_k\otimes e_k. Then the following quantities are equivalent:

  1. \rho_{2,d}(A_1,\dots,A_r)^2.
  2. \rho_{2,d}(A)^2.
  3. \max\{\frac{\rho(A_1\otimes X_1+\dots+A_r\otimes X_r)^2}{\|\Phi(X_1,\dots,X_r)\|_1}\mid (X_1,\dots,X_r)\in M_d(\mathbb{C})\setminus\{0\}\}.
  4. \max\{\frac{\rho(\Gamma(A,X))^2}{\|\Phi(X)\|_1}\mid X\in L(U,U\otimes W)\setminus\{0\}\}.
  5. \max\{\frac{\rho(A_1\otimes X_1+\dots+A_r\otimes X_r)^2}{\|\Phi(X_1,\dots,X_r)\|_{CB,1}}\mid (X_1,\dots,X_r)\in M_d(\mathbb{C})\setminus\{0\}\}.
  6. \max\{\frac{\rho(\Gamma(A,X))^2}{\|\Phi(X)\|_{CB,1}}\mid X\in L(U,U\otimes W)\setminus\{0\}\}.
  7. \max\{\frac{\rho(\Gamma(A,X))^2}{\|X\|_{\infty}^2}\mid X\in L(U,U\otimes W)\setminus\{0\}\}.

There are other similar formulae for \rho_{2,d}(A), but for the sake of brevity, we shall leave the task of finding other formulae for \rho_{2,d}(A) to the reader.

Observation: \|X\|_p=\|AXB^*\|_p whenever A,X,B are complex matrices, A,B are isometries, and this product makes sense.

Lemma: Suppose that R,S are isometries. Then \rho(\Gamma(R,S))\leq\|\Gamma(R,S)\|_1\leq 1.

Proof: Observe that \|\Gamma(R,S)(X)\|_1=\|\text{Tr}_W(RXS^*)\|_1\leq\|RXS^*\|_1=\|X\|_1 whenever X is an operator. Therefore, \rho(\Gamma(R,S))\leq \|\Gamma(R,S)\|_1\leq 1. Q.E.D.

Lemma: Suppose that R,S are isometries. Then \rho(\Gamma(R,S))\leq 1.

Proof: Suppose that \lambda is an eigenvalue for \Gamma(R,S). Then \Gamma(R,S)(X)=\lambda X for some X. Therefore, \lambda X=\text{Tr}_W(RXS^*). Now, by the polar decomposition, there is a positive semidefinite P and an isometry H where X=HP. Let T=(H^*\otimes 1_W)RH. Now, \lambda P=\lambda H^*HP=H^*\text{Tr}_W(RHPS*)=\text{Tr}_W(TPS^*).

Suppose that P=\sum_k\sigma_ke_ke_k^*. Then \text{Tr}(\lambda P)=\lambda\sum_k\sigma_k and \text{Tr}(\lambda P)=\text{Tr}(TPS^*)=\sum_k\sigma_k\text{Tr}(Te_ke_k^*S^*)=\sum_k\sigma_k\text{Tr}((Se_k)^*Te_k)=\sum_k\sigma_k\langle Te_k,Se_k\rangle. Therefore, \lambda\sum_k\sigma_k=\sum_k\sigma_k\langle Te_k,Se_k\rangle. This is only possible if |\lambda|\leq 1.

Q.E.D.

Theorem: (J. Van Name) Suppose that U,V are finite dimensional complex vector spaces and A_1,\dots,A_r:U\rightarrow U,B_1,\dots,B_r:V\rightarrow V. Suppose that (A_1,\dots,A_r) is pre-trace preserving, and (B_1,\dots,B_r) is has no non-trivial invariant subspace. If \rho(\Gamma(A_1,\dots,A_r;B_1,\dots,B_r))=\rho_2(A_1,\dots,A_r)\rho_2(B_1,\dots,B_r), then U has an invariant subspace U' and there is a linear bijection C:U'\rightarrow V and non-zero \eta with B_j=\eta CA_j^\sharp C^{-1} for 1\leq j\leq r where A_j^\sharp is the restriction of A_j to the invariant subspace U'.

Proof: Since A_1,\dots,A_r,B_1,\dots,B_r are both pre-trace preserving, there are matrices A,B and non-zero complex numbers \mu,\nu such that if R_j=\mu AA_jA^{-1},S_j=\nu BB_jB^{-1} for 1\leq j\leq r, then \Phi(R_1,\dots,R_r),\Phi(S_1,\dots,S_r) are quantum channels. Suppose now that R=R_1\otimes e_1+\dots R_r\otimes e_r,S=S_1\otimes e_1+\dots+S_r\otimes e_r. Then

\frac{\rho(\Gamma(A_1,\dots,A_r;B_1,\dots,B_r))}{\rho_2(A_1,\dots,A_r)\rho_2(B_1,\dots,B_r)}=\frac{\rho(\Gamma(R_1,\dots,R_r;S_1,\dots,S_r))}{\rho_2(R_1,\dots,R_r)\rho_2(S_1,\dots,S_r)} =\rho(\Gamma(R_1,\dots,R_r;S_1,\dots,S_r))=\rho(\Gamma(R;S)).

Suppose now that e_k,\sigma_k,\lambda,H,P,T are the same as in the above lemma, and suppose that |\lambda|=1. Then \sum_k\lambda\sigma_ke_ke_k^*=\sum_k\sigma_k\langle Te_k,Se_k\rangle.

This is only possible if Te_k=\lambda\cdot e_k whenever \sigma_k>0. This happens precisely when T|_{\text{Im}(P)}=\lambda\cdot S|_{\text{Im}(P)}. Therefore, we have \lambda P=\text{Tr}_W(TPS^*)=\text{Tr}_W(\lambda SPS^*). We therefore, conclude that P=\text{Tr}_W(SPS^*). The positive definite matrix P is positive definite, so (H^*\otimes 1_W)RH=T=\lambda S.

Suppose that x\in V. Then \|RH(x)\|=\|x\|=\|\lambda S(x)\|=\|(H^*\otimes 1_W)RH(x)\|. Therefore, RH(x)\in\text{Im}(H)\otimes 1_W whenever x\in V.

Now, let H^\sharp:V\rightarrow\text{Im}(H),R^\sharp:\text{Im}(H)\rightarrow \text{Im}(H)\otimes W,R_j^\sharp:\text{Im}(H)\rightarrow\text{Im}(H), A_j^\sharp:A^{-1}[\text{Im}(H)]\rightarrow A^{-1}[\text{Im}(H)],A^\sharp:A^{-1}[\text{Im}(H)]\rightarrow\text{Im}(H) be the restrictions of H,R,R_j,A_j,A.

The mapping H^\sharp is unitary. Here, ((H^\sharp)^*\otimes 1_W)R^\sharp H^\sharp=\lambda S. Therefore, (H^{\sharp})^*R_j^{\sharp}H^\sharp=\lambda S_j, so (H^\sharp)^*\mu A^{\sharp}A^{\sharp}_j(A^{\sharp})^{-1}H^{\sharp}=\lambda\nu BB_jB^{-1}. Therefore, A_j^\sharp=\lambda\nu\mu^{-1}(A^\sharp)^{-1}H^{\sharp}BB_jB^{-1}(H^\sharp)^*A^\sharp, so A_j^\sharp=\lambda\nu\mu^{-1}(A^\sharp)^{-1}H^{\sharp}BB_j(A^{-1}H^{\sharp}B)^{-1}.

Q.E.D.

Theorem: (J. Van Name) Let U,V be finite dimensional complex inner product spaces. Suppose that A_1,\dots,A_r:U\rightarrow U,B_1,\dots,B_r:V\rightarrow V are linear operators. Then we can assign the vector spaces U,V bases such that for 1\leq j\leq r, we can write the operators A_j,B_j as block matrices to get

A_j=\begin{bmatrix} A_{j,1,1} & \cdots & A_{j,1,u}  \\ \vdots & \ddots & \vdots  \\ A_{j,u,1} & \dots & A_{j,u,u} \end{bmatrix} and B_j=\begin{bmatrix} B_{j,1,1} & \cdots & B_{j,1,v}  \\ \vdots & \ddots & \vdots  \\ B_{j,v,1} & \dots & B_{j,v,v} \end{bmatrix}

where

i. A_{j,\alpha,\beta}=0 whenever u\geq \alpha>\beta\geq 1,1\leq j\leq r,

ii. A_{j,\alpha,\alpha} is square whenever 1\leq j\leq r,1\leq \alpha\leq u,

iii. (A_{1,\alpha,\alpha},\dots,A_{r,\alpha,\alpha}) has no non-trivial irreducible subspace whenever 1\leq \alpha\leq u,

iv. B_{j,\alpha,\beta}=0 whenever v\geq \alpha>\beta\geq 1,1\leq j\leq r,

v. B_{j,\alpha,\alpha} is square whenever 1\leq j\leq r,1\leq\alpha\leq v, and

vi. (B_{1,\alpha,\alpha},\dots,B_{r,\alpha,\alpha}) has no non-trivial irreducible subspace whenever 1\leq \alpha\leq v.

Given such a decomposition of (A_1,\dots,A_r),(B_1,\dots,B_r) into block matrices, the following are equivalent:

  1. \rho(\Gamma(A_1,\dots,A_r;B_1,\dots,B_r))=\rho_2(A_1,\dots,A_r)\rho_2(B_1,\dots,B_r).
  2. There exists \alpha,\beta, a complex number \lambda and an invertible C where \rho_2(A_1,\dots,A_r)=\rho_2(A_{1,\alpha,\alpha},\dots,A_{r,\alpha,\alpha}) and \rho_2(B_1,\dots,B_r)=\rho_2(B_{1,\beta,\beta},\dots,A_{r,\beta,\beta}) and where A_{j,\alpha,\alpha}=\lambda CB_{j,\beta,\beta}C^{-1} for 1\leq j\leq r.

Corollary: (J. Van Name) If (A_1,\dots,A_r) has no non-trivial invariant subspace, then \rho_{2,d}(A_1,\dots,A_r)<\rho_2(A_1,\dots,A_r) whenever d<\dim(A_1).

Proof: By the above result, we can choose (X_1,\dots,X_r)\in M_d(\mathbb{C})^{++} such that \rho_2(A_1,\dots,A_r)=\frac{\rho(A_1\otimes X_1+\dots+A_r\otimes X_r)}{\rho_2(X_1,\dots,X_r)}, but by the above result, we know that \frac{\rho(A_1\otimes X_1+\dots+A_r\otimes X_r)}{\rho_2(X_1,\dots,X_r)}<\rho_2(A_1,\dots,A_r). Q.E.D.

Statement 1 in the following theorem was originally proven by Fedja from MathOverflow, but the proof given is by Joseph Van Name (I was only able to see how quantum channels were related to \rho_{2,d} after reading Fedja’s proof).

Theorem: (J. Van Name) 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 the block matrix

A=\begin{bmatrix} A_{1,1} & \cdots & A_{1,m}  \\ \vdots & \ddots & \vdots  \\ A_{m,1} & \dots & A_{m,m} \end{bmatrix}.

Then

  1. \rho(A)^2\leq\min(d,m)\cdot\rho_2((A_{i,j})_{i,j})^2.

2. For all d,m, the matrices A_{i,j} can be chosen such that \rho(A)^2=\min(d,m)\cdot\rho_2((A_{i,j})_{i,j})^2>0.

3. If \rho(A)^2=\min(d,m)\cdot\rho_2((A_{i,j})_{i,j})^2 and d\leq m, then \text{Rank}(A_{i,j})\leq 1 for each i,j.

4. Let \Omega_m\in C(\mathbb{C}^m) denote the complete depolarizing channel. Then \rho_{2,d}(\Omega_m)=\frac{\min(d,m)}{m}.

Proof:

If A is an md\times md-complex matrix, then let (A_{i,j})_{i,j}\in M_d(\mathbb{C})^{m\times m} be the system of submatrices so that

A=\begin{bmatrix} A_{1,1} & \cdots & A_{1,m}  \\ \vdots & \ddots & \vdots  \\ A_{m,1} & \dots & A_{m,m} \end{bmatrix}.

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 O which are pre-trace preserving. Let E^\uparrow (resp O^\uparrow) be the collection of all A\in M_{md}(\mathbb{C}) where (A_{i,j})_{i,j}\in E (resp (A_{i,j})_{i,j}\in O).

Suppose that C is an md\times md-matrix where (C_{i,j})_{i,j} is a quantum channel. Then

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

Therefore, \rho(C)^2\leq\|C\|_\infty^2\leq\|C\|_2^2\leq d. Furthermore, if \rho(C)^2=d, then \|C\|_\infty=\|C\|_2, and this is only possible if \text{Rank}(C)\leq 1.

  1. Suppose now that (A_{i,j})_{i,j}\in E. Then there is a complex number \lambda and an invertible B where \Phi((\lambda BA_{i,j}B^{-1})_{i,j}) is a quantum channel. Suppose now that C is the md\times md matrix with C_{i,j}=\lambda BA_{i,j}B^{-1} for each i,j. In this case,

\frac{\rho(A)^2}{\rho(\Phi(A_{i,j})_{i,j})}=\frac{\rho(C)^2}{\rho(\Phi(C_{i,j}))}=\phi(C)\leq d. Furthermore, if (A_{i,j})_{i,j}\in E and \rho(A)^2=d\cdot\rho(\Phi((A_{i,j})_{i,j})), then \text{Rank}(C)\leq 1, so \text{Rank}(A)\leq 1 as well. Since E is dense in 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\in M_{md}(\mathbb{C}).

2. Let A_{i,j}=0 if i>d or j>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 0. In this case, we have \rho(A)^2=\min(d,m)\cdot\rho_2((A_{i,j})_{i,j})^2>0.

3. We shall now define functions f:O^\uparrow\rightarrow\mathbb{R} and g:O^\uparrow\rightarrow\mathbb{R}. Let f(A)=\frac{\rho(A)^2}{\rho(\Phi((A_{i,j})_{i,j}))} whenever A\in O^\uparrow and g(A)=\frac{|\lambda_2^2|}{\rho(\Phi((A_{i,j})_{i,j}))} where \lambda_1,\dots,\lambda_{md} are the eigenvalues of A ordered so that |\lambda_1|\geq|\lambda_2|\geq\dots\geq|\lambda_{md}|. Observe that if A\in O^\uparrow, then g(A)=0 precisely when \text{Rank}(A)\leq 1.

Now suppose that f(A)=d\leq m. Then let \delta>0. Then there is some \epsilon>0 where if \|A-H\|_2<\epsilon and H\in O^\uparrow, then f(H)>d-\delta. Now select a matrix H\in E^\uparrow with \|A-H\|_2<\epsilon. Then f(H)>d-\delta. Therefore, there is some B and \lambda>0 where if C is the md\times md matrix with C_{i,j}=\lambda BH_{i,j}B^{-1} for each i,j, then \Phi((C_{i,j})_{i,j}) is a quantum channel. Therefore, we have f(C)=f(H)>d-\delta.

Thus, d-\delta<\rho(C)^2\leq\|C\|_\infty^2\leq\|C\|_2^2\leq d. Let \lambda_1,\dots,\lambda_{md} be the eigenvalues of C ordered such that |\lambda_1|\geq\dots\geq|\lambda_{md}|. Then d-\delta\leq|\lambda_1|^2\leq|\lambda_1|^2+|\lambda_2|^2\leq\|C\|_2^2\leq d. Therefore, d-\delta+|\lambda_2|^2\leq d, so |\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, so g(A)=0 which means that \text{Rank}(A)\leq 1.

4. Let C_{i,j} be the m\times m-matrix where all entries in C_{i,j} are zero except for the (i,j)-th entry, and where the (i,j)-th entry in C_{i,j} is 1. Observe that \Omega_m=\Phi((C_{i,j})_{i,j}/\sqrt{m}) and if A is a dm\times dm-matrix, then A=\sum_{i,j}A_{i,j}\otimes C_{i,j}. Therefore, \min(d,m)=\max_{A\in O^\uparrow}\frac{\rho(A)^2}{\rho_2((A_{i,j})_{i,j})^2}=\rho_{2,d}((C_{i,j})_{i,j})^2, so \rho_{2,d}(\Omega_m)=\frac{\min(m,d)}{m}.

Q.E.D.

Let V be an inner product space. Then (e_k)_{k\in K} is said to be a frame if there are 0<\alpha<\beta<\infty with \alpha\|x\|^2\leq\sum_{k\in K}|\langle x,e_k\rangle|^2\leq\beta\|x\|^2 for all x\in V. If \alpha=\beta, then we say that the frame (e_k)_{k\in K} is a tight frame. In other words, (e_k)_{k\in K} is a tight frame if \alpha\|x\|^2=\sum_{k\in K}|\langle x,e_k\rangle|^2 for all x\in V. We observe that (e_k)_{k\in K} is a tight frame precisely when \sum_{k\in K}e_ke_k^*=\alpha\cdot 1. An equal-norm tight frame is a tight frame (e_k)_{k\in K} where \|e_j\|=\|e_k\| for all j,k.

Lemma: Suppose that F is either the field of real or complex numbers. There exists an equal-norm tight frame (v_1,\dots,v_n) for the inner product space V=F^d.

See Corollary 7.1 in the book An Introduction to Finite Tight Frames by Shayne F. D. Waldron for a proof of the above lemma.

Lemma: (Weyl’s inequality) Suppose that X is a d\times d-matrix with eigenvalues \lambda_1,\dots,\lambda_d and singular values \sigma_1,\dots,\sigma_d ordered such that |\lambda_1|\geq|\lambda_2|\geq\dots\geq|\lambda_d| and \sigma_1\geq\dots\geq\sigma_d. Then \prod_{k=1}^{m}|\lambda_k|\leq\prod_{k=1}^{m}\sigma_k whenever 1\leq m\leq d.

Let r be a natural number. Let C_1,\dots,C_r be the matrices where C_i=(\delta_{(j,k),(i,i+1)})_{j,k} such that \delta refers to the Kronecker delta function and where the addition is taken modulo r. Then \rho(C_1\otimes X_1+\dots+C_r\otimes X_r)=\rho(X_1\dots X_r)^{1/r}. Therefore, \rho_{2,d}(C_1,\dots,C_r) is the maximum value of \frac{\rho(X_1\dots X_r)^{1/r}}{\Phi(X_1,\dots,X_r)^{1/2}} where (X_1,\dots,X_r)\in M_d(\mathbb{C})^{r++}.

Theorem: (J. Van Name) Suppose that 1\leq d\leq r.

  1. \rho(X_1\dots X_r)^{2/r}\leq\frac{d}{r}\cdot\rho(\Phi(X_1,\dots,X_r)) whenever X_1,\dots,X_r\in M_d(\mathbb{C}).

2. If X_1,\dots,X_r\in M_d(\mathbb{C}) are matrices such that \frac{\rho(X_1\dots X_r)^{2/r}}{\rho(\Phi(X_1,\dots,X_r))}=d/r, then \text{Rank}(X_j)=1 for 1\leq j\leq r.

3. Suppose (Z_1,\dots,Z_r) are matrices. Then the following are equivalent:

i. \Phi(Z_1,\dots,Z_r) is a quantum channel with \rho(Z_1\dots Z_r)^{2/r}=d/r.

ii. there is an equal-norm tight frame (w_1,\dots,w_r) with \|w_j\|_2^2=d/r for 1\leq j\leq r and \alpha_j,\beta_j with |\alpha_j\beta_j|^2=r/d for 1\leq j\leq r where if v_j=\alpha_jw_j,u_{j+1}=\beta_{j+1}w_j, then Z_j=u_jv_j^* for 1\leq j\leq r.

4. There are real d\times d-matrices X_1,\dots,X_r such that \Phi(X_1,\dots,X_r) is a quantum channel and \rho(X_1\dots X_r)^{2/r}=d/r.

5. Let C_1,\dots,C_r be the matrices in the above example. Then \rho_{2,d}(C_1,\dots,C_r)=\rho_{2,d}(\Delta^S)=\rho_{2,d}^R(C_1,\dots,C_r)=\sqrt{d/r}.

Proof:

  1. Suppose that Z_1,\dots,Z_r\in M_d(\mathbb{C}) and \Phi(Z_1,\dots,Z_r) is a quantum channel. Then d=\text{Tr}(1_d)=\text{Tr}(Z_1^*Z_1+\dots+Z_r^*Z_r)=\|Z_1\|_2^2+\dots+\|Z_r\|_2^2.

Therefore, by the arithmetic-geometric mean inequality, we have

\rho(Z_1\dots Z_r)^{2/r}\leq\|Z_1\dots Z_r\|_\infty^{2/r}\leq(\|Z_1\|^2_\infty\dots\|Z_r\|^2_\infty)^{1/r}

\leq (\|Z_1\|^2_2\dots\|Z_r\|^2_2)^{1/r}\leq\frac{\|Z_1\|_2^2+\dots+\|Z_r\|_2^2}{r}=\frac{d}{r}=\frac{d}{r}\rho(\Phi(Z_1,\dots,Z_r)).

Therefore, if \lambda is a complex number, A is a complex matrix, and Z_j=\lambda AX_jA^{-1} for 1\leq j\leq r, then \frac{\rho(X_1\dots X_r)^{2/r}}{\rho(\Phi(X_1,\dots,X_r))}=\frac{\rho(Z_1\dots Z_r)^{2/r}}{\rho(\Phi(Z_1,\dots,Z_r))}\leq\frac{d}{r}. Therefore, \rho(X_1\dots X_r)^{2/r}\leq\frac{d}{r}\cdot\rho(\Phi(X_1,\dots,X_r)) whenever (X_1,\dots,X_r) is pre-trace preserving. We conclude that \rho(X_1\dots X_r)^{2/r}\leq\frac{d}{r}\cdot\rho(\Phi(X_1,\dots,X_r)) for all (X_1,\dots,X_r)\in M_d(\mathbb{C})^r by continuity since the pre-trace preserving maps are dense in M_d(\mathbb{C})^r whenever r>1.

2. If Z_1,\dots,Z_r\in M_d(\mathbb{C}), and \Phi(Z_1,\dots,Z_r) is a quantum channel with \rho(Z_1\dots Z_r)^{2/r}=\frac{d}{r}\rho(\Phi(Z_1,\dots,Z_r)), then \|Z_j\|_\infty^2=\|Z_j\|_2^2=d/r for all j which implies that \text{Rank}(Z_j)=1 for 1\leq j\leq r. By applying continuity, we shall show that if X_1,\dots,X_r\in M_d(\mathbb{C}), and \rho(X_1\dots X_r)^{2/r}=\frac{d}{r}\rho(\Phi(X_1,\dots,X_r)), then \text{Rank}(X_j)=1 for 1\leq j\leq r.

Let E_{d,r} be the collection of all tuples (X_1,\dots,X_r)\in M_{d}(\mathbb{C})^r which are pre-trace preserving. Let f:M_{d}(\mathbb{C})^{r++}\rightarrow\mathbb{R} be the mapping defined by f(X_1,\dots,X_r)=\frac{\rho(X_1\dots X_r)^{2/r}}{\rho(\Phi(X_1,\dots,X_r))}.

Let g^{-}:M_d(\mathbb{C})\rightarrow\mathbb{R} be the mapping where g^-(X)=|\lambda_1\lambda_2| where \lambda_1,\dots,\lambda_d are the eigenvalues of X ordered in such a way so that |\lambda_1|\geq|\lambda_2|\geq\dots\geq|\lambda_d|. Let g:O_{d,r}\rightarrow\mathbb{R} be the mapping defined by letting g(X_1,\dots,X_r)=\frac{g^-(X_1)+\dots+g^-(X_r)}{r\cdot\rho(\Phi(X_1,\dots,X_r))}.

Suppose now that (X_1,\dots,X_r)\in O_{d,r} and suppose that f(X_1,\dots,X_r)=d/r. Then for each \delta>0, there is a neighborhood U of (X_1,\dots,X_r) where if (Y_1,\dots,Y_r)\in U, then f(Y_1,\dots,Y_r)>d/r-\delta. Therefore, select a (Y_1,\dots,Y_r)\in U\cap E_{d,r}. Then there is some \lambda\neq 0 and invertible B where if we set Z_j=\lambda BY_jB^{-1}, then \Phi(Z_1,\dots,Z_r) is a quantum channel. Now, for 1\leq j\leq r, let \lambda_{j,1},\dots,\lambda_{j,d} be the eigenvalues of Z_j and suppose that these eigenvalues are ordered in a way so that |\lambda_{j,1}|\geq|\lambda_{j,2}|\geq\dots\geq|\lambda_{j,d}|. Then

\frac{d}{r}-\delta<f(Y_1,\dots,Y_r)=f(Z_1,\dots,Z_r)=\rho(Z_1\dots Z_r)^{2/r}

\leq\frac{\|Z_1\|_\infty^2+\dots+\|Z_r\|_\infty^2}{r}=\frac{\sigma_{1,1}^2+\dots+\sigma_{r,1}^2}{r}\leq \frac{(\sigma_{1,1}^2+\sigma_{1,2}^2)+\dots+(\sigma_{r,1}^2+\sigma_{r,2}^2)}{r}\leq\frac{\|Z_1\|_2^2+\dots+\|Z_r\|_2^2}{r}=\frac{d}{r}.

Therefore, we conclude that \sigma_{j,1}^2\leq\frac{d}{r} and \sigma_{j,2}^2\leq\delta. We conclude that g(Y_1,\dots,Y_r)=g(Z_1,\dots,Z_r)\leq \sum_{j=1}^{r}\frac{1}{r}\cdot\lambda_{j,1}\lambda_{j,2}\leq\sum_{j=1}^{r}\frac{1}{r}\cdot\sigma_{j,1}\sigma_{j,2}\leq\sqrt{\frac{d\delta}{r}}. Therefore, g(X_1,\dots,X_r)=0, so \text{Rank}(X_j)=0 for 1\leq j\leq r.

3. \rightarrow Suppose that \Phi(Z_1,\dots,Z_r) is a quantum channel and \rho(Z_1\dots Z_r)^{2/r}=\frac{d}{r}=\frac{d}{r}\rho(\Phi(Z_1,\dots,Z_r)). Then since \text{Rank}(Z_j)\leq 1, there are vectors u_j,v_j with Z_j=u_jv_j^* for 1\leq j\leq r. In this case, \|Z_j\|_2^2=\text{Tr}(u_jv_j^*(u_jv_j^*)^*)=\text{Tr}(u_jv_j^*v_ju_j^*) =\text{Tr}(v_j^*v_ju_j^*u_j)=\|u_j\|_2^2\cdot\|v_j\|_2^2. Therefore, \|Z_j\|_2=\|u_j\|\cdot\|v_j\|=\sqrt{d/r}.

Thus, \rho(Z_1\dots Z_r)=|\text{Tr}(Z_1\dots Z_r)|=|\text{Tr}(u_1v_1^*\dots u_rv_r^*)|

=|\text{Tr}(v_1^*u_2\dots v_r^*u_1)|=|\langle v_1,u_2\rangle\dots\langle v_r,u_1\rangle|.

Since \rho(Z_1\dots Z_r)=\|Z_1\|_\infty\dots\|Z_r\|_\infty, we have |\langle v_1,u_2\rangle\dots\langle v_r,u_1\rangle|=\|u_1\|\cdot\|v_1\|\cdots\|u_r\|\cdot\|v_r\|.

This means that there are non-zero constants \gamma_1,\dots,\gamma_r where v_j=\overline{\gamma_j}\cdot u_{j+1} for 1\leq j\leq r.

Now set, w_j=\|u_j\|\cdot v_j=\|u_j\|\cdot\overline{\gamma_j}u_{j+1}. Then 1_d=\sum_{j=1}^{r}Z_j^*Z_j=\sum_{j=1}^{r}(u_jv_j^*)^*u_jv_j^*=\sum_{j=1}^{r}v_ju_j^*u_jv_j^*=\sum_{j=1}^{r}\|u_j\|^2\cdot v_jv_j^*=\sum_{j=1}^{r}w_jw_j^*. Observe that (w_1,\dots,w_r) is an equal-norm tight frame with \|w_j\|^2=d/r for all j. In this case, if we set \alpha_j,\beta_j so that v_j=\alpha_jw_j,u_{j+1}=\beta_{j+1}w_j, then \sqrt{d/r}=\|u_j\|\cdot\|v_j\|=\|\beta_jw_{j-1}\|\cdot\|\alpha_jw_j\|=|\beta_j\alpha_j|\cdot\|w_j\|^2=|\beta_j\alpha_j|\cdot d/r. Therefore, we have |\alpha_j\beta_j|=\sqrt{r/d}.

\leftarrow Now suppose that (w_1,\dots,w_r) is an equal-norm tight frame with \|w_j\|_2^2=d/r for 1\leq j\leq r and \alpha_j,\beta_j with |\alpha_j\beta_j|^2=r/d for 1\leq j\leq r where if v_j=\alpha_jw_j,u_{j+1}=\beta_{j+1}w_j, then Z_j=u_jv_j^* for 1\leq j\leq r.

Then \sum_{j=1}^rZ_j^*Z_j=\sum_{j=1}^r(u_jv_j^*)^*u_jv_j^*=\sum_{j=1}^rv_ju_j^*u_jv_j^* =\sum_{j=1}^{r}\|u_j\|^2\cdot v_jv_j^*=\sum_{j=1}^r\|\beta_jw_{j-1}\|^2(\alpha_jw_j)(\alpha_jw_j)^*=\sum_{j=1}^{r}|\beta_j|^2\cdot\frac{d}{r}|\alpha_j|^2w_jw_j^* =\sum_{j=1}^{r}w_jw_j^*=1_d.

Q.E.D.

Miscellaneous examples

Here are a few examples of where we give bounds for \rho_{2,d}.

Example: (J. Van Name). Suppose that \mathcal{E}:L(V)\rightarrow L(V) is completely positive. Then \rho_{2,d}(\mathcal{E})^n\leq\rho_{2,d}(\mathcal{E}^n).

Proof: Suppose that (A_1,\dots,A_r) are matrices with \mathcal{E}(X)=\sum_{k=1}^{r}A_kXA_k^* whenever X\in L(X). Let B_1,\dots,B_r be d\times d-matrices where \Phi(B_1,\dots,B_r) is a quantum channel and \rho(A_1\otimes B_1+\dots+A_r\otimes B_r)=\rho_{2,d}(A_1,\dots,A_r).

In this case, \Phi((B_{i_1}\dots B_{i_n})_{i_1,\dots,i_n\in\{1,\dots,r\}})=\Phi(B_1,\dots,B_r)^n, so \Phi((B_{i_1}\dots B_{i_n})_{i_1,\dots,i_n\in\{1,\dots,r\}}) is a quantum channel. However, we have

\rho(\sum_{i_1,\dots,i_n}A_{i_1}\dots A_{i_n}\otimes B_{i_1}\dots B_{i_n})=\rho(A_1\otimes B_1+\dots+A_r\otimes B_r)^n=\rho_{2,d}(A_1,\dots,A_r)^n.

Therefore, \rho_{2,d}(A_1,\dots,A_r)^n\leq \rho((A_{i_1}\dots A_{i_n})_{i_1,\dots,i_n\in\{1,\dots,r\}}). Therefore, \rho_{2,d}(\mathcal{E})^n\leq\rho_{2,d}(\mathcal{E}^n).

Q.E.D.

For the next example, observe that tensor products behave well with regards to the Frobenius norm. Here, \langle A\otimes B,C\otimes D\rangle=\langle A,C\rangle\cdot\langle B,D\rangle whenever A,B,C,D are complex matrices where the formula makes sense. In particular, if A,C are orthogonal, then A\otimes B,C\otimes D are also orthogonal.

Example: (J. Van Name) Suppose that A_1,\dots,A_r are n\times n-complex matrices. Then \rho_{2,d}(\alpha I,\beta A_1,\dots,\beta A_r)^2\leq |\alpha|^2+|\beta|^2\cdot \rho_{2,d}(A_1,\dots,A_r)^2.

Proof: Suppose that B_1,\dots,B_r are d\times d-complex matrices where \Phi(B_1,\dots,B_r) is a quantum channel and A_1\otimes B_1+\dots+A_r\otimes B_r has \lambda as an eigenvalue with |\lambda|=\rho_{2,d}(A_1,\dots,A_r).

Suppose now that |\gamma|^2+|\delta|^2=1. Then \Phi (\gamma I,\delta B_1,\dots,\delta B_r) is a quantum channel, and

\alpha I\otimes \gamma I+\beta A_1\otimes \delta B_1+\dots+\beta A_r\otimes \delta B_r=\alpha\gamma I+\beta\delta(A_1\otimes B_1+\dots+A_r\otimes B_r), and \alpha I\otimes \gamma I+\beta A_1\otimes \delta B_1+\dots+\beta A_r\otimes \delta B_r has \alpha\gamma+\beta\delta\lambda as an eigenvalue. |\alpha\gamma+\beta\delta\lambda| is maximized subject to |\gamma|^2+|\delta|^2=1 when \gamma=\frac{\overline{\alpha}}{\sqrt{|\alpha|^2+|\beta\lambda|^2}},\delta=\frac{\overline{\beta\lambda}}{\sqrt{|\alpha|^2+|\beta\lambda|^2}}. In this case, we have \alpha\gamma+\beta\delta\lambda=\sqrt{|\alpha|^2+|\beta\lambda|^2}. Therefore, \rho_{2,d}(\alpha I,\beta A_1,\dots,\beta A_r)^2\leq |\alpha|^2+|\beta|^2\cdot \rho_{2,d}(A_1,\dots,A_r)^2. Q.E.D.

We conjecture that \rho_{2,d}(\alpha I,\beta A_1,\dots,\beta A_r)^2=|\alpha|^2+|\beta|^2\cdot \rho_{2,d}(A_1,\dots,A_r)^2.

Proposition: (J. Van Name) Suppose that A:V\rightarrow V\otimes W is a linear operator. Then \rho_{2,d}(A)^2\leq d\cdot\inf_{C\in GL(V)}\max_{w\in W,\|w\|=1}\|(C\otimes w^*)AC^{-1}\|_2^2.

Proof: The mapping [v,u]\mapsto\langle (1\otimes u^*)A,(1\otimes v^*)A\rangle is a positive semidefinite sesquilinear form. Therefore, there is a positive semidefinite P\in L(W) such that \langle Pv,u\rangle=\langle (1\otimes u^*)A,(1\otimes v^*)A\rangle. Since P\in L(W) is positive semidefinite, there is a basis (e_1,\dots,e_r) for W and non-negative \sigma_1,\dots,\sigma_r with P=\sum_{k=1}^r\sigma_ke_ke_k^*. Now set A_j=(1\otimes e_j^*)A for 1\leq j\leq r. In this case, we have \rho_{2,d}(A)=\rho_{2,d}(A_1,\dots,A_r). Now,

\langle A_j,A_k\rangle=\langle (1\otimes e_j^*)A,(1\otimes e_k^*)A\rangle=\langle Pe_k,e_j\rangle=0 whenever j\neq k. Furthermore,

\|A_j\|_2^2=\langle (1\otimes e_j^*)A,(1\otimes e_j^*)A\rangle=\langle Pe_j,e_j\rangle=\sigma_j.

Suppose now that \Phi(B_1,\dots,B_r) is a quantum channel. Then

\rho(A_1\otimes B_1+\dots+A_r\otimes B_r)^2\leq \|A_1\otimes B_1+\dots+A_r\otimes B_r\|_2^2=\|A_1\otimes B_1\|_2^2+\dots+\|A_r\otimes B_r\|_2^2=\|A_1\|_2^2\cdot\|B_1\|_2^2+\dots+\|A_r\|_2^2\cdot\|B_r\|_2^2

\leq d\cdot(\max(\|A_1\|_2^2,\dots,\|A_r\|_2^2))\leq d\cdot\max(\sigma_1,\dots,\sigma_r)=d\cdot\|P\|_\infty. Therefore,

\rho_{2,d}(A)^2=\rho_{2,d}(A_1,\dots,A_r)^2\leq d\cdot\|P\|_\infty=d\cdot\max_{w\in W,\|w\|=1}\|(1\otimes w^*)A\|_2^2.

We conclude that \rho_{2,d}(A)^2\leq d\cdot\inf_{C\in GL(V)}\max_{w\in W,\|w\|=1}\|(C\otimes w^*)AC^{-1}\|_2^2. Q.E.D.

Conclusions

We have seen that there are many different sensible notions of a spectral radius of multiple operators, but in many regards, the L_2-spectral radius seems to be the correct way to generalize the spectral radius to multiple operators, and the L_{2,d}-spectral radius seems to be a sensible approximation to the L_2-spectral radius.

While we have produced a few basic results that initially develop the theory of the L_{2,d}-spectral radius, computer calculations indicate that the pure mathematical theory of the L_{2,d}-spectral radius can be developed much further. In particular, if A\in L(V,V\otimes W),X\in L(U,U\otimes W) with \dim(U)\leq\dim(V), and \rho_{2,d}(A)=\frac{\rho(\Gamma(A,X))}{\rho_{2}(X)}, then our computer calculations suggest that the linear operator X seems to be unique up to simultaneous similarity in most cases, and X seems to inherit at least to some extent many of the properties that A has including rank, realness, symmetry, self-adjointness, positivity, unitarity, etc. One should therefore consider the operator X as an operator obtained by reducing the dimension of the space V to obtain the space U while preserving the properties of A in the best possible way.

The L_{2,d}-spectral radius is a mathematical function that should therefore be of interest to pure mathematicians for purely mathematical and aesthetic reasons, but we will apply the L_{2,d}-spectral radius to measure the cryptographic security of block ciphers. The pure mathematical nature of the L_{2,d}-spectral radius should make the L_{2,d}-spectral radius a more appealing measure of security of block ciphers. In a future post, we shall see that the L_{2,d}-spectral radius can be used to measure aspects of cryptographic security of block ciphers.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: