Connections between graphs and matrix spaces

DOI10.1007/S11856-023-2515-7MaRDI QIDQ6074039zbMATHOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(10)

• The number of connected components in a graph associated with a rectangular \((0,1)\)-matrix
• Maximal generalized rank in graphical matrix spaces
• 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.
• Associated graphs of \(p\)-dimensional (0,1)-matrices.
• scientific article; zbMATH DE number 1416064 (Why is no real title available?)
• 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

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)