Proof of Word Polynomials under a Unitary Law: Linearity, Traciality, Positivity, the Cauchy-Schwarz Inequality and the l1 Bound

Each result cited is universally quantified over the data in its own statement.

Throughout, $X,Y,Z$ have support sets $F,G,H$ (Word Polynomials in Unitary Letters: the Normed *-Algebra of Finitely Supported Word Functions §polynomials). For $A\subseteq W_{2d}$ we write $A^{*}=\{u^{*}:u\in A\}$. As in Word Polynomials in Unitary Letters: the Normed *-Algebra of Finitely Supported Word Functions §product, $S=\{uv:(u,v)\in F\times G\}$ is the support set of $XY$ and $P_{w}=\{(u,v)\in F\times G:uv=w\}$. Finite sums are those of Sum over a Finite Index Set over the field $\mathbb{C}$ or $\mathbb{R}$; reindexing, additivity and homogeneity refer to claims 2, 3 and 4 of Properties of a Sum over a Finite Index Set. Products, evaluations and $\ell^{1}$ norms do not depend on the support sets used (Word Polynomials in Unitary Letters: the Normed *-Algebra of Finitely Supported Word Functions §product, Evaluation of Word Polynomials by a Unitary Law §evaluation, Word Polynomials in Unitary Letters: the Normed *-Algebra of Finitely Supported Word Functions §norm); so whenever convenient we replace a support set by a larger nonempty finite set, for instance $F$ and $G$ by $F\cup G$, which is finite by Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §finite-union and outside which both $X$ and $Y$ vanish.

Step 1 (adjoint words). (W1) $(w^{*})^{*}=w$ for every $w\in W_{2d}$, as shown in Word Polynomials in Unitary Letters: the Normed *-Algebra of Finitely Supported Word Functions §adjoint. Hence $u\mapsto u^{*}$ is its own inverse, and for every $A\subseteq W_{2d}$ it restricts to a bijection of $A$ onto $A^{*}$, with $(A^{*})^{*}=A$.

(W2) $(uv)^{*}=v^{*}u^{*}$ for all $u,v\in W_{2d}$. If $u=\varnothing$ or $v=\varnothing$ this follows from $\varnothing^{*}=\varnothing$ (Words in Unitary Letters: Generators, Signs, Inverse Letters, Lengths and Adjoint Words §adjoint) and Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §monoid. Otherwise, for a word $x$ of length $k$ let $x^{\vee}$ be the word of length $k$ with $(x^{\vee})_{i}=(x_{i})^{-1}$ for $i\in[k]$; then $x^{*}=(x^{\mathrm{rev}})^{\vee}$ by Words in Unitary Letters: Generators, Signs, Inverse Letters, Lengths and Adjoint Words §adjoint. By Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §concatenation the letters of $xy$ are those of $x$ followed by those of $y$, so $(xy)^{\vee}=x^{\vee}y^{\vee}$. By Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §reversal, $(uv)^{\mathrm{rev}}=v^{\mathrm{rev}}u^{\mathrm{rev}}$, and therefore $(uv)^{*}=(v^{\mathrm{rev}}u^{\mathrm{rev}})^{\vee}=(v^{\mathrm{rev}})^{\vee}(u^{\mathrm{rev}})^{\vee}=v^{*}u^{*}$.

Step 2 (regrouping over factorisations). (P0) For every map $\psi:F\times G\to\mathbb{C}$ (or $\mathbb{R}$),

$$\sum_{w\in S}\ \sum_{(u,v)\in P_{w}}\psi\bigl((u,v)\bigr)=\sum_{(u,v)\in F\times G}\psi\bigl((u,v)\bigr).$$

Indeed, $S$ is nonempty and finite, and each $P_{w}$ with $w\in S$ is nonempty, since $w=uv$ for some $(u,v)\in F\times G$. By Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §pairs the left side is the sum over the set $T$ of pairs $(w,(u,v))$ with $w\in S$ and $(u,v)\in P_{w}$. The map $(w,(u,v))\mapsto(u,v)$ is a bijection of $T$ onto $F\times G$, since $w=uv$ is determined by $(u,v)$ and $(uv,(u,v))\in T$ for every $(u,v)\in F\times G$; reindexing gives (P0).

