Noncommutative Gröbner Bases. A computational and theoretical tool.

Edward L. Green

Virginia Polytechnic Institute and State Universtity Blacksburg, Virgina USA

December 15, 1996

Overview

These notes consists of five lectures. Each lecture covers the material that I will present with fuller details and exercises. I have also included some material in appendices which the reader might find interesting but which I will not have time to cover in my lectures.

Lecture 1 introduces both linear Gröbner bases and Gröbner bases for algebras.

Lecture 2 surveys some of the basis algorithms of Gröbner basis theory. These include the Division Algorithm, and the Termination Theorem (Bergman’s Diamond Lemma).

Lecture 3 presents the noncommutative version of Buchberger’s algorithm, universal Gröbner bases and considers the special case of finite dimensional algebras.

Lecture 4 applies the theory of Gröbner bases to the study of modules. Projective presentations and resolutions are considered. A method of constructing projective resolutions of finite dimensional modules is given.

Lecture 5 considers further theoretical applications. The study of Koszul algebras via Gröbner bases in presented.

1991 Mathematics Subject Classification. Primary 16W50; Secondary 16G20

1 Gröbner bases

1.1 Linear Gröbner bases

In this section we consider only vector spaces. The ideas introduced here underlie much of what follows.

Throughout these notes, K will denote a field. Let V be a vector space. We fix a K-basis B = {b_{i}}_{i∈I} where I is an index set. One of the essential features of the theory of Gröbner basis is the selection of a well-ordered basis. Recall that < is a well-order on B if < is a total order on B and every nonempty subset of B has a minimal element. The standard axioms of set theory imply that every set can be well-ordered.

Let < be a well-order on B. We recall a basic properties of <.

Proposition 1.1 [15] If B is a set then < is a well-order on B if and only if for each descending chain of elements of B, b_{1} ≥ b_{2} ≥ b_{3} ≥ ⋯, there exists some N > 0, such that b_{N} = b_{N+1} = b_{N+2} = · · ·.

We will keep the following convention for the remainder of these lectures. If I is an index set and v_{i} ∈ V for i ∈ I then ∑_{i∈I} v_{i} implies that all but a finite number of v_{i} = 0. Thus, if I write ∑_{i∈I} α_{i}b_{i} with α_{i} ∈ K and b_{i} ∈ B, then all but a finite number of α_{i} = 0.

One of the main uses of a well-order is to be able to have the notion of a largest basis element in a vector. If v = ∑_{i∈I} α_{i}b_{i} we say b_{i} occurs in v if α_{i} ≠ 0. This leads to the following important definition.

Definition. If B = {b_{i}}_{i∈I} is a a basis of a vector space V and < is a well-order on B, then if v = ∑_{i∈I} α_{i}b_{i} is a nonzero element of V, we say b_{i} is the tip of v if b_{i} occurs in v and b_{i} ≥ b_{j} for all b_{j} occurring in v.

We denote the tip of v by Tip(v). If X is a subset of V we let

Tip(X) = {b ∈ B | b = Tip(x) for some nonzero x ∈ X}.

We let

NonTip(X) = B \ Tip(X).

Thus, both Tip(X) and NonTip(X) are subsets of the fixed basis B. Both sets are dependent of the choice of well ordering of B.

It is not easy to see what the tip set of a subspace is from a generating set. Consider the following example where K is the rational numbers. Let V = K^{7} and B be standard basis ordered by e_{1} > e_{2} > ⋯ > e_{7}. Let W be the subspace spanned by (1, 2, −1, 0, 2, 1, 5), (−1, −2, 0, 0, 1, −1, −3), (1, 2, −1, 0, 5, 1, 6). Then the tip set of W is {e_{1}, e_{3}, e_{5}}. Hence NonTip(W) = {e_{2}, e_{4}, e_{6}, e_{7}}.

We give a fundamental result which will be used often in what follows.

Theorem 1.2 Let V be a vector space over the field K with basis B. Let < be a well-ordering on B. Suppose that W is a subspace of V. Then

V = W ⊕ Span(NonTip(W)).

Proof. First we show that W ∩ Span(NonTip(W)) = (0). Let x ∈ Span(NonTip(W)) \ {0}. If x ∈ W then Tip(x) ∈ Tip(W). But Tip(x) ∈ NonTip(W) since x ∈ Span(NonTip(W)) and we would obtain a contradiction.

Now we show that W + Span(NonTip(W)) = V. This will use that < is a well-order on B. Let v ∈ V be such that Tip(v) is minimal with respect to the property that v ∉ W + Span(NonTip(W)). We wish to show this leads to a contradiction. Consider Tip(v) = b. Let α be the coefficient of b in v. Note that

Tip(v − α · b) < Tip(v).

If b ∈ NonTip(W) then by the above remarks and the minimality condition on v, v − α · b = w + z with w ∈ W and z ∈ Span(NonTip(W)). But since b ∈ NonTip(W), we see

v = w + (z + α · b) ∈ V + Span(NonTip(W)),

a contradiction.

On the other hand, if b ∈ Tip(W) let w ∈ W such that Tip(w) = b. Let α be the coefficient of b in v and β be the coefficient of b in w. Then v − (α/β)w has smaller tip than v. Again, by the minimality condition on v,

v − (α/β) · w = w′ + z,

where w′ ∈ W and z ∈ Span(NonTip(W)). Thus, we get a contradiction, since then

v = (w′ + (α/β)w) + z ∈ W + Span(NonTip(W)).

We now give the definition of a linear Gröbner basis. Let W be a subspace of V. We say a set of vectors G ⊂ W is a linear Gröbner basis for W with respect to < if

Span(Tip(G)) = Span(Tip(W)).

The reader should attempt exercises 1.2 and 1.3 to get a feel for linear Gröbner bases. In particular, those exercises show that if G is a linear Gröbner basis for W, and if w ∈ W \ {0}, then w ∈ Span(G).

Considering the fundamental Theorem 1.2, we see that every nonzero vector v ∈ V can be written UNIQUELY as w_{v} + N(v), where w_{v} ∈ W and N(v) ∈ Span(NonTip(W)).

Definition. We call N(v) the normal form of v.

Let the coefficient of the tip of a vector v be denoted CTip(v). There is a “best” linear Gröbner basis which can be defined as follows.

Definition. Let W be a subspace of V. We say a set G of vectors in W is a reduced linear Gröbner basis for V (with respect to <) if the following conditions hold:

1. G is a linear Gröbner basis of W.

2. If g ∈ G then CTip(g) = 1.

3. If g and g′ are distinct elements of G then Tip(g) ≠ Tip(g′).

4. If g ∈ G then g − Tip(g) ∈ Span(NonTip(W)).

The next result shows the existence and uniqueness of reduced linear Gröbner bases.

Proposition 1.3 Let V be a vector space and < a well-ordering on a basis B of V. Let W be a subspace of V. Then there is a unique linear reduced Gröbner basis of V.

Proof. Let T = Tip(W). Then define G = {t − N(t) | t ∈ cT }. By Theorem 1.2, t − N(t) ∈ W. Now, Tip(t − N(t)) = t since no basis element occuring in N(t) can be the tip of an element in W. Thus G is a linear Gröbner basis of W. The rest of the properties of a reduced linear Gröbner basis are easy to check.

Note that by exercise 1.4, a reduced linear Gröbner basis is in fact a basis. The next result gives both an alogorithm to find the reduced linear Gröbner basis in the finite dimensional case and also, in conjuction with Proposition 1.3, proves the uniqueness of the reduced row echelon form of a matrix. We omit the details of row reduction techniques except to remind the reader that there are three row operations:

1. Multiply a row by a nonzero constant.

2. Interchange two rows.

3. Change a row by adding a multiple of another row to it.

Given an m × n matrix M we view the m rows as vectors in K^{n}. The row space of M is the span of the row vectors. It is easy to see that performing row operations to a matrix does not change the row space.

Since we are fixing a K-basis of our vector space V, if dim_{K}V = n then we will identify V with K^{n} by using the ordering of B. Let {e_{1}, …, e_{n}} be the standard basis for K^{n} and we assume that < is the order e_{1} > e_{2} > ⋯ > e_{n}. Now if W is a subspace of V spanned by vectors w_{1}, …, w_{m} then we view W as the row space of the matrix that has w_{1}, …, w_{m} as the rows.

An m × n matrix M is reduced row-echelon form if

1. For some 1 ≤ r ≤ m the first r rows are nonzero and the last m − r are zero.

2. There is an increasing sequence 1 ≤ c_{1} < c_{2} < ⋯ < c_{r} ≤ n such the first nonzero column in the i^{th} row is c_{i} with entry 1.

3. If i ≠ j then entry in the j^{th} column of the i^{th} is 0.

The proof of the following proposition is left as an exercise.

Proposition 1.4 Let e_{1}, …, e_{n} be the standard basis of K^{n} with well-ordering e_{1} > e_{2} > ⋯ > e_{n}. If M is an m × n matrix is reduced row echelon form with r nonzero rows, then the reduced linear Gröbner basis for the row space M is given by the first r row vectors.

Note that as a consequence of the above discussion, using Theorem 1.2 and the uniqueness of the reduced Gröbner basis, we have an easy proof the uniqueness of the reduced row echelon form of a matrix.

1.2 Rings and Admissible Orders

We now turn our attention to K-algebras. Let R be a K-algebra and let B be a K-basis. We assume that B is a semigroup with 0. That is, assume that under the multiplication of the ring, we have

b, b′ ∈ B implies b · b′ ∈ B or b · b′ = 0.

We call such a K-basis a multiplicative basis of R.

Examples a). Let R = K[x_{1}, …, x_{n}], the commutative polynomial ring in n variables. Let B = {monomials}.

b). Let R = K < x_{1}, …, x_{n} > be the free associative algebra in n noncommuting variables. Let B = {monomials}.

c). Path algebras: Let Γ = (Γ_{0}, Γ_{1}) be a finite directed graph. Here Γ_{0} = {v_{1}, …, v_{n}} will be the vertex set (which we give some arbitrary order) and Γ_{1} = {a_{1}, …, a_{m}} is the arrow set ( which we also give some arbitrary order). Technically, we need two functions from Γ_{1} → Γ_{0} corresponding to the origin vertex of the arrow and the terminus vertex of the arrow. We will denote these by o(a) and t(a) respectively. Furthermore, for vertices we set o(v_{i}) = v_{i} = t(v_{i}).

Let B denote the set of finite directed paths in Γ, including the vertices, which are viewed as paths of length 0. Each path p has a length, l(p), which is the number of arrows in p. We will write paths as follows:

p = a_{i_{1}}a_{i_{2}} ⋯ a_{i_{r}}

where a_{i_{j}} ∈ Γ_{1}, o(a_{i_{j}}) = t(a_{i_{j+1}}) for 1 ≤ j ≤ r − 1. We let o(p) = o(a_{i_{1}}) and t(p) = t(a_{i_{r}}) and say that p is a (directed) path from o(a_{i_{1}}) to t(a_{i_{r}}). Of course in this case l(p) = r.

We give B structure of a semigroup with 0 via concatenation. That is, if p = a_{1} … a_{r} ∈ B and q = b_{1} … b_{s} ∈ B where a_{i}, b_{j} ∈ Γ_{1} then

