How to constructively/combinatorially prove Schur-Weyl duality?

Question

How is Schur-Weyl duality (specifically, the fact that the actions of the group ring $\mathbb{K}\left[ S_{n}\right] $ and the monoid ring $\mathbb{K}\left[ \left( \operatorname*{End}V,\cdot\right) \right] $ on the tensor power $V^{\otimes n}$ are each other's centralizers) for a field $\mathbb{K}$ of characteristic $0$ proven constructively?

Let me now define the notions and explain what I mean by "constructively" and what I want to avoid.

Notations

Let $\mathbb{K}$ be a field of characteristic $0$. Fix $n\in\mathbb{N}$, and let $S_{n}$ be the symmetric group of the set $\left\{ 1,2,\ldots,n\right\} $.

Let $V$ be a finite-dimensional $\mathbb{K}$-vector space. The symmetric group $S_{n}$ acts on the $n$-th tensor power $V^{\otimes n}$ by permuting the tensorands:

$\sigma\left( v_{1}\otimes v_{2}\otimes\cdots\otimes v_{n}\right) =v_{\sigma^{-1}\left( 1\right) }\otimes v_{\sigma^{-1}\left( 2\right) }\otimes\cdots\otimes v_{\sigma^{-1}\left( n\right) }$ for all $\sigma\in S_{n}$ and $v_{1},v_{2},\ldots,v_{n}\in V$.

Thus, the group ring $\mathbb{K}\left[ S_{n}\right] $ acts on $V^{\otimes n}$ as well (by linearity). This makes $V^{\otimes n}$ into a $\mathbb{K} \left[ S_{n}\right] $-module.

On the other hand, the monoid $\left( \operatorname*{End}V,\cdot\right) $ acts on $V^{\otimes n}$ as follows:

$M\left( v_{1}\otimes v_{2}\otimes\cdots\otimes v_{n}\right) =Mv_{1}\otimes Mv_{2}\otimes\cdots\otimes Mv_{n}$ for all $M\in\operatorname*{End}V$ and $v_{1},v_{2},\ldots,v_{n}\in V$.

Thus, the monoid ring $\mathbb{K}\left[ \left( \operatorname*{End} V,\cdot\right) \right] $ acts on $V^{\otimes n}$ as well. This makes $V^{\otimes n}$ into a $\mathbb{K}\left[ \left( \operatorname*{End} V,\cdot\right) \right] $-module.

(Many authors tend to restrict this module to a $\mathbb{K}\left[ \operatorname*{GL}V\right] $-module, but this doesn't feel particularly natural to me. Either way, these things behave pretty much interchangeably.)

Schur-Weyl duality makes the following two claims:

(a) Each endomorphism of the $\mathbb{K}\left[ S_{n}\right] $-module $V^{\otimes n}$ is the action of some element of $\mathbb{K}\left[ \left( \operatorname*{End}V,\cdot\right) \right] $.

(b) Each endomorphism of the $\mathbb{K}\left[ \left( \operatorname*{End}V,\cdot\right) \right] $-module $V^{\otimes n}$ is the action of some element of $\mathbb{K}\left[ S_{n}\right] $.

In general, "some element" is not uniquely determined, as none of the two module structures is faithful. The $\mathbb{K}\left[ S_{n}\right] $-module structure is faithful when $n\leq\dim V$; the $\mathbb{K}\left[ \left( \operatorname*{End}V,\cdot\right) \right] $-module structure is probably never faithful. The quotients that do act faithfully can be described, but this is a different story.

How is this usually proven?

For a theorem that appears in every other book on representation theory, Schur-Weyl duality seems to have a shortage of actually distinct proofs. The argument (as given, e.g., in §4.18 and §4.19 of Pavel Etingof et al, Introduction to representation theory, arXiv:0901.0827v5) proceeds, roughly, as follows: [EDIT: The proof outlined in the following is neither the simplest nor the slickest version of the standard argument. The Etingof-et-al text does it in a much clearer way, by factoring out some of the semisimple-modules arguments into a general lemma. As pointed out by commenters, David Speyer and Mark Wildon (in MO question #90094) have further elementarized the argument, but their versions are still not as lightweight as I'd like them to be (e.g., they still use Schur's lemma, requiring proof of absolute irreducibility).]

• First prove part (a) using fairly elementary methods. (Outline: Let $f$ be an endomorphism of the $\mathbb{K}\left[ S_{n}\right] $-module $V^{\otimes n}$. Write $f$ as a $\mathbb{K}$-linear combination of endomorphisms of the form $f_{1}\otimes f_{2}\otimes\cdots\otimes f_{n}$, where each $f_{i}$ is in $\operatorname*{End}V$. Since $f$ is $\mathbb{K} \left[ S_{n}\right] $-equivariant, we can symmetrize it, so that $f$ also becomes a $\mathbb{K}$-linear combination of endomorphisms of the form $\dfrac{1}{n!}\sum_{\sigma\in S_{n}}f_{\sigma\left( 1\right) }\otimes f_{\sigma\left( 2\right) }\otimes\cdots\otimes f_{\sigma\left( n\right) } $, where each $f_{i}$ is in $\operatorname*{End}V$. It remains to show that each endomorphism of the latter form is the action of some element of $\mathbb{K}\left[ \left( \operatorname*{End}V,\cdot\right) \right] $. This is done using some polarization identity, e.g., $\sum_{\sigma\in S_{n} }f_{\sigma\left( 1\right) }\otimes f_{\sigma\left( 2\right) }\otimes \cdots\otimes f_{\sigma\left( n\right) }=\sum_{I\subseteq\left\{ 1,2,\ldots,n\right\} }\left( -1\right) ^{n-\left\vert I\right\vert }\left( \sum_{i\in I}f_{i}\right) ^{\otimes n}$.)

• Let $B$ be the $\mathbb{K}$-algebra $\operatorname*{End} \nolimits_{\mathbb{K}\left[ S_{n}\right] }\left( V^{\otimes n}\right) $. Then, $B$ is a quotient of $\mathbb{K}\left[ \left( \operatorname*{End} V,\cdot\right) \right] $ because of part (a). Thus, $\operatorname*{End} \nolimits_{\mathbb{K}\left[ \left( \operatorname*{End}V,\cdot\right) \right] }\left( V^{\otimes n}\right) =\operatorname*{End}\nolimits_{B} \left( V^{\otimes n}\right) $.

• Recall that $\mathbb{K}\left[ S_{n}\right] $ is a semisimple algebra (by Maschke's theorem), and thus $V^{\otimes n}$ decomposes as $V^{\otimes n}=\bigoplus_{\lambda\in\Lambda}V_{\lambda}\otimes L_{\lambda}$ for some finite set $\Lambda$, some nonzero $\mathbb{K}$-vector spaces $V_{\lambda}$ and some pairwise non-isomorphic simple $\mathbb{K}\left[ S_{n}\right] $-modules $L_{\lambda}$. Conclude that $\operatorname*{End} \nolimits_{\mathbb{K}\left[ S_{n}\right] }\left( V^{\otimes n}\right) \cong\prod_{\lambda\in\Lambda}\operatorname*{End}\left( V_{\lambda}\right) $. This is a particularly tricky step, since several things are happening at once here: First of all, we need to know that $\operatorname*{End} \nolimits_{\mathbb{K}\left[ S_{n}\right] }\left( L_{\lambda}\right) \cong\mathbb{K}$, which would be a consequence of Schur's lemma if we assumed that $\mathbb{K}$ is algebraically closed, but as we don't, requires some knowledge of the representation theory of $S_{n}$ (namely, of the fact that the simple $\mathbb{K}\left[ S_{n}\right] $-modules are the Specht modules, and are absolutely simple). But even knowing that, we need to know that the endomorphism ring of a direct sum of irreducible $\mathbb{K}\left[ S_{n}\right] $-modules decomposes as a direct product according to the isotypic components, and on each component is a matrix ring. This is standard theory of semisimple algebras, but also requires a nontrivial amount of work.

• Now, $B=\operatorname*{End}\nolimits_{\mathbb{K}\left[ S_{n}\right] }\left( V^{\otimes n}\right) \cong\prod_{\lambda\in\Lambda} \operatorname*{End}\left( V_{\lambda}\right) $, so the $V_{\lambda}$ for $\lambda\in\Lambda$ are the simple $B$-modules. Hence, the decomposition $V^{\otimes n}=\bigoplus_{\lambda\in\Lambda}V_{\lambda}\otimes L_{\lambda}$ can be viewed as a decomposition of the $B$-module $V^{\otimes n}$ into simples. Hence, the endomorphisms of the $B$-module $V^{\otimes n}$ are direct sums of the form $\bigoplus_{\lambda\in\Lambda}\operatorname*{id} \nolimits_{V_{\lambda}}\otimes f_{\lambda}$, where each $f_{\lambda}$ lies in $\operatorname*{End}\left( L_{\lambda}\right) $. (This, again, requires some basic semisimple module theory.) It is now straightforward to show that all such isomorphisms are actions of elements of $\mathbb{K}\left[ S_{n}\right] $ (indeed, the $L_{\lambda}$ are pairwise non-isomorphic simple $\mathbb{K} \left[ S_{n}\right] $-modules, and thus $\prod_{\lambda\in\Lambda }\operatorname*{End}\left( L_{\lambda}\right) $ is a quotient of $\mathbb{K}\left[ S_{n}\right] $). Due to $\operatorname*{End} \nolimits_{\mathbb{K}\left[ \left( \operatorname*{End}V,\cdot\right) \right] }\left( V^{\otimes n}\right) =\operatorname*{End}\nolimits_{B} \left( V^{\otimes n}\right) $, this yields part (b).

What do I want?

I am fairly happy with the proof of part (a) given above, but the proof of part (b) is exactly the kind of argument I shun. It is implicit, non-constructive and relies on half a semester's worth of representation theory. Probably my biggest problem with it is aesthetical -- I see (b) as a combinatorial problem (at least a lot of its invariant-theoretical applications are combinatorial in nature), but the proof is combing this cat completely against the grain (if not pulling it along its tail). But asking for a combinatorial or explicit proof is not a well-defined problem, whereas asking for a constructive one, at least, is clear-cut.

That said, I suspect that a constructive proof can be obtained by some straightforward manipulations of the above argument. The representation theory of $S_{n}$ can be done constructively (see, e.g., Adriano Garsia's notes on Young's seminormal form), and most semisimple-algebra arguments can probably be emulated by plain linear algebra (albeit losing what little intuitive meaning they carry). I would much prefer something that avoids this and either significantly simplifies the representation theory or replaces it by something completely different.

What has been done?

My hopes for a better proof have a reason: Schur-Weyl duality actually works in far greater generality than the above proof. Theorem 1 in Steven Doty's Schur-Weyl duality in positive characteristic (arXiv:math/0610591v3) claims that both (a) and (b) hold for any infinite field $\mathbb{K}$, no matter what the characteristic is! The proof in that paper, however, goes way over my head (it isn't self-contained either, so the 17 pages are not an upper bound). Another paper that might contain answers is Roger W. Carter and George Lusztig, On the Modular Representations of the General Linear and Symmetric Groups, but that one looks even less approachable.

Of course, I would love to see a proof that works for any infinite field $\mathbb{K}$, or maybe even more generally for any commutative ring $\mathbb{K}$, assuming that we replace the endomorphisms of the $\mathbb{K} \left[ \left( \operatorname*{End}V,\cdot\right) \right] $-module $V^{\otimes n}$ by a more reasonable notion of $\operatorname*{GL} $-equivariant maps (namely, endomorphisms of $V^{\otimes n}$ that commute with the action of a "generic $n\times n$-matrix" adjoined freely to the base ring). But I would be happy enough to see just vanilla Schur-Weyl duality proven in a neat way.

One step that can be done easily is a proof of part (b) in the case when $\dim V\geq n$. Namely, in this case, we can argue as follows: Let $\left( e_{1},e_{2},\ldots,e_{d}\right) $ be the standard basis of $V$; thus, $d=\dim V\geq n$. Let $F$ be an endomorphism of the $\mathbb{K}\left[ \left( \operatorname*{End}V,\cdot\right) \right] $-module $V^{\otimes n}$. Let $\eta=F\left( e_{1}\otimes e_{2}\otimes\cdots\otimes e_{n}\right) $. For every $n$ vectors $v_{1},v_{2},\ldots,v_{n}\in V$, we can find a linear map $M\in\operatorname*{End}V$ satisfying $v_{i}=Me_{i}$ for all $i\in\left\{ 1,2,\ldots,n\right\} $, and thus we have

$F\left( v_{1}\otimes v_{2}\otimes\cdots\otimes v_{n}\right) =F\left( Me_{1}\otimes Me_{2}\otimes\cdots\otimes Me_{n}\right) $

$=\left( M\otimes M\otimes\cdots\otimes M\right) \underbrace{F\left( e_{1}\otimes e_{2}\otimes\cdots\otimes e_{n}\right) }_{=\eta}$ (since $F$ is $\mathbb{K}\left[ \left( \operatorname*{End}V,\cdot\right) \right] $-equivariant)

$=\left( M\otimes M\otimes\cdots\otimes M\right) \eta$.

Thus, the value of $\eta$ uniquely determines the endomorphism $F$. Furthermore, we can write $\eta$ as a $\mathbb{K}$-linear combination of pure tensors of the form $e_{i_{1}}\otimes e_{i_{2}}\otimes\cdots\otimes e_{i_{n}}$ and show that, for each such pure tensor that actually occurs in this linear combination (with nonzero coefficient), the $n$-tuple $\left( i_{1} ,i_{2},\ldots,i_{n}\right) $ must be a permutation of $\left( 1,2,\ldots ,n\right) $. (To prove this, we assume the contrary; i.e., assume that the $n$-tuple $\left( i_{1},i_{2},\ldots,i_{n}\right) $ is not a permutation of $\left( 1,2,\ldots,n\right) $, but the tensor $e_{i_{1}}\otimes e_{i_{2} }\otimes\cdots\otimes e_{i_{n}}$ does occur in $\eta$. Thus, either one of the numbers $i_{1},i_{2},\ldots,i_{n}$ is $>n$, or two of these numbers are equal. In the first case, pick an $M\in\operatorname*{End}V$ that sends the corresponding $e_{i_{k}}$ to $0$; in the second, pick an $M\in \operatorname*{End}V$ that multiplies the corresponding $e_{i_{k}}$ by a generic $\lambda$. Either way, again use the $\mathbb{K}\left[ \left( \operatorname*{End}V,\cdot\right) \right] $-equivariance of $F$ to obtain something absurd. Sorry for the lack of details.) The result is that $\eta$ is a $\mathbb{K}$-linear combination of various permutations of $e_1 \otimes e_2 \otimes \cdots \otimes e_n$; and therefore, $F$ (being determined by this $\eta$) is the action of some element of $\mathbb{K}\left[S_n\right]$.

However, this argument completely breaks down when $\dim V<n$, since $e_{1}\otimes e_{2}\otimes\cdots\otimes e_{n}$ does not exist any more. Is there any way to fix it, or is it a dead end?

(Remark: This argument for part (b) in the case $\dim V \geq n$ is quite similar to the proof of Theorem 3.6 in Tom Halverson, Arun Ram, Partition Algebras, arXiv:math/0401314v2, which in itself is a kind of Schur-Weyl duality (but where the symmetric group acts on each tensorand instead of permuting the tensorands!).)

A few more pointers:

• Maybe Weyl's unitary trick gives another proof of Schur-Weyl duality, but it would probably be neither constructive nor combinatorical in my book (Haar measure!).

• There are various papers on a combinatorial approach to invariant theory (e.g., D. Eisenbud, D. De Concini, C. Procesi, Young diagrams and determinantal varieties, which appears to be one of the most readable). However, it is not clear whether they give an answer. The invariant theory of the $\operatorname{GL}$-action on tuples of vectors and covectors (by left/right multiplication) is usually derived (in characteristic $0$, in the non-combinatorial approach) from Schur-Weyl duality; however, I don't know how one would go in the reverse direction (after all, the projection from the tensor algebra to the symmetric algebra is not injective). The FFT for the invariant theory of the $\operatorname{GL}$-action on tuples of matrices by (simultaneous) conjugation is actually equivalent to Schur-Weyl duality, but I haven't seen anyone claim a combinatorial approach to that one.

• Schur's thesis Ueber eine Klasse von Matrizen, die sich einer gegebenen Matrix zuordnen lassen is available online from two places (EUDML/GDZ and archive.org/Harvard), but I am not sure if Schur-Weyl duality is actually in there. (Its notations are sufficiently dated that even searching for the statement is a nontrivial task.)

• The notion of "Schur-Weyl duality" is not standardized across literature; some authors use this name for different assertions. For example, Daniel Bump, in Chapter 34 of his Lie Groups (2nd edition), proves something he calls "Frobenius-Schur duality", and claims that this is exactly Schur-Weyl duality. But it is not what I call Schur-Weyl duality above; it is just the one-to-one correspondence between representations of symmetric groups and Schur functors.

UPDATE: In comments to this post, Frieder Ladisch has alerted me to the fact that the double centralizer theorem (or, rather, the part of the double centralizer theorem that is relevant to the proof of part b)) can be proven constructively (provided that the input is sufficiently explicit). And now I am seeing that essentially his proof appears in Section 11.1 of Jan Draisma and Dion Gijswijt, Invariant Theory with Applications. (Jan: I took the freedom to guess the URL of the PDF file, seeing that the hyperlink was broken due to an incorrect relative path. If you actually don't want these notes to be linked, please let me know!) Some parts of their argument need to be slightly modified to ensure constructivity: The use of continuity in the proof of Theorem 11.1.1 should be replaced by a straightforward argument using Zariski density. The group $H$ in Theorem 11.1.2 should be required to be finite. The vector space $W$ in Theorem 11.1.2 should be required to be finite-dimensional. The requirement in Theorem 11.1.2 that the representation $\lambda$ be completely reducible should be replaced by a requirement that $\left|H\right|$ is invertible in the ground field. The direct complement $U$ of $M$ in the proof of Theorem 11.1.2 should be constructed using Maschke's theorem, which has a well-known proof relying merely on linear algebra (viz., the existence of a complement of an explicitly-defined subspace of a finite-dimensional vector space).

Of course, this beautiful argument still "feels inexplicit" in the sense that it uses some representation-theoretical ideas. But the worst offenders (Artin-Wedderburn theory, passing to algebraic closure, analysis/geometry etc.) are gone. Had I known this argument in advance, I wouldn't have asked this question. Nevertheless, I am leaving this question open, since I have yet to digest various other answers, some of which appear to lead to more general proofs, maybe even in positive characteristic (for whatever parts of Schur-Weyl duality hold there).

Answer 1

This is a quick answer to explain the statement that the hard direction of Schur-Weyl duality is the same thing the First Fundamental Theorem of invariant theory.

Let $V$ be a finite dimensional vector space and $V^{\ast}$ the dual space. The FFT (or a special case there of) says that the $GL(V)$ invariant multilinear functions $V^n \times (V^{\ast})^n$ are spanned by the functions $$(v_1, v_2, \ldots, v_n, v^{\ast}_1, v^{\ast}_2, \ldots, v^{\ast}_n) = \prod \langle v_i, v^{\ast}_{\sigma(i)} \rangle $$ for $\sigma \in S_n$.

Translating "multilinear functions" into "tensors", this gives a spanning set for the $GL(V)$ invariants in $V^{\otimes n} \otimes (V^{\ast})^{\otimes n} \cong \mathrm{Hom}(V^{\otimes n}, V^{\otimes n})$.

Unwinding the isomorphism $V^{\otimes n} \otimes (V^{\ast})^{\otimes n} \cong \mathrm{Hom}(V^{\otimes n}, V^{\otimes n})$, we see that the $GL(V)$ action on $\mathrm{Hom}(V^{\otimes n}, V^{\otimes n})$ is conjugation by the $GL(V)$ action on $V^{\otimes n}$. So a $GL(V)$-invariant is precisely a map $\mathrm{Hom}(V^{\otimes n}, V^{\otimes n})$ which commutes with the $GL(V)$ action. And the $n!$ spanning elements found above turn into the $n!$ maps which permute tensor factors. So FFT says that a map $V^{\otimes n} \to V^{\otimes n}$ which commutes with the $GL(V)$ action is a linear combination of permutation of tensor factors, just as you want.

Answer 2

This a continuation of my first answer. I was trying to edit the previous one but the MathJax processing was freezing my computer. I suppose that answer was getting too long.

@Darij: There has been lots of action on this question since I posted my first answer last night. Although, I must say, there has not been much reading of that answer ... ;)

In your comments you raised two issues.

Issue 1: how does FFT imply part b) of Schur-Weyl duality (the hard part)?

My reply: The proof I gave does in one sweep, with no pause in between, the FFT for $SU(d)$ (and not $U(d)$ as in David's answer) and Schur-Weyl duality. But I could have written it in two steps. In this case the main protagonist $T$ would be an array with entries $$ T_{a_1\ldots a_p,i_1\ldots i_q} $$ corresponding to an invariant of $p$ vectors and $q$ covectors. After eliminating the matrix elements of $g^{-1}$ by Cramer's rule, one has a degree $p+q(d-1)=qd+p-q$ homogeneous polynomial in the entries of $g$ to be hit by a suitable power $r$ of ${\rm det}(\partial g)$. If $d$ does not divide $p-q$ then $T$ must vanish. Otherwise $r=q+\frac{p-q}{d}$ and at the end of the argument above using the elimination of $\epsilon$'s and $\tau$'s in pairs with the identity "${\rm det}(AB)={\rm det}(A){\rm det}(B)$", the number of $\epsilon$'s is $q$ while the number of $\tau$'s is $r$.

1. If $p>q$: then $r>q$ and after pairwise elimination of $q$ $\epsilon$-$\tau$ pairs, one is left with $q$ direct contractions of vectors and covectors mediated by a permutation in $S_q$ (this is the Schur-Weyl or $GL$ invariant part) as well as $(p-q)/d$ surviving $\tau$'s giving what the classics called "Klammerfaktoren" involving vectors only.
2. If $p<q$: then $r<q$ and after pairwise elimination of $r$ $\epsilon$-$\tau$ pairs, one is left with $p$ direct contractions of vectors and covectors mediated by a permutation in $S_p$ (this is again the Schur-Weyl or $GL$ invariant part) as well as $(q-p)/d$ surviving $\epsilon$'s giving "Klammerfaktoren" involving covectors only.
3. What you are interested in is the special case $p=q=n$, or pure Schur-Weyl situation with no "Klammerfaktoren". In other words, Schur-Weyl duality part b) is this particular case of the First Fundamental theorem of classical invariant theory for $SU(d)$ slash $SL(d)$.

Issue 2: This does not count because the proof uses analysis, Haar measure etc.

My reply: The Haar measure is just salad dressing. I incorporated into the narrative in order to make the structure of the proof more natural. The proof I gave for the FFT of $SU(d)$ slash $SL(d)$ has three easy steps only: 1) average over the group. 2) figure out what averaging means in algebro/combinatorial terms rather than analytic ones 3) do the calculation and contemplate the result. It would have taken me too long to draw pictures in my answer but this is a purely graphical proof. If you want to see these pictures at least in the case $d=2$, $p$ arbitrary and $q=0$ case, then see pages 16-17 of this article. (If you have access to JKTR, the published version is quite a bit better).

