Walks on graphs and tensor products

graph theoryquiverrepresentation-theory

In Qiaochu's article https://qchu.wordpress.com/2010/03/07/walks-on-graphs-and-tensor-products/#more-4807, he gives the following setup:

Construct a directed graph $\Gamma(V)$ as follows: its vertices are the irreducible representations of $G$, and the number of arrows from $A$ to $B$ is the multiplicity of $B$ in $A \otimes V$. Then the multiplicity of the trivial representation in $V^{\otimes n}$ is, essentially by definition, the number of walks on $\Gamma(V)$ of length $n$ from the trivial representation to itself!
If in addition $V \simeq V^{*}$, then $A$ $\otimes V \simeq A \otimes V^{*} = \textbf{Hom}(V, A)$ (the internal hom), so a form of Frobenius reciprocity then implies that $\Gamma(V)$ is an undirected graph.

When $G$ is finite, $\Gamma(V)$ has finitely many vertices and its adjacency matrix has coefficients

$\displaystyle \frac{1}{|G|} \sum_{g \in G} \chi_A(g) \chi_V(g) \overline{\chi_B}(g)$.

Three thing are unclear to me here:

  1. How does the fact that the multiplicity of an irreducible representation in $V^{\otimes n}$ equals the number of walks on $\Gamma(V)$ of length $n$ from it to itself come from the definition of multiplicity above? I encountered the claim that every irreducible representation of a group $G$ is contained in some tensor power of a representation of $G$, but the proof didn't seem trivial.

  2. How does the undirectness follow from Frobenius reciprocity? I guess it creates a symmetry of multiplicities in the opposite directions but how can one see it rigorously?

  3. Correct me if I'm wrong but as far as I know, "matrix coefficients" refers to "matrix entries". Adjacency matrices have entries $\{0,1\}$, how come we get entries of different values here?

Best Answer

(2) Technically if you're constructing a directed graph, then by fiat you get a directed graph, not an undirected one. But if you get the same number of edges in both directions between every pair of vertices, then you might as well have constructed an undirected graph since having directions may be unnecessary information in that case. (Or, you can tweak the definition of an undirected graph to simply be a directed one with the appropriate symmetry.) That's all that's being said here.

(3) For a simple graph, sure, you get $0$s and $1$s as the matrix entries. But these are not (in general) simple graphs, since they (in general) have multiple edges between vertices. As you ought to be able to guess from context, that means the matrix entry designates not merely if there is an edge from one vertex to another but how many there are from one to another.

The multiplicity of an irrep $U$ in an irrep $V$ is $\dim\hom_G(U,V)=\tfrac{1}{|G|}\sum\overline{\chi_U(g)}\chi_V(g)$, which ought to be in any rep thry text, and which we can apply here to the multiplicity of an irrep $B$ in $V\otimes A$. (And the character of a tensor product is a product of characters.)

(1). The number of walks of length $n$ from one vertex to another is the corresponding entry of the $n$th power of the adjacency matrix. This is a textbook graph theory fact, and makes a good exercise to see this.

Any rep is a direct sum of irreps, so we can specify a rep by the irreps' multiplicity in a vector. Applying the adjacency matrix to this vector produces the same result as tensoring with $V$ and then expressing as a vector!

Related Question