Column Rank of Matrix equals Row Rank

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathbf A$ be a matrix.

The column rank of $\mathbf A$ is equal to the row rank of $\mathbf A$.


Proof

Proof Outline and Definitions

Recall:

The row rank of $\mathbf A$ is defined as the dimension of the row space.
The column rank of $\mathbf A$ is defined as the dimension of the column space.


Without loss of generality, we define the rank of $\mathbf A$ to be the column rank of $\mathbf A$.



This page or section has statements made on it that ought to be extracted and proved in a Theorem page.
In particular: We announce and prove results like the following by means of a separate page dedicated to that result. Please review the design philosophy of $\mathsf{Pr} \infty \mathsf{fWiki}$.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by creating any appropriate Theorem pages that may be needed.
To discuss this page in more detail, feel free to use the talk page.


From the definition of the Definition: Transpose of Matrix, the columns of a matrix are the rows of its transpose and the rows of a matrix are the columns of its transpose. Thus, Row Rank of Transpose is Column Rank and of course Column Rank of Transpose is Row Rank:


$\map r {\mathbf A} = \map c {\mathbf A^\intercal}$
$\map c {\mathbf A} = \map r {\mathbf A^\intercal}$

where $\map r {\mathbf A}$ and $\map c {\mathbf A}$ denote the row rank and column rank respectively.


Hence this result is equivalent to:

$\map c {\mathbf A} = \map c {\mathbf A^\intercal}$

where $\mathbf A^\intercal$ denotes the transpose of $\mathbf A$.


Proof using Orthogonality

Let $\map c {\mathbf A}$ denote the column rank of $\mathbf A$.

Let $\map r {\mathbf A}$ denote the row rank of $\mathbf A$.


Let $\mathbf A$ be an $m\times n$ matrix whose row rank is $r$.

Therefore, the dimension of the row space of $\mathbf A$ is $r$. Let $\mathbf x_1, \ldots, \mathbf x_r$ be a basis of the row space of $\mathbf A$. We claim that the vectors $\mathbf A \mathbf x_1, \ldots, \mathbf A \mathbf x_r$ are linearly independent. To see why, consider the following linear combination of these vectors with scalar coefficients $c_1, \ldots, c_r$:

$\mathbf 0 = c_1 \mathbf A \mathbf x_1 + c_2 \mathbf A \mathbf x_2 + \cdots + c_r \mathbf A \mathbf x_r = \mathbf A \paren {c_1 \mathbf x_1 + c_2 \mathbf x_2 + \cdots + c_r \mathbf x_r} = \mathbf A \mathbf v$

where $\mathbf v = c_1 \mathbf x_1 + \cdots + c_r \mathbf x_r$. We make two observations: $(a)$ $\mathbf v$ is a linear combination of vectors in the row space of $\mathbf A$, which implies that $\mathbf v$ belongs to the row space of $\mathbf A$, and $(b)$ since $\mathbf A \mathbf v = \mathbf 0$, the vector $\mathbf v$ is orthogonal to every row vector of $\mathbf A$ and, hence, is orthogonal to every vector in the row space of $\mathbf A$. The facts $(a)$ and $(b)$ together imply that $\mathbf v$ is orthogonal to itself, which proves that $\mathbf v = \mathbf 0$. Therefore,

$c_1 \mathbf x_1 + c_2 \mathbf x_2 + \cdots + c_r \mathbf x_r = \mathbf 0$

But recall that $\mathbf x_1, \ldots, \mathbf x_r$ were chosen as a basis of the row space of $\mathbf A$ and so are linearly independent. This implies that $c_1=\cdots=c_r=0$. It follows that $\mathbf A \mathbf x_1,\ldots, \mathbf A \mathbf x_r$ are linearly independent.