I could have written my first answer in a purely combinatorial way without mentioning the Haar measure at all but then some elements of the proof would have come totally out the blue. In particular, I would have had to all of a sudden say: if $T$ is invariant then $$ T=c_n\ ({\rm det}(\partial g))^n\ gT $$ where $gT$ is the expression obtained after Cramer's rule and the $g$'s are treated as formal variables. So again I insist, my answer is purely combinatorial. But I don't know if it may be useful in nonzero characteristic. This may require understanding the arithmetic of the $c_n$'s.

Additional remark: A more natural proof in the spirit of the one I gave would be to use the FFT for $U(d)$ slash $GL(d)$ rather than $SU(d)$ slash $SL(d)$. This would need an explicit formula for averaging as an infinite order differential operator. I remember seeing something like that in a physics paper, but I would have to find that reference. Usually people resort to Weingarten calculus which goes in the orthogonal direction of the character theory of the symmetric group.

---

Edit: Yet another rewriting of the proof of the FFT for $SU(d)$ slash $SL(d)$ in order to eliminate analysis and Haar measures etc.

For any $p,q\ge 0$, let $\mathcal{T}_{p,q}$ be the set of arrays $$ T=(T_{a_1,\ldots,a_p,i_1\ldots,i_q})_{a_1,\ldots,a_p,i_1\ldots,i_q\in [d]} $$ of complex numbers. For $g\in GL(d)$ and $T\in\mathcal{T}_{p,q}$ define the new array $gT$ by $$ (gT)_{a_1,\ldots,a_p,i_1\ldots,i_q}=\sum_{b_1,\ldots,b_p,j_1\ldots,j_q\in [d]} T_{j_1,\ldots,j_p,b_1\ldots,b_q} g_{a_1 j_1}\cdots g_{a_p j_p}\ (g^{-1})_{b_1 i_1}\cdots (g^{-1})_{b_q i_q} $$ If $q=0$ then this is well defined for all matrices $g$ and not just invertible ones.

