  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.
