[latexpage]

Rank-nullity theorem

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. \]