11 Wielandt Bound
This chapter proves the quantum Wielandt bounds of [ SPGWC10 ] . For a primitive normalized tensor, it compares the uniform vector-spreading index \(q(\mathcal{E}_A)\) with the first exact word length \(\iota (A)\) satisfying \(S_{\iota (A)}(A)=M_{D}(\mathbb {C})\) and proves \(\iota (A)\le (D^2-\operatorname{kr}(A)+1)D^2\). The cumulative bound \(T_{D^2}(A)=M_{D}(\mathbb {C})\) is an intermediate step in the proof of Lemma 1.
11.1 Cumulative span
The exact-word identities used in this section are proved in Section 11.6. The stabilization and spectral linear algebra behind the cumulative estimates are collected in Section 11.7.
Let \(K=\{ K^i\} _{i=0}^{d-1}\) be a finite family of \(D\times D\) matrices. For a word \(w=(i_1,\ldots ,i_n)\), its word evaluation is
with the empty word evaluated as the identity matrix.
The fixed-length vector span at length \(n\) is
This is \(S_n(K)|\varphi \rangle \) in the notation of [ SPGWC10 ] .
11.1.1 Paper primitivity and indices
For the quantitative bounds, write \(d'=\dim S_1(A)\) for the number of linearly independent Kraus operators. The source definitions and Proposition 3 of [ SPGWC10 ] distinguish uniform vector spreading, eventual exact-word spanning, and spectral strong irreducibility.
The next seven results use the following notation. For nonnegative integers \(d\) and \(D\), let \(K=\{ K^i\} _{i=0}^{d-1}\) be a finite family of \(D\times D\) matrices, and let \(\mathcal{E}_K\) be its Kraus map.
For every choice of \(d\), \(D\), and \(K\) as above, every \(q\ge 0\), and every \(\varphi \in \mathbb {C}^D\),
Expand the Kraus representation of the \(q\)-fold iterate. Each summand is \(K^w|\varphi \rangle \! \langle \varphi |(K^w)^\dagger =|K^w\varphi \rangle \! \langle K^w\varphi |\).
For every choice of \(d\), \(D\), and \(K\) as above and every \(q\ge 0\), suppose \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \in \mathbb {C}^D\). Then \(\mathcal{E}_K^q(|\varphi \rangle \! \langle \varphi |){\gt}0\) for every \(\varphi \neq 0\).
The preceding theorem expresses the image as the frame operator of the spanning family \((K^w\varphi )_{|w|=q}\). A finite frame operator is positive definite exactly when its vectors span the ambient space.
For every choice of \(d\), \(D\), and \(K\) as above and every \(n\ge 0\), the iterate \(\mathcal{E}_K^n\) maps positive-semidefinite matrices to positive-semidefinite matrices.
Decompose a positive-semidefinite matrix into a finite sum of rank-one positive matrices and apply Theorem 11.1.1.1 to every summand.
For every choice of \(d\), \(D\), and \(K\) as above and every \(q\ge 0\), suppose \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \). Then \(\mathcal{E}_K^q(\rho ){\gt}0\) for every nonzero positive-semidefinite matrix \(\rho \).
For every choice of \(d\), \(D\), and \(K\) as above and every \(q\ge 0\), suppose \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \). Then every nonzero positive-semidefinite fixed point of \(\mathcal{E}_K\) is positive definite.
A fixed point of \(\mathcal{E}_K\) is fixed by \(\mathcal{E}_K^q\), whose action on every nonzero positive-semidefinite matrix is positive definite.
For every choice of \(d\), \(D\), and \(K\) as above and every \(q\ge 0\), suppose \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \). For every \(p{\gt}0\), each nonzero positive-semidefinite fixed point of \(\mathcal{E}_K^p\) is positive definite.
If \(\mathcal{E}_K^p(\rho )=\rho \), then \(\mathcal{E}_K^{pq}(\rho )=\rho \). Factor this iterate as \(\mathcal{E}_K^q\mathcal{E}_K^{(p-1)q}\). The inner image is nonzero and positive semidefinite, so the outer application is positive definite.
For every choice of \(d\), \(D\), and \(K\) as above and every \(q\ge 0\), if \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \), then the Kraus map \(\mathcal{E}_K\) is irreducible.
Let \(P\) be an invariant orthogonal projection. Every word \(K^w\) preserves \(\operatorname {ran}P\). If \(P\neq 0\), choose a nonzero vector in this range. Its length-\(q\) word orbit spans \(\mathbb {C}^D\) by hypothesis and remains in \(\operatorname {ran}P\), hence \(P=\mathbb {1}\).
Let \(E:M_{D}(\mathbb {C})\to M_{D}(\mathbb {C})\) be positive. If \(E(X)=\mu X\), then \(E(X^\dagger )=\overline\mu X^\dagger \).
Positivity implies that \(E\) preserves adjoints. Taking the adjoint of \(E(X)=\mu X\) gives the result.
Let \(E:M_{D}(\mathbb {C})\to M_{D}(\mathbb {C})\) be linear. If \(E(X)=\mu X\) and \(\mu ^p=1\), then \(E^p(X)=X\).
Theorem 8.1.8 gives \(E^p(X)=\mu ^pX=X\).
Let \(E:M_{D}(\mathbb {C})\to M_{D}(\mathbb {C})\) be positive. If \(E(X)=\mu X\) and \(\mu ^p=1\), then \(E^p(X^\dagger )=X^\dagger \).
The conjugate eigenvalue is \(\overline\mu \), and \((\overline\mu )^p=\overline{\mu ^p}=1\).
Let \(E:M_{D}(\mathbb {C})\to M_{D}(\mathbb {C})\) preserve the trace. If \(E(X)=\mu X\) and \(\mu \neq 1\), then \(\operatorname{tr}(X)=0\).
Trace preservation gives \(\mu \operatorname{tr}(X)=\operatorname{tr}(E(X))=\operatorname{tr}(X)\). Since \(\mu -1\neq 0\), the trace vanishes.
Let \(E\) be a channel, and suppose \(E(X)=\mu X\) with \(X\neq 0\), \(\mu \neq 1\), and \(\mu ^p=1\). Then there is a nonzero Hermitian matrix \(H\) such that \(\operatorname{tr}(H)=0\) and \(E^p(H)=H\).
At least one of \(X+X^\dagger \) and \(i(X^\dagger -X)\) is nonzero. Both are Hermitian, both have trace zero, and each is fixed by \(E^p\).
Suppose \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \). If \(p{\gt}0\) and \(\rho ,\sigma \) are nonzero positive-semidefinite fixed points of \(\mathcal{E}_K^p\), then \(\sigma =c\rho \) for some \(c\in \mathbb {C}\).
Fixed-length spreading makes every nonzero positive-semidefinite fixed point of \(\mathcal{E}_K^p\) positive definite. The critical-scalar argument then gives proportionality.
If \(E\) is completely positive, then \(E^p\) is completely positive for every \(p\geq 0\).
Induct on \(p\), using complete positivity of the identity map at \(p=0\) and closure of completely positive maps under composition for the induction step.
If \(E\) is a channel, then \(E^p\) is a channel for every \(p\geq 0\).
Complete positivity and trace preservation are both closed under composition and hold for the identity map.
Let \(K\) be trace-preserving and suppose \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \). If \(p{\gt}0\) and \(H=H^\dagger \) satisfies \(\operatorname{tr}(H)=0\) and \(\mathcal{E}_K^p(H)=H\), then \(H=0\).
Decompose \(H\) as a difference of positive-semidefinite fixed points of the channel \(\mathcal{E}_K^p\). Both are proportional to one nonzero fixed point. Their traces and \(\operatorname{tr}(H)=0\) force equal coefficients, hence \(H=0\).
Let \(D{\gt}0\), and let \(K=\{ K^i\} _{i=0}^{d-1}\) be a finite family of \(D\times D\) matrices satisfying
Suppose there is a common length \(q\ge 0\) such that \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \in \mathbb {C}^D\). Then there is a positive-definite matrix \(\rho \) such that \(\mathcal{E}_K(\rho )=\rho \).
Let \(D{\gt}0\), and let \(K=\{ K^i\} _{i=0}^{d-1}\) be a finite family of \(D\times D\) matrices satisfying
Suppose there is a common length \(q\ge 0\) such that \(H_q(K,\varphi )=\mathbb {C}^D\) for every nonzero \(\varphi \in \mathbb {C}^D\). Then the Kraus map \(\mathcal{E}_K\) is primitive: it has a nonzero fixed point and \(1\) is its only peripheral eigenvalue.
The normalization makes \(\mathcal{E}_K\) a channel, so Theorem 8.1.20 gives a nonzero positive-semidefinite fixed point. This supplies the peripheral eigenvalue \(1\). Theorem 11.1.1.7 gives irreducibility. Thus \(\mathcal{E}_K\) is an irreducible channel. By Theorem 2.13.2.7, every peripheral eigenvalue \(\mu \) is a root of unity; choose \(p{\gt}0\) with \(\mu ^p=1\).
Suppose \(\mu \neq 1\). Theorem 11.1.1.12 gives a nonzero Hermitian matrix \(H\) with \(\operatorname{tr}(H)=0\) and \(\mathcal{E}_K^p(H)=H\). Theorem 11.1.1.16 gives \(H=0\), a contradiction. Thus \(\mu =1\).
11.2 Nonzero trace product
Let \(T_N(K)\) be the span of the products of at most \(N\) matrices from a finite family \(K\). If \(D{\gt}0\) and \(T_N(K)=M_{D}(\mathbb {C})\), then there are a word \(w\), a nonzero scalar \(\mu \), and a nonzero vector \(\varphi \in \mathbb {C}^D\) such that
Since the identity lies in \(T_N(K)\) and has nonzero trace, some word of length at most \(N\) has nonzero trace. Such a matrix has a nonzero eigenvalue and a corresponding nonzero eigenvector by Theorem 11.7.4.
11.3 Eigenvector spreading
Let \(K=\{ K^i\} _{i=0}^{d-1}\) be a finite family of \(D\times D\) matrices, where \(D{\gt}0\), and let \(\varphi \neq 0\). If, for some \(N\), words in \(K\) of length at most \(N\) span \(M_{D}(\mathbb {C})\), then the vectors \(K^w\varphi \) with \(|w|\leq D-1\) span \(\mathbb {C}^D\).
The cumulative vector spaces are monotone and have dimension at most \(D\). Once two consecutive spaces agree, the common space is invariant under every \(K^i\). Full cumulative matrix span then forces it to contain \(M_{D}(\mathbb {C})\varphi =\mathbb {C}^D\). Since the initial space is nonzero, it reaches dimension \(D\) by step \(D-1\).
Suppose \(K^{i_0}\varphi =\mu \varphi \) with \(\mu \neq 0\). For every \(n\), the span of \(K^w\varphi \) over words with \(|w|\leq n\) equals \(H_n(K,\varphi )\).
Repeating the letter \(i_0\) pads a word of length \(m\leq n\) to length \(n\). Its action on \(\varphi \) gains the nonzero factor \(\mu ^{n-m}\), so every shorter-word vector belongs to the fixed-length span. The reverse inclusion is immediate.
Let \(K=(K^i)_{i=0}^{d-1}\) be a finite family of \(D\times D\) matrices, where \(D{\gt}0\), and suppose that \(S_n(K)=M_{D}(\mathbb {C})\) for every sufficiently large \(n\). If \(\varphi \neq 0\), \(\mu \neq 0\), and \(K^{i_0}\varphi =\mu \varphi \), then \(H_{D-1}(K,\varphi )=\mathbb {C}^D\).
Eventual fullness gives a level at which the cumulative matrix span is all of \(M_{D}(\mathbb {C})\). The cumulative vector spaces therefore reach \(\mathbb {C}^D\) by level \(D-1\). The eigenvector relation then pads shorter words to length \(D-1\) by nonzero powers of \(\mu \).
11.4 Quantum Wielandt bounds
Section 11.8 proves the one-step augmentation facts used in cases (2) and (3). The blocking identities used in the general case are proved in Section 11.9.
11.5 Wielandt Bound
This section collects exact-word, cumulative-span, augmentation, blocking, complementary-gap, and one-step padding results used by the main quantitative argument earlier in this chapter.
11.6 Exact-word and block-injectivity support
If \(C\in M_{D}(\mathbb {C})\) is nonzero, then
This is the matrix-factorization input used in [ PGVWC07 , Lemma 3 ] .
Choose a nonzero entry \(C_{pq}\). Then every matrix unit \(E_{ij}\) is a scalar multiple of \(E_{ip}CE_{qj}\), so the span in (1) contains the standard matrix basis.
11.7 Cumulative-span and spectral linear algebra
The next two lemmas connect irreducible matrix actions with the cumulative word span used throughout Chapter 11.
A Fitting decomposition of a linear endomorphism \(f:V\to V\) on a finite-dimensional vector space over an algebraically closed field consists of:
\(f\) is nilpotent on the generalized \(0\)-eigenspace,
\(f\) is invertible on each generalized \(\mu \)-eigenspace for \(\mu \neq 0\),
the generalized eigenspaces span \(V\),
the generalized eigenspaces are linearly independent.
Every linear endomorphism on a finite-dimensional vector space over an algebraically closed field admits a Fitting decomposition.
Nilpotency on the zero generalized eigenspace follows from the definition of generalized eigenspaces. Invertibility on nonzero generalized eigenspaces follows because \(f-\mu \) is nilpotent there, so \(f=\mu (1-(1-f/\mu ))\) is invertible. Spanning and independence are standard results for generalized eigenspaces over algebraically closed fields. In [ SPGWC10 ] and [ Wol12 , Lemma 6.3(b) ] , the Jordan normal form is used directly. The argument is phrased in terms of generalized eigenspaces instead.
If \(f\) is nilpotent on a space of dimension \(n\), then \(f^n=0\).
A nilpotent endomorphism on an \(n\)-dimensional space has nilpotency index at most \(n\).
If \(M\in M_{D}(\mathbb {C})\) has \(\operatorname{tr}(M)\neq 0\), then \(M\) has a nonzero eigenvalue \(\mu \neq 0\) and a corresponding eigenvector \(\varphi \neq 0\) satisfying \(M\varphi =\mu \varphi \).
The trace is the sum of the eigenvalues of \(M\), counted with multiplicity, so a nonzero trace gives a nonzero eigenvalue \(\mu \). Choosing a nonzero vector \(\varphi \in \ker (M-\mu \mathbb {1})\) gives \(M\varphi =\mu \varphi \).
11.8 One-step augmentation
11.9 Blocking and fixed-length spanning
11.10 Complementary-gap consequences
11.11 Identity in the one-step span
In \(M_{2}(\mathbb {C})\), let \(A^0=E_{12}\) and \(A^1=E_{21}\) be the off-diagonal matrix units. Then \(\operatorname{alg}(A)=M_{2}(\mathbb {C})\) and \(T_2(A)=M_{2}(\mathbb {C})\), but the word spans alternate: \(S_n(A)\) contains only off-diagonal matrices for odd \(n\) and only diagonal matrices for even \(n\). Hence \(S_n(A)\neq M_{2}(\mathbb {C})\) for every \(n\), and \(A\) is not normal. The one-step padding condition fails because \(\mathbb {1}\notin S_1(A)=\operatorname{span}_{\mathbb {C}}\{ E_{12},E_{21}\} \).