article published yes Yinan Li author Youming Qiao author Avi Wigderson author Yuval Wigderson author 2d0023a0-1567-11f0-833d-d5c1e476d4b5 Chuanqi Zhang author 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´asz (FCT, 1979) observed connections between perfect matchings in G and full-rank matrices in SG. 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 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´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 Dieudonn´e’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. Springer Nature2023 eng 0021-2172 1565-8511 2206.0481510.1007/s11856-023-2515-7 2562513-580 yes Li, Yinan, et al. “Connections between Graphs and Matrix Spaces.” <i>Israel Journal of Mathematics</i>, vol. 256, no. 2, Springer Nature, 2023, pp. 513–80, doi:<a href="https://doi.org/10.1007/s11856-023-2515-7">10.1007/s11856-023-2515-7</a>. Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, and C. Zhang, “Connections between graphs and matrix spaces,” <i>Israel Journal of Mathematics</i>, vol. 256, no. 2. Springer Nature, pp. 513–580, 2023. Li, Yinan, Youming Qiao, Avi Wigderson, Yuval Wigderson, and Chuanqi Zhang. “Connections between Graphs and Matrix Spaces.” <i>Israel Journal of Mathematics</i>. Springer Nature, 2023. <a href="https://doi.org/10.1007/s11856-023-2515-7">https://doi.org/10.1007/s11856-023-2515-7</a>. Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, C. Zhang, Israel Journal of Mathematics 256 (2023) 513–580. Li Y, Qiao Y, Wigderson A, Wigderson Y, Zhang C. 2023. Connections between graphs and matrix spaces. Israel Journal of Mathematics. 256(2), 513–580. Li, Y., Qiao, Y., Wigderson, A., Wigderson, Y., &#38; Zhang, C. (2023). Connections between graphs and matrix spaces. <i>Israel Journal of Mathematics</i>. Springer Nature. <a href="https://doi.org/10.1007/s11856-023-2515-7">https://doi.org/10.1007/s11856-023-2515-7</a> Li Y, Qiao Y, Wigderson A, Wigderson Y, Zhang C. Connections between graphs and matrix spaces. <i>Israel Journal of Mathematics</i>. 2023;256(2):513-580. doi:<a href="https://doi.org/10.1007/s11856-023-2515-7">10.1007/s11856-023-2515-7</a> 221622026-06-29T10:52:37Z2026-07-08T10:44:50Z