1
$\begingroup$

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?

Thank you in advance!

1 Answers 1

2

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?

  • 0
    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..2011-06-26
  • 0
    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.2011-06-26
  • 0
    Myerson thank you very much!2011-06-27