17
$\begingroup$

I have the following theorem:

Theorem 3.12. Let A be an m n matrix. Then the dimension of its row space is equal to the dimension of its column space.

And the following proof is given:

Proof. Suppose that $\lbrace v_1,v_2,\dots,v_k\rbrace$ is a basis for the column space of $A$. Then each column of $A$ can be expressed as a linear combination of these vectors; suppose that the $i$-th column $c_i$ is given by $$c_i = \gamma_{1i}v_1+\gamma_{2i}v_2+\dots+\gamma_{ki}v_k$$ Now form two matrices as follows: $B$ is an $m\times k$ matrix whose columns are the basis vectors $v_i$, while $C=(\gamma_{ij})$ is a $k\times n$ matrix whose $i$-th column contains the coefficients $\gamma_{1i},\gamma_{2i,}\dots,\gamma_{ki}$. It then follows$^7$ that $A=BC$.

However, we can also view the product $A= BC$ as expressing the rows of $A$ as a linear combination of the rows of $C$ with the $i$-th row of $B$ giving the coefficients for the linear combination that determines the $i$-th row of $A$. Therefore, the rows of $C$ are a spanning set for the row space of $A$, and so the dimension of the row space of $A$ is at most $k$. We conclude that: $$\dim(\operatorname{rowsp}(A))\leq\dim(\operatorname{colsp}(A))$$ Applying the same argument to $A^t$, we conclude that:$$\dim(\operatorname{colsp}(A))\leq\dim(\operatorname{rowsp}(A))$$and hence these values are equal

However, I am finding this proof impossible to follow and understand. Can someone please offer an alternative proof or explain what this proof is saying?

Thank you.

$\endgroup$
5
  • $\begingroup$ Perhaps it'll be better if someone simply clarifies the proof I posted up? A detailed walk-through of each step would be nice. :) $\endgroup$ Aug 23, 2016 at 6:45
  • 2
    $\begingroup$ Hi there. This is in fact a very cool and simple proof. I've never seen it before but now that I have I think it's the coolest proof there is. Its understanding hinges on the fact that matrix multiplication may be understood in 4 different ways. Please watch the YT vids where professor Gilbert Strang teaches Linear Algebra and you'll see what are the 4 ways to understand matrix multiplication. Then you'll understand this proof and appreciate its simplicity. $\endgroup$
    – darlove
    Mar 23, 2021 at 22:11
  • $\begingroup$ @darlove I know Strang does a beautiful job with the 4 fundamental subspaces, but there are only two ways to understand matrix multiplication, right? The row viewpoint and the column viewpoint. $\endgroup$ Mar 23, 2021 at 22:17
  • 1
    $\begingroup$ @TedShifrin No, there are 4 ways to understand matrix multiplication from a technical point of view. 1) The standard definition way: $c_{i,j} = \sum_{k=1}^n a_{i,k}b_{k,j}$, 2) The "combination of column vectors" way, 3) the "combination of row vectors" way and 4) the "sum of 1-rank matrices" way. Watch his vids and you'll see him explaining all 4. By the way, to understand the proof above you only have to understand the 2) and 3) way. $\endgroup$
    – darlove
    Mar 24, 2021 at 12:22
  • 1
    $\begingroup$ Ah, yes, I don't bother with 1 and 4. I've taught out of his book, have written my own books and have my own videos. ;) $\endgroup$ Mar 24, 2021 at 14:22

4 Answers 4

9
$\begingroup$

You can consider it as the next explanation also for the fact that the row dimension of a Matrix equals the column dimension of a matrix. For that I will use what it's called the rank of a Matrix.

The rank $r$ of a Matrix can be defines as the number of non-zero singular values of the Matrix, So applying the singular value decomposition of the matrix, we get $A=U\Sigma V^T$. This implies that the range $dim(R(A))=r$, as the range of $A$ is spanned by the first $r$ columns of $U$. We know that the range of $A$ is defined as the subspace spanned by the columns of $A$, so the dimension of it will be $r$.

If we take the transpose of the Matrix and compute it's SVD, we see that $A^T=V\Sigma^T U^T$, and as the Sigma Matrix remains the same number of non-zero elements as the one for $A$, the rank of this Matrix will still be $r$. So as done for $A$, the dimension for the range of $A^T$ is equal to $r$ too, but as the range of $A^T$ is the row space of $A$, we conclude that the dimension for both spaces must be the same and equal to the range of the Matrix $A$.

