  In 1967, Edmonds introduced the problem of computing the rank over the
rational function field of an $n\times 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^2\cdot 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 $\sigma\leq (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.
