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.

  • $\begingroup$ How do you define the rank of a matrix? $\endgroup$ – Brian May 5 at 12:44
  • $\begingroup$ @Brian The dimension of column space. $\endgroup$ – 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$?

  • $\begingroup$ How shall we connect 𝑊 with reduced row echelon form 𝑅 please? @Brain $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.