p · q = \{ \begin{matrix}a_{1} … a_{r}b_{1} … b_{s} if t(a_{r}) = o(b_{1}) \\ 0 otherwise. \end{matrix}

Note that under the above definition, v_{i} · v_{j} is 0 if i ≠ j and is v_{i}v_{i} = v_{i} if i = j.

The fact that B is a semigroup with a relatively easy structure (for computational purposes) is one of the essential features of Gröbner bases. As we will see, reducing computations to B is one of the underlying reasons that the techniques are so powerful.

We are now in a position to introduce the path algebra which we will denote by KΓ. As a K-vector space, KΓ has as a basis B. Thus the elements of KΓ are K-linear combinations of paths and look like

x = ∑_{i=1}^{r} α_{i}p_{i}

where α_{i} ∈ K and p_{i} are paths in B. We call the α_{i} the coefficient of p_{i} and say that p_{i} occurs in x if α_{i} ≠ 0. Having described the additive structure of KΓ we need to give the multiplicative structure. For this, we define the multiplication on B and then extend linearly to all of KΓ. If p, q ∈ B we define via the semigroup multiplication in B. Thus, p · q is 0 if the terminus of p is different than the origin of q, otherwise p · q is the concatenated path pq. We let K act centrally in KΓ by α · ∑ α_{i}p_{i} = ∑(αα_{i})p_{i}. The action of K commutes with all elements of KΓ.

Theorem 1.5 Basic Properties Let K be a field and Γ a finite directed graph. Then (1). KΓ is a K-algebra with 1. (2). 1 = ∑_{v∈Γ_{1}} v. (3). {v : v ∈ Γ_{0}} is a full set of primitive orthogonal idempotents for KΓ (

a primitive idempotent is an idempotent that cannot be written as a sum of two orthogonal nonzero idempotents and we say two idempotents are orthogonal if their product, in either order, is 0)

(4). KΓ is a positively Z-graded ring with the elements of B homogeneous and if p ∈ B has length l then p ∈ (KΓ)_{l}.

(5). KΓ is a tensor algebra.

In Appendix A, we explain how path algebras naturally arise.

Now assume that R is a K-algebra with multiplicative basis B. We do not want an arbitrary well-ordering on B. We want one that works well with the multiplicative structure of B. For this, we introduce the following definition.

We say a well-ordering < on B is admissible if it satisfies the following two conditions where p, q, r, s ∈ B:

1. if p < q then pr < qr if both pr ≠ 0 and qr ≠ 0.

2. if p < q then sp < sq if both sp ≠ 0 and sq ≠ 0.

3. if p = qr then p > q and p > r.

Note that in case R is the commutative or noncommutative polynomial ring, the requirements that pr ≠ 0, qr ≠ 0, sp ≠ 0, and sq ≠ 0 all can be dropped. If R is a path algebra, then we can obtain 0 when multiplying basis elements.

The above properties restrict the orderings under consideration to those that “work well” with the multiplicative structure of B. In the commutative theory of Gröbner bases, admissible orders are usually called “term orders” or “monomial orders”.

We now give some examples which show that there are “natural” admissible orders on B in the case of path algebras. For the following examples, assume we are given a finite directed graph Γ.

Example 1: The (left) length-lexicographic order:

Order the vertices and arrows arbitrarily and set the vertices smaller than the arrows. Thus

v_{1} < ⋯ < v_{n} < a_{1} < ⋯ < a_{m}.

If p and q are paths of length at least 1, set p < q if l(p) < l(q) or if p = b_{1} … b_{r} and q = b′_{1} … b′_{r} with b_{i}, b′_{j} ∈ B then for some 1 ≤ i ≤ r, b_{j} = b′_{j} for j < i and b_{i} < b′_{i}.

The right length-lexicographic order is defined similarly.

Example 2: The (left) weight-lexicographic order:

Let W : Γ_{1} → {1, 2, 3, …} be a set map. Define W : B → {1, 2, 3, …} to be the natural extension. That is, W (v) = 0 if v is a vertex and if a_{i} ∈ Γ_{1} define W (a_{1} ⋯ a_{r}) = ∑_{i=1}^{r} W (a_{i}). Next, order the vertices and set the vertices smaller than the arrows. Order the arrows in such a fashion that if W (a) < W (b) then a < b.

Finally, define p < q if W (p) < W (q) or if W (p) = W (q) then use the left lexicographic order. Notice that the length-lexicographic order is a special case of the weight-lexicographic order. Mainly, give every arrow weight 1.

This order is sometimes called the degree-lexicographic order also.

It should be pointed out that the (left) lex order is NOT admissible in general. For example, if Γ has one vertex and two loops, a and b with b > a then we get

b > ab > aab > aaab > · · · .

Hence it is not a well-ordering. This is different from the commutative case. There are some other, less obvious admissible orders. Example 3: The (left) weight-reverse-lex order: Take W : Γ_{1} → {1, 2, 3, …} and < define on the arrows and vertices as in the

weight-lex order. Note that arrows and paths of positive length have positive weights.

Define p < q if W (p) < W (q) or if W (p) = W (q) then p > q in the right lex order. This is a well-ordering since there are only a finite number paths of any weight.

One final example:

Example 4: The Total Lexicographic Order:

Label the arrows arbitrarily, say a_{1}, …, a_{m}. Arbitrarily order the vertices and let them be smaller than any path of positive length. If p and q are paths, then p < q if there is some i, 1 ≤ i ≤ m, such that the number of a_{j}’s occuring in p and q are the same for j < i and the number of a_{i}’s occurring in p is less than the number of a_{i}’s occurring in q. If p and q have the same number of each arrow then p < q in lexicographic ordering (for some choice of ordering on the arrows).

1.3 Gröbner Bases

Let R be a K-algebra with multiplicative basis B and admissible order <. Let I be an ideal in R.

Definition. We say that a set G ⊂ I is a Gröbner basis for I with respect to < if

<Tip(G)>=<Tip(I)> .

That is, the two-sided ideal generated by the tips of G equals the two-sided ideal generated by the tips of I. Equivalently, G ⊂ I is a Gröbner basis for I if for every b ∈ Tip(I) there is some g ∈ G such that Tip(g) divides b; i.e., there are basis elements p, q ∈ B such that pTip(g)q = b.

We end this section by recalling Theorem 1.2 in the setting of rings. Suppose that R is K-algebra with multiplicative basis B and admissible order <. Then if I is an ideal then

R = I ⊕ Span(NonTip(I))

as vector spaces. In particular, every nonzero element r of R can be written uniquely as r = i_{r} + N(r) where i_{r} ∈ R and N(r) ∈ Span(NonTip(I)). N(r) is still called the normal form of r. In the next lecture, I will address the existence of a reduced Gröbner basis and how to construct Gröbner bases.

Exercises 1.1 Prove Proposition 1.1.

1.2 Prove that if G is linear Gröbner basis of W in V then Span(G) = W.

1.3 Give an example of two vectors v_{1}, v_{2} of R^{5} and different well-orderings of the standard basis B = {e_{1}, e_{2}, …, e_{5}} such that in the first order, {v_{1}, v_{2}} is a linear Gröbner basis of Span(v_{1}, v_{2}) whereas in the second order {v_{1}, v_{2}} is NOT a linear Gröbner basis.

1.4 Prove Propositon 1.4.

1.5 If K is the real numbers and V = R^{6} find the reduced linear Gröbner basis for the span of

(1, 0, 4, 5, −1, 6), (1, 1, 4, 4, −1, 7), (0, 1, 0, −1, 0, −1), (−1, 2, 0, −2, 0, 3).

What is the tip set and the nontip set in this case?

1.6 Pick an example of an admissible order on a path algebra and prove that it is admissible.

2 Algorithms

2.1 Monomial ideals and Reduced Gröbner Bases

We begin with a proposition which shows that not all rings with a multiplicative basis admit an admissible ordering on the basis. Recall, if B is a subset of R we say b_{1} divides b_{2} (in B) if b_{1}, b_{2} ∈ B and there are elements c, d ∈ B such that b_{2} = cb_{1}d.

Proposition 2.1 If a multiplicative basis B of a ring R admits an admissible order then every infinite sequence of elements of B, b_{1}, b_{2}, b_{3}, ⋯, such that b_{i} divides b_{i−1} for i ≥ 1 stabilizes; that is, for some N, b_{N} = b_{N+1} = b_{N+2} = · · ·.

Proof. The proof follows for the properties of an admissible order. Namely, suppose > is an admissible order for B. Then, if b_{i} divides b_{i−1}, we get b_{1} ≥ b_{2} ≥ b_{3} ≥ · · ·. Since < is a well-ordering of B, we get the desired result.

Let R be a ring with multiplicative basis B. We will call the elements of B monomials. We say an ideal I in R is a monomial ideal if it can be generated by elements of B. The next proposition is important in the definition of a reduced Gröbner basis.

Proposition 2.2 Let R be K-algebra with multiplicative basis B which admits an admissible order. If I is a monomial ideal then I has a unique minimal monomial generating set.

Proof. Consider the set A of all monomials in I. Let M = {p ∈ A | if q ∈ A divides p then q = p}. Note that by Proposition 2.1, M is not empty. We claim that M is the unique minimal generating set of I. To show that M generates I, let B be a set of monomials that generates I. If b ∈ B, then for some m ∈ M, m divides b. Hence, B ⊂<M >. Thus I ⊂<M >.

If M′ is another set of monomial set of generators of I, then every m ∈ M is divisible by some m′ ∈ M′. But then, by definition of M, m = m′ and we have shown that M ⊂ M′.

Note that the minimal set of generators given in the above proposition is independent of any particular admissible order. The existence of an admissible order is necessary to show that M is nonempty. Furthermore, it is possible that the unique minimal monomial generating set is not finite. See exercise 2.1. This differs from the commutative case in that Dickson’s Lemma [15] proves that every monomial ideal in commutative polynomial ring is can be generated by a finite number of monomials. Good references for the commutative theory are [15, 9, 1].

Let I be an ideal in R and < an admissible order on a multiplicative basis B. Then if G is a Gröbner basis of I, then Tip(G) must contain the minimal monomial generating set of <Tip(I)>.

If I is an ideal in R, we let I_{MON} be the ideal generated by Tip(I) (given some admissible order <). Then there is a unique minimal monomial generating set T of I_{MON}.

Definition. The reduced Gröbner basis for I with respect to < is

G = {t − N(t) | t ∈ T }.

The proof of the next result is left as an exercise.

Proposition 2.3 Let < be an admissible order on a multiplicative basis B of a K-algebra R. Let I be an ideal in R. Let G be the reduced Gröbner basis for I. Then the following holds.

1. G is a Gröbner basis for I.

2. If g ∈ G then CTip(g) = 1.

3. If g ∈ G then g − Tip(g) ∈ Span(NonTip(I)).

4. Tip(G) is the minimal monomial generating set for I_{MON}.

2.2 The Division Algorithm

In this section, we present a “division algorithm” in the rings we are studying. Throughout this section, we fix a K-algebra R with multiplicative basis B and admissible order <.

Given an ORDERED set of elements X = {x_{1}, x_{2}, …, x_{n}} of R and another element y ∈ R we show how to “divide” y by the set. We emphasize that the order of the elements affects the outcome of the division algorithm. What should division mean in this context? We mean that we find nonnegative integers m_{1}, …, m_{n} and elements u_{i,j}, v_{i,j}, r ∈ R for 1 ≤ i ≤ n and 1 ≤ j ≤ m_{i} such that

1. y = ∑_{i=1}^{n}(∑_{j=1}^{m_{i}} u_{i,j}x_{i}v_{i,j}) + r.

2. Tip(y) ≥ Tip(u_{i,j}x_{i}v_{i,j}) for all i and j.

3. For b ∈ B occurring in r, Tip(x_{i}) does not divide b for 1 ≤ i ≤ n.

Note that it follows that Tip(r) ≤ Tip(y). We will call r a remainder by division by x_{1}, …, x_{n}.

We now present the algorithm in psuedo-code. The Division Algorithm

INPUT: x_{1}, …, x_{n} (ordered), y OUTPUT: m_{1}, …, m_{n}, u_{i,j}, v_{i,j}, r INITIALIZE: m_{1} := 0, …, m_{n} := 0,r := 0,z := y,DIVOCCUR:=False WHILE(z ≠ 0 and DIVOCCUR==False) DO

FOR(i = 1) TO n DO

IF Tip(z) = uTip(x_{i})v for u, v ∈ B THEN · m_{i} := m_{i} + 1 · u_{i,m_{i}} := [CTip(z)/CTip(x_{i})]u · v_{i,m_{i}} := v · z := z − [CTip(z)/CTip(x_{i})]ux_{i}v · DIVOCCUR:=True

ELSE i := i + 1 IF DIVOCCUR==False THEN r:= r + CTip(z)Tip(z) z:= z-CTip(z)Tip(z)

We leave it to the reader to analyze the algorithm and show that it does what it is supposed to do. We give one small example.

Example. Let R be the noncommutative polynomial ring in three noncommuting variables x, y, z over a field K. Let B be the set of monomials and < the length-lexicographic order with x > y > z. Let’s divide xy−x = f_{1}, xx−xz = f_{2} into zxxyx. Note that the tip of f_{1} is xy and tip of f_{2} is xx.

Beginning the algorithm, we see that zxxyx = (zx)Tip(f_{1})x.

Thus u_{1,1} = zx, v_{1,1} = x and we replace zxxyx by zxxyx − zx(f_{1})x = zxxx. Now Tip(f_{1}) does not divide zxxx. Continuing, Tip(f_{2}) does. There are two ways to divide zxxx by xx and for the algorithm to be precise we must choose one. Say we choose the “left most” division. Then zxxx = z(Tip(f_{2}))x and we let u_{2,1} = z, v_{2,1} = x and replace zxxx by zxzx. Neither Tip(f_{1}) nor Tip(f_{2}) divide zxzx so we let r = zxzx and zxzx is replaced by 0 and the algorithm stops. We have

zxxyx = (zx)f_{1}x + zf_{2}x + zxzx.

The remainder is zxzx.

Note that if we interchange the order of f_{1} and f_{2} (so we start with f_{2} first) we see the outcome of the division algorithm is

zxxyx = z(f_{2})yx + zxzyx,

which gives a different remainder, namely, zxzyx.

Definition. If X = {x_{1}, …, x_{n}} (as an ordered set) and y is divided by X, we will denote the remainder r by y ⇒_{X} r.

If one had an infinite set X = {x_{1}, x_{2}, …} with Tip(x_{1}) ≤ Tip(x_{2}) ≤ Tip(x_{3}) ≤ ⋯ and only a finite number of x_{i}’s with a given tip, we could perform division by X. For, given y, there can only be a finite number of x_{i}’s such that Tip(x_{i}) ≤ Tip(y), say x_{1}, …, x_{n}. By the desired properties of division, x_{n+1}, x_{n+2}, … would never occur since we want Tip(y) ≥ Tip(u_{i,j}x_{i}v_{i,j}). Thus, we may divide by an infinite set of elements of R provided that that the set has the desired properties described earlier in the paragraph.

Now we show that when we have a Gröbner basis, the order of the x_{i}’s does not affect the remainder!

Proposition 2.4 If G be a Gröbner basis for an ideal I in R. Let y ∈ R and assume that X = {g_{1}, …, g_{n}} = {g ∈ G | Tip(g) ≤ Tip(y)}. If y ⇒_{X} r then r is independent of the order of g_{1}, …, g_{n} in X. In fact, r = N(y).

Proof. Consider y ⇒_{X} r. Then, since Tip(r) ≤ Tip(y), we see that for each g ∈ G, Tip(g) does not divide any basis element occurring in r. Hence r ∈ Span(NonTip(I)). Now y = ∑_{i} ∑_{j} u_{i,j}g_{i}v_{i,j} + r. But Theorem 1.2 implies that y = i_{y} + N(y) with i_{y} ∈ I and N(y) ∈ Span(NonTip(I)) unique. But ∑_{i} ∑_{j} u_{i,j}g_{i}v_{i,j} ∈ I and r ∈ Span(NonTip(I)). Hence r = N(y).

Corollary 2.5 If G is a Gröbner basis of an ideal I in R such that for each b ∈ B there are only a finite number of elements g in G with Tip(g) ≤ b then there is an algorithm to find the normal form of elements of R.

In practice, Gröbner bases are found with only a finite number of terms with a given tip and hence the division algorithm gives an algorithm to find normal forms. Moreover, this is usually a “fast algorithm”. The difficulty is in constructing Gröbner bases!

Note that we also now have a method to find the reduced Gröbner basis once we have found a Gröbner basis with only a finite number of terms with a given tip. This is an algorithm if I_{MON} has a finite set of monomial generators. The method proceeds as follows:

1. Given a Gröbner basis G such that only a finite number terms of G have a given tip.

2. Output will be the reduced Gröbner basis.

3. Find the minimal monomial generating set T of I_{MON}.

4. For each t ∈ T , using the division algorithm, calculate t ⇒_{G} N(t).

5. The reduced Gröbner basis is {t − N(t) | t ∈ T }.

2.3 Overlap relations and the Termination Theorem

In this section, we give the noncommutative version of the S-polynomial found in commutative theory [15, 9]. We call these overlap relations. Throughout this section, R will be a K-algebra with multiplicative basis B and admissible order < for B.

Definition. Let f, g ∈ R and suppose that there are elements b, c ∈ B such that

1. Tip(f)c = bTip(g).

2. Tip(f) does not divide b and Tip(g) does not divide c.

Then the overlap relation of f and g by b, c is

o(f, g, b, c) = (1/CTip(f))fc − (1/CTip(g))bg.

Note that Tip(o(f, g, b, c)) < Tip(f)c = bTip(g). We give some examples to help clarify overlap relations. Examples Let R = KΓ where Γ is the graph:

\begin{matrix}v_{1}• & →^{a} & •v_{2} \\ d ↑ & & ↓ b \\ v_{4}• & ←^{c} & •v_{3} \\ g ↑ & & ↓ e \\ v_{6}• & ←^{f} & •v_{5} \end{matrix}

Use the length-lexicographic order with v_{1} < ⋯ < v_{6} < a < b < c < ⋯ < g. Consider p = abcdabcd − abefgd and q = cdabcda − efgda. There are a number of overlap relations between p and q. We list them below.

1. o(p, q, a, ab) = p · a − ab · q = (−abefgd)a + abefgda = 0.

2. o(p, q, abcda, abcdab) = p·abcda−abcdab·q = −abefgdabcda+abcdabefgda ≠ 0.

3. o(q, p, bcd, cd) = −efgdabcd + cdabefgd ≠ 0.

4. o(q, p, bcdabcd, cdabcd) = −efgdabcdabcd + cdabcdabefgd ≠ 0.

As the above example shows, we need to look at all overlaps, including self overlaps; that is, overlaps of the form o(f, f, p, q). In this example, we have self overlaps o(p, p, abcd, abcd) and o(q, q, cdab, bcad). In the commutative case, one only uses the least common multiple of the leading monomials. In the noncommutative case, we must look at all overlaps.

Next we consider “tip reduction”. Suppose that X = {x_{1}, …, x_{n}} is a set of elements in R. Let I be the ideal generated by X. If Tip(x_{i}) = uTip(x_{j})v for some u, v ∈ B, then letting

X′ = {x_{1}, …, x_{i−1}, x_{i} − [CTip(x_{i})/CTip(x_{j})]ux_{j}v, x_{i+1}, …, x_{n}}

we that X′ is a generating set of I also. Continuing in this fashion, we will obtain a finite set of generators of I such that no tip of a generator divides the tip of another generator. This process is finite by the well-ordering assumption on <. Thus it is not unreasonable to assume that we have no tip divisions on a set of generators of an ideal.

Definition. We say a set of elements X is tip reduced if for distinct elements x, y ∈ X, Tip(x) does not divide Tip(y).

Before giving the termination theorem, we need one more concept: uniformity. Definition. We say an element ∑_{i=1}^{n} α_{i}b_{i}, with α_{i} ∈ K^{∗} and b_{i} ∈ B, is uniform if for each c ∈ B, either cb_{i} = 0 for all i, 1 ≤ i ≤ n or cb_{i} ≠ 0 for all i, 1 ≤ i ≤ n.

Note that in the case of a noncommutative polynomial ring with B = {monomials}, all elements are uniform. In the case of a path algebra, with B = {finite directed paths}, then an element ∑_{i=1}^{n} α_{i}p_{i} is uniform if and only if there are vertices v, w such that for 1 ≤ i ≤ n, the origin vertex of p_{i} is v and the terminus vertex is w. Note that every element x ∈ KΓ is a sum of uniform elements. Since 1 = v_{1} + ⋯ + v_{n}, we have x = ∑_{i,j=1}^{n} v_{i}xv_{j} and we see that v_{i}xv_{j} is uniform since all the paths that occur must have origin vertex v_{i} and terminus vertex v_{j}. It follows that every ideal in a path algebra can be generated by uniform elements.

We also note that if f ∈ R is a uniform element and b ∈ B then both bf and fb are either 0 or uniform elements. We also remark that elements of B are uniform.

We now give the termination theorem which is a version of G. Bergman’s Diamond Lemma [11, 16].

Theorem 2.6 Let R be a K-algebra with multiplicative basis B and admissible order <. Suppose the G is a set of uniform, tip reduced elements of R. Suppose for every overlap relation

o(g_{1}, g_{2}, p, q) ⇒_{G} 0,

with g_{1}, g_{2} ∈ G. Then G is a Gröbner basis for <G >.

A proof of the theorem can be found in Appendix B. Note also that if division by G of some overlap relation is NOT 0, then G is not a Gröbner basis. This is easy to see since the remainder will have tip which is not divisible by the tip of any element of G. Thus, when the hypothesis of Theorem 2.6 are met, we have a fast algorithm to determine if G is a Gröbner basis (assuming G is finite). Example Let R = KΓ where Γ is the graph:

•^{v_{1}}  \begin{matrix}a \\ → \\ ← \\ d \end{matrix}  •^{v_{2}}  \begin{matrix}b \\ → \\ ← \\ c \end{matrix}  •^{v_{3}}

Let >_{1} be the length-lexicographic order with v_{1} < v_{2} < v_{2} < d < c < b < a. Consider G = {cdab − cb, bc − da}. Both elements are uniform and tip reduced. Then

o(bc − da, cdab − cb, dab, b) = −dadab + bcb ⇒_{G} −dadab + dab ≠ 0.

Hence G is not a Gröbner basis with respect to >_{1}.

But if we change >_{1} to >_{2} which is the length-lexicographic order with v_{1} < v_{2} < v_{3} < a < b < c < d then Tip(cdab−cb) = cdab and Tip(bc−da) = da. Thus the set is not tip reduced. If we tip reduce G we get G′ = {cbcb − cb, −da + bc}. Then Tip(cbcb − cb) = cbcb and Tip(−da + bc) = da. The only overlap relation is

o(cbcb − cb, cbcb − cb, cb, cb) = 0.

Hence all overlap relations have remainder 0 and we conclude that under >_{2}, G′ is a Gröbner basis.

Exercises 2.1 Show that in the free algebra in two noncommuting variables, there is a monomial ideal with no finite generating set.

2.2 Let I be an ideal in R and < an admissible order on a multiplicative basis B of R. Prove that if G is a Gröbner basis of I, then Tip(G) must contain the minimal monomial generating set of I_{MON}.

2.3 Give an example of a K-algebra R with a multiplicative basis B which does NOT admit an admissible order.

2.4 Prove Proposition 2.3

2.5 Let R be the noncommutative polynomial ring in variables x, y, z. Let < be the degree-lexicographic order with x > y > z. Find all overlap relations of f = 2xyzyxyx − 3yy and g = yxyxyz + 4yxy.

2.6 Let KΓ be the path algebra given in the last example of this section. Let G = {bc − da, ad, cb, ab, cd} is a Gröbner basis of the ideal it generates for every admissible order.

3 Computational Aspects

3.1 Construction of Gröbner bases

In this section we present the noncommutative analog of Buchberger’s algorithm [13] for constructing Gröbner bases. Given uniform elements f_{1}, …, f_{n} in R, let I =< f_{1}, …, f_{n} >. Hence, by construction, I is generated by a set of uniform elements. The algorithm produces a (possibly infinite) sequence of uniform elements g_{1}, g_{2}, … where g_{i} = f_{i} for 1 ≤ i ≤ n and, for i > n, g_{i} ∈ I such that Tip(g_{i}) ∉< Tip(g_{1}), Tip(g_{2}), …, Tip(g_{i−1}) >. It can be shown that {g_{1}, g_{2}, …, g_{m}, g_{m+1}, …} is in fact a Gröbner basis for I. We present the algorithm in psuedocode.

INPUT: f_{1}, …, f_{n}

OUPUT: g_{1}, g_{2}, g_{3}, ⋯

FOR i = 1 TO n DO

g_{i} := f_{i}

G := {g_{1}, …, g_{n}}

Count:=n

DO

H := G

FOR each pair of elements h, k ∈ H AND each overlap relation of h, k DO

IF o(h, k, p, q) ⇒_{H} r AND r ≠ 0 DO Count:=Count+1 gCount = r G := G ∪ {gCount}

WHILE(H ≠ G)

Modifying the proof of the termination theorem found in Appendix B, it can be shown that if b ∈ B is a minimal monomial generator of I_{MON} then for some m, Tip(g_{m}) = b. From this we get the next result.

Proposition 3.1 If I_{MON} has a finite set of monomial generators then the above algorithm terminates in a finite number of steps and yeilds a finite Gröbner basis.

Proof. If I_{MON} has a finite set of mononial generators, then the unique minimal monomial generating set must be finite. Suppose T = {t_{1}, …, t_{s}} is the finite generating set of minimal monomials for I_{MON}. Then, by the remarks preceeding the proposition, T ⊂ {Tip(g_{1}), …, Tip(g_{N})} for sufficiently large N. But then Tip({g_{1}, …, g_{N}}) generates I_{MON} and hence is a Gröbner basis of I. But then division by {g_{1}, …, g_{N}} can only have remainder 0 since all overlap relations are elements of I. Thus the algorithm terminates in a finite number of steps outputting a Gröbner basis.

For a discussion of improvements of the Buchberger algorithm in the commutative case we refer to [9]. Most of the discussion there can be translated to the noncommutative case.

3.2 Basic Computational Use of Gröbner Bases

We are interested in studying quotient rings R/I. Elements of R/I consist of equivalence classes of the form f + I where f ∼ g if and only if f − g ∈ I. The K-algebra has addition and multiplication given by

\begin{aligned}(f + I) + (g + I) & = ((f + g) + I) \\ (f + I) · (g + I) & = ((fg) + I) \end{aligned}

To study R/I we need a way studying the equivalence classes f+I. Assuming we have R represented on a computer via the given multiplicative basis B, we would like to be able to find “good” representatives of equivalence classes. But given an admissible order > on B and we have such representatives.

Proposition 3.2 Let R be a K-algebra with multiplicative basis B and admissible order > on B. Let I be an ideal in K.

1. f + I = g + I if and only N(f) = N(g).

2. f + I = N(f) + I.

3. The map σ : R/I → R with σ(f + I) = N(f), is a vector space splitting to the canonical surjection π : R → R/I .

4. σ is a K-linear isomorphism between R/I and Span(NonTip(I)).

5. Identifying R/I with Span(NonTip(I)), then NonTip(I) is a K-basis of R/I contained in B.

Proof. The first two parts are immediate consequences of Theorem 1.2 which states that R = I ⊕ Span(NonTip(I)). The remaining parts are left as an exercise.

Thus, normal forms solves the problem of finding representatives of the equivalence classes. Furthermore, addition of two equivalence classes (f + I) + (g + I) is given simply by N(f) + N(g) = N(f + g) since Span(NonTip(I)) is a linear subspace of R. By Proposition 3.2, since N(f) ∈ f + I we see that multiplication of classes is given by

N(N(f) · N(g)),

that is, to find the representative of (f + I) · (g + I) simply multiply N(f)N(g) in R and then take the normal form of the result.

As pointed out in the last lecture, once a Gröbner basis has been found, the division algorithm provides a fast algorithm to find normal forms. In this way, one can use the computer to study quotient rings R/I.

3.3 Finite Dimensional Algebras

Suppose that R/I is finite dimensional. What further can be said?

Proposition 3.3 Let R be a finitely generated K-algebra with multiplicative basis B and admissible order >. Suppose that I is an ideal such that dim_{K}(R/I) = N. Then I_{MON} has a finite set of monomial generators.

Proof. Since R/I is isomorphic to Span(NonTip(I)) as vector spaces, it follows that NonTip(I) is a finite set since it is a basis of Span(NonTip(I)). Next, since R is finitely generated as an algebra, B is finitely generated as a semigroup (exercise 3.4).

Let X = {b_{1}, …, b_{k}} generate B. We show

{bc | b ∈ X and c ∈ NonTip(I)} ∩ Tip(I)

generates I_{MON}. Suppose that t is a element of the minimal monomial generating set of I_{MON}. Then t = b_{i_{1}}b_{i_{2}} ⋯ b_{i_{l}} with b_{i_{j}} ∈ X. By minimality, b_{i_{2}} ⋯ b_{i_{l}} ∉ Tip(I). Thus, b_{i_{2}} ⋯ b_{i_{l}} ∈ NonTip(I). Hence t = b_{i_{1}}c with c ∈ NonTip(I). This completes the proof.

The above result has the following immediate consequence.

Corollary 3.4 Let R be a finitely generated K-algebra with multiplicative basis and admissible order >. Suppose that I is an ideal generated by uniform elements and R/I is finite dimensional. Then I has a finite uniform Gröbner basis with respect to > and can be computed in a finite number of steps by the above algorithm.

Open Question: Given R and a multiplicative basis B. Find necessary and sufficient conditions on an ideal I in R such that there is some admissible order < for which I has a finite Gröbner basis.

3.4 Universal Gröbner Bases

If R is a K-algebra with multiplicative basis B. Assume that R is finitely generated and hence so is B. Fix a set of generators of the semigroup B, b_{1}, …, b_{n}. Definition. If b ∈ B we define the length of b to be k if b is a product of k generators and cannot be written as a product of fewer than k generators. We denote the length of b by length(B).

Thus length(b_{i}) = 1 for i = 1, …, n and if b ∈ B, length(b) ≥ 1.

Let I be an ideal in R.

Definition. We say a set of elements G in I is a universal Gröbner basis for I if for every admissible order >, G is a Gröbner basis with respect to >.

In some cases, finite universal Gröbner bases exist.

Example Let R be the noncommutative polynomial ring in three noncommuting variables x, y, z over the rational numbers. Let B be the set of monomials. Let I be the ideal generated by xy − 2yx, zx, zy. This set is a universal Gröbner basis since all overlap relations reduce to 0 whether the tip of xy − 2yx is xy or is yx. Hence the order doesn’t affect that the set is a Gröbner basis. Note that R/I is not even noetherian.

In general, it is not known which ideals have finite universal Gröbner bases. One of the difficulties with this problem in the noncommutative case is that admissible orders are not classified.

We will show that finite universal Gröbner bases exist if R/I is finite dimensional. For this we introduce some terminology. If V is a vector space with basis B, then the support of a vector v, supp_{B}(v), is defined to be

supp_{B}(v) = {b ∈ B | b occurs in v}.

If X is a subset of V, the support of X is

supp_{B}(X) = {supp_{B}(x) | x ∈ X}.

Proposition 3.5 Let R be a finitely generated K-algebra with multiplicative basis B which admits an admissible order. Let I be an ideal such that R/I is finite dimensional. Then there exists a finite universal Gröbner basis for I.

Proof. Let d = dim_{K}(R/I) and let π : KΓ → KΓ/I be the canonical surjection. Assume that B is generated by X = {b_{1}, …, b_{n}}. We claim that every b ∈ B with of length longer than D = (d + 2)n has a factor which is the tip of an element in I of smaller length. That is, if the length of p is greater than D, then there is some momomial q of smaller length such that p = sqt and such that q is the tip of some element in I. Suppose p is a monomial of length longer than D. Write p = b_{i_{1}}b_{i_{2}} … b_{i_{E}} with b_{i_{j}} ∈ X and E > D. Then some generator of B, say b^{∗}, must occur at least d + 2 times. Hence we have a factorization of p into monomials, p = p_{1}c_{1} ⋯ c_{d+1}p_{2}, where each c_{i} is of the form b^{∗}b_{i_{j}} … b^{∗} and is of length at least 1 but of length less than the length of p. Since dim_{K}(R/I) = d, the set {π(c_{1}), …, π(c_{d+1})} is linearly dependent over K. Therefore there is a nontrivial linear combination x = ∑_{j=1}^{d+1} α_{i}c_{i} ∈ I. Thus, some c_{i} is a tip in the given ordering and we have proven the claim.

Now let V be the vector subspace of R with basis Ω consisting of monomials of length bounded by D. Let Y be the subspace I ∩ V of V. Since V is finite dimensional, the support of Y is a finite set, say supp_{Ω}(Y) = {s_{1}, …, s_{m}}. For each s_{i} ∈ supp_{Ω}(X), choose an element f_{i} ∈ I such that supp(f_{i}) = s_{i}. We now show that G = {f_{1}, …, f_{m}} is a universal Gröbner basis for I.

Let < be an admissible order and let h ∈ I. Suppose the remainder h^{∗} of division of h by G is not 0. No monomial occuring in h^{∗} is divisible by any Tip(f_{i}), i = 1, …, m. Let h^{∗} have that property that the longest monomial in h^{∗} is minimal in the set of all h ∈ I such that no monomial in h is divisible by any Tip(f_{i}). Let C be the length of the longest monomial in h^{∗}. If C ≤ D then supp(h^{∗}) ∈ supp_{Ω}(Y) and hence there is some f_{i} ∈ G such that supp(f_{i}) = supp(h^{∗}). But then Tip(f_{i}) = Tip(h^{∗}), a contradiction. If C > D, then by an earlier argument, if p ∈ B has length greater than D and occurs in h^{∗}, then there is some f ∈ G such that Tip(f) is a subpath of p. Thus, p can be reduced by an element in G. But this contradicts our assumption on h^{∗} and we are done.

Exercises 3.1 In K < x, y, z > with the degree-lexicographic order and x > y > z, apply the algorithm to find the Gröbner basis for the ideal generated by xx − y.

3.2 Let R = KΓ where Γ is the graph

\begin{matrix}v_{1}• & →^{a} & •v_{2} \\ d ↑ & & ↓ b \\ v_{4}• & ←^{c} & •v_{3} \\ g ↑ & & ↓ e \\ v_{6}• & ←^{f} & •v_{5} \end{matrix}

Use the length-lexicographic order with v_{1} < ⋯ < v_{6} < a < b < c < ⋯ < g. Find the Gröbner basis for the ideal generated by abefgd − abcd, gdabcda − gda, abcda, bcdab, cdabc, dabcd.

3.3 Complete the proof of Proposition 3.2.

3.4 Prove that if the K-algebra R is finitely generated as an algebra then any multiplicative basis B of R is finitely generated as a semigroup.

4 Modules, Presentations and Resolutions

In this lecture I will address the problem of studying R/I-modules. If R/I is not finite dimensional and the module is not finite dimensional, then the only possibility of computationally handling this situation is using generators and relations; a setup ideally suited for the use of the theory of Gröbner bases. Throughout this section we fix a K-algebra R, a multiplicative basis B, and an admissible order >. Also fix an ideal I in R and assume we have a Gröbner basis G of I with respect to >.

4.1 Modules

Suppose that M is a finitely presented right R/I-module. This means that M is the cokernel of a map between finitely generated projective R/I-modules. This is equivalent to assuming that M is the cokernel of a map between to finitely generated free R/I-modules.

Let f_{1} : F_{1} → F_{0} be an R/I-homomorphism between finitely generated free right R/I-modules. We choose bases for F_{0} and F_{1}, say {e_{1}, …, e_{n}} for F_{0} and {d_{1}, …, d_{m}} for F_{1}. Then f_{1} is given by an m × n matrix A_{f_{1}} = (a_{i,j}) where a_{i,j} ∈ R/I. Then

f_{1}(d_{i}) = ∑_{j}^{n} e_{j}a_{i,j}.

Let M = Coker(f_{1}) = F_{0}/Im(f_{1}) and let f_{0} : F_{0} → M be the canonical map.

Note that computationally, we can represent the matrix A_{f_{1}} by an m × n matrix with entries in Span(NonTip(I)).

Before specializing, I present a way of viewing M as an ideal in a ring where we can use Gröbner basis theory to study M. In the representation theory of finite dimensional algebras, this is called “one point extension”.

Let S̄ = ( \begin{matrix}K & M \\ 0 & R/I \end{matrix} ). Note that multiplication is just matrix multiplication; namely,

( \begin{matrix}k & m \\ 0 & r \end{matrix} ) · ( \begin{matrix}k′ & m′ \\ 0 & r′ \end{matrix} ) = ( \begin{matrix}kk′ & km′ + mr′ \\ 0 & rr′ \end{matrix} ) ,

which makes sense in that we view M as a K-R/I-bimodule (with elements of K commuting will elements of M).

We now show how to view S̄ as quotient of a K-algebra for which we can find a multiplicative basis and an admissible order related to that of R.

Let G_{0} = ∐_{i=1}^{n} R with basis e_{1}^{∗}, …, e_{n}^{∗}.

Define S to be the K-algebra by S = ( \begin{matrix}K & G_{0} \\ 0 & R \end{matrix} ). Set π : S → S̄ by

π(( \begin{matrix}k & ∑_{i=1} e_{i}^{∗}r_{i} \\ 0 & r \end{matrix} )) = ( \begin{matrix}k & f_{0}(∑_{i=1} e_{i}^{∗}N(r_{i})) \\ 0 & N(r) \end{matrix} ) .

Note that we have identified R/I with Span(NonTip(I)). Let I^{∗} = Ker(π). We now give a multiplicative basis for S. Let B^{∗} be the set

\{( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} )\} ∪ \{( \begin{matrix}0 & 0 \\ 0 & b \end{matrix} ) | b ∈ B\} ∪ \{( \begin{matrix}0 & e_{i}^{∗}b \\ 0 & 0 \end{matrix} ) | 1 ≤ i ≤ n, b ∈ B\}.

