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 V has 2n elements then the Tutte matrix is a 2n × 2n matrix A with entries

$A_{ij}={\begin{cases}x_{ij}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i<j\\-x_{ji}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i>j\\0\;\;\;\;{\mbox{otherwise}}\end{cases}}$

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. (It should be noted that this is not the Tutte polynomial of G.)

The Tutte matrix is a generalisation of the Edmonds matrix for a balanced bipartite graph.

References

• R. Motwani, P. Raghavan (1995). Randomized Algorithms. Cambridge University Press. 
• Allen B. Tucker (2004). Computer Science Handbook. CRC Press. ISBN 158488360X. 
• W.T. Tutte (April 1947). "The factorization of linear graphs.". J. London Math. Soc. 22: 107-111. DOI:10.1112/jlms/s1-22.2.107. Retrieved on 2008-06-15. Research Blogging.