Column Rank = Row Rank. (The Rank of a Matrix is the Same as the Rank of its Transpose)
Problem 136
Let $A$ be an $m\times n$ matrix. Prove that the rank of $A$ is the same as the rank of the transpose matrix $A^{\trans}$.
Sponsored Links
Contents
Hint.
Recall that the rank of a matrix $A$ is the dimension of the range of $A$.
The range of $A$ is spanned by the column vectors of the matrix $A$.
Proof.
We write $A=(a_{ij})$ and let
\[\mathbf{A}_i=\begin{bmatrix}
a_{1i} \\
a_{2i} \\
\cdots \\
a_{mi}
\end{bmatrix}\]
be the $i$-th column vector of $A$ for $i=1,2,\dots, n$.
Also let
\[\mathbf{B}_i=\begin{bmatrix}
a_{i1} \\
a_{i2} \\
\cdots \\
a_{in}
\end{bmatrix}\]
be the $i$-th column vector of $A^{\trans}$ for $i=1, 2, \dots, m$, that is $B_i$ is the transpose of the $i$-th row vector of $A$.
Suppose that $\rk(A)=\dim(\calR(A^{\trans}))=k$ and let $\{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_k\}$ be a basis for the range $\calR(A^{\trans})$.
We write
\[\mathbf{v}_{i}=\begin{bmatrix}
v_{i1} \\
v_{i2} \\
\vdots \\
v_{in}
\end{bmatrix}\]
for $i=1,2, \dots, k$.
Then each column vector $\mathbf{B}_i$ of $A^{\trans}$ is a linear combination of $\{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_k\}$. Thus we have
\begin{align*}
\mathbf{B}_1 &=c_{11}\mathbf{v}_1+\cdots+c_{1k}\mathbf{v}_k\\
\mathbf{B}_2 &=c_{21}\mathbf{v}_1+\cdots+c_{2k}\mathbf{v}_k\\
\vdots\\
\mathbf{B}_m &=c_{m1}\mathbf{v}_1+\cdots+c_{mk}\mathbf{v}_k.
\end{align*}
More explicitly we have,
\begin{align*}
\begin{bmatrix}
a_{11} \\
a_{12} \\
\cdots \\
a_{1n}
\end{bmatrix} &=c_{11}\begin{bmatrix}
v_{11} \\
v_{12} \\
\vdots \\
v_{1n}
\end{bmatrix}+\cdots+c_{1k}\begin{bmatrix}
v_{k1} \\
v_{k2} \\
\vdots \\
v_{kn}
\end{bmatrix}\\
\begin{bmatrix}
a_{21} \\
a_{22} \\
\cdots \\
a_{2n}
\end{bmatrix} &=c_{21}\begin{bmatrix}
v_{11} \\
v_{12} \\
\vdots \\
v_{1n}
\end{bmatrix}+\cdots+c_{2k}\begin{bmatrix}
v_{k1} \\
v_{k2} \\
\vdots \\
v_{kn}
\end{bmatrix}\\
\vdots\\
\begin{bmatrix}
a_{m1} \\
a_{m2} \\
\cdots \\
a_{mn}
\end{bmatrix} &=c_{m1}\begin{bmatrix}
v_{11} \\
v_{12} \\
\vdots \\
v_{1n}
\end{bmatrix}+\cdots+c_{mk}\begin{bmatrix}
v_{k1} \\
v_{k2} \\
\vdots \\
v_{kn}
\end{bmatrix}\\
\end{align*}
Now, we look at the $i$-th entries for the above vectors and we have
\begin{align*}
a_{1i}&=c_{11}v_{1i}+\cdots+c_{1k}v_{ki}\\
a_{2i}&=c_{21}v_{1i}+\cdots+c_{2k}v_{ki}\\
\vdots \\
a_{mi}&=c_{m1}v_{1i}+\cdots+c_{mk}v_{ki}\\.
\end{align*}
We rewrite these as a vector equality and obtain
\begin{align*}
\mathbf{A}_i&=\begin{bmatrix}
a_{1i} \\
a_{2i} \\
\cdots \\
a_{mi}
\end{bmatrix}=v_{1i}\begin{bmatrix}
c_{11} \\
c_{21} \\
\vdots \\
c_{m1}
\end{bmatrix}+\cdots +v_{ki}\begin{bmatrix}
c_{1k} \\
c_{2k} \\
\vdots \\
c_{mk}
\end{bmatrix}\\
&=v_{1i}\mathbf{c}_{1}+\cdots+v_{ki}\mathbf{c}_k,
\end{align*}
where we put
\[c_j=\begin{bmatrix}
c_{1j} \\
c_{2j} \\
\vdots \\
c_{mj}
\end{bmatrix}\]
for $j=1,2,\dots,k$.
This shows that any column vector $\mathbf{A}_i$ of $A$ is a linear combination of vectors $\mathbf{c}_1, \dots, \mathbf{c}_k$. Therefore we have
\[\calR(A)=\Span\{\mathbf{A}_1, \dots, \mathbf{A}_n\} \subset \Span\{\mathbf{c}_1, \dots, \mathbf{c}_k\}. \]
Since the dimension of a subspace is smaller than or equal to the dimension of a vector space containing it, we have
\[\rk(A)=\dim(\calR(A)) \leq \dim(\Span\{\mathbf{c}_1, \dots, \mathbf{c}_k\}) \leq k. \]
Hence we obtain
\[\rk(A) \leq \rk(A^{\trans}).\]
To achieve the opposite inequality, we repeat this argument using $A^{\trans}$, and we obtain
\[\rk(A^{\trans}) \leq \rk((A^{\trans})^{\trans})=\rk(A)\]
since we have $(A^{\trans})^{\trans}=A$.
Therefore, we proved the required equality
\[\rk(A)=\rk(A^{\trans}).\]
Add to solve later
Sponsored Links
There is a typo in definition of i-th column vector of A. It’s last element should be a(m,i), not a(n,i). This mistake remains in the equation following “We rewrite these as a vector equality and obtain…”
Dear Hank,
Thank you for catching the typo. I modified it accordingly. Thanks!