Answer to Question #24293 in Linear Algebra for Jacob Milne

Question

Let A be an arbitrary M by N matrix and B the matrix in row-reduced echelon form obtained from A. Prove that there is a non-zero solution of the system of linear equations Ax = 0 iff B has fewer than N non-zero rows.

Answer 1

As says Rouché–Capelli theorem, system of equations Ax=bhave a solution iff rank(A)=rank(A|b). Then we know that matrix A can be transformed into amatrix B in row-reduced echelon form using elementary row operations, each
operation is in one to one correspondence with left matrix multiplying by
elementary, and they are invertible, so matrix A and B are equivalent by
viewing that B=E₁E₂…E_nA, and E_i areelementary matrices. Thus systems Ax=0 and Bx=0 have the same solutions and by Rouché–Capelli theorem rank(B) = rank(A) =rank(A|0). If B has N non-zero rows, then N=rank(A) and A is invertible, so x=0. Then B has to have R fewer than Nnon-zero rows, then we canchoose N-R nonzero values of x components, and obtain the whole nonzero x.