Tutte matrix

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,\dots ,n\}$ then the Tutte matrix is an n × n matrix A with entries

$A_{ij}=\{\begin{array}{l}{x}_{ij}\text{if}(i,j)\in E\text{ and }i<j\\ -x_{ji}\text{if}(i,j)\in E\text{ and }i>j\\ 0\text{otherwise}\end{array}$

where the x_ij are indeterminates. The determinant of this skew-symmetric matrix is then a polynomial (in the variables x_ij, 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.

References

• R. Motwani, P. Raghavan (1995). Randomized Algorithms. Cambridge University Press. p. 167. 
• Allen B. Tucker (2004). Computer Science Handbook. CRC Press. p. 12.19. ISBN 1-58488-360-X. 
• {{cite journal|url= http://jlms.oxfordjournals.org/cgi/reprint/s1-22/2/107.pdf%7Ctitle= The factorization of linear graphs