Rank and Invertibility

Concepts#

1. 1 Linear Mapwhat a matrix does: $x \mapsto Ax$, with kernel (lost inputs) and image (reached outputs) start here
2. 2 System of Linear Equationsthe problem $Ax = b$ whose solvability is at stake
3. 3 Matrix Rankthe number that classifies the matrix
4. 4 Invertible Matrixthe square, full-rank case
5. 5 Positive Semidefinite MatrixGram matrices $A^\top A$ are PSD, and positive definite exactly in the full column rank case

How it fits together#

For $A \in \mathbb{R}^{m \times n}$ and $r = \operatorname{rank}(A)$:

• Rank → invertibility: a matrix is invertible iff it is square and has full rank. The rank is the cause. $\det(A) \neq 0$ (Determinant), $\ker(A) = \{0\}$ and “no zero eigenvalue” are equivalent tests for a square $A$ (see the theorem in Invertible Matrix > Properties).
• Uniqueness vs. existence: full column rank ($\ker(A) = \{0\}$, the map is injective) gives uniqueness. Full row rank ($\operatorname{im}(A) = \mathbb{R}^m$, the map is surjective) gives existence. A square matrix needs both, but for a square matrix one implies the other.
• Why only square matrices: an inverse must undo the map in both directions, so the map must be bijective. A tall matrix ($m > n$) has $\dim\operatorname{im}(A) \le n < m$, so it is not surjective. A wide matrix ($m < n$) has $\dim\ker(A) \ge n - m > 0$, so it is not injective. Algebraically: $AB = I_m$ and $BA = I_n$ give $m = \operatorname{rank}(AB) \le \operatorname{rank}(A) \le n$ and $n = \operatorname{rank}(BA) \le \operatorname{rank}(A) \le m$, so $m = n$.
• Least squares (MSI): for $\min_\theta \|y - \Phi\theta\|^2$ with $\Phi \in \mathbb{R}^{N \times d}$, the normal equations $\Phi^\top\Phi\,\theta = \Phi^\top y$ have the square $d \times d$ matrix $\Phi^\top\Phi$. Since $\operatorname{rank}(\Phi^\top\Phi) = \operatorname{rank}(\Phi)$:
  • $\operatorname{rank}(\Phi) = d$ ⇒ $\Phi^\top\Phi \succ 0$ is invertible, and $\theta^* = (\Phi^\top\Phi)^{-1}\Phi^\top y$ is unique (MSI script p. 30).
  • $\operatorname{rank}(\Phi) < d$ ⇒ $\Phi^\top\Phi$ is singular, the problem is ill-posed and the minimizers form an affine set (MSI script p. 32).
• Definiteness as a rank test for Gram matrices: the chain behind the least squares case is $A^\top A \succcurlyeq 0$ always (since $x^\top A^\top A x = \|Ax\|_2^2$), with $x^\top A^\top A x = 0 \iff x \in \ker(A)$. So full column rank ⇔ $\ker(A) = \{0\}$ ⇔ $A^\top A \succ 0$ ⇔ $A^\top A$ invertible (Positive Semidefinite Matrix). Positive definiteness is the stronger, “quadratic” way of stating full rank for symmetric matrices.
• From system to matrix: a linear system becomes $Ax = b$ by writing one row per equation and one column per unknown. Its solvability then only depends on $\operatorname{rank}(A)$ vs. $\operatorname{rank}([A \mid b])$ and $n$, which is the table above read for a fixed $b$.

Exercises & Exam Questions#

Key Formulas#

• $\operatorname{rank}(A) + \dim\ker(A) = n$ (Matrix Rank)
• $A \in \mathbb{R}^{n \times n}$ invertible $\iff \operatorname{rank}(A) = n \iff \det(A) \neq 0$ (Invertible Matrix)
• $\operatorname{rank}(A^\top A) = \operatorname{rank}(A)$ (Matrix Rank)

Lectures#

• No lecture yet. MSI uses this material in script chapter 4 (linear least squares).