Feeds:
Posts

## Singular value decomposition

As a warm-up to the subject of this blog post, consider the problem of how to classify $n \times m$ matrices $M \in \mathbb{R}^{n \times m}$ up to change of basis in both the source ($\mathbb{R}^m$) and the target ($\mathbb{R}^n$). In other words, the problem is to describe the equivalence classes of the equivalence relation on $n \times m$ matrices given by

$\displaystyle M \sim N \Leftrightarrow M = PNQ^{-1}, P \in GL_n(\mathbb{R}), Q \in GL_m(\mathbb{R})$.

It turns out that the equivalence class of $M$ is completely determined by its rank $r = \text{rank}(M)$. To prove this we construct some bases by induction. For starters, let $x_1 \in \mathbb{R}^m$ be a vector such that $y_1 = M x_1 \neq 0$; this is always possible unless $M = 0$. Next, let $x_2 \in \mathbb{R}^m$ be a vector such that $y_2 = M x_2$ is linearly independent of $y_1$; this is always possible unless $\text{rank}(M) = 1$.

Continuing in this way, we construct vectors $x_1, \dots x_r \in \mathbb{R}^m$ such that the vectors $y_1 = M x_1, \dots y_r = M x_r \in \mathbb{R}^n$ are linearly independent, hence a basis of the column space of $M$. Next, we complete the $x_i$ and $y_i$ to bases of $M$ in whatever manner we like. With respect to these bases, $M$ takes a very simple form: we have $M x_i = y_i$ if $1 \le i \le r$ and otherwise $M x_i = 0$. Hence, in these bases, $M$ is a block matrix where the top left block is an $r \times r$ identity matrix and the other blocks are zero.

Explicitly, this means we can write $M$ as a product

$\displaystyle M = PDQ^{-1}, P \in GL_n(\mathbb{R}), Q \in GL_m(\mathbb{R})$

where $D$ has the block form above, the columns of $P$ are the basis of $\mathbb{R}^n$ we found by completing $M x_1, \cdots M x_r$, and the columns of $Q$ are the basis of $\mathbb{R}^m$ we found by completing $x_1, \cdots x_r$. This decomposition can be computed by row and column reduction on $M$, where the row operations we perform give $P$ and the column operations we perform give $Q$.

Conceptually, the question we’ve asked is: what does a linear transformation $T : X \to Y$ between vector spaces “look like,” when we don’t restrict ourselves to picking a particular basis of $X$ or $Y$? The answer, stated in a basis-independent form, is the following. First, we can factor $T$ as a composite

$\displaystyle X \xrightarrow{p} \text{im}(T) \xrightarrow{i} Y$

where $\text{im}(T)$ is the image of $T$. Next, we can find direct sum decompositions $X \cong \text{im}(T) \oplus X'$ and $Y \cong \text{im}(T) \oplus Y'$ such that $p$ is the projection of $X$ onto its first factor and $i$ is the inclusion of the first factor into $Y$. Hence every linear transformation “looks like” a composite

$\displaystyle \text{im}(T) \oplus X' \xrightarrow{p_{\text{im}(T)}} \text{im}(T) \xrightarrow{i_{\text{im}(T)}} \text{im}(T) \oplus Y$

of a projection onto a direct summand and an inclusion of a direct summand. So the only basis-independent information contained in $T$ is the dimension of the image $\text{im}(T)$, or equivalently the rank of $T$. (It’s worth considering the analogous question for functions between sets, whose answer is a bit more complicated.)

The actual problem this blog post is about is more interesting: it is to classify $n \times m$ matrices $M \in \mathbb{R}^{n \times m}$ up to orthogonal change of basis in both the source and the target. In other words, we now want to understand the equivalence classes of the equivalence relation given by

$\displaystyle M \sim N \Leftrightarrow M = UNV^{-1}, U \in O(n), V \in O(m)$.

Conceptually, we’re now asking: what does a linear transformation $T : X \to Y$ between finite-dimensional Hilbert spaces “look like”?