  Gaussian graphical models are semi-algebraic subsets of the cone of positive
definite covariance matrices. Submatrices with low rank correspond to
generalizations of conditional independence constraints on collections of
random variables. We give a precise graph-theoretic characterization of when
submatrices of the covariance matrix have small rank for a general class of
mixed graphs that includes directed acyclic and undirected graphs as special
cases. Our new trek separation criterion generalizes the familiar
$d$-separation criterion. Proofs are based on the trek rule, the resulting
matrix factorizations and classical theorems of algebraic combinatorics on the
expansions of determinants of path polynomials.
