C Wielandt Bound: Supporting Results
The quantitative Wielandt argument of Chapter 6 rests on structural properties of exact-word spans, cumulative spans, one-step augmentations, blocking, and complementary transfer-map gaps.
C.1 Exact-word and block-injectivity support
Exact-word products satisfy direct concatenation factorizations and dimension bounds in low dimensions.
One has \(S_m(A)S_n(A)\subseteq S_{m+n}(A)\): the product of word spans at lengths \(m\) and \(n\) is contained in the word span at length \(m+n\).
Every product \(A^{w_1}A^{w_2}\) with \(|w_1|=m\) and \(|w_2|=n\) equals \(A^{w_1w_2}\), where \(|w_1w_2|=m+n\).
For all \(m,n\geq 0\), one has \(S_{m+n}(A)=S_m(A)S_n(A)\).
For words \(w_1,w_2\) of lengths \(m,n\), concatenation satisfies
Split each word of length \(m+n\) after its first \(m\) letters for one inclusion, and concatenate words of lengths \(m\) and \(n\) for the other.
If \(D\ge 2\), then \(S_0(A)\neq M_{D}(\mathbb {C})\).
The zero-length products consist only of the identity, so \(S_0(A)=\operatorname{span}_{\mathbb {C}}\{ \mathbb {1}\} \) has dimension \(1\). Since \(\dim M_{D}(\mathbb {C})=D^2\ge 4\), this span cannot equal \(M_{D}(\mathbb {C})\).
If \(D\ge 1\) and \(A\) is \(0\)-block injective, then \(D=1\).
If \(A\) is \(L\)-block injective and \(X\neq 0\), then
By \(L\)-block injectivity, the length-\(L\) word products span \(M_{D}(\mathbb {C})\). Bilinearity of \((R,S)\mapsto RXS\) reduces the claim to Lemma [ 216 , “Two-sided span from one nonzero matrix” ] , with \(R\) and \(S\) chosen among those word products.
C.2 Cumulative-span and spectral linear algebra
Cumulative word spans form an ascending chain of subspaces whose stabilization is governed by finite dimensionality and Burnside’s theorem.
The next two lemmas connect irreducible matrix actions with the cumulative word span used throughout Chapter 6.
The passage from irreducible tensors to full algebra spanning first passes through the irreducible action on \(\mathbb {C}^D\). Burnside’s theorem then says that the resulting irreducible subalgebra of \(M_{D}(\mathbb {C})\) is all of \(M_{D}(\mathbb {C})\). Once the algebra span is full, finite-dimensionality gives a single cumulative span that already equals \(M_{D}(\mathbb {C})\).
If the letters of \(A\) act irreducibly on \(\mathbb {C}^D\), then \(A\) has no nontrivial invariant orthogonal projection.
If \(P\) were a nontrivial invariant orthogonal projection, then its range would be invariant under every letter of \(A\). Irreducibility of the action forces this range to be either \(0\) or all of \(\mathbb {C}^D\), so \(P\) must be \(0\) or \(\mathbb {1}\), a contradiction.
If the generated unital algebra satisfies \(\operatorname{alg}(A)=M_{D}(\mathbb {C})\), then there exists \(N\) such that \(T_N(A)=M_{D}(\mathbb {C})\).
Every element of \(\operatorname{alg}(A)\) lies in some cumulative span \(T_n(A)\): the generators lie in \(T_1(A)\), scalar multiples of the identity lie in \(T_0(A)\), and the family \(\{ T_n(A)\} _{n\ge 0}\) is closed under addition and under multiplication with lengths adding. Since \(M_{D}(\mathbb {C})\) is finite-dimensional, the ascending chain \(T_0(A)\subseteq T_1(A)\subseteq \cdots \) stabilizes, so one can choose a single \(N\) with \(T_N(A)=M_{D}(\mathbb {C})\).
Let \(D{\gt}0\). If \(A\) is normal, then \(T_{D^2}(A)=M_{D}(\mathbb {C})\).
By Theorem 6.1.1.22, if \(T_n\neq T_{n+1}\), then \(\dim T_{n+1}{\gt}\dim T_n\). Since \(\dim T_n\le D^2\) by Lemma 6.1.1.20, after at most \(D^2\) steps either \(T_n=M_{D}(\mathbb {C})\) or \(T_n\) has stabilised. Stabilisation before reaching \(M_{D}(\mathbb {C})\) contradicts normality, which requires \(S_{L_0}=M_{D}(\mathbb {C})\) for some \(L_0\) and hence \(T_{L_0}=M_{D}(\mathbb {C})\).
By Theorem 6.2.1, \(\mathbb {1}\in T_{D^2}(A)\), so \(\mathbb {1}\) is a linear combination of word products of length at most \(D^2\). At least one has nonzero trace because \(\operatorname{tr}(\mathbb {1})=D\neq 0\).
Let \(D{\gt}0\). If \(A\) is normal, then there exist a word \(w_0\) with \(|w_0|\le D^2\), a nonzero scalar \(\mu \neq 0\), and a nonzero vector \(\varphi \neq 0\) such that \(A^{w_0}\varphi =\mu \varphi \).
If \(K_n(A,\varphi )=K_{n+1}(A,\varphi )\), then \(K_m(A,\varphi )=K_n(A,\varphi )\) for every \(m\ge n\).
The argument is the same as for Theorem 6.1.1.21: left multiplication by \(A^i\) cannot escape the stabilised span.
If \(T_N(A)=M_{D}(\mathbb {C})\) and \(\varphi \neq 0\), then \(K_N(A,\varphi )=\mathbb {C}^D\).
Every matrix \(M\in M_{D}(\mathbb {C})\) lies in \(T_N(A)\), so in particular every rank-one matrix sending \(\varphi \) to any target vector \(v\) lies in \(T_N(A)\). Applying such matrices to \(\varphi \) recovers all of \(\mathbb {C}^D\).
C.3 One-step augmentation
Augmenting a Kraus family by a matrix already in its one-step span preserves all exact word spans while allowing the adjunction of an invertible generator or an eigenvector.
Let \(A\) be an MPS tensor with Kraus family \(\{ A^i\} _{i=0}^{d-1}\), and let \(X\in M_{D}(\mathbb {C})\). The one-step augmentation of \(A\) by \(X\) is the tensor \(\widetilde A\) with physical dimension \(d+1\) whose first Kraus operator is \(X\) and whose remaining Kraus operators are those of \(A\):
Every Kraus operator \(A^i\) belongs to the one-step span \(S_1(A)\).
This is the length-one word with letter \(i\).
Let \(X\in S_1(A)\), and let \(\widetilde A\) be the one-step augmentation of \(A\) by \(X\). Then \(S_n(\widetilde A)=S_n(A)\) for every \(n\ge 0\).
The new generator \(X\) is already in \(S_1(A)\), and each original generator remains in the augmented family. Hence the one-step spans agree. Multiplying word spans and arguing by induction on the word length gives equality at every length.
Let \(X\in S_1(A)\), and let \(\widetilde A\) be the one-step augmentation of \(A\) by \(X\). If \(A\) is normal, then \(\widetilde A\) is normal, and \(\operatorname{kr}(\widetilde A)=\operatorname{kr}(A)\).
Since all exact word spans are unchanged by Lemma C.3.3, eventual full word span for \(A\) gives eventual full word span for \(\widetilde A\). The equality of Kraus ranks is the equality of the dimensions of the common one-step span.
Let \(A\) be a normal MPS tensor with bond dimension \(D{\gt}0\), and suppose that some Kraus operator \(A^{i_0}\) is invertible. Then
The dimensions of the exact word spans cannot decrease, because left multiplication by the invertible Kraus operator is injective. If this dimension growth stopped before the full matrix algebra was reached, the same argument at every later length would contradict normality. Since \(\dim S_1(A)=\operatorname{kr}(A)\) and \(\dim M_{D}(\mathbb {C})=D^2\), the full algebra is reached by length \(D^2-\operatorname{kr}(A)+1\). The index bound follows from the definition of \(\iota (A)\).
Let \(A\) be an MPS tensor with bond dimension \(D\ge 1\), satisfying \(\sum _i(A^i)^\dagger A^i=\mathbb {1}\), and suppose that \(A\) is primitive in the sense of Definition 6.1.1.3. If some Kraus operator \(A^{i_0}\) is invertible, then
Apply the one-step case to \(X=A^{i_0}\), which belongs to \(S_1(A)\) by Lemma C.3.2.
Let \(A\) be an MPS tensor with bond dimension \(D\ge 1\), satisfying \(\sum _i(A^i)^\dagger A^i=\mathbb {1}\), and suppose that \(A\) is primitive in the sense of Definition 6.1.1.3. If some Kraus operator \(A^{i_0}\) is non-invertible and has an eigenvector \(\varphi \neq 0\) with nonzero eigenvalue \(\mu \), then
Apply the one-step case to \(X=A^{i_0}\), which belongs to \(S_1(A)\) by Lemma C.3.2.
C.4 Blocking and fixed-length spanning
Blocking preserves tensor normality and embeds exact word spans, allowing word eigenvectors to be transferred to single-index eigenvectors of blocked tensors.
If \(A\) is normal and \(L{\gt}0\), then the blocked tensor \(A^{[L]}\) is also normal.
Choose \(N\) with \(S_N(A)=M_{D}(\mathbb {C})\). Then \(\mathbb {1}\in S_N(A)\). For any \(M\in S_N(A)\), write \(\mathbb {1}=\sum _r c_rA^{w_r}\) with each \(|w_r|=N\). Then
By Lemma C.1.1, iterating (1) gives \(S_N(A)\subseteq S_{kN}(A)\) for every \(k\ge 1\). Taking \(k=L\) yields \(M_{D}(\mathbb {C})=S_N(A)\subseteq S_{NL}(A)\). By Lemma C.4.2, \(S_{NL}(A)\subseteq S_N(A^{[L]})\), so \(S_N(A^{[L]})=M_{D}(\mathbb {C})\).
One has \(S_{nL}(A)\subseteq S_n(A^{[L]})\) for all \(n,L\).
If \(A^{w_0}\varphi =\mu \varphi \) for a word \(w_0\) of length \(L\), then \((A^{[L]})^{j_0}\varphi =\mu \varphi \), where \(j_0\) is the encoded blocked index corresponding to \(w_0\).
By (18), \((A^{[L]})^{j_0}=A^{w_0}\).
Suppose \(A\) has bond dimension \(D{\gt}0\), is normal, and \(L{\gt}0\), and we have:
a word \(w_0\) of length \(L\) with eigenvector \(A^{w_0}\varphi =\mu \varphi \) (\(\mu \neq 0\), \(\varphi \neq 0\)),
a word \(\tau _0\) of length \(L\) with transpose eigenvector \((A^{\tau _0})^T\psi =\nu \psi \) (\(\nu \neq 0\), \(\psi \neq 0\)),
a rank-one element \(\varphi \psi ^T\in S_m(A^{[L]})\) for some \(m\).
Then there exists \(N\) such that \(S_N(A)=M_{D}(\mathbb {C})\).
Remark. The proof gives the explicit bound \(N=((D{-}1)+m+(D{-}1))L\); the theorem states only the existential conclusion.
Set \(B=A^{[L]}\), which is normal by Theorem C.4.1. The word eigenvectors transfer to single-index eigenvectors of \(B\) and \(B^T\) by Theorem C.4.3. Eigenvector spreading and padding then give \(H_{D-1}(B,\varphi )=H_{D-1}(B^T,\psi )=\mathbb {C}^D\).
For each standard basis vector \(e_j\), choose \(R_j\in S_{D-1}(B^T)\) with \(R_j\psi =e_j\). Reversing each word after transposition shows that \(R_j^T\in S_{D-1}(B)\), and therefore \((\varphi \psi ^T)R_j^T=\varphi e_j^T\) belongs to \(S_{m+D-1}(B)\). Theorem 6.5.2, applied with \(n=D-1\) and \(m'=m+D-1\), now gives \(S_{(D-1)+m+(D-1)}(B)=M_{D}(\mathbb {C})\). Finally, Lemma 6.5.4 transfers this identity to \(S_{((D-1)+m+(D-1))L}(A)=M_{D}(\mathbb {C})\).
Suppose \(A\) has bond dimension \(D{\gt}0\), is normal, and \(N_0\ge 1\) with \(S_{N_0}(A)=M_{D}(\mathbb {C})\). Then there exist words \(\sigma _0,\tau _0\) of length \(N_0\), nonzero vectors \(\varphi ,\psi \), nonzero scalars \(\mu ,\nu \), and \(m\in \mathbb {N}\) such that:
\(A^{\sigma _0}\varphi =\mu \varphi \),
\((A^{\tau _0})^T\psi =\nu \psi \),
\(\varphi \psi ^T\in S_m(A^{[N_0]})\).
Set \(B=A^{[N_0]}\). By (18) and \(S_{N_0}(A)=M_{D}(\mathbb {C})\), one has \(S_1(B)=M_{D}(\mathbb {C})\). Hence \(\mathbb {1}\in S_1(B)\), so not all blocked generators can have trace zero. Choose \(j_0\) with \(\operatorname{tr}(B^{j_0})\neq 0\). By Theorem [ 216 , “Nonzero trace implies eigenvector” ] , \(B^{j_0}\) has a nonzero eigenvector \(\varphi \) with eigenvalue \(\mu \neq 0\). Writing \(j_0\) as the blocked index corresponding to a word \(\sigma _0\) of length \(N_0\) gives \(A^{\sigma _0}\varphi =\mu \varphi \). Applying the same argument to the transpose blocked tensor gives a word \(\tau _0\) of length \(N_0\), a nonzero vector \(\psi \), and \(\nu \neq 0\) with \((A^{\tau _0})^T\psi =\nu \psi \). Since \(A\) is normal and \(N_0\ge 1\), the blocked tensor \(B\) is normal by Theorem C.4.1. Therefore there exists \(M\) with \(S_M(B)=M_{D}(\mathbb {C})\). In particular, \(\varphi \psi ^T\in S_M(B)\). Taking \(m=M\) proves (3).
C.5 Complementary-gap consequences
A strict spectral-radius bound on the complementary transfer map implies overlap convergence, non-vanishing of iterated transfer maps, and fixed-point uniqueness.
If \(A\) is a primitive MPS tensor, then \(O_{AA}(N)\to 1\).
The claim follows from the self-overlap convergence under a complementary transfer-map gap (Theorem 5.10.2).
Let \(A\) have positive bond dimension and satisfy \(\sum _i(A^i)^\dagger A^i=\mathbb {1}\). If \(A\) is tensor-irreducible and the transfer map is primitive, then \(O_{AA}(N)\to 1\).
Irreducible Perron–Frobenius theory supplies a nonzero positive fixed point. Peripheral primitivity gives a strict spectral-radius bound on the complementary transfer map. Thus \(A\) is a primitive MPS tensor, and Theorem C.5.1 applies.
If \(A\) is a primitive MPS tensor, then for every \(n\ge 0\) there exists a word \(w\) of length exactly \(n\) with \(A^w\neq 0\).
The PSD fixed point \(\rho \) of \(\mathcal{E}_A\) satisfies \(\mathcal{E}_A^n(\rho )=\rho \neq 0\). Since \(\mathcal{E}_A^n(\rho )=\sum _{|w|=n}A^w\rho (A^w)^\dagger \), at least one summand is nonzero, hence some \(A^w\neq 0\).
If \(A\) is a primitive MPS tensor, then \(\mathcal{E}_A^n\neq 0\) for all \(n\ge 0\).
By Lemma C.5.3, there exists a word \(w\) of length \(n\) with \(A^w\neq 0\). The expansion \(\mathcal{E}_A^n(\mathbb {1})=\sum _{|u|=n}A^u(A^u)^\dagger \) contains the nonzero positive semidefinite summand \(A^w(A^w)^\dagger \), so \(\mathcal{E}_A^n(\mathbb {1})\neq 0\).
If \(A\) is a primitive MPS tensor with PSD fixed point \(\rho \), then every fixed point \(\sigma \) of \(\mathcal{E}_A\) is proportional to \(\rho \): \(\sigma =\frac{\operatorname{tr}(\sigma )}{\operatorname{tr}(\rho )}\rho \).
Set \(\sigma '=\sigma -\frac{\operatorname{tr}(\sigma )}{\operatorname{tr}(\rho )}\rho \). Then \(\operatorname{tr}(\sigma ')=0\) and \((\mathcal{E}_A-P_\rho )(\sigma ')=\sigma '\). If \(\sigma '\neq 0\), then \(1\) is an eigenvalue of \(\mathcal{E}_A-P_\rho \), contradicting the complementary transfer-map gap \(\rho _{\operatorname{spec}}(\mathcal{E}_A-P_\rho ){\lt}1\).
If \(A\) is a primitive MPS tensor with PSD fixed point \(\rho \), then \((\mathcal{E}_A-P_\rho )^n\to 0\) in operator norm.
The spectral radius of \(\mathcal{E}_A-P_\rho \) is strictly less than \(1\) by the complementary transfer-map gap hypothesis. Apply the general result that powers of an operator with spectral radius \({\lt}1\) tend to zero.
If \(A\) is a primitive MPS tensor with positive-definite fixed point \(\rho \), then the transfer map \(\mathcal{E}_A\) is irreducible.
By Lemma C.5.5, if \(\sigma \ge 0\) and \(\mathcal{E}_A(\sigma )=\sigma \), then \(\sigma =\frac{\operatorname{tr}(\sigma )}{\operatorname{tr}(\rho )}\rho \). Since \(\rho {\gt}0\), Wolf’s uniqueness criterion for irreducibility applies.
C.6 Identity in the one-step span
When the identity matrix lies in the one-step span \(S_1(A)\), exact word spans grow monotonically and coincide with cumulative spans.
The one-step padding condition is \(\mathbb {1}\in S_1(A)\): the identity matrix lies in the span of the Kraus operators \(\{ A^i\} _{i=0}^{d-1}\). While tensor normalization \(\sum _i(A^i)^\dagger A^i=\mathbb {1}\) is quadratic, the one-step condition \(\mathbb {1}\in S_1(A)\) is linear in the Kraus operators. Theorem 6.7.4.4 obtains normality from a positive-definite fixed point and a complementary gap without this padding condition.
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}\} \).
If \(\mathbb {1}\in S_1(A)\), then \(S_n(A)\le S_{n+1}(A)\) for every \(n\).
For any \(M\in S_n(A)\), one has \(M=M\mathbb {1}\in S_n(A)S_1(A)\subseteq S_{n+1}(A)\) by Lemma C.1.1.
If \(\mathbb {1}\in S_1(A)\), then \(T_n(A)=S_n(A)\) for every \(n\).
By Theorem C.6.3, the word spans form the chain \(S_0(A)\le S_1(A)\le \cdots \le S_n(A)\). Therefore their sum \(T_n(A)=S_0(A)+\cdots +S_n(A)\) equals the largest term \(S_n(A)\).
If \(T_N(A)=M_{D}(\mathbb {C})\) and \(\mathbb {1}\in S_1(A)\), then \(A\) is normal.
Theorem C.6.4 gives \(S_N(A)=T_N(A)=M_{D}(\mathbb {C})\).