Tutte's matrix for perfect matching in bipartite graphs I came across Tutte's matrix for a bipartite graph $G(U, V, E)$ in two different forms.
One form (seen in these notes for example https://www.cs.cmu.edu/afs/cs/academic/class/15859-f04/www/scribes/lec3.pdf) says the matrix M is defined by $$M_{ij} = \begin{cases} x_{ij} \; \text{if}\;  (u_i, v_j) \in E \\ 0 \; \text{if}\;\; (u_i, v_j) \notin E \end{cases}$$
However, other statements and answers on this site state that matrix $M$ is skew-symmetric.
The proof in the notes that shows perfect matching occurs iff $\det(M)$ is non-singular seems to be much easier with the first definition (that does not involve skew-symmetry). Are these two forms equivalent, or is there a reason the first is incorrect ?
 A: The formula in these lecture notes is actually a formula for the Edmonds matrix. It is only defined for bipartite graphs (since the bipartition is baked into the definition) and it only make sense to take its determinant when the bipartite graph is balanced.
The skew-symmetric Tutte matrix is a generalization for any graph. For completeness, here is the definition: it is a matrix $A$ where $$A_{ij} = \begin{cases}x_{ij} & ij \in E, i<j \\ -x_{ij} & ij \in E, i>j \\ 0 & ij \notin E\end{cases}$$
This does not require a graph to be bipartite, and even if the graph is bipartite, it does not require us to know the bipartition.
However, suppose that the graph is a balanced bipartite graph, and further suppose that we sort the vertices in the order $u_1, u_2, \dots, u_n, v_1, v_2, \dots, v_n$. Then if we use this order to index the rows and columns of the Tutte matrix $A$, it will have the block form $$A = \begin{bmatrix}0 & M \\ -M^{\mathsf T} & 0\end{bmatrix}$$ where $M$ is the Edmonds matrix. We will have $\det(A) = \det(M)^2$, so if one determinant is nonzero, so is the other. This makes sense, since for bipartite graphs, both should tell us if a perfect matching exists.
The Tutte matrix can also tell us if a perfect matching exists in a non-bipartite graph, however.
