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 es 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