# Why does every $m \times n$ matrix of rank $r$ reduce to $(m \times r)$ times $(r \times n)$?

How can I prove the following statement?

Every $$m \times n$$ matrix of rank $$r$$ reduces to $$(m \times r)$$ times $$(r \times n)$$:

$$A =$$ (pivot columns of $$A$$) (first $$r$$ rows of $$R$$) = (COL)(ROW).

[ Source: Gilbert Strang, Introduction to Linear Algebra, question $$56$$, section $$3.2$$. ]

I think that the $$R$$ is reduced row echelon form. I believe there is a brief elegant proof.

• How do you define the rank of a matrix? – Brian May 5 at 12:44
• @Brian The dimension of column space. – Tengerye May 6 at 1:32

Let $$\{v_1,\dotsc, v_r\}$$ be a basis of $$\operatorname{Col}(A)$$ where $$A$$ is $$m\times n$$. Put these basis vectors into the columns of a matrix $$V$$, so that $$V=\left[\begin{array}{ccc}v_1 & \cdots & v_r\end{array}\right]$$ Then, for every $$b\in\operatorname{Col}(A)$$ there exists a $$x_b\in\Bbb R^r$$ such that $$Vx_b=b$$.

Now, let $$\{a_1,\dotsc, a_n\}$$ be the columns of $$A$$ so that $$A=\left[\begin{array}{ccc}a_1 & \cdots & a_r\end{array}\right]$$ Each column $$a_k$$ of $$A$$ is in $$\operatorname{Col}(A)$$. So, let $$W=\left[\begin{array}{ccc}x_{a_1} & \cdots & x_{a_r}\end{array}\right]$$ What happens when we compute $$VW$$?

• How shall we connect 𝑊 with reduced row echelon form 𝑅 please? @Brain – Tengerye May 16 at 9:24

Suppose $$\mathbf{A}=[\mathbf{p_1}, \mathbf{f_2}, \cdots, \mathbf{p_n}]$$ where $$\mathbf{p_i}$$ is the column of $$\mathbf{A}$$ indexed $$i$$ and it is pivot column; while $$\mathbf{f_i}$$ is free column with similar notation. Therefore, $$\mathbf{L}=[\mathbf{p_1}, \cdots, \mathbf{p_n}]$$ have columns of pivot columns of $$\mathbf{A}$$. Let $$\mathbf{R}=[\mathbf{p_1^R}, \mathbf{f_2^R}, \cdots, \mathbf{p_n^R}]$$ be the reduced row echelon form of $$\mathbf{A}$$. $$\mathbf{R^c}$$ be the first $$r$$ rows of $$\mathbf{R}$$.

Matrix $$\mathbf{A}$$ is of $$m$$ by $$n$$ with rank $$r$$. Because $$\mathbf{R}$$ is $$rref(\mathbf{A})$$, the last $$r$$ rows of $$R$$ are null row vectors. Thus, $$\mathbf{L}\mathbf{R^c}=[\mathbf{p_1}, \cdots, \mathbf{p_n}, \mathbf{f_2}, \cdots]\mathbf{R}$$ where the last $$n-r$$ columns of $$[\mathbf{p_1}, \cdots, \mathbf{p_n}, \mathbf{f_2}, \cdots]$$ are free columns and first $$n$$ columns are pivot columns.

Now we need to prove $$\mathbf{A}=[\mathbf{p_1}, \cdots, \mathbf{p_n}, \mathbf{f_2}, \cdots]R$$. Every entry of $$\mathbf{p_i^R}$$ is 0 except 1 at the $$i^{th}$$ row, $$[\mathbf{p_1}, \cdots, \mathbf{p_n}, \mathbf{f_2}, \cdots] \mathbf{p_i^R} = \mathbf{p_i}$$. The pivot columns of $$\mathbf{A}$$ remain. For $$\mathbf{f_j^R}=[c_0, \cdots, c_n, 0, \cdots]^{T}$$, we have $$c_0\mathbf{p_0^R}+\cdots+c_n\mathbf{p_n^R}=\mathbf{f_j^R}$$. Because $$\mathbf{R}$$ has the same row space and nullspace of $$\mathbf{A}$$, $$c_0\mathbf{p_0}+\cdots+c_n\mathbf{p_n}=\mathbf{f_j}$$, i.e. $$[\mathbf{p_1}, \cdots, \mathbf{p_n}, \mathbf{f_2}, \cdots]\mathbf{f_j^R}=\mathbf{f_j}$$.

Welcome to alternative proofs.