How unique are $U$ and $V$ in the singular value decomposition $A=UDV^\dagger$?

Question

According to Wikipedia:

A common convention is to list the singular values in descending order. In this case, the diagonal matrix $\Sigma$ is uniquely determined by $M$ (though the matrices $U$ and $V$ are not).

My question is, are $U$ and $V$ uniquely determined up to some equivalence relation (and what equivalence relation)?

Answer 1

Let $A = U_1 \Sigma V_1^* = U_2 \Sigma V_2^*$. Let us assume that $\Sigma$ has distinct diagonal elements and that $A$ is tall. Then

$$A^* A = V_1 \Sigma^* \Sigma V_1^* = V_2 \Sigma^* \Sigma V_2^*.$$

From this, we get

$$\Sigma^* \Sigma V_1^* V_2 = V_1^* V_2 \Sigma^* \Sigma.$$

Notice that $\Sigma^* \Sigma$ is diagonal with all different diagonal elements (that's why we needed $A$ to be tall) and $V_1^* V_2$ is unitary. Defining $V := V_1^* V_2$ and $D := \Sigma^* \Sigma$, we have

$$D V = V D.$$

Now, since $V$ and $D$ commute, they have the same eigenvectors. But, $D$ is a diagonal matrix with distinct diagonal elements (i.e., distinct eigenvalues), so it's eigenvectors are the elements of the canon basis. That means that $V$ is diagonal too, which means that

$$V = \operatorname{diag}(e^{{\rm i}\varphi_1}, e^{{\rm i}\varphi_2}, \dots, e^{{\rm i}\varphi_n}),$$

for some $\varphi_i$, $i=1,\dots,n$.

In other words, $V_2 = V_1 V$. Plug that back in the formula for $A$ and you get

$$A = U_1 \Sigma V_1^* = U_2 \Sigma V_2^* = U_2 \Sigma V^* V_1^* = U_2 V^* \Sigma V_1^*.$$

So, $U_2 = U_1 V$ if $\Sigma$ (and, in extension, $A$) is square nonsingular. Other options, somewhat similar to this, are possible if $\Sigma$ has zeroes on the diagonal and/or is rectangular.

If $\Sigma$ has repeating diagonal elements, much more can be done to change $U$ and $V$ (for example, one or both can permute corresponding columns).

If $A$ is not thin, but wide, you can do the same thing by starting with $AA^*$.

So, to answer your question: for a square, nonsingular $A$, there is a nice relation between different pairs of $U$ and $V$ (multiplication by a unitary diagonal matrix, applied in the same way to the both of them). Otherwise, you get quite a bit more freedom, which I believe is hard to formalize.

Answer 2

I will complete the proof of @Vedran for the case when there exist repeating eigenvalues, which would justify what @glS have said. Let $A = U \Sigma V^T = U^{'} \Sigma {V^{'}}^T$ be a matrix with real entries - the case with complex entries is similar. Then, $$A^T A = V \Sigma^T \Sigma V^{T} = V^{'} \Sigma^T \Sigma {V^{'}}^T.$$