(E) For every map $\varphi:W_{2d}\to\mathbb{C}$,

$$\sum_{w\in S}(XY)(w)\,\varphi(w)=\sum_{(u,v)\in F\times G}X(u)\,Y(v)\,\varphi(uv).$$

Indeed, for $w\in S$ homogeneity gives $(XY)(w)\varphi(w)=\sum_{(u,v)\in P_{w}}X(u)Y(v)\varphi(uv)$, since $uv=w$ on $P_{w}$, and (P0) applies. With $\varphi=\lambda$, Evaluation of Word Polynomials by a Unitary Law §evaluation and the support set $S$ of $XY$ give

$$\lambda(XY)=\sum_{(u,v)\in F\times G}X(u)\,Y(v)\,\lambda(uv).\tag{E$_{\lambda}$}$$

Step 3 (clause 1, algebra). (a) Sums and scalars. Use the support set $F\cup G$ for $X$, $Y$ and $X+Y$, and $H$ for $Z$ (Word Polynomials in Unitary Letters: the Normed *-Algebra of Finitely Supported Word Functions §polynomials). For $w\in W_{2d}$ the set of pairs $(u,v)\in(F\cup G)\times H$ with $uv=w$ is then the same for the products $(X+Y)Z$, $XZ$ and $YZ$. If it is empty, all three values at $w$ are $0$. Otherwise distributivity in $\mathbb{C}$ and additivity give $\sum(X(u)+Y(u))Z(v)=\sum X(u)Z(v)+\sum Y(u)Z(v)$ over this set, that is, $((X+Y)Z)(w)=(XZ)(w)+(YZ)(w)$. The identities $Z(X+Y)=ZX+ZY$ and $(zX)Y=z(XY)=X(zY)$ follow in the same way, the latter by homogeneity. Pointwise, $(X+Y)^{*}(w)=\overline{X(w^{*})+Y(w^{*})}=X^{*}(w)+Y^{*}(w)$ and $(zX)^{*}(w)=\overline{z\,X(w^{*})}=\overline{z}\,X^{*}(w)$, by claim 1 of Properties of Complex Conjugation and Modulus. Also $(X^{*})^{*}(w)=\overline{X^{*}(w^{*})}=\overline{\overline{X((w^{*})^{*})}}=X(w)$ by (W1) and claim 1 of the same lemma.

(b) The words $e_{u}$. With the support sets $\{u\}$ and $\{v\}$, the set of pairs in $\{u\}\times\{v\}$ with product $w$ is $\{(u,v)\}$ if $w=uv$ and empty otherwise. So $(e_{u}e_{v})(w)$ is $1\cdot1=1$ if $w=uv$ and $0$ otherwise, which means $e_{u}e_{v}=e_{uv}$. Next, $(e_{u})^{*}(w)=\overline{e_{u}(w^{*})}$ is $1$ if $w^{*}=u$, that is, if $w=u^{*}$ by (W1), and $0$ otherwise; so $(e_{u})^{*}=e_{u^{*}}$. With the support sets $\{\varnothing\}$ and $F$, the pairs in $\{\varnothing\}\times F$ with product $w$ form $\{(\varnothing,w)\}$ if $w\in F$ and the empty set otherwise, because $\varnothing v=v$ (Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §monoid). Hence $(e_{\varnothing}X)(w)=X(w)$ for $w\in F$, and $(e_{\varnothing}X)(w)=0=X(w)$ for $w\notin F$. In the same way, $Xe_{\varnothing}=X$.

