Edmonds' problem and the membership problem for orbit semigroups of quiver representations
share
A central problem in algebraic complexity, posed by J. Edmonds, asks to decide if the span of a given l-tuple =(_1, …, _l) of N × N complex matrices contains a non-singular matrix. In this paper, we provide a quiver invariant theoretic approach to this problem. Viewing as a representation of the l-Kronecker quiver _l, Edmonds' problem can be rephrased as asking to decide if there exists a semi-invariant on the representation space (^N× N)^l of weight (1,-1) that does not vanish at . In other words, Edmonds' problem is asking to decide if the weight (1,-1) belongs to the orbit semigroup of . Let Q be an arbitrary acyclic quiver and a representation of Q. We study the membership problem for the orbit semi-group of by focusing on the so-called -saturated weights. We first show that for any given -saturated weight σ, checking if σ belongs to the orbit semigroup of can be done in deterministic polynomial time. Next, let (Q, ) be an acyclic bound quiver with bound quiver algebra A=KQ/⟨⟩ and assume that satisfies the relations in . We show that if A/_A() is a tame algebra then any weight σ in the weight semigroup of is -saturated. Our results provide a systematic way of producing families of tuples of matrices for which Edmonds' problem can be solved effectively.
READ FULL TEXT