# Prove that for any matrix $\bf A$ with $n$ columns, $\operatorname{nullity}(\mathbf{A}) + \operatorname{rank}(\mathbf{A}) = n$

$$\DeclareMathOperator{\nullity}{nullity}\DeclareMathOperator{\rank}{rank}$$

Theorem (3.34). The dimension theorem of matrices (rank-nullity theorem): If $$A$$ is a matrix with n columns (number of unknowns) then $$\nullity(\mathbf{A}) + \rank(\mathbf{A}) = n$$

My attempt:

Consider arbitrary matrix $$\bf A$$ with $$n$$ columns.

Let $$\mathbf R = \operatorname{rref}(\mathbf A)$$. Suppose $$\rank(\mathbf A) = n$$. It follows that $$\bf R$$ won't have columns without leading ones. Hence the only vector $$\bf x$$ that satisfies $$\bf Rx = O$$ is zero vector. Since $$\bf Rx = O$$ is equivalent to $$\bf Ax = O$$, solution set must be the same. And that means that null space of $$\bf A$$ consists of a single vector, $$\bf O$$. Hence $$\nullity(\mathbf{A}) = 0$$

We have $$\rank(\mathbf A) + \nullity(\mathbf{A}) = n + 0 = n$$

Let $$\mathbf R = \operatorname{rref}(\mathbf A)$$. Suppose $$\rank(\mathbf{A}) = m$$ where $$m < n$$. It implies that the linear system $$\bf Rx = O$$ will have $$n-m$$ free variables. Since $$\bf Rx = O$$ is equivalent $$\bf Ax = O$$, then $$\bf Ax = O$$ will have $$n-m$$ free variables too. And because number of free variables equals to nullity of the $$\bf A$$ (I tried to prove this proposition here), it follows that $$\nullity(\mathbf A) = n-m$$

We have $$\rank(\mathbf{A}) + \nullity(\mathbf{A}) = m + n - m = n$$ $$\Box$$

Is it correct?

It looks correct. It also looks like you don't need to consider the case where the rank is $$n$$ separately.