We can define an order <^{∗} on B^{∗} by ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) <^{∗} ( \begin{matrix}0 & 0 \\ 0 & b \end{matrix} ) for each b.

( \begin{matrix}0 & 0 \\ 0 & b \end{matrix} ) <^{∗} ( \begin{matrix}0 & 0 \\ 0 & b′ \end{matrix} ) if b < b′. ( \begin{matrix}0 & 0 \\ 0 & b \end{matrix} ) <^{∗} ( \begin{matrix}0 & e_{i}^{∗}b′ \\ 0 & 0 \end{matrix} ) for all b, b′ and

all i. Finally, ( \begin{matrix}0 & e_{i}^{∗}b \\ 0 & 0 \end{matrix} ) <^{∗} ( \begin{matrix}0 & e_{j}^{∗}b′ \\ 0 & 0 \end{matrix} ) if i < j or if i = j, b < b′.

We leave it to the reader to check that <^{∗} is an admissible order on B^{∗}. Next we give a set of generators for I^{∗}. Assume I is generated by {h_{i}}_{i∈I} in R. Then I^{∗} is generated by

(∗) \{( \begin{matrix}0 & 0 \\ 0 & h_{i} \end{matrix} ) | i ∈ I\} ∪ \{( \begin{matrix}0 & ∑_{j=1}^{n} e_{j}^{∗}a_{i,j} \\ 0 & 0 \end{matrix} ) | 1 ≤ i ≤ m\}.

