\section{Introduction}
The $d$-th Hadamard power of a matrix is obtained by taking the $d$-th
power of each entry.  A kernel perceptron is a nonlinear classifier
that separates data in a feature space. 
In this note we discuss a relation between the rank of Hadamard powers of a matrix
and the shattering properties of kernel perceptrons with polynomial
kernel. More precisely, we consider Hadamard powers of the Gramian
matrix associated to a set of data vectors. If the rank is maximal,
then any separation of the data set can be classified by a polynomial
kernel perceptron of the corresponding degree. 
In this context we provide a new proof for the fact that any
Boolean function in $n$ variables can be realized by a kernel
perceptron with polynomial kernel of degree $n$. We compare our rank calculations to lower bounds
obtained quite recently in \cite{HornYang20}. 
Moreover, we show that generically
the rank of the $d$-th Hadamard power of  a matrix
$A\in\mathbb{R}^{n\times m}$ is
\begin{align}
  \label{eq:1}
  \min\left\{\binom{\operatorname{rank}
    A+d-1}{d},n,m\right\}\;.
\end{align}
Properties of Hadamard products and their applications have received attention over many
years, e.g.\ in \cite{Stya73, Ando79, HornJohn85, FiedMark88, HornJohn91,  Math92,
  Fali96}. A prominent result is Schur's product theorem \cite{Schu11}, which
states that the Hadamard product preserves definiteness. Definiteness,
rank, and
other properties of Hadamard powers have been discussed in
\cite{MarcFran92, BhatElsn07, FallJohn07, GuilKhar15, Jain17, BeltGuil19, HornYang20, Jain20, PanwRedd22}. Applications
of Hadamard products in artificial intelligence can be found in
\cite{Zhang20}. But to our knowledge, the relation of Hadamard powers
to polynomial kernel machines has not been accented so far, although
the field of machine learning is very active now. Concerning kernel
perceptrons, we largely follow
the presentation  in the monograph
\cite{SchoSmol02}. The kernelized approach, however, goes back to \cite{AizeBrav65} and
has been taken up e.g.\ in \cite{Anth95, CortVapn95}.\\
Our paper is structured as follows.
In the first section, we collect some facts on kernel perceptrons
and the associated dual optimization problem. In Section~\ref{sec:hadam-prod-polyn}, we introduce the Hadamard product and
Hadamard powers. These two topics are brought together in Section~\ref{sec:class-dich-with}, where we consider the realization of
Boolean functions. Here we have to compute the rank of Hadamard powers
of special matrices explicitly. In contrast to this, Section~\ref{sec:rank-hadamard-powers} is devoted to the generic case. We show
that for all matrices from an open and dense set these ranks equal \eqref{eq:1}.
\section{Kernel perceptrons}
\label{sec:kernel-perceptrons}
We collect basic facts from \cite{SchoSmol02}.
A symmetric mapping $k:\mathbb{R}^n\times
\mathbb{R}^n\to\mathbb{R}$ is called a positive kernel, if for any
$N\in \mathbb{N}$ with $N>0$ and any set of vectors
$x_1,\ldots,x_N\in\mathbb{R}^n$ the matrix
$K=\left(k(x_i,x_j)\right)_{i,j=1,\ldots N}\succeq 0$ is nonnegative
definite. In particular, the polynomial mappings
$(v,w)\mapsto (\langle v,w\rangle+c)^d$, with $c\ge 0$, $d\in\mathbb{N}$
and the standard scalar product $\langle\cdot,\cdot\rangle$ define
positive kernels. To simplify the notation, we only consider the case $c=0$, i.e.\
the kernels $k(v,w)=\langle v,w\rangle^d$. It is easy to transfer the discussion to the case $c>0$.

