uniolympiads Ελληνικά

Rank

The rank–nullity theorem, the inequalities for rank⁡(AB)\rank(AB) and rank⁡(A+B)\rank(A + B), rank-one matrices, and what AB=0AB = 0 tells you.

What to know by heart

For A∈Mm×n(F)A \in \M_{m \times n}(\F), the rank is rank⁡A=dim⁡Im⁡A\rank A = \dim \operatorname{Im} A, and it equals the rank of A⊤A^\top.

  • Rank–nullity: rank⁡A+dim⁡ker⁡A=n\rank A + \dim \ker A = n.
  • Product: rank⁡(AB)≤min⁡(rank⁡A,rank⁡B)\rank(AB) \le \min(\rank A, \rank B). Multiplying by an invertible matrix does not change the rank.
  • Sylvester: for A∈Mm×nA \in \M_{m \times n}, B∈Mn×pB \in \M_{n \times p},  rank⁡A+rank⁡B−n≤rank⁡(AB)\ \rank A + \rank B - n \le \rank(AB).
  • Sum: rank⁡(A+B)≤rank⁡A+rank⁡B\rank(A + B) \le \rank A + \rank B, because Im⁡(A+B)⊆Im⁡A+Im⁡B\operatorname{Im}(A + B) \subseteq \operatorname{Im} A + \operatorname{Im} B.
  • Rank one: rank⁡K=1\rank K = 1 if and only if K=uv⊤K = u v^\top with u,v≠0u, v \ne 0. Then tr⁡K=v⊤u\tr K = v^\top u and K2=(tr⁡K) KK^2 = (\tr K)\, K.
  • Over R\R: rank⁡(A⊤A)=rank⁡A\rank(A^\top A) = \rank A, because A⊤Ax=0⇒x⊤A⊤Ax=∥Ax∥2=0⇒Ax=0A^\top A x = 0 \Rightarrow x^\top A^\top A x = \|Ax\|^2 = 0 \Rightarrow Ax = 0.

When to use it

  • AB=0AB = 0 with A,B∈MnA, B \in \M_n: by Sylvester, rank⁡A+rank⁡B≤n\rank A + \rank B \le n. Equivalently, Im⁡B⊆ker⁡A\operatorname{Im} B \subseteq \ker A.
  • Idempotent matrices (A2=AA^2 = A): rank⁡A=tr⁡A\rank A = \tr A. The eigenvalues are 00 or 11, AA is diagonalisable, and tr⁡A\tr A counts the ones. Also rank⁡A+rank⁡(I−A)=n\rank A + \rank(I - A) = n.
  • A rank-one difference, e.g. rank⁡(A−B)=1\rank(A - B) = 1: write A−B=uv⊤A - B = u v^\top, so that the whole problem goes through one vector. See the move "Rank one".
  • An image inside a kernel: after a relation AB=0AB = 0 or A2=0A^2 = 0, the goal becomes a comparison of dimensions.

Pitfalls

  • rank⁡(A⊤A)=rank⁡A\rank(A^\top A) = \rank A fails over C\C with plain transposition. For A=(1i00)A = \begin{pmatrix} 1 & i \\ 0 & 0 \end{pmatrix} we have AA⊤=0A A^\top = 0, while rank⁡A=1\rank A = 1. Over C\C it holds with the conjugate transpose A∗A^*.
  • rank⁡(A2)\rank(A^2) is not determined by rank⁡A\rank A. (0100)\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} and (1000)\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} both have rank 1, with squares of rank 0 and 1.
  • Rank is not the number of non-zero eigenvalues, unless the matrix is diagonalisable. A nilpotent matrix ≠0\ne 0 has positive rank and only zero eigenvalues.

Further reading

  • Axler, Linear Algebra Done Right, 4th ed., §3B (Null Spaces and Ranges)
  • Gelca & Andreescu, Putnam and Beyond, §2.3.5 (Vector Spaces, Linear Combinations of Vectors, Bases)

Contest problems using these tools

No problems with these tools yet.