Now, $\mathbf A \mathbf x_1, \ldots, \mathbf A \mathbf x_r$ are vectors in the column space of $\mathbf A$ and, from the above argument, are r linearly independent vectors in the column space of $\mathbf A$. Therefore, the dimension of the column space of $\mathbf A$ (that is, the column rank of $\mathbf A$) must be at least as big as $r$. This proves that $\map r {\mathbf A} \le \map c {\mathbf A}$, i.e., row rank of $\mathbf A$ is no larger than the column rank of $\mathbf A$. This result applies to any matrix $\mathbf{A}$ so we can apply this result to the transpose of $\mathbf A$ to get the reverse inequality: $\map r {\mathbf A^\intercal} \le \map c {\mathbf A^\intercal}$. Combining these inequalities, we conclude that row rank equals column rank as follows:

$\map r {\mathbf A} \le \map c {\mathbf A} = \map r {\mathbf A^\intercal} \le \map c {\mathbf A^\intercal} = \map r {\mathbf A}$

$\blacksquare$


Proof using Rank Factorization

Let $\map c {\mathbf A}$ denote the column rank of $\mathbf A$.

Let $\map r {\mathbf A}$ denote the row rank of $\mathbf A$.


Let $\mathbf A$ be an $m \times n$ matrix whose column rank is $r$. Therefore, the dimension of the column space of $\mathbf A$ is $r$. Let $\mathbf c_1, \ldots, \mathbf c_r$ be any basis for the column space of $\mathbf A$. Place these vectors as column vectors to form the $m\times r$ matrix $\mathbf C = \begin {bmatrix} \mathbf c_1 & \mathbf c_2 & \cdots & \mathbf c_r \end{bmatrix}$. Therefore, every column vector of $\mathbf A$ is a linear combination of the columns of $\mathbf C$. To be precise, if $\mathbf A = \begin {bmatrix} \mathbf a_1 & \mathbf a_2 & \cdots & \mathbf a_n \end {bmatrix}$ is an $m \times n$ matrix with $\mathbf a_j$ as the $j$-th column, then

$\mathbf a_j = f_{1j} \mathbf c_1 + f_{2j} \mathbf c_2 + \cdots + f_{rj} \mathbf c_r\quad \mbox{for}\quad j=1,\ldots,n$

where $f_{ij}$ are the scalar coefficients of $\mathbf a_j$ in terms of the basis $\mathbf c_1, \mathbf c_2, \ldots, \mathbf c_r$. This implies that $\mathbf A = \mathbf C \mathbf F$, where $f_{ij}$ is the $\tuple {i, j}$th element of $\mathbf F$.

Using transposition of products, we note that $\mathbf A^\intercal = \mathbf F^\intercal \mathbf C^\intercal$. From the definition of matrix multiplication, this means that each column of $\mathbf A^\intercal$ is a linear combination of the columns of $\mathbf F^\intercal$. Therefore, the column space of $\mathbf A^\intercal$ is a subspace of the column space of $\mathbf F^\intercal$ and, hence, $\map c {\mathbf A^\intercal} \leq \map c {\mathbf F^\intercal}$. Now, $\mathbf F^\intercal$ is $n \times r$, so there are $r$ columns in $\mathbf F^\intercal$ and, hence, $\map c {\mathbf A^\intercal} \leq r = \map c {\mathbf A}$. This proves that $\map c {\mathbf A^\intercal} \leq \map c {\mathbf A}$. Now apply the result to the matrix $\mathbf A^\intercal$ to obtain the reverse inequality: since $\paren {\mathbf A^\intercal}^\intercal = \mathbf A$, we can write $\map c {\mathbf A} = \map c {\paren {\mathbf A^\intercal}^\intercal} \leq \map c {\mathbf A^\intercal}$. This proves $\map c {\mathbf A} \leq \map c {\mathbf A^\intercal}$. We have, therefore, proved $\map c {\mathbf A^\intercal} \leq \map c {\mathbf A}$ and the reverse inequality $\map c {\mathbf A} \leq \map c {\mathbf A^\intercal}$. Therefore, $\map c {\mathbf A} = \map c {\mathbf A^\intercal}$.

$\blacksquare$


Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Column_Rank_of_Matrix_equals_Row_Rank&oldid=674927"