Loading…
On the Gröbner complexity of matrices
In this paper we show that if for an integer matrix A the universal Gröbner basis of the associated toric ideal I A coincides with the Graver basis of A , then the Gröbner complexity u ( A ) and the Graver complexity g ( A ) of its higher Lawrence liftings agree, too. In fact, if the universal Gröbn...
Saved in:
| Published in: | Journal of pure and applied algebra 2009-08, Vol.213 (8), p.1558-1563 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | In this paper we show that if for an integer matrix
A
the universal Gröbner basis of the associated toric ideal
I
A
coincides with the Graver basis of
A
, then the Gröbner complexity
u
(
A
)
and the Graver complexity
g
(
A
)
of its higher Lawrence liftings agree, too. In fact, if the universal Gröbner basis of
I
A
coincides with the Graver basis of
A
, then also the more general complexities
u
(
A
,
B
)
and
g
(
A
,
B
)
agree for arbitrary
B
. We conclude that for the matrices
A
3
×
3
and
A
3
×
4
, defining the 3×3 and 3×4 transportation problems, we have
u
(
A
3
×
3
)
=
g
(
A
3
×
3
)
=
9
and
u
(
A
3
×
4
)
=
g
(
A
3
×
4
)
≥
27
. Moreover, we prove that
u
(
A
a
,
b
)
=
g
(
A
a
,
b
)
=
2
(
a
+
b
)
/
gcd
(
a
,
b
)
for positive integers
a
,
b
and
A
a
,
b
=
(
1
1
1
1
0
a
b
a
+
b
)
. |
|---|---|
| ISSN: | 0022-4049 1873-1376 |
| DOI: | 10.1016/j.jpaa.2008.11.044 |