论文标题
Edmonds的问题和Quiver表示轨道半群的会员问题
Edmonds' problem and the membership problem for orbit semigroups of quiver representations
论文作者
论文摘要
由J. Edmonds提出的代数复杂性中的一个核心问题要求确定给定的$ L $ -TUPLE $ \ v =（\ v_1，\ ldots，\ v_l）$ n \ times n $ n $复杂矩阵包含一个非单向矩阵。 在本文中，我们为这个问题提供了一种颤抖的理论方法。查看$ \ v $作为$ l $ -Kronecker Quiver $ \ k_l $的表示，Edmonds的问题可以表现为要求决定是否存在表示在表示空间$（\ cc^{n \ times n} n \ times n}）^l $（-1，-1，-1）$的$（$ ccc^{n \ times n}）$（-1，-1）的$ v $ f van $ \ v v v v v v v v v v v v v v v v v v v。换句话说，埃德蒙兹的问题是要确定权重$（1，-1）$是否属于$ \ v $的Orbit Semigroup。 令$ q $为任意的无环颤抖，$ \ v $ a表示$ q $。我们通过关注所谓的$ \ v $饱和权重来研究$ \ v $的轨道半组的会员问题。我们首先表明，对于任何给定的$ \ v $ - 饱和权重$σ$，检查$σ$是否属于$ \ v $的Orbit Semigroup，可以在确定性的多项式时间内完成。 接下来，让$（q，\ r）$为一个无环的箭量，带有绑定箭量代数$ a = kq/\ langle \ r \ rangle $，并假设$ \ v $满足$ \ r $中的关系。我们表明，如果$ a/\ ann_a（\ v）$是驯服的代数，那么$ \ v $的权重的任何权重$σ$是$ \ v $ - 饱和。 我们的结果提供了一种系统的方法来生产矩阵的家族，可以为此有效解决埃德蒙兹的问题。
A central problem in algebraic complexity, posed by J. Edmonds, asks to decide if the span of a given $l$-tuple $\V=(\V_1, \ldots, \V_l)$ of $N \times N$ complex matrices contains a non-singular matrix. In this paper, we provide a quiver invariant theoretic approach to this problem. Viewing $\V$ as a representation of the $l$-Kronecker quiver $\K_l$, Edmonds' problem can be rephrased as asking to decide if there exists a semi-invariant on the representation space $(\CC^{N\times N})^l$ of weight $(1,-1)$ that does not vanish at $\V$. In other words, Edmonds' problem is asking to decide if the weight $(1,-1)$ belongs to the orbit semigroup of $\V$. Let $Q$ be an arbitrary acyclic quiver and $\V$ a representation of $Q$. We study the membership problem for the orbit semi-group of $\V$ by focusing on the so-called $\V$-saturated weights. We first show that for any given $\V$-saturated weight $σ$, checking if $σ$ belongs to the orbit semigroup of $\V$ can be done in deterministic polynomial time. Next, let $(Q, \R)$ be an acyclic bound quiver with bound quiver algebra $A=KQ/\langle \R \rangle$ and assume that $\V$ satisfies the relations in $\R$. We show that if $A/\Ann_A(\V)$ is a tame algebra then any weight $σ$ in the weight semigroup of $\V$ is $\V$-saturated. Our results provide a systematic way of producing families of tuples of matrices for which Edmonds' problem can be solved effectively.
