ConceptLinear Algebra used inMSIAI-written · not yet proofread

Matrix Rank

Also Rank · Rang · Rang einer Matrix

The rank of a matrix is the maximal number of linearly independent columns (equivalently, rows), i.e. the dimension of its column space.

Know these firstLinear Map

Properties#

Row rank = column rank: $\operatorname{rank}(A) = \operatorname{rank}(A^\top)$ . So the rank is also the maximal number of linearly independent rows.
Upper bound: $\operatorname{rank}(A) \le \min(m, n)$ $rank (A) \leq min (m, n)$ . With equality, $A$ $A$ has full rank:
- $\operatorname{rank}(A) = n$ : full column rank, i.e. the columns are linearly independent (only possible if $m \ge n$ ).
- $\operatorname{rank}(A) = m$ : full row rank, i.e. the rows are linearly independent (only possible if $m \le n$ ).
Rank–nullity theorem: $\operatorname{rank}(A) + \dim \ker(A) = n$ , with $\ker(A) = \{x \in \mathbb{R}^n \mid Ax = 0\}$ . Full column rank $\iff \ker(A) = \{0\}$ .
Gram matrix: $\operatorname{rank}(A^\top A) = \operatorname{rank}(A)$ . So the $n \times n$ matrix $A^\top A$ (always PSD) is invertible iff $A$ has full column rank. MSI uses this for least squares: $(\Phi^\top \Phi)^{-1}$ exists iff $\operatorname{rank}(\Phi) = d$ .
Via SVD: $\operatorname{rank}(A)$ equals the number of nonzero singular values of $A$ .
Computation: bring $A$ into row echelon form by Gaussian elimination. The rank is the number of nonzero rows (pivots). Row operations don’t change the rank.

Standard linear algebra. There’s no textbook in the subject’s sources: yet.
Use in MSI: MSI script p. 30 (pseudo inverse needs $\operatorname{rank}(\Phi) = d$ ), MSI script p. 34 (SVD of $A$ with $\operatorname{rank}(A) = r$ )
Exercise: MSI Sheet 00, task 1 (not published) (rank of a $3 \times 3$ system matrix)

Connections

Latent Semantic IndexingDBIS
Factorise, then truncate. The SVD writes $A = USV$ with $U \in \mathbb{R}^{m \times r}$ , $S \in \mathbb{R}^{r \times r}$ and $V \in \mathbb{R}^{r \times n}$ , where $r$ is the rank of $A$ . Some exams write $A = U S V^\top$ instead, so check… §
Eigenvalue
$Ax = \lambda x \iff Ax - \lambda I_n x = 0 \iff (A - \lambda I_n)x = 0$ , so (1) ⇔ (2). A nonzero solution exists iff $\ker(A - \lambda I_n) \neq \{0\}$ , iff $\operatorname{rank}(A - \lambda I_n) < n$ by rank–nullity (Matrix Rank), iff… §
Invertible Matrix
$\operatorname{rank}(A) = n$ (full rank). §
Linear Map
$\dim \operatorname{im}(A)$ is the rank, and $\operatorname{rank}(A) + \dim\ker(A) = n$ (rank–nullity). §
Positive Semidefinite Matrix
Gram matrices: for any $A \in \mathbb{R}^{n \times m}$ the matrix $A^\top A \in \mathbb{S}^m$ is positive semidefinite, and $A^\top A \succ 0 \iff \operatorname{rank}(A) = m$ (full column rank). In MSI:… §
Singular Value Decomposition
Rank: $\operatorname{rank}(A)$ = number of nonzero singular values (Matrix Rank). §
Rank and Invertibility
The rank counts the linearly independent columns of a matrix. Comparing it with the number of rows and columns tells you whether the matrix is invertible and how many solutions $Ax = b$ has. In MSI this decides whether a least squares prob… §
Matrix Rank — the number that classifies the matrix §