Connections between graphs and matrix spaces

Li, Y; Qiao, Y; Wigderson, A; Wigderson, Y; Zhang, C

Connections between graphs and matrix spaces

Li, Y Qiao, Y

Wigderson, A Wigderson, Y Zhang, C

Permalink

Publisher:: HEBREW UNIV MAGNES PRESS
Publication Type:: Journal Article
Citation:: Israel Journal of Mathematics, 2023, 256, (2), pp. 513-580
Issue Date:: 2023-09-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

The embargo period expires on 1 Sep 2024

Adobe PDF

Download Accepted versionAdobe PDF (512.98 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Li, Y
dc.contributor.author	Qiao, Y https://orcid.org/0000-0003-4334-1449
dc.contributor.author	Wigderson, A
dc.contributor.author	Wigderson, Y
dc.contributor.author	Zhang, C https://orcid.org/0009-0004-4857-3454
dc.date.accessioned	2024-02-06T10:31:29Z
dc.date.available	2024-02-06T10:31:29Z
dc.date.issued	2023-09-01
dc.identifier.citation	Israel Journal of Mathematics, 2023, 256, (2), pp. 513-580
dc.identifier.issn	0021-2172
dc.identifier.issn	1565-8511
dc.identifier.uri	http://hdl.handle.net/10453/175383
dc.description.abstract	Given a bipartite graph G, the graphical matrix space SG 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ász (FCT, 1979) observed connections between perfect matchings in G and full-rank matrices in SG . Dieudonné (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 SG containing only singular matrices is equal to the maximum size over subgraphs of G without perfect matchings, based on Meshulam’s proof of Dieudonné’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 Dieudonné’s result mentioned above, and 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.
dc.language	English
dc.publisher	HEBREW UNIV MAGNES PRESS
dc.relation.ispartof	Israel Journal of Mathematics
dc.relation.isbasedon	10.1007/s11856-023-2515-7
dc.rights	info:eu-repo/semantics/embargoedAccess
dc.subject	0101 Pure Mathematics, 0102 Applied Mathematics
dc.subject.classification	General Mathematics
dc.subject.classification	4901 Applied mathematics
dc.subject.classification	4902 Mathematical physics
dc.subject.classification	4904 Pure mathematics
dc.title	Connections between graphs and matrix spaces
dc.type	Journal Article
utslib.citation.volume	256
utslib.for	0101 Pure Mathematics
utslib.for	0102 Applied Mathematics
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	open_access	*
utslib.copyright.embargo	2024-09-01T00:00:00+1000Z
dc.date.updated	2024-02-06T10:31:28Z
pubs.issue	2
pubs.publication-status	Published
pubs.volume	256
utslib.citation.issue	2

Abstract:

Given a bipartite graph G, the graphical matrix space SG 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ász (FCT, 1979) observed connections between perfect matchings in G and full-rank matrices in SG . Dieudonné (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 SG containing only singular matrices is equal to the maximum size over subgraphs of G without perfect matchings, based on Meshulam’s proof of Dieudonné’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 Dieudonné’s result mentioned above, and 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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/175383