×

Computing the degree of determinants via discrete convex optimization on Euclidean buildings. (English) Zbl 1446.90135

Summary: In this paper, we consider the computation of the degree of the Dieudonné determinant of a linear symbolic matrix \(A=A_0+A_1 x_1+\cdots+A_mx_m\), where each \(A_i\) is an \(n\times n\) polynomial matrix over \(\mathbb{K}[t]\) and \(x_1,x_2,\dots,x_m\) are pairwise “noncommutative” variables. This quantity is regarded as a weighted generalization of the noncommutative rank (nc-rank) of a linear symbolic matrix, and its computation is shown to be a generalization of several basic combinatorial optimization problems, such as weighted bipartite matching and weighted linear matroid intersection problems. Based on the work on nc-rank by M. Fortin and C. Reutenauer [Sémin. Lothar. Comb. 52, B52f, 12 p. (2004; Zbl 1069.15011)] and G. Ivanyos et al. [Comput. Complexity 27, No. 4, 561–593 (2018; Zbl 1402.68197)], we develop a framework to compute the degree of the Dieudonné determinant of a linear symbolic matrix. We show that the deg-det computation reduces to a discrete convex optimization problem on the Euclidean building for \(\mathrm{SL}(\mathbb{K}(t)^n)\). To deal with this optimization problem, we introduce a class of discrete convex functions on the building. This class is a natural generalization of L-convex functions in discrete convex analysis (DCA). We develop a DCA-oriented algorithm (steepest descent algorithm) to compute the degree of determinants. Our algorithm works with matrix computation on \(\mathbb{K}\) and uses a subroutine to compute a certificate vector subspace for the nc-rank, where the number of calls of the subroutine is sharply estimated. Our algorithm enhances some classical combinatorial optimization algorithms with new insights, and it is also understood as a variant of the combinatorial relaxation algorithm, which was developed earlier by Murota for computing the degree of the (ordinary) determinant.

MSC:

90C27 Combinatorial optimization
51E24 Buildings and the geometry of diagrams
12E15 Skew fields, division rings
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] S. A. Amitsur, Rational identities and applications to algebra and geometry, J. Algebra, 3 (1966), pp. 304-359. · Zbl 0203.04003
[2] G. Birkhoff, Lattice Theory, American Mathematical Society, New York, 1940; 3rd ed., American Mathematical Society, Providence, RI, 1967. · Zbl 0063.00402
[3] F. Bruhat and J. Tits, Groupes réductifs sur un corps local, Inst. Hautes Études Sci. Publ. Math., 41 (1972), pp. 5-251. · Zbl 0254.14017
[4] P. M. Cohn, Algebra. Vol. 3, 2nd ed., John Wiley & Sons, Chichester, 1991. · Zbl 0719.00002
[5] P. M. Cohn, Skew Fields. Theory of General Division Rings, Cambridge University Press, Cambridge, 1995. · Zbl 0840.16001
[6] W. H. Cunningham, Improved bounds for matroid partition and intersection algorithms, SIAM J. Comput., 15 (1986), pp. 948-957, https://doi.org/10.1137/0215066. · Zbl 0619.68040
[7] H. Derksen and V. Makam, Polynomial degree bounds for matrix semi-invariants, Adv. Math., 310 (2017), pp. 44-63. · Zbl 1361.15033
[8] J. Dieudonné, Les déterminants sur un corps non commutatif, Bull. Soc. Math. France, 71 (1943), pp. 27-45. · Zbl 0028.33904
[9] A. W. M. Dress and W. Wenzel, Valuated matroids: A new look at the greedy algorithm, Appl. Math. Lett., 3 (1990), pp. 33-35. · Zbl 0701.05014
[10] A. W. M. Dress and W. Wenzel, Valuated matroids, Adv. Math., 93 (1992), pp. 214-250. · Zbl 0754.05027
[11] J. Edmonds, Systems of distinct representatives and linear algebra, J. Res. Nat. Bur. Standards Sect. B, 71B (1967), pp. 241-245. · Zbl 0178.03002
[12] M. Fortin and C. Reutenauer, Commutative/non-commutative rank of linear matrices and subspaces of matrices of low rank, Sém. Lothar. Combin., 52 (2004), B52f. · Zbl 1069.15011
[13] A. Frank, A weighted matroid intersection algorithm, J. Algorithms, 2 (1981), pp. 328-336. · Zbl 0484.05025
[14] H. Furue and H. Hirai, On a Weighted Linear Matroid Intersection Algorithm by deg-det Computation, preprint, https://arxiv.org/abs/1908.11529, 2019. · Zbl 1497.68554
[15] A. Garg, L. Gurvits, R. Oliveira, and A. Wigderson, Operator scaling: Theory and applications, Found. Comput. Math., to appear. (First online May 6, 2019.) · Zbl 1432.68617
[16] P. B. Garrett, Building and Classical Groups, Chapman & Hall, London, 1997. · Zbl 0933.20019
[17] K. R. Goodearl and R. B. Warfield, Jr., An Introduction to Noncommutative Noetherian Rings, 2nd ed., Cambridge University Press, Cambridge, 2004. · Zbl 1101.16001
[18] G. Grätzer, Lattice Theory: Foundation, Birkhäuser, Basel, 2011. · Zbl 1233.06001
[19] L. Gurvits, Classical complexity and quantum entanglement, J. Comput. System Sci., 69 (2004), pp. 448-484. · Zbl 1093.81012
[20] M. Hamada and H. Hirai, Maximum Vanishing Subspace Problem, CAT(0)-Space Relaxation, and Block-Triangularization of Partitioned Matrix, preprint, https://arxiv.org/abs/1705.02060, 2017.
[21] H. Hirai, Computing DM-decomposition of a partitioned matrix with rank-1 blocks, Linear Algebra Appl., 547 (2018), pp. 105-123. · Zbl 1390.15040
[22] H. Hirai, Discrete convex functions on graphs and their algorithmic applications, in Combinatorial Optimization and Graph Algorithms, Communications of NII Shonan Meetings, T. Fukunaga and K. Kawarabayashi, eds., Springer, Singapore, 2017, pp. 67-100. · Zbl 1397.90237
[23] H. Hirai, L-convexity on graph structures, J. Oper. Res. Soc. Japan, 61 (2018), pp. 71-109. · Zbl 1391.90475
[24] H. Hirai, Uniform Modular Lattice and Euclidean Building, preprint, https://arxiv.org/abs/1801.00240v1, 2017.
[25] H. Ito, S. Iwata, and K. Murota, Block-triangularizations of partitioned matrices under similarity/equivalence transformations, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 1226-1255, https://doi.org/10.1137/S0895479892235599. · Zbl 0811.15008
[26] G. Ivanyos, M. Karpinski, Y. Qiao, and M. Santha, Generalized Wong sequences and their applications to Edmonds’ problems, J. Comput. System Sci., 81 (2015), pp. 1373-1386. · Zbl 1320.68222
[27] G. Ivanyos, M. Karpinski, and N. Saxena, Deterministic polynomial time algorithms for matrix completion problems, SIAM J. Comput., 39 (2010), pp. 3736-3751, https://doi.org/10.1137/090781231. · Zbl 1209.68269
[28] G. Ivanyos, Y. Qiao, and K. V. Subrahmanyam, Non-commutative Edmonds’ problem and matrix semi-invariants, Comput. Complexity, 26 (2017), pp. 717-763. · Zbl 1421.13002
[29] G. Ivanyos, Y. Qiao, and K. V. Subrahmanyam, Constructive non-commutative rank computation is in deterministic polynomial time, Comput. Complexity, 27 (2018), pp. 561-593. · Zbl 1402.68197
[30] S. Iwata and Y. Kobayashi, A weighted linear matroid parity algorithm, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), Montreal, Canada, 2017, pp. 264-276; also available as Tech. report METR 2017-01, University of Tokyo, 2017. · Zbl 1370.05029
[31] S. Iwata and K. Murota, A minimax theorem and a Dulmage-Mendelsohn type decomposition for a class of generic partitioned matrices, SIAM J. Matrix Anal. Appl., 16 (1995), pp. 719-734, https://doi.org/10.1137/S0895479893255901. · Zbl 0829.15008
[32] S. Iwata, T. Oki, and M. Takamatsu, Index reduction for differential-algebraic equations with mixed matrices, J. ACM, 66 (2019), 35. · Zbl 07165887
[33] S. Iwata and M. Takamatsu, Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation, Algorithmica, 66 (2013), pp. 346-368. · Zbl 1284.65059
[34] T. Kailath, Linear Systems, Prentice-Hall, Englewood Cliffs, NJ, 1980. · Zbl 0454.93001
[35] V. Kabanets and R. Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Comput. Complexity, 13 (2004), pp. 1-46. · Zbl 1089.68042
[36] B. Korte and J. Vygen, Combinatorial Optimization. Theory and Algorithms, 6th ed., Springer, Berlin, 2018. · Zbl 1390.90001
[37] Ü. Kotta, J. Belikov, M. Halás, and A. Leibak, Degree of Dieudonné determinant defines the order of nonlinear system, Internat. J. Control, 92 (2017), pp. 518-527. · Zbl 1414.93095
[38] E. L. Lawler, Matroid intersection algorithms, Math. Program., 9 (1975), pp. 31-56. · Zbl 0315.90039
[39] L. Lovász, On determinants, matchings, and random algorithms, in Fundamentals of Computation Theory (FCT’79), Proceedings of Algebraic, Arithmetic, and Categorical Methods in Computation Theory, L. Budach, ed., Akademie-Verlag, Berlin, 1979, pp. 565-574. · Zbl 0446.68036
[40] L. Lovász, Singular spaces of matrices and their application in combinatorics, Bol. Soc. Brasil. Mat., 20 (1989), pp. 87-99. · Zbl 0757.05035
[41] K. Murota, Computing Puiseux-series solutions to determinantal equations via combinatorial relaxation, SIAM J. Comput., 19 (1990), pp. 1132-1161, https://doi.org/10.1137/0219077. · Zbl 0711.68066
[42] K. Murota, Computing the degree of determinants via combinatorial relaxation, SIAM J. Comput., 24 (1995), pp. 765-796, https://doi.org/10.1137/S0097539791201897. · Zbl 0834.05037
[43] K. Murota, Discrete convex analysis, Math. Programming Ser. A, 83 (1998), pp. 313-371. · Zbl 0920.90103
[44] K. Murota, Matrices and Matroids for Systems Analysis, Springer-Verlag, Berlin, 2000. · Zbl 0948.05001
[45] K. Murota, Discrete Convex Analysis, Discrete Math. Appl. 10, SIAM, Philadelphia, 2003, https://doi.org/10.1137/1.9780898718508. · Zbl 1029.90055
[46] K. Murota and M. Iri, Structural solvability of systems of equations. A mathematical formulation for distinguishing accurate and inaccurate numbers in structural analysis of systems, Japan J. Appl. Math., 2 (1985), pp. 247-271. · Zbl 0598.15003
[47] K. Murota and A. Shioura, Exact bounds for steepest descent algorithms of L-convex function minimization, Oper. Res. Lett., 42 (2014), pp. 361-366. · Zbl 1408.90261
[48] T. Oki, Computing the maximum degree of minors in polynomial matrices over skew fields, in Proceedings of the 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (HJ 2019), Tokyo, pp. 332-343.
[49] T. Soma, Fast deterministic algorithms for matrix completion problems, SIAM J. Discrete Math., 28 (2014), pp. 490-502, https://doi.org/10.1137/130909214. · Zbl 1307.15041
[50] L. Taelman, Dieudonné determinants for skew polynomial rings, J. Algebra Appl., 5 (2006), pp. 89-93. · Zbl 1093.15012
[51] J. Tits, Buildings of Spherical Type and Finite BN-pairs, Lecture Notes in Math. 386, Springer-Verlag, Berlin, 1974. · Zbl 0295.20047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.