$\endgroup$
6
  • $\begingroup$ Thanks but I don't quite understand this explanation either. I'm not familiar with terms such as 'singular value decomposition'. $\endgroup$ Aug 22, 2016 at 21:27
  • 2
    $\begingroup$ What the proof is basically saying is the next thing: it first takes the columns of the matrix $A$ and sees that there are k linearly independent columns, implying that all the other can be written as a linear combination of those k vectors. Then the columns of $A$ are expressed as the matricial product $BC$, where B is just the matrix whose columns are the $k-basis$ of the columns and $C$ is the matrix containing the coefficients necessary to create the columns of $A$ from the $k-basis$ vector. Then the reasoning is based that, as a matricial product can be seen as many diferent... $\endgroup$ Aug 23, 2016 at 8:11
  • 1
    $\begingroup$ ways for doing (see outer and inner product en.wikipedia.org/wiki/Matrix_multiplication), then it can be seen that the rows of A are spanned by the rows of your recently generated matrix C with the coefficients given by B. This implies that, as C is kxn, the dimension of the row space is as maximum k, implying that it has to be less or equal than the column space dimension. Finally, if you apply all of this reasoning to the $A^T$, you get the same result as before, but as the rows of A are the columns of $A^T$, you can get the last inequality... $\endgroup$ Aug 23, 2016 at 8:15
  • $\begingroup$ As both of the inequalities are true, that implies that both of dimensions have to be the same. Hope that this helps! $\endgroup$ Aug 23, 2016 at 8:16
  • $\begingroup$ Got it! Thank you. :) $\endgroup$ Aug 23, 2016 at 17:08
7
$\begingroup$

Here is a more explicit step-by-step version of the proof quoted in the question.



Proof

Let $A\in\mathcal{M}_{m\times n}(\mathbb{K})$, where $\mathbb{K}$ is any field. Let $\{\boldsymbol{u^1},\ldots, \boldsymbol{u^k} \}$ be a basis of the column space of $A$, where $k\in\{1,\ldots,n\}$. $\boldsymbol{u^i}$ is a vector in $\mathbb{K}^m$ (the vector space of $m$-tuples with entries in $\mathbb{K}$) for all $i\in\{1,\ldots,k\}$. Thus each column in $A$ can be expressed as a linear combination of $\boldsymbol{u^1},\ldots,\boldsymbol{u^k}$. That is, for every $j\in\{1,\ldots,n\}$ there exist unique coefficients $\lambda_{1j},\ldots,\lambda_{nj}\in\mathbb{K}$ such that $$ \forall j\in\{1,\ldots,n\}\qquad \boldsymbol{v^j} = \sum_{\ell=1}^{k} \lambda_{\ell j} \boldsymbol{u^\ell}\,, $$ where $\boldsymbol{v^j}$ denotes the $j$-th column in $A$.


Let $B\in\mathcal{M}_{m\times k}(\mathbb{K})$ be the matrix with such vectors as columns: $$ B = \begin{pmatrix} \vert & & \vert \\ \boldsymbol{u^1} & \cdots & \boldsymbol{u^k} \\ \vert & & \vert \end{pmatrix}\,. $$ Let $[s]$ denote $\{1,\ldots,s\}$ for all $s\in\mathbb{N}$. Let $C\in\mathcal{M}_{k\times n}(\mathbb{K})$ be the matrix with the aforementioned coefficients: $$ C = (\lambda_{ij})_{(i,j)\in[k]\times[n]} = \begin{pmatrix} \lambda_{11} & \cdots & \lambda_{1n} \\ \vdots & \ddots & \vdots \\ \lambda_{k1} & \cdots & \lambda_{kn} \end{pmatrix}\,. $$