Note that we view the elements a_{i,j} ∈ Span(NonTip(I)) in this setting as elements of R. Again the reader may check that (*) is a generating set for I^{∗}. Under reasonable circumstances, we can find a Gröbner basis for I^{∗} with respect to >^{∗}. For example, if R is a path algebra, then S is also a path algebra and hence we can algorithmically find Gröbner bases.

Applying Theorem 1.2, we get S = I^{∗} ⊕ Span(NonTip(I^{∗})). Remember that S/I^{∗} = ( \begin{matrix}K & M \\ 0 & R/I \end{matrix} ). In particular, M can be identified with ( \begin{matrix}0 & M \\ 0 & 0 \end{matrix} ). It

follows that the elements of NonTip(I^{∗}) of the form ( \begin{matrix}0 & c \\ 0 & 0 \end{matrix} ) form a K-basis

of M. Noting that if x ∈ I then ( \begin{matrix}0 & 0 \\ 0 & x \end{matrix} ) ∈ I^{∗} and hence ( \begin{matrix}0 & e_{i}^{∗}x \\ 0 & 0 \end{matrix} ) ∈ I^{∗} we conclude that the c’s occurring in the K-basis of M are all of the form ∑_{i=1}^{n} e_{i}^{∗}c_{i} with c_{i} ∈ Span(NonTip(I)).

Finally, assuming that a Gröbner basis of uniform elements of I^{∗} can be computed, we note that the normal form of an element of M, ( \begin{matrix}0 & c \\ 0 & 0 \end{matrix} ), when

multiplied by an element of R/I, ( \begin{matrix}0 & 0 \\ 0 & b \end{matrix} ), yeilds an element of the form

( \begin{matrix}0 & c′ \\ 0 & 0 \end{matrix} ) with c′ = ∑_{i=1}^{n} e_{i}^{∗}c_{i}^{∗} with c_{i}^{∗} ∈ Span(NonTip(I)).

We identify R/I with Span(NonTip(I)) (as usual) and M with c = ∑_{i=1}^{n} e_{i}^{∗}c_{i} ∈ G_{0} where c_{i} ∈ Span(NonTip(I)) with ( \begin{matrix}0 & c \\ 0 & 0 \end{matrix} ) ∈ Span(NonTip(I^{∗})). Note that such c can in fact be viewed as in F_{0} and with this identification, we get a vector space splitting σ : M → F_{0} of f_{0} : F_{0} → M by σ(m) = N(( \begin{matrix}0 & g \\ 0 & 0 \end{matrix} )) where f_{0}(g) = m.

Stepping back from the above details, what we have is the following, assuming we can compute a Gröbner basis of uniform elements of I^{∗} algorithmically:

1. One can compute a K-basis of M inside F_{0} algorithmically; namely, the Gröbner basis of I^{∗} with respect to >^{∗}.

2. One can algorithmically compute the action of R/I on this basis; namely, the computation of the normal form of the product.

In practice, we can use a Gröbner basis of I with respect to > in that the elements ( \begin{matrix}0 & 0 \\ 0 & g \end{matrix} ) are part of a Gröbner basis of I^{∗}. Once the Gröbner basis for I^{∗} is computed, operations by elements of R/I on M can be performed using fast algorithms.

4.2 Projective Resolutions

In this section, we use the results of the previous section and Gröbner bases to construct projective resolutions of modules. We need to require more properties of R.

Our goal is to show how to algorithmically construct a projective R/Iresolution of a right R/I-module M. This construction will use both the construction of Gröbner bases, overlap relations and the division algortithm.

In this section we assume

1. R has a multiplicative basis B and an admissible order >.

2. R is a finitely generated K-algebra and B is generated by X = {b_{1}, …, b_{n}}.

3. Every element of B is a unique product of elements of X; that is, if c_{1} ⋯ c_{r} = d_{1} ⋯ d_{s} with c_{i}, d_{j} ∈ B then r = s and c_{i} = d_{i}.

4. I is an ideal with Gröbner basis G.

As in the previous section, given a finitely presented right R/I-module M with presentation f_{1} : F_{1} → F_{0}, we form the ring S̄ = ( \begin{matrix}K & M \\ 0 & R/I \end{matrix} ). Viewing S̄ as a quotient of

S = ( \begin{matrix}K & F_{0} \\ 0 & R \end{matrix} )

by I^{∗} , we find a Gröbner basis G^{∗} of I^{∗} with respect to >^{∗}. Recall that

G^{∗} = \{( \begin{matrix}0 & 0 \\ 0 & g \end{matrix} ) | g ∈ G\} ∪ \{( \begin{matrix}0 & h_{i}^{∗} \\ 0 & 0 \end{matrix} )\}_{i∈I} where G is a Gröbner basis for I

with respect to > and h_{i}^{∗} are of the form ∑_{i=1} e_{i}^{∗}c_{i} with c_{i} ∈ Span(NonTip(I)). We assume each ∑_{i=1}^{n} e_{i}^{∗}c_{i} and each g ∈ G are are uniform elements of R. Furthermore, assume F_{0} has basis e_{1}, …, e_{n}

Note that if h_{i}^{∗} = ∑_{j} e_{j}^{∗}c_{i,j}, we define F′_{1} to be the free R/I-module with basis {d′_{i} | i ∈ I}. Define

f′_{1} : F′_{1} → F_{0}

by f′_{1}(d′_{i}) = ∑_{j} e_{j}c_{i,j}. We see that f′_{1} : F′_{1} → F_{0} is also a free presentation of M.

Let f′_{1} be represented by the matrix (a_{i,j}) as in the last section. We also let f_{0} : F_{0} → M be the canonical surjection. Note that the modules ( 0 R/I ) and ( K M ) are projective S̄-modules. This follows from ( 0 R/I ) ≃

