# Nearest matrix in doubly stochastic matrix set

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!

-

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}$$

-
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.

-