{
  "id": "2104.14841",
  "version": "v1",
  "published": "2021-04-30T08:53:34.000Z",
  "updated": "2021-04-30T08:53:34.000Z",
  "title": "A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with $2 \\times 2$ submatrices",
  "authors": [
    "Yuni Iwamasa"
  ],
  "comment": "Full version of an IPCO 2021 paper",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "In this paper, we consider the problem of computing the degree of the determinant of a block-structured symbolic matrix (a generic partitioned polynomial matrix) $A = (A_{\\alpha\\beta} x_{\\alpha \\beta} t^{d_{\\alpha \\beta}})$, where $A_{\\alpha\\beta}$ is a $2 \\times 2$ matrix over a field $\\mathbf{F}$, $x_{\\alpha \\beta}$ is an indeterminate, and $d_{\\alpha \\beta}$ is an integer for $\\alpha, \\beta = 1,2,\\dots, n$, and $t$ is an additional indeterminate. This problem can be viewed as an algebraic generalization of the maximum weight perfect bipartite matching problem. The main result of this paper is a combinatorial $O(n^4)$-time algorithm for the deg-det computation of a $(2 \\times 2)$-type generic partitioned polynomial matrix of size $2n \\times 2n$. We also present a min-max theorem between the degree of the determinant and a potential defined on vector spaces. Our results generalize the classical primal-dual algorithm (Hungarian method) and min-max formula (Egerv\\'ary's theorem) for maximum weight perfect bipartite matching.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-04-30T08:53:34.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "generic partitioned polynomial matrix",
      "combinatorial algorithm",
      "maximum weight perfect bipartite matching",
      "perfect bipartite matching problem",
      "determinant"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}