( \begin{matrix}0 & 0 \\ 0 & 1 \end{matrix} ) S̄ and ( K M ) ≃ ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) S̄.

Let U be the right S̄-module (K 0) (with the action of S̄ given by right matrix multiplication). We have a projective presentation of U given as follows.

( 0 F_{0} ) \underrightarrow{( 0 f_{0} )} ( K M ) → U → 0.

Note that the image of ( 0 f_{0} ) is ( 0 M ). We may continue the resolution using f′_{1} as follows:

(∗∗) ( 0 F′_{1} ) \underrightarrow{( 0 f′_{1} )} ( 0 F_{0} ) \underrightarrow{( 0 f_{0} )} ( K M ) → U → 0.

We show how to algorithmically find F_{2}, a free R/I-module and a map f_{2} : F_{2} → F′_{1} so that

F_{2} →^{f_{2}} F′_{1} →^{f′_{1}} F_{0} →^{f_{0}} M → 0

is an exact sequence. Once this is done, we can continue the projective resolution by replacing F′_{1} →^{f′_{1}} F_{0} with F_{2} →^{f_{2}} F′_{1} and repeat the construction. This will be done by continuing the sequence (**) over S̄ and finding the next map in the resolution

( 0 F_{2} ) \underrightarrow{( 0 f_{2} )} ( 0 F′_{1} ) .

For this we first describe F_{2}. Let O be the set of all overlap relation of form o(α, β, p^{∗}, q^{∗}) where α is of the form ( \begin{matrix}0 & h_{i}^{∗} \\ 0 & 0 \end{matrix} ) and β is of the form ( \begin{matrix}0 & 0 \\ 0 & g \end{matrix} ).

Let o(α, β, p^{∗}, q^{∗}) be an overlap relation in O. Let α = ( \begin{matrix}0 & h \\ 0 & 0 \end{matrix} ) and

β = ( \begin{matrix}0 & 0 \\ 0 & g \end{matrix} ). It follows that from the structure of B^{∗} that p = ( \begin{matrix}0 & p \\ 0 & 0 \end{matrix} ) for

some p ∈ B and that q^{∗} = ( \begin{matrix}0 & 0 \\ 0 & q \end{matrix} ) for some q ∈ B. Furthermore, we have

o(α, β, p^{∗}, q^{∗}) = (1/Tip(α))α · q^{∗} − (1/Tip(β))p^{∗}β =

( \begin{matrix}0 & (1/Tip(h))hq − (1/Tip(g))pg \\ 0 & 0 \end{matrix} ) .

Since G^{∗} is a Gröbner basis, the remainder of o(α, β, p^{∗}, q^{∗}) by division by G^{∗} is 0. Hence

\begin{matrix}o(α, β, p^{∗}, q^{∗}) = \\ ∑_{i} ∑_{j} ( \begin{matrix}0 & h_{i} \\ 0 & 0 \end{matrix} ) ( \begin{matrix}0 & 0 \\ 0 & q_{i,j} \end{matrix} ) + ∑_{g∈G} ∑_{j} ( \begin{matrix}0 & u_{i,j} \\ 0 & 0 \end{matrix} ) ( \begin{matrix}0 & 0 \\ 0 & g \end{matrix} ) ( \begin{matrix}0 & 0 \\ 0 & v_{i,j} \end{matrix} ) \end{matrix}

where q_{i,j}, u_{i,j}, v_{i,j} ∈ B.

We can now describe F_{2} and f_{2} : F_{2} → F′_{1}. F_{2} is the free R/I-module with basis ê_{i}, where i is indexed by the overlap set O. To describe f_{2} : F_{2} → F′_{1} we need only define f_{2}(ê_{i}) for i ∈ O. If i = o(α, β, p^{∗}, q^{∗}), then, keeping the notation of the previous paragraph,

f_{2}(ê_{i}) = ∑_{j∈I} d′_{j}c_{i,j}.

The above description of the construction of projective resolutions is a variation on the results found in [17] which use results from [5]. The proof of the next result can be obtained by vary the proof found in [17] of Theorem 4.1 to our setup.

Theorem 4.1 Keeping the above notations,

F_{2} →^{f_{2}} F′_{1} →^{f′_{1}} F_{0} →^{f_{1}} M → 0

is an exact sequence.

4.3 Finite Dimensional Algebras and Modules

In this section, we show how to find projective presentations from “standard” representations of modules and vice versa. R will denote a finitely generated K-algebra with multiplicative basis B, and generators b_{1}, …, b_{n} and admissible order >. Let I be an ideal such that R/I is finite dimensional. Let M be a finite dimensional right R/I-module. As usual, we identify R/I with Span(NonTip(I)) and let Span(NonTip(I)) = \overline{B}. Without loss of generality, we may assume that the generators b_{1}, …, b_{n} of B are in \overline{B}. (If some b_{i} ∉ \overline{B} then b_{i} acts as 0 on M and the following can be modified accordingly.)

Let {m_{j}}_{j∈J} be a K-basis for M. Well-order the m_{j}’s arbitrarily. Let D = |J |. Viewing M as a D-dimensional vector space, each generator b can be represented by a D × D-matrix (c_{i,j}^{b}) with entries in K, where

m_{i} · b = ∑_{j=1}^{D} m_{j}c_{i,j}^{b}.

The n D × D matrices (c_{i,j}^{b_{l}}), l = 1, …, n might be called the “standard” way of representing M.

First we show how to obtain the (c_{i,j}^{b_{l}}) from an R/I-free presentation of M, f_{1} : F_{1} → F_{0}. Suppose F_{0} has R/I-basis {e_{1}, …, e_{r}} and F_{1} has R/I-basis {d_{1}, …, d_{s}}. Then, viewing f_{1} as a K-linear map M is the cokernel of f_{1}. Note that the K-bases of F_{0} and F_{1} are just \{e_{i}b | 1 ≤ i ≤ r and b ∈ \overline{B}\} and \{d_{i}b | 1 ≤ i ≤ s and b ∈ \overline{B}\} respectively. Hence knowledge of f_{1} as an R/Ihomomorphism easily yields viewing f_{1} as a K-linear map. Furthermore, for each generator b_{l} we have a commutative diagram:

\begin{matrix}F_{1} & →^{f_{1}} & F_{0} \\ ↓b_{l} & & ↓b_{l} \\ F_{1} & →^{f_{1}} & F_{0} \end{matrix}

where the vertical morphisms are right multiplication by b_{l}. It follows that we get a map g_{b_{l}} : M → M representing multiplication by b_{l}. g_{b_{l}} yeilds the matrix (c_{i,j}^{b_{l}}).

To go the other way, assume that we have a K-basis {m_{j}}_{j∈J} of M and the D × D K-matrices (c_{i,j}^{b_{l}}) representing multiplication by the n generators b_{l}, 1 ≤ l ≤ n. We show how to construct an R/I-projective presentation f_{1} : F_{1} → F_{0} of M. First let F_{0} be the free R/I-module with basis {e_{j} | j ∈ J } and F_{1} be the free R/I-module with basis \{d_{x,j} | x ∈ \overline{B}, j ∈ J \}. Define f_{0} : F_{0} → M by f_{0}(e_{j}) = m_{j}. Next, define f_{1} : F_{1} → F_{0} as follows. Given j ∈ J and x ∈ X, since x is a product of b_{l}’s, using the matrices (c_{u,v}^{b_{l}}), we may calculate m_{j} · x = ∑_{i∈J} m_{i}α_{i,j}^{x} where α_{i,j}^{x} ∈ K. We now define f_{1}(d_{x,j}) = e_{j}x − ∑_{i∈J} e_{i}α_{i,j}^{x}.

Proposition 4.2 Keeping the notations above,

F_{0} ⟶^{f_{1}} F_{1} ⟶^{f_{0}} M → 0

is exact.

Proof. We have seen that f_{0}(F_{0}) = M. Hence the sequence is exact at M. It is immediate that f_{0}f_{1}(d_{x,j}) = 0 for each x ∈ \overline{B} and j ∈ J. Thus Im(f_{1}) ⊂ Ker(f_{0}). It remains to show that Ker(f_{0}) ⊂ Im(f_{1}).

