Rank of a matrix

Rank of a matrix#

Matrix spaces#

Let $\boldsymbol A \in \mathbb R^{m\times n}$ be a rectangular matrix. Define

nullspace of $\boldsymbol A$ as all solutions of the homogeneous linear system $\boldsymbol{Ax} = \boldsymbol 0$, i.e.,

\[ N(\boldsymbol A) = \{\boldsymbol x \in \mathbb R^n \colon \boldsymbol{Ax} = \boldsymbol 0\}; \]
left nullspace of $\boldsymbol A$ as all solutions of the homogeneous linear system $\boldsymbol y^\mathsf{T} \boldsymbol{A} = \boldsymbol 0$ (note that it is equal to $N(\boldsymbol A^\mathsf{T}))$;
column space of $\boldsymbol A = [\boldsymbol a_1 \ldots \boldsymbol a_n]$ as the spanning space of its columns:

\[ C(\boldsymbol A) = \mathrm{span}(\boldsymbol a_1, \ldots, \boldsymbol a_n) = \Big\{\sum\limits_{j=1}^n c_j \boldsymbol a_j \colon c_1, \ldots, c_n \in \mathbb R\Big\}. \]
row space of

\[\begin{split} \boldsymbol A = \begin{pmatrix} \boldsymbol a_1^\mathsf{T} \\ \vdots \\ \boldsymbol a_m^\mathsf{T} \end{pmatrix} \end{split}\]

as the spanning space of its rows:

\[ R(\boldsymbol A) = \mathrm{span}(\boldsymbol a_1^\mathsf{T}, \ldots, \boldsymbol a_m^\mathsf{T}) = \Big\{\sum\limits_{j=1}^m c_j \boldsymbol a_j^\mathsf{T} \colon c_1, \ldots, c_m \in \mathbb R\Big\}. \]

Note that $ R(\boldsymbol A) = C(\boldsymbol A^\mathsf{T})$. Also, both $N(\boldsymbol A)$ and $C(\boldsymbol A^\mathsf{T})$ are subspaces of $\mathbb R^n$, whereas $N(\boldsymbol A^\mathsf{T})$ and $C(\boldsymbol A)$ are subspaces of $\mathbb R^m$.

Rank#

There are two ways to define the rank of $\boldsymbol A \in \mathbb R^{m\times n}$:

column rank is $\dim C(\boldsymbol A)$;
row rank is $\dim C(\boldsymbol A^\mathsf{T})$.

These two definitions are equivalent as the following theorem states.

Fundamental theorem of linear algebra

For any matrix $\boldsymbol A \in \mathbb R^{m\times n}$ the following equality holds:

\[ \dim C(\boldsymbol A) = \dim C(\boldsymbol A^\mathsf{T}) = r, \quad 0\leqslant r \leqslant \min\{m, n\}, \]

Moreover,

\[ \dim C(\boldsymbol A) + \dim N(\boldsymbol A) = n, \quad \dim C(\boldsymbol A^\mathsf{T}) + \dim N(\boldsymbol A^\mathsf{T}) = m. \]

Proof of Rank Theorem

Permute the columns of $\boldsymbol A$ in such a way that its reduced echelon form is

\[\begin{split} \boldsymbol R = \begin{pmatrix} \boldsymbol I_r & \boldsymbol F \\ \boldsymbol 0 & \boldsymbol 0 \end{pmatrix}. \end{split}\]

To establish the equality $\dim C(\boldsymbol A) = \dim C(\boldsymbol A^\mathsf{T}) = r$ it is enough to show that

$\dim C(\boldsymbol A) = \dim C(\boldsymbol R)$;
$\dim C(\boldsymbol A^\mathsf{T}) = \dim C(\boldsymbol R^\mathsf{T})$;
$\dim C(\boldsymbol R) = \dim C(\boldsymbol R^\mathsf{T}) = r$.

The equality $\dim C(\boldsymbol R^\mathsf{T}) = r$ holds since the first $r$ rows of $\boldsymbol R$ are linearly independent (why?), whereas adding any of other $m-r$ zero rows would make them linearly dependent. On the other hand, each of the last $n-r$ columns of $\boldsymbol R$ is a linear combination of the first $r$ columns (why?), consequently, they form a basis in $C(\boldsymbol R)$. Hence, the third claim is proved.

The statement 2 holds because elemetary operations using in Gaussian elimination do not change the row space: $C(\boldsymbol A^\mathsf{T}) = C(\boldsymbol R^\mathsf{T})$.

The first proposition follows from the observation $N(\boldsymbol A) = N(\boldsymbol R)$, i.e., $\boldsymbol{Ax} = \boldsymbol 0$ iff $\boldsymbol{Rx} = \boldsymbol 0$, $\boldsymbol x \in \mathbb R^n$. Hence, linear combinations of columns of $\boldsymbol A$ and $\boldsymbol R$ with same indices are either both zero or both nonzero. Therefore, any two bases of $C(\boldsymbol A)$ and $C(\boldsymbol R)$ must be of equal size.

Full column rank matrices#

Прямоугольная матрица $\boldsymbol A \in \mathbb R^{m\times n}$ называется полноранговой по столбцам, если $\mathrm{rank}(\boldsymbol A) = n$. Такая матрица обладает следующими свойствами:

все столбцы матрицы $\boldsymbol A$ опорные;
ядро матрицы $\boldsymbol A$ нулевое;
однородная система уравнений $\boldsymbol {Ax} = \boldsymbol 0$ имеет только нулевое решение;
СЛАУ $\boldsymbol {Ax} = \boldsymbol b$ имеет не более одного решения.