Let now a set of vectors $x_1,\ldots, x_m\in\mathbb{R}^n$ with labels
$y_1,\ldots,y_m\in\{\pm 1\}$  be given. 
A kernel perceptron is a classifier defined by its transfer function $f_p:\mathbb{R}^n\to\{\pm 1\}$ of
the form
\begin{align}\label{eq:decision_fct}
  f_p(x)&=\sigma\left(\sum_{i=1}^m \alpha_iy_i k(x_i,x) +b
          \right)\quad \text{with}\quad \sigma(z)=\left\{
  \begin{array}{rl}
    1,&z\ge 0\\-1,&z<0
  \end{array}\right.\;.
\end{align}
The task is to construct  the real parameters 
$b$ and $\alpha_i$, such that
\begin{align}\label{eq:task}
f_p(x_j)=y_j\text{ for all } j=1,\ldots,m\;.
\end{align}
\begin{thm}
  The given task is feasible, if and only if the constrained maximization
  problem
\begin{subequations}\label{eq:CMP}
  \begin{equation} \label{eq:CMP_target}
    \max_{a\in\mathbb{R}^m} \left(\|a\|_ 1-\frac12 \sum_{i,j=1}^ma_ia_jy_iy_j k(x_i,x_j)\right)
\end{equation}
\begin{equation}\label{eq:CMP_constraint}
  \text{subject to } \sum_{i=1}^m y_ia_i=0, a_1,\ldots,a_m\ge 0
\end{equation}
\end{subequations}
 
 
 
 
  has a solution. In this case $\alpha_i=a_i$
   for $i=1,\ldots,m$ and
   \begin{align*}
b=\frac12\left(\min_{\{j\;|\;y_j=1\}} \sum_{i=1}^m \alpha_iy_i k(x_i,x_j)+\max_{\{j\;|\;y_j=-1\}} \sum_{i=1}^m \alpha_iy_i k(x_i,x_j)\right)
   \end{align*}
   provide an optimal separation margin.
 \end{thm}
 \begin{proof}
 See \cite[Section 7.4]{SchoSmol02}.
\end{proof}
Let $y=[y_1,\ldots,y_m]$, $Y=\operatorname{diag}(y_1,\ldots,y_m)$ and
$K=\left(k(x_i,x_j)\right) _{i,j=1,\ldots m}$. Then for
$a\in\mathbb{R}^m$, we have
 \begin{align*}
    \sum_{i,j=1}^ma_ia_jy_iy_j k(x_i,x_j)&= a^TYKY a\;.
 \end{align*}
 With this notation we easily derive the following criterion.
\begin{cor}\label{cor:exists_perceptron}
  The constrained maximization
  problem \eqref{eq:CMP}  is infeasible, if and only if
 
  \begin{align}
    \label{eq:bad_a}
    \exists a\in\mathbb{R}_+^m\setminus\{0\}:  ya=0
   
    \text{ and } KYa=0\;.
  \end{align}
\end{cor}
\begin{proof}
 If $a$ satisfies \eqref{eq:bad_a}, then for all $t>0$ the vector $ta$
 satisfies the constraint \eqref{eq:CMP_constraint} while the target
 function in  \eqref{eq:CMP_target} simplifies to $\|ta\|_1=t\|a\|_1$.
 Since $\|a\|_1\neq 0$, there is no maximum.\\
 Conversely let $KYa\neq 0$ for all $a\neq 0$ satisfying
 \eqref{eq:CMP_constraint}. Since $K$ is nonnegative definite, also
 $a^TYKYa> 0$ and by compactness
 \begin{align}\label{eq:mu}
\mu=\min\{a^TYKYa\;\big|\; a\in\mathbb{R}_+^m,  ya=0
   
    \|a\|_1=1\}>0\;.
 \end{align}
 Hence, for all $a$ satisfying \eqref{eq:CMP_constraint} the target
 function in  \eqref{eq:CMP_target} is bounded by
 \begin{align*}
   \|a\|_1-\frac12a^TYKYa&\le \|a\|_1- \frac12\mu \|a\|_1^2 \;.
 \end{align*}
 Thus, if $a_0$ is a minimizer for \eqref{eq:mu}, then $a=\frac{a_0}\mu$
 solves \eqref{eq:CMP}. 
\end{proof}
\begin{ex}\label{ex:XOR}
  Let us illustrate this for the famous XOR-classification problem,
  where the vectors $x_i$ are given as the columns of the matrix
  $X=\left[
    \begin{array}{cccc}
      0&1&0&1\\0&0&1&1
    \end{array}
  \right]$ and the labels $y_i$ as the entries of the vector
  $y=\left[
    \begin{array}{cccc}
      -1&1&1&-1
    \end{array}
  \right]$.\\
  We compare the kernels $k(x,y)=\langle x,y\rangle ^d$ for $d=1$ and $d=2$.
  
  \begin{itemize}
  \item If $d=1$ then $KY=\left[
      \begin{smallmatrix}
        0&0&0&0\\
        0&1&0&-1\\
        0&0&1&-1\\
        0&1&1&-2
      \end{smallmatrix}
    \right]$ with $v=\left[
      \begin{smallmatrix}
        1\\1\\1\\1
      \end{smallmatrix}
    \right]\in\ker KY$. Since $yv=0$, this implies that
    the XOR function can not be realized by a classical perceptron.
    Note that here $\operatorname{rank} KY=2$.
    \item If $d=2$, then $KY=\left[
      \begin{smallmatrix}
        0&0&0&0\\
        0&1&0&-1\\
        0&0&1&-1\\
        0&1&1&-4
      \end{smallmatrix}
    \right]$. It is evident that $\operatorname{rank} KY=3$ and $\ker KY=\operatorname{span}\{ e_1\}$ with the
    first canonical unit vector $e_1$. Thus $KYv\neq 0$ for all
    $v\neq 0$ with $yv=0$. In fact, with $k(v,w)=\langle v,w\rangle^2$ the XOR-function is realized by
    \eqref{eq:decision_fct} with $\alpha_1=6$, $\alpha_2=\alpha_3=4$,
    $\alpha_4=2$,
    and $b=-1$. 
  \end{itemize}
\end{ex}
More generally, it is known that any Boolean function in $n$ variables
can be realized by a kernel perceptron with $k(v,w)=\langle
v,w\rangle^n$ (e.g.\ \cite{WangWill91}). In this note, we give a proof of this result following
the reasoning in the previous example, where we exploit properties of
the  Hadamard product and Hadamard powers.

\section{Hadamard products and powers}
\label{sec:hadam-prod-polyn}

For $A=\left(a_{ij}\right), B=\left(b_{ij}\right)\in \mathbb{R}^{n\times m}$ the Hadamard
product  is defined as the componentwise product $A\circ
B=\left(a_{ij}b_{ij}\right)$.  In the same way, we define the Hadamard
power $A^{\circ d}=\left(a_{ij}^d\right)$ for $d\in\mathbb{N}$, e.g.\
\cite{HornJohn85, HornJohn91}. The following simple identity for
rank-1 matrices can be found
e.g.\ in \cite{Stya73} or \cite[Fact 9.6.2]{Bern18}.
\begin{lemma}\label{lemma:Hadamard_mixed_product}
 If $u,w\in\mathbb{R}^n$, $v,z\in\mathbb{R}^m$ then
  \begin{align*}
   \left(uv^T\right)\circ \left(wz^T\right)&=(u\circ w)(v\circ z)^T\;.
  \end{align*}
\end{lemma}
By this lemma it follows easily that the Hadamard product preserves
nonnegative definiteness. Namely, if $A=A^T\in\mathbb{R}^{n\times n}$ and $B=B^T\in\mathbb{R}^{n\times n}$ are
nonnegative definite, they can be written as sums of rank-1 matrices,
i.e.\
\begin{align*}
  A\circ B&=\left(\sum_{i=1}^n a_ia_i^T\right)\circ \left(\sum_{j=1}^n
            b_jb_j^T\right)
  =\sum_{i,j=1}^n (a_i\circ b_j)(a_i\circ b_j)^T \succeq 0\;.
\end{align*}
This further implies, that the product of two positive kernels and any
natural power of a positive kernel  is again a positive kernel. \\
In Example~\ref{ex:XOR}, the rank of $K$ was essential. This motivates
us to study the rank of Hadamard powers of nonnegative definite
matrices. Some relations of this rank to the Kruskal rank and the Hadamard power rank of the
matrix have been reported in \cite{HornYang20}.
\begin{defi}
  Let $A\in\mathbb{R}^{n\times m}$. If $A$ possesses a zero column, then its
  \emph{Kruskal rank} $k_A$ is zero. Otherwise $k_A$ is defined as the
  largest positive integer $k$, such that any selection of $k$
  distinct columns of $A$  is linearly independent.\\
  If $\operatorname{rank} A\ge 2$, then the \emph{Hadamard power rank} $h_A$ of $A$ is the largest positive
  integer $h$, such that there exists a selection of $h$ distinct
  columns of $A$, which are pairwise linearly independent. If $\operatorname{rank}
  A<2$, then $h_A=\operatorname{rank} A$.
\end{defi}
With this notation, we can summarize \cite[Prop.~6 and Cor.~9]
{HornYang20} as follows.
\begin{prop}\label{prop:HornYang}
  Let $A\in\mathbb{R}^{n\times n}$ with $n\ge 2$ be nonnegative definite.
  \begin{itemize}
  \item[(a)]  $k_A\ge 2$ $\iff$ $\forall d\ge n-1: A^{\circ d}\succ 0$
  \item[(b)] $\forall d\ge \max\{h_A-1,1\}: \operatorname{rank} A^{\circ d}=h_A$.
  \end{itemize}
\end{prop}

\section{Realization of Boolean functions with polynomial kernels}
\label{sec:class-dich-with}
Let us return to the realization of Boolean functions in $n$
variables by a kernel perceptron. For $j=0,\ldots, 2^n-1$ let $x_j=\left[
  \begin{array}{c}
    x_{1,j}\\\vdots\\ x_{n,j}
  \end{array}
\right]\in\{0,1\}^n$ contain a binary representation of
$j$, i.e.\
\begin{align}\label{eq:defXn}
  j&=\sum_{\ell=1}^n x_{\ell,j}2^{\ell-1}\;.
\end{align}
We say that in the binary representation of $j$ the $\ell$-th bit is
\emph{active}, if $x_{\ell,j}=1$.\\
A Boolean function $f:\{0,1\}^n\to \{\pm 1\}$ in $n$ variables is defined by a selection of
labels  $y_j\in\{\pm 1\}$ for $j=0,\ldots, 2^n-1$. The function $f$ is
called a \emph{dichotomy}, since it defines a partition
of $\{0,1\}^n$ in $X_+=\{x\in\{0,1\}^n\;\big|\; f(x)=1\}$ and
$X_-=\{x\in\{0,1\}^n\;\big|\; f(x)=-1\}$.  The goal is to find a
kernel perceptron that can be used to classify $X_+$ and $X_-$.\\
If $k(v,w)=\langle v,w\rangle^d$ for $d\in\mathbb{N}$, then let 
\begin{align}\label{eq:defKd}
K_d&=\Big(k(x_i,x_j)\Big)_{i,j=1}^{2^n-1}=\Big(\langle
     x_i,x_j\rangle^d\Big)_{i,j=1}^{2^n-1}=(X^TX)^{\circ d}=K_1^{\circ
     d}\;.
\end{align}
Here, obviously, $K_1=X^TX$. Since $x_0=0$, the first column and row of $K_d$ vanishes for
all $d>0$, i.e.\
$K_de_1=0$ and also $K_d\operatorname{diag}(y)e_1=0$. By Corollary~\ref{cor:exists_perceptron} and the argument in Example~\ref{ex:XOR}, there exists a kernel perceptron
\begin{align*}
  f_p(x)&=\sigma\left(\sum_{i=1}^m \alpha_iy_i \langle x_i,x\rangle^d +b \right)\;,
\end{align*}
such that $f_p(x_j)=y_j$ for all $j=0,\ldots,2^n-1$, if $\operatorname{rank} K=2^n-1$.
\begin{ex}\label{ex:Bcasen3}
  For $n=3$ we have
                     
    \begin{align*}
X^T= \left[
    \begin{array}{ccc}
     0&0&0\\
     1&0&0\\
     0&1&0\\
     1&1&0\\
     0&0&1\\
     1&0&1\\
     0&1&1\\
     1&1&1
    \end{array}
\right],\quad
   K_d= \left[
    \begin{array}{cccccccc}
     0&0&0&0&0&0&0&0\\
     0&1&0&1&0&1&0&1\\
     0&0&1&1&0&0&1&1\\
     0&1&1&2^d&0&1&1&2^d\\
     0&0&0&0&1&1&1&1\\
     0&1&0&1&1&2^d&1&2^d\\
     0&0&1&1&1&1&2^d&2^d\\
     0&1&1&2^d&1&2^d&2^d&3^d
    \end{array}
\right]
  \end{align*}
  with $\operatorname{rank} K_1=3$, $\operatorname{rank} K_2=6$ and $\operatorname{rank} K_3=7$.\\
   Because of the zero column in all $K_d$, the rank cannot increase further.
Note also that the Hadamard power rank $h_{K_1}$ equals
$7$, since the last seven columns of $K_1$ are pairwise linearly
independent. According to Proposition~\ref{prop:HornYang} we only know
that $K_1^{\circ p}=7$ for all $p\ge 6$. Our observation that
already  $\operatorname{rank} K_1^{\circ 3}=7$ thus is stronger.
We will show that $\operatorname{rank} K_1^{\circ n}=2^n-1=h_{K_1}$ for all $n$. 
\end{ex}
For $A=X^TX$ we can compute the ranks of the Hadamard powers exactly. 
\begin{thm}\label{thm:main}
  Let $n\in\mathbb{N}$ and $X=(x_{\ell,j})\in \mathbb{R}^{n\times
    (2^n-1)}$ be defined according to \eqref{eq:defXn}.  Then 
  \begin{align*}
\operatorname{rank} (X^TX)^{\circ d}&=\left\{
                        \begin{array}{ll}\displaystyle
                          \sum_{p=1}^d\binom{n}{p},&\text{ if }d\le n\;,\\[5mm]
                           \displaystyle  2^n-1,&
                                \text{ if } d\ge n\;.
                        \end{array}\right.
  \end{align*}
\end{thm}
\begin{proof}
Let us write $X^T=(\beta_{j,\ell}) = [B_1,\ldots, B_n]$, with
$B_\ell\in\mathbb{R}^{2^n}$. The $j$-th entry $\beta_{j,\ell}=x_{\ell,j}$ of $B_\ell$
equals $1$, if and only if the $\ell$-th bit is active in the binary
representation of the number $j$ as in \eqref{eq:defXn}. In particular,
\begin{align}\label{eq:BellUj}
\beta_{j,\ell}&=\left\{
            \begin{array}{ll}
              1,& \text{ if }j=2^{\ell-1}\\
              0,&\text{ if } j<2^{\ell-1}
            \end{array}\right. .
\end{align}
For $j=1,\ldots,2^{n-1}$, we define the sets
\begin{align*}
  U(j)=\{ u\in\mathbb{R}^{2^n}\;\big|\; u_{j+1}=1\text{ and } u_i=0\text{
  for } i\le j\}\;.
\end{align*}
Obviously, vectors from different $U(j)$ are linearly independent.
From \eqref{eq:BellUj}, it follows that $B_\ell\in U(2^{\ell-1})$,
as is illustrated for $n=3$ in Example~\ref{ex:Bcasen3}. 
We now consider
Hadamard products of columns $B_{\ell_1},\ldots,
B_{\ell_p}$. If $\ell_1=\ell_2$, then $B_{\ell_1}\circ
B_{\ell_2}=B_{\ell_1}$. Therefore let now $\ell_1<\ldots<\ell_p$.
Note that this product corresponds to a logical AND
operation: The $j$-th entry of
$B_{\ell_1}\circ \cdots\circ  B_{\ell_p}$ is non-zero, if and only if
in the  binary representation  \eqref{eq:defXn} of $j$ the bits
$\ell_1$ to $\ell_p$ are active. Clearly, the smallest number $j$ with
this property is $j=2^{\ell_1-1}+\cdots+2^{\ell_p-1}$. Hence
\begin{align*}
 B_{\ell_1}\circ \cdots\circ  B_{\ell_p}\in U\left(2^{\ell_1-1}+\cdots+2^{\ell_p-1}\right)\;,
\end{align*}
 and the set
\begin{align*}
  \{B_{\ell_1}\circ \cdots\circ
  B_{\ell_p}\;\big|\; 1\le p\le n, 1\le\ell_1<\ldots<\ell_p\le n\}
\end{align*}
is linearly independent. Recall also that
\begin{align}\label{eq:repeating_ell}
\{\tilde\ell_1,\ldots,\tilde\ell_{\tilde p}\}=\{\ell_1,\ldots,\ell_p\}
  \quad \Rightarrow\quad B_{\ell_1}\circ \cdots\circ
  B_{\ell_p} =B_{\tilde\ell_1}\circ \cdots\circ
  B_{\tilde\ell_p}\;
\end{align}
We apply these observations to the Hadamard powers of $X^TX$. By Lemma~\ref{lemma:Hadamard_mixed_product} we have
\begin{align*}
  \left(\sum_{j=1}^n B_j B_j^T\right)^{\circ 2}&=\left(\sum_{i=1}^n B_i
  B_i^T\right)\circ \left(\sum_{j=1}^n B_j B_j^T\right)
  =\sum_{i,j=1}^n (B_iB_i^T)\circ (B_jB_j^T) \\&=\sum_{i,j=1}^n
  (B_i\circ B_j)(B_i\circ B_j)^T\;.
\end{align*}
Inductively, it follows that
\begin{align*}
  \left(\sum_{j=1}^n B_j B_j^T\right)^{\circ d}&=
   \sum_{\ell_1,\ldots,\ell_d=1}^n (B_{\ell_1}\circ\cdots \circ B_{\ell_d})(B_{\ell_1}\circ\cdots \circ B_{\ell_d})^T\;.
\end{align*}
By \eqref{eq:repeating_ell} the image of this matrix is 
\begin{align*}
\operatorname{Im}  \left(\sum_{j=1}^n B_j B_j^T\right)^{\circ d} 
 
 
 
  &=\bigoplus_{p=1}^d \operatorname{span}\{B_{\ell_1}\circ \cdots\circ
  B_{\ell_p}\;\big|\;
1\le \ell_1<\ldots<\ell_p\le n \}\;.
\end{align*}
Since each of the direct summands has dimension $\binom{n}{p}$, the
proof is complete.
\end{proof}
\begin{cor}
  Any Boolean function in $n$ variables can be realized by a
  perceptron with polynomial kernel of degree $n$. 
\end{cor}
\begin{proof}
 Let $K=K_n=(X^TX)^{\circ n}$. Since $\operatorname{rank} K=2^n-1$, the null space of
 $KY$ only contains scalar multiples $a=te_1$ of the first canonical unit
 vector. But then $ya=ty_1\neq 0$, if $a\neq 0$, i.e.\
 \eqref{eq:bad_a} does not hold.
\end{proof}
\section{The rank of Hadamard powers in the
  generic case}
\label{sec:rank-hadamard-powers}
For the matrix $X$ containing the binary representations of all
numbers $0,1,\ldots,2^n-1$ we have computed the ranks of the Hadamard
powers of $X^TX$ explicitly and found them to be larger than the lower bounds in
Proposition~\ref{prop:HornYang}. Generically, we can expect even
higher ranks. To make this precise, we now analyze sets of vectors whose Hadamard products are in general position.
\begin{defi}
  A set $\mathcal{S}\subset\mathbb{R}^n$ is in
  \emph{general position}, if any subset of $\mathcal{S}$ with at most
  $n$ elements is linearly independent.
\end{defi}
For a given matrix $B\in\mathbb{R}^{n\times m}$ with columns
$B_1,\ldots,B_m$ we define the sets of
Hadamard products of  given order $d\in\mathbb{N}$ and of arbitrary order as
\begin{align*}
  \mathcal{H}_B^d
  =\{B_{\ell_1}\circ \cdots\circ
  B_{\ell_d}\;\big|\;  1\le\ell_1\le\ell_2\le\ldots\le \ell_d\le m\}\text{ and } \mathcal{H}_B=\bigcup_{d\in\mathbb{N}} \mathcal{H}_B^d \;.
\end{align*}
In the following example, we construct $B\in\mathbb{R}^{n\times m}$
such that $\mathcal{H}_B$ is in general position.
\begin{ex}\label{ex:B_gp}
  Let $p_j\in\mathbb{N}$ denote the $j$-th prime number, i.e.\  $(p_1,p_2,p_3,\ldots)=(2,3,5,\ldots)$ and consider
  \begin{align*}
    B&=[B_1,\ldots,B_m]=(b_{ij})_{i=1,\ldots,n}^{j=1,\ldots,m}=\left[
       \begin{array}{ccc}
         1&\cdots&1\\
         e^{\sqrt{p_1}}&&e^{\sqrt{p_m}}\\
         \vdots&\ddots&\vdots\\
         e^{(n-1)\sqrt{p_1}}&\cdots&e^{(n-1)\sqrt{p_m}}
       \end{array}
\right]\;.
  \end{align*}
 For $d\in\mathbb{N}$ and a given $d$-tuple $(\ell_1,\ldots,\ell_{d})$ we set
 $\alpha_{\ell_1,\ldots,\ell_{d}}=\exp\left(\sum_{j=1}^d\ell_j\sqrt{p_{\ell_j}}\right)$.
 Since the numbers $\sqrt{p_j}$ are rationally independent, it follows
 that the mapping $(\ell_1,\ldots,\ell_{d})\mapsto
 \alpha_{\ell_1,\ldots,\ell_{d}}$ is injective. Hence, for different
 $d$ and different
 $(\ell_1,\ldots,\ell_{d})$, the vectors 
  \begin{align*}
    B_{\ell_1}\circ \cdots\circ
  B_{\ell_d}&=\left[
                                  \begin{array}{ccccc}
                                    1&\alpha_{\ell_1,\ldots,\ell_{d}}&\alpha_{\ell_1,\ldots,\ell_{d}}^2&\cdots&\alpha_{\ell_1,\ldots,\ell_{d}}^{n-1}
                                  \end{array}
\right]^T
  \end{align*}
  constitute different columns of an $n\times n$ Vandermonde matrix.
  It is well-known that such a matrix is nonsingular. Hence
  $\mathcal{H}_B$ is in general position. 
\end{ex}
In fact, $\mathcal{H}_B$ is in general position for most matrices in
the following sense.
\begin{lemma}\label{lemma:Hsetsgeneric}
  Consider the normed matrix space $\mathbb{R}^{n \times m}$ with
  $n,m\ge 2$.
  \begin{itemize}
  \item[(a)] Let $N\in\mathbb{N}$. The set of matrices $B\in
    \mathbb{R}^{n \times m}$, for which $\bigcup_{d=1}^N\mathcal{H}_B^d$ is in
    general position is open and dense in $\mathbb{R}^{n \times m}$.
  \item[(b)] The set of matrices $B\in
    \mathbb{R}^{n \times m}$, for which $\mathcal{H}_B$ is not in
    general position is of the first category (in the sense of Baire).
  \end{itemize}
\end{lemma}
\begin{proof}
(a) We first fix
$d\in\mathbb{N}$.  Let $X\in \mathbb{R}^{n \times m}$. To test
whether $\mathcal{H}^d_{X}$ is in general position amounts to
considering determinants of a finite number of $n\times n$
matrices with pairwise different columns from $\mathcal{H}^d_{X}$. Each of these
determinants is a multivariate polynomial in the entries of $X$ and
thus continuous in $X$. If therefore all the determinants are nonzero
for the given $X$, then the same holds on an open neighbourhood of
$X$. This proves the openness statement. To prove denseness, choose a
matrix $B$ such that $\mathcal{H}^d_{B}$ is in general position
(e.g.\ as in Example~\ref{ex:B_gp}) and consider
$X^{\epsilon}=X+\epsilon B$ with $\epsilon>0$. As before, we consider
the determinants of all $n\times n$ matrices   with pairwise different
columns from $\mathcal{H}^d_{X+\epsilon B}$. Each of
these determinants is a polynomial in $\epsilon$, and all these
polynomials are nonzero, because $\mathcal{H}^d_{B}$ is in
general position. Hence there exists an $\epsilon_0>0$, such that all
the determinants are nonzero for $0<\epsilon<\epsilon_0$. Thus
$\mathcal{H}^d_{X+\epsilon B}$ is in general position for small $\epsilon>0$. This proves
denseness.\\
It follows that the set of matrices $B\in
    \mathbb{R}^{n \times m}$ for which $\bigcup_{d=1}^N\mathcal{H}_B^d$ is in
    general position is a finite intersection of open dense subsets
    and therefore open and dense itself.\\
 (b) The complement of an open and dense set is nowhere dense.
 Therefore the set of matrices $B\in
    \mathbb{R}^{n \times m}$, for which $\mathcal{H}_B$ is not in
    general position, is a countable union of nowhere dense sets. 
    By definition, the set is thus of the first category.
\end{proof}
We will also need the following general statement.
\begin{lemma}\label{lemma:factor_generic}
  For arbitrary $m,n$ let $\mathcal{S}_{n,m}$  be an open and dense subset of
  $\mathbb{R}^{n\times m}$. Consider $M_r=\{ A\in\mathbb{R}^{n\times
    m}\;\big|\; \operatorname{rank} A=r\}$ with the topology inherited from
  $\mathbb{R}^{n\times m}$. Then
  \begin{align*}
    \{ BC\;\big|\; B\in \mathcal{S}_{n,r}, C\in \mathcal{S}_{r,m}\} 
  \end{align*}
  is open and dense in $M_r$.
\end{lemma}
\begin{proof}
If $A\in M_r$, then it possesses a nonsingular $r\times r$ submatrix.
With suitable permutation matrices, we have $P_1^TAP_2=\left[
  \begin{array}{cc}
    A_{11}&A_{12}\\A_{21}&A_{22}
  \end{array}
\right]$ with $A_{11}\in\mathbb{R}^{r\times r}$ nonsingular. Since
$\operatorname{rank} A=r$, there exists an $R\in\mathbb{R}^{r\times(m-r)}$, such that $\left[
  \begin{array}{c}
    A_{12}\\A_{22}
  \end{array}
\right]=\left[
  \begin{array}{c}
    A_{11}\\A_{21}
  \end{array}
\right]R$. Obviously, $R=A_{11}^{-1}A_{12}$, i.e.\
\begin{align}\label{eq:CTB_factor}
  A&
       BC\quad\text{ with }\quad B=P_1\left[
  \begin{array}{c}
    A_{11}\\A_{21}
  \end{array}
\right]T, \; C=T^{-1}\left[
  \begin{array}{cc}
    I&A_{11}^{-1}A_{12}
  \end{array}
\right]P_2^T\;,
\end{align}
where $T\in\mathbb{R}^{r\times r}$ is an arbitrary nonsingular matrix.
Moreover, all possible factorizations are of this form.\\
Hence, if $A=BC$ with $B\in \mathcal{S}_{n,r}$, $C\in
\mathcal{S}_{r,m}$, then $B$ and $C$ are as in \eqref{eq:CTB_factor}
with a given $T=T_A$. Consider now $\tilde A$ with $\operatorname{rank}
\tilde A=r$ and $\|\tilde A-A\|<\epsilon$. Then also $\tilde A=\tilde
B\tilde C$ with $\tilde B=P_1\left[
  \begin{array}{c}
    \tilde A_{11}\\\tilde A_{21}
  \end{array}
\right]T_A$ and $\tilde C=T_A^{-1}\left[
  \begin{array}{cc}
    I&\tilde A_{11}^{-1}\tilde A_{12}
  \end{array}
\right]P_2^T$. For sufficiently small $\epsilon>0$, it follows that
$\tilde B\in \mathcal{S}_{n,r}$ and $\tilde C\in
\mathcal{S}_{r,m}$. This proves openness.\\
Denseness is immediate, because in any neighbourhood of a matrix $A=BC$ there exists a
matrix $\tilde A=\tilde B\tilde C$ with $\tilde B\in \mathcal{S}_{n,r}$ and $\tilde C\in
\mathcal{S}_{r,m}$.
\end{proof}
\begin{thm}\label{thm:generic}
  There exists an open and dense subset
  $\mathcal{A}\subset\mathbb{R}^{n\times m}$  such that for
  $A\in\mathcal{A}$ and all $d\in\mathbb{N}$ the rank of the $d$-th
  Hadamard power equals
  \begin{align}\label{eq:Hadamard_rank_formula}
    \operatorname{rank} A^{\circ d} &=\min\left\{\binom{\operatorname{rank} A+d-1}{d},n,m\right\}\;.
  \end{align}
\end{thm}
\begin{proof}
If $\operatorname{rank} A=0$ or $\operatorname{rank} A=1$, then $ \operatorname{rank} A^{\circ
  d} =\operatorname{rank} A$ for all $d=1,2,\ldots$. This
is consistent with the convention that $\binom{d-1}{d}=0$ and
$\binom{d}{d}=1$.\\
From now on let $\operatorname{rank} A\ge 2$ and consider a factorization $A=BC^T$, where $B=[B_1,\ldots,B_r]\in\mathbb{R}^{n\times r}$ and $C=[C_1,\ldots,C_r]\in
\mathbb{R}^{m\times r}$.  As in the proof of Theorem~\ref{thm:main}, we have
\begin{align*}
  A^{\circ d}&=\sum_{\ell_1,\ldots,\ell_d=1}^r (B_{\ell_1}\circ\cdots \circ B_{\ell_d})(C_{\ell_1}\circ\cdots \circ C_{\ell_d})^T\;.
\end{align*}
By the Lemmas~\ref{lemma:Hsetsgeneric} and \ref{lemma:factor_generic}
there exists an open and dense set $\mathcal{A}$, such that for
$A\in\mathcal{A}$ we can further make the following assumption: For all $d< \min\{n,m\}$ and all $d$-tuples
$1\le\ell_1\le\ell_2\le\ldots\le \ell_d\le r$ the vectors $
B_{\ell_1}\circ\cdots \circ B_{\ell_d}\in\mathbb{R}^n$ and the vectors $ C_{\ell_1}\circ\cdots \circ C_{\ell_d}\in\mathbb{R}^m$
are  in general position. Therefore as long as $\operatorname{rank} A^{\circ d}<
\min\{n,m\}$ it equals the
number of $d$-tuples
$(\ell_1,\ldots,\ell_{d})$ with $1\le\ell_1\le\ell_2\le\ldots\le
\ell_d\le r$. 
Choosing such a $d$-tuple is an instance of unordered sampling without replacement.
It is well-known, (e.g.\ \cite[Thm.\ 2.1]{Pish14}) that the number of
choices equals $\binom{r+d-1}{d}$.\\
Since $\binom{r+d-1}{d}\ge \binom{d+1}{d}=d+1$, for $d\ge \min\{n,m\}$
the rank of $A^{\circ d}$ is guaranteed to be maximal and we do not need
the assumption on the general position for these $d$. Therefore
\eqref{eq:Hadamard_rank_formula} holds for all $A\in\mathcal{A}$ and
all $d\in\mathbb{N}$.
\end{proof}
\begin{remark}
  In the proof, we have used the bound $\binom{r+d-1}{d}\ge d+1$,
  which is only sharp for $r=2$. For larger $r$ and a given $n$ it is useful to find a
  small $d$ satisfying $\binom{r+d-1}{d}\ge n$. 
  Note that
  \begin{align*}
    \binom{r+d-1}{d}&=\frac{\prod_{j=1}^{r-1}(d+j)}{(r-1)!}\ge \frac{(d+1)^{r-1}}{(r-1)!}\;.
  \end{align*}
  Hence, it suffices to choose $d\ge \sqrt[r-1]{n(r-1)!}-1$.
\end{remark}
We now interpret a matrix  $X\in\mathbb{R}^{n\times m}$ as a
set of $m$ sample vectors in $\mathbb{R}^n$.
\begin{cor} Let $m\ge n$.
  There is an open and dense subset
  $\mathcal{X}\subset\mathbb{R}^{n\times m}$, such that for all
  $X\in\mathcal{X}$, all choices of  labels $y_j\in\{-1,1\}$,
  $j=1,\ldots,m$,  and all
  $d$ satisfying $\binom{n+d-1}{d}\ge m$, there exists a
  decision function  \eqref{eq:decision_fct} with
  $k(v,w)=\langle v,w\rangle^d$ solving the task \eqref{eq:task}. 
\end{cor}
\begin{proof}
  Let $\mathcal{X}=\{X\in\mathbb{R}^{n\times m}\;\big|\;
  \binom{n+d-1}{d}\le m \;\Rightarrow\;
  \mathcal{H}_X^d\text{ is in general position}\}$. By  Lemma~\ref{lemma:Hsetsgeneric}, the set $\mathcal{X}$ is open and dense in
  $\mathbb{R}^{n\times m}$. In particular $\operatorname{rank} X=n$ for
  $X\in\mathcal{X}$. Therefore, as in the proof of Theorem~\ref{thm:generic}, it follows that
  \begin{align*}
  K_d&=  (X^TX)^{\circ d}=\sum_{\ell_1,\ldots,\ell_d=1}^r (x_{\ell_1}\circ\cdots \circ x_{\ell_d})(x_{\ell_1}\circ\cdots \circ x_{\ell_d})^T
  \end{align*}
  is nonsingular, if $\binom{n+d-1}{d}\ge m$. The assertion now
  follows from Corollary~\ref{cor:exists_perceptron}.
\end{proof}
\begin{remark}
  Usually, with a positive kernel $k$, one associates a reproducing
  Hilbert space $\mathcal{R}_k$ as the feature space. The previous result is consistent
  with  $\dim\mathcal{R}_k=\binom{n+d-1}{d}$ for
  $k(\cdot,\cdot)=\langle\cdot,\cdot\rangle^d$, cf.\
  \cite{SchoSmol02}.
  One also says that every $X\in\mathcal{X}$ is shattered by the set
  of kernel perceptrons with this $k$.
\end{remark}
\begin{ex}
  From Section~\ref{sec:class-dich-with} recall the matrix $X\in\mathbb{R}^{n\times m}$ of Boolean vectors,
  where $m=2^n$. We have shown that this set of vectors is shattered
  by polynomial kernel perceptrons of degree $d=n$. For arbitrarily
  small perturbations of $X$ it suffices to choose the minimal
  $d=d_n$, so that $\binom{n+d-1}{d}\ge 2^n$. For instance, we have
  $d_{10}=5$, $d_{20}=8$, $d_{40}=14$, $d_{80}=26$, $d_{160}=50$.
\end{ex}
\section{Conclusion}
\label{sec:conclusion}
The main goal of this note was to point out a relation between kernel
perceptrons with polynomial kernel and the rank of Hadamard powers. 
This relation provided us with a new way of deriving some known
results on the capacity of such perceptrons. Moreover, we computed the
generic rank of Hadamard powers directly without resorting to abstract
results on algebraic varieties. 
