A small frame and a certificate of its injectivity

I Translation to polynomials

Following the set up of , we translate the injectivity of measurements into a condition on the solutions of a system of polynomial equations.

A useful step is the following reformulation of injectivity by Bandeira et. al. [4, Lemma 9]. They observe that a frame $\Phi$ defines injective measurements if and only if the linear space

does not contain any non-zero Hermitian matrices of rank $\leq 2$. The existence of rank $\leq 2$ Hermitian matrices in $\mathcal{L}_{\Phi}$ can be rephrased as the existence of real roots of a certain system of polynomial equations as follows.

Any $4\times 4$ Hermitian matrix can be written as $Q=$

where $x_{11},\ldots,y_{34}$ are real numbers. We will write our polynomial condition for injectivity in the 16 variables $x_{jk},y_{jk}$. For $1\leq j,k\leq 4$, let $m_{jk}$ denote the determinant of the $3\times 3$ matrix obtained by removing the $j$th row and $k$th column from the matrix $Q$. The matrix $Q$ has rank $\leq 2$ when all these minors $m_{jk}$ equal zero.

II A small injective frame

The frame $\Phi=(\phi_{1},\ldots,\phi_{11})$, consisting of the rows of the matrix

Apart from the coordinate vectors, the vectors of $\Phi$ were chosen to have first coordinate 1 and otherwise found by a random search. This matrix is by no means unique, as further discussed in Section III.

$\Phi$ in (2) defines injective measurements.

Using the set-up of Section I, it suffices to show the equations (1) have no non-zero real solution.

Such a certificate verifies that $f(x_{34},y_{34})=0$ for all solutions to (1). Unfortunately the polynomial multipliers $p_{jk}$, $q_{k}$ involved are too large to reproduce here.

These computations complete the certification that there are no non-zero solutions to the system of equations (1). Thus there are no non-zero Hermitian matrices of rank $\leq 2$ in the linear space $\mathcal{L}_{\Phi}$ and, by [4, Lemma 9], the frame $\Phi$ defines injective measurements.

The code for these computations in both Macaulay2 and Mathematica are available at http://www4.ncsu.edu/~clvinzan/smallFrame.html. ∎

Solving the system of equations (1) numerically, we see that, up to scaling, there are exactly twenty rank-2 matrices in the linear space $\mathcal{L}_{\Phi}$. These are in one-to-one correspondence with the twenty complex roots of the polynomial $f(x_{34},1)$. As none of these roots are real, none of the rank-2 matrices in $\mathcal{L}_{\Phi}$ are Hermitian. For example, the solution $(x_{34},y_{34})\approx(1.95+2.08i,1)$ corresponds to the rank-2 matrix

and its conjugate, $(x_{34},y_{34})\approx(1.95-2.08i,1)$, gives

Because the certificates used in the proof of Theorem 1 are too large to give here, we now present a much smaller example of the computations involved.

Suppose we want to show that there is no rank-one Hermitian matrix of the form

III The set of injective frames

For example, we can replace the last vector of $\Phi$,

Acknowledgements. Thanks to Bernhard Bodmann for his encouragement and interest in this problem. The author was supported by an NSF postdoc DMS-1204447.

References