# Proving the Column Correspondence Principle

Suppose there is a four by five matrix A in which three of the five column vectors are linearly independent. Today my professor demonstrated that the the reduced row echelon form of A hints at the position of the linearly independent matrix.

Specifically, if the u th , v th and w th column vector are the three linearly independent column vectors in the reduced row echelon form matrix of A (hence the column vectors that contain the leading ones), then the u th, v th and w th column vectors of A are also linearly independent. He calls it the column correspondence principle. What is the proof for this?

Let's say $A$ is the original matrix and $R$ the reduced echelon form. The reduction to reduced echelon form can be viewed as the application (multiplication) of a sequence of matrices to $A$: $D L_{n-1} \cdots L_0 A = R.$ The matrices $L_i$ are called Gauss transforms and the matrix $D$ is diagonal. Importantly, those matrices are square and invertable (nonsingular).
Next, let's take the linearly independent columns of $R$ and create a matrix $\widetilde R$ with those and let's take the corresponding columns of $A$ and make a matrix $\widetilde A$ with those. Then $D L_{n-1} \cdots L_0 \widetilde A = \widetilde R$. Now, if the columns of $\widetilde R$ are linearly independent, then we know that $\widetilde R x = 0$ implies that $x = 0$. Let's see what this tells us about $\widetilde A$: Assume $\widetilde A x = 0$. Then $\widetilde A x = L_0^{-1} \cdots L_{n-1}^{-1} D^{-1} \widetilde R x$ which implies that $\widetilde R x = 0$. But that means that $x = 0$. So, if columns in $R$ are linearly independent, then the corresponding columns in $A$ are linearly independent. The converse can be proven similarly.
• There is no assumption in my discussion about the matrices being square. Only $L_i$ and $D$ have to be square. – Robert van de Geijn Mar 28 '18 at 2:19