Connections between graphs and matrix spaces. (English) Zbl 1522.05281
Summary: Given a bipartite graph \(G\), the graphical matrix space \(\mathcal{S}_G\) consists of matrices whose non-zero entries can only be at those positions corresponding to edges in \(G\). W. T. Tutte [J. Lond. Math. Soc. 22, 107–111 (1947; Zbl 0029.23301)], J. Edmonds [J. Res. Natl. Bur. Stand., Sect. B 71, 241–245 (1967; Zbl 0178.03002)] and L. Lovász [in: Fundamentals of computation theory – FCT ’79. Proceedings of the conference on algebraic, arithmetic, and categorial methods in computation theory held in Berlin/Wendisch-Rietz (GDR) September 17–21, 1979. Berlin: Akademie-Verlag. 565–574 (1979; Zbl 0446.68036)] observed connections between perfect matchings in \(G\) and full-rank matrices in \(\mathcal{S}_G\). J. Dieudonné [Arch. Math. 1, 282–287 (1949; Zbl 0032.10601)] proved a tight upper bound on the dimensions of those matrix spaces containing only singular matrices. The starting point of this paper is a simultaneous generalization of these two classical results: we show that the largest dimension over subspaces of \(\mathcal{S}_G\) containing only singular matrices is equal to the maximum size over subgraphs of \(G\) without perfect matchings, based on R. Meshulam’s proof of Dieudonné’s result [Q. J. Math., Oxf. II. Ser. 36, 225–229 (1985; Zbl 0565.15006)].
Starting from this result, we go on to establish more connections between properties of graphs and matrix spaces. For example, we establish connections between acyclicity and nilpotency, between strong connectivity and irreducibility, and between isomorphism and conjugacy/congruence. For each connection, we study three types of correspondences, namely the basic correspondence, the inherited correspondence (for subgraphs and subspaces), and the induced correspondence (for induced subgraphs and restrictions). Some correspondences lead to intriguing generalizations of classical results, such as Dieudonné’s result mentioned above, and a celebrated theorem of M. Gerstenhaber [Am. J. Math. 80, 614–622 (1958; Zbl 0085.26204)] regarding the largest dimension of nil matrix spaces.
Finally, we show some implications of our results to quantum information and present open problems in computational complexity motivated by these results.
Starting from this result, we go on to establish more connections between properties of graphs and matrix spaces. For example, we establish connections between acyclicity and nilpotency, between strong connectivity and irreducibility, and between isomorphism and conjugacy/congruence. For each connection, we study three types of correspondences, namely the basic correspondence, the inherited correspondence (for subgraphs and subspaces), and the induced correspondence (for induced subgraphs and restrictions). Some correspondences lead to intriguing generalizations of classical results, such as Dieudonné’s result mentioned above, and a celebrated theorem of M. Gerstenhaber [Am. J. Math. 80, 614–622 (1958; Zbl 0085.26204)] regarding the largest dimension of nil matrix spaces.
Finally, we show some implications of our results to quantum information and present open problems in computational complexity motivated by these results.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 15A30 | Algebraic systems of matrices |
| 68Q25 | Analysis of algorithms and problem complexity |
| 81P45 | Quantum information, communication, networks (quantum-theoretic aspects) |
Citations:
Zbl 0029.23301; Zbl 0178.03002; Zbl 0446.68036; Zbl 0032.10601; Zbl 0565.15006; Zbl 0085.26204References:
| [1] | Adams, J. F., Vector fields on spheres, Annals of Mathematics, 75, 603-632 (1962) · Zbl 0112.38102 · doi:10.2307/1970213 |
| [2] | Albert, A. A., A theory of power-associative commutative algebras, Transactions of the American Mathematical Society, 69, 503-527 (1950) · Zbl 0039.26501 · doi:10.1090/S0002-9947-1950-0038959-X |
| [3] | Adams, J. F.; Lax, P. D.; Phillips, R. S., On matrices whose real linear combinations are nonsingular, Proceedings of the American Mathematical Society, 16, 318-322 (1965) · Zbl 0168.02404 |
| [4] | Atkinson, M. D., Spaces of matrices with several zero eigenvalues, Bulletin of the London Mathematical Society, 12, 89-95 (1980) · Zbl 0404.15004 · doi:10.1112/blms/12.2.89 |
| [5] | Baer, R., Groups with abelian central quotient group, Transactions of the American Mathematical Society, 44, 357-386 (1938) · Zbl 0020.00802 · doi:10.1090/S0002-9947-1938-1501972-1 |
| [6] | Ben-Aroya, A.; Schwartz, O.; Ta-Shma, A., Quantum expanders: Motivation and construction, Theory of Computing, 6, 47-79 (2010) · Zbl 1213.81052 · doi:10.4086/toc.2010.v006a003 |
| [7] | T. Bannink, J. Briët, F. Labib and H. Maassen, Quasirandom quantum channels, Quantum 4 (2020), Article no. 298. |
| [8] | Bei, X.; Chen, S.; Guan, J.; Qiao, Y.; Sun, X., From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: Another bridge between graphs and alternating matrix spaces, SIAM Journal on Computing, 50, 924-971 (2021) · Zbl 1517.05094 · doi:10.1137/19M1299128 |
| [9] | Berkowitz, S. J., On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, 18, 147-150 (1984) · Zbl 0541.68019 · doi:10.1016/0020-0190(84)90018-8 |
| [10] | Buss, J. F.; Frandsen, G. S.; Shallit, J. O., The computational complexity of some problems of linear algebra, Journal of Computer and Systems Sciences, 58, 572-596 (1999) · Zbl 0941.68059 · doi:10.1006/jcss.1998.1608 |
| [11] | Bang-Jensen, J.; Gutin, G. Z., Digraphs (2008), London: Springer, London · Zbl 1001.05002 |
| [12] | Bourgain, J., Expanders and dimensional expansion, Comptes Rendus Mathématique. Académie des Sciences. Paris, 347, 357-362 (2009) · Zbl 1160.22006 · doi:10.1016/j.crma.2009.02.009 |
| [13] | Brachter, J.; Schweitzer, P., On the Weisfeiler-Leman dimension of finite groups, Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 287-300 (2020), New York: ACM, New York · Zbl 1498.20002 · doi:10.1145/3373718.3394786 |
| [14] | Bourgain, J.; Yehudayoff, A., Expansion in · Zbl 1268.05103 · doi:10.1007/s00039-012-0200-9 |
| [15] | Chávez-Domínguez, J. A.; Swift, A. T., Connectivity for quantum graphs, Linear Algebra and its Applications, 608, 37-53 (2021) · Zbl 1486.05163 · doi:10.1016/j.laa.2020.08.020 |
| [16] | Cohn, P. M., The word problem for free fields: A correction and an addendum, Journal of Symbolic Logic, 40, 69-74 (1975) · Zbl 0298.02044 · doi:10.2307/2272273 |
| [17] | Dieudonné, J., Sur une généralisation du groupe orthogonal à quatre variables, Archiv der Mathematik, 1, 282-287 (1948) · Zbl 0032.10601 · doi:10.1007/BF02038756 |
| [18] | Diestel, R., Graph Theory (2017), Berlin: Springer, Berlin · Zbl 1375.05002 · doi:10.1007/978-3-662-53622-3 |
| [19] | Dvir, Z.; Shpilka, A., Towards dimension expanders over finite fields, Combinatorica, 31, 305-320 (2009) · Zbl 1265.05595 · doi:10.1007/s00493-011-2540-8 |
| [20] | de Seguins Pazzis, C., On Gerstenhaber’s theorem for spaces of nilpotent matrices over a skew field, Linear Algebra and its Applications, 438, 4426-4438 (2013) · Zbl 1305.15006 · doi:10.1016/j.laa.2013.01.035 |
| [21] | Duan, R.; Severini, S.; Winter, A., Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number, IEEE Transactions on Information Theory, 59, 1164-1174 (2013) · Zbl 1364.81059 · doi:10.1109/TIT.2012.2221677 |
| [22] | Dvir, Z.; Wigderson, A., Monotone expanders: Constructions and applications, Theory of Computing, 6, 291-308 (2010) · Zbl 1213.68440 · doi:10.4086/toc.2010.v006a012 |
| [23] | Edmonds, J., Systems of distinct representatives and linear algebra, Journal of Research of the National Bureau of Standards. Section B. Mathematics and Mathematical Physics, 71B, 241-245 (1967) · Zbl 0178.03002 · doi:10.6028/jres.071B.033 |
| [24] | Eisenbud, D.; Harris, J., Vector spaces of matrices of low rank, Advances in Mathematics, 70, 135-155 (1988) · Zbl 0657.15013 · doi:10.1016/0001-8708(88)90054-0 |
| [25] | Evans, D. E.; Høegh-Krohn, R., Spectral properties of positive maps on C*-algebras, Journal of the London Mathematical Society, 2, 345-355 (1978) · Zbl 0384.46042 · doi:10.1112/jlms/s2-17.2.345 |
| [26] | Futorny, V.; Grochow, J. A.; Sergeichuk, V. V., Wildness for tensors, Linear Algebra and its Applications, 566, 212-244 (2019) · Zbl 1447.16011 · doi:10.1016/j.laa.2018.12.022 |
| [27] | Fenner, S.; Gurjar, R.; Thierauf, T., Bipartite perfect matching is in Quasi-NC, SIAM Journal on Computing, 50, 218-235 (2021) · Zbl 1464.68126 · doi:10.1137/16M1097870 |
| [28] | Flanders, H., On spaces of linear transformations with bounded rank, Journal of the London Mathematical Society, 1, 10-16 (1962) · Zbl 0101.25403 · doi:10.1112/jlms/s1-37.1.10 |
| [29] | F. G. Frobenius, Über die Darstellung der endlichen Gruppen durch lineare substitutionen, Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften zu Berlin (1897), 944-1015. · JFM 28.0130.01 |
| [30] | Forbes, M. A.; Shpilka, A., Explicit Noether normalization for simultaneous conjugation via polynomial identity testing, Approximation, Randomization, and Combinatorial Optimization, 527-542 (2013), Heidelberg: Springer, Heidelberg · Zbl 1407.68535 · doi:10.1007/978-3-642-40328-6_37 |
| [31] | Gerstenhaber, M., On nilalgebras and linear varieties of nilpotent matrices, I, American Journal of Mathematics, 80, 614-622 (1958) · Zbl 0085.26204 · doi:10.2307/2372773 |
| [32] | Garg, A.; Gurvits, L.; Oliveira, R. M.; Wigderson, A., Operator scaling: Theory and applications, Foundations of Computational Mathematics, 20, 223-290 (2020) · Zbl 1432.68617 · doi:10.1007/s10208-019-09417-z |
| [33] | Gurvits, L., Classical complexity and quantum entanglement, Journal of Computer and Systems Sciences, 69, 448-484 (2004) · Zbl 1093.81012 · doi:10.1016/j.jcss.2004.06.003 |
| [34] | Hall, P., On representatives of subsets, Journal of the London Mathematical Society, 1, 26-30 (1935) · JFM 61.0067.01 · doi:10.1112/jlms/s1-10.37.26 |
| [35] | Harrow, A. W., Quantum expanders from any classical Cayley graph expander, Quantum Information & Computation, 8, 715-721 (2008) · Zbl 1236.81067 · doi:10.26421/QIC8.8-9-2 |
| [36] | M. B. Hastings, Random unitaries give quantum expanders, Physical Review. A 76 (2007), Article no. 032315. |
| [37] | Hamada, M.; Hirai, H., Computing the nc-rank via discrete convex optimization on CAT (0) spaces, SIAM Journal on Applied Algebra and Geometry, 5, 455-478 (2021) · Zbl 1528.68422 · doi:10.1137/20M138836X |
| [38] | Horn, R. A.; Johnson, C. R., Matrix Analysis (1985), Cambridge: Cambridge University Press, Cambridge · Zbl 0576.15001 · doi:10.1017/CBO9780511810817 |
| [39] | X. He and Y. Qiao, On the Baer-Lovász-Tutte construction of groups from graphs: Isomorphism types and homomorphism notions, European Journal of Combinatorics 98 (2021), Article no. 103404. · Zbl 1471.05120 |
| [40] | Ivanyos, G.; Karpinski, M.; Qiao, Y.; Santha, M., Generalized Wong sequences and their applications to Edmonds’ problems, Journal of Computer and Systems Sciences, 81, 1373-1386 (2015) · Zbl 1320.68222 · doi:10.1016/j.jcss.2015.04.006 |
| [41] | Ivanyos, G.; Karpinski, M.; Saxena, N., Deterministic polynomial time algorithms for matrix completion problems, SIAM Journal on Computing, 39, 3736-3751 (2010) · Zbl 1209.68269 · doi:10.1137/090781231 |
| [42] | Ivanyos, G.; Qiao, Y.; Subrahmanyam, K. V., Non-commutative Edmonds’ problem and matrix semi-invariants, Computational Complexity, 26, 717-763 (2017) · Zbl 1421.13002 · doi:10.1007/s00037-016-0143-x |
| [43] | Ivanyos, G.; Qiao, Y.; Subrahmanyam, K. V., Constructive non-commutative rank computation is in deterministic polynomial time, Computational Complexity, 27, 561-593 (2018) · Zbl 1402.68197 · doi:10.1007/s00037-018-0165-7 |
| [44] | Karp, R. M., Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, York-town Heights, NY, 1972), 85-103 (1972), New York: Pleanum, New York · Zbl 1467.68065 |
| [45] | Kabanets, V.; Impagliazzo, R., Derandomizing polynomial identity tests means proving circuit lower bounds, Computational Complexity, 13, 1-46 (2004) · Zbl 1089.68042 · doi:10.1007/s00037-004-0182-6 |
| [46] | Karp, R. M.; Upfal, E.; Wigderson, A., Constructing a perfect matching is in random NC, Combinatorica, 6, 35-48 (1986) · Zbl 0646.05051 · doi:10.1007/BF02579407 |
| [47] | Lang, S., Algebra (2002), New York: Springer, New York · Zbl 0984.00001 · doi:10.1007/978-1-4613-0041-0 |
| [48] | Linial, N.; Lováasz, L.; Wigderson, A., Rubber bands, convex embeddings and graph connectivity, Combinatorica, 8, 91-102 (1988) · Zbl 0674.05046 · doi:10.1007/BF02122557 |
| [49] | Lovaász, L., On determinants, matchings, and random algorithms, Fundamentals of Computation Theory, 565-574 (1979), Berlin: Akademie, Berlin · Zbl 0446.68036 |
| [50] | Lovaász, L., Singular spaces of matrices and their application in combinatorics, Boletim da Sociedade Brasileira de Matemáatica, 20, 87-99 (1989) · Zbl 0757.05035 · doi:10.1007/BF02585470 |
| [51] | Li, Y.; Qiao, Y., Linear algebraic analogues of the graph isomorphism problem and the Erdős-Renyi model, 58th IEEE Annual Symposium on Foundations of Computer Science—FOCS 2017, 463-474 (2017), Los Alamitos, CA: IEEE Computer Society, Los Alamitos, CA · doi:10.1109/FOCS.2017.49 |
| [52] | Li, Y.; Qiao, Y., Group-theoretic generalisations of vertex and edge connectivities, Proceedings of the American Mathematical Society, 148, 4679-4693 (2020) · Zbl 1506.20038 · doi:10.1090/proc/15184 |
| [53] | Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson and C. Zhang, On linear-algebraic notions of expansion, https://arxiv.org/abs/2212.13154. |
| [54] | Lubotzky, A.; Zelmanov, E., Dimension expanders, Journal of Algebra, 319, 730-738 (2008) · Zbl 1154.15002 · doi:10.1016/j.jalgebra.2005.12.033 |
| [55] | Meshulam, R., On the maximal rank in a subspace of matrices, Quarterly Journal of Mathematics, 36, 225-229 (1985) · Zbl 0565.15006 · doi:10.1093/qmath/36.2.225 |
| [56] | MacDonald, G. W.; MacDougall, J. A.; Sweet, L. G., On the dimension of linear spaces of nilpotent matrices, Linear Algebra and its Applications, 436, 2210-2230 (2012) · Zbl 1236.15038 · doi:10.1016/j.laa.2011.10.028 |
| [57] | Mathes, B.; Omladič, M.; Radjavi, H., Linear spaces of nilpotent matrices, Linear Algebra and its Applications, 149, 215-225 (1991) · Zbl 0722.15016 · doi:10.1016/0024-3795(91)90335-T |
| [58] | Mulmuley, K.; Vazirani, U. V.; Vazirani, V. V., Matching is as easy as matrix inversion, Combinatorica, 7, 105-113 (1987) · Zbl 0632.68041 · doi:10.1007/BF02579206 |
| [59] | Makam, V.; Wigderson, A., Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties), Journal für die Reine und Angewandte Mathematik, 780, 79-131 (2021) · Zbl 1476.14081 · doi:10.1515/crelle-2021-0044 |
| [60] | Ortiz, C. M.; Paulsen, V. I., Lovász theta type norms and operator systems, Linear Algebra and its Applications, 477, 128-147 (2015) · Zbl 1327.46053 · doi:10.1016/j.laa.2015.03.022 |
| [61] | Pisier, G., Quantum expanders and geometry of operator spaces, Journal of the European Mathematical Society, 16, 1183-1219 (2014) · Zbl 1307.46045 · doi:10.4171/JEMS/458 |
| [62] | Y. Qiao, Turán and Ramsey problems for alternating multilinear maps, https://arxiv.org/abs/2007.12820. |
| [63] | Y. Qiao, Enumerating alternating matrix spaces over finite fields with explicit coordinates, Discrete Mathematics 344 (2021), Article no. 112580. · Zbl 1485.05079 |
| [64] | Rossmann, T., Enumerating conjugacy classes of graphical groups over finite fields, Bulletin of the London Mathematical Society, 54, 1923-1943 (2022) · Zbl 1530.20087 · doi:10.1112/blms.12665 |
| [65] | T. Rossmann and C. Voll, Groups, graphs, and hypergraphs: Average sizes of kernels of generic matrices with support constraints, Memoirs of the American Mathematical Society, to appear. |
| [66] | Raz, O. E.; Wigderson, A., Subspace arrangements, graph rigidity and derandomization through submodular optimization, Building Bridges, 377-415 (2019), Berlin: Springer, Berlin · Zbl 1452.68089 |
| [67] | Schwartz, J. T., Fast probabilistic algorithms for verification of polynomial identities, Journal of the Association for Computing Machinery, 27, 701-717 (1980) · Zbl 0452.68050 · doi:10.1145/322217.322225 |
| [68] | Serežkin, V. N., On linear transformations preserving nilpotency, Izvestiya Akademii Nauk BSSR. Seriya Fiziko-Matematicheskikh Nauk, 6, 46-50 (1985) · Zbl 0593.15009 |
| [69] | Shannon, C. E., The zero error capacity of a noisy channel, Institute of Radio Engineers Transactions on Information Theory, IT-2, 8-19 (1956) · doi:10.1109/TIT.1956.1056798 |
| [70] | Svensson, O.; Tarnawski, J., The matching problem in general graphs is in quasi-NC, 58th IEEE Annual Symposium on Foundations of Computer Science-FOCS 2017, 696-707 (2017), Los Alamitos, CA: IEEE Computer Society, Los Alamitos, CA · doi:10.1109/FOCS.2017.70 |
| [71] | Shpilka, A.; Yehudayoff, A., Arithmetic circuits: a survey of recent results and open questions, Foundations and Trends in Theoretical Computer Science, 5, 207-388 (2009) · Zbl 1205.68175 · doi:10.1561/0400000039 |
| [72] | Tutte, W. T., The factorization of linear graphs, Journal of the London Mathematical Society, 22, 107-111 (1947) · Zbl 0029.23301 · doi:10.1112/jlms/s1-22.2.107 |
| [73] | Valiant, L. G., Completeness classes in algebra, Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing (Atlanta, Ga., 1979), 249-261 (1979), New York: ACM, New York |
| [74] | Vanegas, E. O Q.; Fernandez, J. C G., Nilpotent linear spaces and Albert’s problem, Linear Algebra and its Applications, 518, 57-78 (2017) · Zbl 1400.17002 · doi:10.1016/j.laa.2016.12.026 |
| [75] | Weaver, N., Quantum graphs as quantum relations, Journal of Geometric Analysis, 31, 9090-9112 (2021) · Zbl 1490.81046 · doi:10.1007/s12220-020-00578-w |
| [76] | M. M. Wolf, Quantum channels & operations: Guided tour, Lecture Notes, https://mediatum.ub.tum.de/doc/1701036/document.pdf. |
| [77] | Zhang, F., The Schur Complement and Its Applications (2005), New York: Springer, New York · Zbl 1075.15002 · doi:10.1007/b105056 |
| [78] | Zippel, R., Probabilistic algorithms for sparse polynomials, Symbolic and Algebraic Computation, (EUROSAM’ 79, An International Symposiumon Symbolic and Algebraic Computation, Marseille, France, 1979), 216-226 (1979), Berlin-New York: Springer, Berlin-New York · Zbl 0418.68040 |
| [79] | Zenklusen, R.; Ries, B.; Picouleau, C.; de Werra, D.; Costa, M-C; Bentz, C., Blockers and transversals, Discrete Mathematics, 309, 4306-4314 (2009) · Zbl 1204.05085 · doi:10.1016/j.disc.2009.01.006 |
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.
