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.
翻译:根据双面图形 G$, 图形矩阵空间 $\ mathcal{S ⁇ G$ 由矩阵组成, 其非零条目只能位于与G$的边缘相对应的位置。 Tutte(J. London Math. Soc.,1947年)、 Edmonds(J. Res. Nat. Bur. 标准 section. B,1967年) 和 Lov\'asz(FCT,1979年) 观察到, 以G$为单位的完美匹配与以$为单位的全级矩阵之间的联系。 Dieudonn\e({Arch. Math.), 1948年) 证明, 这些矩阵空间的大小与美元相对应的精确性(Quart. commexmissionalal relations) 之间有密切的深度连接。 开始, 开始于我们之间, 开始于1985年, 直径的直径, 和直径之间的直径, 和直径, 直径之间, 直径。