On biunimodular vectors for unitary matrices

Note

As we have learned from the referees, the existence of biunimodular vectors for an arbitrary unitary matrix has been recently proved in this journal by Idel and Wolf (see ) basing on the results of in symplectic geometry due to Biran, Entov and Polterovich. In this paper we provide an independent account of this existence phenomenon and push a bit further the theory of biunimodular vectors.

Outline

Background

The paper explores the notion of a biunimodular vector that traces back to Gauss. The classic example of such vectors are Gauss sequences given for $k=0,1,\dots,n-1$ as

Following Haagerup () and Saffari () we attribute the starting point of the general theory of biunimodular vectors to Per Enflo. In 1983 he has asked whether for prime $n$ the only unimodular vectors of length $n$ whose Fourier transform is also unimodular are Gauss sequences. While the answer is affirmative when $n\leq 5$, a computer search done by Björck for $n=7$ provided a surprising counterexample

with $\theta=\arccos(-\frac{3}{4})$ yielding $e^{i\theta}=-\frac{3}{4}+i\frac{\sqrt{7}}{4}$. These findings, published in 1985 (), have been generalized in and later the term “bi-unimodular sequence” has been coined by Björck and Saffari to describe a unimodular finite vector, whose Fourier transform is unimodular as well (see ).

The Björck sequences provided in are biunimodular vectors of a prime length $p$. For $p\equiv-1\pmod{4}$ their coefficients are either $1$ or $e^{i\theta}$ with $\theta=\arccos\frac{1-p}{1+p}$. For $p\equiv 1\pmod{4}$ their coefficients are either $1$, $e^{i\eta}$ or $e^{-i\eta}$ with $\eta=\arccos\frac{1}{\sqrt{p}+1}$. The importance of Björck sequences has been underlined in , where it was shown that for these sequences (contrary to Gauss sequences) the discrete narrow band ambiguity function has an optimal bound. However, Gauss and Björck sequences provide only a glimpse at the structure of biunimodular vectors for $F_{n}$. Even in the case $p=7$ there is another such vector found by Björck and Fröberg that is related neither to a Gauss nor to a Björck sequence (see or ).

Moreover, in Björck and Saffari proved that if $n$ is divisible by a square, then there are infinitely many (continuum) biunimodular vectors with the leading entry 1, and they conjectured that for all square-free $n$ the number of such biunimodular vectors is finite.

An easy observation is that a unimodular vector $u=(u_{0},u_{1},\dots,u_{n-1})$ is biunimodular for $F_{n}$ if and only if its cyclic translations are orthogonal. This orthogonality relation is called zero autocorrelation and means that

where the index $k+i$ is taken $(\bmod n)$.

The idea of Björck to search for biunimodular vectors $u$ for $F_{n}$ relies on setting $x_{k}=\frac{u_{k+1}}{u_{k}}$, where $k=0,1,\dots,n-1$ with $u_{n}=u_{0}$ and transforming (1) to the following set of equations:

The unimodular solutions of the above set of equations are in one-to-one correspondence to biunimodular vectors for $F_{n}$ (with the leading entry 1). The general complex solutions of (2) are called cyclic $n$-roots and became a research area of independent interest. In the mid-1980s Arnborg has asked Davenport to establish whether the set of cyclic 6-roots is finite, leading to the popularisation of the cyclic $n$-roots problem in . Backelin proved in that for $n$ divisible by a square the number of cyclic $n$-roots is infinite. For $2\leq n\leq 8$ all cyclic $n$-roots were found by Björck and Fröberg (see ) by using Gröbner basis techniques to solve the system (2). Faugère has found cyclic 9 and 10 roots by improving the search for the Gröbner basis (see and ). These results have been confirmed and extended by polyhedral homotopy continuation methods applied for solving (2) as a benchmark problem. The numbers of cyclic $n$-roots for a square-free $n$ between 2 and 14 is listed below.For $2\leq n\leq 11$ the amount of roots has been verified by various methods, for $n=13$ and $14$ the number of cyclic $n$-roots is claimed only by Li and Tsai (see ). Moreover, they count only isolated roots, so the number of cyclic 14-roots still has to be verified as finite or not.

The table also contains information about the number of unimodular cyclic $n$-roots that yields the amount of biunimodular vectors for $F_{n}$. The numbers up to $n=7$ were given by Björck, Fröberg and Haagerup, who inspected the obtained cyclic $n$-roots to check for unimodular solutions, establishing the real benchmark for solving the cyclic $n$-root problem (see and ). The number of biunimodular vectors for $n=13$ has been obtained by Gabidulin and Shorin in .

Basing on the number of cyclic $p$-roots for prime $p$ up to 7 Fröberg concluded that the amount of cyclic $p$-roots should be ${2p-2\choose p-1}$. This conjecture has been confirmed by Haagerup in under the condition that the roots are counted with multiplicities.

(Haagerup) For prime $p$ the number of cyclic $p$-roots counted with multiplicities is ${2p-2\choose p-1}$.

The paper of Haagerup contains an elegant direct argument showing that the number of cyclic $p$-roots is finite for prime $p$, confirming Conjecture 1.1 in the prime case. His more advanced reasoning allows to count the cyclic $p$-roots with multiplicities, imposing a question whether for all primes cyclic $p$-roots have multiplicity 1 and providing an additional motivation to verify the number of distinct cyclic 13-roots.

A slightly different approach towards finding biunimodular vectors for $F_{n}$ has been taken by Gabidulin and Shorin. In they multiplied the system (1) by the product $\prod_{k=0}^{n-1}u_{k}$ to obtain a system of equations that has been treated with Gröbner basis techniques as well, providing the mentioned number of biunimodular vectors for $F_{13}$.

The theory of biunimodular vectors may be hard to follow due to their popularity stemming from applications in several fields of signal processing. This popularity can be measured by the amount of various names given to the same objects by many researchers working within the area. Gauss sequences are often called Zadoff, Chu or Wiener sequences. Unimodular vectors are described as constant amplitude, phase-shift keyed or polyphase sequences. Vectors whose Fourier transform is unimodular are named as perfect, having optimum correlation or zero autocorrelation. Therefore, biunimodular vectors are studied as CAZAC (constant amplitude zero autocorrelation) sequences, PSK (phase-shift keyed) perfect sequences, polyphase sequences with optimum correlation and so on (see by Benedetto et al. for a better account of this nomenclature and a list of relevant papers that can be extended by adding an early reference ).

