Fundamental theorem of linear algebra

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

    \[x=y+z, y \in \mathbf{N}(A), \quad z \in \mathbf{R}\left(A^T\right), \quad y^T z=0 .\]

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:

    \[x^T y=0 \text { whenever } A y=0 \Longleftrightarrow \exists \lambda \in \mathbb{R}^m: x=A^T \lambda \text {. }\]

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).

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