$M$ is an $n\times n$ matrix. Consider the submatrices $M(P;Q)$ formed from $P$ rows and $Q$ columns of $M$ where $P$ and $Q$ are disjoint indices.

Is there some way to encode the various determinants such as $\det M((1,2,4);(3,5,6))$, $\det M((1,2);(3,5))$, and $\det M((1,3);(2,4))$ in a single object much like chromatic polynomials and generating functions.

As a motivation, such determinants represent some kind of information about connections in an adjacency matrix of a graph and connections have information interrelated among each other. Therefore, it feels like the various determinants should be interrelated and that therefore there should be a way to intertwine them all in a single object like chromatic polynomials and generating functions.

-
As far as I can understand, you want to understand the structure of the submatrices that don't use the diagonal. If $|P|=|Q|=1$ then you have direct access to the diagonal elements, so the remaining determinants are superfluous information. – Allen Knutson Sep 1 '11 at 3:58
@Allen Knutson: I think you mean "to the off-diagonal elements" – Federico Poloni Sep 1 '11 at 7:17
Oops, yes indeed. – Allen Knutson Sep 1 '11 at 21:44

If you consider $M\colon V\to V$ as a linear map of an $n$-dimensional vector space $V$ into itself (with some canonical basis $e_i$ used to express $M$ as a matrix), then the $k$-minors (which you called subdeterminants) of $M$ are the components of the induced linear map $\bigwedge^k M\colon \bigwedge^k V \to \bigwedge^k V$ of the $k$-th exterior power of $V$, provided you use the canonical basis $e_{i_1}\wedge\cdots\wedge e_{i_k}$ to express it as a matrix.
Since you are not interested in minors that have the same index appearing in both the row and column lists, you can just set those components of $\bigwedge^k M$ to zero. From the linear algebra point of view, this can be accomplished by applying a certain projector to this matrix, whose precise form is not difficult to figure out. The result, say denoted by $[\bigwedge^k M]$, is still an map from $\bigwedge^k V$ to itself. Thus you can capture some information about $[\bigwedge^k M]$ in its characteristic polynomial. This polynomial will be invariant under permutations of the graph vertices. Though probably not all the coefficients this polynomial will be independent invariants.
Could you formally specify $\bigwedge^k M\colon \bigwedge^k V \to \bigwedge^k V$. Its not obvious to me what the linear map $\bigwedge^k M$ is. – user16557 Sep 3 '11 at 4:14
Sure. Any element of $\bigwedge^k V$ is a linear combination of vectors of the form $v_1\wedge\cdots\wedge v_k$, where the $v_i\in V$ could be any set of vectors, including the canonical basis vectors $e_i$. On these elements the map is defined as $\bigwedge^k M\colon v_1\wedge\cdots\wedge v_k \mapsto (Mv_1)\wedge\cdots\wedge(Mv_k)$. Expressed in the canonical basis, the matrix of $\bigwedge^k M$ is called the $k$-th compount matrix of the matrix of $M$, at least in Gantmacher's classic Theory of Matrices. – Igor Khavkine Sep 3 '11 at 9:26
Explicitly in component form, if $M^a_b$ are the components of $M$ then the components of say $\bigwedge^3 M$ are $(M_3)^{abc}_{def} = 3! M^{[a}_{[d} M^{b}_{e} M^{c]}_{f]}$, where square brackets denote idempotent total antisymmetrization. Also, if $(P_i)^a_b$ is the projection onto the subspace of $V$ spanned by $e_i$, the contraction $(P_i)^d_a (M_3)^{abc}_{def}$ will give you the matrix of all minors $\det M((abc);(def))$ where $i$ appears in both $(abc)$ and $(def)$. These are precisely the components you want to subtract off. – Igor Khavkine Sep 3 '11 at 9:40