We define two maps $\phi:\mathcal{T}_{p,q}\rightarrow \mathcal{T}_{p+q(d-1),0}$ and $\psi:\mathcal{T}_{p+q(d-1),0} \rightarrow\mathcal{T}_{p,q}$ as follows: $$ (\phi(T))_{a_1\ldots a_p, b_{11}\ldots b_{1 (d-1)},\cdots, b_{q 1}\ldots, b_{q (d-1)}}=\sum_{b_1,\ldots,b_q\in [d]} $$

$$ T_{a_1,\ldots,a_p,b_1\ldots,b_q} \tau_{b_1,b_{11}\ldots b_{1 (d-1)}}\cdots \tau_{b_q, b_{q 1}\ldots b_{q (d-1)}} $$ and $$ (\psi(S))_{a_1,\ldots,a_p,i_1\ldots,i_q}=\sum_{j_{11}\ldots j_{1 (d-1)},\cdots, j_{q 1}\ldots, j_{q (d-1)}\in [d]} $$

$$ S_{a_1\ldots a_p, i_1, j_{11}\ldots j_{1 (d-1)},\cdots, i_q, j_{q 1}\ldots, j_{q (d-1)}} \epsilon_{i_1, j_{11}\ldots j_{1 (d-1)}}\cdots \epsilon_{i_q, j_{q 1}\ldots j_{q (d-1)}} $$ For all invertible $g$ one has $$ g\phi(T)=({\rm det}(g))^{q} \ \phi(gT) $$ and $$ g\psi(S)=({\rm det}(g))^{-q}\ \psi(gS) $$ as trivial consequences of the even more trivial identity $$ \sum_{i_1\ldots i_d\in [d]}\epsilon_{i_1\ldots i_d} M_{i_1 j_1}\cdots M_{i_d j_d}= {\rm det}(M)\epsilon_{j_1\ldots j_d} $$ and also a good pair of glasses.