(c) $(XY)^{*}=Y^{*}X^{*}$. Use the support sets $G^{*}$ and $F^{*}$ of $Y^{*}$ and $X^{*}$ (Word Polynomials in Unitary Letters: the Normed *-Algebra of Finitely Supported Word Functions §adjoint). Let $w\in W_{2d}$, let $Q_{w}=\{(u,v)\in F\times G:uv=w^{*}\}$, and let $Q'_{w}=\{(v',u')\in G^{*}\times F^{*}:v'u'=w\}$. The map $(u,v)\mapsto(v^{*},u^{*})$ is a bijection of $Q_{w}$ onto $Q'_{w}$, with inverse $(v',u')\mapsto(u'^{*},v'^{*})$: by (W1) and (W2), $uv=w^{*}$ holds if and only if $w=(uv)^{*}=v^{*}u^{*}$. If $Q_{w}$ is empty, so is $Q'_{w}$, and both $(Y^{*}X^{*})(w)$ and $(XY)^{*}(w)=\overline{(XY)(w^{*})}$ are $0$. Otherwise we reindex, and then use claim 1 of Properties of Complex Conjugation and Modulus and Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §conjugate:

$$(Y^{*}X^{*})(w)=\sum_{(u,v)\in Q_{w}}\overline{Y(v)}\ \overline{X(u)}=\overline{\sum_{(u,v)\in Q_{w}}X(u)Y(v)}=\overline{(XY)(w^{*})}=(XY)^{*}(w).$$

(d) Associativity. Let $T=\{vz:(v,z)\in G\times H\}$ be the support set of $YZ$. For $w\in W_{2d}$ let $R_{w}$ be the set of $((u,v),z)\in(F\times G)\times H$ with $(uv)z=w$, and let $R'_{w}$ be the set of $(u,(v,z))\in F\times(G\times H)$ with $u(vz)=w$. By Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §monoid, $((u,v),z)\mapsto(u,(v,z))$ is a bijection of $R_{w}$ onto $R'_{w}$. We claim that $((XY)Z)(w)$ is the sum of $X(u)Y(v)Z(z)$ over $R_{w}$ when $R_{w}\neq\emptyset$, and is $0$ otherwise. By definition, $((XY)Z)(w)$ is the sum of $(XY)(t)Z(z)$ over $O_{w}=\{(t,z)\in S\times H:tz=w\}$. If $O_{w}$ is empty, then so is $R_{w}$, since $((u,v),z)\in R_{w}$ would give $(uv,z)\in O_{w}$; in that case the value is $0$. Otherwise homogeneity gives $(XY)(t)Z(z)=\sum_{(u,v)\in P_{t}}X(u)Y(v)Z(z)$, where each $P_{t}$ with $t\in S$ is nonempty. By Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §pairs the resulting double sum is a sum over the pairs $((t,z),(u,v))$ with $(t,z)\in O_{w}$ and $(u,v)\in P_{t}$. The map $((t,z),(u,v))\mapsto((u,v),z)$ is a bijection of this set onto $R_{w}$, with inverse $((u,v),z)\mapsto((uv,z),(u,v))$, and reindexing proves the claim. In the same way, $(X(YZ))(w)$ is the sum of $X(u)Y(v)Z(z)$ over $R'_{w}$, or $0$ when $R'_{w}=\emptyset$. Reindexing along the bijection $R_{w}\to R'_{w}$ gives $((XY)Z)(w)=(X(YZ))(w)$.

Step 4 (clause 2, linearity). Using the support set $F\cup G$ for $X$, $Y$ and $X+Y$, Evaluation of Word Polynomials by a Unitary Law §evaluation and additivity give $\lambda(X+Y)=\sum_{w\in F\cup G}\bigl(X(w)\lambda(w)+Y(w)\lambda(w)\bigr)=\lambda(X)+\lambda(Y)$. Homogeneity gives $\lambda(zX)=\sum_{w\in F}zX(w)\lambda(w)=z\lambda(X)$.

