Polar Decomposition of Matrices with an Application in Deriving SVD (to be added in my linear algebra notes)

In this post I want to record a standard result in linear algebra that I haven't paid attention before---the polar decomposition. An immediate consequence that I come up with is the SVD decompsition theorem, which I prove as two consequences, one is for square matrices and one is for general matrices.

In what follows we say that a matrix $A$ is positive if $x\mapsto x\cdot Ax$ is always nonnegative, and strictly positive if $x\mapsto x\cdot Ax$ forms an inner product.

Digression. When we say that an operator $T:H\to H$ on a complex Hilbert space is positive: $\inner{Tx,x}\ge 0$ for every $x$, it is necessarily (i.e., can be proved to be) self-adjoint! The key is that we can always recover the value $\inner{Tx,y}$ by just knowing what is $\inner{Tx,x}$ for every $x\in H$, while this may not happen in real Hilbert spaces.

Theorem (Polar Decomposition). Let $A$ be an $n\times n$ matrix over $\F=\R$ or $\C$, then there is a unitary (orthogonal when $\F=\R$) matrix $U$ and a positive matrix $P$ such that \[
A=UP,
\] where $P=\sqrt{A^*A}$, the unique positive square root of the positive matrix $A^*A$.

Proof. First we observe that \[
\|\sqrt{A^*A}x\|^2=\inner{\sqrt{A^*A}x, \sqrt{A^*A}x} = \inner{x,A^*Ax}=\inner{Ax,Ax}=\|Ax\|^2,
\] therefore $\|\sqrt{A^*A}x\|= \|Ax\|$. Now we define an isometry: \[
S_1:\range \sqrt{A^*A} \to \range A; \quad \sqrt{A^*A}x\mapsto Ax,
\] this map is automatically well-defined since it preserves norm. Namely, if $\sqrt{A^*A}x=\sqrt{A^*A}y$, then \[\|\sqrt{A^*A}(x-y)\|=\|A(x-y)\|=0,\] so $Ax=Ay$.

Now if we can extend $S_1$ to a unitary operator $S$ on $\F^n$, then we will have for every $x\in \F^n$, \[
S(\sqrt{A^*A}x)=S_1(\sqrt{A^*A}x)=Ax,
\] and we will be done. Note that since $S_1$ is injective, $\dim \range \sqrt{A^*A}=\dim \range S_1$ necessarily. Recall that extending unitary $T:U\to V$ (with $\dim U=\dim V$) "unitarily" to whole vector space is the same as defining unitary operator $T':U^\perp \to V^\perp$ with $T\oplus T'$ as an extension of $T$, which will be easily done in the next paragraph.

We let $\{u_1,\dots,u_k\}$ be an orthonormal basis of $(\range \sqrt{A^*A})^\perp$ and $\{v_1,\dots,v_k\}$ be that of $(\range S_1)^\perp$. We can also define \[
S_2: (\range \sqrt{A^*A})^\perp\to (\range S_1)^\perp;\quad a_1u_1+\cdots+a_ku_k\mapsto a_1v_1+\cdots+a_kv_k.
\] Finally we define $S=S_1\oplus S_2$. It is a direct verification that $S$ preserves length: for $u\in \text{dom } S_1$ and $v\in \text{dom } S_2$, we have \[
\|S(u+v)\|^2=\|Su+Sv\|^2 = \|S_1u+S_2v\|^2 = \|S_1u\|^2+\|S_2v\|^2,
\] since $u=\sqrt{A^*A}x$ for some $x\in \F^n$ and $\|S_2v\|=\|v\|$, we have \begin{align*}
\|S(u+v)\|^2 &= \|S_1(A^*Ax)\|^2+\|v\|^2\\
&=\|Ax\|^2 + \|v\|^2 \\
&= \|\sqrt{A^*A}x\|^2 +\|v\|^2\\
&=\|u\|^2+\|v\|^2 = \|u+v\|^2,
\end{align*}as desired. Since preserving length is the same as preserving inner product, thus $S$ must be unitary.$\qed$

Remark. A similar statement holds for every bounded linear operator $T:H\to H$ on a Hilbert space $H$, with unitary $U$ here replaced by partial isometry.

Consequence 1. For every $n\times n$ matrix $A$, the matrix $\sqrt{A^*A}$ is often called the positive part of $A$. Since it is analogues to decomposition of complex number that $z=e^{i\theta}|z|$, it is also common to denote $|A|=\sqrt{A^*A}$, therefore for every matrix $A$, there is a unitary matrix $U$ such that $A=U|A|$. With this notation, it can be easily checked that a matrix is normal if and only if $|A|=|A^*|$ (set $A=UP$, say).$\qed$

