Rank-nullity theorem

Alicia Y. Tsai; Authors: Laurent EI Ghaoui; Contributors: Phan Hoang, Tony Tin, Ha To Tam, Nguyen Van Kep, Le Dinh Nam, Juliette Decugis, Nguyen Quoc Cuong.; Giuseppe C. Calafiore

Rank-nullity theorem

The nullity (dimension of the nullspace) and the rank (dimension of the range) of an $m \times n$ matrix $A$ add up to the column dimension of $A$ , $n$ .

Proof: Let $p$ be the dimension of the nullspace $\mathbf{N}(A)$ ( $p \le n$ ). Let $U_1$ be a $n \times p$ matrix such that its columns form an orthonormal basis of $\mathbf{N}(A)$ . In particular, we have $AU_1 = 0$ . Using the QR decomposition of the matrix $\begin{bmatrix} U_1 & I_{n} \end{bmatrix}$ , we obtain a $n \times (n-p)$ matrix $U_2$ such that the matrix $\begin{bmatrix} U_1 & U_2 \end{bmatrix}$ is orthogonal. Now define the $m \times (n-p)$ matrix $V := AU_2$ .

We proceed to show that the columns of $V$ form a basis for the range of $A$ . To do this, we first prove that the columns of $V$ span the range of $A$ . Then we will show that these $n-p$ columns are independent. This will show that the dimension of the range (that is, the rank) is indeed equal to $n-p$ .

Since $U$ is an orthonormal matrix, for any $x \in \mathbb{R}^n$ , there exist two vectors $x_1, x_2$ such that

$x = U_1x_1 + U_2x_2.$

If $x \in \mathbf{R}(A)$ , then

$Ax = AU_2x_2 = Vx_2 \in \mathbf{R}(V).$

This proves that the columns of $V$ span the range of $A$ :

$\mathbf{R}(A) = \mathbf{R}(V).$

Now let us show that the columns of $V$ are independent. Assume a vector $z$ satisfies $Vz = 0$ and let us show $z = 0$ . We have $Vz = AU_2 z = 0$ , which implies that $U_2z$ is in the nullspace of $A$ . Hence, there exists another vector $y$ such that $U_2z = U_1y$ . This is contradicted by the fact that $\begin{bmatrix} U_1 & U_2 \end{bmatrix}$ is an orthogonal matrix: pre-multiplying the last equation by $U_2^T$ , and exploiting the fact that