Step 5 (clause 3, traciality). By (E$_{\lambda}$), $\lambda(XY)$ is the sum of $X(u)Y(v)\lambda(uv)$ over $(u,v)\in F\times G$, and $\lambda(YX)$ is the sum of $Y(v)X(u)\lambda(vu)$ over $(v,u)\in G\times F$. By Laws of d-Tuples of Unitaries §cyclic, $\lambda(uv)=\lambda(vu)$, and $Y(v)X(u)=X(u)Y(v)$ by commutativity of multiplication in $\mathbb{C}$. Reindexing along the bijection $(u,v)\mapsto(v,u)$ of $F\times G$ onto $G\times F$ gives $\lambda(XY)=\lambda(YX)$.

Step 6 (clause 4, adjoints). We reindex along the bijection $u\mapsto u^{*}$ of $F$ onto $F^{*}$, using (W1). We then use Unitary Laws: Adjoints, the Bound One, and Reduction to Cyclically Reduced Words §adjoint, claim 1 of Properties of Complex Conjugation and Modulus and Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §conjugate:

$$\lambda(X^{*})=\sum_{w\in F^{*}}\overline{X(w^{*})}\,\lambda(w)=\sum_{u\in F}\overline{X(u)}\,\lambda(u^{*})=\sum_{u\in F}\overline{X(u)}\ \overline{\lambda(u)}=\overline{\lambda(X)}.$$

Step 7 (clause 5, positivity). Apply (E$_{\lambda}$) to $X^{*}$ and $X$, with support sets $F^{*}$ and $F$, and reindex along the bijection $(u,v)\mapsto(u^{*},v)$ of $F\times F$ onto $F^{*}\times F$, using (W1):