Consequence 2 (Singular Value Decomposition---SVD---of Square Matrices). The baby version of SVD can also be obtained from Polar Decomposition. Let $A$ be any $n\times n$ matrix over $\F$, then $A=S|A|$ for some unitary (orthogonal when $\F=\R$) matrix $S$. We may assume $A\neq 0$, since $|A|$ is positive definite, by Spectral Theorem there is a unitary matrix (orthogonal when $\F=\R$) $V$ and diagonal $\Sigma$ such that \[
A=S[V\Sigma V^*] = (SV) \Sigma V^* = U\Sigma V^*,
\] where $U=SV$ is unitary (orthogonal when $\F=\R$). If we further arrange columns of $V$ such that $\Sigma=\text{diag}(\sigma_1,\dots,\sigma_n)$ with $\sigma_1\ge \sigma_2\ge\cdots \ge \sigma_n\ge 0$, then the decomposition above is exactly the baby version of SVD (which applies for matrix of arbitrary dimension).$\qed$

Consequence 3 (SVD of General Matrices). The work below will be very messy. In order not to insert "(orthogonal when $\F=\R$)" everytime, let me use the term $\F$-unitary with obvious meaning.

Now suppose that $A$ is an $m\times n$ matrix, w.l.o.g. let's assume $m>n$ (otherwise consider $A^T$). Extend $A$ to a square by adjoining it an $m\times (m-n)$ 0 matrix $O$, then by consequence 2 there are $m\times m$ dimensional $\F$-unitary $U$ and $V$ such that \begin{equation}\label{mul here}
\begin{bmatrix} A&O\end{bmatrix}=U\Sigma V^*,
\end{equation} where $\Sigma=\text{diag}(\sigma_1,\dots,\sigma_m)$ with $\sigma_1\ge \sigma_2\ge \cdots \ge \sigma_m\ge 0$.

By our definition, for every $i>n$, \[
0 = U\Sigma V^* e_i=U\brac{\sum_{k=1}^m \sigma_k e_kv_k^*(e_i)},
\] since $U$ is invertible, we have \[
\sigma_k v_k^*(e_i)=0 \text{ for each }k=1,2,\dots, m\text{ and for each }i>n.
\]In particular, if $\rank A=r$, then $\sigma_{r+1}=0$ (and then $\sigma_i=0$ for every $i > r$), and we then have $v_k^*(e_i)=0$ for every $k=1,2,\dots,r$ and $i>n$. In other words, \begin{equation}\label{recall this}
v_1,\dots v_r\in \F^n\times \{0_{m-n}\}.
\end{equation}
Now multiplying both sides of (\ref{mul here}) by $\begin{bmatrix}I_{n\times n}\\ O\end{bmatrix}$, we have
\[
A = U\Sigma V^*_{m\times n},
\] where $V^*_{m\times n}$ is the left $m\times n$ part of the matrix $V^*$. Denote $D=\text{diag}(\sigma_1,\dots,\sigma_n)$---the upper left $n\times n$ part of $\Sigma$, then \[
A=U
\begin{bmatrix}
D&O_{n,m-n}\\
O_{m-n,n}&O_{m-n,m-n}
\end{bmatrix}  V^*_{m\times n}= U\begin{bmatrix}
DV_{n\times n}^*\\
O_{m-n,n}
\end{bmatrix}=U\begin{bmatrix}
D\\
O
\end{bmatrix} V_{n\times n}^*,
\] where $V_{n\times n}^*$ denotes the upper left $n\times n$ part of $V^*$.

We are almost there, except the fact that $V_{n\times n}^*$ is not necessarily $\F$-unitrary. But we can always rearrange $V$, if necessary, to achieve this. For this, let's study the term $DV_{n\times n}^*$.

Since $\sigma_i=0$ for $i>r$, we have  \[
DV_{n\times n}^* = \begin{bmatrix}
\sigma_1 v_1'^*\\
\vdots \\
\sigma_rv_r'^*\\
0\cdot v_{r+1}'^*\\
\vdots \\
0\cdot v_{n}'^*
\end{bmatrix},\]
where $v'$ means the first $n$ coordinates of $v\in \F^m$. We may replace $v_{r+1},\dots,v_n\in \F^m$ freely such that $v_1,\dots,v_n$ form an orthogonal basis of $\F^n\times \{0_{m-n}\}$ (recall (\ref{recall this})) without changing $DV_{n\times n}^*$, thus we may assume $V_{n\times n}^*$ itself is $\F$-unitary, and we are done.$\qed$