Now consider the matrix product $BC\in\mathcal{M}_{m\times n}(\mathbb{K})$. Let $(bc)_{ij}$, $b_{ij}$ and $c_{ij}$ denote the $(i,j)$-th element of $BC$, $B$ and $C$ respectively. By definition of matrix product, \begin{equation}\tag{1}\label{foo} (bc)_{ij} = \sum_{\ell=1}^{k} b_{i\ell}c_{\ell j} \qquad\forall (i,j)\in[m]\times[n]\,. \end{equation} Let us consider the $j$-th column of $BC$ for an arbitrary $j\in[n]$. Let $v^\ell_i$ denote the $i$-th component of $\boldsymbol{u^\ell}$ for all $\ell\in[k]$ and for all $i\in[m]$.

$$ \begin{multline*} \left((bc)_{ij}\right)_{i\in[m]} = \left( \sum_{\ell=1}^{k} b_{i\ell}c_{\ell j} \right)_{i\in[m]} = \begin{pmatrix} \sum_{\ell=1}^{k} b_{1\ell}c_{\ell j} \\ \vdots \\ \sum_{\ell=1}^{k} b_{m\ell}c_{\ell j} \end{pmatrix} = \\ % = \begin{pmatrix} \sum_{\ell=1}^{k} v^\ell_1\cdot\lambda_{\ell j} \\ \vdots \\ \sum_{\ell=1}^{k} v^\ell_m\cdot\lambda_{\ell j} \end{pmatrix} = \sum_{\ell=1}^k \lambda_{\ell j} % \begin{pmatrix} v^\ell_1 \\ \vdots \\ v^\ell_m \end{pmatrix} = \sum_{\ell=1}^{k} \lambda_{\ell j}\boldsymbol{u^\ell} = \boldsymbol{v^j}\,. \end{multline*} $$

Thus, the columns of $BC$ are the columns of $A$. Ergo, $A=BC$.


On the other hand, let us consider the $i$-th row of $A$, denoted by $\boldsymbol{r^i}$. That is, $$ \boldsymbol{r^i} = (a_{ij})_{j\in[n]} \qquad \forall i\in[m]\,. $$ Again, by the definition of matrix multiplication, $$ a_{ij} = \sum_{\ell=1}^{k} b_{i\ell}c_{\ell j} \qquad\forall (i,j)\in[m]\times[n] $$ (this is the same equation found in eq. \eqref{foo}). Thus,

$$ \begin{multline}\tag{2}\label{rows} \boldsymbol{r^i} = \left(\sum_{\ell=1}^{k} b_{i\ell}c_{\ell j} \right)_{j\in[n]} = \begin{pmatrix} \sum_{\ell=1}^{k} b_{i\ell}c_{\ell 1} & \cdots & \sum_{\ell=1}^{k} b_{i\ell}c_{\ell n} \end{pmatrix} = \\ = \begin{pmatrix} \sum_{\ell=1}^{k} v^\ell_i\cdot\lambda_{\ell 1} & \cdots & \sum_{\ell=1}^{k} v^\ell_i\cdot\lambda_{\ell n}\,. \end{pmatrix} \end{multline} $$

Now, let $\boldsymbol{\Lambda^\ell}$ be the $\ell$-th row of $C$ for all $\ell\in[k]$, as a row vector:

$$ \begin{equation*} \boldsymbol{\Lambda^\ell} = \begin{pmatrix} \lambda_{\ell 1} & \cdots & \lambda_{\ell n}\,. \end{pmatrix} \end{equation*} $$

Thus, with the same notation as before, ${\Lambda^\ell_i} = \lambda_{\ell i}$ for all $i\in[n]$. Also, let $\mu_{i \ell}$ denote $v^\ell_i$ for all $i\in[m]$ and for all $\ell\in[k]$ — this is merely a change of notation to remark the fact that $v^\ell_i$ can be seen as "coefficients". Thus, continuing to develop equation \eqref{rows}, we get

$$ \begin{multline*} \boldsymbol{r^i} = \begin{pmatrix} \sum_{\ell=1}^{k} \mu_{i\ell}\cdot\Lambda^\ell_1 & \cdots & \sum_{\ell=1}^{k} \mu_{i\ell}\cdot\Lambda^\ell_n \end{pmatrix} = \\ = \sum_{\ell=1}^k \mu_{i\ell} \begin{pmatrix} \Lambda^\ell_1 & \cdots & \Lambda^\ell_n \end{pmatrix} = \sum_{\ell=1}^k \mu_{i\ell} \boldsymbol{\Lambda^\ell}\,. \end{multline*} $$


