Minimum supports of functions on the Hamming graphs with spectral constrains

Alexandr Valyuzhenich, Konstantin Vorob'ev

Published 2018-07-24Version 1

We study functions defined on the vertices of the Hamming graphs $H(n,q)$. The adjacency matrix of $H(n,q)$ has $n+1$ distinct eigenvalues $n(q-1)-q\cdot i$ with corresponding eigenspaces $U_{i}(n,q)$ for $0\leq i\leq n$. In this work, we consider the problem of finding the minimum possible support (the number of nonzeros) of functions belonging to a direct sum $U_i(n,q)\oplus U_{i+1}(n,q)\oplus\ldots\oplus U_j(n,q)$ for $0\leq i\leq j\leq n$. For the case $n\geq i+j$ and $q\geq 3$ we find the minimum cardinality of the support of such functions and obtain a characterization of functions with the minimum cardinality of the support. In the case $n<i+j$ and $q\geq 4$ we also find the minimum cardinality of the support of functions, and obtain a characterization of functions with the minimum cardinality of the support for $i=j$, $n<2i$ and $q\geq 5$. In particular, we characterize eigenfunctions from the eigenspace $U_{i}(n,q)$ with the minimum cardinality of the support for cases $i\le \frac{n}{2}$,$q\ge 3$ and $i> \frac{n}{2}$,$\,q\ge 5$.