Consider {z = ∑_{j∈J} e_{j}w_{j} ∈ Ker(f_{0}) | z ∉ Im(f_{1}). We wish to show this set is empty. Let z = ∑_{j∈J} e_{j}w_{j} be in this set. Suppose w_{j} = ∑_{x∈\overline{B}} β_{j,x}x. Consider z′ = z + f_{1}(∑_{j,x} d_{j,x}β_{j,x}). Since z ∉ Im(f_{1}), z′ ∉ Im(f_{1}). But, from the definition of f_{1}, we see f_{1}(∑_{j,x} d_{j,x}β_{j,x}) = ∑_{j∈J} e_{j}γ_{j} − z for some γ_{j} ∈ K. Thus z′ = ∑_{j∈J} e_{j}γ_{j}. But f(z′) = 0 and hence ∑_{j∈J} m_{j}γ_{j} = 0. It follows that γ_{j} = 0 for all j ∈ J. This is a contradiction and we have shown no such z can exist.

Exercises 4.1 Prove that the order <^{∗} on B^{∗} is an admissible order.

4.2 Show that the set (*) is a generating set for I^{∗} in S.

4.3 Refine the construction of F_{1} to be the free R/I-module with basis d_{b_{l},j} where j ∈ J and b_{l} varies the generators of B.

5 Applications of Gröbner Bases

Throughout this section, we will tacitly assume that R = KΓ, B is the set of paths, and > is an admissible order. Hence Gröbner bases exist for ideals in R.

5.1 Topics not covered

1. Computation of Hom_{R/I}(M, N) for two right R/I-modules can easily be performed. More precisely, Gröbner bases yield K-bases of right modules which behave “nicely” with respect to the ring structure of R/I. That is, viewing R/I as Span(NonTip(I)) with “rewrite formulas” given by the Gröbner basis, the module bases constructed in the last lecture come with how the basis of R/I acts on basis elements of the module because that is precisely the information contained in the Gröbner basis of I^{∗} in ( \begin{matrix}K & G_{0} \\ 0 & R \end{matrix} ) of the last lecture. Using these bases, the computation of Hom_{R/I}(M, N) as a vector space is straightforward.

2. The study of submodules and quotient modules can be easily handled using the bases of last lecture.

3. Computation of M ⊗_{R/I} N for a left R/I-module M and a right R/Imodule N can be performed. For this one must be able to find bases of both left and right modules (which Gröbner bases can do). One method of attacking the computation M ⊗_{R/I} N is to find M ⊗_{K} N using the K-bases provided by the Gröbner bases of the last lecture and then put in the relations over R/I and find quotient.

4. Using the above two parts, it should be apparent that one can computationally study module theory of noncommutative rings that are quotients of rings that have a theory of Gröbner bases. This class includes algebras that are quotients of path algebras and therefore includes quotients of free algebras.

5. One can study the growth of algebras. By Theorem 1.2, R/I can be identified with Span(NonTip(I)) and NonTip(I) is a K-basis of R/I. If R is the free algebra and B is the set of monomials or if R is a path algebra and B is the set of paths then the growth of the number of nontips of a given degree or length measures the growth of the algebra. More precisely, if H_{n} = dim_{K}(Span({x ∈ NonTip(I) | length(x) = n}), then the Hilbert series of R/I is

H(R/I) = ∑_{n=o}^{∞} H_{n}z^{n}.

Here z is a variable. Questions like the rationality of H(R/I) are being studied [2, 3, 4, 31]. One of the important tools to study H(R/I) and the numbers H_{n} is the Ufnarovski graph. Time doesn’t permit me to say much about it, but it is a powerful tool to study the nontips of I. We refer to [33] and recent work of Z. Kramer [25].

6. Noncommutative Gröbner bases in free algebras have been applied to study H^{∞} control problems in the work of Helton, Stankus and Varvik.

7. As described in the last lecture, Gröbner bases allows the construction of projective resolutions of a right module M. Then, applying Hom_{R/I}(−, N) to the resolution and taking cohomology of the resulting complex, one can obtain the ext-groups Ext_{R/I}^{n}(M, N). For a left R/I-module N, applying − ⊗_{R/I} N to the resolution and taking cohomology of the resulting complex, one can obtain the tor-groups Tor_{n}^{R/I}(M, N). Hence, one can study homological questions computationally. One important invariant of an algebra is the Poincaré series of a module. If M is a right R/I-module and S is a simple right R/I-module (usually K), let P_{n} = dim_{K}Ext_{R/I}^{n}(M, S). The Poincaré series is

P_{S}(M) = ∑_{n=0}^{∞} P_{n}z^{n}.

Again, questions like rationality and connections with the Hilbert series are of interest. [4, 31]

8. Michael Bardzell [8] has used the theory of Gröbner basis to study the Hochschild cohomology of a monomial K-algebra.

5.2 Algebras and Their Associated Monomial Algebras

One of the interesting connections one obtains from the theory of Gröbner bases is the associated monomial algebra to an algebra. As we have done, let I_{MON} = Span(NonTip(I)). Then I_{MON} is a monomial ideal. We say R/I_{MON} is the associated monomial algebra to R/I. Note that R/I_{MON} is dependent on the choice of basis B of R and on the choice of admissible order >.

If R/I is a finite dimensional K-algebra, there is an important invariant of R/I called the Cartan matrix. Let S_{1}, …, S_{n} be a full set of nonisomorphic simple R/I-modules and let P_{1}, …, P_{n} be indecomposable projective R/I-modules such that there are surjections P_{i} → S_{i}. Then we define the Cartan matrix of R/I to be the n × n matrix (C_{i,j}) where C_{i,j} is the number of times S_{i} occurs as a composition factor of P_{j}.

Since R is a path algebra, it is sometimes natural to assume the I is contained in the ideal < Γ_{1} >^{2} where Γ_{1} is the set of arrows in Γ. In this case there are certain simple modules of R/I we distinguish, called the vertex simple modules. A vertex simple module is a module of the form S_{i} = v_{i}R/ < Γ_{1} > where v_{i} is a vertex. It is easy to see that if there are n vertices in Γ, S_{1}, …, S_{n} are right simple R/I-modules which are 1-dimensional over K.

If M is a right R-module and

⋯ P_{n} →^{f_{n}} P_{n−1} → ⋯ → P_{1} →^{f_{1}} P_{0} →^{f_{0}} M → 0

is a projective resolution of M, then the projective dimension of M, pd_{R/I}(M), is the smallest n such that Im(f_{0}) is a projective module. If no such n exists, we say that M has infinite projective dimension and write pd_{R/I}(M) = ∞. The global dimension of R/I, gl.dim(M), is N if

N = Sup{pd_{R/I}(M) | M is an R/I-module}

if such an N exists. Otherwise, gl.dim(M) = ∞.

We can state a result relating R/I and R/I_{MON}.

Theorem 5.1 [23] Let R = KΓ be a path algebra with K-basis B the finite directed path in Γ and with admissible order >. Let I be an ideal in R and I_{MON} be the associated monomial ideal. Then

1. H(R/I) = H(R/I_{MON}).

2. If R/I is finite dimensional, then

dim_{K}(R/I) = dim_{K}(R/I_{MON}) = |NonTip(I)|.

3. Assume that I ⊂<Γ_{1} >^{2}.

(a) The construction of a projective resolution given in [17] for each vertex simple module S_{i} is minimal for R/I_{MON}.

(b) For each i = 1, …, n, pd_{R/I}(S_{i}) ≤ pd_{R/I_{MON}} (S_{i}).

(c) If R/I is finite dimensional, then gl.dim(R/I) ≤ gl.dim(R/I_{MON}).

(d) If R/I is finite dimensional, then the Cartan matrices of R/I and R/I_{MON} are equal.

(e) If S is a vertex simple module viewed as a module over both R/I and R/I_{MON}, and if → P_{1} → P_{0} → S → 0 and → P′_{1} → P′_{0} → S → 0 are minimal projective resolutions over R/I and R/I_{MON} respectively, then dim_{K}(P_{n}) ≤ dim_{K}(P′_{n}) for all n ≥ 0.

5.3 Koszul Algebras

Let R = KΓ and I be an ideal in R. We say that I is a quadratic ideal if there is a set of generators {f_{1}, …, f_{n}} of I such that each f_{1} is a K-linear combination of paths in Γ of exactly length 2. In this case, we say that {f_{1}, …, f_{n}} is a set of quadratic generators and that R/I is a quadratic algebra.

The path algebra R has a natural positive Z-grading given by letting vertices be homogeneous of degree 0, and paths be homogeneous of degree equal to the length. We will view R as a graded ring in this way. Note that an element x = ∑_{i=1}^{m} α_{i}p_{i} with α_{i} ∈ K and p_{i} ∈ B is homogeneous if each p_{i} occurring in x has the same length. We call this the length grading of R. Let I be a graded ideal in R; that is, an ideal generated by homogeneous elements. Then R/I is a Z-graded algebra by the induced grading.

For the remainder of this section, we assume that I is graded ideal in R and let R/I = S_{0} ⊕ S_{1} ⊕ S_{2} ⊕ ⋯ as a graded ring. We let Gr(S) denote the category of Z-graded S-modules and degree 0 S-module maps. That is, the objects of Gr(S) are

M = ⋯ ⊕ M_{−2} ⊕ M_{−1} ⊕ M_{0} ⊕ M_{1} ⊕ M_{2} ⊕ ⋯

where each i, j, M_{i} is a right S_{0}-module and if s_{j} ∈ S_{j} and m_{i} ∈ M_{i} then m_{i}s_{j} ∈ M_{i+j} such that, forgetting the graded structure, M is a right S-module. A degree 0 map f : M → N between graded S-modules is an S-module map such that if m_{i} ∈ M_{i} then f(m_{i}) ∈ N_{i}.

We say a graded S-module is generated in degree n if M_{j} = 0 for j < n and for all i ≥ 0, the multiplication maps M_{n} ⊗_{S_{0}} S_{i} → M_{n_{i}} are surjective. We say that an S-module X is gradeable if there is a graded S-module M, such that X is isomorphic to M when one forgets the grading on M and views M as an S-module. We have the following result whose proof is standard.

Proposition 5.2 Let I be a graded ideal in a path algebra KΓ where KΓ has the length grading. Assume that I ⊂< Γ_{1} >. Let KΓ/I = S_{0} ⊕ S_{1} ⊕ S_{1} ⊕ ⋯ be the graded quotient ring. Then

1. S_{0} is isomorphic to KΓ/<Γ_{1} > and hence is semisimple.

2. Each S_{i} is finite dimensional over K.

3. The vertex simple modules are gradeable modules.

4. S_{1} ⊕ S_{2} ⊕ ⋯ is the graded Jacobson radical of S.

5. The category of finitely generated graded S-modules has projective covers.

6. Graded S-modules have graded projective resolutions.

7. A graded S-projective resolution of a graded S-module M forgets to a Sprojective resolution of X where X is the X S-module M when we forget the graded structure.

We say R/I is Koszul algebra if S_{0}, viewed as a graded S-module generated in degree 0 has a graded projective resolution

⋯ P_{n} → P_{n−1} → ⋯ → P_{1} → P_{0} → M → 0

such that for each n, P_{n} is generated in degree n. See Appendix C for a brief survey of some of the basic results about Koszul algebras. They are an important class of algebras that naturally occur in algebraic geometry, topology, and the theory of quantum groups [10, 12, 14, 30, 32, 34]. Proofs of many of the basic results about Koszul algebras can be found in [21, 22, 10]. My goal here is to demonstrate that Gröbner bases can be used in studying such a class of Koszul algebras.

It is well-known that if R/I is a Koszul algebra then I must be a quadratic ideal [21, 10]. At this time, there is no classification known of which quadratic ideals I have the property that KΓ/I is a Koszul algebra at this time, in terms of the generators of the quadratic ideals. We do have the following result though.

Theorem 5.3 [20] Let I be a quadratic ideal in a path algebra KΓ. Let > be an admissible order on the paths such that I has a quadratic Gröbner basis. Then KΓ/I is a Koszul algebra.

The proof of the result, although too technical for these lectures, involves an investigation of the projective resolution of the vertex simple modules given by the construction discussed in the last lecture. Analysis of the construction shows that if the algebra is graded and the module is graded, then the constructed resolution is, in fact, a graded resolution of the module. It is also shown that if the generators of I are quadratic, then the construction of a graded projective resolution of a vertex simple module has the desired degree properties.

The next result follows from the above theorem and also from [23].

Corollary 5.4 Let I be a monomial ideal generated by some paths of length 2. Then KΓ/I is a Koszul algebra.

Proof. If J is a monomial ideal in a path algebra, since overlap relations are in fact 0, we see by the Termination Theorem that any generating set of monomials for J is a Gröbner basis under any admissible order. Since I can be generated by paths of length 2, it follows that I has a quadratic Gröbner basis.

We end with another application which is more fully described in [19]. Let R = K< x_{1}, …, x_{n} > be the free associative algebra in n noncommuting variables. Let > be the degree-lexicographic order with x_{1} < x_{2} < … < x_{n}. For 1 ≤ i < j ≤ n, let

q_{i,j} = x_{j}x_{i} − c_{i,j}x_{i}x_{j} + r_{i,j}

where r_{i,j} is a quadratic polynomial, each of whose terms is less than x_{i}x_{j}. Thus Tip(q_{i,j}) = x_{j}x_{i} and Tip(q_{i,j} − Tip(q_{i,j}) = x_{i}x_{i}. Let I be the ideal generated by {q_{i,j}}.

Note that I is a quadratic ideal. Consider R/I. We denote the image of x_{i} in R/I by x̄_{i}. We say R/I has a Poincaré-Birkhoff-Witt basis or PBW basis if {x̄_{1}^{a_{1}}x̄_{2}^{a_{2}} … x̄_{n}^{a_{n}}} where a_{i} are nonnegative integers, is a K-basis of R/I.

The set {q_{i,j}}_{1≤i,j≤n} can be viewed as rewriting rules in the sense that if a monomial m̄ = x̄_{i_{1}} x̄_{i_{2}} … x̄_{i_{s}} has the property that for some j, i_{j} > i_{j+1} then in R/I, x̄_{j}x̄_{i} = c_{i,j}x̄_{i}x̄_{j} − r̄_{i,j},

m̄ = x̄_{i_{1}} x̄_{i_{2}} … x̄_{j−1}x̄_{j+1}x̄_{j}x̄_{j+2} … x̄_{i_{s}} − x̄_{i_{1}} x̄_{i_{2}} … x̄_{j−1}r̄_{i,j}x̄_{j+2} … x̄_{i_{s}}.

Thus, by replacing x̄_{j}x̄_{i} as above if j > i and by the fact that > is a wellorder, we see that {x̄_{1}^{a_{1}}x̄_{2}^{a_{2}} … x̄_{n}^{a_{n}}} generate R/I as a K vector space. It is natural to ask if R/I has a PBW basis. The next result answers the question.

Proposition 5.5 Keeping the above notations, R/I has a PBW basis if and only if {q_{i,j}} is a Gröbner basis of I. Thus, if R/I has a PBW basis, R/I is a Koszul algebra. I.

Proof. Suppose that R/I has a PBW basis. Then {x̄_{1}^{a_{1}}x̄_{2}^{a_{2}} … x̄_{n}^{a_{n}}} is a Kbasis for R/I. To show that {q_{i,j}} is a Gröbner basis for I it suffices to show that overlap relations have remainder 0 when divided by {q_{i,j}}.

Consider division by {q_{i,j}}. Any monomial m occuring in a remainder cannot have x_{j}x_{i} with j > i in it since if so, Tip(q_{i,j}) would divide m. Thus, the remainder of division by {q_{i,j}} of any overlap relation is in the span of {x_{1}^{a_{1}} … x_{n}^{a_{n}}}. By the PBW basis assumption, no element of this span is in I other than 0.

If {q_{i,j}} is a Gröbner basis for I, then

NonTip({q_{i,j}}) = {m ∈ B | Tip(q_{i,j}) does not divide m}.

But it immediate that NonTip({q_{i,j}) is {x_{1}^{a_{1}} … x_{n}^{a_{n}} | a_{i} ≥ 0}. But NonTip(I) is a K-basis of R/I under the usual identification. Thus, R/I has a PBW basis.

The last result of the proposition is a consequence of Theorem 5.3

6 Appendix 1: Why path algebras?

Why develop a theory of Gröbner bases for path algebras and not just free associative algebras? Path algebras are quotients of free algebras and therefore it becomes questionable why we should look at the seemly more complicated situation.

First let’s prove the assertion about path algebras.

Proposition 6.1 Every path algebra is a quotient of a free associative algebra.

Proof. Let Γ be given with n vertices and m arrows. Then KΓ is a quotient of the free algebra K < X_{1}, …, X_{n+m} > by sending X_{1}, …, X_{n} to the vertices and X_{n+1}, …, X_{n+m} to the arrows. This makes KΓ a homomorphic image of the free algebra.

So why not just consider free algebras and avoid the notational (and theoretical) inconvenenience of general path algebras? One unsatisfactory answer might be: Well,... free algebras are special cases of path algebras. But this is not very convincing!

This appendix is devoted to answering this question. I will state some results without proof and assume a certain level of knowledge of algebra that is not necessary of the lecture notes. I begin by giving some indication of where path algebras naturally arise in algebra. Once this is done, I remark on the computational reasons not to view path algebras as quotients of free algebras.

Let Λ be a finite dimensional K-algebra. There is a two-sided ideal in Λ called the Jacobson radical of Λ which I will denote by r. The ideal r is defined to be the intersection of all maximal left ideals in Λ. It can be shown that r is also the intersection of all maximal right ideals in Λ. One of the fundamental results in studying finite dimensional algebras is a version of the Artin-Wedderburn Theorem.

Theorem 6.2 Let Λ be a finite dimensional K-algebra where K is a field. Let r denote the Jacobson radical of Λ. Then Λ/r is isomorphic to

∏_{i=1}^{n} M_{t_{i}}(D_{i})

where each D_{i} is a finite dimensional K-division ring and M_{t_{i}}(D_{i}) denotes the t_{i} × t_{i}-matrix ring over D_{i}.

The next result I want to mention is another classic result.

Theorem 6.3 If K is an algebraically closed field and D is a finite K-dimensional division ring in which K is contained in the center of D then D = K. That is, K is the only finite dimensional division ring when K is algebraically closed.

Proof. Let x ∈ D. Consider the subring of D generated by x; that is, K[x]. Since D is finite dimensional over K, {x, x^{2}, x^{3}, …} contains a linear dependency. Thus there is a linear combination, ∑_{i=1}^{m} k_{i}x^{i} which is 0. Solving for the smallest x^{i} occuring and then dividing by k_{i}x^{i} (remembering that we are in a division ring) we get 1 = xy for some y ∈ K[x]. We see that x is a unit in K[x]. It follows that K[x] is a field, finite dimensional over K. Thus K[x] = K.

So, putting the two previous theorems together we get the next result.

Corollary 6.4 If K is an algebraically closed field and Λ a finite dimensional K-algebra with Jacobson radical r then

Λ/r ≃ ∐_{i=1}^{n} M_{n_{i}}(K).

Our next goal is to “remove” the matrix rings in the above formula. For this, we will need the concept of Morita equivalence. I will not go into details, but if one studies the “category” of modules over a ring, one is led to the concept of Morita equivalence. A bit more precisely, a category consists of objects and morphisms, so the category of modules over a ring has as its objects the modules and as its morphisms the module homomorphisms between modules. As in any mathematical theory we need the concept of equality – when two things we are studying should be considered the same. For two categories, we say they are “equivalent” when they are the same. Morita studied equivalent module categories and described what these equivalences must look like; thus, we use the phrase “Morita equivalence” for an equivalence of two module categories. There are many properties of modules one studies that are preserved under Morita equivalence. That is, if R and S are Morita equivalent rings (i.e., the category of R-modules is equivalent to the category of S-modules), then, for many properties of modules, it doesn’t make a difference if we study S-modules or R-modules.

Returning to our interest in this section, finite dimensional algebras, we have a particularly nice situation.

Theorem 6.5 Let Λ be a finite dimensional K-algebra with Jacobson radical r such that Λ/r ≃ ∐_{i=1}^{n} M_{n_{i}}(K). Then Λ is Morita equivalent to a finite dimensional K-algebra Λ^{∗} with Jacobson radical r^{∗} such that

Λ^{∗}/r^{∗} ≃ ∐_{i=1}^{n} K.

Corollary 6.6 If Λ is a finite dimensional algebra over an algebraically closed field K then Λ is Morita equivalent to a finite dimensional K-algebra Λ^{∗} with Jacobson radical r^{∗} such that

Λ^{∗}/r^{∗} ≃ ∐_{i=1}^{n} K.

Before proceeding we need a result about the relationship of the idempotents of Λ/r and the idempotents of Λ. Let π : Λ → Λ/r be the canonical surjection.

Proposition 6.7 Let Λ be a finite dimensional K- algebra. If ē ∈ Λ/r is an idempotent then there is an idempotent e ∈ Λ such that π(e) = ē.

Proof. Let x ∈ Λ be such that π(x) = ē. Then there is a linear dependence of the powers of x as in an ealier result. Solving now for the smallest power of x occuring and dividing by a constant we get an equation of the form:

x^{n} = x^{n+1}y.

Here, y is a K-linear combination of x^{i}’s so y commutes with x. Thus, x^{n} = x^{n+2}y^{2} = ⋯ = x^{2n}y^{n}. Consider z = x^{n}y^{n}. First note that z^{2} = x^{2n}y^{2n} = x^{n}y^{n} = z. Thus z is an idempotent. Finally we claim that π(z) = ē. Let d̄ = π(z). Then d̄ is an idempotent. Furthermore, since x^{n}z = x^{n} we see ēd̄ = ē. But d̄ − ē = π(x^{n})π(y^{n} − 1) = ēū where ū = π(y^{n} − 1). Thus ē(d̄− ē) = ēēū = ēū = d̄− ē. On the other hand, ē(d̄− ē) = 0. Thus d̄= ē.

Next we extend this result to orthogonal idempotents.

Proposition 6.8 Let Λ be a finite dimensional K- algebra. If ē and d̄ are orthogonal idempotents in Λ/r then there exist orthogonal idempotents e, d ∈ Λ such that π(e) = ē and π(d) = d̄.

Proof. Let x, y ∈ Λ be idempotents such that π(x) = ē and π(y) = d̄. Then π(xy) = 0. Hence x−xy maps to ē. Note that (x−xy)y = 0. Thus, x−xy maps to ē and is a left zero divisor of y. By the construction in the above proposition, we may construct an idempotent z ∈ Λ mapping to ē and such that zy = 0. To see this, note that the idempotent constructed from the element x−xy mapping onto ē is a linear combination of powers of x − xy. Next consider z − yz. Then z − yz maps to ē and is orthogonal to y. Again the construction of the previous proposition preserves the orthogonality to y and we are done.

Our next result is a blend of Nakayama’s lemma and finite dimensional algebras.

Proposition 6.9 If Λ is a finite dimensional algebra then a). every element of r is nilpotent b). every element of the form 1 − x with x ∈ r is a unit. c). r is nilpotent.

Proof. Let x ∈ r. Consider the set of powers of x. This set must contain a linear dependency. If x^{n} ≠ 0 for all n, by applying the arguments of an earlier proposition, we get an idempotent z in r. If 1 − z is not a unit, it is in some maximal left ideal. but z is in every maximal ideal. Thus 1 is in m a contradiction. But z(1 − z) = 0. Thus z = 0. But x^{n}z = x^{n} ≠ 0 (from the proof that z is an idempotent). Contradiction. Hence a) follows.

