Connections between graphs and matrix spaces

DOI10.1007/S11856-023-2515-7zbMATH Open1522.05281arXiv2206.04815OpenAlexW4387382674MaRDI QIDQ6074039FDOQ6074039

Authors: Yinan Li, Youming Qiao, A. Wigderson, Yuval Wigderson, Chuanqi Zhang 

Publication date: 12 October 2023

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Abstract: 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$. Tutte (J. London Math. Soc., 1947), Edmonds (J. Res. Nat. Bur. Standards Sect. B, 1967) and Lov'asz (FCT, 1979) observed connections between perfect matchings in $G$ and full-rank matrices in $mathcal{S}_G$. Dieudonn'e ({Arch. Math., 1948) 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 Meshulam's proof of Dieudonn'e's result (Quart. J. Math., 1985). 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 for Dieudonn'e's result mentioned above, and for a celebrated theorem of Gerstenhaber regarding the largest dimension of nil matrix spaces (Amer. J. Math., 1958). Finally, we show some implications of our results to quantum information and present open problems in computational complexity motivated by these results.

Full work available at URL: https://arxiv.org/abs/2206.04815

Recommendations

• Publication:4943285
• Maximal rank in matrix spaces via graph matchings
• From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces.
• From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces
• scientific article; zbMATH DE number 4053666

zbMATH Keywords

irreducibilityacyclicitynilpotencystrong connectivity

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Analysis of algorithms and problem complexity (68Q25) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Algebraic systems of matrices (15A30)

Cites Work

• Matrix Analysis
• The Schur complement and its applications
• Reducibility among Combinatorial Problems
• Title not available (Why is that?)
• Zero-Error Communication via Quantum Channels, Noncommutative Graphs, and a Quantum Lovász Number
• The Factorization of Linear Graphs
• Blockers and transversals
• Non-commutative Edmonds' problem and matrix semi-invariants
• Title not available (Why is that?)
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• On Matrices Whose Real Linear Combinations are Nonsingular
• Title not available (Why is that?)
• Vector fields on spheres
• Vector spaces of matrices of low rank
• Sur une généralisation du groupe orthogonal à quatre variables
• On Spaces of Linear Transformations with Bounded Rank
• ON THE MAXIMAL RANK IN A SUBSPACE OF MATRICES
• On computing the determinant in small parallel time using a small number of processors
• Constructing a perfect matching is in random NC
• Matching is as easy as matrix inversion
• Graph Theory
• Arithmetic circuits: a survey of recent results and open questions
• Derandomizing polynomial identity tests means proving circuit lower bounds
• On the dimension of linear spaces of nilpotent matrices
• On Nilalgebras and Linear Varieties of Nilpotent Matrices, I
• Title not available (Why is that?)
• Spectral Properties of Positive Maps on C^* -Algebras
• A Theory of Power-Associative Commutative Algebras
• Linear spaces of nilpotent matrices
• The computational complexity of some problems of linear algebra
• Quantum expanders and geometry of operator spaces
• Expanders and dimensional expansion
• Dimension expanders
• Monotone expanders: constructions and applications
• Expansion in SL\(_2(\mathbb R)\) and monotone expanders
• Towards dimension expanders over finite fields
• Rubber bands, convex embeddings and graph connectivity
• On Gerstenhaber's theorem for spaces of nilpotent matrices over a skew field
• Systems of distinct representatives and linear algebra
• Title not available (Why is that?)
• Classical complexity and quantum entanglement
• Nilpotent linear spaces and Albert's problem
• Groups with Abelian Central Quotient Group
• Singular spaces of matrices and their application in combinatorics
• Title not available (Why is that?)
• Spaces of Matrices with Several Zero Eigenvalues
• Generalized Wong sequences and their applications to Edmonds' problems
• Deterministic polynomial time algorithms for matrix completion problems
• Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
• Quantum graphs as quantum relations
• The word problem for free fields: a correction and an addendum
• Constructive non-commutative rank computation is in deterministic polynomial time
• Wildness for tensors
• On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions
• Enumerating alternating matrix spaces over finite fields with explicit coordinates
• From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces
• Group-theoretic generalisations of vertex and edge connectivities
• Lovász theta type norms and operator systems
• Operator scaling: theory and applications
• Quantum expanders from any classical Cayley graph expander
• Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties)
• Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization
• Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
• Connectivity for quantum graphs
• On the Weisfeiler-Leman Dimension of Finite Groups
• Bipartite Perfect Matching is in Quasi-NC
• Enumerating conjugacy classes of graphical groups over finite fields

Cited In (7)

• From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces.
• Associated graphs of \(p\)-dimensional (0,1)-matrices.
• Title not available (Why is that?)
• The graph spaces of connectivity maps
• The relation between the Jordan structure of a matrix and its graph
• The inertia bound is far from tight
• Maximal generalized rank in graphical matrix spaces

This page was built for publication: Connections between graphs and matrix spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074039)