Let $(x_i)_{i=1}^N$ be a set of vectors in $\mathbb{R}^D$. Define the matrix $W \in \mathbb{R}^{N \times N}$ as:
$W_{ij} = \frac{\exp(-||x_i-x_j||^2)}{\sum_k \exp(-||x_i-x_k||^2)}$
i.e. row $i$ of $W$ is the output of a softmax, whose inputs are negative squared Euclidean distances between $x_i$ and each $x_j$. Hence $W$ is a (row-) stochastic matrix (i.e. rows sum to 1).
I would like to bound $||W||_2$, the spectral norm of $W$ i.e. the largest singular value.
One line of approach is to use the inequality $||W||_2 \leq \sqrt{||W||_1 ||W||_{\infty}}$ where $||W||_{\infty}$ is the maximum row sum, and $||W||_1$, the maximum column sum. Since $W$ is stochastic $||W||_{\infty}=1$. Hence upper bounding $||W||_1$ is sufficient.
$||W||_1 = \max_{j} \sum_i W_{ij} = \max_{j} \sum_i \frac{\exp(-||x_i-x_j||^2)}{\sum_k \exp(-||x_i-x_k||^2)}$
It is easy to see that $||W||_1 \leq N$, since $N$ is the sum of all entries of $W$. I'm wondering if the bound can be made tighter. Brute force calculus leads to a mess, and numerically optimising the inputs to maximise the column sum, I'm observing that the maximum column sum grows very slowly with $N$, at most a logarithmic rate. Can this be proved?