Sinkhorn normal form for unitary matrices

Introduction

For every $n\times n$ matrix $A$ with positive entries there exist two diagonal matrices $L,~{}R$ such that $LAR$ is doubly stochastic, i.e. the entries of each column and row sum up to one. This result was first obtained by Sinkhorn [Sin64], who also gave an algorithm how to compute $L$ and $R$ by iterated left and right multiplication of diagonal matrices.

Recently, De Vos and De Baerdemacker studied the same problem for unitary matrices [DVB14a]. They conjectured that for every $n\times n$ unitary $U$ there exist two unitary diagonal matrices $L,R$ such that $LUR$ has all row and column sums equal to one. To support their conjecture, they construct an algorithm similar to the iteration procedure for matrices with positive entries from [Sin64, SK67]. They also provide numerical evidence that the algorithm always converges to a unitary matrix with row and column sums equal to one.

The goal of this paper is to prove the conjecture of De Vos and De Baerdemacker that such a normal form always exists by reformulating the problem in terms of symplectic topology. It turns out that the reformulated problem is a special case of the Arnold (sometimes Arnold-Givental) conjecture on the intersection of Lagrangian submanifolds [MS98], which was solved for this case in [BEP04, Cho04]. More precisely, in section 2 we show:

For every unitary matrix $U\in U(n)$ there exist two diagonal unitary matrices $L,R\in U(n)$ such that $A:=LUR$ satisfies $\sum_{j}A_{ji}=\sum_{j}A_{ij}=1$ for all $i=1,\ldots n$.

For a given unitary $U\in U(n)$ the triple $(L,R,A)$ is certainly not unique, since multiplying $L$ by a global phase and $R$ by its inverse does not change $LAR$. Hence, it makes sense to consider the decomposition $U=e^{i\varphi}L^{\prime}AR^{\prime}$, where $L^{\prime},R^{\prime}$ are unitary diagonal such that $L^{\prime}_{11}=R^{\prime}_{11}=1$ and $\varphi\in[0,2\pi)$. In particular, for $U(2)$, a simple complete solution was given in [DVB14a] from which one can see that for every non-diagonal matrix, there are only two different $A$ such that $e^{i\varphi}LAR=U$. For $n>2$ the picture is less clear and the reformulation in terms of symplectic topology appears to give further insight into the freedom of the decomposition.

In addition to the Sinkhorn-type normal form above, in section 3 we give several reformulations that might be interesting for applications, for instance regarding the decomposition of general $2n-$port linear optics devices into canonical multiports and phase shifters.

Sinkhorn-type normal form

Likewise, since $\overline{A}e=Ae$ and $A$ is unitary, we obtain

so that columns and rows of $A$ sum up to one.

The definition is slightly different from the one in [BEP04], where the authors only consider nonempty open sets such that the restriction of $\omega$ to these sets is exact. However, they prove that the torus $T^{n}$ is displaceable in the above definition, if and only if there exists an open neighborhood $\mathcal{V}\supset T^{n}$ such that $\omega|_{\mathcal{V}}$ is exact and $\mathcal{V}$ is displaceable. With this we can state the final and crucial ingredient in the proof of the normal form:

Because every unitary matrix defines a Hamiltonian isotopy (see proposition 5 in the appendix), the theorem tells us in particular $T^{n}\cap UT^{n}\neq\emptyset$ for all unitaries $U\in U(n)$ so that together with lemma 1 this proves the sought normal form:

For every unitary matrix $U\in U(n)$ there exist two diagonal unitary matrices $L,R\in U(n)$ such that $A:=LUR$ fulfills $\sum_{j}A_{ji}=\sum_{j}A_{ij}=1$ for all $i=1,\ldots n$.

Equivalent normal forms for unitary matrices

Now let $A\in U(n)$ be such that $Ae=A^{T}e=e$. Then $F_{n}^{\dagger}AF_{n}e_{0}=e_{0}$ and similarly, $(F_{n}^{\dagger}AF_{n})^{T}e_{0}=F_{n}A^{T}F_{n}^{\dagger}e_{0}=e_{0}$, which shows that

This decomposition has an immediate application in quantum optics, where any $n\times n$ unitary corresponds to a passive transformation on $n$ modes or a $2n-$multiport. In this scenario a diagonal unitary corresponds to a set of phase shifters, which are applied to the modes individually and the discrete Fourier transformation is known as canonical $2n$-multiport [MMW+95], which may be implemented by a symmetric fibre coupler. The structure of the corresponding decomposition is graphically depicted in Figure 1.

