%      Unitary Invariance of the Kostlan norm
%        (Linear Algebra proof)
%
%      by Gregorio Malajovich
%         gregorio@labma.ufrj.br
%
%
%      This is an AMS-Latex file.
%      AMS-Latex is a kind of upgrade of Latex, by the AMS.
%      Its primary distrbution site is e-math.ams.com
%      It can be reached by anonymous ftp.
%
% -----------------------------------------------------------------
\documentstyle[12pt]{amsart}

\newcommand{\aff}{^{\text {\rm aff}}}
\newcommand{\proj}{^{\text {\rm proj}}}
\newcommand{\pseu}{^{\text {\rm pseu}}}
\newcommand{\rtrans}{^{\text{\rm t}}}
\newcommand{\ctrans}{^{\text{\rm *}}}
\newcommand{\dproj}{d_{\text{\rm proj}}}
\newcommand{\exact}{_{\text{\rm exact}}}
\newcommand{\appr}{_{\text{\rm appr}}}
\newcommand{\opt}{_{\text{\rm opt}}}
\newcommand{\diag}{{\text{\rm diag}}}
\newcommand{\discr}{{\text{\rm discr}}}
\newcommand{\rank}{{\text{\rm rank}}}
\newcommand{\sgn}{{\text{\rm sgn}}}
\newcommand{\fl}{\text{\rm fl}}
\newcommand{\tensor}{\otimes}
\newcommand{\drond}{\partial}
\newcommand{\Hd}{{\cal H}_d}
\newcommand{\Pd}{{\cal P}_d}
\newcommand{\round}{\hbox{Round}}
\renewcommand{\Re}{\text{\rm Re}}
\renewcommand{\Im}{\text{\rm Im}}
\newcommand{\imag}{\hbox{im}}
\newcommand{\COMP}{\hbox{COMP}}
\newcommand{\PR}[2]{\left[\begin{array}{c}{#1}\\{#2}\ctrans\end{array}\right]}
\newcommand{\PDf}[2]{\left[\begin{array}{c}Df(#1)\\{#2}\ctrans\end{array}\right]}
\newcommand{\PV}[1]{\left[\begin{array}{c}{#1}\\0\end{array}\right]}
\newcommand{\GDf}[2]{{Df({#1})_{|#2}}}
\newcommand{\Df}[2]{\GDf{#1}{V({#2})}}
\newcommand{\DfI}[2]{\GDf{#1}{V({#2})}^{-1}}
\newcommand{\binomial}[2]{\left(\begin{array}{c}{#1}\\{#2}\end{array}\right)}
\newcommand{\macheps}{{\epsilon _m}}
\newcommand{\knorm}[1]{{\left \| {#1} \right \|_{\text{k}}}}
\newcommand{\fnorm}[1]{{\left \| {#1}\right  \|_{\text{\rm f}}}}
\newcommand{\kinner}[2]{{\left < {#1} , {#2} \right  >_{\text{k}}}}
\newcommand{\inner}[2]{{\left < {#1} , {#2} \right  >}}
\newcommand{\norm}[1] {{\left \| {#1} \right \|_2}}
\newcommand{\abs}[1] {{\left | {#1} \right |}}
\newcommand{\onenorm}[1]{{\left \| {#1} \right \|_1}}
\newcommand{\bignorm}[1]{{\left \| {#1} \right \|_2}}
\newcommand{\supnorm}[1]{{\left \| {#1} \right \|_{\infty}}}
\newcommand{\maxnorm}[1]{{\left \| {#1} \right \|_{\text{\rm max}}}}
\newcommand{\maxtwonorm}[1]{{\left \|{#1}\right \|_{\text{\rm max,2}}}}
\newcommand{\fmu}{{\mu_{\text{\rm f}}}}

\newcommand{\rem}[1]{{\par \tt #1}}
\newcommand{\ignore}[1]{{}}


\newcommand{\noteind}[2]{\@writefile{not}{\string{ {#1} & \text{#2} & \text{Page \pageref}}}}


\renewcommand{\paragraph}[1]{\medskip \par \noindent {\bf {#1} \/} }

\newcounter{linenumber}

\newenvironment{algorithm}
      { \medskip \centerline { {\bf Algorithm \ }}
        \begin {list}{\arabic{linenumber}}{\usecounter{linenumber}}
      }
      {  \end{list}  }

\newtheorem {main}        {Main Theorem}
\newtheorem {theorem}     {Theorem}
\newtheorem {corollary}   {Corollary}
\newtheorem {proposition} {Proposition}
\newtheorem {lemma}       {Lemma}
\newtheorem {claim}       {Claim} 
\newtheorem {remark}      {Remark} 

\theoremstyle {definition}

\newtheorem {definition}  {Definition} 
\newtheorem {problem}     {Problem} 

\theoremstyle {remark}
\newtheorem   {note}        {Note}


\newcommand{\glossaryentry}[2]{#1 & #2 \cr}

\title      {Unitary Invariance of the Kostlan norm \\
             (Linear Algebra proof)}
\author     {Gregorio Malajovich}
\address    {Departamento de Matematica Aplicada da UFRJ \\
             Caixa Postal 68530 \\ CEP 21945 \\ Rio de Janeiro \\ RJ \\
             BRASIL}
\email      {gregorio@@labma.ufrj.br}
\date       {February 4, 1994}


\begin{document}

\maketitle



Let $\Hd$ be the space of systems of $n$ homogeneous polynomials
of degree $d = (d_1, \dots , d_n)$ in variables $x_0, \dots , x_n$~,
with complex coefficients.
The {\em Kostlan norm} $\knorm{.}$ is defined in $\Hd$ as follows~:
$$
\knorm{F}^2 = \sum_i \knorm{F_i}^2
$$
\par
where, for any single polynomial $f$ of degree $d$ in variables
$x_0, \dots , x_n$, we set ~:
$$
\knorm{f}^2 = \sum_{|J| = d} {|f_J|^2 \over \binomial{d}{J}}
$$
\par
Above, $J$ are multi-indices, and ~:
$$
\binomial{d}{J} = {d ! \over J_0 ! J_1 ! \dots J_n !}
$$
\medskip
\par
We will give an easy proof of the Theorem :
{ \theorem [Kostlan]
           Let $F \in \Hd$.
           Then for any unitary automorphism $U$ of $\Bbb C ^{n+1}$,
           $\knorm{F} = \knorm{F \circ U}$.
           }
\par
This theorem was proven by Eric Kostlan in \cite{KOSTLAN}. I do not
have his paper, but I took a look once, and (if I remember correctly)
he gave a diferent proof.
\par
Unitary invariance of the Kostlan norm was extremely important to
the development of the complexity theory of solving systems of
multivariate polynomials (see e.g. Mike Shub and Steve Smale ~
\cite{BEZI}), since $\knorm{.}$ is the natural norm in $\Hd$.
\medskip
\par
We first prove the Lemma :
{ \lemma Let $f = \sum f_j x^{i-j}y^j$
   be a homogeneous polynomial of degree $i$
   in $x$ and $y$, with coefficients $f_j$ in a complex vector space $K$
   with Hermitian inner product $\inner{.}{.}$~.
   Let $\kinner{f}{\tilde f}$ denote~:
   $$
   \kinner{f}{\tilde f} \  = \sum_{0 \le j \le i}
       {\inner{f_j}{{\tilde f}_j} \over \binomial{i}{j}}
   $$
   \par
   Then for any $U \in U(2)$, $\knorm{f} = \kinner{f}{f}^{1 \over 2}
    = \kinner{f \circ U}{f \circ U}^{1 \over 2}
   = \knorm{f \circ U}$~.
   }

\medskip
\par
The Lemma implies the Theorem for $n=2$, by making $K = \Bbb C$ and
$\inner{w}{z} = w \bar z$. We first prove the Lemma. Then we will show that
the Lemma implies the Theorem in general.
\medskip
\par
{\bf Proof of the Lemma : }

We first show that $\knorm{.}$ is invariant under ordinary rotations
of the form~:
$$
U_t = \begin{pmatrix} \cos t & - \sin t \\ \sin t & \cos t \end{pmatrix}
$$
\par
Indeed, let $f_t = f \circ U_t$. It suffices to prove that for any $f$,
we have~:
$$
\Re \left( \kinner{f}{\dot f} \right) = 0
$$
\par
where $\dot f$ means ${\partial f_t \over \partial t}$ when
$t=0$~. Indeed, this will show that for any $t$,
$$
{\partial \over \partial t} \knorm{f_t}
=
2 \ \Re \left( \kinner{f}{\dot f} \right)
= 0
$$
\par
We write~:
$$
\dot f(0)
 =
 \sum_{0 \le j < i}
    f_j (i-j) x^{i-j-1} y^{j+1}
 \
 -
 \sum_{0 < j \le i}
    f_j j x^{i-j+1} y^{j-1}
$$
\par
Therefore,
$$
\kinner{f}{\dot f} =
 \sum_{0 \le j < i}
   { \inner{f_{j+1}}{f_j} (i-j)
   \over
   \binomial{i}{j+1}
   }
 \
 -
 \sum_{0 < j \le i}
   {
     \inner{f_{j-1}}{f_j} j
   \over
   \binomial{i}{j-1}
   }
$$
\par
We substitute $j$ by $j+1$ in the first sum and get~:
$$
\kinner{f}{\dot f} =
 \sum_{0 < j \le i}
   { \inner{f_j}{f_{j-1}} (i-j+1)
   \over
   \binomial{i}{j}
   }
 \
 -
 \sum_{0 < j \le i}
   {
     \inner{f_{j-1}}{f_j} j
   \over
   \binomial{i}{j-1}
   }
$$
$$
\kinner{f}{\dot f} = 2 i \Im \left(
\sum_{0 < j \le i}
{
j! i - j + 1 !
\over
i !
}
\inner{f_j}{f_{j-1}}
\right)
$$
\par
Therefore, $\kinner{f}{\dot f}$ is a pure imaginary, and $\knorm{f_t}$
does not depend on $t$. This proves that $\knorm{.}$ is
rotation-invariant. A general unitary transformation can be
represented a rotation times a complex
in the unit circle, times (eventually) permutation of variables.
This proves the Lemma.
\medskip
\par
{\bf Proof of the Theorem : }

We first prove that $\knorm{.}$ is invariant under (complex) Givens
rotations. A Givens rotation is a rotation in a plane generated
by two complex coordinates, and leaving all other coordinates
invariant. Without loss of generality,
we can show that fact for rotations of variables $x_0$ and $x_1$ only.
We write $f$ as :
$$
f(x) = \sum_{0 \le i \le d}
       \sum_{0 \le j \le i}
       {x_0}^{i-j} {x_1}^{j} f_{ij}(x_2, \dots , x_n)
$$
\par
It is easy to see that ~:
$$
\kinner{f}{\tilde f} =
  \sum_{0 \le i \le d}
  \sum_{0 \le j \le i}
  {
  \kinner{f_{ij}}{\tilde f_{ij}}
  \over
  {
  d !
  \over
  d-i ! i-j ! j !
  }
  }
=
  \sum_{0 \le i \le d}
  \sum_{0 \le j \le i}
  {
  \kinner{f_{ij}}{\tilde f_{ij}}
  \over
  \binomial{i}{j}
  \binomial{d}{i}
  }
$$
\par
According to the Lemma, for each $i$, the real part of the
sum in $j$ is invariant by unitary transforms of $x_0$ and $x_1$.
Therefore, $\Re(\kinner{.}{.})$ is invariant by unitary transforms of
$x_0$ and $x_1$. Hence, $\knorm{.}$ is invariant under (complex)
Givens rotations. We can use the well-known~:
\par
{\proposition Every element of $U(n+1)$ can be written as a product
of (complex) Givens rotations} and (eventually) a variable permutation.
\medskip
\par
It follows from the proposition that $\knorm{f}$ is $U(n+1)$~-invariant,
and the invariance Theorem is proved.
\medskip
\par
The proof of this proposition uses the same argument than the Givens $QR$
factorization. Namely, let A be a unitary transform.
By applying a variable permutation,
we can assume that $det A = +1$. Now we reproduce the
classical argument (See Golub and Van Loan \cite{GOLUB},
Algorithm 5.2.2 page 214 or Watkins \cite{WATKINS},
Theorem 3.2.9, page 143)~:
\medskip
\par
We assumed that $A^{(0)} = A \in SU(n+1)$~. There is a Givens rotation
$G^{(0)}$ changing only coordinates $n$ and $n+1$ such that the
matrix $A^{(1)} = G^{(0)} A^{(0)} $ verifies~:
$$
{A^{(1)}}_{n+1,1} = 0
$$
\par
Namely, we set~:
$$
c =
{
{
  \Bar { A^{(0)}}_{n+1,1}
     }
\over
\sqrt{
\abs{{A^{(0)}}_{n,1}}^2
+
\abs{{A^{(0)}}_{n+1,1}}^2
}}
$$
$$
s =
{
 {
 \Bar  {A^{(0)}}_{n,1}
     }
\over
\sqrt{
\abs{{A^{(0)}}_{n,1}}^2
+
\abs{{A^{(0)}}_{n+1,1}}^2
}}
$$
$$
G^{(0)} =
\begin{pmatrix}
 & I & &   &  \\
 &   & & c & s\\
 &   & &-s & c
\end{pmatrix}
$$
\medskip
\par
By the same procedure, we construct
$$
G^{(1)} =
\begin{pmatrix}
 & I & &   &   &\\
 &   & & c & s &\\
 &   & &-s & c &\\
 &   & &   &   & 1
\end{pmatrix}
$$
\par
such that $A^{(1)} = G^{(1)} A^{(0)}$ verifies~:
$$
{A^{(1)}}_{n,1}
=
{A^{(1)}}_{n+1,1}
=
0
$$
\par
and so on. We will then construct $A^{(n)} = \prod_{i=n-1}^0 G^{(i)} \  A^{(0)}$
such that ${A^{(n)}}_{i,1} = 0$ for $i > 1$ and ${A^{(n)}}_{1,1} = 1$~.
We can then construct a Givens rotation $G^{(n)}$~,
$$
G^{(n)} =
\begin{pmatrix}
 & I & &   &  \\
 &   & & c & s\\
 &   & &-s & c
\end{pmatrix}
$$
\par
such that $A^{(n+1)} = G^{(n)} A^{(n)}$ verifies
${A^{(n+1)}}_{n+1,2} = 0$~,
${A^{(n+1)}}_{i,1} = 0$ for $i > 1$ and ${A^{(n+1)}}_{1,1} = 1$
~.
By the same procedure as above, we obtain
$A^{(2n-1)} $ with all ${A^{(2n-1)}}_{i,j} = 0$ for $i>j$ and $j=1,2$~,
and ${A^{(2n-1)}}_{i,i} = 1$ for $i = 1,2$.
\medskip
\par
Continuing the same procedure, we finally get a matrix
$$
A^{\left( {n (n-1) \over 2 } \right)}
=
\prod_{i = {n (n-1) \over 2 } - 1}^0 G^{(i)} \ A^{(0)}
$$
\par
that is upper triangular and has only $1$'s in the diagonal.
Since $A^{\left( {n (n-1) \over 2 } \right)}$ is also a rotation
(an element of $SU(n+1)$~), it follows that it is precisely
the identity of ${\Bbb C}^{n+1}$~.
\par
Therefore, we can write~:
$$
A^{(0)}
=
\prod_{i=0}^{{n (n-1) \over 2 } - 1} {G^{(i)}}^{-1}
$$
\par
and $A$ is a product of Givens rotations. This concludes the
proof of the Proposition.


\begin {thebibliography}{10}

\bibitem{GOLUB}
Gene Golub and Charles Van Loan,
\newblock {\em Matrix Computations}, Second Edition.
\newblock The John Hopkins University Press, Baltimore and London, 1990.

\bibitem{KOSTLAN}
Eric Kostlan,
\newblock{\em Random polynomials and the statistical fundamental
          theorem of algebra},
\newblock Preprint, Univ. of Hawaii, 1987.

\bibitem{BEZI}
Michael Shub and Steve Smale,
\newblock On the Complexity of Bezout's Theorem I - Geometric aspects.
\newblock {\em Journal of the AMS}, {\bf 6}, 2, Apr 1993.

\bibitem{WATKINS}
David S. Watkins,
\newblock {\em Fundamentals of matrix computations},
\newblock John Wiley \& Sons, New York, 1991

\end {thebibliography}
\end {document}