Since full understanding of biunimodular vectors would allow to resolve the circulant Hadamard matrix conjecture, and is just a tip of the iceberg being a classification of all Hadamard matrices, the complexity of the topic is apparent.

In it has been proved that biunimodular vectors exist for the Fourier transform on any finite abelian group. This raises the question of existence of such vectors for an arbitrary unitary matrix and motivates the following

In the following sections we explain that the existence of biunimodular vectors for an arbitrary unitary matrix allows to understand the structure of unitary matrices in fairly simple terms.

Synthesis of U​(n)𝑈𝑛U(n)

Unitary $n\times n$ matrices form the unitary group $U(n)$ and are a basic notion in mathematics, physics, chemistry and engeneering. These matrices can be obtained in various standard ways: Gram-Schmidt process, Householder reflections, Hurwitz parametrization, Cayley transform and via Hermitian matrices using the matrix exponential. In 1952 Murnaghan described a convenient parametrization of the unitary group (see ).Another such parametrization has been provided in 1982 by Diţă (see ). This has been followed by the work of Reck et al. who in 1994 proved that any unitary matrix can be obtained as a sequence of consecutive beam splitter transformations, that can be conducted experimentally in the laboratory using optical devices (). In the current century the research on finding the ways to generate unitary matrices has intensified. Nemoto described the special unitary group $SU(n)$ in basing on an earlier result of Rowe et al. Tilma and Sudarshan provided an Euler angle parametrization for $SU(n)$ and $U(n)$ (see ). Meanwhile Diţă in has shown another description of $U(n)$. A recursive parametrization of unitary matrices has been given by Jarlskog in and a composite parameterization was done in (see and for more details on these developments).

and run the following recursive procedure using the Fourier transform $(F_{l})_{j,k}=\frac{1}{\sqrt{l}}e^{-2\pi i\frac{jk}{l}}$ and its conjugate transpose $(F_{l}^{*})_{j,k}=\frac{1}{\sqrt{l}}e^{2\pi i\frac{jk}{l}}$ .

The initial unitary matrix $A_{1}$ is given as $[a_{11}]$. And, in general, for $2\leq l\leq n$

The above procedure is not one-to-one, meaning that different sets of parameters may give the same matrix. As to the question if it is onto, the simplicity of the above scheme can raise some doubts whether it can reveal the structure of an arbitrary unitary matrix. Nevertheless, in the next section we shall prove that all unitary matrices can be obtained in this way, provided that all of them possess biunimodular vectors.

Analysis of U​(n)𝑈𝑛U(n)

A unitary matrix $A\in U(n)$ has a biunimodular vector $v$ if and only if

The description of the group ${\rm Fix}(\mathbf{1})$ is related to the group ${\rm Fix}(\mathbf{e})$. Indeed, since $F_{n}\mathbf{e}=\frac{1}{\sqrt{n}}\mathbf{1}$, it is easy to see that $M\in{\rm Fix}(\mathbf{1})$ iff $F_{n}^{*}MF_{n}\in{\rm Fix}(\mathbf{e})$.

Therefore, we see that $A$ has a biunimodular vector $v$ iff $F_{n}^{*}D_{w}^{*}AD_{v}F_{n}\in{\rm Fix}(\mathbf{e})$. Due to the obvious description of ${\rm Fix}(\mathbf{e})$ the proposition follows. $\Box$

The Fourier transform $F_{n}$ enters the above scheme as a generic unitary matrix with the property that $F_{n}\mathbf{e}=\frac{1}{\sqrt{n}}\mathbf{1}$. We need to clarify that, in the above proposition, $F_{n}$ can be replaced by any unitary matrix $F$ such that $F\mathbf{e}=\frac{1}{\sqrt{n}}\mathbf{1}$. However, clearly the easiest description of such $F$ is given by $F=F_{n}M$ with $M\in{\rm Fix}(\mathbf{e})$.

On the other hand, as pointed out by the referees, one has the following crucial

(Idel, Wolf + Biran, Entov, Polterovich) Every unitary matrix has a biunimodular vector.

In the following section we shall examine the existence of biunimodular vectors from a few different angles.

Biunimodular problem

The biunimodular problem is to find (or prove the existence of) a biunimodular vector for a given unitary matrix. With the notation explained below we can restate this task in equivalent terms.

Let $A\in U(n)$. The matrix $A$ has a biunimodular vector if and only if either of the following holds

$A\in\mathcal{D}\cdot{\rm Fix}(\mathbf{1})\cdot\mathcal{D}_{1}$.

$A^{\prime}\in\mathcal{D^{\prime}}\cdot{\rm E}(\mathbf{1})\cdot\mathcal{D^{\prime}}$.

(a’) Here, $A^{\prime}=\lambda A$ with $\lambda^{n}=\overline{\det(A)}$, so $A^{\prime}\in SU(n)$. $\mathcal{D^{\prime}}=\mathcal{D}\cap SU(n)$ and ${\rm E}(\mathbf{1})$ denotes the subgroup of $SU(n)$ that has $\mathbf{1}$ as an eigenvector. Clearly, (a’) is a mere translation of (a) into the special unitary setting.

proving that $\|A\|_{\infty\to 1}\leq n$. Thus, if $A$ has a biunimodular vector $v$, then $\|Av\|_{1}=n\|v\|_{\infty}$ showing that $\|A\|_{\infty\to 1}=n$.

Part (a) of Theorem 4.1 is equivalent to saying that $A\in\mathcal{D}\cdot{\rm Fix}(\mathbf{1})\cdot\mathcal{D}$. Thus, Theorem 3.4 is equivalent to the decomposition $U(n)=\mathcal{D}\cdot{\rm Fix}(\mathbf{1})\cdot\mathcal{D}$. Unfortunately, there is no general theory explaining when two subgroups $H$, $H^{\prime}$ of a Lie group $G$ yield the decomposition $G=H\cdot H^{\prime}\cdot H$. Moreover, the Cartan decomposition and Kostant decomposition of any semisimple Lie group G, that both are given in this form, indicate potential difficulties in developing such a general explanation.

