SET m TO number of rows of A
SET n TO number of columns of A
SET p TO 1
SET q TO 1
WHILE p ≤ m AND q ≤ n
Find the smallest j ≥ q with Ak,j = 0 for some k ≥ p
IF k = p
Replace Rp by Rp/Ak,j
ELSE
Replace Rp by Rp + Rk/Ak,j
IF there are other rows with non-zero entries in the j th column
Replace Ri by Ri i Ai,jRp
SET p TO p + 1
SET q TO j + 1
RETURN A