Gaussian elimination *is* a polynomial-time algorithm. While it may not be obvious on the first sight, the intermediate entries have only polynomial size (bit length), because they happen to be equal to ratios of determinants of certain submatrices of the original matrix.