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
