Unlabeled Sensing Using Rank-One Moment Matrix Completion

In this subsection, we prove the following theorem, which implies that one can obtain the unique and desired vector $\xi^{*}$ for a generic matrix $A^{*}$ and a permutation $y^{*}$ of a generic vector in the column space of $A^{*}$ by solving the polynomial system $Q_{m}$.

When $m=n+1$, the morphism $g$ equals $f$, i.e., Theorem 2 implies Theorem 1 in this special case.

We decompose $g$ into the composition of two dominant morphisms $\alpha$ and $\beta$ defined by (9) and (12) respectively. To show $g$ is birational, it suffices to show $\alpha$ and $\beta$ are birational.

Define the morphism $\alpha$

where $D_{n+1}(A|y)$ is the zero locus of the all $(n+1)$-minors of the matrix $(A|y)$, $A=[a_{ij}]$ is a $m$-by-$n$ matrix of $mn$ variables and $y=[y_{i}]$ is a column vector of $m$ variables, ${i\in[m],j\in[n]}$. Namely, $D_{n+1}(A|y)$ is the determinantal variety consisting of $m$-by-$(n+1)$ matrices of rank less than $n+1$. The determinantal variety $D_{n+1}(A|y)$ is irreducible [6, Proposition 1.1], i.e., it is not a union of any two proper closed subvarieties.

The second dominant morphism, to be shown to be birational, is

Note that $\beta$ is the restriction of the finite morphism

hence $\beta$ is also a finite and closed morphism [22, Chapter II, Exercise 3.5], and

To prove the following Lemma 2, we shall first clarify the actions of $\Sigma_{m}$ on both $\mathbb{C}^{m\times n}\times\mathbb{C}^{m}$ and $\mathbb{C}[A,y]$.

A permutation $\sigma\in\Sigma_{m}$ acts on $\mathbb{C}[A,y]$ as a $\mathbb{C}$-algebra isomorphism given by $\sigma(y_{i})=y_{\sigma(i)}$ and fixing $A$. Then for any $f\in\mathbb{C}[A,y]$ and $y^{*}=(y_{1}^{*},\dots,y_{m}^{*})\in\mathbb{C}^{m}$, we have

A permutation $\sigma\in\Sigma_{m}$ acts on $y^{*}=(y_{1}^{*},\dots,y_{m}^{*})\in\mathbb{C}^{m}$ by

Then $(\sigma(f))(y^{*})=f\left(\sigma^{-1}(y^{*})\right)$. This action induces the fiberwise action of $\Sigma_{m}$ on $\mathbb{C}^{m\times n}\times\mathbb{C}^{m}$, i.e., for $(A^{*},y^{*})\in\mathbb{C}^{m\times n}\times\mathbb{C}^{m}$, we define

For the variable vector $y=[y_{1},\dots,y_{m}]$,

is also a vector of variables, and we denote by $D_{n+1}(A|\sigma(y))$ the determinantal variety on which all the $(n+1)$-minors of $(A|\sigma(y))$ vanish. Then we have

Now Theorem 2 follows, because $g$ is the composition of the birational morphisms $\alpha$ and $\beta$.

To show the morphism $\gamma$ in (7) is birational, we need the projection

Notice that $(A^{*},p_{1}(\eta^{*}),\dots,p_{n+1}(\eta^{*}))$ is a point in $f(\mathbb{C}^{m\times n}\times\mathbb{C}^{n})$. Hence, $\delta$ is uniquely determined by (21).

Now we give the sketch of the proof that the morphism $\gamma$ is birational.

• •

  For generic $(A^{*},w^{*})\in\mathbb{C}^{m\times n}\times\mathbb{C}^{n}$, the fiber $(\delta\gamma g)^{-1}(A^{*},w^{*})$ consists of at most $n!$ points [62, Theorem 2] . Since $g$ is birational, we deduce that the fiber $(\delta\gamma)^{-1}(A^{*},w^{*})$ also generically consists of at most $n!$ points. Hence, it suffices to show that $\delta$ is also a generically finite morphism with generic covering degree $n!$.

• •

  Let $A=[a_{ij}]_{m\times n},t=[t_{1},\dots,t_{n}]$ and $z=[z_{1},\dots,z_{n+1}]$ be the matrix and vectors in variables $a_{ij}$, $t_{i},z_{j}$ respectively. Let $R(A,z)\in\mathbb{Z}[A,z]$ and $c(A)\in\mathbb{Z}[A]$ be the resultants of the polynomial systems

  	$$\displaystyle\{p_{k}(At)-z_{k}:k=1,\dots,n+1\},$$		(22)
  	$$\displaystyle\{p_{k}(At):k=1,\dots,n\}$$		(23)

  eliminating the variables $t_{1},\ldots,t_{n}$, respectively. We shall show that

  1. (i)

     The leading term of $R(A,z)$ in $z_{n+1}$ is $c(A)^{n+1}z_{n+1}^{n!}$;

  2. (ii)

     $R(A,p_{1}(Ax),\dots,p_{n+1}(Ax))=0$;

  3. (iii)

     $R(A,z)$ is irreducible in $\mathbb{C}(A,z_{1},\dots,z_{n})[z_{n+1}]$.

  • –

    To show (i), we use Macaulay’s assertions on resultants [40, Section 8] to deduce that $\deg_{z_{n+1}}(R(A,z))\leqslant n!$ and the coefficient of $z_{n+1}^{n!}$ in $R(A,z)$ is $c(A)^{n+1}$. According to Lemma 4 in [62], $p_{1}(A^{*}t),\dots,p_{n}(A^{*}t)$ is a homogeneous regular sequence of $\mathbb{C}[t]$ for generic matrix $A^{*}\in\mathbb{C}^{m\times n}$, hence $p_{1}(At),\dots,p_{n}(At)$ is also a homogeneous $\mathbb{C}(A)[t]$-regular sequence. Thus, the system (23) in variables $t$ has no solution in the projective $(n-1)$-space over the algebraic closure of $\mathbb{C}(A)$. Therefore, [40, Section 10] asserts that $c(A)$ is nonzero in $\mathbb{C}[A]$, whence the leading term of $R(A,z)$ in $z_{n+1}$ is $c(A)^{n+1}z_{n+1}^{n!}$.

    Moreover, the fact that $p_{1}(At),\dots,p_{n}(At)$ is a homogeneous $\mathbb{C}(A)[t]$-regular sequence implies that the field extension degree

    $$[\mathbb{C}(A,x):\mathbb{C}(A,p_{1}(Ax),\dots,p_{n}(Ax))]=n!$$

    is the product of the degrees of $p_{k}(At),k\in[n]$ in $t$. This fact also implies that for generic $(A^{*},w^{*})\in\mathbb{C}^{m\times n}\times\mathbb{C}^{n}$, the fiber $(\delta\gamma)^{-1}(A^{*},w^{*})$ consists of $n!$ points.

  • –

    To show (ii), we notice that the system (22) substituting $z_{k}$ with $p_{k}(Ax)$ has a solution $t=x$ in the affine space over the algebraic closure of $\mathbb{C}(A,p_{1}(Ax),\dots,p_{n+1}(Ax))$. According to arguments in [40, Section 10], we know that

    $$R(A,p_{1}(Ax),\dots,p_{n+1}(Ax))=0.$$

  • –

    To show (iii), let $\overline{A}$ be the first $n+1$ rows of $A$, and $A_{>n+1}$ be the last $m-(n+1)$ rows of $A$. Then

    1. (a)

       $R\left(\overline{A},z\right)\equiv R(A,z)\mod A_{>n+1}$, and $c\left(\overline{A}\right)\neq 0$;

    2. (b)

       The leading term of $R\left(\overline{A},z\right)$ in $z_{n+1}$ is $c\left(\overline{A}\right)^{n+1}z_{n+1}^{n!}$;

    3. (c)

       $R\left(\overline{A},p_{1}\left(\overline{A}x\right),\dots,p_{n+1}\left(\overline{A}x\right)\right)=0$;

    4. (d)

       $\left[\mathbb{C}\left(\overline{A},x\right):\mathbb{C}\left(\overline{A},p_{1}\left(\overline{A}x\right),\dots,p_{n}\left(\overline{A}x\right)\right)\right]=n!$.

    Note that the birational morphism $g$ for the case $m=n+1$ implies that

    $$\mathbb{C}\left(\overline{A},p_{1}\left(\overline{A}x\right),\dots,p_{n+1}\left(\overline{A}x\right)\right)=\mathbb{C}\left(\overline{A},x\right),$$

    hence the polynomial $R\left(\overline{A},p_{1}\left(\overline{A}x\right),\dots,p_{n}\left(\overline{A}x\right),z_{n+1}\right)$ in $z_{n+1}$ is irreducible over $\mathbb{C}\left(\overline{A},p_{1}\left(\overline{A}x\right),\dots,p_{n}\left(\overline{A}x\right)\right)$. Since $p_{1}\left(\overline{A}x\right),\dots,p_{n}\left(\overline{A}x\right)$ is $\mathbb{C}\left(\overline{A}\right)[x]$-regular, $R\left(\overline{A},z\right)$ in $z_{n+1}$ is also irreducible over $\mathbb{C}\left(\overline{A},z_{1},\dots,z_{n}\right)$. Using Gauss’ Lemma, we see that any factorization $R(A,z)=uv$ in $\mathbb{C}(A,z_{1},\dots,z_{n})[z_{n+1}]$ induces a factorization $R(A,z)=u_{1}v_{1}$ in $\mathbb{C}[A,z]$ satisfying

    $$\deg_{z_{n+1}}u_{1}=\deg_{z_{n+1}}u,~{}\deg_{z_{n+1}}v_{1}=\deg_{z_{n+1}}v$$

    and the leading coefficients of $u_{1}$ and $v_{1}$ in $z_{n+1}$ ly in $\mathbb{C}[A]$. Modulo $A_{>n+1}$ and noticing that $c\left(\overline{A}\right)^{n+1}\neq 0$ is the leading coefficient of $R\left(\overline{A},z\right)$, we deduce that $R\left(\overline{A},z\right)=\overline{u_{1}}\overline{v_{1}}$, $\deg_{z_{n+1}}\overline{u_{1}}=\deg_{z_{n+1}}u_{1}$ and $\deg_{z_{n+1}}\overline{v_{1}}=\deg_{z_{n+1}}v_{1}$. Thus, $R(A,z)$ is irreducible over $\mathbb{C}(A,z_{1},\dots,z_{n})$.

  Hence, the algebraic field extension degree

  $$[\mathbb{C}(A,p_{1}(Ax),\dots,p_{n+1}(Ax)):\mathbb{C}(A,p_{1}(Ax),\dots,p_{n}(Ax))]=n!$$

  coincides with

  $$[\mathbb{C}(A,x):\mathbb{C}(A,p_{1}(Ax),\dots,p_{n}(Ax))]=n!,$$

  which implies that $\delta$ is a generically finite morphism with a generic covering degree $n!$, and

  $$\mathbb{C}(A,p_{1}(Ax),\dots,p_{n+1}(Ax))=\mathbb{C}(A,x),$$

  namely, $\gamma$ is birational, and Theorem 1 follows. We refer to [37] for detailed proof of the above arguments.