Moreover, one has $$ \psi(\phi(T))= \frac{1}{(d-1)!^q} \ T $$ as a consequence of Cramer's rule for the identity matrix, namely, $$ \sum_{j_1\ldots j_{d-1}\in [d]}\epsilon_{j,j_1\ldots j_{d-1}}\tau_{i,j_1\ldots j_{d-1}}=(d-1)!\ \delta_{j,i} $$ The above is prep work for a reduction of the FFT for $SU(d)$ to the case $q=0$ and $p$ divisible by $d$.

Let us now assume that $q=0$ and that $T\in\mathcal{T}_{p,0}$ is invariant, i.e., $gT=T$ for all $g\in SU(d)$ or rather $SL(d)$. Since any $g\in GL(d)$ can be written as $g=\lambda h$ with $h\in SL(d)$ and $\lambda$ some $d$-th root of ${\rm det}(g)$ then since $gT$ is a homogeneous polynomial we more generally have $gT=({\rm det}(g))^n\ T$ for all $g\in GL(d)$, and even for all $g\in {\rm Mat}_{d\times d}$. Here $n$ denotes the weight $p/d$. We now have $$ ({\rm det}(\partial g))^n\ gT=({\rm det}(\partial g))^n\ ({\rm det}(g))^n T=\rho_n\ T $$ The heart of the proof (as well as of the understanding of the Haar measure as pure combinatorics), is to show that $$ \rho_n=({\rm det}(\partial g))^n\ ({\rm det}(g))^n \neq 0 $$ The most precise way of doing this is via the "Cayley identity" exercise which gives the explicit formula $$ \rho_n=\frac{1}{c_n} $$ But a cheaper argument goes as follows. When summing over the permutation in $S_{nd}$ which I called a Wick contraction scheme (just the Leibnitz rule) arising in the computation of $\rho_n$, one gets a sum of squares: what I called the two decoupled (rather than connected) components that I mentioned earlier are identical and deliver the same numerical evaluation. One just need choose one of these contraction schemes, for instance, coming from $$ \left[({\rm det}(\partial g))\ ({\rm det}(g))\right]^n $$ and check it is nonzero. The germ of this "mirror symmetry" between the two components is visible in the right-hand side of the basic identity I used $$ \frac{\partial}{\partial g_{cl}}g_{i b}=\delta_{ci}\delta_{lb} $$