Now consider x ∈ r. Note that x is nilpotent. Then (1 − x)(1 + x) = 1 − x^{2}. (1 − x^{2})(1 + x^{2}) = 1 − x^{4} Eventually, we get (1 − x)z = 1 for some z and hence b) follows.

Consider ⋯ ⊂ r^{n} ⊂ r^{n−1} ⊂ ⋯ ⊂ r. By finite dimensionality, we get r^{n} = r^{n+1}. Choose a generting set of r^{n}, g_{1}, …, g_{m} where m is minimal (possible since Λ is finite dimensional). Then g_{1} = x_{1}g_{1} + ⋯ + x_{m}g_{m} where x_{i} ∈ r.

Then (1 − x_{1})g_{1} = x_{2}g_{2} + … + x_{m}g_{m}. But 1 − x_{1} is a unit and hence we can remove g_{1} from the generating set. This proves c) and we are done.

FOR THE REMAINDER OF THIS SECTION, WE ASSUME THAT Λ IS A FINITE DIMENSIONAL K-ALGEBRA WITH JACOBSON RADICAL r SUCH THAT

Λ/r ≃ ∐_{i=1}^{n} K.

A finite dimensional algebra that satisfies this condition is called a basic algebra. (More generally, a finite dimensional algebra is basic if the algebra modulo its Jacobson radical is a product of division rings.)

Under this assumption, we will now prove that Λ is isomorphic to the quotient of a path algebra. We will see that the quiver of Λ is defined in a canonical way and it turns out it is a categorical invariant of the Morita class of Λ. The Morita class of a ring Λ is the class of all algebras that are Morita equivalent to Λ.

Let π : Λ → Λ/r be the canonical surjection.

Proposition 6.10 Under the above hypothesis, there is a ring homomorphsim τ : Λ/r → Λ such that πτ = 1_{Λ/r}.

Proof. Let \overline{e_{i}} = (0, 0, …, 0, 1, 0, …, 0) ∈ ∏ K where 1 is in the i-th position. The \overline{e_{i}}’s are orthogonal idempotents. Since orthogonal idempotents lift to orthogonal idempotents, let e_{i} ∈ Λ be such that {e_{i}} is a set of orthogonal idempotents and π(e_{i}) = \overline{e_{i}}. Let R be the K subspace of Λ generated by the e_{i}’s. Since the e_{i}’s are a set of orthogonal idempotents, R is a ring with identity ∑_{i} e_{1}. Sending ē_{i} to e_{i} induces the ring homomorphism τ.

Note d = ∑ e_{i} maps to 1 in Λ/r and d is an idempotent. Thus 1−d maps to 0. Hence 1 − d ∈ r. But 1 − d is an idempotent so 1 − d = 0 since r is nilpotent. It follows that ∑_{i} e_{i} = 1 and the above ring homomorphism takes 1 to 1.

Corollary 6.11 If Λ is a finite dimensional K-algebra such that Λ/r ≃ ∏_{i=1}^{n} K then Λ is a split algebra. That is,

Λ ≃ Λ/r ⊕ r.

The multiplicative action in Λ/r ⊕ r is given by identifying Λ/r with its image R via τ of the above proposition.

The last preparatory result we need is an analysis of the Jacobson radical of Λ. We begin with studying the radical modulo the radical squared. Let e_{1} = (0, 0, …, 0, 1, 0, …, 0) with 1 in the ith position in Λ/r = ∏_{i=1}^{n} K.

Proposition 6.12 Assuming Λ = ∏_{i=1}^{n} K then as a Λ/r-bimodule r/r^{2} is isomorphic to

∐_{i,j=1}^{n} e_{i}(r/r^{2})e_{j}.

Proof. This result is easily seen to be true for any Λ/r-bimodule, M, in particular r/r^{2}. As a left Λ/r-module M = ∐_{i=1}^{n} e_{i}M since the e_{i} are CENTRAL orthogonal idempotents in Λ/r. Now each e_{i}M is a right Λ/r-module. Again, since the e_{j} are central orthogonal idempotents, each e_{i}M = ∐_{j=1}^{n} e_{i}Me_{j} and the result follows.

We can now define the quiver of a basic algebra. If Λ/r is a product of n copies of K then the quiver of Λ is the finite directed graph Γ_{Λ} with vertex set {v_{1}, …, v_{n}} and exactly n_{i,j} arrows from v_{i} to v_{j} where

n_{i,j} = dim_{K}(e_{i}r/r^{2}e_{j}).

Theorem 6.13 Let Λ be a basic algebra with Λ/r a product copies of a field K. Then there is a (non-canonical) K-algebra surjection Φ : KΓ_{Λ} → Λ where Γ_{Λ} is the quiver of Λ. Moreover, the kernel of Φ is contained in the ideal generated by paths of length 2.

Proof. Define Φ(v_{i}) = τ(ē_{i}) where τ : ∏_{i=1}^{n} K → Λ is the K-algebra map which splits the canonical surjection π : Λ → Λ/r.

Choosing K-bases {x_{i,j}} of the e_{i}r/r^{2}e_{j} for 1 ≤ i, j ≤ n, we define Φ on the arrow set of Γ_{Λ} in the obvious way (remembering there are dim_{K}(e_{i}r/r^{2}e_{j}) arrows from v_{i} to v_{j}). Note that Φ is dependent on the choice of bases of the e_{i}r/r^{2}e_{j}.

Now extend Φ to paths in the obvious way and extend Φ linearly to KΓ. It remains to show that Φ is a surjective K-algebra homomorphism. I leave it as an exercise that Φ is a ring homomorphism. We must prove that Φ is onto. Let x ∈ Λ. Then there is an integer m such that x ∈ r^{m} − r^{m+1}.

Let π_{m} : r^{m} → r^{m}/r^{m+1} be the canonical surjection. Then π_{m}(x) ≠ 0. Note that the multiplication map:

⊗_{Λ/r}^{m}r/r^{2} → r^{m}/r^{m+1}

is surjective. To see this, note that the multiplication map ⊗_{Λ}^{m}r → r^{m} is surjective and that tensoring with Λ/r yeilds the result. Thus π_{m}(x) is equal to a linear combination of elements of the form:

π_{m}(y_{1}y_{2} … y_{m})

where y_{i} ∈ {x_{u,v}}_{1≤u,v≤n}. But each y_{i} is in the image of Φ. Thus, there is some element z ∈ KΓ_{Λ} such that π_{m}(Φ(z)) = π_{m}x. But then x − Φ(z) ∈ r^{m+1}. Continuing as using the fact that the evenually, r^{t} = 0 we see that Φ is onto.

That the kernel is contained in the ideal generated by paths of length two follows from the constrcution. That is, the vertices go in a one to one correspondence to a full set of primitive orthogonal idempotents in Λ and the arrows go in a one to one correspondence to a minimal generating set of r/r^{2}.

Some concluding remarks are in order. It is a fact that Γ_{Λ} is a Morita invariant of the the Morita class of Λ. Thus, in summary we have shown:

Theorem 6.14 Let K be an algebraically closed field and Λ be a finite dimensional K-algebra. Then there a finite directed graph Γ and an ideal I contained in the ideal generated by paths of length 2 such that Λ is Morita equivalent to KΓ/I.

We end with an example which shows why using the path modulo an ideal is much more computationally accessible that viewing a finite dimensional algebra as a quotient of a free algebra.

Example: Let Γ be quiver

•^{v_{1}}  →^{a_{1}} ; →^{a_{2}}  •^{v_{2}}  →^{a_{3}} ; →^{a_{4}}  •^{v_{3}}  →^{a_{5}} ; →^{a_{6}}  •^{v_{4}}

Since Γ_{0} consists of 4 vertices and Γ_{1} has 6 arrows, to view Γ as a quotient of a free algera we new 10 variables:

x_{1}, …, x_{4}, y_{1}, ..., y_{6}

We send x_{i} to v_{i} and y_{i} to a_{i}. Then we get relations: x_{1}^{2} = x1, x_{2}^{2} = x_{2}, x_{3}^{2} = x_{3}, x_{4}^{2} = x_{4}, x_{1}x_{2} = 0, x_{1}x_{3} = 0, x_{1}x_{4} = 0 x_{2}x_{1} = 0, x_{3}x_{1} = 0, x_{4}x_{1} = 0 x_{2}x_{3} = 0, x_{2}x_{4} = 0, x_{3}x_{2} = 0, x_{4}x_{3} = 0 x_{3}x_{4} = 0, x_{4}x_{3} = 0 x_{1}y_{1} = y_{1}, x_{2}y_{1} = 0, x_{3}y_{1} = 0, x_{4}y_{1} = 0 y_{1}x_{1} = 0, y_{1}x_{2} = y_{2}, y_{1}x_{3} = 0, y_{1}x_{4} = 0 x_{1}y_{2} = y_{2}, x_{2}y_{2} = 0, x_{3}y_{2} = 0, x_{4}y_{2} = 0 y_{2}x_{1} = 0, y_{2}x_{2} = y_{2}, y_{2}x_{3} = 0, y_{2}x_{4} = 0 x_{1}y_{3} = 0, x_{2}y_{3} = y_{3}, x_{3}y_{3} = 0, x_{4}y_{3} = 0 y_{3}x_{1} = 0, y_{3}x_{2} = 0, y_{3}x_{3} = y_{3}, y_{3}x_{4} = 0 x_{1}y_{4} = 0, x_{2}y_{4} = y_{4}, x_{3}y_{4} = 0, x_{4}y_{4} = 0 y_{4}x_{1} = 0, y_{4}x_{2} = 0, y_{4}x_{3} = y_{4}, y_{4}x_{4} = 0 x_{1}y_{5} = 0, x_{2}y_{5} = 0, x_{3}y_{5} = y_{5}, x_{4}y_{5} = 0 y_{5}x_{1} = 0, y_{5}x_{2} = 0, y_{5}x_{3} = 0, y_{5}x_{4} = y_{5} x_{1}y_{6} = 0, x_{2}y_{6} = 0, x_{3}y_{6} = y_{6}, x_{4}y_{6} = 0 y_{6}x_{1} = 0, y_{6}x_{2} = 0, y_{6}x_{3} = 0, y_{6}x_{4} = y_{6} Clearly, for the simple graph Γ the increased computational complexity of

viewing Γ as a quotient of a path algebra (before we even consider relations) justifies the implementation of a Gröbner basis package for path algebras.

7 Appendix 2: Proof of the Termination Theorem

Theorem 7.1 2.6 Let R be a K-algebra with multiplicative basis B and admissible order <. Suppose the G is a set of uniform, tip reduced elements of R. Suppose for every overlap relation

o(g_{1}, g_{2}, p, q) ⇒_{G} 0,

with g_{1}, g_{2} ∈ G. Then G is a Gröbner basis for <G >.

Proof. Assume that G has the property that all overlap relations have remainder 0 under division by G. Let x ∈ I and we assume that tip(x) is not divisible by the tip of any element of G. We show this leads to a contradiction. Without loss of generality, we amy assume that x is uniform. In this way, all multiplications are in effect nonzero. Since we are assuming that G is a generating set, we may write

