{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T16:58:06Z","timestamp":1757609886446,"version":"3.44.0"},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,11,2]],"date-time":"2024-11-02T00:00:00Z","timestamp":1730505600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,11,2]],"date-time":"2024-11-02T00:00:00Z","timestamp":1730505600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP21K19759, JP24K21315","JP20K23323, JP20H05795, JP22K17854, JP24K21315"],"award-info":[{"award-number":["JP21K19759, JP24K21315","JP20K23323, JP20H05795, JP22K17854, JP24K21315"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009023","name":"Precursory Research for Embryonic Science and Technology","doi-asserted-by":"publisher","award":["JPMJPR192A"],"award-info":[{"award-number":["JPMJPR192A"]}],"id":[{"id":"10.13039\/501100009023","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009024","name":"Exploratory Research for Advanced Technology","doi-asserted-by":"publisher","award":["JPMJER1903","JP22K17853","JP19K20212"],"award-info":[{"award-number":["JPMJER1903","JP22K17853","JP19K20212"]}],"id":[{"id":"10.13039\/501100009024","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We address the computation of the degrees of minors of a noncommutative symbolic matrix of form <jats:disp-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$ A[c] :=\\sum _{k=1}^m A_k t^{c_k} x_k, $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>[<\/mml:mo>\n                      <mml:mi>c<\/mml:mi>\n                      <mml:mo>]<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>:<\/mml:mo>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:munderover>\n                      <mml:mo>\u2211<\/mml:mo>\n                      <mml:mrow>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mo>=<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                      <\/mml:mrow>\n                      <mml:mi>m<\/mml:mi>\n                    <\/mml:munderover>\n                    <mml:msub>\n                      <mml:mi>A<\/mml:mi>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:msup>\n                      <mml:mi>t<\/mml:mi>\n                      <mml:msub>\n                        <mml:mi>c<\/mml:mi>\n                        <mml:mi>k<\/mml:mi>\n                      <\/mml:msub>\n                    <\/mml:msup>\n                    <mml:msub>\n                      <mml:mi>x<\/mml:mi>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>,<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:disp-formula>where <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$A_k$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mi>k<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> are matrices over a field <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathbb {K}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>K<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$x_k$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>x<\/mml:mi>\n                    <mml:mi>k<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> are noncommutative variables, <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$c_k$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>c<\/mml:mi>\n                    <mml:mi>k<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> are integer weights, and <jats:italic>t<\/jats:italic> is a commuting variable specifying the degree. This problem extends noncommutative Edmonds\u2019 problem (Ivanyos et al. in Comput Complex 26:717\u2013763, 2017), and can formulate various combinatorial optimization problems. Extending the study by Hirai 2018, and Hirai, Ikeda 2022, we provide novel duality theorems and polyhedral characterization for the maximum degrees of minors of <jats:italic>A<\/jats:italic>[<jats:italic>c<\/jats:italic>] of all sizes, and develop a strongly polynomial-time algorithm for computing them. This algorithm is viewed as a unified algebraization of the classical Hungarian method for bipartite matching and the weight-splitting algorithm for linear matroid intersection. As applications, we provide polynomial-time algorithms for weighted fractional linear matroid matching and for membership of rank-2 Brascamp\u2013Lieb polytopes.<\/jats:p>","DOI":"10.1007\/s10107-024-02158-0","type":"journal-article","created":{"date-parts":[[2024,11,2]],"date-time":"2024-11-02T02:02:22Z","timestamp":1730512942000},"page":"941-984","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Algebraic combinatorial optimization on the degree of determinants of noncommutative symbolic matrices"],"prefix":"10.1007","volume":"213","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4784-5110","authenticated-orcid":false,"given":"Hiroshi","family":"Hirai","sequence":"first","affiliation":[]},{"given":"Yuni","family":"Iwamasa","sequence":"additional","affiliation":[]},{"given":"Taihei","family":"Oki","sequence":"additional","affiliation":[]},{"given":"Tasuku","family":"Soma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,11,2]]},"reference":[{"key":"2158_CR1","doi-asserted-by":"crossref","unstructured":"Allen-Zhu, Z., Garg, A., Li, Y., Oliveira, R., Wigderson, A.: Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 172\u2013181 (2018)","DOI":"10.1145\/3188745.3188942"},{"key":"2158_CR2","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1016\/0021-8693(66)90004-4","volume":"3","author":"SA Amitsur","year":"1966","unstructured":"Amitsur, S.A.: Rational identities and applications to algebra and geometry. J. Algebra 3, 304\u2013359 (1966)","journal-title":"J. Algebra"},{"issue":"2","key":"2158_CR3","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s002220050267","volume":"134","author":"F Barthe","year":"1998","unstructured":"Barthe, F.: On a reverse form of the Brascamp-Lieb inequality. Invent. Math. 134(2), 335\u2013361 (1998)","journal-title":"Invent. Math."},{"key":"2158_CR4","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1007\/s00039-007-0619-6","volume":"17","author":"J Bennett","year":"2008","unstructured":"Bennett, J., Carbery, A., Christ, M., Tao, T.: The Brascamp-Lieb inequalities: finiteness, structure and extremals. Geom. Funct. Anal. 17, 1343\u20131415 (2008)","journal-title":"Geom. Funct. Anal."},{"key":"2158_CR5","unstructured":"Bergman, G.\u00a0M.: Skew fields of noncommutative rational functions, after Amitsur (preliminary version). In: S\u00e9minaire M. P. Sch\u00fctzenberger, A. Lentin et M. Nivat, 1969\/70: Probl\u00e8mes Math\u00e9matiques de la Th\u00e9orie des Automates. Exp. 16 (1970)"},{"key":"2158_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2066-4","volume-title":"Coxeter Matroids","author":"AV Borovik","year":"2003","unstructured":"Borovik, A.V., Gelfand, I.M., White, N.: Coxeter Matroids. Birkh\u00e4user, Boston, MA (2003)"},{"key":"2158_CR7","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0001-8708(76)90184-5","volume":"20","author":"H Brascamp","year":"1976","unstructured":"Brascamp, H., Lieb, E.: Best constants in young\u2019s inequality, its converse, and its generalization to more than three functions. Adv. Math. 20, 151\u2013173 (1976)","journal-title":"Adv. Math."},{"key":"2158_CR8","doi-asserted-by":"crossref","unstructured":"Burgisser, P., Franks, C., Garg, A., Oliveira, R., Walter, M., Wigderson, A.: Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 883\u2013897 (2018)","DOI":"10.1109\/FOCS.2018.00088"},{"key":"2158_CR9","doi-asserted-by":"crossref","unstructured":"B\u00fcrgisser, P., Franks, C., Garg, A., Oliveira, R., Walter, M., Wigderson, A.: Towards a theory of non-commutative optimization: Geodesic 1st and 2nd order methods for moment maps and polytopes. In: Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 845\u2013861 (2019)","DOI":"10.1109\/FOCS.2019.00055"},{"key":"2158_CR10","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0012-365X(00)00219-3","volume":"237","author":"S Chang","year":"2001","unstructured":"Chang, S., Llewellyn, D.C., Vande Vate, J.H.: Matching 2-lattice polyhedra: finding a maximum vector. Discrete Math. 237, 29\u201361 (2001)","journal-title":"Discrete Math."},{"key":"2158_CR11","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0012-365X(00)00220-X","volume":"237","author":"S Chang","year":"2001","unstructured":"Chang, S., Llewellyn, D.C., Vande Vate, J.H.: Two-lattice polyhedra: duality and extreme points. Discrete Math. 237, 63\u201395 (2001)","journal-title":"Discrete Math."},{"key":"2158_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139087193","volume-title":"Skew Fields: Theory of General Division Rings","author":"PM Cohn","year":"1995","unstructured":"Cohn, P.M.: Skew Fields: Theory of General Division Rings. Cambridge University Press, Cambridge (1995)"},{"key":"2158_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-0039-3","volume-title":"Further Algebra and Applications","author":"PM Cohn","year":"2003","unstructured":"Cohn, P.M.: Further Algebra and Applications. Springer, London (2003)"},{"key":"2158_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511542794","volume-title":"Free Ideal Rings and Localization in General Rings","author":"PM Cohn","year":"2006","unstructured":"Cohn, P.M.: Free Ideal Rings and Localization in General Rings. Cambridge University Press, Cambridge (2006)"},{"key":"2158_CR15","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.aim.2017.01.018","volume":"310","author":"H Derksen","year":"2017","unstructured":"Derksen, H., Makam, V.: Polynomial degree bounds for matrix semi-invariants. Adv. Math. 310, 44\u201363 (2017)","journal-title":"Adv. Math."},{"key":"2158_CR16","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1080\/03081087.2017.1337058","volume":"66","author":"H Derksen","year":"2018","unstructured":"Derksen, H., Makam, V.: On non-commutative rank and tensor rank. Linear Multilinear Algebra 66, 1069\u20131084 (2018)","journal-title":"Linear Multilinear Algebra"},{"key":"2158_CR17","doi-asserted-by":"publisher","first-page":"27","DOI":"10.24033\/bsmf.1345","volume":"71","author":"J Dieudonn\u00e9","year":"1943","unstructured":"Dieudonn\u00e9, J.: Les d\u00e9terminants sur un corps non commutatif. Bulletin de la Soci\u00e9t\u00e9 Math\u00e9matique de France 71, 27\u201345 (1943)","journal-title":"Bulletin de la Soci\u00e9t\u00e9 Math\u00e9matique de France"},{"key":"2158_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-7934-7","volume-title":"Polynomial Identity Rings","author":"V Drensky","year":"2004","unstructured":"Drensky, V., Formanek, E.: Polynomial Identity Rings. Birkh\u00e4user Verlag, Basel (2004)"},{"key":"2158_CR19","doi-asserted-by":"publisher","first-page":"241","DOI":"10.6028\/jres.071B.033","volume":"71B","author":"J Edmonds","year":"1967","unstructured":"Edmonds, J.: Systems of distinct representatives and linear algebra. J. Res. Natl. Bureau Stand. 71B, 241\u2013245 (1967)","journal-title":"J. Res. Natl. Bureau Stand."},{"key":"2158_CR20","first-page":"B52f","volume":"52","author":"M Fortin","year":"2004","unstructured":"Fortin, M., Reutenauer, C.: Commutative\/non-commutative rank of linear matrices and subspaces of matrices of low rank. S\u00e9minaire Lotharingien de Combinatoire 52, B52f (2004)","journal-title":"S\u00e9minaire Lotharingien de Combinatoire"},{"key":"2158_CR21","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1016\/0196-6774(81)90032-8","volume":"2","author":"A Frank","year":"1981","unstructured":"Frank, A.: A weighted matroid intersection algorithm. J. Algorithms 2, 328\u2013336 (1981)","journal-title":"J. Algorithms"},{"key":"2158_CR22","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7, 49\u201365 (1987)","journal-title":"Combinatorica"},{"key":"2158_CR23","doi-asserted-by":"crossref","unstructured":"Franks, C., Soma, T., Goemans, M.\u00a0X.: Shrunk subspaces via operator sinkhorn iteration. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1655\u20131668. SIAM (2023)","DOI":"10.1137\/1.9781611977554.ch62"},{"key":"2158_CR24","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1007\/s13160-020-00413-3","volume":"37","author":"H Furue","year":"2020","unstructured":"Furue, H., Hirai, H.: On a weighted linear matroid intersection algorithm by deg-det computation. Japan J. Ind. Appl. Math. 37, 677\u2013696 (2020)","journal-title":"Japan J. Ind. Appl. Math."},{"key":"2158_CR25","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/s00039-018-0434-2","volume":"28","author":"A Garg","year":"2018","unstructured":"Garg, A., Gurvits, L., Oliveira, R., Wigderson, A.: Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. Geometric Funct. Anal. 28, 100\u2013145 (2018)","journal-title":"Geometric Funct. Anal."},{"key":"2158_CR26","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s10208-019-09417-z","volume":"20","author":"A Garg","year":"2020","unstructured":"Garg, A., Gurvits, L., Oliveira, R., Wigderson, A.: Operator scaling: theory and applications. Found. Comput. Math. 20, 223\u2013290 (2020)","journal-title":"Found. Comput. Math."},{"key":"2158_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-011-5340-9","volume-title":"Buildings and Classical Groups","author":"P Garrett","year":"1997","unstructured":"Garrett, P.: Buildings and Classical Groups. Chapman & Hall, London (1997)"},{"key":"2158_CR28","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s004930070031","volume":"20","author":"JF Geelen","year":"2000","unstructured":"Geelen, J.F.: An algebraic matching algorithm. Combinatorica 20, 61\u201370 (2000)","journal-title":"Combinatorica"},{"key":"2158_CR29","first-page":"63","volume":"1185","author":"JF Geelen","year":"2001","unstructured":"Geelen, J.F.: An algebraic approach to matching problems. S\u016brikaisekikenky\u016bsho Koky\u016broku 1185, 63\u201371 (2001)","journal-title":"S\u016brikaisekikenky\u016bsho Koky\u016broku"},{"key":"2158_CR30","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1016\/j.jctb.2013.05.004","volume":"103","author":"D Gijswijt","year":"2013","unstructured":"Gijswijt, D., Pap, G.: An algorithm for weighted fractional matroid matching. J. Combinat. Theory Ser. B 103, 509\u2013520 (2013)","journal-title":"J. Combinat. Theory Ser. B"},{"key":"2158_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tchel","year":"1993","unstructured":"Gr\u00f6tchel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin (1993)"},{"key":"2158_CR32","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1137\/20M138836X","volume":"5","author":"M Hamada","year":"2021","unstructured":"Hamada, M., Hirai, H.: Computing the nc-rank via discrete convex optimization on CAT(0) spaces. SIAM J. Appl. Geometry Algebra 5, 455\u2013478 (2021)","journal-title":"SIAM J. Appl. Geometry Algebra"},{"key":"2158_CR33","unstructured":"Hirai, H.: Convex analysis on Hadamard spaces and scaling problems. Foundations of Computational Mathematics. to appear"},{"key":"2158_CR34","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1137\/18M1190823","volume":"3","author":"H Hirai","year":"2019","unstructured":"Hirai, H.: Computing the degree of determinants via discrete convex optimization on Euclidean buildings. SIAM J. Appl. Geometry Algebra 3, 523\u2013557 (2019)","journal-title":"SIAM J. Appl. Geometry Algebra"},{"key":"2158_CR35","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1007\/s00037-022-00227-4","volume":"31","author":"H Hirai","year":"2022","unstructured":"Hirai, H., Ikeda, M.: A cost-scaling algorithm for computing the degree of determinants. Comput. Complex. 31, 10 (2022)","journal-title":"Comput. Complex."},{"key":"2158_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-021-01676-5","volume":"195","author":"H Hirai","year":"2022","unstructured":"Hirai, H., Iwamasa, Y.: A combinatorial algorithm for computing the rank of a generic partitioned matrix with 2$$\\times $$2 submatrices. Math. Program. Ser. A 195, 1\u201337 (2022)","journal-title":"Math. Program. Ser. A"},{"key":"2158_CR37","doi-asserted-by":"publisher","first-page":"357","DOI":"10.4086\/toc.2015.v011a014","volume":"11","author":"P Hrube\u0161","year":"2015","unstructured":"Hrube\u0161, P., Wigderson, A.: Non-commutative arithmetic circuits with division. Theory Comput. 11, 357\u2013393 (2015)","journal-title":"Theory Comput."},{"key":"2158_CR38","doi-asserted-by":"publisher","first-page":"1226","DOI":"10.1137\/S0895479892235599","volume":"15","author":"H Ito","year":"1994","unstructured":"Ito, H., Iwata, S., Murota, K.: Block-triangularizations of partitioned matrices under similarity\/equivalence transformations. SIAM J. Matrix Anal. Appl. 15, 1226\u20131255 (1994)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"2158_CR39","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s00037-016-0143-x","volume":"26","author":"G Ivanyos","year":"2017","unstructured":"Ivanyos, G., Qiao, Y., Subrahmanyam, K.V.: Non-commutative Edmonds\u2019 problem and matrix semi-invariants. Comput. Complex. 26, 717\u2013763 (2017)","journal-title":"Comput. Complex."},{"key":"2158_CR40","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/s00037-018-0165-7","volume":"27","author":"G Ivanyos","year":"2018","unstructured":"Ivanyos, G., Qiao, Y., Subrahmanyam, K.V.: Constructive noncommutative rank computation in deterministic polynomial time over fields of arbitrary characteristics. Comput. Complex. 27, 561\u2013593 (2018)","journal-title":"Comput. Complex."},{"key":"2158_CR41","doi-asserted-by":"crossref","unstructured":"Iwamasa, Y.: A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with 2$$\\times $$ 2 submatrices. Mathematical Programming, Series A, pp. 1\u201353 (2023)","DOI":"10.1007\/s10107-023-01949-1"},{"key":"2158_CR42","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1137\/17M1141709","volume":"51","author":"S Iwata","year":"2022","unstructured":"Iwata, S., Kobayashi, Y.: A weighted linear matroid parity algorithm. SIAM J. Comput. 51, 238\u2013280 (2022)","journal-title":"SIAM J. Comput."},{"key":"2158_CR43","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1137\/S0895479893255901","volume":"16","author":"S Iwata","year":"1995","unstructured":"Iwata, S., Murota, K.: A minimax theorem and a Dulmage-Mendelsohn type decomposition for a class of generic partitioned matrices. SIAM J. Matrix Anal. Appl. 16, 719\u2013734 (1995)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"2158_CR44","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1137\/0917064","volume":"17","author":"S Iwata","year":"1996","unstructured":"Iwata, S., Murota, K., Sakuta, I.: Primal-dual combinatorial relaxation algorithms for the maximum degree of subdeterminants. SIAM J. Sci. Comput. 17, 993\u20131012 (1996)","journal-title":"SIAM J. Sci. Comput."},{"key":"2158_CR45","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V Kabanets","year":"2004","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex. 13, 1\u201346 (2004)","journal-title":"Comput. Complex."},{"issue":"1\u20132","key":"2158_CR46","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s11045-010-0122-3","volume":"23","author":"DS Kaliuzhnyi-Verbovetskyi","year":"2012","unstructured":"Kaliuzhnyi-Verbovetskyi, D.S., Vinnikov, V.: Noncommutative rational functions, their difference-differential calculus and realizations. Multidimen. Syst. Signal Process. 23(1\u20132), 49\u201377 (2012)","journal-title":"Multidimen. Syst. Signal Process."},{"key":"2158_CR47","unstructured":"Li, Y., Qiao, Y., Wigderson, A., Wigderson, Y., Zhang, C.: On linear-algebraic notions of expansion. Theory of Computing. to appear"},{"issue":"2","key":"2158_CR48","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/s11856-023-2515-7","volume":"256","author":"Y Li","year":"2023","unstructured":"Li, Y., Qiao, Y., Wigderson, A., Wigderson, Y., Zhang, C.: Connections between graphs and matrix spaces. Israel J. Math. 256(2), 513\u2013580 (2023)","journal-title":"Israel J. Math."},{"key":"2158_CR49","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/BF01233426","volume":"102","author":"E Lieb","year":"1990","unstructured":"Lieb, E.: Gaussian kernels have only Gaussian maximizers. Invent. Math. 102, 179\u2013208 (1990)","journal-title":"Invent. Math."},{"key":"2158_CR50","unstructured":"Lov\u00e1sz, L.: On determinants, matchings, and random algorithms. In: Fundamentals of Computation Theory FCT\u201979, pp. 565\u2013574 (1979)"},{"key":"2158_CR51","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/BF02585470","volume":"20","author":"L Lov\u00e1sz","year":"1989","unstructured":"Lov\u00e1sz, L.: Singular spaces of matrices and their application in combinatorics. Boletim da Sociedade Brasileira de Matem\u00e1tica 20, 87\u201399 (1989)","journal-title":"Boletim da Sociedade Brasileira de Matem\u00e1tica"},{"key":"2158_CR52","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1137\/S0097539791201897","volume":"24","author":"K Murota","year":"1995","unstructured":"Murota, K.: Computing the degree of determinants via combinatorial relaxation. SIAM J. Comput. 24, 765\u2013796 (1995)","journal-title":"SIAM J. Comput."},{"key":"2158_CR53","volume-title":"Matrices and Matroids for Systems Analysis","author":"K Murota","year":"2000","unstructured":"Murota, K.: Matrices and Matroids for Systems Analysis. Springer-Verlag, Berlin (2000)"},{"key":"2158_CR54","doi-asserted-by":"crossref","unstructured":"Murota, K.: Discrete Convex Analysis. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2003)","DOI":"10.1137\/1.9780898718508"},{"key":"2158_CR55","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/j.jsc.2022.10.010","volume":"116","author":"T Oki","year":"2023","unstructured":"Oki, T.: Computing valuations of the Dieudonn\u00e9 determinants. J. Symbol. Comput. 116, 284\u2013323 (2023)","journal-title":"J. Symbol. Comput."},{"key":"2158_CR56","doi-asserted-by":"crossref","unstructured":"Oki, T., Soma, T.: Algebraic algorithms for fractional linear matroid parity via non-commutative rank. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 4188\u20134204. SIAM (2023)","DOI":"10.1137\/1.9781611977554.ch161"},{"key":"2158_CR57","doi-asserted-by":"crossref","unstructured":"Raz, O.\u00a0E., Wigderson, A.: Subspace arrangements, graph rigidity and derandomization through submodular optimization. In: Building Bridges II\u2014Mathematics of L\u00e1szl\u00f3 Lov\u00e1sz, pp. 377\u2013415. Springer, Berlin (2019)","DOI":"10.1007\/978-3-662-59204-5_12"},{"key":"2158_CR58","volume-title":"Polynomial Identities in Ring Theory","author":"LH Rowen","year":"1980","unstructured":"Rowen, L.H.: Polynomial Identities in Ring Theory. Academic Press, New York (1980)"},{"key":"2158_CR59","volume-title":"Combinatorial Optimization, Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization, Polyhedra and Efficiency. Springer-Verlag, Berlin (2003)"},{"key":"2158_CR60","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0095-8956(92)90037-X","volume":"55","author":"JH Vande Vate","year":"1992","unstructured":"Vande Vate, J.H.: Fractional matroid matchings. J. Combinat. Theory Ser. B 55, 133\u2013145 (1992)","journal-title":"J. Combinat. Theory Ser. B"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02158-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02158-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02158-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T12:04:06Z","timestamp":1756901046000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02158-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,2]]},"references-count":60,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["2158"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02158-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2024,11,2]]},"assertion":[{"value":"15 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 October 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}