Exact same solutions implies same row-reduced echelon form?

Solutions to the homogeneous system associated with a matrix is the same as determining the null space of the relevant matrix. The row space of a matrix is complementary to the null space. This is true not only for inner product spaces, and can be proved using the theory of non-degenerate symmetric bilinear forms.

So if two matrices of the same order have exactly the same null space, they must also have exactly the same row space. In the row reduced echelon form the nonzero rows form a basis for the row space of the original matrix, and hence two matrices with the same row space will have the same row reduced echelon form.