Does an arbitrary matrix $X \in M_{n \times p}$ have a SVD?

Question

I have proven, as below, that if $X \in M_{n \times n}$ is symmetric, then it has a SVD.

$D(\lambda_i) = \text{Diag}(\lambda_i)$ is a diagonal matrix with entries $\lambda_1, \lambda_2, \dots$.

$X^{\prime}$ denotes the transpose of $X$.

We say a square matrix $P$ is orthogonal if $P^{\prime} = P^{-1}$.

Theorem. Suppose $A \in M_{n \times n}$ is symmetric. Then there exists an orthogonal matrix $P$ such that $P^{\prime}AP = \text{Diag}(\lambda_i)$, where $\lambda_1, \lambda_2, \dots, \lambda_n$ are the eigenvalues of $A$.

Let $\{v_i\}_{i \in \{1, 2, \dots, n\}}$ be an orthonormal set of eigenvectors, each vector corresponding to an element in $\{\lambda_i\}_{i \in \{1, 2, \dots, n\}}$.

Let $P = \begin{bmatrix} v_1 & \cdots & v_n \end{bmatrix}$. Then \begin{align*} P^{\prime}AP = \begin{bmatrix} v^{\prime}_1 \\ \vdots \\ v^{\prime}_n \end{bmatrix}\begin{bmatrix} Av_1 & \cdots & Av_n \end{bmatrix} &= \begin{bmatrix} v^{\prime}_1 \\ \vdots \\ v^{\prime}_n \end{bmatrix}\begin{bmatrix} \lambda_1v_1 & \cdots & \lambda_nv_n \end{bmatrix} \\ &= \begin{bmatrix} \lambda_1 v^{\prime}_1 v_1 & \cdots & \lambda_n v^{\prime}_1 v_n \\ \vdots & \ddots & \vdots \\ \lambda_1 v^{\prime}_n v_1 & \cdots & \lambda_n v^{\prime}_n v_n \end{bmatrix}\\ &= \begin{bmatrix} \lambda_1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \lambda_n \end{bmatrix} \\ &= \text{Diag}(\lambda_i) \end{align*} since \begin{equation*} v^{\prime}_iv_j = v_i \cdot v_j = \begin{cases} 1, & i = j \\ 0, & i \neq j \end{cases} \end{equation*} due to orthonormality.

Corollary. Suppose $A \in M_{n \times n}$ is symmetric. Then, by Theorem, $A = PD(\lambda_i)P^{\prime}$. This is known as the singular value decomposition of $A$.

Since $P$ is orthogonal, it is invertible. Furthermore, $$ A = \left(P^{\prime}\right)^{-1}D(\lambda_i)P^{-1} = \left(P^{-1}\right)^{-1}D(\lambda_i)P^{\prime} = PD(\lambda_i)P^{\prime}\text{.} $$

Does this apply for arbitrary matrices (i.e., not necessarily symmetric nor square matrices)? I came up with this question after looking at this solution which is reliant on $X \in M_{n \times p}$ having a SVD.

I have seen this Wikipedia page which says that $A = B\text{Diag}(\text{something})C$, where $B$ is orthogonal and $\text{Diag}(\text{something})$ is a diagonal matrix (but does the diagonal necessarily have to consist of the eigenvalues of $A$?) and I have no idea what $C$, this "conjugate transpose" is.

Could someone help clarify the concept of a SVD for an arbitrary matrix and perhaps help me with a sketch of a proof?

Answer 1

I'll start with an explanation of "$*$". In general $A^*$ is called the adjoint of $A$. This is defined relative to some inner product, often the Euclidean one. It is characterized by the equation $(x,Ay)=(A^*x,y)$. For the real Euclidean inner product, the adjoint is the transpose. For the complex Euclidean inner product, the adjoint is the conjugate transpose, where you take the transpose and also take the conjugate of each element. Moving on to your question:

