# Tutte matrix

2010 Mathematics Subject Classification: *Primary:* 05C50 *Secondary:* 05C70 [MSN][ZBL]

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 \times 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

- Rajeev Motwani, Prabhakar Raghavan, "Randomized Algorithms", Cambridge University Press (1995) ISBN 978-0-521-47465-8 Zbl 0849.68039
- Allen B. Tucker, "Computer Science Handbook", 2nd ed. CRC Press (2004) ISBN 158488360X
- W.T. Tutte, "The factorization of linear graphs",
*J. London Math. Soc.***22**(1947) 107-111 DOI 10.1112/jlms/s1-22.2.107

**How to Cite This Entry:**

Tutte matrix.

*Encyclopedia of Mathematics.*URL: http://www.encyclopediaofmath.org/index.php?title=Tutte_matrix&oldid=39570