热带线性与最小加复杂性：计算问题与NP完全性

1热带和最小加线性前变的复杂性。Dima Grigoriev1，Vladimir V. Podolskii21CNRS，Math′ematiques，Universit′eLille，FranceDmitry. math.univ-lille1.fr2俄罗斯莫斯科斯捷克洛夫数学研究所podolskii@mi.ras.ru摘要一个热带（或min-plus）半环是一个集合Z（或Z <${∞}），它被赋予两个运算：一个是通常的最小值，另一个是通常的加法。在热带代数中，向量x是多项式g1（x）<$g2（x）<$的解。. . 如果min i（gi（x））中的最小值至少达到两次，则证明g k（x），其中gi（x）是热带单项式。 在min-plus代数中，形式为g1（x）的方程组的解. . . gk（ x）= h1（ x）. . 研究了λ h_l（x）.本文考虑与热带线性系统有关的计算问题我们证明了可解性问题（在Z和Z<${∞}上）和判定两个线性系统等价的问题（在Z和Z<${∞}上）在多项式时间约化下等价于平均支付博弈，并且等价于分析问题。min-plus代数中的一些问题。特别地，所有这些问题都属于NP问题。因此，我们提供了热带线性代数的计算方面与平均支付游戏和最小加线性代数的紧密联系。另一方面，我们证明了计算热带线性系统和最小加线性系统的解空间的维数是NP-完全的。我们也将我们的一些结果推广到最小加线性不等式组1介绍一个极小加或热带半环定义为集合K赋予了两个运算和。对于K，我们可以取Z，R，Z<${+∞}，R<${+∞}等，本文主要考虑Z和Z∞=Z<${+∞}的情形。arXiv：1204.4578v1 [cs.CC] 2012年4月2我们的结果也推广到了Q和Q∞=Q <${∞}的情形。热带加法运算和热带乘法运算的定义如下：x y= min{ x，y}，x y= x+ y.对于与矩阵A∈Km×n相联系的热带线性系统，我们称之为min{aij+xj}，1≤i≤m，（1）1≤j≤n或者换句话说，向量A∈x，对于x =（x1，. . . ，xn）。 我们说，xi=（∞，. . .，∞）是系统（1）的解，如果对于每一行1≤i≤m，有两列1≤k< l≤n，使得aik+ xk= ail+ xl= min{ aij+ xj}。1≤j≤n按照[14]的记号，我们把热带线性系统的解的集合称为热带线性预簇。从[14]的分析可以得出是在“prevariety”中使用pre-in的原因之一我们称热带前变种的维数为包含在其中的多面体的最大维数。对于与一对矩阵A，B∈Km×n相关联的（双边）最小线性方程组，我们称之为min{aij+xj}=min{bij+xj}，1≤i≤m。（二）1≤j≤n1≤j≤n关于一对矩阵A，B∈Km×n的（双边）最小加线性不等式组，我们称之为min{aij+xj}≤min{bij+xj}，1≤i≤m。（三）1≤j≤n1≤j≤n我们注意到，对于所有系统，我们认为使用最小或最大值的函数并不重要。整个理论仍然是一样的。与（min，+）结构有关的代数的两个分支--热带代数和min-plus代数有不同的起源。热带代数出现在代数几何（见调查[10，15]）和最小代数出现在调度理论（见最近的专着[4]）。因此，这两个分支的理论是不同的，而且大多是平行发展的关于这些代数的计算方面，最基本的问题是线性代数领域。在经典代数中，最著名的高斯3.Σ算法在多项式时间内解决线性系统。在热带半环的情况下，事情变得更加复杂，没有多项式时间算法是已知的热带线性系统，也不为min-plus线性系统。然而，对于热带情况，已知该问题是NP问题，也有伪多项式算法[8，1]，并且已知该问题简化为众所周知的长期存在的问题平均支付游戏[1]（参见第2节的定义）。在算法方面，Grigoriev [8]构造了一个对常长矩阵同时是伪多项式和多项式的算法，即它的运行时间同时受poly（m，n）MlogM和poly（2nm，logM）的限制，其中n是列数，m是行数，M是矩阵项的最大绝对值。 关于对n和mm+nn在第二个上界中，最著名的上界大致是由Davydov [5]证明的在[5]中也显示，是Grigoriev算法的紧上界关于最小加线性系统的可解性问题，我们知道得更多。除了包含在NP问题和伪多项式算法中，对于热带系统，Bezem等人[3]证明了该问题是多项式时间等价于平均支付博弈。与我们的考虑有关的min-plus代数的一个更复杂的方面是min-plus线性不等式组的可解性问题。在经典的情况下，相应的问题本质上是线性规划，它在一段时间内被认为是NP完全NP，并最终被证明是P[9]。因此，直觉上，最小加代数中的相应问题似乎比求解线性最小加方程组更难（并且可以看出，不等式在形式上并不比最小加线性代数中的等式更难）。对于最小加线性不等式组，已知可解性问题等价于平均支付对策[1]。本文的第一个结果是热带线性系统的可解性问题也等价于平均支付博弈。因此，一方面刻画了热带线性系统可解性问题的复杂性，另一方面给出了平均支付对策的一个新的重新表述。特别地，我们的结果意味着平均支付博弈的可解性问题等价于最小加系统的可解性问题。这样，我们就建立了op上代数的两个分支之间的紧联系最小值和+值。此外，从我们的减少翻译格里戈里耶夫的算法，平均支付游戏如下。我们不知道一个而另一个具有并行执行它们的第二边界）。这4表明该转换算法可能本质上不同于用于平均支付游戏的已知算法。接下来我们研究与热带线性系统有关的其他问题：两个给定的热带线性系统的等价问题和计算热带前变的维数的问题。前一个问题也被证明是等价于平均支付游戏。最小加线性系统的类似状态也是真实的，并遵循已知的结果（见下面的引理11）。有趣的是，热带前变种的维数问题是NP-完全的. 更确切地说，我们证明了如下问题的NP-完全性：给定一个m×n的矩阵A，其个数k决定对应于A的热带线性系统的热带前簇的维数是否至少为k。对于最小正线性系统和最小正不等式组，我们也证明了类似的结果。上述结果我们对Z和Z∞域都证明了（这两种情况之间没有明显的转换）。我们的证明技术主要是组合的。对于可解性问题与平均支付博弈的等价性，我们使用[13]的结果，其中显示了平均支付博弈与最大原子问题（简称MAP）的等价性（定义见第2节）。这个结果在文献[3]中已经被用来证明最小加线性系统的可解性问题等价于平均支付对策。证明了极小加线性方程组的可解性问题等价于MAP问题。对于我们的结果，我们表明热带线性系统的可解性问题是等价的MAP。这里的主要困难是MAP更容易用于研究min-plus结构而不是热带结构。从可解性的等价问题的意思是支付游戏之间的一些纯粹的热带计算问题的等价我们也给出了直接的组合证明，不涉及这些问题之间的平均支付博弈的减少。对于热带线性方程组的维数问题，我们给出了顶点覆盖问题的一个约化这里的主要技术成分是给定热带线性系统的热带前变种的维度的组合表征本文的其余部分组织如下。在第二节中，我们陈述了我们需要的关于热带线性系统的事实。在第三节中，我们证明了热带线性方程组的可解性问题与平均支付对策的可解性问题的等价性。第四节讨论了热带线性方程组解空间的维数与已知热带秩概念之间的关系。在第5节和第6节中，我们证明了热带前簇维数的NP完全性：在第5节中，我们给出了一个组合的5刻画的维度，并在后者，我们用它来证明NP-完全性。2预赛在整个论文中，对于整数n，我们用[n]表示集合{1，2，. . . ，n}。通过≤m，我们表示多项式时间的多到一的约简。通过≤T，我们表示多项式时间图灵约简。2.1平均收益博弈在一个平均支付博弈的例子中，我们给出一个有向二部图G=（V，E），它的顶点被分成两个不相交的集合V=V1<$V2，某个固定的初始节点v∈V1，以及一个函数w：E→Z给G的边赋权.在游戏开始时，初始顶点v。在每一轮中，其中一个玩家将代币移动到图中的其他节点。游戏的每一轮都是按以下方式进行的。如果令牌当前位于某个节点u∈V1，则第一个玩家可以将其移动到任何节点w，使得（u，w）∈E。 另一方面，如果u∈V2，则第二个玩家可以将代币移动到任何节点w，使得（u，w）∈E。博弈是无限的，博弈的过程可以用节点v0，v1，v2，.的序列来描述。. . 令牌访问的对象。注意v0=v。第一个玩家赢得游戏，如果1吨极限信息n→∞ti=1w（v i−1，v i）> 0。（四）相应的平均支付博弈问题是决定第一个参与者是否有获胜策略。欲了解更多关于平均付费游戏的信息，请参阅调查[12]。众所周知，两个玩家都有最优的位置策略，也就是说，策略只取决于代币的当前位置，而不取决于历史。特别地，由此可以得出博弈的最优值（第一个参与者可以达到的（4）的最大左边）是一个有理数，分母多项式是G的顶点数。另外，很明显，否定的平均支付博弈问题的实例，即第二个玩家是否有获胜策略的问题，是多项式时间m-可约的平均支付博弈。 实际上，只需改变参与者的角色，并添加新的初始顶点v′，没有进入边和一条出去边（v′，v），将移动传递给第二个参与者。6博弈的值可能为零的问题可以通过将所有权重改变一个小的有理数来处理（之后博弈的值总是非零的），然后将它们乘以分母使它们成为整数。在我们的约简过程中，有时我们会遇到这样的情况，当我们将某个问题约简为另一个问题的几个实例的解时，等价于平均支付博弈，也就是说，原始问题的输入将是“是”的实例，在约简过程中构造的所有输入都是等价于平均支付博弈的问题的“是”的输入。在这种情况下，我们实际上可以用一个输入来代替几个输入，因为我们可以对平均支付策略这样做。事实上，我们可以只考虑由对应于我们的几个输入的所有图的不连接副本组成的图，添加属于第二个玩家的节点，他可以从该节点到达所有起始节点并添加一个节点，将第一步传递给第一个玩家。2.2热带和极小加线性方程组考虑任意热带线性系统（1）。注意，它的热带prevariety S在热带标量乘法下是封闭的，或者，换句话说，S=S+Z→1，其中y→1不等于所有的向量。胡世伟可以把（1）的解的集合看作是热带射影spaceTPn−1=Rn/n→1<$R中的一个集合。在这篇文章中，我们将讨论空间Rn和TRn−1中的解预变，这取决于在当前的论证中哪一个更方便。考虑某个矩阵A∈Zm×n.请注意，给A的某行的所有项加上某个数字并不改变系统（1）的热带前变种因此，在证明的过程中，我们可以自由地从所考虑的矩阵的某行中我们把一个向量r→v∈Zn用于A的所有路径，而不是由A→v 产 生 的 向 量。 新发现A→v的热带前变种是A的热带前变种的线性翻译。由于许多重要的我们将把这种变换应用于矩阵。最后，让我们将矩阵的所有元素乘以相同的常数c∈N。请注意，热带前变种中的所有向量也乘以相同的常数。有时我们也会做这个操作特别地，这个观察意味着我们的所有结果对于域Q和Q ∈{∞}也是正确的。上述所有观察结果对于最小加等式系也是正确的7∞和不平等。考虑一个热带线性方程组，其矩阵为A∈Zm×n，并假设对所有i∈[m]，j∈[n]，a ij > 0（我们可以将任何矩阵约化为这样的形式addingvectorsc·→1toherws ） . 假 设 矩 阵 x 的 整 数 由 某 个 值 M 限 定 ， 即aij≤M。在[8]中证明了以下限制最小解的大小的引理。引理1（[8]）. 如果系统有解（x1，. . .，xn），则它具有解（x′，. . . ，x′）满足0 ≤ x′≤ M。1个nj已知A的解空间是可能不同维数的多面体系统[14]。我们也知道解空间是连通的（见[16]，引理4.12）。在本文中，我们考虑以下问题。• TropSolv. 在这个问题中，我们给定一个整数矩阵A∈Zm×n。问题是决定相应的热带系统（1）是否可解。• TropEq UI v. 在这个问题中，我们给定两个整数矩阵A∈Zm×n和B∈Zk×n。问题是决定在同一组变量上对应的热带系统（1）是否等价。• Tropi Mpl. 在这个问题中，我们给定一个整数矩阵A∈Zn×n和一个向量l ∈ Zn。问题是判定对应于A的热带系统（1）是否蕴涵对应于A的热带等式去洛• TropD IM.在这个问题中，我们给定一个整数矩阵A∈Zm×n和一个数k ∈ N。问题是确定对应于热带系统（1）的热带前变的维数是否至少为k。对于上述所有问题，在Z∞上也有它们的变体。 我们用下标∞来表示它们，例如在TropSolv ∞问题中，给定一个矩阵A∈Zm×n，问题是判定Z ∞上相应的热带系统是否可解。对于Z∞上具有无穷坐标的点的热带前变的局部维数（即某点邻域的维数），我们只考虑有限坐标上的8当我们考虑Z∞上的系统时，我们不允许解仅由无穷多个组成。接下来，我们展示Z和Z∞情况之间的一些简单关系引理2.1. TropSolv ≤mTropSolv∞;2. TropIM pl≤mTropIM pl∞;3. TropD IM≤TropD IM∞。证据对于第一个约化，如果我们给定一个系数在Z中的热带线性系统，那么它在Z上可解，它在Z∞上可解。对于非平凡方向，如果在Z∞上存在一个解，其中某些坐标是无穷的，我们可以用足够大的有限数来代替它们。对于第二个约化，如果我们给定一个热带线性系统，在Z上的回归线性等式，考虑它们在Z∞上。如果在Z上没有蕴涵，也就是说，在Z上存在系统的解，但它不是方程的解，那么显然在Z∞上也是如此，也没有蕴涵。 如果在Z∞上没有蕴涵，则系统在Z∞用足够大的常数替换解中的无穷多个，我们得到在Z上也没有蕴涵。对于最后一个约化，如果我们有一个系数在Z中的热带线性系统，并且我们有一些无穷坐标的解，那么如果我们用足够大的有限数代替无穷数，那么在这一点上的局部维数不会减少。2.3最大原子问题为了证明我们的第一个结果，我们需要一个中间的最大原子问题或MAP。这个问题包括解决以下形式的不等式系统：max{x，y}+k>z（5）其中k也是整数。3求解热带系统等价于平均收益博弈在这一节中，我们证明了热带线性系统的可解性问题为此，我们证明TropSolv等同于MAP。首先，我们证明下面的简单引理。9引理3.TropSolv在多项式时间内减少到最小加不等式系统的可解性问题。此外，对于给定的热带线性方程组，我们可以有效地构造出在相同的变量集上具有相同的解集的最小加不等式组。对于定义域Z∞也是如此。证据设A是某个热带线性系统。对于每一个它的方程，我们构造了等价于该方程的同一变量集上的最小加不等式组为此，min{x1+a1 ， x2+a2 ， ...，xn+an}（6）是系统A的行之一。为了符号简单，我们表示y i= x i+ a i ， 其中 i = 1， . . . ， n.然后 我们 可以将 （ 6） 重写为min{y1，. . . ，y n}。很容易看出，上述表达式中的最小值至少达到两次的事实等价于对于任何i = 1，. . . ，n这是真的，min{y1，.， y i−1，y i+1，.， y n} ≤ y i.（七）每一个不等式都等价于min {y1，.， y i−1，y i− 1，y i+1，.， y n} ≤min {y1− 1，.， y i−1− 1，y i，y i+1− 1，.，y n− 1}。最后一个不等式已经是最小-最大不等式的形式，因此我们知道任何热带不等式都等价于最小-最大不等式组。为了得到等价于等式组的不等式组，我们只需将A的所有等式组合并。请注意，完全相同的分析适用于Z∞的情况。备注。 Akian et al. [1]证明了（在Z和Z∞上）最小加不等式组的可解性问题等价于平均支付对策。在那里也证明了TropSolv和TropSolv∞可以简化为平均支付博弈。上面的引理特别表明，后者的结果很容易从前者得出。作为引理3的推论，我们有从TropSolv到MAP的简化。推论4. TropSolv ≤mMAP。证据给定一个热带线性系统A，首先对每个等式构造不等式系统（7）。然后将所有这些不等式乘以（−1），并对变量x<$→ −x进行变换，从min切换到10最大在此之后，不等式几乎是MAP的形式，并且可以通过[3]第2节中描述的简单技巧容易地转换为所需的形式现在，我们开始反向还原。为此，我们需要以下技术引理。我是5分。 Letk≤nanddconsiderarbitryvector→a=（a1，. . . ，ak）∈Zk.则对任意C ∈Z，存在一个热带线性系统A∈Zm×n，其中m=n-k+1，使得• 对于任何i∈[m]和任何j ∈[k]，我们有ij=j;• 对于任何i∈[m]和任何j ∈[n]\[k]，我们有ij>C;• 对A的任意解和任意行，至少在行的e→a-p中的两次迭代中达到最小值。证据为了证明引理，我们将引入几个热带方程，系统A将是它们的并集。首先考虑与以下向量l=（→a，C +1，. . . 、C+1），其中l∈Zn.接下来，对于每个i = k +1，. . . ，n让li=l−ei=（→a，C+1，. . . 、C、. . . 、C+1），其中ei∈Zn是向量，第i个坐标为1，所有其他坐标为0，令克l0= l−i=1ei=（→a−→1，C+1，. . . 、C+1）。设A是由等式l0，l k+1，.组成的系统。. . ，l n.假设，通过矛盾的方式，A有一个解，使得在somerowlitthereis是一个最小的minimuminthehe→apartt。在这一行中，在列j中存在最小值，使得k+1≤j≤n。如果ji=i，则考虑行l j。很容易看出，这一行恰好包含一个最小值（在列j中），这就是矛盾。因此，f → a的最小值可以在列i（具体地，i = 0）中被唯一地确定。但由于最小值至少在那里达到两次，这是一个从一个人到一个人的过程。 现在我们知道了。可以理解的是，该流程的最小值是f→a的最小值，并且这些最小值是其中的至少两个。11我我我我我为了证明所需的减少，我们将使用下面的引理限制MAP的最小解的大小，这在[3]中得到了证明引理6（[3]）. 设M是变量x1，. . . ，xn，设C为M中所有常数的绝对值之和。则如果M是可解的，则有一个solution→xsucht有maxi∈[n]{xi}−mini∈[n]{xi}≤C。现在我们准备证明向后方向的归约定理7. MAP ≤mTropSolv.证据假设我们给出一个形式为max{x，y}+k>z的不等式组A。首先将所有不等式乘以（−1），并进行变量x<$→（−x）的变换。然后我们有一个形式为min{x，y}+k≤z的不等式组B，它是可解的当且仅当初始组是可解的。我们用C表示B中所有常数的绝对值之和。现在我们准备构造一个热带线性系统T。 让我们用x1，. . . ，x n.对于B的每个变量xi，我们的热带线性系统将有两个对应的变量xi和x′。我们希望这些变量在T的任何解中都相等。这可以通过Lemma5的方法容易地实现。 对于k=2，→a=（0，0），C=C，并将其应用于变量xi，x′。结果我们得到系统Ti，它保证在每个解中x i和x′相等. 我们包括系统Ti中的所有i。其次，我们必须保证对于B的任何不等式min{x，y}+ k ≤ z，其中x，y，z是x1，. . . ，xn的解，则T. 因为我们已经知道，对于T的每一个解，变量xi和x′是相等的，所以可以说，min{x，x′，y，y′，z−k，z′−k +1}至少达到两次。然而，我们必须在这个不等式中加入其他变量这可以通过引理5再次实现。对于这个引理k=6，→a=（0，0，0，0，−k，−k+1），C=Caplyatotevariablesx，x′，y，y′，z，z′，并将所得系统包含到系统T中。现在T的构造完成了，我们必须证明它是可解的当且仅当B是可解的。首先假设T有解。然后从T的构造得出，对于每个i=1，. . .，n个变量x ix是相等的。从这里再从T的结构中B的每个不等式都是真的。12我我另一方面，假设B是可满足的。然后，通过引理6，hereisasolution→xsucthatmax {x i} − min {x i} ≤ C。i∈[n]i∈[n]如果n∈[n]{x i}=0，则对于所有i，我们都有0≤x i≤C。 为解决方案设x i与B的解相同，且x′=x i对所有i。 剩下的就是检查这个向量是否是T的解。我们可以分别检查所有行。如果该行在T i中，对于某个i，则显然由于应用引理5时常数C的选择，在xi和x ′上达到最小值。 如果这行来自B的某个不等式min{x，y}+ k ≤ z，那么很明显，最小值要么在x和x′上，要么在y和y′上达到。由定理7和推论4，我们得出以下结论。推论8。 问题TropSolv多项式等价于平均支付游戏。此外，我们也可以对问题TropSolv∞得出同样的结论。推论9。 问题TropSolv∞多项式等价于平均支付博弈。证据Akian等人[1]证明了TropSolv∞是多项式时间可约化的平均支付博弈（也见引理3后的注释）。定理7给出了平均支付博弈可以简化为TropSolv。最后，TropSolv通过引理2简化为TropSolv∞，因此所有三个问题都是等价的。特别地，可以得出问题TropSolv和TropSolv∞是多项式时间等价的。但是，这两个纯粹的热带问题的等价性的在附录A中，我们给出了这个等价性的直接证明。我们的分析的另一个推论涉及热带线性系统的等价性和蕴涵问题。推论10。问题TropEq UI v，TropEq UI v∞是多项式时间等价于平均支付博弈。问题TropI M pl和TropI M pl∞在图灵归约下是多项式时间等价于平均支付博弈。13证据很容易看出，问题TropEqUI v等价于问题TropIM pl（在图灵归约下）。设给定一个热带系统A和一个热带方程l.决定l是否从A出发是等价于判定系统A和A∈ {l}是否等价。另一方面，如果我们需要检验两个系统A和B是否等价，只需检验第二个系统的每个方程是否都是从第一个系统得出的，反之亦然。我曾以为，吴亦凡是一个有实力的人。alent toTropIM pl.同样的论证也告诉我们，等于TropI M pl∞。注意，同样的论证也适用于最小加系统和最小加不等式系统。接下来，很容易构造从TropSolv到TropEq UI v的约简。事实上，要检验某个系统是否可解，只需检验它是否等价于某个固定的不可解系统。在引理2中证明了TropIM pl到TropIM pl∞的约化因此，只需要证明TropEqUI v∞简化为平均支付博弈。假设我们有两个热带系统A1和A2，我们必须检查它们是否等价。第一个引理3，我们构造了具有相同解集的不等式组。然后用同样的方法把不等式组的等价问题归结为不等式的蕴涵问题。最后，我们可以应用Allamigeon等人的结果。[2]指出Z∞上的最小加不等式的蕴涵问题等价于平均支付博弈。记 住 在 表 中 的 讨 论 ， 很 容 易 看 出 ， 对 于 问 题 TropEqUI v和TropEqUI v∞的情况，这些约简可以转化为m-约简。不难看出，对于最小加线性方程组，类似的结果与已知的结果是一致的。引理11. 环Z和Z ∞上最小加线性方程组的等价性和蕴涵问题等价于平均支付对策。对于线性不等式的最小加系统也是如此。证据与推论10的证明相同。代替引理3，我们可以应用min-plus等式和不等式之间的平凡关系关于Z∞上线性不等式的最小加系统的蕴涵问题的结果已在[2]中得到证明。14对于最小-加和热带线性方程组，我们在附录B中给出了可解性与等价问题之间等价性的直接组合证明。4维度和热带等级在经典线性系统的情况下，解空间的维数与矩阵的秩密切相关。 自然的想法是，也许热带前变种的维数也与热带矩阵的某个“秩”有关在文 献中 研究 的热 带代 数中 有三 种“ 秩 ” 的概 念： Barvinok秩、Kapranov秩和热带秩（定义见[ 6 ]）。对他们来说，热带等级（A）≤Kapranov等级（A）≤Barvinok等级（A）。（8）对任意矩阵A.所有的不等式在（8）中都是严格的。我们将显示以下结果。引理12. 对于任何矩阵A ∈ Rm×n，我们有n-热带维度（A）≤热带等级（A），不等式可以是紧不等式也可以是严格不等式。 这里的热带维数是指维数的仿射变量。这个引理与（8）一起表明热带矩阵的热带维数和秩之间存在关系，但这种关系不足以满足计算需要。Lemma的证明设A的热带秩等于r，并考虑A中热带独立列的最大集C，即使得由它们生成的热带线性系统不可解的最大列集。这组列的大小等于r（参见[6，11，8]）。 将剩余的n-r列中的一列加到C上，并将所得的m×（r+1）矩阵表示为C′。 C′中的列都依赖于热带，所以热带线性系统有一个解，列C′。这个解可以推广到整个系统的解，只要把所有坐标xi固定为足够大的数，i∈[n]\C′ 注意，A的结果解的这些坐标可以是15局部变化（如果选择的数字足够大）。因此我们有解空间包含维数为n−（r+1）的子空间。但请注意，目前我们有投影维数：一些坐标在这个子空间中永远不会改变 因此，我们可以将向量（1，. . . ，1）到我们的子空间，得到所需的n − r维子空间。为了证明不等式是紧的，例如考虑矩阵.Σ100.0 1 0很容易看出，对应的热带系统的解空间由点（c，c，c）组成，对于任何c，因此维数为1。该矩阵的热带秩为2。要看到这一点，考虑由前两列定义的子矩阵。另一方面，为了证明不等式可以是严格的，考虑矩阵变换0 0 0 0 01 0 0 0 01 1 0 0 01 1 1 0 0该矩阵的热带秩为4。为此，考虑由前四列定义的子矩阵。另一方面，解空间的维数也是4，因为它包含由（1，0，0，0，0）生成的子空间，（0，1，0，0，0），（0，0，1，0，0），（1，1，1，1，1）.上面的两个例子都可以很容易地推广到任意矩阵大小。5热带前变种在我们的分析中，使用下面的定义会很方便定义13. 设A是一个m×n的矩阵。我们将它与同样大小m×n的表A相关联，在表A中，我们将星号放在条目（i，j）iaij=minkaik中，而将所有其他条目留空。表A列出了热带系统A的基本性质。例 如 ，向量x =（x1，. . . ，x n）是系统A i的解，在表（{a ij+ x j}ij）的每一行中至少有两颗星，接下来，我们给出了局部维数的组合特征（在给定点）的热带prevariety在表A。 为此我们将使用以下矩阵的块三角形形式.16∗ ∗∗ ∗∗ ∗∗ ∗ ∗∅∗ ∗∗ ∗∗ ∗∗∗∅∅∗∅C1C2···Cd∗ ∗R1无菌过滤器∗ ∗A=R2双金属氧化物∗D∗ ∗ ∗∗ ∗∗ ∗∗ ∗定义14. 矩阵A的大小为d的分块三角形是将A的行集合划分为集合R1，R2，. . .，Rd（某些集合Ri可能是空的）和将A的列集合划分为非空集合C1，. . .，C d具有以下性质（见图）：1. 对于每个i，Ri中的每行在Ai中的列Ci中至少有两颗星;2. 如果1≤ij≤d，则Ri中的行在Ai中的列Cj中没有星。<我们寻找的是矩阵的分块三角形形式，它具有最大可能的d。接下来我们对最大尺寸的块三角形的结构进行几个观察：• 在不失一般性的情况下，具有空Ri的对（Ci，Ri）可以被移动到列表的开头，从而相应地置换Ci-s的列表和Ri-s的列表。• 我们可以假设具有空Ri的对具有|Ci|= 1。的确如果|> 1，我们可以将它分成几个大小为1的集合，而不违反块三角形的性质，大小只会增加。|> 1 we can break it into several sets of size 1 withoutviolating the properties of the block triangular form and the size will onlyincrease.现在我们准备给出前簇维数的一个组合刻画定理15. 设零矢量是热带线性系统A的解. 则系统A在零处的局部投影维数∗R.∗∗∗17解等于最大d，使得存在大小为d+1的A的块三角形形式。显然，任意解的情况可以归结为零解。证据 我们也可以假设A的每一行的最小值为0。用d表示最大块三角形减1的大小，用dimA表示零解中热带前簇的局部投影维数。不难看出，A>D。实际上，考虑大小为d + 1的块三角形形式，并将对于所有i = 2，. . . ，d +1。很明显，这个空间中任何一个足够接近零向量的点都是热带系统。这需要证明dimA≤d。考虑包含零点的热带前变种的最大维数的多面体。我们可以把自己限制在一个顶点为零点的同维圆锥上，并且使得顶点与圆锥相交的邻域位于多面体中。考虑一组独立的整数向量f1，f2，. . . ，fk位于锥中，其中k=dimA.由 于 我 们 考 虑 维度的 投 影 版 本 ， 因 此 我 们 在 projectivepac e 和afteranadditinofvetorc·→1=（c，. . . ，c）在圆锥中的任何矢量保持在圆锥中 所以我们可以同意向量f1，. . . ，f k是非正的。对于基向量f1，. . . ，f k考虑元组f i=（f 1，. . . ，f k）的基中的向量的所有第i个坐标。注意我我a=|{f1，f2，. . . ，fn}|>k+1，这是不同类型的视频的集合fi至少为k+1。实际上，将向量f 0=（−1，. . . （1）根据去拿钥匙吧。如果一个文件中的所有文件都不完整，如果i=→0，则k+1的新网络可以识别出矢量向量c i∈R是关于c0，c1，. . .，c k.该系统的k+1小于等式，因此具有非零解。 这意味着f 0，f 1，. . . ，f，k是线性相关，我们有矛盾。接下来，考虑101，. . . ，k- 有 理 数 上 线 性 无 关 的 足 够 小 的 正 实数 ， 并 考 虑 向量克f′=i=1阿吉菲岛18i=1L“Small 这个向量的不同坐标的数目相等a>k+ 1。 事实上，由于{k}k的线性独立性，我们有为不同的文件设置不同的文件夹。让我们以递增的顺序来计算f ′中的每一个元素：b1<。. .

下载后可阅读完整内容，剩余1页未读，立即下载