Page 76 - Textos de Matemática Vol. 39

66 SHMUEL FRIEDLAND AND DANIEL LEVY
Proof. It is enough to consider the nontrivial case k < m. Let 2
Gw =(V(A),Ew(A)),Gw,k =(V(Ak),Ew(Ak))betheweightedgraphscorre- sponding to A, Ak respectively. Note that Gw is a weighted subgraph of Gw,k induced by V (A) = ⟨m⟩ ⊂ ⟨2m − 2k⟩ = V (Ak). Furthermore, each vertex in V (Ak )\V (A) is connected exactly to each vertex in V (A). The weights of each of these edges is 1. These are all edges in G(Ak). A perfect match in G(Ak) correspond to:
• An m − 2k match between the set of vertices V (Ak )\V (A) and the set of vertices α′ ∈ Qm−2k,m, viewed as a subset of V (A).
• A k match between the set of vertices α := ⟨m⟩\α′ ⊂ V (B).
Fix α ∈ Q2k,m. Then the total weight of k-matchings in Gw(Ak) using the set of vertices α ⊂ V (Ak) is given by haf A[α, α]. The total weight of m − 2k matchings using V (Ak )\V (A) and V (A)\α is (m − 2k)!. Hence the total weight of perfect matchings in Gw (Ak ), which matches the set of vertices α ⊂ V (Ak ) isgivenby(m−2k)!hafA[α,α].ThushafAk =(m−2k)!hafkA.
It is not known if the computation of the number of perfect matching in an arbitrary undirected graph on an even number of vertices, or more generally the computation of haf A for an arbitrary A ∈ S2n,0(R+), has a fpras. The probabilistic algorithm outlined in [7] carries over to the computation of haf A, however it is an open problem if this algorithm is a fpras. Theorem 3.1 shows that the computation of hafk A, for A ∈ Sm,0(R+), has the same complexity as the computation of haf A, for A ∈ S2n,0(R+).
4. Remarks
In this section we offer an explanation, using the recent results in [3], why permA is a nicer function than haf A. Let A = [aij] ∈ Sn(R),B = [bij] ∈ Rn×n. Forx:=(x1,...,xn)⊤ ∈Rn let
n n 1
p(x) := ( bijxj), q(x) := 2x⊤Ax.
i=1 j=1 nnn
Then perm B =
Assume that B ∈ Rn×n has no zero row. Then p(x) is a positive hyperbolic
∂ p(x) and haf A = (( n )!)−1 ∂ q(x) 2 if n is even. ∂x1...∂xn 2 ∂x1...∂xn
+
polynomial. (See the definition in [3].) Assume that A ∈ S2m,0(R+) is irre-
ducible. Then q(x), and hence any power q(x)i,i ∈ N, is positive hyperbolic if and only if all the eigenvalues of A, except the Perron-Frobenius eigenvalue, are nonpositive.