x = ∑_{i,j} α_{i,j}p_{i,j}g_{i}q_{i,j} (∗)

where g_{i} varies over G and p_{i,j}, q_{i,j} ∈ B. Consider all such ways of writing x. Let p^{∗} be the largest path occuring on the rhs of (*). Since we are assuming that tip(x) is not divisible by the tip of any element of G, by uniformity it follows that p^{∗} is larger than tip(x) in the < order. Thus, the p^{∗}’s terms cancel each other out.

Considering all ways of writing x as in (*), choose one such that p^{∗} is as small as possible and has the fewest occurrences in the rhs of (*).

Since p^{∗} does not occur on the lhs, it must appear in two summand of the rhs. So there exist i, j, i′, j′ so that

p^{∗} = p_{i,j}tip(g_{i})q_{i,j} = p_{i′,j′}tip(g′_{i})q_{i′,j′}.

To simplify notation, write p = p_{i,j}, g = g_{i}, q = q_{i,j}p′ = p_{i′,j′}, g′ = g′_{i} and q′ = q_{i′,j′}. We proceed by a case by case study of the possible scenarios. Case 1: length p < length p′.

In this case either, length q ≥ length q′ or not. Case 1.1: Length q < length q′.

Then tip(g′) contains tip(g) and hence tip(g) divides tip(g′) contradicting the hypothesis. Case 1.2: length q ≥ length q′. We consider two possibilities. Case 1.2.1: length p′ ≥ length ptip(g).

Then there is no overlap of tip(g) and tip(g′) in p^{∗}. By the choice of lengths, it follows that there is a path q′′ such that p^{∗} = ptip(g)q′′g′q′. Now if g = ∑ α_{i}p_{i} + αtip(g), and g′ = ∑ β_{i}p′_{i} + βtip(p′), then

\begin{aligned}pgq & = & pgq′′(1/β)g′q′ − pgq′′(1/β)(g′ − tip(g′))q′ \\ & = & (α/β)ptip(g)q′′g′q′ + ∑(α_{i}/β)pp_{i}q′′g′q′ − ∑(β_{i}/β)pgq′′(p′_{i}). \end{aligned}

Thus, in writing pgq this way, can combine its tip with the tip of p′g′q′ and lower the number of occurrances of p^{∗} which contradicts the minimality assumption.

Case 1.2.2: length p′ < length ptip(g).

Then there is an overlap of tip(g) and tip(g′) is p^{∗}. Say tip(g)r = s · tip(g′). Thus p^{∗} = ptip(g)rq′ = pstip(g′)q′. Then

pgq = c_{g}(tip(g))po(g, g′, r, s)q + (c_{g}(tip(g))/c′_{g}(tip(g′)))p′g′q′.

By assumption o(g, g′, r, s) totally reduces over G so is a K-linear combination of terms of the form p̂ĝq̂ for paths p̂, q̂ ∈ B and ĝ ∈ G, all of whose tips are smaller that tip(g)r = s·tip(g′). So we may combine the occurrance of p^{∗} in pgq with its occurrance in p′gq′. This again contradicts the minimality assumption. Case 2: length p = length p′.

Then tip(g) divides tip(g′) or vice versa - which contradicts the assumption on G. Case 3: length p > length p′.

Same as Case 1.

8 Appendix 3: Fundamental Theorems on Koszul Algebras

Throughout this section, we assume that Λ = KΓ/I is a graded K-algebra with the length grading and that I is contained in J^{2} where J is the ideal in KΓ generated by the arrows. We say a graded Λ-module M is generated in degree i if M_{n} = Λ_{n−i}M_{i} for all n ∈ Z. We say a graded module M has a linear resolution if M is generated in degree 0 and if there is a graded projective Λ-resolution of M

⋯ → P_{n} →^{f_{n}} P_{n−1} → ⋯ → P_{1} →^{f_{1}} P_{0} →^{f_{0}} M → 0

such that for n ≥ 0, P_{n} is generated in degree n. We get the first main result which provides an equivalent description of a Koszul algebra.

Theorem 8.1 [21, Cor 3.4] [30, 10] Let Λ = KΓ/I be as above. Then the following statements are equivalent:

1. Λ is a Koszul algebra.

2. As a graded Λ-module generated in degree 0, Λ/r has a linear resolution.

Let E(Λ) = ∐_{n≥0} Ext_{Λ}^{n}(Λ/r, Λ/r) = Ext_{Λ}^{∗}(Λ/r, Λ/r) be the Yoneda algebra of Λ. That is, E(Λ) is given a multiplicative structure using the Yoneda product (see [28]). E(Λ) has also been called the Ext-algebra of Λ and also the cohomology ring of Λ. We view E(Λ) as a graded K-algebra via E(Λ)_{n} = Ext_{Λ}^{n}(Λ/r, Λ/r). We say that Λ is a quasi-Koszul algebra if E(Λ) is generated in degrees 0 and 1; that is, if Ext_{Λ}^{1}(Λ/r, Λ/r)·Ext_{Λ}^{n}(Λ/r, Λ/r) = Ext_{Λ}^{n+1}(Λ/r, Λ/r) for all n ≥ 0. In the graded case, if E(Λ) is generated in degrees 0 and 1 we say that E(Λ) is a Koszul algebra.

The next result is also fundamental.

Theorem 8.2 [21, Thm 6.1] [30, 10] If Λ = KΓ/I is a Koszul algebra then the Yoneda algebra E(Λ) = Ext_{Λ}^{∗}(Λ/r, Λ/r) is a Koszul algebra.

We remark that even if Λ is a commutative algebra, E(Λ) is, in general, not commutative. Furthermore, even if Λ is finite dimensional, E(Λ) need not be Noetherian. Thus, the setting of noncommutative rings which are not necessarily Noetherian naturally arises in the studey of Koszul algebras.

We say that Λ = KΓ/I is a quadratic algebra if I is generated linear combinations of paths of length 2. Note that Λ is quadratic if and only if I is homogeneous in the length grading and generated by elements of degree 2.

Proposition 8.3 [21, Cor 7.3] If Λ is a Koszul algebra then Λ is a quadratic algebra.

We remark that the converse is not true in general. For example, if Γ is the graph

∘^{v_{1}}  \begin{matrix}a \\ → \\ ← \\ b \end{matrix}  ∘^{v_{2}}  \begin{matrix}c \\ → \\ ← \\ d \end{matrix}  ∘^{v_{3}}

and I is the ideal generated by ba, ab + dc, and cd in KΓ then although I is quadratic, it is not hard to show that KΓ/I is not a Koszul algebra.

The next result describes the algebra structure of the Yoneda algebra of a Koszul algebra. For this we need some further notation and definitions. We let Γ^{op} denote the opposite quiver of Γ. That is, Γ_{0}^{op} = Γ_{0} and Γ_{1}^{o} = {a^{o} : v → w | where a : w → v is an arrow in Γ}. Let V_{2} denote the vector space in KΓ spanned by the paths of length 2 in Γ and let V_{2}^{o} denote the vector space in KΓ^{op} spanned by the paths of length 2 in Γ^{op}. Let x_{1}, …, x_{m} be the K-basis of V_{2} of paths of length 2. Similarly, let x_{1}^{o}, …, x_{m}^{o} be the corresponding basis of of V_{2}^{o}; that is, if x_{i} = ab with a, b ∈ Γ_{1} then x_{i}^{o} = b^{o}a^{o}. If W is a K-vector space we let W^{∗}, the dual space of W, be Hom_{K}(W, K). We let {x_{i}^{∗}} denote the dual basis of V_{2}^{∗} associated to the basis {x_{i}} of V_{2}. Then we have a canonical bilinear form

< , >: V_{2} × V_{2}^{o} → K

given by < x_{i}, x_{j}^{o} >= x_{j}^{∗}(x_{i}) where x_{j}^{∗} ∈ V_{2}^{∗} is part of the dual basis {x_{i}^{∗}} associated to the basis {x_{i}} of V_{2}. Finally, if Z is a subspace of V_{2}, then Z^{⊥} = {z^{o} ∈ V_{2}^{o} | < Z, z^{o} >= 0}.

We can now give the structure of the Yoneda algebra of a Koszul algebra.

Theorem 8.4 [22, Thm 2.2] [26] Let Λ = KΓ/I be a Koszul algebra and let I_{2} = I ∩ V_{2}. Then E(Λ) is isomorphic to KΓ^{op}/<I_{2}^{⊥} >.

Note that if Z is a subspace of V_{2}, then (Z^{⊥})^{⊥} = Z. We get the following result.

Corollary 8.5 [22, Thm 2.3] Let Λ = KΓ/I be a Koszul algebra. Then E(E(Λ)) is isomorphic to Λ as graded algebras.

We have a partial converse to this corollary.

Theorem 8.6 [22, Thm 2.4] Let Λ = KΓ/I be a graded algebra with the length grading. Then Λ is a Koszul algebra if and only if E(E(Λ)), the Yoneda algebra of the Yoneda algebra of Λ is isomorphic to Λ as graded algebras.

We give two final ring theoretic results about Koszul algebras.

Proposition 8.7 [22, Cor 4.3] If Λ = KΓ/I is a Koszul algebra then the opposite algebra of Λ, Λ^{op} is also a Koszul algebra.

This result can be interpretted as saying that Λ is a Koszul algebra if and only if Λ/r has a colinear injective resolution. The definition of a colinear injective resolution is left to the reader.

Theorem 8.8 [22, Thm 3.7] If Λ = KΓ/I and Λ′ = KΓ′/I′ are Koszul algebras then Λ ⊗_{K} Λ′ is a Koszul algebra.

References

[1] W. Adams and P. Loustaunau, An Introduction to Gröbner bases, Graduate St. in Math, AMS, 3, 1994.

[2] D. Anick,Noncommutative graded algebras and their Hilbert series, J. of Algebra 78, (1982), 120-140.

[3] D. Anick,On monomial algebras of finite global dimension, Transactions AMS 291 (1985), 291-310.

[4] D. Anick, Recent progress in Hilbert and Poincaré series LNM 1318, (1986) Springer-Verlag, 1-25.

[5] D. Anick and E.L. Green, On the homology of path algebras, Comm. in Algebra, 15, (1985), 641-659.

[6] M. Auslander, I. Reiten, and S. Smalø, Representation Theory of Artin Algebras , Canbridge Studies in Advanced Math., 36, (1995), Cambridge Univ. Press.

[7] J. Backelin, R. Froberg, Koszul algebras, Veronese subrings and rings with linear resolutions, Rev. Roumaine Math. Pures Appl. 30 (1980), 85-97.

[8] M. Bardzell, The alternating syzygy behavior of monomial algebras, to appear J. of Algebra.

[9] T. Becker and V. Weispfenning, Gröbner bases. A Computational Approach to Commutative Algebra GTM, 141 Springer-Verlag, 1993.

[10] A. Beilinson, V. Ginsburg, & W. Soergel, Koszul Duality Patterns in Representation Theory, J. Amer. Math.Soc. 9 (1996) 473-527.

[11] G. Bergman, The diamond lemma for ring theory Adv. Math., 29, (1978) 178-218.

[12] A.I. Bondal, Helices, representations of quivers and Koszul algebras, London Math. Soc. Lecture Note Ser. 148, (1990), 75-95.

[13] Buchberger,An algorithm for finding a basis for the residue class ring of a zero-dimensional ideal Ph.D. Thesis, University of Innsbruck, (1965).

[14] E. Cline, B. Parshall, and L. Scott, Finite dimensional algebras and highest weight categories, J. Reine Angew. Math. 391 (1988), 85-99.

[15] D. Cox, J. Little, and D. O’Shea, Ideals, Varieties, and Algorithms, UTM Series, Springer-Verlag (1992).

[16] D.R. Farkas, C. Feustel, and E.L. Green, Synergy in the theories of Gröbner bases and path algebras, Canad. J. of Mathematics, 45 (1993), 727-739.

[17] C. Feustel, E.L. Green, E. Kirkman, and J. Kuzmanovich, Constructing projective resolutions, Comm. in Alg. 21 (1993) 1869-1887.

[18] E.L. Green, Representation theory of tensor algebras, J. Algebra, 34, (1975), 136-171.

[19] E.L. Green, Poincaré-Birkhoff-Witt bases and Gröbner bases, preprint.

[20] E.L. Green and R. Huang, Projective resolutions of straightening closed algebras generated by minors, Adv. in Math. 110 (1995), 314-333.

[21] E.L. Green, and R. Martínez Villa, Koszul and Yoneda algebras, Canadian Math. Soc., 18, (1994), 247-298.

[22] E.L. Green, and Martínez Villa, Koszul and Yoneda algebras II, to appear.

[23] E.L. Green and D. Zacharia, The cohomology ring of a monomial algebra Manuscripta Math. 85 (1994).

[24] R. Hartshone, Residues and Duality, LNM 20, Springer-Verlag, (1966).

[25] Z. Kramer, *****.

[26] C. Löfwall, On the subalgebra generated by the one-dimensional elements in the Yoneda ext-algebra, LNM 1183, Springer-Verlag, (1986), 291-338.

[27] R. Martínez Villa, Applications of Koszul algebras: the preprojective algebra, Canadian Math. Soc., 18, (1994), 487-504..

[28] S. McLane, Homology, Springer-Verlag, 1963.

[29] F. Mora, Gröbner bases for non-commutative polynomial rings, Proc. AAECC3 L.N.C.S. 229 (1986).

[30] S. Priddy, Koszul resolutions, Trans. AMS, 152 (1970), 39-60.

[31] J.E. Roos, Relations between the Poincaré-Betti series of loop spaces and of local rings, LNM, 740, Springer-Verlag, 285-322.

[32] M. Rosso, Koszul resolutions and quantum groups, Nuclear Phys. B Proc. Suppl., 18b (1990), 269-276.

[33] V. Ufnarovskii, A growth criterion for graphs and algebras defined by words Mat. Zemati 31 (1980) 465-472; Math. Notes 37 (1982) 238-241.

[34] Y. Yoshino, Modules with linear resolutions over a polynomial ring in two variables, Nagoya Math. J. 113, (1989), 89-98.