Yes. A good way to "read" the SVD, which is commonly written $A=U \Sigma V^*$, is through the action of $A$ and $A^*$ on the singular vectors. Specifically, the SVD tells you that

$$Av_i=\sigma_i u_i \\ A^* u_i=\sigma_i v_i$$

where $v_i$ is the $i$th column of $V$, $u_i$ is the $i$th column of $U$, and $\sigma_i$ is the $i$th singular value. From these equations you can see that $v$ is a right singular vector if and only if it is an eigenvector of $A^* A$, while $u$ is a left singular vector if and only if it is an eigenvector of $A A^*$. Now these matrices are Hermitian nonnegative definite, so they are diagonalizable with nonnegative eigenvalues by the spectral theorem. The singular values of $A$ are the square roots of these eigenvalues.

An important note here is that if $A$ is rectangular, then $A^* A$ and $A A^*$ don't have the same sizes. Consequently $U,\Sigma,V^*$ have different sizes too: when $A$ is $m \times n$, $U$ is $m \times m$, $\Sigma$ is $m \times n$, and $V^*$ is $n \times n$.

Note that this proof is actually rather constructive: it reduces the problem of finding the SVD to the eigenproblem for the matrix $\begin{bmatrix} 0 & A \\ A^* & 0 \end{bmatrix}$. This is not a practical algorithm for direct use, but more realistic algorithms can actually be designed using this observation.

One other correction: if $A$ is symmetric but has negative eigenvalues, then its SVD and its eigendecomposition are not the same, because singular values are always nonnegative. Instead, to convert from an eigendecomposition to an SVD, you "move the minus signs" into the eigenvector matrix, by writing $D=S \Sigma$ where $S$ is diagonal and its only entries are $1$ or $-1$. Then with $A=Q D Q^*$, you get $U=QS,V=Q$ in the SVD.

Reference: Numerical Linear Algebra by Trefethen and Bau.

Answer 2

Sketch of the proof:

The classical proof of the existence of the SVD is based on the fact that for any matrix $A$, there is a unit vector $v$ such that $$\tag{1} \sigma=\|Av\|_2=\max_{w:\|w\|_2=1}\|Aw\|_2\geq 0 $$ and using the induction. Given such a $v$, take a unit vector $u$ such that $Av=\sigma u$. Then you construct two square unitary matrices: $$ U_1=[u,\tilde{U}], \quad V_1=[v,\tilde{V}], $$ and compute $$ U_1^*AV_1=\pmatrix{u^*Av&u^*AV_1\\U_1^*Av&U_1^*AV_1}=\pmatrix{\sigma&z\\0&B}=:C. $$ First, one has to show now that $z=0$. We have $\|A\|_2=\sigma$. On the other hand, $\|A\|_2=^2\|C\|_2^2\geq\sigma^2+\|z\|_2^2$. This implies that $\|z\|_2=0$. Next, taking an induction hypothesis that $B$ has an SVD $B=U_2\Sigma_2V_2^*$, we get $$\tag{2} \color{red}{\underbrace{\pmatrix{1&\\&U_2^*}U_1^*}_{=U^*}}A\color{blue}{\underbrace{V_1\pmatrix{1&0\\&V_2}}_{=V}}=\pmatrix{\sigma&\\&\Sigma_2}=:\Sigma. $$ So we get unitary matrices $U$ and $V$ such that $U^*AV=\Sigma$ is diagonal, where the diagonal entries of $\Sigma$ are nonnegative which is precisely what SVD is: finding unitary bases of the domain and image of $A$ for which $A$ is represented by a diagonal matrix.

Answer 3

Your decomposition is even more than an SVD since it gives you not only singular values but eigen values of a square matrix.

SVD is a bit more general and applies to rectangular matrices (not only square) and allow to give a decomposition with unitary matrices $M=U\Sigma V^*$ (! not the same on left and right sides of the diagonal matrix, wich is not square).

The conjugate transpose is pretty simple. In case of real matrix, it is just the transpose. If it is complexe, you transpose plus take the complexe conjugate.