Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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?

Thank you in advance!

share|cite|improve this question
up vote 2 down vote accepted

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?

share|cite|improve this answer
Myerson Thank you for your answer! Yes, I know what a ring is but haven't heard of "noncommutative rings" before. Can you tell me what the "1" element is for this ring and how multiplying of these elements work exactly? I don't understand the entire definition of the multiplication.. – muffel Jun 26 '11 at 21:32
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
Myerson thank you very much! – muffel Jun 27 '11 at 6:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.