Matrices constructed from a parameterized multivariate polynomial system are analyzed to ensure that such a matrix contains a condition for the polynomial system to have common solutions irrespective of whether its parameters are specialized or not. Such matrices include resultant matrices constructed using well-known methods for computing resultants over projective, toric and affine varieties. Conditions on these matrices are identified under which the determinant of a maximal minor of such a matrix is a nontrivial multiple of the resultant over a given variety. This condition on matrices allows a generalization of a linear algebra construction, called rank submatrix, for extracting resultants from singular resultant matrices, as proposed by Kapur, Saxena and Yang in ISSAC'94. This construction has been found crucial for computing resultants of non-generic, specialized multivariate polynomial systems that arise in practical applications. The new condition makes the rank submatrix construction based on maximal minor more widely applicable by not requiring that the singular resultant matrix have a column independent of the remaining columns. Unlike perturbation methods, which require introducing a new variable, rank submatrix construction is faster and effective. Properties and conditions on symbolic matrices constructed from a polynomial system are discussed so that the resultant can be computed as a factor of the determinant of a maximal non-singular submatrix.

A geometric concept of the support hull of the support of a polynomial was used earlier by the authors for developing a tight upper bound on the size of the Cayley-Dixon resultant matrix for an unmixed polynomial system. The relationship between the support hull and the Cayley-Dixon resultant construction is analyzed in this paper. The support hull is shown to play an important role in the construction and analysis of resultant matrices based on the Cayley-Dixon formulation, similar to the role played by the associated convex hull (Newton polytope) for analyzing resultant matrices over the toric variety. For an unmixed polynomial system, the sizes of the resultant matrices (both dialytic as well as nondialytic) constructed using the Cayley-Dixon formulation are determined by the support hull of its support. Consequently, degree of the projection operator (which is in general, a nontrivial multiple of the resultant) computed from such a resultant matrix is determined by the support hull.The support hull of a given support is similar to its convex hull except that instead of the Euclidean distance, the support hull is defined using rectilinear distance. The concept of a support-hull interior point is introduced. It is proved that for an unmixed polynomial system, the size of the resultant matrix (both dialytic and nondialytic) based on the Cayley-Dixon formulation remains the same even if a term whose exponent is support-hull interior with respect to the support is generically added to the polynomial system. This key insight turned out to be instrumental in generalizing the concept of an unmixed polynomial system with a corner-cut support from 2 dimensions to arbitrary dimension as well as identifying an unmixed polynomial system with almost corner-cut support in arbitrary dimension.An algorithm for computing the size (and the lattice points) of the support hull of a given support is presented. It is proved that determining whether a given lattice point is not in the support hull, is NP-complete. A heuristic for computing a good variable ordering for constructing Dixon matrices for mixed as well as unmixed polynomial systems is proposed using the support hull and its projections. This is one of the first results on developing heuristics for variable orderings for constructing resultant matrices. A construction for a Sylvester-type resultant matrix based on the support hull of a polynomial system is also given.

Structural conditions on polynomial systems are developed for which the Dixon-based resultant methods often compute exact resultants. For cases when this cannot be done, the degree of the extraneous factor in the projection operator computed using the Dixon-based methods is typically minimal. A method for constructing a resultant matrix based on a combination of Sylvester-dialytic and Dixon methods is proposed. A heuristic for variable ordering for this construction often leading to exact resultants is developed.

A structural criteria on polynomial systems is developed for which the generalized Dixon formulation of multivariate resultants defined by Kapur, Saxena and Yang (1994) computes the resultant exactly. The concept of a Dixon-exact support (the set of exponent vectors of terms appearing in a polynomial system) is introduced so that the Dixon formulation produces the exact resultant for generic unmixed polynomial systems whose support is Dixon-exact. A geometric operation, called direct-sum, on the supports is defined that preserves the property of supports being Dixon-exact. Generic n-degree systems and multigraded systems are shown to be a special case of generic unmixed polynomial systems whose support is Dixon-exact. Using a scaling techniques discussed by Kapur and Saxena (1997), a wide class of polynomial systems can be identified for which the Dixon formulation produces exact resultants. This analysis can be used to classify terms appearing in the convex hull (also called the Newton polytope) of the support of a polynomial system that can cause extraneous factors in the computation of a projection operation by the generalized Dixon formulation. For the bivariate case, a complete analysis of the terms corresponding to the exponent vectors in the Newton polytope of the support of a polynomial system is given vis a vis their role in producing extraneous factors in a projection operator. A necessary and sufficient condition is developed for a support to be Dixon-exact. Such an analysis is likely to give insights for the general case of elimination of arbitrarily many variables.