I guess that's enough details for you to finish the proof of the FFT for $SU$ or $SL$.

Let me simply say that this is not my proof but Clebsch's in his amazing article "Ueber symbolische Darstellung algebraischer Formen" in Crelle 1861. (Please click on the full text link and read Section 3 of that article and in particular pages 12 and 13 which contain the sum of squares non-vanishing argument). As another comment about history, I put quotes when talking about the "Cayley identity" because (of course Arnold would say) it is nowhere to be found in the works of Cayley. The earliest instance I have seen is in Clebsch's book on binary forms for $d=2$. No doubt, he must have been trying to get a better understanding of the $\rho_n$ coefficients and also the Gordan-Clebsch series (see my JKTR article). Tony Crilly, Alan Sokal and I are supposed to work on an article on the history of the "Cayley identity" but we have been distracted by other tasks. It is on the $({\rm back})^n$-burner with $n$ large.

Answer 3

look at

C. De Concini, C. Procesi, A characteristic free approach to invariant theory, Adv. Math. 21 (1976), 330–354.

Answer 4

Since you are OK with an explicit combinatorial proof in characteristic zero I think you should also be OK with working over $\mathbb{C}$. Part b) of Schur-Weyl duality follows from the First Fundamental Theorem of classical invariant theory for $SU(d)$ with an equal number $n$ of vectors and covectors. I prefer high-school algebra so I will let $\mathcal{T}$ be the set of arrays of complex numbers $$ T=(T_{a_1,\ldots,a_n,i_1\ldots,i_n})_{a_1,\ldots,a_n,i_1\ldots,i_n\in [d]} $$ where $[d]=\{1,2,\ldots,d\}$. I define the left action of $g\in U(d)$ on $\mathcal{T}$ by $$ (gT)_{a_1,\ldots,a_n,i_1\ldots,i_n}=\sum_{b_1,\ldots,b_n,j_1\ldots,j_n\in [d]} T_{j_1,\ldots,j_n,b_1\ldots,b_n} g_{a_1 j_1}\cdots g_{a_n j_n}\ (g^{-1})_{b_1 i_1}\cdots (g^{-1})_{b_n i_n} $$ Suppose $T$ is invariant by $U(d)$ and thus by $SU(d)$ then for all values of the $a$ and $i$ indices $$ T_{a_1,\ldots,a_n,i_1\ldots,i_n}=\int_{SU(d)} (gT)_{a_1,\ldots,a_n,i_1\ldots,i_n}\ d\mu(g) $$ where $d\mu$ is the normalized Haar measure. Let me define the special arrays $\epsilon$ and $\tau$. Let $$ \epsilon=(\epsilon_{i_1\ldots i_d})_{i_1\ldots i_d\in [d]} $$ with $\epsilon_{i_1\ldots i_d}$ equal to the sign of the permutation $i_1,\ldots,i_d$ of $1,2,\ldots,d$ if the indices are distinct and equal to zero otherwise. I define $$ \tau=(\tau_{a_1\ldots a_d})_{a_1\ldots a_d\in [d]} $$ in exactly the same way so in fact as "hyper-matrices" $\tau=\epsilon$ but they will serve different purposes so I will keep the distinction. For $g\in SU(d)$, Cramer's rule says that $$ (g^{-1})_{bi}=\frac{1}{(d-1)!}\sum_{b_1\ldots b_{d-1}, i_1\ldots i_{d-1}\in[d]} \tau_{b b_1\ldots b_{d-1}}\epsilon_{i i_1\ldots i_{d-1}} g_{i_1 b_1}\cdots g_{i_{d-1} b_{d-1}} $$ So after substituting in the above integral one is reduced to computing $\int_{SU(d)}\ldots d\mu(g)$ for a monomial of degree $n+n(d-1)=nd$ in the matrix elements of $g$.

