|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Non-commutative Edmonds' problem and matrix semi-invariants | | Gábor Ivanyos
; Youming Qiao
; K. V. Subrahmanyam
; | | Date: |
4 Aug 2015 | | Abstract: | In 1967, Edmonds introduced the problem of computing the rank over the
rational function field of an $n imes n$ matrix $T$ with integral homogeneous
linear polynomials. In this paper, we consider the non-commutative version of
Edmonds’ problem: compute the rank of $T$ over the free skew field. It is known
that this problem relates to the ring of matrix semi-invariants. In particular,
if the nullcone of matrix semi-invariants is defined by elements of degree
$leq sigma$, then there follows a $mathrm{poly}(n, sigma)$-time randomized
algorithm to decide whether the non-commutative rank of $T$ is $<n$. To our
knowledge, previously the best bound for $sigma$ was $O(n^2cdot 4^{n^2})$
over algebraically closed fields of characteristic $0$ (Derksen, 2001).
In this article we prove the following results:
(1) We observe that by using an algorithm of Gurvits, and assuming the above
bound $sigma$ for $R(n, m)$ over $mathbb{Q}$, deciding whether $T$ has
non-commutative rank $<n$ over $mathbb{Q}$ can be done deterministically in
time polynomial in the input size and $sigma$.
(2) When $mathbb{F}$ is large enough, we devise a deterministic algorithm
for non-commutative Edmonds’ problem in time polynomial in $(n+1)!$, with the
following consequences.
(2.a) If the commutative rank and the non-commutative rank of $T$ differ by a
constant, then there exists a randomized efficient algorithm that computes the
non-commutative rank of $T$.
(2.b) We prove that $sigmaleq (n+1)!$. This not only improves the bound
obtained from Derksen’s work over algebraically closed field of characteristic
$0$ but, more importantly, also provides for the first time an explicit bound
on $sigma$ for matrix semi-invariants over fields of positive characteristics. | | Source: | arXiv, 1508.0690 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER