In graph theory, the Tutte matrix A of a graph G = (V, E) is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once.
If the set of vertices is
V=\{1,2,...,n\}
Aij=\begin{cases}xij if (i,j)\inEandi<j\\ -xji if (i,j)\inEandi>j\\ 0 otherwise\end{cases}
where the xij are indeterminates. The determinant of this skew-symmetric matrix is then a polynomial (in the variables xij, i < j): this coincides with the square of the pfaffian of the matrix A and is non-zero (as a polynomial) if and only if a perfect matching exists. (This polynomial is not the Tutte polynomial of G.)
The Tutte matrix is named after W. T. Tutte, and is a generalisation of the Edmonds matrix for a balanced bipartite graph.