A Generalized Sylvester Identity and Fraction-free Random Gaussian Elimination

Sylvester’s identity is a well-known identity that 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.