4
$\begingroup$

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!

2 Answers 2

1

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

  • 0
    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?2012-06-19
0

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.