# Understanding special weightings for a digraph / noncommutative polynomial ring

A digraph is defined as $G=(V,E,\phi)$ with

• a set of nodes $V$
• a set of edges $E$
• a mapping $\phi : E \rightarrow V \times V$

A weighting $\mathcal{W}$ for a directed graph $G=(V,E,\phi)$ is a mapping $E \rightarrow R$ from $E$ to a ring $R$. This ring is considered to be the noncommutative polynomial ring $R=\mathbb{C}\left<\Sigma\right>$ over an alphabet $\Sigma$.

Let $\Sigma$ be an alphabet. The addition and multiplication on the set $$\mathbb{C}\langle \Sigma \rangle := \left\{ \sum_{w \in \Sigma^*} a_w w ~|~\begin{array}{c} a_w \in \mathbb{C} \\ a_w = 0/; \mbox{for almost all } w \in \Sigma^* \end{array} \right\}$$ are defined by $$(\sum_{w \in \Sigma^*} a_w w) + (\sum_{w \in \Sigma^*} b_w w) := \sum_{w \in \Sigma^*} (a_w + b_w) w.$$

$$(\sum_{w \in \Sigma^*} a_w w) \cdot (\sum_{w \in \Sigma^*} b_w w) := \sum_{w \in \Sigma^*} (\sum_{uv = w} a_ub_v) w.$$

The set $\mathbb{C}\left<\Sigma\right>$ describes in combination with the given definitions for addition and multiplication a ring with 1.

Hi!

I do understand what a directed graph is, and I generally understand what a weighted direct graph is as well. But I have only used integers for the weightings before.

Could you please explain to me what this ring is (could you please provide a simple example) and how I might understand the last sentence?

A simple example: take $\Sigma$ to be $\lbrace x,y\rbrace$. Then ${\bf C}\langle\Sigma\rangle$ is all the polynomials in $x$ and $y$ with complex coefficients, but with one twist: while you add these things as usual, when you come to multiply them, $xy$ is not the same as $yx$. So that means ${\bf C}\langle\Sigma\rangle$ contains things like $\pi ix^2y^3x^4y^5+\sqrt2yxyxyxy$, and you can't simplify, say, $xyx$ to $x^2y$.
Do you know what a ring is? If so, can you see that with this definition ${\bf C}\langle\Sigma\rangle$ is a ring?
The "1" element is simply 1, just as in the more familiar commutative polynomial rings; it's 1 considered as a polynomial, you could think of it as $1x^0y^0$. The formula you quote for multiplication looks quite forbidding, but as I said it's really the usual way only keeping $xy$ distinct from $yx$. E.g., $(2x+3y)(4x+5y)=6x^2+10xy+12yx+15y^2$, and you're not allowed to take the step of combining terms into $6x^2+22xy+15y^2$ because $xy$ isn't $yx$. Another example: $(x+y)^3=x^3+x^2y+xyx+yx^2+xy^2+yxy+y^2x+y^3$, and no further simplifications are permitted. –  Gerry Myerson Jun 26 '11 at 23:41
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.7897105813026428, "perplexity": 183.23902929090195}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-27/segments/1435375098072.11/warc/CC-MAIN-20150627031818-00288-ip-10-179-60-89.ec2.internal.warc.gz"}