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. \]

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)
2

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:

  1. \(\boldsymbol{AA}^\dagger \boldsymbol A = \boldsymbol A\);

  2. \(\boldsymbol{A}^\dagger \boldsymbol A \boldsymbol{A}^\dagger =\boldsymbol{A}^\dagger\);

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

  4. \((\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#

  1. Find rank of the following matrices: \(\boldsymbol 0_{m\times n}\), \(\boldsymbol 1_{m\times n}\), \(\boldsymbol I_n\).

  2. 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\).

  3. 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\).

  4. Let \(\boldsymbol A \in \mathbb R^{m\times n}\). Prove that \(N(\boldsymbol A) = N(\boldsymbol A^{\mathsf T}\boldsymbol A)\).

  5. Prove that for each one-rank matrix \(\boldsymbol A = \boldsymbol{uv}^\mathsf{T}\) the equality \(\mathrm{rank}(\boldsymbol A) = 1\) holds.

  6. 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.

  7. 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}). \]
  8. Prove that \(\boldsymbol{A}^\dagger = \boldsymbol{A}^{-1}\) if \(\boldsymbol{A}\) is a square invertible matrix.