Scaling a unitary matrix

Introduction

By definition, the scaling of an $n\times m$ matrix $A$ is the multiplication of this matrix to the left by a diagonal $n\times n$ matrix $L$ and to the right by a diagonal $m\times m$ matrix $R$, resulting in the $n\times m$ matrix $B=LAR$, called the scaled matrix .

Sinkhorn has demonstrated that an arbitrary matrix $A$ with exclusively real and positive entries can be scaled by diagonal matrices $L$ and $R$ with exclusively positive real entries, such that the resulting scaled matrix $B$ is doubly stochastic, i.e. such that all entries of $B$ are real and in the interval $(0,1)$ and all line sums (i.e. all row sums and all column sums) of $B$ are equal to 1.

In order to find the appropriate matrices $L$ and $R$, one could consider the set of $n+m$ line-sum equations and solve it for the $n$ unknown entries of $L$ and the $m$ unknown entries of $R$. However, all equations are quadratic. As the equations are non-linear, an analytic solution of the set is not available. Instead, one proceeds iteratively, in the way pioneered by Kruithof . One computes the matrices $A_{1}$, $A_{2}$, …, successive approximations of the wanted matrix $B$. At the $k$ th iteration, one chooses a diagonal matrix $L_{k}$ with diagonal entries equal to the inverse of the row sums of the matrix $A_{k-1}$ :

and one chooses a diagonal matrix $R_{k}$ with diagonal entries equal to the inverse of the resulting column sums

Because this procedure converges, the matrices $L_{k}$ and $R_{k}$ ultimately become the $n\times n$ and $m\times m$ unit matrices, respectively. This means that ultimately $A_{k}$ becomes a matrix with unit line sums. By choosing $A_{0}$ equal to $A$, the two wanted scaling matrices are

and the scaled matrix $B$ is $A_{\infty}$.

In the present paper, we investigate whether it is possible to scale an $n\times n$ unitary matrix $A$ by two unitary diagonal matrices $L$ and $R$, such that the scaled matrix $B=LAR$ has all line sums equal to 1. For this purpose, we apply a Sinkhorn-like algorithm, however with

thus guaranteeing that all the diagonal entries of $L_{k}$ and $R_{k}$ are automatically unitary. Here, we call a complex number $x$ unitary iff $|x|=1$ and define the function $\Phi$ of a complex number $y$ as

If this procedure ultimately converges, then both $L_{k}$ and $R_{k}$ ultimately become the $n\times n$ unit matrix. This means that ultimately $A_{k}$ becomes a matrix with all line sums having $\Phi=1$, i.e. with all line sums real (positive or zero). Below, we will see that not only $A_{k}$ converges to a matrix $A_{\infty}$ with exclusively realThe $n\times n$ unitary matrices with real line-sums form a subset of U($n$), but not a subgroup of U($n$). This can easily be illustrated by multiplying two U(2) matrices: the square root of NOT matrix M_{1}=\frac{1}{2}\ {\scriptsize\left(\begin{array}[]{rr}1+i&1-i\\ 1-i&1+i\end{array}\right)} and the orthogonal matrix M_{2}=\frac{1}{2}\ {\scriptsize\left(\begin{array}[]{rr}\sqrt{3}&-1\\ 1&\sqrt{3}\end{array}\right)}. All four line sums of both matrices are real (and positive); their product $M_{1}M_{2}$, however, has a real and positive first column sum $c_{1}=(\sqrt{3}+1)/2$, but a complex first row sum $r_{1}=(\sqrt{3}-i)/2$. (non-negative) line sums, but that surprisingly those line sums moreover equal 1.

A progress measure

For investigating the progress in the matrix sequence $A_{0},A_{1},A_{2},...$, we basicly follow a reasoning similar to the elegant proofs of Sinkhorn’s theorem by Linial et al. and by Aaronson . However, the pivotal role (called either ‘progress measure’ or ‘potential function’) played either by the matrix permanent (Linial et al.) or by the matrix product (Aaronson) is taken over here by the absolute value of the matrix sum. The matrix sum of an $n\times m$ matrix $X$ is defined as the sum of all its entries:

Assume a matrix $X$ with row sums $r_{a}$ and column sums $c_{b}$. We denote by $L$ the diagonal matrix with entries $L_{aa}$ equal to $1/\Phi(r_{a})$. If $X^{\prime}$ is a short-hand notation for $LX$, and $r^{\prime}_{a}$ and $c^{\prime}_{b}$ are its row sums and column sums, respectively, then we have

because $\sum_{a}r^{\prime}_{a}$ can be regarded as a vector sum of vectors with the same length as the vectors $r_{a}$ but with zero angles between them. The equality sign holds iff all numbers $r_{a}$ have the same argument. Similarly, we denote by $R$ the diagonal matrix with entries $R_{bb}$ equal to $1/\Phi(c^{\prime}_{b})$. If $X^{\prime\prime}$ is a short-hand notation for $X^{\prime}R$, and $c^{\prime\prime}_{b}$ are its column sums, then

where the equality sign holds iff all numbers $c^{\prime}_{b}$ have the same argument. We thus can conclude that

where the equality holds iff the equality holds both in (1) and in (2). The equality in (1) occurs if all $r_{a}$ have the same argument, whereas the equality in (2) occurs if all $c^{\prime}_{b}$ have the same argument. But, a constant $\arg(r_{a})$ leads to an $X^{\prime}$ of the form $e^{i\alpha}\,X$ and therefore to column sums $c^{\prime}_{b}=e^{i\alpha}\,c_{b}$ and the condition of constant $\arg(c^{\prime}_{b})$ then is equivalent to the condition of constant $\arg(c_{b})$.

We conclude that, in the matrix sequence $A_{0},A_{1},A_{2},...$ of Section 1, we have

where the equality sign holds iff $A_{k-1}$ is a matrix with all line sum arguments equal. As soon as $k-1>0$, this condition is equivalent to iff $A_{k-1}$ is a matrix with all line sums real, either zero or positiveWe remark that, for $k>0$, the procedure of Section 1 guarantees that all column sums and thus also the matrix sum are positive or zero. Hence, for $k\geq 2$, the absolute value symbols in (3) could be omitted..

In Appendix A, we prove that, for an arbitrary $n\times n$ unitary matrix $U$, we have $|\mbox{sum}(U)|\leq n$. The equality sign holds iff $U$ is, up to a global phase, a matrix with all line sums equal to 1. For sake of convenience, we define the potential function $\Psi$ of an $n\times n$ matrix $M$ as

such that for all unitary matrices $0\leq\Psi\leq n^{2}$ holds and the zero potential corresponds with unit line-sum matrices (times a factor $e^{i\alpha}$). With this convention, we rewrite (3) as

The $\Psi$ landscape of the matrix group U($n$) displays stationary points. In Appendix B, we show that these points either have zero matrix sum or have all (non-zero) line sums with same argument. We distinguish three categories of stationary points: their potential satisfies

If the first case occurs, then the stationary point is a global maximum; if the second case occurs, then the stationary point is a global minimum. We conjecture that the third class consists of saddle points. In other words: we conjecture that the $\Psi$ landscape has no local minima (nor local maxima). As a result, the scaling procedure (with ever decreasing $\Psi$) ultimaltely converges to the point with minimal potential. We conjecture that this global minimum is a matrix with $\Psi=0$ and thus is a wanted unit line-sum matrix $B$.

Either the given matrix $A$ does not have constant line sum arguments, in which case we choose $A_{0}=A$. As long as the subsequent matrices $A_{1}$, $A_{2}$, … do not have all row sums real, we have a strictly decreasing sequence $\Psi(A_{0})>\Psi(A_{1})>\Psi(A_{2})>...$. This sequence is bounded by 0. Therefore a limit matrix $A_{\infty}$ exists, with $\Psi(A_{\infty})\geq 0$.

If $\Psi(A_{\infty})=0$, then $A_{\infty}$ is the wanted scaled matrix. The scaling matrices are $L=L_{\infty}...L_{2}L_{1}$ and $R=R_{1}R_{2}...R_{\infty}$.

In the (very unlikely) case that $\Psi(A_{\infty})>0$, the matrix $A_{\infty}$ is a stationary point in the potential landscape $\Psi$. According to the conjecture, this point is a saddle point and therefore we can apply appropriate matrices $L$ and $R$, both close to the unit matrix, such that $LA_{\infty}R$ has potential $\Psi$ lower than $\Psi(A_{\infty})$. It is sufficient to try $n$ mutually orthogonal directions in the $(2n-1)$-dimensional neighbourhood of the saddle point. After applying these $L$ and $R$, we restart the algorithm with a new $A_{0}$, equal to $LA_{\infty}R$.

Or the given matrix $A$ has all line sum arguments equal and thus $A$ is a stationary point. In this case we choose $A_{0}=L_{0}AR_{0}$, with two appropriate matrices $L_{0}$ and $R_{0}$, such that the start matrix $A_{0}$ is not a stationary point. For this purpose, we can proceed as follows:

If at least two row sums of $A$ are different from 0, e.g. $r_{x}\neq 0$ and $r_{y}\neq 0$, then we take $R_{0}$ equal to the unit matrix and all entries of $L_{0}$ equal to 1, except $(L_{0})_{xx}$, thus resulting in at least two different row-sum arguments for $A_{0}$.

If at least two column sums of $A$ are different from 0, e.g. $c_{x}\neq 0$ and $c_{y}\neq 0$, then we take $L_{0}$ equal to the unit matrix and all entries of $R_{0}$ equal to 1, except $(R_{0})_{xx}$, thus resulting in at least two different column-sum arguments for $A_{0}$.

If only one row sum (say $r_{x}$) and only one column sum (say $c_{y}$) of $A$ differ from 0, i.e. if $A$ is a generalized Hadamard matrix , then we take $R_{0}$ equal to the unit matrix and all entries of $L_{0}$ equal to 1, except $(L_{0})_{xx}$, thus resulting in at least two different column-sum arguments for $A_{0}$.

An example of the latter case is the orthogonal matrix

where, for convenience, we assume $0<\phi<\pi/4$. Indeed: all its line sums have zero argument. If we would take $A_{0}=A$, then $L_{1}$ would be equal to the $2\times 2$ unit matrix and subsequently $R_{1}$ would be equal to the unit matrix, such that $A_{1}$ and, in fact, all subsequent $A_{k}$ would be equal to $A$ and therefore $\Psi(A_{0})=\Psi(A_{1})=\Psi(A_{2})=...$, equal to $2\cos(\phi)$ in this example. In this way, the algorithm cannot find the wanted solution, in spite of the fact that such scaled matrices with exclusively unit line sums actually exist, e.g.

In order to avoid the no-start of the convergence towards the desired scaled matrix $B$, we apply e.g. the matrices L_{0}={\scriptsize\left(\begin{array}[]{rr}i&0\\ 0&1\end{array}\right)} and R_{0}={\scriptsize\left(\begin{array}[]{rr}1&0\\ 0&1\end{array}\right)}, resulting in

where row sums $r_{1}=i(\cos(\phi)+\sin(\phi))$ and $r_{2}=\cos(\phi)-\sin(\phi)$ indeed have unequal arguments: $\pi/2$ and 0, respectively.

Convergence speed

As a first example of the procedure of Section 2, we take the unitary matrix

with line sums, matrix sum, and potential

Because $\Psi\neq n^{2}$, $\Psi\neq 0$, and the line sums do not have equal argument, we are in a ‘common’ case, i.e. not in a stationary point of the $\Psi$ landscape. We thus choose $A_{0}=A$. Subsequent steps of the algorithm yield potentials

Next, with the method of Życzkowski et al. , we generate 1,000 random elements of U(3), uniformly distributed with respect to the Haar measure. Table 1 shows how the potential $\Psi$ decreases after each step of the scaling procedure. Whereas the $\Psi$ values of the initial matrices $A_{0}$ have a wide distribution between 0 and $n^{2}=9$, the distribution of $\Psi(A_{k})$ is very peaked at $\Psi=0$, as soon as $k>0$.

The convergence speed turns out to be strongly different for different matrices $A$. Among the 1,000 samples, some converge exceptionally slowly, as is illustrated by the column ‘maximum($\Psi$)’. Usually, however, convergence is fast, as is illustrated by the column ‘average($\Psi$)’. We stress the fact that all 1,000 experiments directly converge to the global minimum $\Psi=0$, and thus none ‘gets trapped’ in a local minimum and none temporarily ‘halts’ in a saddle point.

Finally, similar experiments with 1,000 random elements from U(4) (see Table 1) and with 1,000 random elements from U(5) lead to similar results.

For $n$ equal to 2, 4, 8, 16, and 32, Figure 1 shows the probability distribution of the potential $\Psi$, after $k=0$, $1$, $2$, and $4$ iteration steps. We see how the distribution, at each step, shifts more and more to $\Psi=0$.

The convergence can also be visualized by displaying $\Psi_{k+1}$ as a function of $\Psi_{k}$, i.e. the correlation between a $\Psi$ after and before an iteration step. Figure 2 shows $\Psi_{1}(\Psi_{0})$, $\Psi_{2}(\Psi_{1})$, and $\Psi_{3}(\Psi_{2})$ for both $n=2$ and $n=3$. As expected, all points lay below the line $\Psi_{k+1}=\Psi_{k}$. We see how the cloud of points, after each step, becomes smaller and smaller and moves closer and closer to the point $\Psi_{k}=\Psi_{k+1}=0$.

Application

In Reference , two subgroups of the unitary group U($n$) are presented:

the subgroup ZU($n$), consisting of all $n\times n$ diagonal matrices with upper-left entry equal to 1 and other diagonal entries from U(1);

the subgroup XU($n$), consisting of all $n\times n$ unitary matrices with all of their $2n$ line sums are equal to 1,

and the following theorem is proved: any U($n$) matrix $U$ can be decomposed as

with $p\leq n(n-1)/2+1$ and where all $Z_{j}$ are ZU($n$) matrices and all $X_{j}$ are XU($n$) matrices. In Reference , it is proved that a shorter decomposition exists: with $p\leq n$.

In the present paper, we conjecture that even a far stronger theorem holds: $p\leq 2$. This means that any U($n$) matrix $U$ can be decomposed as

where both $Z_{1}$ and $Z_{2}$ are ZU($n$) matrices and $X$ is an XU($n$) matrix. In , it is proved that the group XU($n$) is isomorphic to U($n-1$) and hence has dimension $(n-1)^{2}$. Therefore, the product $e^{i\alpha}\,Z_{1}XZ_{2}$ has

degrees of freedom, matching exactly the dimension of U($n$) and thus making the conjecture dimensionally possible. However, no analytic expression is provided for the unknown entries neither of the matrices $Z_{1}$ and $Z_{2}$ nor of the scaled matrix $X$. An analytic solution of the decomposition problem is easily found for $n=2$. Indeed, an arbitrary member of U(2) can be decomposed according to (4), in two different ways:

For more details about the case U(2), the reader is referred to Appendix C.

No analytic solution is found as soon as $n>2$. Even the decomposition of an arbitrary member of U(3) is an unsolved problemAs soon as one of the nine entries of the U(3) matrix equals zero, the problem is analytically solvable., in spite of substantial efforts by the authors of the present paper. Independently, in the framework of an other but related problem, Shchesnovich comes to a similar conclusion. For arbitrary $n$, Reference gives an analytic solution for a $2n$-dimensional subset of the $n^{2}$-dimensional group U($n$). We conjecture that the asymptotic scaling procedure of Sections 1 and 2 provides a numerical solution, for any member of U($n$), with arbitrary $n$.

If, in particular, we have $n=2^{w}$, then a U($n$) matrix represents a quantum circuit of width $w$, i.e. acting on $w$ qubits. We thus may conclude that such circuit can be decomposed as the cascade of an overall phase, two $Z$ subcircuits and one $X$ subcircuit. The basic building block of any $Z$ circuit is the 1-qubit circuit represented by $2\times 2$ matrix

the basic building block of any $X$ circuit is the 1-qubit circuit represented by

The NEGATOR realizes an arbitrary root of NOT and thus is a natural generalization of the square root of the NOT gate .

Each $2^{w}\times 2^{w}$ matrix $Z$ is implemented by a string of $2^{w-1}$ controlled PHASORs; any $2^{w}\times 2^{w}$ matrix $X$ represents a circuit composed of controlled NEGATORs .

where $a$ is a short-hand notation for $e^{i\alpha}$ and $X_{0}$ is the permutation matrix

we can transform (4) into a decomposition containing exclusively XU and ZU matrices:

where $X_{0}$ is an XU matrix which can be implemented with classical reversible gates (i.e. NOTs and controlled NOTs), where $Z_{0}$ is a ZU matrix which can be implemented by a single (uncontrolled) PHASOR gate, and where $Z_{1}^{\prime}$ is the product $\mbox{diag}(1,a,1,a,1,...,1,a)\,Z_{1}$. The short decomposition (6) illustrates the power of the two subgroups XU($n$) and ZU($n$), which are complementary , in the sense that

they overlap very little, as their intersection is the trivial group consisting of merely the $n\times n$ unit matrix and

they strengthen each other sufficiently, as their closure is the whole unitary group U($n$).

As an example, we give here a decomposition of the Hadamard gate according to schemes (4) and (6), respectively:

Conclusion

We have presented a method for scaling an arbitrary matrix from the unitary group U($n$), by multiplying the matrix to the left and to the right by unitary diagonal matrices. We conjecture that the resulting scaled matrix is a member of XU($n$), i.e. the subgroup of U($n$) consisting of all $n\times n$ unitary matrices with all $2n$ line sums equal to 1. If $n=2$, then scaling can be performed analytically and thus with infinite precision. If $n>2$, then scaling has to be performed numerically and thus with finite precision. In the terminology of Linial et al. , we would say that matrices from U(2) are ‘scalable’, whereas matrices from U($n$) with $n>2$ are ‘almost scalable’. The conjecture that the numerical algorithm converges to a unit line-sum matrix, is based on four observations:

the proof that such matrix exists in the case $n=2$,

the proof that such matrix exists for a $2n$-dimensional subset of the general case U($n$) ,

the success of 1,000 numerical experiments in the cases $n=3$, $n=4$, and $n=5$, and

the fact that, according to (5), there are, for arbitrary $n$, exactly the right number of freedoms.

For the special case of $n=2^{w}$, this leads to a decomposition of an arbitrary quantum circuit into

one overall phase, one X circuit and two Z circuits or

References

Appendix A Theorem

Theorem : The absolute value of the matrix sum of a U($n$) matrix is smaller than or equal to $n$. The U($n$) matrices with abs(matrixsum) = $n$ are member of the subgroup $e^{i\alpha}$ XU($n$), where XU($n$) denotes the subgroup of U($n$) consisting of the matrices with unit line sums.

Let $r_{1}$, $r_{2}$, …, and $r_{n}$ be the row sums of an $n\times n$ matrix. For convenience, we give their real and imaginary parts an explicit notation:

as proved in Appendix A of Reference . We rewrite this property as follows:

where the angle $\Sigma$ is allowed to have any value.

We consider (9) as the eqn of an $n$-dimensional hypersphere. We ask ourselves what is the highest value of the function

on the surface of this hypersphere. For this purpose, we note that $f=k$, with $k$ some positive constant, is the eqn of the set of two parallel hyperplanes:

The highest value of $k$ on the hypersphere is when the two planes are tangent to the sphere. This happens when $k$ equals $n^{2}\,\cos^{2}(\Sigma)$, the two tangent points having coordinates $(s_{1},s_{2},...,s_{n})=\pm\cos(\Sigma)\ (1,1,...,1)$ and $f$ having the value $n^{2}\cos^{2}(\Sigma)$. See the 2-dimensional illustration in Figure 3.

A similar reasoning is possible for the function

Noting that $|m|^{2}$ equals $f+g$, we conclude that $|m|^{2}$ has maximum value $n^{2}\,\cos^{2}(\Sigma)+n^{2}\,\sin^{2}(\Sigma)=n^{2}$. The unitary matrices with this particular $|m|^{2}$ value are the matrices with $r_{j}=\pm\cos(\Sigma)\pm i\sin(\Sigma)$, i.e. the matrices with constant row sum equal to $e^{i\alpha}$, where $\alpha$ is either $\Sigma$ or $\Sigma+\pi$.

A dual reasoning holds for the column sums, with $c_{j}=d_{j}+ie_{j}$, such that $d_{1}^{2}+d_{2}^{2}+...+d_{n}^{2}=n\cos^{2}(\Delta)$ and $e_{1}^{2}+e_{2}^{2}+...+e_{n}^{2}=n\sin^{2}(\Delta)$. The unitary matrices with $|m|^{2}=n^{2}$ are the matrices with $c_{j}=\pm\cos(\Delta)\pm i\sin(\Delta)$, i.e. the matrices with constant column sum equal to $e^{i\beta}$, where $\beta$ is either $\Delta$ or $\Delta+\pi$. Because a matrix can have only one matrix sum, a matrix with both constant row sum and constant column sum necessarily has constant line sum. Therefore, for the matrices with $|m|^{2}=n^{2}$, the angle $\beta$ equals the angle $\alpha$.

The maximum-$|m|$ matrices equal $e^{i\alpha}$ times a matrix with constant line sum equal to 1. Thus they are member of the group $e^{i\alpha}$ XU($n$), a subgroup of U($n$), isomorphic to U(1) $\times$ XU($n$), and thus isomorphic to U(1) $\times$ U($n-1$).

Appendix B The potential landscape

Given a unitary matrix $A$, finding the scaled matrix $B$ is equivalent to solving the (non-linear) eqn

we introduce a $2n$-dimensional landscape $\Psi$, given by

We have to find the minimum of this function, i.e. the point $\Psi=0$.

In order to investigate the shape of the $\Psi$ function, we linearize the equation around $A$, i.e. in the neighbourhood of $(\lambda_{1},\lambda_{2},...,\lambda_{n},\rho_{1},\rho_{2},...,\rho_{n})$ = $(0,0,...,0,$ $0,0,...,0)$. For this purpose, we write the row sums, column sums, and matrix sum of the given matrix $A$ as follows:

The coefficients of $\lambda_{j}$ and $\rho_{j}$ form the gradient vector of the $\Psi$ landscape. A stationary point occurs whenever, for all $j$,

These conditions can only be fulfilled in the following cases:

i.e. when the matrix sum is zero and hence $\Psi$ has the global maximum value of $n^{2}$,

i.e. when all non-zero line sums have the same argument.

We conjecture that all these stationary points are either maxima or saddle points or global minima. In other words: we conjecture that no local minima exist. Moreover, we conjecture that the global minima satisfy $\Psi=0$.

Appendix C The case U(2)

We consider the unitary group U(2). All $2\times 2$ diagonal unitary matrices form the subgroup DU(2), isomorphic to U(1) $\times$ U(1). The subgroup DU(2) divides its supergroup U(2) into double cosets. Let $A$ be an arbitrary U(2) matrix:

Its double coset consists of all matrices

where $c$ and $s$ are short-hand notations for $\cos(\phi)$ and $\sin(\phi)$, respectively. We introduce the variables

Therefore, the double coset is the 3-parameter space

Thus the double coset of $A$ consists of the matrices $U(\phi,x,y,z)$, i.e. of all matrices with the same value of the angle $\phi$. This constitutes a 3-dimensional subspace of the 4-dimensional space U(2), except for the cases $s=0$ (i.e. for the double coset of the IDENTITY matrix {\tiny\left(\begin{array}[]{cc}1&0\\ 0&1\end{array}\right)}) and $c=0$ (i.e. for the double coset of the NOT matrix {\tiny\left(\begin{array}[]{cc}0&1\\ 1&0\end{array}\right)}), which both are 2-dimensional onlyOne may consider an arbitrary place $P(\varphi,\lambda)$ on earth. The points $Q(\varphi,x)$, with same latitude $\varphi$ but arbitrary longitude $x$, form a 1-dimensional subspace of the 2-dimensional earth surface, called the parallel of $P$, except if either $\varphi=\pi/2$, in which case $Q(\varphi,x)$ is a 0-dimensional subspace, called the north pole, or $\varphi=-\pi/2$, in which case $Q(\varphi,x)$ is a 0-dimensional subspace, called the south pole. We therefore may consider the 2-dimensional double coset of the IDENTITY matrix and the 2-dimensional double coset of the NOT matrix as the north and the south pole, respectively, of the 4-dimensional U(2) manifold..

What are, within the double coset of $A$, the stationary points of the $\Psi$ landscape? We easily find

The conditions $\partial\Psi/\partial x=0$, $\partial\Psi/\partial y=0$, and $\partial\Psi/\partial z=0$ immediately lead to

This set of two trigonometric equations in the three unknowns $x$, $y$, and $z$ has infinitely many solutions, leading to an infinite number of matrices:

with $x$ arbitrary, $k\in\{0,1,2,3\}$, and $l\in\{0,1,2,3\}$. These sixteen sets of matrices lead to $\Psi$ values equal to $4$, $4c^{2}$, $4s^{2}$, and , corresponding to global maxima, saddle points, saddle points, and global minima, respectively. The saddle points belong to U(1)$\times$O(2), subgroup of U(2); the global extrema do not.

What are, within the same double coset, the matrices with all line sums real? We easily find the conditions:

This set of three trigonometric equations in the three unknowns $x$, $y$, and $z$ has twelve solutions:

Four matrices have matrix sum and thus $\Psi=4$; four matrices have matrix sum $\pm 2s$ and thus $\Psi=4\cos^{2}(\phi)$; four matrices have matrix sum $\pm 2c$ and thus $\Psi=4\sin^{2}(\phi)$; four matrices have matrix sum $\pm 2$ and thus $\Psi=0$. Thus four of the twelve matrices represent a global maximum; eight of the twelve matrices represent a saddle point; four of the twelve matrices represent a global minimum.

As an example, we choose the $A$ matrix with $0<\phi<\pi/4$, such that $0<s<c<1/\sqrt{2}$. Among the twelve matrices of its double coset with real line sums , there are only four matrices where the four line sums are positive, i.e.

where $e$ is a short-hand notation for $e^{i\phi}=c+is$. Among these four matrices, only $B$ and $B^{\prime}$ have unit line sum (and thus $\Psi=0$).

In the neighbourhood of $S$, we have the matrices

with $x$, $y$, and $z$ small. This yields a matrix sum

The opposite signs of the coefficients of $y^{2}$ and $z^{2}$ illustrate the fact that $S$ is a saddle point of the $\Psi$ landscape. Only if the subsequent matrices $A_{k},A_{k+1},...$ are situated on the $z=0$ line, then the Sinkhorn-like procedure of Section 2 halts at the point $S$. In order to leave this stop, it suffices to continue along another line, e.g. $y=0$. Similar conclusions hold for the point $S^{\prime}$.

In the neighbourhood of $B$, we have the matrices

with $x$, $y$, and $z$ small. This yields a matrix sum