Therefore, the rows of $A$ (i.e., $\boldsymbol{r^i}$) are linear combinations of the rows of $C$ (i.e., $\boldsymbol{\Lambda^\ell}$). Thus, we necessarily have $$ \mathrm{rowsp}\ A \subseteq \mathrm{rowsp}\ C \ \implies\ \dim (\mathrm{rowsp}\ A) \le \dim (\mathrm{rowsp}\ C)\,. $$ Since $C$ has $k$ rows, its row space can have at most dimension $k$, which is the dimension of $\mathrm{colsp}\ A$ (by hypothesis): $$ \dim(\mathrm{rowsp}\ C) \le k = \dim(\mathrm{colsp}\ A)\,. $$ Combining both inequalities, we have $$ \dim (\mathrm{rowsp}\ A) \le \dim (\mathrm{colsp}\ A)\,. $$


Applying this whole argument again on $A^\mathrm{t}$, $$ \dim (\mathrm{rowsp}\ A^\mathrm{t}) \le \dim (\mathrm{colsp}\ A^\mathrm{t}) \iff \dim (\mathrm{colsp}\ A) \le \dim (\mathrm{rowsp}\ A)\,. $$ Since we have both $\dim (\mathrm{rowsp}\ A) \le \dim (\mathrm{colsp}\ A)$ and $\dim (\mathrm{colsp}\ A) \le \dim (\mathrm{rowsp}\ A)$, we conclude that $$ \dim (\mathrm{colsp}\ A) = \dim (\mathrm{rowsp}\ A)\,. \quad \square $$

$\endgroup$
2
$\begingroup$

The long proof by Anakhand, even though perfectly correct, is harder to understand than the proof given in the original question. This is because it gets to the nitty-gritty details of matrix multiplication. Matrix multiplication can be understood in several different ways. One of them is the fact that if a matrix is right-multiplied by a column vector, then the output is a linear combination of columns of the matrix where the coefficients are the vector's coordinates (this is crucial to understanding the proof in the question and is a simple observation). So, if one multiplies 2 matrices, the output is a matrix where each column of the output matrix is a linear combination of the columns of the first matrix and the coefficients are the coordinates of the corresponding vector in the second matrix. On the other hand, if you left-multiply a matrix by a row vector, then the output is a row vector which is a linear combination of rows in the matrix. Similarly when you multiply 2 matrices. If one understands this, the proof in the question becomes much clearer than the proof that goes into the nitty-gritty details of matrix multiplication.

$\endgroup$
0
$\begingroup$

Row reduction eliminates the redundant rows in a matrix, i.e. the rows that are linear combinations of other rows. Row operations also do not change the row space because taking nonzero linear combinations of a set of vectors does not change their span.

It is impossible not to eliminate a row that is a linear combination of the others when reducing to reduced echelon form, and so the RREF of the matrix will give you the number of linearly independent rows, i.e. the dimension of the row space. Let p be the number of rows of zeroes at the bottom of the matrix. Then the dimension of the row space is m - p.

Now consider the effect of this reduction on columns. Row operations preserve linear dependence relations among the columns of A so that the same linear dependence relation holds for columns of the RREF of A as for A. If you have an m x n matrix with p rows of zeros at the bottom, then you also have m - p pivots. If this were not the case, then one of the rows above those p rows would be row reducible to a row of all zeros, which is what happens to any row that does not have a pivot.

Since the number of pivots is equal to the number of linearly independent vectors in the RREF, and this is also equal to the number of linearly independent vectors in the original matrix, these columns form a basis for Col(A). The dimension of the column space is the number of basis vectors, and so we have shown that the two are equal.

$\endgroup$
2
  • $\begingroup$ "Now consider the effect of this reduction on columns. Row operations preserve linear dependence relations among the columns of A so that the same linear dependence relation holds for columns of the RREF of A as for A." This bit is about as clear as mud. It might be true but it's highly non-obvious. How can you explain in a simple way that this indeed is true? $\endgroup$
    – darlove
    Mar 23, 2021 at 21:57
  • $\begingroup$ When you're solving a system of linear equations, your solution solves both the RREF of the system and the original system. Hence, the linear dependence relations among the columns are maintained. $\endgroup$ Mar 24, 2021 at 22:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .