** Applied Mathematics ** Vol. 3 No. 7 (2012) , Article ID: 19863 , 3 pages DOI:10.4236/am.2012.37121

An Application of Eulerian Graph to PI on

School of Mathematics and Computer Science, Hubei University, Wuhan, China

Email: yousongfa@163.com

Received April 25, 2012; revised May 31, 2012; accepted June 6, 2012

**Keywords:** Eulerian Graph; Eulerian Path; Admissible; Polynomial Identity

ABSTRACT

We obtain a new class of polynomial identities on the ring of n ´ n matrices over any commutative ring with 1 by using the Swan’s graph theoretic method [1] in the proof of Amitsur-Levitzki theorem. Let be an Eulerian graph with k vertices and d edges. Further let be an integer and assume that.

We proof that is an PI on. Standard and Chang [2] Giambruno-Sehgal [3] polynomial identities are the special examples of our conclusions.

1. Introduction

Let be a finite directed graph with multiple edges allowed, and let denote the vertex set of and the edges set of. Let and be the functions from to defined by where e_{s} is an edge from vertex i to vertex j. For a vertex we put

and

We say that is an Eulerian path of if is an element of Sym(d) (the symmetric group acting on the set and for.

It is well known that a connected graph has an Eulerin path starting at vertex p and ending at vertex q if and only if one of the following two conditions applies:

1) and for each;

2) and, and for each.

A directed connected graph with fixed vertices p and q is called Eulerian if either condition 1) or 2) is satisfied. We note that if is an Eulerian graph of type (b), then the vertices p, q are uniquely determined, but in the other case we may choose any vertex. For an Eulerian graph denote by

2. Main Results

Let be an Eulerian graph with d edges and distinguished points p and q. the polynomial associated with is defined as follows:

Thus is a multilinear polynomial in the set of non-commuting indeterminates.

Let be an integer, C a commutative ring with 1 and a set map where the’s are the standard matrix units over C. It is clear that T can be viewed as a substitution. we shall define a directed graph induced from by T. First consider the directed graph on the vertex set with edge set where, and. Now we define by restricting the vertex set to. We note that the graph so obtained need by no means be connected let alone Eulerian. If it is Eulerian however, by construction has at most min vertices, where, i.e., for all and ,. Those elements of which do lift to an Eulerian path of will be called admissible (with respect to T). It is clear that is admissible if and only if is an Eulerian path of. For the remainder of this section, we introduce Swan’s theorem and our main results.

Swan [1]. Let be an Eulerian graph with d edges and k vertices satisfying. Then has the same number of odd and even permutations (with respect to the fixed order)

Theorem 1. Let be an Eulerian graph with vertex set and d edges. Further let be an integer such that

.

Then is a polynomial identity on the ring of matrices over a commutative ring C with 1 Corollary 2. Let be an Eulerian graph with k vertices and d edges. Further let be an integer and assume that. Then is a polynomial identity on.

3. Proof of Theorem 1

Since is multilinear, it suffices to show that for any substitution T of matrix units over C. Fix such an T and put,. Then

(*)

Now consider. Clearly, and summand in (*) vanishes unless, for the given,

for all, i.e., if is admissible. If so, on multiplying the matrix units, we obtain

.

It follows that where the inner sum is taken over all admissible permutations with and. If no such admissible exists, the inner sum is 0 by definition. We want to prove that this inner sum is 0 anyway. It is readily seen that for any choice of u and b, a sum and in the inner sum arises precisely of lifts to an Eulerian path of from (p, (u) to (q, v). Thus, on applying Swan’s theorem to with and, we find that the number of even and odd admissible permutations with and coincide whence the inner sum is 0 for any choice of u and v. This completes the proof.

4. Applications

1) Let be the Eulerian graph on one vertex with d loops. Then and

the standard polynomial [2] in d indeterminates.

More generally, let be the Eulerian graph on k vertices with distinguished points and the number of edges from vertex i to j:

Now clearly and

k times. On putting and labelling the indeterminates, corresponding to the edges from i to by, from the corollary 2 it follows that

is a polynomial identity on [3] if, i.e., if.

2) For we define a sequence, of staircase steps, and the staircase height. We will construct a substitution T, such that lifts to the unique convering directed path of (i.e.,). First define a function by

;,

,.

Next we define by recursion the sequence of pair, , where is a natural number and is a subset of. We put and. Having in hand. There are three cases to consider:

a)b), c),.

We now put

and

Let for all, it is clear that gives a substitution of matrix units over C. Now

is the unique covering directed path of from

to [4-7]. Since the entry of the matrix is, we have Theorem 3. Let be an Eulerian graph and. If, then is not a polynomial identity on the ring of matrices over a commutative ring C with 1.

Remark. It is an obvious consequence of the above theorem that if is not the least integer for which is not a polynomial identity on.

We note that, in general min is not the least integer for which is not a polynomial identity on.

Let be the Eulerian graph on one vertex d loops. It is easily see that

Thus for all and the minimality assertion of the Amitsur-Levitzki theorem follows; the main part is an immediate consequence of the corollary.

Let be the Eulerian graph on k vertices with distinguished points and the number of edges from vertex i to j:

Analogously, for any we have

In consequence for all.

For we get the double Capelli polynomial; it is known, however, that in this case is not the smallest n for which is not a polynomial identity on.

When we use x, y and z instead of the symbols, , and respectively to denote the indeterminates of the triple Capelli polynomial and continue to write m for the number of edges from vertex i to i + 1. Thus the triple Capelli polynomial is

REFERENCES

- R. G. Swan, “An Application of Graph Theory to Algebra,” Proceedings of the American Mathematical Society, Vol. 14, 1963, pp. 367-373.
- Q. Chang, “Some Consequences of the Standard Polynomial,” Proceedings of the American Mathematical Society, Vol. 104, 1988, pp. 707-710. doi:10.1090/S0002-9939-1988-0964846-8
- A. Giambruno and S. K. Sehgal, “On a Polynomial Identity for n´n Matrices,” Journal of Algebra, Vol. 126, No. 2, 1989, pp. 451-453. doi:10.1016/0021-8693(89)90312-8
- S. F. You, Y. M. Zheng and D. G. Hu, “Eulerian Graph and Polynomial Identities on Matrix Rings,” Advances in Math, Vol. 32, 2003, pp. 425-428.
- S. F. You, “The Primitivity of Extended Centroid Extension on Prime GPI-Rings,” Advances in Math, Vol. 29, 2000, pp. 331-336.
- S. F. You, “The Essential (One-Sided) Ideal of Semiprime PI-Rings,” Acta Mathematica Sinica, Vol. 44, 2001, pp. 747-752.
- S. F. You, M. Cao and Y. J. Feng, “Semiautomata and Near Rings,” Quantitative Logic and Soft Computing, Vol. 5, 2012, pp. 428-431. doi:10.1142/9789814401531_0058