The positive signs of the coefficients of $y^{2}$ and $z^{2}$ illustrate the fact that $B$ is a minimum (actually, a global minimum) of the $\Psi$ landscape. The same conclusion holds for the point $B^{\prime}$.

Let us assume that, in spite of the direct analytic solution for $n=2$, we scale a U(2) matrix by the iterative method of Sections 1 and 2. Once close to the point $B$, how fast do we converge to this global minimum of $\Psi$? Close to $B$, we have $A_{k}$ of the form

As soon as $k>0$, both column sums of $A_{k}$ are real (or zero), such that $x=0$ and $z=(c^{2}/s^{2})y$. Thus we have a matrix

and, because of (15), a potential $\Psi(A_{k})=(4c^{2}/s^{2})\,y^{2}$. Thus all matrices $A_{k}$ lay on a line, the 1-dimensional space (17), subspace of the 3-dimensional space (16). If we apply the $(k+1)$ th step of the iterative algorithm, we find, after some algebra:

where $a=1-4c^{2}s^{2}=\cos^{2}(2\phi)$. Hence the new potential is $\Psi(A_{k+1})=(4c^{2}/s^{2})\,(ay)^{2}$ and

This illustrates the fact that the convergence speed of the algorithm is indeed dependent on the given matrix $A$, more specifically on its parameter $\phi$. If this angle is close to $\pi/4$, then convergence is fast; if the angle is close to , then convergence is slow.

Finally, we ask ourselves, given the matrix $A$, does the algorithm of Sections 1 and 2 lead to the scaled matrix $B$ or to the scaled matrix $B^{\prime}$ ? The separatrice consists of the spaces $\chi=\psi$ and $\chi=\psi+\pi$. If $0<\chi-\psi<\pi$, then the trajectory $A_{0}$, $A_{1}$, $A_{2}$, … ends in the attractor $B$; if $-\pi<\chi-\psi<0$, then the trajectory $A_{0}$, $A_{1}$, $A_{2}$, … ends in the attractor $B^{\prime}$; if $\chi-\psi=0$ or $\chi-\psi=\pi$, then $A_{1}$ is an orthogonal matrix (either $S$ or $S^{\prime}$) and thus a saddle-point, such that the final destination (either $B$ or $B^{\prime}$) depends on the direction in which one leaves the saddle point.

We close this appendix by comparing the above quantitative U(2) results with the qualitative U($n$) properties. It is well-known that, if a finite group G has a subgroup H, then H divides G into double cosets with sizes ranging from order(H) to order2(H). Similarly, if a Lie group G has a Lie subgroup H, then H divides G into double cosets with dimension ranging from dim(H) to 2 dim(H). The group U($n$) is $n^{2}$-dimensional and its subgroup DU($n$) is $n$-dimensional. As a result, DU($n$) divides U($n$) into double cosetsThis set of double cosets, i.e. the double coset space $\mbox{U}(1)^{n}\setminus\mbox{U}(n)\,/\ \mbox{U}(1)^{n}$ can be mapped to the set (not group!) of so-called unistochastic $n\times n$ matrices , a subset of the well-known semigroup of $n\times n$ bistochastic matrices (a.k.a. doubly stochastic matrices)., each with dimension between $n$ and $2n$. In fact, in this particular case, the dimensions of the double cosets range from $n$ to $2n-1$. Most of the double cosets are $(2n-1)$-dimensional; only some are lower-dimensional, e.g. the $n!$ double cosets of permutation matrices being only $n$-dimensionalTogether these $n!$ double cosets form the group of complex permutation matrices, a group isomorphic to the semidirect product DU($n$) : Sn, where Sn is the symmetric group of degree $n$.. Thus within a double coset, we have at most $2n-1$ degrees of freedom. If we want a matrix with all line sums real, then this imposes $2n-1$ conditions, usually lowering the number of freedoms to 0. In other words: in each double coset there usually are a finite number of real line-sum matrices. We conjecture that at least one of these matrices is a unit line-sum matrix.