I have a matrix whose entries are powers of Hamming distances between binary vectors:
$a_{ij} = s^{ d(x_i,x_j) }$
where $0\le s\le 1$ and $x_i$ an $n$-dimensional binary vector and $d$ is the Hamming distance (number of differences between the vectors). Can I conclude that the matrix $A=\{a_{ij}\}$ is positive (semi)definite? Equivalently, is the function $K(x,y)=s^{d(x,y)}$ positive definite? I suppose this is trivial and the examples I can write down suggest positive-definiteness, but I cannot find a way to prove this.
The closest I have found are statements that $s^{n-d(x,y)}$ is positive definite.
Update: This paper http://ti.arc.nasa.gov/m/pub-archive/558h/0558%20(Macready).pdf treats the exact function I am interested in as a kernel satisfying positive definiteness. I have emailed the author but the address is no longer valid.
Update: Of course, Hamming distance is the same as square Euclidean distance, given the patterns are binary… so any results on square Euclidean distance is welcome!
Best Answer
As you have mentioned, since the data points are binary vectors, Hamming distance coincides with squared Euclidean norm. If we denote $\alpha=-\log s>0$, then $a_{ij}=\exp\left(-\alpha\|x_i-x_j\|_2^2\right)$.
It follows that the matrix $A$ is positive definite when all data points are distinct (otherwise $A$ is positive semidefinite). This is a direct application of Schoenberg's interpolation theorem (see chapter 15 of A Course in Approximation Theory by Cheney and Light or sec. 2.5 of this book chapter, for instance): the radial basis function $\phi(y) = \exp(-\alpha y)$ is completely monotone on $[0,\infty)$, therefore the function $\phi(\|\cdot\|_2^2)$ is strictly positive definite.
Remark. Before you edited your question, I only considered the Hamming distance between 0-1 vectors as a 1-norm but didn't realise that it is the squared Euclidean norm. When it is viewed as a 1-norm, the problem is more difficult. On $\mathbb R^n$, the kernel function $\exp\left(-\alpha\|\cdot\|_1\right)$ is known to be strictly conditionally positive definite of order one, but I am not sure if it is strictly positive definite. For more details, see chapter 10 of Fasshauer's Meshfree Approximation Methods with MATLAB.