Full row rank matrices#

Матрица полного ранга по строкам, для которой $\mathrm{rank}(\boldsymbol A) = m$, обладает следующими свойствами:

все строки матрицы $\boldsymbol A$ опорные;
$C(\boldsymbol A) = \mathbb R^m$;
СЛАУ $\boldsymbol {Ax} = \boldsymbol b$ имеет решение при любом $\boldsymbol b \in \mathbb R^m$;
$\dim N(\boldsymbol A) = n - m$.

Полноранговые квадратные матрица $\boldsymbol A \in \mathbb R^{n\times n}$ имеют ранг $n = r$. Этот класс матриц в точности совпадает с классом невырожденных матриц.

np.linalg.matrix_rank calculates the rank of a matrix:

import numpy as np
A = np.arange(1, 13).reshape(3, 4)
A

array([[ 1,  2,  3,  4],
       [ 5,  6,  7,  8],
       [ 9, 10, 11, 12]])

np.linalg.matrix_rank(A)

Pseudo inverse#

The Moore-Penrose pseudo inverse of $\boldsymbol A \in \mathbb R^{m\times n}$ is such a matrix $\boldsymbol A^\dagger \in \mathbb R^{n\times m}$ that satisfies the following $4$ properties:

$\boldsymbol{AA}^\dagger \boldsymbol A = \boldsymbol A$;
$\boldsymbol{A}^\dagger \boldsymbol A \boldsymbol{A}^\dagger =\boldsymbol{A}^\dagger$;
$(\boldsymbol{AA}^\dagger)^\mathsf{T} = \boldsymbol{AA}^\dagger$;
$(\boldsymbol{A}^\dagger \boldsymbol A)^\mathsf{T} = \boldsymbol{A}^\dagger \boldsymbol A$.

Note that

$\boldsymbol{A}^\dagger = \boldsymbol{A}^{-1}$ if $\boldsymbol A$ is a square invertible matrix;
$\boldsymbol{A}^\dagger = (\boldsymbol A^\mathsf{T}\boldsymbol A)^{-1} \boldsymbol A^\mathsf{T}$ if $m > n$ and $\boldsymbol A$ has full column rank;
$\boldsymbol{A}^\dagger = \boldsymbol A^\mathsf{T}(\boldsymbol A\boldsymbol A^\mathsf{T})^{-1} $ if $m < n$ and $\boldsymbol A$ has full row rank.

To get pseudo inversed matrix, call np.linalg.pinv:

A = np.array([[1, 2], [2, 4], [3, 6]])
np.linalg.pinv(A)

array([[0.01428571, 0.02857143, 0.04285714],
       [0.02857143, 0.05714286, 0.08571429]])

Exerices#

Find rank of the following matrices: $\boldsymbol 0_{m\times n}$, $\boldsymbol 1_{m\times n}$, $\boldsymbol I_n$.
Let $\boldsymbol A \in \mathbb R^{m\times n}$. Show that $N(\boldsymbol A)$ is a subspace in $\mathbb R^n$, i.e., if $\boldsymbol x, \boldsymbol y \in N(\boldsymbol A)$ then $\alpha\boldsymbol x + \beta\boldsymbol y \in N(\boldsymbol A)$ for all $\alpha, \beta \in \mathbb R$.
Let $\boldsymbol A \in \mathbb R^{m\times n}$. Show that $C(\boldsymbol A)$ is a subspace in $\mathbb R^m$, i.e., if $\boldsymbol x, \boldsymbol y \in C(\boldsymbol A)$ then $\alpha\boldsymbol x + \beta\boldsymbol y \in C(\boldsymbol A)$ for all $\alpha, \beta \in \mathbb R$.
Let $\boldsymbol A \in \mathbb R^{m\times n}$. Prove that $N(\boldsymbol A) = N(\boldsymbol A^{\mathsf T}\boldsymbol A)$.
Prove that for each one-rank matrix $\boldsymbol A = \boldsymbol{uv}^\mathsf{T}$ the equality $\mathrm{rank}(\boldsymbol A) = 1$ holds.
Prove that $\mathrm{rank}(\boldsymbol{AB}) \leqslant \min\{\mathrm{rank}(\boldsymbol A), \mathrm{rank}(\boldsymbol B)\}$. Give an examples of two matrices for which this inequality is strict.
Hint

To prove the inequality $\mathrm{rank}(\boldsymbol{AB}) \leqslant \mathrm{rank}(\boldsymbol B)$ write

\[ \boldsymbol B = [\boldsymbol b_1 \ldots \boldsymbol b_n], \quad \boldsymbol{AB} = [\boldsymbol {Ab}_1 \ldots \boldsymbol {Ab}_n], \]
```
and show that if a linear combination of columns of $\boldsymbol{B}$ is $\boldsymbol 0$ than the same is true for the similar linear combination of columns of $\boldsymbol{AB}$.
```
Let $\boldsymbol A \in \mathbb R^{m\times n}$. Prove that

\[ \mathrm{rank}(\boldsymbol A) = \mathrm{rank}(\boldsymbol A^\mathsf{T}) = \mathrm{rank}(\boldsymbol A^\mathsf{T} \boldsymbol A) = \mathrm{rank}(\boldsymbol A \boldsymbol A^\mathsf{T}). \]
Prove that $\boldsymbol{A}^\dagger = \boldsymbol{A}^{-1}$ if $\boldsymbol{A}$ is a square invertible matrix.