Edmonds' problem and the membership problem for orbit semigroups of quiver representations (Q2079660): Difference between revisions

Edmonds' Problem asks to decide if the span of a given tuple of square matrices over the field of complex numbers contains a non-singular matrix. It plays essential role in algebraic complexity theory. For example, a deterministic polynomial time algorithm for Edmonds' Problem implies non-trivial arithmetic circuit lower bounds. A \textit{quiver datum} \((W,\sigma)\) consists of a representation \(W\) of a quiver \(Q\) (a finite acyclic directed graph) and a weight \(\sigma\) (an integer valued function on the set of vertices \(Q_0\) of \(Q\)) satisfying \(\sum_{v\in Q_0}\underline{\dim}(W)(v)\theta(v)=0\). The authors associate with the quiver datum \((W,\sigma)\) a tuple of square matrices, obtained as block matrices by placing matrix components of \(W\) in various positions determined by the quiver and the weight. The authors point out that as a consequence of a known description of semi-invariants of quivers, the span of the tuple associated to \((W,\sigma)\) contains a non-singular matrix if and only if the weight \(\sigma\) belongs to the orbit semigroup \(S_Q(W)\) of \(W\). Recall that the \textit{orbit semigroup} \(S_Q(W)\) is the affine semigroup consisting of the weights \(\sigma\) for which there exists a semi-invariant polynomial function of weight \(\sigma\) on the space of representations of \(Q\) with dimension vector \(\underline{\dim}(W)\) which does not vanish at \(W\). A weight \(\sigma\) is \textit{\(W\)-saturated} if whenever \(n\sigma\) is contained in \(S_Q(W)\) for some positive integer \(n\), then \(\sigma\) belongs to \(S_Q(W)\). The first main result characterizes \(\sigma\)-semistability of \(W\) in terms of the capacity of \((W,\sigma)\), and proves that \(\sigma\) is \(W\)-saturated if and only if \((W,\sigma)\) has the Edmonds-Rado Property. Consequently, for a \(W\)-saturated weight \(\sigma\) there exists a deterministic polynomial time algorithm to check if \(\sigma\) belongs to \(S_Q(W)\). The second main result provides a source of \(W\)-saturated weights. It is shown that if the factor of the path algebra of the quiver \(Q\) modulo the annihilator of \(W\) is a tame algebra, then all weights in the so-called weight semigroup of \(W\) are \(W\)-saturated. This way the authors produced families of matrix tuples for which Edmonds' Problem can be solved effectively.