Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose $\mathcal{D}_N$ denote an $N\times N$ doubly stochastic matrix, given any element $M\in \mathcal{D}_N$ , the singular value decomposition for $M$ is $$ M=USV'$$

where $U$ and $V$ are two $N\times N$ orthogonal matrix and $S$ is a $N \times N$ diagonal matrix

Let $P$ be the 'closest' orthogonal matrix to $M$, i.e. $P=\arg\min_{X\in\mathcal{O}}||X-M||_F^2$,$\mathcal{O}$ represents the $N\times N$ orthogonal matrix set. Note such $P$ may be not unique. In this case, we choose any of it. On conclusion about $P$ is $P=UV'$, where $U$ and $V$ are defined before(although can be not unique, we just choose any of them)

$M_1 \in \mathcal{D}_N$, which is 'closest' to $P$. More specifically

$$ M_1 = \arg\min_{X\in\mathcal{D}} ||X - P||_F ^2 $$ Similarly, If $M_1$ is not unique, we choose any of it(This should not happen actually. Since we may image it as a 'ball' approaching a 'polygon', should have only one minimum)

My question is :

The statement: $M_1=M$ if and only if $M$ is a permutation matrix

Does this statement always hold true?

Actually, if $M$ is a permutation matrix, $M_1=M$, this is obvious, since $S=I$, and $P=M$. However, does another direction always hold true? If so, how to prove this, otherwise, how to give a counter-example?

Thanks for any suggestions!

share|cite|improve this question

Unless you specify some condition fixing a unique singular value decomposition you want to use, your $P$ is not well-defined for non-permutation doubly stochastic matrices.

For instance, $$ \frac12\,\begin{bmatrix}1&1\\ 1&1\end{bmatrix}=\begin{bmatrix}1/\sqrt2&-1/\sqrt2\\1/\sqrt2&1/\sqrt2\end{bmatrix} \begin{bmatrix}1&0\\ 0&0\end{bmatrix} \begin{bmatrix}1/\sqrt2&1/\sqrt2\\-1/\sqrt2&1/\sqrt2\end{bmatrix} $$ is a singular value decomposition which would give you $P=I_2$.

But we also have

$$ \frac12\,\begin{bmatrix}1&1\\ 1&1\end{bmatrix}=\begin{bmatrix}1/\sqrt2&1/\sqrt2\\1/\sqrt2&-1/\sqrt2\end{bmatrix} \begin{bmatrix}1&0\\ 0&0\end{bmatrix} \begin{bmatrix}1/\sqrt2&1/\sqrt2\\-1/\sqrt2&1/\sqrt2\end{bmatrix} $$ and now $$ P=\begin{bmatrix}1/\sqrt2&1/\sqrt2\\1/\sqrt2&-1/\sqrt2\end{bmatrix} \begin{bmatrix}1/\sqrt2&1/\sqrt2\\-1/\sqrt2&1/\sqrt2\end{bmatrix} =\begin{bmatrix}0&1\\ 1&0\end{bmatrix} $$

share|cite|improve this answer
Sorry, Martin, seems I haven't though enough. $P$ is actually a orthogonal $N\times N$ matrix, 'closest' to $M$. i.e. $$ P = \arg\min_{x\in \mathcal{O}}||X-M||_F^2$$, where $\mathcal{O}$ represents orthogonal matrix set. One conclusion about $P$ is $P=UV'$ where $U,V$ are defined as $M=USV'$. It seems $P$ is actually not unique. Here we choose any of it – Benson Jun 19 '12 at 8:53
I've modified the question. In this case, whenever $P$ is any one of$[1\quad 0;0\quad1]$ or $[0\quad 1;1\quad 0]$, it's permutation matrix, does this hold true for all cases? – Benson Jun 19 '12 at 9:11

I didn't exactly get your question. But the solution for the optimization problem you are looking is always a permutation matrix. This follows from the birkhoff's theorem. The birkhoff's theorem states that every doubly stochastic matrix is a convex combination of the permutation matrices. Hence, permutation matrices form the corners of the convex set of all doubly stochastic matrices. The objective function you have here is a convex function. Thus the minimum should be attained at one of the corner points, which are all permutation matrices.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.