# Rank

Previously in section, we discussed the row space spanned on rows of an*m*×

*n*matrix

**A**. Its dimension is called the row-rank. Similarly, we worked in section with columns and showed that, for any

*m*×

*n*matrix

**A**, the dimension of its range (which is also called the column space) is called column-rank. Now we show that these two ranks are actually equal to each other in the following theorem.

Recall that a set of vectors β is said to generate or span a
vector space *V* if every element from
*V* can be represented as a linear combination of vectors from β.

**Theorem: **
For any *m*×*n* matrix **A**, its column rank and the row
rank are always equal.

**A**be a matrix of size

*m*×

*n*(with

*m*rows and

*n*columns). Let the column rank of

**A**be

*r*and let

*c*

_{1},

*c*

_{2}, ... ,

*c*

_{r}be any basis for the column space of

**A**. Place these as the columns of an

*m*×

*r*matrix

**C**. Every column of

**A**can be expressed as a linear combination of the

*r*columns in

**C**. This means that there is an

*r*×

*n*matrix

**R**such that

**A**=

**C**

**R**.

**R**is the matrix whose i-th column is formed from the coefficients giving the i-th column of

**A**as a linear combination of the

*r*columns of

**C**. Now, each row of

**A**is given by a linear combination of the

*r*rows of

**R**. Therefore, the rows of

**R**form a spanning set of the row space of

**A**and, by the Steinitz exchange lemma, the row rank of

**A**cannot exceed

*r*. This proves that the row rank of

**A**is less than or equal to the column rank of

**A**. This result can be applied to any matrix, so apply the result to the transpose of

**A**. Since the row rank of the transpose of

**A**is the column rank of

**A**and the column rank of the transpose of

**A**is the row rank of

**A**, this establishes the reverse inequality and we obtain the equality of the row rank and the column rank of

**A**. (Also see rank factorization.)

**Another proof:**
Let **A** be a matrix of size *m* × *n* (with *m* rows and
*n* columns) with entries from ℝ whose row rank is *r*.
Therefore, the dimension of the row space of **A** is *r*. Let
**x**_{1}, **x**_{2}, ... , **x**_{r}
be a basis of the row space of **A**. We claim that the vectors
**A****x**_{1}, **A****x**_{2}, ... ,
**A****x**_{r} are linearly independent. To see why, consider a linear
homogeneous relation involving these vectors with scalar coefficients
*c*_{1}, *c*_{2}, ... , *c*_{r}:

**v**=

*c*

_{1}

**x**

_{1}+

*c*

_{2}

**x**

_{2}+ ... +

*c*

_{r}

**x**

_{r}. We make two observations: (a)

**v**is a linear combination of vectors in the row space of

**A**, which implies that v belongs to the row space of

**A**, and (b) since

**A**

**v**=

**0**, the vector

**v**is orthogonal to every row vector of

**A**and, hence, is orthogonal to every vector in the row space of

**A**. The facts (a) and (b) together imply that

**v**is orthogonal to itself, which proves that

**v**=

**0**or, by the definition of

**v**,

**x**

_{i}were chosen as a basis of the row space of

**A**and so are linearly independent. This implies that \( c_1 = c_2 = \cdots = c_r =0 . \) It follows that

**A**

**x**

_{1},

**A**

**x**

_{2}, ... ,

**A**

**x**

_{r}are linearly independent.

Now, each

**A**

**x**

_{i}is obviously a vector in the column space of

**A**. So

**A**

**x**

_{1},

**A**

**x**

_{2}, ... ,

**A**

**x**

_{r}is a set of r linearly independent vectors in the column space of

**A**and, hence, the dimension of the column space of

**A**(i.e., the column rank of

**A**) must be at least as big as

*r*. This proves that row rank of

**A**is no larger than the column rank of

**A**. Now apply this result to the transpose of

**A**to get the reverse inequality and conclude as in the previous proof.

**Another proof:**
If **A** = **0**, then both row space and column space of **A** are
zero dimensional. Suppose **A** ≠ **0** and its rank is *r*.
Then its column space is spanned on *r* column vectors of **A**:

**A**. We build

*m*×

*r*matrix

**B**of these basis column vectors.

Since each column vector of **A** is a linear combination of the columns of
**B**, there exits an *r*×*n* matrix **X** such that
**A** = **BX**. next we partition *n*×*r* matrix
**X**^{T} into its column vectors:

*m*-vector

**x**, we have

**A**is less or equal to the dimension of its column space. We can repeat the reverse combination and obtain the required identity.

**A**is an

*m*×

*n*matrix, then its

**rank**is the maximum number of linearly independent row vectors or column vectors. This integer is denoted rank(

**A**) or rank

**A**.

**Observation: **
Elementary row operations and elementary column operations on a matrix are
rank preserving.

**Observation: **
The rank of any matrix equals the maximum number of its linearly independent
columns or rows; that is, the rank of a matrix is the dimension of the
subspace generated either by its columns or by its rows.

**Observation: **
The rank of any matrix equals the number of pivots; that is, the rank of a
matrix is the number of leading 1's in its Gauss-Jordan form.

**Theorem: **
Let **A** and **B** be two matrices of dimensions
*m*×*n* and *n*×*k*, so their product
**AB** exists. Then

*r*of any

*n*×

*k*matrix

**B**is the number of its linearly independent rows or columns. The range of any matrix cannot exceed the dimension of its image because

*r*≤ max{

*k*,

*n*}. So matrix

**B**maps

*n*linearly independent vectors from space ℝ

^{n}into

*r*linearly independent vectors. Next application of matrix

**A**deals with

*r*linearly independent vectors and therefore it maps into certain number of linearly independent vectors that is less or equal to

*r*.

**Theorem: **
Let **A** be an *m*×*n* matrix. If *p*×*m*
matrix **S** has full column rank and *n*×*q* matrix
**T** has full row rank, then

- rank(
**AT**) = rank(**A**); - rank(
**SA**) = rank(**A**); - rank(
**SAT**) = rank(**A**).

*Mathematica*confirms, 3×4 matrix

**A**has rank 2, 5×3 matrix

**S**has rank 3, and 4×4 matrix

**T**has rank 4. We slightly modify matrices

**S**and

**T**

**A**with

**S**

_{1}and

**T**

_{1}give

**Theorem: **
Let **A** be an *m*×*n* matrix of rank *r*. By means of
a finite number of elementary row and column operations **A** can be
transformed into the "diagonal" matrix

**I**is the identity matrix of dimension

*r*and three matrices

**0**are rectangular matrices with all zero entries.

**A**≠

**0**and

*r*= rank

**A**> 0. The proof is by mathematical induction on

*m*, the number of rows of

**A**.

Suppose that *m* = 1. By means of interchanging any two rows or columns
and multiplying columns by a nonzero number, matrix **A** can be transformed into a matrix with a 1 in the (1,1) position. By means of at most *n*-1
elementary operations (adding rows or columns with some multiples) this matrix
can in turn be transformed into the matrix

**A**, that is, 1.

Next assume that the theorem hlds for any matrix with at most *m-1* rows
(for some *m*>1). We must prove that the theorem holds for any matrix
with *m* rows.

**Corollary: **
Let **A** be an *m*×*n* matrix of rank *r*. Then there
exist invertible matrices **X** and **Y** of sizes *m*×*m* and *n*×*n*, respectively, such that **Λ** =
**XAY**, where the "diagonal" matrix **Λ** is described in the
previous theorem.

**Corollary: **
Let **A** be an *m*×*n* matrix. Then rank(**A**) =
rank(**A**^{T}).

**Corollary: **
Every invertible matrix is a product of elementary matrices.

**A**is an invertible

*n*×

*n*matrix, then rank(

**A**) =

*n*. Hence, by Corollary, there exist invertible matrices

**X**and

**Y**such that

**Λ**=

**XAY**, where

**Λ**is the identity matrix of size

*n*, that is

**Λ**=

**I**.

As in the previous proof, not that **X** = **E**_{p}
**E**_{p-1} ... **E**_{1} and **Y** =
**G**_{1} **G**_{2} ... **G**_{q}, where
**E**_{i}'s and **G**_{j}'s are elementary matrices.
Hence,

**A**is the product of elementary matrices.

*Mathematica*finds its rank without a problem.

MatrixRank[A]

**A**from left by the elementary matrix

(E1.A ) // MatrixForm

(E1.A .G1) // MatrixForm

E3 = {{1, 0, 0}, {0, 1, 0}, {0, -2, 1}}

**A**is 2. ■

*n*. It has dimension

*n*+1. ■