From this, we get $$\Sigma^T \Sigma V^T V^{'} = V^T V^{'} \Sigma^T \Sigma.$$ Defining the square matrix $Q$ as $Q = V^T V^{'}$, we have $Q^T Q = (V^T V^{'})^T V^T V^{'} = I$, and similarly, $Q Q^T = I.$ Hence, $Q$ is an orthogonal matrix that satisfies the Sylvester equation $$Q\Sigma^T\Sigma - \Sigma^T \Sigma Q = 0.\tag{1}$$

Aiming to simplify the Sylvester equation (1) a little, counting the multiplicities, we can write $\Sigma^T \Sigma $ $= \sigma_1^2 I_{n_1} \oplus \sigma_2^2 I_{n_2} \oplus \cdots $ $ \oplus \sigma_{k}^2 I_{n_k} $ $= \text{diag}(\sigma_1^2 I_{n_1}, \sigma_2^2 I_{n_2},$ $ \cdots, \sigma_{k}^2 I_{n_k}),$ with $\sigma_i=\sigma_j$ iff $i=j$ and $n_i$ the multiplicity of $\sigma_{i}$.

Now, writing $Q$ in blocks conformally to $\Sigma^T \Sigma$, i.e., with $Q \Sigma^T \Sigma$ and $\Sigma^T \Sigma Q$ making sense, we have a new system of Sylvester equations $$\sigma_i^2 Q_{ij} I_{n_i} - \sigma_j^2 I_{n_j} Q_{ij}=0,$$ for each $1\leq i,j\leq k$. This means that, since both matrices $\sigma_i^2 I_{n_i}$ and $\sigma_j^{2}I_{n_j}$ do not share any of its eigenvalues for $i\not=j,$ by the result discussed here, if $i\not= j$, we have necessarily that $Q_{ij} = 0$. This means that $V^T V^{'} = \text{diag} (Q_{11}, Q_{22},\cdots, Q_{kk})$ for orthogonal matrices $Q_{ii}$, meaning that $$V' = V \text{diag}(Q_{11}, Q_{22},\cdots, Q_{kk})=V Q.\tag{2}$$

We can repeat the argument above for the matrix $A A^T$ and conclude that there exist an orthogonal matrix $\bar{Q}$ such that $$\bar{Q} = \text{diag}(\bar{Q}_{11}, \bar{Q}_{22},\cdots, \bar{Q}_{kk})\tag{3}$$ and $U' = U \bar{Q},$ with the matrices $\bar{Q}_{ii}$ of the same size of $Q_{ii}$ whenever $\sigma_i\not=0$ - this is possible because the matrices $A^T A$ and $A A^T$ have the same eigenvalues with the same multiplicity, except possibly the null eigenvalue. Taking into account that $A = U \Sigma V^T = U^{'} \Sigma {V^{'}}^T$, we would be able to conclude $\Sigma = U^T U^{'} \Sigma {V^{'}}^T V = U^T U \bar{Q} \Sigma Q^T V^T V,$ which simplifies to $$\Sigma = \bar{Q} \Sigma Q^T. $$ Lastly, considering the nonzero blocks of $\Sigma$ associated with the matrices $Q_{ii}$ and $\bar{Q}_{ii}$, we are able to conclude that $\bar{Q}_{ii} = Q_{ii}$ in the expression (3), whenever $\sigma_i\not=0$.

Answer 3

$\newcommand\R{\mathbb{R}}$I see that this question has been asked a few times. I'd like to provide a simple answer to this.

The singular values $s_1, \dots, s_k$ of an $n$-by-$m$ matrix $M$ are the square roots of the positive eigenvalues of $M^*M$. Let $d_1, \dots, d_k$ be the respective dimensions of the eigenspaces, and $d_{k+1}$ be the dimension of the kernel. Observe that $r = d_1+\cdots + d_k$ is the rank of $M$.

If $$ M = U\Sigma V^* $$ is a singular decomposition, then $M^*M = V\Sigma^2V^*$, and therefore the columns of $V$ form a unitary basis of eigenvectors $(v_1, \dots, v_m)$. $V$ is clearly unique up to unitary transformations of each eigenspace.

Now, for each $1 \le j \le k$, let $w_j = Mv_j$ and observe that for any $1 \le i,j \le r$, $$ \langle w_i,w_j\rangle = \langle Mv_i,Mv_j\rangle = \langle v_i,M^*Mv_j\rangle = \lambda_j\langle v_i,v_j\rangle = \lambda_j\delta_{ij}, $$ where the $\lambda_j$ are the singular values listed with the appropriate multiplicities. Therefore, $$ u_j = \frac{w_j}{\lambda_j},\ 1 \le j \le r $$ are a unitary basis of the image of $M$. They can be extended to a unitary basis $(u_1, \dots, u_n)$ of $\R^n$. It is now easy to show that the matrix $U$ whose columns are $u_1, \dots, u_n$ satisfies the equation $$ M = U\Sigma V^*.$$ It is also easy to show that conversely, if $$ M = U\Sigma V^*, $$ then, for each $1 \le j \le r$, then $$ \lambda_j u_j = Mv_j,$$ and $u_{r+1}, \dots, u_n$ are a unitary basis of the orthogonal complement of the image of $M$. It follows that given any $V$ satisfying the conditions above, the first $r$ columns of $U$ are uniquely determined and the last $n-r$ columns can be any unitary basis of $(\operatorname{image} M)^\perp$.

From all this, we see that $U$ and $V$ are unique up to unitary transformations of the eigenspaces of $M^*M$ and unitary transformations of $(\operatorname{image} M)^\perp$.