Positive definiteness of power of distance matrix 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!
 A: 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.