For part (a’) included in the above characterization, we would like to notice that $\mathcal{D^{\prime}}$ is a maximal torus subgroup of a compact simple Lie group $SU(n)$. Thus, Theorem 3.4 is equivalent to the following maximal torus decomposition:

with $\dim(SU(n))=\dim({\rm E}(\mathbf{1}))+2\dim(\mathcal{D^{\prime}})$. This allows to conjecture, or ask, whether every compact simple Lie group $G$ admits a maximal torus decomposition $G=T\cdot H\cdot T$, with a maximal torus $T$ of $G$ and a subgroup $H\subseteq G$ such that $\dim G=\dim H+2\dim T$.

Regarding part (b), as in , an interpolation argument can be used to conclude that $\|A\|_{\infty\to 1}=n$ is in turn equivalent to saying that $\|A\|_{p\to q}=n^{\frac{1}{q}-\frac{1}{p}}$ in the region $1\leq q\leq 2\leq p\leq\infty$. This further amplifies the interest in biunimodular vectors, that are precisely those vectors, where the norm $\|A\|_{p\to q}=n^{\frac{1}{q}-\frac{1}{p}}$ is attained, in the indicated range of $p$ and $q$.

Part (d) of the characterization provides a deceptively simple geometric interpretation of the problem: Describe the intersection of two tori. This geometric angle has been exploited to prove Theorem 3.4.

With the above characterization we close the motivational part of the paper and present our findings on the biunimodular problem.

U​(2)𝑈2U(2)

Obtaining biunimodular vectors of a given unitary $2\times 2$ matrix is an easy task.

Every matrix in $U(2)$ has a biunimodular vector.

Proof. Every matrix $A\in U(2)$ can be written as

where $\alpha=\arg x$ and $\beta=\arg y$. $\Box$

As we indicated in Section 2, the existence of biunimodular vectors for every matrix in $U(2)$ allows for writing an alternative formula describing $U(2)$.

Proof. Let $A\in U(2)$. Since $A$ has a biunimodular vector, by Theorem 4.1 we have that $A\in\mathcal{D}\cdot{\rm Fix}(\mathbf{1})\cdot\mathcal{D}_{1}$. Clearly, in this case

U​(3)𝑈3U(3)

Some elementary calculations allow to conclude that all orthogonal matrices in $O(3)$ have a biunimodular vector. Another easy case is given in the following.

For $A\in U(3)$ with at least one zero entry we shall explain how to exhibit its biunimodular vectors. By interchanging rows and columns of $A$ we can assume that there is a zero entry in the top right corner of $A$. Moreover, we can multiply rows and columns of $A$ by unimodular constants in such a way that the outcome shall have only real entries. Therefore, we can assume that $A$ is given as

Moreover, if $A$ has only one zero entry, then there are no other biunimodular vectors for $A$. It is also clear, that when $A$ has at least two zero entries, then at least one of its entries has modulus 1 leading to a trivialization of $A$ and a continuum of biunimodular vectors.

Whenever we talk about the number of biunimodular vectors for a given unitary matrix, we concentrate only on vectors with the leading entry equal to 1, as it was indicated in Remark 3.2. The above example explains the structure and the number of biunimodular vectors for $A\in U(3)$ in the case when $A$ has at least one zero entry. In the case when all entries of $A\in U(3)$ are nonzero, we have only found examples of matrices with the number of biunimodular vectors equal to 4,5 or 6.

In order to exhibit the method allowing to count biunimodular vectors of a given matrix $A\in U(3)$, let us consider a vector $u=u_{xy}=(1,e^{ix},e^{iy})$ and the square $Q=[-\pi,\pi]^{2}$. The idea is to look at three regions $R_{j}=\{(x,y)\in Q:|Au(j)|\geq 1\}$, $j=1,2,3$ and check the intersection of their boundaries.

For the Fourier case $A=F_{3}$ the corresponding three regions are given in Fig.1. The points where the boundaries of these regions intersect correspond to biunimodular vectors of $A$. From the unitarity of $A$ it follows that every intersection point of two such boundaries belongs to the boundary of the third region as well, allowing for a visual count of biunimodular vectors.

The next figure shows these regions for three exemplary unitary matrices providing the mentioned count of biunimodular vectors (conducted and plotted with Mathematica).

In general, since $A$ is unitary these closed regions cover $Q$, and therefore, any of these regions must intersect with at least one of the two other regions. Unfortunately, it is hard to argue that at least one pair of the regions intersects in such a way that their boundaries also intersect, closing a natural way to prove Theorem 6.3. This obstacle boils down to the lack of proof for a classification of the regions $R_{j}$, that essentially can be simplified to

A working proof that all $A\in U(3)$ have biunimodular vectors, that we give below, relies on findings of Section 8, that are included in Appendix A.

Every matrix in $U(3)$ has a biunimodular vector.

Proof. In Appendix A (Observation A.3) we prove that

Thus, in order to prove that every matrix in $U(3)$ has a biunimodular vector, it is enough to show it for the matrix $T_{(\alpha,\beta,\gamma,z)}$.

Then, the second entry of $v$ is given as $v_{2}=uz\cos\beta-e^{im}w\sin\beta$, where $u=e^{ix}\cos\gamma+e^{iy}\sin\gamma$. And $v_{3}=uz\sin\beta+e^{im}w\cos\beta$. In short,

with $j=1,2$ and concentrate on the final equation $\sin\alpha-w_{j}(m)\cos\alpha=e^{im}w_{j}(m)$.

so $\sin\alpha-e^{ix_{0}}w_{j_{0}}(m_{0})\cos\alpha=e^{im}e^{ix_{0}}w_{j_{0}}(m_{0})$, leading to the conclusion that $m_{0},j_{0}$ and $x_{0}$ solve (8) by setting $(e^{ix},e^{iy})=e^{ix_{0}}(1,(-1)^{j_{0}}ie^{i\varphi_{m_{0}}})$.

Thus, we are left with solving (9). Here, it is important to notice that the biunimodular vectors $(1,ie^{i\varphi_{m}})$ and $(1,-ie^{i\varphi_{m}})$ are orthogonal. Thus, if we define $f_{j}(m)=|w_{j}(m)|^{2}$ for $j=1,2$ and $m\in[0,2\pi]$, then $f_{1}(m)+f_{2}(m)=2\|(-\sin\gamma,\cos\gamma)\|_{2}^{2}=2$. Moreover, there is an $m_{1}\in[0,2\pi]$ such that $e^{im_{1}}=z$, and then $\varphi_{m_{1}}=0$ by (6), so $f_{1}(m_{1})=f_{2}(m_{1})=1$. Finally, let us notice that for $g(m)=\left|\frac{\sin\alpha}{e^{im}+\cos\alpha}\right|^{2}$ one has $\inf g=\left(\frac{|\sin\alpha|}{1+|\cos\alpha|}\right)^{2}\leq 1$ and $\sup g=\left(\frac{|\sin\alpha|}{1-|\cos\alpha|}\right)^{2}\geq 1$.

This allows to finish the proof. Indeed, if $f_{1}>g$ and $f_{2}>g$, then $1>g$ contradicting $\sup g\geq 1$. Similarly, if $f_{1}<g$ and $f_{2}<g$, then $1<g$ contradicting $\inf g\leq 1$. Thus, there is an $m_{2}\in[0,2\pi]$ such that $g(m_{2})$ is between $f_{1}(m_{2})$ and $f_{2}(m_{2})$. However, $g$ can not be strictly between $f_{1}$ and $f_{2}$ on $[0,2\pi]$, because $f_{1}(m_{1})=f_{2}(m_{1})$. Therefore, there is an $m_{0}\in[0,2\pi]$ such that either $g(m_{0})=f_{1}(m_{0})$ or $g(m_{0})=f_{2}(m_{0})$. $\Box$

As in the $U(2)$ case, the existence of biunimodular vectors for all members of $U(3)$ allows to write a formula for an arbitrary matrix in $U(3)$.

Proof. Let $A\in U(3)$. By Theorems 6.3 and 4.1 we have that $A\in\mathcal{D}\cdot{\rm Fix}(\mathbf{1})\cdot\mathcal{D}_{1}$. Moreover, in this case ${\rm Fix}(\mathbf{1})=F_{3}\cdot{\rm Fix}((1,0,0))\cdot F_{3}^{*}$, where $F_{3}$ is the Fourier transform and

due to the description of $U(2)$ provided in Corollary 5.2. Since $F_{3}=\frac{1}{\sqrt{3}}\begin{bmatrix}1&1&1\\ 1&\overline{\omega}&\omega\\ 1&\omega&\overline{\omega}\end{bmatrix}$we can finish the proof. $\Box$

Moreover, as a byproduct from the proof of Theorem 6.3 we obtain the following description of $U(3)$.

Proof. This follows from Observation A.3 used in the proof of Theorem 6.3 and the matrix factorization:

that leads to the provided description of $U(3)$ via easy matrix manipulations. $\Box$

The above description of $U(3)$ can be compared with the standard Euler-Tait-Bryan decomposition of $O(3)$:

U​(4)𝑈4U(4) and beyond

The above observation allows to construct matrices in $U(n)$ with all nonzero entries having a continuum of biunimodular vectors, whenever $n\geq 4$. It also allows for a further appreciation of Haagerup’s result stated in Theorem 1.2. It is not clear, however, whether for all unitary matrices with a continuum of biunimodular vectors one can find vectors $u$ and $w$ as in Observation 7.1. Even if this would be true, pointing to a conclusion that for any unitary matrix the set of its biunimodular vectors is a (finite) union of tori, it still would not tell, whether the set can be empty or not, underscoring the importance of Theorem 3.4.

In the next section, we provide an alternative way of building $U(2^{n})$, that is based solely on the biunimodular structure of $U(2)$. After that, we conduct the study of biunimodular vectors in the general $U(n)$ case from the Lie groups perspective. Finally, we present a numerical treatment of the biunimodular problem with certain applications to the classical Fourier case.

In this section we show, that a further generalization of the biunimodular problem allows to build all matrices in $U(2n)$ from matrices in $U(n)$.

In order to achieve this goal we employ the formula for $U(2)$ given in Section 5:

where $I$ stands for the identity matrix in $U(n)$.

Before we prove the theorem, we need a slim primary on block matrices. Let $M(n)$ denote the set of all $n\times n$ matrices with complex entries. An arbitrary matrix in $M(2n)$ can be written in a block form as $\begin{bmatrix}A&B\\ C&D\end{bmatrix}$ with $A,B,C,D\in M(n)$.

Clearly, we have that $\begin{bmatrix}A&B\\ C&D\end{bmatrix}\begin{bmatrix}A^{\prime}&B^{\prime}\\ C^{\prime}&D^{\prime}\end{bmatrix}=\begin{bmatrix}AA^{\prime}+BC^{\prime}&AB^{\prime}+BD^{\prime}\\ CA^{\prime}+DC^{\prime}&CB^{\prime}+DD^{\prime}\end{bmatrix}$ and $\begin{bmatrix}A&B\\ C&D\end{bmatrix}^{*}=\begin{bmatrix}A^{*}&C^{*}\\ B^{*}&D^{*}\end{bmatrix}$. Moreover, every $2n\times n$ matrix with complex entries can be written as $\begin{bmatrix}X\\ Y\end{bmatrix}$ with $X,Y\in M(n)$ and $\begin{bmatrix}A&B\\ C&D\end{bmatrix}\begin{bmatrix}X\\ Y\end{bmatrix}=\begin{bmatrix}AX+BY\\ CX+DY\end{bmatrix}$.

Let $\frac{1}{\sqrt{2}}\begin{bmatrix}A&B\\ C&D\end{bmatrix}\in U(2n)$ with $A\in U(n)$ and $B,C,D\in M(n)$. Then $B,C,D\in U(n)$.

Let $U=\frac{1}{\sqrt{2}}\begin{bmatrix}A&B\\ C&D\end{bmatrix}$ and $I\in U(n)$ be the identity matrix. Since $UU^{*}=\begin{bmatrix}I&0\\ 0&I\end{bmatrix}$ we get that $BB^{*}=I$. Considering $U^{*}U=\begin{bmatrix}I&0\\ 0&I\end{bmatrix}$ yields that $C^{*}C=I$ and $D^{*}D=I$. ∎

We can recognize the task as a special sort of a biunimodular problem. For an arbitrary unitary matrix $U\in U(2n)$ we need to find a unitary matrix $C\in U(n)$ such that $U\begin{bmatrix}I\\ C^{*}\end{bmatrix}$ is “unimodular”, in the sense that

In order to solve the biunimodular problem (12) we write $U=\begin{bmatrix}X&Y\\ X^{\prime}&Y^{\prime}\end{bmatrix}$ with $X,Y,X^{\prime},Y^{\prime}\in M(n)$ and apply the singular value decomposition (SVD) to $X$ and $Y$.

Recall that for an arbitrary matrix $M\in M(n)$ there are unitary matrices $W,W^{\prime}\in U(n)$ and a diagonal matrix with non-negative entries $\Sigma\in M(n)$ such that $M=W^{\prime}\Sigma W^{*}$. This leads to the polar decomposition $M=S_{M}U_{M}$ with $S_{M}=W^{\prime}\Sigma(W^{\prime})^{*}$ - a positive semi-definite matrix and a unitary matrix $U_{M}=W^{\prime}W^{*}\in U(n)$.

In short, we use polar decomposition $X=S_{X}U_{X}$, $Y=S_{Y}U_{Y}$ to write

with $A,B\in U(n)$ as desired, so $C^{*}=iU_{Y}^{*}U_{X}$ solves problem (12). To see this, we check that $A=(S_{X}+iS_{Y})U_{X}$ and $AA^{*}=S_{X}^{2}+S_{Y}^{2}+i(S_{Y}S_{X}-S_{X}S_{Y})$. Since $UU^{*}=\begin{bmatrix}I&0\\ 0&I\end{bmatrix}$ we get that $S_{X}^{2}+S_{Y}^{2}=I$, so $S_{X}^{2}$ and $S_{Y}^{2}$ commute. For positive semi-definite matrices $S_{X}$ and $S_{Y}$ this means that they commute as well and, therefore, $A\in U(n)$.

To finish the proof we make the final observation that $A\in U(n)$ already implies that $B\in U(n)$. Indeed, we can extend the matrix $\frac{1}{\sqrt{2}}\begin{bmatrix}I\\ C^{*}\end{bmatrix}$ to a unitary matrix $\frac{1}{\sqrt{2}}\begin{bmatrix}I&C\\ C^{*}&-I\end{bmatrix}\in U(2n)$ and see that $\frac{1}{\sqrt{2}}U\begin{bmatrix}I&C\\ C^{*}&-I\end{bmatrix}=\frac{1}{\sqrt{2}}\begin{bmatrix}A&X^{\prime\prime}\\ B&Y^{\prime\prime}\end{bmatrix}\in U(2n)$. Since $A$ is unitary, Lemma 8.2 assures that $B\in U(n)$.

U​(n)𝑈𝑛U(n)

Moreover, let us make the following formal definition:

Clearly, $\mathcal{B}_{n}$ is the set of $n\times n$ unitary matrices that possess biunimodular vectors and Theorem 3.4 asserts that $\mathcal{B}_{n}=U(n)$. While it would be hard to reproduce this result, one can check what information about $\mathcal{B}_{n}$ and ${\hbox{Bi}}(A)$ can be drawn by using basic tools of Lie groups theory.

containing the entire information concerning the existence of biunimodular vectors.

Indeed, the matrices possessing biunimodular vectors are given as the image of $\Phi$, what already provides some information on $\mathcal{B}_{n}$.

$\mathcal{B}_{n}=\mathcal{D}\cdot{\rm Fix}(\mathbf{1})\cdot\mathcal{D}_{1}=\Phi(\mathcal{D}\times{\rm Fix}(\mathbf{1})\times\mathcal{D}_{1})$. In particular, $\mathcal{B}_{n}$ is a closed, pathwise connected subset of $U(n)$.

Proof. As we mentioned before, the equality $\mathcal{B}_{n}=\mathcal{D}\cdot{\rm Fix}(\mathbf{1})\cdot\mathcal{D}_{1}$ follows immediately from Theorem 4.1(a). Thus, by definition, $\mathcal{B}_{n}=\Phi(\mathcal{D}\times{\rm Fix}(\mathbf{1})\times\mathcal{D}_{1})$. Since the subgroups $\mathcal{D},\,{\rm Fix}(\mathbf{1}),\,\mathcal{D}_{1}$ are compact and pathwise connected, $\mathcal{B}_{n}$, which is the continuous image of their cartesian product, has the same properties. $\Box$

Moreover, the preimage $\Phi^{-1}(A)$ bijectively corresponds to ${\hbox{Bi}}(A)$.

There is a continuous bijection between ${\hbox{Bi}}(A)$ and $\Phi^{-1}(A)$.

$U(n)$ has (real) dimension $n^{2}$, whereas ${\rm Fix}(\mathbf{1})\cong U(n-1)$ is of dimension $(n-1)^{2}$. $\mathcal{D}$ has dimension $n$ and $\mathcal{D}_{1}$ has dimension $n-1$, hence $\Phi$ is a mapping between two manifolds of (real) dimension $n^{2}$. Clearly, $\Phi$ is smooth.

In order to proceed with the calculations we provide some basic facts from the theory of Lie groups and establish the necessary notation.

Since multiplication (on the left or on the right) with a group element $g$ is a diffeomorphism on $H$, that is a matrix group, one obtains that

We let $\mathfrak{u},\mathfrak{d},\mathfrak{d}_{1},\mathfrak{f}$ denote the Lie algebras of $U(n),\mathcal{D},\mathcal{D}_{1},{\rm Fix}(\mathbf{1})$, respectively. Then

$\mathfrak{d}$ consists of all diagonal matrices with purely imaginary entries, and $\mathfrak{d}_{1}\subset\mathfrak{d}$ is the subspace of matrices with vanishing upper left corner. Differentiating the equality $\exp(tX)\mathbf{1}=\mathbf{1}$ at $t=0$ yields the following description of $\mathfrak{f}$:

i.e. the elements of $\mathfrak{f}$ are characterized by the fact that the sum over rows are zero. We also note the simple fact that $\mathfrak{d}\cap\mathfrak{f}=\{0\}$.

To calculate the Jacobian of $\Phi:\mathcal{D}\times{\rm Fix}(\mathbf{1})\times\mathcal{D}_{1}\to U(n)$ we shall use the following

Let $H_{1},\,H_{2}$ be closed subgroups of $U(n)$ and $m:H_{1}\times H_{2}\to U(n)$, $m(g,h)=g\cdot h$. Then, for all $g,h\in U(n)$, the Jacobian of $m$ at $(g,h)$ is given by

Proof. Let $\gamma_{i}:(-\epsilon,\epsilon)\to H_{i}$ denote smooth curves with

By a standard reasoning, the product rule for scalar-valued functions easily extends to matrix-valued functions implying that

Using this lemma and the chain rule, we obtain a rather transparent description of the Jacobian $d\Phi(D_{1},S,D_{2})$:

Let $(D_{1},S,D_{2})\in\mathcal{D}\times{\rm Fix}(\mathbf{1})\times\mathcal{D}_{1}$. Then

applying the previous lemma twice and using the chain rule yields

Recall that we are particularly interested in the rank of $d\Phi$, that is, the real dimension of the image of $d\Phi$. The following lemma translates this to a more tractable problem in linear algebra:

For all (any) $(D_{1},D_{2})\in\mathcal{D}\times\mathcal{D}_{1}$ the Jacobian $d\Phi(D_{1},S,D_{2})$ has rank $m$.

Proof. For the equivalence (a) $\Leftrightarrow$ (b) we observe that $\Phi(CD_{1},S,D_{2}C^{\prime})=C\Phi(D_{1},S,D_{2})C^{\prime}$ for all $C\in\mathcal{D}$, and $C^{\prime}\in\mathcal{D}_{1}$. Thus, by the chain rule, $d\Phi(CD_{1},S,D_{2}C^{\prime})=Cd\Phi(D_{1},S,D_{2})C^{\prime}$, what yields the equivalence.

To see that (b) $\Leftrightarrow$ (c) we note, that by the previous lemma, $d\Phi(I,S,I)(X,Y^{\prime},Z)=XS+Y^{\prime}+SZ$, for all $X\in\mathfrak{d},Y^{\prime}\in T_{S}({\rm Fix}(\mathbf{1})),Z\in\mathfrak{d}_{1}$. Since $S$ is invertible, the rank of $d\Phi(I,S,I)$ equals the rank of $R_{S^{*}}\circ d\Phi(I,S,I)$, where $R_{S^{*}}$ denotes right multiplication with $S^{*}$. Clearly, $R_{S^{*}}\circ d\Phi(I,S,I)(X,Y^{\prime},Z)=X+Y^{\prime}S^{*}+SZS^{*}$ and this map has the same rank as the map $C_{S}$ from (c), since $Y=Y^{\prime}S^{*}\in\mathfrak{f}$ iff $Y^{\prime}\in T_{S}({\rm Fix}(\mathbf{1}))$. $\Box$

Proof. Let $C_{S}:\mathfrak{d}\times\mathfrak{f}\times\mathfrak{d}_{1}\to\mathfrak{u}$ denote the linear map from Lemma 9.6. Let $\mathfrak{n}=\mathfrak{d}+\mathfrak{f}\subset\mathfrak{u}$. Then $\mathfrak{d}\cap\mathfrak{f}=\{0\}$ implies that the restriction of $C_{S}$ to $\mathfrak{d}\times\mathfrak{f}$ is an isomorphism onto $\mathfrak{n}$. This allows for the first step towards (13) by considering the quotient map

By Lemma 9.6 and a rank formula for the quotient map we obtain that

Thus, we have established that ${\rm rank}(\overline{C_{S}})={\rm rank}({\rm Im}(S))$, so equation (13) follows from (14).

Thus, Lemma 9.7 implies that ${\rm rank}(d\Phi(I,S,I))=n^{2}$. $\Box$

With the above lemma we can draw the mentioned conclusion regarding the structure of $\mathcal{B}_{n}$.

Proof. By Proposition 9.1 $\mathcal{B}_{n}=\Phi(\mathcal{D}\times{\rm Fix}(\mathbf{1})\times\mathcal{D}_{1})$ and $\Phi$ is a map between groups of dimension $n^{2}$. Lemma 9.8 guarantees an existence of a point in $\mathcal{D}\times{\rm Fix}(\mathbf{1})\times\mathcal{D}_{1}$, where the Jacobian of $\Phi$ has the full rank. Therefore, by the inverse function theorem, $\Phi$ is a diffeomorphism around this point. $\Box$

$\mathcal{B}_{n}=U(n)$ if and only if $\mathcal{B}_{n}\cdot\mathcal{B}_{n}\subset\mathcal{B}_{n}$.

Proof. Clearly, $A\in\mathcal{B}_{n}$ iff $A^{-1}\in\mathcal{B}_{n}$. Therefore, $\mathcal{B}_{n}$ is a symmetric subset of $U(n)$ that, by the above theorem, has a nonempty open interior. If, in addition, it is closed under multiplication, then $\mathcal{B}_{n}$ must be an open subgroup. Since $U(n)$ is connected, it follows that $\mathcal{B}_{n}=U(n)$. The converse is clear. $\Box$

The results of this subsection can be compared with a theorem of De Vos and De Baerdemacker based on Hurwitz parametrization and stating that $(\mathcal{B}_{n})^{n-1}=U(n)$.

3 The structure of Bi​(A)Bi𝐴{\hbox{Bi}}(A)

Regarding the structure of ${\hbox{Bi}}(A)$ it is crucial to recall Conjecture 1.1. In light of the hypothesis imposed by Björck and Saffari, the main issue is to establish the cardinality of ${\hbox{Bi}}(A)$. Therefore, there is a merit in proving the following.

For almost all $A\in U(n)$ the set ${\hbox{Bi}}(A)$ is finite.

Proof. This follows from Proposition 9.2 and Sard’s theorem. By Proposition 9.2 we can replace ${\hbox{Bi}}(A)$ by $\Phi^{-1}(A)$. Clearly, we can concentrate on the case $\Phi^{-1}(A)\not=\emptyset$. Recall that the regular points of a smooth map are those for which the rank of the Jacobian is full; any point that is not regular is called critical. A regular value is a value, such that all the points in the preimage are regular. If $A$ is a regular value of $\Phi$, then $\Phi^{-1}(A)$ must be a discrete subset of the compact space $\mathcal{D}\times{\rm Fix}(\mathbf{1})\times\mathcal{D}_{1}$, hence finite. Thus, if $\Phi^{-1}(A)$ is infinite, then $A$ must be the image of a critical point of $\Phi$. However, Sard’s theorem states that the images of the critical points constitute a set of the Haar measure zero, what concludes the proof.

In order to achieve a deeper understanding of the set ${\hbox{Bi}}(A)$ for a given $A\in U(n)$, we consider the phasing manifold of $A$

introduced in , and the stabilizer group $\mathcal{D}_{A}=\{(E_{1},E_{2})\in\mathcal{D}\times\mathcal{D}_{1}:E_{1}AE_{2}=A\}$.

By Proposition 9.2 the next result establishes a bijection

that can be explained in the following way. Intuitively, finding all biunimodular vectors for $A$ amounts to finding all $S\in{\rm Fix}(\mathbf{1})$ for which there exists a pair $(D_{1},D_{2})\in\mathcal{D}\times\mathcal{D}_{1}$ such that $A=D_{1}SD_{2}$ (i.e. $S=D_{1}^{-1}AD_{2}^{-1}\in\mathcal{M}_{A}$) and, after that, finding other such pairs for $S$ by considering the set $\{(D_{1}E_{1},D_{2}E_{2}):(E_{1},E_{2})\in\mathcal{D}_{A}\}$. We shall prove that this simple scheme yields all members of ${\hbox{Bi}}(A)$ in a one-to one fashion.

There is a bijection $\Psi:\left(\mathcal{M}_{A}\cap{\rm Fix}(\mathbf{1})\right)\times\mathcal{D}_{A}\to\Phi^{-1}(A)$.

Proof. We can pick a map $\psi:\mathcal{M}_{A}\cap{\rm Fix}(\mathbf{1})\to\mathcal{D}\times\mathcal{D}_{1}$, $\psi(S)=(\psi_{1}(S),\psi_{2}(S))$, such that $\psi_{1}(S)\,S\,\psi_{2}(S)=A$. Indeed, by definition, for every $S\in\mathcal{M}_{A}\cap{\rm Fix}(\mathbf{1})$ there is $(D_{1},D_{2})\in\mathcal{D}\times\mathcal{D}_{1}$, such that $S=D_{1}AD_{2}$, thus we can pick one of such pairs and set $(\psi_{1}(S),\psi_{2}(S))=(D_{1}^{-1},D_{2}^{-1})$.

Then, the map $\Psi:\left(\mathcal{M}_{A}\cap{\rm Fix}(\mathbf{1})\right)\times\mathcal{D}_{A}\to\Phi^{-1}(A)$ is given by

To see that the image of $\Psi$ is contained in $\Phi^{-1}(A)$, it is enough to note that

The map is one-to-one, since $\Psi\left(S,(E_{1},E_{2})\right)=\Psi\left(S^{\prime},(E^{\prime}_{1},E^{\prime}_{2})\right)$ implies that $S=S^{\prime}$ and this, in turn, implies that $E_{i}=E_{i}^{\prime}$, for $i=1,2$. To check that the map is onto, we take an arbitrary element $(G_{1},S,G_{2})\in\Phi^{-1}(A)$ and easily verify that $\Psi\left(S,(E_{1},E_{2})\right)=(G_{1},S,G_{2})$ with $E_{i}=G_{i}\,(\psi_{i}(S))^{-1}$, for $i=1,2$. Since $G_{1}(\psi_{1}(S))^{-1}A\,(\psi_{2}(S))^{-1}G_{2}=G_{1}SG_{2}=A$, we get that $(E_{1},E_{2})\in\mathcal{D}_{A}$ and end the proof. $\Box$

Since in the above theorem it is hard to guarantee the continuity of $\psi$, we can not conclude that the bijection $\Psi$ is continuous. We mention this, because otherwise, by Proposition 9.2 the set ${\hbox{Bi}}(A)$ would be homeomorphic to $(\mathcal{M}_{A}\cap{\rm Fix}(\mathbf{1}))\times\mathcal{D}_{A}$.

With Theorem 9.12, we can concentrate on the set $\left(\mathcal{M}_{A}\cap{\rm Fix}(\mathbf{1})\right)\times\mathcal{D}_{A}$, in order to investigate the cardinality of ${\hbox{Bi}}(A)$. For that, we need a better understanding of the phasing manifold $\mathcal{M}_{A}$, for a given $A\in U(n)$. This can be obtained by defining the mapping

and noting that $\mathcal{M}_{A}=\Phi_{A}(\mathcal{D}\times\mathcal{D}_{1})$. This setup allows for making some useful observations.

For every $A\in U(n)$ the set $\mathcal{M}_{A}$ is the orbit of $A$ under the left action of $\mathcal{D}\times\mathcal{D}_{1}$ on $U(n)$ given by $\left((D_{1},D_{2}),A\right)\mapsto D_{1}AD_{2}$. In particular, $\mathcal{M}_{A}$ is a closed submanifold of $U(n)$ with $\mathcal{M}_{A}\simeq\left(\mathcal{D}\times\mathcal{D}_{1}\right)/\mathcal{D}_{A}$, so ${\rm dim}(\mathcal{M}_{A})+{\rm dim}(\mathcal{D}_{A})=2n-1$.

Proof. Note that the map $\left((D_{1},D_{2}),A\right)\mapsto D_{1}AD_{2}$ indeed defines an action of the product group, since the diagonal group is commutative; and clearly $\mathcal{M}_{A}$ is the orbit of $A$. The remaining statements follow from this: $\Phi_{A}$ is just the quotient map with respect to this action, what implies that the differential of $\Phi_{A}$ has constant rank; and this in turn allows to define a manifold structure on $\mathcal{M}_{A}$. In addition, $\mathcal{M}_{A}$ is compact, hence closed, and $\Phi_{A}$ induces a continuous bijection $\left(\mathcal{D}\times\mathcal{D}_{1}\right)/\mathcal{D}_{A}\to\mathcal{M}_{A}$ between compact Hausdorff spaces, which then has to be a homeomorphism. Therefore, ${\rm dim}(\mathcal{M}_{A})+{\rm dim}(\mathcal{D}_{A})={\rm dim}(\mathcal{D}\times\mathcal{D}_{1})=2n-1$. $\Box$

${\rm dim}(\mathcal{M}_{A})=2n-1\iff{\rm dim}(\mathcal{D}_{A})=0\iff\mathcal{D}_{A}{\rm\,\,\,is\,\,finite.}$

The first equivalence follows immediately from the dimension formula given in the above lemma. In the second equivalence one implication is obvious. For the other implication we note that, if ${\rm dim}(\mathcal{D}_{A})=0$ then $\mathcal{D}_{A}$ must be a discrete subgroup of the compact group $\mathcal{D}\times\mathcal{D}_{1}$, so it must be finite. ∎

At this stage we can provide the following explanation on the cardinality $|{\hbox{Bi}}(A)|$ of ${\hbox{Bi}}(A)$.

Obviously, for $n=1$ we have $|{\hbox{Bi}}(A)|=1$. When $n=2$, then $|{\hbox{Bi}}(A)|$ equals to 2 or to the continuum $\mathfrak{c}$. For $n=3$ we have only found examples where $|{\hbox{Bi}}(A)|$ equals to 4, 5, 6 or $\mathfrak{c}$. By Theorem 9.12, $|{\hbox{Bi}}(A)|$ is equal to the cardinality of the set $\left(\mathcal{M}_{A}\cap{\rm Fix}(\mathbf{1})\right)\times\mathcal{D}_{A}$. Therefore, to see the general picture, we employ the above corollary together with Theorem 3.4 and get the following:

If ${\rm dim}(\mathcal{M}_{A})<2n-1$ then $|{\hbox{Bi}}(A)|=\mathfrak{c}$.

If ${\rm dim}(\mathcal{M}_{A})=2n-1$ then

${\hbox{Bi}}(A)$ is infinite but countable (no examples) or

Regarding the case ${\rm dim}(\mathcal{M}_{A})<2n-1$, it is clear that for the identity matrix $I$ (and any diagonal matrix) we have that $\mathcal{M}_{I}=\mathcal{D}$, so ${\rm dim}(\mathcal{M}_{I})=n$. Moreover, there are examples of matrices $A\in U(n)$ with ${\rm dim}(\mathcal{M}_{A})$ in the range from $n$ to $2n-1$.

We would like to end this section by getting closer to understanding the classical Fourier case. As it turns out, for the Fourier matrix $F_{n}$ the stabilizer $\mathcal{D}_{F_{n}}$ is trivial.

The above lemma together with Theorem 9.12 and Lemma 9.14 entail the following information on the set of all biunimodular vectors in the classical Fourier case.

The above theorem indicates the resilience of Conjecture 1.1. Another approach towards this conjecture has been designed by Gabidulin. Unfortunately, even in the prime case, where some details are provided, he does not explain how to exclude that ${\hbox{Bi}}(F_{n})$ is infinite but countable. Therefore, the only accessible confirmation of the conjecture in the prime case is .

Numerical Results

so that $v={\hbox{sign}}(v)|v|$. Since (15) holds for all $v$ with $|v|\leq 1$, we can safely define ${\hbox{sign}}(v)$ as zero on the complement of the support of $v$.

In this way we rediscover a phase retrieval method that has a pretty long history. To make it short, following Jaming we recall that as early as 1932, Pauli was asking whether the information on the moduli of a wave function and its Fourier transform allows to recover the phase of the wave function (i.e. Having $|\psi|$ and $|{\cal F}\psi|$ can we recover $\psi$?). In practice, the phase retrieval problem is a serious obstacle for analysing complex valued signals, since only partial information is given on $|\psi|$ (see by Candès et al. or and for recent developments on this notorious problem). Nevertheless, under original Pauli constrains, a method for recovering the phase of a signal has been provided in 1972 by Gerchberg and Saxton (see ). Gerchberg-Saxton algorithm has several variants, and the one that is relevant to us takes the following form. Let $|\psi|=g$ and $|{\cal F}\psi|=h$. In order to recover $\psi$ define

and starting with an $f_{0}$ such that $|f_{0}|=g$, run $f_{j}=P_{gh}^{j}(f_{0})$ until it converges to a solution $\psi^{\prime}$.Unfortunately, $\psi^{\prime}$ is not unique (it depends on the choice of $f_{0}$), so it is only a candidate for $\psi$ (see Subsection 10.3). This algorithm can be viewed as an alternating projection method for finding an intersection of two subsets of a Hilbert space, that was discovered by von Neumann in 1933 (), in the case when the subsets are closed subspaces. This view is justified by writing $P_{gh}$ as $P_{G}\circ P_{H}$, where $P_{G}f=g\,{\hbox{sign}}_{1}(f)$ and $P_{H}f={\cal F}^{*}(h\,{\hbox{sign}}_{1}({\cal F}f)))$ are projections on certain subsets of a Hilbert space.

instead of $P^{\prime}_{A}$, we shall quickly confine our search to the range where both these operators agree. Thus, we shall refer to this method as “alternating projection algorithm” anyway.

so $|Av|\geq\frac{1}{2}$ for $\delta\leq\frac{1}{8}$. Moreover, for such $\delta$ we get

so $|A^{*}({\hbox{sign}}(Av))|\geq\frac{1}{2}$ as well. This allows to draw the following conclusions.

If the stopping condition $(\ref{delta0})$ is satisfied, then $\|\mathbf{1}-|AV_{J}|\|_{2}<\sqrt{2\delta}$. If the initial condition