A generalized Sylvester identity and fraction-free random Gaussian elimination

Sylvester's identity is a well-known identity which can be used to prove that certain Gaussian elimination algorithms are fraction-free. In this paper we will generalize Sylvester's identity and use it to prove that certain random Gaussian elimination algorithms are fraction-free. This can be used to yield fraction-free algorithms for solving Ax = b (x 0) and for the simplex method in linear programming. 1 Introduction Sylvester's identity is a well-known identity relating a hyperdeterminant of a matrix (i.e. a determinant of minors) to the determinant of that matrix. Let R be a commutative ring and A = (a ij ) an n \Theta m matrix over R. For 0 k ! min(n; m), k ! i n and k ! j m define a (k) i;j = fi fi fi fi fi fi fi fi fi a 11 \Delta \Delta \Delta a 1k a 1j . . . . . . . . . a k1 \Delta \Delta \Delta a kk a kj a i1 \Delta \Delta \Delta a ik a ij fi fi fi fi fi fi fi fi fi : (1) We can now state Sylvester's identity (for a proof see for example [1]). Theorem 1 (Sylvest..