# How unique are $U$ and $V$ in the Singular Value Decomposition?

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

• Do you understand why $U$ and $V$ are not uniquely determined? Think about what happens if $\Sigma$ is not regular, which means that some eigenvalues are zero. Or what happens if you have multiple eigenvalues. – Marc Jan 19 '14 at 23:29
• @Marc *singular values. ;-) – Vedran Šego Jan 20 '14 at 0:25
• Oops, of course. Thanks for the correction. – Marc Jan 20 '14 at 0:35
• The two posts address the phase ambiguities explicitly: math.stackexchange.com/questions/2287795/…, math.stackexchange.com/questions/1805191/… – dantopa Jun 10 '17 at 23:07

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.

• I believe that if there are repeated singular values, you just simply use "small" unitary matrices instead of the factors $e^{\mathrm{i}\varphi}$, that is, $V$ is block diagonal instead (of course, assuming that the singular values are properly ordered). – Algebraic Pavel Jan 20 '14 at 10:38
• @AlgebraicPavel Yes, you are right. Such small matrices then correspond to linear combinations that keep the unitarity. These can be random, and completely different between $U$ and $V$. – Vedran Šego Jan 20 '14 at 12:28
• very good answer, thanks! So I meant to think this through on my own, but I haven't gotten around to it, so I will ask: Is it just that any such pairs are related in this way, OR can you multiply any U and V by ANY unitary diagonal matrix and get another valid U1, V1 that would SVD the original matrix A? – capybaralet Jan 25 '14 at 19:56
• If you have an SVD of $A$, you can multiply its $U$ and $V$ by a diagonal unitary matrix (the same one for each!). However, sometimes you can do even more, as discussed in my answer and Pavel's comment. – Vedran Šego Jan 25 '14 at 22:00

### SVD in dyadic notation removes "trivial" redundancies

The SVD of an arbitrary matrix $$A$$ can be written in dyadic notation as $$A=\sum_k s_k u_k v_k^*,\tag A$$ where $$s_k\ge0$$ are the singular values, and $$\{u_k\}_k$$ and $$\{v_k\}_k$$ are orthonormal sets of vectors spanning $$\mathrm{im}(A)$$ and $$\ker(A)^\perp$$, respectively. The connection between this and the more standard way of writing the SVD of $$A$$ as $$A=UDV^\dagger$$ is that $$u_k$$ is the $$k$$-th column of $$U$$, and $$v_k$$ is the $$k$$-th column of $$V$$.

### Global phase redundancies are always present

If $$A$$ is nondegenerate, the only freedom in the choice of vectors $$u_k,v_k$$ is their global phase: replacing $$u_k\mapsto e^{i\phi}u_k$$ and $$v_k\mapsto e^{i\phi}v_k$$ does not affect $$A$$.

### Degeneracy gives more freedom

On the other hand, when there are repeated singular values, there is additional freedom in the choice of $$u_k,v_k$$, similarly to how there is more freedom in the choice of eigenvectors corresponding to degenerate eigenvalues. More precisely, note that (A) implies $$AA^\dagger=\sum_k s_k^2 \underbrace{u_k u_k^*}_{\equiv\mathbb P_{u_k}}, \qquad A^\dagger A=\sum_k s_k^2 \mathbb P_{v_k}.$$ This tells us that, whenever there are degenerate singular values, the corresponding set of principal components is defined up to a unitary rotation in the corresponding degenerate eigenspace. In other words, the set of vectors $$\{u_k\}$$ in (A) can be chosen as any orthonormal basis of the eigenspace $$\ker(AA^\dagger-s_k^2)$$, and similarly $$\{v_k\}_k$$ can be any basis of $$\ker(A^\dagger A-s_k^2)$$.

However, note that a choice of $$\{v_k\}_k$$ determines $$\{u_k\}$$, and vice-versa (otherwise $$A$$ wouldn't be well-defined, or injective outside its kernel).

### TL;DR

A choice of $$U$$ uniquely determines $$V$$, so we can restrict ourselves to reason about the freedom in the choice of $$U$$. There are twe main sources of redundancy:

1. The vectors can be always scaled by a phase factor: $$u_k\mapsto e^{i\phi_k}u_k$$ and $$v_k\mapsto e^{i\phi_k}v_k$$. In matrix notation, this corresponds to changing $$U\mapsto U \Lambda$$ and $$V\mapsto V\Lambda$$ for an arbitrary diagonal unitary matrix $$\Lambda$$.
2. When there are "degenerate singular values" $$s_k$$ (that is, singular values corresponding to degenerate eigenvalues of $$A^\dagger A$$), there is additional freedom in the choice of $$U$$, which can be chosen as any matrix whose columns form a basis for the eigenspace $$\ker(AA^\dagger-s_k^2)$$.

Finally, we should note that the former point is included in the latter, which therefore encodes all of the freedom allowed in choosing the vectors $$\{v_k\}$$. This is because multiplying the elements of an orthonormal basis by phases does not affect its being an orthonormal basis.