$$\lambda(X^{*}X)=\sum_{(u',v)\in F^{*}\times F}\overline{X(u'^{*})}\,X(v)\,\lambda(u'v)=\sum_{(u,v)\in F\times F}\overline{X(u)}\,X(v)\,\lambda(u^{*}v).$$

By Laws of d-Tuples of Unitaries §positive, $K(u,v)=\lambda(u^{*}v)$ is a positive semidefinite kernel on $F$. The right side is its quadratic form at the restriction of $X$ to $F$, so it is a nonnegative real number by Positive Semidefinite Kernel on a Finite Set §kernel. Now let $X$ and $Y$ be self-adjoint. By clause 4 (Step 6), clause 1 (Step 3(c)) and clause 3 (Step 5), $\overline{\lambda(XY)}=\lambda((XY)^{*})=\lambda(Y^{*}X^{*})=\lambda(YX)=\lambda(XY)$. Hence $\lambda(XY)$ is real by claim 1 of Properties of Complex Conjugation and Modulus. Finally $\lambda(XX)=\lambda(X^{*}X)\ge0$.

Step 8 (clause 6, Cauchy–Schwarz). Put $\alpha=\lambda(X^{*}X)$, $\beta=\lambda(Y^{*}Y)$ and $c=\lambda(X^{*}Y)$; by Step 7, $\alpha$ and $\beta$ are nonnegative reals. By clause 1, $(Y^{*}X)=(X^{*}Y)^{*}$, so $\lambda(Y^{*}X)=\overline{c}$ by clause 4. Let $z\in\mathbb{C}$. By clause 1, $(X+zY)^{*}(X+zY)=X^{*}X+z\,X^{*}Y+\overline{z}\,Y^{*}X+\overline{z}z\,Y^{*}Y$. Clause 2, Step 7, and claims 1, 2 and 3 of Properties of Complex Conjugation and Modulus then give

$$0\le q(z):=\lambda\bigl((X+zY)^{*}(X+zY)\bigr)=\alpha+zc+\overline{zc}+|z|^{2}\beta .$$

Case $0<\beta$. Take $z=-\beta^{-1}\overline{c}$. Then $zc=-\beta^{-1}|c|^{2}$ is real, so $\overline{zc}=zc$, and $|z|^{2}=z\overline{z}=\beta^{-2}|c|^{2}$ (claims 1 and 3 of Properties of Complex Conjugation and Modulus). So $zc+\overline{zc}=2zc=-2\beta^{-1}|c|^{2}$ and $|z|^{2}\beta=\beta^{-2}|c|^{2}\beta=\beta^{-1}|c|^{2}$. Hence $0\le q(z)=\alpha-2\beta^{-1}|c|^{2}+\beta^{-1}|c|^{2}=\alpha-\beta^{-1}|c|^{2}$. Multiplying by $\beta\ge0$ (claims 3 and 5 of Elementary Arithmetic in an Ordered Field) gives $|c|^{2}\le\alpha\beta$. Case $\beta=0$. Suppose $c\neq0$. Then $|c|\neq0$ by claim 3 of Properties of Complex Conjugation and Modulus, so $0<|c|^{2}$ (claim 5 of Elementary Order Arithmetic in an Ordered Field). Take $z=-t\overline{c}$ with the real number $t=(\alpha+1)|c|^{-2}$. Then $zc=-(\alpha+1)$ is real, and $q(z)=\alpha-2(\alpha+1)=-\alpha-2<0$, because $0\le\alpha$ and $0<2$ give $0<2+\alpha$ (claims 3, 4 and 8 of Elementary Order Arithmetic in an Ordered Field). This contradicts $0\le q(z)$, so $c=0$ and $|c|^{2}=0=\alpha\beta$. In both cases $|\lambda(X^{*}Y)|^{2}\le\lambda(X^{*}X)\lambda(Y^{*}Y)$.

Step 9 (clause 7, $\ell^{1}$ bounds). We use Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §modulus, claim 4 of Properties of Complex Conjugation and Modulus, and $|\lambda(w)|\le1$ from Unitary Laws: Adjoints, the Bound One, and Reduction to Cyclically Reduced Words §bound, together with $0\le|X(w)|$ and claim 5 of Elementary Arithmetic in an Ordered Field. With Real Sums over a Finite Index Set: Comparison, Nonnegativity, Monotonicity, Term Bounds, Absolute Values, Counting and Limits §comparison they give $|\lambda(X)|\le\sum_{w\in F}|X(w)|\,|\lambda(w)|\le\sum_{w\in F}|X(w)|=\lVert X\rVert_{1}$. On the support set $F\cup G$, the triangle inequality (claim 7 of Properties of Complex Conjugation and Modulus), Real Sums over a Finite Index Set: Comparison, Nonnegativity, Monotonicity, Term Bounds, Absolute Values, Counting and Limits §comparison and additivity give $\lVert X+Y\rVert_{1}\le\lVert X\rVert_{1}+\lVert Y\rVert_{1}$. Claim 4 of the same lemma and homogeneity give $\lVert zX\rVert_{1}=|z|\,\lVert X\rVert_{1}$. Reindexing along $u\mapsto u^{*}$, together with $|\overline{\zeta}|=|\zeta|$ (claim 3 of that lemma), gives $\lVert X^{*}\rVert_{1}=\sum_{w\in F^{*}}|X(w^{*})|=\sum_{u\in F}|X(u)|=\lVert X\rVert_{1}$. Finally, for $w\in S$, $|(XY)(w)|\le\sum_{(u,v)\in P_{w}}|X(u)|\,|Y(v)|$. Summing over $w\in S$ and using Real Sums over a Finite Index Set: Comparison, Nonnegativity, Monotonicity, Term Bounds, Absolute Values, Counting and Limits §comparison, (P0) for the real map $\psi((u,v))=|X(u)|\,|Y(v)|$, and The Product of Two Sums over Finite Index Sets is a Sum over the Cartesian Product, we obtain

$$\lVert XY\rVert_{1}=\sum_{w\in S}|(XY)(w)|\le\sum_{(u,v)\in F\times G}|X(u)|\,|Y(v)|=\Bigl(\sum_{u\in F}|X(u)|\Bigr)\Bigl(\sum_{v\in G}|Y(v)|\Bigr)=\lVert X\rVert_{1}\lVert Y\rVert_{1}.\qquad\blacksquare$$