Rank-nullity theorem

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

    \[U_2^T U_2 = I_{n-p}\), \(U_2^T U_1 = 0,\]

we obtain

    \[ z = U_2^T U_2 z = U_2^T U_1 y = 0. \]

License

Icon for the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

Linear Algebra and Applications Copyright © 2023 by VinUiversity is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, except where otherwise noted.

Share This Book