{'fraction_non_alphanumeric': 0.07023093957608352, 'fraction_numerical': 0.02348940208794685, 'mean_word_length': 3.579068083051666, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 48, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Multihomogeneous resultant formulae by means of complexes

We provide conditions and algorithmic tools so as to classify and construct the smallest possible determinantal formulae for multihomogeneous resultants arising from Weyman complexes associated to line bundles in products of projective spaces. We also examine the smallest Sylvester-type matrices, generically of full rank, which yield a multiple of the resultant. We characterize the systems that admit a purely B\'ezout-type matrix and show a bijection of such matrices with the permutations of the variable groups. We conclude with examples showing the hybrid matrices that may be encountered, and illustrations of our Maple implementation. Our approach makes heavy use of the combinatorics of multihomogeneous systems, inspired by and generalizing results by Sturmfels-Zelevinsky, and Weyman-Zelevinsky.


Introduction
Resultants provide efficient ways for studying and solving polynomial systems by means of their matrices. This paper considers the sparse (or toric) resultant, which exploits a priori knowledge on the support of the equations. We concentrate on unmixed (i.e. with identical supports) systems where the variables can be partitioned into groups so that every polynomial is homogeneous in each group. Such polynomials, and the resulting systems, are called multihomogeneous. Multihomogeneous structure is a first step away from the classical theory of homogeneous systems towards fully exploiting arbitrary sparse structure. Multihomogeneous systems are encountered in several areas including geometric modeling (e.g. [CGZ98], [Sax97], [Zha00]), game theory and computational economics [MM97].
Known sparse resultant matrices are of different types. On the one end of the spectrum are the pure Sylvester-type matrices, where the polynomial coefficients fill in the nonzero entries of the matrix; such is the coefficient matrix of linear systems, Sylvester's matrix for univariate polynomials, and Macaulay's matrix for homogeneous systems. On the other end are the pure Bézout-type matrices, i.e. matrices where the coefficients of the Bezoutian associated to the input polynomials fill in the nonzero entries of the matrix, whereas hybrid matrices, such as Dixon's, contain blocks of both pure types. The examples in Section 7.2 show the intricacy of such matrices. Hence the interest to describe them in advance in terms of combinatorial data, which allows for a structured matrix representation, based on quasi-Toeplitz or quasi-Hankel structure [EP02], [MP00].
Our work builds on [WZ94] and their study of multihomogeneous systems through the determinant of a resultant complex. First, we give precise degree vectors together with algorithmic methods for identifying and constructing determinantal formulae for the sparse resultant, i.e. matrices whose determinant equals the sparse resultant. The underlying resultant complex is made explicit and computational tools are derived in order to produce the smallest such formula. Second, we describe and construct the smallest possible pure Sylvester matrices, thus generalizing the results of [SZ94] and [GKZ94,Sec. 13.2, Prop. 2.2], already present in the interesting paper [McC33] pointed by one of the referees. The corresponding systems include all systems for which exact Sylvester-type matrices are known. We consider more general Sylvestertype matrices, and show that in the search of small formulae, these more general matrices are not crucial. The third contribution of this paper is to offer sufficient and necessary conditions for systems to admit purely Bézout determinantal formulae, thus generalizing a result from [CK00]. It turns out that these are precisely the same systems admitting optimal Sylvester-type formulae, and this is nothing but a special case of complexes with only two non-vanishing cohomologies. We also show a bijection of such matrices with the permutations on {1, . . . , r}, where r stands for the number of the variable groups. While constructing explicit Bézout-type formulae, we derive a precise description of the support of the Bezoutian polynomial.
The complex with terms K ν (m) described in the next section is known as the Weyman complex. For any choice of dimensions, of degrees of the input equations and of an integer vector m, the multihomogeneous resultant equals the determinant of the Weyman complex (for the corresponding monomial basis at each of the terms), which can be expressed as a quotient of products of subdeterminants extracted from the differentials in the complex. This way of defining the resultant was introduced by Cayley [GKZ94, app. A], [Wey94], [WZ94]. In the particular case in which the complex has just two terms, its determinant is nothing but the determinant of the only nonzero differential, which is therefore equal to the resultant. In this case, we say that there is a determinantal formula for the resultant and the corresponding degree vector m is called determinantal . In [WZ94], the multihomogeneous systems for which a determinantal formula exists were classified; see also [GKZ94,Sec. 13.2]. Their work, though, does not identify completely the corresponding morphisms nor the determinantal vectors m, a question we partially undertake. We follow the results in [DD01], which concerned the homogeneous case, inspired also by [Jou97].
The main result of [SZ94] was to prove that a determinantal formula of Sylvester type exists exactly when all defects are zero. In [SZ94,Thm. 2] (recalled in [GKZ94,Sec. 13.2, Prop. 2.2]; see also [McC33,Thm. 4]) all such formulae are characterized by showing a bijection with the permutations of {1, . . . , r} and defined the corresponding degree vector m as in Definition 5.2 below. This includes all known Sylvester-type formulae, in particular, linear systems, systems of 2 univariate polynomials and bihomogeneous systems of 3 polynomials whose resultant is, respectively, the coefficient determinant, the Sylvester resultant and the Dixon resultant. In fact, Sturmfels and Zelevinsky characterized all determinantal Cayley-Koszul complexes, which are instances of the Weyman complexes when all the higher cohomologies vanish.
The incremental algorithm for sparse resultant matrices [EC95] relies on the determination of a degree vector m. When δ = 0, it produces optimal Sylvester matrices by [SZ94]. For other multihomogeneous systems, [EC95] heuristically produces small matrices, yet with no guarantee. For instance, on the system of Ex. 5.5, it finds a 1120 × 1200 matrix. The present paper explains the behavior of the algorithm, since the latter uses degree vectors following (5.2) defined by random permutations. Our results provide immediately the smallest possible matrix. More importantly, the same software constructs all Sylvestertype formulae described here.
Pure Bézout-type formulae were studied in [CK00] for unmixed systems whose support is the direct sum of what they call basis simplices, i.e. the convex hull of the origin and another l k points, each lying on a coordinate axis. This includes the case of multihomogeneous systems. They showed that in this case a sparse resultant matrix can be constructed from the Bezoutian polynomial, to be defined in Section 6, though the corresponding matrix formula is not always determinantal. Their Corollary 4.2.1 states that for multihomogeneous systems with null defect vector, the Bézout formula becomes determinantal; Saxena had proved the special case of all l k = 1 [Sax97]. In [CK00,Sec. 4.2] they indicate there are r! such formulae and in Section 5 they study bivariate systems (n = 2) showing that then, these are the only determinantal formulae.
Section 6 proves these results in a different manner and characterizes the determinantal cases for multihomogeneous systems, showing that a null defect vector is a sufficient but also necessary condition for a determinantal formula of pure Bézout type for any n. Thus, there is an optimal Sylvester-type formula for the resultant if and only of there is an optimal pure Bézout-type formula. (cf. Definition 6.1) This had been proven for arbitrary systems only in the bivariate case [CGZ98]. In particular, we explicitly exhibit a choice of the differential in the Weyman complex in this case (cf. Theorem 6.13), thus partially answering the "challenge to make these maps explicit" of [WZ94, Sec. 5.1].
Studies exist [CGZ98], [DD01], [Zha00] for dealing with hybrid formulae including Bézout-type blocks or pure Bézout matrices, and concentrate on the computation of such matrices. In particular, [Zha00] elaborates on the relation of Sylvester and Bézout-type matrices (called Cayley-type there) and the transformations that link them. The theoretical setting together with Pfaffian formulae for resultants is addressed in [ES01]. This is made explicit for any toric surface in [K02]. In the recent preprint [ACG02], not also the multihomogeneous resultant but the whole ideal of inertia forms is studied, extending results of Jouanolou [Jou80] in the homogeneous case. This paper is organized as follows. The next section provides some technical facts useful later. Section 3 offers bounds in searching for the smallest possible determinantal (hybrid) formulae. Section 4 makes explicit one degree vector attached to any determinantal data of dimensions of projective spaces, and discusses further techniques for obtaining determinantal formulae. Section 5 and 6 characterize matrices of pure Sylvester and pure Bézout type respectively. In Section 7 we fully describe the formulae of a system of 3 bilinear polynomials. Then, we provide an explicit example of a hybrid resultant matrix for a multidegree for which neither pure Sylvester nor pure Bézout determinantal formulae exist; this example illustrates the possible morphisms that may be encountered with multihomogeneous systems. Our Maple implementation is described in Section 8.
A preliminary version of certain results in this paper has appeared in [DE02].

Preliminary observations
We consider the r-fold product X := P l 1 × . . . × P lr of projective spaces of respective dimensions l 1 , . . . , l r over an algebraically closed field of characteristic zero, for some natural number r. We denote by n = r k=1 l k the dimension of X, i.e. the number of affine variables.
This is an instance of the sparse resultant [GKZ94]. It may be chosen with integer coefficients, and it is uniquely defined up to sign by the requirement that it has relatively prime coefficients. The resultant polynomial is itself homogeneous in the coefficients of each f i , with degree given by the multihomogeneous Bézout bound n l 1 ,...,lr d l 1 1 · · · d lr r [GKZ94, Prop. 13.2.1]. This number is also called the m-homogeneous bound [Wam92].
Let V be the space of (n + 1) tuples f = (f 0 , . . . , f n ) of multihomogeneous forms of degree d over X. Given a degree vector m ∈ Z r there exists a finite complex K · = K · (m) of free modules over the ring of polynomial functions on V [WZ94], whose terms depend only on (l 1 , . . . , l r ), d and m and whose differentials are polynomials on V satisfying: (i) For every given f we can specialize the differentials in K · by evaluating at f to get a complex of finite-dimensional vector spaces. (ii) This complex is exact iff R(f 0 , . . . , f n ) = 0.
In order to describe the terms in these complexes some facts from cohomology theory are necessary; see [Har77] for details. Given a degree vector m ∈ Z r , define, for ν ∈ {−n, . . . , n + 1}, where for an integer r-tuple m ′ , H q (X, m ′ ) denotes the q-th cohomology of X with coefficients in the sheaf O(m ′ ) such that its global sections H 0 (X, m ′ ) are identified with multihomogeneous polynomials of (multi)degree m ′ . By the Künneth formula, we have where q = p − ν and the second sum runs over all integer sums j 1 + · · · + j r = q, j k ∈ {0, l k }. In particular, H 0 (P l k , α k ) is the space of all homogeneous polynomials in l k + 1 variables with total degree α k . By Serre's duality, for any α ∈ Z r , we also know that where * denotes dual. We recall Bott's formulae for these cohomologies.
Let us establish a general technical lemma.
We detail now the main results in [WZ94]. They show (Lemma 3.3(a)) that a vector m ∈ Z r is determinantal iff K −1 (m) = K 2 (m) = 0. They also prove in Theorem 3.1 that a determinantal vector m exists iff δ k ≤ 2 for all k ∈ [r]. To describe a differential in the complex from K ν (m) to K ν+1 (m), one needs to describe all the morphisms δ p,p ′ from the summand corresponding to an integer p to the summand corresponding to another integer p ′ , where both p, p ′ ∈ {0, . . . , n + 1}. [WZ94, Prop. 2.5, 2.6] proves this map is 0 when p < p ′ and that, roughly speaking, it corresponds to a Sylvester map (g 0 , . . . , g n ) → n i=0 g i f i when p = p ′ + 1, thus having all nonzero entries in the corresponding matrix given by coefficients of f 0 , . . . , f n . For p > p ′ + 1, the maps δ p,p ′ are called higher-order differentials. By degree reasons, they cannot be given by Sylvester matrices. Theorem 2.10 also gives an explicit theoretical construction of the higher-order differentials in the pure Bézout case (cf. Definition 6.1).

Bounds for determinantal degree vectors
This section addresses the computational problem of enumerating all determinantal degree vectors m ∈ Z r . The "procedure" of [WZ94, Sec. 3] "is quite explicit but it seems that there is no nice way to parametrize these vectors", as stated in that paper. Instead, we bound the range of m to implement a computer search for them. In Section 4 we will give an explicit choice of degree vector m for each determinantal data ( l 1 , . . . , l r ; d 1 , . . . , d r ).
Given k ∈ {1, . . . , r} and a vector m ∈ Z r define as in [WZ94]: [WZ94], it is easy to give bounds for all determinantal vectors m for which all P k (m) = ∅.
Proof. By [WZ94, Lem. 3.3(b)], P k (m) ⊂ [0, n + 1] ⇒ m k /d k ≥ −1 and (m k + l k )/d k ≥ 0, which imply the lower bound. Also, (m k + l k )/d k < n + 2 ⇔ m k ≤ (n + 2)d k − l k − 1 and m k /d k < n + 1 ⇔ m k ≤ (n + 1)d k − 1 yield the upper bound. Notice that the possible values for m k form a non-empty set, since the two bounds are negative and positive respectively. ✷ Thus, a first guess could be that all determinantal vectors give P k (m) = ∅. But this is not the case, as the following example shows: Example 3.2 Set l = (1, 2), d = (2, 3). We focus on degree vectors of the form m = (2µ 1 , 3µ 2 ), for µ 1 , µ 2 ∈ Z. Then, for all such m, the sets P k (m), for k = 1, 2, are empty. Nevertheless, there exist 4 determinantal vectors of this form, namely m = (4, 3), (0, 6), (2, 6) or (6, 3). Moreover, the vector m = (6, 3) gives a determinantal formula with a matrix of size 88, which is closer to the smallest possible one which has size 72. The largest determinantal formula is given by the determinant of a square matrix of size 180. Note that the degree of the multihomogeneous resultant is 216. More details on this example are provided in Section 8. ✷ We wish now to get a bound for those determinantal vectors for which some Definition 3.3 Given m ∈ Z r and k ∈ {1, . . . , r}, define new vectors m ′ , m ′′ ∈ Z r whose j-th coordinates equal those of m for all j = k and such that Lemmas 3.5 and 3.6 imply Theorem 3.7 For any determinantal m ∈ Z r , define vectors m ′ , m ′′ ∈ Z r as in Definition 3.3 which differ from m only at the k-th coordinates, This implies there is a finite number of vectors to be tested in order to enumerate all possible determinantal m. This could also be deduced from the fact that the dimension of K 0 (m) equals the degree of the resultant. Corollary 3.9 gives a precise bound for the box in which to search algorithmically for all determinantal m, including those that are "pure" in the terminology of [WZ94]. Our Maple implementation, along with examples, is presented in Section 8.
If we take r = 1 = l 1 and m = 2d 1 −1 we obtain the classical Sylvester formula and the upper bound given by Corollary 3.8 is attained. At the lower bound m = −1, the corresponding complex H 1 (P 1 , −1 − 2d) = H 0 (P 1 , 2d 1 − 1) * → H 1 (P 1 , d 1 − 1) 2 = (H 0 (P 1 , d 1 − 1) * ) 2 yields the same matrix transposed. In addition, the system of 3 bilinear polynomials in Section 7.1 admits a pure Sylvester formulae with m = (2, −1), which attains both lower and upper bounds of the Corollary. The bounds in Lemma 3.1 can also be attained (see Ex. 5.5 continued in Section 8) hence Corollary 3.9 is tight. It is possible that some combination of the coordinates of m restricts the search space.

Explicit determinantal degree vectors
We focus on the case of δ k ≤ 2 for all k, which is a necessary and sufficient condition for the existence of a determinantal complex [WZ94]. We shall describe specific degree vectors m that yield determinantal complexes.
Proof. First, K 1 = 0 and K 0 = 0 because they each contain at least one nonzero direct summand, namely H 0 (X, m π − pd) for p = 1, 0 respectively. To see this, it suffices to prove m π k − d k ≥ 0, k = 1, . . . , r, which follows from This holds by Lemma 2.5.
To demonstrate that K 2 = 0 we shall see that every one of its direct summands H q (X, m π − (q + 2)d) vanishes for q = π(j)∈J l j , where J is any proper subset of [r]. Recall that the case J = [r] is irrelevant by the definitions of Section 2. It is enough to show H 0 (P l k , m π k − (q + 2)d k ) = 0, for some k with π(k) ∈ J. Let k be the maximum of the indices verifying π(k) ∈ J; such a k ∈ [r] always It now suffices to establish K −1 (m) = 0. Since this module has no zero cohomology summand, let q = π(j)∈J l j , with J = ∅. Let k ∈ J such that π(j) ≥ π(k) for all j ∈ J. Then, δ k ≤ 2 implies (2 − δ k )d k ≥ 0, from which m π k −(q −1)d k ≥ −l k , and so H q (X, m π −(q −1)d) = 0 for any direct summand of K −1 (m). ✷ When the defects are at most 1, we can give another explicit choice of determinantal degree vector for each permutation of [r].
Proof. Let us modify the previous proof. First, This holds by Lemma 2.5.
To demonstrate that K 2 = 0 we repeat the corresponding argument in the proof of Theorem 4.1. Then, it suffices to show that (−δ k + l k )d k − l k < 2d k , which is weaker than the inequality before (4) above. Similarly, to establish One can easily verify that the vectors m π in both Theorems above satisfy the bounds of Corollary 3.9.
A natural question is how to give an explicit degree vector yielding a determinantal formula of smallest size. When r = 1, this is the content of Lemma 5.3 in [DD01]. Even for r = 2, this seems to be a difficult task in general.
Also, when r = 1 it is shown in [DD01] that the smallest formula is attained for "central" determinantal degree vectors. In this example, all degree vectors m satisfy that either 1 ≤ m 1 ≤ 5 and 4 ≤ m 2 ≤ 7 or 7 ≤ m 1 ≤ 11 and 0 ≤ m 2 ≤ 4; these bounds are computed by the routines described in §8. The smallest resultant matrix has size 340 × 340, and corresponds to the degree vectors (3, 6) or (9, 1), which are in a "central" position among determinantal degree vectors, in other words, their coordinates lie in a "central" position between the respective coordinates of other determinantal vectors. However, the vectors (k, 4) are determinantal for k from 1 to 5, but the size of a matrix corresponding to the vector (3, 4) (both of whose coordinates lie between the coordinates of the vectors (1, 4) and (5, 4)), equals 580. So, it is bigger than the size of a resultant matrix associated to the vector (5, 4), which is of dimension 540. ✷ In the above example, the two degree vectors giving the smallest resultant matrices satisfy (9, 1) + (3, 6) = (12, 7), which is the critical vector from Definition 2.3. It is clear that for any determinantal m, the vector (12, 7) − m is also determinantal yielding the same matrix dimension. This is a consequence of Serre's duality recalled in (2). The general statement in summarized in the next Proposition.
Proposition 4.4 Assume m, m ′ ∈ Z r satisfy m + m ′ = ρ, the latter being the critical degree vector of Definition 2.3. Then, K ν (m) is dual to K 1−ν (m ′ ) for all ν ∈ Z. In particular, m is determinantal if and only if m ′ is determinantal, yielding matrices of the same size, namely dim(K 0 (m)) = dim(K 1 (m ′ )).
Therefore, for all q = 0, . . . , n, Serre's duality (2) implies that H q (X, m ′ − pd) and H n−q (X, m−(n+1−p)d) are dual. Since (n+1−p)−(n−q) = 1−(p−q), we deduce that K ν (m) is dual to K 1−ν (m ′ ) for all ν ∈ Z, as desired. Observe that in particular K −1 (m) ≃ K 2 (m ′ ) * and K 0 (m) ≃ K 1 (m ′ ) * , the latter giving the matrix dimension in the case of determinantal formulae. ✷ We end this section making explicit a consequence of Proposition 3.7 in [WZ94] (and giving an independent proof), which gives a generalization of the characterization of determinantal complexes in [SZ94], [WZ94]. This result will allow us to give in §6 explicit expressions for all degree vectors yielding a determinantal formula of smallest size when all defects vanish. The assumption of the theorem means that there exist exactly two integers p 1 , p 2 ∈ {0, . . . , n + 1} for which H j(p i ) (X, m − p i d) = 0, i = 1, 2; cf. also [WZ94,Lem. 3.3(a)]. Then, for any p ∈ {0, . . . , n + 1} \ {p 1 , p 2 }, there exists k such that k / ∈ A(p) ∪ B(p), i.e., p ∈ P k (m). The latter set is defined at the beginning of Section 3. Then, {0, . . . , n + 1} \ {p 1 , p 2 } ⊆ ∪ r k=1 P k (m) and so where the first inequality uses the fact that # ∪ r k=1 P k (m) ≤ r k=1 #P k (m) and the second follows from the definition of P k (m). Since l k ≥ ⌈ l k d k ⌉ for all k, we deduce that l k = ⌈ l k d k ⌉, and this can only happen iff l k = 1 or d k = 1. ✷

Pure Sylvester-type formulae
This section constructs rectangular matrices of pure Sylvester-type that have at least one maximal minor which is a nontrivial multiple of the sparse resultant, coming from a complex of the form: where K 1 (m) = H j (X, m − d) n+1 , and K 0 (m) = H 0 (X, m) for a non negative vector m ∈ Z r ≥0 .
Lemma 5.1 If m = m ′ ∈ Z r ≥0 yield a Sylvester-type matrix and m ′ k ≥ m k for all k ∈ {1, . . . , r} then, the Sylvester matrix associated to m ′ is strictly larger than the Sylvester matrix associated to m.
The cohomology is nonzero, thus m ′ k − pd k ≥ m k − pd k ≥ 0 and this implies the desired inequality because s+l k l k = (s + l k ) · · · (s + 1)/l k !. The inequality is strict since there exists an index k such that m ′ k > m k . When all defects are zero, these are the vectors defined in [SZ94] yielding determinantal Sylvester formulae and they also coincide with those defined in (3) in Theorem 4.1.
Proof. For p = n + 1, ν = 1, a necessary condition is that H n (X, m − (n + 1)d) = 0. Hence, there exists i ∈ [r] : i by choosing π(i) = 1. For any p as in the statement, The latter inequality is obvious for all p, whereas the former reduces to l i d i ≥ l i which holds since d i ≥ 1. ✷ Theorem 5.4 A degree vector m ∈ Z r ≥0 gives a Sylvester-type matrix iff there exists a permutation π such that m j ≥ m π j for j = 1, . . . , r. Moreover, the smallest Sylvester matrix is attained among the vectors m π .
Proof. We prove the forward direction by induction on k = 1, . . . , r. Assume m gives a Sylvester-type complex and consider the necessary condition K 1 (m) = H 0 (X, m − d). The base case k = 1 was proven in Lemma 5.3. The inductive hypothesis for k ∈ {1, . . . , r −1} specifies which cohomologies vanish and which not, where m u ≥ m π u , π(u) ≤ k. In particular, for all subsets J such that ∅ = J ⊂ {1, . . . , r} \ {1, . . . , k}, p = 1 + π(j)∈J l j , p 0 = p + l v , for some v such that π(v) ≤ k, we assume: For the inductive step, we exploit the necessary condition that H p−1 (X, m − pd) = 0 for p = 1+ π(j)>k l j . By (6), there exists i such that H l i P l i , m i − pd i = 0. Then, m i ≥ pd i −l i = m π i where we define π(i) = k+1. To complete the step, we show H 0 P lu , m u − pd u = 0 where π(u) ≤ k + 1, p = 1 + π(j)∈J l j , and any subset J such that ∅ = J ⊂ {k + 2, . . . , r}. The non-vanishing of the cohomology is equivalent to m u ≥ pd u . It suffices to prove m π i ≥ d i (1+ π(j)>k+1 l j ). By definition, this reduces to −l i + d i l i ≥ 0 ⇔ d i ≥ 1. The converse direction follows from analogous arguments as above. The claim on minimality follows from Lemma 5.1. ✷ This gives an algorithm for finding the minimal Sylvester formulae by testing at most r! vectors m π , which is implemented in Maple (Section 8). To actually obtain the square submatrix whose determinant is divisible by the sparse resultant, it suffices to execute a rank test. These matrices exhibit quasi-Toeplitz structure, implying that asymptotic complexity is quasi-quadratic in the matrix dimension [EP02]. Observe that P k (m π ) = ∅ because there exists p ∈ Z such that p = 1 + π(j)≤π(k) l j such that m π k < d k p = m π k + l k for all k.
It is possible to obtain a pure Sylvester-matrix whose determinant equals the multihomogeneous resultant when the complex has as only non-zero terms K 1 (m) = H j (X, m − (j + 1)d) ( n+1 j+1 ) , and K 0 (m) = H j (X, m − jd) ( n+1 j ) for any j = 0, . . . , n. But in this case we deduce from Theorem 4.5 that all defects vanish. So (cf. [SZ94]) there exists a pure Sylvester-type determinantal formula associated to a non negative degree vector (i.e. m k ≥ 0, k = 1, . . . , r), or equivalently, for j = 0. Thus, if a determinantal data ( l 1 , . . . , l r ; d 1 , . . . , d r ) admits a degree vector yielding a two term Sylvester complex for some j, it admits such a formula for j = 0 as well. Hence, concentrating on j = 0 is not restrictive in the case of determinantal complexes. The Sylvester-type matrices for positive j correspond to degree vectors with some negative entries, unlike the assumption in [SZ94,p.118]. We show such an example in the bilinear case in §7. Thus, the first part of conjecture [SZ94,Conj.3] can be true only for non-negative degree vectors.

Pure Bézout-type formulae
In this section, we will study the following complexes: Weyman complexes of pure Bézout type correspond to generically surjective maps such that any maximal minor is a nontrivial multiple of the multihomogeneous resultant. In fact, we shall show that the only possible such formulae are determinantal (i.e. K 2 (m) = 0). We shall exhibit the corresponding differential in terms of the Bezoutian and characterize the possible degree vectors. We show that there exists a pure Bézout-type formula iff there exists a pure Sylvester formula. We remark that the dimension of the matrix with pure Bézout coefficients equals the dimension of the Sylvester matrix divided by n + 1. Now we can generalize results in [CK00], [Sax97] (cf. Section 1).
Theorem 6.2 There exists a determinantal formula of pure Bézout type iff for all k either l k = 1 or d k = 1, i.e. all defects vanish.
Proof. This is just a special instance of Theorem 4.5, where the only non-zero cohomologies in the complex correspond to p 1 = 0, p 2 = n + 1. ✷ Let us study degree vectors yielding pure Bézout formulae, which will then provide the smallest determinantal formulae in case all defects vanish. When all δ k = 0 these are precisely the vectors defined in (5) in Theorem 4.2. Note that our assumptions in (7) imply H l j P l j , m j − (n + 1)d j = 0, Lemma 6.4 The existence of any pure Bézout formula implies 0 ≤ m j < (n + 1)d j − l j , for all j.
In fact, the m π of Def. 6.3 satisfy these constraints for all permutations π.
Proof. The non negativity of all m j is deduced from the fact that H 0 (X, m) = 0. On the other side, the non vanishing of H n (X, m − (n + 1)d) implies the other inequality. ✷ Lemma 6.5 If m ∈ Z r yields a pure Bézout-type complex, then there exists a permutation π : for any J ⊂ {1, . . . , r} \ {i}, J = ∅.
Proof. Since H n (X, m − nd) = 0, there exists an index i ∈ {1, . . . , r} such that m i − nd i ≥ −l i . It is enough to define π(i) = 1. ✷ Theorem 6.6 If m ∈ Z r yields a pure Bézout-type complex, it is possible to find a permutation π such that the degree vector m verifies m i ≥ m π i for all i = 1, . . . , r.
Proof. It suffices to consider K 1 (m) = H n (X, m − (n + 1)d); it is nonzero by Lemma 6.4. We prove by induction that m = m π by using the fact that all other summands in (1) for K 1 (m) vanish. For H 0 (X, m − d) to vanish, there must exist i ∈ [r] such that H 0 (P l i , m i − d i ) = 0 ⇔ m i < d i . Hence we need to define π(i) = r because π(i) < r ⇒ m π This proves the inductive basis. The inductive hypothesis is: for all u ∈ U ⊂ [r], where |U| = k, π(u) > r − k, then δ u = 0, m u = m π u and for all J such that U ⊂ J ⊂ [r]. For the inductive step, consider that H q (X, m − (1 + q)d) must vanish for q = j∈U l j . None of its summand cohomologies H lu P lu , m u − (1 + q)d u vanish due to the last inequality. So there exists i such that H 0 (P l i , Hence π(i) = r − k so that m i = m π i = −l i + d i π(j)≥r−k l j < (1 + q)d i ⇔ −l i + d i l i < d i ⇔ δ i = 0 by Lemma 2.4. No larger m i works because m π i is the maximum integer strictly smaller than (1 + q)d i . And π(i) < r − k would make m i too large. Now extend the inequality (10) to J ′ where (U ∪ {i}) ⊂ J ′ and observe m π i < d i π(j)≥r−k l j < d i (1 + j∈J ′ l j ).
The hypothesis is proven for all U ⊂ [r], including the case |U| = r. For the converse, assume there exists a permutation π such that m = m π and all defects vanish. Then K 0 (m), K 1 (m) satisfy all conditions for a pure Bézout formula. Furthermore, K −1 (m) = 0, hence the formula is generically surjective. ✷ The condition K 2 (m) = 0, which yields a square matrix, is obtained by the hypothesis of a pure Bézout and generically surjective formula; i.e., there is no rectangular surjective pure Bézout formula.
Corollary 6.8 If a generically surjective formula is of pure Bézout type, then it is determinantal. Furthermore, for any permutation π, the matrix is of the same dimension, i.e. dim K 0 (m) = deg R/(n + 1).

Explicit Bézout-type formulae
We start by defining a dual permutation π ′ to any permutation π.
Proof. m π i + m π ′ i = d i (n + l i ) − 2l i for all i because the sum in the parenthesis includes {l j : π(j) ≥ π(i)} ∪ {l j : π ′ (j) ≥ π ′ (i)}, and latter set is Denote by x i (resp. x ij ) the i-th variable group (resp. the j-th variable in the group), i ∈ [r], j = 0, . . . , l i . Introduce r new groups of variables y i with the same cardinalities and denote by y ij their variables.
Proof. By Lemma 6.10 it suffices to bound α i , β i . But α i is the degree of the x i in the determinant decreased by l i in order to account for the division by (12). The former equals the product of d i with the number of rows where an x ij variable appears for any j ∈ [1, l i ]. These are the first row, the rows where y j are introduced for j ∈ {σ(1), . . . , σ(k − 1)} such that σ(k) = i, and another l i − 1 rows when σ(k) = i. The condition on j : π(j) < π(i) is equivalent to r + 1 − π(j) > r + 1 − π(i), hence α i ≤ −l i + d i π ′ (j)≥π ′ (i) l j = m π ′ i . Similarly, we prove the upper bound on β i . The rows containing y ij for some j ∈ [1, l i ] are those where j ∈ {σ(k + 1), . . . , σ(r)} : σ(k) = i, another l i − 1 rows when σ(k) = i, and the last row. Now, π(j) ≥ k + 1 > k = π(i), so β i ≤ −l i + d i π(j)≥π(i) l j = m π i . Clearly α i , β i ≥ 0. ✷ For generic polynomials, the upper bounds of α i , β i are attained. The lemma thus gives tight bounds on the support of the Bezoutian.
Theorem 6.13 Assume all defects are zero and B π (x, y) is defined as above. For any π, (b αβ ) is a square matrix of dimension dim K 0 (m) = l l 1 , . . . , l r d l 1 1 · · · d lr r = deg R (n + 1) .
Proof. First, we show that (b αβ ) is square of the desired size. The dimensions are given by the number of exponent vectors α, β bounded by Lemma 6.12 which are exactly dim K 0 (m π ′ ), dim K 0 (m π ) respectively. Both m π , m π ′ are determinantal, hence both of these numbers are equal to deg R/(n + 1), by Theorem 6.7 and Corollary 6.8. R(f 0 , . . . , f n ) divides every nonzero maximal minor of the matrix (b αβ ); cf. [CM96], [EM99,Thm. 3.13]. Since any nonzero proper minor has degree < deg R, the determinant of the matrix (b αβ ) is nonzero and equals the resultant. ✷ Note that there is not a unique choice of higher differentials in the Weyman complexes. We could chase the arrows in a resultant spectral sequence as in [GKZ94,Ch. 2,Prop. 5.4] to show that the matrix we propose comes from the explicitization of one possible choice. We have followed instead the more direct route based on the above property of the Bezoutian in [CM96], which uses more elementary tools.
7 Two examples 7.1 The bilinear system The generic system of 3 bilinear polynomials is and has type (1, 1; 1, 1). The degree of the resultant in the coefficients is 3 2 1,1 = 6. We shall enumerate all 14 possible determinantal formulae in the order of decreasing matrix dimension, from 6 to 2, and shall make the corresponding maps explicit. This study goes back to the pioneering work of Dixon [Dix08].
There are additional determinantal Sylvester formulae corresponding to m = (2, −1) and m = (−1, 2). Their matrices contain the f i and the f i multiplied by x −1 1 or by x −1 2 . In the former case, the complex is , and the columns are indexed by 1, x 1 , x 2 , x 1 x 2 , x −1 1 , x −1 1 x 2 . This construction can be verified by hand calculations.
For m = (1, 1) the complex becomes 0 → K 1 = H 0 (0, 0) ( 3 1 ) ⊕ H 2 (−2, −2) → K 0 = H 0 (1, 1) → 0. The matrix is square, of dimension equal to 4, and hybrid. We compute the two maps by hand; for a larger example see Section 7. The foundations for constructing such matrices can be found in [WZ94]. The transposed 4×4 determinantal formula is written as follows, by using brackets: The matrix rows contain the f i and a rational multiple of the affine toric Jacobian, whereas the columns are indexed by 1, x 1 , x 2 , x 1 x 2 . This formula is obtained in [CDS98] in a more general toric setting. An analogous 4×4 matrix corresponds to m = (0, 0).

A hybrid determinantal formula
Assume l = (3, 2), d = (2, 3). We present explicit formulae which can be extrapolated in general, giving an answer to the problem stated in [WZ94,p. 578]. We plan to carry this extensively in a future work, but we include here the example without proofs as a hint for the interested reader. Our Maple program enumerates 30 determinantal vectors m, among which we find m (2,1) = (3, 13) according to Theorem 4.1.
Let us take a closer look at δ 22 , which denotes both the map and the corresponding matrix. Let α ∈ N l 1 , β ∈ N l 2 , be the degree vectors of the elements of H 0 (2), H 0 (3) * respectively, thus |α| ≤ 2, |β| ≤ 3. Let I, J ⊂ {0, . . . , 5}, |I| = 3, |J| = 2 express the chosen polynomials according to the cohomology exponents. Then the entries are given by where T J ∈ H 0 (0) * , S β I are elements of the respective dual bases of monomials. We expect such a construction to be generalizable, but such a proof would be part of future work. Now take the Bézout maps: The matrix entries are given in (11) for σ = (2, 1): the entry (i, j), i, j ∈ {0, . . . , 5} contains f j (x (1) , . . . , x (5−i) , y (6−i) , . . . , y (5) ), where each x (i) is a leading subsequence of x 11 , x 12 , x 13 , x 21 , x 22 ; similarly with the new variables y (i) . The degree of the determinant, i.e. the Bezoutian, is 6, 3, 2, 12 in x 1 , x 2 , y 1 , y 2 respectively and these coefficients fill in the matrix B 50 . For the Bézout block B x 1 52 , consider "partial" Bezoutians defined from the 6 polynomials with the exception of those indexed in J, where J, I are as  Table 1 The main functionalities of our software.
above. Only the x 1 variables are substituted by new ones, thus yielding a 4 × 4 matrix. For B x 2 20 , take all polynomials indexed in I and develop the Bezoutian with new variables y 2 from a 3 × 3 matrix. Hence the entries of the Bézout blocks have, respectively, degree 6, 4, 3 in the coefficients of the f i .

Implementation
We have implemented on Maple V routines for the above operations, including those in Table 1. They are illustrated below and are available in file mhomo.mpl through: http://www.di.uoa.gr/~emiris/index-eng.html. The last 2 commands find all 488 determinantal vectors. The smallest formulae are indicated (the minimum dimension is 224) and for some we report the P k 's. No determinantal formulae is pure Sylvester. Notice that the assumption of empty sets P k is used only in order to bound the search, but within the appropriate range empty P k 's are considered, so no valid degree vector is missed. This is illustrated by the last P 3 = ∅ marked NO INT.
The vectors predicted by Theorem 4.1 are found among those produced above, including m (123) = (6, 5, 3), m (213) = (4, 9, 3), m (312) = (0, 9, 7). The corresponding matrix dimensions are 672, 600, and 800. ✷ Example 6.11 (Cont'd) Recall that l = (1, 2), d = (2, 1). The only pure Bézout formulae are the 2 determinantal formulae of Ex. 6.11, for which we have m π = (5, 0), m π ′ = (1, 1). Our results can be generalized to polynomials with scaled supports or with a different degree d per polynomial. One question is whether the vectors m ′ , m ′′ of Definition 3.3 lead to smaller or larger matrices than m. Notice that certain cohomologies, which were nonzero for m, may vanish for m ′ or m ′′ . We plan to complete the description of hybrid determinantal formulae. We would also like to answer in general the question stated in §4 of determining a priori the degree vectors yielding the smallest determinantal formulae in all possible cases. A problem related to the Sylvester formulae calls for identifying in advance the nonzero maximal minor in the matrix, which leads to finding a determinant with exact degree in some polynomial.