Let us finally discuss the question of uniqueness of these decompositions and to this end come back to the original normal form

where $D_{1},D_{2}$ are unitary diagonal with $(D_{i})_{11}=1$ and $A$ has row and column sums equal to 1. Counting parameters, using that the matrices $A$ are isomorphic to $U(n-1)$ as proven above, we have:

parameters (c.f. [DVB14a]). Hence, the number of parameters matches exactly the dimension of $U(n)$. Given a unitary $U=e^{i\varphi}D_{1}AD_{2}$ as above, this means that it might be reasonable to expect only a discrete set of different decompositions or at least a discrete set of $A$ that $U$ can be scaled to. The exact number of different $A$ can easily be seen to be two for the case $n=2$ (c.f. [DVB14a]), but already for $n=3$ and $n=4$, there is only a conjectured bound (6 and 20, c.f. [Shc13]).

In [Cho04] it is proven that if $T^{n}$ and $UT^{n}$ intersect transversally, their number of distinct intersection points must be at least $2^{n}$, which follows from general results in Floer-homology theory when applied to Lagrangian intersection theory. Since transversality is a generic property for intersections, one might therefore conjecture that for a generic unitary $U\in U(n)$ [Cho04] implies a lower bound $2^{n-1}$ on the number of different normal forms. However, it is not true that we always have a discrete number of decompositions or (in contrast to the $2\times 2$ case) at least a discrete number of $A$ such that $A$ has row and column-sums equal to one and $e^{i\varphi}LAR=U$. A counterexample is given by the Fourier transform in $4\times 4$ dimensions, where we have for any $\varphi\in[0,2\pi)$:We thank the anonymous referee for providing this counterexample.

After completion of this document, we learned that part of this section, in particular corollary 1 were independently found in [DVB14b].

Conclusion

We have studied a variant of a Sinkhorn type normal form for unitary matrices. Its existence was conjectured in [DVB14a] and we give a nonconstructive proof. This means in particular that the question, whether the algorithm presented in [DVB14a] always converges for any set of starting conditions, remains open. Also, it would be nice to have an elementary proof of the fact that for any unitary matrix $U$ we have $T^{n}\cap UT^{n}\neq\emptyset$. The decomposition is in not unique: We provided an example where, contrary to the $2\times 2$-case, there is a one-parameter set of $A$ as well as $L$ and $R$, such that $LAR=U$. We suggested an argument that the number of different decompositions, if it is discrete, might grow exponentially. However this lower bound relies on a lower bound on Lagrangian intersections which holds only for transversal intersections.

We thank Michael Keyl for many helpful comments on the parts involving symplectic topology. M. Idel is supported by the Studienstiftung des deutschen Volkes. M. Wolf acknowledges support from the CHIST-ERA/BMBF project CQC.

References

Appendix A Symplectic Preliminaries

This section introduces the definitions and results from symplectic topology beyond the first chapters of [MS98] needed to understand the basic reductions of the proof of theorem 1 in [BEP04].

Let $(\mathcal{M},\omega)$ be a closed symplectic manifold. If the manifold is simply connected (i.e. every loop is contractible)

In principle, the result also holds for arbitrary symplectic manifolds. One has to be more careful with non-compactly supported functions, but we can safely ignore these subtleties, since our manifold of interest will be closed.

Furthermore, let us recall that a Lagrangian submanifold $\mathcal{L}$ of a $2n$-dimensional symplectic manifold $(\mathcal{M},\omega)$ is a smooth $n$-dimensional submanifold of $\mathcal{M}$ such that

A.2 The Clifford-torus as a Lagrangian submanifold

We now study the Clifford torus as a special case of the Lagrangian submanifold of interest for our result.

The next step is to show non-degeneracy. For this, note that $\Phi^{*}\omega(X,Y)=0~{}\forall Y$ if and only if $d\Phi X=0$ pointwise, since $\omega$ is non-degenerate. But $d\Phi X=0$ implies in particular $d\pi X=0$ and hence, $\omega_{FS}$ as defined above is a non-degenerate 2-form.

since $d$ commutes with pullbacks and $\omega$ is closed. Since this holds on any patch $U_{i}$, $d\omega_{FS}=0$ globally.

Then $T_{\pi(p)}T^{n}$ will be spanned by $d\pi X^{i}_{\pi(p)}$.