[latexpage]
Fundamental theorem of linear algebra
|
Let $A \in \mathbb{R}^{m \times n}$. The sets $\mathbf{N}(A)$ and $\mathbf{R}\left(A^T\right)$ form an orthogonal decomposition of $\mathbb{R}^n$, in the sense that any vector $x \in \mathbb{R}^n$ can be written as $$ In particular, we obtain that the condition on a vector $x$ to be orthogonal to any vector in the nullspace of $A$ implies that it must be in the range of its transpose: $$ |
Proof: The theorem relies on the fact that if a SVD of a matrix $A$ is
$$
A=U \tilde{S} V^T, \quad \tilde{S}=\mathbf{diag}\left(\sigma_1, \ldots, \sigma_r, 0, \ldots, 0\right)
$$
then an SVD of its transpose is simply obtained by transposing the three-term matrix product involved:
$$
A^T=\left(U \tilde{S} V^T\right)^T=V \tilde{S} U^T .
$$
Thus, the left singular vectors of $A$ are the right singular vectors of $A^T$.
From this we conclude in particular that the range of $A^T$ is spanned by the first $r$ columns of $V$. Since the nullspace of $A$ is spanned by the last $n-r$ columns of $V$, we observe that the nullspace of $A$ and the range of $A^T$ are two orthogonal subspaces, whose dimension sum to that of the whole space. Precisely, we can express any given vector $x$ in terms of a linear combination of the columns of $V$; the first $r$ columns correspond to the vector $z \in \mathbf{R}\left(A^T\right)$ and the last $n-r$ to the vector $y \in \mathbf{N}(A)$ :
$$
x=V\left(V^T x\right)=\underbrace{\sum_{i=1}^r \tilde{x}_i v_i}_{=z}+\underbrace{\sum_{i=r+1}^n \tilde{x}_i v_i}_{=y}, \quad \tilde{x}:=V^T x .
$$
This proves the first result in the theorem.
The last statement is then an obvious consequence of this first result: if $x$ is orthogonal to the nullspace, then the vector $y$ in the theorem above must be zero, so that $x \in \mathbf{R}\left(A^T\right)$.