For a matrix variable $J\in {\rm Mat}_{d\times d}(\mathbb{C})$ let $$ Z(J)=\int_{SU(d)}\ \exp({\rm tr}(Jg))\ d\mu(g) $$ The following facts are easy exercises.

$Z(J)$ is an entire analytic function of $J$.

$Z(J)$ only depends on ${\rm det}(J)$.

One has an everywhere convergent series representation $$ Z(J)=\sum_{n=0}^{\infty} c_n ({\rm det}(J))^n $$ for some suitable coefficients $c_n$.

Another easy exercise is the so-called "Cayley identity" $$ {\rm det}(\partial J) ({\rm det}(J))^n=b(n) ({\rm det}(J))^{n-1} \ $$ with $\partial J=(\frac{\partial}{\partial J_{ij}})_{1\le i,j,\le d}$ and the explicit Bernstein polynomial $$ b(n)=n(n+1)\ldots (n+d-1)\ . $$

It is not hard to deduce from this a recursion for the $c_n$ and finally the explicit formula $$ c_n=\frac{0! 1!\cdots (d-1)!}{n! (n+1)!\cdots (n+d-1)!}\ . $$ As a result, the Haar integral for $T$ is given by hitting that right-hand side (of degree $nd$ in $g$) with the order $nd$ differential operator $c_n ({\rm det}(\partial g))^n$. For this next step, write $$ {\rm det}(\partial g)=\frac{1}{d!}\sum_{c_1\ldots c_d,l_1\ldots l_d\in [d]} \tau_{c_1\ldots c_d}\epsilon_{l_1\ldots l_d} \frac{\partial}{\partial g_{c_1 l_1}} \cdots \frac{\partial}{\partial g_{c_d l_d}} $$ The basic formula for derivation $$ \frac{\partial}{\partial g_{c l}} g_{i b}=\delta_{c i}\delta_{l b} $$ gets amplified by the Leibnitz rule which involves a sum over a permutation (or Wick contraction scheme) of $nd$ elements. This permutation decides which $\frac{\partial}{\partial g_{c l}}$ factor hits which $g_{i b}$ factor. When applying this to $T$, and after carefully following the tensor contractions, one sees that the "graph of index contractions" has two decoupled components. One component contains the $j,b,l$ indices and gives a numerical factor. The component which matters contains the $a,b,i$ indices. It involves exactly $n$ factors $\epsilon$ and $n$ factors $\tau$. There may be direct $\epsilon$-to-$\tau$ contractions of indices. The remaining $\epsilon$ indices must be $i_1,\ldots,i_n$ featuring in the "matrix element" $T_{a_1\ldots a_n,i_1\ldots i_n}$ to be computed. Likewise, the remaining $\tau$ indices must be $a_1,\ldots,a_n$. Now choose an arbitrary pairing between the $\epsilon$'s and the $\tau$'s among the $n!$ possible ones. Finally use the identity $$ \epsilon_{l_1\ldots l_d}\tau_{c_1\ldots c_d}=\sum_{\sigma\in S_d} {\rm sign}(\sigma)\delta_{l_1 c_{\sigma(1)}} \cdots \delta_{l_d c_{\sigma(d)}} $$ (which is just ${\rm det}(AB)={\rm det}(A){\rm det}(B)$) for each such (admittedly artificial) $\epsilon$-$\tau$ pair.

At the end of the day, after expanding a sum over $n$ permutations $\sigma_1,\ldots,\sigma_n$, the terms obtained are all linear combinations of $T^{\sigma}$, $\sigma\in S_n$, where $$ (T^{\sigma})_{a_1\ldots a_n,i_1\ldots i_n}=\delta_{a_1 i_{\sigma(1)}} \cdots \delta_{a_n i_{\sigma(n)}}\ . $$ This last statement is Schur-Weyl duality.